第二章线性表(LinearList)课件.ppt

《第二章线性表(LinearList)课件.ppt》由会员分享，可在线阅读，更多相关《第二章线性表(LinearList)课件.ppt（100页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、12类型定义和基本操作类型定义和基本操作顺序表示和实现顺序表示和实现链式表示和实现链式表示和实现应用举例应用举例31. 了解线性表的逻辑结构特性了解线性表的逻辑结构特性数据元素之间存在数据元素之间存在着线性关系；着线性关系；2. 在计算机中表示这种关系的两类不同的存储结构是在计算机中表示这种关系的两类不同的存储结构是顺序存储结构顺序存储结构和和链式存储结构链式存储结构。用前者表示的线性。用前者表示的线性表简称为表简称为顺序表顺序表，用后者表示的线性表简称为，用后者表示的线性表简称为链表链表。 3. 熟练掌握这两类存储结构的熟练掌握这两类存储结构的描述方法描述方法以及线性表的以及线性表的基本操作

2、基本操作在这两种存储结构上的在这两种存储结构上的实现实现。4. 能够从时间和空间复杂度的角度综合比较线性表能够从时间和空间复杂度的角度综合比较线性表两两种存储结构的不同特点种存储结构的不同特点及其及其适用场合适用场合。5. 结合线性表类型的定义增强对抽象数据类型的理解。结合线性表类型的定义增强对抽象数据类型的理解。使用本章所学的基本知识设计有效算法解决与线性使用本章所学的基本知识设计有效算法解决与线性表相关的应用问题。表相关的应用问题。4链表链表是本章的重点和难点。是本章的重点和难点。扎实的指针操作和内存动态分配的编程技术扎实的指针操作和内存动态分配的编程技术是学好本章的基本要求；是学好本章的

3、基本要求；分清链表中指针分清链表中指针 p 和结点和结点 *p 之间的对应关系；之间的对应关系；区分链表中的区分链表中的头结点头结点、头指针头指针和和开始开始结点结点的的不同所指；不同所指；掌握掌握循环链表、双向链表的特点等。循环链表、双向链表的特点等。56&线性表线性表由由n(n0)个数据元素个数据元素(结点结点)a1, a2, a3, ., ai-1, ai, ai+1, ., an组组成的成的有限有限序列。序列。 记作记作，L=(a1, a2, a3, ., ai-1, ai, ai+1, ., an)。其中其中， n为数据元素的个数，称为为数据元素的个数，称为表的长度表的长度; ai为

4、组成该线性表的为组成该线性表的数据元素数据元素； i为为ai在线性表中的在线性表中的位序位序； 当当n=0 时，称为时，称为空表空表。7&线性表的特性线性表的特性线性表中的所有数据元素的数据类型是一致的。线性表中的所有数据元素的数据类型是一致的。数据元素在线性表中的位置只取决于它的序号。数据元素在线性表中的位置只取决于它的序号。结点间的逻辑关系是线性的。结点间的逻辑关系是线性的。8例例1、26个英文字母组成的字母表个英文字母组成的字母表 La=（A，B，C，Z）姓姓 名名学学 号号性性 别别年龄年龄 健康情况健康情况王小林王小林790631男男18健康健康陈陈 红红790632女女20一般一般

5、刘建平刘建平790633男男21健康健康张立立张立立790634男男17神经衰弱神经衰弱 . . . 例例2、某校、某校1978年到年到1983年各型号计算机拥有量的变化情况。年各型号计算机拥有量的变化情况。 Lb=（6，17，28，50，92，188） 例例3、学生健康情况登记表、学生健康情况登记表9抽象数据类型线性表的定义：抽象数据类型线性表的定义：ADT List数据对象数据对象: D= ai | ai ElemSet, i=1, 2, , n, n 0数据关系数据关系: R1= | ai-1, ai D, i=2, , n基本操作基本操作:InitList(&L) 操作结果：操作结果：

6、 构造一个空的线性表构造一个空的线性表L。DestroyList(&L) 初始条件：线性表初始条件：线性表L已存在。已存在。操作结果：销毁线性表操作结果：销毁线性表L。ClearList(&L)初始条件：线性表初始条件：线性表L已存在。已存在。操作结果：将线性表操作结果：将线性表L重置为空表。重置为空表。10ListEmpty(L)初始条件：线性表初始条件：线性表 L 已存在。已存在。操作结果：若操作结果：若 L 为空表，则返回为空表，则返回TRUE，否则返回，否则返回FALSE。ListLength(L)初始条件：线性表初始条件：线性表 L 已存在。已存在。操作结果：返回操作结果：返回 L

7、中数据元素的个数。中数据元素的个数。GetElem(L, i, &e) 初始条件：线性表初始条件：线性表 L 已存在已存在, 1 i ListLength(L)。操作结果：用操作结果：用 e 返回线性表返回线性表 L 中第中第 i 个数据元素的值。个数据元素的值。LocateElem(L, e, compare()初始条件：线性表初始条件：线性表L已存在已存在, compare() 是数据元素判定函数。是数据元素判定函数。操作结果：返回操作结果：返回L中第中第1个与个与e满足关系的数据元素的位序。满足关系的数据元素的位序。 若这样的数据元素不存在，则返回值为若这样的数据元素不存在，则返回值为0

8、。11PriorElem(L, cur_e, &pre_e)初始条件：线性表初始条件：线性表 L 已存在。已存在。操作结果：若操作结果：若cur_e是是L的数据元素，且不是第一个，则用的数据元素，且不是第一个，则用pre_e 返回它的前驱；否则操作失败，返回它的前驱；否则操作失败， pre_e无定义。无定义。NextElem(L, cur_e, &next_e)初始条件：线性表初始条件：线性表 L 已存在。已存在。操作结果：若操作结果：若cur_e是是L的数据元素且不是第一个，则用的数据元素且不是第一个，则用next_e 返回它的后继；否则操作失败，返回它的后继；否则操作失败， next_e无

9、定义。无定义。ListInsert(&L, i, e)初始条件：线性表初始条件：线性表 L 已存在，已存在， 1 i ListLength(L)+1。操作结果：在操作结果：在L 中第中第 i 个位置前插入新的数据元素个位置前插入新的数据元素e，L的长度的长度 加加1。12ListDelete(&L, i, &e)初始条件：线性表初始条件：线性表 L 已存在且非空，已存在且非空， 1 i ListLength(L)。操作结果：删除操作结果：删除L的第的第 i 个数据元素，且用个数据元素，且用e返回其值，返回其值，L的的 长度减长度减1。ListTranverse(L, visit()初始条件：线

10、性表初始条件：线性表 L 已存在。已存在。操作结果：依次对操作结果：依次对L的每个数据元素调用函数的每个数据元素调用函数visit() 。一旦。一旦 visit()失败，则操作失败。失败，则操作失败。ADT List13基本操作：基本操作： 初始化线性表初始化线性表LInitList(&L) 销毁线性表销毁线性表LDestoryList(&L) 引用型操作引用型操作没有改变线性表中的数据元素和数据元素之间的关系没有改变线性表中的数据元素和数据元素之间的关系 判别线性表判别线性表L是否为空表是否为空表ListEmpty(L) 求线性表求线性表L的长度的长度ListLength(L) 获取线性表获

11、取线性表L中的某个数据元素内容中的某个数据元素内容 GetElem(L, i, &e) 返回与返回与e满足关系的数据元素位序满足关系的数据元素位序LocateElem(L,e,compare() 返回线性表返回线性表L中中e的直接前驱元素的直接前驱元素 PriorElem(L, e, &pre_e) 返回线性表返回线性表L中中e的直接后继元素的直接后继元素 NextElem(L, e, &next_e) 遍历线性表遍历线性表L中所有数据元素中所有数据元素 ListTranverse(L, visit()加工型操作加工型操作修改表中的数据元素或元素之间的关系修改表中的数据元素或元素之间的关系 清

12、空线性表清空线性表LClearList(&L) 在线性表在线性表L中插入一个数据元素（前插）中插入一个数据元素（前插）ListInsert(&L, i, e) 删除线性表删除线性表L中第中第i个数据元素个数据元素 ListDelete(&L, i, &e) 14合并合并分拆分拆合并两顺序表合并两顺序表1516&顺序表示顺序表示 用一组用一组连续连续的存储单元（地址连续）依次存放线性表的各数的存储单元（地址连续）依次存放线性表的各数据元素。据元素。 即在顺序表中即在顺序表中逻辑结构相邻的数据元素，其物理位置也相邻逻辑结构相邻的数据元素，其物理位置也相邻。逻辑地址逻辑地址数据元素数据元素存储地址存

13、储地址 数据元素数据元素1a1LOC(a1)a12a2LOC(a1)+ca2iaiLOC(a1)+(i-1)*cainanLOC(a1)+(n-1)*can 表中第一个元素的存储位置作为线性表的起始地址，称表中第一个元素的存储位置作为线性表的起始地址，称作线性表的作线性表的基地址基地址。线性表的这种机内表示，称线性表的这种机内表示，称顺序存储结构顺序存储结构（或（或顺序映顺序映象象）,也称也称向量结构向量结构。通常用。通常用数组来描述数据结构中的顺数组来描述数据结构中的顺序存储结构。具有这种存储序存储结构。具有这种存储结构的线性表称结构的线性表称顺序表顺序表。17&顺序表示顺序表示 相邻两数据

14、元素的存储位置计算公式为：相邻两数据元素的存储位置计算公式为：LOC(ai+1)=LOC(ai)+c这里，这里，c为一个数据元素所占据的存储单元数目为一个数据元素所占据的存储单元数目。 线性表中任意一个数据元素的存储位置的计算公式为：线性表中任意一个数据元素的存储位置的计算公式为： LOC(ai)=LOC(a1)+(i-1)*c这里，这里，LOC(a1)为基地址为基地址 只要确定了首地址，线性表中任意数据元素都可以随机存取。只要确定了首地址，线性表中任意数据元素都可以随机存取。所以线性表的顺序存储结构是一种所以线性表的顺序存储结构是一种随机存取的存储结构随机存取的存储结构。逻辑地址逻辑地址数据

15、元素数据元素存储地址存储地址数据元素数据元素1a1LOC(a1)a12a2LOC(a1)+ca2iaiLOC(a0)+(i-1)*cainanLOC(a0)+(n-1)*can18&在在C语言中，实现线性表顺序存储结构的类型定义语言中，实现线性表顺序存储结构的类型定义 #define LIST_INIT_SIZE 100 /线性表存储空间的初始分配量线性表存储空间的初始分配量 #define LISTINCREMENT 10 /线性表存储空间的分配增量线性表存储空间的分配增量 typedef struct ElemType *elem; /指向存放线性表中数据元素的基地址指向存放线性表中数据元

16、素的基地址 int length; /线性表的当前长度线性表的当前长度 int listsize; /当前分配的存储容量当前分配的存储容量(sizeof(ElemType)为单位为单位) SqList；19 算法算法2.3 创建空顺序表创建空顺序表Status InitList_Sq(SqList &L) 算法算法 获取线性表中某个元素内容获取线性表中某个元素内容Status GetElem_Sq(Sqlist L, int i, ElemType &e) 算法算法2.4 顺序表的（前）插入顺序表的（前）插入 Status ListInsert_Sq(SqList &L, int i, Ele

17、mType e) 算法算法2.5 顺序表的删除顺序表的删除 Status ListDelete_Sq(SqList &L, int i, ElemType &e) 算法算法2.7 合并两顺序表合并两顺序表 void MergeList_Sq(SqList La, SqList Lb, SqList &Lc) 20Status InitList_Sq(SqList &L) 初始化算法的思想初始化算法的思想： 根据初始分配量给线性表分配空间；检查分配根据初始分配量给线性表分配空间；检查分配是否成功；是否成功； 初始化各成员变量。初始化各成员变量。21Status InitList_Sq(SqLis

18、t &L) Status InitList_Sq(SqList &L) / 构造一个空的线性表构造一个空的线性表L L.elem = (ElemType*)malloc(LIST_INIT_SIZE*sizeof(ElemType); if (!L.elem) exit(OVERFLOW); / 存储分配失败存储分配失败 L.length = 0; / 空表长度为空表长度为0 L.listsize = LIST_INIT_SIZE; / 初始存储容量初始存储容量 return OK; / InitList_Sq22Status GetElem_Sq(Sqlist L, int i, ElemT

19、ype &e) 算法思路算法思路： 若要获取的元素位置超出范围，返回错误信息；若要获取的元素位置超出范围，返回错误信息； 取第取第i个元素给个元素给e，操作成功。，操作成功。23Status GetElem_Sq(Sqlist L, int i, ElemType &e) if (iL.length) return ERROR; /判断判断i值是否合理，若不合理，返回值是否合理，若不合理，返回ERROR e=L.elemi-1; /数组中第数组中第i-1的单元存储着线性表中第的单元存储着线性表中第i个数据元素的内容个数据元素的内容 return OK;24Status ListInsert_S

20、q(SqList &L, int i, ElemType e) 25Status ListInsert_Sq(SqList &L, int i, ElemType e) 插入算法的思想插入算法的思想： 若插入位置不适当，则返回错误信息；若插入位置不适当，则返回错误信息； 若当前存储空间已满，则增加分配空间；若当前存储空间已满，则增加分配空间； 当当1 i n时，则从表尾开始到时，则从表尾开始到i个依次向后移动一个依次向后移动一个位置个位置(共需移动共需移动n-i+1个数据元素个数据元素)。 最后将最后将e存入，表长存入，表长n增增1插入成功。插入成功。26 Status ListInsert_

21、Sq(SqList &L, int i, ElemType e) / 在顺序表在顺序表L中第中第i个位置之前插入新的元素个位置之前插入新的元素e； / i 的合法值为的合法值为 1 i ListLength_Sq(L)+1 if (i L.length+1) return ERROR; / i值不合法值不合法 if (L.length = L.listsize) /当前存储空间已满，增加分配当前存储空间已满，增加分配 ElemType *newbase = (ElemType *)realloc(L.elem, (L.listsize+LISTINCREMENT)*sizeof (ElemTy

22、pe); if (!newbase) return ERROR; / 存储分配失败存储分配失败 L.elem = newbase; / 新基址新基址 L.listsize += LISTINCREMENT; / 增加存储容量增加存储容量 27 q = &(L.elemi-1); / q为插入位置为插入位置 for (p = &(L.elemL.length-1); p=q; -p) *(p+1) = *p; / 插入位置及之后的元素右移插入位置及之后的元素右移 *q = e; / 插入插入e +L.length; / 表长增表长增1 return OK; / ListInsert_Sq28St

23、atus ListInsert_Sq(SqList &L, int i, ElemType e) 插入算法分析插入算法分析：上述算法上述算法for循环语句的执行次数为循环语句的执行次数为n-i+1;若若i=1, 需移动全部需移动全部n个结点；（最坏：个结点；（最坏：O(n)）若若i=n+1（在表尾插入）（在表尾插入）, 无需用移动结点，直接插入即无需用移动结点，直接插入即可；（最好：可；（最好：O(1)）移动结点的平均次数：移动结点的平均次数：)i(npniiis111按等概率考虑，则按等概率考虑，则pi=1/(n+1)。21211111111111111nnnnnninninpEniniii

24、s)()()()(（顺序表插入算法平均约需移动顺序表插入算法平均约需移动一半一半结点。结点。29Status ListDelete_Sq(SqList &L, int i, ElemType &e) 30Status ListDelete_Sq(SqList &L, int i, ElemType &e) 删除算法的思想删除算法的思想： 若删除位置不适当，则返回错误信息；若删除位置不适当，则返回错误信息； 从从i+1开始到表尾开始到表尾n依次向前移动一个位置依次向前移动一个位置(共需共需移动移动n-i个数据元素个数据元素)。 将表长将表长n减减1，删除成功。，删除成功。31 Status Li

25、stDelete_Sq(SqList &L, int i, ElemType &e) / 在顺序表在顺序表L中删除第中删除第i个元素，并用个元素，并用e返回其值返回其值 / i 的合法值为的合法值为 1 i ListLength_Sq(L) if (iL.length) return ERROR; / i值不合法值不合法 p = &(L.elemi-1); /p为被删除元素的位置为被删除元素的位置 e = *p; / 被删除元素的值赋给被删除元素的值赋给e q = L.elem+L.length-1; / 表尾元素的位置表尾元素的位置 for (+p; p=q; +p) *(p-1) = *p

26、;/ 被删除元素后的元素左移被删除元素后的元素左移 -L.length; / 表长减表长减1 return OK; / ListDelete_Sq32Status ListDelete_Sq(SqList &L, int i, ElemType &e) 删除算法分析删除算法分析：上述算法上述算法for循环语句的执行次数为循环语句的执行次数为n-i;若若i=1, 需移动需移动n-1个结点；（最坏：个结点；（最坏：O(n)）若若i=n, 无需移动结点无需移动结点, 直接删除即可；（最好：直接删除即可；（最好：O(1)）移动结点的平均次数：移动结点的平均次数：i)(nqniidl1按等概率考虑，则按

27、等概率考虑，则qi=1/n。212011111nnnninninqEniniidl)()(（顺序表删除算法平均约需移动顺序表删除算法平均约需移动一半一半结点。结点。33合并有序表合并有序表。已知两线性表已知两线性表LA和和LB为按值非递减排列的有序表为按值非递减排列的有序表。现要现要求将求将LA和和LB合并为一个新的线性表合并为一个新的线性表LC，且，且LC中的数据元中的数据元素仍按值非递减有序排列。素仍按值非递减有序排列。分析：分析： 合并过程合并过程建空表建空表LC，然后将，然后将LA或或LB中的元素逐个插中的元素逐个插 入到入到LC中；中； 为使为使LC中元素按值非递减有序排列，可设两个

28、指针分别中元素按值非递减有序排列，可设两个指针分别指向指向LA和和LB中当前元素，同时将两指针所指示的两元素中当前元素，同时将两指针所指示的两元素（设为（设为a和和b）进行比较：）进行比较：a b时，时，c=a;否则，否则，c=b。 然后将然后将LA或或LB中剩余的数据元素加入到中剩余的数据元素加入到LC中。中。34 void MergeList_Sq(SqList La, SqList Lb, SqList &Lc) / 已知顺序线性表已知顺序线性表La和和Lb的元素按值非递减排列。的元素按值非递减排列。 / 合并合并La和和Lb得到新的顺序线性表得到新的顺序线性表Lc, / Lc的元素也按

29、值非递减排列。的元素也按值非递减排列。 ElemType *pa,*pb,*pc,*pa_last,*pb_last; pa = La.elem; pb = Lb.elem; Lc.listsize = Lc.length = La.length+Lb.length; pc = Lc.elem = (ElemType*)malloc(Lc.listsize*sizeof(ElemType); if (!Lc.elem) exit(OVERFLOW); / 存储分配失败存储分配失败 35 pa_last = La.elem+La.length-1; pb_last = Lb.elem+Lb.le

30、ngth-1; while (pa = pa_last & pb = pb_last) / 合并合并 if (*pa = *pb) *pc+ = *pa+; else *pc+ = *pb+; while (pa = pa_last) *pc+ = *pa+; / 插入插入La的剩余元素的剩余元素 while (pb data和和p-next 指针变量指针变量p和结点变量和结点变量*p的的关系关系 指针变量指针变量p的值的值结点地址结点地址 结点变量结点变量*p的值的值结点内容结点内容 (*p).data的值的值p指针所指结点的指针所指结点的data域的值域的值 (*p).next的值的值*p

31、后继结点的地址后继结点的地址*(*p).next)*p后继结点后继结点 4546 算法算法2.8 在单链表中取某下标的元素在单链表中取某下标的元素Status GetElem_L(LinkList L, int i, ElemType &e) 算法算法2.9 单链表的插入单链表的插入 Status ListInsert_L(LinkList &L, int i, ElemType e) 算法算法2.10 单链表的删除单链表的删除 Status ListDelete_L(LinkList &L, int i, ElemType &e) 算法算法2.11 单链表的创建单链表的创建void Crea

32、teList_L(LinkList &L, int n) 算法算法2.12 合并两顺序表合并两顺序表 void MergeList_L(LinkList &La, LinkList &Lb, LinkList &Lc)47Status ListInsert_L(LinkList &L, int i, ElemType e) newnode-next = p-next; p-next = newnode;headnewnodeheadnewnode非空表非空表ppheadnewnodeheadnewnode空表空表pp48 Status ListInsert_L(LinkList &L, int

33、 i, ElemType e) /在带头结点的单链线性表在带头结点的单链线性表L的第的第i个元素之前插入元素个元素之前插入元素e LinkList p,s;p = L; int j = 0; if (iListLength(L)+1) return ERROR; / 合法性检查合法性检查 while ( j next; +j; if( !s = (LinkList)malloc(sizeof(LNode) return ERROR; / 生成新结点生成新结点 s-data = e; s-next = p-next; p-next = s; / 插入插入L中中 return OK; / List

34、Insert_L49Status ListDelete_L(LinkList &L, int i, ElemType & e) q = p-next; p-next = q-next; free(q); headhead非空表非空表pqheadhead空表空表0pq50 Status ListDelete_L(LinkList &L, int i, ElemType &e) / 在带头结点的单链表在带头结点的单链表L中，删除第中，删除第i个元素，并由个元素，并由e返回其值返回其值 LinkList p,q; int j; if (iListLength(L) return ERROR; /检查

35、检查i值的合理性值的合理性 for(p=L, j=0; j next, j+); /寻找第寻找第i-1个结点个结点 q = p-next; p-next =q-next; e=q-data; free(q);/ 删除并释放结点删除并释放结点 return OK; / ListDelete_L51 void MergeList_L(LinkList &La, LinkList &Lb, LinkList &Lc) / 已知单链线性表已知单链线性表La和和Lb的元素按值非递减排列。的元素按值非递减排列。 / 合并合并La和和Lb得到新的单链表得到新的单链表Lc，Lc元素也按值非递减排列。元素也按值

36、非递减排列。 LinkList pa, pb, pc; pa = La-next; pb = Lb-next; Lc = pc = La; / 用用La的头结点作为的头结点作为Lc的头结点的头结点 while (pa & pb) if (pa-data data) pc-next = pa; pc = pa; pa = pa-next; else pc-next = pb; pc = pb; pb = pb-next; pc-next = pa ? pa : pb; / 插入剩余段插入剩余段 free(Lb); / 释放释放Lb的头结点的头结点 / MergeList_L52 优势：优势： 能

37、有效利用存储空间能有效利用存储空间。 单链表的存储密度比顺序表低，多占用了存储空间。但顺序表必须分单链表的存储密度比顺序表低，多占用了存储空间。但顺序表必须分配足够大的连续的存储空间，而链表可以利用零星的存储单元，因此配足够大的连续的存储空间，而链表可以利用零星的存储单元，因此链式的分配比顺序分配有效。链式的分配比顺序分配有效。 用用指针指针指示数据元素之间的后继关系，指示数据元素之间的后继关系，便于进行便于进行插入插入、删除删除等操作等操作。 劣处劣处： 结点中的结点中的指针域需额外占用存储空间指针域需额外占用存储空间。当每个结点的数据域。当每个结点的数据域所占字节不多时，指针域所占存储空间

38、的比重就显得很大。所占字节不多时，指针域所占存储空间的比重就显得很大。 不能随机存取数据元素不能随机存取数据元素；同时，它还丢失了一些顺序表有的；同时，它还丢失了一些顺序表有的长处，如线性表的长处，如线性表的“表长表长”和数据元素在线性表中的和数据元素在线性表中的“位序位序”。 对任一结点的操作都要从头指针依指针链查找到该结点，这对任一结点的操作都要从头指针依指针链查找到该结点，这增加了算法的复杂度增加了算法的复杂度。53具体要求具体要求顺序表顺序表链表链表基于空间基于空间适于线性表长度变化适于线性表长度变化不大，易于事先确定不大，易于事先确定其大小时采用。其大小时采用。适于当线性表长度变化大

39、，适于当线性表长度变化大，难以估计其存储规模时采难以估计其存储规模时采用。用。基于时间基于时间由于顺序表是一种随由于顺序表是一种随机存储结构，当线性机存储结构，当线性表的操作主要是查找表的操作主要是查找时，宜采用。时，宜采用。链表中对任何位置进行插链表中对任何位置进行插入和删除都只需修改指针，入和删除都只需修改指针，所以这类操作为主的线性所以这类操作为主的线性表宜采用链表做存储结构。表宜采用链表做存储结构。若插入和删除主要发生在若插入和删除主要发生在表的首尾两端，则宜采用表的首尾两端，则宜采用尾指针表示的单循环链表。尾指针表示的单循环链表。54表中最后一个结点的指针域指向头结点，整个链表形成一

40、表中最后一个结点的指针域指向头结点，整个链表形成一个环。个环。优点：优点：从表中任一结点出发均可找到表中某一结点。从表中任一结点出发均可找到表中某一结点。实际应用中，常让指向循环链表的指针指向最后一个结点实际应用中，常让指向循环链表的指针指向最后一个结点 ，这样无论是找第一个结点还是找最后一个结点都很方便。这样无论是找第一个结点还是找最后一个结点都很方便。循环链表的运算与线性链表基本一致。但两者循环链表的运算与线性链表基本一致。但两者判断判断是否到表是否到表尾的尾的条件不同条件不同： 线性表：判断某结点的链域是否为空。线性表：判断某结点的链域是否为空。 循环链表：判断某结点的链域值是否等于头指

41、针循环链表：判断某结点的链域值是否等于头指针。an-1heada1a0head(空表空表)(非空表非空表)55为克服单链表单向性的缺点，设置两个指针域，其一指向为克服单链表单向性的缺点，设置两个指针域，其一指向直接后继，另一指向直接前趋。直接后继，另一指向直接前趋。双向链表通常采用带表头结点的循环链表形式。双向链表通常采用带表头结点的循环链表形式。prior element nextheadheadp-priorp-nextppriornext56&在在C语言中，实现双向链表的类型定义语言中，实现双向链表的类型定义typedef int ElemType; /* 定义元素类型为整型，也可定义为

42、其他类型定义元素类型为整型，也可定义为其他类型 */typedef struct DuLNode/* 双向链表结点结构双向链表结点结构 */ ElemType data; /* 数据域数据域 */ struct DuLNode *prior; /* 指向直接前趋的指针域指向直接前趋的指针域 */ struct DuLNode *next; /* 指向直接后继的指针域指向直接后继的指针域 */ DuLNode, *DuLinkList;57Status ListInsert_DuL(DuLinkList &L, int i, ElemType e)25headcurrentcurrent25he

43、adheadhead314815currentcurrent3148251525newnode58Status ListInsert_DuL(DuLinkList &L, int i, ElemType e)newnode-prior = current-prior;newnode-next = current;current-prior-next = newnode;current-prior = newnode;59 Status ListInsert_DuL(DuLinkList &L, int i, ElemType e) / 在带头结点的双链循环表在带头结点的双链循环表L的第的第i个

44、元素前插入元素个元素前插入元素e， / i的合法值为的合法值为1i表长表长+1。 DuLinkList p, s; int j=1; / 初始化，初始化，j为计数器为计数器 if (iListLength_DuL(L)+1) return ERROR; / 合法性检查合法性检查 p = L-next; / 初始化，初始化，p指向第一个结点指向第一个结点 while ( j next; +j; if (!(s = (DuLinkList)malloc(sizeof(DuLNode) return ERROR; s-data = e; s-prior = p-prior; p-prior-next

45、 = s; s-next = p; p-prior = s; return OK; / ListInsert_DuL60Status ListDelete_DuL(DuLinkList &L, int i, ElemType &e)headhead314815current3115currentcurrent-prior-next = current-next;current-next-prior = current-prior; 61Status ListDelete_DuL(DuLinkList &L, int i, ElemType &e)headhead31currentcurrent

46、current-prior-next = current-next;current-next-prior = current-prior; 62 Status ListDelete_DuL(DuLinkList &L, int i, ElemType &e) / 删除带头结点的双链循环线性表删除带头结点的双链循环线性表L的第的第i个元素，个元素， / i的合法值为的合法值为1i表长表长 DuLinkList p; int j=1; / 初始化，初始化，j为计数器为计数器 if (iListLength_DuL(L) return ERROR; / 合法性检查合法性检查 p = L-next;

47、/ 初始化，初始化，p指向第一个结点指向第一个结点 while ( j next; +j; e = p-data; p-prior-next = p-next; p-next-prior = p-prior; free(p); return OK; / ListDelete_DuL63 int ListLength_DuL(DuLinkList va) /返回带头结点的双链循环线性表返回带头结点的双链循环线性表va的长度的长度 DuLinkList p; p = va-next; int len = 0; / 初始化，初始化，p指向第一个结点，指向第一个结点，j为计数器为计数器 while (

48、p!=va ) p = p-next; +len; return(len); /ListLength_DuL64typedef struct LNode/结点结构结点结构 ElemType data; /数据域数据域 struct LNode *next; /指针域指针域 *Link, *Position; typedef struct/链表结构链表结构Link head, tail; /分别指向线性链表中的头结点和最后一个结点分别指向线性链表中的头结点和最后一个结点int len;/指示表中数据元素的个数指示表中数据元素的个数LinkList;655，7，8，186667 编号编号为为1，2

49、，n的的n个人按顺时针方向围坐在一个人按顺时针方向围坐在一张圆桌旁，每个人手中持有一个张圆桌旁，每个人手中持有一个密码密码（正整数）。（正整数）。首先输入一个正整数作为报数上限值首先输入一个正整数作为报数上限值m，然后，从，然后，从第一个人开始按顺时针方向自第一个人开始按顺时针方向自1开始顺序报数，报开始顺序报数，报到到m的人离开桌旁，并将他手中的密码作为新的的人离开桌旁，并将他手中的密码作为新的m值，从顺时针方向的下一个就坐在桌旁的人开始重值，从顺时针方向的下一个就坐在桌旁的人开始重新从新从1报数，如此下去，直至所有人全部离开桌旁报数，如此下去，直至所有人全部离开桌旁为止。为止。 约瑟夫（约

50、瑟夫（Josephus）问题）问题： 求出按出列次序得到的求出按出列次序得到的n个人员的序列。个人员的序列。68 假设有假设有7个人，编号从个人，编号从1到到7，他们手中的密码分，他们手中的密码分别是别是3，1，7，2，4，8，4，最初的，最初的m=2。 1 2 3 4 5 6 7 3 1 1 1 1 1 1 1 1 7 2 4 8 4 m=269 1 2 3 4 5 6 7 3 1 1 1 1 1 1 1 1 7 2 4 8 4 m=2 1 2 3 4 5 6 7 3 1 0 1 1 1 1 1 1 7 2 4 8 4 m=1 输出序号：输出序号：2、 1 2 3 4 5 6 7 3 1 0