《数据结构(C语言描述)》教学课件汇总完整版电子教案全书整套课件幻灯片(最新)

1、21世纪高等院校规划教材数据结构（C语言描述）第一章 学习数据结构课程的意义学习重点掌握学习本课程的意义掌握本课程的主体框架和讨论范围掌握如何对算法进行描述和分析引入： 一般情况下，用计算机解决一个实际问题时，都是先对具体问题抽象，建立问题的求解模型，然后设计相应的算法，编写程序并上机调试，最后解决问题。 1.1 实例：高校选修课程管理1.2 数据结构的主要内容1.3 算法和算法分析本章总结1.1 实例：高校选修课程管理1.1.1 问题描述1.1.2 问题的分析1.1.3 学习本课程的意义1.1.1 问题描述 表1-1是一所学校学生选修课程的选修情况登记表。要求用计算机来完成对学生选修课程的全

2、程管理。 通常必备的功能有登记，修改、查询和打印等。在本例中重点完成查询功能。 学号姓名系别选修课程名学分成绩课程名课程代码等级分数0351103王杰计算机摄影技术50130351212李丽计算机电脑音乐50210351220商立计算机摄影技术50130432233赵燕机械三维动画30320432118张欣机械三维动画30320322140王芳材料证券投资2053表1-1 某学校学生选修课程情况登记表 1.1.2 问题的分析 利用计算机解决实际问题的步骤：第一步：从具体问题抽象出一个适当的数据模型。 第二步：进行算法设计。 第三步：实现抽象数据类型定义，即从编程语言的角度确定抽象数据类型的存储

3、形式和确定抽象数据类型中每一种操作的具体实现算法。 第四步：编制相应的程序代码并进行调试。 第一步：抽象数据模型一般包括三部分：处理的数据对象、对象间的关系和需要实现的操作。常用以下格式描述：ADT 选修课程 数据对象：D=ai | ai记录类型，i=1,2,n , n0 数据关系：R=Ri | Ri记录间关系，i=1,2,m , m0 基本操作： DengjiList ( &L) 完成功能：对学生选修情况进行登记 EditList(&L) 完成功能：对选修情况登记表进行修改 LocateList(&L,查询条件) 完成功能：根据给定的查询条件，从登记表中查找满足条件的记录 PrintList

4、(L) 完成功能：打印学生选修情况登记表 ADT选修课程第二步：根据上面给定的抽象数据类型定义，写出实现各种操作的算法描述。下面以查询操作为例给出伪代码表示：int LocateList( 选修课程 &L, 查询条件) 对给定的查询条件进行分析，确定是对表中哪个数据项进行查询； 对表中元素按给定的查询条件进行查询； 若查询成功，返回记录的位置；否则返回0值，表示表中不存在满足给定条件的记录；第三步：确定表中的记录的类型（结构体），表在内存中存储方式（按输入顺序存放）。具体定义如下：struct kechengsrtuct /选修课程名类型定义char *kechengming ; / 课程名i

5、nt kechengdaima ; / 课程代码 ;struct chengjistruct / 成绩类型定义char *dengji ; / 成绩等级int fenshu ; / 分数 ;struct student / 表中学生记录类型定义long int num ; / 学号char *name ; / 姓名char *xibie ; / 系别kechengstruct kechent ;int xuefen ; / 学分chengjistruct chengji ; ;表在内存中的存储类型定义：struct sqlist student *A ; / 将记录顺序存放在一个一维数组中in

6、t len ; / 表中记录的个数 ; 结论： 数据结构的实质就是一门研究非数值计算问题的程序设计中计算机的操作对象以及它们之间的关系和运算操作的一门学科。 1.1.3 学习本课程的意义 数据结构作为一门独立的课程在国外是从1968年开始设立的 。瑞士著名计算机科学家N.Wirth提出的著名公式“程序=算法+数据结构”。数据结构是一门介于数学、计算机硬件和软件三者之间的核心课程。 用一句话概括：本课程就是从实际问题抽象出数据类型的手段。主要研究计算机所处理的数据对象、对象间存在的关系及进行的各种操作。 1.2 数据结构的主要内容 1.2.1 基本概念和术语 1.2.2 数据结构定义 1.2.3

7、 逻辑结构的表示方法 1.2.1 基本概念和术语 数据是对客观事物的符号表示，是一种信息的载体，是所有能输入到计算机中并被识别、存储和加以处理的信息的总称。 数据元素是数据的基本单位。一个数据元素也可以由若干个数据项组成 。数据对象是性质相同的数据元素的集合，是数据的一个子集。 数据类型是对计算机中表示的数据对象、对象特征及该数据对象上的一组操作的描述。抽象数据类型是指一个数学模型及定义在该数学模型上的一组操作。定义取决于它的逻辑特性，与其在计算机内部如何表示（存储）和实现无关。 1.2.2 数据结构定义 数据结构是指相互间存在一种或多种特定关系的数据元素的集合。 数据具有相同属性的数据元素的

8、集合； 结构数据元素间存在的一种或多种关系。对一个给定的数据结构进行分析时，一般从它的逻辑结构、存储结构及对数据元素所进行的操作三个方面进行讨论。（本课程的主要讨论点） 逻辑结构是对给定数据结构的一种描述方式，是从实际问题抽象出来的数据模型。主要描述数据元素，及元素之间存在的逻辑关系。 通常按元素间存在的逻辑关系的不同特征，将数据结构分为四类： 集合结构 线性结构 树型结构 图型结构集合结构：数据元素之间除了同属于一个集合之外，没有其他关系的数据结构。例子：从大街上随意的找五个人组成一个小组，编号分别为1、2、3、4、5，则这五个人之间除了属于同一组以外，相互间不存在任何的关系。 组成集合的数

9、据元素之间不存在任何的关系线性结构：数据元素之间存在“一对一”线性关系的数据结构。学号姓名系别学分0351103王杰计算机30351212李丽计算机1例：学生基本情况登记表中每条学生记录都按一定的顺序排列，除了第一条和最后一条以外，每条记录都只有唯一的前驱和后继元素。元素之间是1：1关系，都只有唯一的前驱和唯一的后继树型结构：数据元素之间存在“一对多”逻辑关系的数据结构。例：一个大学的人事档案管理。每个系有多个专业，但一个专业只能属于一个系；一个专业有多名学生，但一个学生只能属于一个专业元素之间的关系是1：n，每个元素都只有唯一的前驱元素，但可以有多个后继元素图型结构：数据元素之间存在“多对多

10、”逻辑关系的数据结构。例：五个城市间的交通图。从1可以直达5，也可以经过2、3到达5，或也可以经过2、4到5。元素之间的关系是m:n，每个元素都可以有多个前驱元素和多个后继元素 存储结构又称物理结构，就是数据结构在计算机中的存储方式。它包括数据元素在计算机中的存储方式，还包括元素之间关系在内存中的表示。 根据存储空间的不同分配方式将数据结构分为两类： 顺序存储 链式存储第一方面第二方面 顺序存储：所有元素存放在一片连续的存储空间中，逻辑上相邻的元素在内存中的物理位置也是相邻的。 注意：元素存放在连续的存储空间中，元素之间的逻辑关系由在内存中的物理位置来体现。 例：对一个由（1，2，3，4，5）

11、五个元素组成的数据结构采用顺序存储，则内存中的存储示意图如下所示：元素1元素2元素3元素4元素5起始地址 链式存储：所有元素存放在可以不连续的存储单元中，以结点的形式存在，每个结点除了保存数据元素信息外，还通过指针来保存元素之间的关系。 注意：既元素存储在不连续的存储单元中，元素间的关系通过结点中的指针信息来体现。 元素1元素4元素3元素2例：对一个由（1，2，3，4）四个元素组成的数据结构采用链式存储，则内存中的存储示意图如下所示：1.2.3 逻辑结构的表示方法 二元组表示法表示形式为： D=（K，R）其中，K=a1 , a2 , , an ，为数据元素的集合 R=r1 , r2 , , r

12、 m ，为元素之间关系的集合 r1= | 其中，x,yK 序偶表示：元素x和元素y之间存在关系，并且称元素x为元素y的前驱，元素y为元素x的后继。如果元素x既是元素y的前驱，也是元素y的后继，既且，则用（x,y）形式表示。图形表示法 用圆圈来代表数据元素，用带箭头的连线来表示元素之间的关系，如图所示。二元组表示法：D1=( K , R ) 其中，K=a,b,c,d,e R=r r = , , , 1.3 算法和算法分析 1.3.1 算法定义 1.3.2 算法分析 1.3.1 算法定义 算法是对特定问题求解步骤的一种描述，是一组指令的有限序列，其中每一条指令都代表解题过程中的一个或者多个操作。算

13、法特点： 有穷性、确定性、可行性、输入、输出算法描述可以有多种方式，如：用流程图描述、用自然语言描述、还可用数学语言或特定的符号进行描述。本书中所有算法都是用C语言来进行描述 。1.3.2 算法分析 算法的设计要求如下： 正确性 可读性 健壮性 效率与低存储量的需求 其中，效率指的是算法执行的时间。存储量需求指的是算法执行过程中所需要的最大存储空间，通常主要考虑算法所需的辅助存储空间。 这四个设计要求中最主要的是算法的执行时间和执行时所占的存储空间大小。 算法的执行时间是指一个算法在计算机上运行时所花费的时间。 =简单操作所需要的时间简单操作的次数影响算法执行时间的两个因素： （1）每个简单操

14、作执行时所需时间与机器有关，而与算法无关。讨论算法中包含的简单操作的执行次数。 （2）另外一个与算法的执行时间相关的是问题的规模。 通常算法的执行时间用时间复杂度表示： T(n) = O( f ( n ) ) 其中，n为问题的规模 T（n）为时间复杂度 此式子表示，随着问题规模n的增大，算法执行时间的增长率和f(n)的增长率相同。所以只要求出简单操作的次数关于n的增长率即可，然后用n的最高数量级来表示算法的时间复杂度。 例： for (j=1;j=n;j+) for (k=1;k=m;k+) +x; s+=x; 分析：各个简单操作的执行次数如下所示：for (j=1;j=n;j+)/次数为1+

15、（n+1）+nfor (k=1;k=n;k+) /执行次数为（1+（n+1）+n）n +x; /执行次数为n*n s+=x; /执行次数为n*n 简单操作的执行次数之和为：4n2+4n+2，用n的最高数量级表示，时间复杂度为：O（n2）。衡量一个算法性能的另一个标准就是算法执行时所占的存储空间的大小。一般一个算法所占的存储空间包括存储算法所占用的存储空间、算法的输入/输出数据所占用的存储空间和程序运行过程中临时占用的存储空间这三个方面。其中，只有算法执行过程中所占的临时空间与算法有着密切关系。 通常一个算法在执行过程中所占用的临时存储空间的大小由空间复杂度来衡量，记作： S（n）= O（f（n

16、） 其中，n为问题的规模；S（n）为空间复杂度。通常用n的最高数量级来表示。 本章总结：本章介绍了学习数据结构课程的意义、本课程的主题框架及相关内容和如何对算法进行评价。 数据结构主要研究计算机所处理的数据对象、对象之间存在的各种关系及进行的各种操作，是用计算机来解决实际问题与编写相应程序两者之间的纽带。数据结构从定义上可以理解为数据+结构。其中，数据指的是所要处理的若干个数据元素的集合；结构指的是数据元素之间的关系。按逻辑结构可分为集合结构、线性结构、树型结构和图型结构四种。按存储结构可分为顺序存储和链式存储两种。 算法是解决问题步骤的一种描述，它有有穷性、确定性、可行性、输入和输出等五个特

17、点。 一个好的算法应该满足正确性、可读性、健壮性和效率与低存储量需求等四个要求，其中算法的执行效率和低存储量需求是衡量一个算法的最主要的标准。通常用时间复杂度来衡量算法的执行时间，用空间复杂度来衡量算法执行过程中所占用的临时存储空间的大小。它们都是问题的规模n的一个函数，所以用n的最高数量级来表示。 第5章 数组数组的基本概念和存储结构稀疏矩阵的定义、表示方法、存储结构及基本操作的实现算法特殊矩阵的存储广义表的定义、链式存储结构，以及相应操作的实现算法。 第5章 数组 5.1 数组 5.2 数学中的应用 5.3 广义表 本章总结5.1 数组 5.1.1 一维数组 5.1.2 多维数组 5.1.

18、1 一维数组 一维数组在数组结构中可以看成是一个线性表或一个向量，通常分配一块连续的存储单元。在C语言中，一维数组a n 的存储单元是从a 0 至an1的一块连续的存储空间，设a 0 的存储地址LOC（a 0 ），数据元素所占的存储单元为k个字节，则任一元素a i 的首字节地址LOC（a i ）： LOC（a i ）= LOC（a 0 ）+ i * k (0in) 5.1.2 多维数组 多维数组的定义：1 行向量形式Amn=A，则A = （a0，a1，ai，am1）一维数组其中，aj =（aj, 0，aj, 1，aj, n-1）（0jm）是一个行向量形式的线性表。就是以行序为主序的存储方式。

19、2 列向量形式Amn=A，则A = （a0，a1，ai，an1），其中，ap =（a0, p，a1, p，am-1, p）(0pn)是一个列向量形式的线性表，如式子（5-3）所示。是以列序为主序的存储结构。 数组的存储结构 对于二维数组来说，设数组的第一个元素a0, 0的地址LOC（a0, 0），每个元素所占的存储单元为k，则二维数组中任一元素ai，j的存储地址：LOC（ai , j）= LOC（a0 , 0）+（i * nj）* k n为列数 n维数组ad1d2 dn的数据元素存储位置的计算公式：5.2 数学中的应用 5.2.1 稀疏矩阵 5.2.2 特殊矩阵 5.2.1 稀疏矩阵 稀疏矩阵

20、的概念 稀疏矩阵的三元组线性表表示 稀疏矩阵的顺序存储方式 稀疏矩阵的链式存储方式 稀疏矩阵各种操作的实现 稀疏矩阵的概念： 在一个阶数较大的矩阵中非零元素个数s相对于矩阵元素的总个数t非常小，即 s sublist)+1 其它情况 实现算法： （略） 时间复杂度为O（n），其中n为广义表中所有结点的个数。该算法的空间复杂度为O（m），m为广义表的深度。建立广义表 分析：建立广义表过程可以通过递归实现。将广义表分解成表头和表尾，而表头和表尾若仍是广义表，则继续分解为表头和表尾。创建过程就是建立表头和建立表尾。 区分表头和表尾中的元素是单元素还是表元素的方法： （1）如果 i为“（）”，表示这是

21、一个空的表元素，字符串长度为2； （2）如果 i长度为1，表明它是一个单元素； （3）如果长度1，这是一个表元素。 前两种情况就可作为递归过程的结束条件。 实现算法： （略） 时间复杂度和空间复杂度：0（n），n广义表中字符个数输出广义表 分析：设GL为表头指针，则输出时，需要对子表进行递归调用。当GL结点为表结点时，应首先输出作为一个表的起始符号“（”。然后再输出以sublist为表头指针的表；当GL结点为原子结点时，则应输出该元素的值。当以sublist为表头指针的表输出结束后，应在其最后输出一个作为表终止符的“）”。当GL结点输出结束后，若存在后继结点，则应首先输出一个逗号作为分隔符，然

22、后再递归输出由next指针所指向的后继表。 实现算法： （略） 时间复杂度和空间复杂度：0（n），n广义表中结点个数。本章总结： 一维数组在内存中开辟一块连续的存储单元存储数据，适合于随机查找。多维数组可以看成是一维数组的推广，也是一个线性表，表中的每个数据元素本身也是一个线性表。 稀疏矩阵是指非零元素个数相对于矩阵元素的总个数十分小的矩阵。稀疏矩阵的存储方法有三种：第一种是三元组表示法，第二种是行逻辑链式存储，第三种是十字链式存储。稀疏矩阵的基本操作有五种，都采用了顺序存储方式。 特殊矩阵是指非零元素或零元素的分布有一定规律的矩阵。为了节省存储空间可以对特殊矩阵进行压缩存储。 广义表的元素分

23、为原子和子表，是一种递归结构。表中所含元素的个数称为长度。表中括号嵌套的最大次数称为深度。常用的基本操作有求广义表的长度、深度、创建和输出广义表等，操作的共同点是都通过递归实现。 第6章 树 学习重点：树和二叉树的概念、性质和相互间的转换方法树和二叉树的遍历方法和实现算法哈夫曼树、线索二叉树和二叉排序树的构造方法与应用 第6章 树 6.1 实例1：文件目录管理 6.2 树的逻辑结构6.3 树的遍历 6.4 实例2：通信中电文编码 6.5 二叉树定义、存储结构 6.6 二叉树遍历 6.7 树与二叉树的转换 6.8 应用举例 本章总结 6.1 实例1：文件目录管理 6.1.1 问题描述 6.1.2

24、 问题的分析 6.1.3 实现算法6.1.1 问题描述 在操作系统中对文件进行访问时提供按名存取机制，只需给出文件名，就可以访问到相应的文件，而无需知道文件的存储位置。 如何实现按名存取机制呢？ 6.1.2 问题的分析 文件系统将这些说明部分的全部信息集中起来构成文件控制块（FCB），文件目录由文件控制块组成。再将所有的文件目录组合在一起构成一个目录文件，目录文件以树型目录结构存储。树型目录结构中文件目录的第一级系统目录为树的根结点，定义为根目录，文件目录的第二级和以下各级目录均为树的分支结点（非终结点），均定义为子目录，只有树的叶子结点（终结点）才为文件。所以实现文件的按名存取，就是从目录结

25、构的根目录开始直到所要找的文件为止 。6.1.3 实现算法 实现算法：（略）结论： 文件目录结构是一种树型结构，目录树中的根目录是树的根结点，根目录下各级子目录和文件是树的其余结点。对处在同一层的各个子目录和文件进行比较可以发现各个子目录和文件都只有一个共同的上一级目录，而同一层的各个子目录可以有任意多个下级子目录和文件。 文件目录结构中的各个目录和文件都满足树型结构的特征。 6.2 树的逻辑结构6.2.1 树的逻辑结构 6.2.2 树的相关术语 6.2.1 树的逻辑结构 树或者是一棵空树，或者是一棵非空树。一棵非空树由n（n0）个结点来组成。它满足以下条件： l有且仅有一个根结点，它没有前驱

26、结点 l其余结点构成m(m=0)棵互不相交的树，称为该树的子树。每棵子树又是一棵树（递归定义）。 逻辑结构：一棵树由若干个结点组成，元素以结点的形式存在；关系：树的各个结点间是一对多的关系，即除根结点外，所有结点有且仅有一个前驱结点，所有结点或者没有后继结点，或者有任意多个后继结点。6.2.2 树的相关术语 根结点：唯一没有前驱的结点。所有非空树，都有唯一的一个根结点。 结点的度：结点所拥有的子树的个数，或者结点所拥有的后继结点的个数。树的度是指树中所有结点的度的最大值。 终端结点（叶子结点）：度为0的结点，或者树中没有后继的结点。 非终端结点（分支结点）：度不为0的结点，或者指有后继的结点。

27、 父结点、孩子结点：对一个结点来讲，它的前驱结点是它的父结点（双亲结点）；它的后继结点是它的孩子结点（子结点）。兄弟结点是指父结点相同的结点，即前驱结点是相同的结点。结点的深度是指该结点在树中所处的层数，根结点所在的层为第一层。树的深度是指树中结点的最大层次数。有序树是指构成树的各子树，从左到右有一定顺序，不能互相交换的树。无序树是指构成树的各子树是无顺序的，可以互相交换的树。森林是指若干棵互不相交的树。 6.3 树的遍历 6.3.1 先根遍历 6.3.2 后根遍历 6.3.3 按层遍历 树的遍历指的是按照某一种顺序访问树中的所有结点，并且每个结点只访问一次。 树的遍历顺序：先根遍历（先序遍历

28、）、后根遍历（后序遍历）和按层遍历。6.3.1 先根遍历先根遍历指如果树非空，则按下列规则进行遍历： l 先访问树的根结点。 l从左到右访问根结点的所有子树。 l对子树也按先根遍历顺序来访问所有的结点。 6.3.2 后根遍历后根遍历指如果树非空，则按下列规则进行遍历： l 先从左到右访问根结点的所有子树。 l 后访问树的根结点。 l 对子树也按后根遍历顺序来访问所有的结点。 6.3.3 按层遍历按层遍历指如果树非空，则按下列规则进行遍历： l 从第一层开始，从上到下顺序遍历各层，同一层从左到右访问各个结点。 l 树的根结点所在层定义为第一层，依次类推。 6.4 实例2：通信中电文编码 6.4.

29、1 问题的描述 6.4.2 问题的分析 6.4.3 实现算法 6.4.1 问题的描述 在电信科技日新月异的今天，人们早已淡忘了，曾经风靡一时的电报。电报的原文发送时，都按一定的规则翻译成编码，以编码的形式传送。收到的电文中，每个文字的下面都会有一个数字编码。下面介绍的也是一种电报的编码方法：发送的电文翻译成0和1的数字序列。 6.4.2 问题的分析 电报主要依靠将传送的文字转换成由二进制数组成的字符串进行传送。第一种解决方法：将所有传送的文字都转换成等长的二进制字符串来传送，接收者只需按等长进行译码。第二种解决方法：对电文中出现的字符设计长度不等的字符编码，对电文中出现次数比较多的字符采用尽可

30、能短的字符编码，则传送的信息的长度就可以减少了。 前缀编码（哈夫曼编码）：每个字符的编码都不是另一个字符的编码的前缀。 构造字符哈夫曼编码的方法： 将每个字符按在代码中出现的次数为出现频率，构成一个频率集合，然后画一棵满足以下条件的树： l从频率集合中，每次选择出现频率最小的两个字符构成一棵树，所构成树的父结点的值等于这两个字符的频率之和。 l将选中的两个字符的频率从频率集中删除，并将它们的父结点加到频率集合中。 重复上述两个过程，直到频率集合中只剩一个元素为止。 编码规则：从树的根结点起，左边的孩子结点的编号为0，右边的孩子结点的编号为1，对所有的子树也按这个规则编码。所画的树称之为哈夫曼树

31、，频率称之为权值。 6.4.3 实现算法 实现算法：（略）结论：哈夫曼树的每个结点最多有两个孩子结点，结点度的最大值为2，这种树称为二叉树，两个孩子结点分别称为左孩子结点和右孩子结点。6.5 二叉树定义、存储结构 6.5.1 二叉树的定义6.5.2 二叉树的性质 6.5.3 二叉树的存储结构 6.5.1 二叉树的定义 二叉树定义（递归定义）： 或者是一棵空二叉树，或者是一棵非空二叉树。一棵非空二叉树由n（n0）个结点组成。它满足以下条件： l有且仅有一个根结点，它没有前驱结点 l其余结点构成两棵互不相交的子树，称为该树的左子树和右子树。每棵子树又是一棵二叉树。 特点：每个结点最多只能有两个孩子

32、结点，也就是说二叉树中不存在度大于2的结点。 Root (BT) 求根结点。ParentBT(BT,elem) 求父结点。LchildBT(BT,elem)和RchildBT(BT,elem)求左、右孩子结点。CreateBT(BT,R,n)创建一棵二叉树。DepthBT(BT)求层数。PreOrdetBT(BT)先根遍历。InOrdetBT(BT)中根遍历。PostOrdetBT(BT)后根遍历。 LeverOrdetBT(BT)按层遍历。二叉树的基本操作：6.5.2 二叉树的性质 性质1：如果计二叉树的根结点所在层为第一层，则第k层的结点数最多为2 k-1个。 性质2：层数为k的二叉树的最

33、大结点数为2 k-1个。 性质3：在一个二叉树中，度为0的结点的个数为n0，度为2的结点的个数为n2，则n0=n2+1。性质4：具有n个结点的完全二叉树的层数为： 或 。 满二叉树是指层数为k的有2 k-1个结点的二叉树，既每层都保持它的最大结点数，每层结点都是满的。 完全二叉树是指如果一棵层数为k的n个结点的二叉树的所有结点都与层数为k的满二叉树中编号为1 n的结点一一对应，则称此二叉树为完全二叉树。 性质5：对一棵有n个结点的完全二叉树来讲，编号为i的结点满足以下条件：（1）如果i=1，则结点i是根结点，无父结点；如果i1，则父结点的编号是 。（2）如果2in，则结点i没有左孩子结点的叶子

34、结点；否则其左孩子结点的编号是2i。（3）如果2i+1n，则结点 i没有右孩子结点；否则其右孩子结点的编号是2i+1 。 6.5.3 二叉树的存储结构 存在两种存储方式： 顺序存储方式 链式存储方式 用一组连续的存储空间来存放一棵二叉树的所有结点。结点存放时对二叉树中的所有结点都按满二叉树中结点编号来顺序编号，将编号当成存储结点的数组元素的下标来处理。顺序存储方式： 指存储二叉树中的全部结点信息及结点间的关系。结点间的关系通常有两种：一种是左右孩子结点的关系，另一种是父结点的关系。 二叉链表存储方式：每个结点除了存储结点元素的信息外，还存储该结点的左、右孩子结点的信息。（常用存储方式） 三叉链

35、表存储方式：在二叉链表的基础上，在结点中再增加一个存放该结点的父结点信息的指针域。链式存储方式：typedef struct Btnode Elemtype data ; / 存储二叉树结点元素的信息 Btnode *lchild ; / 存储该结点的左孩子结点的信息 Btnode *rchild ; / 存储该结点的右孩子结点的信息 BtTree ;二叉链表存储的结点类型定义：6.6 二叉树遍历 6.6.1 先根遍历 6.6.2 中根遍历 6.6.3 后根遍历 6.6.4 按层遍历 6.6.5 二叉树遍历的应用 一棵二叉树是由根结点、左子树和右子树组成，争别用D、L和R表示，并要求左子树在右

36、子树前遍历，则可得到DLR（先根遍历）、LDR（中根遍历）和LRD（后根遍历）三种。除了这三种外，还可按结点所在层数进行遍历，称按层遍历。 6.6.1 先根遍历 先根遍历（先序遍历）定义： 若二叉树为非空树，则 l访问二叉树的根结点 l先根遍历左子树 l先根遍历右子树 分析：先根遍历是一个递归过程，先遍历根结点，后先根遍历左、右子树。对左、右子树也是按先根遍历。 先根遍历的递归算法为：（二叉链表形式存储） void PreOrdetBT( BtTree *BT ) if ( BT ) printf( “输出格式串”，BT-data ) ; PreOrdetBT( BT-lchild ) ; P

37、reOrdetBT( BT-rchild ) ; 先根遍历的递归算法 分析：二叉树的先根遍历从根结点开始，沿左子树一直到左孩子为空为止。在整个过程中，访问所遇到的结点，然后沿线往回返，每返回一个结点都去遍历该结点的右子树，直到遍历完右子树为止。在沿左子树遍历过程中，若左子树为空，都要往上一个访问结点返回（退栈）。所以需要存储（进栈）遍历过程中每个访问到的结点（定义一个栈）。重复此过程，直到栈为空或指向结点的指针为空时停止。 先根遍历的非递归算法为： （略）先根遍历的非递归算法6.6.2 中根遍历 中根遍历（中序遍历）的定义：若二叉树为非空树，则 l中根遍历左子树 l访问二叉树的根结点 l中根遍

38、历右子树中根遍历的递归算法 分析：中根遍历是一个递归过程，先中根遍历左子树，然后访问根结点，最后中根遍历右子树。对左、右子树也按中根遍。 中根遍历的递归算法：（二叉链表形式存储） void InOrdetBT( BtTree *BT ) if ( BT ) PreOrdetBT( BT-lchild ) ; printf( “输出格式串”，BT-data )； PreOrdetBT( BT-rchild ) ; 中根遍历的非递归算法 分析：中根遍历是一个从二叉树的根结点开始，沿左子树一直到左孩子为空时，沿线往回返，每返回一个结点都先访问该结点，然后去遍历该结点的右子树。在沿左子树遍历的过程中，

39、若左子树为空，都要往上一个访问结点返回，所以需要存储遍历过程中遇到的每个结点（设定一个栈）。沿左子树遍历时每遇到一个结点，就将该结点进栈，当左子树为空时，从栈顶退栈一个结点，先访问该结点，然后去访问该结点的右孩子结点。重复此过程，直到栈为空或指向结点的指针为空时停止。 中根遍历的非递归算法：（略） 6.6.3 后根遍历 后根遍历（后序遍历 ）的定义：若二叉树为非空树，则 l 后根遍历左子树 l后根遍历右子树 l访问二叉树的根结点后根遍历的递归算法 分析：后根遍历过程是一个递归过程，先后根遍历左、右子树，后遍历根结点。对左、右子树也是先后根遍历其左、右分支，后遍历根结点。 后根遍历的递归算法：（

40、二叉链表形式存储） void PostOrdetBT( BtTree *BT ) if ( BT ) PreOrdetBT( BT-lchild ) ; PreOrdetBT( BT-rchild ) ; printf( “输出格式串”，BT-data ) ; 后根遍历的非递归算法 分析：后根遍历过程从二叉树的根结点开始，沿左子树一直到左孩子为空停止，左孩子为空时，沿线往回返，每返回一个结点都先去遍历该结点的右子树，最后才访问该结点。所以每个结点第一次出栈时，刚遍历完该结点的左子树，还需要将结点再次压入栈中，等再次弹出时，已遍历完该结点的右子树，这时才可以访问该结点。为了区分同一结点的两次进栈

41、，可以引入一个标志栈，当从存放结点的栈中出栈一个结点时，从标志栈也要出栈一个元素，根据此元素的值来确定该结点是再次进栈，还是访问该结点。 后根遍历的非递归算法：（略） 6.6.4 按层遍历 按层遍历的定义：若二叉树为非空树，则 l先访问根结点 l按从左到右的顺序遍历根结点的左、右孩子结点l 依次类推，由层数的从低到高，同层从左到右的顺序遍历所有结点 注意：二叉树中定义根结点的层数为第一层 按层遍历的非递归算法 分析：实现按层遍历时就可以定义一个队列来存放结点。整个按层遍历的过程就从根结点开始，访问完一个结点就让该结点进队，然后从队列中出队一个结点，去访问该结点的左、右孩子结点，每访问一个结点就

42、让该结点进队。直到队列为空时停止。二叉树以二叉链表形式存储 。 按层遍历的非递归算法：（略） 6.6.5 二叉树遍历的应用 例1：写出图6-9中给出的二叉树的先根、中根、后根和按层遍历的结点序列。解： 先根遍历：ABDEKCFG中根遍历：DBEKAFCG后根遍历：DKEBFGCA按层遍历：ABCDEFGK 已知：给定的先根遍历结点序列为：ABDGHCEIJF，中根遍历结点序列为：GDHBAEIJCF。 分析：对一棵二叉树先根遍历时，第一个访问到的结点肯定是二叉树的根结点，所以从先根遍历的结点序列中可得知，二叉树的根结点为A。中根遍历先遍历左子树，然后遍历根结点，最后遍历右子树，所以在结点序列中

43、确定根结点后，根结点前面的结点序列肯定是左子树中结点的中根遍历后的结果，而后面的是右子树的中根遍历后的所得结果。即可将二叉树分成左子树、根和右子树三部分，依次类推。 解题过程：（略） 例2：根据给定的遍历序列，画出相应的二叉树。6.7 树与二叉树的转换 6.7.1 树的存储结构 6.7.2 树与二叉树的转换 6.7.3 森林与二叉树的转换 6.7.1 树的存储结构 双亲表示法 孩子表示法 孩子双亲表示法 孩子兄弟表示法 双亲表示法： 实现：开辟一段连续的存储单元来存放结点信息及该结点的双亲结点信息。通常定义一个一维数组存放结点的元素信息及双亲结点的信息。（顺序存储）双亲表示法的存储类型定义为：

44、const int maxsize = 常数 ;struct node Elemtype data ; /存放树中结点元素信息int parent ; /存放双亲结点在数组t中的下标 ; node t maxsize ; /存储结点及双亲信息 孩子表示法： 实现：将每个结点的所有孩子结点链接成一个单链表，并将所有的单链表的表头结点存放在一个一维数组。孩子表示法的存储类型定义为：const maxsize = 常数 ; / 存储空间的大小struct Link int child ; / 存放孩子结点在数组中的下标 Link *next ; / 指向该结点的下一个孩子结点的指针 ; / 单链表的

45、结点类型定义 struct node Elemtype data ; / 存储树中结点元素的信息 Link*next ; /指向该结点所有子结点组成的单链表的第一个结点 ; / 数组元素的类型定义node t maxsize ; / 用数组来存储树中结点的相关信息 孩子双亲表示法 ：实现：将孩子表示法和双亲表示法结合在一起就是孩子双亲表示法。孩子双亲表示法存储类型定义：（略）孩子兄弟表示法： 实现：在孩子兄弟表示法中每个结点由三个域组成，除了存放结点信息的值域外，另外两个指针域分别指向该结点的第一个孩子结点和与该结点相邻的兄弟结点，是一种链式存储方式。孩子兄弟表示法存储类型定义：（略）6.7.

46、2 树与二叉树的转换 将树转换为二叉树的方法： l连线：将每个结点跟与它相邻的右边的兄弟结点用线连起来。 l 抹线：对所有结点，除了该结点的最左边的孩子结点外，将该结点与其它孩子结点之间的连线全部删除。 l 旋转：将树以根结点为重心，顺时针方向旋转大概45。角，把树中的水平连线变成右分支，原有连线变成左分支。 将二叉树还原为树的方法： l 加线：对二叉树中所有具有双亲结点的左孩子的右孩子，及右孩子的右孩子都与双亲结点连起来。 l 抹线：抹掉二叉树中所有双亲结点与右孩子间的连线。 l 调整：以二叉树的根结点作为树的根结点，将其余结点的位置进行调整。 结论： 1 树转换成的二叉树是一棵右子树为空的

47、二叉树。 2 二叉树中每个结点的左孩子结点在原树中是它的最左孩子结点，而右孩子结点是它的兄弟结点。 3 树的孩子兄弟表示法其实就是将树转换成二叉树的方法。 6.7.3 森林与二叉树的转换 森林转换成二叉树的方法： l 转换：将组成森林的所有树转换成一棵棵二叉树。 l 连线：将转换成的所有二叉树的根结点连起来。 l 旋转：以第一棵树的根结点为中心，按顺时针方向旋转所添加的所有的水平线和原有连线。 二叉树转换成森林的方法： l 抹线：抹掉二叉树中根结点右链上的所有结点的连线，将二叉树分成若干棵以右链上的结点为根结点的二叉树。 l转换：将分成的二叉树转换成树。 l 调整：以树的根结点为准，排列成一排

48、。 6.8 应用举例 6.8.1 线索二叉树 6.8.2 二叉排序树 6.8.3 哈夫曼树 6.8.4 二叉树的综合实例 6.8.1 线索二叉树 线索二叉树定义: 如果对一棵二叉树用指针指出按某种方式遍历时的结点的前驱和后继信息，则称指针为线索，而给出线索的二叉树就称为线索二叉树，画出线索的过程称为线索化。 线索化二叉树(二叉链表的形式存储)： 结点结构如下所示：lchildltagdatartagrchild6.8.2 二叉排序树 二叉排序树的定义（递归定义 ） 或者是一棵空二叉树，或者是一棵满足以下条件的二叉树： l左子树中所有结点的值都小于根结点的值 l右子树中所有结点的值都大于等于根结

49、点的值 l左、右子树本身也是一棵二叉排序树 结论：中根遍历后的结点序列是一个有序序列。如果用待排序数据构造一棵二叉排序树，并对它进行中根遍历，则达到排序目的。 二叉排序树是一种排序方法。 构造二叉排序树 构造过程：从空树逐步插入各个结点的过程。每插入一个结点时，插入位置的确定都从根结点开始，根据二叉排序树的定义，小于根结点的插入位置应在左子树中，否则，插入位置应在右子树中。一直进行比较，直到找到一个合适的插入位置，将结点插入成为一个叶子结点为止。二叉排序树的插入算法 ：（略）6.8.3 哈夫曼树 哈夫曼树的相关概念 路径：连接两个结点的分支 路径长度：两个结点间路径上的分支个数。 树的路径长度

50、：从根结点到其余各结点间路径之和。 结点的权：树中结点所赋的数值。 结点的带权路径长度：从根结点到该结点的路径长度和该结点的权植的乘积。 树的带权路径长度是指树中所有叶子结点的带权路径长度之和。通常记作： 其中，wi代表第i个结点的权值；li代表第i个结点的路径长度；n为树中叶子结点的个数 哈夫曼树（最优二叉树）是指带权路径长度最小的二叉树。哈夫曼树的构造方法： l根据给定的n个权值（w1,w2,wn），构成n棵二叉树的集合。其中，每棵二叉树都只有一个权值为wi的根结点，没有左、右子树。 l从二叉树的集合中，选择权值最小的两棵树作为左右子树，构成一棵新的二叉树，新二叉树的根结点的值为左右孩子结

51、点的权值之和。 l从二叉树集合中，删除刚选取的两棵树，同时将新得到的二叉树添加到二叉树集合中。 重复上述过程，直到二叉树集合中只有一棵二叉树为止，该树既为哈夫曼树。 6.8.4 二叉树的综合实例 问题的描述： 创建一棵二叉树，给出此二叉树按四种遍历方式遍历后的结点序列、计算此二叉树的层数。问题的分析： 设二叉链表形式存储，结点值用单个字符表示。 创建：按先序遍历的顺序建立二叉链表。先建立根结点，然后依次建立根的左、右子树。在建立过程中，将二叉树当成完全二叉树，二叉树中与完全二叉树对应的结点输入结点元素的值；没有对应的结点时，输入#来代替，直到二叉树的全部结点输入完毕为止。二叉树的遍历过程是一个

52、递归过程，所以建立算法也可以写成一个递归算法。遍历：可以直接调用6.6二叉树遍历中给定的算法。求深度：二叉树的深度为树中结点层次的最大值，所以从上一层的根结点开始往下递推可得到树的层数。在整个过程中也需要确定一个遍历方式，本例中使用后序遍历来实现。实现算法 ： （略）本章总结 本章介绍了树和二叉树的逻辑结构、存储结构、各种基本操作的实现及应用。 树是若干个结点的有限集合。主要特征是只有一个没有前驱的结点为根结点，其余结点都只有一个前驱，所有结点可以有任意多个后继，是一对多的关系。 树有四种存储方式：双亲表示法、孩子表示法、孩子双亲表示法和孩子兄弟表示法。树的主要操作是树的遍历。遍历是指访问树中

53、所有结点，并且每个结点只能访问一次。树有三种遍历方法：先根遍历、后根遍历和按层遍历。 森林是若干棵树的集合，有先根遍历和后根遍历两种遍历方式。 二叉树主要特征是只有一个没有前驱的根结点，其余结点都只有一个前驱，所有结点最多有两个后继结点，分别为该结点的左孩子结点和右孩子结点。 二叉树的存储方式：顺序存储，链式存储（二叉链表）。顺序存储适合存储完全二叉树，普通二叉树适合用链式存储方式。 二叉树有四种遍历方式：先根遍历、中根遍历、后根遍历和按层遍历。 树、森林和二叉树之间可以进行转换，转换的主要依据就是树的孩子兄弟表示法，组成森林的所有树的根结点之间是兄弟关系。 树、森林与二叉树进行转换结论：树的

54、先根遍历和后根遍历的结点序列就是该树转换成二叉树后的先根和中根遍历的结点序列；森林的先根遍历和后根遍历的结点序列就是该森林转换成二叉树后的先根和中根遍历的结点序列。 二叉树的主要应用：线索二叉树、二叉排序树和哈夫曼树等。第7章 图 学习重点：掌握图的基本概念、逻辑特征和图的存储结构。掌握图的深度优先搜索遍历和广度优先搜索遍历的思想、遍历过程及邻接矩阵和邻接表上的实现算法。 掌握图的最小生成树的概念和求图的最小生成树的克鲁斯卡尔算法和普里姆算法的思想、求解过程和画出对应的最小生成树并求出最小生成树的权。掌握求有向图最短路径和拓扑序列的思想和求解过程。 第7章 图 7.1 实例：求城市间最短路径

55、7.2 图的逻辑结构、特征 7.3 图的存储结构 7.4 图的遍历 7.5 最小生成树 7.6 应用举例 本章总结7.1 实例：求城市间最短路径 7.1.1 问题描述 假设乘飞机旅行，想选择一条所要参观的两个城市间距离最短的路线。 7.1.2 问题的分析 如果以点代表城市，以线代表两个城市之间的距离，并在线上标出具体的距离值，可画出相应的图。通常将解决这种问题中的出发点称之为源点，则求最短路径就变成一个求从源点到终点的最短路径的问题。解决此问题时需要求出源点到其余各顶点间的最短路径才能得到最终的答案。 第一步：先求从源点出发的各个路径中的最短路径。有两种情况：第一种直接有线相连，比较路径值的大

56、小；另一种没有直接连线，表示这两个城市间不直接通。第二步：在上一结果的基础上求从源点出发的各个路径中的最短路径。到达各个城市的路径存在二种可能性：第一种是途径刚选择的城市仍没有通路；第二种是途径刚选择的城市后，到达该城市的路径又多出一种选择，此时选择短的路径。第三步：重复第二步，每选中一个城市，都要修改一下到其余各城市间的最短路径，直到求出源点到其余各城市间的最短路径为止。 求解过程大体如下： 从画出的图可知，此图是一种图型结构，图中每个圆圈就是图型结构中的一个顶点，连线称之为边，所以图是由若干个顶点的集合和边的集合组成的。 上面的例子就是图的日常生活中的一种应用：求从源点到其余各顶点间的最短

57、距离。 结论：7.2 图的逻辑结构、特征 7.2.1 图的逻辑结构 7.2.2 图的特征 图是一种复杂的非线性数据结构。在图形结构中，结点之间的关系是任意的，即图中的每个结点都可以有任意多个前驱结点和任意多个后继结点，是多对多的关系。 7.2.1 图的逻辑结构 图的定义： 图（Graph）由两个集合V和E组成，它的二元组定义可以表示成： Graph=（V，E） 其中， V是顶点的有穷非空集合，即V=vi | n1，viVertexType，VertexType为顶点值的类型，它可以代表任何类型，n为顶点数； E是V上顶点间二元关系的有穷集合，称这种关系为边。 用V（G）表示图的顶点集合；E（G

58、）来表示图G的边集合，E（G）可以为空集。当E（G）为空集时，图G称为空图。 无向图：在图G中，如果代表边的顶点序偶关系都是对称的，即和同时成立，则以无序对（vi，vj）替代这两个有序对。 有向图：图G中边的顶点是有序的。在有向图中边表示从顶点vi到顶点vj的一条有向边（弧），顶点vi称为有向边的尾（或始点），顶点vj称为有向边的头（或终点），用由起点指向终点的箭头表示有向边。 7.2.2 图的特征 端点和邻接点 在一个无向图中，若存在一条边（vi，vj），则称vi，vj为此边的两个端点，并称它们互为邻接点。在一个有向图中，若存在一条边，则称此边为顶点vi的一条出边，顶点vj的一条入边（ine

59、dge）；称vj是vi的出边邻接点，vi是vj的入边邻接点。顶点的度、入度、出度 在无向图中，顶点v所具有的边的数目称为该顶点的度。有向图中顶点v的度又分为入度（以顶点v为终点的入边的数目）和出度（以顶点v为始点的出边的数目）。一个顶点的入度与出度的和为该顶点的度。完全图、稠密图、稀疏图 若无向图中的每两个顶点之间都存在着一条边，有向图中的每两个顶点之间都存在着方向相反的两条边，则称此图为完全图。当一个图接近完全图时，则称它为稠密图。相反，当一个图含有较少的边数时，则称为稀疏图。子图 设有两个图G=（V，E）和G=(V，E)，若V是V的子集，即VV，且E是E的子集，即EE，则称G是G的子图。

60、路径和路径长度路径（path）是一个顶点序列。路径长度是指该路径上经过的边的数目。若一条路径上除了开始点和结束点可以相同外，其余顶点均不相同，则称此路径为简单路径。回路或环若一条路径上的开始点与结束点为同一个顶点，则此路径被称为回路或环（cycle）。开始点与结束点相同的简单路径被称为简单回路或简单环。连通、连通图和连通分量 在无向图G中，若从顶点vi 到顶点vj有路径，则称vi和vj是连通的。若图G中任意两个顶点都连通，则称G为连通图，否则称为非连通图。无向图G中极大连通子图称为G的连通分量。强连通图和强连通分量 在有向图G中，若从顶点vi 到顶点vj有路径，则称vi和vj是连通的。若任意两