《概论线性表new.ppt》由会员分享，可在线阅读，更多相关《概论线性表new.ppt（83页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、第第1 1章章 数据结构概论数据结构概论 本章主要介绍以下内容本章主要介绍以下内容l 数据结构研究的主要内容数据结构研究的主要内容l 数据结构中涉及的基本概念数据结构中涉及的基本概念l 算法的概念、描述方法以及评价标准算法的概念、描述方法以及评价标准1.1 1.1 数据结构研究的主要内容数据结构研究的主要内容当今计算机应用的特点：当今计算机应用的特点：l l 所处理的数据量大且具有一定的关系；所处理的数据量大且具有一定的关系；2 2 对其操作不再是单纯的数值计算，而更多地是需要对其操作不再是单纯的数值计算，而更多地是需要对其进行组织、管理和检索。对其进行组织、管理和检索。应用举例应用举例1 1
2、学籍档案管理学籍档案管理 假设一个学籍档案管理系统应包含如下表假设一个学籍档案管理系统应包含如下表1-11-1所示所示的学生信息。的学生信息。表表表表1-11-1 特点：特点：l l 每个学生的信息占据一行，所有学生的信息按学号每个学生的信息占据一行，所有学生的信息按学号顺序依次排列构成一张表格；顺序依次排列构成一张表格；2 2 表中每个学生的信息依据学号的大小存在着一种前表中每个学生的信息依据学号的大小存在着一种前后关系，这就是我们所说的线性结构；后关系，这就是我们所说的线性结构；3 3 对它的操作通常是插入某个学生的信息，删除某个对它的操作通常是插入某个学生的信息，删除某个学生的信息，更新
3、某个学生的信息，按条件检索某个学生学生的信息，更新某个学生的信息，按条件检索某个学生的信息等等。的信息等等。应用举例应用举例2 2输出输出n n个对象的全排列个对象的全排列 输出输出n n个对象的全排列可以使用下图个对象的全排列可以使用下图1-11-1所示的形式描述。所示的形式描述。图图 1-1 3个对象的全排列过程个对象的全排列过程特点：特点：l l在求解过程中，所处理的数据之间具有层次关系，这在求解过程中，所处理的数据之间具有层次关系，这是我们所说的树形结构；是我们所说的树形结构；l l对它的操作有：建立树形结构，输出最低层结点内容对它的操作有：建立树形结构，输出最低层结点内容等等。等等。
4、应用举例应用举例3 3制定教学计划制定教学计划 在制定教学计划时，需要考虑各门课程的开设顺序。在制定教学计划时，需要考虑各门课程的开设顺序。有些课程需要先导课程，有些课程则不需要，而有些课程有些课程需要先导课程，有些课程则不需要，而有些课程又是其他课程的先导课程。比如，计算机专业课程的开设又是其他课程的先导课程。比如，计算机专业课程的开设情况如下表情况如下表1-21-2所示：所示：表表1-2课程先后关系的图形描形式：课程先后关系的图形描形式：c1c9c4c2c12c10c11c5c3c6c7c8图图 1-2 计算机专业必修课程开设先后关系计算机专业必修课程开设先后关系 特点特点 l l课程之间
5、的先后关系用图结构描述；课程之间的先后关系用图结构描述；2 2通过实施创建图结构，按要求将图结构中的顶点进行通过实施创建图结构，按要求将图结构中的顶点进行线性排序。线性排序。结论结论 计算机的操作对象的关系更加复杂，操作形式不再是计算机的操作对象的关系更加复杂，操作形式不再是单纯的数值计算，而更多地是对这些具有一定关系的数据单纯的数值计算，而更多地是对这些具有一定关系的数据进行组织管理，我们将此称为非数值性处理。要使计算机进行组织管理，我们将此称为非数值性处理。要使计算机能够更有效地进行这些非数值性处理，就必须弄清楚这些能够更有效地进行这些非数值性处理，就必须弄清楚这些操作对象的特点，在计算机
6、中的表示方式以及各个操作的操作对象的特点，在计算机中的表示方式以及各个操作的具体实现手段。这些就是具体实现手段。这些就是数据结构数据结构这门课程研究的主这门课程研究的主要内容。要内容。1.2 1.2 基本概念和术语基本概念和术语数据数据 是对客观事物的符号表示。在计算机科学中其含义是指是对客观事物的符号表示。在计算机科学中其含义是指所有能够输入到计算机中并被计算机程序处理的符号集合。所有能够输入到计算机中并被计算机程序处理的符号集合。数据元素数据元素 是数据集合中的一个实体，是计算机程序中加工处理的是数据集合中的一个实体，是计算机程序中加工处理的基本单位。基本单位。数据元素按其组成可分为简单型
7、数据元素和复杂型数据数据元素按其组成可分为简单型数据元素和复杂型数据元素。简单型数据元素由一个数据项组成，所谓数据项就是元素。简单型数据元素由一个数据项组成，所谓数据项就是数据中不可再分割的最小单位；复杂型数据元素由多个数据数据中不可再分割的最小单位；复杂型数据元素由多个数据项组成，它通常携带着一个概念的多方面信息。项组成，它通常携带着一个概念的多方面信息。数据结构数据结构 简单地说，就是相互之间存在一种或多种特定关系的数简单地说，就是相互之间存在一种或多种特定关系的数据元素的集合。常见的数据结构有：线性结构、树形结构和据元素的集合。常见的数据结构有：线性结构、树形结构和图形结构。图形结构。逻
8、辑结构逻辑结构 数据结构中所说的数据结构中所说的“关系关系”实际上是指数据元素之间的实际上是指数据元素之间的逻辑关系，又称此为逻辑结构逻辑关系，又称此为逻辑结构。存储结构存储结构（物理结构）（物理结构）是指数据结构在计算机存储器中的具体实现。与孤立是指数据结构在计算机存储器中的具体实现。与孤立的数据元素表示形式不同，数据结构中的数据元素不但要的数据元素表示形式不同，数据结构中的数据元素不但要表示其本身的实际内容，还要表示清楚数据元素之间的逻表示其本身的实际内容，还要表示清楚数据元素之间的逻辑结构。辑结构。常见的存储结构常见的存储结构 顺序存储结构：特点是借助于数据元素的相对存储位顺序存储结构：
9、特点是借助于数据元素的相对存储位置来表示数据元素之间的逻辑结构；置来表示数据元素之间的逻辑结构；链式存储结构：特点是借助于指示数据元素地址的指链式存储结构：特点是借助于指示数据元素地址的指针表示数据元素之间的逻辑结构。针表示数据元素之间的逻辑结构。1.3 1.3 算法算法 1.3.1 1.3.1 算法的概念算法的概念 算法是解决某个特定问题的一种方法或一个过程。算法是解决某个特定问题的一种方法或一个过程。计算机对数据的操作可以分为数值性和非数值性计算机对数据的操作可以分为数值性和非数值性两种类型。在数值性操作中主要进行的是算术运算；两种类型。在数值性操作中主要进行的是算术运算；而在非数值性操作
10、中主要进行的是检索、排序、插入、而在非数值性操作中主要进行的是检索、排序、插入、删除等等。删除等等。设计算法的基本过程设计算法的基本过程 l l通过对问题进行详细地分析，抽象出相应的数学模型；通过对问题进行详细地分析，抽象出相应的数学模型；2 2确定使用的数据结构，并在此基础上设计对此数据结确定使用的数据结构，并在此基础上设计对此数据结构实施各种操作的算法；构实施各种操作的算法；3 3选用某种语言将算法转换成程序；选用某种语言将算法转换成程序；4 4调试并运行这些程序。调试并运行这些程序。算法应该具有下列五个特性算法应该具有下列五个特性（1 1）有穷性：有穷性：一个算法必须在执行有穷步之后结束
11、。一个算法必须在执行有穷步之后结束。（2 2）确定性确定性：算法中的每一步，必须有确切的含义，在他：算法中的每一步，必须有确切的含义，在他人理解时不会产生二义性。人理解时不会产生二义性。（3 3）可行性可行性：算法中描述的每一步操作都可以通过已有的：算法中描述的每一步操作都可以通过已有的基本操作执行有限次实现。基本操作执行有限次实现。（4 4）输入：输入：一个算法应该有零个或多个输入。一个算法应该有零个或多个输入。（5 5）输出：输出：一个算法应该有一个或多个输出。这里所说的一个算法应该有一个或多个输出。这里所说的输出是指与输入有某种特定关系的量。输出是指与输入有某种特定关系的量。举例举例问题
12、：按从小到大的顺序重新排列问题：按从小到大的顺序重新排列x x，y y，z z三个数值的内容。三个数值的内容。算法：算法：（1 1）输入）输入x x，y y，z z三个数值；三个数值；（2 2）从三个数值中挑选出最小者并换到）从三个数值中挑选出最小者并换到x x中；中；（3 3）从）从y y，z z中挑选出较小者并换到中挑选出较小者并换到y y中；中；（4 4）输出排序后的结果。）输出排序后的结果。1.3.2 1.3.2 算法的描述算法的描述 选择算法描述语言的准则选择算法描述语言的准则（1 1）该语言应该具有描述数据结构和算法的基本功能；）该语言应该具有描述数据结构和算法的基本功能；（2 2
13、）该语言应该尽可能地简捷，以便于掌握、理解；）该语言应该尽可能地简捷，以便于掌握、理解；（3 3）使用该语言描述的算法应该能够比较容易地转换成任）使用该语言描述的算法应该能够比较容易地转换成任何一种程序设计语言。何一种程序设计语言。“类类C”C”描述语言是通过对描述语言是通过对C C语言进行精心筛选保留语言进行精心筛选保留的一个核心子集，并为了便于描述，又做了若干扩展修的一个核心子集，并为了便于描述，又做了若干扩展修改，从而，增强了语言的描述功能。改，从而，增强了语言的描述功能。1.1.预定义常量及类型预定义常量及类型#define TRUE 1#define TRUE 1#define FA
14、LSE 0#define FALSE 0#define OK 1#define OK 1#define ERROR 0#define ERROR 0#define OVERFLOW -1#define OVERFLOW -1 数据元素被约定数据元素被约定为为dateTypedateType 类型，用户需要根据类型，用户需要根据具体情况，自行定义该数据类型。具体情况，自行定义该数据类型。2.2.算法描述为以下的函数形式：算法描述为以下的函数形式：函数类型函数类型 函数名（函数参数表）函数名（函数参数表）语句序列；语句序列；为了简化函数的书写，提高算法描述的清晰度，为了简化函数的书写，提高算法描述
15、的清晰度，我们规定除函数参数表中的参数需要说明数据类型外，我们规定除函数参数表中的参数需要说明数据类型外，函数中使用的局部变量可以不做变量说明，必要时给函数中使用的局部变量可以不做变量说明，必要时给出相应的注释即可。另外，在书写算法时，应该养成出相应的注释即可。另外，在书写算法时，应该养成对重点语句段落添加注解的良好习惯。对重点语句段落添加注解的良好习惯。3.3.在算法描述中可以使用的赋值语句形式有：在算法描述中可以使用的赋值语句形式有：简单赋值简单赋值 变量名变量名 =表达式；表达式；串联赋值串联赋值 变量名变量名1=1=变量名变量名2=.=2=.=变量名变量名n=n=表达式；表达式；成组赋
16、值成组赋值 （变量名（变量名1 1，.，变量名，变量名n n）=（表达式表达式1 1，.，表达式表达式n n）；）；结构赋值结构赋值 结构名结构名1=1=结构名结构名2 2；结构名结构名 =（值（值1 1，值，值2 2，.，值，值n n）；）；条件赋值条件赋值 变量名变量名 =条件表达式条件表达式?表达式表达式1 1：表达式：表达式2 2；交换赋值交换赋值 变量名变量名1 1 变量名变量名2 2；4.4.在算法描述中可以使用的选择结构语句形式有：在算法描述中可以使用的选择结构语句形式有：条件语句条件语句1 if 1 if（表达式）表达式）语句；语句；条件语句条件语句2 if 2 if（表达式）
17、表达式）语句；语句；else else 语句；语句；开关语句开关语句1 switch 1 switch（表达式）表达式）case case 值值1 1：语句序列：语句序列1 1；breakbreak；case case 值值2 2：语句序列：语句序列2 2；breakbreak；.case case 值值n n：语句序列语句序列n n；breakbreak；defaultdefault：语句序列语句序列n+1n+1；开关语句开关语句2 switch 2 switch case case 条件条件1 1：语句序列：语句序列1 1；breakbreak；case case 条件条件2 2：语句序列
18、：语句序列2 2；breakbreak；.case case 条件条件n n：语句序列语句序列n n；breakbreak；defaultdefault：语句序列语句序列n+1n+1；5.5.在算法描述中可以使用的循环结构语句形式有：在算法描述中可以使用的循环结构语句形式有：forfor循环语句循环语句 for for（表达式表达式1 1；循环条件表达式；循环条件表达式；表达式表达式2 2）语句；语句；whilewhile循环语句循环语句 while while（循环条件表达式）循环条件表达式）语句；语句；do-whiledo-while循环语句循环语句 do do 语句序列；语句序列；whi
19、le while（循环条件表达式）；循环条件表达式）；6.6.在描述算法中可以使用的结束语句形式有：在描述算法中可以使用的结束语句形式有：函数结束语句函数结束语句 return return 表达式；表达式；return;return;case case或循环结束语句或循环结束语句 break;break;异常结束语句异常结束语句 exitexit（异常代码）；异常代码）；7.7.在算法描述中可以使用的输入输出语句形式有：在算法描述中可以使用的输入输出语句形式有：输入语句输入语句 scanfscanf(格式串格式串，变量名，变量名1 1，.，变量名，变量名n)n)；输出语句输出语句 print
20、fprintf(格式串格式串，表达式，表达式1 1，.，表达式，表达式n);n);/方括号（方括号（）中的内容是可以省略的部分。）中的内容是可以省略的部分。8.8.在算法描述中使用的注释格式为：在算法描述中使用的注释格式为：单行注释单行注释 /文字序列文字序列9.9.在算法描述中可以使用的扩展函数有：在算法描述中可以使用的扩展函数有：求最大值求最大值 maxmax（表达式表达式1 1，.，表达式，表达式n n）；）；这个函数这个函数返回参数表中返回参数表中n n个表达式计算结果中的最大值。个表达式计算结果中的最大值。求最小值求最小值 minmin（表达式表达式1 1，.，表达式，表达式n n）
21、；）；这个函数这个函数返回参数表中返回参数表中n n个表达式计算结果中的最小值个表达式计算结果中的最小值。【算法算法1-11-1】用类用类C C描述将三个数值排序的算法。描述将三个数值排序的算法。viodviod Three_Sort(Three_Sort(intint*x,intx,int*y,inty,int*z)*z)/将将x,y,zx,y,z三个指针所指示的内容按从小到大的顺序重新排列三个指针所指示的内容按从小到大的顺序重新排列 /挑选出最小的数值并换到挑选出最小的数值并换到 x x指针所指的存储单元中指针所指的存储单元中 if(*y*x&*y*z)*xif(*y*x&*y*z)*x*
22、y;*y;else if(*z*x&*z*y)*x else if(*z*x&*z*y)*x*z;*z;/在在y y和和z z所指示的存储单元中挑选出较小者换到所指示的存储单元中挑选出较小者换到y y中中 if(*z*y)*yif(*zlength=-1 L-length=-1；/将当前线性表长度将当前线性表长度置置0 0 return L return L；2.2.销毁线性表销毁线性表L Lvoid Destroy_List(SQ_LIST*L)void Destroy_List(SQ_LIST*L)if(L)free(L);if(L)free(L);/释放线性表占据的所有存储空间释放线性表
23、占据的所有存储空间 3.3.清空线性表清空线性表L Lvoid Clear_List(SQ_LIST*L)void Clear_List(SQ_LIST*L)L-length=-1;L-length=-1;/将线性表的长度置为将线性表的长度置为0 0 4.4.求线性表求线性表L L的长度的长度intint Length_List(SQ_LIST L)Length_List(SQ_LIST L)return(L.length+1);return(L.length+1);5.5.判断线性表判断线性表L L是否为空是否为空intint IsEmpty(SQ_LISTIsEmpty(SQ_LIST L
24、)L)if(L.length=-1)return TRUE;if(L.length=-1)return TRUE;else return FALSE;else return FALSE;6.6.获取线性获取线性表表L L中的某个数据元素的内容中的某个数据元素的内容intint Get _List(SQ_LIST Get _List(SQ_LIST L,intL,int i,dataType*e)i,dataType*e)if if(iL(iL.length+1).length+1)return return ERROR;ERROR;/判判断断i i值值是否合理，若不合理，返回是否合理，若不合理
25、，返回ERRORERROR *e=L*e=L.datai-1;.datai-1;/数数组组中中第第i-1i-1的的单单元元存存储储着着线线性性表中第表中第i i个数据元素的内容个数据元素的内容 return OK;return OK;7.7.在线性表在线性表L L中检索值为中检索值为e e的数据元素的数据元素intint Locate _List(SQ_LIST*L,dataType e)Locate _List(SQ_LIST*L,dataType e)for(i=0;ilength;i+)for(i=0;ilength;i+)if(L-datai=e)return i+1;if(L-dat
26、ai=e)return i+1;return 0;return 0;8.8.在线性表在线性表L L中第中第i i个数据元素之前插入数据元素个数据元素之前插入数据元素e e intint Insert_List(SQ_LIST*Insert_List(SQ_LIST*L,intL,int i,dataType e)i,dataType e)if(L-length=LIST_MAX_LENGTH-1)return ERROR;if(L-length=LIST_MAX_LENGTH-1)return ERROR;/检查是否有剩余空间检查是否有剩余空间 if(iL-length+2)return ER
27、ROR;if(iL-length+2)return ERROR;/检查检查i i值是否合理值是否合理 for(j=L-length;j=i-1;j-)for(j=L-length;j=i-1;j-)/将线性表第将线性表第i i个元素之后的所有元素向后移动个元素之后的所有元素向后移动 L-dataj+1=L-dataj;L-dataj+1=L-dataj;L-datai-1=e;L-datai-1=e;/将新元素的内容放入线性表的第将新元素的内容放入线性表的第i i个位置个位置 L-length+;L-length+;return OK;return OK;9.9.将线性表将线性表L L中第中第
28、i i个数据元素删除个数据元素删除intint Delete_List(SQ_LIST*Delete_List(SQ_LIST*L,intL,int i,dataType*e)i,dataType*e)if(if(IsEmptyIsEmpty(*L)return ERROR;(*L)return ERROR;/检测线性表是否为空检测线性表是否为空 if(iL-length+1)return ERROR;if(iL-length+1)return ERROR;/检查检查i i值是否合理值是否合理 *e=L-datai-1;e=L-datai-1;/将欲删除的数据元素内容保留在将欲删除的数据元素内
29、容保留在e e所指示的存储单元中所指示的存储单元中 for(j=i;jlength;j+)for(j=i;jlength;j+)/将线性表第将线性表第i+1i+1个元素之后的所有元素向前移动个元素之后的所有元素向前移动 L-dataj-1=L-dataj;L-dataj-1=L-dataj;L-length-;L-length-;return OK;return OK;插入算法的分析插入算法的分析 假设线性表中含有假设线性表中含有n n个数据元素，在进行插入操作个数据元素，在进行插入操作时，若假定在时，若假定在n+1n+1个位置上插入元素的可能性均等，则个位置上插入元素的可能性均等，则平均移动
30、元素的个数为：平均移动元素的个数为：删除算法的分析删除算法的分析 在进行删除操作时，若假定删除每个元素的可能性均在进行删除操作时，若假定删除每个元素的可能性均等，则平均移动元素的个数为：等，则平均移动元素的个数为：分析结论分析结论 顺序存储结构表示的线性表，在做插入或删除操作时，顺序存储结构表示的线性表，在做插入或删除操作时，平均需要移动大约一半的数据元素。当线性表的数据元素平均需要移动大约一半的数据元素。当线性表的数据元素量较大，并且经常要对其做插入或删除操作时，这一点需量较大，并且经常要对其做插入或删除操作时，这一点需要值得考虑。要值得考虑。2.3 2.3 线性表的链式存储结构线性表的链式
31、存储结构 线性表顺序存储结构的特点：线性表顺序存储结构的特点：它是一种简单、方便的存储方式。它要求线性表它是一种简单、方便的存储方式。它要求线性表的数据元素依次存放在连续的存储单元中，从而利用的数据元素依次存放在连续的存储单元中，从而利用数据元素的存储顺序表示相应的逻辑顺序，这种存储数据元素的存储顺序表示相应的逻辑顺序，这种存储方式属于静态存储形式。方式属于静态存储形式。暴露的问题：暴露的问题：l l 在做插入或删除元素的操作时，会产生大量的数在做插入或删除元素的操作时，会产生大量的数据元素移动；据元素移动；2 2 对于长度变化较大的线性表，要一次性地分配足对于长度变化较大的线性表，要一次性地
32、分配足够的存储空间，但这些空间常常又得不到充分的利用；够的存储空间，但这些空间常常又得不到充分的利用；3 3 线性表的容量难以扩充。线性表的容量难以扩充。线性表的链式存储结构线性表的链式存储结构 线性表的链式存储结构是指用一组任意的存储单元线性表的链式存储结构是指用一组任意的存储单元（可以连续，也可以不连续）存储线性表中的数据元素。（可以连续，也可以不连续）存储线性表中的数据元素。为了反映数据元素之间的逻辑关系，对于每个数据元素不为了反映数据元素之间的逻辑关系，对于每个数据元素不仅要表示它的具体内容，还要附加一个表示它的直接后继仅要表示它的具体内容，还要附加一个表示它的直接后继元素存储位置的信
33、息。假设有一个线性表（元素存储位置的信息。假设有一个线性表（a,b,c,da,b,c,d），），可可用下图用下图2-22-2所示的形式存储：所示的形式存储：图图2-2 线性表链式存储结构示意图线性表链式存储结构示意图 术语：术语：表示每个数据元素的两部分信息组合在一起被称为表示每个数据元素的两部分信息组合在一起被称为结点结点；其中表示数据元素内容的部分被称为其中表示数据元素内容的部分被称为数据域数据域（datadata）；）；表示直接后继元素存储地址的部分被称为表示直接后继元素存储地址的部分被称为指针指针或或指针域指针域（nextnext）。）。单链表简化的图单链表简化的图2-32-3描述形式
34、描述形式headd cba图图 2-3 单链表结构示意图单链表结构示意图 其中，其中，headhead是头指针，它指向单链表中的第一个是头指针，它指向单链表中的第一个结点，这是单链表操作的入口点。由于最后一个结点结点，这是单链表操作的入口点。由于最后一个结点没有直接后继结点，所以，它的指针域放入一个特殊没有直接后继结点，所以，它的指针域放入一个特殊的值的值NULLNULL。NULLNULL值在图示中常用（值在图示中常用（）符号表示。）符号表示。带头结点的单链表：带头结点的单链表：为了简化对链表的操作，人们经常在链表的第一为了简化对链表的操作，人们经常在链表的第一个结点之前附加一个结点，并称为个
35、结点之前附加一个结点，并称为头结点头结点。这样可以。这样可以免去对链表第一个结点的特殊处理。如下图免去对链表第一个结点的特殊处理。如下图2-42-4所示：所示：d headcba图图 2-4 带头结点的单链表结构示意图带头结点的单链表结构示意图链式存储结构的特点链式存储结构的特点（1 1）线性表中的数据元素在存储单元中的存放顺序与逻辑顺）线性表中的数据元素在存储单元中的存放顺序与逻辑顺序不一定一致；序不一定一致；（2 2）在对线性表操作时，只能通过头指针进入链表，并通过）在对线性表操作时，只能通过头指针进入链表，并通过每个结点的指针域向后扫描其余结点，这样就会造成寻找每个结点的指针域向后扫描其
36、余结点，这样就会造成寻找第一个结点和寻找最后一个结点所花费的时间不等。第一个结点和寻找最后一个结点所花费的时间不等。在在C C语言中，实现线性表的链式存储结构的类型定义语言中，实现线性表的链式存储结构的类型定义 typedeftypedef structstruct node node /结点类型及表头类型结点类型及表头类型 datatypedatatype data;data;structstruct node*next;node*next;LNODE,*LINK_LIST;LNODE,*LINK_LIST;2.3.2 2.3.2 典型操作的算法实现典型操作的算法实现1.1.1 1初始化链表
37、初始化链表L(L(在单链表的头部插入结点在单链表的头部插入结点)LINK_LIST Init_List1()LINK_LIST Init_List1()LINK_LIST L=NULL LINK_LIST L=NULL；LNODE*s;LNODE*s;intint x;x;scanf(“%d”,&xscanf(“%d”,&x););while(x!=-1)while(x!=-1)s=s=malloc(sizeof(LNODEmalloc(sizeof(LNODE););s-data=x;s-data=x;s-next=L;s-next=L;L=s;L=s;scanf(“%d”,&xscanf(
38、“%d”,&x););return L;return L;1.1.2 2 初始化链表初始化链表L(L(在单链表的尾部插入结点在单链表的尾部插入结点)LINK_LIST Init_List2()LINK_LIST Init_List2()LINK_LIST L=NULL LINK_LIST L=NULL；LNODE*sLNODE*s，*R=NULL;R=NULL;intint x;x;scanf(“%d”,&xscanf(“%d”,&x););while(x!=-1)while(x!=-1)s=s=malloc(sizeof(LNODEmalloc(sizeof(LNODE)；s-data=xs
39、-data=x；if(L=NULL)L=sif(L=NULL)L=s；else R-next=selse R-next=s；R=sR=s；scanf(“%d”,&xscanf(“%d”,&x)；if(R!=NULL)R-next=NULL if(R!=NULL)R-next=NULL；return L;return L;2.2.清空链表清空链表L L void void Destory_List(LINK_LISTDestory_List(LINK_LIST L)L)LNODE*p;LNODE*p;while(L-next)while(L-next)/依次删除链表中的所有结点依次删除链表中的所
40、有结点 p=L-next;L-next=p-next;p=L-next;L-next=p-next;free(p);free(p);3.3.求链求链表表L L的长度的长度intint Length_List(LINK_LIST L)Length_List(LINK_LIST L)LNODE*p LNODE*p；intint lenlen；for(for(p=L,p=L,lenlen=0=0；p-next!=NULLp-next!=NULL；len+,plen+,p=p-=p-nextnext););return(lenreturn(len)；4.4.判链表判链表L L空否空否 intint I
41、sEmpty(LINK_LISTIsEmpty(LINK_LIST L)L)if(L-next=NULL)return TRUE;if(L-next=NULL)return TRUE;else return FALSE;else return FALSE;5.5.在链表在链表L L中查找到第中查找到第i i个元素，并把元素内容放到元素个元素，并把元素内容放到元素e e中中LNODE *Get_List(LINK_LIST LNODE *Get_List(LINK_LIST L,intL,int i,dataType*e)i,dataType*e)LNODE*p=L;LNODE*p=L;inti
42、nt j;j;/检测检测i i值的合理性值的合理性 if(iLength_List(L)return NULL;if(iLength_List(L)return NULL;for(j=0;j for(j=0;jnext,j+);=p-next,j+);*e=p-data;*e=p-data;/将第将第i i个结点的内容赋给个结点的内容赋给e e return p;return p;/返回指针返回指针p p 6.6.在链表在链表L L中检索值中检索值为为e e的数据元素的数据元素LNODE*LNODE*LocateELem(LINK_LISTLocateELem(LINK_LIST L,data
43、Type e)L,dataType e)LNODE*p;LNODE*p;for(p=L-for(p=L-next;pnext;p!=!=NULL&pNULL&p-data!=e;p=p-next);-data!=e;p=p-next);/寻找满足条件的结点寻找满足条件的结点 return(p);return(p);7.7.返回链表返回链表L L中结点中结点e e的直接前驱结点的直接前驱结点LNODE*LNODE*PriorElem(LINK_LISTPriorElem(LINK_LIST L,LNODE*e)L,LNODE*e)LNODE*p;LNODE*p;if(L-next-data=e)
44、return NULL;if(L-next-data=e)return NULL;/检测第一个结点检测第一个结点 for(p=L-next;p-next!=NULL&p-next-data!=e;p=p-next);for(p=L-next;p-next!=NULL&p-next-data!=e;p=p-next);if(p-next-data=e)return p;if(p-next-data=e)return p;else return NULL;else return NULL;8.8.返回链表返回链表L L中结点中结点e e的直接后继结点的直接后继结点LNODE*LNODE*NextE
45、lem(LINK_LISTNextElem(LINK_LIST L,LNODE*e)L,LNODE*e)LNODE*p;LNODE*p;for(p=L-next;p&p!=e;p=p-next);for(p=L-next;p&p!=e;p=p-next);if(p)p=p-next;if(p)p=p-next;return p;return p;9.9.在链表在链表L L中第中第i i个数据元素之前插入数据元素个数据元素之前插入数据元素e e intint Insert_List(LINK_LIST Insert_List(LINK_LIST L,intL,int i,dataType e)i
46、,dataType e)LNODE*p,*s;LNODE*p,*s;p=Get_List(L,i-1);p=Get_List(L,i-1);if(p=NULL)if(p=NULL)printfprintf(“(“参数错误！参数错误！”);return 0;);return 0;else s=else s=malloc(sizeof(LNODEmalloc(sizeof(LNODE););if(s=NULL)return ERROR;if(s=NULL)return ERROR;s-data=e;s-data=e;s-next=p-next;p-next=s;s-next=p-next;p-ne
47、xt=s;return OK;return OK;10.10.将链表将链表L L中第中第i i个数据元素删除，并将其内容保存个数据元素删除，并将其内容保存在在e e中中intint Delete_List(LINK_LIST Delete_List(LINK_LIST L,intL,int i,dataType*e)i,dataType*e)LNODE*p LNODE*p，*s;s;p=Get_List(L,i-1);p=Get_List(L,i-1);if(p=NULL)if(p=NULL)printfprintf(“(“第第i-1i-1个结点不存在！个结点不存在！”);return-1;)
48、;return-1;else if(p-next=NULL)else if(p-next=NULL)printfprintf(“(“第第i i个结点不存在！个结点不存在！”);return 0;);return 0;else else s=p-next;s=p-next;/用用s s指向将要删除的结点指向将要删除的结点 *e=s-data;e=s-data;p-next=s-next;p-next=s-next;/删除删除s s指针所指向的结点指针所指向的结点 free(s);free(s);return OK;return OK;2.3.3 2.3.3 2.3.3 2.3.3 循环链表循环链
49、表循环链表循环链表 若将链表中最后一个结点的若将链表中最后一个结点的nextnext域指向头结点域指向头结点 实现循环链表的类型定义与单链表完全相同，它的实现循环链表的类型定义与单链表完全相同，它的所有操作也都与单链表类似。只是判断链表结束的条件所有操作也都与单链表类似。只是判断链表结束的条件有所不同。下面我们就列举两个循环链表操作的算法示有所不同。下面我们就列举两个循环链表操作的算法示例。例。head 图图2-7 带头结点的循环链表示意图带头结点的循环链表示意图1.1.初始化链表初始化链表CLCLLINK_LIST LINK_LIST InitListInitList()()LINK_LIS
50、T CL;LINK_LIST CL;LNODE*s LNODE*s，*R=NULL;R=NULL;CL=(LNODE*)CL=(LNODE*)malloc(sizeof(LNODEmalloc(sizeof(LNODE)；CL-next=CLCL-next=CL；intint x;x;scanf(“%d”,&xscanf(“%d”,&x););while(x!=-1)while(x!=-1)s=(LNODE*)s=(LNODE*)malloc(sizeof(LNODEmalloc(sizeof(LNODE)；s-data=xs-data=x；if(CL-next=CL)s-next=CL;CL