用c语言描述完整版课件全套ppt整本书电子讲义全书电子课件最全教学教程.ppt

第第一一章章 绪论绪论第第1章章绪论绪论1.1什么是数据结构什么是数据结构1.2基本概念和术语基本概念和术语1.3数据类型和抽象数据类型数据类型和抽象数据类型1.4算法描述与算法评价算法描述与算法评价第第一一章章 绪论绪论 本本章章将将介介绍绍数数据据结结构构研研究究的的对对象象、基基本本概概念念和和术术语语、算算法法的的概概念念及及其其描描述述方方法法（C C语语言言描描述述）、数数据据类类型型以以及及抽抽象象数数据据类类型型，并并概概述述数数据据结结构的发展概况及其在计算机科学中的地位。构的发展概况及其在计算机科学中的地位。第第1 1章章 绪绪 论论第第一一章章 绪论绪论随随着着计计算算机机应应用用领领域域的的不不断断扩扩大大，计计算算机机处处理理的的对对象象更更多多的的是是非非数数值值计计算算问问题题，它它们们的的数数学学模模型型无无法法用用数数学学方方程程来来进进行行描描述述，此此时时就就必必须须建建立立相相应应的的数数据据结结构构来来进进行行描描述述，分分析析问问题题中中所所用用到到的的数数据据是是如如何何组组织织的的，研研究究数数据据之之间间的的关关系系如如何何，进进而而为为解解决决这这些些问问题题设设计计出出合合适的数据结构。适的数据结构。1.1什么是数据结构什么是数据结构第第一一章章 绪论绪论例例1职工信息管理职工信息管理图图1.1职工花名册表职工花名册表编号编号姓姓 名名性性 别别年年 龄龄月月 收收 入入1 1李李 泉泉男男51519809802 2王王 怡怡女女47479459453 3张张 三三男男35358708704 4马小丁马小丁男男2727840840.第第一一章章 绪论绪论将将每每位位职职工工的的信信息息组组织织成成如如图图1.1所所示示的的花花名名册册。花花名名册册中中每每个个职职工工的的信信息息由由编编号号、姓姓名名、性性别别、年年龄龄、月月收收入入等等项项目目组组成成，占占表表的的一一行行，表表中中的的结结点点和和结结点点之之间间是是一一种种简简单单的的线线性性关关系系,这这就就是是上上述述花花名名册册表表的的线线性性逻逻辑辑结结构构。当当用用计计算算机机对对上上述述花花名名册册表表中中的的数数据据进进行行运运算算时时，就就要要考考虑虑那那些些结结点点在在计计算算机机中中的的存存储储表表示示，即即存存储储结结构构。另另外外，还还必必须须考考虑虑如如何进行结点的插入、删除、修改、检索或查找，这就涉及到数据的运算何进行结点的插入、删除、修改、检索或查找，这就涉及到数据的运算第第一一章章 绪论绪论例例2旅游交通网络图旅游交通网络图如图如图1.2所示，为一个旅游交通网络咨询系统，可采用一种称之为所示，为一个旅游交通网络咨询系统，可采用一种称之为图的结构来表示实际的交通网络，图的结构来表示实际的交通网络，此时，这个交通网络图就表示一个此时，这个交通网络图就表示一个数据结构。在这个数据结构中，结点之间的关系可以是任意的，图中数据结构。在这个数据结构中，结点之间的关系可以是任意的，图中任意两个结点之间都可以相关。同样，必须考虑构造后将这张图存放任意两个结点之间都可以相关。同样，必须考虑构造后将这张图存放入计算机中，这就要涉及到图的存储结构问题，以及图的运算。入计算机中，这就要涉及到图的存储结构问题，以及图的运算。从以上例子可见，要描述诸如此类的非数值计算问题的数学模型，从以上例子可见，要描述诸如此类的非数值计算问题的数学模型，涉及到一些诸如表、图还有树之类的数据结构。涉及到一些诸如表、图还有树之类的数据结构。数据结构课程实际上是一门研究非数值计算问题的程序设计中计数据结构课程实际上是一门研究非数值计算问题的程序设计中计算机的操作对象以及它们之间的关系和运算操作等的一门学科。在计算机的操作对象以及它们之间的关系和运算操作等的一门学科。在计算机科学中，数据结构不仅是一般程序设计（特别是非数值计算的程算机科学中，数据结构不仅是一般程序设计（特别是非数值计算的程序设计）的基础，而且是设计和实现编译程序、操作系统、数据库系序设计）的基础，而且是设计和实现编译程序、操作系统、数据库系统及其它系统程序和大型应用程序的重要基础。统及其它系统程序和大型应用程序的重要基础。第第一一章章 绪论绪论第第一一章章 绪论绪论数据是指信息的载体，是对客观事物的符号表示，是对有效地输入到数据是指信息的载体，是对客观事物的符号表示，是对有效地输入到计算机中并能被计算机程序处理的符号的总称。如声音、图形、图像。计算机中并能被计算机程序处理的符号的总称。如声音、图形、图像。数据元素是数据的基本单位，数据项是数据的不可分割的最小单位。数据元素是数据的基本单位，数据项是数据的不可分割的最小单位。有时也称之为结点、元素、顶点、记录等。一个数据元素可由若干个数据有时也称之为结点、元素、顶点、记录等。一个数据元素可由若干个数据项组成，如上面职工花名册中的每个人的信息就是一个数据元素，而每个项组成，如上面职工花名册中的每个人的信息就是一个数据元素，而每个人的信息包括编号、姓名、性别、年龄、月收入等，这每一个项目就属于人的信息包括编号、姓名、性别、年龄、月收入等，这每一个项目就属于数据项。数据项。1.2基本概念和术语基本概念和术语第第一一章章 绪论绪论数据对象是性质相同的数据元素的集合，是数据的一个子集。数据对象是性质相同的数据元素的集合，是数据的一个子集。数据类型（数据类型）是对在计算机中表示的同一数据对象及其在该数据类型（数据类型）是对在计算机中表示的同一数据对象及其在该数据对象上的一组操作的总称。数据对象上的一组操作的总称。数据类型有时还分为原子数据类型和结构数据类型有时还分为原子数据类型和结构数据类型。数据类型。数据结构指的是数据及数据之间的相互关系。一般地，数据结构包括数据结构指的是数据及数据之间的相互关系。一般地，数据结构包括以下三个方面的内容：以下三个方面的内容：（1）数据元素之间的逻辑关系，有时也称为数据的逻辑结构。）数据元素之间的逻辑关系，有时也称为数据的逻辑结构。（2）数据元素及其关系在计算机内存中的表示（又称为映象），称之）数据元素及其关系在计算机内存中的表示（又称为映象），称之为数据的物理结构，又称为数据的存储结构，它包括数据元素的表示和数为数据的物理结构，又称为数据的存储结构，它包括数据元素的表示和数据元素之间关系的表示。据元素之间关系的表示。（3）数据的运算及实现，即对数据元素可以施加的操作及其这些操作）数据的运算及实现，即对数据元素可以施加的操作及其这些操作在相应的存储结构上的实现。在相应的存储结构上的实现。第第一一章章 绪论绪论数据的逻辑结构是从逻辑关系上描述数据，可以看作是从具体问题数据的逻辑结构是从逻辑关系上描述数据，可以看作是从具体问题抽象出来的数学模型。如上例中的职工花名册表。根据数据元素之间的抽象出来的数学模型。如上例中的职工花名册表。根据数据元素之间的不同特性，通常有下列四类基本逻辑结构：不同特性，通常有下列四类基本逻辑结构：（1）线性结构：结构中的数据元素存在一个对一个的关系，即所谓）线性结构：结构中的数据元素存在一个对一个的关系，即所谓的线性关系。的线性关系。（2）树型结构：结构中的数据元素之间存在一个对多个的关系，是）树型结构：结构中的数据元素之间存在一个对多个的关系，是结点之间有分支、并具有层次关系的结构，它非常类似于自然界中的树。结点之间有分支、并具有层次关系的结构，它非常类似于自然界中的树。（3）图或网状结构：该结构中的数据元素之间的关系存在多个对多）图或网状结构：该结构中的数据元素之间的关系存在多个对多个的关系，如交通网络图就是一个图状结构。个的关系，如交通网络图就是一个图状结构。（4）集合：结构中的数据元素之间除了）集合：结构中的数据元素之间除了“同属于一个集合同属于一个集合”的相互的相互关系外，别无其它关系。关系外，别无其它关系。有时将树形结构、集合和图或网状结构称为非线性结构，此时数据有时将树形结构、集合和图或网状结构称为非线性结构，此时数据逻辑结构就可分为线性结构和非线性结构两类。逻辑结构就可分为线性结构和非线性结构两类。第第一一章章 绪论绪论数据的存储结构是指逻辑结构用计算机语言的实现，就是数据元素数据的存储结构是指逻辑结构用计算机语言的实现，就是数据元素及其关系如何存放入计算机内存的问题。一般地，数据的存储结构可按及其关系如何存放入计算机内存的问题。一般地，数据的存储结构可按以下四种基本存储方法而得到：以下四种基本存储方法而得到：（1）顺序存储方法：是把逻辑上相邻的结点存储在物理位置上相邻）顺序存储方法：是把逻辑上相邻的结点存储在物理位置上相邻的存储单元中，结点间的逻辑关系由存储单元的相邻关系而体现。由此的存储单元中，结点间的逻辑关系由存储单元的相邻关系而体现。由此得到的存储表示称为顺序存储结构，通常可借助计算机语言的数组来描得到的存储表示称为顺序存储结构，通常可借助计算机语言的数组来描述。述。（2）链状存储方式：不要求逻辑上相邻的结点在物理位置上也相邻，）链状存储方式：不要求逻辑上相邻的结点在物理位置上也相邻，数据元素可以存储在任意位置。为了实现数据元素之间逻辑关系的存储，数据元素可以存储在任意位置。为了实现数据元素之间逻辑关系的存储，必须通过一些附加的手段来存储这种相互关系，由此得到的存储表示称必须通过一些附加的手段来存储这种相互关系，由此得到的存储表示称为链状存储结构。一般可以用指针来实现，通常可借助计算机程序语言为链状存储结构。一般可以用指针来实现，通常可借助计算机程序语言的指针类型或者游标来来描述。的指针类型或者游标来来描述。第第一一章章 绪论绪论（3）索引存储方法：该方法通常是在存储结点信息的同时，建立）索引存储方法：该方法通常是在存储结点信息的同时，建立附加的索引表。索引表一般有稠密索引和稀疏索引两种。附加的索引表。索引表一般有稠密索引和稀疏索引两种。（4）散列存储方法：该方法是依据结点的关键字直接计算出该结）散列存储方法：该方法是依据结点的关键字直接计算出该结点的存储地址，而后将结点按某种方式存入该地址的一种存储方法。点的存储地址，而后将结点按某种方式存入该地址的一种存储方法。数据的运算是指定义在数据的逻辑结构上的一组操作的集合。例数据的运算是指定义在数据的逻辑结构上的一组操作的集合。例如，检索（查找）、插入、删除、定位、修改、排序等。要注意的是，如，检索（查找）、插入、删除、定位、修改、排序等。要注意的是，这些运算实际上是在逻辑结构上对抽象数据所施加的一系列抽象的操这些运算实际上是在逻辑结构上对抽象数据所施加的一系列抽象的操作，运算的实现依赖于所选取的存储结构，是依赖于不同的计算机程作，运算的实现依赖于所选取的存储结构，是依赖于不同的计算机程序设计语言的。序设计语言的。第第一一章章 绪论绪论数据类型是具有相同性质的计算机数据的集合及在这个数据集合上数据类型是具有相同性质的计算机数据的集合及在这个数据集合上的一组运算。的一组运算。在高级程序语言中，数据类型可以分为原子类型和结构类型。原子类在高级程序语言中，数据类型可以分为原子类型和结构类型。原子类型即值不可分解的类型，如型即值不可分解的类型，如C语言中的整型、字符型、实型、指针类型等；语言中的整型、字符型、实型、指针类型等；而结构类型则指的是其值可由若干成分按某种结构组成的类型，是可以分而结构类型则指的是其值可由若干成分按某种结构组成的类型，是可以分解的，如解的，如C语言中提供的结构体。语言中提供的结构体。抽象数据类型（抽象数据类型（ADT）是指一个数学模型及定义在该数学模型上的一）是指一个数学模型及定义在该数学模型上的一组操作。抽象数据模型的定义取决于它的一组逻辑特性，与其在计算机内组操作。抽象数据模型的定义取决于它的一组逻辑特性，与其在计算机内部如何表示和实现无关。部如何表示和实现无关。1.3数据类型和抽象数据类型数据类型和抽象数据类型第第一一章章 绪论绪论算法是对特定问题求解方法和步骤的一种描述，它是指令的一组有限算法是对特定问题求解方法和步骤的一种描述，它是指令的一组有限序列。一个算法必须具备以下五个重要特性：序列。一个算法必须具备以下五个重要特性：（1）输入：一个算法必须具有零个或多个的外界输入。）输入：一个算法必须具有零个或多个的外界输入。（2）输出：一个算法必须有一个或多个的输出。）输出：一个算法必须有一个或多个的输出。（3）有穷性：一个算法对任何合法的输入值必须总是在执行有穷步之后）有穷性：一个算法对任何合法的输入值必须总是在执行有穷步之后结束，并且每步都必须在有穷时间内完成。利用这一点，我们可以区别算结束，并且每步都必须在有穷时间内完成。利用这一点，我们可以区别算法与程序。法与程序。（4）确定性：算法中每一条指令必须有确切的含义，不会产生二义性。）确定性：算法中每一条指令必须有确切的含义，不会产生二义性。（5）可行性：算法中描述的操作都必须可以通过已经实现的基本运算有）可行性：算法中描述的操作都必须可以通过已经实现的基本运算有限次执行来实现，而且算法必须在有限时间内完成。限次执行来实现，而且算法必须在有限时间内完成。一个算法可以用自然语言、数学语言或约定的符号来描述，也可用计一个算法可以用自然语言、数学语言或约定的符号来描述，也可用计算机高级程序语言来描述，如算机高级程序语言来描述，如PASCAl语言、语言、C语言、语言、C、Java或伪代或伪代码等。本书选用码等。本书选用C语言作为描述算法的工具。语言作为描述算法的工具。1.4.1算法描述算法描述1.4算法描述与算法评价算法描述与算法评价第第一一章章 绪论绪论1.4.2算法的设计要求算法的设计要求设计一个好的算法可以从以下几个方面考虑：设计一个好的算法可以从以下几个方面考虑：（1）正确性。算法是为了针对解决具体问题而提出的，算法的正确与）正确性。算法是为了针对解决具体问题而提出的，算法的正确与否必须满足解决实际问题的需要，要经得起一切可能的输入数据的考验。否必须满足解决实际问题的需要，要经得起一切可能的输入数据的考验。（2）可读性。算法要让人阅读得懂，程序要尽可能地简单通俗，当然）可读性。算法要让人阅读得懂，程序要尽可能地简单通俗，当然也必须有效。也必须有效。（3）健壮性。当输入数据非法时，算法应能适当地作出反应或进行处）健壮性。当输入数据非法时，算法应能适当地作出反应或进行处理。理。（4）高效率。要求算法的执行时间要尽可能地短，对于存储空间要尽）高效率。要求算法的执行时间要尽可能地短，对于存储空间要尽可能地少，即做到既省时又节省空间。可能地少，即做到既省时又节省空间。要设计一个好的算法，必须对这几个方面综合考虑，才可以设计出较要设计一个好的算法，必须对这几个方面综合考虑，才可以设计出较好较优的算法。好较优的算法。第第一一章章 绪论绪论考虑算法的效率应从下几个方面考虑：考虑算法的效率应从下几个方面考虑：（1）时间效率。考虑算法所耗费的运行时间。）时间效率。考虑算法所耗费的运行时间。（2）空间效率。考虑运行算法需要耗费的存储空间，其中主要考虑算）空间效率。考虑运行算法需要耗费的存储空间，其中主要考虑算法所需的辅助存储空间。法所需的辅助存储空间。（3）算法应尽可能地简单，易于理解，易于编码和调试并能得出正确）算法应尽可能地简单，易于理解，易于编码和调试并能得出正确结果。结果。一个算法的运行时间是指一个算法在计算机上运行所耗费的时间。它一个算法的运行时间是指一个算法在计算机上运行所耗费的时间。它可以认为是算法中每条语句的执行时间之和。可以认为是算法中每条语句的执行时间之和。1.4.3算法的评价算法的评价第第一一章章 绪论绪论例如，两个例如，两个nn矩阵相乘的算法：矩阵相乘的算法：for（i=1；i=n；i+）/*n+1次次*/for（j=1；j=n；j+）/*n（n+1）次）次*/cij=0；/*nn次次*/for（k=1；k0时的线性表记为：（时的线性表记为：（a1，a2，ai，an）其中，其中，a1是第一个数据元素，又称为起始结点，是第一个数据元素，又称为起始结点，an是最后一个数据是最后一个数据元素，又称为终端结点。当元素，又称为终端结点。当i=1，2，n1时，时，ai有且仅有一个直接后有且仅有一个直接后继继ai+1；当；当i=2，3，n时，时，ai有且仅有一个直接前趋有且仅有一个直接前趋ai1。注意这里的。注意这里的ai（1in）仅仅是一个抽象的符号，其具体含义，在不同的情况下各）仅仅是一个抽象的符号，其具体含义，在不同的情况下各不相同，它可以是一个数，一条记录或一个符号，甚至是更复杂的信息。不相同，它可以是一个数，一条记录或一个符号，甚至是更复杂的信息。例如，英文字母表例如，英文字母表(A，B，Z)是一个线性表，职工工资表等。是一个线性表，职工工资表等。线性表的结点之间的逻辑关系符合线性结构的逻辑特征，是一种线线性表的结点之间的逻辑关系符合线性结构的逻辑特征，是一种线性结构。性结构。2.1.1线性表的逻辑结构线性表的逻辑结构2.1线性表的基本概念线性表的基本概念第二章第二章 线性表线性表常见的线性表的基本运算：常见的线性表的基本运算：（1）置空表）置空表SETNULL(L)：将线性表：将线性表L置成空表。置成空表。（2）求长度）求长度LENGTH(L)：求给定线性表：求给定线性表L中数据元素的个数。中数据元素的个数。（3）取元素）取元素GET(L,i)：结果是线性表：结果是线性表L中的第中的第i个数据元素。个数据元素。（4）定位函数）定位函数LOCATE(L,x)：当线性表中存在一个值为：当线性表中存在一个值为x的数据元的数据元素，则结果是该数据元素在表中的位序，否则，表示值为素，则结果是该数据元素在表中的位序，否则，表示值为x的数据元素的数据元素不存在。不存在。（5）前趋函数）前趋函数PRIOR(L,x)：若：若x为线性表中的一个数据元素，且为线性表中的一个数据元素，且其位序大于其位序大于1，则结果为，则结果为L的直接前趋，否则，给出一个特殊值示出该的直接前趋，否则，给出一个特殊值示出该元素没有直接前趋。元素没有直接前趋。（6）后继函数）后继函数NEXT（L，x）：若）：若x的位序小于的位序小于LENGTH（L），），则结果为该元素的直接后继，否则，给出一个特殊值，示出则结果为该元素的直接后继，否则，给出一个特殊值，示出x无直接后无直接后继。继。2.1.2线性表的运算线性表的运算第二章第二章 线性表线性表（7）插入）插入INSERT(L,x,i)：函数功能为在线性表：函数功能为在线性表L中的第中的第i个位置上插入个位置上插入一个值为一个值为x的新元素，使运算前长度为的新元素，使运算前长度为n的线性表变为长度为的线性表变为长度为n+1的线性表。的线性表。（8）删除）删除DELETE(L,i)：函数功能为删除线性表：函数功能为删除线性表L中的第中的第i个数据元素，个数据元素，使在此之前长度为使在此之前长度为n的线性表的线性表L变成长度为变成长度为n1的线性表。的线性表。利用基本运算可以实现线性表的其它复杂运算。利用基本运算可以实现线性表的其它复杂运算。需要指出的是，这里给出的只是定义在逻辑结构上的抽象运算，即只关需要指出的是，这里给出的只是定义在逻辑结构上的抽象运算，即只关心这些运算是心这些运算是“做什么做什么”的，至于的，至于“怎样实现怎样实现”则依赖于所选定的存储结构。则依赖于所选定的存储结构。第二章第二章 线性表线性表顺序表是线性表的顺序存储结构，即按顺序存储方式构成的线性表的顺序表是线性表的顺序存储结构，即按顺序存储方式构成的线性表的存储结构。其存储方式是：线性表的第一个元素存放在个一片连续的存储存储结构。其存储方式是：线性表的第一个元素存放在个一片连续的存储空间开始位置处，第二个元素紧跟着存放在第一元素之后空间开始位置处，第二个元素紧跟着存放在第一元素之后，以此类推。，以此类推。利用顺序表来存储线性表，可借助数据元素在计算机内的物理位置相利用顺序表来存储线性表，可借助数据元素在计算机内的物理位置相邻特性来表示线性表中数据元素之间的线性逻辑关系。邻特性来表示线性表中数据元素之间的线性逻辑关系。设线性表每个元素占设线性表每个元素占c个存储单元，若以第一个数据元素在存储单元个存储单元，若以第一个数据元素在存储单元中的存储地址作为起始地址，则可得出线性表中第中的存储地址作为起始地址，则可得出线性表中第i个数据元素的地址为：个数据元素的地址为：LOC(ai)=LOC(a1)+(i1)*c（1iLENGTH(L)）这样，一旦起始地址这样，一旦起始地址LOC（a1）（图（图2.1中设为中设为b）和一个数据元素占）和一个数据元素占用的存储单元的大小（用的存储单元的大小（c值）确定下来，就可求出任一个数据元素的存储值）确定下来，就可求出任一个数据元素的存储地址，显然，这种表便于进行随机访问，因此，顺序表是一种随机存取的地址，显然，这种表便于进行随机访问，因此，顺序表是一种随机存取的结构。结构。2.2.1顺序表顺序表2.2 线性表的顺序存储线性表的顺序存储第二章第二章 线性表线性表第二章第二章 线性表线性表在具体实现时，可利用高级程序设计语言中的一维数组即向量来为在具体实现时，可利用高级程序设计语言中的一维数组即向量来为线性表的顺序存储开辟存储空间，存储空间大小应大于等于线性表长度，线性表的顺序存储开辟存储空间，存储空间大小应大于等于线性表长度，用一个整型变量来表示线性表的长度，从而可将顺序表描述为：用一个整型变量来表示线性表的长度，从而可将顺序表描述为：#defineMAXSIZE999typedefintelemtype；/*elemtype表示元素类型，此处设为表示元素类型，此处设为int*/typedefstructelemtypevecMAXSIZE；intlen；sequenlist；在上面描述中，顺序表是一个结构体类型。其中，在上面描述中，顺序表是一个结构体类型。其中，vec成员（又称成员（又称为数据域）指线性表数据元素所占用的存储空间，而为数据域）指线性表数据元素所占用的存储空间，而len成员（又称为长成员（又称为长度域）则用于存储线性表长度，它表示线性表最后一个元素在向量中的度域）则用于存储线性表长度，它表示线性表最后一个元素在向量中的位置，位置，elemtype则为线性表中数据元素类型。则为线性表中数据元素类型。第二章第二章 线性表线性表 本节讨论在定义线性表顺序存储结构之后，如何在这种结构上实本节讨论在定义线性表顺序存储结构之后，如何在这种结构上实 现有关数据运算。下面重点讨论线性表的数据元素的插入和删除运算。现有关数据运算。下面重点讨论线性表的数据元素的插入和删除运算。1插入运算插入运算 线性表的插入运算是指在表的第线性表的插入运算是指在表的第i个元素之前插入一个新的数据元素，个元素之前插入一个新的数据元素，插入的结果使得线性表的长度由插入的结果使得线性表的长度由n变为变为n+1，线性表的数据元素间的逻辑，线性表的数据元素间的逻辑关系发生了变化，使得物理存储顺序也发生相应的变化。插入过程如图关系发生了变化，使得物理存储顺序也发生相应的变化。插入过程如图2.2所示。所示。2.2.2顺序表上的基本运算顺序表上的基本运算第二章第二章 线性表线性表第二章第二章 线性表线性表具体算法描述如下：具体算法描述如下：intinsert(sequenlist*L，inti，elemtypex)intj；if(*L).len)=MAXSIZE1)printf(“thelistisoverflow!n”)；/*溢出判断溢出判断*/return（0）；）；elseif(i(*L).len+1)printf(“positionisnotcorrect!n”)；return（0）；）；/*插入位置不正确插入位置不正确*/第二章第二章 线性表线性表 elsefor(j=(*L).len；j=i1；j)/*后移元素后移元素*/(*L).vecj+1=(*L).vecj；(*L).veci1=x；/*插入新元素插入新元素x*/(*L).len=(*L).len+1；/*修改表长修改表长*/return(1);/*insert*/在本算法中是从最后一个元素开始后移，直到第在本算法中是从最后一个元素开始后移，直到第i个元素为止。该算法时个元素为止。该算法时间主要花费在间主要花费在for循环语句上，执行的次数为循环语句上，执行的次数为ni+1。当。当i=1时，全部元素均参时，全部元素均参加移动，共需要移动加移动，共需要移动n次；当次；当i=n+1时，不需移动元素。时，不需移动元素。算法在最坏情况下，时间复杂度为算法在最坏情况下，时间复杂度为O(n)，最好情况下时间复杂度为，最好情况下时间复杂度为O(1)。显然，元素移动的次数直接影响了算法执行时间。显然，元素移动的次数直接影响了算法执行时间。第二章第二章 线性表线性表平均移动次数。平均移动次数。假设假设pi为在第为在第i个元素之前插入一个元素的概率，且为等概率，则平均个元素之前插入一个元素的概率，且为等概率，则平均移动次数的期望值为：移动次数的期望值为：其中，当其中，当1in+1时，时，p1=p2=pn+1=可见，在顺序存储的线性表中插入一个元素，约平均移动线性表中一可见，在顺序存储的线性表中插入一个元素，约平均移动线性表中一半的元素，显然，当半的元素，显然，当n较大时，算法效率较低，算法的平均时间复杂度为较大时，算法效率较低，算法的平均时间复杂度为O(n)。2删除运算删除运算删除运算是指将线性表中的第删除运算是指将线性表中的第i个元素删除，使线性表的长度由个元素删除，使线性表的长度由n变成变成n1，由：，由：(a1，a2，ai1，ai，ai+1，an)变成为：变成为：(a1，a2，ai1，ai+1，an)其中，其中，1in。线性表进行删除元素后，仍是一个线性表。删除过程如图线性表进行删除元素后，仍是一个线性表。删除过程如图2.3所示。所示。第二章第二章 线性表线性表第二章第二章 线性表线性表具体算法如下：具体算法如下：voiddelete(L，i)sequenlist*L；inti；intj；if(i(*L).len+1)printf(“deletefail！n”)；/*删除位置不正确删除位置不正确*/else*y=(*L).veci1；/*y为一外部变量，用于接收被删除的元素为一外部变量，用于接收被删除的元素*/for(j=i；j=(*L).len；j+)(*L).vecj1=(*L).vecj；/*元素前移元素前移*/(*L).Len；/*修改表长修改表长*/*delete*/第二章第二章 线性表线性表 与插入算法相似，要删除一个元素需向前移动元素，与插入算法相似，要删除一个元素需向前移动元素，删除第删除第i个元素时，个元素时，将第将第i+1，i+2，n个元素依次前移，其移动次数为个元素依次前移，其移动次数为ni，假设删除线性，假设删除线性表中的任一位置上元素的概率相等（等于表中的任一位置上元素的概率相等（等于1/n），则删除运算所需的移动），则删除运算所需的移动元素的平均移动次数如下所示。元素的平均移动次数如下所示。由此可见，对线性表删除一个元素时，约需有一半的元素参加移动。由此可见，对线性表删除一个元素时，约需有一半的元素参加移动。显然，该算法的时间复杂度为显然，该算法的时间复杂度为(n)。通过以上讨论可以发现，当表长较大时，对顺序存储结构进行插入和通过以上讨论可以发现，当表长较大时，对顺序存储结构进行插入和删除运算，由于要移动元素，运算效率低，但这种存储结构对于随机存取删除运算，由于要移动元素，运算效率低，但这种存储结构对于随机存取元素却十分方便。元素却十分方便。第二章第二章 线性表线性表例如，一个线性表中可能含有重复的元素（值相同），现要求删除重复例如，一个线性表中可能含有重复的元素（值相同），现要求删除重复元素中的多余元素，只保留其中位序最小的一个。如线性表（元素中的多余元素，只保留其中位序最小的一个。如线性表（5，2，2，3，5，2），经过清除重复元素后变为），经过清除重复元素后变为(5，2，3)。假定线性表以顺序存储方式存储，则其算法可描述如下：假定线性表以顺序存储方式存储，则其算法可描述如下：voidpurge(sequenlist*L)inti=0，j，k；while(i=(*L).Len1)j=i+1；while(j=(*L).Len1)if(*L).veci=(*L).vecj)for(k=j；knext=NULL；/*生成头结点生成头结点*/r=p；/*建立单链表表尾指针建立单链表表尾指针*/ch=getchar()；/*ch为建立与否标志为建立与否标志*/while(ch!=?)/*?为输入结束标志符为输入结束标志符*/scanf(“%d”,&x)；/*读入新数据元素读入新数据元素*/p=（linklist*）malloc(sizeof(linklist)；pdata=x;pnext=NULL；/*生成新结点生成新结点*/rnext=p；/*连接新结点连接新结点*/r=rnext；/*修改尾指针修改尾指针*/ch=getchar()；/*读入建立与否的标志读入建立与否的标志*/return(head)；/*返回表头指针返回表头指针head*/*creatlist*/第二章第二章 线性表线性表（2）建立不带头结点的单链表）建立不带头结点的单链表linklist*creatlist()/*函数返回一个指向链表表头的指针函数返回一个指向链表表头的指针*/charch；intx；linklist*head，*p，*rhead=NULL；r=NULL；/*设立尾指针设立尾指针r，其初值为空，其初值为空*/ch=getchar()；/*读入建立与否标志读入建立与否标志*/while(ch!=?)/*?为输入结束标志符为输入结束标志符*/p=(linklist*)malloc(sizeof(linklist)；/*申请新结点空间申请新结点空间*/scanf(“%d”，&x)；pdata=x;if(head=NULL)head=p；elsernext=p；/*非空表，则新结点非空表，则新结点*p插入到插入到*r之后之后*/r=p；/*尾指针移动，指向新的表尾尾指针移动，指向新的表尾*/ch=getchar()；/*读入建立与否的标志读入建立与否的标志*/if(r!=NULL)rnext=NULL；returnhead；/*返回表头指针返回表头指针head*/*creatlist*/在算法中引入头结点可以不必区分空表与非空表，可以统一空链表在算法中引入头结点可以不必区分空表与非空表，可以统一空链表与非空链表的处理。与非空链表的处理。上述两个算法的时间复杂度都为上述两个算法的时间复杂度都为O(n)。第二章第二章 线性表线性表2.单链表上元素的检索单链表上元素的检索一般情况下，可以按某个元素的序号或按某给定值两种方法检索。一般情况下，可以按某个元素的序号或按某给定值两种方法检索。（1）按值检索）按值检索按值检索，即是检索单链表中是否存在值为给定值按值检索，即是检索单链表中是否存在值为给定值k的结点，整个过的结点，整个过程可以通过结点的值和给定值的比较而实现。程可以通过结点的值和给定值的比较而实现。linklist*locate（linklist*head，elemtypek）linklist*s；s=headnext；/*从第一个结点起开始比较从第一个结点起开始比较*/while(s!=NULL)/*扫描整个链表扫描整个链表*/if(sdata!=k)s=snext；elsebreak；returns；/*返回结点的位置或返回结点的位置或NULL*/*Locate*/算法时间复杂度为算法时间复杂度为O(n)。第二章第二章 线性表线性表（2）按序号检索按序号检索即利用被访问结点的序号而检索或查找结点的过程。即利用被访问结点的序号而检索或查找结点的过程。linklist*get(linklist*head，inti)intj；linklist*p；p=head；j=0；while(pnext!=NULL)&(ij)p=pnext；j+；if(i=j)returnp；elsereturnNULL；/*get*/该算法中最坏情况下的时间复杂度为该算法中最坏情况下的时间复杂度为O(n)。第二章第二章 线性表线性表3单链表上元素的插入和删除运算单链表上元素的插入和删除运算插入结点的指针变化图插入结点的指针变化图2.8所示。指针的修改操作为：所示。指针的修改操作为：snext=pnext；pnext=s；上述指针进行相互赋值的语句顺序不能颠倒，上述指针进行相互赋值的语句顺序不能颠倒，若次序变化为：若次序变化为：pnext=s；snext=pnext；则会导致错误。；则会导致错误。同样，要删除单链表结点同样，要删除单链表结点*p的后继结点也很简单，只要用一个指针指的后继结点也很简单，只要用一个指针指向被删除结点，修改向被删除结点，修改*p的指针域，最后释放结点的指针域，最后释放结点*p即可，如图即可，如图2.9所示。所示。删删除一个结点除一个结点*p的后继结点的指针操作为：的后继结点的指针操作为：pnext=pnextnext；不难发现，不难发现，在单链表存储结构中进行元素的插入和删除时，只需要修在单链表存储结构中进行元素的插入和删除时，只需要修改有关的指针内容，而不需要移动元素。改有关的指针内容，而不需要移动元素。第二章第二章 线性表线性表第二章第二章 线性表线性表（1）插入算法插入算法（a）insert(linklist*p,elemtypex)/*将值为将值为x的新结点插入的新结点插入*p之后之后*/linklist*s；s=（linklist*）malloc(sizeof(linklist)；/*生成生成x的新结点的新结点*s*/sdata=x；snext=pnext；/*新结点链入单链表新结点链入单链表*/pnext=s；/*insert*/第二章第二章 线性表线性表（b）voidinsert(linklist*head,elemtypek,elemtypex)/*在单链表中值为在单链表中值为k的结点之前插入一个值为的结点之前插入一个值为x的新结点的新结点*/linklist*q，*p，*r；r=(linklist*)malloc(sizeof(linklist)；/*生成新结点生成新结点*/rdata=x；if(headnext=NULL)headnext=r；rnext=NULL；elseq=headnext；p=headnextnext；while(p!=NULL)if(pdata!=k)*/q=p；p=pnext；elsebreak；第二章第二章 线性表线性表if(p!=NULL)qnext=r；rnext=p；else/*在链表表尾处插入新结点在链表表尾处插入新结点*/qnext=r；rnext=NULL；/*insert*/该算法的时间主要耗费在查找值为该算法的时间主要耗费在查找值为k的结点位置上，算法时间复杂的结点位置上，算法时间复杂度为度为O(n)。第二章第二章 线性表线性表（2）删除算法）删除算法（a）delete(linklist*p)/*删除删除*p结点的后继结点结点的后继结点*/linklist*r；r=pnext；if(r!=NULL)pnext=rnext；free(r)；/*delete*/（b）linklist*delete(linklist*head，inti)/*删除单链表删除单链表head的第的第i个结点个结点*/intj=0；linklist*p，*s，*q；p=head；j=0；while(pnext!=NULL)&(jnext；j+；第二章第二章 线性表线性表if(pnext!=NULL)q=pnext；pnext=pnextnext；free(q)；elseret