《【课件】计算机考研基础讲义 数据结构基础》由会员分享，可在线阅读，更多相关《【课件】计算机考研基础讲义 数据结构基础（108页珍藏版）》请在金锄头文库上搜索。
1、计算机考研小组计算机考研小组计算机考研小组计算机考研小组(100)(100)(100)(100)202120212021202120212021年计算机考研根底班讲义年计算机考研根底班讲义年计算机考研根底班讲义年计算机考研根底班讲义年计算机考研根底班讲义年计算机考研根底班讲义第一章第一章 绪论绪论n n什么是数据结构直观定义：数据结构是研究程序设计中计算直观定义：数据结构是研究程序设计中计算直观定义：数据结构是研究程序设计中计算直观定义：数据结构是研究程序设计中计算机操作的对象以及它们之间关系和运算的一机操作的对象以及它们之间关系和运算的一机操作的对象以及它们之间关系和运算的一机操作的对象以及
2、它们之间关系和运算的一门学科。门学科。门学科。门学科。数据结构是指数据之间的关系数据结构是指数据之间的关系数据结构是指数据之间的关系数据结构是指数据之间的关系 按某种关系组织起来的一批数据。以一按某种关系组织起来的一批数据。以一按某种关系组织起来的一批数据。以一按某种关系组织起来的一批数据。以一定的存储方式把它们存储到计算机的存储器定的存储方式把它们存储到计算机的存储器定的存储方式把它们存储到计算机的存储器定的存储方式把它们存储到计算机的存储器中，并在这些数据上定义一个运算集合，这中，并在这些数据上定义一个运算集合，这中，并在这些数据上定义一个运算集合，这中，并在这些数据上定义一个运算集合，这
3、就是数据结构。就是数据结构。就是数据结构。就是数据结构。学习数据结构的重要性学习数据结构的重要性“ “数据结构在计算机科学中是一门综合性的专数据结构在计算机科学中是一门综合性的专数据结构在计算机科学中是一门综合性的专数据结构在计算机科学中是一门综合性的专业根底课业根底课业根底课业根底课, , 在考研中占很大的分值。在考研中占很大的分值。在考研中占很大的分值。在考研中占很大的分值。数据结构是介于数学、计算机硬件和计算机软件数据结构是介于数学、计算机硬件和计算机软件数据结构是介于数学、计算机硬件和计算机软件数据结构是介于数学、计算机硬件和计算机软件三者之间的一门核心课程。三者之间的一门核心课程。三
4、者之间的一门核心课程。三者之间的一门核心课程。数据结构这一门课的内容不仅是一般程序设计数据结构这一门课的内容不仅是一般程序设计数据结构这一门课的内容不仅是一般程序设计数据结构这一门课的内容不仅是一般程序设计特别是非数值性程序设计的根底，而且是设特别是非数值性程序设计的根底，而且是设特别是非数值性程序设计的根底，而且是设特别是非数值性程序设计的根底，而且是设计和实现编译程序、操作系统、数据库系统及计和实现编译程序、操作系统、数据库系统及计和实现编译程序、操作系统、数据库系统及计和实现编译程序、操作系统、数据库系统及其他系统程序的重要根底。其他系统程序的重要根底。其他系统程序的重要根底。其他系统程
5、序的重要根底。数据结构的概念数据结构的概念一、根本概念一、根本概念数据：能输入计算机且被能计算机处理的一切数据：能输入计算机且被能计算机处理的一切对象。对象。数据元素：对现实世界中某独立个体的数据描数据元素：对现实世界中某独立个体的数据描述。述。数据项：具有独立意义的最小数据单位。数据项：具有独立意义的最小数据单位。数据类型：每个数据项必须属于某确定的数据数据类型：每个数据项必须属于某确定的数据类型。类型。根底根底根底根底 数据的逻辑结构数据的逻辑结构一、根本概念一、根本概念数据对象：具有相同特征的数据元素的集数据对象：具有相同特征的数据元素的集合。合。关系：在数据对象中各数据元素之间存在关系
6、：在数据对象中各数据元素之间存在着某种关系或联系。这种关系反映着某种关系或联系。这种关系反映了该数据对象中数据元素所固有的一种了该数据对象中数据元素所固有的一种结构。在数据处理领域，通常把数据之结构。在数据处理领域，通常把数据之间这种固有的关系简单的用前驱和后继间这种固有的关系简单的用前驱和后继关系描述。关系描述。数据的逻辑结构数据的逻辑结构二、数据的逻辑结构二、数据的逻辑结构设设D表示数据元素的集合，表示数据元素的集合，R表示表示D上的关上的关系的集合，那么一个数据结构系的集合，那么一个数据结构B可表示为：可表示为：B = D ，R 由此可见数据结构由两局部构成由此可见数据结构由两局部构成1
7、表示各元素的信息表示各元素的信息 D2表示数据之间关系的信息表示数据之间关系的信息R一般用二元组表示一般用二元组表示D中各数据元素之间的中各数据元素之间的前驱、后继关系。假设前驱、后继关系。假设a,b是是D中的两个中的两个元素，那么二元组元素，那么二元组表示表示a是是b的前驱，的前驱，b是是a的后继。的后继。1.3 数据的逻辑结构数据的逻辑结构三、数据结构的分类三、数据结构的分类三、数据结构的分类三、数据结构的分类n n线性结构：线性结构：线性结构：线性结构：除了一个根结点外，其他各结点有除了一个根结点外，其他各结点有除了一个根结点外，其他各结点有除了一个根结点外，其他各结点有唯一的前驱；除了
8、一个终端结点外，其他各结点唯一的前驱；除了一个终端结点外，其他各结点唯一的前驱；除了一个终端结点外，其他各结点唯一的前驱；除了一个终端结点外，其他各结点有唯一的后继。有唯一的后继。有唯一的后继。有唯一的后继。n n树状结构：树状结构：树状结构：树状结构：除了一个根结点外，各结点有唯一除了一个根结点外，各结点有唯一除了一个根结点外，各结点有唯一除了一个根结点外，各结点有唯一的前驱；所有的结点都可以有多个后继。的前驱；所有的结点都可以有多个后继。的前驱；所有的结点都可以有多个后继。的前驱；所有的结点都可以有多个后继。n n网状结构：网状结构：网状结构：网状结构：各结点可以有多个前驱或多个后继。各结
9、点可以有多个前驱或多个后继。各结点可以有多个前驱或多个后继。各结点可以有多个前驱或多个后继。1.4 数据的存储结构数据的存储结构n n数据结构在计算机中的表示称为数据的存储结构。数据结构在计算机中的表示称为数据的存储结构。数据结构在计算机中的表示称为数据的存储结构。数据结构在计算机中的表示称为数据的存储结构。n n数据结构包括结点的值及结点之间的关系，其存储结数据结构包括结点的值及结点之间的关系，其存储结数据结构包括结点的值及结点之间的关系，其存储结数据结构包括结点的值及结点之间的关系，其存储结构除了必须存储结点的值外，还得能以直接或隐含的构除了必须存储结点的值外，还得能以直接或隐含的构除了必
10、须存储结点的值外，还得能以直接或隐含的构除了必须存储结点的值外，还得能以直接或隐含的方式表达出结点之间的关系。方式表达出结点之间的关系。方式表达出结点之间的关系。方式表达出结点之间的关系。n n四种根本的存储方式：四种根本的存储方式：四种根本的存储方式：四种根本的存储方式：n n1 1、顺序方式、顺序方式、顺序方式、顺序方式n n顺序结构最适合于线性结构，它把逻辑上相邻的结点顺序结构最适合于线性结构，它把逻辑上相邻的结点顺序结构最适合于线性结构，它把逻辑上相邻的结点顺序结构最适合于线性结构，它把逻辑上相邻的结点存放到物理上相邻的存储单元中，顺序存储结构只存存放到物理上相邻的存储单元中，顺序存储
11、结构只存存放到物理上相邻的存储单元中，顺序存储结构只存存放到物理上相邻的存储单元中，顺序存储结构只存储结点的值，不存储结点的关系，结点的关系通过存储结点的值，不存储结点的关系，结点的关系通过存储结点的值，不存储结点的关系，结点的关系通过存储结点的值，不存储结点的关系，结点的关系通过存储单元相邻关系隐含表示出来。储单元相邻关系隐含表示出来。储单元相邻关系隐含表示出来。储单元相邻关系隐含表示出来。1.4 数据的存储结构数据的存储结构n n2 2、链接方式、链接方式、链接方式、链接方式n n链接存储方式不仅存储结点的值，而且还存储结链接存储方式不仅存储结点的值，而且还存储结链接存储方式不仅存储结点的
12、值，而且还存储结链接存储方式不仅存储结点的值，而且还存储结点之间的关系。它利用结点附加的指针字段，存点之间的关系。它利用结点附加的指针字段，存点之间的关系。它利用结点附加的指针字段，存点之间的关系。它利用结点附加的指针字段，存储其后继结点的地址。储其后继结点的地址。储其后继结点的地址。储其后继结点的地址。n n3 3、索引方式、索引方式、索引方式、索引方式n n在线性结构中，各结点可以依前驱、后继关系排在线性结构中，各结点可以依前驱、后继关系排在线性结构中，各结点可以依前驱、后继关系排在线性结构中，各结点可以依前驱、后继关系排成一个序列成一个序列成一个序列成一个序列a1,a2,a3, an)a
13、1,a2,a3, an)。每个结点。每个结点。每个结点。每个结点aiai在在在在序列中都对应一个序号序列中都对应一个序号序列中都对应一个序号序列中都对应一个序号i i序号序号序号序号i i也称为结点也称为结点也称为结点也称为结点aiai的索引的索引的索引的索引号。索引存储就是通过建立一个附加的索引表，号。索引存储就是通过建立一个附加的索引表，号。索引存储就是通过建立一个附加的索引表，号。索引存储就是通过建立一个附加的索引表，然后利用索引表中的索引项的值来确定结点的实然后利用索引表中的索引项的值来确定结点的实然后利用索引表中的索引项的值来确定结点的实然后利用索引表中的索引项的值来确定结点的实际存
14、储单元的地址。际存储单元的地址。际存储单元的地址。际存储单元的地址。1.4 数据的存储结构数据的存储结构n n4 4、散列方式、散列方式、散列方式、散列方式n n利用该结点的值确定该结点的存储单元地址。利用该结点的值确定该结点的存储单元地址。利用该结点的值确定该结点的存储单元地址。利用该结点的值确定该结点的存储单元地址。1.5 数据运算和算法数据运算和算法1 1、数据运算、数据运算、数据运算、数据运算按一定的逻辑结构把数据组织起来，采用适当的存储方式按一定的逻辑结构把数据组织起来，采用适当的存储方式按一定的逻辑结构把数据组织起来，采用适当的存储方式按一定的逻辑结构把数据组织起来，采用适当的存储
15、方式把数据结构存储到计算机中，最终的目的是为了有效地把数据结构存储到计算机中，最终的目的是为了有效地把数据结构存储到计算机中，最终的目的是为了有效地把数据结构存储到计算机中，最终的目的是为了有效地处理数据，提高数据的运算效率。处理数据，提高数据的运算效率。处理数据，提高数据的运算效率。处理数据，提高数据的运算效率。1 1插入：往数据结构中添加新的结点称为插入。插入：往数据结构中添加新的结点称为插入。插入：往数据结构中添加新的结点称为插入。插入：往数据结构中添加新的结点称为插入。2 2删除：把指定的结点从数据结构中删除。删除：把指定的结点从数据结构中删除。删除：把指定的结点从数据结构中删除。删除
16、：把指定的结点从数据结构中删除。3 3更新：改变指定结点的值或者改变某些结点的关系称为更新：改变指定结点的值或者改变某些结点的关系称为更新：改变指定结点的值或者改变某些结点的关系称为更新：改变指定结点的值或者改变某些结点的关系称为更新。更新。更新。更新。4 4查找：在数据结构中查找某些满足条件的结点。查找：在数据结构中查找某些满足条件的结点。查找：在数据结构中查找某些满足条件的结点。查找：在数据结构中查找某些满足条件的结点。5 5排序：对线性表的各结点，按指定数据项的值从小到大排序：对线性表的各结点，按指定数据项的值从小到大排序：对线性表的各结点，按指定数据项的值从小到大排序：对线性表的各结点
17、，按指定数据项的值从小到大或从大到小的重新排列。排序运算实际上是破坏线性表或从大到小的重新排列。排序运算实际上是破坏线性表或从大到小的重新排列。排序运算实际上是破坏线性表或从大到小的重新排列。排序运算实际上是破坏线性表的旧关系，重新建立线性表的新关系。的旧关系，重新建立线性表的新关系。的旧关系，重新建立线性表的新关系。的旧关系，重新建立线性表的新关系。1.5 数据运算和算法数据运算和算法2 2、算法、算法、算法、算法算法是对特定问题求解步骤的一种描述。算法是对特定问题求解步骤的一种描述。算法是对特定问题求解步骤的一种描述。算法是对特定问题求解步骤的一种描述。算法应具有的几个特征：算法应具有的几
18、个特征：算法应具有的几个特征：算法应具有的几个特征：1 1有穷性：算法应在计算机存储资源容许的条件下，在一有穷性：算法应在计算机存储资源容许的条件下，在一有穷性：算法应在计算机存储资源容许的条件下，在一有穷性：算法应在计算机存储资源容许的条件下，在一定时间内执行完毕。定时间内执行完毕。定时间内执行完毕。定时间内执行完毕。2 2确定性：算法的每一步骤应定义明确，没有二义。确定性：算法的每一步骤应定义明确，没有二义。确定性：算法的每一步骤应定义明确，没有二义。确定性：算法的每一步骤应定义明确，没有二义。3 3可行性：算法是可以被计算机执行的。当输入正确的数可行性：算法是可以被计算机执行的。当输入正
19、确的数可行性：算法是可以被计算机执行的。当输入正确的数可行性：算法是可以被计算机执行的。当输入正确的数据后，应得到正确的结果。据后，应得到正确的结果。据后，应得到正确的结果。据后，应得到正确的结果。1.5 数据运算和算法数据运算和算法3 3、算法的评价、算法的评价、算法的评价、算法的评价n n对算法评价的几个指标对算法评价的几个指标对算法评价的几个指标对算法评价的几个指标n n空间复杂度空间复杂度空间复杂度空间复杂度n n空间复杂度是指执行算法所需要的辅助空间空间复杂度是指执行算法所需要的辅助空间空间复杂度是指执行算法所需要的辅助空间空间复杂度是指执行算法所需要的辅助空间大小。大小。大小。大小
20、。n n时间复杂度时间复杂度时间复杂度时间复杂度n n时间复杂度是指执行完算法所需的运算次数。时间复杂度是指执行完算法所需的运算次数。时间复杂度是指执行完算法所需的运算次数。时间复杂度是指执行完算法所需的运算次数。第二章第二章 线性表线性表n n线性表是一种最简单、最常用的数据结构。线性表是一种最简单、最常用的数据结构。线性表是一种最简单、最常用的数据结构。线性表是一种最简单、最常用的数据结构。n n线性表的主要存储结构有两种：顺序存储结线性表的主要存储结构有两种：顺序存储结线性表的主要存储结构有两种：顺序存储结线性表的主要存储结构有两种：顺序存储结构和链接存储结构。构和链接存储结构。构和链接
21、存储结构。构和链接存储结构。2.1 线性表的定义及根本运算线性表的定义及根本运算n n一、线性表的定义一、线性表的定义一、线性表的定义一、线性表的定义n n线性表是由线性表是由线性表是由线性表是由n(n0)n(n0)个性质相同的数据元素个性质相同的数据元素个性质相同的数据元素个性质相同的数据元素a1,a2,a3,ana1,a2,a3,an组成的有限序列，记为组成的有限序列，记为组成的有限序列，记为组成的有限序列，记为(a1,a2,a3,an)(a1,a2,a3,an)。n n二、线性表的根本运算二、线性表的根本运算二、线性表的根本运算二、线性表的根本运算n n1 1置线性表为空表；置线性表为空
22、表；置线性表为空表；置线性表为空表；n n2 2求线性表的长度；求线性表的长度；求线性表的长度；求线性表的长度；n n3 3读取线性表中的第读取线性表中的第读取线性表中的第读取线性表中的第i i个元素；个元素；个元素；个元素；n n4 4修改线性表中的第修改线性表中的第修改线性表中的第修改线性表中的第i i个元素；个元素；个元素；个元素；n n5 5查找线性表中具有某个特征值的数据元素；查找线性表中具有某个特征值的数据元素；查找线性表中具有某个特征值的数据元素；查找线性表中具有某个特征值的数据元素；2.1 线性表的定义及根本运算线性表的定义及根本运算n n二、线性表的根本运算二、线性表的根本运
23、算二、线性表的根本运算二、线性表的根本运算n n6 6在线性表的第在线性表的第在线性表的第在线性表的第i i个数据元素之前或之后插入一个数据元素之前或之后插入一个数据元素之前或之后插入一个数据元素之前或之后插入一个新的数据元素；个新的数据元素；个新的数据元素；个新的数据元素；n n7 7删除线性表中第删除线性表中第删除线性表中第删除线性表中第i i个数据元素或满足给定条件个数据元素或满足给定条件个数据元素或满足给定条件个数据元素或满足给定条件的第一个数据元素；的第一个数据元素；的第一个数据元素；的第一个数据元素；n n8 8对线性表中的所有元素按照给定的关键字大对线性表中的所有元素按照给定的关
24、键字大对线性表中的所有元素按照给定的关键字大对线性表中的所有元素按照给定的关键字大小进行排序。小进行排序。小进行排序。小进行排序。2.2 线性表的顺序存储结构及运算线性表的顺序存储结构及运算一、一、一、一、线性表的顺序存储结构线性表的顺序存储结构线性表的顺序存储结构线性表的顺序存储结构 线性表的顺序存储结构是将线性表中的结点按其逻辑线性表的顺序存储结构是将线性表中的结点按其逻辑线性表的顺序存储结构是将线性表中的结点按其逻辑线性表的顺序存储结构是将线性表中的结点按其逻辑顺序依次存放在内存中一组连续的存储单元中，即把线性顺序依次存放在内存中一组连续的存储单元中，即把线性顺序依次存放在内存中一组连续
25、的存储单元中，即把线性顺序依次存放在内存中一组连续的存储单元中，即把线性表中相邻的结点存放在地址相邻的内存单元中。表中相邻的结点存放在地址相邻的内存单元中。表中相邻的结点存放在地址相邻的内存单元中。表中相邻的结点存放在地址相邻的内存单元中。 线性表在线性表在线性表在线性表在c c语言中用一维数组表示。语言中用一维数组表示。语言中用一维数组表示。语言中用一维数组表示。 c c语言的描述语言的描述语言的描述语言的描述 Typedef int ET;Typedef int ET; #define maxlen 1000 #define maxlen 1000 ET smaxlen; ET smaxl
26、en;2.2 线性表的顺序存储结构及运算线性表的顺序存储结构及运算一、线性表的顺序存储结构一、线性表的顺序存储结构一、线性表的顺序存储结构一、线性表的顺序存储结构线性表线性表线性表线性表C C语言描述的说明：语言描述的说明：语言描述的说明：语言描述的说明： 在在在在C C语言中，数组的下标是从语言中，数组的下标是从语言中，数组的下标是从语言中，数组的下标是从0 0开始的，数据结构开始的，数据结构开始的，数据结构开始的，数据结构中的结点的序号是从一开始的。因此在线性表中的中的结点的序号是从一开始的。因此在线性表中的中的结点的序号是从一开始的。因此在线性表中的中的结点的序号是从一开始的。因此在线性
27、表中的第一个元素是指第一个元素是指第一个元素是指第一个元素是指S0S0。 两个相邻结点两个相邻结点两个相邻结点两个相邻结点aiai和和和和a i+1a i+1的存储位置记为的存储位置记为的存储位置记为的存储位置记为 LOC LOC ai ai 和和和和LOCLOC a i+1 a i+1 ，那么结点满足以，那么结点满足以，那么结点满足以，那么结点满足以下关系下关系下关系下关系 LOC LOC a i+1 a i+1 = LOC= LOC ai ai +1+12.2 线性表的顺序存储结构及运算线性表的顺序存储结构及运算二、线性表的运算二、线性表的运算二、线性表的运算二、线性表的运算1 1、插入运
28、算的算法描述：、插入运算的算法描述：、插入运算的算法描述：、插入运算的算法描述：int insertqlist(int i,ET x,ET s,int *np)int insertqlist(int i,ET x,ET s,int *np) int j,n; int j,n; n=*np; n=*np; if (in+1) if (in+1) return(0); return(0); else else for (j=n;j=i;j-) for (j=n;j=i;j-) sj=sj-1; sj=sj-1; sj=x; sj=x; *np=+n; *np=+n; return(1); retu
29、rn(1); 2.2 线性表的顺序存储结构及运算线性表的顺序存储结构及运算二、线性表的运算二、线性表的运算二、线性表的运算二、线性表的运算2 2、删除运算的算法描述：、删除运算的算法描述：、删除运算的算法描述：、删除运算的算法描述：int delqlist(int i,ET s,int *np)int delqlist(int i,ET s,int *np) int j,n; int j,n; n=*np; n=*np; if (in) if (in) return(0); return(0); else else for (j=i;jn;j+) for (j=i;jn;j+) sj-1=sj
30、; sj-1=sj; *np=-n; *np=-n; return(1); return(1); 2.2 线性表的顺序存储结构及运算线性表的顺序存储结构及运算二、线性表的运算二、线性表的运算二、线性表的运算二、线性表的运算3 3、查找运算的算法描述：、查找运算的算法描述：、查找运算的算法描述：、查找运算的算法描述：int fincl(ET x,ET s,int n)int fincl(ET x,ET s,int n) int j; int j; for (i=0;in;i+) for (i=0;idata=0;p-link=NULL; head=p; p-data=0;p-link=NULL;
31、 head=p; for (i=1;i=n;i+) for (i=1;idata); scanf(%d,&q-data); q-link=NULL; p-link=q;p=p-link; q-link=NULL; p-link=q;p=p-link; return (head); return (head); 2.3 线性表的链接存储结构及运算线性表的链接存储结构及运算2 2、查找链表中的、查找链表中的、查找链表中的、查找链表中的 X X 查找链表中是否存在结点查找链表中是否存在结点查找链表中是否存在结点查找链表中是否存在结点X X，算法的根本思想为：，算法的根本思想为：，算法的根本思想为：，
32、算法的根本思想为： 从表头指针指向的第一个结点开始，依次把表中结从表头指针指向的第一个结点开始，依次把表中结从表头指针指向的第一个结点开始，依次把表中结从表头指针指向的第一个结点开始，依次把表中结点的数据域和给定值点的数据域和给定值点的数据域和给定值点的数据域和给定值X X 进行比较，直到某个结点的进行比较，直到某个结点的进行比较，直到某个结点的进行比较，直到某个结点的数据域的值等于给定值数据域的值等于给定值数据域的值等于给定值数据域的值等于给定值X X 既查找成功，那么返既查找成功，那么返既查找成功，那么返既查找成功，那么返回该结点的地址；如果查找到表尾仍未找到既查回该结点的地址；如果查找到
33、表尾仍未找到既查回该结点的地址；如果查找到表尾仍未找到既查回该结点的地址；如果查找到表尾仍未找到既查找失败，那么返回找失败，那么返回找失败，那么返回找失败，那么返回NULLNULL。查找单链表中结点X的算法描述：NODE *found(NODE *head,ET x) NODE *p; p=head-link; while(p!=NULL)&(p-data!=x) p=p-link; return (p); 2.3 线性表的链接存储结构及运算线性表的链接存储结构及运算3 3、在单链表中插入新结点、在单链表中插入新结点、在单链表中插入新结点、在单链表中插入新结点X X 在链表中的某一结点在链表中
34、的某一结点在链表中的某一结点在链表中的某一结点p p 之后插入一个数据为之后插入一个数据为之后插入一个数据为之后插入一个数据为X X 的新结的新结的新结的新结点。过程如下：点。过程如下：点。过程如下：点。过程如下： 1 1生成一个新结点生成一个新结点生成一个新结点生成一个新结点q q ，将，将，将，将X X 赋给赋给赋给赋给q-data;q-data; 2 2修改有关结点的指针域：将原修改有关结点的指针域：将原修改有关结点的指针域：将原修改有关结点的指针域：将原p p 结点的后继作结点的后继作结点的后继作结点的后继作为为为为q q 结点的后继，结点的后继，结点的后继，结点的后继，q q 结点作
35、为结点作为结点作为结点作为p p 结点的后继。结点的后继。结点的后继。结点的后继。在单链表中插入新结点在单链表中插入新结点X X的算法描述：的算法描述：void insert(NODE *head,NODE *p,ET x)void insert(NODE *head,NODE *p,ET x) NODE *q; NODE *q; q=(NODE *)malloc(sizeof(NODE); q=(NODE *)malloc(sizeof(NODE); q-data=x; q-data=x; if (head-link=NULL) if (head-link=NULL) head-link=q
36、;q-link=NULL; head-link=q;q-link=NULL; else else q-link=p-link;p-link=q; q-link=p-link;p-link=q; 2.3 线性表的链接存储结构及运算线性表的链接存储结构及运算4 4、删除单链表中的结点、删除单链表中的结点、删除单链表中的结点、删除单链表中的结点X X 删除单链表中的结点删除单链表中的结点删除单链表中的结点删除单链表中的结点X X ，并由系统收回其占用的存储空，并由系统收回其占用的存储空，并由系统收回其占用的存储空，并由系统收回其占用的存储空间。过程如下：间。过程如下：间。过程如下：间。过程如下： 1
37、 1设定两指针设定两指针设定两指针设定两指针p p 和和和和q q ，p p 指针指向被删除结点；指针指向被删除结点；指针指向被删除结点；指针指向被删除结点；q q 为跟踪结点，指向被删除结点的前驱结点为跟踪结点，指向被删除结点的前驱结点为跟踪结点，指向被删除结点的前驱结点为跟踪结点，指向被删除结点的前驱结点; ; 2 2p p 从表头指针从表头指针从表头指针从表头指针headhead指向的第一个结点开始向后依指向的第一个结点开始向后依指向的第一个结点开始向后依指向的第一个结点开始向后依次进行搜索。当次进行搜索。当次进行搜索。当次进行搜索。当p-datap-data等于等于等于等于X X 时，
38、被删除结点找到。时，被删除结点找到。时，被删除结点找到。时，被删除结点找到。 3 3修改修改修改修改p p 的前驱结点的前驱结点的前驱结点的前驱结点q q 的指针域：使被删除结点的的指针域：使被删除结点的的指针域：使被删除结点的的指针域：使被删除结点的后继结点成为其前驱结点的后继结点，既后继结点成为其前驱结点的后继结点，既后继结点成为其前驱结点的后继结点，既后继结点成为其前驱结点的后继结点，既q-link=p-q-link=p-linklink，p p结点被删除，然后再释放存储空间。结点被删除，然后再释放存储空间。结点被删除，然后再释放存储空间。结点被删除，然后再释放存储空间。在单链表中删除结
39、点在单链表中删除结点X X的算法描述：的算法描述：void delete(NODE *head,ET x)void delete(NODE *head,ET x) NODE *p,*q; NODE *p,*q; p=head; q=p; p=head; q=p; p=p-link; p=p-link; while(p!=NULL)&(p-data!=x) while(p!=NULL)&(p-data!=x) q=p;p=p-link; q=p;p=p-link; if (p=NULL) if (p=NULL) printf(Not found!n); printf(Not found!n);
40、else else q-link=p-link;free(p); q-link=p-link;free(p); 2.3 线性表的链接存储结构及运算线性表的链接存储结构及运算三、循环链表三、循环链表三、循环链表三、循环链表 链表中的最后一个结点的指针指向链表中第链表中的最后一个结点的指针指向链表中第链表中的最后一个结点的指针指向链表中第链表中的最后一个结点的指针指向链表中第一个结点，使链表形成一个环行，此链表称循一个结点，使链表形成一个环行，此链表称循一个结点，使链表形成一个环行，此链表称循一个结点，使链表形成一个环行，此链表称循环链表。环链表。环链表。环链表。 循环链表是线性链表的一种变形。其
41、优点是循环链表是线性链表的一种变形。其优点是循环链表是线性链表的一种变形。其优点是循环链表是线性链表的一种变形。其优点是从链表中任何一个结点出发都可以访问到表中从链表中任何一个结点出发都可以访问到表中从链表中任何一个结点出发都可以访问到表中从链表中任何一个结点出发都可以访问到表中的所有结点。的所有结点。的所有结点。的所有结点。 在循环链表中为了使空表和非空表处理一致，在循环链表中为了使空表和非空表处理一致，在循环链表中为了使空表和非空表处理一致，在循环链表中为了使空表和非空表处理一致，可以附加一个表头结点。可以附加一个表头结点。可以附加一个表头结点。可以附加一个表头结点。2.3 线性表的链接存
42、储结构及运算线性表的链接存储结构及运算三、循环链表三、循环链表非空表非空表a)a)headheadheadhead空表空表b)b)(1)(1)在头指针为在头指针为headhead的循环链表查找值为的循环链表查找值为x x的前的前驱结点。驱结点。NODE *looknode(head,x)NODE *looknode(head,x) ET x;NODE *head; ET x;NODE *head; NODE *p; NODE *p; p=head; p=head; while (p-link!=head)& while (p-link!=head)& (p-link)-data)!=x) (p
43、-link)-data)!=x) p=-link; p=-link; return (p); return (p); (2)(2)在头指针为在头指针为headhead的循环链表在值为的循环链表在值为x x的结点的结点之前插入一个值为之前插入一个值为b b的新结点。的新结点。NODE insnode(head,x,b)NODE insnode(head,x,b) ET x,b;NODE *head; ET x,b;NODE *head; NODE *p,*q; NODE *p,*q; p=(NODE *)malloc(sizeof(NODE); p=(NODE *)malloc(sizeof(N
44、ODE); p-data=b; p-data=b; q=looknode(head,x); q=looknode(head,x); p-link=q-link; p-link=q-link; q-link=p; q-link=p; return ; return ; (3)(3)在头指针为在头指针为headhead的循环链表中，删除值为的循环链表中，删除值为x x的结点。的结点。Void delnode (head,x)Void delnode (head,x) ET x;NODE *head; ET x;NODE *head; NODE *p,*q; NODE *p,*q; q=lookno
45、de(head,x); q=looknode(head,x); if (q-link=head) if (q-link=head) printf(“No this node the list!n printf(“No this node the list!n) ) return; return; p=q-link;q-link=p-link;free(p); p=q-link;q-link=p-link;free(p); return ; return ; 2.3 线性表的链接存储结构及运算线性表的链接存储结构及运算四、循环链表四、循环链表四、循环链表四、循环链表 一个链表的每一个结点含有两个
46、指一个链表的每一个结点含有两个指一个链表的每一个结点含有两个指一个链表的每一个结点含有两个指针域，一个指针指向其前驱结点，另一针域，一个指针指向其前驱结点，另一针域，一个指针指向其前驱结点，另一针域，一个指针指向其前驱结点，另一个指针指向其后继结点，这样的链表称个指针指向其后继结点，这样的链表称个指针指向其后继结点，这样的链表称个指针指向其后继结点，这样的链表称为双向链表。为双向链表。为双向链表。为双向链表。五、双向链表五、双向链表headhead llinkllinkrlinkrlinkdatadata带头结点的双向链表带头结点的双向链表带头结点的双向链表带头结点的双向链表双向链表的结点结构
47、双向链表的结点结构双向链表的结点结构双向链表的结点结构2.4 数组数组一、数组的定义一、数组的定义 数组是由一组类型相同的数据元素构造数组是由一组类型相同的数据元素构造而成。而成。 假设数组元素只含有一个下标，这样的假设数组元素只含有一个下标，这样的数组称为一维数组。数组称为一维数组。 当一个数组的每一个数组元素都含有两当一个数组的每一个数组元素都含有两个下标时，该数组称为两维数组。个下标时，该数组称为两维数组。2.4 数组数组二、数组的存储结构二、数组的存储结构二、数组的存储结构二、数组的存储结构 数组是一种顺序存储结构。也就是将数组元素顺序数组是一种顺序存储结构。也就是将数组元素顺序数组是
48、一种顺序存储结构。也就是将数组元素顺序数组是一种顺序存储结构。也就是将数组元素顺序地存放在一片连续的存储单元中。地存放在一片连续的存储单元中。地存放在一片连续的存储单元中。地存放在一片连续的存储单元中。三、规那么矩阵的压缩存储三、规那么矩阵的压缩存储三、规那么矩阵的压缩存储三、规那么矩阵的压缩存储 有时矩阵中包含大量的零元素或某一确定值的元有时矩阵中包含大量的零元素或某一确定值的元有时矩阵中包含大量的零元素或某一确定值的元有时矩阵中包含大量的零元素或某一确定值的元素，为了节省存储空间，可以对这类矩阵采用压缩素，为了节省存储空间，可以对这类矩阵采用压缩素，为了节省存储空间，可以对这类矩阵采用压缩
49、素，为了节省存储空间，可以对这类矩阵采用压缩存储。存储。存储。存储。 所谓压缩存储是指对零元素不分配存储空间，而只所谓压缩存储是指对零元素不分配存储空间，而只所谓压缩存储是指对零元素不分配存储空间，而只所谓压缩存储是指对零元素不分配存储空间，而只对非零元素进行存储。压缩存储必须能够表达矩阵的对非零元素进行存储。压缩存储必须能够表达矩阵的对非零元素进行存储。压缩存储必须能够表达矩阵的对非零元素进行存储。压缩存储必须能够表达矩阵的逻辑结构。逻辑结构。逻辑结构。逻辑结构。 2.4 数组数组四、稀疏矩阵及存储四、稀疏矩阵及存储四、稀疏矩阵及存储四、稀疏矩阵及存储 当一个矩阵的非零元素的个数远远少于零元
50、素当一个矩阵的非零元素的个数远远少于零元素当一个矩阵的非零元素的个数远远少于零元素当一个矩阵的非零元素的个数远远少于零元素的个数时，称该矩阵为稀疏矩阵。对稀疏矩阵的的个数时，称该矩阵为稀疏矩阵。对稀疏矩阵的的个数时，称该矩阵为稀疏矩阵。对稀疏矩阵的的个数时，称该矩阵为稀疏矩阵。对稀疏矩阵的存储方式常采用压缩存储。方法有两种：三元组存储方式常采用压缩存储。方法有两种：三元组存储方式常采用压缩存储。方法有两种：三元组存储方式常采用压缩存储。方法有两种：三元组表和十字链表。表和十字链表。表和十字链表。表和十字链表。 1 1、在稀疏矩阵中，每一个非零元素可以用它所、在稀疏矩阵中，每一个非零元素可以用它
51、所、在稀疏矩阵中，每一个非零元素可以用它所、在稀疏矩阵中，每一个非零元素可以用它所在的行号在的行号在的行号在的行号 i i、列号、列号、列号、列号 j j以及元素值以及元素值以及元素值以及元素值 a a i ji j组成的三元组组成的三元组组成的三元组组成的三元组( ( i, j, a i, j, a i ji j) )来表示。来表示。来表示。来表示。 三元组的结点定义：三元组的结点定义：三元组的结点定义：三元组的结点定义： typedef struct nodetypedef struct node int r, c ; ET v; NODE; int r, c ; ET v; NODE;2
52、.4 数组数组 40 0 1 00 0 2 0 090 0 0 00 0 0 0 70 0 0 5 0 5 55 56 61 11 14 41 14 41 12 23 32 23 31 19 94 45 57 75 54 45 5 r c v r c v Ma0Ma0Ma1Ma1Ma2Ma2Ma3Ma3Ma4Ma4Ma5Ma5Ma6Ma6A=A=2.4 数组数组 40 9 0 00 0 0 0 00 2 0 0 01 0 0 0 50 0 0 7 0 5 55 56 61 11 14 41 13 39 93 32 22 24 41 11 14 45 55 55 54 47 7 r c v r
53、c v Mb0Mb0Mb1Mb1Mb2Mb2Mb3Mb3Mb4Mb4Mb5Mb5Mb6Mb6B=B=2.4 数组数组实现矩阵转置的算法：实现矩阵转置的算法： int syz(NODE ma,NODE mb)int syz(NODE ma,NODE mb) int i,j,n,t,k; int i,j,n,t,k; if (ma0.v=0) return (0); if (ma0.v=0) return (0); n=ma0.c;t=ma0.v; n=ma0.c;t=ma0.v; mb0.r=n;mb0.c=ma0.r;mb0.v=t; mb0.r=n;mb0.c=ma0.r;mb0.v=t;
54、k=1; k=1; for (j=1;j=n;j+) for (j=1;j=n;j+) for (i=1;i=t;i+) for (i=1;idata=x; p-data=x; p-link=top; p-link=top; top=p; top=p; return (top); return (top); 3.1.2 栈的存储结构及其运算栈的存储结构及其运算(2)(2)出栈出栈 栈顶元素出栈算法的栈顶元素出栈算法的C C语言描述：语言描述： NODE *popstack(NODE *top, ET *p)NODE *popstack(NODE *top, ET *p) NODE *q; NO
55、DE *q; if (top != NULL) if (top != NULL) *q=top; *q=top; *p=top-data; *p=top-data; top=top-link; top=top-link; free(q); free(q); return (top); return (top); 3.1.2 栈的存储结构及其运算栈的存储结构及其运算3 3、栈的应用举例、栈的应用举例、栈的应用举例、栈的应用举例 表表表表达达达达式式式式求求求求值值值值是是是是程程程程序序序序设设设设计计计计语语语语言言言言编编编编译译译译中中中中的的的的一一一一个个个个最最最最根根根根本本本本问
56、问问问题题题题。它它它它的的的的实实实实现现现现方方方方法法法法是是是是栈栈栈栈的的的的一一一一个个个个典典典典型型型型的的的的应应应应用用用用实实实实例。例。例。例。 (1)(1)中中中中缀缀缀缀算算算算术术术术表表表表达达达达式式式式：将将将将运运运运算算算算符符符符置置置置于于于于两两两两个个个个操操操操作作作作数数数数中间的算术表达式，称中缀表达史。中间的算术表达式，称中缀表达史。中间的算术表达式，称中缀表达史。中间的算术表达式，称中缀表达史。 2 2后后后后缀缀缀缀表表表表达达达达式式式式：将将将将运运运运算算算算符符符符置置置置于于于于两两两两个个个个操操操操作作作作数数数数的的的
57、的后后后后面面面面的的的的算算算算术术术术表表表表达达达达式式式式称称称称为为为为后后后后缀缀缀缀表表表表达达达达式式式式。这这这这种种种种表表表表达达达达式式式式不不不不存存存存在在在在括括括括号号号号，也也也也不不不不存存存存在在在在优优优优先先先先级级级级的的的的差差差差异异异异，计计计计算算算算过过过过程程程程完完完完全全全全按按按按照照照照运运运运算算算算符符符符出出出出现现现现的的的的先先先先后后后后次次次次序序序序进进进进行行行行。计计计计算算算算机机机机在在在在处处处处理理理理这这这这种种种种表表表表达达达达式式式式时时时时，只只只只需需需需对对对对其其其其扫扫扫扫描描描描一一
58、一一遍遍遍遍，就就就就可可可可完完完完成计算。成计算。成计算。成计算。3.2 队列队列 在在在在日日日日常常常常生生生生活活活活中中中中队队队队列列列列很很很很常常常常见见见见，如如如如，我我我我们们们们经经经经常常常常排排排排队队队队购购购购物物物物或或或或购购购购票票票票，排排排排队队队队是是是是表表表表达达达达了了了了“ “先先先先来来来来先先先先效效效效劳劳劳劳即即即即“ “先先先先进进进进先先先先出出出出的原那么。的原那么。的原那么。的原那么。 队队队队列列列列在在在在计计计计算算算算机机机机系系系系统统统统中中中中的的的的应应应应用用用用也也也也非非非非常常常常广广广广泛泛泛泛。例
59、例例例如如如如：操操操操作作作作系系系系统统统统中中中中的的的的作作作作业业业业排排排排队队队队。在在在在多多多多道道道道程程程程序序序序运运运运行行行行的的的的计计计计算算算算机机机机系系系系统统统统中中中中，可可可可以以以以同同同同时时时时有有有有多多多多个个个个作作作作业业业业运运运运行行行行，它它它它们们们们的的的的运运运运算算算算结结结结果果果果都都都都需需需需要要要要通通通通过过过过通通通通道道道道输输输输出出出出，假假假假设设设设通通通通道道道道尚尚尚尚未未未未完完完完成成成成输输输输出出出出，那那那那么么么么后后后后来来来来的的的的作作作作业业业业应应应应排排排排队队队队等等等
60、等待待待待，每每每每当当当当通通通通道道道道完完完完成成成成输输输输出出出出时时时时，那那那那么么么么从从从从队队队队列列列列的的的的队队队队头头头头退退退退出出出出作作作作业业业业的的的的输输输输出出出出操操操操作作作作，而而而而但但但但凡凡凡凡申申申申请请请请该该该该通通通通道道道道输输输输出出出出的的的的作作作作业业业业都都都都从从从从队尾进入该队列。队尾进入该队列。队尾进入该队列。队尾进入该队列。3.2 队列队列 计计计计算算算算机机机机系系系系统统统统中中中中输输输输入入入入输输输输出出出出缓缓缓缓冲冲冲冲区区区区的的的的结结结结构构构构也也也也是是是是队队队队列列列列的的的的应应应
61、应用用用用。在在在在计计计计算算算算机机机机系系系系统统统统中中中中经经经经常常常常会会会会遇遇遇遇到到到到两两两两个个个个设设设设备备备备之之之之间间间间的的的的数数数数据据据据传传传传输输输输，不不不不同同同同的的的的设设设设备备备备通通通通常常常常处处处处理理理理数数数数据据据据的的的的速速速速度度度度是是是是不不不不同同同同的的的的，当当当当需需需需要要要要在在在在它它它它们们们们之之之之间间间间连连连连续续续续处处处处理理理理一一一一批批批批数数数数据据据据时时时时，高高高高速速速速设设设设备备备备总总总总是是是是要要要要等等等等待待待待低低低低速速速速设设设设备备备备，这这这这就就
62、就就造造造造成成成成计计计计算算算算机机机机处处处处理理理理效效效效率率率率的的的的大大大大大大大大降降降降低低低低。为为为为了了了了解解解解决决决决这这这这一一一一速速速速度度度度不不不不匹匹匹匹配配配配的的的的矛矛矛矛盾盾盾盾，通通通通常常常常就就就就是是是是在在在在这这这这两两两两个个个个设设设设备备备备之之之之间间间间设设设设置置置置一一一一个个个个缓缓缓缓冲冲冲冲区区区区。这这这这样样样样，高高高高速速速速设设设设备备备备就就就就不不不不必必必必每每每每次次次次等等等等待待待待低低低低速速速速设设设设备备备备处处处处理理理理完完完完一一一一个个个个数数数数据据据据，而而而而是是是是把
63、把把把要要要要处处处处理理理理的的的的数数数数据据据据依依依依次次次次从从从从一一一一端端端端参参参参加加加加缓缓缓缓冲冲冲冲区区区区，而而而而低低低低速速速速设设设设备备备备从从从从另另另另一一一一端端端端取取取取走走走走要要要要处理的数据。处理的数据。处理的数据。处理的数据。3.2 队列队列一、队列的定义及运算一、队列的定义及运算一、队列的定义及运算一、队列的定义及运算 队队队队列列列列也也也也是是是是一一一一种种种种特特特特殊殊殊殊的的的的线线线线性性性性表表表表，它它它它是是是是只只只只允允允允许许许许在在在在表表表表的的的的一一一一端端端端进进进进行行行行插插插插入入入入，在在在在表
64、表表表的的的的另另另另一一一一端端端端进进进进行行行行删删删删除除除除的的的的线线线线性性性性表表表表。允允允允许许许许插插插插入的一端称为队尾，允许删除的一端称为队首。入的一端称为队尾，允许删除的一端称为队首。入的一端称为队尾，允许删除的一端称为队首。入的一端称为队尾，允许删除的一端称为队首。 假假假假设设设设给给给给定定定定队队队队列列列列q=(a0, q=(a0, a1, a1, a2, a2, a3, a3, a4, a4, , , a a n-1)n-1)，我我我我们称们称们称们称a0a0是队首元素，是队首元素，是队首元素，是队首元素，a n-1a n-1是队尾元素。是队尾元素。是队
65、尾元素。是队尾元素。 a a0 0, a, a1 1, a, a2 2, a, a3 3, a, a4 4, , ,a ,a i i a a n-1n-1出队出队出队出队入队入队入队入队第四章第四章 递归递归 递递归归是是程程序序设设计计中中一一个个重重要要的的算算法法设设计计方方法法和和技技术术。递递归归子子程程序序是是通通过过调调用用自自身身来来完完成成与与自自身身要要求求相相同同的的子子问问题题的的求求解解,并并利利用用系系统统内内部部功功能能自自动动实实现现调调用用过过程程中中信信息息的的保保存存与与恢恢复复，而而省省略略了了程程序序设设计计中中的的许许多多细细节节操操作作，简简化化了
66、了程程序序设设计计过过程程,使使程程序序设设计计人人员员可可以以集集中中注注意意力力于于主主要要问问题题求求解上。解上。4.1 递归的定义 递递归归就就是是一一个个事事件件或或对对象象局局部部由由自自己己组组成。成。 递归算法包括递推和回归两局部递归算法包括递推和回归两局部 1递递推推：就就是是为为得得到到问问题题的的解解，将将其推倒比原来问题简单的问题的求解。其推倒比原来问题简单的问题的求解。 2就就是是指指当当“简简单单的的问问题题得得到到解解后后，回归到原问题的解上。回归到原问题的解上。4.2 递归的实现 1、采用递归算法具备的条件、采用递归算法具备的条件 1所所需需解解决决的的问问题题
67、可可以以转转化化成成另另一一个个问问题题，而而解解决决新新问问题题的的方方法法与与原原始始问问题题的解法相同。的解法相同。 2必必须须具具备备终终止止递递归归的的条条件件。程程序序中中不不能能出出现现无无终终止止的的递递归归调调用用，而而只只能能出出现有限次的，有终止的递归调用。现有限次的，有终止的递归调用。4.2 递归的实现 2 2、递归算法例如、递归算法例如、递归算法例如、递归算法例如: n: n！阶乘算法的求解。！阶乘算法的求解。！阶乘算法的求解。！阶乘算法的求解。int fact(int n)int fact(int n) if (n= =0) if (n= =0) s=1; retu
68、rn 1; s=1; return 1; else else s=n*fact(n-1); return s; s=n*fact(n-1); return s; void main()void main() int n; int n; n= fact(5); n= fact(5); printf(“n=%dn printf(“n=%dn,n,n阶乘递归的实现main()main()参数表参数表参数表参数表返回地址返回地址返回地址返回地址活动记录进退栈示意图活动记录进退栈示意图活动记录进退栈示意图活动记录进退栈示意图fact(5)fact(5)5 5ReLoc1ReLoc1fact(4)fact
69、(4)4 4ReLoc2ReLoc2fact(3)fact(3)3 3ReLoc3ReLoc3fact(2)fact(2)2 2ReLoc4ReLoc4fact(1)fact(1)1 1ReLoc5ReLoc50 0ReLoc6ReLoc6s=fact(1)=1*fact(0)=1s=fact(1)=1*fact(0)=1s=fact(2)=2*fact(1)=2s=fact(2)=2*fact(1)=2s=fact(3)=3*fact(2)=6s=fact(3)=3*fact(2)=6s=fact(4)=4*fact(3)=24s=fact(4)=4*fact(3)=24s=fact(5)=
70、5*fact(4)=120s=fact(5)=5*fact(4)=120fact(0)=1fact(0)=1调用者调用者调用者调用者主函数主函数mani()mani()N=fact(5)N=fact(5)第一层调用第一层调用n=5n=5s=5*fact(4)s=5*fact(4)第二层调用第二层调用n=4n=4s=4*fact(3)s=4*fact(3)第三层调用第三层调用n=3n=3S=3*fact(2)S=3*fact(2)第四层调用第四层调用n=2n=2S=2*fact(1)S=2*fact(1)第五层调用第五层调用n=1n=1S=1S=1fact(1)=1fact(1)=1fact(2
71、)=2fact(2)=2fact(3)=6fact(3)=6fact(4)=24fact(4)=24fact(5)=120fact(5)=120输出输出s=120.00s=120.00递归调用过程示意图递归调用过程示意图递归调用过程示意图递归调用过程示意图从图中可看到从图中可看到从图中可看到从图中可看到factfact函数共被调用函数共被调用函数共被调用函数共被调用5 5次，即次，即次，即次，即fact(5)fact(5)、fact(4)fact(4)、fact(3)fact(3)、fact(2)fact(2)、fact(1)fact(1)。其中，其中，其中，其中，fact(5)fact(5)
72、为主函数调用，其它那么为在为主函数调用，其它那么为在为主函数调用，其它那么为在为主函数调用，其它那么为在factfact函数内调用。每一次递归调用并函数内调用。每一次递归调用并函数内调用。每一次递归调用并函数内调用。每一次递归调用并未立即得到结果，而是进一步向深度递归调用，直到未立即得到结果，而是进一步向深度递归调用，直到未立即得到结果，而是进一步向深度递归调用，直到未立即得到结果，而是进一步向深度递归调用，直到n=1n=1或或或或n=0n=0时，函数时，函数时，函数时，函数factfact结果结果结果结果为为为为1 1，然后再一一返回计算，最终得到结果。，然后再一一返回计算，最终得到结果。，
73、然后再一一返回计算，最终得到结果。，然后再一一返回计算，最终得到结果。例例例例 汉诺塔汉诺塔汉诺塔汉诺塔传说在创世纪时，在一个叫传说在创世纪时，在一个叫传说在创世纪时，在一个叫传说在创世纪时，在一个叫BrahmaBrahmaBrahmaBrahma的寺庙里，有三个柱子，其中的寺庙里，有三个柱子，其中的寺庙里，有三个柱子，其中的寺庙里，有三个柱子，其中一柱上有一柱上有一柱上有一柱上有64646464个盘子从小到大依次叠放，僧侣的工作是将这个盘子从小到大依次叠放，僧侣的工作是将这个盘子从小到大依次叠放，僧侣的工作是将这个盘子从小到大依次叠放，僧侣的工作是将这64646464个盘个盘个盘个盘子从一根
74、柱子移到另一个柱子上。子从一根柱子移到另一个柱子上。子从一根柱子移到另一个柱子上。子从一根柱子移到另一个柱子上。 移动时的规那么：移动时的规那么：移动时的规那么：移动时的规那么： 每次只能移动一个盘子；每次只能移动一个盘子；每次只能移动一个盘子；每次只能移动一个盘子； 只能小盘子在大盘子上面；只能小盘子在大盘子上面；只能小盘子在大盘子上面；只能小盘子在大盘子上面； 可以使用任一柱子。可以使用任一柱子。可以使用任一柱子。可以使用任一柱子。当工作做完之后，就标志着世界永远和平。当工作做完之后，就标志着世界永远和平。当工作做完之后，就标志着世界永远和平。当工作做完之后，就标志着世界永远和平。x y
75、zx y zx y zx y zn nn 1n 1分析：分析：分析：分析： 设三根柱子分别为设三根柱子分别为设三根柱子分别为设三根柱子分别为 x x x x，y, z , y, z , y, z , y, z , 盘子在盘子在盘子在盘子在x x x x柱上，要移到柱上，要移到柱上，要移到柱上，要移到z z z z柱上。柱上。柱上。柱上。1 1 1 1、当、当、当、当n=1n=1n=1n=1时，盘子直接从时，盘子直接从时，盘子直接从时，盘子直接从 x x x x 柱移到柱移到柱移到柱移到 z z z z 柱上；柱上；柱上；柱上；2 2 2 2、当、当、当、当n1n1n1n1时时时时, , , ,
76、 那么那么那么那么设法将前设法将前设法将前设法将前n1n1n1n1个盘子借助个盘子借助个盘子借助个盘子借助z z z z，从，从，从，从x x x x移到移到移到移到y y y y柱上，柱上，柱上，柱上，把把把把 盘子盘子盘子盘子n n n n从从从从x x x x移到移到移到移到z z z z柱上；柱上；柱上；柱上； 把把把把n1n1n1n1个盘子从个盘子从个盘子从个盘子从y y y y移到移到移到移到z z z z柱上。柱上。柱上。柱上。Hanoi问题void Hanoi ( int n, char x, char y, char z )void Hanoi ( int n, char x
77、, char y, char z ) / /将将将将 n n 个个个个 编号从上到下为编号从上到下为编号从上到下为编号从上到下为 1 1n n 的盘子从的盘子从的盘子从的盘子从 x x 柱，借助柱，借助柱，借助柱，借助 y y 柱移到柱移到柱移到柱移到 z z 柱柱柱柱 if ( n = = 1 ) if ( n = = 1 ) move ( x , 1 , z ) ; move ( x , 1 , z ) ; / /将编号为将编号为将编号为将编号为 1 1 的盘子从的盘子从的盘子从的盘子从 x x 柱移到柱移到柱移到柱移到 z z 柱柱柱柱 else else / /将将将将 n -1n -
78、1个个个个 编号从上到下为编号从上到下为编号从上到下为编号从上到下为1 1n-1n-1的盘子从的盘子从的盘子从的盘子从 x x 柱，借助柱，借助柱，借助柱，借助 y y 柱移到柱移到柱移到柱移到 z z 柱柱柱柱 Hanoi ( n-1 , x , z , y ) ; Hanoi ( n-1 , x , z , y ) ; move ( x , n, z) ; move ( x , n, z) ; / /将编号为将编号为将编号为将编号为 n n 的盘子从的盘子从的盘子从的盘子从 x x 柱移到柱移到柱移到柱移到 z z 柱柱柱柱 / /将将将将 n -1n -1个个个个 编号从上到下为编号从上
79、到下为编号从上到下为编号从上到下为 1 1n-1n-1的盘子从的盘子从的盘子从的盘子从 y y 柱，借助柱，借助柱，借助柱，借助 x x 柱移到柱移到柱移到柱移到 z z 柱柱柱柱 Hanoi ( n-1 , y , x , z );Hanoi ( n-1 , y , x , z ); /Hanoi /Hanoi第五章第五章 串串 在在在在计计计计算算算算机机机机的的的的各各各各方方方方面面面面应应应应用用用用中中中中，非非非非数数数数值值值值处处处处理理理理问问问问题题题题的的的的应应应应用用用用越越越越来来来来越越越越多多多多。如如如如程程程程序序序序源源源源代代代代码码码码，在在在在事事
80、事事务务务务处处处处理理理理系系系系统统统统中中中中，用用用用户户户户的的的的姓姓姓姓名名名名和和和和地地地地址址址址及及及及货货货货物物物物的的的的名名名名称称称称、规规规规格格格格等等等等，都都都都是是是是作作作作为一种字符串数据进行处理的。为一种字符串数据进行处理的。为一种字符串数据进行处理的。为一种字符串数据进行处理的。 字字字字符符符符串串串串一一一一般般般般简简简简称称称称为为为为串串串串，可可可可以以以以将将将将它它它它看看看看作作作作是是是是一一一一种种种种特特特特殊殊殊殊的的的的线线线线性性性性表表表表，这这这这种种种种线线线线性性性性表表表表的的的的数数数数据据据据元元元元
81、素素素素的的的的类类类类型型型型总总总总是是是是字字字字符符符符型型型型的的的的，字字字字符符符符串串串串的的的的数数数数据据据据对对对对象象象象约约约约束束束束为为为为字字字字符符符符集集集集。在在在在一一一一般般般般线线线线性性性性表表表表的的的的根根根根本本本本操操操操作作作作中中中中，大大大大多多多多以以以以“ “单单单单个个个个元元元元素素素素作作作作为为为为操操操操作作作作对对对对象象象象，而而而而在在在在串串串串中中中中，那那那那么么么么是是是是以以以以“ “串串串串的的的的整整整整体体体体或或或或一一一一局局局局部部部部作作作作为为为为操操操操作作作作对对对对象象象象。因因因因
82、此此此此，一一一一般般般般线线线线性性性性表表表表和和和和串串串串的的的的操操操操作作作作有有有有很很很很大大大大的的的的不不不不同同同同。本本本本章章章章主主主主要要要要讨讨讨讨论论论论串串串串的的的的根根根根本本本本概概概概念念念念、存存存存储储储储结结结结构构构构和和和和一一一一些根本的串处理操作。些根本的串处理操作。些根本的串处理操作。些根本的串处理操作。5.1 串的根本概念串的根本概念 串串串串或或或或字字字字符符符符串串串串StringString是是是是由由由由零零零零个个个个或或或或多多多多个个个个字字字字符符符符组成的有限序列。一般记作组成的有限序列。一般记作组成的有限序列。
83、一般记作组成的有限序列。一般记作 s= s=a0a1a2an-1a0a1a2an-1 (n0) (n0) 其其其其中中中中：s s为为为为串串串串名名名名，用用用用双双双双引引引引号号号号括括括括起起起起来来来来的的的的字字字字符符符符序序序序列列列列是是是是串串串串的的的的值值值值；ai(0in-1)ai(0in-1)可可可可以以以以是是是是字字字字母母母母、数数数数字字字字或或或或其其其其它它它它字字字字符符符符；双双双双引引引引号号号号为为为为串串串串值值值值的的的的定定定定界界界界符符符符，不不不不是是是是串串串串的的的的一一一一局局局局部部部部；字字字字符符符符串串串串字字字字符符符
84、符的的的的数数数数目目目目n n称称称称为为为为串串串串的的的的长长长长度度度度。零零零零个个个个字字字字符符符符的的的的串串串串称称称称为为为为空空空空串串串串，通通通通常常常常以以以以两两两两个个个个相相相相邻邻邻邻的的的的双双双双引引引引号号号号来来来来表表表表示示示示空空空空串串串串Null Null stringstring，如如如如：s=s=，它它它它的的的的长长长长度度度度为为为为零零零零；仅仅仅仅由由由由空空空空格格格格组组组组成成成成的的的的的的的的串串串串称称称称为为为为空空空空格格格格串串串串，如如如如：s=s=；假假假假设设设设串串串串中中中中含含含含有有有有空空空空格
85、格格格，在在在在计计计计算算算算串串串串长长长长时时时时，空空空空格格格格应应应应计计计计入入入入串串串串的的的的长长长长度度度度中，如：中，如：中，如：中，如：s=s=Im a studentIm a student的长度为的长度为的长度为的长度为1313。 5.2 串的存储结构串的存储结构一、顺序存储一、顺序存储一、顺序存储一、顺序存储 和和和和线线线线性性性性表表表表一一一一样样样样，可可可可以以以以用用用用一一一一组组组组连连连连续续续续的的的的存存存存储储储储单单单单元元元元依依依依次次次次存存存存放放放放串串串串中中中中各各各各字字字字符符符符。利利利利用用用用字字字字符符符符单单
86、单单元元元元地地地地址址址址的的的的顺顺顺顺序序序序表表表表示示示示串串串串中字符的相邻关系。中字符的相邻关系。中字符的相邻关系。中字符的相邻关系。 struct string struct string char ch_stringmaxlen; char ch_stringmaxlen; int len ; int len ; ; ; 当当当当计计计计算算算算机机机机按按按按字字字字(Word)(Word)为为为为单单单单位位位位编编编编址址址址时时时时，一一一一个个个个存存存存储储储储单单单单元元元元由由由由假假假假设设设设干干干干字字字字节节节节组组组组成成成成。这这这这时时时时，顺顺
87、顺顺序序序序存存存存储储储储结结结结构构构构有有有有紧紧紧紧凑凑凑凑格格格格式和非紧凑格式两种。式和非紧凑格式两种。式和非紧凑格式两种。式和非紧凑格式两种。5.3 串的根本运算串的根本运算 串串串串的的的的根根根根本本本本运运运运算算算算有有有有赋赋赋赋值值值值、串串串串连连连连接接接接、求求求求串串串串长长长长、取取取取子子子子串串串串、子子子子串串串串定定定定位位位位、判判判判断断断断两两两两个个个个串串串串是是是是否否否否相相相相等等等等、插插插插入入入入子子子子串串串串，删删删删除除除除子子子子串串串串等等等等。在在在在本本本本节节节节中中中中，我我我我们们们们尽尽尽尽可可可可能能能能
88、以以以以C C语语语语言言言言的的的的库库库库函函函函数数数数表表表表示示示示其其其其中中中中的的的的一一一一些些些些运运运运算算算算，假假假假设设设设没没没没有有有有库库库库函函函函数数数数，那那那那么么么么用用用用自自自自定定定定义义义义函函函函数说明。数说明。数说明。数说明。 struct string struct string char ch_stringmaxlen; char ch_stringmaxlen; int len ; int len ; ; ;1 1、串连接、串连接所谓串连接就是把一个串连接在另一个串的末尾，组成一个所谓串连接就是把一个串连接在另一个串的末尾，组成一个
89、新串。新串。Struct string concat(s1,s2)Struct string concat(s1,s2) struct string s1,s2; struct string s1,s2;struct string s;struct string s; int i; int i; if (s1.len+s2.len=maxlen) if (s1.len+s2.len=maxlen) for (i=0;is1.len;i+ ) for (i=0;is1.len;i+ ) s.ch_stringi= s1.ch_stringi; s.ch_stringi= s1.ch_string
90、i; for (i=0;is2.len;i+ ) for (i=0;is2.len;i+ ) s.ch_strings1.len+i= s2.ch_stringi; s.ch_strings1.len+i= s2.ch_stringi; s.len=s1.len+s2.len; s.len=s1.len+s2.len; else else s.len=0; s.len=0; return (s); return (s); 2 2、串相等判断、串相等判断当两个串的长度相等且各对应位置上的字符都相等时，两个当两个串的长度相等且各对应位置上的字符都相等时，两个字符串才相等。字符串才相等。 int e
91、qual(s1,s2) int equal(s1,s2) struct string s1,s2; struct string s1,s2; int i; int i; if (s1.len != s2.len) if (s1.len != s2.len) return (0); return (0); else else for (i=0; is1.len ;i+) for (i=0; i=1)&(n1=1)& (n2=1)&(n1=1)& (n2=s.len-n1+1)n1+1) for (i=0; i=n2 ;i+) for (i=0; i=n2 ;i+) sub.ch_stringi=
92、s.ch_stringn1+i sub.ch_stringi=s.ch_stringn1+i sub.len=n2; sub.len=n2; else else sub.len=0; sub.len=0; return (sub); return (sub); 4 4、插入子串、插入子串所谓插入子串就是在指定位置上插入一个子串。所谓插入子串就是在指定位置上插入一个子串。struct string insert(s,s1,n)struct string insert(s,s1,n) struct string s,s1; int n; struct string s,s1; int n; str
93、uct string sub1,sub2,str; struct string sub1,sub2,str; if (s.len+s1.len=1)& if (s.len+s1.len=1)& (n=s.len+1) (n=s.len+1) sub1=substr(s,1,n-1); sub1=substr(s,1,n-1); sub2=substr(s,n,s.len-n+1); sub2=substr(s,n,s.len-n+1); str=concat(concat(sub1,s1),sub2); str=concat(concat(sub1,s1),sub2); else else s
94、tr.len=0; str.len=0; return (str); return (str); 5 5、子串定位、子串定位所谓子串定位就是给出子串在母串中的位置。子串的定位操所谓子串定位就是给出子串在母串中的位置。子串的定位操作也称模式匹配。作也称模式匹配。 int index(s,s1) int index(s,s1) struct string s,s1; struct string s,s1; int i , j , k ; int i , j , k ; i=0; i=0; while (i=s.len while (i=s.len s1.len) s1.len) j=i ; k=0
95、 ; j=i ; k=0 ; while (ks1.len)&(s.ch_sj=s1.ch_sk) while (k0)个结点的有穷集合个结点的有穷集合K，且在，且在K中定义了一个关系中定义了一个关系N，N满足以下满足以下条件：条件： (1) 有且仅有一个结点有且仅有一个结点K0它对于关系它对于关系N来说来说没有前驱，称没有前驱，称K0为树的根结点；为树的根结点； (2) 除除K0外，外，K中的每一个结点对于关系中的每一个结点对于关系N来来说有且仅有一个前驱；说有且仅有一个前驱； (3)K中各结点对关系中各结点对关系N来说可以有来说可以有m个后继个后继7.2 树的常用术语树的常用术语n n树的
96、结点：包含一个数据元素及假设干指树的结点：包含一个数据元素及假设干指向其子树的分支向其子树的分支n n结点的度：结点所拥有的子树的个数称为结点的度：结点所拥有的子树的个数称为该结点的度该结点的度n n叶子：度为零的结点，又称终端结点叶子：度为零的结点，又称终端结点n n树的深度：树中各结点层次的最大值称为树的深度：树中各结点层次的最大值称为该树的深度该树的深度7.3 二叉树二叉树n n二叉数的定义二叉数的定义n n二叉数的存储结构：顺序存储结构、链式二叉数的存储结构：顺序存储结构、链式存储结构存储结构n n二叉数的遍历：就是按某一种规那么访问二叉数的遍历：就是按某一种规那么访问树中的每一个结点
97、，且使得每个结点均被树中的每一个结点，且使得每个结点均被访问一次，而且仅被访问一次。访问一次，而且仅被访问一次。n n二叉数的遍历方法：前序遍历、中序遍历、二叉数的遍历方法：前序遍历、中序遍历、后序遍历后序遍历第九章第九章 查找查找n n查找查找查找查找(Searching)(Searching)n n又称检索。就是从一个数据元素集合中找出某个又称检索。就是从一个数据元素集合中找出某个又称检索。就是从一个数据元素集合中找出某个又称检索。就是从一个数据元素集合中找出某个特定的数据元素；特定的数据元素；特定的数据元素；特定的数据元素；n n它是数据处理中经常使用的一种重要的操作，尤它是数据处理中经
98、常使用的一种重要的操作，尤它是数据处理中经常使用的一种重要的操作，尤它是数据处理中经常使用的一种重要的操作，尤其是当所涉及的数据量较大时，查找算法的优劣其是当所涉及的数据量较大时，查找算法的优劣其是当所涉及的数据量较大时，查找算法的优劣其是当所涉及的数据量较大时，查找算法的优劣对整个软件的效率影响很大；对整个软件的效率影响很大；对整个软件的效率影响很大；对整个软件的效率影响很大；n n本章首先介绍关于查找的根本概念，然后讨论查本章首先介绍关于查找的根本概念，然后讨论查本章首先介绍关于查找的根本概念，然后讨论查本章首先介绍关于查找的根本概念，然后讨论查找的各种方法，最后对各种查找方法作一比较。找
99、的各种方法，最后对各种查找方法作一比较。找的各种方法，最后对各种查找方法作一比较。找的各种方法，最后对各种查找方法作一比较。9.1 查找的根本概念查找的根本概念n n查找表查找表查找表查找表(Search Table)(Search Table) 是由同一类型的数据元素是由同一类型的数据元素是由同一类型的数据元素是由同一类型的数据元素( (或记录或记录或记录或记录) )构成的集合构成的集合构成的集合构成的集合n n对查找表进行的操作有以下四种对查找表进行的操作有以下四种对查找表进行的操作有以下四种对查找表进行的操作有以下四种 (1)(1)查询某个特定的数据元素是否在查找表中查询某个特定的数据元
100、素是否在查找表中查询某个特定的数据元素是否在查找表中查询某个特定的数据元素是否在查找表中 (2)(2)检索某个特定的数据元素的各种属性检索某个特定的数据元素的各种属性检索某个特定的数据元素的各种属性检索某个特定的数据元素的各种属性 (3)(3)在查找表中插入一个数据元素在查找表中插入一个数据元素在查找表中插入一个数据元素在查找表中插入一个数据元素 (4)(4)从查找表中删除某个数据元素从查找表中删除某个数据元素从查找表中删除某个数据元素从查找表中删除某个数据元素9.1 查找的根本概念查找的根本概念n n静态查找表静态查找表静态查找表静态查找表(Static Search Table)(Stat
101、ic Search Table)n n 假设只对查找表进行查找和检索两种操作假设只对查找表进行查找和检索两种操作假设只对查找表进行查找和检索两种操作假设只对查找表进行查找和检索两种操作, ,那那那那么称此查找表为静态查找表么称此查找表为静态查找表么称此查找表为静态查找表么称此查找表为静态查找表n n动态查找表动态查找表动态查找表动态查找表(Dynamic Search table)(Dynamic Search table)n n 假设再查找过程中同时插入查找表中不存在假设再查找过程中同时插入查找表中不存在假设再查找过程中同时插入查找表中不存在假设再查找过程中同时插入查找表中不存在的记录的记录
102、的记录的记录, ,或从查找表中删除已存在的某个记录或从查找表中删除已存在的某个记录或从查找表中删除已存在的某个记录或从查找表中删除已存在的某个记录, ,那么称此类表为动态查找表那么称此类表为动态查找表那么称此类表为动态查找表那么称此类表为动态查找表n n关键字关键字关键字关键字(Key)(Key)n n 标志数据元素标志数据元素标志数据元素标志数据元素( (或记录或记录或记录或记录) )中某个数据项的值中某个数据项的值中某个数据项的值中某个数据项的值, ,用用用用它可以标识一个数据元素它可以标识一个数据元素它可以标识一个数据元素它可以标识一个数据元素( (或记录或记录或记录或记录) )9.2
103、线性表的查找线性表的查找n n顺序查找顺序查找顺序查找顺序查找(sequential Search)(sequential Search)n n 也称线性查找也称线性查找也称线性查找也称线性查找, ,是一种最简单的查找方法是一种最简单的查找方法是一种最简单的查找方法是一种最简单的查找方法, ,它它它它属于静态查找属于静态查找属于静态查找属于静态查找n n顺序查找方法顺序查找方法顺序查找方法顺序查找方法n n 顺序查找的根本思想顺序查找的根本思想顺序查找的根本思想顺序查找的根本思想: :从表的一端开始从表的一端开始从表的一端开始从表的一端开始, ,顺序顺序顺序顺序扫描线性表扫描线性表扫描线性表扫
104、描线性表, ,依次用待查找的关键字值与线性依次用待查找的关键字值与线性依次用待查找的关键字值与线性依次用待查找的关键字值与线性表里各结点的关键字值逐个比较表里各结点的关键字值逐个比较表里各结点的关键字值逐个比较表里各结点的关键字值逐个比较, ,假设在表中假设在表中假设在表中假设在表中找到了某个记录的关键字与待查找的关键字值找到了某个记录的关键字与待查找的关键字值找到了某个记录的关键字与待查找的关键字值找到了某个记录的关键字与待查找的关键字值相等相等相等相等, ,说明查找成功说明查找成功说明查找成功说明查找成功; ;如果找遍所有结点也没有如果找遍所有结点也没有如果找遍所有结点也没有如果找遍所有结
105、点也没有与待查找的关键字值相等与待查找的关键字值相等与待查找的关键字值相等与待查找的关键字值相等, ,那么说明查找失败那么说明查找失败那么说明查找失败那么说明查找失败9.2 线性表的查找线性表的查找main()main()int a100=0,12,5,36,58,21,61,15,16,32,17;int a100=0,12,5,36,58,21,61,15,16,32,17; int i,key; int i,key; printf (Input the Key:); printf (Input the Key:); scanf (%d,&key); scanf (%d,&key); a0
106、=key; a0=key; for (i=10;ai!=key;i-); for (i=10;ai!=key;i-); if (i=0) if (i=0) printf (Searching Fail!n); printf (Searching Fail!n); else else printf (Searching Success!n); printf (Searching Success!n); printf (a%d=%dn,i,key); printf (a%d=%dn,i,key); 9.2 线性表的查找线性表的查找n n折半查找折半查找折半查找折半查找(binary Search)
107、(binary Search)n n 也称为二分查找也称为二分查找也称为二分查找也称为二分查找, ,是一种效率较高的查找方法是一种效率较高的查找方法是一种效率较高的查找方法是一种效率较高的查找方法, ,查找时要求表中的结点按关键字的大小排序查找时要求表中的结点按关键字的大小排序查找时要求表中的结点按关键字的大小排序查找时要求表中的结点按关键字的大小排序n n折半查找方法折半查找方法折半查找方法折半查找方法n n 折半查找的根本思想折半查找的根本思想折半查找的根本思想折半查找的根本思想: :首先用要查找的关键字首先用要查找的关键字首先用要查找的关键字首先用要查找的关键字值与中间位置结点的关键字值
108、相比较值与中间位置结点的关键字值相比较值与中间位置结点的关键字值相比较值与中间位置结点的关键字值相比较( (这个中这个中这个中这个中间结点把线性表分成了两个子表间结点把线性表分成了两个子表间结点把线性表分成了两个子表间结点把线性表分成了两个子表). ).比较结果相比较结果相比较结果相比较结果相等等等等, ,那么查找成功那么查找成功那么查找成功那么查找成功; ;假设不相等假设不相等假设不相等假设不相等, ,再根据要查找再根据要查找再根据要查找再根据要查找的关键字值与该中间结点关键字值的大小确定的关键字值与该中间结点关键字值的大小确定的关键字值与该中间结点关键字值的大小确定的关键字值与该中间结点关
109、键字值的大小确定下一步查找在哪个子表中进行下一步查找在哪个子表中进行下一步查找在哪个子表中进行下一步查找在哪个子表中进行#include #include main()main()int a100=0,5,13,19,22,37,56,64,75,80,88,92;int a100=0,5,13,19,22,37,56,64,75,80,88,92; int low=1,high=11,mid,key,flag=0; int low=1,high=11,mid,key,flag=0; printf (Input the Key:); printf (Input the Key:); scanf
110、 (%d,&key); scanf (%d,&key); while (low=high) while (low=high) mid=(low+high)/2; mid=(low+high)/2; if (key=amid) if (key=amid) printf (Searching Success!); printf (Searching Success!); printf (a%d=%dn,mid,key); printf (a%d=%dn,mid,key); flag=1;break; flag=1;break; else else if (keyamid) high=mid-1;
111、if (keyamid) high=mid-1; else low=mid+1; else low=mid+1; if (flag=0)if (flag=0) printf (Searching Fail!n); printf (Searching Fail!n); 第十章第十章 排序排序n n排序是在数据处理中经常使用的一种重排序是在数据处理中经常使用的一种重要的算法。如何进行排序，特别是高效要的算法。如何进行排序，特别是高效率的排序是计算机应用中的重要课题。率的排序是计算机应用中的重要课题。n n排序的目的：是方便查找排序的目的：是方便查找n n排序分为：内部排序、外部排序排序分为：内部排
112、序、外部排序n n本章主要介绍几种常用的内部排序方法：本章主要介绍几种常用的内部排序方法：插入排序、选择排序、交换排序的根本插入排序、选择排序、交换排序的根本思想、排序步骤及实现方法思想、排序步骤及实现方法10.1 排序的根本概念排序的根本概念n n关键字关键字(Key)n n 标志数据元素标志数据元素(或记录或记录)中某个数据项的中某个数据项的值值,用它可以标识一个数据元素用它可以标识一个数据元素(或记录或记录)n n排序排序(Sorting)n n 是将一组记录按照记录中某个关键字进是将一组记录按照记录中某个关键字进行有序递增或递减排列过程行有序递增或递减排列过程10.2 内部排序内部排序
113、n n插入排序插入排序n n 插入排序就是按关键字大小将一个记录插入排序就是按关键字大小将一个记录插入到一个有序的文件中的适当位置，插入到一个有序的文件中的适当位置，并且插入后使文件仍然有序。并且插入后使文件仍然有序。n n直接插入排序直接插入排序n n 每一趟将一个待排序的记录，按关键字每一趟将一个待排序的记录，按关键字的大小插入到已经排序的局部文件中适的大小插入到已经排序的局部文件中适当位置，直到全部插入完成当位置，直到全部插入完成main()int a100=0,19,1,23,17,19,55,84,150,19,1,23,17,19,55,84,15; int i,j; for(i=
114、2;i=8;+i) if(aiai-1) a0=ai; for(j=i-1;a0aj;-j) aj+1=aj; aj+1=a0; for(i=1;i=8;i+) printf(%d ,ai); printf(n); 10.2 内部排序内部排序n n折半插入排序折半插入排序n n 由于插入排序的根本操作是在一个由于插入排序的根本操作是在一个有序表中进行查找和插入，而查找操有序表中进行查找和插入，而查找操作可利用折半查找来实现，由此进行作可利用折半查找来实现，由此进行的插入排序称之为折半插入排列的插入排序称之为折半插入排列Binary Insertion Sort，又称为二，又称为二分法插入排序。
115、分法插入排序。main()main()int a100=0,19,1,23,17,19,55,84,15;int a100=0,19,1,23,17,19,55,84,15; int i,j,low,high,m; int i,j,low,high,m; for(i=2;i=8;+i) for(i=2;i=8;+i) if(aiai-1) if(aiai-1) a0=ai;low=1;high=i-1; a0=ai;low=1;high=i-1; while(low=high) while(low=high) m=(low+high)/2; m=(low+high)/2; if(a0am) h
116、igh=m-1; if(a0=high+1;-j) for(j=i-1;j=high+1;-j) aj+1=aj; aj+1=aj; ahigh+1=a0; ahigh+1=a0; for(i=1;i=8;i+) for(i=1;i=8;i+) printf(%d ,ai); printf(%d ,ai); printf(n); printf(n); 10.2 内部排序内部排序n n冒泡排序冒泡排序n n 冒泡排序的根本思想：将待排序的冒泡排序的根本思想：将待排序的序列中的关键字与第二个关键字进行序列中的关键字与第二个关键字进行比较从小到大，如果那么交换比较从小到大，如果那么交换r1和和r2记
117、录序列中的位置，否那么不交记录序列中的位置，否那么不交换，然后再接着对当前序列中的第二换，然后再接着对当前序列中的第二个和第三个记录作同样的比较，依次个和第三个记录作同样的比较，依次类推，直到序列中最后两个记录处理类推，直到序列中最后两个记录处理完为止。完为止。main()main()int a100=0,5,7,3,8,2,9,1,4;int a100=0,5,7,3,8,2,9,1,4; int i,j,flag,temp;int i,j,flag,temp; flag=1;flag=1; for(i=1;i9 & flag=1;i+) for(i=1;i9 & flag=1;i+) fl
118、ag=0; flag=0; for(j=0;j9-i;j+) for(j=0;jaj+1) if (ajaj+1) flag=1;flag=1; temp=aj;aj=aj+1; temp=aj;aj=aj+1; aj+1=temp;aj+1=temp; for(i=1;i=8;i+)for(i=1;i=8;i+) printf(%d ,ai); printf(%d ,ai); printf(n);printf(n); 10.2 内部排序内部排序n n快速排序快速排序快速排序快速排序n n 快速排序是由冒泡排序改进而得的，是一种快速排序是由冒泡排序改进而得的，是一种快速排序是由冒泡排序改进而得
119、的，是一种快速排序是由冒泡排序改进而得的，是一种分区交换排序方法分区交换排序方法分区交换排序方法分区交换排序方法n n 排序的根本思想：一趟快速排序采用从两头排序的根本思想：一趟快速排序采用从两头排序的根本思想：一趟快速排序采用从两头排序的根本思想：一趟快速排序采用从两头向中间扫描的方法，同时交换与基准记录逆序向中间扫描的方法，同时交换与基准记录逆序向中间扫描的方法，同时交换与基准记录逆序向中间扫描的方法，同时交换与基准记录逆序的记录。在待排序的的记录。在待排序的的记录。在待排序的的记录。在待排序的n n个记录中任取一个记录，个记录中任取一个记录，个记录中任取一个记录，个记录中任取一个记录，把
120、该记录放入最终位置后，序列被这个记录分把该记录放入最终位置后，序列被这个记录分把该记录放入最终位置后，序列被这个记录分把该记录放入最终位置后，序列被这个记录分割成两局部，所有关键字比该记录关键字小的割成两局部，所有关键字比该记录关键字小的割成两局部，所有关键字比该记录关键字小的割成两局部，所有关键字比该记录关键字小的放置在前一局部，所有比它大的放置在后一局放置在前一局部，所有比它大的放置在后一局放置在前一局部，所有比它大的放置在后一局放置在前一局部，所有比它大的放置在后一局部，并把该记录排在这两局部的中间。部，并把该记录排在这两局部的中间。部，并把该记录排在这两局部的中间。部，并把该记录排在这
121、两局部的中间。void q_sort(int *a,int left,int right)void q_sort(int *a,int left,int right) int partition; /* int partition; /* 分割元素分割元素分割元素分割元素 */ */ int temp int temp, , i,j,k; i,j,k; if ( left right ) /* if ( left right ) /* 是否继续分割是否继续分割是否继续分割是否继续分割 */ */ i = left; /* i = left; /* 分割的最左分割的最左分割的最左分割的最左 */
122、 */ j = right + 1; /* j = right + 1; /* 分割的最右分割的最右分割的最右分割的最右 */ */ partition = aleft; /* partition = aleft; /* 取第一个元素取第一个元素取第一个元素取第一个元素 */ */ do do do /* do /* 从左往右找从左往右找从左往右找从左往右找 */ */ i+; i+; while( ai partition ); while( ai partition ); while( aj partition ); if ( i j )if ( i j ) temp = ai; ai =
123、 aj; aj = temp; temp = ai; ai = aj; aj = temp; /* /* 交换数据交换数据交换数据交换数据 */ */ while( i j ); while( i j ); temp= aleft; aleft = aj; aj = temp;/* temp= aleft; aleft = aj; aj = temp;/* 交换数据交换数据交换数据交换数据 */ */ printf(printf(输出结果输出结果输出结果输出结果: );: ); for ( k = left; k = right; k+) /* for ( k = left; k = righ
124、t; k+) /* 输出处理数据输出处理数据输出处理数据输出处理数据 */ */ printf(%d ,ak); printf(%d ,ak); printf(n); /* printf(n); /* 换行换行换行换行 */ */ q_sort(a,left,j-1); /* q_sort(a,left,j-1); /* 快速排序递归调用快速排序递归调用快速排序递归调用快速排序递归调用 */ */ q_sort(a,j+1,right); /* q_sort(a,j+1,right); /* 快速排序递归调用快速排序递归调用快速排序递归调用快速排序递归调用 */ */ 10.2 内部排序内部排
125、序n n选择排序选择排序n n直接选择排序的根本思想：从待排序的直接选择排序的根本思想：从待排序的所有记录中，选取关键字最小的记录并所有记录中，选取关键字最小的记录并将它与原始序列的第一个记录交换位置，将它与原始序列的第一个记录交换位置，然后从去掉了关键字最小的记录的剩余然后从去掉了关键字最小的记录的剩余记录中选择关键字最小的记录与原始记记录中选择关键字最小的记录与原始记录中的第二个记录交换位置。录中的第二个记录交换位置。main()main()int a100=0,5,7,3,8,2,9,1,4;int a100=0,5,7,3,8,2,9,1,4; int i,j,k,w; int i,j
126、,k,w; for(i=1;i8;i+) for(i=1;i8;i+) k=i; k=i; for(j=i+1;j9;j+) for(j=i+1;j9;j+) if (ajak) k=j; if (ajak) k=j; if (k!=i) if (k!=i) w=ai;ai=ak;ak=w; w=ai;ai=ak;ak=w; for(i=1;i=8;i+) for(i=1;i=8;i+) printf(%d ,ai); printf(%d ,ai); printf(n); printf(n); 10.2 内部排序内部排序n n快速排序快速排序快速排序快速排序n n 快速排序是由冒泡排序改进而得
127、的，是一种快速排序是由冒泡排序改进而得的，是一种快速排序是由冒泡排序改进而得的，是一种快速排序是由冒泡排序改进而得的，是一种分区交换排序方法分区交换排序方法分区交换排序方法分区交换排序方法n n 排序的根本思想：一趟快速排序采用从两头排序的根本思想：一趟快速排序采用从两头排序的根本思想：一趟快速排序采用从两头排序的根本思想：一趟快速排序采用从两头向中间扫描的方法，同时交换与基准记录逆序向中间扫描的方法，同时交换与基准记录逆序向中间扫描的方法，同时交换与基准记录逆序向中间扫描的方法，同时交换与基准记录逆序的记录。在待排序的的记录。在待排序的的记录。在待排序的的记录。在待排序的n n个记录中任取一
128、个记录，个记录中任取一个记录，个记录中任取一个记录，个记录中任取一个记录，把该记录放入最终位置后，序列被这个记录分把该记录放入最终位置后，序列被这个记录分把该记录放入最终位置后，序列被这个记录分把该记录放入最终位置后，序列被这个记录分割成两局部，所有关键字比该记录关键字小的割成两局部，所有关键字比该记录关键字小的割成两局部，所有关键字比该记录关键字小的割成两局部，所有关键字比该记录关键字小的放置在前一局部，所有比它大的放置在后一局放置在前一局部，所有比它大的放置在后一局放置在前一局部，所有比它大的放置在后一局放置在前一局部，所有比它大的放置在后一局部，并把该记录排在这两局部的中间。部，并把该记
129、录排在这两局部的中间。部，并把该记录排在这两局部的中间。部，并把该记录排在这两局部的中间。10.2 内部排序内部排序n n快速排序快速排序快速排序快速排序n n 快速排序是由冒泡排序改进而得的，是一种快速排序是由冒泡排序改进而得的，是一种快速排序是由冒泡排序改进而得的，是一种快速排序是由冒泡排序改进而得的，是一种分区交换排序方法分区交换排序方法分区交换排序方法分区交换排序方法n n 排序的根本思想：一趟快速排序采用从两头排序的根本思想：一趟快速排序采用从两头排序的根本思想：一趟快速排序采用从两头排序的根本思想：一趟快速排序采用从两头向中间扫描的方法，同时交换与基准记录逆序向中间扫描的方法，同时
130、交换与基准记录逆序向中间扫描的方法，同时交换与基准记录逆序向中间扫描的方法，同时交换与基准记录逆序的记录。在待排序的的记录。在待排序的的记录。在待排序的的记录。在待排序的n n个记录中任取一个记录，个记录中任取一个记录，个记录中任取一个记录，个记录中任取一个记录，把该记录放入最终位置后，序列被这个记录分把该记录放入最终位置后，序列被这个记录分把该记录放入最终位置后，序列被这个记录分把该记录放入最终位置后，序列被这个记录分割成两局部，所有关键字比该记录关键字小的割成两局部，所有关键字比该记录关键字小的割成两局部，所有关键字比该记录关键字小的割成两局部，所有关键字比该记录关键字小的放置在前一局部，
131、所有比它大的放置在后一局放置在前一局部，所有比它大的放置在后一局放置在前一局部，所有比它大的放置在后一局放置在前一局部，所有比它大的放置在后一局部，并把该记录排在这两局部的中间。部，并把该记录排在这两局部的中间。部，并把该记录排在这两局部的中间。部，并把该记录排在这两局部的中间。10.2 内部排序内部排序n n快速排序快速排序快速排序快速排序n n 快速排序是由冒泡排序改进而得的，是一种快速排序是由冒泡排序改进而得的，是一种快速排序是由冒泡排序改进而得的，是一种快速排序是由冒泡排序改进而得的，是一种分区交换排序方法分区交换排序方法分区交换排序方法分区交换排序方法n n 排序的根本思想：一趟快速
132、排序采用从两头排序的根本思想：一趟快速排序采用从两头排序的根本思想：一趟快速排序采用从两头排序的根本思想：一趟快速排序采用从两头向中间扫描的方法，同时交换与基准记录逆序向中间扫描的方法，同时交换与基准记录逆序向中间扫描的方法，同时交换与基准记录逆序向中间扫描的方法，同时交换与基准记录逆序的记录。在待排序的的记录。在待排序的的记录。在待排序的的记录。在待排序的n n个记录中任取一个记录，个记录中任取一个记录，个记录中任取一个记录，个记录中任取一个记录，把该记录放入最终位置后，序列被这个记录分把该记录放入最终位置后，序列被这个记录分把该记录放入最终位置后，序列被这个记录分把该记录放入最终位置后，序列被这个记录分割成两局部，所有关键字比该记录关键字小的割成两局部，所有关键字比该记录关键字小的割成两局部，所有关键字比该记录关键字小的割成两局部，所有关键字比该记录关键字小的放置在前一局部，所有比它大的放置在后一局放置在前一局部，所有比它大的放置在后一局放置在前一局部，所有比它大的放置在后一局放置在前一局部，所有比它大的放置在后一局部，并把该记录排在这两局部的中间。部，并把该记录排在这两局部的中间。部，并把该记录排在这两局部的中间。部，并把该记录排在这两局部的中间。
