《数据结构（C语言版）》教案.doc

数据构造C语言版教案2022 至20_ 学年第 一 学期 教案 课程名称数据构造使用教材数据构造C语言版教学时数56课程性质必修任课班级人数信管53人信息系部 信管教研室 任课老师 山东科技大学泰山科技学院 课 时 授 课 计 划 2022-20_学年第 二学期第1周 授 课 日 期 2月 20 日 星期1 月 日 星期 月 日 星期 月 日 星期 月 日 星期 班 级 信管10-1 根本课题 第1章 绪论 1.1-1.2 教学目的与要求：1.理解数据构造的根本概念 2.理解常用术语 教学重点：数据构造的根本概念和术语 教学难点：数据元素之间的四种构造关系 作业及参考书：1、 什么是数据构造？ 数据构造算法实现及解析/高一凡 编著 教具：多媒体 板书 课堂类型：讲授 教学过程：自我介绍开课引入展开举例小结作业 一、自我介绍和课程介绍 约8min 课时：64 二、引入 约2min 由问题的提出引入 三、讲课进程设计 1.1 什么是数据构造 1.1.1、数据构造与其它的关系 约15min 数据构造 +算法 =程序 程序设计: 为计算机处理问题编制一组指令集 算法: 处理问题的策略 数据构造: 问题的数学模型 1.1.2、当今计算机应用的特点：约25min l) 所处理的数据量大且具有一定的关系；2) 对其操作不再是单纯的数值计算，而更多地是需要对其进展组织、管理和检索。举例说明：1) 学生成绩表 2)井安棋对弈 3)交通管理 结论 计算机的操作对象的关系更加复杂，操作形式不再是单纯的数值计算，而更多地是对这些具有一定关系的数据进展组织管理；我们将此称为非数值性处理。要使计算机可以更有效地进展这些非数值性处理，就必须弄清楚这些操作对象的特点，在计算机中的表示方式以及各个操作的详细实现手段。1.2 根本概念和术语 1.1.1、数据与数据构造 约20min 数据：是对客观事物的符号表示。所有能被输入到计算机中，且能被计算机处理的符号的集合。是计算机操作的对象的总称。是计算机处理的信息的某种特定的符号表示形式。数据元素：是数据集合中的一个“个体”，是数据构造中讨论的根本单位。数据对象：是性质一样的数据元素的集合，是数据的一个子集。数据构造：是互相之间存在一种或多种特定关系的数据元素的集合。这种集合称为构造。数据的逻辑构造可归结为以下四类:  种类 特征 例如 集合 元素间为松散的关系   线性构造 元素间为严格的一对一关系 如上面的成绩表中各元素 树形构造 元素间为严格的一对多关系 图状构造或网状构造元素间为多对多关系 数据构造的形式定义为:数据构造是一个二元组 数据的存储构造 ： 逻辑构造在存储器中的映像 数据元素的映象方法：计算机中存储信息的最小单位：位，8位为一字节，两个字节为一字，字节、字或更多的二进制位可称为位串。在逻辑描绘中，把位串称为元素或结点。关系的映象方法：顺序映象 链式映象 1.2.2、数据类型 约5min 数据类型 是一个 值的集合和定义在此集合上的 一组操作的总称。1.2.3、抽象数据类型 约20min 是指一个数学模型以及定义在此数学模型上的一组操作。关键：使用它的人可以只关心它的逻辑特征，不需要理解它的存储方式。定义它的人同样不必要关心它如何存储。抽象数据类型表示法：三元组表示：D，S，P其中D是数据对象，S是D上的关系集，P是对D的根本操作集。书中的定义格式：ADT 抽象数据类型名数据对象：数据关系：根本操作：ADT 抽象数据类型名 ADT 有两个重要特征: 数据抽象 数据封装 四、本次课小结：约3min 1.熟悉各名词 2.术语的含义 3.掌握根本概念 五、作业 约2min 2、 什么是数据构造？ 课 时 授 课 计 划 2022-20_学年第 二 学期第1周 授 课 日 期 2月 24日 星期5 月 日 星期 月 日 星期 月 日 星期 月 日 星期 班 级 信管10-1 根本课题 抽象数据类型的表示与实现 算法和算法分析p 教学目的与要求：类C语言的各种句型及算法描绘的标准 教学重点：类C语言的各种句型及算法描绘的标准 教学难点：类C语言的各种句型及算法描绘的标准 作业及参考书：数据构造算法实现及解析/高一凡 编著 教具：多媒体 板书 课堂类型：讲授 教学过程：复习引入展开举例小结作业 一、复习：约5min 1、数据构造的根本概念 2、一些根本术语 二、引入 约2min 由程序设计过程遇到的问题引入 三、讲课进程设计 1.3抽象数据类型的表示与实现 1.3.1根本操作：约15min Assignple_( Z, v1, v2 ) 操作结果：构造复数 Z,其实部和虚部 分别被赋以参数 v1 和 v2 的值。Destroyple_( Z) 操作结果：复数Z被销毁。GetReal( Z, realPart ) 初始条件：复数已存在。操作结果：用realPart返回复数Z的实部值。GetImag( Z, ImagPart ) 初始条件：复数已存在。操作结果：用ImagPart返回复数Z的虚部值。Add( z1,z2, sum ) 初始条件：z1, z2是复数。操作结果：用sum返回两个复数z1, z2 的和值。1.3.2对本书所采用的类C语言作简要说明 约18min 1.预定义常量及类型 2、数据构造的存储构造typedef 3、算法描绘为以下的函数形式：4.在算法描绘中可以使用的赋值语句形式有：5.在算法描绘中可以使用的选择构造语句形式有：6.在算法描绘中可以使用的循环构造语句形式有：7.在描绘算法中可以使用的完毕语句形式有：8.在算法描绘中可以使用的输入输出语句形式有：9.在算法描绘中使用的注释格式为：10.在算法描绘中可以使用的扩展函数有：11.逻辑运算约定 1.4算法和算法分析p 1.4.1、算法 约10min 算法是为理解决某类问题而规定的一个有限长的操作序列。一个算法必须满足以下五个重要特性：1有穷性 2确定性 3可行性 4有输入 5有输出 1.4.2、算法设计的原那么 约10min 设计算法时，通常应考虑到达以下目的：1正确性2.可读性3强健性4高效率与低存储量需求 1.4.3、算法效率的衡量方法和准那么 约20min 通常有两种衡量算法效率的方法 事后统计法 缺点：1必须执行程序 2其它因素掩盖算法本质 事前分析p 估算法 和算法执行时间相关的因素：1算法选用的策略2问题的规模3编写程序的语言4编译程序产生的机器代码的质量5计算机执行指令的速度 算法 = 控制构造 + 原操作 固有数据类型的操作一个算法的执行时间大致上等于其所有语句执行时间的总和，对于语句的执行时间是指该条语句的执行次数和执行一次所需时间的乘积。在计算时间复杂度时所采用的记号“O”是数学符号，其严格的数学定义是：假设T(n)和f(n)是定义在正整数集合上的两个函数，那么T(n)=O(f(n)表示存在正的常数c和n0，使得当n>=n0时都满足0=|ai-1 ,aiD, i=2,n 根本操作：构造初始化操作：InitList( L ) 操作结果：构造一个空的线性表L。构造销毁操作：DestroyList( L ) 初始条件：线性表 L 已存在。操作结果：销毁线性表 L。引用型操作 ListEmpty( L )线性表判空ListLength( L )求线性表的长度PriorElem( L, cur_e, pre_e )求数据元素的前驱Ne_tElem( L, cur_e, ne_t_e )求数据元素的后继GetElem( L, i, e )求线性表中某个数据元素LocateElem( L, e, pare( ) )定位函数ListTraverse(L, visit( )遍历线性表加工型操作 ClearList( L )线性表置空PutElem( L, i, e )改变数据元素的值ListInsert( L, i, e )插入数据元素ListDelete(L, i, e) 删除数据元素2.1.2举例 约10min 两个线性表合并LA和LB 2.2 线性表的顺序表示和实现 2.2.1顺序映象 约15min 以 _ 的存储位置和 y 的存储位置之间某种关系表示逻辑关系。最简单的一种顺序映象方法是：令y的存储位置和_的存储位置相邻。线性表的根本操作在顺序表中的实现 InitList(L) / 构造初始化 LocateElem(L, e, pare) / 查找 ListInsert(L, i, e) / 插入元素 ListDelete(L, i) / 删除元素 2.1.1、线性表操作 约20min ListInsert(L, i, e)的实现：首先分析p 插入元素时，线性表的逻辑构造发生什么变化？ 线性表操作 ListDelete(L, i, e)的实现：首先分析p ：删除元素时，线性表的逻辑构造发生什么变化？线性表类型的实现 2.1.2、线性表顺序存储构造的特点：约20min 它是一种简单、方便的存储方式。它要求线性表的数据元素依次存放在连续的存储单元中，从而利用数据元素的存储顺序表示相应的逻辑顺序，这种存储方式属于静态存储形式。暴露的问题 (1)在做插入或删除元素的操作时，会产生大量的数据元素挪动；(2)对于长度变化较大的线性表，要一次性地分配足够的存储空间，但这些空间常常又得不到充分的利用；(3)线性表的容量难以扩大。三、小结 约5min 1.理解线性表的逻辑构造特性是数据元素之间存在着线性关系，在计算机中表示这种关系的两类不同的存储构造是顺序存储构造和链式存储构造。用前者表示的线性表简称为顺序表，用后者表示的线性表简称为链表。2.纯熟掌握这两类存储构造的描绘方法，以及线性表的各种根本操作的实现。课 时 授 课 计 划 2022-20_学年第 二 学期第2周 授 课 日 期 3月 3 日 星期 月 日 星期 月 日 星期 月 日 星期 月 日 星期 班 级 信管10-1 根本课题 线性表的链式表示和实现 一元多项式的表示及相加 教学目的与要求：1、掌握线性链表、单链表、静态链表的概念、表示及实现方法。2、掌握循环链表的概念 3、掌握双向链表的表示与实现 教学重点：1、线性链表之单链表的表示及实现方法。2、双向链表的表示与实现 教学难点：1、线性链表 2、双向链表的存储表示 作业及参考书：写一算法将单链表中值重复的结点删除，使所得的结果表中各结点值均不一样。数据构造算法实现及解析/高一凡 编著 教具：多媒体 板书 课堂类型：讲授 教学过程：复习引入展开举例小结作业 一、复习 约5min 复习线性表有的概念 二、引入 约2min 由线性表的表示不方便引入 三、讲课进程设计 2.3 线性表的链式表示和实现 线性表顺序存储构造的特点：约10min 它是一种简单、方便的存储方式。它要求线性表的数据元素依次存放在连续的存储单元中，从而利用数据元素的存储顺序表示相应的逻辑顺序，这种存储方式属于静态存储形式。暴露的问题 (1)在做插入或删除元素的操作时，会产生大量的数据元素挪动；(2)对于长度变化较大的线性表，要一次性地分配足够的存储空间，但这些空间常常又得不到充分的利用；(3)线性表的容量难以扩大。2.3.1、单链表 约10min 用一组地址任意的存储单元存放线性表中的数据元素这组存储单元可以是连续的也可以是不连续的。2.3.2、结点和单链表的 C 语言描绘 约10min 2.3.3、单链表操作的实现 约13min 因此生成链表的过程是一个结点“逐个插入”的过程。操作步骤：1、建立一个“空表”；2、输入数据元素an，建立结点并插入；3、输入数据元素an-1，建立结点并插入；4、依次类推，直至输入a1为止。2.3.4、其它形式的链表 约5min 1.循环链表2.双向链表 2.3.5、有序表类型 约5min 2.4一元多项式的表示 2.4.1一元多项式 约20min 在计算机中，可以用一个线性表来表示: P = (p0, p1, ，pn) 抽象数据类型一元多项式的定义如下：ADT Polynomial 数据对象：D ai| aiTermSet,i=1,2,m, m0 TermSet 中的每个元素包含一个 表示系数的实数和表示指数的整数 数据关系：R1 |ai-1 ,aiD, i=2,n 且ai-1中的指数值ai中的指数值 根本操作：CreatPolyn ( P, m ) 操作结果：输入 m 项的系数和指数， 建立一元多项式 P。DestroyPolyn ( P ) 初始条件：一元多项式 P 已存在。操作结果：销毁一元多项式 P。PrintPolyn ( P ) 初始条件：一元多项式 P 已存在。操作结果：打印输出一元多项式 P。PolynLength( P ) 初始条件：一元多项式 P 已存在。操作结果：返回一元多项式 P 中的项数。AddPolyn ( Pa, Pb ) 初始条件：一元多项式 Pa 和 Pb 已存在。操作结果：完成多项式相加运算，即：Pa = PaPb，并销毁一元多项式 Pb。SubtractPolyn ( Pa, Pb ) ADT Polynomial 2.4.2一元多项式的实现：约10min typedef OrderedLinkList polynomial; / 用带表头结点的有序链表表示多项式 四、小结约5min 1.可以从时间和空间复杂度的角度综合比拟线 性表两种存储构造的不同特点及其适用场合。五、本章作业：约5min 写一算法将单链表中值重复的结点删除，使所得的结果表中各结点值均不一样。此题可以这样考虑，先取开场结点中的值，将它与其后的所有结点值一一比拟，发现一样的就删除掉，然后再取第二结点的值，重复上述过程直到最后一个结点。课 时 授 课 计 划 2022-20_学年第 一 学期第3周 授 课 日 期 9月22日 五 星期 月 日 星期 月 日 星期 月 日 星期 月 日 星期 班 级 信管10-1 根本课题栈栈的应用举例 教学目的与要求：1、 栈的数据类型定义 2、 栈的顺序存储与实现 3、 掌握栈的应用方法，理解栈的重要作用 教学重点：1、栈的顺序存储表示与实现方法 2、利用栈实现行编辑、利用栈实现表达式求值 教学难点：1、栈的定义 2、利用栈实现表达式求值 作业及参考书：1、栈定义的应用 2、栈的特点 数据构造算法实现及解析/高一凡 编著 教具：多媒体 板书 课堂类型：讲授 教学过程：引入展开举例小结作业 一、引入约10min 1.什么是线性构造？   2.以餐馆中一叠一叠的盘子的使用为例，引出栈的特点。二、讲课进程设计 3.1 栈的类型定义3.1.1、栈、栈顶、栈底(bottom)的定义约10min 3.1.2栈的类型定义约10min 3.2 栈的应用举例 例一、 数制转换 约10min 十进制数N和其他d进制数的转换是计算机实现计算的根本问题，个简单算法基于以下原理：N = (N div d)×d + N mod d (其中：div为整除运算，mod为求余运算) 例二、 括号匹配的检验 约10min 检验括号是否匹配的方法可用“期待的急迫程度”这个概念来描绘。三种情况对应到栈的操作即为：1和栈顶的左括弧不相匹配；2栈中并没有左括弧等在哪里；3栈中还有左括弧没有等到和它相匹配的右括弧。例三、 行编辑程序问题 约10min 在用户输入一行的过程中，允许用户输入出过失，并在发现有误时可以及时更正。合理的作法是：设立一个输入缓冲区，用以承受用户输入的一行字符，然后逐行存入用户数据区,并假设“#”为退格符，“”为退行符。例四、 迷宫求解 约10min 假设以栈S记录“当前途径”，那么栈顶中存放的是“当前途径上最后一个通道块”。“纳入途径”的操作即为“当前位置入栈；“从当前途径上删除前一通道块”的操作即为“出栈“。例五、表达式求值 约10min 任何一个表达式都是由操作数(operand)、运算符(operator)和界限符(delimiter)组成。例六、 实现递归 约10min 递归函数的实现 一个递归函数的运行过程类似于多个函数的嵌套调用，差异仅在于“调用函数和被调用函数是同一个函数”。为了保证“每一层的递归调用”都是对“本层”的数据进展操作，在执行递归函数的过程中需要一个“递归工作栈”。三、小结约5min 1.掌握栈和队列类型的特点，并能在相 应的应用问题中正确选用它们。2.纯熟掌握栈类型的两种实现方法，特 别应注意栈满和栈空的条件以及它们的描绘方法。四、作业约5min 1、4个元素a1，a2，a3和a4依次通过一个栈，在a4进栈前，栈的状态，那么不可能的出栈序是(A)a4，a3，a2，a1(B)a3，a2，a4，a1 (C)a3，a1，a4，a2(D)a3，a4，a2，a1 2、栈的特点是。课 时 授 课 计 划 2022-20_学年第 一 学期第3周 授 课 日 期 9月27日 三 星期 月 日 星期 月 日 星期 月 日 星期 月 日 星期 班 级 信管10-1 根本课题队列 教学目的与要求：1.纯熟掌握循环队列和链队列的根本操作实现算法。2.理解递归算法执行过程中栈的状态变化过程。教学重点：1链队的表示与实现 教学难点：.1。链队的表示与实现 作业及参考书：1栈与队列的比拟 2读程序段 数据构造算法实现及解析/高一凡 编著 教具：多媒体 板书 课堂类型：讲授 教学过程：引入展开举例小结作业 一、引入约5min 在日常生活中，为了维持正常的社会秩序而出现的常见现象是什么？ 是“排队“。在计算机程序中，模拟排队的数据构造是“队列“。二、讲课进程设计 3.4 队列 1队列的定义约10min 2队列的抽象类型定义 约15min 3.队列的根本操作：约20min InitQueue(Q) 操作结果：构造一个空队列Q。DestroyQueue(Q) 初始条件：队列Q已存在。操作结果：队列Q被销毁，不再存在。QueueEmpty(Q) 初始条件:队列Q已存在。操作结果:假设Q为空队列,那么返回TRUE，否那么返回FALSE。QueueLength(Q) 初始条件:队列Q已存在。操作结果:返回Q的元素个数，即队列 的长度。GetHead(Q, e) 初始条件：Q为非空队列。操作结果：用e返回Q的队头元素。ClearQueue(Q) 初始条件：队列Q已存在。操作结果：将Q清为空队列。EnQueue(Q, e) 初始条件:队列Q已存在。操作结果:插入元素e为Q的新的队尾元素。DeQueue(Q, e) 初始条件：Q为非空队列。操作结果：删除Q的队头元素，并用e返回其值。QueueTravers(Q, visit) 队列类型的实现 4.链队列链式映象 约15min 5.循环队列顺序映象 约20 min 队列在程序设计中的一个典型应用例子是作业排队问题。三、小结约5min 1.纯熟掌握循环队列和链队列的根本操作实现算法，特别注意队满和队空的描绘方法。2.理解递归算法执行过程中栈的状态变化过程。四、作业约10min 1、线性表、栈和队列都是构造,可以在线性表的位置插入和删除元素，对于栈只能在插入和删除元素，对于队列只能在插入元素和删除元素。2、 指出下述程序段的功能是什么?  (1) void Demo1(SeqStack _S)int i; arr64 ; n=0 ;while ( StackEmpty(S) arrn+=Pop(S);for (i=0, i| 0ib1-2, 0jb2-1 COL = | 0ib1-1, 0 jb2-2 根本操作：约10min InitArray(A, n,bound1,boundn) DestroyArray(A) Value(A, e, inde_1, , inde_n) Assign(A, e, inde_1, , inde_n) 5.2 数组的顺序表示和实现 类型特点: 约10min 1) 只有引用型操作，没有加工型操作；2) 数组是多维的构造，而存储空间是 一个一维的构造。有两种顺序映象的方式: 约10min 1)以行序为主序(低下标优先)；2)以列序为主序(高低标优先)。5.3 矩阵的压缩存储 5.3.1特殊矩阵a.对称矩阵 约15min 定义 压缩存储方式 b.三角矩阵 约15min 定义 压缩存储方式 c.对角矩阵 约20min 定义 压缩存储方式 三、小结 1、数组的特殊性 2、数组的存储 3、特殊矩阵的存储 课 时 授 课 计 划 2022-20_学年第 二 学期第5周 授 课 日 期 3月23日 三 星期 月 日 星期 月 日 星期 月 日 星期 月 日 星期 班 级 信管10-1 根本课题稀疏矩阵广义表 教学目的与要求：1、掌握稀疏矩阵的定义，三元组表示 2、掌握广义表的定义，它的链接存储构造 教学重点：1、三元组表示 2、广义表的存储构造 教学难点：1、三元组表示法 2、定义 作业及参考书：1、画出给出的广义表的两种存储构造 2、求广义表的运算 3、在对象矩阵中求下标变换公式 数据构造算法实现及解析/高一凡 编著 教具：多媒体 板书 课堂类型：讲授 教学过程：引入展开举例小结作业 一、引入约5min 由特殊矩阵引入 二、讲课进程设计5.3.2稀疏矩阵 1、定义约5min 两类稀疏矩阵：1) 特殊矩阵2) 随机稀疏矩阵 2、随机稀疏矩阵的压缩存储方法: 1、三元组顺序表 约20min 2、行逻辑联接的顺序表 约20min 3、十字链表 约10min 5.4 广义表 广义表的定义约20min 1、 广义表：表头：非空广义表的第一个元素1 表尾：其余元素2， ，n组成的表。2、 广义表的抽象数据类型定义3、广义表的操作：5.5广义表的的存储构造 由于广义表中的数据元素可以具有不同的构造因此，采用链式存储构造表示广义表。每个数据元素可用一个结点表示。1、 广义表的头尾链表存储表示约10min typedef enumATOM, LISTElemTag; typedef struct GLNode ElemTag tag; union AtomType atom; struct struct GLNode _hp , _tp;ptr ; _GList; 三、小结约5min 1.理解数组的两种存储表示方法，并掌握数组在以行为主的存储构造中的地址计算方法。2.掌握对特殊矩阵进展压缩存储时的下标变换公式。3.理解稀疏矩阵的两类压缩存储方法的特点和适用范围，领会以三元组表示稀疏矩阵时进展矩阵运算采用的处理方法。4、掌握广义表的构造特点及其存储表示方法，读者可根据自己的习惯纯熟掌握任意一种构造的链表，学会对非空广义表进展分解的两种分析p 方法：即可将一个非空广义表分解为表头和表尾两局部或者分解为n个子表。四、课后作业及习题约5min 1、画出下面广义表的两种存储构造图示：   (a), b), ( ), d), (e, f) 2、求以下广义表运算的结果：1      GetHEAD(a,b),(c,d); 2       GetTAIL(a,b),(c,d); 3       GetTAILHEAD(a,b),(c,d); 4       GetHEADTAILHEAD(a,b),(c,d); 5       GetTAILHEADTAIL(a,b),(c,d); 3、设有三对角矩阵An×n ,将其三条对角线上的元素逐行地存于数组B(1:3n-2)中，使得Bk= aij ，求：1       用i,j表示k的下标变换公式；2       用k表示i,j的下标变换公式。课 时 授 课 计 划 2022-20_学年第 一 学期 第6周 授 课 日 期 10月20日 五 星期 月 日 星期 月 日 星期 月 日 星期 月 日 星期 班 级 信管10-1 根本课题树的定义和根本术语二叉树 教学目的与要求：1、掌握树、二叉树的根本概念和术语，二叉树的性质 2、掌握二叉树的两种存储构造 教学重点：1、二叉树的性质和定义 2、链式存储构造 教学难点：1、二叉树的性质 2、链式存储二叉树的根本操作 作业及参考书：1、一棵度为2的树与二叉树的区别 2、3个结点的树与3个结点的二叉树 数据构造算法实现及解析/高一凡 编著 教具：多媒体 板书 课堂类型：讲授 教学过程：引入展开举例小结作业 一、引入约5min 由前几章的线性构造带来的问题引出非线性构造。二、讲课进程设计第6章 树和二叉树 6.1树的定义和根本术语 1、 树的定义约10min 树是包含n个结点的有限集合(n>0) Tree=(D,R) 其中，D是具有一样性质的数据元素的集合，假设D中只有一个元素，那么R为空集，否那么R是D上某个二元关系H的集合，H是如下描绘的二元关系：1在D中存在唯一一个称为根的元素r0,它在关系H下无前驱；2除结点r0外,K中每个结点对于关系H来说，都有且只有一个前驱。3结点r0外的任何结点rR，都存在一个结点序列r0,r1,rs,H(1|i=1,2,m,m>0 6.2二叉树 6.2.1二叉树的类型定义约15min 二叉树是另一种树型构造，它的特点是每个结点至多只有二棵子树即二叉树中不存在度大于2的结点),并且,二叉树的子树有左右之分,其次序不能任意颠倒。二叉树或为空树，或是由一个根结点加上两棵分别称为左子树和右子树的、互不交的二叉树组成。(树的度最大为2) 二叉树的主要根本操作：查 找 类 Root(T); Value(T, e); Parent(T, e); LeftChild(T, e); RightChild(T, e); LeftSibling(T, e); RightSibling(T, e); BiTreeEmpty(T); BiTreeDepth(T); PreOrderTraverse(T, Visit); InOrderTraverse(T, Visit); PostOrderTraverse(T, Visit); LevelOrderTraverse(T, Visit); 插 入 类 InitBiTree(T); Assign(T, e, value); CreateBiTree(T, definition); InsertChild(T, p, LR, c); 删 除 类 ClearBiTree(T); DestroyBiTree(T); DeleteChild(T, p, LR); 6.2.2二叉树的性质 约20min 性质1：在二叉树的第i 层上至多有2i-1 个结点。(i1) 性质 2 ：深度为 k 的二叉树上至多含 2k-1个结点k1。性质 3 ：对任何一棵二叉树，假设它含有n0 个叶子结点0度结点、n2 个度为 2的结点，那么必存在关系式：n0 = n2+1。两类特殊的二叉树：满二叉树：指的是深度为k且含有2k-1个结点的二叉树。完全二叉树：树中所含的 n 个结点和满二叉树中编号为 1 至 n 的结点一一对应。编号的规那么为，由上到下，从左到右。性质 4 ：具有 n 个结点的完全二叉树的深度为 ëlog2nû +1 。性质 5 ：假设对含 n 个结点的完全二叉树从上到下且从左至右进展 1 至 n 的编号，那么对完全二叉树中任意一个编号为 i 的结点：1如i=1，那么序号为i的结点是根结点，无双亲结点；如i>1，那么序号为i的结点的双亲结点序号为。2如2×i>n，那么序号为i的结点无左孩子；如2×in，那么序号为i的结点的左孩子结点的序号为2×i。3如2×i1>n，那么序号为i的结点无右孩子；如2×i1n，那么序号为i的结点的右孩子结点的序号为2×i1 6.2.3 二叉树的存储构造 约25min 1、 二叉树的顺序存储表示 2、二叉树的链式存储表示 1).二叉链表 2)三叉链表 3)双亲链表 4)线索链表 三、小结约5min 1、树、二叉树的定义 2、二叉树的性质 3、存储构造 四、作业约5min 1.一棵度为2的树与一棵二叉树有何区别？ 2.试分别画出具有3个结点的二叉树和3 个结点的二叉树的所有不同形态。课 时 授 课 计 划 2022-20_学年第 一 学期 第7周 授 课 日 期 10月25日 三 星期 月 日 星期 月 日 星期 月 日 星期 月 日 星期 班 级 信管10-1 根本课题遍历二叉树和线索二叉树 教学目的与要求：1.遍历二叉树是二叉树各种操作的根底。掌握各种遍历策略的递归算法，灵敏运用遍历算法实现二叉树的其它操作。2.理解二叉树线索化的本质.纯熟掌握二叉树的线索化过程以及在中序线索化树上找给定结点的前驱和后继的方法。教学重点：1.遍历二叉树是二叉树各种操作的根底。2各种遍历策略的递归算法，运用遍历算法实现二叉树的其它操作。教学难点：各种遍历策略的递归算法，运用遍历算法实现二叉树的其它操作。二叉树的线索化过程以及在中序线索化树上找给定结点的前驱和后继的方法。作业及参考书：写出所给二叉树的前、中、后序的序列 数据构造算法实现及解析/高一凡 编著 教具：多媒体 板书 课堂类型：讲授 教学过程：引入展开举例小结作业 一、 引入约3min 由二叉树的构造引出对每个结点的遍历。二、 讲课进程设计 6.3遍历二叉树和线索二叉树 6.3.1二叉树的遍历 一、问题的提出约7min 顺着某一条搜索途径巡访二叉树中的结点，使得每个结点均被访问一次，而且仅被访问一次。将树线性化对“二叉树”而言，可以有三条搜索途径：Ø 1先上后下的按层次遍历；Ø 2先左子树后右子树的遍历；Ø 3先右子树后左子树的遍历。二、先左后右的遍历算法 约10min 先根序的遍历算法 假设二叉树为空树，那么空操作；否那么 1访问根结点；2先序遍历左子树；3先序遍历右子树。中根序的遍历算法 假设二叉树为空树，那么空操作；否那么 1中序遍历左子树；2访问根结点；3中序遍历右子树。后根序的遍历算法 假设二叉树为空树，那么空操作；否那么 1后序遍历左子树；2后序遍历右子树；3访问根结点。三、算法的递归描绘 约10min 总结：无论先序、中序、后序遍历二叉树，遍历时的搜索道路是一样的：从根结点出发，逆时针延二叉树外缘挪动对每个结点均途径三次。先序遍历：第一次经过结点时访问。中序遍历：第二次经过结点时访问。后序遍历：第三次经过结点时访问。四、中序遍历算法的非递归描绘 约10min 五、遍历算法的应用举例 约30min 1、统计二叉树中叶子结点的个数(先序遍历) 先序(或中序或后序)遍历二叉树，在 遍历过程中查找叶子结点，并计数。由此，需在遍历算法中增添一个“计数” 的参数，并将算法中“访问结点”的操 作改为：假设是叶子，那么计数器增1。2、求二叉树的深度(后序遍历) 算法根本思想: 首先分析p 二叉树的深度和它的左、右子树深度之间的关系。3、复制二叉树(后序遍历) 其根本操作为：生成一个结点。4、建立二叉树的存储构造 p 不同的定义方法相应有不同的存储构造的建立算法 按给定的表达式建相应二叉树 由先缀表示式建树 由原表达式建树 我们已经知道二叉树构造和它的某个遍历序列不存在一一对应的关系，但假设一个二叉树的前序序列和中序序列，却一定可以惟一确定一个二叉树的构造。6.3.2线索二叉树 约20min 何谓线索二叉树？ 遍历二叉树的结果是，求得结点的一个线性序列。 如何保存这种在遍历过程中得到的信息？ 最简单的方法是在每个