【课件】计算机考研基础讲义 数据结构基础

《【课件】计算机考研基础讲义 数据结构基础》由会员分享，可在线阅读，更多相关《【课件】计算机考研基础讲义 数据结构基础（108页珍藏版）》请在金锄头文库上搜索。

1、计算机考研小组计算机考研小组计算机考研小组计算机考研小组(100)(100)(100)(100)2010201020102010年计算机考研基础班讲义年计算机考研基础班讲义年计算机考研基础班讲义年计算机考研基础班讲义http:/ 绪论绪论n n什么是数据结构直观定义：数据结构是研究程序设计中计算直观定义：数据结构是研究程序设计中计算机操作的对象以及它们之间关系和运算的一机操作的对象以及它们之间关系和运算的一门学科。门学科。数据结构是指数据之间的关系数据结构是指数据之间的关系 按某种关系组织起来的一批数据。以一按某种关系组织起来的一批数据。以一定的存储方式把它们存储到计算机的存储器定的存储方式把

2、它们存储到计算机的存储器中，并在这些数据上定义一个运算集合，这中，并在这些数据上定义一个运算集合，这就是数据结构。就是数据结构。学习数据结构的重要性学习数据结构的重要性1.1.“ “数据结构数据结构数据结构数据结构” ”在计算机科学中是一门综合性的专在计算机科学中是一门综合性的专在计算机科学中是一门综合性的专在计算机科学中是一门综合性的专业基础课业基础课业基础课业基础课, , 在考研中占很大的分值。在考研中占很大的分值。在考研中占很大的分值。在考研中占很大的分值。2.2.2.2.数据结构是介于数学、计算机硬件和计算机软数据结构是介于数学、计算机硬件和计算机软数据结构是介于数学、计算机硬件和计算

3、机软数据结构是介于数学、计算机硬件和计算机软件三者之间的一门核心课程。件三者之间的一门核心课程。件三者之间的一门核心课程。件三者之间的一门核心课程。3.3.3.3.数数数数据据据据结结结结构构构构这这这这一一一一门门门门课课课课的的的的内内内内容容容容不不不不仅仅仅仅是是是是一一一一般般般般程程程程序序序序设设设设计计计计（特特特特别别别别是是是是非非非非数数数数值值值值性性性性程程程程序序序序设设设设计计计计）的的的的基基基基础础础础，而而而而且且且且是是是是设设设设计计计计和和和和实实实实现现现现编编编编译译译译程程程程序序序序、操操操操作作作作系系系系统统统统、数数数数据据据据库库库库系

4、系系系统统统统及其他系统程序的重要基础。及其他系统程序的重要基础。及其他系统程序的重要基础。及其他系统程序的重要基础。1.2数据结构的概念数据结构的概念一、基本概念一、基本概念n n数据：数据：数据：数据：能输入计算机且被能计算机处理的一切对能输入计算机且被能计算机处理的一切对能输入计算机且被能计算机处理的一切对能输入计算机且被能计算机处理的一切对象。象。象。象。n n数据元素：数据元素：数据元素：数据元素：对现实世界中某独立个体的数据描述。对现实世界中某独立个体的数据描述。对现实世界中某独立个体的数据描述。对现实世界中某独立个体的数据描述。n n数据项：数据项：数据项：数据项：具有独立意义的

5、最小数据单位。具有独立意义的最小数据单位。具有独立意义的最小数据单位。具有独立意义的最小数据单位。n n数据类型：数据类型：数据类型：数据类型：每个数据项必须属于某确定的数据类每个数据项必须属于某确定的数据类每个数据项必须属于某确定的数据类每个数据项必须属于某确定的数据类型。型。型。型。基础基础 1.3数据的逻辑结构数据的逻辑结构一、基本概念一、基本概念n n数据对象：数据对象：数据对象：数据对象：具有相同特征的数据元素的集合。具有相同特征的数据元素的集合。具有相同特征的数据元素的集合。具有相同特征的数据元素的集合。n n关系：关系：关系：关系：在数据对象中各数据元素之间存在着在数据对象中各数

6、据元素之间存在着在数据对象中各数据元素之间存在着在数据对象中各数据元素之间存在着某种关系（或联系）。这种关系反映了该数某种关系（或联系）。这种关系反映了该数某种关系（或联系）。这种关系反映了该数某种关系（或联系）。这种关系反映了该数据对象中数据元素所固有的一种结构。在数据对象中数据元素所固有的一种结构。在数据对象中数据元素所固有的一种结构。在数据对象中数据元素所固有的一种结构。在数据处理领域，通常把数据之间这种固有的关据处理领域，通常把数据之间这种固有的关据处理领域，通常把数据之间这种固有的关据处理领域，通常把数据之间这种固有的关系简单的用前驱和后继关系描述。系简单的用前驱和后继关系描述。系简

7、单的用前驱和后继关系描述。系简单的用前驱和后继关系描述。1.3数据的逻辑结构数据的逻辑结构二、数据的逻辑结构二、数据的逻辑结构n n设设设设D D表示数据元素的集合，表示数据元素的集合，表示数据元素的集合，表示数据元素的集合，R R表示表示表示表示D D上的关系的集合，上的关系的集合，上的关系的集合，上的关系的集合，则一个数据结构则一个数据结构则一个数据结构则一个数据结构B B可表示为：可表示为：可表示为：可表示为：n nB = B = （ D D ，R R ）n n由此可见数据结构由两部分构成由此可见数据结构由两部分构成由此可见数据结构由两部分构成由此可见数据结构由两部分构成n n（1 1）

8、表示各元素的信息）表示各元素的信息）表示各元素的信息）表示各元素的信息 D Dn n（2 2）表示数据之间关系的信息）表示数据之间关系的信息）表示数据之间关系的信息）表示数据之间关系的信息R Rn n一般用二元组表示一般用二元组表示一般用二元组表示一般用二元组表示D D中各数据元素之间的前驱、中各数据元素之间的前驱、中各数据元素之间的前驱、中各数据元素之间的前驱、后继关系。假设后继关系。假设后继关系。假设后继关系。假设a,ba,b是是是是D D中的两个元素，则二元中的两个元素，则二元中的两个元素，则二元中的两个元素，则二元组组组组表示表示表示表示a a是是是是b b的前驱，的前驱，的前驱，的前

9、驱，b b是是是是a a的后继。的后继。的后继。的后继。1.3 数据的逻辑结构数据的逻辑结构三、数据结构的分类三、数据结构的分类三、数据结构的分类三、数据结构的分类n n线性结构：线性结构：线性结构：线性结构：除了一个根结点外，其他各结点有除了一个根结点外，其他各结点有除了一个根结点外，其他各结点有除了一个根结点外，其他各结点有唯一的前驱；除了一个终端结点外，其他各结点唯一的前驱；除了一个终端结点外，其他各结点唯一的前驱；除了一个终端结点外，其他各结点唯一的前驱；除了一个终端结点外，其他各结点有唯一的后继。有唯一的后继。有唯一的后继。有唯一的后继。n n树状结构：树状结构：树状结构：树状结构：

10、除了一个根结点外，各结点有唯一除了一个根结点外，各结点有唯一除了一个根结点外，各结点有唯一除了一个根结点外，各结点有唯一的前驱；所有的结点都可以有多个后继。的前驱；所有的结点都可以有多个后继。的前驱；所有的结点都可以有多个后继。的前驱；所有的结点都可以有多个后继。n n网状结构：网状结构：网状结构：网状结构：各结点可以有多个前驱或多个后继。各结点可以有多个前驱或多个后继。各结点可以有多个前驱或多个后继。各结点可以有多个前驱或多个后继。1.4 数据的存储结构数据的存储结构n n数据结构在计算机中的表示称为数据的存储结构。数据结构在计算机中的表示称为数据的存储结构。数据结构在计算机中的表示称为数据

11、的存储结构。数据结构在计算机中的表示称为数据的存储结构。n n数据结构包括结点的值及结点之间的关系，其存储结数据结构包括结点的值及结点之间的关系，其存储结数据结构包括结点的值及结点之间的关系，其存储结数据结构包括结点的值及结点之间的关系，其存储结构除了必须存储结点的值外，还得能以直接或隐含的构除了必须存储结点的值外，还得能以直接或隐含的构除了必须存储结点的值外，还得能以直接或隐含的构除了必须存储结点的值外，还得能以直接或隐含的方式体现出结点之间的关系。方式体现出结点之间的关系。方式体现出结点之间的关系。方式体现出结点之间的关系。n n四种基本的存储方式：四种基本的存储方式：四种基本的存储方式：

12、四种基本的存储方式：n n1 1、顺序方式、顺序方式、顺序方式、顺序方式n n顺序结构最适合于线性结构，它把逻辑上相邻的结顺序结构最适合于线性结构，它把逻辑上相邻的结顺序结构最适合于线性结构，它把逻辑上相邻的结顺序结构最适合于线性结构，它把逻辑上相邻的结点存放到物理上相邻的存储单元中，顺序存储结构点存放到物理上相邻的存储单元中，顺序存储结构点存放到物理上相邻的存储单元中，顺序存储结构点存放到物理上相邻的存储单元中，顺序存储结构只存储结点的值，不存储结点的关系，结点的关系只存储结点的值，不存储结点的关系，结点的关系只存储结点的值，不存储结点的关系，结点的关系只存储结点的值，不存储结点的关系，结点

13、的关系通过存储单元相邻关系隐含表示出来。通过存储单元相邻关系隐含表示出来。通过存储单元相邻关系隐含表示出来。通过存储单元相邻关系隐含表示出来。1.4 数据的存储结构数据的存储结构n n2 2、链接方式、链接方式、链接方式、链接方式n n链接存储方式不仅存储结点的值，而且还存储链接存储方式不仅存储结点的值，而且还存储链接存储方式不仅存储结点的值，而且还存储链接存储方式不仅存储结点的值，而且还存储结点之间的关系。它利用结点附加的指针字段，结点之间的关系。它利用结点附加的指针字段，结点之间的关系。它利用结点附加的指针字段，结点之间的关系。它利用结点附加的指针字段，存储其后继结点的地址。存储其后继结点

14、的地址。存储其后继结点的地址。存储其后继结点的地址。n n3 3、索引方式、索引方式、索引方式、索引方式n n在线性结构中，各结点可以依前驱、后继关系在线性结构中，各结点可以依前驱、后继关系在线性结构中，各结点可以依前驱、后继关系在线性结构中，各结点可以依前驱、后继关系排成一个序列（排成一个序列（排成一个序列（排成一个序列（a a1 1,a,a2 2,a,a3 3, , a an n) )。每个结点。每个结点。每个结点。每个结点a ai i在序列中都对应一个序号在序列中都对应一个序号在序列中都对应一个序号在序列中都对应一个序号i i序号序号序号序号i i也称为结点也称为结点也称为结点也称为结点

15、a ai i的的的的索引号。索引存储就是通过建立一个附加的索索引号。索引存储就是通过建立一个附加的索索引号。索引存储就是通过建立一个附加的索索引号。索引存储就是通过建立一个附加的索引表，然后利用索引表中的索引项的值来确定引表，然后利用索引表中的索引项的值来确定引表，然后利用索引表中的索引项的值来确定引表，然后利用索引表中的索引项的值来确定结点的实际存储单元的地址。结点的实际存储单元的地址。结点的实际存储单元的地址。结点的实际存储单元的地址。1.4 数据的存储结构数据的存储结构n n4 4、散列方式、散列方式、散列方式、散列方式n n利用该结点的值确定该结点的存储单元地址。利用该结点的值确定该结

16、点的存储单元地址。利用该结点的值确定该结点的存储单元地址。利用该结点的值确定该结点的存储单元地址。1.5 数据运算和算法数据运算和算法1 1、数据运算、数据运算、数据运算、数据运算n n按一定的逻辑结构把数据组织起来，采用适当的存储按一定的逻辑结构把数据组织起来，采用适当的存储按一定的逻辑结构把数据组织起来，采用适当的存储按一定的逻辑结构把数据组织起来，采用适当的存储方式把数据结构存储到计算机中，最终的目的是为了方式把数据结构存储到计算机中，最终的目的是为了方式把数据结构存储到计算机中，最终的目的是为了方式把数据结构存储到计算机中，最终的目的是为了有效地处理数据，提高数据的运算效率。有效地处理

17、数据，提高数据的运算效率。有效地处理数据，提高数据的运算效率。有效地处理数据，提高数据的运算效率。n n1 1）插入：往数据结构中添加新的结点称为插入。）插入：往数据结构中添加新的结点称为插入。）插入：往数据结构中添加新的结点称为插入。）插入：往数据结构中添加新的结点称为插入。n n2 2）删除：把指定的结点从数据结构中删除。）删除：把指定的结点从数据结构中删除。）删除：把指定的结点从数据结构中删除。）删除：把指定的结点从数据结构中删除。n n3 3）更新：改变指定结点的值或者改变某些结点的关）更新：改变指定结点的值或者改变某些结点的关）更新：改变指定结点的值或者改变某些结点的关）更新：改变指

18、定结点的值或者改变某些结点的关系称为更新。系称为更新。系称为更新。系称为更新。n n4 4）查找：在数据结构中查找某些满足条件的结点。）查找：在数据结构中查找某些满足条件的结点。）查找：在数据结构中查找某些满足条件的结点。）查找：在数据结构中查找某些满足条件的结点。n n5 5）排序：对线性表的各结点，按指定数据项的值从）排序：对线性表的各结点，按指定数据项的值从）排序：对线性表的各结点，按指定数据项的值从）排序：对线性表的各结点，按指定数据项的值从小到大或从大到小的重新排列。排序运算实际上是破小到大或从大到小的重新排列。排序运算实际上是破小到大或从大到小的重新排列。排序运算实际上是破小到大或

19、从大到小的重新排列。排序运算实际上是破坏线性表的旧关系，重新建立线性表的新关系。坏线性表的旧关系，重新建立线性表的新关系。坏线性表的旧关系，重新建立线性表的新关系。坏线性表的旧关系，重新建立线性表的新关系。1.5 数据运算和算法数据运算和算法2 2、算法、算法、算法、算法n n算法是对特定问题求解步骤的一种描述。算法是对特定问题求解步骤的一种描述。算法是对特定问题求解步骤的一种描述。算法是对特定问题求解步骤的一种描述。n n算法应具有的几个特征：算法应具有的几个特征：算法应具有的几个特征：算法应具有的几个特征：n n1 1）有穷性：算法应在计算机存储资源容许的条件下，）有穷性：算法应在计算机存

20、储资源容许的条件下，）有穷性：算法应在计算机存储资源容许的条件下，）有穷性：算法应在计算机存储资源容许的条件下，在一定时间内执行完毕。在一定时间内执行完毕。在一定时间内执行完毕。在一定时间内执行完毕。n n2 2）确定性：算法的每一步骤应定义明确，没有二义。）确定性：算法的每一步骤应定义明确，没有二义。）确定性：算法的每一步骤应定义明确，没有二义。）确定性：算法的每一步骤应定义明确，没有二义。n n3 3）可行性：算法是可以被计算机执行的。当输入正确）可行性：算法是可以被计算机执行的。当输入正确）可行性：算法是可以被计算机执行的。当输入正确）可行性：算法是可以被计算机执行的。当输入正确的数据后

21、，应得到正确的结果。的数据后，应得到正确的结果。的数据后，应得到正确的结果。的数据后，应得到正确的结果。1.5 数据运算和算法数据运算和算法3 3、算法的评价、算法的评价、算法的评价、算法的评价n n对算法评价的几个指标对算法评价的几个指标对算法评价的几个指标对算法评价的几个指标n n空间复杂度空间复杂度空间复杂度空间复杂度n n空间复杂度是指执行算法所需要的辅助空间空间复杂度是指执行算法所需要的辅助空间空间复杂度是指执行算法所需要的辅助空间空间复杂度是指执行算法所需要的辅助空间大小。大小。大小。大小。n n时间复杂度时间复杂度时间复杂度时间复杂度n n时间复杂度是指执行完算法所需的运算次数。

22、时间复杂度是指执行完算法所需的运算次数。时间复杂度是指执行完算法所需的运算次数。时间复杂度是指执行完算法所需的运算次数。第二章第二章 线性表线性表n n线性表是一种最简单、最常用的数据结构。线性表是一种最简单、最常用的数据结构。线性表是一种最简单、最常用的数据结构。线性表是一种最简单、最常用的数据结构。n n线性表的主要存储结构有两种：顺序存储结线性表的主要存储结构有两种：顺序存储结线性表的主要存储结构有两种：顺序存储结线性表的主要存储结构有两种：顺序存储结构和链接存储结构。构和链接存储结构。构和链接存储结构。构和链接存储结构。2.1 线性表的定义及基本运算线性表的定义及基本运算n n一、线性

23、表的定义一、线性表的定义一、线性表的定义一、线性表的定义n n线性表是由线性表是由线性表是由线性表是由n(n0)n(n0)个性质相同的数据元素个性质相同的数据元素个性质相同的数据元素个性质相同的数据元素a a1 1,a,a2 2,a,a3 3, ,a an n组成的有限序列，记为组成的有限序列，记为组成的有限序列，记为组成的有限序列，记为(a(a1 1,a,a2 2,a,a3 3, ,a an n) )。n n二、线性表的基本运算二、线性表的基本运算二、线性表的基本运算二、线性表的基本运算n n（1 1）置线性表为空表；）置线性表为空表；）置线性表为空表；）置线性表为空表；n n（2 2）求线

24、性表的长度；）求线性表的长度；）求线性表的长度；）求线性表的长度；n n（3 3）读取线性表中的第）读取线性表中的第）读取线性表中的第）读取线性表中的第i i个元素；个元素；个元素；个元素；n n（4 4）修改线性表中的第）修改线性表中的第）修改线性表中的第）修改线性表中的第i i个元素；个元素；个元素；个元素；n n（5 5）查找线性表中具有某个特征值的数据元素；）查找线性表中具有某个特征值的数据元素；）查找线性表中具有某个特征值的数据元素；）查找线性表中具有某个特征值的数据元素；2.1 线性表的定义及基本运算线性表的定义及基本运算n n二、线性表的基本运算二、线性表的基本运算二、线性表的基

25、本运算二、线性表的基本运算n n（6 6）在线性表的第）在线性表的第）在线性表的第）在线性表的第i i个数据元素之前或之后插入一个数据元素之前或之后插入一个数据元素之前或之后插入一个数据元素之前或之后插入一个新的数据元素；个新的数据元素；个新的数据元素；个新的数据元素；n n（7 7）删除线性表中第）删除线性表中第）删除线性表中第）删除线性表中第i i个数据元素或满足给定条件个数据元素或满足给定条件个数据元素或满足给定条件个数据元素或满足给定条件的第一个数据元素；的第一个数据元素；的第一个数据元素；的第一个数据元素；n n（8 8）对线性表中的所有元素按照给定的关键字大）对线性表中的所有元素按

26、照给定的关键字大）对线性表中的所有元素按照给定的关键字大）对线性表中的所有元素按照给定的关键字大小进行排序。小进行排序。小进行排序。小进行排序。2.2 线性表的顺序存储结构及运算线性表的顺序存储结构及运算一、一、一、一、线性表的顺序存储结构线性表的顺序存储结构线性表的顺序存储结构线性表的顺序存储结构线性表的顺序存储结构是将线性表中的结点按其线性表的顺序存储结构是将线性表中的结点按其线性表的顺序存储结构是将线性表中的结点按其线性表的顺序存储结构是将线性表中的结点按其逻辑顺序依次存放在内存中一组连续的存储单元中，即把逻辑顺序依次存放在内存中一组连续的存储单元中，即把逻辑顺序依次存放在内存中一组连续

27、的存储单元中，即把逻辑顺序依次存放在内存中一组连续的存储单元中，即把线性表中相邻的结点存放在地址相邻的内存单元中。线性表中相邻的结点存放在地址相邻的内存单元中。线性表中相邻的结点存放在地址相邻的内存单元中。线性表中相邻的结点存放在地址相邻的内存单元中。线性表在线性表在线性表在线性表在c c语言中用一维数组表示。语言中用一维数组表示。语言中用一维数组表示。语言中用一维数组表示。c c语言的描述语言的描述语言的描述语言的描述Typedef int ET;Typedef int ET; #define maxlen 1000 #define maxlen 1000 ET smaxlen; ET sm

28、axlen;2.2 线性表的顺序存储结构及运算线性表的顺序存储结构及运算一、一、一、一、线性表的顺序存储结构线性表的顺序存储结构线性表的顺序存储结构线性表的顺序存储结构线性表线性表线性表线性表C C语言描述的说明：语言描述的说明：语言描述的说明：语言描述的说明：在在在在C C语言中，数组的下标是从语言中，数组的下标是从语言中，数组的下标是从语言中，数组的下标是从0 0开始的，开始的，开始的，开始的，数据结构中的结点的序号是从一开始的。因数据结构中的结点的序号是从一开始的。因数据结构中的结点的序号是从一开始的。因数据结构中的结点的序号是从一开始的。因此在线性表中的第一个元素是指此在线性表中的第一

29、个元素是指此在线性表中的第一个元素是指此在线性表中的第一个元素是指S0S0。两个相邻结点两个相邻结点两个相邻结点两个相邻结点a ai i和和和和a a i+1i+1的存储位置记为的存储位置记为的存储位置记为的存储位置记为LOCLOC（ a ai i ）和）和）和）和LOCLOC（ a a i+1i+1 ），则结），则结），则结），则结点满足以下关系点满足以下关系点满足以下关系点满足以下关系LOCLOC（ a a i+1i+1 ）= LOC= LOC（ a ai i ）+1+12.2 线性表的顺序存储结构及运算线性表的顺序存储结构及运算二、线性表的运算二、线性表的运算二、线性表的运算二、线性表的

30、运算1 1、插入运算的算法描述：、插入运算的算法描述：、插入运算的算法描述：、插入运算的算法描述：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

31、(1); return(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+

32、) sj-1=sj; 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-l

33、ink=NULL; 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，算法的基本思想为：，算法的基本思想为：，算

34、法的基本思想为：，算法的基本思想为：从表头指针指向的第一个结点开始，依次把表中从表头指针指向的第一个结点开始，依次把表中从表头指针指向的第一个结点开始，依次把表中从表头指针指向的第一个结点开始，依次把表中结点的数据域和给定值结点的数据域和给定值结点的数据域和给定值结点的数据域和给定值X X 进行比较，直到某个结点进行比较，直到某个结点进行比较，直到某个结点进行比较，直到某个结点的数据域的值等于给定值的数据域的值等于给定值的数据域的值等于给定值的数据域的值等于给定值X X （既查找成功），则返（既查找成功），则返（既查找成功），则返（既查找成功），则返回该结点的地址；如果查找到表尾仍未找到（既查

35、回该结点的地址；如果查找到表尾仍未找到（既查回该结点的地址；如果查找到表尾仍未找到（既查回该结点的地址；如果查找到表尾仍未找到（既查找失败），则返回找失败），则返回找失败），则返回找失败），则返回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

36、 X 在链表中的某一结点在链表中的某一结点在链表中的某一结点在链表中的某一结点p p 之后插入一个数据为之后插入一个数据为之后插入一个数据为之后插入一个数据为X X 的新结的新结的新结的新结点。过程如下：点。过程如下：点。过程如下：点。过程如下：（1 1）生成一个新结点）生成一个新结点）生成一个新结点）生成一个新结点q q ，将，将，将，将X X 赋给赋给赋给赋给q-data;q-data; （2 2）修改有关结点的指针域：将原）修改有关结点的指针域：将原）修改有关结点的指针域：将原）修改有关结点的指针域：将原p p 结点的后继作结点的后继作结点的后继作结点的后继作为为为为q q 结点的后继，

37、结点的后继，结点的后继，结点的后继，q q 结点作为结点作为结点作为结点作为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 (he

38、ad-link=NULL) head-link=q;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 ，并由系统收回其占用的存储空，并由系统收回其占用的存储空，并由系统收回其占用的存储空，并由系统收回其占用的存储空间。过程如

39、下：间。过程如下：间。过程如下：间。过程如下：（1 1）设定两指针）设定两指针）设定两指针）设定两指针p p 和和和和q q ，p p 指针指向被删除结点；指针指向被删除结点；指针指向被删除结点；指针指向被删除结点；q q 为跟踪结点，指向被删除结点的前驱结点为跟踪结点，指向被删除结点的前驱结点为跟踪结点，指向被删除结点的前驱结点为跟踪结点，指向被删除结点的前驱结点; ; （2 2）p p 从表头指针从表头指针从表头指针从表头指针headhead指向的第一个结点开始向后依指向的第一个结点开始向后依指向的第一个结点开始向后依指向的第一个结点开始向后依次进行搜索。当次进行搜索。当次进行搜索。当次进

40、行搜索。当p-datap-data等于等于等于等于X X 时，被删除结点找到。时，被删除结点找到。时，被删除结点找到。时，被删除结点找到。（3 3）修改）修改）修改）修改p p 的前驱结点的前驱结点的前驱结点的前驱结点q q 的指针域：使被删除结点的指针域：使被删除结点的指针域：使被删除结点的指针域：使被删除结点的后继结点成为其前驱结点的后继结点，既的后继结点成为其前驱结点的后继结点，既的后继结点成为其前驱结点的后继结点，既的后继结点成为其前驱结点的后继结点，既q-link=p-q-link=p-linklink，p p结点被删除，然后再释放存储空间。结点被删除，然后再释放存储空间。结点被删除

41、，然后再释放存储空间。结点被删除，然后再释放存储空间。在单链表中删除结点在单链表中删除结点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(

42、Not found!n); printf(Not found!n); else else q-link=p-link;free(p); q-link=p-link;free(p); 2.3 线性表的链接存储结构及运算线性表的链接存储结构及运算三、循环链表三、循环链表三、循环链表三、循环链表链表中的最后一个结点的指针指向链表中链表中的最后一个结点的指针指向链表中链表中的最后一个结点的指针指向链表中链表中的最后一个结点的指针指向链表中第一个结点，使链表形成一个环行，此链表称第一个结点，使链表形成一个环行，此链表称第一个结点，使链表形成一个环行，此链表称第一个结点，使链表形成一个环行，此链表称循环链

43、表。循环链表。循环链表。循环链表。循环链表是线性链表的一种变形。其优点循环链表是线性链表的一种变形。其优点循环链表是线性链表的一种变形。其优点循环链表是线性链表的一种变形。其优点是从链表中任何一个结点出发都可以访问到表是从链表中任何一个结点出发都可以访问到表是从链表中任何一个结点出发都可以访问到表是从链表中任何一个结点出发都可以访问到表中的所有结点。中的所有结点。中的所有结点。中的所有结点。在循环链表中为了使空表和非空表处理一在循环链表中为了使空表和非空表处理一在循环链表中为了使空表和非空表处理一在循环链表中为了使空表和非空表处理一致，可以附加一个表头结点。致，可以附加一个表头结点。致，可以附

44、加一个表头结点。致，可以附加一个表头结点。2.3 线性表的链接存储结构及运算线性表的链接存储结构及运算三、循环链表三、循环链表非空表（a)headhead空表（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-l

45、ink)-data)!=x) (p-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

46、*)malloc(sizeof(NODE); 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; NOD

47、E *p,*q; q=looknode(head,x); q=looknode(head,x); if (q-link=head) if (q-link=head) printf( printf(“ “No this node the list!nNo 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 线性表的链接存储结构及运算线性表的链接存储结构及运算四、循环链表四、循环链表四、循环链表

48、四、循环链表一个链表的每一个结点含有两一个链表的每一个结点含有两一个链表的每一个结点含有两一个链表的每一个结点含有两个指针域，一个指针指向其前驱结点，个指针域，一个指针指向其前驱结点，个指针域，一个指针指向其前驱结点，个指针域，一个指针指向其前驱结点，另一个指针指向其后继结点，这样的链另一个指针指向其后继结点，这样的链另一个指针指向其后继结点，这样的链另一个指针指向其后继结点，这样的链表称为双向链表。表称为双向链表。表称为双向链表。表称为双向链表。五、双向链表五、双向链表headllinkrlinkdata带头结点的双向链表带头结点的双向链表双向链表的结点结构双向链表的结点结构2.4 数组数组

49、一、数组的定义一、数组的定义数组是由一组类型相同的数据元素数组是由一组类型相同的数据元素构造而成。构造而成。若数组元素只含有一个下标，这样若数组元素只含有一个下标，这样的数组称为一维数组。的数组称为一维数组。当一个数组的每一个数组元素都含当一个数组的每一个数组元素都含有两个下标时，该数组称为两维数组。有两个下标时，该数组称为两维数组。2.4 数组数组二、数组的存储结构二、数组的存储结构二、数组的存储结构二、数组的存储结构数组是一种顺序存储结构。也就是将数组元素数组是一种顺序存储结构。也就是将数组元素数组是一种顺序存储结构。也就是将数组元素数组是一种顺序存储结构。也就是将数组元素顺序地存放在一片

50、连续的存储单元中。顺序地存放在一片连续的存储单元中。顺序地存放在一片连续的存储单元中。顺序地存放在一片连续的存储单元中。三、规则矩阵的压缩存储三、规则矩阵的压缩存储三、规则矩阵的压缩存储三、规则矩阵的压缩存储有时矩阵中包含大量的零元素（或某一确定值有时矩阵中包含大量的零元素（或某一确定值有时矩阵中包含大量的零元素（或某一确定值有时矩阵中包含大量的零元素（或某一确定值的元素），为了节省存储空间，可以对这类矩阵采用的元素），为了节省存储空间，可以对这类矩阵采用的元素），为了节省存储空间，可以对这类矩阵采用的元素），为了节省存储空间，可以对这类矩阵采用压缩存储。压缩存储。压缩存储。压缩存储。所谓压缩

51、存储是指对零元素不分配存储空间，所谓压缩存储是指对零元素不分配存储空间，所谓压缩存储是指对零元素不分配存储空间，所谓压缩存储是指对零元素不分配存储空间，而只对非零元素进行存储。压缩存储必须能够体现矩而只对非零元素进行存储。压缩存储必须能够体现矩而只对非零元素进行存储。压缩存储必须能够体现矩而只对非零元素进行存储。压缩存储必须能够体现矩阵的逻辑结构。阵的逻辑结构。阵的逻辑结构。阵的逻辑结构。 2.4 数组数组四、稀疏矩阵及存储四、稀疏矩阵及存储四、稀疏矩阵及存储四、稀疏矩阵及存储当一个矩阵的非零元素的个数远远少于零元当一个矩阵的非零元素的个数远远少于零元当一个矩阵的非零元素的个数远远少于零元当一

52、个矩阵的非零元素的个数远远少于零元素的个数时，称该矩阵为稀疏矩阵。对稀疏矩阵素的个数时，称该矩阵为稀疏矩阵。对稀疏矩阵素的个数时，称该矩阵为稀疏矩阵。对稀疏矩阵素的个数时，称该矩阵为稀疏矩阵。对稀疏矩阵的存储方式常采用压缩存储。方法有两种：三元的存储方式常采用压缩存储。方法有两种：三元的存储方式常采用压缩存储。方法有两种：三元的存储方式常采用压缩存储。方法有两种：三元组表和十字链表。组表和十字链表。组表和十字链表。组表和十字链表。1 1、在稀疏矩阵中，每一个非零元素可以用、在稀疏矩阵中，每一个非零元素可以用、在稀疏矩阵中，每一个非零元素可以用、在稀疏矩阵中，每一个非零元素可以用它所在的行号它所

53、在的行号它所在的行号它所在的行号 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.4 数组数组 40 0 1 00 0 2 0 090 0 0 00 0 0 0 70

54、 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 Ma0Ma1Ma2Ma3Ma4Ma5Ma6A=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 Mb0Mb1Mb2Mb3Mb4Mb5Mb6B=2.4 数组数组实现矩阵转置的算法：实现矩阵转置的算法： int syz(NODE ma,NODE m

55、b)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; 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;

56、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; NODE *q; if (top != NULL) if (top != NULL) *q=top; *q=top; *p=top-data; *p=top-data; top=top-link; top=to

57、p-link; free(q); free(q); return (top); return (top); 3.1.2 栈的存储结构及其运算栈的存储结构及其运算3 3、栈的应用举例、栈的应用举例、栈的应用举例、栈的应用举例 表表表表达达达达式式式式求求求求值值值值是是是是程程程程序序序序设设设设计计计计语语语语言言言言编编编编译译译译中中中中的的的的一一一一个个个个最最最最基基基基本本本本问问问问题题题题。它它它它的的的的实实实实现现现现方方方方法法法法是是是是栈栈栈栈的的的的一一一一个个个个典典典典型型型型的的的的应应应应用用用用实实实实例。例。例。例。 (1)(1)中中中中缀缀缀缀算算算算

58、术术术术表表表表达达达达式式式式：将将将将运运运运算算算算符符符符置置置置于于于于两两两两个个个个操操操操作作作作数数数数中间的算术表达式，称中缀表达史。中间的算术表达式，称中缀表达史。中间的算术表达式，称中缀表达史。中间的算术表达式，称中缀表达史。 （2 2）后后后后缀缀缀缀表表表表达达达达式式式式：将将将将运运运运算算算算符符符符置置置置于于于于两两两两个个个个操操操操作作作作数数数数的的的的后后后后面面面面的的的的算算算算术术术术表表表表达达达达式式式式称称称称为为为为后后后后缀缀缀缀表表表表达达达达式式式式。这这这这种种种种表表表表达达达达式式式式不不不不存存存存在在在在括括括括号号号

59、号，也也也也不不不不存存存存在在在在优优优优先先先先级级级级的的的的差差差差别别别别，计计计计算算算算过过过过程程程程完完完完全全全全按按按按照照照照运运运运算算算算符符符符出出出出现现现现的的的的先先先先后后后后次次次次序序序序进进进进行行行行。计计计计算算算算机机机机在在在在处处处处理理理理这这这这种种种种表表表表达达达达式式式式时时时时，只只只只需需需需对对对对其其其其扫扫扫扫描描描描一一一一遍遍遍遍，就就就就可可可可完完完完成成成成计算。计算。计算。计算。3.2 队列队列 在在在在日日日日常常常常生生生生活活活活中中中中队队队队列列列列很很很很常常常常见见见见，如如如如，我我我我们们们

60、们经经经经常常常常排排排排队队队队购购购购物物物物或或或或购购购购票票票票，排排排排队队队队是是是是体体体体现现现现了了了了“ “先先先先来来来来先先先先服服服服务务务务” ”（即即即即“ “先先先先进进进进先先先先出出出出” ”）的原则。）的原则。）的原则。）的原则。 队队队队列列列列在在在在计计计计算算算算机机机机系系系系统统统统中中中中的的的的应应应应用用用用也也也也非非非非常常常常广广广广泛泛泛泛。例例例例如如如如：操操操操作作作作系系系系统统统统中中中中的的的的作作作作业业业业排排排排队队队队。在在在在多多多多道道道道程程程程序序序序运运运运行行行行的的的的计计计计算算算算机机机机系

61、系系系统统统统中中中中，可可可可以以以以同同同同时时时时有有有有多多多多个个个个作作作作业业业业运运运运行行行行，它它它它们们们们的的的的运运运运算算算算结结结结果果果果都都都都需需需需要要要要通通通通过过过过通通通通道道道道输输输输出出出出，若若若若通通通通道道道道尚尚尚尚未未未未完完完完成成成成输输输输出出出出，则则则则后后后后来来来来的的的的作作作作业业业业应应应应排排排排队队队队等等等等待待待待，每每每每当当当当通通通通道道道道完完完完成成成成输输输输出出出出时时时时，则则则则从从从从队队队队列列列列的的的的队队队队头头头头退退退退出出出出作作作作业业业业的的的的输输输输出出出出操操操

62、操作作作作，而而而而凡凡凡凡是是是是申申申申请请请请该该该该通通通通道道道道输输输输出出出出的的的的作作作作业业业业都都都都从从从从队队队队尾尾尾尾进进进进入该队列。入该队列。入该队列。入该队列。3.2 队列队列 计计计计算算算算机机机机系系系系统统统统中中中中输输输输入入入入输输输输出出出出缓缓缓缓冲冲冲冲区区区区的的的的结结结结构构构构也也也也是是是是队队队队列列列列的的的的应应应应用用用用。在在在在计计计计算算算算机机机机系系系系统统统统中中中中经经经经常常常常会会会会遇遇遇遇到到到到两两两两个个个个设设设设备备备备之之之之间间间间的的的的数数数数据据据据传传传传输输输输，不不不不同同同

63、同的的的的设设设设备备备备通通通通常常常常处处处处理理理理数数数数据据据据的的的的速速速速度度度度是是是是不不不不同同同同的的的的，当当当当需需需需要要要要在在在在它它它它们们们们之之之之间间间间连连连连续续续续处处处处理理理理一一一一批批批批数数数数据据据据时时时时，高高高高速速速速设设设设备备备备总总总总是是是是要要要要等等等等待待待待低低低低速速速速设设设设备备备备，这这这这就就就就造造造造成成成成计计计计算算算算机机机机处处处处理理理理效效效效率率率率的的的的大大大大大大大大降降降降低低低低。为为为为了了了了解解解解决决决决这这这这一一一一速速速速度度度度不不不不匹匹匹匹配配配配的的的

64、的矛矛矛矛盾盾盾盾，通通通通常常常常就就就就是是是是在在在在这这这这两两两两个个个个设设设设备备备备之之之之间间间间设设设设置置置置一一一一个个个个缓缓缓缓冲冲冲冲区区区区。这这这这样样样样，高高高高速速速速设设设设备备备备就就就就不不不不必必必必每每每每次次次次等等等等待待待待低低低低速速速速设设设设备备备备处处处处理理理理完完完完一一一一个个个个数数数数据据据据，而而而而是是是是把把把把要要要要处处处处理理理理的的的的数数数数据据据据依依依依次次次次从从从从一一一一端端端端加加加加入入入入缓缓缓缓冲冲冲冲区区区区，而而而而低低低低速速速速设设设设备备备备从从从从另另另另一一一一端端端端取取

65、取取走走走走要要要要处理的数据。处理的数据。处理的数据。处理的数据。3.2 队列队列一、队列的定义及运算一、队列的定义及运算一、队列的定义及运算一、队列的定义及运算 队队队队列列列列也也也也是是是是一一一一种种种种特特特特殊殊殊殊的的的的线线线线性性性性表表表表，它它它它是是是是只只只只允允允允许许许许在在在在表表表表的的的的一一一一端端端端进进进进行行行行插插插插入入入入，在在在在表表表表的的的的另另另另一一一一端端端端进进进进行行行行删删删删除除除除的的的的线线线线性性性性表表表表。允允允允许插入的一端称为队尾，允许删除的一端称为队首。许插入的一端称为队尾，允许删除的一端称为队首。许插入的

66、一端称为队尾，允许删除的一端称为队首。许插入的一端称为队尾，允许删除的一端称为队首。 若若若若给给给给定定定定队队队队列列列列q=(aq=(a0 0, , a a1 1, , a a2 2, , a a3 3, , a a4 4, , , , a a n-1n-1) )，我我我我们们们们称称称称a a0 0是队首元素，是队首元素，是队首元素，是队首元素，a a n-1n-1是队尾元素。是队尾元素。是队尾元素。是队尾元素。 a0, a1, a2, a3, a4, ,a i a n-1出队出队入队入队第四章第四章 递归递归 递递归归是是程程序序设设计计中中一一个个重重要要的的算算法法设设计计方方法

67、法和和技技术术。递递归归子子程程序序是是通通过过调调用用自自身身来来完完成成与与自自身身要要求求相相同同的的子子问问题题的的求求解解,并并利利用用系系统统内内部部功功能能自自动动实实现现调调用用过过程程中中信信息息的的保保存存与与恢恢复复，而而省省略略了了程程序序设设计计中中的的许许多多细细节节操操作作，简简化化了了程程序序设设计计过过程程,使使程程序序设设计计人人员员可可以以集集中中注注意意力力于于主主要要问问题题求求解上。解上。4.1 递归的定义 递递归归就就是是一一个个事事件件或或对对象象部部分分由由自自己己组组成。成。 递归算法包括递推和回归两部分递归算法包括递推和回归两部分 （1）递

68、递推推：就就是是为为得得到到问问题题的的解解，将将其推倒比原来问题简单的问题的求解。其推倒比原来问题简单的问题的求解。 （2）就就是是指指当当“简简单单的的问问题题得得到到解解后后，回归到原问题的解上。回归到原问题的解上。4.2 递归的实现 1、采用递归算法具备的条件、采用递归算法具备的条件 （1）所所需需解解决决的的问问题题可可以以转转化化成成另另一一个个问问题题，而而解解决决新新问问题题的的方方法法与与原原始始问问题题的解法相同。的解法相同。 （2）必必须须具具备备终终止止递递归归的的条条件件。程程序序中中不不能能出出现现无无终终止止的的递递归归调调用用，而而只只能能出出现有限次的，有终止

69、的递归调用。现有限次的，有终止的递归调用。4.2 递归的实现 2 2、递归算法示例、递归算法示例、递归算法示例、递归算法示例: n: n！（阶乘）算法的求解。！（阶乘）算法的求解。！（阶乘）算法的求解。！（阶乘）算法的求解。int fact(int n)int fact(int n) if (n= =0) if (n= =0) s=1; return 1; s=1; return 1; else else s=n*fact(n-1); s=n*fact(n-1); return s; return s; void main()void main() int n; int n; n= fact(

70、5); n= fact(5); printf( printf(“ “n=%dnn=%dn” ”,n,n4.3阶乘递归的实现main()main()参数表参数表参数表参数表返回地址返回地址返回地址返回地址活动记录进退栈示意图活动记录进退栈示意图fact(5)fact(5)5 5ReLoc1ReLoc1fact(4)fact(4)4 4ReLoc2ReLoc2fact(3)fact(3)3 3ReLoc3ReLoc3fact(2)fact(2)2 2ReLoc4ReLoc4fact(1)fact(1)1 1ReLoc5ReLoc50 0ReLoc6ReLoc6s=fact(1)=1*fact(0)

71、=1s=fact(2)=2*fact(1)=2s=fact(3)=3*fact(2)=6s=fact(4)=4*fact(3)=24s=fact(5)=5*fact(4)=120fact(0)=1调用者调用者主函数mani()N=fact(5)第一层调用n=5s=5*fact(4)第二层调用n=4s=4*fact(3)第三层调用n=3S=3*fact(2)第四层调用n=2S=2*fact(1)第五层调用n=1S=1fact(1)=1fact(2)=2fact(3)=6fact(4)=24fact(5)=120输出s=120.00递归调用过程示意图递归调用过程示意图从图中可看到fact函数共被调

72、用5次，即fact(5)、fact(4)、fact(3)、fact(2)、fact(1)。其中，fact(5)为主函数调用，其它则为在fact函数内调用。每一次递归调用并未立即得到结果，而是进一步向深度递归调用，直到n=1或n=0时，函数fact结果为1，然后再一一返回计算，最终得到结果。例例 汉诺塔汉诺塔传说在创世纪时，在一个叫传说在创世纪时，在一个叫BrahmaBrahma的寺庙里，有三个柱子，其中的寺庙里，有三个柱子，其中一柱上有一柱上有6464个盘子从小到大依次叠放，僧侣的工作是将这个盘子从小到大依次叠放，僧侣的工作是将这6464个盘个盘子从一根柱子移到另一个柱子上。子从一根柱子移到另

73、一个柱子上。 移动时的规则：移动时的规则： 每次只能移动一个盘子；每次只能移动一个盘子； 只能小盘子在大盘子上面；只能小盘子在大盘子上面； 可以使用任一柱子。可以使用任一柱子。当工作做完之后，就标志着世界永远和平。当工作做完之后，就标志着世界永远和平。x y zx y znn 1分析：分析： 设三根柱子分别为设三根柱子分别为 x x，y, z , y, z , 盘子在盘子在x x柱上，要移到柱上，要移到z z柱上。柱上。1 1、当、当n=1n=1时，盘子直接从时，盘子直接从 x x 柱移到柱移到 z z 柱上；柱上；2 2、当、当n1n1时时, , 则则设法将前设法将前n n1 1个盘子借助个

74、盘子借助z z，从，从x x移到移到y y柱上，柱上，把把 盘子盘子n n从从x x移到移到z z柱上；柱上； 把把n n1 1个盘子从个盘子从y y移到移到z z柱上。柱上。Hanoi问题void Hanoi ( int n, char x, char y, char z )void Hanoi ( int n, char x, char y, char z ) / /将将将将 n n 个个个个 编号从上到下为编号从上到下为编号从上到下为编号从上到下为 1 1n n 的盘子从的盘子从的盘子从的盘子从 x x 柱，借助柱，借助柱，借助柱，借助 y y 柱移到柱移到柱移到柱移到 z z 柱柱柱柱

75、 if ( n = = 1 ) if ( n = = 1 ) move ( x , 1 , z ) ; move ( x , 1 , z ) ; / /将编号为将编号为将编号为将编号为 1 1 的盘子从的盘子从的盘子从的盘子从 x x 柱移到柱移到柱移到柱移到 z z 柱柱柱柱 else else / /将将将将 n -1n -1个个个个 编号从上到下为编号从上到下为编号从上到下为编号从上到下为1 1n-1n-1的盘子从的盘子从的盘子从的盘子从 x x 柱，借助柱，借助柱，借助柱，借助 y y 柱移到柱移到柱移到柱移到 z z 柱柱柱柱 Hanoi ( n-1 , x , z , y ) ;

76、Hanoi ( n-1 , x , z , y ) ; move ( x , n, z) ; move ( x , n, z) ; / /将编号为将编号为将编号为将编号为 n n 的盘子从的盘子从的盘子从的盘子从 x x 柱移到柱移到柱移到柱移到 z z 柱柱柱柱 / /将将将将 n -1n -1个个个个 编号从上到下为编号从上到下为编号从上到下为编号从上到下为 1 1n-1n-1的盘子从的盘子从的盘子从的盘子从 y y 柱，借助柱，借助柱，借助柱，借助 x x 柱移到柱移到柱移到柱移到 z z 柱柱柱柱 Hanoi ( n-1 , y , x , z );Hanoi ( n-1 , y ,

77、x , z ); /Hanoi /Hanoi第五章第五章 串串 在在在在计计计计算算算算机机机机的的的的各各各各方方方方面面面面应应应应用用用用中中中中，非非非非数数数数值值值值处处处处理理理理问问问问题题题题的的的的应应应应用用用用越越越越来来来来越越越越多多多多。如如如如程程程程序序序序源源源源代代代代码码码码，在在在在事事事事务务务务处处处处理理理理系系系系统统统统中中中中，用用用用户户户户的的的的姓姓姓姓名名名名和和和和地地地地址址址址及及及及货货货货物物物物的的的的名名名名称称称称、规规规规格格格格等等等等，都都都都是是是是作作作作为一种字符串数据进行处理的。为一种字符串数据进行处理

78、的。为一种字符串数据进行处理的。为一种字符串数据进行处理的。 字字字字符符符符串串串串一一一一般般般般简简简简称称称称为为为为串串串串，可可可可以以以以将将将将它它它它看看看看作作作作是是是是一一一一种种种种特特特特殊殊殊殊的的的的线线线线性性性性表表表表，这这这这种种种种线线线线性性性性表表表表的的的的数数数数据据据据元元元元素素素素的的的的类类类类型型型型总总总总是是是是字字字字符符符符型型型型的的的的，字字字字符符符符串串串串的的的的数数数数据据据据对对对对象象象象约约约约束束束束为为为为字字字字符符符符集集集集。在在在在一一一一般般般般线线线线性性性性表表表表的的的的基基基基本本本本操

79、操操操作作作作中中中中，大大大大多多多多以以以以“ “单单单单个个个个元元元元素素素素” ”作作作作为为为为操操操操作作作作对对对对象象象象，而而而而在在在在串串串串中中中中，则则则则是是是是以以以以“ “串串串串的的的的整整整整体体体体” ”或或或或一一一一部部部部分分分分作作作作为为为为操操操操作作作作对对对对象象象象。因因因因此此此此，一一一一般般般般线线线线性性性性表表表表和和和和串串串串的的的的操操操操作作作作有有有有很很很很大大大大的的的的不不不不同同同同。本本本本章章章章主主主主要要要要讨讨讨讨论论论论串串串串的的的的基基基基本本本本概概概概念念念念、存存存存储储储储结结结结构构

80、构构和和和和一些基本的串处理操作。一些基本的串处理操作。一些基本的串处理操作。一些基本的串处理操作。5.1 串的基本概念串的基本概念 串串串串（或或或或字字字字符符符符串串串串）（StringString）是是是是由由由由零零零零个个个个或或或或多多多多个个个个字字字字符符符符组成的有限序列。一般记作组成的有限序列。一般记作组成的有限序列。一般记作组成的有限序列。一般记作 s=s=a a0 0a a1 1a a2 2a an-1n-1 (n0) (n0) 其其其其中中中中：s s为为为为串串串串名名名名，用用用用双双双双引引引引号号号号括括括括起起起起来来来来的的的的字字字字符符符符序序序序列

81、列列列是是是是串串串串的的的的值值值值；a ai i(0in-1)(0in-1)可可可可以以以以是是是是字字字字母母母母、数数数数字字字字或或或或其其其其它它它它字字字字符符符符；双双双双引引引引号号号号为为为为串串串串值值值值的的的的定定定定界界界界符符符符，不不不不是是是是串串串串的的的的一一一一部部部部分分分分；字字字字符符符符串串串串字字字字符符符符的的的的数数数数目目目目n n称称称称为为为为串串串串的的的的长长长长度度度度。零零零零个个个个字字字字符符符符的的的的串串串串称称称称为为为为空空空空串串串串，通通通通常常常常以以以以两两两两个个个个相相相相邻邻邻邻的的的的双双双双引引引

82、引号号号号来来来来表表表表示示示示空空空空串串串串（Null Null stringstring），如如如如：s=s=，它它它它的的的的长长长长度度度度为为为为零零零零；仅仅仅仅由由由由空空空空格格格格组组组组成成成成的的的的的的的的串串串串称称称称为为为为空空空空格格格格串串串串，如如如如：s=s=；若若若若串串串串中中中中含含含含有有有有空空空空格格格格，在在在在计计计计算算算算串串串串长长长长时时时时，空空空空格格格格应应应应计计计计入入入入串串串串的的的的长长长长度度度度中中中中，如：如：如：如：s=s=I I m a studentm a student的长度为的长度为的长度为的长度

83、为1313。 5.2 串的存储结构串的存储结构一、顺序存储一、顺序存储一、顺序存储一、顺序存储 和和和和线线线线性性性性表表表表一一一一样样样样，可可可可以以以以用用用用一一一一组组组组连连连连续续续续的的的的存存存存储储储储单单单单元元元元依依依依次次次次存存存存放放放放串串串串中中中中各各各各字字字字符符符符。利利利利用用用用字字字字符符符符单单单单元元元元地地地地址址址址的的的的顺顺顺顺序序序序表表表表示示示示串中字符的相邻关系。串中字符的相邻关系。串中字符的相邻关系。串中字符的相邻关系。struct stringstruct string char ch_stringmaxlen; c

84、har ch_stringmaxlen; int len ; int len ; ; ; 当当当当计计计计算算算算机机机机按按按按字字字字(Word)(Word)为为为为单单单单位位位位编编编编址址址址时时时时，一一一一个个个个存存存存储储储储单单单单元元元元由由由由若若若若干干干干字字字字节节节节组组组组成成成成。这这这这时时时时，顺顺顺顺序序序序存存存存储储储储结结结结构构构构有有有有紧紧紧紧凑凑凑凑格格格格式和非紧凑格式两种。式和非紧凑格式两种。式和非紧凑格式两种。式和非紧凑格式两种。5.3 串的基本运算串的基本运算 串串串串的的的的基基基基本本本本运运运运算算算算有有有有赋赋赋赋值值值

85、值、串串串串连连连连接接接接、求求求求串串串串长长长长、取取取取子子子子串串串串、子子子子串串串串定定定定位位位位、判判判判断断断断两两两两个个个个串串串串是是是是否否否否相相相相等等等等、插插插插入入入入子子子子串串串串，删删删删除除除除子子子子串串串串等等等等。在在在在本本本本节节节节中中中中，我我我我们们们们尽尽尽尽可可可可能能能能以以以以C C语语语语言言言言的的的的库库库库函函函函数数数数表表表表示示示示其其其其中中中中的的的的一一一一些些些些运运运运算算算算，若若若若没没没没有有有有库库库库函函函函数数数数，则则则则用用用用自自自自定定定定义义义义函函函函数数数数说说说说明。明。明

86、。明。struct stringstruct string char ch_stringmaxlen; char ch_stringmaxlen; int len ; int len ; ; ;1 1、串连接、串连接所谓串连接就是把一个串连接在另一个串的末尾，组成一个所谓串连接就是把一个串连接在另一个串的末尾，组成一个新串。新串。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

87、; 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_stringi; 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;

88、s.len=s1.len+s2.len; else else s.len=0; s.len=0; return (s); return (s); 2 2、串相等判断、串相等判断当两个串的长度相等且各对应位置上的字符都相等时，两个当两个串的长度相等且各对应位置上的字符都相等时，两个字符串才相等。字符串才相等。 int equal(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);

89、 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=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、插入子串、

90、插入子串所谓插入子串就是在指定位置上插入一个子串。所谓插入子串就是在指定位置上插入一个子串。struct string insert(s,s1,n)struct string insert(s,s1,n) struct string s,s1; int n; struct string s,s1; int n; struct 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

91、); 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 str.len=0; str.len=0; return (str); return (str); 5 5、子串定位、子串定位所谓子串定位就是给出子串在母串中的位置。子串的定位操所谓子串定位就是给出子串在母串中的位置。子串的定位操作也称模式匹配。作也称模式匹配。 int index

92、(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 ; j=i ; k=0 ; while (ks1.len)&(s.ch_sj=s1.ch_sk) while (k0)个结点的有穷集个结点的有穷集合合K，且在，且在K中定义了一个关系中定义了一个关系N，N满足以满足以下条件：下条件：(1) 有且仅有一个结点有且仅有一个结点K0它

93、对于关系它对于关系N来说来说没有前驱，称没有前驱，称K0为树的根结点；为树的根结点；(2) 除除K0外，外，K中的每一个结点对于关系中的每一个结点对于关系N来说有且仅有一个前驱；来说有且仅有一个前驱；(3)K中各结点对关系中各结点对关系N来说可以有来说可以有m个后继个后继7.2 树的常用术语树的常用术语n n树的结点：包含一个数据元素及若干指向树的结点：包含一个数据元素及若干指向其子树的分支其子树的分支n n结点的度：结点所拥有的子树的个数称为结点的度：结点所拥有的子树的个数称为该结点的度该结点的度n n叶子：度为零的结点，又称终端结点叶子：度为零的结点，又称终端结点n n树的深度：树中各结点

94、层次的最大值称为树的深度：树中各结点层次的最大值称为该树的深度该树的深度7.3 二叉树二叉树n n二叉数的定义二叉数的定义n n二叉数的存储结构：顺序存储结构、链式二叉数的存储结构：顺序存储结构、链式存储结构存储结构n n二叉数的遍历：就是按某一种规则访问树二叉数的遍历：就是按某一种规则访问树中的每一个结点，且使得每个结点均被访中的每一个结点，且使得每个结点均被访问一次，而且仅被访问一次。问一次，而且仅被访问一次。n n二叉数的遍历方法：前序遍历、中序遍历、二叉数的遍历方法：前序遍历、中序遍历、后序遍历后序遍历第九章第九章 查找查找n n查找查找查找查找(Searching)(Searchin

95、g)n n又称检索。就是从一个数据元素集合中找出某个又称检索。就是从一个数据元素集合中找出某个又称检索。就是从一个数据元素集合中找出某个又称检索。就是从一个数据元素集合中找出某个特定的数据元素；特定的数据元素；特定的数据元素；特定的数据元素；n n它是数据处理中经常使用的一种重要的操作，尤它是数据处理中经常使用的一种重要的操作，尤它是数据处理中经常使用的一种重要的操作，尤它是数据处理中经常使用的一种重要的操作，尤其是当所涉及的数据量较大时，查找算法的优劣其是当所涉及的数据量较大时，查找算法的优劣其是当所涉及的数据量较大时，查找算法的优劣其是当所涉及的数据量较大时，查找算法的优劣对整个软件的效率

96、影响很大；对整个软件的效率影响很大；对整个软件的效率影响很大；对整个软件的效率影响很大；n n本章首先介绍关于查找的基本概念，然后讨论查本章首先介绍关于查找的基本概念，然后讨论查本章首先介绍关于查找的基本概念，然后讨论查本章首先介绍关于查找的基本概念，然后讨论查找的各种方法，最后对各种查找方法作一比较。找的各种方法，最后对各种查找方法作一比较。找的各种方法，最后对各种查找方法作一比较。找的各种方法，最后对各种查找方法作一比较。9.1 查找的基本概念查找的基本概念n n查找表查找表查找表查找表(Search Table)(Search Table) 是由同一类型的数据元素是由同一类型的数据元素是

97、由同一类型的数据元素是由同一类型的数据元素( (或记录或记录或记录或记录) )构成的集合构成的集合构成的集合构成的集合n n对查找表进行的操作有以下四种对查找表进行的操作有以下四种对查找表进行的操作有以下四种对查找表进行的操作有以下四种(1)(1)查询某个特定的数据元素是否在查找表中查询某个特定的数据元素是否在查找表中查询某个特定的数据元素是否在查找表中查询某个特定的数据元素是否在查找表中(2)(2)检索某个特定的数据元素的各种属性检索某个特定的数据元素的各种属性检索某个特定的数据元素的各种属性检索某个特定的数据元素的各种属性(3)(3)在查找表中插入一个数据元素在查找表中插入一个数据元素在查

98、找表中插入一个数据元素在查找表中插入一个数据元素(4)(4)从查找表中删除某个数据元素从查找表中删除某个数据元素从查找表中删除某个数据元素从查找表中删除某个数据元素9.1 查找的基本概念查找的基本概念n n静态查找表静态查找表静态查找表静态查找表(Static Search Table)(Static Search Table) 若只对查找表进行查找和检索两种操作若只对查找表进行查找和检索两种操作若只对查找表进行查找和检索两种操作若只对查找表进行查找和检索两种操作, ,则称此则称此则称此则称此查找表为静态查找表查找表为静态查找表查找表为静态查找表查找表为静态查找表n n动态查找表动态查找表动态

99、查找表动态查找表(Dynamic Search table)(Dynamic Search table) 若再查找过程中同时插入查找表中不存在的记若再查找过程中同时插入查找表中不存在的记若再查找过程中同时插入查找表中不存在的记若再查找过程中同时插入查找表中不存在的记录录录录, ,或从查找表中删除已存在的某个记录或从查找表中删除已存在的某个记录或从查找表中删除已存在的某个记录或从查找表中删除已存在的某个记录, ,则称则称则称则称此类表为动态查找表此类表为动态查找表此类表为动态查找表此类表为动态查找表n n关键字关键字关键字关键字(Key)(Key) 标志数据元素标志数据元素标志数据元素标志数据元

100、素( (或记录或记录或记录或记录) )中某个数据项的值中某个数据项的值中某个数据项的值中某个数据项的值, ,用它用它用它用它可以标识一个数据元素可以标识一个数据元素可以标识一个数据元素可以标识一个数据元素( (或记录或记录或记录或记录) )9.2 线性表的查找线性表的查找n n顺序查找顺序查找顺序查找顺序查找(sequential Search)(sequential Search) 也称线性查找也称线性查找也称线性查找也称线性查找, ,是一种最简单的查找方法是一种最简单的查找方法是一种最简单的查找方法是一种最简单的查找方法, ,它属它属它属它属于静态查找于静态查找于静态查找于静态查找n n顺

101、序查找方法顺序查找方法顺序查找方法顺序查找方法顺序查找的基本思想顺序查找的基本思想顺序查找的基本思想顺序查找的基本思想: :从表的一端开始从表的一端开始从表的一端开始从表的一端开始, ,顺序扫顺序扫顺序扫顺序扫描线性表描线性表描线性表描线性表, ,依次用待查找的关键字值与线性表里依次用待查找的关键字值与线性表里依次用待查找的关键字值与线性表里依次用待查找的关键字值与线性表里各结点的关键字值逐个比较各结点的关键字值逐个比较各结点的关键字值逐个比较各结点的关键字值逐个比较, ,若在表中找到了某若在表中找到了某若在表中找到了某若在表中找到了某个记录的关键字与待查找的关键字值相等个记录的关键字与待查找

102、的关键字值相等个记录的关键字与待查找的关键字值相等个记录的关键字与待查找的关键字值相等, ,表明表明表明表明查找成功查找成功查找成功查找成功; ;如果找遍所有结点也没有与待查找的如果找遍所有结点也没有与待查找的如果找遍所有结点也没有与待查找的如果找遍所有结点也没有与待查找的关键字值相等关键字值相等关键字值相等关键字值相等, ,则表明查找失败则表明查找失败则表明查找失败则表明查找失败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;

103、 int i,key; int i,key; printf (Input the Key:); printf (Input the Key:); scanf (%d,&key); scanf (%d,&key); a0=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 S

104、uccess!n); printf (a%d=%dn,i,key); printf (a%d=%dn,i,key); 9.2 线性表的查找线性表的查找n n折半查找折半查找折半查找折半查找(binary Search)(binary Search) 也称为二分查找也称为二分查找也称为二分查找也称为二分查找, ,是一种效率较高的查找方法是一种效率较高的查找方法是一种效率较高的查找方法是一种效率较高的查找方法, ,查找时要求表中的结点按关键字的大小排序查找时要求表中的结点按关键字的大小排序查找时要求表中的结点按关键字的大小排序查找时要求表中的结点按关键字的大小排序n n折半查找方法折半查找方法折半

105、查找方法折半查找方法折半查找的基本思想折半查找的基本思想折半查找的基本思想折半查找的基本思想: :首先用要查找的关键字首先用要查找的关键字首先用要查找的关键字首先用要查找的关键字值与中间位置结点的关键字值相比较值与中间位置结点的关键字值相比较值与中间位置结点的关键字值相比较值与中间位置结点的关键字值相比较( (这个中间这个中间这个中间这个中间结点把线性表分成了两个子表结点把线性表分成了两个子表结点把线性表分成了两个子表结点把线性表分成了两个子表). ).比较结果相等比较结果相等比较结果相等比较结果相等, ,则查找成功则查找成功则查找成功则查找成功; ;若不相等若不相等若不相等若不相等, ,再根

106、据要查找的关键字再根据要查找的关键字再根据要查找的关键字再根据要查找的关键字值与该中间结点关键字值的大小确定下一步查值与该中间结点关键字值的大小确定下一步查值与该中间结点关键字值的大小确定下一步查值与该中间结点关键字值的大小确定下一步查找在哪个子表中进行找在哪个子表中进行找在哪个子表中进行找在哪个子表中进行#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,fla

107、g=0; int low=1,high=11,mid,key,flag=0; printf (Input the Key:); printf (Input the Key:); scanf (%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,k

108、ey); printf (a%d=%dn,mid,key); flag=1;break; flag=1;break; else else if (keyamid) high=mid-1; 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排序是在数据处理中经常使用的一种重排序是在数据处理中经常使用的一种重要的算法。如何进行排序，特别是高效要的算法。如何

109、进行排序，特别是高效率的排序是计算机应用中的重要课题。率的排序是计算机应用中的重要课题。n n排序的目的排序的目的：是方便查找：是方便查找n n排序分为排序分为：内部排序、外部排序内部排序、外部排序n n本章主要介绍几种常用的内部排序方法：本章主要介绍几种常用的内部排序方法：插入排序、选择排序、交换排序的基本插入排序、选择排序、交换排序的基本思想、排序步骤及实现方法思想、排序步骤及实现方法10.1 排序的基本概念排序的基本概念n n关键字关键字(Key) 标志数据元素标志数据元素(或记录或记录)中某个数据项的值中某个数据项的值,用它可以标识一个数据元素用它可以标识一个数据元素(或记录或记录)n

110、 n排序排序(Sorting) 是将一组记录按照记录中某个关键字进是将一组记录按照记录中某个关键字进行有序（递增或递减）排列过程行有序（递增或递减）排列过程10.2 内部排序内部排序n n插入排序插入排序插入排序就是按关键字大小将一个记录插入排序就是按关键字大小将一个记录插入到一个有序的文件中的适当位置，插入到一个有序的文件中的适当位置，并且插入后使文件仍然有序。并且插入后使文件仍然有序。n n直接插入排序直接插入排序每一趟将一个待排序的记录，按关键字每一趟将一个待排序的记录，按关键字的大小插入到已经排序的部分文件中适的大小插入到已经排序的部分文件中适当位置，直到全部插入完成当位置，直到全部插

111、入完成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=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折半插入排序折半插入排序由于插入排序的基本操作是在一个由于插入排序的基本操作是在一个有序表中进行查找和插入，而查找操有序表中进行查找和插入，而查找操作可利用折半查找来实现，由此进行作可利

112、用折半查找来实现，由此进行的插入排序称之为折半插入排列的插入排序称之为折半插入排列（Binary Insertion Sort），又称为），又称为二分法插入排序。二分法插入排序。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;hi

113、gh=i-1; while(low=high) while(low=high) m=(low+high)/2; m=(low+high)/2; if(a0am) high=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;ir2.key则交换则交换r1和和r2记录序列记录序列中的位置，否则不交换，然后再接着中的位置，否则不交换，然后再接着对当前序列中的第二个和第三个记录对当前序列中的第二个和第三个记录作同样的比较，依次类推，

114、直到序列作同样的比较，依次类推，直到序列中最后两个记录处理完为止。中最后两个记录处理完为止。main()main()main()main()inta100=0,5,7,3,8,2,9,1,4;inta100=0,5,7,3,8,2,9,1,4;inta100=0,5,7,3,8,2,9,1,4;inta100=0,5,7,3,8,2,9,1,4; inti,j,flag,temp;inti,j,flag,temp;inti,j,flag,temp;inti,j,flag,temp; flag=1;flag=1;flag=1;flag=1; for(i=1;i9&flag=1;i+)for(i=

115、1;i9&flag=1;i+)for(i=1;i9&flag=1;i+)for(i=1;i9&flag=1;i+) flag=0;flag=0;flag=0;flag=0; for(j=0;j9-i;j+)for(j=0;j9-i;j+)for(j=0;j9-i;j+)for(j=0;jaj+1)if(ajaj+1)if(ajaj+1)if(ajaj+1) flag=1;flag=1;flag=1;flag=1; temp=aj;aj=aj+1;temp=aj;aj=aj+1;temp=aj;aj=aj+1;temp=aj;aj=aj+1; aj+1=temp;aj+1=temp;aj+1=t

116、emp;aj+1=temp; for(i=1;i=8;i+)for(i=1;i=8;i+)for(i=1;i=8;i+)for(i=1;i=8;i+) printf(%d,ai);printf(%d,ai);printf(%d,ai);printf(%d,ai); printf(n);printf(n);printf(n);printf(n);10.2 内部排序内部排序n n快速排序快速排序快速排序快速排序快速排序是由冒泡排序改进而得的，是一种快速排序是由冒泡排序改进而得的，是一种快速排序是由冒泡排序改进而得的，是一种快速排序是由冒泡排序改进而得的，是一种分区交换排序方法分区交换排序方法分区交

117、换排序方法分区交换排序方法排序的基本思想排序的基本思想排序的基本思想排序的基本思想：一趟快速排序采用从两头：一趟快速排序采用从两头：一趟快速排序采用从两头：一趟快速排序采用从两头向中间扫描的办法，同时交换与基准记录逆序向中间扫描的办法，同时交换与基准记录逆序向中间扫描的办法，同时交换与基准记录逆序向中间扫描的办法，同时交换与基准记录逆序的记录。在待排序的的记录。在待排序的的记录。在待排序的的记录。在待排序的n n个记录中任取一个记录，个记录中任取一个记录，个记录中任取一个记录，个记录中任取一个记录，把该记录放入最终位置后，序列被这个记录分把该记录放入最终位置后，序列被这个记录分把该记录放入最终

118、位置后，序列被这个记录分把该记录放入最终位置后，序列被这个记录分割成两部分，所有关键字比该记录关键字小的割成两部分，所有关键字比该记录关键字小的割成两部分，所有关键字比该记录关键字小的割成两部分，所有关键字比该记录关键字小的放置在前一部分，所有比它大的放置在后一部放置在前一部分，所有比它大的放置在后一部放置在前一部分，所有比它大的放置在后一部放置在前一部分，所有比它大的放置在后一部分，并把该记录排在这两部分的中间。分，并把该记录排在这两部分的中间。分，并把该记录排在这两部分的中间。分，并把该记录排在这两部分的中间。voidq_sort(int*a,intleft,intright)voidq_

119、sort(int*a,intleft,intright)voidq_sort(int*a,intleft,intright)voidq_sort(int*a,intleft,intright)intpartition;/*intpartition;/*intpartition;/*intpartition;/*分割元素分割元素分割元素分割元素*/*/*/*/inttempinttempinttempinttemp, ,i,j,k;i,j,k;i,j,k;i,j,k;if(leftright)/*if(leftright)/*if(leftright)/*if(leftright)/*是否继续分

120、割是否继续分割是否继续分割是否继续分割*/*/*/*/ i=left;/*i=left;/*i=left;/*i=left;/*分割的最左分割的最左分割的最左分割的最左*/*/*/*/ j=right+1;/*j=right+1;/*j=right+1;/*j=right+1;/*分割的最右分割的最右分割的最右分割的最右*/*/*/*/ partition=aleft;/*partition=aleft;/*partition=aleft;/*partition=aleft;/*取第一个元素取第一个元素取第一个元素取第一个元素*/*/*/*/ dodododo do/*do/*do/*do/*

121、从左往右找从左往右找从左往右找从左往右找*/*/*/*/ i+;i+;i+;i+; while(aipartition);while(aipartition);while(aipartition);while(aipartition);while(ajpartition);while(ajpartition);while(ajpartition); if(ij)if(ij)if(ij)if(ij) temp=ai;ai=aj;aj=temp;temp=ai;ai=aj;aj=temp;temp=ai;ai=aj;aj=temp;temp=ai;ai=aj;aj=temp; /*/*/*/*交换

122、数据交换数据交换数据交换数据*/*/*/*/ while(ij);while(ij);while(ij);while(ij); temp=aleft;aleft=aj;aj=temp;/*temp=aleft;aleft=aj;aj=temp;/*temp=aleft;aleft=aj;aj=temp;/*temp=aleft;aleft=aj;aj=temp;/*交换数据交换数据交换数据交换数据*/*/*/*/ printf(printf(printf(printf(输出结果输出结果输出结果输出结果:);:);:);:); for(k=left;k=right;k+)/*for(k=left

123、;k=right;k+)/*for(k=left;k=right;k+)/*for(k=left;k=right;k+)/*输出处理数据输出处理数据输出处理数据输出处理数据*/*/*/*/ printf(%d,ak);printf(%d,ak);printf(%d,ak);printf(%d,ak); printf(n);/*printf(n);/*printf(n);/*printf(n);/*换行换行换行换行*/*/*/*/ q_sort(a,left,j-1);/*q_sort(a,left,j-1);/*q_sort(a,left,j-1);/*q_sort(a,left,j-1);/

124、*快速排序递归调用快速排序递归调用快速排序递归调用快速排序递归调用*/*/*/*/ q_sort(a,j+1,right);/*q_sort(a,j+1,right);/*q_sort(a,j+1,right);/*q_sort(a,j+1,right);/*快速排序递归调用快速排序递归调用快速排序递归调用快速排序递归调用*/*/*/*/ 10.2 内部排序内部排序n n选择排序选择排序n n直接选择排序的基本思想直接选择排序的基本思想：从待排序的：从待排序的所有记录中，选取关键字最小的记录并所有记录中，选取关键字最小的记录并将它与原始序列的第一个记录交换位置，将它与原始序列的第一个记录交换位

125、置，然后从去掉了关键字最小的记录的剩余然后从去掉了关键字最小的记录的剩余记录中选择关键字最小的记录与原始记记录中选择关键字最小的记录与原始记录中的第二个记录交换位置。录中的第二个记录交换位置。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,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!=

126、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快速排序快速排序快速排序快速排序快速排序是由冒泡排序改进而得的，是一种快速排序是由冒泡排序改进而得的，是一种快速排序是由冒泡排序改进而得的，是一种快速排序是由冒泡排序改进而得的，是一种分区交换排序方法分区交换排序方法分区交换排序方法分区交换排序方法排序的基本思想排序的基本思想排序的基本思想排序的基本思

127、想：一趟快速排序采用从两头：一趟快速排序采用从两头：一趟快速排序采用从两头：一趟快速排序采用从两头向中间扫描的办法，同时交换与基准记录逆序向中间扫描的办法，同时交换与基准记录逆序向中间扫描的办法，同时交换与基准记录逆序向中间扫描的办法，同时交换与基准记录逆序的记录。在待排序的的记录。在待排序的的记录。在待排序的的记录。在待排序的n n个记录中任取一个记录，个记录中任取一个记录，个记录中任取一个记录，个记录中任取一个记录，把该记录放入最终位置后，序列被这个记录分把该记录放入最终位置后，序列被这个记录分把该记录放入最终位置后，序列被这个记录分把该记录放入最终位置后，序列被这个记录分割成两部分，所有

128、关键字比该记录关键字小的割成两部分，所有关键字比该记录关键字小的割成两部分，所有关键字比该记录关键字小的割成两部分，所有关键字比该记录关键字小的放置在前一部分，所有比它大的放置在后一部放置在前一部分，所有比它大的放置在后一部放置在前一部分，所有比它大的放置在后一部放置在前一部分，所有比它大的放置在后一部分，并把该记录排在这两部分的中间。分，并把该记录排在这两部分的中间。分，并把该记录排在这两部分的中间。分，并把该记录排在这两部分的中间。10.2 内部排序内部排序n n快速排序快速排序快速排序快速排序快速排序是由冒泡排序改进而得的，是一种快速排序是由冒泡排序改进而得的，是一种快速排序是由冒泡排序

129、改进而得的，是一种快速排序是由冒泡排序改进而得的，是一种分区交换排序方法分区交换排序方法分区交换排序方法分区交换排序方法排序的基本思想排序的基本思想排序的基本思想排序的基本思想：一趟快速排序采用从两头：一趟快速排序采用从两头：一趟快速排序采用从两头：一趟快速排序采用从两头向中间扫描的办法，同时交换与基准记录逆序向中间扫描的办法，同时交换与基准记录逆序向中间扫描的办法，同时交换与基准记录逆序向中间扫描的办法，同时交换与基准记录逆序的记录。在待排序的的记录。在待排序的的记录。在待排序的的记录。在待排序的n n个记录中任取一个记录，个记录中任取一个记录，个记录中任取一个记录，个记录中任取一个记录，把

130、该记录放入最终位置后，序列被这个记录分把该记录放入最终位置后，序列被这个记录分把该记录放入最终位置后，序列被这个记录分把该记录放入最终位置后，序列被这个记录分割成两部分，所有关键字比该记录关键字小的割成两部分，所有关键字比该记录关键字小的割成两部分，所有关键字比该记录关键字小的割成两部分，所有关键字比该记录关键字小的放置在前一部分，所有比它大的放置在后一部放置在前一部分，所有比它大的放置在后一部放置在前一部分，所有比它大的放置在后一部放置在前一部分，所有比它大的放置在后一部分，并把该记录排在这两部分的中间。分，并把该记录排在这两部分的中间。分，并把该记录排在这两部分的中间。分，并把该记录排在这

131、两部分的中间。10.2 内部排序内部排序n n快速排序快速排序快速排序快速排序快速排序是由冒泡排序改进而得的，是一种快速排序是由冒泡排序改进而得的，是一种快速排序是由冒泡排序改进而得的，是一种快速排序是由冒泡排序改进而得的，是一种分区交换排序方法分区交换排序方法分区交换排序方法分区交换排序方法排序的基本思想排序的基本思想排序的基本思想排序的基本思想：一趟快速排序采用从两头：一趟快速排序采用从两头：一趟快速排序采用从两头：一趟快速排序采用从两头向中间扫描的办法，同时交换与基准记录逆序向中间扫描的办法，同时交换与基准记录逆序向中间扫描的办法，同时交换与基准记录逆序向中间扫描的办法，同时交换与基准记

132、录逆序的记录。在待排序的的记录。在待排序的的记录。在待排序的的记录。在待排序的n n个记录中任取一个记录，个记录中任取一个记录，个记录中任取一个记录，个记录中任取一个记录，把该记录放入最终位置后，序列被这个记录分把该记录放入最终位置后，序列被这个记录分把该记录放入最终位置后，序列被这个记录分把该记录放入最终位置后，序列被这个记录分割成两部分，所有关键字比该记录关键字小的割成两部分，所有关键字比该记录关键字小的割成两部分，所有关键字比该记录关键字小的割成两部分，所有关键字比该记录关键字小的放置在前一部分，所有比它大的放置在后一部放置在前一部分，所有比它大的放置在后一部放置在前一部分，所有比它大的放置在后一部放置在前一部分，所有比它大的放置在后一部分，并把该记录排在这两部分的中间。分，并把该记录排在这两部分的中间。分，并把该记录排在这两部分的中间。分，并把该记录排在这两部分的中间。