线性表双向链表和习题课课件

,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,双向链表,线性表,(List),部分操作的实现,小结和作业,双向循环链表,习题讲解,复习,一元多项式,双向链表线性表(List)部分操作的实现小结和作业双向循环链,复习-单链表,a,1,a,2,a,3,L,L,逻辑形态,空链表,复习-单链表a1a2a3LL逻辑形态空链表,复习-循环单链表,a,1,a,2,a,3,L,尾指针：,a,1,a,2,a,3,L,头指针：,L,复习-循环单链表a1a2a3L尾指针：a1a2a3L头指针：,双向链表,一、作用：方便定位一个结点的前驱结点和后继结点,二、结点的形式,a,i,三、C语言描述,typedef struct DuLNode,ElemType data;,struct DuLNode *prior;,struct DuLNode *next;,DuLNode；,双向链表一、作用：方便定位一个结点的前驱结点和后继结点二、结,双向链表,五、逻辑形态,四、头指针的描述,typedef struct DuLNode*DuLinkList;,L,a,2,a,3,a,1,L,双向链表五、逻辑形态四、头指针的描述typedef str,部分操作的实现,InitList(&L),ListInsert(&L,i,e),ListDelete(&L,i,&e),ListLength(L),部分操作的实现InitList(&L)ListInsert(,InitList,Status InitList(DuListLink&L),node=(DuLNode*)malloc(sizeof(DuLNode);,return(OK);,if(!node)return(ERROR);,node-prior=node-next=NULL;,L=node;,L,InitListStatus InitList(DuList,ListLength,1、p指向头结点,j=0,2、如果p-next不为空，j+,p-next,3、重复2，直到 p-next为空，,j,即为长度。,a,2,a,3,a,1,L,ListLength1、p指向头结点,j=02、如果p-,ListLength(,讨论,),1、p指向头结点,j=0,2、如果p-prior不为空，j+,p-prior,3、重复2，直到 p-prior为空，,j,即为长度。,a,2,a,3,a,1,L,ListLength(讨论)1、p指向头结点,j=02、如,ListLength,int ListLength(DuLinkList L),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,),ListLengthint ListLength(DuLin,ListInsert,逻辑结构的变化,(a,1,a,i-1,a,i,a,n,),(a,1,a,i-1,e,a,i,a,n,),存储结构的变化,ListInsert逻辑结构的变化,ListInsert,a,i-1,a,i,e,s-next=p-next;s-prior=p;,p-next=s;,s-next-prior=s;,p,s,a,i-1,a,i,ListInsertai-1aies-next=p-,ListInsert,1、p指向头结点,分析,：,2、执行p=p-next i-1次，使得p指向第 i-1 个结点,3、申请一个新结点s，调整s、第i-1和第i个结点的指针,ListInsert1、p指向头结点分析：2、执行p=p-,ListInsert,找到第i-1个结点的代码是：,p=L;j=0;,while(jnext;,j+,ListInsert找到第i-1个结点的代码是：p=L;j,ListInsert,生成一个新结点存放数据元素e 的代码是：,s=(DuLNode*)malloc(sizeof(DuLNode);,if(!s)return(ERROR);,s-data=e;,ListInsert生成一个新结点存放数据元素e 的代码是：,ListInsert,s-next=p-next;s-prior=p;,p-next=s;,s-next-prior=s;,ListInserts-next=p-next;,ListInsert(,讨论,),a,2,a,3,a,1,L,e,s,s-next=p-next;s-prior=p;,p-next=s;,s-next-prior=s;,i=1?,i=length+1?,ListInsert(讨论)a2a3a1Less-next,ListDelete(,讨论,),(a,1,a,i-1,a,i,a,i+1,a,n,),(a,1,a,i-1,a,i+1,a,n,),逻辑结构的变化：,存储结构的变化：,ListDelete(讨论)(a1,ai-1,a,ListDelete(,讨论,),a,i-1,a,i,a,i+1,p-next=p-next-next;,p-next-prior=p;,p,a,i-1,q,q=p-next;,ListDelete(讨论)ai-1aiai+1p-nex,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,ListDelete(讨论)1、p指向头结点q=p-n,ListDelete(,讨论,),a,2,a,3,a,1,L,p-next=p-next-next;,p-next-prior=p;,a,i-1,a,i,a,i+1,p,a,i-1,i=1?,i=length?,ListDelete(讨论)a2a3a1Lp-next=,双向循环链表,1、每个结点的next域构成了一个循环单链表,2、每个结点的prior域构成了另一个循环单链表,逻辑形态,L,a,2,a,3,a,1,L,双向循环链表1、每个结点的next域构成了一个循环单链表2、,双向循环链表-Insert,a,i-1,a,i,e,p,s,a,i-1,a,i,s-next=p-next;s-prior=p;,p-next=s;,s-next-prior=s;,a,2,a,3,a,1,L,双向循环链表-Insertai-1aiepsai-1ais-,双向循环链表-Delete,p-next=p-next-next;,p-next-prior=p;,a,2,a,3,a,1,L,a,i-1,p,a,i-1,a,i,a,i+1,双向循环链表-Deletep-next=p-next,线性表的应用-一元多项式,p=(p,0,p,1,，p,n,),但是对于形如:,S(x)=1+3x,10000,2x,20000,线性表的应用-一元多项式p=(p0,p1,，p,稀疏一元多项式,一般情况下的一元稀疏多项式可写成：,P,n,(x)=p,1,x,e1,+p,2,x,e2,+p,m,x,em,其中：p,i,是指数为e,i,的项的非零系数，,0 e,1,e,2,e,m,=n,可以下列线性表表示,：,(p,1,e,1,),(p,2,e,2,),(p,m,e,m,),稀疏一元多项式 一般情况下的一元稀疏多项式可写成：可以下列,稀疏一元多项式,P,999,(x)=7x,3,-2x,12,-8x,999,例如:,(7,3),(-2,12),(-8,999),稀疏一元多项式 P999(x)=7x3-2x12-,稀疏一元多项式的实现,typedef struct,/,项,的表示,float,coef;/,系数,int,expn;/,指数,ElemType,;,typedef,LinkList polynomial;,/用带表头结点的,有序链表,表示多项式,稀疏一元多项式的实现typedef struct,一元多项式的操作,AH,=1-3,x,6,+7,x,12,BH,=-,x,4,+3,x,6,-9,x,10,+8,x,14,-3 6,7 12,AH,3 6,-9 10,8 14,BH,-1 4,1 0,1 0,CH,-1 4,-9 10,7 12,8 14,一元多项式的操作AH=1-3x6+7x12-3,习题讲解-2.21,2.21 逆置顺序表,a,1,a,2,a,3,a,4 ,a,n-3,a,n-2,a,n-1,a,n,L.elem,L.length,L.listsize,a,n,a,n-1,a,n-2,a,n-3,a,4,a,3,a,2,a,1,L.elem,L.length,L.listsize,a,1,a,n,a,2,a,n-1,a,3,a,n-2,a,i,a,n-i+1,i=1,length/2,习题讲解-2.212.21 逆置顺序表a1,习题讲解-2.21,void reverse(SqList&l),if(L.length=1)return;,for(i=1;inext=t，t=p，p=q，q=p-next,5、重复执行，直到q为空指针,L,a,1,a,2,p,t,q,6、L-next-next=NULL,L-next=p;,习题讲解-2.22(方法一)1、p指向要修改指针的结点，初始,习题讲解-2.22(方法一),1、如果表中只有一个结点，不处理,2、如果表是空表，不处理,L,L,习题讲解-2.22(方法一)1、如果表中只有一个结点，不处理,习题讲解-2.22(方法一),void reverse(LinList&L),if(!L-next|!L-next-next)return;/空表或单元素,t=L,p=t-next,q=p-next;/t,p,q分别指向a,i-1,a,i,a,i+1,while(q),p-next=t;,t=p,p=q,q=p-next;,L-next-next=NULL;,L-next=p;,习题讲解-2.22(方法一)void reverse(Lin,习题讲解-,2.22(方法二),a,1,a,2,a,3,L,L,p,succ,a,1,p,succ,a,2,p,succ,a,3,p,习题讲解-2.22(方法二)a1a2a3LLpsucca,习题讲解-,2.22(方法二),void reverse(LinkList&L),/逆置带头结点的单链表 L,p=L-next;L-next=NULL;,while(p),succ=p-next;/succ,指向*p的后继,p-next=L-next;,L-next=p;/*p插入在头结点之后,p=succ;,习题讲解-2.22(方法二)void reverse(Li,习题讲解-,2.22(扩展),双向循环链表?,a,2,a,3,a,1,L,L,习题讲解-2.22(扩展)双向循环链表?a2a3a1L,习题讲解-,2.22(扩展),a,2,a,3,a,1,L,p,q,p,q,p,q,p,q,q=p-next;,p-next=p-prior;,p-prior=q;,习题讲解-2.22(扩展)a2a3a1Lpqpqpqpqq,习题讲解-,2.22(扩展),void reverse(DuLinkList&L),/逆置带头结点的单链表 L,p=L;q=p-next;,while(q!=L),p-next=p-prior;,p-prior=q;,p=q;,q=p-next;,习题讲解-2.22(扩展)void reverse(Du,小 结,双向循环链表,双向链表,由于结构的不合理，使用的较少,小 结双向循环链表 双向链表 由于结构的不合理，使用的较少,作业,作业：,2.8，2.32,作业作业：2.8