.清华大学_严蔚敏

算法与数据结构严蔚敏， 教材：《数据结构(C语言版)》。严蔚敏，吴伟民 编 教材： 著。清华大学出版社。 清华大学出版社。
参考文献： 参考文献：数据结构》 张选平， 1 《数据结构》 。张选平，雷咏梅 编， 严蔚敏 审。 机械工业出版社。 机械工业出版社。 数据结构与算法分析》 2 《数据结构与算法分析》。Clifford A. Shaffer著， 电子工业出版社。 张 铭，刘晓丹 译。电子工业出版社。 李春葆。 3 《数据结构习题与解析(C语实言版)》。李春葆。 清华大学出版社。 清华大学出版社。 数据结构与算法》 编著。 4 《数据结构与算法》。夏克俭 编著。国防工业出 版社。 版社。
第1章
绪 论
目前，计算机已深入到社会生活的各个领域， 目前，计算机已深入到社会生活的各个领域，其应 用已不再仅仅局限于科学计算，而更多的是用于控制， 用已不再仅仅局限于科学计算，而更多的是用于控制， 管理及数据处理等非数值计算领域。 管理及数据处理等非数值计算领域。计算机是一门研究 用计算机进行信息表示和处理的科学。 用计算机进行信息表示和处理的科学。这里面涉及到两 个问题：信息的表示 信息的处理 表示， 处理。 个问题：信息的表示，信息的处理。 信息的表示和组织又直接关系到处理信息的程序的 效率。随着应用问题的不断复杂， 效率。随着应用问题的不断复杂，导致信息量剧增与信 息范围的拓宽，使许多系统程序和应用程序的规模很大， 息范围的拓宽，使许多系统程序和应用程序的规模很大， 结构又相当复杂。因此， 结构又相当复杂。因此，必须分析待处理问题中的对象 的特征及各对象之间存在的关系， 的特征及各对象之间存在的关系，这就是数据结构这门 课所要研究的问题。 课所要研究的问题。
计算机求解问题的一般步骤编写解决实际问题的程序的一般过程：– 如何用数据形式描述问题?—即由问题抽象出一个 如何用数据形式描述问题? 即由问题抽象出一个
适当的数学模型; 适当的数学模型; – 问题所涉及的数据量大小及数据之间的关系; 问题所涉及的数据量大小及数据之间的关系; – 如何在计算机中存储数据及体现数据之间的关系? 如何在计算机中存储数据及体现数据之间的关系? – 处理问题时需要对数据作何种运算? 处理问题时需要对数据作何种运算? – 所编写的程序的性能是否良好? 所编写的程序的性能是否良好? 上面所列举的问题基本上由数据结构这门课程来回答。 上面所列举的问题基本上由数据结构这门课程来回答。
1.1 数据结构及其概念算法与数据结构》 《算法与数据结构》是计算机

科学中的一门综合性 专业基础课。是介于数学、计算机硬件、 专业基础课。是介于数学、计算机硬件、计算机软件三 者之间的一门核心课程，不仅是一般程序设计的基础， 者之间的一门核心课程，不仅是一般程序设计的基础， 而且是设计和实现编译程序、操作系统、 而且是设计和实现编译程序、操作系统、数据库系统及 其他系统程序和大型应用程序的重要基础。 其他系统程序和大型应用程序的重要基础。
1.1.1 数据结构的例子例1：电话号码查询系统 ：设有一个电话号码薄，它记录了 个人的名字和其 设有一个电话号码薄，它记录了N个人的名字和其 相应的电话号码，假定按如下形式安排： 相应的电话号码，假定按如下形式安排：(a1, b1)，(a2, ， b2)，…(an, bn)，其中ai, bi(i=1，2…n) 分别表示某人的 ， ，其中 ， 名字和电话号码。 本问题是一种典型的表格问题。 名字和电话号码。 本问题是一种典型的表格问题。如 线性关系。 表1-1，数据与数据成简单的一对一的线性关系。 ，数据与数据成简单的一对一的线性关系姓名 陈海 李四锋 。。。 电话号码 136******** 130******** 。。。
表1-1 线性表结构
例2：磁盘目录文件系统磁盘根目录下有很多子目录 及文件， 及文件，每个子目录里又可以包 含多个子目录及文件， 含多个子目录及文件，但每个子 目录只有一个父目录，依此类推： 目录只有一个父目录，依此类推： 本问题是一种典型的树型结 构问题，如图1 构问题，如图1-1 ，数据与数据 成一对多的关系， 成一对多的关系，是一种典型的 非线性关系结构—树形结构 树形结构。 非线性关系结构 树形结构。
图 1-1
树形结构 树形结构
例3：交通网络图从一个地方到另外一个地方可以有多条路径。 从一个地方到另外一个地方可以有多条路径。本问 题是一种典型的网状结构问题， 网状结构问题 题是一种典型的网状结构问题，数据与数据成多对多的 关系，是一种非线性关系结构。 关系，是一种非线性关系结构。广州 佛山 惠州 东莞 中山
深圳 珠海 图1-2 网状结构
1.1.2 基本概念和术语数据(Data) 是客观事物的符号表示。 数据(Data) ：是客观事物的符号表示。在计算机科 学中指的是所有能输入到计算机中并被计算机程序处理 的符号的总称。 的符号的总称。 数据元素( Element) 是数据的基本单位， 数据元素(Data Element) ：是数据的基本单位，在 程序中通常作为一个整体来进行考虑和处理。 作为一个整体来进行考虑和处理 程序中通常作为一个整体来进行考虑和处理。 一个数据元素可由若干个数据项( Item)组成。 一个数据元素可由若干个数据

项(Data Item)组成。 数据项 数据项是数据的不可分割的最小单位。数据项是对客观 数据项是数据的不可分割的最小单位。 事物某一方面特性的数据描述。 事物某一方面特性的数据描述。 数据对象( Object) 数据对象(Data Object)：是性质相同的数据元素的 集合，是数据的一个子集。 集合，是数据的一个子集。如字符集合 C={‘A , B , C, C,…} C={ A’,’B’,’C, } 。
数据结构(Data Structure)：是指相互之间具有 存在 数据结构 ：是指相互之间具有(存在 )一定联系 关系 的数据元素的集合。元素之间的相互联 一定联系(关系 的数据元素的集合。 一定联系 关系)的数据元素的集合 系(关系 称为逻辑结构。数据元素之间的逻辑结构有四 关系)称为逻辑结构。 关系 称为逻辑结构 种基本类型，如图1-3所示 所示。 种基本类型，如图 所示。 集合：结构中的数据元素除了“同属于一个集合” ① 集合：结构中的数据元素除了“同属于一个集合” 没有其它关系。 外，没有其它关系。 ② 线性结构：结构中的数据元素之间存在一对一的 线性结构： 关系。 关系。 树型结构： ③ 树型结构：结构中的数据元素之间存在一对多的 关系。 关系。 图状结构或网状结构： ④ 图状结构或网状结构：结构中的数据元素之间存 在多对多的关系。 在多对多的关系。
图1-3
四类基本结构图 四类基本结构图
1.1.3 数据结构的形式定义数据结构的形式定义是一个二元组： 数据结构的形式定义是一个二元组： Data-Structure=(D，S) Data-Structure=(D， 其中： 是数据元素的有限集， 上关系的有限集。 其中：D是数据元素的有限集，S是D上关系的有限集。 例2：设数据逻辑结构B=（K，R） 设数据逻辑结构B=（ B=K={k1, k2, …, k9} , R={ ，，，，，，，，，， } 画出这逻辑结构的图示，并确定那些是起点， 画出这逻辑结构的图示，并确定那些是起点，那些是终点
数据元素之间的关系可以是元素之间代表某种含义 的自然关系， 的自然关系，也可以是为处理问题方便而人为定义的 关系，这种自然或人为定义的 关系” 关系，这种自然或人为定义的 “关系”称为数据元素 之间的逻辑关系 相应的结构称为逻辑结构 逻辑关系， 结构称为逻辑结构。 之间的逻辑关系，相应的结构称为逻辑结构。
1.1.4 数据结构的存储方式数据结构在计算机内存中的存储包括数据元素的 数据结构在计算机内存中的存储包括数据元素的 存储和元素之间的关系的表示。 存储和元素之间的关系的表示。 元素之间的关系在计算机中有两种不同的表示方法： 元素之间的关

系在计算机中有两种不同的表示方法： 顺序表示和非顺序表示。由此得出两种不同的存储结构： 顺序表示和非顺序表示。由此得出两种不同的存储结构： 顺序存储结构和链式存储结构。 顺序存储结构和链式存储结构。 – 顺序存储结构：用数据元素在存储器中的相对位 顺序存储结构： 置来表示数据元素之间的逻辑结构(关系) 置来表示数据元素之间的逻辑结构(关系)。
– 链式存储结构：在每一个数据元素中增加一个存 链式存储结构： 放另一个元素地址的指针(pointer )， 放另一个元素地址的指针(pointer )，用该指针来表 示数据元素之间的逻辑结构(关系) 示数据元素之间的逻辑结构(关系)。 设有数据集合A={3.0,2.3,5.0, A={3.0,2.3,5.0,例：设有数据集合A={3.0,2.3,5.0,-8.5,11.0} ，两种 不同的存储结构。 不同的存储结构。 – 顺序结构：数据元素存放的地址是连续的 顺序结构：数据元素存放的地址是连续的 地址是连续的； – 链式结构：数据元素存放的地址是否连续没有要 链式结构：数据元素存放的地址是否连续没有要 求。 数据的逻辑结构和物理结构是密不可分的两个方面， 数据的逻辑结构和物理结构是密不可分的两个方面， 一个算法的设计取决于所选定的逻辑结构 算法的设计取决于所选定的逻辑结构， 一个算法的设计取决于所选定的逻辑结构，而算法的实 现依赖于所采用的存储结构。 所采用的存储结构 现依赖于所采用的存储结构。 语言中， 一维数组表示顺序存储结构 表示顺序存储结构； 在C语言中，用一维数组表示顺序存储结构；用结 构体类型表示链式存储结构 表示链式存储结构。 构体类型表示链式存储结构。
数据结构的三个组成部分： 数据结构的三个组成部分： 逻辑结构： 逻辑结构 数据元素之间逻辑关系的描述D_S=（D，S） （ ， ）
存储结构： 存储结构 数据元素在计算机中的存储及其逻辑关系的表现称为数据的存储结构或物理结构。 关系的表现称为数据的存储结构或物理结构。
数据操作： 对数据要进行的运算。 数据操作 对数据要进行的运算。本课程中将要讨论的三种逻辑结构及其采用的存储 结构如图1-4所示 所示。 结构如图 所示。
逻辑结构线性表 树 图图1-4
物理结构顺序存储结构 链式存储结构 复合存储结构逻辑结构与所采用的存储结构
数据的逻辑结构
线性结构
非线性结构
受限线性表
线性表推广
集合
树形结构
图状结构
一般线性表
栈和队列 串
数组
广义表
一般树
二叉树
有向图
无向图
图1-5
数据逻辑结构层次关系图
1.1.5 数据类型数据类型( Type) 指的是一个值的集合 一个值的集合和定 数据

类型(Data Type)：指的是一个值的集合和定 义在该值集上的一组操作的总称。 该值集上的一组操作的总称 义在该值集上的一组操作的总称。 数据类型是和数据结构密切相关的一个概念。 数据类型是和数据结构密切相关的一个概念。 在C 语言中数据类型有：基本类型和构造类型。 语言中数据类型有：基本类型和构造类型。 数据结构不同于数据类型，也不同于数据对象，它 数据结构不同于数据类型，也不同于数据对象， 不仅要描述数据类型的数据对象，而且要描述数据对象 不仅要描述数据类型的数据对象， 各元素之间的相互关系。 各元素之间的相互关系。
1.1.6 数据结构的运算数据结构的主要运算包括： 数据结构的主要运算包括： 建立(Create)一个数据结构； (Create)一个数据结构 ⑴ 建立(Create)一个数据结构； 消除(Destroy)一个数据结构； (Destroy)一个数据结构 ⑵ 消除(Destroy)一个数据结构； 从一个数据结构中删除(Delete)一个数据元素； (Delete)一个数据元素 ⑶ 从一个数据结构中删除(Delete)一个数据元素； 把一个数据元素插入(Insert)到一个数据结构中； (Insert)到一个数据结构中 ⑷ 把一个数据元素插入(Insert)到一个数据结构中； 对一个数据结构进行访问(Access) (Access)； ⑸ 对一个数据结构进行访问(Access)； 对一个数据结构(中的数据元素) ⑹ 对一个数据结构(中的数据元素)进行修改 (Modify)； (Modify)； 对一个数据结构进行排序(Sort) (Sort)； ⑺ 对一个数据结构进行排序(Sort)； 对一个数据结构进行查找(Search) (Search)。 ⑻ 对一个数据结构进行查找(Search)。
1.2 抽象数据类型抽象数据类型( 简称ADT ADT) 抽象数据类型(Abstract Data Type ，简称ADT)： 是指一个数学模型以及定义在该模型上的一组操作。 是指一个数学模型以及定义在该模型上的一组操作。 ADT的定义仅是一组逻辑特性描述， ADT的定义仅是一组逻辑特性描述， 与其在计算 的定义仅是一组逻辑特性描述 机内的表示和实现无关。因此，不论ADT ADT的内部结构如 机内的表示和实现无关。因此，不论ADT的内部结构如 何变化，只要其数学特性不变，都不影响其外部使用。 何变化，只要其数学特性不变，都不影响其外部使用。 ADT的形式化定义是三元组：ADT=(D， ADT的形式化定义是三元组：ADT=(D，S，P) 的形式化定义是三元组 其中： 其中：D是数据对象，S是D上的关系集，P是对D的基 数据对象， 上的关系集， 是对D 关系集 本操作集。 本操作集。
ADT的一般定义形式是： ADT的一般定义形式是： 的一般定义形式是 <抽象数据类型名 抽象数据类型名>{ ADT <抽象数据类型名>{ 数据对象： 数据对象的定义> 数据对象： <

数据对象的定义> 数据关系： <数据关系的定义> 数据关系： 数据关系的定义> 基本操作： 基本操作的定义> 基本操作： <基本操作的定义> } ADT <抽象数据类型名> <抽象数据类型名 抽象数据类型名> – 其中数据对象和数据关系的定义用伪码描述。 其中数据对象和数据关系的定义用伪码描述。 – 基本操作的定义是： 基本操作的定义是：<基本操作名>(<参数表>) 基本操作名>(<参数表>) >(<参数表 初始条件： 初始条件描述> 初始条件： <初始条件描述> 操作结果： 操作结果描述> 操作结果： <操作结果描述>
– 初始条件：描述操作执行之前数据结构和参数应 初始条件：
满足的条件;若不满足，则操作失败， 满足的条件 若不满足，则操作失败，返回相应的出 若不满足 错信息。 错信息。 – 操作结果：描述操作正常完成之后，数据结构的 操作结果：描述操作正常完成之后， 应返回的结果。 变化状况和 应返回的结果。
1.3 算法分析初步1.3.1 算法算法(Algorithm) 是对特定问题求解方法(步骤) 算法(Algorithm)：是对特定问题求解方法(步骤)的一种 描述，是指令的有限序列， 描述，是指令的有限序列，其中每一条指令表示一个或 多个操作。 多个操作。 算法具有以下五个特性 有穷性： ① 有穷性： 一个算法必须总是在执行有穷步之后结 且每一步都在有穷时间内完成。 束，且每一步都在有穷时间内完成。 确定性：算法中每一条指令必须有确切的含义。 ② 确定性：算法中每一条指令必须有确切的含义。 不存在二义性。且算法只有一个入口和一个出口。 不存在二义性。且算法只有一个入口和一个出口。 可行性： 一个算法是能行的。 ③ 可行性： 一个算法是能行的。即算法描述的操作 都可以通过已经实现的基本运算执行有限次来实现。 都可以通过已经实现的基本运算执行有限次来实现。
输入： 一个算法有零个或多个输入， ④ 输入： 一个算法有零个或多个输入，这些输入 取自于某个特定的对象集合。 取自于某个特定的对象集合。 输出： 一个算法有一个或多个输出， ⑤ 输出： 一个算法有一个或多个输出，这些输出 是同输入有着某些特定关系的量。 是同输入有着某些特定关系的量。 一个算法可以用多种方法描述，主要有： 一个算法可以用多种方法描述，主要有：使用自然 语言描述；使用形式语言描述；使用计算机程序设计语 语言描述；使用形式语言描述； 言描述。 言描述。 算法和程序是两个不同的概念。 算法和程序是两个不同的概念。一个计算机程序是 对一个算法使用某种程序设计语言的具体实现。 对一个算法使用某种程序设计语言

的具体实现。算法必 须可终止意味着不是所有的计算机程序都是算法。 须可终止意味着不是所有的计算机程序都是算法。 在本门课程的学习、作业练习、上机实践等环节， 在本门课程的学习、作业练习、上机实践等环节， 算法都用C语言来描述。在上机实践时， 算法都用C语言来描述。在上机实践时，为了检查算法 是否正确，应编写成完整的C语言程序。 是否正确，应编写成完整的C语言程序。
1.3.2 算法设计的要求评价一个好的算法有以下几个标准 正确性( ① 正确性(Correctness )： 算法应满足具体问题 的需求。 的需求。 可读性(Readability) ② 可读性(Readability)： 算法应容易供人阅读和 交流。可读性好的算法有助于对算法的理解和修改。 交流。可读性好的算法有助于对算法的理解和修改。 健壮性(Robustness) 算法应具有容错处理。 ③ 健壮性(Robustness)： 算法应具有容错处理。 当输入非法或错误数据时， 当输入非法或错误数据时，算法应能适当地作出反 应或进行处理，而不会产生莫名其妙的输出结果。 应或进行处理，而不会产生莫名其妙的输出结果。 通用性(Generality) ④ 通用性(Generality)： 算法应具有一般性 ，即 算法的处理结果对于一般的数据集合都成立。 算法的处理结果对于一般的数据集合都成立。
效率与存储量需求： ⑤ 效率与存储量需求： 效率指的是算法执行的时 间；存储量需求指算法执行过程中所需要的最大存 储空间。一般地，这两者与问题的规模有关。 储空间。一般地，这两者与问题的规模有关。
1.3.3 算法效率的度量算法执行时间需通过依据该算法编制的程序在计算 机上运行所消耗的时间来度量。其方法通常有两种： 机上运行所消耗的时间来度量。其方法通常有两种： 事后统计： 事后统计：计算机内部进行执行时间和实际占用空间的 统计。 统计。 问题：必须先运行依据算法编制的程序； 问题：必须先运行依据算法编制的程序；依赖软硬 件环境，容易掩盖算法本身的优劣；没有实际价值。 件环境，容易掩盖算法本身的优劣；没有实际价值。 事前分析：求出该算法的一个时间界限函数。 事前分析：求出该算法的一个时间界限函数。
与此相关的因素有： 与此相关的因素有： – 依据算法选用何种策略； 依据算法选用何种策略； – 问题的规模； 问题的规模； – 程序设计的语言； 程序设计的语言； – 编译程序所产生的机器代码的质量； 编译程序所产生的机器代码的质量； – 机器执行指令的速度； 机器执行指令的速度； 撇开软硬件等有关部门因素， 撇开软硬件等有关部门因素，可以认为一个特定算 运行

工作量”的大小，只依赖于问题的规模（ 法“运行工作量”的大小，只依赖于问题的规模（通 常用n表示），或者说， 是问题规模的函数。 ），或者说 常用n表示），或者说，它是问题规模的函数。
算法分析应用举例算法中基本操作重复执行的次数是问题规模n 算法中基本操作重复执行的次数是问题规模n的某 基本操作重复执行的次数是问题规模 个函数， T(n)=O(f(n))， 个函数，其时间量度记作 T(n)=O(f(n))，称作算法的 complexity) 渐近时间复杂度( 渐近时间复杂度(Asymptotic Time complexity)，简 时间复杂度。 称时间复杂度。 一般地，常用最深层循环内的语句中的原操作的执 一般地，常用最深层循环内的语句中的原操作的执 最深层循环内的语句中的原操作的 行频度(重复执行的次数)来表示。 行频度(重复执行的次数)来表示。 “O”的定义： 若f(n)是正整数n的一个函数，则 O(f(n)) 的定义： f(n)是正整数n的一个函数， 的定义 是正整数 表示? 使得当n 表示? M≥0 ，使得当n ≥ n0时，| f(n) | ≤ M | f(n0) | 。 表示时间复杂度的阶有： 时间复杂度的阶有 表示时间复杂度的阶有： O(1) ：常量时间阶 O(㏒ O(㏒n) ：对数时间阶 (n)： O (n)：线性时间阶 O(n㏒ O(n㏒n) ：线性对数时间阶
O (nk)： k≥2 ，k次方时间阶 两个n 例１ 两个n阶方阵的乘法 for(i=1， for(i=1，i<=n; ++i) for(j=1; j<=n; ++j) { c[i][j]=0 ; for(k=1; k<=n; ++k) c[i][j]+=a[i][k]*b[k][j] ; } 由于是一个三重循环，每个循环从1 由于是一个三重循环，每个循环从1到n，则总次数为： 则总次数为： 时间复杂度为T(n)=O(n n×n×n=n3 时间复杂度为T(n)=O(n3) 例２ {++x; s=0 ;} 将x自增看成是基本操作，则语句频度为１，即时 自增看成是基本操作，则语句频度为１ 间复杂度为Ｏ 间复杂度为Ｏ(1) 。
如果将s=0也看成是基本操作，则语句频度为２ 如果将s=0也看成是基本操作，则语句频度为２，其时 s=0也看成是基本操作 间复杂度仍为Ｏ(1)，即常量阶。 间复杂度仍为Ｏ(1)，即常量阶。 例３ for(i=1; i<=n; ++i) { ++x; s+=x ; } 语句频度为：2n，其时间复杂度为： 语句频度为：2n，其时间复杂度为：O(n) ，即为线性 阶。 例４ for(i=1; i<=n; ++i) for(j=1; j<=n; ++j) { ++x; s+=x ; } 语句频度为： 其时间复杂度为： 语句频度为：2n2 ，其时间复杂度为：O(n2) ，即为 平方阶。 平方阶。
定理： 定理：若A(n)=a m n m +a m-1 n m-1 +…+a1n+a0是一个 +am次多项式，则A(n)=O(n m) 次多项式， 例５ for(i=2;i<=n;++i) for(j=2;j<=ifor(j=2;j<=i-1;++j) {++x; a[i,j]=x; } 语句频度为： 1+2+3+…+n 2=(1+n+n(n语句频度为： 1+2+3+ +n-2=(1+n-2) ×(n-2)/2 =(n-1)(n=(n-1)(n-2)/2 =n2-3n+2 时间复杂度为O(n ∴时间复杂度为O(n2)，即此算法的时间复杂

度为平方 阶。 – 一个算法时间为O(1)的算法，它的基本运算执行 一个算法时间为O(1)的算法， O(1)的算法 的次数是固定的。因此，总的时间由一个常数（即 的次数是固定的。因此，总的时间由一个常数（ 零次多项式）来限界。而一个时间为O(n 零次多项式）来限界。而一个时间为O(n2)的算法则 由一个二次多项式来限界。 由一个二次多项式来限界。
以下六种计算算法时间的多项式是最常用的。 以下六种计算算法时间的多项式是最常用的。其 关系为： 关系为： O(1)素数的判断算法。 例1：素数的判断算法。 Void prime( int n)n是一个正整数 /* n是一个正整数 */
{ int i=2 ; while ( (n% i)!=0 && i*1.0< sqrt(n) ) i++ ; if (i*1.0>sqrt(n) ) printf(“&d 是一个素数\ printf( &d 是一个素数\n” , n) ; else printf(“&d 不是一个素数\ printf( &d 不是一个素数\n” , n) ; } 嵌套的最深层语句是i++ 其频度由条件( i++； 嵌套的最深层语句是i++；其频度由条件( (n% 决定，显然i*1.0< i)!=0 && i*1.0< sqrt(n) ) 决定，显然i*1.0< sqrt(n) ， 时间复杂度O(n 时间复杂度O(n1/2)。
冒泡排序法。 例2：冒泡排序法。 a[]， Void bubble_sort(int a[]，int n) { change=false; (i=n--i) for (i=n-1; change=TURE; i>1 && change; --i) for (j=0; ja[j+1]) ←→a[j+1] { a[j] ←→a[j+1] ; change=TURE ; } } – 最好情况：0次 最好情况： – 最坏情况：1+2+3+?+n-1=n(n-1)/2 最坏情况：1+2+3+?+n-1=n(n– 平均时间复杂度为： O(n2) 平均时间复杂度为：
1.3.4 算法的空间分析空间复杂度( complexity) 空间复杂度(Space complexity) ：是指算法编写 成程序后， 成程序后，在计算机中运行时所需存储空间大小的度 量。记作： S(n)=O(f(n)) 记作： 其中： 为问题的规模(或大小) 其中： n为问题的规模(或大小) 该存储空间一般包括三个方面： 该存储空间一般包括三个方面： – 指令常数变量所占用的存储空间; 指令常数变量所占用的存储空间; – 输入数据所占用的存储空间; 输入数据所占用的存储空间; – 辅助(存储)空间。 辅助(存储

)空间。 一般地，算法的空间复杂度指的是辅助空间 空间复杂度指的是辅助空间。 一般地，算法的空间复杂度指的是辅助空间。 – 一维数组a[n]： 空间复杂度 O(n) 一维数组a[n] a[n]： – 二维数组a[n][m]： 空间复杂度 O(n*m) 二维数组a[n][m] a[n][m]：
习题一简要回答术语：数据，数据元素，数据结构， 1 简要回答术语：数据，数据元素，数据结构，数据 类型。 类型。 数据的逻辑结构？数据的物理结构？ 2 数据的逻辑结构？数据的物理结构？逻辑结构与物 理结构的区别和联系是什么？ 理结构的区别和联系是什么？ 3 数据结构的主要运算包括哪些？ 数据结构的主要运算包括哪些？ 算法分析的目的是什么？ 4 算法分析的目的是什么？算法分析的主要方面是什 么？ 分析以下程序段的时间复杂度， 5 分析以下程序段的时间复杂度，请说明分析的理由 或原因。 或原因。
⑴Sum1( int n ) { int p=1, sum=0, m ; for (m=1; m<=n; m++) { p*=m ; sum+=p ; } return (sum) ; }
⑶ 递归函数fact( int n ) { if (n<=1) return(1) ; else return( n*fact(n-1)) ; }
⑵Sum2( int n ) { int sum=0, m, t ; for (m=1; m<=n; m++) { p=1 ; for (t=1; t<=m; t++) p*=t ; sum+=p ; } return (sum) ; }
第2章
线性表
线性结构是最常用、最简单的一种数据结构。 线性结构是最常用、最简单的一种数据结构。而线 性表是一种典型的线性结构。 性表是一种典型的线性结构。其基本特点是线性表中的 数据元素是有序且是有限的。在这种结构中： 数据元素是有序且是有限的。在这种结构中： 存在一个唯一的被称为“第一个”的数据元素； ① 存在一个唯一的被称为“第一个”的数据元素； 存在一个唯一的被称为“最后一个”的数据元素； ② 存在一个唯一的被称为“最后一个”的数据元素； 除第一个元素外， ③ 除第一个元素外，每个元素均有唯一一个直接前 驱； 除最后一个元素外， ④ 除最后一个元素外，每个元素均有唯一一个直接 后继。 后继。
2.1 线性表的逻辑结构2.1.1 线性表的定义线性表(Linear List) ：是由 ≧0)个数据元素 结 是由n(n≧ 个数据元素 个数据元素(结 线性表 组成的有限序列。 点)a1，a2， …an组成的有限序列。该序列中的所有结 点具有相同的数据类型。其中数据元素的个数n称为线 点具有相同的数据类型。其中数据元素的个数 称为线 性表的长度。 性表的长度。 当n=0时，称为空表。 时 称为空表。 当n>0时，将非空的线性表记作： (a1，a2，…an) 时 将非空的线性表记作： a1称为线性表的第一个(首)结点，an称为线性表的最后 称为线性表的第一个 第一个( 结点， 称为线性表的最后 一个( 结点。 一个(尾)结点。
a1，a2，…ai-1都是 i(

2≦i≦n)的前驱，其中 i-1是ai的直 都是a ≦ ≦ 的前驱，其中a 接前驱; 接前驱 ai+1，ai+2，…an都是 i(1≦i ≦n-1)的后继，其中 i+1是ai 都是a ≦ 的后继，其中a 直接后继。 的直接后继。
2.1.2 线性表的逻辑结构线性表中的数据元素a 线性表中的数据元素 i所代表的具体含义随具体应 用的不同而不同，在线性表的定义中， 用的不同而不同，在线性表的定义中，只不过是一个抽 象的表示符号。 象的表示符号。 线性表中的结点可以是单值元素 结点可以是单值元素(每个元素只有一 ◆ 线性表中的结点可以是单值元素 每个元素只有一 个数据项) 个数据项 。 例1: 26个英文字母组成的字母表： (A，B，C、…、Z） 个英文字母组成的字母表： ， ， 、 、 ） 个英文字母组成的字母表
例2 ： 某校从1978年到1983年各种型号的计算机拥 某校从1978年到 年到1983年各种型号的计算机拥 有量的变化情况：(6，17，28，50，92，188） 有量的变化情况：(6，17，28，50，92，188） 例3 ： 一副扑克的点数 A) (2， (2，3，4，…，J，Q，K，
◆ 线性表中的结点可以是记录型元素，每个元素 线性表中的结点可以是记录型元素， 结点可以是记录型元素 含有多个数据项 ，每个项称为结点的一个域 。每个 元素有一个可以唯一标识每个结点的数据项组 数据项组， 元素有一个可以唯一标识每个结点的数据项组，称 关键字。 为关键字。 例4 ： 某校2001级同学的基本情况： 某校2001级同学的基本情况 级同学的基本情况： {(‘2001414101’ {(‘2001414101’，‘张里户’，‘男’， 张里户’ 06/24/1983)， 2001414102’ 06/24/1983)， (‘2001414102’，‘张化司’， 张化司’ 2001414102’ ‘男’，08/12/1984) …， (‘2001414102’， 李利辣’ ‘李利辣’，‘女’，08/12/1984) } ◆ 若线性表中的结点是按值(或按关键字值)由小到 若线性表中的结点是按值 或按关键字值) 按值(
线性表是一种相当灵活的数据结构， ◆ 线性表是一种相当灵活的数据结构，其长度可根 据需要增长或缩短。 据需要增长或缩短。 对线性表的数据元素可以访问、插入和删除。 ◆ 对线性表的数据元素可以访问、插入和删除。
2.1.3 线性表的抽象数据类型定义ADT List{ 数据对象： 数据对象：D = { ai | ai∈ElemSet, i=1,2,…,n, n≧0 } ≧ 数据关系： 数据关系：R = { | ai-1, ai∈D, i=2,3,…,n } 基本操作： 基本操作： InitList( &L ) 操作结果：构造一个空的线性表 ； 操作结果：构造一个空的线性表L；
ListLength( L ) 初始条件：线性表L已存在 已存在； 初始条件：线性表 已存在； 操作结果： 为空表， 操作结果：若L为空表，则返回 为空表 则返回TRUE，否则返回 ， FAL

SE； ； …. GetElem( L, i, &e ) 初始条件：线性表L已存在，1≦i≦ListLength(L)； 初始条件：线性表 已存在， ≦ ≦ ； 已存在 操作结果： 返回 中第i个数据元素的值 返回L中第 个数据元素的值； 操作结果：用e返回 中第 个数据元素的值； ListInsert ( L, i, &e ) 初始条件：线性表L已存在 已存在， ≦ ≦ 初始条件：线性表 已存在，1≦i≦ListLength(L) ； 操作结果：在线性表L中的第 个位置插入元素e； 中的第i个位置插入元素 操作结果：在线性表 中的第 个位置插入元素 ； … } ADT List
2.2 线性表的顺序存储2.2.1 线性表的顺序存储结构把线性表的结点按逻辑顺序 按逻辑顺序依次存放 顺序存储 ：把线性表的结点按逻辑顺序依次存放 在一组地址连续的存储单元里 在一组地址连续的存储单元里。用这种方法存储的线性 表简称顺序表。 表简称顺序表。
顺序存储的线性表的特点： 顺序存储的线性表的特点： 的线性表的特点线性表的逻辑顺序与物理顺序一致; ◆ 线性表的逻辑顺序与物理顺序一致 数据元素之间的关系是以元素在计算机内“ ◆ 数据元素之间的关系是以元素在计算机内“物理 位置相邻”来体现。 位置相邻”来体现。 设有非空的线性表： 设有非空的线性表：(a1，a2，…an) 。顺序存储如图 2-1所示。 所示。 所示
Loc(a1) Loc(ai)+(i-1)* l
… a1 a2 … ai … an …图2-1 线性表的顺序存储表示
在具体的机器环境下： 在具体的机器环境下：设线性表的每个元素需占 个存储单元， 用l个存储单元，以所占的第一个单元的存储地址作为 数据元素的存储位置。则线性表中第i+1个数据元素的 数据元素的存储位置。则线性表中第i+1个数据元素的 存储位置LOC(a 和第i 存储位置LOC(ai+1)和第i个数据元素的存储位置 LOC(ai)之间满足下列关系： 之间满足下列关系： )+l LOC(ai+1)=LOC(ai)+l 线性表的第i个数据元素a 的存储位置为： 线性表的第i个数据元素ai的存储位置为： LOC(ai)=LOC(a1)+(i-1)*l )+(i-1)*l
在高级语言( 在高级语言(如C语言)环境下：数组具有随机存取 语言)环境下： 的特性，因此，借助数组来描述顺序表。 的特性，因此，借助数组来描述顺序表。除了用数组来 存储线性表的元素之外， 存储线性表的元素之外，顺序表还应该有表示线性表的 长度属性，所以用结构类型来定义顺序表类型。 长度属性，所以用结构类型来定义顺序表类型。 #define OK 1 #define ERROR -1 #define MAX_SIZE 100 typedef int Status ; typedef int ElemType ; typedef struct sqlist { ElemType Elem_array[MAX_SIZE] ; int length ; } SqList ;
2.2.2 顺序表的基本操作顺序存储结构中，很容易实现线性表的一些操作： 顺序存储结构中，很容易实现线

性表的一些操作： 初始化、赋值、查找、修改、插入、删除、求长度等。 初始化、赋值、查找、修改、插入、删除、求长度等。 以下将对几种主要的操作进行讨论。 以下将对几种主要的操作进行讨论。
1
顺序线性表初始化{ L->elem_array=( ElemType * L)malloc(MAX_SIZE*sizeof( ElemType ) ) ; if ( !L -> elem_array ) return ERROR ; else { } LL->length= 0 ; return OK ; }
Status Init_SqList( SqList *L )
2
顺序线性表的插入 顺序线性表的插入
在线性表 L= (a1，…a i-1，ai， ai+1，…，an) 的第i(1≦ n)个位置上插入一个新结点 个位置上插入一个新结点e 中的第i(1≦i≦n)个位置上插入一个新结点e，使其成 为线性表： 为线性表： L=(a1，…ai-1，e，ai，ai+1，…，an)
实现步骤(1) 将线性表L中的第i个至第n个结点后移一个位置。 将线性表L中的第 个至第n个结点后移一个位置。 (2) 将结点e插入到结点ai-1之后。 将结点e插入到结点a 之后。 (3) 线性表长度加1。 线性表长度加1
算法描述Status Insert_SqList(Sqlist *L，int i ， *L， ElemType e) { int j ; if ( i<0||i>L->length-1) return i<0||i>L->lengthERROR ; if (L->length>=MAX_SIZE) (L{ printf(“线性表溢出!\n”); return printf(“线性表溢出! ERROR ; } for ( j=L->length–1; j>=i-1; --j ) j=L->length– j>=i- --j L->Elem_array[j+1]=L>Elem_array[j+1]=L>Elem_array[j];/* i-1位置以后的所有结点后移 */ i-
L->Elem_array[i-1]=e; >Elem_array[i-
/* 在i-1位置插入
时间复杂度分析在线性表L中的第 元素之前插入新结点， 在线性表L中的第i个元素之前插入新结点，其时 间主要耗费在表中结点的移动操作上，因此， 间主要耗费在表中结点的移动操作上，因此，可用结点 的移动来估计算法的时间复杂度。 的移动来估计算法的时间复杂度。 设在线性表L中的第i个元素之前插入结点的概率 在线性表L中的第 不失一般性，设各个位置插入是等概率， 为Pi，不失一般性，设各个位置插入是等概率，则 Pi=1/(n+1)，而插入时移动结点的次数为n-i+1。 =1/(n+1)，而插入时移动结点的次数为n i+1。 总的平均移动次数： Einsert=∑pi*(n-i+1) *(n总的平均移动次数： (1≦ (1≦i≦n) ∴ Einsert=n/2 。 即在顺序表上做插入运算，平均要移动表上一半结 在顺序表上做插入运算， 当表长n较大时，算法的效率相当低。 点。当表长n较大时，算法的效率相当低。因此算法的 平均时间复杂度为O(n)。 平均时间复杂度为O(n)。
3
顺序线性表的删除
在线性表 L=(a1，…a i-1，ai， ai+1，…，an) 中删除结点a (1≦ n)，使其成为线性表： 中删除结点ai(1≦i≦n)，使其成为线性表： L= (a1，…ai-1，ai+1，…，an)
实现步骤(1) 将线性表L中的第i+1个至第n个结点依此向前 将线性表L中的第i+1个至第

个至第n 移动一个位置。 移动一个位置。 (2) 线性表长度减1。 线性表长度减1
算法描述ElemType Delete_SqList(Sqlist *L，int i) *L， { int k ; ElemType x ;
if (L->length==0) (L{ printf(“线性表L为空!\n”); return printf(“线性表L为空! ERROR; } else if ( i<1||i>L->length ) i<1||i>L{ printf(“要删除的数据元素不存在!\n”) ; printf(“要删除的数据元素不存在! return ERROR ; } else { x=L->Elem_array[i-1] ; /*保 x=L->Elem_array[i/*保存结点的值* 存结点的值*/
for ( k=i ; klength ; k++) kElem_array[k-1]=L>Elem_array[k-1]=L>Elem_array[k];/* i位置以后的所有结点前移 */ i位置以后的所有结点前移
L->length--; return (x); >length--; }
时间复杂度分析删除线性表L中的第 个元素， 删除线性表 中的第i个元素，其时间主要耗费在表 中的 中结点的移动操作上，因此， 中结点的移动操作上，因此，可用结点的移动来估计算 法的时间复杂度。 法的时间复杂度。 设在线性表L中删除第 个元素的概率为 i，不失 在线性表 中删除第i个元素的概率为P 一般性，设删除各个位置是等概率， 一般性，设删除各个位置是等概率，则Pi=1/n，而删除 ， 时移动结点的次数为n-i。 时移动结点的次数为 。 则总的平均移动次数： 则总的平均移动次数： Edelete=∑pi*(n-i) (1≦i≦n) ≦≦ ∴ Edelete=(n-1)/2 。 即在顺序表上做删除运算，平均要移动表上一半结 在顺序表上做删除运算， 当表长n较大时 算法的效率相当低。 较大时， 点。当表长 较大时，算法的效率相当低。因此算法的 平均时间复杂度为O(n)。 平均时间复杂度为 。
4
顺序线性表的查找定位删除
在线性表 L= (a1，a2，…，an) 中删除值为x的 中删除值为x 第一个结点。 第一个结点。
实现步骤(1) 在线性表L查找值为x的第一个数据元素。 在线性表L查找值为x的第一个数据元素 一个数据元素。 (2) 将从找到的位置至最后一个结点依次向前移动一 将从找到的位置至最后一个结点依次向前移动一 个位置。 个位置。 (3) 线性表长度减1。 线性表长度减1
算法描述Status Locate_Delete_SqList(Sqlist *L， *L， ElemType x)/* 删除线性表L中值为x的第一个结点 删除线性表L中值为x 一个结点 */
{ int i=0 , k ;
while (ilength) (i/*查找值为 /*查找值为x的第一 查找值为x
{
if (L->Elem_array[i]!=x ) i++ ; (Lelse { for ( k=i+1; k< L->length; Lk++) L->Elem_array[k-1]=L>Elem_array[k-1]=L>Elem_array[k]; L->length--; break ; >length--; }
} if (i>L->length) (i>L{ printf(“要删除的数据元素不存在!\n”) ; printf(“要删除的数据元素不存在! return ERROR ; }
时间复杂度分析时间主要耗费在数据元素的比较和移动操作上。 时间主要耗费在数据元素的比较和移动操作上

。 首先，在线性表 中查找值为 中查找值为x的结点是否存在; 首先，在线性表L中查找值为 的结点是否存在 其次， 值为x的结点存在，且在线性表 中的位置为i 线性表L中的位置为 其次，若值为 的结点存在，且在线性表 中的位置为 ， 则在线性表 中删除第 个元素。 线性表L中删除 则在线性表 中删除第i个元素。 删除数据元素概率为 设在线性表L删除数据元素概率为 i，不失一般性， 在线性表 删除数据元素概率为P 不失一般性， 设各个位置是等概率， 设各个位置是等概率，则Pi=1/n。 。 比较的平均次数： ◆ 比较的平均次数： Ecompare=∑pi*i ∴ Ecompare=(n+1)/2 。 删除时平均移动次数： ◆ 删除时平均移动次数：Edelete=∑pi*(n-i) (1≦i≦n) ≦≦ 平均时间复杂度： ∴ Edelete=(n-1)/2 。 平均时间复杂度：Ecompare+Edelete=n ， 即为O(n) 即为 (1≦i≦n) ≦≦
2.3 线性表的链式存储2.3.1 线性表的链式存储结构一组任意的存储单元存储线性表 链式存储 ：用一组任意的存储单元存储线性表 中的数据元素。用这种方法存储的线性表简称线性链 中的数据元素。用这种方法存储的线性表简称线性链 表。 存储链表中结点的一组任意的存储单元可以是连 续的，也可以是不连续的， 续的，也可以是不连续的，甚至是零散分布在内存中 的任意位置上的。 的任意位置上的。 链表中结点的逻辑顺序和物理顺序不一定相同。 链表中结点的逻辑顺序和物理顺序不一定相同。
为了正确表示结点间的逻辑关系，在存储每个结点 为了正确表示结点间的逻辑关系， 值的同时，还必须存储指示其直接后继结点的地址( 值的同时，还必须存储指示其直接后继结点的地址(或 位置) 称为指针(pointer)或链 或链(link)， 位置)，称为指针(pointer)或链(link)，这两部分组 成了链表中的结点结构，如图2 所示。 成了链表中的结点结构，如图2-2所示。 链表是通过每个结点的指针域将线性表的n 链表是通过每个结点的指针域将线性表的n个结点 按其逻辑次序链接在一起的。 按其逻辑次序链接在一起的。 每一个结只包含一个指针域的链表，称为单链表。 每一个结只包含一个指针域的链表，称为单链表。 为操作方便， 为操作方便，总是在链表的第一个结点之前附设一 个头结点(头指针)head指向第一个结点。 个头结点(头指针)head指向第一个结点。头结点的数 指向第一个结点 据域可以不存储任何信息(或链表长度等信息) 据域可以不存储任何信息(或链表长度等信息)。data next data ：数据域，存放结点的值。next ：指针 数据域，存放结点的值。 存放结点的直接后继的地址。 域，存放结点的直接后继的地址。图2-2 链

表结点结构
……
单链表是由表头唯一确定， 单链表是由表头唯一确定，因此单 链表可以用头指针的名字来命名。 链表可以用头指针的名字来命名。 例1、线性表L=(bat，cat，eat，fat， 线性表 ， ， ， ， hat) 其带头结点的单链表的逻辑状态和物理 带头结点的单链表的逻辑状态和物理 存储方式如图2-3所示 所示。 存储方式如图 所示。head
1100
hat NULL …… cat 1305 eat 3700 …… bat 1300
1300
1305
3695head bat图2-3
cat
eat
fat
hat ?
3700
fat 1100 ……
带头结点的单链表的逻辑状态、 带头结点的单链表的逻辑状态、物理存储方式
1 结点的描述与实现C语言中用带指针的结构体类型来描述 语言中用带指针的结构体类型来描述 语言中用带指针的结构体类型 typedef struct Lnode { ElemType data; }LNode;/*数据域，保存结点的值 */ 数据域， 数据域 /*指针域 指针域*/ 指针域
struct Lnode *next;/*结点的类型 */ 结点的类型
2 结点的实现结点是通过动态分配和释放来的实现， 结点是通过动态分配和释放来的实现，即需要时分 不需要时释放。实现时是分别使用C语言提供的标 配，不需要时释放。实现时是分别使用 语言提供的标 准函数： 准函数：malloc() ，realloc()，sizeof() ，free() 。 ，
动态分配 p=(LNode*)malloc(sizeof(LNode)); 函数malloc分配了一个类型为 函数malloc分配了一个类型为LNode的结点变量的空 分配了一个类型为LNode的结点变量的空 并将其首地址放入指针变量p 间，并将其首地址放入指针变量p中。 动态释放 free(p) ; 系统回收由指针变量p所指向的内存区。 系统回收由指针变量p所指向的内存区。P必须是最近一 次调用malloc函数时的返回值 函数时的返回值。 次调用malloc函数时的返回值。
3 最常用的基本操作及其示意图 ⑴ 结点的赋值LNode *p; p=(LNode*)malloc(sizeof(LNode)); p->data=20; p->next=NULL ;
p 20 NULL
⑵
常见的指针操作p q … p … a … 操作前 p a b 操作前 p a b 操作前 q a p c b … … a … 操作后 q p b …
① q=p ;
② q=p->next ; ③ p=p->next ; ④ q->next=p ; (a)
…
a
操作后 p … … a b 操作后 q a p b …
…
…
…
…
…
… 操作前
c … 操作后
q … a q … a b b
p … x 操作前 p … x y …
(b)
y q
…
⑤ q->next=p->next ; q (a)… p a b y x q 操作前 a q … a b b
操作后 … a b p … y x 操作后 p … y … … …
…
(b)
… x 操作前 p … x
y
…
操作后
2.3.2 单线性链式的基本操作1 建立单链表假设线性表中结点的数据类型是整型，以32767 假设线性表中结点的数据类型是整型， 作为结束标志。动态地建立单链表的常用方法有如下两 作为结束标志。 头插入法，尾插入法。 种：头插入法，尾插入法。
⑴ 头插入法

建表从一个空表开始，重复读入数据，生成新结点， 从一个空表开始，重复读入数据，生成新结点， 将读入数据存放到新结点的数据域中， 将读入数据存放到新结点的数据域中，然后将新结点插 入到当前链表的表头上，直到读入结束标志为止。 入到当前链表的表头上，直到读入结束标志为止。即每 次插入的结点都作为链表的第一个结点。 次插入的结点都作为链表的第一个结点。
算法描述LNode *create_LinkList(void)/* 头插入法创建单链表,链表的头结点head作为返回值 头插入法创建单链表,链表的头结点head作为返回值 */
{
int data ; LNode *head, *p; head= (LNode *) malloc( sizeof(LNode)); headhead->next=NULL; /* 创建链表的表头结点head */
while (1) { scanf(“%d”, &data) ; scanf(“%d” if (data==32767) break ; p= (LNode *)malloc(sizeof(LNode));
p–>next=head–>next ; head– >next=head– head– >next=p ;/* 钩链，新创建的结点总是作为第一个结点 钩链，新创建的结点总是作为第一个结点 */
} return (head); }
(2)
尾插入法建表
头插入法建立链表虽然算法简单，但生成的链表 头插入法建立链表虽然算法简单， 中结点的次序和输入的顺序相反。若希望二者次序一致， 中结点的次序和输入的顺序相反。若希望二者次序一致， 可采用尾插法建表。该方法是将新结点插入到当前链表 可采用尾插法建表。该方法是将新结点插入到当前链表 的表尾，使其成为当前链表的尾结点。 的表尾，使其成为当前链表的尾结点。
算法描述LNode *create_LinkList(void)/* 尾插入法创建单链表,链表的头结点head作为返回值 尾插入法创建单链表,链表的头结点head作为返回值
*/ {
int data ; LNode *head, *p, *q; head=p=(LNode *)malloc(sizeof(LNode)); p->next=NULL; /* 创建单链表的表头结点head */
while (1) { scanf(“%d”,& data); scanf(“%d” if (data==32767) break ; q= (LNode
/*钩链 新创建的结点总是作为最后一个结点 /*钩链，新创建的结点总是作为最后一个结点*/ 钩链， 的结点总是作为最后一个结点*
} return (head); } 无论是哪种插入方法，如果要插入建立的单线 无论是哪种插入方法， 性链表的结点是n 算法的时间复杂度均为O(n)。 性链表的结点是n个，算法的时间复杂度均为O(n)。 对于单链表，无论是哪种操作，只要涉及到钩链( 对于单链表，无论是哪种操作，只要涉及到钩链( 或重新钩链) 如果没有明确给出直接后继 钩链( 没有明确给出直接后继， 或重新钩链)，如果没有明确给出直接后继，钩链(或 重新钩链)的次序必须是“先右后左” 重新钩链)的次序必须是“先右后左”。
2 单链表的查找(1) 按序号查找 取单链表中的第i个元素。 取单链表中的第i个元素。

对于单链表，不能象顺序表中那样直接按序号i访 对于单链表，不能象顺序表中那样直接按序号i 问结点，而只能从链表的头结点出发，沿链域next逐 问结点，而只能从链表的头结点出发，沿链域next逐 个结点往下搜索，直到搜索到第i个结点为止。因此， 个结点往下搜索，直到搜索到第i个结点为止。因此， 链表不是随机存取结构。 链表不是随机存取结构。 设单链表的长度为n 要查找表中第i个结点， 设单链表的长度为n，要查找表中第i个结点，仅 的值是合法的。 当1≦i≦n时，i的值是合法的。
算法描述ElemType Get_Elem(LNode *L ， int i) { int j ; LNode *p; p=Lp=L->next; j=1;*/ /* 使p指向第一个结点
while (p!=NULL && jnext; j++; } p=p–p , j计数 */ j计数
/* 移动指针
if (j!=i) return(-32768) ; return(else return(preturn(p->data);/* p为 p为NULL 表示i太大; j>i表示i为0 */ 表示i太大; j>i表示 表示i
} 移动指针p的频度： 移动指针p的频度： i<1时 i<1时：0次; i∈[1,n]：i-1次；i>n：n次。 i∈[1,n]： i>n：
(2) 按值查找按值查找是在链表中，查找是否有结点值等于给定 按值查找是在链表中， key的结点 若有，则返回首次找到的值为key的结 的结点? 值key的结点? 若有，则返回首次找到的值为key的结 点的存储位置；否则返回NULL。 点的存储位置；否则返回NULL。查找时从开始结点出 沿链表逐个将结点的值和给定值key作比较 作比较。 发，沿链表逐个将结点的值和给定值key作比较。
算法描述LNode *Locate_Node(LNode *L，int key) *L，/* 在以L为头结点的单链表中查找值为key的第一个结点 */ 在以L为头结点的单链表中查找值为key的第一个结点
{
LNode *p=L–>next; *p=L– while ( p!=NULL&& p–>data!=key) p– p=p– p=p–>next; if (p–>data==key) (p– else { } printf(“所要查找的结点不存在!!\ printf(“所要查找的结点不存在!!\n”); retutn(NULL); return p;
}key O(n)
3 单链表的插入插入运算是将值为e的新结点插入到表的第i 插入运算是将值为e的新结点插入到表的第i个结 点的位置上，即插入到a 之间。因此， 点的位置上，即插入到ai-1与ai之间。因此，必须首先 找到a 所在的结点 的结点p 然后生成一个数据域为e 找到ai-1所在的结点p，然后生成一个数据域为e的新 结点q 结点q，q结点作为p的直接后继结点。 结点作为p的直接后继结点。
算法描述void Insert_LNode(LNode *L，int i， *L， i， ElemType e)/* 在以L为头结点的单链表的第i个位置插入值为e的结 在以L为头结点的单链表的第i个位置插入值为e 点 */
{
int j=0; LNode *p，*q; *p， p=L– p=L–>next ; while ( p!=NULL&& jif (j!=i-1) (j!=iprintf(“i太大或i为0!!\n ”); printf(“ 太大或i 0!!\ else { q=(LNode *

)malloc(sizeof(LNode)); q–>data=e; q–>next=p–>next; q–>next=p– p–>next=q; } } 设链表的长度为n 合法的插入位置是1 设链表的长度为n，合法的插入位置是1≦i≦n。算 法的时间主要耗费移动指针 移动指针p 法的时间主要耗费移动指针p上，故时间复杂度亦为 O(n)。 O(n)。
4 单链表的删除⑴ 按序号删除删除单链表中的第i个结点。 删除单链表中的第i个结点。 为了删除第i个结点a 必须找到结点的存储地址。 为了删除第i个结点ai，必须找到结点的存储地址。 该存储地址是在其直接前趋结点a next域中 域中， 该存储地址是在其直接前趋结点ai-1的next域中，因 必须首先找到a 的存储位置p 然后令p 此，必须首先找到ai-1的存储位置p，然后令p–>next 指向a 的直接后继结点，即把a 从链上摘下。 指向ai的直接后继结点，即把ai从链上摘下。最后释放 结点a 的空间，将其归还给“存储池” 结点ai的空间，将其归还给“存储池”。 设单链表长度为n 则删去第i个结点仅当1 设单链表长度为n，则删去第i个结点仅当1≦i≦n 时是合法的。则当i=n+1时 虽然被删结点不存在， 时是合法的。则当i=n+1时，虽然被删结点不存在， 但其前趋结点却存在，是终端结点。 但其前趋结点却存在，是终端结点。故判断条件之一是 p–>next!=NULL。显然此算法的时间复杂度也是 >next!=NULL。 O(n)。 (n)。
算法描述void Delete_LinkList(LNode *L， int i) *L，/* 删除以L为头结点的单链表中的第i个结点 删除以L为头结点的单链表中的第i */
{ int j=1; LNode *p，*q; *p， p=L; q=L->next; q=Lwhile ( p->next!=NULL&& jnext; j++; } q=q– if (j!=i) printf(“ 太大或i 0!!\ printf(“i太大或i为0!!\n ”); else { p–>next=q–>next; free(q); } p–>next=q– }
⑵ 按值删除删除单链表中值为key的第一个结点 删除单链表中值为key的第一个结点。 的第一个结点。 与按值查找相类似，首先要查找值为key的结点是 key的结点是 与按值查找相类似，首先要查找值为key 否存在? 若存在，则删除；否则返回NULL。 否存在? 若存在，则删除；否则返回NULL。
算法描述void Delete_LinkList(LNode *L，int key) *L，/* 删除以L为头结点的单链表中值为key的第一个结点 */ 删除以L为头结点的单链表中值为key的第一个结点
{
LNode *p=L, *q=L–>next; *q=L– while ( q!=NULL&& q–>data!=key) q– { p=q; q=q–>next; } q=q– if (q–>data==key) (q– { p->next=q->next; free(q); } p->next=qelse printf(“所要删除的结点不存在!!\ printf(“所要删除的结点不存在!!\n”);
}
算法的执行与形参key有关 算法的执行与形参key有关，平均时间复杂度为 有关， O(n)。 O(n)。 从上面的讨论可以看出， 从上面的讨论可以看出，链表上实现插入和

删除运 无需移动结点，仅需修改指针。 算，无需移动结点，仅需修改指针。解决了顺序表的插 入或删除操作需要移动大量元素的问题。 入或删除操作需要移动大量元素的问题。
变形之一： 变形之一：删除单链表中值为key的所有结点 删除单链表中值为key的所有结点。 的所有结点。 与按值查找相类似，但比前面的算法更简单。 与按值查找相类似，但比前面的算法更简单。
基本思想：从单链表的第一个结点开始， 基本思想：从单链表的第一个结点开始，对每个结点进行检查，若结点的值为key，则删除之，然后检查下 key， 进行检查，若结点的值为key 则删除之， 一个结点，直到所有的结点都检查。 一个结点，直到所有的结点都检查。
算法描述void Delete_LinkList_Node(LNode *L，int *L， key)/* 删除以L为头结点的单链表中值为key的第一个结点 */ 删除以L为头结点的单链表中值为key的第一个结点
{
LNode *p=L, *q=L–>next; *q=L– while ( q!=NULL) { if (q–>data==key) (q– { p->next=q->next; free(q); p->next=qq=pq=p->next; } else { p=q; q=q–>next; } q=q– }
}
变形之二： 变形之二：删除单链表中所有值重复的结点， 删除单链表中所有值重复的结点，使得所有结点的 值都不相同。 值都不相同。 与按值查找相类似，但比前面的算法更复杂。 与按值查找相类似，但比前面的算法更复杂。
基本思想：从单链表的第一个结点开始， 基本思想：从单链表的第一个结点开始，对每个结点进行检查：检查链表中该结点的所有后继结点，只要有 进行检查：检查链表中该结点的所有后继结点， 值和该结点的值相同，则删除之；然后检查下一个结点， 值和该结点的值相同，则删除之；然后检查下一个结点， 直到所有的结点都检查。 直到所有的结点都检查。
算法描述void Delete_Node_value(LNode *L)/* 删除以L为头结点的单链表中所有值相同的结点 */ 删除以L
{
LNode *p=L->next, *q, *ptr; *p=Lwhile ( p!=NULL) /* 检查链表中所有结点*/
{
*q=p, *ptr=p–>next; *ptr=p–/* 检查结点p的所有后继结点ptr */ 检查结点p的所有后继结点ptr
while (ptr!=NULL) { if (ptr–>data==p->data) (ptr–>data==p{ q->next=ptr->next; q->next=ptrfree(ptr); ptr=qptr=q->next; } else { q=ptr; ptr=ptr–>next; ptr=ptr–
p=pp=p->next ; } }
5 单链表的合并设有两个有序的单链表，它们的头指针分别是La 设有两个有序的单链表，它们的头指针分别是La 、 Lb，将它们合并为以Lc为头指针的有序链表。 Lb，将它们合并为以Lc为头指针的有序链表。合并前 的示意图如图2 所示。 的示意图如图2-4所示。Lc pc La Lb -2 pb图2-4 两个有序的单链表La 两个有序的单链表 ，Lb的初始状态 的初始状态
pa -

7 3 4 12 9 …… …… 23 ? 15 ?
合并了值为合并了值为-7，-2的结点后示意图如图2-5所示。 的结点后示意图如图2 所示。La Lc Lb -2 pc图2-5
pa -7 3 4 pb 12 9 …… …… 23 ? 15 ?
合并了值为-7 合并了值为 ，-2的结点后的状态 的结点后的状态
算法说明算法中pa pb分别是待考察的两个链表的当前 算法中pa ，pb分别是待考察的两个链表的当前 结点，pc是合并过程中合并的链表的最后一个结点。 结点，pc是合并过程中合并的链表的最后一个结点。 是合并过程中合并的链表的最后一个结点
算法描述LNode *Merge_LinkList(LNode *La， *La， LNode *Lb)/* 合并以La, Lb为头结点的两个有序单链表 合并以La, Lb为头结点的两个有序单链表 */
{
LNode *Lc, *pa , *pb , *pc, *ptr ; Lc=La ; pc=La ; pb=Lbpb=Lb->next ; pa=Lapa=La->next ;
while (pa!=NULL && pb!=NULL) { if (pa->datadata) (pa->datanext=pa ; pc=pa ; pcpa=papa=pa->next ; }/* 将pa所指的结点合并，pa指向下一个结点 */ pa所指的结点合并 pa指向下一个结点 所指的结点合并，
if (pa->data>pb->data) (pa->data>pb-
if (pa->data==pb->data) (pa->data==pb{ pc->next=pa ; pc=pa ; pcpa=papa=pa->next ; ptr=pb ; pb=pb->next ; pb=pbfree(ptr) ; }/* 将pa所指的结点合并，pb所指结点删除 */ pa所指的结点合并 pb所指结点删除 所指的结点合并，
} if (pa!=NULL) pc->next=pa ; pcelse pc->next=pb ; /*将剩余的结点链上*/ pc/*将剩余的结点链上 将剩余的结点链上* free(Lb) ; return(Lc) ; }
算法分析若La ，Lb两个链表的长度分别是m，n，则链 Lb两个链表的长度分别是 两个链表的长度分别是m
2.3.3 循环链表循环链表(Circular Linked List)：是一种 List)头尾相接的链表。其特点是最后一个结点的指针域指向 头尾相接的链表。 链表的头结点，整个链表的指针域链接成一个环。 链表的头结点，整个链表的指针域链接成一个环 链表的指针域链接成一个环。 从循环链表的任意一个结点出发都可以找到链表 中的其它结点，使得表处理更加方便灵活。 中的其它结点，使得表处理更加方便灵活。 图2-6是带头结点的单循环链表的示意图。 是带头结点的单循环链表的示意图。head head a1 空表图2-6 单循环链表示意图
a2 非空表
……
an
循环链表的操作对于单循环链表，除链表的合并外， 对于单循环链表，除链表的合并外，其它的操作和 单线性链表基本上一致， 单线性链表基本上一致，仅仅需要在单线性链表操作算 法基础上作以下简单修改： 法基础上作以下简单修改： 判断是否是空链表： ⑴ 判断是否是空链表：head->next==head ; 判断是否是表尾结点： ⑵ 判断是否是表尾结点：p->next==head ;
2.4 双向链表双向链表(Double Linked List) :指的是构 List)成

本文来源：https://www.bwwdw.com/article/93wl.html