《线性表双向链表和习题课课件.ppt》由会员分享，可在线阅读，更多相关《线性表双向链表和习题课课件.ppt（43页珍藏版）》请在三一办公上搜索。
1、双向链表,线性表(List),部分操作的实现,小结和作业,双向循环链表,习题讲解,复习,一元多项式,复习-单链表,逻辑形态,空链表,复习-循环单链表,尾指针：,头指针：,双向链表,一、作用：方便定位一个结点的前驱结点和后继结点,二、结点的形式,三、C语言描述,typedef struct DuLNode ElemType data;struct DuLNode*prior;struct DuLNode*next;DuLNode；,双向链表,五、逻辑形态,四、头指针的描述,typedef struct DuLNode*DuLinkList;,部分操作的实现,InitList(&L),ListIn
2、sert(&L,i,e),ListDelete(&L,i,&e),ListLength(L),InitList,Status InitList(DuListLink&L),node=(DuLNode*)malloc(sizeof(DuLNode);,return(OK);,if(!node)return(ERROR);,node-prior=node-next=NULL;,L=node;,ListLength,1、p指向头结点,j=0,2、如果p-next不为空，j+,p-next,3、重复2，直到 p-next为空，j即为长度。,ListLength(讨论),1、p指向头结点,j=0,2、如
3、果p-prior不为空，j+,p-prior,3、重复2，直到 p-prior为空，j即为长度。,ListLength,int ListLength(DuLinkList L),ListInsert,逻辑结构的变化,(a1,ai-1,ai,an)(a1,ai-1,e,ai,an),存储结构的变化,ListInsert,s-next=p-next;s-prior=p;p-next=s;s-next-prior=s;,p,s,ListInsert,1、p指向头结点,分析：,2、执行p=p-next i-1次，使得p指向第 i-1 个结点,3、申请一个新结点s，调整s、第i-1和第i个结点的指针,L
4、istInsert,找到第i-1个结点的代码是：,p=L;j=0;,while(ji-1),p=p-next;,j+,ListInsert,生成一个新结点存放数据元素e 的代码是：,s=(DuLNode*)malloc(sizeof(DuLNode);,if(!s)return(ERROR);,s-data=e;,ListInsert,s-next=p-next;s-prior=p;p-next=s;s-next-prior=s;,ListInsert(讨论),s,s-next=p-next;s-prior=p;p-next=s;s-next-prior=s;,i=1?i=length+1?,
5、ListDelete(讨论),(a1,ai-1,ai,ai+1,an),(a1,ai-1,ai+1,an),逻辑结构的变化：,存储结构的变化：,ListDelete(讨论),p-next=p-next-next;p-next-prior=p;,p,q,q=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个结点,4、修改第i-1个和第i个结点的指针,5、释放结点q,Li
6、stDelete(讨论),L,p-next=p-next-next;p-next-prior=p;,p,i=1?i=length?,双向循环链表,1、每个结点的next域构成了一个循环单链表,2、每个结点的prior域构成了另一个循环单链表,逻辑形态,双向循环链表-Insert,s-next=p-next;s-prior=p;p-next=s;s-next-prior=s;,双向循环链表-Delete,p-next=p-next-next;p-next-prior=p;,线性表的应用-一元多项式,p=(p0,p1,，pn),但是对于形如:,S(x)=1+3x10000 2x20000,稀疏一元
7、多项式,一般情况下的一元稀疏多项式可写成：Pn(x)=p1xe1+p2xe2+pmxem其中：pi 是指数为ei 的项的非零系数，0 e1 e2 em=n,可以下列线性表表示：(p1,e1),(p2,e2),(pm,em),稀疏一元多项式,P999(x)=7x3-2x12-8x999,例如:,(7,3),(-2,12),(-8,999),稀疏一元多项式的实现,typedef struct/项的表示 float coef;/系数 int expn;/指数 ElemType;,typedef LinkList polynomial;/用带表头结点的有序链表表示多项式,一元多项式的操作,AH=1-3
8、x6+7x12BH=-x4+3x6-9x10+8x14,-3 6,7 12,AH,3 6,-9 10,8 14,BH,-1 4,习题讲解-2.21,2.21 逆置顺序表,a1 ana2an-1a3an-2,ai an-i+1i=1,length/2,习题讲解-2.21,void reverse(SqList&l),if(L.length=1)return;,for(i=1;i=L.length%2;i+),tmp=L.elemi-1;,L.elemi-1=L.elemL.length-i;,L.elemL.length-i=L.elemi-1;,ai an-i+1i=1,length/2,习题
9、讲解-2.22(方法一),2.22 逆置线性链表,习题讲解-2.22(方法一),(a1,a2,ai-1,ai,ai+1,an-1,an),(an,an-1,ai+1,ai,ai-1,a2,a1),ai的前驱变成了后继，后继变成了前驱,该问题的核心是要修改数据元素的邻里关系,习题讲解-2.22(方法一),1、p指向要修改指针的结点，初始时是a1,2、q指向p的后继？,否则，修改p的指针，链就断了,3、t指向p的前驱？,在新表中t是p的后继,4、p-next=t，t=p，p=q，q=p-next,5、重复执行，直到q为空指针,6、L-next-next=NULL,L-next=p;,习题讲解-2.
10、22(方法一),1、如果表中只有一个结点，不处理,2、如果表是空表，不处理,L,习题讲解-2.22(方法一),void reverse(LinList&L),if(!L-next|!L-next-next)return;/空表或单元素,t=L,p=t-next,q=p-next;/t,p,q分别指向ai-1,ai,ai+1,while(q),p-next=t;,t=p,p=q,q=p-next;,L-next-next=NULL;,L-next=p;,习题讲解-2.22(方法二),a1,a2,a3,L,p,a1,a2,a3,习题讲解-2.22(方法二),void reverse(LinkList,习题讲解-2.22(扩展),双向循环链表?,习题讲解-2.22(扩展),L,q=p-next;p-next=p-prior;p-prior=q;,习题讲解-2.22(扩展),void reverse(DuLinkList,小 结,双向循环链表,双向链表,由于结构的不合理，使用的较少,作业,作业：2.8，2.32,
