数据结构与算法(Python语言描述)课件3

线性表的链式存储•用一组地址任意的存储单元存放线性表中的数据元素，结点动态生成，利用指示元素位置的指针表示逻辑关系•几种形式：–单链表、循环链表、双向链表、双向循环链表链式存储•每个结点包括数据域和指向链表中下一个结点的指针。单链表a1a2a3∧L头结点首元素结点typedefstructLNode{ElemTypedata;//数据域structLNode*next;//指针域}LNode,*LinkList;LinkListL;//L为单链表的头指针单链表的表示datanextvoidListInit(LinkList&L){//初始化L=(LNode*)malloc(sizeof(LNode));L-next=NULL;}单链表的操作La1a2a5∧La3a4p=L-next;while(p!=NULL){第p指向的结点操作；p=p-next;//指针前行}单链表的遍历a1a2a5∧La3a4p=L-next;j=1;//可替换为：p=L;j=0;while(p!=NULL&&ji){p=p-next;j++}if(p!=NULL)对第i个结点操作；else第i个结点不存在；确定链表中的第i个元素位置StatusGetElem_L(LinkListL,inti,ElemType&e){//L是带头结点的链表的头指针，以e返回第i个元素//确定第i个元素的位置p=L-next;j=1;while(p&&ji){p=p-next;++j;}if(!p||ji)//第i个元素不存在returnERROR;e=p-data;//取得第i个元素returnOK;}算法时间复杂度为:O(ListLength(L))StatusListInsert_L(LinkList&L,inti,ElemTypee){//L为带头结点的单链表的头指针，在第i个结点之前插入元素e//确定第i-1个元素的位置p=L;j=0;while(p&&ji-1){p=p-next;++j;}if(!p||ji-1)returnERROR;生成结点插入在p之后；returnOK;}算法的时间复杂度为:O(ListLength(L))//生成新结点s=(LinkNode*)malloc(sizeof(LNode));s-data=e;s-next=p-next;//先连后！p-next=s;//再改前！生成结点插入在p之后eai-1aiai-1spq=p-next;p-next=q-next;e=q-data;free(q);删除指针p指向的结点ai-1aiai+1ai-1pqvoidClearList(&L){//将单链表重新置为一个空表while(L-next){p=L-next;L-next=p-next;free(p);}}算法时间复杂度：O(ListLength(L))voidCreateList_L(LinkList&L,intn){//逆序输入n个数据元素，建立带头结点的单链表//先建立一个带头结点的单链表L=(LinkList)malloc(sizeof(LNode));L-next=NULL;for(i=n;i0;--i){p=(LinkList)malloc(sizeof(LNode));scanf(&p-data);//输入元素值p-next=L-next;L-next=p;//插入L之后}}算法的时间复杂度为:O(Listlength(L))•和单链表在搜索操作上的差别:–单链表：while(p!=NULL){…}–循环链表：while(p!=L){…}循环链表a1a2…...antypedefstructDuLNode{ElemTypedata;//数据域structDuLNode*prior;//指向前驱的指针域structDuLNode*next;//指向后继的指针域}DuLNode,*DuLinkList;双向链表priordatanexta1a2…...ans-next=p-next;p-next=s;s-next-prior=s;s-prior=p;双向链表的插入ai-1aiepsai-1aip-next=p-next-next;p-next-prior=p;双向链表的删除ai-1aiai+1pai-1双向循环链表空表非空表a1a2…...an