第04讲表3.ppt

* * 授课者：章 英 E-mail：walking7876@ Essential of Lecture Four ： 一、循环链表 二、双向链表 三、静态链表 四、链表的应用 难点 定义：整个链表形成一个环，从表中任一结点出发均可找到表中其它结点。 特点： （1）表中最后一个结点的指针指向第一个结点或表头结点（如有表头结点的话）。 （2）循环链表的运算与线性链表基本一致。但两者判断是否到表尾的条件不同。 一、 循环链表 Circular Linked List head head 非空表 空表 rear rear 两个单循环链表（用尾指针表示）的链接示意图 ra rb p ① ② ③ 思考: 如何将其合并? 定义：单链表的每个结点再增加一个指向其前趋的指针域 prior，这样形成的链表有两条不同方向的链，称之为双（向）链表。 二、 双向链表 Double Linked List 特点： 双链表一般也由头指针head唯一确定。 每一结点均有： 数据域（data） 左链域（prior）指向前趋结点. 右链域（next）指向后继。 是一种对称结构（既有前趋，又有后继）。 前驱方向 ? ? 后继方向 prior data next 结点结构 typedef struct Node { DataType data; struct Node * prior, * next; }DLNode, *DoubleList; L L 非空表 空表 p == p-prior-next == p-next-prior 插入 5 9 7 p q ① ③ ④ ② q-prior = p-prior q-next=p p-prior-next = q p-prior=q 删除 5 9 7 p-prior-next = p-next p-next-prior = p-prior 存储结构的实现 #define MAXSIZE　1000 typedef struct { ElemType data; int next; }SLinkList[MAXSIZE]; 三、 静态链表 实例： -1 WANG 7 ZHENG 6 WU 5 ZHOU 4 LI 3 SUN 2 QIAN 1 ZHAO 5 SHI -1 WANG 7 ZHENG 6 WU 8 ZHOU 4 LI 3 SUN 2 QIAN 1 ZHAO 0 1 2 3 4 5 6 7 8 9 10 0 1 2 3 4 5 6 7 8 9 10 四、 链表的应用 1、假设一个单循环链表，其结点含有三个域pre、data、link。其中data为数据域；pre为指针域，它的值为空指针（NULL）；link为指针域，它指向后继结点。请设计算法，将此表改成双向循环链表。 【西安电子科技大学 1999软件 五（10分）】 void StoDouble(LinkedList La) { while(La-link-pre==NULL) { La-link-pre=La; La=La-link; } } 算法中没有设置变量记住单循环链表的起始结点，至少省去了一个指针变量。当算法结束时，la恢复到指向刚开始操作的结点，这是本算法的优点所在。 2、一元稀疏多项式以单循环链表按降幂排列，结点有三个域，系数域coef、指数域exp和指针域next；现对链表求一阶导数，链表的头指针为ha，头结点的exp域为-1。 【南京理工 2000 （10分）】 void derivative(DLinkedList ha) { q=ha; pa=ha-next; while( (1) ) { if( (2) ) { (3) ; free(pa); pa= (4) ; } else { pa-coef (5) ; pa-exp (6) ; q=(7) ; pa= (8) ;