《数据结构(C语言版)》教案

1、欢迎关注作者！作者每天都会史新粘品文苹!数据结构（C语言版）教案数据结构（C语言版）教案2020至2020学年第一学期教 案课程名称 数据结构 使用教材数据结构 （C语言版）教学时数56课程性质 必修任课班级（人数）信管（53人）信息 系（部）信管 教研室任课教师山东科技大学泰山科技学院课时授课计划2020-2020学年笫二学期第1周授课日期2月20日星期1月 日星期月 日星期月 日星期月 日星 期班级信管10-1基本课题第1章绪论1.1-1.2教学目的与要求：1. 了解数据结构的基本概念2.理解常用术语教学重点：数据结构的基本概念和术语教学难点：数据元素之间的四种结构关系作业及参考书：1、什

2、么是数据结构？数据结构算法实现及解析/高一凡编著教具：多媒体板书课堂类型：讲授 教学过程：自我介绍开课引入展开举例小结作业 一、自我介绍和课程介绍约Smin课时：64二、引入 约2min由问题的提出引入 三、 讲课进程设计1.1什么是数据结构1.1.1、数据结构与其它的关系约15min数据结构+ 算法二程序程序设计：为计算机处理问题编制一组指令集算法：处理问题的策略数据 结构：问题的数学模型1.1.2、当今计算机应用的特点：约25min 1）所处理的数据量大且具有一定的关系；2）对其操作不再是单纯的数值计算，而更多地是需要对其进行组织、管理和检索。举例说明：1）学生成绩表2）井安棋对弈3）交通

3、管理结论计算机的操作对象的关系更加复杂， 操作形式不再是单纯的数值计算，而更多地是对这些具有一定关系的数据进行组织管理；我们将此称为非数值性处理。要使计算机能够更有效地进行这些非数值性处理，就必 须弄清楚这些操作对象的特点，在汁算机中的表示方式以及各个操作的具体实现手段。1.2基本概念和术语1.1.1、数据与数据结构 约20min数据：是对客观事物的符号表所有能被输入到计算机中，且能被讣算机处理的符号的集合。是计算机操作的对象的 总称。是计算机处理的信息的某种特定的符号表示形式。数据元素：是数据（集合）中的一个“个体”，是数据结构中讨论的基本单位。数据对象：是性质相同的数据元素的集合，是数据的

4、一个子集。数据结构：是相互之间存在一种或多种特定关系的数据元素的集合。这种集合称为结 构。数据的逻辑结构可归结为以下四类：种类特征示例集合元素间为松散的关系线 性结构元素间为严格的一对一关系如上面的成绩表中各元素树形结构元素间为严格 的一对多关系图状结构（或网状结构）元素间为多对多关系数据结构的形式定义为:数 据结构是一个二元组数据的存储结构：逻辑结构在存储器中的映像数据元素的映 象方法：计算机中存储信息的最小单位：位，8位为一字节，两个字节为一字，字节、字 或更多的二进制位可称为位串。在逻辑描述中，把位串称为元素或结点。关系的映象方法：顺序映象链式映象122、数据类型约5min数据类型是一个

5、值 的集合和定义在此集合上的一组操作的总称。123、抽象数据类型约20min是指一个数学模型以及定义在此数学模型上的一组操 作。关键：使用它的人可以只关心它的逻辑特征，不需要了解它的存储方式。定义它的人 同样不必要关心它如何存储。抽象数据类型表示法：三元组表示：（D, S, P） 其中D是数据对象，S是D上的关系集，P是对D的 基本操作集。书中的定义格式：ADT抽象数据类型名数据对象：数据对象的定义数据关系：数据关系的定义基本操作：基本操作的定义ADT抽象数据类型名ADT有两个重要特征：数据抽象数据封装四、本次课小结：约3min 1.熟悉各名词2.术语的含义3.掌握基本概念五、作业约2min

6、2、什么 是数据结构？课时授课计划2020-2020学年笫二学期 第1周授课日期2月24日星期5月 日星期月 日星期月 日星期月 日星期 班级信管10-1基本课题抽象数据类型的表示与实现算法和算法分析教学LJ的与要 求：类C语言的各种句型及算法描述的规范教学重点：类C语言的各种句型及算法描述的规范教学难点：类C语言的各种句型及算法描述的规范作业及参考书：数据结构算法实现及解析/高一凡编著教具：多媒体 板书 课堂类型：讲授 教学过程：复习一引入展开举例小结作业一、复习：约5minl、数据结构的基本概念2、一些基本术语二、引入约2min由程序设计过 程遇到的问题引入 三、讲课进程设计1.3抽象数据

7、类型的表示与实现131基本操作：约15min ASSignCOmPlex( Z, vl, v2 )操作结果：构造复数Z,其实部和虚部 分别被赋 以参数Vl和v2的值。DestroyComplexC Z)操作结果：复数Z被销毁。GetRea1(乙realPart)初始条件：复数已存在。操作结果：用realPart返回复数Z的实部值。Getlmag(乙ImagPait)初始条件：复数已存在。操作结果：用ImagPart返回复数Z的虚部值。Add( zl,z2, SUm )初始条件：zl, z2是复数。操作结果：用SUm返回两个复数zl, z2的和值。1.3.2对本书所采用的类C语言作简要说明约18

8、min 1.预定义常量及类型2、数据结 构的存储结构typedef3.算法描述为以下的函数形式：4. 在算法描述中可以使用的赋值语句形式有：5. 在算法描述中可以使用的选择结构语句形式有：6. 在算法描述中可以使用的循环结构语句形式有：7. 在描述算法中可以使用的结束语句形式有：&在算法描述中可以使用的输入输出语句形式有：9. 在算法描述中使用的注释格式为：10. 在算法描述中可以使用的扩展函数有：11. 逻辑运算约定14算法和算法分析1.4.1、算法 约IOmin算法是为了解决某类问 题而规定的一个有限长的操作序列。一个算法必须满足以下五个重要特性：1.有穷性2.确定性3.可行性4.有输入5

9、.有输出1.4.2、算法设计的原则约 IOmin设计算法时，通常应考虑达到以下目标：1. 正确性2.可读性3.健壮性4.高效率与低存储量需求1.4.3、算法效率的衡量方 法和准则约20min通常有两种衡量算法效率的方法事后统计法缺点：1.必须执行程序2. 其它因素掩盖算法本质事前分析估算法和算法执行在计算算法的存储量包括：1.输入数据所占空间2.程序本身所占空间3.辅助变量所占空 间四、小结：约5min 1.理解算法五个要素的确切含义。2. 掌握计算语句频度和估算算法五、作业 约5min 1、试编写算法求一元多项式Pn(X)=a+alx+a2x2+a3x3+.ax的值 Pn(xO),并确定算法

10、中的每一语句的执行次数和整个算法的试讨论这两种方法的优缺点，并在本题算法中以你认为较好的一种方式实现输入和 输出。课时授课计划2020-2020学年第二学期第2周授课日期2月27日星期月 日星期月 日星期月 日星期月 日星期 班 级 信管10-1基本课题 线性表的类型定义 线性表的顺序表示和实现 教学Ll的与要 求：1、掌握线性表的概念和类型定义2、掌握线性表的顺序表示和实现方法教学重点：线性表的类型定义线性表的顺序表示和实现方法教学难点：线性表的类型定义线性表的顺序存储的实现方法作业及参考书：数据结构算法实现及解析/高一凡编著教具：多媒体板书课堂类型：讲授教学过程：复习引入展开举例小结一、引

11、入约3min由顺序 的算法引入二、讲课进程设计2. 1线性表的类型定义12.1.1线性表的定义约27min线 欢迎关注作者！作者每天都会史新粘品文克!性表是山n (n0)个类型相同的数据元素组成的有限序列。抽象数据类型线性表的定义如下：ADT LiSt 数据对象 D= ai I ai ElemSet, i=l,2,.,n, nO 称 n 为线性表的表长;称n=O时的线性表为空表。数据关系Rl= ai-1 ,ai Iai-I ,aiD, i=2n )基本操作： 结构初始化操作：InitList( L)操作结果：构造一个空的线性表L。结构销毁操作：DestroyList( L )初始条件：线性表L

12、已存在。操作结果：销毁线性表Lo 引用型操作ListEmptyC L )(线性表判空)LiStLength( L)(求线性表的长度) PriorElem( L，cur_e, pre_e )(求数据元素的前驱)NeXtEIem(L, cur_e, next_e )(求数据元 素的后继)GetElem( L, i, e )(求线性表中某个数据元素)LOCateEIem( L, e, COmPare()(定位函数)LiStTraVerse(L, visit()(遍历线性表)加工型操作CIearList( L)(线性表置 空)PUtEIem( L, i, e )(改变数据元素的值)LiStInsert

13、( L, i, e )(插入数据元素)LiStDeIete(L, i, e)(删除数据元素)2.1.2举例约IOmin两个线性表合并LA和LB 2.2线性表的顺序 表示和实现221顺序映象约15min以X的存储位置和y的存储位置之间某种关 系表示逻辑关系x,y。最简单的一种顺序映象方法是：令y的存储位置和X的存储位置相邻。线性表的基本操作在顺序表中的实现InitLiSt(L)/ 结构初始化 LOCateElem(L, e, COmPareo) H 查找 LiStlnSert(L, i, e) / 插入元素 LiStDelete(L, i) / 删除元素 2.1、线性表操作 约 20min Li

14、StlnSert(L, i, e)的实现：首先分析插入元素时，线性表的逻辑结构发生什么变化？线性表操作LiStDeIete(U i, e)的实现:首先分析：删除元素时，线性表的逻辑结构发生什么变化？线性表类型的实现2.1.2、线性表顺 序存储结构的特点：约20min它是一种简单、方便的存储方式。它要求线性表的数据元素依次存放在连续 的存储单元中，从而利用数据元素的存储顺序表示相应的逻辑顺序，这种存储方式属于静 态存储形式。暴露的问题(1)在做插入或删除元素的操作时，会产生大量的数据元素移动；(2) 对于长度变化较大的线性表，要一次性地分配足够的存储空间，但这些空间常常乂 得不到充分的利用；(3

15、) 线性表的容量难以扩充。三、小结约5min 1.7解线性表的逻辑结构特性是数据元素之间存在着线性关系，在 计算机中表示这种关系的两类不同的存储结构是顺序存储结构和链式存储结构。用前者表 示的线性表简称为顺序表，用后者表示的线性表简称为链表。2. 熟练掌握这两类存储结构的描述方法，以及线性表的各种基本操作的实现。课时授课计划2020-2020学年第二学期第2周授课日期3月3日星期月 日星期月 日星期月 日星期月 日星期 班级信管10-1基本课题线性表的链式表示和实现一元多项式的表示及相加教学LI的 与要求：1、掌握线性链表、单链表、静态链表的概念、表示及实现方法。2、掌握循环链表的概念3、掌握

16、双向链表的表示与实现教学重点：1、线性链表之单链表的表示及实现方法。2、双向链表的表示与实现教学难点：1、线性链表2、双向链表的存储表示作业及参考书：写一算法将单链表中值重复的结点删除，使所得的结果表中各结点值均不相同。数据结构算法实现及解析/高一凡编著教具：多媒体板书课堂类型：讲授 教学过程：复习引入展开举例小结作业一、复习约5min复习线性表有的概念二、引入约2min由线性表的表示不方便引入三、讲课进程设计2.3线性表的链式表示和实现线 性表顺序存储结构的特点：约IOmin它是一种简单、方 便的存储方式。它要求线性表的数据元素依次存放在连续的存储单元中，从而利用数据元 素的存储顺序表示相应

17、的逻辑顺序，这种存储方式属于静态存储形式。暴露的问题(1)在做插入或删除元素的操作时，会产生大量的数据元素移动；(2)对于长度变化较大的线性表，要一次性地分配足够的存储空间，但这些空间常常乂得不到充分的利用；(3)线性表的容量难以扩充。231、单链表约IOmin用一组地址任意的存储单元存放线性表中的数据元素(这组存储单元可以是连续的也可以是 不连续的)。2.3.2、结点和单链表的C语言描述约IOmin 2.3.3、单链表操作的实现约13min因此生成链表的过程是一个结点“逐个插入”的过程。操作步骤：1、建立一个“空表”；2、输入数据元素an,建立结点并插入：3、输入数据元素an-l,建立结点并

18、插入；4、依次类推，直至输入al为止。2.3.4、其它形式的链表约5min 1.循环链表2.双向链表2.3.5、有丿了；表类型约5min 2.4 元多项式的表示2.4.1 一元多项式约20min在计算机中，可以用一个线性表来表示:P = (Po,pl,., Pn)抽象数据类型一元 多项式的定义如下：ADT POIynOmial 数据对象：D= ail aiTennSet,i=l,2,.,m, m0 TermSet 中的每个 元素包含一个表示系数的实数和表示指数的整数数据关系：Rl=ai-l,ai Iai-I ,aiD, i=2n fiai-1中的指数值ai中的指数值基本操作：CreatPOIy

19、n ( P, m )操作结果：输入m项的系数和指数，建立一元多项式PoDeStrOyPOlyn ( P )初始条件：一元多项式P已存在。操作结果：销毁一元多项式POPrintPOIyn ( P )初始条件：一元多项式P已存在。操作结果：打印输出一元多项式PoPolynLengtlX P )初始条件：一元多项式P已存在。操作结果：返回一元多项式P中的项数。欢迎关注作者！作者每天都会史新粘品文克!AddPOlyn ( Pa, Pb )初始条件：一元多项式Pa和Pb已存在。操作结果：完成多项式相加运算，即：Pa = Pa+Pb,并销毁一元多项式PboSUbtraCtPOlyIl ( Pa, Pb )

20、 ADT PoIynOmial 2.4.2 一元多项式的实现：纟勺 IOmin typedefOrdereClLinkLiSt polynomial; /用带表头结点的有序链表表示多项式四、小结 约5min 1.能够从五、本章作业：约5min写一算法将单链表中 值重复的结点删除，使所得的结果表中各结点值均不相同。本题可以这样考虑，先取开始结点中的值，将它与其后的所有结点值一一比较，发现 相同的就删除掉，然后再取第二结点的值，重复上述过程直到最后一个结点。课时授课计划2020-2020学年第一学期第3周授课日期9月22日五星期月 日星期月 日星期月 日星期月 日星 期班级信管10-1基本课题栈栈

21、的应用举例教学目的与要求：1、栈的数据类型定义2、栈的顺序存储与实现3、掌握栈的应用方法，理解栈的 重要作用教学重点：1、栈的顺序存储表示与实现方法2、利用栈实现行编辑、利用栈实现表达式求值教 学难点：1、栈的定义2、利用栈实现表达式求值作业及参考书：1、栈定义的应用2、栈的特点数据结构算法实现及解析/高一凡编著教具： 多媒体板书课堂类型：讲授 教学过程：引入展开举例小结一作业一、引入约IOmin 1.什么是线性结构？2.以餐馆中一叠一叠的盘子的使用为例，引出栈的特点。二、讲课进程设计3.1栈的类型定义3.1、栈、栈顶(top)、栈底(bottom)的定义约IOmin 3.2栈的类型定义约IO

22、min 3.2栈的应用举例 例一、数制转换约IOmin十进制数N和其他d进制数的转换是讣算机实现讣算的基本问题，个简单算法基于下列原理：N = (N div d)d + N mod d (其中：div为整除运算，mod为求余运算)例二、括号匹 配的检验约IOmin检验括号是否匹配的方法可用“期待的急迫程度”这个概念来描述。三种悄况对应到栈的操作即为：1. 和栈顶的左括弧不相匹配；2. 栈中并没有左括弧等在哪里；3. 栈中还有左括弧没有等到和它相匹配的右括弧。例三、行编辑程序问题约1 Omin在用户输入一行的过程中，允许用户输入出差错，并在发现有误时可以及时更正。合理的作法是：设立一个输入缓冲区

23、，用以接受用户输入的一行字符，然后逐行存入 用户数据区,并假设“# ”为退格符，“ ”为退行符。例四、迷宫求解约IOmin假设以栈S记录“当前路径”，则栈顶中存放的是“当前路径上最后一个通道块”。“纳入路径”的操作即为“当前位置入栈；“从当前路径上删除前一通道块”的操作即为“出栈“。例五、表达式求值约IOmin任何一个表达式都是由操作数(OPerand)、运算符(OPeratOr)和界限符(delimiter)组成。例六、实现递归约IOmin递归函数的实现一个递归函数的运行过程类似于多个函数的嵌套调用，差别仅在于“调用函数和 被调用函数是同一个函数”。为了保证“每一层的递归调用”都是对“本层”

24、的数据进行操作， 在执行递归函数的过程中需要一个“递归栈”。三、小结约5min 1.掌握栈和队列类型的特点，并能在相应的应用问题中正确选用它们。2.熟练掌握栈类型的两种实现方法，特别应注意栈满和栈空的条件以及它们的描述 方法。四、作业 约5min 1. 4个元素al, a2, a3和a4依次通过一个栈，在“4进栈前，栈的状态，则不可欢迎关注作者！作者每天都会史新粘品文克!能的出栈序是()(A)a4, a3, a2, al (B)a3, a2, a4, al (C)a3, al, a4, a2 (D)a3,a4, a2, al 2、栈的特点是()。课时授课计划2020-2020学年第一学期第3周

25、授课日期9月27日三星期月 日星期月 日星期月 日星期月 日星 期班级信管10-1基本课题队列教学目的与要求：1. 熟练掌握循环队列和链队列的基本操作实现算法。2. 理解递归算法执行过程中栈的状态变化过程。教学重点：1.链队的表示与实现教学难点：.1。链队的表示与实现作业及参考书：1.栈与队列的比较2.读程序段数据结构算法实现及解析/高一凡编著教具： 多媒体板书课堂类型：讲授 教学过程：引入展开举例小结一作业一、引入约5min在日常生活中，为了维持正常的社会秩序而出现的常见现象是什么？是“排队“。在计算机程序中，模拟排队的数据结构是“队列“。二、讲课进程设计3.4队列1队列的定义约IOmin

26、2队列的抽象类型定义约15min 3.队列的基本操作:约 20min InitQUeUe(Q)操作结 果：构造一个空队列Q。DeStrOyQUeUe(Q)初始条件:队列Q已存在。操作结果：队列Q被销毁，不再存在。QUeUeEnlPty(Q)初始条件:队列Q已存在。操作结果:若Q为空队列,则返回TRUE,否则返回FALSEOQUeUeLength(Q)初始条件:队列Q已存在。操作结果:返回Q的元素个数，即队列的长度。GetHead(Q, e)初始条件：Q为非空队列。操作结果：用e返回Q的队头元素。CIearQUeUe(Q)初始条件：队列Q已存在。操作结果：将Q清为空队列。EnQUeUe(Q, e

27、)初始条件:队列Q已存在。操作结果:插入元素e为Q的新的队尾元素。DeQUeUe(Q, e)初始条件：Q为非空队列。操作结果：删除Q的队头元素，并Hle返回其值。QUeUeTraVers(Q, ViSito)队列类型的实现4.链队列链式映象约15min 5.循环队列顺序映象约20 min队列在程序设汁中的一个典型应用例子是作业排队问题。三、小结约5min 1.熟练掌握循环队列和链队列的基本操作实现算法，特别注意队满和队空的描述 方法。2.理解递归算法执行过程中栈的状态变化过程。四、作业约IOminK线性表、栈和队列都是()结构,可以在线性表的()位置插入和删除元素， 对于栈只能在()插入和删除

28、元素，对于队列只能在()插入元素和()删除元素。2、指出下述程序段的功能是什么？(1) VOid Demol(SeqStaCk *S)int i;arr64 ; n=0 ;While ( StaCkEmPty(S) arrn+=Pop(S);for (i=0, i i+)PUSh(S, arri); /Demol课时授课计划2020-2020学年第一学期第4周授课日期月 日星期月 日星期月 日星期月 日星期月 日星期班 级信管10-1基本课题实验二 栈和队列的总结复习教学目的与要求：1、深入了解栈和队列的特征，以便在实际问题背景下灵活运用它们；2、巩固这两种结构的构造方法，接触较复杂问题的递归

29、算法设计。教学重点：巩固这两种结构的构造方法，接触较复杂问题的递归算法设计乙教学难点：巩固这两种结构的构造方法，接触较复杂问题的递归算法设汁。作业及参考书：数据结构算法实现及解析/高一凡编著教具：课堂类型：教学过程：停车场管理问题描述设停车场内只有一个的停放n辆汽车的狭长通道，且只有一个大门可供汽车进出。汽车在停车场内按车辆到达测试数据设 n=2,输入数据为：(tA, 1, 5), (A, 2, 10), ( D, 1, 15), (A,3,20),(A, 4, 25), (A, 5, 30), (D, 2, 35), (D, 4, 40), (E, 0, 0)。其中宀表示到达；Tr表示离去，

30、表示输入结束。基本要求以栈模拟停车场，以队列模拟车场外的便道，按照从终端读入的输入数据序列进行模拟管理。每一组输入数据包括三个数据项：汽车“到达”或“离去”信息、汽 车牌照号码及到达或离去的时刻，对每一组输入数据进行操作后的输出数据为：若是车辆 到达，则输出汽车在停车场内或便道上的停车位置；若是车离去；则输出汽车在停车场内停留的实现提示需另设一个栈，临时停放为给要离去的汽车让路而从停车场退出来的汽车，也用顺序存储结构实现。输入数据按到达或离去的时刻有序。栈中每个元素表示一 辆汽车，包含两个数据项：汽车的牌照号码和进入停车场的时刻。选作内容(1)两个栈共享空间，思考应开辟数组的空间是多少？(2)

31、汽车可有不同种类，则它们的占地面积不同，收费标准也不同，如1辆客车和15辆小汽 车的占地面积相同，1辆十轮卡车占地面积相当于3辆小汽车的占地面积。(3) 汽车可以直接从便道上开走，此时派在它前面的汽车要先开走让路，然后再依 次排到队尾。(4) 停放在便道上的汽车也收费，收费标准比停放在停车场的车低，请思考如何修 改结构以满足这种要求。课时授课计划2020-2020学年第一学期第4周授课日期10月8日日星期月 日星期月 日星期月 日星期月曰星 期班 级信管10-1基本课题串教学目的与要求：1、熟悉串七种基本操作的定义，并能利用这些基本操作实现传的其他各种操作的方 法。2、熟悉掌握在串的定长顺序存

32、储结构上实现串的各种操作的方法。3、掌握串的堆存储结构以及在其上实现串的各种操作的基本方法。教学重点：1、串七种基本操作的定义2、串的定长顺序存储3、串的堆存储结构教学难点：1、串七种基本操作的定义2、串的堆存储结构作业及参考书：对串的操作的应用数据结构算法实现及解析/高一凡编著教具：多媒体板书课堂类型：讲授 教学过程：引入展开举例小结作业一、引入约5min计算机上的非数值处理的对象基本上都是字符串数据。二、讲课进程设计4.1串的抽象数据类型的定义1.定义约IOmin 串、串长、空串、子串、主串、位置、相等、空格串2.串的抽象数据类型 的定义约 1 Omin StrASSign(T, Char

33、S) StrCOPy (T, S) DeStrOyString (S) StrEmPty(S) StrCOmPare(S,T) StrLength(S) COnCat(T,S 1 ,S2) SUbString (Sub,S,pos,len) IndeX(S,T,pos) RePIaCe(S,T,V) StrlnSert (S, pos, T) StrDelete (S, pos, Ien) ClearString(S) 4.2串的表示和实现4.2.1、串的定长顺序存储表示 约15min 1.串联接2.求子串422、串的堆分配存储表示约20min通常,C语言中提供的串类型就是以这种存储方式实现的

34、。系统利用函数malloc() 和free()进行吊值空间的动态管理，为每一个新产生的串分配一个存储区，称串值共享的 存储空间为“堆”。423、串的块链存储表示约IOmin也可用链表来存储串值，由于串的数据元素是一个字符，它只有8位二进制数， 因此用链表存储时，通常一个结点中存放的不是一个字符，而是一个子串。4.4串操作应用举例4.4.1文本编辑约20min可用于文本编辑的程序很多，功能强弱差别很大，但基本操作是一致的：都包括 串的查找，插入和删除等基本操作。对用户来讲，一个文本(文件)可以包括若干页，每页包括若干行，每行包括若干文 字。欢迎关注作者！作者毎天都会史新粘品文苹!对文本编辑程序来

35、讲，可把整个文本看成一个长字符串，称文本串，页是文本串的子 串，行乂是页的子串。为简化程序复杂程度，可简单地把文本分成若干行。三、小结约5min 1.熟悉串的七种基本操作的定义，并能利用这些基本操作来实现吊的其它各种操 作的方法。2. 熟练掌握在串的定长顺序存储结构上实现串的各种操作的方法。3. 了解串的堆存储结构以及在其上实现串操作的基本方法。4. 了解串操作的应用方法和特点。四、作业约5min假设有如下的串说明：chai* sl30=tStocktom,CA, s230=MMarCh 5 1999, s330, *p; (1)在执行下列语句后， s3 的值是什么？StrCOPy(S3,si

36、); COnCat(S3,u,u); ColICat(S3,s2);(2)调用函数StrCOmPare(S 1 ,s2)的返回值是什么？(3)调用函数StrCOmPaIe(Sl5,tonu)的返回值是什么？调用函数Strlength(ConCat(Sl,s2)fiJ返回值是什么?课时授课计划2020-2020学年 第一学期第5周授课日期10月11日三星期月 日星期月 日星期月曰星期月曰星期班级信管 10-1基本课题数组教学的与要求：1、掌握数组的定义2、掌握数组的顺序表示方法教学重点：1、数组的定义2、数组的顺序表示方法教学难点：数组的顺序表示方法作业及参考书：数据结构算法实现及解析/高一凡编

37、著教具：多媒体板书课堂类型：讲授 教学过程：引入展开举例小结一、引入约5min山前儿章讨论的线性结构中的数据元素都是非结构的原子类型引入数组。二、讲课进程设计5.1数组的类型定义抽象数据类型定义约5minADTArray 数据对象：数据关系：)ADT Array 二维数组的定义：约 IOmin 数据对: D= aij 0ibl-l, 0 jb2-l数 据关系:R = ROW, COL ROW= ai,j,ail,j 0ibl-2, 0jb2-l） COL= ai,j,ai,j+ll 0ibl-l,0jl)性质2 :深度为k的二叉树上至多含2k-l个结点(1)。性质3 :对任何一棵二叉树，若它含

38、有n个叶子结点(0度结点)、n2个度为2的 结点，则必存在关系式：0 = n2+lo两类特殊的二义树：满二叉树：指的是深度为k且含有2k-l个结点的二叉树。完全二叉树：树中所含的个结点和满二叉树中编号为1至的结点一一对应。(编号的规则为，由上到下，从左到右。)性质4 ：具有n个结点的完全二叉树的深度 为 elog2nu +1。性质5 :若对含n个结点的完全二叉树从上到下且从左至右进行1至n的编号， 则对完全二叉树中任意一个编号为i的结点：(1)如i=l,则序号为i的结点是根结点， 无双亲结点；如订，则序号为i的结点的双亲结点序号为。(2)如2in,则序号为i的结点无左孩 子；如2in,则序号为

39、i的结点的左孩子结点的序号为2xi。(3)如2i+ln,则序号为i 的结点无右孩子；如2iln,则序号为i的结点的右孩子结点的序号为2il 6.2.3二义树的存储结 构约25min 1.二叉树的顺序存储表示2、二叉树的链式存储表示1).二义链表2).三 叉链表3).双亲链表4).线索链表三、小结约5min 1.树、二叉树的定义2、二义树的性质3、存储结构四、作业约5min 1.一棵度为2的树与一棵二叉树有何区别？ 2.试分别画出具有3个结点的二叉树 和3个结点的二义树的所有不同形态。课时授课计划2020-2020学年第一学期第7周授课日期10月25日三 星期月 日星期月 日星期月 日星期月 日

40、星期班级信管10-1基本课题 遍历二叉树和线索二叉树 教学目的与要求：1. 遍历二义树是二义树各种操作的基础。掌握各种遍历策略的递归算法，灵活运用遍 历算法实现二叉树的其它操作。2. 理解二义树线索化的实质熟练掌握二叉树的线索化过程以及在中序线索化树上找 给定结点的前驱和后继的方法。教学重点：1. 遍历二叉树是二叉树各种操作的基础。2. 各种遍历策略的递归算法，运用遍历算法实现二叉树的其它操作。教学难点：各种遍历策略的递归算法，运用遍历算法实现二义树的其它操作。二叉树的线索化过程以及在中序线索化树上找给定结点的前驱和后继的方法。作业及参考书：写出所给二叉树的前、中、后序的序列数据结构算法实现及

41、解析/高一凡编著教 具：多媒体板书课堂类型：讲授 教学过程：引入展开举例小结一作业一、引入约3min山二义树的结构引出对每个结点的遍历。二、讲课进程设计6.3遍历二义树和线索二叉树6.3.1二义树的遍历一、问题的提 出约7min顺着某一条搜索路径巡访二义树中的结点，使得每个结点均被访问一次，而且仅被访问一次。(将树线性化)对“二叉树”而言，可以有三条搜索路径：01.先上后下的按层次遍历；0 2.先左（子树）后右（子树）的遍历；0 3.先右（子树）后左（子树）的遍历。二、先左后右的遍历算法约IOmin先（根）序的遍历算法若二义树为空树，则空操 作；否则（1）访问根结点；（2）先序遍历左子树；（3

42、）先序遍历右子树。中（根）序的遍历算法若二义树为空树，则空操作；否则（1）中序遍历左子树；（2）访问根结点；（3）中序遍历右子树。后（根）序的遍历算法若二叉树为空树，则空操作；否则（1）后序遍历左子树；（2）后序遍历右子树；（3）访问根结点。三、算法的递归描述约IOmin总结：无论先序、中序、后序遍历二叉树，遍历时的 搜索路线是相同的：从根结点出发，逆时针延二义树外缘移动对每个结点均途径三次。先序遍历：第一次经过结点时访问。中序遍历：第二次经过结点时访问。后序遍历：第三次经过结点时访问。四、中序遍历算法的非递归描述约IOmin五、遍历算法的应用举例约30minl、统 计二义树中叶子结点的个数（

43、先序遍历）先序（或中序或后序）遍历二义树，在遍历过程中查 找叶子结点，并计数。曲此，需在遍历算法中增添一个“计数”的参数，并将算法中“访问 结点”的操作改为：若是叶子，则计数器增1。2、求二义树的深度（后序遍历）算法基本思想：首先分析二义树的深度和它的左、右子 树深度之间的关系。3、复制二叉树（后序遍历）其基本操作为：生成一个结点。4、建立二义树的存储结构P不同的定义方法相应有不同的存储结构的建立算法按 给定的表达式建相应二义树山先缀表示式建树山原表达式建树我们已经知道二义树结 构和它的某个遍历序列不存在一一对应的关系，但若已知一个二义树的前序序列和中序序 列，却一定可以惟一确定一个二叉树的结

44、构。6.3.2线索二叉树约20min 何谓线索二叉树？遍历二义树的结果是，求得结点的 一个线性序列。如何保存这种在遍历过程中得到的信息？最简单的方法是在每个结点上增加二 个指针域：fwd和bkwd用来指示此结点在遍历中的前驱和后继结点。线索链表的遍历算法山于在线索链表中添加了遍历中得到的“前驱”和“后继”的 信息，从而简化了遍历的算法。如何建立线索链表？结索化的实质是将二义链表中的空指针改为指向前驱或后继 的线索，而前驱或后继的信息只有在遍历时才能得到，因此线索化的过程即为在遍历的过 程中修改空指针的过程。为了记下遍历过程中访问结点的先后关系，附设一个指针Pre始 终指向刚刚访问过的结点，若指

45、针P指向当前访问的结点，则Pre指向它的前驱。山此在 中序遍历过程中修改结点的左、右指针域，以保存当前访问结点的“前驱”和“后继”信息。 遍历过程中，附设指针Pe并始终保持指针Pre指向当前访问的、指针P所指结点的前驱。三、小结约7min 1.遍历的总结2、线索化的总结四、作业1、对所给出的二义树写出前、中、 后序的遍历序列。课时授课计划2020-2020学年第一学期第7周授课日期11月1日三 星期月 日星期月 日星期月 日星期月 日星期班级信管10-1基本课题 树和森林 教学的与要求：1. 熟悉树的各种存储结构及其特点，掌握树、森林与二义树的转换方法。2. 学会编写实现树的各种操作的算法。教

46、学重点：1、树、森林与二叉树的转换方法2.学会编写实现树的各种操作的算法。教学难点：1、树、森林与二叉树的转换方法2.学会编写实现树的各种操作的算法。欢迎关注作者！作者每天都会史新粘品文克!作业及参考书：树和森林的转换数据结构算法实现及解析/高一凡编著教具：多媒体板书课堂类型：讲授 教学过程：引入展开举例小结作业一、引入约5min由前面树、二叉树的回顾引入 二、讲课进程设Ii 6.4树和森林641树的存储结 构约25min 1 双亲表示法以一组连续的存储空间存放树的结点，每个结点中附设一个指针指示其双亲结点在 这连续的存储空间中的位置（下标，这种结构属静态链表），可形式表示如下：typrdef StrUCt tnode datatype