当前位置:首页 >> 工学 >>

数据结构-清华大学严蔚敏PPT


算法与数据结构
严蔚敏, 教材:《数据结构(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,数据与数据成简单的一对一的线性关系。 ,数据与数据成简单的一对一的线性关系
姓名 陈海 李四锋 。。。 电话号码 13612345588 13056112345 。。。

表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={ <k1, k3>,<k1, k8>,<k2, k3>,<k2, k4>,<k2, k5>,<k3, k9>,<k5, k6>,<k8, k9>,<k9, k7>,<k4, k7>,<k4, k6> } 画出这逻辑结构的图示,并确定那些是起点, 画出这逻辑结构的图示,并确定那些是起点,那些是终点

数据元素之间的关系可以是元素之间代表某种含义 的自然关系, 的自然关系,也可以是为处理问题方便而人为定义的 关系,这种自然或人为定义的 关系” 关系,这种自然或人为定义的 “关系”称为数据元素 之间的逻辑关系 相应的结构称为逻辑结构 逻辑关系, 结构称为逻辑结构。 之间的逻辑关系,相应的结构称为逻辑结构。

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 例1 两个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) 例2 {++x; s=0 ;} 将x自增看成是基本操作,则语句频度为1,即时 自增看成是基本操作,则语句频度为1 间复杂度为O 间复杂度为O(1) 。

如果将s=0也看成是基本操作,则语句频度为2 如果将s=0也看成是基本操作,则语句频度为2,其时 s=0也看成是基本操作 间复杂度仍为O(1),即常量阶。 间复杂度仍为O(1),即常量阶。 例3 for(i=1; i<=n; ++i) { ++x; s+=x ; } 语句频度为:2n,其时间复杂度为: 语句频度为:2n,其时间复杂度为:O(n) ,即为线性 阶。 例4 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是一个 +a
m次多项式,则A(n)=O(n m) 次多项式, 例5 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)<O(㏒n)<O(n)<O(n㏒ O(1)<O(㏒n)<O(n)<O(n㏒n)<O(n2)<O(n3) – 指数时间的关系为: 指数时间的关系为: O(2n)<O(n!)<O(nn) 当n取得很大时,指数时间算法和多项式时间算法 取得很大时, 在所需时间上非常悬殊。因此, 在所需时间上非常悬殊。因此,只要有人能将现有指 数时间算法中的任何一个算法化简为多项式时间算法, 数时间算法中的任何一个算法化简为多项式时间算法, 那就取得了一个伟大的成就。 那就取得了一个伟大的成就。 – 有的情况下,算法中基本操作重复执行的次数还 有的情况下, 随问题的输入数据集不同而不同。 随问题的输入数据集不同而不同。

素数的判断算法。 例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; j<i; ++j) if (a[j]>a[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,3,4,…,J,Q,K, (2,

◆ 线性表中的结点可以是记录型元素,每个元素 线性表中的结点可以是记录型元素, 结点可以是记录型元素 含有多个数据项 ,每个项称为结点的一个域 。每个 元素有一个可以唯一标识每个结点的数据项组 数据项组, 元素有一个可以唯一标识每个结点的数据项组,称 关键字。 为关键字。 例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> | ai-1, ai∈D, i=2,3,…,n } 基本操作: 基本操作: InitList( &L ) 操作结果:构造一个空的线性表 ; 操作结果:构造一个空的线性表L;

ListLength( L ) 初始条件:线性表L已存在 已存在; 初始条件:线性表 已存在; 操作结果: 为空表, 操作结果:若L为空表,则返回 为空表 则返回TRUE,否则返回 , FALSE; ; …. 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,…a
i-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≦i≦n) (1≦ ∴ 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 ; k<L->length ; k++) k<LL->Elem_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 (i<L->length) (i<L个结点*/ 结点*

/*查找值为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

3695
head 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

① q=p ;

a … 操作前 p a b 操作前 p a b 操作前 q a b c … …

a … 操作后 q p b … 操作后 p

② q=p->next ; ③ p=p->next ; ④ q->next=p ; (a)



a







a b 操作后 q a p b



… p







… 操作前

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 && j<i) { p=p–>next; 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<i-1) j<i-

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&& j<i) p{ p=q; q=q–>next; 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->data<pb->data) (pa->data<pb{ pc->next=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)
成链表的每个结点中设立两个指针域:一个指向其直接 成链表的每个结点中设立两个指针域: 前趋的指针域prior, 前趋的指针域prior,一个指向其直接后继的指针域 next。这样形成的链表中有两个方向不同的链, next。这样形成的链表中有两个方向不同的链,故称 双向链表。 为双向链表。 和单链表类似, 和单链表类似,双向链表一般增加头指针也能使双 链表上的某些运算变得方便。 链表上的某些运算变得方便。 将头结点和尾结点链接起来也能构成循环链表, 将头结点和尾结点链接起来也能构成循环链表,并 称之为双向循环链表。 称之为双向循环链表。 双向链表是为了克服单链表的单向性的缺陷而引入 的。

1

双向链表的结点及其类型定义

双向链表的结点的类型定义如下。其结点形式如 双向链表的结点的类型定义如下。 所示,带头结点的双向链表的形式如图2 所示。 图2-7所示,带头结点的双向链表的形式如图2-8所示。 typedef struct Dulnode { ElemType data ; struct Dulnode *prior , *next ; }DulNode ;
prior data next head ? ? ?
空双向链表 图2-7 双向链表结点形式

head a1 a2 …… an ?
非空双向链表 图2-8 带头结点的双向链表形式

双向链表结构具有对称性, 双向链表结构具有对称性,设p指向双向链表中的 某一结点,则其对称性可用下式描述: 某一结点,则其对称性可用下式描述: (p->prior)->next=p=(p->next)->prior (p->prior)->next=p=(p->next); 结点p的存储位置存放在其直接前趋结点 结点p的存储位置存放在其直接前趋结点p直接前趋结点p >prior的直接后继指针域中 同时也存放在其直接后 >prior的直接后继指针域中,同时也存放在其直接后 继结点p >next的直接前趋指针域中 继结点p->next的直接前趋指针域中。

2 双向链表的基本操作
(1) 双向链表的插入 将值为e的结点插入双向链表 将值为e
p p 中。插入前后链表的变化如图2-9所示。 插入前后链表的变化如图2 所示。 …… ai S e ai+1 …… ……
图2-9 双向链表的插入

ai S e

ai+1

……

① 插入时仅仅指出直接前驱结点,钩链时必须注意 插入时仅仅指出直接前驱结点, 先后次序是: 先右后左” 部分语句组如下: 先后次序是: “先右后左” 。部分语句组如下: S=(DulNode S=(DulNode *)malloc(sizeof(DulNode)); *)malloc(sizeof(DulNode)); S->data=e; S->next=p->next; >next=p常重要 */

p->next->prior=S; p->next/* 钩链次序非

p->next=S; S->prior=p; S-

② 插入时同时指出直接前驱结点p和直接后继结点 插入时同时指出直接前驱结点p q,钩链时无须注意先后次序。部分语句组如下: 钩链时无须注意先后次序。部分语句组如下: S=(DulNode S=(DulNode *)malloc(sizeof(DulNode)); *)malloc(sizeof(DulNode)); S->data=e;

(2)

双向链表的结点删除

设要删除的结点为 设要删除的结点为p ,删除时可以不引入新的辅助 的结点为p 指针变量,可以直接先断链,再释放结点。 指针变量,可以直接先断链,再释放结点。部分语句组 如下: 如下: p->prior->next=p->next; >prior->next=pp->next->prior=p->prior; >next->prior=pfree(p);

注意: 注意:
与单链表的插入和删除操作不同的是, 与单链表的插入和删除操作不同的是,在双向链 表中插入 删除必须同时 插入和 必须同时修改两个方向上的指针域的指 表中插入和删除必须同时修改两个方向上的指针域的指 向。

2.5 一元多项式的表示和相加
1 一元多项式的表示
一元多项式 p(x)=p0+p1x+p2x2+ … +pnxn , n+1个系数唯一确定 则在计算机中可用线性表 个系数唯一确定。 用线性表(p 由n+1个系数唯一确定。则在计算机中可用线性表(p0 , p1 ,p2 ,… ,pn )表示。既然是线性表,就可以用顺 表示。既然是线性表 线性表, 序表和链表来实现。 序表和链表来实现。两种不同实现方式的元素类型定义 如下: 如下: (1) 顺序存储表示的类型 (2) 链式存储表示的类型 typedef struct ploy typedef struct { float coef ; /*系数部分 系数部分*/ 系数部分 { float coef; /*系数部分 系数部分*/ 系数部分 int expn ; /*指数部分 指数部分*/ 指数部分 int expn; /*指数部分 指数部分*/ 指数部分 struct ploy *next ; } ElemType ; } Ploy ;

2

一元多项式的相加
不失一般性,设有两个一元多项式: 不失一般性,设有两个一元多项式: P(x)=p0+p1x+p2x2+ … +pnxn , Q(x)=q0+q1x+q2x2+ … +qmxm (m<n) R(x)=P(x)+ Q(x)

R(x)由线性表 R(x)由线性表R((p0+q0) ,(p1+q1) , 由线性表R((p (p2+q2) , … ,(pm+qm) , … , pn)唯一表示。 唯一表示。

⑴ 顺序存储表示的相加 线性表的定义
typedef struct { ElemType a[MAX_SIZE] ; a[MAX_SIZE] int length ;

}Sqlist ; 用顺序表示的相加非常简单。访问第5 用顺序表示的相加非常简单。访问第5项可直接 访问: 访问:L.a[4].coef , L.a[4].expn

(2) 链式存储表示的相加
当采用链式存储表示时,根据结点类型定义, 当采用链式存储表示时,根据结点类型定义,凡 是系数为0的项不在链表中出现, 是系数为0的项不在链表中出现,从而可以大大减少链 表的长度。 表的长度。

一元多项式相加的实质是 一元多项式相加的实质是:
? 指数不同: 是链表的合并。 指数不同: 是链表的合并。 ? 指数相同: 系数相加,和为0,去掉结点,和不 指数相同: 系数相加,和为0 去掉结点, 修改结点的系数域。 为0,修改结点的系数域。

算法之一: 算法之一:
就在原来两个多项式链表的基础上进行相加,相加 就在原来两个多项式链表的基础上进行相加, 后原来两个多项式链表就不在存在。 后原来两个多项式链表就不在存在。当然再要对原来 两个多项式进行其它操作就不允许了。 两个多项式进行其它操作就不允许了。

算法描述
Ploy *add_ploy(ploy *La, ploy *Lb) *La,
/* 将以La ,Lb为头指针表示的一元多项式相加 */ 将以La Lb为头指针表示的一元多项式相加

{ ploy *Lc , *pc , *pa , *pb ,*ptr ; float x ; Lc=pc=La ; pa=La->next ; pb=Lbpa=Lapb=Lb>next ; while (pa!=NULL&&pb!=NULL) { if (pa->expn<pb->expn) (pa->expn<pb{ pc->next=pa ; pc=pa ; pa=papcpa=pa>next ; }
/* 将pa所指的结点合并,pa指向下一个结点 pa所指的结点合并 pa指向下一个结点 所指的结点合并, */

else { x=pa->coef+pb->coef ; x=pa->coef+pbif (abs(x)<=1.0e-6) (abs(x)<=1.0e/* 如果系数和为0,删除两个结点 */ 如果系数和为0

{ ptr=pa ; pa=pa->next ; pa=pafree(ptr) ; ptr=pb ; pb=pb->next ; pb=pbfree(ptr) ; } else
/* 如果系数和不为0,修改其中 如果系数和不为0 一个结点的系数域, 一个结点的系数域,删除另一个结点 */

{ pc->next=pa ; papcpa>coef=x ; pc=pa ; pa=pa->next ; pa=pa-

} }
/* end of while */

if (pa==NULL) pc->next=pb ; pcelse pc->next=pa ; pcreturn (Lc) ; }

算法之二: 算法之二:
对两个多项式链表进行相加,生成一个新的相加后 对两个多项式链表进行相加, 的结果多项式链表,原来两个多项式链表依然存在, 的结果多项式链表,原来两个多项式链表依然存在, 不发生任何改变, 不发生任何改变,如果要再对原来两个多项式进行其 它操作也不影响。 它操作也不影响。

算法描述
Ploy *add_ploy(ploy *La, ploy *Lb) *La,
/* 将以La ,Lb为头指针表示的一元多项式相加,生成一 将以La Lb为头指针表示的一元多项式相加 为头指针表示的一元多项式相加, 个新的结果多项式 */

{ ploy *Lc , *pc , *pa , *pb , *p ; x; pa=Lapa=La->next ; pb=Lb->next ; pb=Lbwhile (pa!=NULL&&pb!=NULL) { if (pa->expn<pb->expn) (pa->expn<pb-

float

Lc=pc=( Lc=pc=(ploy *)malloc(sizeof(ploy)) ; *)malloc(sizeof(ploy))

{ p=(ploy *)malloc(sizeof(ploy)) p=( *)malloc(sizeof(ploy)) ; p->coef=pa->coef ; p>coef=pap-

/* 生成一个新的结果结点并赋值 */

pc->next=p ; pc=p ; pa=papcpa=pa>next ; }
/* 生成的结点插入到结果链表的最后,pa指 生成的结点插入到结果链表的最后,pa指 向下一个结点 */

if (pa->expn>pb->expn) (pa->expn>pb{ p=(ploy *)malloc(sizeof(ploy)) p=( *)malloc(sizeof(ploy)) ; p->coef=pb->coef ; p>coef=pbp>expn=pb>expn=pb->expn ; p->next=NULL ;
/* 生成一个新的结果结点并赋值 */

pc->next=p ; pc=p ; pb=pbpcpb=pb-

if (pa->expn==pb->expn) (pa->expn==pb{ x=pa->coef+pb->coef ; x=pa->coef+pbif (abs(x)<=1.0e-6) (abs(x)<=1.0e/* 系数和为0,pa, pb分别直接后继 系数和为0 pb分别直接后继 结点 */

{ pa=pa->next ; pb=pbpa=papb=pb>next ; }
/* 若系数和不为0,生成的结点 若系数和不为0 插入到结果链表的最后, pb分别直接后继结点 插入到结果链表的最后, pa, pb分别直接后继结点 */

else

{ p=(ploy p=( *)malloc(sizeof(ploy)) *)malloc(sizeof(ploy)) ; p->coef=x ; pp>expn=pb>expn=pb->expn ;

} } }
/* end of while */

if (pb!=NULL) while(pb!=NULL) { p=(ploy *)malloc(sizeof(ploy)) p=( *)malloc(sizeof(ploy)) ; p->coef=pb->coef ; p>coef=pbp>expn=pb>expn=pb->expn ; p->next=NULL ;
/* 生成一个新的结果结点并赋值 */

pc->next=p ; pc=p ; pb=pbpcpb=pb>next ;

if (pa!=NULL) while(pa!=NULL) { p=(ploy *)malloc(sizeof(ploy)) p=( *)malloc(sizeof(ploy)) ; p->coef=pb->coef ; p>coef=pbp>expn=pa>expn=pa->expn ; p->next=NULL ;
/* 生成一个新的结果结点并赋值 */

pc->next=p ; pc=p ; pa=papcpa=pa>next ; } return (Lc) ; }

习题二
1 简述下列术语:线性表,顺序表,链表。 简述下列术语:线性表,顺序表,链表。 2 何时选用顺序表,何时选用链表作为线性表的存 何时选用顺序表, 储结构合适?各自的主要优缺点是什么? 储结构合适?各自的主要优缺点是什么? 3 在顺序表中插入和删除一个结点平均需要移动多 少个结点?具体的移动次数取决于哪两个因素? 少个结点?具体的移动次数取决于哪两个因素? 4 链表所表示的元素是否有序?如有序,则有序性 链表所表示的元素是否有序?如有序, 体现于何处? 体现于何处?链表所表示的元素是否一定要在物理上是 相邻的?有序表的有序性又如何理解? 相邻的?有序表的有序性又如何理解? 5 设顺序表L是递增有序表,试写一算法,将x插入 设顺序表L是递增有序表,试写一算法, 中并使L仍是递增有序表。 到L中并使L仍是递增有序表。

6 写一求单链表的结点数目ListLength(L)的算 写一求单链表的结点数目ListLength(L)的算 法。 7 写一算法将单链表中值重复的结点删除,使所得 写一算法将单链表中值重复的结点删除, 的结果链表中所有结点的值均不相同。 的结果链表中所有结点的值均不相同。 8 写一算法从一给定的向量A删除值在x到 写一算法从一给定的向量A删除值在x y(x≤y)之间的所有元素 注意: y(x≤y)之间的所有元素(注意:x和y是给定的参数, 之间的所有元素( 是给定的参数, 可以和表中的元素相同,也可以不同) 可以和表中的元素相同,也可以不同)。 9 设A和B是两个按元素值递增有序的单链表,写一 是两个按元素值递增有序的单链表, 算法将A 归并为按按元素值递减有序的单链表C 算法将A和B归并为按按元素值递减有序的单链表C, 试分析算法的时间复杂度。 试分析算法的时间复杂度。

第3章 栈和队列
栈和队列是两种应用非常广泛的数据结构, 栈和队列是两种应用非常广泛的数据结构,它们都 来自线性表数据结构,都是“操作受限”的线性表。 来自线性表数据结构,都是“操作受限”的线性表。 栈在计算机的实现有多种方式: 栈在计算机的实现有多种方式: ◆ 硬堆栈:利用CPU中的某些寄存器组或类似的硬 硬堆栈:利用CPU中的某些寄存器组或类似的硬 件或使用内存的特殊区域来实现。这类堆栈容量有限, 件或使用内存的特殊区域来实现。这类堆栈容量有限, 但速度很快; 但速度很快; ◆ 软堆栈:这类堆栈主要在内存中实现。堆栈容量 软堆栈:这类堆栈主要在内存中实现。 可以达到很大。在实现方式上,又有动态方式 动态方式和 可以达到很大。在实现方式上,又有动态方式和静态 方式两种 两种。 方式两种。 本章将讨论栈和队列的基本概念、存储结构、 本章将讨论栈和队列的基本概念、存储结构、基本 操作以及这些操作的具体实现。 操作以及这些操作的具体实现。

3.1 栈
3.1.1 栈的基本概念
1 栈的概念
栈(Stack):是限制在表的一端进行插入和删除 Stack)
操作的线性表。又称为后进先出LIFO (Last In 操作的线性表。又称为后进先出LIFO First Out)或先进后出FILO (First In Last Out) Out)或先进后出FILO Out) 线性表 线性表。

栈顶(Top) 允许进行插入、删除操作的一端, 栈顶(Top):允许进行插入、删除操作的一端,
又称为表尾。用栈顶指针(top)来指示栈顶元素。 来指示栈顶元素。 又称为表尾。用栈顶指针(top)来指示栈顶元素

栈底(Bottom) 是固定端,又称为表头。 栈底(Bottom):是固定端,又称为表头。 空栈:当表中没有元素时称为空栈。 空栈:当表中没有元素时称为空栈。

设栈S=(a 设栈S=(a1,a2,…an),则 a1称为栈底元素,an为栈顶元素, 称为栈底元素, 为栈顶元素, 如图3 所示。 如图3-1所示。

进栈( 进栈(push) )

出栈(pop) 出栈

top

栈中元素按a 栈中元素按a1,a2,…an的次 序进栈, 序进栈,退栈的第一个元素应为栈顶 元素。 元素。即栈的修改是按后进先出的原 bottom 则进行的。 则进行的。 图3-1

an ?? ai ?? a2 a1
顺序栈示意图 顺序栈示意图

2 栈的抽象数据类型定义
ADT Stack{ 数据对象: 数据对象:D ={ ai|ai∈ElemSet, i=1,2,…,n,n≥0 } , 数据关系: 数据关系:R ={<ai-1, ai>|ai-1,ai∈D, i=2,3,…,n } 基本操作:初始化、进栈、出栈、 基本操作:初始化、进栈、出栈、取栈顶元素等 } ADT Stack

3.1.2 栈的顺序存储表示
栈的顺序存储结构简称为顺序栈,和线性表相类似, 栈的顺序存储结构简称为顺序栈,和线性表相类似, 一维数组来存储栈。根据数组是否可以根据需要增大, 用一维数组来存储栈。根据数组是否可以根据需要增大, 又可分为静态顺序栈 动态顺序栈。 静态顺序栈和 又可分为静态顺序栈和动态顺序栈。 ◆ 静态顺序栈实现简单,但不能根据需要增大栈的 静态顺序栈实现简单 实现简单, 存储空间; 存储空间; ◆ 动态顺序栈可以根据需要增大栈的存储空间,但 动态顺序栈可以根据需要增大栈的存储空间 可以根据需要增大栈的存储空间, 实现稍为复杂。 实现稍为复杂。

3.1.2.1 栈的动态顺序存储表示
采用动态一维数组来存储栈。所谓动态, 采用动态一维数组来存储栈。所谓动态,指的是栈 动态一维数组 的大小可以根据需要增加。 的大小可以根据需要增加。 ◆ 用bottom表示栈底指针,栈底固定不变的;栈 bottom表示栈底指针 栈底固定不变的; 表示栈底指针, 顶则随着进栈和退栈操作而变化。 top( 顶则随着进栈和退栈操作而变化。用top(称为栈顶 指针)指示当前栈顶位置。 指针)指示当前栈顶位置。 ◆ 用top=bottom作为栈空的标记,每次top指向 top=bottom作为栈空的标记 每次top指向 作为栈空的标记, 栈顶数组中的下一个存储位置。 栈顶数组中的下一个存储位置。 ◆ 结点进栈:首先将数据元素保存到栈顶(top所 结点进栈:首先将数据元素保存到栈顶(top所 指的当前位置) 然后执行top加 top指向栈顶 指的当前位置),然后执行top加1,使top指向栈顶 的下一个存储位置; 的下一个存储位置;

◆ 结点出栈:首先执行top减1,使top指向栈顶 结点出栈:首先执行top减 top指向栈顶 元素的存储位置,然后将栈顶元素取出。 元素的存储位置,然后将栈顶元素取出。 图3-2是一个动态栈的变化示意图。 是一个动态栈的变化示意图。
top top bottom top 空栈 bottom 元素a进栈 元素 进栈 top

a

bottom 元素b, 进栈 元素 ,c进栈

c b a

top bottom 元素c退栈 元素 退栈

b a

bottom 元素d, , 进栈 元素 ,e,f进栈

f e d b a

动态)堆栈变化示意图 图3-2 (动态 堆栈变化示意图 动态

基本操作的实现
1 栈的类型定义
#define STACK_SIZE 100
*/ /* 栈初始向量大小 /* 存储空间分

#define STACKINCREMENT 10
配增量 */

#typedef int ElemType ; typedef struct sqstack { ElemType *bottom; ElemType *top; int stacksize ;
为单位 */ /* 栈不存在时值为 NULL */ /* 栈顶指针 */ /* 当前已分配空间,以元素 当前已分配空间,

2 栈的初始化
Status Init_Stack(void) { SqStack S ; S.bottom=(ElemType *)malloc(STACK_SIZE *sizeof(ElemType)); if (! S.bottom) return ERROR; S.top=S.bottom ;
相同 */ /* 栈空时栈顶和栈底指针

S. stacksize=STACK_SIZE; return OK ; }

3 压栈(元素进栈) 压栈(元素进栈)
Status push(SqStack S , ElemType e)

{ if (S.top-S.bottom>=S. (S.topstacksizestacksize-1)
{ S.bottom=(ElemType *)realloc((S. STACKINCREMENT+STACK_SIZE) *sizeof(ElemType)); /* 栈满,追加存储空 栈满,
间 */

if (! S.bottom) return ERROR; S.top=S.bottom+S. stacksize ; S. stacksize+=STACKINCREMENT ; }

4 弹栈(元素出栈) 弹栈(元素出栈 出栈)
Status pop( SqStack
/*弹出栈顶元素*/ /*弹出栈顶元素 弹出栈顶元素*

S, ElemType *e )

{

if ( S.top== S.bottom ) return ERROR ;
*/ /* 栈空,返回失败标志 栈空,

S.top-S.top-- ; e=*S. top ; return OK ; }

3.1.2.2 栈的静态顺序存储表示
采用静态一维数组来存储栈。 采用静态一维数组来存储栈。 静态一维数组 栈底固定不变的,而栈顶则随着进栈和退栈操作变 栈底固定不变的, 化的, 化的, ◆ 栈底固定不变的;栈顶则随着进栈和退栈操作而 栈底固定不变的; 变化,用一个整型变量top(称为栈顶指针) 变化,用一个整型变量top(称为栈顶指针)来指示当 前栈顶位置。 前栈顶位置。 ◆ 用top=0表示栈空的初始状态,每次top指向栈 top=0表示栈空的初始状态 每次top指向栈 表示栈空的初始状态, 顶在数组中的存储位置。 顶在数组中的存储位置。 ◆ 结点进栈:首先执行top加1,使top指向新的 结点进栈:首先执行top加 top指向新的 栈顶位置,然后将数据元素保存到栈顶(top所指的 栈顶位置,然后将数据元素保存到栈顶(top所指的 当前位置) 当前位置)。

◆ 结点出栈:首先把top指向的栈顶元素取出,然 结点出栈:首先把top指向的栈顶元素取出 指向的栈顶元素取出, 后执行top减 top指向新的栈顶位置 指向新的栈顶位置。 后执行top减1,使top指向新的栈顶位置。 若栈的数组有Maxsize个元素 若栈的数组有Maxsize个元素,则 个元素, top=Maxsize- 时栈满。 top=Maxsize-1时栈满。图3-3是一个大小为5的栈 是一个大小为5 的变化示意图。 的变化示意图。
top top top bottom top bottom 空栈

a
Top=1 1个元素进栈 个元素进栈 bottom

c b a

top

b a
bottom Top=2 元素c进栈 元素 进栈

e d b a
Top=4 栈满

Top=3 3个元素进栈 个元素进栈

bottom

静态堆栈变化示意图 图3-3 静态堆栈变化示意图

基本操作的实现
1 栈的类型定义
/* 栈向

# define MAX_STACK_SIZE 100
量大小 */

# typedef int ElemType ; typedef struct sqstack { ElemType stack_array[MAX_STACK_SIZE] ; int top; }SqStack ;

2 栈的初始化
SqStack Init_Stack(void) { } SqStack S ; S.bottom=S.top=0 ; return(S) ;

3 压栈(元素进栈) 压栈(元素进栈)
Status push(SqStack S , ElemType e)
/* 使数据元素e 使数据元素e进栈成为新的栈顶 */

{ if (S.top==MAX_STACK_SIZE-1) (S.top==MAX_STACK_SIZEreturn ERROR;
*/ /* 栈满,返回错误标志 栈满,

S.top++ ;
顶 */

/*

栈顶指针加1 栈顶指针加1 */ /* e成为新的栈 */

S.stack_array[S.top]=e ; return OK; }
/* 压栈成功

4 弹栈(元素出栈) 弹栈(元素出栈 出栈)
Status pop( SqStack
/*弹出栈顶元素*/ /*弹出栈顶元素 弹出栈顶元素*

S, ElemType *e )

{ if ( S.top==0 ) return ERROR ;
*/ /* 栈空,返回错误标志 栈空,

*e=S.stack_array[S.top] ; S.top-S.top-- ; return OK ; }

当栈满时做进栈运算必定产生空间溢出,简称“ 当栈满时做进栈运算必定产生空间溢出,简称“上 上溢是一种出错状态,应设法避免。 溢”。上溢是一种出错状态,应设法避免。 当栈空时做退栈运算也将产生溢出,简称“下溢”。 当栈空时做退栈运算也将产生溢出,简称“下溢” 下溢则可能是正常现象,因为栈在使用时, 下溢则可能是正常现象,因为栈在使用时,其初态或终 态都是空栈,所以下溢常用来作为控制转移的条件。 态都是空栈,所以下溢常用来作为控制转移的条件。

3.1.3 栈的链式存储表示
1 栈的链式表示
栈的链式存储结构称为链栈,是运算受限的单链表。 栈的链式存储结构称为链栈,是运算受限的单链表。 链式存储结构称为链栈 其插入和删除操作只能在表头位置上进行。因此, 其插入和删除操作只能在表头位置上进行。因此,链栈 没有必要像单链表那样附加头结点,栈顶指针top就是 没有必要像单链表那样附加头结点,栈顶指针top就是 链表的头指针。 是栈的链式存储表示形式。 链表的头指针。图3-4是栈的链式存储表示形式。 链栈的结点类型说明如下: 链栈的结点类型说明如下: 结点类型说明如下 typedef struct Stack_Node { ElemType data ; struct Stack_Node *next ; } Stack_Node ;
top 空栈

? top

a4 a3 a2 a1 ?
非空栈

图3-4 链栈存储形式

2

链栈基本操作的实现

(1) 栈的初始化
Stack_Node *Init_Link_Stack(void) { Stack_Node *top ; top=(Stack_Node top=(Stack_Node *)malloc(sizeof(Stack_Node )) ; )malloc(sizeof(Stack_Node toptop->next=NULL ; return(top) ; }

(2) 压栈(元素进栈) 压栈(元素进栈)
Status push(Stack_Node *top , ElemType push(Stack_Node e) { Stack_Node *p ; p=(Stack_Node p=(Stack_Node *)malloc(sizeof(Stack_Node)) ; )malloc(sizeof(Stack_Node)) if (!p) return ERROR;
/* 申请新结点失败,返回错误标志 */ 申请新结点失败,

p->data=e ; p->next=top->next ; >next=toptoptop->next=p ; return OK; }
/* 钩链 */

(3) 弹栈(元素出栈) 弹栈(元素出栈 出栈)
Status pop(Stack_Node *top , ElemType pop(Stack_Node *e)
/* 将栈顶元素出 将栈顶元素出栈 */

{

Stack_Node *p ; ElemType e ; if (top->next==NULL ) (topreturn ERROR ;
*/ /* 栈空,返回错误标志 栈空, /* 取栈顶元 */

p=topp=top->next ; e=p->data ; e=p素 */ /*

top->next=ptop->next=p->next ; free(p) ;

修改栈顶指针

3.2 栈的应用
由于栈具有的“后进先出”的固有特性,因此, 由于栈具有的“后进先出”的固有特性,因此,栈 成为程序设计中常用的工具和数据结构。 成为程序设计中常用的工具和数据结构。以下是几个栈 应用的例子。 应用的例子。

3.2.1 数制转换
十进制整数N向其它进制数d(二 十进制整数N向其它进制数d(二、八、十六)的转 十六) 换是计算机实现计算的基本问题。 换是计算机实现计算的基本问题。 转换法则:该转换法则对应于一个简单算法原理: 转换法则:该转换法则对应于一个简单算法原理: n=(n div d)*d+n mod d 其中:div为整除运算,mod为求余运算 为整除运算, 其中:div为整除运算 mod为求余运算 例如 (1348)10= (2504)8,其运算过程如下: 其运算过程如下: n 1348 168 21 2 n div 8 168 21 2 0 n mod 8 4 0 5 2

采用静态顺序栈方式实现 void conversion(int n , int d)
/*将十进制整数N转换为 或8)进制数 将十进制整数 转换为 转换为d(2或 进制数 进制数*/

{ SqStack S ;

int k, *e ; }

S=Init_Stack(); while (n>0) { k=n%d ; push(S , k) ; n=n/d ;
/* 求出所有的余数,进栈 */ 求出所有的余数

while (S.top!=0) { pop(S, e) ;

/* 栈不空时出栈,输出 */ 栈不空时出栈,

printf(“%1d” , *e) ; } }

3.2.2

括号匹配问题

在文字处理软件或编译程序设计时,常常需要检 在文字处理软件或编译程序设计时, 查一个字符串或一个表达式中的括号是否相匹配? 查一个字符串或一个表达式中的括号是否相匹配?

匹配思想:从左至右扫描一个字符串(或表达式) 匹配思想:从左至右扫描一个字符串(或表达式),则
每个右括号将与最近遇到的那个左括号相匹配。 每个右括号将与最近遇到的那个左括号相匹配。则可以 在从左至右扫描过程中把所遇到的左括号存放到堆栈中。 在从左至右扫描过程中把所遇到的左括号存放到堆栈中。 每当遇到一个右括号时,就将它与栈顶的左括号( 每当遇到一个右括号时,就将它与栈顶的左括号(如果 存在)相匹配,同时从栈顶删除该左括号。 存在)相匹配,同时从栈顶删除该左括号。

算法思想:设置一个栈,当读到左括号时, 算法思想:设置一个栈,当读到左括号时,左括号进
栈。当读到右括号时,则从栈中弹出一个元素,与读到 当读到右括号时,则从栈中弹出一个元素, 的左括号进行匹配,若匹配成功,继续读入; 的左括号进行匹配,若匹配成功,继续读入;否则匹配 失败,返回FLASE。 失败,返回FLASE。

算法描述
#define TRUE 0 #define FLASE -1 SqStack S ; S=Init_Stack() ; /*堆栈初始化*/ /*堆栈初始化 堆栈初始化* int Match_Brackets( ) { char ch , x ; scanf(“%c” scanf(“%c” , &ch) ; while (asc(ch)!=13)

{ if ((ch==‘(’)||(ch==‘[’)) push(S , ((ch==‘ )||(ch==‘ ch) ; else if (ch==‘]’) (ch==‘ { x=pop(S) ; if (x!=‘[’) (x!=‘ { printf(“’[’括号不匹配”) ; printf(“’[ 括号不匹配” return FLASE ; } } else if (ch==‘)’) (ch==‘ { x=pop(S) ; if (x!=‘(’) (x!=‘ { printf(“’(’括号不匹配”) ; printf(“’( 括号不匹配” return FLASE ;} } }

if (S.top!=0) { printf(“括号数量不匹配!”) ; printf(“括号数量不匹配! return FLASE ; } else return TRUE ; }

3.2.2 栈与递归调用的实现
栈的另一个重要应用是在程序设计语言中实现递归 调用。 调用。

递归调用:一个函数(或过程) 递归调用:一个函数(或过程)直接或间接地调用
自己本身,简称递归(Recursive)。 自己本身,简称递归 Recursive) 递归( 递归是程序设计中的一个强有力的工具。 递归是程序设计中的一个强有力的工具。因为递归 是程序设计中的一个强有力的工具 函数结构清晰,程序易读,正确性很容易得到证明。 函数结构清晰,程序易读,正确性很容易得到证明。 为了使递归调用不至于无终止地进行下去, 为了使递归调用不至于无终止地进行下去,实际上 有效的递归调用函数(或过程)应包括两部分: 有效的递归调用函数(或过程)应包括两部分:递推规则 方法) 终止条件。 (方法),终止条件。

例如: 例如:求n!

1 Fact(n)=

当n=0时 时

终止条件 递推规则

n*fact(n-1) 当n>0时 时

为保证递归调用正确执行,系统设立一个“ 为保证递归调用正确执行,系统设立一个“递归工 作栈” 作为整个递归调用过程期间使用的数据存储区。 作栈”,作为整个递归调用过程期间使用的数据存储区。 每一层递归包含的信息如:参数、局部变量、 每一层递归包含的信息如:参数、局部变量、上一 层的返回地址构成一个“工作记录” 。每进入一层递 层的返回地址构成一个“工作记录” 一个 就产生一个新的工作记录压入栈顶; 归,就产生一个新的工作记录压入栈顶;每退出一层递 就从栈顶弹出一个工作记录。 归,就从栈顶弹出一个工作记录。

从被调函数返回调用函数的一般步骤: 从被调函数返回调用函数的一般步骤: (1) 若栈为空,则执行正常返回。 若栈为空,则执行正常返回。 从栈顶弹出一个工作记录。 ⑵ 从栈顶弹出一个工作记录。 工作记录”中的参数值、 ⑶ 将“工作记录”中的参数值、局部变量值赋给相 应的变量;读取返回地址。 应的变量;读取返回地址。 将函数值赋给相应的变量。 ⑷ 将函数值赋给相应的变量。 (5) 转移到返回地址。 转移到返回地址。

3.3

队 列

3.3.1 队列及其基本概念
1 队列的基本概念
队列(Queue) 也是运算受限的线性表。 队列(Queue):也是运算受限的线性表。是一种 先进先出( 简称FIFO) 先进先出(First In First Out ,简称FIFO)的线性 只允许在表的一端进行插入,而在另一端进行删除。 表。只允许在表的一端进行插入,而在另一端进行删除。 队首(front) 允许进行删除的一端称为队首。 队首(front) :允许进行删除的一端称为队首。 队尾(rear) 允许进行插入的一端称为队尾。 队尾(rear) :允许进行插入的一端称为队尾。 例如:排队购物。操作系统中的作业排队。 例如:排队购物。操作系统中的作业排队。先进入 队列的成员总是先离开队列。 队列的成员总是先离开队列。

队列中没有元素时称为空队列。 队列中没有元素时称为空队列。在空队列中依次 加入元素a 之后, 是队首元素, 加入元素a1, a2, …, an之后,a1是队首元素,an是队 尾元素。显然退出队列的次序也只能是a 尾元素。显然退出队列的次序也只能是a1, a2, …, an , 即队列的修改是依先进先出的原则进行的,如图3 先进先出的原则进行的 即队列的修改是依先进先出的原则进行的,如图3-5所 示。 出队 a1 , a2 , … , an 入队
队首 队尾

图3-5 队列示意图

2 队列的抽象数据类型定义
ADT Queue{ 数据对象: 数据对象:D ={ ai|ai∈ElemSet, i=1, 2, …, n, n >= 0 }

数据关系: 数据关系:R = {<ai-1, ai> | ai-1, ai∈D, i=2,3,…,n } 约定a 端为队首, 端为队尾。 约定 1端为队首,an端为队尾。 基本操作: 基本操作: Create():创建一个空队列; :创建一个空队列; EmptyQue():若队列为空,则返回true ,否则返 :若队列为空,则返回 回flase ; ?? InsertQue(x) :向队尾插入元素 ; 向队尾插入元素x; DeleteQue(x) :删除队首元素 ; 删除队首元素x; } ADT Queue

3.3.2 队列的顺序表示和实现
利用一组连续的存储单元 一维数组 利用一组连续的存储单元(一维数组 依次存放从队 一组连续的存储单元 一维数组) 首到队尾的各个元素,称为顺序队列 顺序队列。 首到队尾的各个元素,称为顺序队列。 对于队列,和顺序栈相类似,也有动态和静态之分。 对于队列,和顺序栈相类似,也有动态和静态之分。 本部分介绍的是静态顺序队列 其类型定义如下: 静态顺序队列, 本部分介绍的是静态顺序队列,其类型定义如下: #define MAX_QUEUE_SIZE 100 typedef struct queue { ElemType Queue_array[MAX_QUEUE_SIZE] ; int front ; int rear ; }SqQueue;

3.3.2.1 队列的顺序存储结构 队列的顺序存储结构
设立一个队首指针 一个队尾指针 队尾指针rear ,分 设立一个队首指针front ,一个队尾指针 队首指针 别指向队首和队尾元素。 别指向队首和队尾元素。 初始化: ◆ 初始化:front=rear=0。 。 入队:将新元素插入rear所指的位置,然后 所指的位置, ◆ 入队:将新元素插入 所指的位置 然后rear加 加 1。 。 出队:删去front所指的元素,然后加 并返回被删 所指的元素, ◆ 出队:删去 所指的元素 然后加1并返回被删 元素。 元素。 队列为空: ◆ 队列为空:front=rear。 。 队满: ◆ 队满:rear=MAX_QUEUE_SIZE-1或front=rear。 或 。

在非空队列里,队首指针始终指向队头元素, 在非空队列里,队首指针始终指向队头元素,而 队尾指针始终指向队尾元素的下一位置。 队尾指针始终指向队尾元素的下一位置。 顺序队列中存在“假溢出”现象。 顺序队列中存在“假溢出”现象。因为在入队和 出队操作中,头、尾指针只增加不减小,致使被删除元 出队操作中, 尾指针只增加不减小, 素的空间永远无法重新利用。因此, 素的空间永远无法重新利用。因此,尽管队列中实际元 素个数可能远远小于数组大小, 素个数可能远远小于数组大小,但可能由于尾指针巳超 出向量空间的上界而不能做入队操作。该现象称为假溢 出向量空间的上界而不能做入队操作。该现象称为假溢 如图3 所示是数组大小为5的顺序队列中队首、 出。如图3-6所示是数组大小为5的顺序队列中队首、 队尾指针和队列中元素的变化情况。 队尾指针和队列中元素的变化情况。

Q.rear Q.rear Q.rear Q.front (a) 空队列 Q.front a3 a2 a1 Q.rear Q.front Q.front

a5 a4

(b) 入队 个元素 (c) 出队 个元素 入队3个元素 出队3个元素 图3-6 队列示意图

(d) 入队 个元素 入队2个元素

3.3.2.2

循环队列

为充分利用向量空间,克服上述“假溢出” 为充分利用向量空间,克服上述“假溢出”现象的 方法是:将为队列分配的向量空间看成为一个首尾相接 方法是:将为队列分配的向量空间看成为一个首尾相接 循环队列(Circular Queue)。 的圆环,并称这种队列为循环队列 。 的圆环,并称这种队列为循环队列 在循环队列中进行出队、入队操作时,队首、 在循环队列中进行出队、入队操作时,队首、队尾 指针仍要加1,朝前移动。只不过当队首、 指针仍要加 ,朝前移动。只不过当队首、队尾指针指 向向量上界(MAX_QUEUE_SIZE-1)时,其加 操作的 向向量上界 时 其加1操作的 结果是指向向量的下界0。 结果是指向向量的下界 。 这种循环意义下的加1操作可以描述为: 这种循环意义下的加 操作可以描述为: 操作可以描述为 if (i+1==MAX_QUEUE_SIZE) i=0; else i++ ; 其中: 代表队首指针 代表队首指针(front)或队尾指针 或队尾指针(rear) 其中: i代表队首指针 或队尾指针

用模运算可简化为: 用模运算可简化为: i=(i+1)%MAX_QUEUE_SIZE ; 显然,为循环队列所分配的空间可以被充分利用 显然, 除非向量空间真的被队列元素全部占用, ,除非向量空间真的被队列元素全部占用,否则不会上 因此,真正实用的顺序队列是循环队列。 溢。因此,真正实用的顺序队列是循环队列。 有循环队列QU[0,5], 例:设有循环队列QU[0,5],其初始状态是 front=rear=0,各种操作后队列的头、 front=rear=0,各种操作后队列的头、尾指针的状 态变化情况如下图3 所示。 态变化情况如下图3-7所示。 rear
front 0 5 4 3 rear 1 2 5 4 3 front

d

0

1

e
2 b 5

0 4 rear

1 2 b 3

front

g

g

(a) 空队列

(b) d, e, b, g入队 入

(c) d, e出队 出队

rear

rear

k j 5 i

0 4

1 2 b 3

front

k j 5

k
1 2 4 3 front

0

0 4

1 3

r
2 p rear

j 5 i

g

front

i

(d) i, j, k入队 入

(e) b, g出队 出队

(f) r, p, s, t入队 入队

图3-7 循环队列操作及指针变化情况

入队时尾指针向前追赶头指针, 入队时尾指针向前追赶头指针,出队时头指针向前 追赶尾指针,故队空和队满时头尾指针均相等。因此, 追赶尾指针,故队空和队满时头尾指针均相等。因此, 无法通过front=rear来判断队列 来判断队列“ 还是“ 无法通过front=rear来判断队列“空”还是“满”。 解决此问题的方法是:约定入队前, 解决此问题的方法是:约定入队前,测试尾指针在循环 意义下加1后是否等于头指针,若相等则认为队满。 意义下加1后是否等于头指针,若相等则认为队满。即: ◆ rear所指的单元始终为空。 rear所指的单元始终为空 所指的单元始终为空。

◆ 循环队列为空:front=rear 。 循环队列为空: ◆ 循环队列满: 循环队列满: (rear+1)%MAX_QUEUE_SIZE =front。 =front。

循环队列的基本操作
1 循环队列的初始化
SqQueue Init_CirQueue(void) { SqQueue Q ; Q.front=Q.rear=0; return(Q) ; }

2 入队操作
Status Insert_CirQueue(SqQueue Q , ElemType e)
/* 将数据元素e插入到循环队列 的队尾 将数据元素 插入到循环队列Q的队尾 插入到循环队列 */

{ if ((Q.rear+1)%MAX_QUEUE_SIZE== Q.front) return ERROR;
/* 队满,返回错误标志 队满, */

Q.Queue_array[Q.rear]=e ; /* 元素 入队 */ 元素e入队 Q.rear=(Q.rear+1)% MAX_QUEUE_SIZE ;
/* 队尾指针向前移动 */

return OK; }

/* 入队成功 */

3 出队操作
Status Delete_CirQueue(SqQueue Q, ElemType *x )
/* 将循环队列Q的队首元素出队 将循环队列 的队首元素出队 */

{ if (Q.front+1== Q.rear) return ERROR ;
/* 队空,返回错误标志 队空, */

*x=Q.Queue_array[Q.front] ; /* 取队首元素 */ Q.front=(Q.front+1)% MAX_QUEUE_SIZE ;
/* 队首指针向前移动 */

return OK ; }

3.3.3 队列的链式表示和实现
1 队列的链式存储表示
队列的链式存储结构简称为链队列,它是限制仅 队列的链式存储结构简称为链队列, 在表头进行删除操作和表尾进行插入操作的单链表。 在表头进行删除操作和表尾进行插入操作的单链表。 结点, 需要两类不同的结点:数据元素结点 队列的队首 需要两类不同的结点:数据元素结点,队列的队首 指针和队尾指针的结点 如图3 所示。 的结点, 指针和队尾指针的结点,如图3-8所示。 数据元素结点类型定义: 数据元素结点类型定义: typedef struct Qnode { ElemType }QNode ; data ; struct Qnode *next ;
data
数据元素结点

front rear
指针结点

图3-8 链队列结点示意图

指针结点类型定义: 指针结点类型定义: typedef struct link_queue { QNode *front , *rear ; }Link_Queue ;

2

链队运算及指针变化

链队的操作实际上是单链表的操作,只不过是删 链队的操作实际上是单链表的操作, 除在表头进行,插入在表尾进行。插入、 除在表头进行,插入在表尾进行。插入、删除时分别修 改不同的指针。链队运算及指针变化如图3 所示。 改不同的指针。链队运算及指针变化如图3-9所示。

front rear
(a) 空队列



front rear
(b) x入队 入队

x ∧

front rear

x
(c) y再入队 再入队

y ∧

front rear

x
(d) x出队 出队

y ∧

图3-9 队列操作及指针变化

3 链队列的基本操作
⑴ 链队列的初始化
LinkQueue *Init_LinkQueue(void) { LinkQueue *Q ; QNode *p ; p=(QNode *)malloc(sizeof(QNode)) ; /* 开辟头结点 */ p->next=NULL ; Q=(LinkQueue *)malloc(sizeof(LinkQueue)) ;
/* 开辟链队的指针结点 */

Q.front=Q.rear=p ; return(Q) ; }

⑵ 链队列的入队操作 链队列的入队操作
在已知队列的队尾插入一个元素e 修改队尾指 在已知队列的队尾插入一个元素 ,即修改队尾指 针(Q.rear)。 。 Status Insert_CirQueue(LinkQueue *Q , ElemType e)
/* 将数据元素e插入到链队列 的队尾 将数据元素 插入到链队列Q的队尾 插入到链队列 */

{ p=(QNode *)malloc(sizeof(QNode)) ; if (!p) return ERROR;
/* 申请新结点失败,返回错误标志 */ 申请新结点失败,

p->data=e ; p->next=NULL ; return OK; }

/* 形成新结点 */

Q.rear->next=p ; Q.rear=p ; /* 新结点插入到队尾 */

⑶ 链队列的出队操作
Status Delete_LinkQueue(LinkQueue *Q, ElemType *x) { QNode *p ; if (Q.front==Q.rear) return ERROR ; /* 队空 */ p=Q.front->next ; /* 取队首结点 */ *x=p->data ; Q.front->next=p->next ;
/* 修改队首指针 */

if (p==Q.rear) Q.rear=Q.front ;
/* 当队列只有一个结点时应防止丢失队尾指针 */

free(p) ; return OK ;

⑷ 链队列的撤消
void Destroy_LinkQueue(LinkQueue *Q )
/* 将链队列 的队首元素出队 */ 将链队列Q的队首元素出队

{ while (Q.front!=NULL) { Q.rear=Q.front->next;
/* 令尾指针指向队列的第一个结点 */

free(Q.front); Q.ront=Q.rear; } }

/* 每次释放一个结点 */

/* 第一次是头结点,以后是元素结点 */ 第一次是头结点,

习 题 三
1 设有一个栈,元素进栈的次序为a, b, c。问经过 设有一个栈,元素进栈的次序为a, c。 栈操作后可以得到哪些输出序列? 栈操作后可以得到哪些输出序列? 2 循环队列的优点是什么?如何判断它的空和满? 循环队列的优点是什么?如何判断它的空和满? 3 设有一个静态顺序队列,向量大小为MAX,判断 设有一个静态顺序队列,向量大小为MAX, 队列为空的条件是什么?队列满的条件是什么? 队列为空的条件是什么?队列满的条件是什么? 4 设有一个静态循环队列,向量大小为MAX,判断 设有一个静态循环队列,向量大小为MAX, 队列为空的条件是什么?队列满的条件是什么? 队列为空的条件是什么?队列满的条件是什么? 5 利用栈的基本操作,写一个返回栈S中结点个数的 利用栈的基本操作,写一个返回栈S 算法int 并说明S 算法int StackSize(SeqStack S) ,并说明S为何 不作为指针参数的算法 的算法? 不作为指针参数的算法?

6 一个双向栈S是在同一向量空间内实现的两个栈, 一个双向栈S是在同一向量空间内实现的两个栈, 它们的栈底分别设在向量空间的两端。 它们的栈底分别设在向量空间的两端。试为此双向栈设 计初始化InitStack(S) 入栈Push(S,i,x), 计初始化InitStack(S) ,入栈Push(S,i,x),出栈 Pop(S,i,x)算法 其中i Pop(S,i,x)算法,其中i为0或1 ,用以表示栈号。 算法, 用以表示栈号。 7 设Q[0,6]是一个静态顺序队列,初始状态为 Q[0,6]是一个静态顺序队列 是一个静态顺序队列, front=rear=0, front=rear=0,请画出做完下列操作后队列的头尾 指针的状态变化情况,若不能入对,请指出其元素, 指针的状态变化情况,若不能入对,请指出其元素,并 说明理由。 说明理由。 a, b, c, d入队 d入队 a, b, c出队 c出队 i , j , k , l , m入队 m入队 d, i出队 i出队 n, o, p, q, r入队 r入队

8 假设Q[0,5]是一个循环队列,初始状态为 假设Q[0,5]是一个循环队列 是一个循环队列, front=rear=0, front=rear=0,请画出做完下列操作后队列的头尾 指针的状态变化情况,若不能入对,请指出其元素, 指针的状态变化情况,若不能入对,请指出其元素,并 说明理由。 说明理由。 d, e, b, g, h入队 h入队 d, e出队 e出队 i , j , k , l , m入队 m入队 b出队 n, o, p, q, r入队 r入队

第4章 串
在非数值处理、 在非数值处理、事务处理等问题常涉及到一系列 的字符操作。 的字符操作。计算机的硬件结构主要是反映数值计算的 要求,因此,字符串的处理比具体数值处理复杂。 要求,因此,字符串的处理比具体数值处理复杂。本章 讨论串的存储结构及几种基本的处理。 讨论串的存储结构及几种基本的处理。

4.1 串类型的定义
4.1.1 串的基本概念
串(字符串):是零个或多个字符组成的有限序列。 字符串) 是零个或多个字符组成的有限序列。 …”,其中S是串名, (1≦ 记作: S=“ 记作: S=“a1a2a3…”,其中S是串名,ai(1≦i≦n) 是单个,可以是字母、数字或其它字符。 是单个,可以是字母、数字或其它字符。 串值:双引号括起来的字符序列是串值。 串值:双引号括起来的字符序列是串值。 串长:串中所包含的字符个数称为该串的长度。 串长:串中所包含的字符个数称为该串的长度。 空串(空的字符串) 长度为零的串称为空串, 空串(空的字符串):长度为零的串称为空串,它不 包含任何字符。 包含任何字符。 空格串(空白串) 空格串(空白串):构成串的所有字符都是空格的串 称为空白串。 称为空白串。

注意:空串和空白串的不同,例如“ 注意:空串和空白串的不同,例如“ ”和“”分别表 “”分别表 示长度为1的空白串和长度为0的空串。 示长度为1的空白串和长度为0的空串。 子串(substring) 子串(substring):串中任意个连续字符组成的子 序列称为该串的子串,包含子串的串相应地称为主串。 序列称为该串的子串,包含子串的串相应地称为主串。 子串的序号: 子串的序号:将子串在主串中首次出现时的该子串 的首字符对应在主串中的序号, 的首字符对应在主串中的序号,称为子串在主串中的序 或位置)。 号(或位置)。 例如,设有串A 分别是: 例如,设有串A和B分别是: A=“这是字符串”,B=“是” A=“这是字符串” B=“ 则B是A的子串,A为主串。B在A中出现了两次,其中 的子串, 为主串。 中出现了两次, 首次出现所对应的主串位置是3 因此, 首次出现所对应的主串位置是3。因此,称B在A中的序 号为3 号为3 。

特别地,空串是任意串的子串,任意串是其自身的 特别地,空串是任意串的子串, 子串。 子串。 串相等:如果两个串的串值相等(相同) 串相等:如果两个串的串值相等(相同),称这两个 串相等。换言之,只有当两个串的长度相等, 串相等。换言之,只有当两个串的长度相等,且各个对 应位置的字符都相同时才相等。 应位置的字符都相同时才相等。 通常在程序中使用的串可分为两种:串变量和串常 通常在程序中使用的串可分为两种: 量。 串常量和整常数、实常数一样, 串常量和整常数、实常数一样,在程序中只能被引 用但不能不能改变其值,即只能读不能写。通常串常量 用但不能不能改变其值,即只能读不能写。 是由直接量来表示的,例如语句错误( 溢出” 是由直接量来表示的,例如语句错误(“溢出”)中“溢 是直接量。 出”是直接量。 串变量和其它类型的变量一样,其值是可以改变。 串变量和其它类型的变量一样,其值是可以改变。

4.1.2 串的抽象数据类型定义
ADT String{ 数据对象: 数据对象:D = { ai|ai∈CharacterSet, i=1,2,…,n, n ≥0 } 数据关系: 数据关系:R = {<ai-1, ai>| ai-1, ai∈D, i=2,3,…,n } 基本操作: 基本操作: StrAssign(t , chars) 初始条件: 是一个字符串常量。 初始条件: chars是一个字符串常量。 是一个字符串常量 操作结果:生成一个值为 的串t 操作结果:生成一个值为chars的串 。 的串 StrConcat(s, t) 初始条件: 已存在。 初始条件:串s, t 已存在。

操作结果:将串 联结到串 后形成新串存放到s中 联结到串s后形成新串存放到 操作结果:将串t联结到串 后形成新串存放到 中。 StrLength(t) 初始条件:字符串 已存在 已存在。 初始条件:字符串t已存在。 操作结果:返回串 中的元素个数 称为串长。 中的元素个数, 操作结果:返回串t中的元素个数,称为串长。 SubString (s, pos, len, sub) 初始条件: 已存在, ≦ ≦ 初始条件:串s, 已存在 1≦pos≦StrLength(s)且 且 0≦len≦StrLength(s) –pos+1。 ≦ ≦ 。 操作结果: 返回串s的第 个字符起长度为len 操作结果:用sub返回串 的第 个字符起长度为 返回串 的第pos个字符起长度为 的子串。 的子串。 …… } ADT String

4.2 串的存储表示和实现
串是一种特殊的线性表,其存储表示和线性表类似, 串是一种特殊的线性表,其存储表示和线性表类似, 但又不完全相同。 但又不完全相同。串的存储方式取决于将要对串所进行 的操作。串在计算机中有3种表示方式: 的操作。串在计算机中有3种表示方式: ◆ 定长顺序存储表示:将串定义成字符数组,利用 定长顺序存储表示:将串定义成字符数组, 串名可以直接访问串值。用这种表示方式, 串名可以直接访问串值。用这种表示方式,串的存 储空间在编译时确定,其大小不能改变。 储空间在编译时确定,其大小不能改变。 ◆ 堆分配存储方式:仍然用一组地址连续的存储单 堆分配存储方式: 元来依次存储串中的字符序列, 元来依次存储串中的字符序列,但串的存储空间是 在程序运行时根据串的实际长度动态分配的。 在程序运行时根据串的实际长度动态分配的。 ◆ 块链存储方式:是一种链式存储结构表示。 块链存储方式:是一种链式存储结构表示。

4.2.1 串的定长顺序存储表示
这种存储结构又称为串的顺序存储结构。 这种存储结构又称为串的顺序存储结构。是用一 组连续的存储单元来存放串中的字符序列。 组连续的存储单元来存放串中的字符序列。所谓定长顺 序存储结构,是直接使用定长的字符数组来定义,数组 序存储结构,是直接使用定长的字符数组来定义, 的上界预先确定。 的上界预先确定。 定长顺序存储结构定义为: 定长顺序存储结构定义为: #define MAX_STRLEN 256 typedef struct { char str[MAX_STRLEN] ; int length; } StringType ;

1 串的联结操作
Status StrConcat ( StringType s, StringType t)
/* 将串t联结到串s之后,结果仍然保存在s 将串t联结到串s之后,结果仍然保存在s中 */

{ int i, j ; if ((s.length+t.length)>MAX_STRLEN) Return ERROR ;
/* 联结后长度超出范围 */

for (i=0 ; i<t.length ; i++) s.str[s.length+i]=t.str[i] ;
到串s 到串s之后 */ /* 串t联结

s.length=s.length+t.length ; /* 修改联结
后的串长度 */

return OK ;

2

求子串操作

Status SubString (StringType s, int pos, int (StringType len, StringType *sub) { int k, j ; if (pos<1||pos>s.length||len<0||len>(s. lengthlength-pos+1)) return ERROR ;
度 */ /* 参数非法 */ /* 求得子串长

sub->length=lensub->length=len-pos+1 ;

for (j=0, k=pos ; k<=leng ; k++, j++) subsub->str[j]=s.str[i] ;
得子串 */ /* 逐个字符复制求

4.2.2 串的堆分配存储表示
实现方法: 实现方法:系统提供一个空间足够大且地址连续的 供串使用。可使用C语言的动态 存储空间(称为“ 存储空间(称为“堆”)供串使用。可使用 语言的动态 存储分配函数malloc()和free()来管理。 存储分配函数 和 来管理。 特点是: 特点是:仍然以一组地址连续的存储空间来存储字 符串值, 符串值,但其所需的存储空间是在程序执行过程中动态 分配,故是动态的,变长的。 分配,故是动态的,变长的。 串的堆式存储结构的类型定义 typedef struct { char *ch; int length; } HString ;
/* 若非空,按长度分配,否则为NULL */ 若非空,按长度分配,否则为 /* 串的长度 */

1 串的联结操作
Status Hstring *StrConcat(HString *T, HString *s1, HString *s2)
/* 用T返回由s1和s2联结而成的串 */ 返回由s1和s2联结而成的串

{

int k, j , t_len ; if (T.ch) free(T);
/* 释放旧空间 */

t_len=s1->length+s2t_len=s1->length+s2->length ; if ((p=(char *)malloc(sizeof((char)*t_len))==NUL L) { printf(“系统空间不够,申请空间失败 ! printf(“系统空间不够, \n ” ) ; return ERROR ; }

for (k=s1->length, j=0 ; j<s2->length; (k=s1j<s2k++, j++) T->ch[j]=s1->ch[j] ; /* 将串s2复制到 >ch[j]=s1将串s2复制到
串T中 */

free(s1free(s1->ch) ; free(s2free(s2->ch) ; return OK ;

}

4.2.3 串的链式存储表示
串的链式存储结构和线性表的串的链式存储结构类 采用单链表来存储串,结点的构成是: 似,采用单链表来存储串,结点的构成是: ◆ data域:存放字符,data域可存放的字符个数称为 域 存放字符, 域可存放的字符个数称为 结点的大小; 结点的大小; ◆ next域:存放指向下一结点的指针。 域 存放指向下一结点的指针。 若每个结点仅存放一个字符, 若每个结点仅存放一个字符,则结点的指针域就非 常多,造成系统空间浪费,为节省存储空间, 常多,造成系统空间浪费,为节省存储空间,考虑串结 构的特殊性,使每个结点存放若干个字符, 构的特殊性,使每个结点存放若干个字符,这种结构称 为块链结构。 是块大小为3的串的块链式存储结 为块链结构。如图4-1是块大小为 的串的块链式存储结 是块大小为 构示意图。 构示意图。

head

a b c

e p c

??

g @ @?

图4-1 串的块链式存储结构示意图

串的块链式存储的类型定义包括: 串的块链式存储的类型定义包括: ⑴ 块结点的类型定义 #define BLOCK_SIZE 4 typedef struct Blstrtype { char data[BLOCK_SIZE] ; struct Blstrtype *next; }BNODE ;

(2) 块链串的类型定义 typedef struct { BNODE head; int Strlen ; } Blstring ; 在这种存储结构下, 在这种存储结构下,结点的分配总是完整的结点为 单位,因此,为使一个串能存放在整数个结点中, 单位,因此,为使一个串能存放在整数个结点中,在串 的末尾填上不属于串值的特殊字符,以表示串的终结。 的末尾填上不属于串值的特殊字符,以表示串的终结。 当一个块(结点 内存放多个字符时,往往会使操作 当一个块 结点)内存放多个字符时, 结点 内存放多个字符时 过程变得较为复杂, 过程变得较为复杂,如在串中插入或删除字符操作时通 常需要在块间移动字符。 常需要在块间移动字符。
/* 头指针 */ /* 当前长度 */

4.3 串的模式匹配算法
模式匹配(模范匹配) 模式匹配(模范匹配):子串在主串中的定位称为模
式匹配或串匹配(字符串匹配) 式匹配或串匹配(字符串匹配) 。模式匹配成功是指在 主串S中能够找到模式串T 否则,称模式串T在主串S 主串S中能够找到模式串T,否则,称模式串T在主串S 中不存在。 中不存在。 模式匹配的应用在非常广泛。例如,在文本编辑 模式匹配的应用在非常广泛。例如, 程序中, 程序中,我们经常要查找某一特定单词在文本中出现的 位置。显然, 位置。显然,解此问题的有效算法能极大地提高文本编 辑程序的响应性能。 辑程序的响应性能。 模式匹配是一个较为复杂的串操作过程。迄今为止, 模式匹配是一个较为复杂的串操作过程。迄今为止, 人们对串的模式匹配提出了许多思想和效率各不相同的 计算机算法。介绍两种主要的模式匹配算法。 计算机算法。介绍两种主要的模式匹配算法。

4.3.1 Brute-Force模式匹配算法 模式匹配算法
设S为目标串,T为模式串,且不妨设: 为目标串, 为模式串,且不妨设: S=“s0s1s2…sn-1” , T=“t0t1t2 …tm-1” S=“ T=“ 串的匹配实际上是对合法的位置0 串的匹配实际上是对合法的位置0≦i≦n-m依次 将目标串中的子串s[i…i+m-1]和模式串 和模式串t[0… 将目标串中的子串s[i…i+m-1]和模式串t[0…m-1] 进行比较: 进行比较: ◆ 若s[i…i+m-1]=t[0…m-1]:则称从位置i s[i…i+m-1]=t[0… 1]:则称从位置i 开始的匹配成功,亦称模式t在目标s中出现; 开始的匹配成功,亦称模式t在目标s中出现; ◆ 若s[i…i+m-1]≠t[0…m-1]:从i开始的匹 s[i…i+m-1]≠t[0… 1]: 配失败。位置i称为位移, s[i…i+m配失败。位置i称为位移,当s[i…i+m1]=t[0… 1]=t[0…m-1]时,i称为有效位移;当 1]时 称为有效位移; s[i…i+ms[i…i+m-1] ≠t[0…m-1]时,i称为无效位移。 ≠t[0… 1]时 称为无效位移。

这样,串匹配问题可简化为找出某给定模式T在给 问题可简化为找出某给定模式T 这样,串匹配问题可简化为找出某给定模式 定目标串S中首次出现的有效位移 的有效位移。 定目标串S中首次出现的有效位移。

算法实现
int IndexString(StringType s , StringType t , int pos )
/* /* /* 采用顺序存储方式存储主串s和模式t 采用顺序存储方式存储主串s和模式t, 返回位置,否则返回-1 返回位置,否则返回*/ */ 若模式t在主串s中从第pos位置开始有匹配的子串, 若模式t在主串s中从第pos位置开始有匹配的子串,*/ pos位置开始有匹配的子串

{ char *p , *q ; int k , j ; k=posk=pos-1 ; j=0 ; p=s.str+pos-1 ; p=s.str+posq=t.str ;
/* 初始匹配位置设置 */

while (k<s.length)&&(j<t.length) { if (*p==*q) j++ ; } { p++ ; q++ ; k++ ;

else { k=k-j+1 ; j=0 ; q=t.str ; k=kp=s.str+k ; }
/* 重新设置匹配位置 */

} if (j==t.length) return(kreturn(k-t.length) ;
*/ /* 匹配,返回位置 匹配, */

else return(-1) ; return(}

/*

不匹配,返回不匹配,返回-1

该算法简单,易于理解。在一些场合的应用里, 该算法简单,易于理解。在一些场合的应用里, 如文字处理中的文本编辑,其效率较高。 如文字处理中的文本编辑,其效率较高。 该算法的时间复杂度为O(n*m) 其中n 该算法的时间复杂度为O(n*m) ,其中n 、m 分别是主串和模式串的长度。通常情况下, 分别是主串和模式串的长度。通常情况下,实际运行过 程中,该算法的执行时间近似于O(n+m) 程中,该算法的执行时间近似于O(n+m) 。

理解该算法的关键点
当第一次s 当第一次sk≠tj时:主串要退回到k-j+1的位置,而 主串要退回到k j+1的位置 的位置, 模式串也要退回到第一个字符( j=0的位置 的位置)。 模式串也要退回到第一个字符(即j=0的位置)。 则应该有s 比较出现s 比较出现sk≠tj时:则应该有sk-1=tj-1,…,skj+1=t1, sk-j=t0 。

4.3.2 模式匹配的一种改进算法
该改进算法是由D.E.Knuth J.H.Morris和 该改进算法是由D.E.Knuth ,J.H.Morris和 V.R.Pratt提出来的 简称为KMP算法 V.R.Pratt提出来的,简称为KMP算法。其改进在于: 提出来的, 算法。 改进在于: 每当一趟匹配过程出现字符不相等时, 每当一趟匹配过程出现字符不相等时,主串指示 器不用回溯,而是利用已经得到的“部分匹配”结果, 器不用回溯,而是利用已经得到的“部分匹配”结果, 将模式串的指示器向右“滑动”尽可能远的一段距离后, 将模式串的指示器向右“滑动”尽可能远的一段距离后, 继续进行比较。 继续进行比较。

例:设有串s=“abacabab” ,t=“abab” 。则第一 设有串s=“abacabab” t=“abab”
次匹配过程如图4 所示。 次匹配过程如图4-2所示。
s=“a b cbb” || || ≠ t=“a b b” i=3 j=3 匹配失败

图4-2 模式匹配示例

在i=3和j=3时,匹配失败。但重新开始第二次 i=3和j=3时 匹配失败。 匹配时,不必从i=1 j=0开始 因为s 开始。 匹配时,不必从i=1 ,j=0开始。因为s1=t1,t0≠t1, 必有s 又因为t 所以必有s 必有s1≠t0,又因为t0=t2,s2=t2,所以必有s2=t0。 由此可知,第二次匹配可以直接从i=3 j=1开始 开始。 由此可知,第二次匹配可以直接从i=3 、j=1开始。 总之,在主串s与模式串t的匹配过程中,一旦出现 总之,在主串s与模式串t的匹配过程中, 主串s的指针不必回溯, si≠tj ,主串s的指针不必回溯,而是直接与模式串的 tk(0≦k<j进行比较,而k的取值与主串s无关,只与 (0≦k<j进行比较 进行比较, 的取值与主串s无关, 模式串t本身的构成有关,即从模式串t可求得k 模式串t本身的构成有关,即从模式串t可求得k值。)

不失一般性,设主串s=“s1s2…sn” ,模式串 不失一般性, 主串s=“ t=“t1 t2 …tm” 。 t=“ (1≦ j<m,m<n)时 当si≠tj(1≦i≦n-m,1≦j<m,m<n)时,主 的指针i不必回溯,而模式串t的指针j 串s的指针i不必回溯,而模式串t的指针j回溯到第 k(k<j)个字符继续比较 则模式串t的前k k(k<j)个字符继续比较,则模式串t的前k-1个字符必 个字符继续比较, 须满足4 而且不可能存在k >k满足 满足4 须满足4-1式,而且不可能存在k’>k满足4-1式。 t1t2…tk-1= si-(k-1) si-(k-2) … si-2 si-1 (k(k(4-1) (4部分匹配”的结果为: 而已经得到的 “部分匹配”的结果为: tj-(k-1) tj-k… tj-1=si-(k-1) si-(k-2) … si-2 si-1 (k(k(k(4-2) (4由式(4-1)和式 -2)得 和式(4 由式(4-1)和式(4-2)得: t1t2…tk-1=tj-(k-1) tj-k… tj-1 (k(4-3) (4-

i 主串s 模式串t k
图4-3 KMP算法示例 算法示例

j

定义next[j]函数为 函数为 定义
0 当j=1时 时 其它情况 next[j]= Max{k|1<k<j∧t1t2…tk-1=tj-(k-1) tj-k… tj-1 } 该集合不空时 ∧ 1

在求得了next[j]值之后 KMP算法的思想是 在求得了next[j]值之后,KMP算法的思想是: 值之后, 算法的思想是: 设目标串(主串) 设目标串(主串)为s,模式串为t ,并设i指针和j指 模式串为t 并设i指针和j 针分别指示目标串和模式串中正待比较的字符, 针分别指示目标串和模式串中正待比较的字符,设i和j 的初值均为1 若有s 分别加1 否则, 的初值均为1。若有si=tj,则i和j分别加1。否则,i不 退回到j=next[j]的位置 再比较s 的位置, 若相等, 变,j退回到j=next[j]的位置,再比较si和tj,若相等, 分别加1 否则, 不变, 则i和j分别加1。否则,i不变,j再次退回到 j=next[j]的位置 依此类推。直到下列两种可能: j=next[j]的位置,依此类推。直到下列两种可能: 的位置, (1) j退回到某个下一个[j]值时字符比较相等,则 j退回到某个下一个 值时字符比较相等 退回到某个下一个[j]值时字符比较相等, 指针各自加1继续进行匹配。 指针各自加1继续进行匹配。 ?退回到j=0,将i和j分别加1,即从主串的下一个 退回到j=0, 分别加1 字符s 模式串的t 重新开始匹配。 字符si+1模式串的t1重新开始匹配。

KMP算法如下 KMP算法如下

#define Max_Strlen 1024 int next[Max_Strlen]; int KMP_index (StringType s , StringType t)
/* 用KMP算法进行模式匹配,匹配返回位置,否则返回-1 KMP算法进行模式匹配 匹配返回位置,否则返回算法进行模式匹配, */ /*用静态存储方式保存字符串, s和t分别表示主串和模式串 /*用静态存储方式保存字符串 用静态存储方式保存字符串, */

{

int k=0 , j=0 ; /*初始匹配位置设置 */ /*初始匹配位置设置 while (k<s.length)&&(j<t.length { if ((j==-1)|| (s. str[k]==t.str[j])) ((j=={ k++ ; j++ ; } else j=next[j] ; } if (j>= t.length) return(k-t.length) ; return(k-

很显然,KMP_index函数是在已知下一个函数 很显然,KMP_index函数是在已知下一个函数 值的基础上执行的,以下讨论如何求next函数值 函数值? 值的基础上执行的,以下讨论如何求next函数值? 由式(4-3)知 求模式串的next[j]值与主串 由式(4-3)知,求模式串的next[j]值与主串s 值与主串s 无关,只与模式串t本身的构成有关,则可把求next函 无关,只与模式串t本身的构成有关,则可把求next函 数值的问题看成是一个模式匹配问题。 next函数定 数值的问题看成是一个模式匹配问题。由next函数定 义可知: 义可知: 当j=1时:next[1]=0。 j=1时 next[1]=0。 设next[j]=k,即在模式串中存在:t1t2…tknext[j]=k,即在模式串中存在: 其中下标k满足1<k<j的某 1=tj-(k-1)tj-k… tj-1 ,其中下标k满足1<k<j的某 (k个最大值,此时求next[j+1]的值有两种可能 的值有两种可能: 个最大值,此时求next[j+1]的值有两种可能: 则表明在模式串中有: ⑴ 若有tk=tj :则表明在模式串中有: 若有t t1t2…tk-1tk=tj-(k-1)tj-k… tj-1 tj,且不可能存 (k>k满足上式 满足上式, 在k’>k满足上式,即: next[j+1]=next[j]+1=k+1

(2) 若有tk≠tj :则表明在模式串中有:t1 t2…tk若有t 则表明在模式串中有: 时应将模式向 1 tk≠tj-(k-1) tj-k… tj-1 tj ,当tk≠tj时应将模式向 (k右滑动至以模式中的第 至以模式中的第next[k]个字符和主串中的 右滑动至以模式中的第next[k]个字符和主串中的 个字符相比较。 k’ 第j个字符相比较。若next[k]= k’,且tj = tk’, 则说明在主串中第j+1字符之前存在一个长度为 字符之前存在一个长度为k 则说明在主串中第j+1字符之前存在一个长度为k’( next[k])的最长子串 的最长子串, 即next[k])的最长子串,与模式串中从第一个字 符起长度为k 的子串相等。 符起长度为k’的子串相等。即 next[j+1]=k’ next[j+1]=k’+1 同理,若tj≠tk,应将模式继续向右滑动至将模式 将模式继续向右滑动至将模式 同理, 中的第next[k’ 个字符和t 对齐,??,依此类推, 中的第next[k’]个字符和tj对齐,??,依此类推,直 到tj和模式串中的某个字符匹配成功或者不存在任何 k’(1< k’<j)满足等式:t1 t2…tk-1 tk’=tj-(k’’-1) tj-k’… k’<j)满足等式 满足等式: (k tj-1 tj 则: next[j]+1=1

根据上述分析, 求next函数值的算法如下: 函数值的算法如下: 根据上述分析, next函数值的算法如下 void next(StringType t , int next[])
/* 求模式t的next串t函数值并保存在next数组中 求模式t next串 函数值并保存在next数组中 */

{

int k=1 , j=0 ; next[1]=0; while (k<t.length) { if ((j==0)|| (t.str[k]==t.str[j])) { k++ ; j++ ; if ( t.str[k]!=t.str[j] )
next[k]=j; else next[k]=next[j];

} else next[j]=j ; } }

习 题 四
⑴ 解释下列每对术语的区别:空串和空白串;主串 解释下列每对术语的区别:空串和空白串; 和子串;目标串和模式串。 和子串;目标串和模式串。 ⑵ 若x和y是两个采用顺序结构存储的串,写一算法 是两个采用顺序结构存储的串, 比较这两个字符串是否相等。 比较这两个字符串是否相等。 ⑶ 写一算法void StrRelace(char *T, char 写一算法void *P, char *S),将T中第一次出现的与P相等的子串 *S), 中第一次出现的与P 替换为S 的长度不一定相等, 替换为S,串S和P的长度不一定相等,并分析时间复杂 度。

第5章 数组和广义表
数组是一种人们非常熟悉的数据结构,几乎所有 数组是一种人们非常熟悉的数据结构, 的程序设计语言都支持这种数据结构或将这种数据结 构设定为语言的固有类型。数组这种数据结构可以看 构设定为语言的固有类型。数组这种数据结构可以看 是线性表的推广。 成是线性表的推广。 科学计算中涉及到大量的矩阵问题,在程序设计 科学计算中涉及到大量的矩阵问题, 语言中一般都采用数组来存储, 语言中一般都采用数组来存储,被描述成一个二维数 当矩阵规模很大且具有特殊结构(对角矩阵、 组。但当矩阵规模很大且具有特殊结构(对角矩阵、三 角矩阵、对称矩阵、稀疏矩阵等) 角矩阵、对称矩阵、稀疏矩阵等),为减少程序的时间 和空间需求,采用自定义的描述方式。 和空间需求,采用自定义的描述方式。 广义表是另一种推广形式的线性表, 广义表是另一种推广形式的线性表,是一种灵活 是另一种推广形式的线性表 的数据结构,在许多方面有广泛的应用。 的数据结构,在许多方面有广泛的应用。

5.1 数组的定义
数组是一组偶对 下标值,数据元素值)的集合。 数组是一组偶对(下标值,数据元素值)的集合。 是一组偶对( 在数组中,对于一组有意义的下标, 在数组中,对于一组有意义的下标,都存在一个与其对 应的值。一维数组对应着一个下标值, 应的值。一维数组对应着一个下标值,二维数组对应着 两个下标值,如此类推。 两个下标值,如此类推。 数组是由 数组是由n(n>1)个具有相同数据类型的数据元素 是由n(n>1)个具有相同数据类型的数据元素 a1,a2,…,an组成的有序序列,且该序列必须存储在 组成的有序序列,且该序列必须存储在 一块地址连续的存储单元中。 一块地址连续的存储单元中。 ◆ 数组中的数据元素具有相同数据类型。 数组中的数据元素具有相同数据类型 具有相同数据类型。 ◆ 数组是一种随机存取结构,给定一组下标,就可 数组是一种随机存取结构,给定一组下标, 以访问与其对应的数据元素。 以访问与其对应的数据元素。 ◆ 数组中的数据元素个数是固定的。 数组中的数据元素个数是固定的。

5.1.1 数组的抽象数据类型定义 数组的抽象数据类型定义
1 抽象数据类型定义
ADT Array{ 数据对象: 数据对象:ji= 0,1,…,bi-1 , 1,2, …,n ; D = { aj1j2…jn | n>0称为数组的维数,bi是数组第 维的 称为数组的维数, 是数组第i维的 称为数组的维数 长度,ji是数组元素第i维的下标,aj1j2…jn∈ElemSet 长度, 是数组元素第 维的下标, 维的下标 } 数据关系: 数据关系:R = {R1, R2, …, Rn} Ri={<aj1j2 …ji…jn , aj1j2 …ji+1…jn>|0≦jk≦bk-1 , ≦ 1≦k≦n且k≠i,0≦ji≦bi-2, aj1j2 …ji+1…jn∈D } ≦ ≦ 且 , ≦ , 基本操作: 基本操作: …… } ADT Array

由上述定义知, 维数组中有b 由上述定义知,n维数组中有b1×b2 × … × bn个 数据元素,每个数据元素都受到n维关系的约束。 数据元素,每个数据元素都受到n维关系的约束。

2

直观的n 直观的n维数组

以二维数组为例讨论。将二维数组看成是一个定长 以二维数组为例讨论。 的线性表, 每个元素又是一个定长的线性表。 的线性表,其每个元素又是一个定长的线性表。 设二维数组A=(a 设二维数组A=(aij)m×n,则 A=(α A=(α1,α2,…,αp) (p=m或 (p=m或n) 1≦ 1 ≦ j≦ n 1≦ 1≦ i ≦ m 其中每个数据元素α 是一个列向量(线性表) 其中每个数据元素αj是一个列向量(线性表) : =(a αj =(a1j ,a2j ,…,amj) 或是一个行向量: 是一个行向量: αi =(ai1 ,ai2 ,…,ain) =(a 如图5 所示。 如图5-1所示。

a11 a12 … a1n a11 a12 … a1n a21 a22 … a2n A= … … … … … am1 am2 … amn
(a) 矩阵表示形式 矩阵表示形式

a21 a22 … a2n A= …………… am1 am2 … amn
列向量的一维数组形式

(b)

A=

a11 a21 ┆ am1
(c)

a12 a1n a22 ┆ a2n ┆ ┆ ┆ am2 ┆ amn

行向量的一维数组形式

二维数组图例形式 图5-1 二维数组图例形式

5.2 数组的顺序表示和实现 数组的顺序表示和实现
数组一般不做插入和删除操作,也就是说,数组 数组一般不做插入和删除操作,也就是说, 一旦建立, 一旦建立,结构中的元素个数和元素间的关系就不再发 生变化。因此,一般都是采用顺序存储的方法来表示数 生变化。因此,一般都是采用顺序存储的方法来表示数 组。

问题:计算机的内存结构是一维 线性)地址结构, 问题:计算机的内存结构是一维(线性)地址结构, 内存结构是一维(
对于多维数组,将其存放(映射)到内存一维结构时, 对于多维数组,将其存放(映射)到内存一维结构时,有 次序约定问题。 个次序约定问题。即必须按某种次序将数组元素排成一 列序列,然后将这个线性序列存放到内存中。 列序列,然后将这个线性序列存放到内存中。 二维数组是最简单的多维数组, 二维数组是最简单的多维数组,以此为例说明多维 数组存放(映射)到内存一维结构时的次序约定问题 次序约定问题。 数组存放(映射)到内存一维结构时的次序约定问题。

通常有两种顺序存储方式 ⑴ 行优先顺序(Row Major Order) :将数 行优先顺序( Order)
组元素按行排列,第i+1个行向量紧接在第i个行向量 个行向量紧接在第i 组元素按行排列, i+1个行向量紧接在第 后面。对二维数组,按行优先顺序存储的线性序列为: 后面。对二维数组,按行优先顺序存储的线性序列为: a11,a12,…,a1n, a21,a22,…a2n ,……, ……, am1,am2,…,amn PASCAL、 是按行优先顺序存储的,如图5 PASCAL、C是按行优先顺序存储的,如图52(b)示 2(b)示。

⑵ 列优先顺序(Column Major Order) : 列优先顺序( Order)
将数组元素按列向量排列,第j+1个列向量紧接在第j 个列向量紧接在第j 将数组元素按列向量排列, j+1个列向量紧接在第 个列向量之后,对二维数组,按列优先顺序存储的线性 个列向量之后,对二维数组, 序列为: 序列为: a11,a21,…,am1, a12,a22,…am2, ……, ……,

… a11 a12 … a1n a21 a22 … a2n A= … … … … … am1 am2 … amn
(a) 二维数组的表示形式


第 1 行 第 2 行 a11 a21 … am1 a12 a22 … am2 第 1 列 第 2 列

a11 a12 … a1n a21 a22 … a2n




第 m 行




第 n 列

am1 am2 … Amn

a1m a2m … amn

二维数组及其顺序存储图例形式 图5-2 二维数组及其顺序存储图例形式





(b) 行优先顺序存储

(c) 列优先顺序存储

设有二维数组A=(a 设有二维数组A=(aij)m×n,若每个元素占用的存储 单元数为l 表示元素a 的首地址, 单元数为l(个),LOC[a11]表示元素a11的首地址,即 数组的首地址 首地址。 数组的首地址。

1

以“行优先顺序”存储 行优先顺序”
⑴ 第1行中的每个元素对应的(首)地址是: 行中的每个元素对应的 每个元素对应的( 地址是: LOC[a1j]=LOC[a11]+(j-1)×l ]+(j-1)× j=1,2, …,n (2) 第2行中的每个元素对应的(首)地址是: 行中的每个元素对应的 每个元素对应的( 地址是: LOC[a2j]=LOC[a11]+n×l +(j-1)×l ]+n× +(j-1)× j=1,2, …,n ……… ⑶ 第m行中的每个元素对应的(首)地址是: 行中的每个元素对应的 每个元素对应的( 地址是: LOC[a ]=LOC[a ]+(m-1)×n×l +(j]+(m-1)× +(j-

由此可知,二维数组中任一元素 由此可知,二维数组中任一元素aij的(首)地址是: 任一元素a 地址是 LOC[aij]=LOC[a11]+[(i-1)×n +(j-1)]×l ]+[(i-1)× +(j-1)]× (5-1) (5i=1,2, …,m j=1,2, …,n 根据(5-1)式 对于三维数组A=(a 根据(5-1)式,对于三维数组A=(aijk)m×n×p, 若每个元素占用的存储单元数为l 若每个元素占用的存储单元数为l(个),LOC[a111]表 示元素a 的首地址, 数组的首地址 首地址。 示元素a111的首地址,即数组的首地址。以“行优先顺 存储在内存中。 序”存储在内存中。 三维数组中任一元素a 三维数组中任一元素aijk的(首)地址是: 地址是: ]+[(i-1)× p+(jLOC(aijk)=LOC[a111]+[(i-1)×n×p+(j1)×p+(k-1)]×l (5-2) 1)×p+(k-1)]× (5推而广之, 推而广之,对n维数组A=(aj1j2…jn) ,若每个元 维数组A=(a 素占用的存储单元数为l 素占用的存储单元数为l(个),LOC[a11 …1]表示元素

n维数组中任一元素aj1j2…jn的(首)地址是: 维数组中任一元素a 地址是: LOC[aj1j2…jn]=LOC[a11 …1]+[(b2×…×bn)×(j1-1) + (b3×…×bn)×(j2-1)+ … + bn×(jn-1-1)+ (jn-1)] ×l (5-3) (5-

2

以“列优先顺序”存储 列优先顺序”
⑴ 第1列中的每个元素对应的(首)地址是: 列中的每个元素对应的 每个元素对应的( 地址是: ]+(j-1)× LOC[aj1]=LOC[a11]+(j-1)×l j=1,2, …,m (2) 第2列中的每个元素对应的(首)地址是: 列中的每个元素对应的 每个元素对应的( 地址是: LOC[aj2]=LOC[a11]+m×l +(j-1)×l ]+m× +(j-1)× j=1,2, …,m ……… ⑶ 第n列中的每个元素对应的(首)地址是: 列中的每个元素对应的 每个元素对应的( 地址是: LOC[ajn]=LOC[a11]+ (n-1)×m×l +(j1)× +(j1)×l 1)× j=1,2, …,m 由此可知,二维数组中任一元素 由此可知,二维数组中任一元素aij的(首)地址是: 任一元素a 地址是 LOC[a ]=LOC[a ]+[(i-1)×m+(j-1)]×l ]+[(i-1)×m+(j-1)]×

5.3 矩阵的压缩存储
在科学与工程计算问题中,矩阵是一种常用的数 在科学与工程计算问题中, 学对象,在高级语言编程时, 学对象,在高级语言编程时,通常将一个矩阵描述为一 个二维数组。这样,可以对其元素进行随机存取, 个二维数组。这样,可以对其元素进行随机存取,各种 矩阵运算也非常简单。 矩阵运算也非常简单。 对于高阶矩阵 若其中非零元素呈某种规律分布 对于高阶矩阵,若其中非零元素呈某种规律分布或 高阶矩阵, 非零元素呈某种规律分布或 矩阵中有大量的零元素,若仍然用常规方法存储, 者矩阵中有大量的零元素,若仍然用常规方法存储,可 能存储重复的非零元素或零元素, 能存储重复的非零元素或零元素,将造成存储空间的大 量浪费。对这类矩阵进行压缩存储: 量浪费。对这类矩阵进行压缩存储: ◆ 多个相同的非零元素只分配一个存储空间; 多个相同的非零元素只分配一个存储空间; ◆ 零元素不分配空间。 零元素不分配空间。

5.3.1 特殊矩阵
特殊矩阵: 特殊矩阵:是指非零元素或零元素的分布有一定规律
的矩阵。 的矩阵。

1

对称矩阵

若一个n阶方阵A=(a 若一个n阶方阵A=(aij)n×n中的元素满足性质: 中的元素满足性质: aij=aji 1≦i,j≦n且i≠j i,j≦ 则称A为对称矩阵,如图5 所示。 则称A为对称矩阵,如图5-3所示。
1 5 A= 1 3 7 5 0 8 0 0 1 8 9 2 6 3 0 2 5 1 7 0 6 1 3 a11 a21 a22 A= a31 a32 a33 ……… … an1 an2 … ann

图5-3 对称矩阵示例

对称矩阵中的元素关于主对角线对称 因此, 对称矩阵中的元素关于主对角线对称,因此,让 元素关于主对角线对称, (i≠j)分配一个存储空间 分配一个存储空间, 每一对对称元素a 每一对对称元素aij和aji(i≠j)分配一个存储空间,则 n2个元素压缩存储到n(n+1)/2个存储空间,能节约 个元素压缩存储到n(n+1)/2个存储空间 个存储空间, 近一半的存储空间。 近一半的存储空间。 不失一般性,假设按“行优先顺序”存储下三角 不失一般性,假设按“行优先顺序” 包括对角线)中的元素。 形(包括对角线)中的元素。 设用一维数组(向量)sa[0…n(n+1)/2]存储 设用一维数组(向量)sa[0…n(n+1)/2]存储n 存储n 阶对称矩阵,如图5-4所示。为了便于访问,必须找出 阶对称矩阵,如图5 所示。为了便于访问, 矩阵A中的元素的下标值(i,j)和向量sa[k]的 矩阵A中的元素的下标值(i,j)和向量sa[k]的下标值 k之间的对应关系。 之间的对应关系。
K 1 sa 2 3 4 … n(n-1)/2 … n(n+1)/2 a11 a21 a22 a31 a32 a33 … an1 an2 … ann
对称矩阵的压缩存储示例 图5-4 对称矩阵的压缩存储示例

若i≧j:ai j在下三角形中,直接保存在 中。ai j之 ≧ : 在下三角形中,直接保存在sa中 前的i-1行共有元素个数 行共有元素个数: 前的 行共有元素个数: 1+2+…+(i-1)=i×(i-1)/2 × 而在第i行上, 之前恰有j-1个元素 因此,元素a 个元素, 而在第 行上,ai j之前恰有 个元素,因此,元素 i j保 行上 在向量sa中时的下标值k之间的对应关系 中时的下标值 之间的对应关系是 存在向量 中时的下标值 之间的对应关系是: k=i×(i-1)/2+j-1 × i≧j ≧ 是在上三角矩阵中。因为a 若i<j:则aij是在上三角矩阵中。因为 ij=aji,在向 : 中保存的是a 依上述分析可得: 量sa中保存的是 ji 。依上述分析可得: 中保存的是 k=j×(j-1)/2+i-1 × i<j 对称矩阵元素a 保存在向量 中时的下标值 在向量sa中时的下标值k与 对称矩阵元素 i j保存在向量 中时的下标值 与 (i,j)之间的对应关系是: )之间的对应关系是 i×(i-1)/2+j-1 ×
K=

当i≧j时 ≧时 当i<j时 时

j×(j-1)/2+i-1 ×

1≦i,j≦ n ≦ ≦

(5-4)

根据上述的下标对应关系, 根据上述的下标对应关系,对于矩阵中的任意元 均可在一维数组sa中唯一确定其位置 中唯一确定其位置k;反之, 素aij,均可在一维数组 中唯一确定其位置 ;反之, 对所有k=1,2, …,n(n+1)/2,都能确定 对所有 ,都能确定sa[k]中的元素在矩 中的元素在矩 阵中的位置(i,j)。 阵中的位置 。 阶对称矩阵A的压缩存储 称sa[0…n(n+1)/2]为n阶对称矩阵 的压缩存储。 为 阶对称矩阵 的压缩存储。

2

三角矩阵
以主对角线划分, 以主对角线划分,三角矩阵有上三角和下三角两

种。 上三角矩阵的下三角(不包括主对角线) 上三角矩阵的下三角(不包括主对角线)中的元 素均为常数c(一般为0) 下三角矩阵正好相反, 素均为常数 (一般为 )。下三角矩阵正好相反,它的主 对角线上方均为常数,如图5-5所示 所示。 对角线上方均为常数,如图 所示。

a11 a12 … a1n c a22 … a2n … … … c c … ann
(a) 上三角矩阵示例 三角矩阵示例

a11 c … c a21 a22 … c … … … an1 an2 … ann
(b) 下三角矩阵示例 三角矩阵示例

三角矩阵示例 图5-5 三角矩阵示例

三角矩阵中的重复元素c可共享一个存储空间,其 三角矩阵中的重复元素 可共享一个存储空间, 可共享一个存储空间 余的元素正好有n(n+1)/2个,因此,三角矩阵可压缩存 余的元素正好有 个 因此, 储到向量sa[0…n(n+1)/2]中,其中 存放在向量的第 个 存放在向量的第1个 储到向量 中 其中c存放在向量的第 分量中。 分量中。 上三角矩阵元素a 保存在向量 中时的下标值 在向量sa中时的下标值k与 上三角矩阵元素 i j保存在向量 中时的下标值 与 (i,j)之间的对应关系是: )之间的对应关系是

K=

i×(i-1)/2+j-1 × n×(n+1)/2 ×

当i≧j时 ≧时 当i<j时 时

1≦i,j≦ n ≦ ≦

(5-5)

下三角矩阵元素a 保存在向量 中时的下标值k 下三角矩阵元素ai j保存在向量sa中时的下标值k与 在向量sa中时的下标值 i,j)之间的对应关系是 (i,j)之间的对应关系是: K= i×(i-1)/2+j-1 × n×(n+1)/2 × 当i≦j时 时 当i>j时 时
1≦i,j≦n ≦ ≦

(5-6)

3

对角矩阵

矩阵中,除了主对角线和主对角线上或下方若干 矩阵中, 条对角线上的元素之外,其余元素皆为零。 条对角线上的元素之外,其余元素皆为零。即所有的非 零元素集中在以主对角线为了中心的带状区域中, 零元素集中在以主对角线为了中心的带状区域中,如图 5-6所示。 所示。 所示

a11 a12 0 …. 0 a21 a22 a23 0 …. 0 0 a32 a33 a34 0 …. 0 … … … …. 0 …. 0 …. 0 an-1 n-2 an-1 n-1 an-1 n 0 0 an n-1 an n

A=

图5-6 三对角矩阵示例 三对角矩阵示例

如上图三对角矩阵,非零元素仅出现在主对角(ai 如上图三对角矩阵,非零元素仅出现在主对角(a ,1≦ n)上 主对角线上的那条对角线(a i,1≦i≦n)上、主对角线上的那条对角线(ai ,1≦ 主对角线下的那条对角线上(a i+1,1≦i≦n-1) 、主对角线下的那条对角线上(ai+1 ,1≦ 1)。显然, i- |>1时 元素a =0。 i,1≦i≦n-1)。显然,当| i-j |>1时,元素aij=0。 由此可知,一个k对角矩阵(k为奇数)A是满足下述 由此可知,一个k对角矩阵( 为奇数) 条件: i- |>(k-1)/2时 条件: 当| i-j |>(k-1)/2时, ai j=0

对角矩阵可按行优先顺序 对角线顺序, 对角矩阵可按行优先顺序或对角线顺序,将其压缩 行优先顺序或 存储到一个向量中, 存储到一个向量中,并且也能找到每个非零元素和向量 下标的对应关系。 下标的对应关系。 仍然以三对角矩阵为例讨论。 仍然以三对角矩阵为例讨论。 当i=1,j=1、2,或i=n, j=n-1、n或 i=1,j=1、 i=n, j=n1<i<n-1,j=i1<i<n-1,j=i-1、i、i+1的元素aij外,其余元素都 i+1的元素 的元素a 是 0。 对这种矩阵,当以按“行优先顺序”存储时, 对这种矩阵,当以按“行优先顺序”存储时, 第 1行和第n行是2个非零元素,其余每行的非零元素都要 行和第n行是2个非零元素, 是3个,则需存储的元素个数为3n-2… 3n-3 3n-2 则需存储的元素个数为3n- 。 K 1 2 3 4 5 6 7 8
sa a11 a12 a21 a22 a23 a32 a33 a34 … an n-1 ann
对角矩阵的压缩存储示例 图5-7 三对角矩阵的压缩存储示例

如图5-7所示三对角矩阵的压缩存储形式。数组sa 如图 所示三对角矩阵的压缩存储形式。数组 所示 压缩存储形式 中的元素sa[k]与三对角矩阵中的元素 ij存在一一对应关 与三对角矩阵中的元素a 中的元素 与三对角矩阵中的元素 之前有i-1行 共有3× 个非零元素 在第i行 个非零元素, 系,在aij之前有 行,共有 ×i-1个非零元素,在第 行, 个非零元素, 有j-i+1个非零元素,这样,非零元素 ij的地址为: 个非零元素 这样,非零元素a 的地址为: LOC[ai j] =LOC[a11] +[3×i-1+(j-i+1)]×l × × =LOC[a11]+(2×i+j)×l × × 上例中,a34对应着 上例中, 对应着sa[10] , k=2×i+j=2×3+4=10 × × 阶三对角矩阵A的压缩存储 称sa[0…3×n-2]是n阶三对角矩阵 的压缩存储。 × 是 阶三对角矩阵 的压缩存储。 上述各种特殊矩阵, 上述各种特殊矩阵,其非零元素的分布都是有规律 的,因此总能找到一种方法将它们压缩存储到一个向量 中,并且一般都能找到矩阵中的元素与该向量的对应关 通过这个关系,仍能对矩阵的元素进行随机存取。 系,通过这个关系,仍能对矩阵的元素进行随机存取。

5.3.2

稀疏矩阵

稀疏矩阵(Sparse Matrix):对于稀疏矩阵,目前还 稀疏矩阵 :对于稀疏矩阵,
没有一个确切的定义。设矩阵 是一个 是一个n× 的 没有一个确切的定义。设矩阵A是一个 ×m的矩阵中有 s个非零元素,设 δ=s/(n×m),称δ为稀疏因子,如果 个非零元素, 个非零元素 × , 为稀疏因子, 某一矩阵的稀疏因子δ满足 时称为稀疏矩阵, 某一矩阵的稀疏因子 满足δ≦0.05时称为稀疏矩阵,如 时称为稀疏矩阵 所示。 图5-8所示。 所示
0 12 0 0 -3 0 9 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 4

A= 0 0 24 0 0 2 0 0
0 18 0 0 0 0 0 0 0 0 0 0 0 0 -7 0 0 0 0 -6 0 0 0 0
稀疏矩阵 矩阵示例 图5-8 稀疏矩阵示例

5.3.2.1

稀疏矩阵的压缩存储

对于稀疏矩阵,采用压缩存储方法时,只存储非 对于稀疏矩阵,采用压缩存储方法时,只存储非0 元素。必须存储非0元素的行下标值 列下标值、 元素的行下标值、 元素。必须存储非 元素的行下标值、列下标值、元素 因此,一个三元组(i, 值。因此,一个三元组 j, aij)唯一确定稀疏矩阵的一 唯一确定稀疏矩阵的一 个非零元素。 个非零元素。 如图5-8的稀疏矩阵 的三元组线性表为 如图 的稀疏矩阵A的三元组线性表为: 的稀疏矩阵 的三元组线性表为: ( (1,2,12), (1,3,9), (3,1,-3), (3,8,4), (4,3,24), (5,2,18), (6,7,-7), (7,4,-6) )

1 三元组顺序表
若以行序为主序,稀疏矩阵中所有非 元素的三元组 元素的三元组, 若以行序为主序,稀疏矩阵中所有非0元素的三元组, 就可以得构成该稀疏矩阵的一个三元组顺序表。 就可以得构成该稀疏矩阵的一个三元组顺序表。

1

三元组顺序表

若以行序为主序,稀疏矩阵中所有非 元素的三元 若以行序为主序,稀疏矩阵中所有非0元素的三元 就可以得构成该稀疏矩阵的一个三元组顺序表。 组,就可以得构成该稀疏矩阵的一个三元组顺序表。 相应的数据结构定义如下: 相应的数据结构定义如下:

⑴ 三元组结点定义
#define MAX_SIZE 101 typedef int elemtype ; typedef struct { int row ; int col ; }Triple ;
/* 行下标 */ /* 列下标 */ /* 元素值 */

elemtype value;

⑵ 三元组顺序表定义
typedef struct { int rn ; int cn ; int tn ; Triple }TMatrix ; 图5-8所示的稀疏矩阵及其相应的转置矩阵所对应 的三元组顺序表如图5 所示。 的三元组顺序表如图5-9所示。
/* /* /* 行数 列数 */ */ */

非0元素个数

data[MAX_SIZE] ;

7 8 9 1 1 3 3 4 4 5 6 7

rn行数 行数 cn列数 列数 tn元素个数 元素个数 2 12 3 9 1 -3 8 4 3 24 6 2 2 18 7 -7 4 -6

8 7 9 1 2 2 3 3 4 6 7 8

rn行数 行数 cn列数 列数 tn元素个数 元素个数 3 -3 1 12 5 18 1 9 4 24 7 -6 4 2 6 -7 2 4

row col value
(a) 原矩阵的三元组表

row col value
(b)转置矩阵的三元组表 转置矩阵的三元组表

稀疏矩阵及其转置矩阵的三元组顺序表 图5-9 稀疏矩阵及其转置矩阵的三元组顺序表

矩阵的运算包括矩阵的转置、矩阵求逆、 矩阵的运算包括矩阵的转置、矩阵求逆、矩阵的加 矩阵的乘除等。在此, 减、矩阵的乘除等。在此,先讨论在这种压缩存储结构 下的求矩阵的转置的运算。 下的求矩阵的转置的运算。 一个m× 的矩阵 的矩阵A,它的转置B是一个 是一个n× 的矩阵 的矩阵, 一个 ×n的矩阵 ,它的转置 是一个 ×m的矩阵, 的行是A的列 且b[i][j]=a[j][i],0≦i≦n,0≦j≦m,即B的行是 的列, , ≦≦ , ≦≦ , 的行是 的列, B的列是 的行。 的列是A的行 的列是 的行。 设稀疏矩阵A是按行优先顺序压缩存储在三元组表 设稀疏矩阵 是按行优先顺序压缩存储在三元组表 a.data中,若仅仅是简单地交换 的内容, 中 若仅仅是简单地交换a.data中i和j的内容,得 中 和 的内容 到三元组表b.data,b.data将是一个按列优先顺序存储 将是一个按列优先顺序 到三元组表 , 将是一个按列优先顺序存储 的稀疏矩阵B,要得到按行优先顺序存储的b.data,就 的稀疏矩阵 ,要得到按行优先顺序存储的 , 必须重新排列三元组表b.data中元素的顺序。 中元素的顺序。 必须重新排列三元组表 中元素的顺序

求转置矩阵的基本算法思想是: 求转置矩阵的基本算法思想是:
① 将矩阵的行、列下标值交换。即将三元组表中的 将矩阵的行、列下标值交换。 列位置值i 相互交换 交换; 行、列位置值i 、j相互交换; ② 重排三元组表中元素的顺序。即交换后仍然是按 重排三元组表中元素的顺序。即交换后仍然是按 中元素的顺序 行优先顺序排序的 排序的。 行优先顺序排序的。

方法一: 方法一: 算法思想:按稀疏矩阵A 三元组表a.data中的 算法思想:按稀疏矩阵A的三元组表a.data中的列次 中的列次
序依次找到相应的三元组存入 序依次找到相应的三元组存入b.data中。 找到相应的三元组存入b.data中 每找转置后矩阵的一个三元组, 每找转置后矩阵的一个三元组,需从头至尾扫描 整个三元组表a.data 整个三元组表a.data 。找到之后自然就成为按行优先 的转置矩阵的压缩存储表示。 的转置矩阵的压缩存储表示。

按方法一求转置矩阵的算法如下: 按方法一求转置矩阵的算法如下: void TransMatrix(TMatrix a , TMatrix b) { int p , q , col ; b.rn=a.cn ; b.cn=a.rn ; b.tn=a.tn ;
/* 置三元组表b.data的行、列数和非 元素个数 */ 列数和非0元素个数 三元组表 的

if (b.tn==0) else { q=0;

printf(“ The Matrix A=0\n” );

for (col=1; col<=a.cn ; col++)
/* 每循环一次找到转置后的一个三元组 */

for (p=0 ;p<a.tn ; p++)
/* 循环次数是非 元素个数 */ 循环次数是非0元素个数

if (a.data[p].col==col) { b.data[q].row=a.data[p].col ; b.data[q].col=a.data[p].row ; b.data[q].value=a.data[p].value; q++ ; } } }

算法分析:本算法主要的工作是在p col的两个循 算法分析:本算法主要的工作是在p和col的两个循
环中完成的,故算法的时间复杂度为O(cn×tn),即 环中完成的,故算法的时间复杂度为O(cn×tn),

而一般传统矩阵的转置算法为: 而一般传统矩阵的转置算法为: for(col=1; col<=n ;++col) for(row=0 ; row<=m ;++row) b[col][row]=a[row][col] ; 其时间复杂度为O(n×m)。当非零元素的个数tn 其时间复杂度为O(n×m)。当非零元素的个数tn 同数量级时,算法TransMatrix的时间复杂度 和m×n同数量级时,算法TransMatrix的时间复杂度 O(m× 为O(m×n2)。 由此可见,虽然节省了存储空间,但时间复杂度却 由此可见,虽然节省了存储空间, 大大增加。所以上述算法只适合于稀疏矩阵中非0 大大增加。所以上述算法只适合于稀疏矩阵中非0元素 的个数tn远远小于 远远小于m 的情况。 的个数tn远远小于m×n的情况。

方法二(快速转置的算法) 方法二(快速转置的算法) 算法思想:直接按照稀疏矩阵A 三元组表a.data的 算法思想:直接按照稀疏矩阵A的三元组表a.data的
次序依次顺序转换,并将转换后的三元组放置于 次序依次顺序转换,并将转换后的三元组放置于三元组 放置于三元组 b.data的恰当位置。 表b.data的恰当位置。

前提:若能预先确定原矩阵A中每一列的( 前提:若能预先确定原矩阵A中每一列的(即B中
每一行)第一个非0元素在b.data中应有的位置, 每一行)第一个非0元素在b.data中应有的位置,则在 中应有的位置 作转置时就可直接放在b.data中恰当的位置。因此, 中恰当的位置 作转置时就可直接放在b.data中恰当的位置。因此, 先求得A中每一列的非0元素个数。 应先求得A中每一列的非0元素个数。 附设两个辅助向量num[ ]和 附设两个辅助向量num[ ]和cpot[ ] 。 ◆ num[col]:统计A中第col列中非0元素的个 num[col]:统计A中第col列中非 列中非0 数; ◆ cpot[col] :指示A中第一个非0元素在 指示A中第一个非0 b.data中的恰当位置。 b.data中的恰当位置。 中的恰当位置

显然有位置对应关系: 显然有位置对应关系:
cpot[1]=1 cpot[col]=cpot[col-1]+num[col-1] 2≦col≦a.cn ≦ ≦ 例图5-8中的矩阵 和表 例图 中的矩阵A和表 中的矩阵 和表5-9(a)的相应的三元组表可 的 以求得num[col]和cpot[col]的值如表 : 的值如表5-1: 以求得 和 的值如表
表5-1 num[col]和cpot[col]的值表 和 的值表

col 1 2 3 4 5 6 7 8 num[col] 1 2 2 1 0 1 1 1 cpot[col] 1 3 5 6 6 7 8 9

快速转置算法如下: 快速转置算法如下:
void FastTransMatrix(TMatrix a, TMatrix FastTransMatrix(TMatrix b) { int p , q , col , k ; int num[MAX_SIZE] , copt[MAX_SIZE] num[MAX_SIZE] copt[MAX_SIZE] ; b.rn=a.cn ; b.cn=a.rn ; b.tn=a.tn ;
/* */ 置三元组表b.data的行、列数和非0元素个数 三元组表b.data的 列数和非0

if (b.tn==0) printf(“ The Matrix printf(“ A=0\ A=0\n” ) ; else { for (col=1 ; col<=a.cn ; ++col) num[col]=0 ;

for (cpot[0]=1, col=2 ; col<=a.cn ; ++col) cpot[col]=cpot[colcpot[col]=cpot[col1]+num[col1]+num[col-1] ;
/* 求第col列中第一个非0元在b.data中的 求第col列中第一个非 元在b.data中的 列中第一个非0 序号 */

for (p=1 ; p<=a.tn ; ++p) { col=a.data[p].col ; q=cpot[col] ; b.data[q].row=a.data[p].col ; b.data[q].col=a.data[p].row ; b.data[q].value=a.data[p].value ;

2 行逻辑链接的三元组顺序表
将上述方法二中的辅助向量cpot[ ]固定在稀疏矩阵 将上述方法二中的辅助向量 固定在稀疏矩阵 的三元组表中,用来指示“ 的信息。 的三元组表中,用来指示“行”的信息。得到另一种 顺序存储结构:行逻辑链接的三元组顺序表。 顺序存储结构:行逻辑链接的三元组顺序表。其类型 描述如下: 描述如下: #define MAX_ROW 100 typedef struct { Triple data[MAX_SIZE] ; int rpos[MAX_ROW]; int rn ,cn , tn ; }RLSMatrix ;
/* 非0元素的三元组表 */ 元素的三元组表 /* 各行第一个非 位置表 */ 各行第一个非0位置表

/* 矩阵的行、列数和非0元个数 */ 矩阵的行、列数和非 元个数

稀疏矩阵的乘法
设有两个矩阵:A=(aij)m×n ,B=(bij)n×p 设有两个矩阵: 则: C=(cij)m×p 其中 cij=∑aik×bkj 1≦k≦n , 1≦i≦m ,1≦j≦p 经典算法是三重循环: 经典算法是三重循环: for ( i=1 ; i<=m ; ++i) for ( j=1 ; j<=p ; ++j) { c[i][j]=0 ; for ( k=1 ; k<=n ; ++k) c[i][j]= c[i][j]+a[i][k]× c[i][j]+a[i][k]×b[k][j]; } 此算法的复杂度为O(m× p)。 此算法的复杂度为O(m×n×p)。

设有两个稀疏矩阵A=(a 设有两个稀疏矩阵A=(aij)m×n ,B=(bij)n×p ,其 存储结构采用行逻辑链接的三元组顺序表。 存储结构采用行逻辑链接的三元组顺序表。

算法思想:对于A中的每个元素a.data[p](p=1, 算法思想:对于A中的每个元素a.data[p](p=1,
2, … , a.tn),找到B中所有满足条件: a.tn),找到B中所有满足条件: a.data[p].col=b.data[q].row的元素 a.data[p].col=b.data[q].row的元素 b.data[q], b.data[q],求得 a.data[p].value×b.data[q].value,该乘积是c a.data[p].value×b.data[q].value,该乘积是cij 中的一部分。 中的一部分。求得所有这样的乘积并累加求和就能得到 cij。 为得到非0的乘积,只要对a.data[1… 为得到非0的乘积,只要对a.data[1…a.tn] 中 每个元素(i, )(1≦ a.rn, 每个元素(i,k,aik)(1≦i≦a.rn,1≦k≦a.cn) , 找到b.data中所有相应的元素 , 中所有相应的元素(k 找到b.data中所有相应的元素(k,j, bkj)(1≦k≦b.rn,1≦j≦b.cn) 相乘即可。则必须 )(1≦ b.rn, 相乘即可。 知道矩阵 中第k行的所有非0元素, 矩阵B ]向量 知道矩阵B中第k行的所有非0元素,而b.rpos[ ]向量

b.rpos[row]指示了矩阵B的第row行中第一 b.rpos[row]指示了矩阵B的第row行中第一 指示了矩阵 个非0元素在b.data[ ]中的位置 序号) 显然, 中的位置( 个非0元素在b.data[ ]中的位置(序号),显然, b.rpos[row+1]- 指示了第row行中最后一个非 b.rpos[row+1]-1指示了第row行中最后一个非0 行中最后一个非0 元素在b.data[ ]中的位置 序号) 最后一行中最后 元素在b.data[ ]中的位置(序号) 。最后一行中最后 中的位置( 一个非0元素在b.data[ ]中的位置显然就是 中的位置显然就是b.tn 一个非0元素在b.data[ ]中的位置显然就是b.tn 。 两个稀疏矩阵相乘的算法如下: 两个稀疏矩阵相乘的算法如下: 算法如下 void MultsMatrix(RLSMatrix a, RLSMatrix b, RLSMatrix c)
/* 求矩阵A 、B的积C=A×B,采用行逻辑链接的顺序表 矩阵A 的积C=A× */

{

elemtype ctemp[Max_Size] ; int p , q , arow , ccol , brow , t ; if (a.cn!=b.rn) { printf(“Error\ printf(“Error\n”) ;

else
{

c.rn=a.rn ; c.cn=b. n ; c.tn=0 ; if (a.tn*b.tn!=0)
*/ /* C 是非零矩阵

/*

初始化C 初始化C */

{ for (arow=1 ; arow<=a.rn ; ++arow) {
加器清零

ctemp[arow]=0 ; /* 当前行累
*/

c.rpos[arow]=c.tn+1; p=a.rops[arow]; for ( ; p<a.rpos[arow+1];++p)
/* 对第arow行的每一个非0元素 对第arow行的每一个非 行的每一个非0

for (q=b.rpos[brow] ; q<t ; ++q) { ccol=b.data[q].col ;
/* 积元素在c 积元素在c中的列号 */

ctemp[ccol]+=a.data[p].value*b.d ata[q].value ; } }
/* 求出c中第arow行中的非0元素 求出c中第arow行中的非 行中的非0 */

for (ccol=1 ; ccol<=c.cn ; ++ccol) if ( ctemp[ccol] !=0 ) { if ( ++c.tn>MAX_SIZE) { printf(“Error\n”) ; printf(“Error\ exit(0); }

c.data[c.tn]=(arow , ccol , ctemp[ccol]) ; } } } }

3 十字链表
对于稀疏矩阵,当非 元素的个数和位置在操作过 对于稀疏矩阵,当非0元素的个数和位置在操作过 程中变化较大时, 程中变化较大时,采用链式存储结构表示比三元组的 线性表更方便。 线性表更方便。 矩阵中非0元素的结点所含的域有:行、列、值、 矩阵中非 元素的结点所含的域有: 列 值 元素的结点所含的域有 行指针(指向同一行的下一个非 指向同一行的下一个非0元 、列指针(指向同一 行指针 指向同一行的下一个非 元)、列指针 指向同一 列的下一个非0元)。其次, 列的下一个非0元)。其次,十字交叉链表还有一个头结 结点的结构如图5-10所示。 所示。 点,结点的结构如图 所示
row col value down right
(a) 结点结构

rn cn tn down right
(b) 头结点结构

十字链表结点结构 图5-10 十字链表结点结构

由定义知,稀疏矩阵中同一行的非0 由定义知,稀疏矩阵中同一行的非0元素的由 right指针域链接成一个行链表 right指针域链接成一个行链表, 由down指针域链接 指针域链接成一个行链表, down指针域链接 成一个列链表。则每个非0元素既是某个行链表中的一 成一个列链表。则每个非0元素既是某个行链表中的一 个结点,同时又是某个列链表中的一个结点,所有的非 个结点,同时又是某个列链表中的一个结点,所有的非 0元素构成一个十字交叉的链表。称为十字链表。 元素构成一个十字交叉的链表 称为十字链表 构成一个十字交叉的链表。 十字链表。 此外,还可用两个一维数组分别存储行链表的头指 此外,还可用两个一维数组分别存储行链表的头指 针和列链表的头指针。对于图5 11(a)的稀疏矩阵A 针和列链表的头指针。对于图5-11(a)的稀疏矩阵A , 对应的十字交叉链表如图5 11(b)所示 所示, 对应的十字交叉链表如图5-11(b)所示,结点的描述 如下: 如下: typedef struct Clnode { int row , col ; /* 行号和列号 */ elemtype value ; /* 元素值 */ struct Clnode *down , *right ; }OLNode ; /* 非0元素结点 */

typedef struct Clnode { int rn; /* 矩阵的
行数 */

int int

cn; tn;

/* 矩阵的列 矩阵的列 /* 非0元素

A.chead

数 */ 总数 */

A.rchead ?

?

1 2 12 ? 2 5 -4 ? ? 32 5 ? ? 43 3 ? ?
(b 稀疏矩阵的十字交叉链表 (b) 稀疏矩阵的十字交叉链表

OLNode *rhead ; OLNode12 0 0 0 ; *chead 0 0 0 } CrossList ; 0 0 -4 A=
0 5 0 0 0 3 0 0 0 0
(a) 稀疏矩阵 稀疏矩阵

稀疏矩阵及其十字交叉链表 矩阵及其 图5-11 稀疏矩阵及其十字交叉链表

5.4 广义表
广义表是线性表的推广和扩充, 广义表是线性表的推广和扩充,在人工智能领域 中应用十分广泛。 中应用十分广泛。 在第2章中,我们把线性表定义为n(n≧ )个元 在第2章中,我们把线性表定义为n(n≧0 )个元 的有穷序列, 素a1, a2 ,…, an的有穷序列,该序列中的所有元素具 有相同的数据类型且只能是原子项(Atom)。所谓原子 有相同的数据类型且只能是原子项(Atom)。所谓原子 项可以是一个数或一个结构,是指结构上不可再分的。 项可以是一个数或一个结构,是指结构上不可再分的。 若放松对元素的这种限制,容许它们具有其自身结构, 若放松对元素的这种限制,容许它们具有其自身结构, 就产生了广义表的概念。 就产生了广义表的概念。

广义表(Lists, 广义表(Lists,又称为列表 ):是由n(n 是由n(n
≧0)个元素组成的有穷序列: LS=(a1,a2,…, 0)个元素组成的有穷序列 个元素组成的有穷序列: an)

其中a 或者是原子项,或者是一个广义表。LS是广 其中ai或者是原子项,或者是一个广义表。LS是广 义表的名字, 为它的长度。 是广义表, 义表的名字,n为它的长度。若ai是广义表,则称为 LS的子表。 LS的子表 的子表。 习惯上:原子用小写字母,子表用大写字母。 小写字母, 大写字母。 习惯上:原子用小写字母 子表用大写字母 若广义表LS非空时 若广义表LS非空时: 非空时: ◆ a1(表中第一个元素)称为表头; 表中第一个元素)称为表头 表头; ◆ 其余元素组成的子表称为表尾;(a2,a3,…, 其余元素组成的子表称为表尾 表尾; an) ◆ 广义表中所包含的元素(包括原子和子表)的个数 广义表中所包含的元素(包括原子和子表) 称为表的长 度。 ◆ 广义表中括号的最大层数称为表深 (度)。 有关广义表的这些概念的例子如表5 所示。 有关广义表的这些概念的例子如表5-2所示。

表5-2

广义表及其示例 广义表及其示例

D A e B a b c d C 0 1 2 3 ∞ 2

广 义 表 表长n 表深h 表深h
A=() B=(e) C=(a,(b,c, d)) D=(A,B,C) E=(a,E) F=(()) 0 1 2 3 2 1

广义表的图形表示 图5-12 广义表的图形表示

广义表的重要结论: 广义表的重要结论:
⑴ 广义表的元素可以是原子,也可以是子表,子表 广义表的元素可以是原子,也可以是子表, 的元素又可以是子表, 的元素又可以是子表, …。即广义表是一个多层次 的结构。 的结构。 表5-2中的广义表D的图形表示如图5-12所示。 中的广义表 的图形表示如图5 12所示 广义表D 所示。 (2) 广义表可以被其它广义表所共享,也可以共享其 广义表可以被其它广义表所共享 也可以共享 所共享, 共享其 它广义表。广义表共享其它广义表时通过表名引用。 共享其它广义表时通过表名引用 它广义表。广义表共享其它广义表时通过表名引用。 (3) 广义表本身可以是一个递归表。 广义表本身可以是一个递归表。 (4) 根据对表头、表尾的定义,任何一个非空广义表 根据对表头 表尾的定义 表头、 的定义, 表头可以是原子 也可以是子表, 而表尾必定是 可以是原子, 的表头可以是原子,也可以是子表, 而表尾必定是 广义表。 广义表。

5.4.1 广义表的存储结构
由于广义表中的数据元素具有不同的结构, 由于广义表中的数据元素具有不同的结构,通常 用链式存储结构表示 每个数据元素用一个结点表示。 表示, 用链式存储结构表示,每个数据元素用一个结点表示。 因此,广义表中就有两类结点: 因此,广义表中就有两类结点: 一类是表结点 用来表示广义表项,由标志域, 表结点, ◆ 一类是表结点,用来表示广义表项,由标志域, 表头指针域,表尾指针域组成; 表头指针域,表尾指针域组成 另一类是原子结点,用来表示原子项,由标志域, 原子结点 ◆ 另一类是原子结点,用来表示原子项,由标志域, 原子的值域组成。如图5-13所示。 所示。 原子的值域组成。如图 所示 只要广义表非空,都是由表头和表尾组成。 只要广义表非空,都是由表头和表尾组成。即一 表头和表尾组成 个确定的表头和表尾就唯一确定一个广义表。 表头和表尾就唯一确定一个广义表 个确定的表头和表尾就唯一确定一个广义表。

标志tag=0 原子的值 原子的值 标志
(a) 原子结点

标志tag=1 表头指针 表头指针hp 标志
(b) 表结点

表尾指针tp 表尾指针

广义表的链表结点结构示意图 图5-13 广义表的链表结点结构示意图

相应的数据结构定义如下: 相应的数据结构定义如下: typedef struct GLNode { int tag ; /* 标志域,为1:表结点;为0 :原子结点 */ 标志域, :表结点; union { elemtype value; /* 原子结点的值域 */ 原子结点的值域 struct { struct GLNode *hp , *tp ; }ptr ; /* ptr和atom两成员共用 */ 和 两成员共用 }Gdata ; } GLNode ; /* 广义表结点类型 */ 广义表结点类型

例: 对A=(),B=(e),C=(a, (b, c, d) ),D=(A, B, C), , , , , E=(a, E)的广义表的存储结构如图5-14所示。 的广义表的存储结构如图5 所示 所示。 的广义表的存储结构如图
A=NULL B 1 C 1 0 a ∧ 0 e 1 1 0 b D 1 ∧ 1 1 ∧ 1 0 c 1 ∧ 1 ∧ E

1 0 a

1



0 d

广义表的存储结构示意图 图5-14 广义表的存储结构示意图

对于上述存储结构,有如下几个特点: 对于上述存储结构,有如下几个特点: (1) 若广义表为空,表头指针为空;否则,表头指 若广义表为空,表头指针为空;否则, 针总是指向一个表结点,其中hp指向广义表的表头 针总是指向一个表结点,其中hp指向广义表的表头 结点(或为原子结点,或为表结点) tp指向广义表 结点(或为原子结点,或为表结点) ,tp指向广义表 的表尾(表尾为空时,指针为空,否则必为表结点) 的表尾(表尾为空时,指针为空,否则必为表结点)。 (2) 这种结构求广义表的长度、深度、表头、表尾 这种结构求广义表的长度 深度、表头、 广义表的长度、 的操作十分方便。 的操作十分方便。 (3) 表结点太多,造成空间浪费。也可用图5-15所 表结点太多,造成空间浪费。也可用图 15所 示的结点结构。 示的结点结构。
tag=0 原子的值 表尾指针 原子的值 表尾指针tp
(a) 原子结点

tag=1 表头指针 表头指针hp 表尾指针 表尾指针tp
(b) 表结点

广义表的链表结点结构示意图 图5-15 广义表的链表结点结构示意图

习题五
⑴ 什么是广义表?请简述广义表与线性表的区别? 什么是广义表?请简述广义表与线性表的区别? ⑵ 一个广义表是(a, (a, b), d, e, (a, (i, j), 一个广义表是(a, k)) ,请画出该广义表的链式存储结构。 请画出该广义表的链式存储结构。 ⑶ 设有二维数组a[6][8],每个元素占相邻的4个 设有二维数组a[6][8],每个元素占相邻的4 字节,存储器按字节编址,已知a的起始地址是1000, 字节,存储器按字节编址,已知a的起始地址是1000, 试计算: 试计算: ① 数组a的最后一个元素a[5][7]起始地址; 数组a的最后一个元素a[5][7]起始地址 起始地址; ② 按行序优先时,元素a[4][6]起始地址; 按行序优先时,元素a[4][6]起始地址 起始地址; ③ 按行序优先时,元素a[4][6]起始地址。 按行序优先时,元素a[4][6]起始地址。 起始地址

⑷ 设A和B是稀疏矩阵,都以三元组作为存储结构, 是稀疏矩阵,都以三元组作为存储结构, 请写出矩阵相加的算法,其结果存放在三元组表C 请写出矩阵相加的算法,其结果存放在三元组表C中, 并分析时间复杂度。 并分析时间复杂度。 ⑸ 设有稀疏矩阵B如下图所示,请画出该稀疏矩阵 设有稀疏矩阵B如下图所示, 的三元组表和十字链表存储结构。 的三元组表和十字链表存储结构。
0 3 0 0 0 0 0 0 0 0 0 0 0 0 0 0 -3 0 0 0 0 0 0 4

A= 0 0 2 0 0 2 0 0
0 18 0 0 0 0 0 0 0 0 0 0 4 0 5 0 0 0 -3 0 0 0 0 0

第6章 树和二叉树
树型结构是一类非常重要的非线性结构。直观地, 树型结构是一类非常重要的非线性结构。直观地, 树型结构是以分支关系定义的层次结构 以分支关系定义的层次结构。 树型结构是以分支关系定义的层次结构。 树在计算机领域中也有着广泛的应用, 树在计算机领域中也有着广泛的应用,例如在编 译程序中,用树来表示源程序的语法结构; 译程序中,用树来表示源程序的语法结构;在数据库系 统中,可用树来组织信息;在分析算法的行为时, 统中,可用树来组织信息;在分析算法的行为时,可用 树来描述其执行过程等等。 树来描述其执行过程等等。 本章将详细讨论树和二叉树数据结构,主要介绍 本章将详细讨论树和二叉树数据结构, 树和二叉树的概念、术语,二叉树的遍历算法。 树和二叉树的概念、术语,二叉树的遍历算法。树和二 叉树的各种存储结构以及建立在各种存储结构上的操作 及应用等。 及应用等。

6.1 树的基本概念
6.1.1 树的定义和基本术语
1 树的定义
树(Tree)是n(n≧0)个结点的有限集合T,若 (Tree)是n(n≧0)个结点的有限集合 个结点的有限集合T n=0时称为空树 否则: n=0时称为空树,否则: 时称为空树, 有且只有一个特殊的称为树的根(Root)结点 结点; ⑴ 有且只有一个特殊的称为树的根(Root)结点; n>1时 其余的结点被分为m(m>0)个 ⑵ 若n>1时,其余的结点被分为m(m>0)个互不 相交的子集 的子集T 相交的子集T1, T2, T3…Tm,其中每个子集本身又 是一棵树,称其为根的子树(Subtree)。 是一棵树,称其为根的子树(Subtree)。 这是树的递归定义,即用树来定义树, 这是树的递归定义,即用树来定义树,而只有一个 结点的树必定仅由根组成,如图6 1(a)所示 所示。 结点的树必定仅由根组成,如图6-1(a)所示。

2 树的基本术语
⑴ 结点(node):一个数据元素及其若干指向其 结点(node):
子树的分支。 子树的分支。

⑵ 结点的度(degree) 、树的度:结点所拥有 结点的度(degree) 树的度:
的子树的棵数称为结点的度 的子树的棵数称为结点的度。树中结点度的最大值称 结点的度。 树的度。 为树的度。
A B A E
(a) 只有根结点

C F G

D H I N J

K
树的示例形式 图6-1 树的示例形式

L

M

(b) 一般的树

如图6-1(b)中结点 的度是 ,结点 的度是 ,结点 中结点A的度是 的度是2 如图 中结点 的度是3 结点B的度是 M的度是 ,树的度是 。 的度是0,树的度是3 的度是

叶子(left)结点、非叶子结点:树中度为 的 结点、非叶子结点:树中度为 度为0的 ⑶ 叶子 结点
叶子结点( 结点称为叶子结点 或终端结点) 相对应地, 结点称为叶子结点(或终端结点)。相对应地,度不为 0的结点称为非叶子结点 或非终端结点或分支结点)。 非叶子结点(或非终端结点或分支结点 的结点称为非叶子结点 或非终端结点或分支结点) 除根结点外,分支结点又称为内部结点。 除根结点外,分支结点又称为内部结点。 如图6-1(b)中结点 、I、J、K、L、M、N是叶子 中结点H、 、 、 、 、 、 是叶子 如图 中结点 结点,而所有其它结点都是分支结点。 结点,而所有其它结点都是分支结点。

孩子结点、双亲结点、 ⑷ 孩子结点、双亲结点、兄弟结点
一个结点的子树的根称为该结点的孩子结点(child) 一个结点的子树的根称为该结点的孩子结点 子树的根称为该结点的孩子结点 或子结点;相应地, 或子结点;相应地,该结点是其孩子结点的双亲结点 (parent)或父结点。 或父结点。 或父结点

如图6-1(b)中结点 、C、D是结点 的子结点,而 中结点B 是结点A的子结点 如图 中结点 、 是结点 的子结点, 结点A是结点B 结点 是结点 、C、D的父结点;类似地结点 、F是 、 的父结点;类似地结点E 是 结点B的子结点 结点B是结点E 的子结点, 结点 的子结点,结点 是结点 、F的父结点。 的父结点。 同一双亲结点的所有子结点互称为兄弟结点 兄弟结点。 同一双亲结点的所有子结点互称为兄弟结点。 如图6-1(b)中结点 、C、D是兄弟结点;结点 、 中结点B 是兄弟结点; 如图 中结点 、 是兄弟结点 结点E F是兄弟结点。 是兄弟结点。 是兄弟结点

⑸ 层次、堂兄弟结点 层次、
规定树中根结点的层次为1, 规定树中根结点的层次为 ,其余结点的层次等于 其双亲结点的层次加1。 其双亲结点的层次加 。 若某结点在第l(l≧ 层 则其子结点在第l+1层 若某结点在第 ≧1)层,则其子结点在第 层。 堂兄弟结点。 双亲结点在同一层上的所有结点互称为堂兄弟结点 双亲结点在同一层上的所有结点互称为堂兄弟结点。 如图6-1(b)中结点 、F、G、H、I、J。 如图 中结点E、 、 、 、 、 。 中结点

结点的层次路径、祖先、 ⑹ 结点的层次路径、祖先、子孙
从根结点开始,到达某结点 所经过的所有结点成 从根结点开始,到达某结点p所经过的所有结点成 结点p的层次路径(有且只有一条) 为结点 的层次路径(有且只有一条)。 结点p的层次路径上的所有结点( 除外 称为p的 除外) 结点 的层次路径上的所有结点(p除外)称为 的 的层次路径上的所有结点 祖先(ancester) 。 祖先 以某一结点为根的子树中的任意结点称为该结点的 子孙结点(descent)。 子孙结点 。

树的深度(depth):树中结点的最大层次值,又 ⑺ 树的深度 :树中结点的最大层次值,
称为树的高度,如图 中树的高度为4。 称为树的高度,如图6-1(b)中树的高度为 。 中树的高度为

有序树和无序树:对于一棵树, ⑻ 有序树和无序树 对于一棵树,若其中每一个
结点的子树(若有)具有一定的次序,则该树称为有 结点的子树(若有)具有一定的次序,则该树称为有 无序树。 序树,否则称为无序树 序树,否则称为无序树。

森林(forest):是m(m≧0)棵互不相交的树的集 棵互不相交的树的集 ⑼ 森林 ≧ 棵互不相交的
合。显然,若将一棵树的根结点删除,剩余的子树就 显然,若将一棵树的根结点删除, 构成了森林。 构成了森林。

3 树的表示形式
倒悬树。是最常用的表示形式,如图6-1(b)。 ⑴ 倒悬树。是最常用的表示形式,如图 。 ⑵ 嵌套集合。是一些集合的集体,对于任何两个 嵌套集合。是一些集合的集体,
集合,或者不相交,或者一个集合包含另一个集合。 集合,或者不相交,或者一个集合包含另一个集合。 图6-2(a)是图 是图6-1(b)树的嵌套集合形式。 树的嵌套集合形式。 是图 树的嵌套集合形式

广义表形式。 是树的广义表形式。 ⑶ 广义表形式。图6-2(b)是树的广义表形式。 是树的广义表形式 凹入法表示形式。 ⑷ 凹入法表示形式。见P120
树的表示方法的多样化说明了树结构的重要性。 树的表示方法的多样化说明了树结构的重要性。

A H E (A(B(E(K,L),F),C(G(M,N)),D(H,I,J)
(b) 广义表形式 广义表形式

D I J C G M N

B F

K L

(a) 嵌套集合形式 嵌套集合形式 树的表示形式 图6-2 树的表示形式

6.1.2 定义
ADT Tree{ 数据对象D: 是具有相同数据类型的数据元素的集 数据对象 :D是具有相同数据类型的数据元素的集 合。 数据关系R: 为空集, 数据关系 :若D为空集,则称为空树; 为空集 则称为空树; …… 基本操作: 基本操作: …… } ADT Tree 详见p118~119。 详见

6.2
1 二叉树的定义

二叉树

6.2.1 二叉树的定义
二叉树(Binary tree)是n(n≥0)个结点的有限 二叉树(Binary tree)是n(n≥0)个结点的有限 集合。 n=0时称为空树 否则: 时称为空树, 集合。若n=0时称为空树,否则: ⑴ 有且只有一个特殊的称为树的根(Root)结点; 有且只有一个特殊的称为树的根(Root)结点 结点; ⑵ 若n>1时,其余的结点被分成为二个互不相交的 n>1时 其余的结点被分成为二个互不相交 二个互不相交的 子集T 分别称之为左、右子树,并且左、 子集T1,T2,分别称之为左、右子树,并且左、右子 树又都是二叉树。 树又都是二叉树。 由此可知,二叉树的定义是递归的。 定义是递归的 由此可知,二叉树的定义是递归

二叉树在树结构中起着非常重要的作用。因为二叉 二叉树在树结构中起着非常重要的作用。 树结构简单,存储效率高,树的操作算法相对简单, 树结构简单,存储效率高,树的操作算法相对简单,且 任何树都很容易转化成二叉树结构。 任何树都很容易转化成二叉树结构。上节中引入的有关 树的术语也都适用于二叉树。 树的术语也都适用于二叉树。

2

二叉树的基本形态
二叉树有5种基本形态,如图6 所示。 二叉树有5种基本形态,如图6-3所示。
A A (a) (b)
(d) 左子树为空

A

A

(c)

(d)
(c) 右子树为空

(e)

(a) 空二叉树

(b) 单结点二叉树 单结点二叉树

(e) 左、右子树都不空

二叉树的基本 树的基本形态 图6-3 二叉树的基本形态

6.2.2
性质1 在非空二叉树中, 层上至多有2 性质1:在非空二叉树中,第i层上至多有2i-1个结点
(i≧1)。 (i≧



证明:用数学归纳法证明。 证明:用数学归纳法证明。
当i=1时:只有一个根结点,21-1=20 =1,命题成 i=1时 只有一个根结点, =1, 立。 现假设对i>1时 处在第i 层上至多有2(i-1)现假设对i>1时,处在第i-1层上至多有2(i-1)-1个 结点。 结点。 由归纳假设知, 层上至多有2 个结点。 由归纳假设知,第i-1层上至多有2i-2个结点。由于 二叉树每个结点的度最大为2 故在第i 二叉树每个结点的度最大为2,故在第i层上最大结点 数为第i 层上最大结点数的2 数为第i-1层上最大结点数的2倍。 即 2×2i-2=2i-1 证毕

性质2 深度为k的二叉树至多有2 性质2:深度为k的二叉树至多有2k-1个结点

证明:深度为k 证明:深度为k的二叉树的最大的结点数为二叉树中每
层上的最大结点数之和。 层上的最大结点数之和。 由性质1 由性质1知,二叉树的第1层、第2层?第k层上的 二叉树的第1 结点数至多有: 结点数至多有: 20、21 …2k-1 。

∴ 总的结点数至多有: 20+21+ …+2k-1=2k-1 总的结点数至多有 结点数至多有:
证毕

性质3 对任何一棵二叉树,若其叶子结点数为n 性质3:对任何一棵二叉树,若其叶子结点数为n0,
+1。 度为2的结点数为n 度为2的结点数为n2,则n0=n2+1。

证明:设二叉树中度为1的结点数为n 证明:设二叉树中度为1的结点数为n1,二叉树中总
结点数为N 因为二叉树中所有结点均小于或等于2 结点数为N,因为二叉树中所有结点均小于或等于2, 则有: 则有:N=n0+n1+n2 再看二叉树中的分支数: 再看二叉树中的分支数:

除根结点外, 除根结点外,其余每个结点都有唯一的一个进入分 而所有这些分支都是由度为1 的结点射出的。 支,而所有这些分支都是由度为1和2的结点射出的。 为二叉树中的分支总数,则有: N=B+1 设B为二叉树中的分支总数,则有:

∴ ∴ ∴
即 证毕

B=n1+2×n2 +2× N=B+1=n1+2×n2+1 +2× n0+n1+n2=n1+2×n2+1 +2× n0=n2+1

满二叉树和完全二叉树
一棵深度为k且有2 一棵深度为k且有2k-1个结点的二叉树称为满二 个结点的二叉树称为满二 叉树(Full Tree)。 叉树(Full Binary Tree)。 如图6 如图6-4(a) 就是一棵深度为4的满二叉树。 就是一棵深度为4的满二叉树。

1 2 4 8 9 10 5 11 12 6 13 14 3 7 15 8 1 3 5 6 4 6 2 5 7 3 4 9 10 2 5

1 3 6 11 12 7

(a) 满二叉树

(b) 完全二叉树

1 2 4

(c) 非完全二叉树

特殊形态的二叉 二叉树 图6-4 特殊形态的二叉树

满二叉树的特点: 满二叉树的特点:
◆ 基本特点是每一层上的结点数总是最大结点数。 基本特点是每一层上的结点数总是最大结点数。 ◆ 满二叉树的所有的支结点都有左、右子树。 满二叉树的所有的支结点都有左、右子树。 ◆ 可对满二叉树的结点进行连续编号,若规定从根 可对满二叉树的结点进行连续编号, 结点开始, 自上而下、自左至右”的原则进行。 结点开始,按“自上而下、自左至右”的原则进行。 完全二叉树( 完全二叉树(Complete Binary Tree):如果深度为 Tree) k,由n个结点的二叉树,当且仅当其每一个结点都与 个结点的二叉树, 深度为k的满二叉树中编号从1 的结点一一对应, 深度为k的满二叉树中编号从1到n的结点一一对应,该 二叉树称为完全二叉树。 二叉树称为完全二叉树。 或深度为k的满二叉树中编号从1 或深度为k的满二叉树中编号从1到n的前n个结点 的前n 构成了一棵深度为k的完全二叉树。 构成了一棵深度为k的完全二叉树。 其中 2 k -1 ≦ n ≦ 2 k - 1 。

完全二叉树是满二叉树的一部分, 完全二叉树是满二叉树的一部分,而满二叉树是完 全二叉树的特例。 全二叉树的特例。

完全二叉树的特点: 完全二叉树的特点:
若完全二叉树的深度为k 若完全二叉树的深度为k ,则所有的叶子结点都出现 在第k层或k 对于任一结点, 在第k层或k-1层。对于任一结点,如果其右子树的最 大层次为l 则其左子树的最大层次为l 大层次为l,则其左子树的最大层次为l或l+1。

性质4 性质4:n个结点的完全二叉树深度为:?㏒2n? +1。 个结点的完全二叉树深度为:
其中符号: ?x?表示不大于x的最大整数。 表示不大于x的最大整数。 其中符号: ?x? 表示不小于x的最小整数。 表示不小于x的最小整数。

证明:假设完全二叉树的深度为k 则根据性质2 证明:假设完全二叉树的深度为k,则根据性质2及完
全二叉树的定义有: 全二叉树的定义有:

2k-1-1<n≦2k-1 1<n≦ ∴



2

k -1

≦n<2k 因为k是整数。 因为k是整数。 证毕

取对数得: 1<㏒ 取对数得:k-1<㏒2n<k k= ?㏒2n? +1

性质5 若对一棵有n个结点的完全二叉树(深度为└ 性质5:若对一棵有n个结点的完全二叉树(深度为└
㏒2n┘+1)的结点按层(从第1层到第?㏒2n? +1层)序自 1)的结点按层 从第1层到第? 的结点按层( 左至右进行编号,则对于编号为i n)的结点: 左至右进行编号,则对于编号为i(1≦i≦n)的结点: ⑴ 若i=1:则结点i是二叉树的根,无双亲结点; i=1:则结点i是二叉树的根,无双亲结点; 否则,若i>1,则其双亲结点编号是 ?i/2? 。 否则, i>1, i/2? ⑵ 如果2i>n:则结点i为叶子结点,无左

相关文章:
数据结构源代码(清华大学+严蔚敏)
搜 试试 7 帮助 全部 DOC PPT TXT PDF XLS 百度文库 教育专区 高等教育 工...数据结构源代码(清华大学+严蔚敏)_工学_高等教育_教育专区。完整的源代码void...
数据结构源代码(清华大学+严蔚敏)
搜 试试 7 帮助 全部 DOC PPT TXT PDF XLS 百度文库 教育专区 高等教育 工...数据结构源代码(清华大学+严蔚敏)_工学_高等教育_教育专区。书上的算法源代码voi...
数据结构复习重点归纳笔记[清华严蔚敏版]
搜试试 3 帮助 全部 DOC PPT TXT PDF XLS 百度文库 数据结构复习重点归纳笔记[清华严蔚敏版] 暂无评价|0人阅读|0次下载|举报文档数据结构复习重点归纳笔记[...
数据结构严蔚敏课件ch2
搜 试试 帮助 全部 DOC PPT TXT PDF XLS 百度文库 专业资料 IT/计算机...数据结构-清华大学严蔚敏P... 814页 免费 第3章 文法和语言 暂无评价 64页 ...
数据结构复习重点归纳笔记[清华严蔚敏版]
数据结构复习重点归纳笔记[清华严蔚敏版] 数据结构复习重点归纳笔记[清华严蔚敏版] 数据结构复习重点归纳[适于清华严版教材] 一、数据结构的章节结构及重点构成 数据...
清华大学严蔚敏数据结构题集答案
搜 试试 7 帮助 全部 DOC PPT TXT PDF XLS 百度文库 教育专区 资格考试/...清华大学严蔚敏数据结构题集答案_IT认证_资格考试/认证_教育专区。清华大学严蔚敏...
数据结构_严蔚敏_清华大学出版社_习题及答案
数据结构严蔚敏PPT 清华大... 814页 10财富值 数据结构(c语言版)课件 第... 78页 1财富值 数据结构(C语言版)严蔚敏清... 54页 1财富值 数据结构(c语言...
清华-严蔚敏《数据结构》习题及答案
搜 试试 7 帮助 全部 DOC PPT TXT PDF XLS 百度文库 教育专区 高等教育 工...清华-严蔚敏数据结构》习题及答案_工学_高等教育_教育专区。习题及答案第...
数据结构习题集答案(c版)(清华大学 严蔚敏)
搜 试试 帮助 全部 DOC PPT TXT PDF XLS 百度文库 教育专区 高等教育 理学...这是数据结构习题集答案(c版)(清华大学 严蔚敏) 别弄错了这是数据结构习题集答案...
数据结构复习重点归纳(适于清华严蔚敏)_格式修改_适合...
清华严蔚敏 数据结构 C 语言版 复习归纳 一、数据结构的章节结构及重点构成数据结构学科的章节划分基本上为:概论,线性表,栈和队列,串,多维数组和广义表, 树和二叉...
更多相关标签: