数据结构实用教程(c语言版)课件

数据结构实用教程（C语言版）

..1第1章概论本章主要介绍以下内容：数据结构中涉及的相关概念数据结构研究的主要内容算法的概念、描述方法以及评价标准.第1章概论本章主要介绍以下内容：.2本章目录1.1什么是数据结构11.2算法和算法分析25.5哈夫曼树5

1.3本章小结3结束.本章目录1.1什么是数据结构11.2算法和算法分析25.31.1什么是数据结构1.1.1基本概念及术语1.1.2数据的逻辑结构1.1.3数据的存储结构1.1.4抽象数据类型返回到本节目录返回到总目录.1.1什么是数据结构1.1.1基本概念及术语返回到本节目41.1.1

基本概念及术语在系统的学习数据结构知识之前，先了解一些相关概念和术语。1．数据（Data）指所有能输入到计算机中并被计算机程序处理的符号的总称。例如，整数、实数、字符、图像、声音等都是数据。2．数据元素（DataElement）数据元素（也称为结点）是数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理。一个数据元素可以由若干个数据项组成。数据项是数据处理中不可分割的最小单位。返回到本节目录.1.1.1基本概念及术语在系统的学习数据结构知识之前，先了53．数据结构（DataStructure）是相互之间存在一种或多种特定关系的数据元素的集合。这些数据元素不是孤立存在的，而是有着某种关系，这种关系称为结构。数据结构一般包括以下三个方面内容：（1）数据元素之间的逻辑关系，也称数据的逻辑结构。（2）数据元素及其关系在计算机存储器内的表示，称为数据的存储结构。（3）数据的运算，即对数据施加的操作。返回到本节目录1.1.1

基本概念及术语.3．数据结构（DataStructure）返回到本节目录16数据结构定义：按某种逻辑关系组织起来的一批数据，按一定的映像方式把它存放在计算机存储器中，并在这些数据上定义了一个运算的集合，就叫做数据结构。简言之，数据结构={逻辑结构+存储结构+运算集合

}。4．数据类型(DataType)数据类型是一组性质相同的值集合以及定义在这个值集合上的一组操作的总称。如在高级语言中，整型类型的取值范围为：-32768～+32767，运算符集合为加、减、乘、除、取模，即+、-、*、/、%。返回到本节目录1.1.1

基本概念及术语.数据结构定义：按某种逻辑关系组织起来的一批数据，按一定的映像75．数据类型(DataType)高级语言中的数据类型分为两大类：（1）原子类型其值是不可分解的。如C语言中的标准类型（整型、实型、字符型）。（2）结构类型其值是由若干成分按某种结构组成的，因此是可以分解的。如C语言中的的构造类型（结构体、共用体、枚举等类型）。返回到本节目录1.1.1

基本概念及术语.5．数据类型(DataType)返回到本节目录.2数据的逻辑结构1．定义数据的逻辑结构是指数据元素之间逻辑关系描述。可以用一个二元组表示，其形式化描述为： Data_Structure=（D，R）其中D是数据元素的有限集合，R是D上关系的有限集合。数据的逻辑结构是从逻辑关系上描述数据，与数据的存储无关，是独立于计算机的。返回到本节目录.1.1.2数据的逻辑结构1．定义返回到本节目录.92．数据的逻辑结构的分类根据数据元素之间的逻辑关系的不同特性，分为下列四类基本结构，如图1-1所示。（a）集合结构

（b）线性结构

（c）树型结构

（d）图形结构图1-1数据结构的四种基本逻辑结构返回到本节目录1.1.2数据的逻辑结构.2．数据的逻辑结构的分类返回到本节目录1.1.2数据的逻辑10（1）集合结构中的数据元素之间除了“同属于一个集合”的关系外，别无其他关系，这是一种最简单的数据结构。（2）线性结构结构中的数据元素之间存在着“一对一”的关系。【例1.1】学籍档案管理假设一个学籍档案管理系统应包含如表1-1所示的学生信息。返回到本节目录1.1.2数据的逻辑结构.（1）集合返回到本节目录1.1.2数据的逻辑结构.11特点：表中的每一行是一个数据元素（或记录、结点），它由学号、姓名、性别及出生年月等数据项组成。表中数据元素之间是一种先后关系，对于表中任一结点，与它相邻且在它前面的结点（称为直接前驱）最多只有一个；与表中任一结点相邻且在其后的结点（称为直接后继）也最多只有一个。我们将这种关系称为“线性结构”。返回到本节目录1.1.2数据的逻辑结构.特点：返回到本节目录1.1.2数据的逻辑结构.12（3）树型结构结构中的数据元素之间存在着“一对多”的关系。【例1.2】人机对弈人与计算机进行对弈的部分图如图1-2为所示。图1-2人机对弈图返回到本节目录1.1.2数据的逻辑结构.（3）树型结构返回到本节目录1.1.2数据的逻辑结构.13特点：图中将每一个棋盘看作一个数据元素，则数据元素之间的关系要比表1-1要复杂许多。图中数据元素之间是一对多关系，即一个数据元素向上和一个数据元素相连（称为双亲结点），向下和多个数据元素相连（称为孩子结点）。我们将这种关系称为“树型结构”。4）图形结构或网状结构结构中的任意数据元素之间都可以有关系，元素之间存在着“多对多”的关系。返回到本节目录1.1.2数据的逻辑结构.特点：返回到本节目录1.1.2数据的逻辑结构.14（【例1.3】制定教学计划在制定教学计划时，需要考虑各门课程的开设顺序。有些课程需要先导先修课程，有些课程则不需要，而有些课程又是其他课程的先导先修课程。比如，计算机专业课程的开设情况如表1-2所示。返回到本节目录1.1.2数据的逻辑结构.（【例1.3】制定教学计划返回到本节目录1.1.2数据的逻15教学计划的关系图如图1-3所示。图1-3教学计划关系图特点：图中数据元素存在着多对多的任意关系。一个结点可能有多个直接前驱和直接后继。返回到本节目录1.1.2数据的逻辑结构.教学计划的关系图如图1-3所示。返回到本节目录1.1.2数161.1.3数据的存储结构数据在计算机中的存储表示称为数据的存储结构，也称为物理结构。数据的存储结构是逻辑结构在计算机存储器中的实现。本书将介绍常用的两种基本的存储结构：顺序存储结构和链式存储结构。数据的逻辑结构和存储结构的关系是：存储结构是逻辑关系的映像与元素本身映像，是数据结构的实现；逻辑结构是数据结构的抽象。

返回到本节目录.1.1.3数据的存储结构数据在计算机中的存储表示称为数据的171.顺序存储结构顺序存储结构：借助元素在存储器中的相对位置来表示数据元素间的逻辑关系。【例1.4】对于表1-1提出的学生信息登记表进行存储，假定每个元素占用50个存储单元，数据从1000号单元开始由低地址向高地址存放，对应的顺序存储结构如表1-3所示。返回到本节目录1.1.3数据的存储结构.1.顺序存储结构返回到本节目录1.1.3数据的存储结构.18顺序存储结构的主要特点：可实现对各数据元素的随机访问。这是因为只要知道存储的首地址以及每个数据元素所占的存储单元，就可以计算出各数据元素的存储地址。不利于修改，在对数据元素进行插入、删除运算时可能要移动一系列的数据元素。返回到本节目录1.1.3数据的存储结构.顺序存储结构的主要特点：返回到本节目录1.1.3数据的存储192.链式存储结构链式存储结构：借助指示元素存储地址的指针表示数据元素间的逻辑关系。【例1.5】对于表1-1学生信息登记表进行链式存储时，在每个数据元素后方附加一个指向“下一个结点地址”的指针字段，用于存放后继数据元素的存储地址，每个数据元素的地址是随机的，可以不连续。对应的链式存储结构见表1-4所示。返回到本节目录1.1.3数据的存储结构.2.链式存储结构返回到本节目录1.1.3数据的存储结构.20链式存储结构的主要特点：利于修改，在对数据元素进行插入、删除运算时，仅需修改数据元素的指针字段值，而不必移动数据元素。由于逻辑上相邻的数据元素在存储位置中不一定相邻，因此，链式存储结构不能对数据元素进行随机访问。返回到本节目录1.1.3数据的存储结构.链式存储结构的主要特点：返回到本节目录1.1.3数据的存储211.1.4抽象数据类型1．抽象数据类型的定义抽象数据类型（AbstractDataType，简称ADT）是指一个数学模型以及定义在该模型上的一组操作。2．抽象数据类型的表示抽象数据类型实际上就是对该数据结构的定义。因为它定义了一个数据的逻辑结构以及在此结构上的一组算法。可以用一个三元组表示：ADT=（Ｄ，Ｓ，Ｐ）其中，D是数据对象，S是D上的关系集，P是对D的基本操作集。返回到本节目录.1.1.4抽象数据类型1．抽象数据类型的定义返回到本节目录22抽象数据类型通常是指由用户定义，用以表示应用问题的数据类型，抽象数据类型由基本的数据类型组成，并包括一组相关的服务（或称操作）。抽象数据类型有些类似于pascal语言中的记录（record）类型和c语言中的构造（struct）类型，但它增加了相关的服务。3．ADT的两个重要特征（1）数据抽象用ADT描述程序处理的实体时，强调的是其本质的特征、其所能完成的功能以及它和外部用户的接口（即外界使用它的方法）。（2）数据封装将实体的外部特性和其内部实现细节分离，并且对外部用户隐藏其内部实现细节。返回到本节目录1.1.4抽象数据类型.抽象数据类型通常是指由用户定义，用以表示应用问题的数据类型，231.2算法和算法分析1.2.1算法的概念1.2.2算法分析1.2.3相关C语言知识回顾返回到总目录.1.2算法和算法分析1.2.1算法的概念返回到总目录.241.2.1算法的概念1．算法的定义瑞士著名的计算机科学家N.Wirth所提出的著名公式“程序=算法+数据结构”，所谓算法，就是为解决特定问题而采取的步骤和方法。2．算法的特性一个算法应该具有下列特性：（1）有穷性：一个算法必须（对任何合法的输入值）在执行有限步之后结束。（2）确定性：算法中的每一条指令必须有确切的含义，不会产生二义性。返回到本节目录.1.2.1算法的概念1．算法的定义返回到本节目录.25（3）可行性：算法中描述的操作都可以通过执行有限次基本操作来实现。（4）输入：一个算法有零个或多个输入。（5）输出：一个算法必有一个或多个输出。3．算法的评价要设计一个好的算法通常需要考虑以下几方面的要求：（1）正确性：要求算法能够正确地执行预先规定的功能，并达到所期望的性能要求。（2）可读性：为了便于理解、测试和修改算法，算法应该具有良好的可读性。返回到本节目录1.2.1算法的概念.（3）可行性：算法中描述的操作都可以通过执行有限次基本操作来26（3）健壮性：当输入非法的数据时，算法应能恰当地做出反应或进行相应处理，而不是产生莫名奇妙的输出结果。并且处理出错的方法不应是中断程序的执行，而是返回一个表示错误或错误性质的值，以便在更高的抽象层次上进行处理。（4）高效性：对同一个问题，执行时间越短，算法的效率越高。（5）低存储量：完成相同的功能，执行算法所占用的存储空间应尽可能的少。返回到本节目录1.2.1算法的概念.（3）健壮性：当输入非法的数据时，算法应能恰当地做出反应或进274．算法的描述为了表示一个算法，可以用多种不同的方法，常用的有自然语言、传统流程图、结构化流程图、N-S流程图等表示。本书采用C的描述语言实现对各种数据结构及算法的操作描述，算法是以函数形式描述，描述如下：类型标识符函数名(形式参数表)/*算法说明*/{语句序列}返回到本节目录1.2.1算法的概念.4．算法的描述返回到本节目录1.2.1算法的概念.281.2.2算法分析在算法满足正确性的前提下，如何评价不同算法的优劣呢？通常主要考虑算法的时间复杂度和空间复杂度这两方面。一般情况下，鉴于运算空间（内存）较为充足，所以把算法的时间复杂度作为重点分析。1.时间复杂度（TimeComplexity）一个算法所需的运算时间通常与所解决问题的规模大小有关。问题规模是一个和输入有关的量，用n表示问题规模的量，把算法运行所需的时间T表示为n的函数，记为T(n)。不同的T(n)算法，当n增长时，运算时间增长的快慢很不相同。一个算法所需的执行时间就是该算法中所有语句执行次数之和。当n逐渐增大时T(n)的极限情况，一般简称为时间复杂度。返回到本节目录.1.2.2算法分析在算法满足正确性的前提下，如何评价不同算29当讨论一个程序的运行时间时，注重的不是T(n)的具体值，而是它的增长率。T(n)的增长率与算法中数据的输入规模紧密相关，而数据输入规模往往用算法中的某个变量的函数来表示，通常是f(n)。随着数据输入规模的增大，f(n)的增长率与T(n)的增长率相近，因此T(n)同f(n)在数量级上是一致的。记作：T(n)=O(f(n))其中，大写字母O为Order(数量级)的字头，f(n)为函数形式，如T(n)=O(n2)。返回到本节目录1.2.2算法分析.当讨论一个程序的运行时间时，注重的不是T(n)的具体值，而是30注意，当T(n)为多项式时，可只取其最高次幂项并省略其系数，其它的次幂项及系数均略去不写。一般地，对于足够大的n，常用的时间复杂性存在以下顺序：

O(1)<O(log2n)<O(n)<O(nlog2n)<O(n2)<O(n3)<O(2n)算法时间复杂度的数量级越大，表示该算法的效率越低，反之越高。例如O(1)为常数数量级,，即算法的时间复杂性与输入规模n无关。返回到本节目录1.2.2算法分析.注意，当T(n)为多项式时，可只取其最高次幂项并省略其系数，31【例1.6】分析以下算法的时间复杂度。x=0;y=0;for(k=1;k<=n;k++)x++;（1）执行n次for(i=1;i<=n;i++)for(j=1;j<=n;j++)y++;（2）执行n2次

解：T(n)=n+n2T(n)=O(n2)上述算法中的基本运算是语句（2），其执行频率为n2。则T(n)=n2=O(n2)返回到本节目录1.2.2算法分析.【例1.6】分析以下算法的时间复杂度。返回到本节目录1.2.32【例1.7】分析以下算法的时间复杂度。i=1;while(i<=n)i=2*i;(1)执行f(n)次解：设语句（1）执行次数是f(n)，则2f(n)≤n得到T(n)=O(log2n)返回到本节目录1.2.2算法分析.【例1.7】分析以下算法的时间复杂度。返回到本节目录1.2.33【例1.8】求两个矩阵相乘的函数的时间复杂度。voidmult(inta[],intb[],intc[]){/*以二维数组存储矩阵元素，c为a和b的乘积*/for(i=1;i<=n;++i)(1)执行n次for(j=1;j<=n;++j)(2)执行n2次{c[i,j]=0;for(k=1;k<=n;++k)(3)执行n3次c[i,j]+=a[i,k]*b[k,j];}}解：嵌套循环为每层循环次数的乘积，因为是该函数为三重循环，所以时间复杂度为O(n3)。返回到本节目录1.2.2算法分析.【例1.8】求两个矩阵相乘的函数的时间复杂度。返回到本节目录342.空间复杂度（SpaceComplexity）一个算法的空间复杂度是指程序运行开始到结束所需要的存储空间。包括算法本身所占用的存储空间、输入/输出数据占用的存储空间以及算法在运行过程中的工作单元和实现算法所需辅助空间。类似于算法的时间复杂度，算法所需存储空间的量度记作：S(n)=O(f(n))表示随着问题规模n的增大，算法运行所需存储量的增长率与f(n)的增长率相同。返回到本节目录1.2.2算法分析.2.空间复杂度（SpaceComplexity）返回到本351.2.3相关C语言知识回顾1．数据类型数据类型是和数据结构密切相关的一个概念，它最早出现在高级程序设计语言中，用以描述操作对象的特性。高级语言中的数据类型可分为两类：一类是原子类型，如C语言中的基本类型（整型、实型、字符型等）指针和空类型等不可再分的值；另一类是结构类型，如数组、结构体等通过若干成分（可以是原子类型或结构类型）构造而成的。返回到本节目录.1.2.3相关C语言知识回顾1．数据类型返回到本节目录.361.2.3相关C语言知识回顾（1）数组类型数组中的每一个元素都属于同一个数据类型。数组有一维数组和多维数组，数组名标识一个数组，下标指示一个数组元素在该数组中的顺序位置，下标从0～n-1（n为数据元素个数）。例如，inta[10];定义了包含10个整数的数组a，数组下标范围0～9。（2）结构体类型结构体是是一种复合的数据类型，该结构体类型内可以有多个成员，每个结构体成员可以有不同的数据类型。基本格式如下：返回到本节目录.1.2.3相关C语言知识回顾（1）数组类型返回到本节目录.37【格式】struct结构体名/*定义结构体类型*/{成员列表;};struct结构体名变量名表;

/*定义结构体变量*/返回到本节目录1.2.3相关C语言知识回顾.【格式】返回到本节目录1.2.3相关C语言知识回顾.38（3）结构体类型指针对结构体成员的引用方法当结构体类型的指针指向某一结构体变量时，就可以使用该指针对其指向的结构体变量内的各成员进行引用。引用的方法为：指针名->成员名等价于：(*指针名).成员名等价于：结构体变量名.成员名在本书中，在程序内大量使用结构体类型的指针，所以大都采用第一种写法。返回到本节目录1.2.3相关C语言知识回顾.（3）结构体类型指针对结构体成员的引用方法返回到本节目录1.39（4）用typedef定义类型除了可以直接使用C提供的标准类型名和自己声明的结构体类型外，还可以用typedef声明新的类型名来代替已有的类型名。其基本定义格式如下：【格式】typedef原类型名

新类型名;其中，typedef为关键字，表示重定义。原类型名是C语言提供的任意一种数据类型，可以是简单数据类型，也可以是构造数据类型。新类型名为原类型名的一个别名。使用新类型名就像使用原类型名那样定义变量。返回到本节目录1.2.3相关C语言知识回顾.（4）用typedef定义类型返回到本节目录1.2.3相关402．动态存储分配函数C语言提供了动态分配函数来实现动态存储分配。最常用的动态存储分配函数有以下两个。（1）分配内存空间函数malloc()【格式】(类型名*)malloc(要分配的内存字节数size)【功能】在内存中分配一个长度为size的连续存储空间，返回值是新分配存储空间的首地址，若内存不足，则返回NULL。其中，类型名表示把该存储空间用于何种数据类型。（类型名*）表示把malloc函数返回值强制转换为该类型指针。返回到本节目录1.2.3相关C语言知识回顾.2．动态存储分配函数返回到本节目录1.2.3相关C语言知识41（2）释放内存空间函数free()【格式】free(指向要释放单元的指针名)【功能】释放该指针所指的一块存储空间，该空间系统可另作它用。注意这个指针所指的空间必须是由malloc()函数和calloc()函数分配的才行。free函数无返回值。例如：int*pt;pt=(int*)malloc(sizeof(int));free(pt);程序段表示释放pt指向的存储空间。返回到本节目录1.2.3相关C语言知识回顾.（2）释放内存空间函数free()返回到本节目录1.2.3423．函数的定义与调用在本书中，绝大多数的算法都是编写成C语言的函数，这些函数需要通过编写相应的主函数才能被执行。（1）函数的定义函数的定义如下：【格式】函数类型函数名（形参表）{内部变量定义函数主体语句返回语句}

返回到本节目录1.2.3相关C语言知识回顾.3．函数的定义与调用返回到本节目录1.2.3相关C语言知识43（2）函数的调用【格式】函数类型

函数名（实参表）;【说明】1．实参表中各参数应与形参表中各参数类型及个数相符。2．在调用函数时，表达式应与该函数的类型相符，如果该函数有返回值时，在调用时要将该函数的返回值赋给相同类型的变量。返回到本节目录1.2.3相关C语言知识回顾.（2）函数的调用返回到本节目录1.2.3相关C语言知识回顾444．TurboC2.0中的汉字显示在TurboC2.0中，如果想输入和显示汉字，需要使用UCDOS汉字系统。但现在的Windows操作系统不支持UCDOS汉字系统的16位显示。下面介绍一种能在WindowsXP系统环境下，在TurboC2.0中使用UCDOS的汉字系统的方法。返回到本节目录1.2.3相关C语言知识回顾.4．TurboC2.0中的汉字显示返回到本节目录1.245（1）将UCDOS的核心文件进行兼容性设置（有的机器可省略这步，直接执行（2））。点“开始”菜单->“所有程序”->“附件”->“程序兼容性向导”->“我想手动定位程序”->“浏览”->\ucdos\->win98->256色，640X480->程序工作正确吗？选“是，设置此程序为一直使用兼容性设置。”完成。有的UCDOS版本的核心文件是knlvga.exe，也要照此进行兼容性设置。返回到本节目录1.2.3相关C语言知识回顾.（1）将UCDOS的核心文件进行兼容性设置（有的机器可省略这46（2）运行UCDOS系统文件的方法。进入到命令提示符（MS-DOS状态）（“开始”->“程序”->“附件”->“命令提示符”）切换到UCDOS目录。（带下划线文字为输入的命令信息，“↙”表示回车键。假设UCDOS文件夹在C盘根目录内，可输入如下命令：）C:\DocumentsandSettings>cd\↙

（回到C盘根目录下）C:\>cdUcdos↙

（进入UCDOS的目录）返回到本节目录1.2.3相关C语言知识回顾.（2）运行UCDOS系统文件的方法。返回到本节目录1.2.347这时不要运行UCDOS.BAT，分别一项一项命令运行。如：C:\UDOS>↙C:\UDOS>↙C:\UDOS>↙C:\UDOS>↙C:\UDOS>↙

（五笔输入，如不用五笔可省略此步）

（注：可直接输入命令名，如输入“rd16↙”，省略扩展名“.com”）

返回到本节目录1.2.3相关C语言知识回顾.这时不要运行UCDOS.BAT，分别一项一项命令运行。如：返48就可以顺利进入ucdos。然后，退出UCDOS目录，再进入tc目录运行tc.exe文件就可以在TurboC2.0中顺利的输入和显示汉字了。如：C:\UDOS>cd\↙C:\>cdtc↙

（假定TurboC2.0的文件夹名称为TC）C:\TC>tc.exe↙(可直接输入tc↙即可)即可进行TurboC2.0输入并运行C语言源程序了。返回到本节目录1.2.3相关C语言知识回顾.就可以顺利进入ucdos。然后，退出UCDOS目录，再进入t49（3）常用的TurboC2.0快捷键Alt+F：文件菜单①Load打开文件

②Save保存

③Writeto另存为

④Quit退出Alt+R：运行菜单Run（或Ctrl+F9）

运行程序

UserScreen(或Alt+F5)查看运行结果Alt+E：编辑（显示光标，有时调试有错时可将光标重新显示在编辑区）F9：编译系统查错返回到本节目录1.2.3相关C语言知识回顾.（3）常用的TurboC2.0快捷键返回到本节目录1.2.50（4）更改汉字输入法Alt+F1区位Alt+F2全拼Alt+F3双拼Alt+F5五笔（必须在UCDOS中输入wb命令才能用此项）Alt+F6英文单次按右shift键

可显示或隐藏中文输入法返回到本节目录1.2.3相关C语言知识回顾.（4）更改汉字输入法返回到本节目录1.2.3相关C语言知识511.3本章小结本章主要介绍了有关数据结构的以下几方面：（1）数据结构主要研究数据的逻辑结构、存储结构和运算方法。（2）数据的逻辑结构包括：集合、线性结构、树型结构、图形结构四种基本类型。（3）数据的存储结构包括：顺序存储结构和链式存储结构。（4）算法是对特定问题求解步骤的一种描述，是指令的有限序列。算法具有：有穷性、确定性、正确性、输入、输出等特性。（5）算法的时间复杂度与空间复杂度。返回到总目录.1.3本章小结本章主要介绍了有关数据结构的以下几方面：返回到52数据结构实用教程（C语言版）

中国水利水电出版社..53第2章线性表本章主要介绍下列内容线性表的定义和基本操作线性表的顺序存储结构线性表的链式存储结构线性表的应用举例.第2章线性表本章主要介绍下列内容.54本章目录2.1线性表的基本概念1

2.2顺序表2

2.3链表32.4线性表的应用举例4

2.5本章小结5结束.本章目录2.1线性表的基本概念12.2552.1线性表的基本概念2.1.1线性表的定义2.1.2线性表的基本操作返回到总目录.2.1线性表的基本概念2.1.1线性表的定义返回到总目录562.1.1

线性表的定义1.线性表的定义线性表是具有相同数据类型的n（n>=0）个数据元素的有限序列，通常记为：（a1，a2，…ai-1，ai，ai+1，…an）

其中n为表长，当n=0时称为空表。

在线性表中相邻元素之间存在着顺序关系。如对于元素ai

而言，ai-1

称为

ai

的直接前驱，ai+1

称为

ai

的直接后继。返回到本节目录.2.1.1线性表的定义1.线性表的定义返回到本节目录.572.线性表的特点（1）有且仅有一个开始结点（a1），它没有直接前驱；（2）有且仅有一个终端结点（an），它没有直接后继；（3）除了开始结点和终端结点以外，其余的结点都有且仅有一个直接前驱和一个直接后继。2.1.1

线性表的定义返回到本节目录.2.线性表的特点2.1.1线性表的定义返回到本节目录.582.1.2

线性表的基本操作数据结构的运算是定义在逻辑结构层次上的，而运算的具体实现是建立在存储结构上的。下面定义的线性表的基本操作仅是定义在逻辑结构上的，每一个操作的具体实现只有在确定了线性表的存储结构之后才能完成。线性表的基本操作有：（1）初始化线性表InitList(L)。其作用是建立一个空表L（即建立线性表的构架，但不包含任何数据元素）。返回到本节目录.2.1.2线性表的基本操作数据结构的运算是定义在逻辑结构层59（2）求线性表的长度GetLength(L)。其作用是返回线性表L的长度（即所含数据元素的个数）。（3）求线性表中第i个元素GetElem(L,i,x)。其作用是在1≤i≤GetLength(L)返回成功，并用x存储线性表L的第i个元素的值。（4）按值查找操作Locate(L,x)。在线性表L查找一个与给定值x相等的数据元素，其作用是若存在一个或多个与x相等的数据元素，则返回的元素所在位置的最小值或地址值；否则返回0或NULL值。2.1.2

线性表的基本操作返回到本节目录.（2）求线性表的长度GetLength(L)。其作用是返回线60（5）插入操作InsElem(L,i,x)。其作用是在线性表L的第i个位置上插入一个值为

x的新元素，使线性表L由（a1，a2，…ai-1，ai，ai+1，…an）变为（a1，a2，…ai-1，x，ai，ai+1，…an）。其中1≤i≤GetLength(L)+1。（6）删除操作DelElem(L,i,x)。其作用是删除线性表L的第i个位置的数据元素并用x将其存储，使线性表L由（a1，a2，…ai-1，ai，ai+1，…an）变为（a1，a2，…ai-1，ai+1，…an）。其中1≤i≤GetLength(L)。（7）输出元素值DispList(L)。其作用是依次扫描线性表L，并输出各元素的值。2.1.2

线性表的基本操作返回到本节目录.2.1.2线性表的基本操作返回到本节目录.612.2顺序表2.2.1顺序表2.2.2顺序表的基本操作实现返回到总目录.2.2顺序表2.2.1顺序表返回到总目录.621.顺序表的定义数据结构在内存中的表示通常有两种形式，即顺序存储表示和链式存储表示。线性表的顺序存储表示又称为顺序表。线性表的顺序存储是指用一组地址连续的存储单元依次存储线性表的数据元素，我们把用这种存储形式存储的线性表称为顺序表。假设顺序表(a1，a2，…ai-1，ai，ai+1，…an)，每个数据元素占用d个存储单元，则元素ai的存储位置为：Loc(ai)=Loc(a1)+(i-1)×d1≤i≤n2.2.1顺序表返回到本节目录.1.顺序表的定义2.2.1顺序表返回到本节目录.63其中，Loc(a1)是顺序表第一个元素a1的存储位置，通称为顺序表的起始地址。顺序存储结构示意图如图2-1所示。顺序表的存储特点：（1）顺序表的逻辑顺序和物理顺序是一致的。（2）顺序表中任意一个数据元素都可以随机存取，所以顺序表是一种随机存取的存储结构。2.2.1顺序表返回到本节目录.其中，Loc(a1)是顺序表第一个元素a1的存储位置，通称为642.顺序表的类型定义#defineMAXLEN100/*定义常量MAXLEN为100表示存储空间总量*/#defineOK/*定义常量OK为1表示成功*/#defineERROR0/*定义常量ERROR为0表示失败*/#defineOVER-1/*定义常量OVER为-1表示结束*/typedefintElemType;/*定义ElemType为int类型*/typedefstruct/*顺序表存储类型*/{ElemTypedata[MAXLEN];/*存放线性表的数组*/intLength;/*Length是顺序表的长度*/}SeqList;2.2.1顺序表返回到本节目录.2.顺序表的类型定义2.2.1顺序表返回到本节目录.652.2.2顺序表的基本操作实现1．顺序表的初始化顺序表的初始化即构造一个空顺序表L，将表L的实际长度置0，算法描述见算法2.1。算法2.1

voidInitList(SeqList*L)

{L->Length=0;

/*初始的化顺序表为空*/}返回到本节目录.2.2.2顺序表的基本操作实现1．顺序表的初始化返回到本节662．顺序表的建立初始化顺序表后向表中输入n个元素建立表L，算法描述见算法2.2。算法2.2voidCreateList(SeqList*L,intn){inti;printf("请输入各个元素值：\n");for(i=0;i<n;i++)scanf("%d",&L->data[i]);L->Length=i;}2.2.2顺序表的基本操作实现返回到本节目录.2．顺序表的建立2.2.2顺序表的基本操作实现返回到本节目673．求顺序表的长度操作返回顺序表L的Length值，算法描述见算法2.3。算法2.3intGetLength(SeqList*L){returnL->Length;}

4．查找操作顺序表的查找分为按值与按序号查找，下面将分别介绍这两种方法的实现，读者可根据具体的问题相应选择所需的查找方法。2.2.2顺序表的基本操作实现返回到本节目录.3．求顺序表的长度操作2.2.2顺序表的基本操作实现返回到68（1）按号查找查找顺序表中第i个元素的值，在i无效时返回出错，有效时返回成功，并用x存储第i个元素的值，算法描述见算法2.4。算法2.4intGetElem(SeqList*L,inti,ElemType*x){if(i<1||i>L->Length)returnERROR;else{*x=L->data[i-1];returnOK;}}2.2.2顺序表的基本操作实现返回到本节目录.（1）按号查找2.2.2顺序表的基本操作实现返回到本节目录692）按值查找操作顺序表中的按值查找是指在顺序表中查找与给定值x相等的数据元素的所在位置，算法描述见算法2.5。算法2.5intLocate(SeqList*L,ElemTypex){

inti=0;while(i<=L->Length&&L->data[i]!=x)i++;if(i>L->Length)

returnERROR;elsereturni+1;

/*返回的是元素位置*/}2.2.2顺序表的基本操作实现返回到本节目录.2）按值查找操作2.2.2顺序表的基本操作实现返回到本节目702.2.2顺序表的基本操作实现5．插入操作线性表的插入是指在表的第i个位置上插入一个值为x的新元素，插入后使原表长增1，原顺序表如图2-2所示。返回到本节目录.2.2.2顺序表的基本操作实现5．插入操作715．插入操作步骤如下：

(1)将an～ai之间的所有结点依次后移，为新元素让出第i个位置，如图2-3所示。返回到本节目录.5．插入操作步骤如下：返回到本节目录.725．插入操作步骤如下：(2)将新结点x插入到第i个位置，如图2-4所示。(3)顺序表的长度增1，插入成功，并返回，算法描述见算法2.6。返回到本节目录.5．插入操作步骤如下：返回到本节目录.735．插入操作算法2.6int

InsElem(SeqList*L,inti,ElemTypex){intj;

if(L->Length>=MAXLEN){printf("顺序表已满！");returnOVER;

/*表满，不能插入*/}if(i<1||i>L->Length+1)

/*检查给定的插入位置的正确性*/{printf("插入位置出错！");returnERROR;}if(i==L->Length+1){L->data[i-1]=x;L->Length++;returnOK;/*插入的位置为表尾，则不需移动直接插入即可*/}for(j=L->Length-1;j>=i-1;j--)

/*结点移动*/L->data[j+1]=L->data[j];L->data[i-1]=x;/*新元素插入*/L->Length++;/*顺序表长度增1*/returnOK;

/*插入成功，返回*/}返回到本节目录.5．插入操作算法2.6返回到本节目录.745．插入操作插入算法的时间性能分析：顺序表插入操作大约需移动表中一半数据元素，其时间复杂度为Ｏ(n)。返回到本节目录.5．插入操作插入算法的时间性能分析：返回到本节目录.752.2.2顺序表的基本操作实现6.删除操作

线性表的删除操作是指将第i个元素从顺序表中去掉，删除后顺序表表长减1，原顺序表如图2-5所示。返回到本节目录.2.2.2顺序表的基本操作实现6.删除操作766.删除操作步骤如下：(1)将要删除的元素值赋给指针变量*x，如图2-6所示返回到本节目录.6.删除操作步骤如下：返回到本节目录.776.删除操作步骤如下：(2)将ai+1～an之间的结点依次顺序向前移动，如图2-7所示。(3)顺序表的长度减1，删除成功，并返回，算法描述见算法2.7。返回到本节目录.6.删除操作步骤如下：返回到本节目录.786.删除操作算法2.7intDelElem(SeqList*L,inti,ElemType*x)

{int

j;if(L->Length==0){printf("顺序表为空！");returnERROR;

/*表空，不能删除*/}if(i<1||i>L->Length)

/*检查是否空表及删除位置的合法性*/{printf("不存在第i个元素");returnERROR;}*x=L->data[i-1];/*用指针变量*x返回删除的元素值*/for(j=i;j<=L->Length-1;j++)

/*结点移动*/L->data[j-1]=L->data[j];L->Length--;

/*顺序表长度减1*/returnOK;

/*删除成功，返回*/}返回到本节目录.6.删除操作算法2.7返回到本节目录.796.删除操作删除算法的时间性能分析：与插入操作相同，其时间主要消耗在了移动表中元素上，（大约需要移动表中一半的元素），显然该算法的时间复杂度为Ｏ(n)。返回到本节目录.6.删除操作删除算法的时间性能分析：返回到本节目录.802.2.2顺序表的基本操作实现7．顺序表的输出操作扫描顺序表L，输出各元素的值，算法描述见算法2.8。算法2.8voidDispList(SeqList*L){inti;for(i=0;i<L->Length;i++)printf("%5d",L->data[i]);}返回到本节目录.2.2.2顺序表的基本操作实现7．顺序表的输出操作返回到812.3链表2.3.1单链表2.3.2单链表的基本操作实现2.3.3链表的变形返回到总目录.2.3链表返回到总目录.822.3.1单链表1.单链表的定义线性表的链式存储结构是指用一组任意的存储单元（可以连续，也可以不连续）存储线性表中的数据元素。为了反映数据元素之间的逻辑关系，对于每个数据元素不仅要表示它的具体内容，还要附加一个表示它的直接后继元素存储位置的信息，这样构成的链表称为线性单向链接表，简称单链表，其结点结构如图2-8所示。数据域后继指针域datanext图2-8单链表的结点示意图其中，data部分称为数据域，用于存储一个数据元素（结点Node）的信息。next部分称为指针域，用于存储其直接后继的存储地址的信息。返回到本节目录.2.3.1单链表1.单链表的定义数据域后继指针域data832.3.1单链表单链表分为带头结点（其next域指向链表第一个结点的存储地址）和不带头结点两种类型。在许多情况下，带头结点的链表中每个结点的存储地址均放在其前驱结点中，这样算法对所有的结点处理可一致化，因此，本节讨论的单链表均指带头结点的单链表。带头结点的单链表如图2-9所示。

图2-9带头结点的单链表其中，头结点的数据域可以不存储任何信息，也可以存放特殊的信息；头结点的指针域存储链表中第一个结点的地址。当头结点的指针域为空（即NULL或用∧表示），则此表为空表。在非空表中，当某个结点的指针域为空，表示它为链表的最后一个结点。返回到本节目录.2.3.1单链表单链表分为带头结点（其next域指向链表第842.3.1单链表链式存储特点：线性表的链式存储结构是通过指针来表示元素之间的逻辑关系，不再有逻辑顺序与物理存储顺序一致的特点，是非顺序存储结构。返回到本节目录.2.3.1单链表链式存储特点：线性表的链式存储结构是通过指852.3.1单链表2.单链表的类型定义#defineOK1#defineERROR0#defineOVER-1typedefcharElemType;/*定义ElemType为char类型*/typedefstructnode/*单链表存储类型*/{ElemTypedata;/*定义结点的数据域*/structnode*next;/*定义结点的指针域*/}LinkList;返回到本节目录.2.3.1单链表2.单链表的类型定义返回到本节目录.862.3.2单链表的基本操作实现1.单链表的初始化单链表的初始化即构造一个仅包含头结点的空单链表L，算法描述见算法2.9。算法2.9

LinkList*InitList(){/*申请一块LinkList类型的存储单元的操作，并将其地址赋值给头指针变量L*/LinkList*L;

L=(LinkList*)malloc(sizeof(LinkList));L->next=NULL;returnL;/*头结点L指针域为空，表示空链表*/}返回到本节目录.2.3.2单链表的基本操作实现1.单链表的初始化返回到本872.3.2单链表的基本操作实现2．单链表的建立（1）头插法建表在初始化链表后，每读取有效的数据都为其生成新结点s，并将读取的数据存放到新结点s的数据域中，然后将新结点插入到当前链表L的表头上，直到循环结束为止，算法描述见算法2.10。算法2.10voidCreateList(LinkList*L){LinkList*s;charch;while((ch=getchar())!='#')/*判断输入数据是否有效*/{s=(LinkList*)malloc(sizeof(LinkList));/*生成新结点*/s->data=ch;/*将数据放入新结点的数据域*/s->next=L->next;/*将新结点的指针域存放头结点的指针域*/L->next=s;/*将新结点插入头结点之后*/}}返回到本节目录.2.3.2单链表的基本操作实现2．单链表的建立返回到本节目882.3.2单链表的基本操作实现（2）尾插法建表头插法建立链表虽然算法简单易理解，但生成的链表中结点的次序和原输入的次序相反。而尾插法建立链表可实现次序的一致，该算法依旧在初始化链表后，但需增加一个尾指针last，使其指向当前链表的尾结点，算法描述见算法2.11。算法2.11voidCreateList(LinkList*L){LinkList*s,*last;charch;last=L;/*last始终指向尾结点，开始时指向头结点*/while((ch=getchar())!='#')/*判断输入数据是否有效*/{s=(LinkList*)malloc(sizeof(LinkList));/*生成新结点*/s->data=ch;/*将数据放入新结点的数据域*/s->next=NULL;/*将新结点的指针域为空*/last->next=s;/*将新结点插入表尾*/last=s;/*将last指针指向表尾结点*/}}返回到本节目录.2.3.2单链表的基本操作实现（2）尾插法建表返回到本节目892.3.2单链表的基本操作实现3．求单链表的长度求长度就是求单链表中数据元素的个数。求带头结点的单链表L的长度需设一个动态指针p指向头结点，计数器j初始值为0，p指针所指结点后面若还有结点，p就向后移动，每次移动一次，计数器j值增1，直到p所指结点后面为空结束，则计数器j的值即为表的长度，算法描述见算法2.12。算法2.12intGetLength(LinkList*L){LinkList*p;intj=0;p=L;/*p指向链表的头结点*/while(p->next!=NULL)/*判断p所指结点后面是否为空*/{p=p->next;/*p向所指结点的后面移动*/j++;/*计数器值增1*/}returnj;/*计数器j的值为表长度*/}返回到本节目录.2.3.2单链表的基本操作实现3．求单链表的长度返回到本节902.3.2单链表的基本操作实现4．查找操作单链表的查找分为按值与按序号查找，下面将分别介绍这两种方法的实现，读者可根据具体的问题相应选择所需的查找方法。（1）按值查找算法思路：从链表的第一个元素结点开始，由前向后依次比较单链表中各结点数据域中的值，若某结点数据域中的值与给定的值x相等，则返回该结点的指针值p；否则继续向后比较直到表结束。若整个单链表中没有这样的结点，则返回空NULL值，算法描述见算法2.13。算法2.13LinkList*Locate(LinkList*L,ElemTypex){LinkList*p;p=L->next;/*p指向链表的第一个结点*/while(p!=NULL&&p->data!=x)p=p->next;returnp;}返回到本节目录.2.3.2单链表的基本操作实现4．查找操作返回到本节目录.912.3.2单链表的基本操作实现（2）按序号查找算法思路：从链表的头结点开始，判断当前结点序号是否是第i个，若是，则返回该结点指针值p；否则继续向后查找直到表结束。若没有第i个结点，则返回空NULL值，算法描述见算法2.14。算法2.14LinkList*GetList(LinkList*L,inti){LinkList*p;intj=0;p=L;/*p指向链表的头结点*/while(p->next!=NULL&&j<i){p=p->next;j++;}if(j==i)/*判断与给定的序号是否相等*/returnp;elsereturnNULL;}返回到本节目录.2.3.2单链表的基本操作实现（2）按序号查找返回到本节目922.3.2单链表的基本操作实现5．插入操作顺序表的插入操作需要移动大量的数据元素，而链表的插入只需修改指针而无需移动原表元素，那链表的插入操作是如何实现呢？（1）在已知结点p之后插入一新结点s已知结点p为链表中任意结点，先创建一个以x为值的新结点s，则插入操作步骤如下：先将结点s的指针域指向结点p的下一个结点（执行语句s->next=p->next）。再将结点p的指针域改为指向新结点s（执行语句p->next=s）。返回到本节目录.2.3.2单链表的基本操作实现5．插入操作返回到本节目录.935．插入操作插入结点的过程如图2-10所示，算法描述见算法2.15。注：插入操作的①与②语句执行顺序不能颠倒，否则原p指针其后的链表将丢失。算法2.15voidIns_Elem(LinkList*p,ElemTypex){LinkList*s;s=(LinkList*)malloc(sizeof(LinkList));/*生成新结点s*/s->data=x;/*将数据x放入新结点的数据域*/s->next=p->next;/*将新结点s的指针域与p结点后面元素相连*/p->next=s;/*将p与新结点s链接*/}返回到本节目录.5．插入操作插入结点的过程如图2-10所示，算法描述见算法2945．插入操作（2）在第i个位置插入新结点s由于单链表的结点结构是单向后指的，因此要完成此操作需要找到第i结点的前驱结点即第i－1结点的指针p，此时可调用按序号查找GetList()函数求出p指针地址，然后在调用在已知结点p后方插入新结点Ins_Elem()函数操作即可，算法描述见算法2.16。算法2.16intInsElem(LinkList*L,inti,ElemTypex){LinkList*p;p=GetList(L,i-1);/*调用按序号查找函数GetList()，求出第i-1个元素地址p*/if(p!=NULL)/*判断查找的元素地址p是否存在*/{Ins_Elem(p,x);/*调用在已知结点p后插入结点函数Ins_Elem()*/returnOK;}elsereturnERROR;}返回到本节目录.5．插入操作（2）在第i个位置插入新结点s返回到本节目录.955．插入操作插入算法的时间性能分析：链表插入操作主要时间耗费在查找操作上，其时间复杂度为Ｏ(n)。返回到本节目录.5．插入操作插入算法的时间性能分析：返回到本节目录.962.3.2单链表的基本操作实现6．删除操作顺序表的删除操作同样需要移动大量的数据元素，而链表的删除只需修改指针而无需移动原表元素，那链表的删除操作是如何实现呢？（1）删除已知结点p之后结点s已知结点p为链表中除终端结点以外的任意结点，先将结点s中的数据域中的值赋给指针变量*x，则删除操作步骤如下：结点p指针域指向结点s下一个结点（执行语句p->next=s->next）。②释放s结点空间（执行语句free(s)）。返回到本节目录.2.3.2单链表的基本操作实现6．删除操作返回到本节目录.976．删除操作删除结点的过程如图2-11所示，算法描述见算法2.17。

图2-11在结点p之后删除结点s算法2.17voidDel_Elem(LinkList*p,ElemType*x){LinkList*s;s=p->next;/*s为要删除结点*/*x=s->data;/*将要删除的数据放入指针变量*x中*/p->next=s->next;/*将p结点的指针域与s结点后面元素相连*/free(s);/*释放结点s*/}返回到本节目录.6．删除操作删除结点的过程如图2-11所示，算法描述见算法2986．删除操作（2）删除未知结点（如第i个结点）s首先求出第i结点的前驱结点（第i-1结点）p的地址，可调用按序号查找GetList()函数求出p指针地址，然后再调用删除已知结点p之后结点s的DelList()函数操作即可。算法中注意if(p!=NULL&&p->next!=NULL)语句,只有当第i-1结点存在即（p!=NULL）而又不是终端结点即（p->next!=NULL）时，才能确定被删除结点存在，算法描述见算法2.18。算法2.18intDelElem(LinkList*L,inti,ElemType*x){LinkList*p;p=GetList(L,i-1);/*调用按序号查找第i-1个元素地址p函数*/if(p!=NULL&&p->next!=NULL){Del_Elem(p,x);/*调用删除已知结点p之后结点函数*/returnOK;}elsereturnERROR;}返回到本节目录.6．删除操作返回到本节目录.996．删除操作删除算法的时间性能分析：链表删除操作也主要时间耗费在查找操作上，其时间复杂度为Ｏ(n)。返回到本节目录.6．删除操作删除算法的时间性能分析：返回到本节目录.1002.3.2单链表的基本操作实现7．单链表的输出操作扫描单链表L，输出各元素的值，算法描述见算法2.19。算法2.19voidDispList(LinkList*L){LinkList*p;p=L->next;while(p!=NULL){printf("%c",p->data);p=p->next;}}返回到本节目录.2.3.2单链表的基本操作实现7．单链表的输出操作返回到本1012.3.3链表的变形1．循环单链表循环链表是另一种形式的链式存储结构。对于单链表而言，最后一个结点的指针域为空，如果将该链表中最后一个结点的指针域指向头结点，整个链表形成一个环，就构成了循环单链表，如图2-12所示。由此，从表中的任意结点出发均可找到表中的其他结点。在循环单链表上的操作基本上与非循环的单链表相同，只是将原来判断指针是否为NULL，改为是否是头指针L即可。图2-12带头结点的循环单链表返回到本节目录.2.3.3链表的变形1．循环单链表图2-12带头结点的1022.3.3链表的变形2．双链表（1）双链表的定义在单链表结点中只有一个指向直接后继的指针域next，这样从某个结点出发只能顺指针方向寻找它的后继结点。若要寻找结点的直接前驱，则需从头指针出发查找前驱。若希望能够快速查找一个结点的直接前驱，则可以再增加一个指向其直接前驱的指针域prior，这样就构成了双向链接表，简称双链表，其结点结构如图2-13所示。图2-13双链表的结点示意图其中，data部分称为数据域，用于存储一个数据元素（结点Node）的信息。prior部分称为前驱指针域，用于存储其直接前驱的存储地址的信息。next部分称为后继指针域，用于存储其直接后继的存储地址的信息。前驱指针域数据域后继指针域priordatanext返回到本节目录.2.3.3链表的变形2．双链表前驱指针域数据域后继指针域p1032．双链表（2）双链表的类型定义typedefcharElemType;/*定义ElemType为char类型*/typedefstructdunode/*双链表存储类型*/{ElemTypedata;/*定义结点的数据域*/structdunode*prior;/*定义结点的前驱指针域*/structdunode*next;/*定义结点的后继指针域*/}DuLinkList;返回到本节目录.2．双链表（2）双链表的类型定义返回到本节目录.1042．双链表为了算法对所有的结点处理可一致化，与单链表一样，本章讨论的双链表均指带头结点的双链表。带头结点的双链表如图2-14所示。其中，头结点的数据域可以不存储任何信息，也可以存放特殊的信息，头结点的前驱指针域为空（即NULL或用∧表示），后继指针域存储链表中第一个结点的地址。当头结点的后继指针域为空（即NULL或用∧表示），则此表为空表。在非空表中，当某个结点的后继指针域为空，表示它为链表的最后一个结点。返回到本节目录.2．双链表为了算法对所有的结点处理可一致化，与单链表一样，本1052．双链表（3）双链表的基本运算在双链表中，有些操作（如求链表的长度、查找某个结点等）仅涉及一个方向的指针，其算法与单链表的操作相同，但在插入和删除操作时却有很大的区别。①在双链表中p指针指向的结点前插入新结点s操作先创建一个以x为值的新结点s，在p结点之前插入结点s，则插入操作步骤如下：将结点s的prior域指向结点p的前一个结点（执行语句s->prior=p->prior）。将结点p的前一个结点的next域指向结点s（执行语句p->prior->next=s）。将结点s的next域指向p结点（执行语句s->next=p）。将结点p的prior域指向结点s。（执行语句p->prior=s）。返回到本节目录.2．双链表（3）双链表的基本运算返回到本节目录.1062．双链表插入结点的过程如图2-15所示，算法描述见算法2.20。注：以上操作的步骤的顺序不是唯一的，但a操作步骤必须放在d操作步骤的前面完成，否则结点p的前驱结点的指针将丢失。返回到本节目录.2．双链表插入