线性表双向链表与习题课.ppt

An Introduction to Database Systenm 双向链表 习题讲解-2.21 void reverse(SqList l){ if(L.length=1)return; for(i=1;i=L.length%2;i++){ tmp=L.elem[i-1]; L.elem[i-1]=L.elem[L.length -i]; L.elem[L.length - i]=L.elem[i - 1]; } } ai ?? an-i+1 i=1,…,length/2 习题讲解-2.22(方法一) L a1 a2 … an 2.22 逆置线性链表 L an an-1 … a1 习题讲解-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为空指针 L a1 a2 p t q 6、L-next-next=NULL, L-next=p; 习题讲解-2.22(方法一) 1、如果表中只有一个结点，不处理 2、如果表是空表，不处理 L 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 L p ? succ a1 ? p succ a2 p succ a3 p 习题讲解-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( 扩展) 双向循环链表??? a2 a3 a1 L L 习题讲解-2.22( 扩展) a2 a3 a1 L p q p q p q p q q=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 * 线性表(List) 部分操作的实现 小结和作业 双向循环链表 习题讲解 复习 一元多项式 复习-单链表 a1 a2 a3 L L 逻辑形态 空链表 复习-循环单链表 a1 a2 a3 L 尾指针： a1 a2 a3 L 头指针： L 双向链表 一、作用：方便定位一个结点的前驱结点和后继结点 二、结点的形式 ai 三、C语言描述 typedef struct DuLNode { ElemType data; struct DuLNode *prior; struct DuLNode *next; } DuLNode； 双向链表 五、逻辑形态 四、头指针的描述 typedef struct DuLNode * DuLinkList; L a2 a3 a1 L 部分操作的实现 InitList(L) ListInsert(L, i, e) ListDelete(L, i, e) ListLength(L) InitList Status InitLi