1、普通高等教育“十一五”国家级规划教材21世纪高职高专新概念教材 数据结构C语言描述(第二版)前前 言言 二十一世纪是科学技术高速发展的信息时代，而计算机是处理信息的主要工具，因此，人们已经认识到，计算机知识已成为人类当代文化的一个重要组成部分。计算机科学技术以惊人的速度向前发展，它的广泛应用已从传统的数值计算领域发展到各种非数值计算领域。在非数值计算领域里，数据处理的对象已从简单的数值发展到一般的符号，进而发展到具有一定结构的数据。在这里，面临的主要问题是：针对每一种新的应用领域的处理对象，如何选择合适的数据表示（构构），如何有效地组织计算机存贮，并在此基础上又如何有效地实现对象之间的“运算”
2、关系。传统的解决数值计算的许多理论、方法和技术已不能满足解决非数值计算问题的需要，必须进行新的探索。数据结构就是研究和解决这些问题的重要基础理论。因此，“数据结构”课程已成为计算机类专业的一门重要专业基础课。数据结构是程序设计的中级课程，主要培养学生分析数据、组织数据的能力，告诉学生如何编写效率高、结构好的程序。本书作为计算机大专系列教材之一，在内容的选取、概念的引入、文字的叙述以及例题和习题的选择等方面，都力求遵循面向应用、逻辑结构简明合理、由浅入深、深入浅出、循序渐进、便于自学的原则，突出其实用性与应用性。全书共分十章。书中，安排了相当的篇幅来介绍这些基本数据结构的实际应用。教学要求教学要
3、求1 1了解：数据结构这门学科发展历史以及了解：数据结构这门学科发展历史以及在计算机科学中所处的地位。在计算机科学中所处的地位。2 2掌握：与数据结构有关的概念和术语。掌握：与数据结构有关的概念和术语。3 3掌握：如何评价一个算法的好坏。掌握：如何评价一个算法的好坏。第一章第一章 绪论绪论主要内容主要内容1.1 引言1.2 数据结构的发展简史及其在计算机科学中所处的地位1.3 什么是数据结构 1.4 基本概念和术语1.5 算法和算法的描述1.1 引言 众所周知，二十世纪四十年代，电子数字计算机问世的直接原因是解决弹道学的计算问题。早期，电子计算机的应用范围，几乎只局限于科学和工程的计算，其处理
4、的对象是纯数值性的信息，通常，人们把这类问题称为数值计算。近三十年来，电子计算机的发展异常迅猛，这不仅表现在计算机本身运算速度不断提高、信息存储量日益扩大、价格逐步下降，更重要的是计算机广泛地应用于情报检索、企业管理、系统工程等方面，已远远超出了科技计算的范围，而渗透到人类社会活动的一切领域。与此相应，计算机的处理对象也从简单的纯数值性信息发展到非数值性的和具有一定结构的信息。因此，再把电子数字计算机简单地看作是进行数值计算的工具，把数据仅理解为纯数值性的信息，就显得太狭隘了。现代计算机科学的观点，是把计算机程序处理的一切数值的、非数值的信息，乃至程序统称为数据（Data），而电子计算机则是加
5、工处理数据（信息）的工具。由于数据的表示方法和组织形式直接关系到程序对数据的处理效率，而系统程序和许多应用程序的规模很大，结构相当复杂，处理对象又多为非数值性数据。因此，单凭程序设计人员的经验和技巧已难以设计出效率高、可靠性强的程序。于是，就要求人们对计算机程序加工的对象进行系统的研究，即研究数据的特性以及数据之间存在的关系数据结构（Date Structure）。1.2 数据结构的发展简史及其在计算机科学中所处的地位发展史：1、“数据结构”作为一门独立的课程在国外是从1968年才开始设立的。2、1968年美国唐欧克努特教授开创了数据结构的最初体系，他所著的计算机程序设计技巧第一卷基本算法是第
6、一本较系统地阐述数据的逻辑结构和存储结构及其操作的著作。地位：1、“数据结构”在计算机科学中是一门综合性的专业基础课。2、数据结构是介于数学、计算机硬件和计算机软件三者之间的一门核心课程。3、数据结构这一门课的内容不仅是一般程序设计（特别是非数值性程序设计）的基础，而且是设计和实现编译程序、操作系统、数据库系统及其他系统程序的重要基础。1.3 什么是数据结构 计算机解决一个具体问题时，大致需要经过下列几个步骤：首先要从具体问题中抽象出一个适当的数学模型，然后设计一个解此数学模型的算法（Algorithm），最后编出程序、进行测试、调整直至得到最终解答。寻求数学模型的实质是分析问题，从中提取操作
7、的对象，并找出这些操作对象之间含有的关系，然后用数学的语言加以描述。计算机算法与数据的结构密切相关，算法无不依附于具体的数据结构，数据结构直接关系到算法的选择和效率。运算是由计算机来完成，这就要设计相应的插入、删除和修改的算法。也就是说，数据结构还需要给出每种结构类型所定义的各种运算的算法。直观定义：数据结构是研究程序设计中计算机操作的对象以及它们之间的关系和运算的一门学科。1.4 基本概念和术语 1数据 数据是人们利用文字符号、数字符号以及其他规定的符号对现实世界的事物及其活动所做的描述。在计算机科学中，数据的含义非常广泛，我们把一切能够输入到计算机中并被计算机程序处理的信息，包括文字、表格
8、、图象等，都称为数据。例如，一个个人书库管理程序所要处理的数据可能是一张如表1-1所示的表格。表 1-1 个人书库2结点 结点也叫数据元素，它是组成数据的基本单位。在程序中通常把结点作为一个整体进行考虑和处理。例如，在表1-1所示的个人书库中，为了便于处理，把其中的每一行（代表一本书）作为一个基本单位来考虑，故该数据由10个结点构成。一般情况下，一个结点中含有若干个字段（也叫数据项）。例如，在表1-1所示的表格数据中，每个结点都有登录号、书号、书名、作者、出版社和价格等六个字段构成。字段是构成数据的最小单位。3逻辑结构 结点和结点之间的逻辑关系称为数据的逻辑结构。在表1-1所示的表格数据中，各
9、结点之间在逻辑上有一种线性关系，它指出了10个结点在表中的排列顺序。根据这种线性关系，可以看出表中第一本书是什么书，第二本书是什么书，等等。4存储结构 数据在计算机中的存储表示称为数据的存储结构。在表1-1所示的表格数据在计算机中可以有多种存储表示，例如，可以表示成数组，存放在内存中；也可以表示成文件，存放在磁盘上，等等。5数据处理 数据处理是指对数据进行查找、插入、删除、合并、排序、统计以及简单计算等的操作过程。在早期，计算机主要用于科学和工程计算，进入八十年代以后，计算机主要用于数据处理。据有关统计资料表明，现在计算机用于数据处理的时间比例达到80%以上，随着时间的推移和计算机应用的进一步
10、普及，计算机用于数据处理的时间比例必将进一步增大。6数据结构（Data Structure）数据结构是研究数据元素（Data Element）之间抽象化的相互关系和这种关系在计算机中的存储表示（即所谓数据的逻辑结构和物理结构），并对这种结构定义相适应的运算，设计出相应的算法，而且确保经过这些运算后所得到的新结构仍然是原来的结构类型。为了叙述上的方便和避免产生混淆，通常我们把数据的逻辑结构统称为数据结构，把数据的物理结构统称为存储结构（Storage Structure）。7数据类型 数据类型是指程序设计语言中各变量可取的数据种类。数据类型是高级程序设计语言中的一个基本概念，它和数据结构的概念密
11、切相关。一方面，在程序设计语言中，每一个数据都属于某种数据类型。类型明显或隐含地规定了数据的取值范围、存储方式以及允许进行的运算。可以认为，数据类型是在程序设计中已经实现了的数据结构。另一方面，在程序设计过程中，当需要引入某种新的数据结构时，总是借助编程语言所提供的数据类型来描述数据的存储结构。8算法 简单地说就是解决特定问题的方法（关于算法的严格定义，在此不作讨论）。特定的问题可以是数值的，也可以是非数值的。解决数值问题的算法叫做数值算法，科学和工程计算方面的算法都属于数值算法，如求解数值积分，求解线性方程组、求解代数方程、求解微分方程等。解决非数值问题的算法叫做非数值算法，数据处理方面的算
12、法都属于非数值算法。例如各种排序算法、查找算法、插入算法、删除算法、遍历算法等。数值算法和非数值算法并没有严格的区别。一般说来，在数值算法中主要进行算术运算，而在非数值算法中主要进行比较和逻辑运算。另一方面，特定的问题可能是递归的，也可能是非递归的，因而解决它们的算法就有递归算法和非递归算法之分。从理论上讲，任何递归算法都可以通过循环，堆栈等技术转化为非递归算法。1.5 1.5 算法和算法的描述算法和算法的描述1.5.1 算法算法是执行特定计算的有穷过程。这个过程有5个特点：1.动态有穷：当执行一个算法时，不论是何种情况，在经过了 有限步骤后，这个算法一定要终止。2.确定性：算法中的每条指令都
13、必须是清楚的，指令无二义性。3.输入：具有0个或0个以上由外界提供的量。4.输出：产生1个或多个结果。5.可行性：每条指令都充分基本，原则上可由人仅用笔和纸在 有限的时间内也能完成。注意：算法和程序是有区别的，即程序未必能满足动态有穷。在本 书中，我们只讨论满足动态有穷的程序，因此“算法”和“程序”是通用的。一个算法可以用自然语言、数字语言或约定的符号来描述，也可以用计算机高级程序语言来描述，如Pascal语言、C语言或伪代码等。本书选用C语言作为描述算法的工具。现简单说明C语言的语法结构如下：1.5.2 算法的描述 1预定义常量和类型：#define TRUE 1；#define FALSE
14、 -1；#define ERROR NULL；2函数的形式 数据类型 函数名 （形式参数）形式参数说明；内部数据说明；执行语句组；/*函数名*/函数的定义主要由函数名和函数体组成，函数体用花括号“”和“”括起来。函数中用方括号括起来的部分为可选项，函数名之间的圆括号不可省略。函数的结果可由指针或别的方式传递到函数之外。执行语句可由各种类型的语句所组成，两个语句之间用“；”号分隔。可将函数中的表达式的值通过return语句返回给调用它的函数。最后的花括号“”之后的/*函数名*/为注释部分，可舍。3赋值语句 简单赋值：变量名=表达式，它表示将表达式的值赋给左边的变量；变量+，它表示变量加1后赋值给
15、变量；变量-，它表示变量减1后赋值给变量；成组赋值：1.（变量1，变量2，变量3，变量k）=（表达式1，表达式2，表达式3，表达式k）；2.数组名1下标1下标2=数组名2下标1下标2 串联赋值：变量1=变量2=变量3=变量k=表达式；条件赋值：变量名=条件表达式？表达式1：表达式2；交换赋值：变量1变量2，表示变量1和变量2互换；4条件选择语句if （表达式）语句；if （表达式）语句1；else 语句2；情况语句 switch （表达式）case 判断值1；语句组1；break；case 判断值2；语句组2；break；case 判断值n；语句组n；break；default：语句组；bre
16、ak；注意：switch case语句是先计算表达式的值，然后用其值与判断值相比较，若它们相一致时，就执行相应的case下的语句 组；若 不 一 致，则 执 行default下的语句组；其中的方括号代表可选项。5循环语句 for语句 for（表达式1；表达式2；表达式3）循环体语句；首先计算表达式1的值，然后求表达式2的值，若结果非零则执行循环体语句，最后对表达式3运算，如此循环，直到表达式2的值为零时止。while语句 while（条件表达式）循环体语句；while循环首先计算条件表达式的值，若条件表达式的值非零，则执行循环体语句，然后再次计算条件表达式，重复执行，直到条件表达式的值为假时退
17、出循环，执行该循环之后的语句。do-while语句 do 循环体语句 while（条件表达式）该循环语句首先执行循环体语句。然后再计算条件表达式的值，若条件表达式成立，则再次执行循环体，再计算条件表达式的值，直到条件表达式的值为零，即条件不成立时结束循环。6输入、输出语句 输入语句：用函数scanf实现，特别当数据为字符时，用getchar函数实现。输出语句：用printf函数实现，当要输出字符数据时，用putchar函数实现。7其他一些语句（1）return表达式或return：用于函数结束。（2）break语句：可用在循环语句或case语句中结束循环过程或跳出情况语句。（3）exit语句：
18、表示出现异常情况时，控制退出语句。8注释形式 可用/*字符串*/或者 单行注释 或/文字序列。9一些基本的函数如：max函数，用于求一个或几个表达式中的最大值；min函数，用于求一个或几个表达式中的最小值；abs函数，用于求表达式的绝对值；eof函数，用于判定文件是否结束；eoln函数，用于判断文本行是否结束。例 计算f=1！+2！+3！+n！，用C语言描述。void factorsum（n）int n；int i，j；int f，w；f=0；for（i=1，i=n；i+）w=1；for（j=1，j=i；j+）w=w*j；f=f+w；return；上述算法所用到的运算有乘法、加法、赋值和比较，
19、其基本运算为乘法操作。在上述算法的执行过程中，对外循环变量i的每次取值，内循环变量j循环i次。因为内循环每执行一次，内循环体语句w=w*j只作一次乘法操作，即当内循环变量j循环i次时，内循环体的语句w=w*j作i次乘法。所以，整个算法所作的乘法操作总数是：f（n）=1+2+3+n=n（n-1）/2。1.5.3 算法评价 设计一个好的算法应考虑以下几个方面：1正确性 “正确”的含义在通常的用法中有很大的差别，大体可分为以下四个层次：程序不含语法错误；程序对于几组输入数据能够得出满足规格说明要求的结果；程序对于精心选择的典型、苛刻而带有刁难性的几组数据能够得出满足规格说明要求的结果；程序对一切合法
20、的输入数据都能产生满足规格说明要求的结果。2运行时间 运行时间是指一个算法在计算机上运算所花费的时间。它大致等于计算机执行一种简单操作（如赋值操作、转向操作、比较操作等等）所需要的时间与算法中进行简单操作次数的乘积。通常把算法中包含简单操作次数的多少叫做算法的时间复杂性，它是一个算法运行时间的相对量度。3占用的存储空间 一个算法在计算机存储器上所占用的存储空间，包括存储算法本身所占用的存储空间，算法的输入、输出数据所占用的存储空间 和算法运行过程中临时占用的存储空间。分析一个算法所占用的存储空间要从各方面综合考虑。算法在运行过程中所占用的存储空间的大小被定义为算法的空间复杂性。它包括局部变量所
21、占用的存储空间和系统为了实现递归所使用的堆栈这两个部分。算法的空间复杂性一般以数量级的形式给出。4简单性 最简单和最直接的算法往往不是最有效的，但算法的简单性使得证明其正确性比较容易，同时便于编写、修改、阅读和调试，所以还是应当强调和不容忽视的。不过对于那些需要经常使用的算法来说，高效率（即尽量减少运行时间和压缩存储空间）比简单性更为重要。本章小结本章小结本章主要介绍了如下一些基本概念：数据结构：数据结构：数据结构是研究数据元素之间抽象化的相互关系和这种关系在计算机中的存储表示（即所谓数据的逻辑结构和物理结构），并对这种结构定义相适应的运算，设计出相应的算法，而且确保经过这些运算后所得到的新结
22、构仍然是原来的结构类型。数据：数据：数据是人们利用文字符号、数字符号以及其他规定的符号对现实世界的事物及其活动所做的描述。在计算机科学中，数据的含义非常广泛，我们把一切能够输入到计算机中并被计算机程序处理的信息，包括文字、表格、图象等，都称为数据。结点：结点：结点也叫数据元素，它是组成数据的基本单位。逻辑结构：逻辑结构：结点和结点之间的逻辑关系称为数据的逻辑结构。存储结构：存储结构：数据在计算机中的存储表示称为数据的存储结构。数据处理：数据处理：数据处理是指对数据进行查找、插入、删除、合并、排序、统计以及简单计算等的操作过程。数据类型：数据类型：数据类型是指程序设计语言中各变量可取的数据种类。
23、数据类型是高级程序设计语言中的一个基本概念，它和数据结构的概念密切相关。习习 题题 一一1简述下列术语：数据、结点、逻辑结构、存储结构、数据处理、数据结构和数据类型。2试根据以下信息：校友姓名、性别、出生年月、毕业时间、所学专业、现在工作单位、职称、职务、电话等，为校友录构造一种适当的数据结构（作图示意），并定义必要的运算和用文字叙述相应的算法思想。3什么是算法？算法的主要特点是什么？4如何评价一个算法？教学要求1了解：线性表的定义和基本运算。2掌握：线性表的两种存储结构：顺序存储结构和链式存储结构的描述方式，以及这两种存储结构上的基本运算的实现算法。3了解：线性表处理一元多项式的操作方法及其
24、算法的实现。4掌握：线性表的两种存储结构的特点及其具体实现。第二章第二章 线性表线性表主要内容2.1 线性表的逻辑结构线性表的逻辑结构2.2 线性表的顺序存储结构线性表的顺序存储结构 2.3 线性表的链式存储结构线性表的链式存储结构2.4 一元多项式的表示及相加一元多项式的表示及相加 2.5实训实训 2.1 2.1 线性表的逻辑结构线性表的逻辑结构 线性表由一组具有相同属性的数据元素构成。数据元素的含义广泛，在不同的具体情况下，可以有不同的含义。例如：英文字母表（A，B，C，Z）是一个长度为26的线性表，其中的每一个字母就是一个数据元素；再如，某公司2000年每月产值表（400，420，500
25、，600，650）(单位：万元)是一个长度为12的线性表，其中的每一个数值就是一个数据元素。上述两例中的每一个数据元素都是不可分割的，在一些复杂的线性表中，每一个数据元素又可以由若干个数据项组成，在这种情况下，通常将数据元素称为记录（record），例如，图2-1的某单位职工工资表就是一个线性表，表中每一个职工的工资就是一个记录，每个记录包含八个数据项：职工号、姓名、基本工资。职工号姓名基本工资岗位工资奖金应发工资扣款实发工资1201张强54030020010402010201301周敏500200200900208801202徐黎芬55030020010503010201105黄承振5302
26、5020098020960图2-1 职工工资表 矩阵也是一个线性表，但它是一个比较复杂的线性表。在矩阵中，我们可以把每行看成是一个数据元素，也可以把每列看成是一个数据元素，而其中的每一个数据元素又是一个线性表。综上所述，一个线性表是n0个数据元素a0，a1，a2，an-1的有限序列。如果n0，则除a0和an-1外，有且仅有一个直接前趋和一个直接后继数据元素，ai（0in-1）为线性表的第i个数据元素，它在数据元素ai-1之后，在ai+1之前。a0为线性表的第一个数据元素，而an-1是线性表的最后一个数据元素；若n=0，则为一个空表，表示无数据元素。因此，线性表或者是一个空表（n=0），或者可以
27、写成：（a0，a1，a2，ai-1，ai，ai+1，an-1）。抽象数据类型线性表的定义如下：LinearList=(D,R)其中，D=ai|aiElemSet,i=0,1,2,，n-1 n1 R=|ai-1，aiD,i=0,1,2,，n-1 Elemset为某一数据对象集；n为线性表的长度。线性表的主要操作有如下几种：1 Initiate(L)初始化：构造一个空的线性表L。2 Insert(L,i,x)插入：在给定的线性表L中，在第i个元素之前插入数据元素x。线性表L长度加1。3 Delete(L,i)删除：在给定的线性表L中，删除第i个元素。线性表L的长度减1。4 Locate(L,x)查
28、找定位：对给定的值x，若线性表L中存在一个元素ai与之相等，则返回该元素在线性表中的位置的序号i，否则返回Null（空）。5 Length(L)求长度：对给定的线性表L，返回线性表L的数据元素的个数。6 Get(L,i)存取：对给定的线性表L，返回第i（0iLength(L)-1）个数据元素，否则返回Null。7 Traverse(L)遍历：对给定的线性表L，依次输出L的每一个数据元素。8 Copy(L,C)复制：将给定的线性表L复制到线性表C中。9 Merge(A,B,C)合并：将给定的线性表A和B合并为线性表C。上面我们定义了线性表的逻辑结构和基本操作。在计算机内，线性表有两种基本的存储结
29、构：顺序存储结构和链式存储结构。下面我们分别讨论这两种存储结构以及对应存储结构下实现各操作的算法。2.2 2.2 线性表的顺序存储结构线性表的顺序存储结构 在计算机中用一组地址连续的存储单元依次存储线性表的各个数据元素，称作线性表的顺序存储结构。2.2.1 线性表的顺序存储结构线性表的顺序存储结构在线性表的顺序存储结构中，其前后两个元素在存储空间中是紧邻的，且前驱元素一定存储在后继元素的前面。由于线性表的所有数据元素属于同一数据类型，所以每个元素在存储器中占用的空间大小相同，因此，要在该线性表中查找某一个元素是很方便的。假设线性表中的第一个数据元素的存储地址为Loc(a0)，每一个数据元素占d
30、字节，则线性表中第i个元素ai在计算机存储空间中的存储地址为：Loc(ai)=Loc(a0)+id在程序设计语言中，通常利用数组来表示线性表的顺序存储结构。这是因为数组具有如下特点：（1）数据中的元素间的地址是连续的；（2）数组中所有元素的数据类型是相同的。而这与线性表的顺序存储空间结构是类似的。1一维数组一维数组若定义数组An=a0，a1，a2，an-1，假设每一个数组元素占用d个字节，则数组元素A0，A1，A2，An-1的地址分别为Loc(A0)，Loc(A0)+d，Loc(A0)+2d，Loc(A0)+（n-1）d。其结构如图2-2所示。若定义数组Anm，表示此数组有n行m列，如下图2-
31、3所示。0 1 2 j m-10 a00 a01 a02 a0j a0 m-11a10 a11 a12 a1j a1 m-12a20 a21 a22 a2j a2 m-1i ai0 ai1 ai2 aij ai m-1 n-1 an-1,0 an-1,1 an-1,2 an-1,j an-1,m-1 图2-3 二维数组二维数组二维数组在C语言中，二维数组的保存是按照行方式存储的，先将第一行元素排好，接着排第二行元素，直至所有行的元素排完。如图2-4所示。图2-4 二维数组存储示意图 2.2.2 线性表在顺序存储结构下的运算线性表在顺序存储结构下的运算可用C语言描述顺序存储结构下的线性表（顺序表
32、）如下：#define TRUE 1#define FALSE 0#define MAXNUM Elemtype ListMAXNUM;/*定义顺序表List*/int num=-1;/*定义当前数据元素下标，并初始化*/我们还可将数组和表长封装在一个结构体中：struct Linear_list Elemtype ListMAXNUM;/*定义数组域*/int length;/*定义表长域*/1.1.顺序表的插入操作顺序表的插入操作在长度为num(0numMAXNUM-2)的顺序表List的第i(0inum+1)个数据元素之前插入一个新的数据元素x时，需将最后一个即第num个至第i个元素（共
33、num-i+1个元素）依次向后移动一个位置，空出第i个位置，然后把x插入到第i个存储位置，插入结束后顺序表的长度增加1，返回TRUE值；若i0或inum+1，则无法插入，返回FALSE。如图2-5所示。在长度为num(0numMAXNUM-2)的顺序表List的第i(0inum+1)个数据元素之前插入一个新的数据元素x时，需将最后一个即第num个至第i个元素（共num-i+1个元素）依次向后移动一个位置，空出第i个位置，然后把x插入到第i个存储位置，插入结束后顺序表的长度增加1，返回TRUE值；若i0或inum+1，则无法插入，返回FALSE。如图2-5所示。0 a0 1 a1 2 a2 i-
34、1 ai-1 i ai i+1 ai+1 i+2 ai+2 num anum 0 a0 1 a1 2 a2 i-1 ai-1 i x i+1 ai i+2ai+1 numanum 插入x图2-5 在数组中插入元素 其算法如下：【算法2.1 顺序表的插入】int Insert(Elemtype List,int*num,int i,Elemtype x)/*在顺序表List中，*num为表尾元素下标位置，在第i个元素前插入数据元素x，若成功，返回TRUE，否则返回FALSE。*/int j;if(i*num+1)printf(“Error!”);/*插入位置出错*/return FALSE;if
35、(*num=MAXNUM-1)printf(“overflow!”);return FALSE;/*表已满*/for(j=*num;j=i;j-)Listj+1=Listj;/*数据元素后移*/Listi=x;/*插入x*/(*num)+;/*长度加1*/return TRUE;注：顺序表List的最大数据元素个数为MAXNUM，num标识为顺序表的当前表尾（numMAXNUM-1）。顺序表的删除操作 序号 元素 0 a0 1 a1 2 a2 i-1 ai-1 i ai+1 i+1 ai+2 num anum 0 a0 1 a1 2 a2 i-1 ai-1 i ai i+1ai+1 numan
36、um 图2-6 在数组中删除元素在长度为num(0numMAXNUM-1)的顺序表List，删除第i(0inum)个数据元素，需将第i至第num个数据元素的存储位置（num-i+1）依次前移，并使顺序表的长度减1，返回TRUE值，若i0或inum，则无法删除，返回FALSE值，如图2-6所示。其算法如下：【算法2.2 顺序表的删除】int Delete(Elemtype List,int*num,int i)/*在线性表List中，*num为表尾元素下标位置，删除第i个元素，线性表的元素减1，若成功，则返回TRUE；否则返回FALSE。*/int j;if(i*num)printf(“Erro
37、r!”);return FALSE;/*删除位置出错！*/for(j=i+1;j=*num;j+)Listj-1=Listj;/*数据元素前移*/(*num)-;/*长度减1*/return TRUE;从上述两个算法来看，很显然，在线性表的顺序存储结构中插入或删除一个数据元素时，其时间主要耗费在移动数据元素上。而移动元素的次数取决于插入或删除元素的位置。假设Pi是在第i个元素之前插入一个元素的概率，则在长度为n的线性表中插入一个元素时所需移动元素次数的平均次数为)(0inpEniiins假设qi是删除第i个元素的概率，则在长度为n的线性表中删除一个元素时所需移动元素次数的平均次数为如果在线性表
38、的任何位置插入或删除元素的概率相等，即 则 可见，在顺序存储结构的线性表中插入或删除一个元素时，平均要移动表中大约一半的数据元素。若表长为n，则插入和删除算法的时间复杂度都为O(n)。在顺序存储结构的线性表中其他的操作也可直接实现，在此不再讲述。)1(10inqEniidel11npinqi12)(110ninnEniins21)1(110ninnEnidel例：将有序线性表La=2,4,6,7,9，Lb=1,5,7,8，合并为Lc=1,2,4,5,6,7,7,8,9。分析：Lc中的数据元素或者是La中的数据元素，或者是Lb中的数据元素，则只要先将Lc置为空表，然后将La或Lb中的元素逐个插入
39、到Lc中即可。设两个指针i和j分别指向La和Lb中的某个元素，若设i当前所指的元素为a，j当前所指的元素为b，则当前应插入到Lc中的元素c为c=当时当时，很显然，指针i和j的初值均为1，在所指元素插入Lc后，i，j在La或Lb中顺序后移。算法如下：void merge(Elemtype La,Elemtype Lb,Elemtype*Lc)int i,j,k;int La_length,Lb_length;i=j=0;k=0;La_length=Length(La);Lb_length(Lb)=Length(Lb);/*取表La,Lb的长度*/Initiate(Lc);/*初始化表Lc*/Wh
40、ile(i=La_length&j=Lb_length)a=get(La,i);b=get(Lb,j);if(ab)insert(Lc,+k,a);+i;else insert(Lc,+k,b);+j;/*将La和Lb的元素插入到Lc中*/while(i=La_length)a=get(La,i);insert(Lc,+k,a);while(jnext=NULL;return TRUE;注意：形参h定义为指针的指针类型，若定义为指针类型，将无法带回函数中建立的头指针值。（2）单链表的插入操作1）已知线性链表head，在p指针所指向的结点后插入一个元素x。在一个结点后插入数据元素时，操作较为简单
41、，不用查找便可直接插入。操作过程如图2-8所示。headpps head(a)插入前a0a1aian-1ai+1(b)插入后图2-8 单链表的后插入xxsan-1aia0a1相关语句如下：【算法2.4 单链表的后插入】s=(slnodetype*)malloc(sizeof(slnodetype);s-data=x;s-next=p-next;p-next=s;2）已知线性链表head，在p指针所指向的结点前插入一个元素x。前插时，必须从链表的头结点开始，找到P指针所指向的结点的前驱。设一指针q从附加头结点开始向后移动进行查找，直到p的前趋结点为止。然后在q指针所指的结点和p指针所指的结点之间
42、插入结点s。操作过程如图2-9所示。相关语句如下：【算法2.5 单链表的结点插入】q=head;while(q-next!=p)q=q-next;s=(slnodetype*)malloc(sizeof(slnodetype);s-data=x;s-next=p;q-next=s;(b)插入后图2-9 单链表的前插入sxpa0ai-1aian-1q headx0aai-1an-1ai headqps（a）插入前【算法2.6 单链表的前插入】int insert(slnodetype*h,int i,Elemtype x)/*在链表h中，在第i个数据元素插入一个数据元素x*/slnodetype
43、*p,*q,*s;int j=0;p=h;while(p!=NULL&jnext;j+;/*寻找第i-1个结点*/if(j!=i-1)printf(“Error!”);return FALSE;/*插入位置错误*/if(s=(slnodetype*)malloc(sizeof(slnodetype)=NULL)return FALSE;s-data=x;s-next=p-next;q-next=s;return TRUE;例：下面C程序中的功能是，首先建立一个线性链表head=3，5，7，9，其元素值依次为从键盘输入正整数（以输入一个非正整数为结束）；在线性表中值为x的元素前插入一个值为y的数
44、据元素。若值为x的结点不存在，则将y插在表尾。#include“stdlib.h”#include“stdio.h”struct slnodeint data;struct slnode*next;/*定义结点类型*/main()int x,y,d;struct slnode*head,*p,*q,*s;head=NULL;/*置链表空*/q=NULL;scanf(“%d”,&d);/*输入链表数据元素*/while(d0)p=(struct slnode*)malloc(sizeof(struct slnode);/*申请一个新结点*/p-data=d;p-next=NULL;if(head
45、=NULL)head=p;/*若链表为空，则将头指针指向当前结点p*/else q-next=p;/*链表不为空时，则将新结点链接在最后*/q=p;/*将指针q指向链表的最后一个结点*/scanf(“%d”,&d);scanf(“%d,%d”,&x,&y);s=(struct slnode*)malloc(sizeof(struct slnode);s-data=y;q=head;p=q-next;while(p!=NULL)&(p-data!=x)q=p;p=p-next;/*查找元素为x的指针*/s-next=p;q-next=s;/*插入元素y*/（3）单链表的删除操作若要删除线性链表h
46、中的第i个结点，首先要找到第i个结点并使指针p指向其前驱第i-1个结点，然后删除第i个结点并释放被删除结点空间。操作过程如图2-10所示。其算法如下：【算法2.7 单链表的删除】int Delet(slnodetype*h,int i)/*在链表h中删除第i个结点*/slnodetype*p,*s;int j;p=h;j=0;while(p-next!=NULL&jnext;j=j+1;/*寻找第i-1个结点,p指向其前驱*/if(j!=i-1)printf(“Error!”);/*删除位置错误!*/return FALSE;s=p-next;p-next=p-next-next;/*删除第i
47、个结点*/free(s);/*释放被删除结点空间*/return TRUE;head head (b)删除并释放第i个结点图2-10 在线性链表中删除一个结点的过程aiai-1ai+1an-1p(a)寻找第i个结点指向其前驱ppsan-1ai+1aiai-1(p!=NULL&jnext!=NULL&jnext;head-next=NULL;while(p!=NULL)q=p-next;p-next=head-next;head-next=p;p=q;a0a1an-1a3pqa0a1an-1a3pqa1a0an-1a3pqa0a1an-1a3 head head head head图2-11 单
48、链表逆置2.3.2 循环链表循环链表循环链表(Circular Linked List)是另一种形式的链式存储结构。是将单链表的表中最后一个结点指针指向链表的表头结点，整个链表形成一个环，这样从表中任一结点出发都可找到表中其他的结点。图2-12（a）为带头结点的循环单链表的空表形式，图2-12（b）为带头结点的循环单链表的一般形式。带头结点的循环链表的操作实现算法和带头结点的单链表的操作实现算法类同，差别在于算法中的条件在单链表中为p!=null或p-next!=null；而在循环链表中应改为p!=head或p-next!=head。在循环链表中，除了头指针head外，有时还加了一个尾指针re
49、ar，尾指针read指向最后一结点，从最后一个结点的指针又可立即找到链表的第一个结点。在实际应用中，使用尾指针代替头指针来进行某些操作，往往更简单。head(a)循环链表的空表形式 head (b)循环链表的一般形式图2-12 循环链表a0a1an-1ai例：将两个循环链表首尾相接。La为第一个循环链表表尾指针，Lb为第二个循环链表表尾指针。合并后Lb为新链表的尾指针。Void merge(slnodetype*La,slnodetype*Lb)slnodetype*p;p=La-next;Lb-next=La-next;La-next=p-next;free(p);(a)a0a1an-1b0
50、b1bn-1a0a1an-1a0a1an-1LaLbLb(b)图2-13 循环链表的合并如图2-13所示，在这个算法中，时间复杂度为O(1)。2.3.3 2.3.3 双向链表双向链表1双向链表双向链表在单链表的每个结点中只有一个指示后继的指针域，因此从任何一个结点都能通过指针域找到它的后继结点；若需找出该结点的前驱结点，则此时需从表头出发重新查找。换句话说，在单链表中，查找某结点的后继结点的执行时间为O(1)，而查找其前驱结点的执行时间为O(n)。我们可用双向链表来克服单链表的这种缺点，在双向链表中，每一个结点除了数据域外，还包含两个指针域，一个指针（next）指向该结点的后继结点，另一个指针
