如果要开发针对实际问题的计算机软件,首先要解决的问题是将现实问题进行抽象,转 化为适合编程处理的模型。这种模型不是纯粹的数学模型,而是一种可以描述问题的数据 组织形式,并且基于这种数据的组织形式可以设计解决问题的程序算法。由不同问题抽象 出来的数据组织形式有很大不同,人们进行了大量的研究,最终归纳总结出了少量常见的数 据组织形式,了解它们的逻辑形式、存储方式和有关算法对编程实践有很大的帮助。这些研 究所形成的一门新的计算机科学分支称为数据结构。 3.1 数据结构基本概念 这一节首先了解一下数据结构中的数据元素、数据结构分类以及算法等基础知识。 1. 数据和数据元素 数字、字符、声音、图像等都可以作为计算机处理的数据,但在不同问题中数据处理的基 本单位是不同的。例如,计算某个班级数学课的平均成绩,它是以数字类型作为基本数据单 位;在一张员工信息表中进行人员的插入、删除操作时,可以认为员工的个人信息为基本数 据单位。这些数据处理的基本单位在数据结构中就称为数据元素。数据结构这门学科研究 的各种数据组织形式就是由数据元素构成,对各种数据组织形式的操作大都也以数据元素 为单位。至于数据元素到底是某种单纯的数据类型,还是某些数据的结合体,并不是数据结 构所关注的内容。 2. 数据结构的类型 现实问题千姿百态,抽象出来的数据组织形式各不相同,而线性结构、树形数据和图状 结构是最常见的几种数据结构。下面分别举例说明。 第一个例子是个人通讯录。每个记录包含姓名、工作单位、电话、住址等信息。如果将 每个通信记录看作一个数据元素,那么整个通信录就是由若干数据元素组成的有限序列。 这种结构称为线性数据结构,其逻辑图如图3-1(a)所示。在现实中,这种结构最为常见。 第二个例子是书的目录管理。如果将各个章节看作数据元素,并将书名作为最上层的 数据元素,则书的目录结构就是如图3-1(b)所示的逻辑形式。这种数据结构称为树形数据 结构。相似的例子还有家谱结构、公司组织图等。 49 图3-1三种基本数据结构示意图 第三个例子是城市交通的调度管理。为了及时跟踪城市各处的交通状况,需要建立整 个城市的电子化交通图。如果将重要的路口、车站作为数据元素,并在数据元素之间按照交 通线的实际情况建立联系,则交通图的逻辑结构就如图3-1(c)所示。这种结构称为图状数 据结构。 树形和图状结构又统称为非线性数据结构。线性结构的元素之间存在确定的先后顺 序,非线性数据结构的元素之间不一定存在确定的先后顺序。以上三种结构都是数据的逻 辑结构。逻辑结构描述的是元素之间的逻辑关系,为了在计算机中实现并操作某种数据结 构,还要考虑数据的物理结构。 数据的物理结构又称为存储结构,是数据元素本身及元素之间的逻辑关系在计算机存 储空间中的映像。存储结构的形式有多种,最主要的两种形式是顺序存储结构和链式存储 结构。 在顺序存储结构中,数据元素存储在一组连续的存储单元中。元素存储位置间的关系 反映了元素间的逻辑关系。例如,在顺序表中,逻辑上相邻的元素存储在物理位置相邻的存 储单元中。顺序存储结构通常借助数组来实现。 在链式存储结构中,数据元素存储在若干不一定连续的存储单元中。它是通过在元素 中附加一个或多个与其逻辑上相连的其他元素的物理地址来建立元素间的逻辑关系。非线 性数据结构常常采用这种存储形式。 3. 算法和算法效率 算法是解决特定问题的步骤,通常被描述为一个程序语言能够实现的指令序列。算法 具有以下五个主要特征。 (1)有穷性:算法由有限条指令构成。 (2)确定性:算法的每条指令含义确切。即对任何初始条件该指令执行结果确定,且 对于相同的输入必然产生相同的输出。 (3)可行性:算法的每条指令都可以由程序语言在有限步内实现。 (4)输入:算法可以有零个或一组输入数据。 (5)输出:算法可以有零个或一组输出数据,它和输入数据有内在联系。 算法的描述可以利用自然语言、框图、伪语言或高级程序语言实现。本章的算法是通过 C++语言描述的。 衡量算法的效率应从时间和空间两个方面来考量,对应的两个主要指标是时间复杂度 和空间复杂度,分别表示一个算法对时间和空间的消耗情况。 时间复杂度的分析主要是考察关键指令重复执行的次数。例如,两个 n 阶方阵相加的 主要语句是两个 n 重循环嵌套,其形式如下: 50 for(i=1; i0,运算结果使得线性表的长度减1。 (7)插入新元素:在线性表L 的第i 个位置上插入元素x,运算结果使线性表长度加1。 线性表的存储结构主要有顺序存储结构和链式存储结构两种,分别称为顺序表和线性链表。 51 .3.2.2 顺序表概念及实现 1.顺序表的概念 采用顺序存储结构的线性表称为顺序表,它的数据元素按照逻辑顺序依次存放在一组 连续的存储单元中。逻辑上相邻的数据元素,其存储位置也彼此相邻。顺序表的存储结构 如图3-2所示。假定元素a1 的物理地址是Loc(a1),每个元素占用d 个存储单元,则第i 个元素的存储位置为: Loc(ai)=Loc(a1)+ (i-1)·d 图3-2 顺序表存储结构示意图 在实际应用中,顺序表可采用结构体类型描述如下。 typedef int DataType; //定义线性表的结构 typedef struct List { DataType* list; //指向线性表的指针 int length; //表长(从1 开始计数) int maxLength; //表容量(从1 开始计数) }ListType; 其中,DataType是某种数据类型的另一种表示,实际应用中需要用整型、浮点型、字符 串结构体或类的形式替代。具体实现要通过typedef语句,在上面的例子中DataType表示 int类型。 在构造顺序表时,一般利用一维数组来存储元素。由于线性表经常执行插入和删除元 素的操作,因此表的实际长度经常改变(在上面的结构体中用length表示)。而数组的长度 一般是固定的,所以为了容纳顺序表,一维数组的总长度应当足够大,在上面的结构体中用 maxLength表示。length初始长度为0(空表),最大不超过maxLength。 注意,在上面的结构体中list指针应当指向元素存储空间,该空间是DataType类型的 一维数组,长度为maxLength。这个空间需要在创建线性表的函数中动态创建,数组下标 从0到maxLength-1。 2.顺序表的主要算法 顺序表的每一种操作都对应一个算法。算法有很多,如创建顺序表、销毁线性表、判断 顺序表是否为空、获取顺序表实际长度、查找元素、删除元素、插入元素等。有些算法比较简 单,例如,判断顺序表是否为空只需判断length是否为零即可。 顺序表的主要算法是在顺序表中插入元素、删除元素以及查找元素。下面对这几种算 法进行简单描述。 (1)在表中pos位置插入新元素data。 算法实现的主要步骤是: 52 第一步,判断插入位置的合理性以及表是否已满。 第二步,从末尾元素开始向前直到pos位置为止,依次将每个元素后移一个位置。 第三步,向空出的pos位置存入新元素data。 第四步,将线性表长度加1。 【注】 这里pos是数组下标,从0开始计数,删除和查找算法中也是如此。 (2)将pos位置处的元素删除。 算法实现的主要步骤是: 第一步,判断删除位置的合理性。 第二步,从pos位置的后一个元素开始,依次向后直到最后一个元素为止,将每个元素 前移一个位置。这时pos位置元素已经被覆盖删除。 第三步,最后将线性表长度减1。 (3)在表中查找某个元素。 查找元素的情况比较复杂。如果数据元素是整数、实数这些基本数据类型,那么查找元 素时自然就是与数据元素本身进行对比。如果数据元素是包含多个属性的结构体或类对 象,那么查找元素时往往是与数据元素的某个属性比较。例如,将学生信息记录作为数据元 素,学生信息表就是一个线性表。在此表中查询某个学生信息时,一般是根据学号或姓名进 行查询,而学号或姓名仅是学生信息的一部分。 下面是根据数据元素本身的值进行查询的算法。从pos位置起查找data第一次出现 的位置,算法返回元素的实际位置。算法描述为: 设n 从位置pos开始循环比较list[n]和data,若不等则n 加1后重新做比较,直到n 为末尾位置为止;若相等则输出位置n,跳出循环结束程序;若循环结束都没有找到等于 data的元素则查找失败。 如果要根据数据元素的某个属性查询,则修改比较条件为list[n].parm==data即可。 其中,parm 表示数据元素某个具体属性,data为需要查找的属性的值。 3.基本顺序表的实现 这里设计一个元素类型为整数的顺序表,包括创建表的函数、销毁表的函数、置空表、获 取第n 个元素的前驱、获取第n 个元素的后继、查找元素、插入元素、删除元素等一系列函 数。由于各个函数都有比较详细的注释,这里不再做其他说明。 【例3-1】 以整数为元素的顺序表。 #include #include /* 此处将整数重定义为DataType */ typedef int DataType; //定义线性表的结构 typedef struct List { DataType* list; //指向线性表的指针 int length; //表长 53 int maxLength; //表容量 }ListType; //声明线性表具有的方法 ListType* CreateList(int length); //创建一个长度为length 的线性表 void DestroyList(ListType* pList); //销毁线性表 void ClearList(ListType* pList); //置空线性表 int IsEmptyList(ListType* pList); //检测线性表是否为空 int GetListLength(ListType* pList); //获取线性表长度 int GetListElement(ListType* pList, int n, DataType* data); //获取线性表中第n 个元素 //从pos 起查找data 第1 次出现的位置 int FindElement(ListType* pList, int pos, DataType data); int GetPriorElement(ListType* pList, int n, DataType* data); //获取第n 个元素的前驱 int GetNextElement(ListType* pList, int n, DataType* data); //获取第n 个元素的后继 int InsertToList(ListType* pList, int pos, DataType data); //将data 插入pos 处 int DeleteFromList(ListType* pList, int pos); //删除线性表上位置为pos 的元素 void PrintList(ListType* pList); //输出线性表 //线性表方法实现 /** *@brief 创建一个新的线性表 *@param length 线性表的最大容量 *@return 成功返回指向该表的指针,否则返回NULL */ ListType* CreateList(int length) { ListType* sqList=(ListType*)malloc(sizeof(ListType)); if(sqList != NULL) { //为线性表分配内存 sqList->list =(DataType*)malloc(sizeof(DataType)*length); //如果分配失败,返回NULL if(sqList->list == NULL) return NULL; //置为空表 sqList->length = 0; //最大长度 sqList->maxLength = length; } return sqList; } /** *@brief 销毁线性表 *@param pList 指向需要销毁的线性表的指针 */ void DestroyList(ListType* pList) 54 { free(pList->list); } /** *@brief 置空线性表 *@param pList 指向需要置空线性表的指针 */ void ClearList(ListType* pList) { pList->length = 0; } /** *@brief 检测线性表是否为空 *@param pList 指向线性表的指针 *@return 如果线性表为空,返回1;否则返回0 */ int IsEmptyList(ListType* pList) { return pList->length == 0 ? 1 : 0; } /** *@brief 获取线性表长度 *@param pList 指向线性表的指针 *@return 线性表的长度 */ int GetListLength(ListType* pList) { return pList->length; } /** *@brief 获取线性表中第n 个元素 *@param pList 指向线性表的指针 *@param n 要获取元素在线性表中的位置 *@param data 获取成功,取得元素存放于data 中 *@return 获取成功返回1, 失败则返回0 */ int GetListElement(ListType* pList, int n, DataType* data) { if(n<0 || n>pList->length - 1) return 0; *data = pList->list[n]; return 1; } /** *@brief 从pos 起查找data 第一次出现的位置 *@param pList 指向线性表的指针 *@param pos 查找的起始位置 *@param data 要查找的元素 *@return 找到则返回该位置, 未找到,返回-1 */ 55 int FindElement(ListType* pList, int pos, DataType data) { for(int n = pos; n < pList->length; ++n) { if(data == pList->list[n]) return n; } return -1; } /** *@brief 获取第n 个元素的前驱 *@param pList 指向线性表的指针 *@param n n 的前驱 *@param data 获取成功,取得元素存放于data 中 *@return 找到则返回前驱的位置(n-1), 未找到,返回-1 */ int GetPriorElement(ListType* pList, int n, DataType* data) { if(n < 1 || n>pList->length-1) return -1; *data = pList->list[n - 1]; return n-1; } /** *@brief 获取第n 个元素的后继 *@param pList 指向线性表的指针 *@param n n 的后继 *@param data 获取成功,取得元素存放于data 中 *@return 找到则返回后继的位置(n+1), 未找到,返回-1 */ int GetNextElement(ListType* pList, int n,DataType* data) { if(n<0 || n>pList->length - 2) return -1; *data = pList->list[n + 1]; return n+1; } /** *@brief 将data 插入线性表的pos 位置处 *@param pList 指向线性表的指针 *@param pos 插入的位置 *@param data 要插入的元素存放于data 中 *@return 成功,返回新的表长(原表长+1), 失败,返回-1 */ int InsertToList(ListType* pList, int pos, DataType data) { //如果插入的位置不正确或者线性表已满,则插入失败 if(pos<0 || pos>pList->length || pList->length == pList->maxLength) return -1; //从pos 起,所有的元素向后移动1 位 56 for(int n = pList->length; n > pos; --n) { pList->list[n]= pList->list[n - 1]; } //插入新的元素 pList->list[pos]= data; //表长增加1 return ++pList->length; } /** *@brief 将pos 位置处的元素删除 *@param pList 指向线性表的指针 *@param pos 删除元素的位置 *@return 成功,返回新的表长(原表长-1), 失败,返回-1 */ int DeleteFromList(ListType* pList, int pos) { if(pos<0 || pos>pList->length) return -1; //将pos 后的元素向前移动一位 for(int n = pos; n < pList->length - 1; ++n) pList->list[n]= pList->list[n + 1]; return --pList->length; } /** *@brief 输出线性表 *@param pList 指向线性表的指针 */ void PrintList(ListType* pList) { for(int n = 0; n < pList->length; ++n) printf("第%d 项: %d\n", n, pList->list[n]); } /* 主函数,创建一个线性表,并测试*/ int main() { const int MAXLENGTH = 1000; //假设最大容量为1000 //创建线性表 ListType* sqList = CreateList(MAXLENGTH); //以下是对线性表的测试 ClearList(sqList); //置表为空 //插入10 个元素并显示 for(int i = 0; i < 10; ++i) InsertToList(sqList, i, i + 1); //输出线性表 PrintList(sqList); //在位置5 插入99 并显示 InsertToList(sqList, 5, 99); printf("插入99 后的线性表\n"); 57 PrintList(sqList); //删除第8 个元素 DeleteFromList(sqList, 8); printf("删除第8 个元素后的线性表\n"); PrintList(sqList); //显示第3 个元素的前驱 DataType data; if(GetPriorElement(sqList, 3, &data) > -1); printf("第3 个元素的前驱是%d\n", data); return 0; } 【运行结果】 第0 项: 1 第1 项: 2 第2 项: 3 第3 项: 4 第4 项: 5 第5 项: 6 第6 项: 7 第7 项: 8 第8 项: 9 第9 项: 10 插入99 后的线性表 第0 项: 1 第1 项: 2 第2 项: 3 第3 项: 4 第4 项: 5 第5 项: 99 第6 项: 6 第7 项: 7 第8 项: 8 第9 项: 9 第10 项: 10 删除第8 个元素后的线性表 第0 项: 1 第1 项: 2 第2 项: 3 第3 项: 4 第4 项: 5 第5 项: 99 第6 项: 6 第7 项: 7 第8 项: 9 第9 项: 10 第3 个元素的前驱是3 本例可看作一个基本顺序表的模板。在创建顺序表时使用malloc()函数分配数组空 58 间。在获取第n 个元素的前驱的函数中,利用指针获得返回的数据,其函数原型如下: int GetPriorElement(ListType* pList, int n, DataType* data) 这里通过data指针将函数外的变量地址传入函数中,并在函数中修改这个外部变量, 也就是将前驱的内容放入该外部变量。而返回值仅表示是否正确得到前驱的值。另一个获 取第n 个元素后继的函数与此函数类似。 .3.2.3 顺序表应用:学生名册管理 这里编写一个学生名册管理程序。要求实现下列功能。 ● 可以在花名册中任何位置插入新生学号和姓名。 ● 可以根据学号删除学生信息。 ● 可以输出整个名单。 【例3-2】 利用顺序表建立学生名册管理程序。 本例是以例3-1的顺序表为基础,做适当修改从而实现学生信息管理。下面仅给出与 例3-1的程序不同的部分(用粗体表示)。 【程序实现】 #include #include #include //包含字符串处理的头文件 //这里将学生的学号和姓名定义成数据元素 struct STU { int id; //学号 char name[20]; //姓名 }; /* 此处将STU 重定义为DataType,以便使用其他函数*/ typedef STU DataType; … 与例3-1 相同部分省略… /* 下面是按照学号id 进行查找的函数*/ int FindElement(ListType* pList, int pos, int id) { for(int n = pos; n < pList->length; ++n) { if(id == pList->list[n].id) //比较学号 return n; } return -1; } … 与例3-1 相同部分省略… /* 输出每个学生的学号、姓名*/ 59 void PrintList(ListType* pList) { for(int n = 0; n < pList->length; ++n) printf("%d %s\n", pList->list[n].id, pList->list[n].name); } … 与例3-1 相同部分省略… /*主函数测试顺序表。 *首先录入三个学生信息,再显示出来,最后删除一个记录 */ int main() { const int MAXLENGTH = 1000; //假设最大容量为1000 ListType* sqList = CreateList(MAXLENGTH); //创建线性表 //插入三个元素 DataType s[5]; printf("请输入三个学生的学号、姓名: \n"); printf("----------------------------- \n"); for(int i = 0; i < 3; i++) scanf("%d %s", &s[i].id, &s[i].name); InsertToList(sqList, 0, s[0]); InsertToList(sqList, 1, s[1]); InsertToList(sqList, 2, s[2]); //输出线性表 PrintList(sqList); //删除元素 int id; printf("\n 输入将要删除的学生的学号: \n"); scanf("%d",&id); int pos = FindElement(sqList, 0, id); DeleteFromList(sqList, pos); PrintList(sqList); return 0; } 【运行结果】 请输入三个学生的学号、姓名: ----------------------------- 9930206 张强 9930205 李维 9930202 刘淇 所有学生的信息 ----------------------------- 9930206 张强 9930205 李维 9930202 刘淇 60 输入将要删除的学生的学号: 9930205 所有学生的信息 ----------------------------- 9930206 张强 9930202 刘淇 实际上,数据结构的算法绝非一成不变的东西,在实际编程中数据结构的标准算法往往 要有所变化。 .3.2.4 链表的概念及实现 顺序表存储在连续的空间中(即数组中),因此每个元素的存储位置可用一个简单的公 式计算得到,所以访问表中某个元素的效率是很高的。但是,正是由于顺序表是连续的,如 果对某一顺序表进行插入和删除操作时,为了保持元素在存储区域的连续性,必须移动大量 的元素。例如,在插入操作中,需要后移若干元素给新元素腾位置,或者在删除操作中,又必 须移动大量后继元素补缺,因此在顺序表中执行插入删除操作时效率并不算高。 而链式结构则刚好具有不同的特点。在链式结构中访问某一个位置的元素速度不快, 而单纯的插入删除操作则效率很高。采用链式存储结构的线性表有单链表、双向链表、单循 环链表以及双向循环链表等多种形式。其中,单链表是最简单的形式。 1.单链表的概念 单链表用一组地址任意的存储单元存放线性表中的数据元素。由于逻辑上相邻的元素 其物理位置不一定相邻,为了建立元素间的逻辑关系,需要在线性表的每个元素中附加其后 继元素的地址信息。这种地址信息称为指针。附加了其他元素指针的数据元素称为结点 (如图3-3所示),每个结点都包含数据域和指针域两部分。结点的形式定义如下。 typedef struct NODE { datatype data; //数据域 Node* next; //指针域 }Node; 这个定义是自引用类型的。换言之,每个结点都包含另一个同类型结点的地址。单链 表就是由这样定义的结点依次连接而成的单向链式结构,如图3-4所示。特别要说明的是, 虽然不同结点存储位置是分散的,但每个结点所包含的数据项却是存放在一小块连续的空 间中。假如结点包含各占4B的一个整数和一个指针(4B),则整个结点将占据8B的连续空 间。结点的指针存放的就是整个结点所占空间的起始地址。由于结点中各部分数据的相对 位置不变,所以通过起始地址就可知道各部分数据的值。 图3-3 单链表的结点 图3-4 带头结点的单链表 61 图3-4中结点内指向后一结点的箭头代表当前结点指针域存储的正是箭头所指结点的 地址。由于最后一个元素无后继,因而其指针域为空(NULL)。另外,为了能顺次访问每个 结点,需要保存单链表第一个结点的存储地址。这个地址称为线性表的头指针,本章用 head表示。为了操作方便,可以在单链表的头部增加一个特殊的头结点。头结点的类型与 其他结点一样,只是头结点的数据域为空。增加头结点避免了在删除或添加第一个位置的 图3-5 单链表存储结构示意图 元素时进行的特殊程序处理。图3-4为带头结点的单链表。 单链表在存储区的物理状态如图3-5所示。head中存放 头结点地址,根据后续结点的指针可以顺次访问所有结点的 数据。单 链表不需要事先分配结点空间,而是在插入结点时动 态申请结点空间。反之,在单链表中删除结点时,结点所占空 间可以立刻释放出来。单链表的长度和所占空间是动态变化 的。在定义一个带头结点的单链表时,只需定义头指针和一 个头结点即可。可用下面几条语句实现。 Node* head; //定义头指针 head =(Node*)malloc(sizeof(Node)); //定义头结点 head->next = NULL; //头结点指针域为空 如果定义一个不带头结点的单链表,则只需定义头指针。 2.单链表的主要算法 单链表也是线性表,也有插入删除等操作。下面给出单链表的若干算法描述。 (1)指针p 如何在链表中向后移动。 对单链表结点的访问一般通过指针进行。假如p 为指向某一结点的指针,则p->data 和p->next就是该结点的数据域和指针域变量,它们可以被赋值,也可以向其他变量赋值。 如果p 为指向结点ai 的指针,q 为另一指针变量,那么p->next就是指向ai 后继结点 ai+1的指针,这时如果执行语句q=p->next就将q 也变为指向结点ai+1的指针。进一步将 q 换为p,语句p=p->next则将p 自身从指向结点ai 的指针变为指向结点ai+1的指针,从 而实现指针后移。在单链表中正是通过指针后移操作访问任意一个结点的。另外,头指针 head在单链表中一般是不后移的。因为head向后移动后,head指针所指结点的前面的结 点就无法访问了,除非将链表变成首尾相连的单循环链表。 (2)求单链表的长度。 单链表长度不定,要确定链表长度需要走遍表中所有结点才能算出。 第一步,设定指针p 指向第一个元素所在结点,置长度变更量L=0。 第二步,如果p 非空,则长度L 加1,再利用p=p->next后移指针,直到p 为空结束。 这时L 就是表长。 (3)从单链表中删除第i 个结点。 为了从单链表中删除第i 个结点,需进行如下操作。 第一步,如果第i 个结点存在则找到第i 和第i-1个结点的指针p 和q。 第二步,通过语句q->next=p->next将第i-1个结点的指针赋值为第i 个结点的指 62 针,从而将第i 个结点从链表中断开。 第三步,释放第i 个结点所占空间以便于重用。 图3-6显示了删除结点前后链表中指针的变化。 图3-6 在单链表中删除结点ai (4)在第i 个位置插入新结点x。 为了在链表的第i 个位置插入一个新结点,需进行如下操作。 第一步,找到第i-1个结点的指针p。 第二步,建立新结点s 并通过语句s->next=p->next将其指针指向第i 个结点。 第三步,通过语句p->next=s 将第i-1个结点的指针指向新结点。 图3-7给出了插入新结点前后链表指针的变化。 图3-7 在单链表中的插入结点x (5)在单链表中查找某个结点。 可以按照数据元素本身的值进行查找,也可以按照数据元素的某个属性进行查找。这 里仅给出按照数据元素本身的值进行查找的算法。 第一步,设定指针p 指向第一个元素所在结点。 第二步,如果p 非空并且p->data不是要查找的元素,则利用p=p->next后移指针, 继续比较,直到p 为空结束,这时查找失败;如果p->data正是要查找的元素,则返回结点 地址指针p,程序结束。 在查找失败时返回空值NULL。 3.单链表的实现 这里实现一个元素类型为整数的单表,包括求表长、销毁表、置空表、获取第n 个元素 的前驱、获取第n 个元素的后继、查找元素、插入元素、删除元素等一系列函数。 【例3-3】 以整数为元素的单链表。 #include #include //假设使用的是整数链表 typedef int DataType; //单链表的结点定义 typedef struct NODE Node; typedef struct NODE 63 { DataType data; //数据域 Node* next; //指针域 }Node; //头指针 typedef Node* Head; //链表的方法声明 int GetLinkListLength(Head head); //求表长 void DestroyLinkList(Head head); //销毁链表 int GetElement(Head head, int n, DataType* data); / /获 取线性表中第n 个元素 int FindElement(Head head, DataType data); / /查 找data 第一次出现的位置 int GetPriorElement(Head head, int n, DataType* data); //获取第n 个元素的前驱 int GetNextElement(Head head, int n, DataType* data); //获取第n 个元素的后继 int DeleteFromList(Head* head, int pos); // 删 除下标位置为pos 的元素 int InsertToList(Head* head, int pos, DataType data); //将data 插入到pos(下标)处 int InsertRear(Head* head, DataType data); // 从表尾插入元素 int InsertHead(Head* head, DataType data); // 从表头插入元素 void PrintList(Head head); //输出线性表 //链表的方法实现 /** *@brief 求表长 *@param head 链表的头指针 *@return 链表的长度 */ int GetLinkListLength(Head head) { if(head == NULL) return 0; int i = 1; Node* pNode = head; while(pNode->next) //!=NULL { i++; pNode = pNode->next; //下一结点 } return i; } /** *@brief 销毁链表 *@param head 链表的头指针 */ void DestroyLinkList(Head head) { //从头开始,依次释放每一个结点 Node* pNode; while(head) { pNode = head; head = head->next; //指向下一个结点 64 free(pNode); //释放当前结点 } } /** *@brief 获取线性表中第n 个元素,第一个元素的位置为0 *@param head 链表的头指针 *@param n 要获取的元素位置 *@param data 获取的数据存放于此 *@return 获取成功返回1, 失败则返回0 */ int GetElement(Head head, int n, DataType* data) { if(n<0 || n>GetLinkListLength(head) - 1) return 0; for(int i = 0; i < n; ++i) head = head->next; //移动到位置n *data = head->data; return 1; } /** *@brie 查找data 第一次出现的位置 *@param head 指向线性表的头指针 *@param data 要查找的元素 *@return 找到则返回该位置, 未找到则返回-1 */ int FindElement(Head head, DataType data) { int i = 0; while(head) { if(head->data == data) //找到 return i; head = head->next; //下一个结点 i++; } return -1; } /** *@brief 获取第n 个元素的前驱 *@param head 指向线性表的头指针 *@param n n 的前驱 *@param data 获取成功,取得元素存放于data 中 *@return 找到则返回前驱的位置(n-1), 未找到则返回-1 */ int GetPriorElement(Head head, int n, DataType* data) { if(n<1 || n>GetLinkListLength(head) - 1) return -1; for(int i = 0; i < n - 1; ++i) head = head->next; //移动到n-1 65 *data = head->data; return n - 1; } /** *@brief 获取第n 个元素的后继 *@param head 指向线性表的头指针 *@param n n 的后继 *@param data 获取成功,取得元素存放于data 中 *@return 找到则返回前驱的位置(n+1), 未找到则返回-1 */ int GetNextElement(Head head, int n, DataType* data) { if(n<0 || n>GetLinkListLength(head) - 2) return -1; for(int i = 0; i < n + 1; ++i) head = head->next; //移动到n *data = head->data; return n + 1; } /** *@brief 将data 插入pos 处 *@param head 指向线性表的头指针 *@param pos 插入的位置 *@param data 要插入的数据 *@return 插入成功返回新的表长,否则返回-1 */ int InsertToList(Head* head, int pos, DataType data) { Node* pNode = *head; int length = GetLinkListLength(pNode); //得到表长 if(pos<0 || pos> length) return -1; //插入的位置不对 if(pos == 0) //在表头插入 return InsertHead(head, data); if(pos == length - 1) //在表尾插入 return InsertRear(head, data); //定位到pos 前1 位置 for(int i = 0; i < pos - 1; ++i) pNode = pNode->next; //生成一个新的结点 Node* pNewNode =(Node*)malloc(sizeof(Node)); if(pNewNode == NULL) return -1; //分配内存失败 pNewNode->data = data; //存入要插入的数据 pNewNode->next = pNode->next; //插入链表 pNode->next = pNewNode; //返回新的链表长度 return ++length; } 66 /** *@brief 删除线性表上位置为pos 的元素 *@param head 指向线性表的头指针 *@param pos 删除的位置 *@return 插入成功返回新的表长,否则返回-1 */ int DeleteFromList(Head* head, int pos) { Node* pNode = *head; int length = GetLinkListLength(*head); //得到表长 if(pos<0 || pos> length - 1) //删除的位置不对 return -1; Node* pDeleteNode; if(pos > 0) { for(int i = 0; i < pos - 1; ++i) pNode = pNode->next; //获得pos 的前驱指针 pDeleteNode = pNode->next; //暂存待删除结点指针 pNode->next = pNode->next->next; //修改前驱结点指针 } if(pos == 0) { pDeleteNode = *head; //暂存待删除结点指针 *head =(*head)->next; } free(pDeleteNode); //释放删除结点的空间 return --length; } /** *@brief 从表尾插入元素 *@param head 指向线性表的头指针 *@param data 插入的数据 *@return 插入成功返回新的表长,否则返回-1 */ int InsertRear(Head* head, DataType data) { //准备新数据 Node* pNewNode =(Node*)malloc(sizeof(Node)); if(pNewNode == NULL) //内存分配失败 return -1; pNewNode->data = data; if(*head == NULL) //如果是空表 { *head = pNewNode; pNewNode->next = NULL; return 1; //表长为1 } //找到表尾 Node* pNode = *head; while(pNode->next) pNode = pNode->next; 67 //插入到表尾 pNode->next = pNewNode; pNewNode->next = NULL; //返回新的表长 return GetLinkListLength(*head); } /** *@brief 从表头插入元素 *@param head 指向线性表的头指针 *@param data 插入的数据 *@return 插入成功返回新的表长,否则返回-1 */ int InsertHead(Head* head, DataType data) { //准备新数据 Node* pNewNode =(Node*)malloc(sizeof(Node)); if(pNewNode == NULL) //内存分配失败 return -1; pNewNode->data = data; //插入 pNewNode->next =(*head); //新结点指向原来的第一个结点 *head = pNewNode; //修改头指针,指向新结点 //返回新的表长 return GetLinkListLength(*head); } /** *@brief 输出线性表 *@param head 指向线性表的头指针 */ void PrintList(Head head) { int n = 0; while(head) { printf("第%d 项元素为%d\n", n, head->data); head = head->next; ++n; } } //主函数 int main() { //创建一个空的线性表 Head head = NULL; //以下是对线性表的测试 //插入5 个元素并显示 for(int i = 0; i < 5; ++i) InsertToList(&head, i, i + 1);