数据结构-线性表-单向和双向循环链表及习题课.课件.ppt

1、线性表线性表(List)小结和作业小结和作业双向循环链表双向循环链表习题讲解习题讲解单向循环链表单向循环链表一元多项式一元多项式单向循环链表单向循环链表定义：最后一个结点的指针不是空指针，而是指向了头结点。La1a2a3L逻辑形态：单向循环链表单向循环链表差异：1、判断空表的条件：L-next=NULL变为L-next =L2、判断最后一个数据元素的条件由p-next=NULL 改变为p-next=LInitListLStatus InitList(LinkList &L)node=(LNode *) malloc(sizeof(LNode);if(!node) return(OVERFLOW

2、);L=node;node-next=L;return(OK);ListLength1、p指向头结点, j=02、如果p-next != L，j+, p-next3、重复2，直到 p为空， j即为长度。a1a2a3LListLengthint ListLength(LinkList L)count=0;p=p-next;count+;return(count);p=L;while( p-next)count=0;p=p-next;count+;return(count);p=L;while( p-next!=L)GetItem1、p指向头结点2、重复p=p-next操作 i 次3、p指向了第i

3、个元素pa1a2a3L单向循环链表单向循环链表a1a2a3L尾指针：a1a2a3L头指针：单向循环链表单向循环链表a1a2a3A将循环单链表A的尾和B的头相连，构成一个新的循环单链表，由B指向新表尾b1b2b3BA-next=q-next;q=B-next; B-next=A-nextfree(q); A=NULL;q双向链表双向链表一、作用：方便定位一个结点的前驱结点和后继结点二、结点的形式ai三、C语言描述typedef struct DuLNode ElemType data; struct DuLNode *prior; struct DuLNode *next; DuLNode；双向

4、链表双向链表五、逻辑形态四、头指针的描述typedef 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(OVERFLOW);node-prior=node-next=NULL;L=node;LListLeng

5、th1、p指向头结点, j=02、如果p-next不为空，j+, p=p-next3、重复2，直到 p-next为空， j即为长度。a2a3a1LListLength(讨论讨论)1、p指向头结点, j=02、如果p-prior不为空，j+, p=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;wh

6、ile( p-prior)ListInsert逻辑结构的变化 , (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-next i-1次，使得p指向第 i-1 个结点3、申请一个新结点s，调整s、第i-1和第i个结点的指针ListInsert找到第i-1个结点的代码是：p=L; j=0;while(jnext;j

7、+ListInsert生成一个新结点存放数据元素e 的代码是：s =(DuLNode *) malloc(sizeof(DuLNode);if(!s) return(OVERFLOW);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

8、+1, , an) , (a1, , ai-1, ai+1, , an)逻辑结构的变化：存储结构的变化：ListDeleteai-1aiai+1p-next = p-next-next;p-next-prior = p;pai-1qq=p-next;ListDelete1、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(讨

9、论讨论)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双向循环链表双向循环链表-Deletep-next = p-next-next;p-next-prior =

10、 p;a2a3a1Lai-1pai-1aiai+1线性表的应用线性表的应用-一元多项式一元多项式p = (p0, p1, ，pn)但是对于形如但是对于形如: : S(x) = 1 + 3x10000 2x20000nnxpxpxppxp+=.)(2210 稀疏一元多项式稀疏一元多项式 一般情况下的一元稀疏多项式可写成： p(x) = p1xe1 + p2xe2 + + pmxem其中：pi 是指数为ei 的项的非零系数， 0 e1 e2 em = n可以下列线性表表示：(p1, e1), (p2, e2), , (pm,em)稀疏一元多项式稀疏一元多项式 p(x) = 7x3 - 2x12 -

11、 8x999例如例如: :( (7, 3), (-2, 12), (-8, 999)稀疏一元多项式的实现稀疏一元多项式的实现typedef struct / 项项的表示 float coef; / 系数系数 int expn; / 指数指数 ElemType; typedef LinkList polynomial; / 用带表头结点的有序链表表示多项式一元多项式的操作一元多项式的操作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 习题

12、讲解习题讲解-2.21(-2.21(方法一方法一) )2.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 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.l

13、ength -i;L.elemL.length - i=tmp;ai an-i+1i=1,length/2ElemType tmp;习题讲解习题讲解-2.21(-2.21(方法二方法二) )2.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-2i=1, 2, 3j=n, n-1,习题讲解习题讲解-2.21-2.21void reverse(SqList &L)if(L.length=1

14、)return;for(i=1, j=L.length; 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

15、,ai+1while(q)p-next=t;t=p, p=q, q=p-next;L-next-next=NULL;L-next=p;习题讲解习题讲解- -2.22( 扩展扩展)双向循环链表?a2a3a1LL习题讲解习题讲解- -2.22( 扩展扩展)a2a3a1Lpqpqpqpqp-next=p-prior;p-prior=q;p=q;q=p-next;p=L;q=p-next;习题讲解习题讲解- -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