5线性表-双向链表和习题课.ppt

《5线性表-双向链表和习题课.ppt》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、双向链表线性表(List)部分操作的实现小结和作业双向循环链表习题讲解复习一元多项式复习-单链表a1a2a3LL逻辑形态空链表复习-循环单链表a1a2a3L尾指针：a1a2a3L头指针：L双向链表一、作用：方便定位一个结点的前驱结点和后继结点二、结点的形式ai三、C语言描述typedefstructDuLNode{ElemTypedata;structDuLNodeprior;structDuLNodenext;}DuLNode；双向链表五、逻辑形态四、头指针的描述typedefstructDuLNodeDuLinkList;La2a3a1L部分操作的实现I

2、nitList(&L)ListInsert(&L,i,e)ListDelete(&L,i,&e)ListLength(L)InitListStatusInitList(DuListLink&L){node=(DuLNode)malloc(sizeof(DuLNode));}return(OK);if(!node)return(ERROR);node->prior=node->next=NULL;L=node;LListLength1、p指向头结点,j=02、如果p->next不为空，j++,p->next3、重复2，直到p->next为空，j即为长度。a2a

3、3a1LListLength(讨论)1、p指向头结点,j=02、如果p->prior不为空，j++,p->prior3、重复2，直到p->prior为空，j即为长度。a2a3a1LListLengthintListLength(DuLinkListL){count=0;p=p->next;count++}}return(count);p=L;while(p->next){count=0;p=p->prior;count++}}return(count);p=L;while(p->prior){ListInsert逻辑结构的变化→

4、e>,(a1,…,ai-1,ai,…,an)→(a1,…,ai-1,e,ai,…,an)存储结构的变化ListInsertai-1aies->next=p->next;s->prior=p;p->next=s;s->next->prior=s;psai-1aiListInsert1、p指向头结点分析：2、执行p=p->nexti-1次，使得p指向第i-1个结点3、申请一个新结点s，调整s、第i-1和第i个结点的指针ListInsert找到第i-1个结点的代码是：p=L;j=0;while(jnext;j++}ListInse

5、rt生成一个新结点存放数据元素e的代码是：s=(DuLNode)malloc(sizeof(DuLNode));if(!s)return(ERROR);s->data=e;ListInserts->next=p->next;s->prior=p;p->next=s;s->next->prior=s;ListInsert(讨论)a2a3a1Less->next=p->next;s->prior=p;p->next=s;s->next->prior=s;i=1?i=length+1???ListDelete(讨论)(a1,…,ai-1,ai,ai+1,…,an)

6、,(a1,…,ai-1,ai+1,…,an)逻辑结构的变化：存储结构的变化：ListDelete(讨论)ai-1aiai+1p->next=p->next->next;p->next->prior=p;pai-1qq=p->next;ListDelete(讨论)1、p指向头结点q=p->next;p->next=p->next->next;p->next->prior=p;e=q->data;free(q);2、执行i-1次p=p->next，p指向了第i-1个结点3、q=p->next,q指向第i个

7、结点4、修改第i-1个和第i个结点的指针5、释放结点qListDelete(讨论)a2a3a1Lp->next=p->next->next;p->next->prior=p;ai-1aiai+1pai-1i=1?i=length???双向循环链表1、每个结点的next域构成了一个循环单链表2、每个结点的prior域构成了另一个循环单链表逻辑形态La2a3a1L双向循环链表-Insertai-1aiepsai-1ais->next=p->next;s->prior=p;p->next=s;s->next->prior=s;a2a3a1L双向循环链表-Delet

8、ep->next=p->next->next;p->