1、双向链表双向链表线性表线性表(List)部分操作的实现部分操作的实现小结和作业小结和作业双向循环链表双向循环链表习题讲解习题讲解复习复习一元多项式一元多项式复习复习-单链表单链表a1a2a3LL逻辑形态空链表复习复习-循环单链表循环单链表a1a2a3L尾指针：a1a2a3L头指针：L双向链表双向链表一、作用：方便定位一个结点的前驱结点和后继结点二、结点的形式ai三、C语言描述typedef struct DuLNode ElemType data;struct DuLNode *prior;struct DuLNode *next;DuLNode；双向链表双向链表五、逻辑形态四、头指针的描述t
2、ypedef struct DuLNode*DuLinkList;La2a3a1L部分操作的实现部分操作的实现InitList(&L)ListInsert(&L,i,e)ListDelete(&L,i,&e)ListLength(L)InitListStatus InitList(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
3、-next3、重复2，直到 p-next为空，j即为长度。a2a3a1LListLength(讨论讨论)1、p指向头结点,j=02、如果p-prior不为空，j+,p-prior3、重复2，直到 p-prior为空，j即为长度。a2a3a1LListLengthint 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)ListInsert逻辑结构的变化 ,(a1,ai-1,ai,
4、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-next i-1次，使得p指向第 i-1 个结点3、申请一个新结点s，调整s、第i-1和第i个结点的指针ListInsert找到第i-1个结点的代码是：p=L;j=0;while(jnext;j+ListInsert生成一个新结点存放数据元素e 的代码是：s=(DuLNode*)malloc(sizeof(DuLNode);if(!s)
5、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),(a1,ai-1,ai+1,an)逻辑结构的变化：存储结构的变化：ListDelete(讨论讨论)ai-1aiai+1p-next=p-next-next;p-next-prior=p;p
6、ai-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个结点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、每个结点的pri
7、or域构成了另一个循环单链表逻辑形态La2a3a1L双向循环链表双向循环链表-Insertai-1aiepsai-1ais-next=p-next;s-prior=p;p-next=s;s-next-prior=s;a2a3a1L双向循环链表双向循环链表-Deletep-next=p-next-next;p-next-prior=p;a2a3a1Lai-1pai-1aiai+1线性表的应用线性表的应用-一元多项式一元多项式nnnxpxpxppxp.)(2210p=(p0,p1,，pn)但是对于形如但是对于形如:S(x)=1+3x10000 2x20000 稀疏一元多项式稀疏一元多项式 一般情况
8、下的一元稀疏多项式可写成：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;/用带表头结点的有序链表表示多项式一元多项式的
9、操作一元多项式的操作AH=1-3x6+7x12BH=-x4+3x6-9x10+8x14-3 67 12AH 3 6-9 108 14BH-1 41 0 1 0CH-1 4-9 107 128 14 习题讲解习题讲解-2.21-2.212.21 逆置顺序表a1 a2 a3 a4 an-3 an-2 an-1 anL.elemL.lengthL.listsizean an-1 an-2 an-3 a4 a3 a2 a1L.elemL.lengthL.listsizea1 ana2an-1a3an-2ai an-i+1i=1,length/2习题讲解习题讲解-2.21-2.21void revers
10、e(SqList&l)if(L.length=1)return;for(i=1;inext=t，t=p，p=q，q=p-next5、重复执行，直到q为空指针La1a2ptq6、L-next-next=NULL,L-next=p;习题讲解习题讲解-2.22(-2.22(方法一方法一)1、如果表中只有一个结点，不处理2、如果表是空表，不处理LL习题讲解习题讲解-2.22(-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,a
11、i+1while(q)p-next=t;t=p,p=q,q=p-next;L-next-next=NULL;L-next=p;习题讲解习题讲解-2.22(方法二方法二)a1a2a3LLpsucca1psucca2p succa3p习题讲解习题讲解-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(扩展扩展)双向循环链表?a2a3a1LL习题讲解习题讲解-2.22(扩展扩展)a2a3a1Lpqpqpqpqq=p-next;p-next=p-prior;p-prior=q;习题讲解习题讲解-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.8，2.32
