Microsoft Word - 第2章 线性表.docx

Transcription

1 第 2 章线性表 学习目标 u 理解顺序表的逻辑与存储原理, 并能实现简单顺序表 u 掌握单链表的逻辑与存储原理, 并能实现单链表 u 掌握双向链表的逻辑与存储原理 u 掌握循环链表的逻辑与存储原理线性表, 顾名思义是像线一样性质的表, 它的用处多不胜数, 是最常用且最简单的一种数据结构, 例如, 一串英文字母 一队手拉手的小朋友 一份学生成绩单等等都可以用线性表表示 线性表的存储结构有顺序存储结构和链式存储结构两种, 本章分别基于这两种存储结构来讲解常用的几个线性表 2.1 什么是线性表 线性表是具有相同特性的数据元素组成的一个有限序列 例如, 定义一个线性表来存储本班学生的学生编号, 可表示为如下形式 : (001, 002, ) 这就是一个线性表 线性表也可以用一个标识符来命名, 如 A = (001, 002, ) 线性表中元素的个数为线性表的长度, 当元素个数为 0 时, 称该线性表为空表 线性表中的元素可以是整数 字符等简单数据, 也可以由数个数据项组成 如第一章中的图 1-1, 它也是一个线性表, 描述的是新学期入学学生的信息, 其中每一个元素都由几个数据项组成, 在这种情况下, 常把元素称为一条记录 每一种数据结构都有它自己的特征, 线性表作为一种最简单的数据结构, 有如下几个特征 : (1) 线性表中有且只有一个开始结点 ( 头结点 ), 这个开始结点没有前驱结点 (2) 线性表中有且只有一个末尾结点 ( 尾结点 ), 这个末尾结点没有后继结点 (3) 除去开始结点与末尾结点, 其它结点都有一个前驱结点和一个后继结点 线性表的这种结构使元素逐个排列开来, 如手拉手的小朋友, 如此呈现给人们的数据形式就比较清晰明了 线性表在存储结构上有顺序存储和链式存储两种方式, 但不管哪种存储方式, 它们的结构都有如下特点 : l 均匀性 : 虽然不同数据表的数据元素可以是各种各样的, 但对于同一个线性表来说, 数据元素必须具有相同的数据类型和长度 l 有序性 : 各数据元素在线性表中的位置只取决于它们的序号, 数据元素之间的相对位置是线性的, 即存在唯一的 第一个 和 最后一个 数据元素, 除了第一个和最后一个外, 其它元素前面均只有一个数据元素 ( 直接前驱 ), 后面均只有一个数据元素 ( 直接后继 ) 数据结构的目的是和算法结合, 实现各种操作 线性表是一种比较灵活的数据结构, 它

2 的长度可根据需要增减, 它也可以进行插入 删除等操作 可对线性表进行的基本操作如下所示 : l 创建 -Create(): 创建一个新的线性表 l 初始化 -Init(): 初始化操作, 将新创建的线性表初始化为空 l 获取长度 -GetLength(): 获取线性表的长度 l 判断表是否为空 IsEmpty(): 判断线性表是否为空 l 获取元素 -Get(): 获取线性表某一个位置上的元素 l 插入 -Insert(): 在线性表的某一个位置插入一个元素 l 删除 -Delete(): 删除某一个位置上的元素 l 清空表 -Clear(): 清空线性表, 将线性表置为空 当然, 在设计线性表时, 也可以有其他操作, 例如, 根据某个条件对线性表中的元素进行排序 将两个线性表合并成一个 重新复制一个线性表等, 上面只是描述了线性表一些最基本的操作 线性表是应用最广泛的一种数据结构, 在使用过程中, 除了链表 栈和队列等, 线性表还有很多推广应用, 如时间表 排序表等 当然, 这些推广应用需要读者在实际开发中去深入学习, 限于教材篇幅, 本书只讲解最基础的线性表 2.2 线性表的顺序存储 ( 顺序表 ) 通过前面的学习可以知道, 线性表有顺序存储与链式存储两种结构, 它们各有自己的存 储特点, 在实现上也有所不同 本节先来学习一下线性表的顺序存储 顺序存储的原理 第一章简单讲解了线性表的顺序存储结构, 读者应对线性表的顺序存储结构原理已有所了解 所谓顺序存储, 就是在存储器中分配一段连续的存储空间, 逻辑上相邻的数据元素其物理存储地址也是相邻的 假如要用顺序表来存储四个字母, 则需要在内存中分配四个连续的存储单元, 如图 2-1 所示 图 2-1 顺序存储结构在图 2-1 中, 要存储的四个字母被存储在一段连续的存储空间中 由存储空间的地址可以看出, 这四个存储单元是连续的, 第一个存储单元由序号 0 来标记, 接下来的存储单元依次递增标记序号, 这样在查找元素时, 只要找到相应的索引就能找到元素, 非常方便 线性表的这种存储方式称为顺序存储或顺序映射, 又由于逻辑上相邻的两个元素在对应的顺序表中的存储位置也相邻, 因此这种映射也称为直接映射

3 在图 2-1 中, 我们分配了四个存储单元来存储这四个字符, 表的长度为 4, 容量也为 4 但要注意的是, 表的长度未必与容量相同 表的长度要小于等于表的容量, 因为可能申请了四个存储单元, 但只存入 3 个元素 在顺序存储中, 只要确定了线性表在存储空间里的起始位置, 线性表中任意元素就都可随机存取, 所以线性表的顺序存储结构是一种随机存取的结构 在高级语言中, 顺序存储是用数组来实现的 在顺序存储中, 系统不需要为表元素之间的逻辑关系增加额外的存储空间, 而且在存取元素时, 它可以根据给出的下标快速计算出元素的存储地址, 从而达到随机读取的目的 例如在图 2-1 中, 如果要读取第 3 个元素, 因它的下标为 2( 与第 1 个元素之间有两个间隔 ), 由内存段的起始地址和元素相差个数可以快速计算出第 3 个元素的存储地址 (0x *2 = 0x003), 计算出地址后, 就可以方便地对数据进行操作 但是, 如果在顺序表中插入或删除元素, 效率会特别低 对插入来说, 只限于在表的长度小于表的容量的顺序表中, 如果插入大量数据, 很难保证空间是否充足 而且一旦分配了存储空间, 如果想要扩充容量, 需要重新分配空间, 然后将原来的数据复制到新的空间中, 非常麻烦 另一方面, 即使空间充足, 那么在插入位置之后的元素必须都要向后移动, 这个效率非常低 同理, 如果要删除大量元素, 那么势必会造成空间的浪费, 而且删除元素后, 后面的元素都要向前移动, 效率也会非常低 顺序存储的实现 了解了顺序表, 那么我们接下来实现一个顺序表, 并完成其查找 插入和删除等基本操作 在实现各种数据结构时, 本书都以 C 语言为例 1 创建顺序表在创建顺序表时, 需要先创建一个头结点来存放顺序表的长度 大小和地址等信息, 然后再创建顺序表, 同时将顺序表的地址保存在头结点中, 其示意图如图 2-2 所示 图 2-2 顺序表示意图实现思路如下 : (1) 定义一个 struct 来保存顺序表信息 (2) 为头结点分配空间 (3) 为顺序表分配空间, 将顺序表空间地址保存在头结点中 (4) 将头结点地址返回给调用者 代码实现如下 : typedef struct _tag_seqlist // 头结点, 记录表的信息 int capacity; // 表容量 int length; // 表长度 int * node; //node[capacity], 为指针数组 TSeqList;

4 // 创建顺序表 SeqList* SeqList_Create(int capacity) // 返回值为 SeqList* 类型, 即顺序表的地址 int ret; TSeqList *temp = NULL; temp = (TSeqList*)malloc(sizeof(TSeqList)); // 为头结点分配空间 if (temp == NULL) ret = 1; printf("func SeqList_Create() error:%d\n", ret); return NULL; memset(temp, 0, sizeof(tseqlist)); temp->capacity = capacity; temp->length = 0; temp->node = (int*)malloc(sizeof(void*)*capacity); // 分配一个指针数组 if (temp->node == NULL) ret = 2; printf("func SeqList_Create() error:%d\n", ret); return NULL; return temp; // 将分配好的顺序表的地址返回 顺序表的实现并不难, 而且实现方式也有多种, 只要思路清晰, 代码实现就很简单, 读者也可以试着自己来实现一遍 2 求顺序表容量在实现顺序表时, 一般将顺序表信息保存在头结点中, 因此求顺序表容量时, 可以直接从头结点中获取 代码实现如下所示 : // 求顺序表容量 int SeqList_Capacity(SeqList* list) // 参数为顺序表地址 TSeqList *temp = NULL; if (list == NULL) // 作健壮性判断 return; temp = (TSeqList *)list; return temp->capacity; 3 求顺序表长度和求顺序表的容量一样, 求顺序表大小也是从头结点中获取信息, 代码如下所示 :

5 // 获取顺序表长度 int SeqList_Length(SeqList* list) TSeqList *temp = NULL; if (list == NULL) return; temp = (TSeqList *)list; return temp->length; 4 插入元素增删改查是数据结构的核心操作, 每种数据结构都要实现这几种最基本的操作 在顺序表中, 要插入元素, 则需要将插入位置后的所有元素向后移动, 其示意图如图 2-3 所示 图 2-3 插入元素在图 2-3 中, 要在顺序表的 1 角标位置插入元素 X, 则在插入时, 需要将 1 角标和其后的元素都向后移动一个单元, 其过程如图 2-4 所示 图 2-4 插入元素 X 图 2-3 和图 2-4 演示了往顺序表中插入元素的过程 在插入过程中, 需要考虑一些异常情况 :

6 l 当顺序表已满时, 表中的元素无法向后移动, 需要作出特别处理 ( 例如不插入, 或者新开辟一块更大的空间来存储这些元素 ) l 当插入的位置在空闲区域时, 需要作出相应处理 : 在空闲位置插入元素, 如图 2-5 所示 图 2-5 在空闲区域插入元素在图 2-5 中, 容量为 5 的顺序表中只有两个元素, 当插入新元素 X 时, 指定的位置是角标 3 的位置, 这样就造成元素不连续, 不符合顺序表的存储规则 在这种情况下可以作适当的修正, 将插入位置改为角标 2 有了插入元素的思路后, 接下来用代码来实现, 代码如下 : // 插入元素 int SeqList_Insert(SeqList* list, SeqListNode* node, int pos) // 参数为顺序表地址, 要插入的元素地址, 插入位置 int i; TSeqList *temp = NULL; // 先作健壮性判断 if (list == NULL node == NULL) // 如果顺序表为空, 或者结点为空 return -1; temp = (TSeqList *)list; // 如果顺序表已满 if (temp->length >= temp->capacity) return -2; // 容错 if (pos > temp->length) // 如果给出的 pos 在长度后, 即中间有空余, pos = temp->length; // 就修正到最后一个元素后面 for (i = temp->length; i > pos; i--) // 将插入位置的元素依次后移动 temp->node[i] = temp->node[i - 1]; temp->node[i] = (int)node; // 然后在腾出的位置插入新元素结点 temp->length++; // 插入成功后, 长度加 1 return 0; 5 删除元素

7 从顺序表中删除某一个元素, 则将元素删除后, 需要将后面的元素依次向前移动来补齐 空位, 删除过程如图 2-6 所示 图 2-6 删除元素删除过程相对来说没有插入过程那么复杂, 不必考虑内存不足时的 溢出 问题, 但因为要移动元素, 效率还是较低的 其代码实现如下所示 : // 删除元素 SeqList* SeqList_Delete(SeqList* list, int pos) int i; // 先作健壮性判断 TSeqList * tlist = NULL; SeqListNode * temp = NULL; tlist = (TSeqList *)list; if (list == NULL pos < 0 pos >= tlist->capacity) printf("seqlist_delete() error\n"); return NULL; temp = (SeqListNode *)tlist->node[pos]; // 要删除的元素 for (i = pos + 1; i < tlist->length; i++) // 将删除元素之后的所有元素前移 tlist->node[i - 1] = tlist->node[i]; tlist->length--; return temp; // 删除元素后, 长度要减 6 查找某个位置上的元素 在顺序表中查找某个元素是非常方便的, 因为顺序表在底层是以数组来实现的, 每个存

8 储单元都有索引标注, 要查找某个位置上的元素, 直接按索引来查找就可以 查找元素的代码实现如下所示 : SeqList* SeqList_Get(SeqList* list, int pos) // 先作健壮性判断 TSeqList * tlist = NULL; SeqListNode * temp = NULL; tlist = (TSeqList *)list; if (list == NULL pos < 0 pos >= tlist->capacity) printf("seqlist_get() error\n"); return NULL; temp = (SeqListNode *)tlist->node[pos]; // 将表中 pos 位置的结点指针赋给 temp return temp; 7 清空表清空顺序表是将表中的内容全部置为 0 其代码实现如下所示: // 清空顺序表 void SeqList_Clear(SeqList* list) TSeqList *temp = NULL; if (list == NULL) return; temp = (TSeqList *)list; temp->length = 0; memset(temp->node, 0, (temp->capacity*sizeof(void*)));// 将顺序表全部归 0 return; 8 销毁表销毁顺序表是将表整个销毁, 无法再进行使用 其代码实现如下所示 : // 销毁顺序表 void SeqList_Destory(SeqList* list) TSeqList* temp = NULL; if (list == NULL) // 如果参数顺序表为空 return; temp = (TSeqList *)list; if (temp->node!= NULL)

9 free(temp->node); // 先释放头结点中的指针数组 free(temp); // 再释放头结点 return; 至此, 已经实现了一个顺序表最基本的操作, 可以完成简单的增删改查的功能 接下来 可以用测试程序来测试一下这个顺序表的使用情况 注意 : 本书同系列教材 C 语言程序设计教程 C++ 程序设计教程 均使用 Visual Studio2013 来开发, 同样, 在本书中仍然使用 Visual Studio2013 作为数据结构的开发环 境, 关于 Visual Studio2013 的安装与使用, 请参考 C 语言程序设计教程 一书 ( 传智播 客高教产品研发部著 ), 本书不再重复叙述 在上述讲解中, 每一个函数都已实现, 因此在本例中, 只添加头文件 SeqList.h 与测试 程序 main.c 两个文件, 而函数实现代码的 SeqList.c 文件, 本例中不再重复给出, 具体如例 2-1 所示 例 2-1 SeqList.h // 头文件 1 #ifndef _SEQLIST_H_ 2 #define _SEQLIST_H_ 3 4 typedef void SeqList; 5 typedef void SeqListNode; 6 7 SeqList* SeqList_Create(int capacity); // 创建顺序表 8 void SeqList_Destory(SeqList* list); // 销毁顺序表 9 void SeqList_Clear(SeqList* list); // 清空线性表 10 int SeqList_Length(SeqList* list); // 获取顺序表长度 11 int SeqList_Capacity(SeqList* list); // 获取顺序表容量 12 int SeqList_Insert(SeqList* list, SeqListNode* node, int pos); // 插入元素 13 SeqList* SeqList_Get(SeqList* list, int pos); // 获取 pos 位置上的元素 14 SeqList* SeqList_Delete(SeqList* list, int pos); // 删除 pos 位置的元素 #endif main.c // 测试程序的文件 17 #include "SeqList.h" 18 #include <stdio.h> 19 #include <stdlib.h> typedef struct _Teacher char name[32]; 24 int age; 25 Teacher; 26

10 27 int main() int ret = 0; 30 SeqList * list = NULL; 31 Teacher t1, t2, t3, t4, t5; // 结点元素 32 t1.age = 31; 33 t2.age = 32; 34 t3.age = 33; 35 t4.age = 34; 36 t5.age = 35; 37 // 创建结点 38 list = SeqList_Create(10); // 创建顺序表 // 插入结点 41 ret = SeqList_Insert(list, (SeqListNode*)&t1,0); // 位置 0: 始终在头部插入 42 ret = SeqList_Insert(list, (SeqListNode*)&t2, 0); 43 ret = SeqList_Insert(list, (SeqListNode*)&t3, 0); 44 ret = SeqList_Insert(list, (SeqListNode*)&t4, 0); 45 ret = SeqList_Insert(list, (SeqListNode*)&t5, 0); printf(" 顺序表容量 :%d\n", SeqList_Capacity(list)); 48 printf(" 顺序表长度 :%d\n", SeqList_Length(list)); // 遍历顺序表 51 printf(" 遍历顺序表 :\n"); 52 for (int i = 0; i < SeqList_Length(list); i++) Teacher* temp = (Teacher*)SeqList_Get(list, i); // 获取链表结点 55 if (temp == NULL) printf("func SeqList_Get() error\n", ret); 58 return; printf("age: %d\n", temp->age); // 销毁链表 65 printf(" 销毁顺序表时 :\n"); 66 while (SeqList_Length(list) > 0) Teacher* temp = (Teacher *)SeqList_Delete(list, 0); // 删除头部元素 69 if (temp == NULL) 70

11 71 printf("func SeqList_Get() error\n", ret); 72 return; printf("age: %d\n", temp->age); SeqList_Destory(list); system("pause"); 80 return 0; 81 运行结果如图 2-7 所示 图 2-7 例 2-1 运行结果由图 2-7 可知, 例 2-1 中创建了一个容量为 10 的顺序表, 并且存入了 5 个元素 在本例中, 第 行代码定义了一个 Teacher 结构体, 保存了 Teacher 的姓名和年龄 ; 第 行代码创建了 5 个结点, 并且为结点中的 age 赋值 ; 第 38 行代码调用 SeqList_Create() 函数创建了一个顺序表, 第 行代码将 Teacher 的 5 个结点插入到顺序表中, 每次都从头部插入 ; 第 行代码分别调用相应函数求算顺序表的容量和长度 ; 第 行代码遍历顺序表中的元素并打印 ; 第 行代码是逐一删除顺序表中的元素, 并打印删除的元素 ; 第 77 行代码将顺序表销毁 通过本节的学习, 读者应对线性表的顺序存储有了一定的掌握 其实它并不难, 只要理清思路, 代码便是手到擒来 2.3 线性表的链式存储 ( 链表 ) 顺序表必须占用一整块事先分配好的 大小固定的存储空间, 不便于存储空间的管理, 为此有人提出可以实现存储空间的动态管理, 即链式存储方式 链表 本节就来学习什么 是链表, 以及链表的实现 链式存储的原理 在链式存储中, 结点之间的存储单元地址可能是不连续的 链式存储中每个结点都包含 两个部分 : 存储元素本身的数据域和存储结点地址的指针域 在第一章中介绍链式存储时,

12 讲解了一些链式存储的原理, 结点中的指针指向的是下一个结点, 如果结点中只有指向后继 结点的指针, 那么这些结点组成的链表称为单向链表 如图 2-8 所示, 就是一个单链表 图 2-8 单向链表一般在链表中也会有一个头结点来保存链表的信息, 然后有一个指针指向下一个结点, 下一个结点又指向它后面的一个结点, 这样直到最后一个结点, 它没有后继结点, 就指向 NULL 在链表中, 这些存储单元可以是不连续的, 因此它可以提高空间利用率, 当需要存储元素时, 哪里有空闲的空间就在哪里分配, 只要将分配的空间地址保存到上一个结点就可以, 这样通过访问前一个元素就能找到后一个元素 当在链表中某一个位置插入元素时, 从空闲空间中为该元素分配一个存储单元, 然后将两个结点之间的指针断开, 上一个结点的指针指向新分配的存储单元, 新分配的结点中指针指向下一个结点 ; 这样不需要移动原来元素的位置, 效率比较高 ; 同样, 当删除链表中的某个元素时, 就断开它与前后两个结点的指针, 然后将它的前后两个结点连接起来, 也不需要移动原来元素的位置 与顺序表相比较, 在插入删除元素方面, 链表的效率要比顺序表高许多 但是随机查找元素时, 链表没有索引标注, 存储单元的空间并不连续, 如果要查找某一个元素, 必须先得经过它的上一个结点中的地址才能找到它, 因此不管遍历哪一个元素, 都必须把它前面的元素都遍历后才能找到它, 效率就不如顺序表高 链式存储的实现 链表的几种操作与顺序表差不多, 也是增删改查几种操作 接下来我们来实现一个链表 1 创建链表以图 2-8 为例, 在创建链表时, 头结点中保存链表的信息, 则需要创建一个 struct, 在其中定义链表的信息与指向下一个结点的指针 代码如下 : struct Header // 头结点 int length; // 记录链表大小 struct Node* next; // 指向第一个结点的指针 ; 存储元素的结点包含两部分内容 : 数据域和指针域, 则也需要定义一个 struct, 代码如下 : struct Node // 结点 int data; // 数据域 struct Node* next; // 指向下一个结点的指针

13 ; 这样头结点与数据结点均已定义 为了使用方便, 将两个 struct 用 typedef 重新定义新的名称, 代码如下 : typedef struct Node List; // 将 struct Node 重命名为 List typedef struct Header phead; // 将 struct Header 重命名为 phead 创建链表要比创建顺序表简单一些 顺序表中需要先为头结点分配空间, 其次为数组分配一段连续空间, 将这段连续空间地址保存在头结点中, 然后往其中存储元素 但创建链表时, 只需要创建一个头结点, 每存储一个元素就分配一个存储单元, 然后将存储单元的地址保存在上一个结点中即可, 不需要在创建时把所有的空间都分配好 创建链表的代码如下 : phead * createlist()//phead 是 struct Header 的别名, 是头结点类型 phead* ph = (phead*)malloc(sizeof(phead)); // 为头结点分配内存 ph->length = 0; // 为头结点初始化 ph->next = NULL; return ph; // 将头结点地址返回 2 获取链表大小链表的大小等信息也是保存在头结点中, 因此需要时从头结点中获取即可, 代码如下 : int Size(pHead* ph) // 获取链表大小 if (ph == NULL) printf(" 参数传入有误!"); return 0; return ph->length; 3 插入元素在链表中插入元素时要比在顺序表中快 以图 2-8 为例, 如果要在 46 和 100 之间插入元素 99, 其插入过程也较简单 : 首先将 46 和 100 之间的连接断开, 然后 46 结点的指针指向 99, 将 99 结点的指针指向 100, 这样就完成了插入 其过程如图 2-9 所示

14 图 2-9 在链表中插入新元素在插入元素时, 不必像顺序表中那样移动元素, 效率要高很多 其代码实现如下 : // 在某一个位置插入某一个元素, 插入成功返回 1 int Insert(pHead* ph, int pos, int val) // 先作健壮性判断 if (ph == NULL pos < 0 pos > ph->length) printf(" 参数传入有误!"); return 0; // 在向链表中插入元素时, 先要找到这个位置 List* pval = (List*)malloc(sizeof(List)); // 分配内存存储要插入的数据 pval->data = val; List *pcur = ph->next; if (pos == 0) ph->next = pval; // 指针断开连接过程 pval->next = pcur; else for (int i = 1; i < pos; i++) pcur = pcur->next; // 当前指针指向头结点后的第一个结点 // 插入在第一个位置 // 找到要插入的位置 pval->next = pcur->next; pcur->next = pval; // 指针断开再连接过程 ph->length++; // 增加一个元素, 长度要加 1 return 1;

15 4 查找某个元素查找链表中的某个元素, 其效率没有顺序表高, 因为不管查找的元素在哪个位置, 都需要将它前面的元素都全部遍历才能找到它 查找的代码实现如下 : List* find(phead* ph, int val) // 查找某个元素 // 先作健壮性判断 if (ph == NULL) printf(" 参数传入有误!"); return NULL; // 遍历链表来查找元素 List *ptmp = ph->next; do if (ptmp->data == val) return ptmp; ptmp = ptmp->next; while (ptmp->next!= NULL); // 循环条件是直到链表结尾 printf(" 没有值为 %d 的元素!", val); return NULL; 5 删除元素在删除元素时, 首先将被删除元素与上下结点之间的连接断开, 然后将这两个上下结点重新连接, 这样元素就从链表中成功删除了 例如, 将图 2-9(b) 中的元素 28 删除, 其过程如图 2-10 所示

16 图 2-10 从链表中删除元素从链表中删除元素, 也不需要移动其他元素, 效率也较高 其代码实现如下 : List* Delete(pHead* ph, int val) // 删除值为 val 的元素, 删除成功, 返回删除的元素 // 先作健壮性判断 if (ph == NULL) printf(" 链表传入错误!"); return NULL; // 找到 val 值所在结点 List* pval = find(ph, val); if (pval == NULL) printf(" 没有值为 %d 的元素!", val); return NULL; // 遍历链表去找到要删除结点, 并找出其前驱及后继结点 List *pre = ph->next; // 当前结点 List *pcur = NULL; if (pre->data == val) // 如果删除的是第一个结点 ph->next = pre->next; ph->length--; return pre; else // 如果删除的是其他结点 for (int i = 0; i < ph->length; i++) // 遍历链表 pcur = pre->next;

17 if (pcur->data == val) // 找到要删除的元素 pre->next = pcur->next; // 将被删除元素的上下两个结点连接起来 ph->length--; // 长度减 1 return pcur; // 将被删除的元素结点返回 pre = pre->next; 6 销毁链表销毁链表时, 将链表中每个元素结点释放掉, 可以将头结点释放掉 ; 但也可以保留头结点, 将其置于初始化状态 代码实现如下 : void Destory(pHead* ph) // 销毁链表 List *pcur = ph->next; List *ptmp; if (ph == NULL) printf(" 参数传入有误!"); while (pcur->next!= NULL) ptmp = pcur->next; free(pcur); // 将结点释放 pcur = ptmp; ph->length = 0; // 回到初始化状态 ph->next = NULL; 在本例中, 没有释放掉头结点, 只是将头结点中的信息归于了初始化状态 7 遍历打印链表实现出链表的遍历打印函数, 是为了在接下来的测试程序中避免代码重复, 打印链表的代码如下 : void print(phead *ph) if (ph == NULL) printf(" 参数传入有误!"); List *ptmp = ph->next; while (ptmp!= NULL) printf("%d ", ptmp->data);

18 ptmp = ptmp->next; printf("\n"); 至此, 链表基本的操作都已经实现, 接下来可以用测试程序来测试这个链表的使用情况 同样, 由于上述操作函数都已经实现, 在接下来的测试中只给出头文件 list.h 和测试代码文件 main.c, 而函数实现 list.c, 读者可以复制上述各操作函数的代码, 也可以试着自己来实现 具体如例 2-2 所示 例 2-2 list.h // 头文件 1 #ifndef _LIST_H_ 2 #define _LIST_H_ 3 4 struct Node; 5 typedef struct Node List; 6 typedef struct Header phead; 7 8 phead * createlist(); // 创建链表 9 int isempty(phead* l); // 判断链表是否为空 10 int Insert(pHead* l, int pos, int val); // 插入元素, 插入成功返回 1; 11 List* Delete(pHead* l, int ele); // 删除元素, 删除成功, 返回删除的元素 12 List* find(phead* l, int ele); // 查找某个元素是否存在 13 int Size(pHead* l); // 获取链表大小 14 void Destory(pHead* l); // 销毁链表 15 void print(phead *l); // 打印链表 struct Node // 结点 int data; // 数据域 20 struct Node* next; // 指向下一个结点的指针 21 ; struct Header // 头结点 int length; // 记录链表大小 26 struct Node* next; 27 ; 28 #endif main.c // 测试文件 29 #define _CRT_SECURE_NO_WARNINGS 30 #include "list.h" 31 #include <stdio.h> 32 #include <stdlib.h> 33

19 34 int main() int ret; 37 phead *ph = createlist(); // 创建链表 38 if (ph == NULL) printf(" 创建链表失败!\n"); int arr[10] = 1, 2, 3, 4, 56, 76, 7, 4, 36, 34;// 定义一个 int 类型数组 for (int i = 0; i <= 6; i++) Insert(ph, 0, arr[i]); // 将数组元素插入到链表中, 每次都从头部插入 printf(" 链表长度 :%d\n", Size(ph)); printf(" 打印链表中的元素 :\n"); 52 print(ph); 53 printf(" 删除链表中的元素, 请输入要删除的元素 :\n"); 54 int num; 55 scanf("%d", &num); // 本例中为测试程序, 为减少异常处理, 请输入链表中有的元素 56 Delete(ph, num); 57 printf(" 元素删除成功, 删除元素 %d 后, 链表中元素为 :\n", num); 58 print(ph); ret = find(ph, 3); // 查找链表中某一个元素 61 if (ret) 62 printf("get!\n"); 63 else 64 printf("no!\n"); system("pause"); 67 return 0; 68 运行如图 2-11 所示 图 2-11 例 2-2 运行结果

20 在例 2-2 中, 第 37 行代码创建了一个链表 ; 第 行定义了一个 int 类型数组, 并将数组中的元素插入到了链表中 ; 第 49 行代码打印出了链表的长度, 由图 2-11 可知, 链表长度为 7; 第 52 行代码调用 print() 函数遍历打印出了链表中的元素 ; 第 行代码是删除链表中的某个元素, 从键盘输入的元素为 4, 即删除链表中的元素 4; 第 58 行代码又调用 print() 函数重新打印删除 4 后的链表元素, 由图 2-11 的运行结果可知, 元素 4 删除成功 ; 第 行代码是查找链表中是否有值为 3 的元素, 由运行结果可知, 这个元素存在 至此, 线性表的顺序存储与链式存储, 包括其原理和实现方式都已讲解完毕, 相信读者对这两种表也有了一定的掌握, 其实只要理解了其存储原理, 思路清晰, 代码实现并不难 掌握了这两种最基本的线性表, 对接下来其他数据结构的学习会有很大帮助 2.4 双向链表 上一节学习了单链表, 但是单链表有一个缺点, 无法快速访问前驱结点, 当查找到某一个元素时, 如果想找前面的元素结点, 需要再次从头遍历, 这样就比较麻烦 那么就有人提出了, 是否可以在结点中再增加一个指针来指向前驱结点? 答案是可以的 增加了指向前驱结点的指针的链表称为双向链表, 本节就来学习一下 什么是双向链表 双向链表, 顾名思义就是可以向两个方向走的链表 它的每一个结点有两个指针, 一个 指向后继结点, 一个指向前驱结点 如图 2-12 所示 图 2-12 双向链表图 2-12 中的双向链表, 第一个结点的前驱指针 pre 指向了 NULL, 当然, 读者在设计时也可以将它指向头结点 ; 最后一个结点的后继结点 next 指向了 NULL, 这和单链表是一样的 在双向链表中, 通过一个结点可以找到它的后继结点, 也可以找到它的前驱结点 双向链表在结构和算法描述上和单链表相同, 只是某些算法实现比单链表复杂一些 例如, 在插入元素时, 需要同时修改两个方向的指针指向 以图 2-12 中的双向链表为例, 在元素 12 与 99 之间插入新元素 33, 其过程如图 2-13 所示

21 图 2-13 在双链表中插入元素从图 2-13 演示的过程中, 可以看出, 在插入元素时, 需要同时修改两个方向的指针指向 同理, 在删除元素时, 也要修改两个指针, 这里我们就不再做相应的图解演示 前面已学习过单链表的实现过程, 双向链表的实现与单链表的实现大同小异, 因此在本节学习完双链表之后, 读者可以试着自己来实现一下双链表的基本操作, 然后再对比与本书中双向链表的实现有何异同 双向链表的实现 学习完双链表的定义与基础操作之后, 我们用 C 语言来实现一个双链表 此双向链表所具有的功能如下所示 : l 创建双向链表 l 获取双向链表的长度 l 判断双向链表是否为空 l 插入 删除 查找元素 l 销毁双向链表 l 打印双向链表

22 在学习单链表时, 每一种操作算法都有详细的描述与实现代码, 双向链表与单链表有很 多操作是相似的, 不再详细描述, 只给出案例代码 具体如例 2-3 所示 例 2-3 dlist.h // 头文件 1 #ifndef _DLIST_H_ 2 #define _DLIST_H_ 3 4 struct Node; 5 typedef struct Head* phead; // 头结点类型 6 typedef struct Node* pnode; // 数据结点类型 7 // 定义头结点 8 struct Head 9 10 int length; 11 pnode next; // 指向下一个结点的指针 12 ; 13 // 定义数据结点 14 struct Node int data; 17 pnode pre; // 指向前驱结点的指针 18 pnode next; // 指向后继结点的指针 19 ; phead DlistCreate(); // 创建双向链表 22 int getlength(phead ph); // 获取双向链表的长度 23 int IsEmpty(pHead ph); // 判断链表是否为空 24 int DlistInsert(pHead ph, int pos, int val); // 在链表的 pos 位置插入元素 val 25 pnode DlistDelete(pHead ph, int val); // 删除双向链表 ph 中的元素 val 26 pnode DlistFind(pHead ph, int val); // 查找双向链表中是否有值为 val 的元素 27 void DlistDestory(pHead ph); // 销毁链表 28 void printfront(phead ph); // 打印双向链表中的元素 29 void printlast(phead ph); 30 #endif dlist.c // 函数实现文件 31 #include "dlist.h" 32 #include <stdio.h> 33 #include <stdlib.h> phead DlistCreate() // 创建双向链表 phead ph = (phead)malloc(sizeof(struct Head)); // 为头结点分配空间 38 if (ph == NULL) 39 printf(" 分配头结点失败!"); // 为了方便运行结果查看, 不设置 return 返回

23 40 // 创建好头结点后, 初始化头结点中数据 41 ph->length = 0; 42 ph->next = NULL; 43 return ph; // 将头结点返回 int getlength(phead ph) // 获取双向链表的长度 // 先对传入进来的链表作健壮性检查 48 if (ph == NULL) 49 printf(" 传入的双链表有误!"); 50 return ph->length; int IsEmpty(pHead ph) // 判断双链表是否为空 if (ph == NULL) 56 printf(" 传入的双链表有误!"); 57 if (ph->length == 0) // 如果长度为 0, 则链表为空 58 return 1; 59 else 60 return 0; int DlistInsert(pHead ph, int pos, int val) // 在链表的 pos 位置插入元素 val pnode pval = NULL; 66 // 先作健壮性判断 67 if (ph == NULL pos < 0 pos > ph->length) 68 printf(" 插入元素时, 参数传入有误!"); // 如果参数无误, 就要为元素分配结点空间 71 pval = (pnode)malloc(sizeof(struct Node)); 72 pval->data = val; // 将值 val 保存到此结点中 // 接下来要判断在哪个位置插入元素, 先判断链表是否为空 75 if (IsEmpty(ph)) // 如果链表为空 ph->next = pval; // 直接将结点插入到头结点后 78 pval->next = NULL; 79 pval->pre = NULL; // 第一个结点不回指头结点 else // 如果双链表不为空, 则要判断是插入哪个位置 pnode pcur = ph->next;

24 84 if (pos == 0) // 在第一个位置 ( 头结点后 ) 插入 ph->next = pval; // 头结点指向 pval 87 pval->pre = NULL; 88 pval->next = pcur; //pval 的后继指针指向 pcur 89 pcur->pre = pval; //pcur 前驱指针指向 pval else // 如果不是插入到第一个位置 for (int i = 1; i < pos; i++) // 就要遍历链表找到要插入的位置 pcur = pcur->next; //pcur 指针向后移 // 循环结束后, 此时 pcur 指向的是要插入的位置 98 pval->next = pcur->next; // 指针断开再连接的过程 99 pcur->next->pre = pval; 100 pval->pre = pcur; 101 pcur->next = pval; ph->length++; 105 return 1; pnode DlistDelete(pHead ph, int val) // 删除双向链表 ph 中的元素 val if (ph == NULL ph->length == 0) printf(" 参数传入有误!"); // 如果参数无误, 则遍历找到值为 val 的元素, 然后将其删除 115 pnode pval = DlistFind(ph, val); // 找到值所在的结点 116 if (pval == NULL) return NULL; printf(" 将其删除 \n"); 121 // 因为双链表中的结点既有前驱结点又有后继结点 122 pnode pre = pval->pre; //pre 指向 pval 结点的前驱结点 123 pnode pnext = pval->next; //pnext 指向 pval 结点的后继结点 pre->next = pnext; 126 pnext->pre = pre; 127 return pval;

25 pnode DlistFind(pHead ph, int val) // 查找某个元素 if (ph == NULL) printf(" 参数传入有误!"); // 如果参数无误, 则需要遍历双链表, 查找要找的元素 137 pnode ptmp = ph->next; // 此过程与单链表无异 138 do if (ptmp->data == val) printf(" 有此元素!\n"); 143 return ptmp; ptmp = ptmp->next; 146 while (ptmp->next!= NULL); // 循环条件是直到链表结尾 printf(" 没有值为 %d 的元素!\n", val); 149 return NULL; void DlistDestory(pHead ph) // 销毁链表 pnode pcur = ph->next; 155 pnode ptmp; 156 if (ph == NULL) 157 printf(" 参数传入有误!"); while (pcur->next!= NULL) ptmp = pcur->next; 162 free(pcur); // 将结点释放 163 pcur = ptmp; ph->length = 0; // 回到初始化状态 166 ph->next = NULL; void printfront(phead ph) // 打印双向链表中的元素, 从前往后打印 if (ph == NULL)

26 printf(" 参数传入有误!"); pnode ptmp = ph->next; 176 while (ptmp!= NULL) printf("%d ", ptmp->data); 179 ptmp = ptmp->next; printf("\n"); void printlast(phead ph) // 倒序打印, 从链表末尾开始向前打印 if (ph == NULL) printf(" 参数传入有误!"); pnode ptmp = ph->next; 191 while (ptmp->next!= NULL) ptmp = ptmp->next; // 先将指针 ptmp 移动到末尾结点 for (int i = --ph->length; i >= 0; i--) // 从末尾结点向前打印元素 printf("%d ", ptmp->data); 198 ptmp = ptmp->pre; printf("\n"); 201 main.c // 测试文件 202 #define _CRT_SECURE_NO_WARNINGS 203 #include "dlist.h" 204 #include <stdio.h> 205 #include <stdlib.h> 206 int main() // 创建一个双向链表 209 phead ph = NULL; 210 ph = DlistCreate(); // 向链表中插入元素 213 int num; 214 printf(" 请输入要插入的元素, 输入 0 结束 :\n");

27 215 while (1) scanf("%d", &num); 218 if (num == 0) 219 break; 220 DlistInsert(ph, 0, num); // 本测试程序从头部插入 printf(" 双链表长度 :%d\n", getlength(ph)); 224 printfront(ph); // 从前往后打印双链表的元素 225 DlistInsert(ph, 3, 99); // 在 3 位置插入新元素 printfront(ph); // 然后再从前往后打印双链表的元素 227 printlast(ph); // 从后往前打印元素 int val; 230 printf(" 请输入要查找的元素 :\n"); 231 scanf("%d", &val); 232 DlistFind(ph, val); // 查找元素 int del; 235 printf(" 请输入要删除的元素 :\n"); 236 scanf("%d", &del); 237 DlistDelete(ph, del); // 删除元素 238 printfront(ph); // 打印删除元素后的链表 DlistDestory(ph); // 销毁链表 241 printf(" 双链表销毁成功!\n 此时链表长度为 :%d\n", ph->length); system("pause"); 244 return 0; 245 运行结果如图 2-14 所示 图 2-14 例 2-3 运行结果

28 在例 2-3 双链表的实现中, 只实现了双链表的增删改查几个基本功能 双向链表的插入删除操作, 实现起来比单链表的稍微复杂一些, 其他操作都无大的改动 双链表是可以倒序遍历的, 为了测试该双链表的功能, 我们在最后的打印链表元素时, 增加了一个倒序打印函数 printlast(), 从后往前打印链表的元素 相对于单链表来说, 双向链表要复杂一些, 因为它多了一个前驱指针, 所以对于插入和删除操作的实现要格外小心 另外, 因为双链表中的每个结点要记录两个指针, 所以空间消耗要略多一些 不过由于它良好的对称性, 使得对某个结点的前后两个结点操作更灵活, 也使算法的时间效率得到了提高, 说到底, 就是用空间换时间 2.5 循环链表 链表中还有一种常用的形式, 那就是循环链表, 看到循环二字, 想必读者已经知道它是 一种怎样的链表了, 不错, 这种链表头尾相接, 形成了一个环 那么它又具有什么样的特性 呢, 本节就来探讨一下 什么是循环链表 循环链表是首尾相接的一种链表, 它尾结点的后继指针又指向链表的第一个结点, 这样 形成了一个环 对于循环链表, 从表中的任何一个结点出发, 能找到其它所有的结点 如图 2-15 所示, 是一种单向的循环链表 图 2-15 单循环链表 循环链表的形式有好几种, 如双循环链表 多重循环链表 ( 将表中结点链在多个环上 ) 等 多重循环链表示例如图 2-16 所示 图 2-16 多重循环链表图 2-16 就是一个多重循环链表, 元素 26 所在的结点既在左边的循环链中, 又在右边的循环链中 多重循环链表并不常用, 我们在讲循环链表时, 主要讲解的是单链的循环链表 循环链表, 既有单链表的优点又有双向链表的优点, 相对于单链表, 双向链表需要为每个结点增加部分存储空间保存前驱指针的信息, 而循环链表无须增加储存量, 只是改变了尾

29 结点中后继指针的指向, 就使操作更加灵活多变 需要注意的是, 循环链表中没有 NULL 指针, 涉及遍历操作时, 其终止条件就不再是非循环链表中判别 pnode->next 是否为空, 而是判别它们是否等于某一指定指针, 如头指针或尾指针等, 用代码表示, 如下所示 : if(pnode->next == phead->next) 循环链表的实现 在单链表中, 从一已知结点出发, 只能访问到该结点及其后继结点, 无法找到该结点之前的其它结点 而在单循环链表中, 从任一结点出发都可访问到表中所有结点, 这一优点使某些运算在单循环链表上更易于实现 循环链表在实现上大多操作都与单链表相同, 如创建 查找等, 这些部分在单链表与双向链表中都有详细的讲解及代码实现, 此处就不再重复, 接下来主要讲解其插入与删除元素时与单链表的异同 1 插入元素在循环链表中插入元素, 如果是插入到第一个位置, 即头结点之后的位置, 则稍稍有一些麻烦, 需要处理三个指针, 头结点中的指针 尾结点中的指针和插入元素的结点指针 其过程如图 2-17 所示 图 2-17 在循环链表的头结点插入元素在头结点之后插入元素时, 要将新结点中的指针指向此位置上原来的结点, 头结点中的指针指向新结点, 尾结点指针指向新结点 比单链表多处理了一个尾结点指针 在尾部插入元素时也有所不同,p->next 不再指向 NULL, 而是指向 head->next 除此两处以外, 在其他位置插入元素, 则与单链表处理相同 其代码实现如下 : int ClistInsert(pHead ph, int pos, int val) // 在链表的 pos 位置插入元素 val

30 if (ph == NULL pos < 0 pos > ph->length) printf(" 插入元素时, 参数传入有误!\n"); pnode pval = NULL; // 参数传入无误, 则为新元素 val 分配结点 pval = (pnode)malloc(sizeof(struct Node)); pval->data = val; // 将值 val 保存到此结点中 // 接下来要判断在哪个位置插入元素, 先判断链表是否为空 if (IsEmpty(ph)) // 如果链表为空 ph->next = pval; // 直接将结点插入到头结点后 pval->next =pval; // 将第一个结点指向它自己 else // 循环链表不为空, 则分为在头部插入 ( 即头结点后 ) 和普通位置插入 pnode prear = ph->next; if (pos == 0) // 在第一个位置 ( 头结点后 ) 插入 // 在 0 号位置插入, 需要先找到尾结点 while (prear->next!= ph->next) // 循环结束的条件 prear = prear->next; //pcur 指针向后移动 //while 循环结束后,pRear 指向尾结点 // 然后插入元素 pval->next = ph->next; ph->next = pval; prear->next = pval; // 这三个步骤顺序不能更改 else // 如果不是 0 号位置插入, 则和单链表无区别 pnode pcur = ph->next; for (int i = 1; i < pos; i++) // 就要遍历链表找到要插入的位置 pcur = pcur->next; //pcur 指针向后移 // 循环结束后, 此时 pcur 指向的是要插入的位置 pval->next = pcur->next; // 指针断开再连接的过程 pcur->next = pval;

31 ph->length++; return 1; 在插入新元素时, 先判断链表是否为空, 如果为空, 则将元素插入到头结点后, 然后将其指针指向自身 ; 如果不为空, 根据插入的位置作出相应操作 2 删除元素在删除元素时, 也要考虑删除的是否为头结点后的第一个元素, 如果是, 则需要将头结点与尾结点的指针指向待删除结点的后继结点, 如图 2-18 所示 图 2-18 删除头结点后的第一个元素如果是删除其他位置的元素, 则和单链表处理方式相同 其代码实现如下 : pnode ClistDelete(pHead ph, int val) // 删除循环链表 ph 中的元素 val if (ph == NULL ph->length == 0) printf(" 参数传入有误!"); // 先找到链表的尾结点 pnode prear = ph->next; while (prear->next!= ph->next) prear = prear->next; // 查找此元素 pnode pval = ClistFind(ph, val); if (pval == NULL) return NULL; // 关于 ClistFind() 函数, 与单链表相同 if (pval == ph->next) // 如果是第 0 号位置上的结点

32 ph->next = pval->next; prear->next = pval->next; else // 如果是其他位置的结点 // 就要找到 pval 的前驱结点 pnode pre = ph->next; for (int i = 0; i < ph->length; i++) if (pre->next == pval) pre->next = pval->next; return pval; pre = pre->next; return NULL; 在循环链表中, 除了插入和删除操作与单链表稍有不同之外, 其他操作与单链表都是一样的, 读者可以参照单链表的操作自己动手实现循环链表, 并完成测试 约瑟夫环 约瑟夫问题是循环链表的一个典型应用, 其描述如下 :m 个人围成了一圈, 从其中任一个人开始, 按顺时针顺序使所有人依次从 1 开始报数, 报到 n 的人出列 ; 然后使 n 之后的人接着从 1 开始报数, 再次使报到 n 的人出列 如此下去, 求算出列的顺序, 及最后留下来的人的编号 为了更清晰的描述问题, 可以将 m 与 n 设定为具体数字, 如 m = 8,n = 3, 即 8 个人围坐成一圈 为这 8 个人编号, 使编号为 1 的人从 1 开始报数, 报到 3 的人出局 ; 编号为 4 的人再从 1 开始报数, 报到 3 的出局 如此重复, 直到这 8 个人全部出局 出局过程如图 2-19 所示

33 图 2-19 约瑟夫环 第一轮 : 从 1 到 3, 第 3 个人出局 第二轮 : 第 4 个人从 1 开始报数, 第 6 个人报到 3, 则第 6 个人出局 第三轮 : 第 7 个人从 1 开始报数, 第 1 个人报到 3, 则第 1 个人出局 第四轮 : 第 2 个人从 1 开始报数, 第 5 个人报到 3, 则第 5 个人出局 第五轮 : 第 7 个人从 1 开始报数, 第 2 个人报到 3, 则第 2 个人出局 第六轮 : 第 4 个人从 1 开始报数, 第 8 个人报到 3, 则第 8 个人出局 第七轮 : 第 4 个人从 1 开始报数, 此时只剩下他和 7, 他自己报到 3, 则第 4 个人出局 最后这一圈人只剩下 7 当数据量较小时, 通过作图我们很轻易地就能找出出列顺序, 但当数据量较大时, 人工 计算几乎是不可能的 要解决这样的问题, 需要借助一定的编程算法, 而我们刚刚学习过的 循环链表就正好可以用来解决此问题 首先用这些数据创建一个循环链表 ; 然后设置限制条 件并循环遍历链表, 当遍历到要出局的元素时, 就将其删除, 这样循环操作直到链表中只剩 下一个结点 具体代码实现如例 2-4 所示 例 2-4 clist.h // 头文件 1 #ifndef _CLIST_H_ 2 #define _CLIST_H_ 3 4 struct Node; 5 typedef struct Head* phead; // 头结点类型 6 typedef struct Node* pnode; // 数据结点类型 7 // 定义头结点 8 struct Head 9 10 int length; 11 pnode next; // 指向下一个结点的指针 12 ;

34 13 // 定义数据结点 14 struct Node int data; 17 pnode next; // 指向后继结点的指针 18 ; 19 phead ClistCreate(); // 创建循环链表 20 int getlength(phead ph); // 获取循环链表的长度 21 int IsEmpty(pHead ph); // 判断链表是否为空 22 int ClistInsert(pHead ph, int pos, int val); // 在链表的 pos 位置插入元素 val 23 void print(phead ph); // 打印循环链表中的元素 #endif clist.c // 文件 26 #include "clist.h" 27 #include <stdio.h> 28 #include <stdlib.h> phead ClistCreate() // 创建循环链表 phead ph = (phead)malloc(sizeof(struct Head)); // 为头结点分配空间 33 if (ph == NULL) 34 printf(" 分配头结点失败!"); // 为了方便运行结果查看, 不设置 return 返回 35 // 创建好头结点后, 初始化头结点中数据 36 ph->length = 0; 37 ph->next = NULL; 38 return ph; // 将头结点返回 int IsEmpty(pHead ph) // 判断链表是否为空 if (ph == NULL) 44 printf(" 传入的循环链表有误!"); 45 if (ph->length == 0) // 如果长度为 0, 则链表为空 46 return 1; 47 else 48 return 0; int ClistInsert(pHead ph, int pos, int val) // 在链表的 pos 位置插入元素 val if (ph == NULL pos < 0 pos > ph->length) 55

35 56 printf(" 插入元素时, 参数传入有误!\n"); pnode pval = NULL; 60 // 参数传入无误, 则为新元素 val 分配结点 61 pval = (pnode)malloc(sizeof(struct Node)); 62 pval->data = val; // 将值 val 保存到此结点中 // 接下来要判断在哪个位置插入元素, 先判断链表是否为空 65 if (IsEmpty(ph)) // 如果链表为空 ph->next = pval; // 直接将结点插入到头结点后 68 pval->next = pval; // 将第一个结点指向它自己 else // 循环链表不为空, 则分为在头部插入 ( 即头结点后 ) 和普通位置插入 pnode prear = ph->next; 73 if (pos == 0) // 在第一个位置 ( 头结点后 ) 插入 // 在 0 号位置插入, 需要先找到尾结点 76 while (prear->next!= ph->next) // 循环结束的条件 prear = prear->next; //pcur 指针向后移动 //while 循环结束后,pRear 指向尾结点 81 // 然后插入元素 82 pval->next = ph->next; 83 ph->next = pval; 84 prear->next = pval; // 这三个步骤顺序不能更改 else // 如果不是 0 号位置插入, 则和单链表无区别 pnode pcur = ph->next; 89 for (int i = 1; i < pos; i++) // 就要遍历链表找到要插入的位置 pcur = pcur->next; //pcur 指针向后移 // 循环结束后, 此时 pcur 指向的是要插入的位置 94 pval->next = pcur->next; // 指针断开再连接的过程 95 pcur->next = pval; ph->length++; 99 return 1;

36 void print(phead ph) // 打印循环链表中的元素 if (ph == NULL ph->length == 0) printf(" 参数传入有误!"); pnode ptmp = ph->next; for (int i = 0; i < ph->length ; i++) printf("%d ", ptmp->data); 114 ptmp = ptmp->next; printf("\n"); 117 Joseph.c // 测试文件 118 #define _CRT_SECURE_NO_WARNINGS 119 #include "clist.h" 120 #include <stdio.h> 121 #include <stdlib.h> int main() int m, n; 126 printf(" 请输入约瑟夫环的总人数 :\n"); 127 scanf("%d", &m); 128 if (m <= 0) printf(" 请输入正确的数字!\n"); 131 return 0; printf(" 请输入出局者的报数 :\n"); 134 scanf("%d", &n); 135 if (n <= 0) printf(" 请输入正确的数字!\n"); 138 return 0; // 根据输入的 m 创建链表 142 phead ph = NULL;

37 143 ph = ClistCreate(); 144 if (ph == NULL) printf(" 创建循环链表失败!\n"); 147 return 0; // 插入元素 151 for (int i = m; i > 0; i--) ClistInsert(ph, 0, i); // 使用头插法从 m 到 1 倒序插入 print(ph); 157 printf(" 出局顺序 :\n"); 158 // 插入元素后, 就循环遍历链表 159 pnode node = ph->next; //node 指针指向第一个结点 160 while (node->next!= node) // 循环结束条件, 结点指向其自身, 此时剩最后一个结点 for (int i = 1; i < n - 1; i++) //i < n - 1, 报到 n 就重新开始 node = node->next; //for 循环结束后,node 指针指向待出局的结点的前驱结点 167 pnode ptmp = node->next; //ptmp 指向要被踢出的结点 // 接下来先要判断这个结点是 0 号位置的结点还是其他位置的结点 170 if (ptmp == ph->next) // 如果此结点在 0 号位置 ph->next = ptmp->next; // 头结点也要作处理 173 node->next = ptmp->next; 174 printf("%d ", ptmp->data); 175 free(ptmp); 176 ph->length--; else // 如果此结点在其他位置 node->next = ptmp->next; 181 printf("%d ", ptmp->data); 182 free(ptmp); 183 ph->length--; node = node->next; 186

38 187 node->next = node; 188 printf("\n"); //循环结束 只剩下 node 一个结点 让其指向自身 printf("链表中最后留下的是 "); 191 print(ph); system("pause"); 194 return 0; 195 运行结果如图 2-20 所示 图2-20 例 2-4 运行结果 在例 2-4 中 创建一个循环链表 以循环链表为基础来计算这一圈人的出局序列 并求 出最后留下来的人 解决约瑟夫问题并没有用到循环链表的全部算法 因此在本例中只实现 了此问题涉及的操作 首先创建一个循环链表 使用每位参与者信息初始化该链表 然后开 始遍历 第 159~187 行代码是将报数为 n 的结点删除 第 160 行代码的循环条件是 node->next!= node 即当链表中只剩一个结点时终止循环 while 循环里用一个 for 循环 第 行代码 来控制报数情况 报到 n 就将此结点删除 2.6 本章小结 本章作为进入数据结构部分的第一章 讲解了最简单的数据结构 线性表 具体包括 常用的顺序表 单链表 双向链表 循环链表 本章针对每一种表分析了它们的逻辑关系 存储原理 并给出了它们常用操作的详细代码实现 通过本章的学习 读者可以掌握线性表 的原理及实现 并使用线性表来解决一些简单的问题 为以后学习其他数据结构打下坚实的 基础 思考题 请从存储结构 基本操作两方面简述顺序表与链表的不同 之处 扫描右 维码 查看思考题答案 北京市昌平区建材城西路金燕龙办公楼一层 电话