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

1、数据结构（C语言版）教案数据结构（c语言版）教案2020至2020学年第一学期教案课程名称数据结构使用教材数据结构（c语言版）教学时数56课程性质必修任课班级（人数）信管（53人）信息系（部）信管教研室任课教师山东科技大学泰山科技学院课时授课计划2020-2020学年第二学期第1周授课日期2月20日星期1月日星期月日星期月日星期月日星期班级信管10-1基本课题第1章绪论1.1-1.2教学目的与要求：了解数据结构的基本概念2.理解常用术语教学重点：数据结构的基本概念和术语教学难点：数据元素之间的四种结构关系作业及参考书：1、什么是数据结构？数据结构算法实现及解析/高一凡编著教具：多媒体板书课堂类

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

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

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

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

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

7、构造复数Z,其实部和虚部分别被赋以参数v1和v2的值。DestroyComplex(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语言作简要说明约18min1.预定义常量及类型2、数据结构的存储结构typedef3、算法描述为以下的函数形式：在算法描述中可以使用的赋值语

8、句形式有：在算法描述中可以使用的选择结构语句形式有：在算法描述中可以使用的循环结构语句形式有：在描述算法中可以使用的结束语句形式有：在算法描述中可以使用的输入输出语句形式有：在算法描述中使用的注释格式为：在算法描述中可以使用的扩展函数有：11.逻辑运算约定1.4算法和算法分析1.4.1、算法约10min算法是为了解决某类问题而规定的一个有限长的操作序列。一个算法必须满足以下五个重要特性：1有穷性2确定性3可行性4有输入5有输出1.4.2、算法设计的原则约10min设计算法时，通常应考虑达到以下目标：1正确性2.可读性3健壮性4高效率与低存储量需求1.4.3、算法效率的衡量方法和准则约20min

9、通常有两种衡量算法效率的方法事后统计法缺点：1必须执行程序2其它因素掩盖算法本质事前分析估算法和算法执行在计算算法的存储量包括:1输入数据所占空间2程序本身所占空间3辅助变量所占空间四、小结：约5min1.理解算法五个要素的确切含义。掌握计算语句频度和估算算法五、作业约5min1、试编写算法求一元多项式Pn(x)=a0+alx+a2x2+a3x3+.anxn的值Pn(xO)，并确定算法中的每一语句的执行次数和整个算法的试讨论这两种方法的优缺点，并在本题算法中以你认为较好的一种方式实现输入和输出。课时授课计划2020-2020学年第二学期第2周授课日期2月27日星期月日星期月日星期月日星期月日星

10、期班级信管10-1基本课题线性表的类型定义线性表的顺序表示和实现教学目的与要求：1、掌握线性表的概念和类型定义2、掌握线性表的顺序表示和实现方法教学重点：线性表的类型定义线性表的顺序表示和实现方法教学难点：线性表的类型定义线性表的顺序存储的实现方法作业及参考书：数据结构算法实现及解析/高一凡编著教具：多媒体板书课堂类型：讲授教学过程：复习引入展开举例小结一、引入约3min由顺序的算法引入二、讲课进程设计2.1线性表的类型定义12.1.1线性表的定义约27min线性表是由n(nNO)个类型相同的数据元素组成的有限序列。抽象数据类型线性表的定义如下：ADTList数据对象D=aiIaiGElemS

11、et,i=l,2,.,n,n0称n为线性表的表长；称n=0时的线性表为空表。数据关系Rl=ai-1,ailai-1,ai$D,i=2,.,n基本操作：结构初始化操作：InitList(L)操作结果：构造一个空的线性表L。结构销毁操作：DestroyList(L)初始条件：线性表L已存在。操作结果：销毁线性表L。引用型操作ListEmpty(L)(线性表判空)ListLength(L)(求线性表的长度)PriorElem(L,cur_e,pre_e)(求数据元素的前驱)NextElem(L,cur_e,next_e)(求数据元素的后继)GetElem(L,i,e)(求线性表中某个数据元素)Loc

12、ateElem(L,e,compare()(定位函数)ListTraverse(L,visit()(遍历线性表)加工型操作ClearList(L)(线性表置空)PutElem(L,i,e()改变数据元素的值)ListInsert(L,i,e()插入数据元素)ListDelete(L,i,e)(删除数据元素)2.1.2举例约lOmin两个线性表合并LA和LB2.2线性表的顺序表示和实现2.2.1顺序映象约15min以x的存储位置和y的存储位置之间某种关系表示逻辑关系x,y。最简单的一种顺序映象方法是：令y的存储位置和x的存储位置相邻。线性表的基本操作在顺序表中的实现InitList(L)/结构初

13、始化LocateElem(L,e,compare()/查找ListInsert(L,i,e)/插入元素ListDelete(L,i)/删除元素2.1.1、线性表操作约20minListInsert(L,i,e)的实现：首先分析插入元素时，线性表的逻辑结构发生什么变化？线性表操作ListDelete(L,i,e)的实现：首先分析：删除元素时，线性表的逻辑结构发生什么变化？线性表类型的实现2.1.2、线性表顺序存储结构的特点：约2Omin它是一种简单、方便的存储方式。它要求线性表的数据元素依次存放在连续的存储单元中，从而利用数据元素的存储顺序表示相应的逻辑顺序，这种存储方式属于静态存储形式。暴露的

14、问题(1)在做插入或删除元素的操作时，会产生大量的数据元素移动；(2)对于长度变化较大的线性表，要一次性地分配足够的存储空间，但这些空间常常又得不到充分的利用；(3)线性表的容量难以扩充。三、小结约5min1.了解线性表的逻辑结构特性是数据元素之间存在着线性关系，在计算机中表示这种关系的两类不同的存储结构是顺序存储结构和链式存储结构。用前者表示的线性表简称为顺序表，用后者表示的线性表简称为链表。2.熟练掌握这两类存储结构的描述方法，以及线性表的各种基本操作的实现。课时授课计划2020-2020学年第二学期第2周授课日期3月3日星期月日星期月日星期月日星期月日星期班级信管10-1基本课题线性表的

15、链式表示和实现一元多项式的表示及相加教学目的与要求：1、掌握线性链表、单链表、静态链表的概念、表示及实现方法。2、掌握循环链表的概念3、掌握双向链表的表示与实现教学重点：1、线性链表之单链表的表示及实现方法。2、双向链表的表示与实现教学难点：1、线性链表2、双向链表的存储表示作业及参考书：写一算法将单链表中值重复的结点删除，使所得的结果表中各结点值均不相同。数据结构算法实现及解析/高一凡编著教具：多媒体板书课堂类型：讲授教学过程：复习引入展开举例小结作业一、复习约5min复习线性表有的概念二、引入约2min由线性表的表示不方便引入三、讲课进程设计2.3线性表的链式表示和实现线性表顺序存储结构的

16、特点：约10min它是一种简单、方便的存储方式。它要求线性表的数据元素依次存放在连续的存储单元中，从而利用数据元素的存储顺序表示相应的逻辑顺序，这种存储方式属于静态存储形式。暴露的问题(1)在做插入或删除元素的操作时，会产生大量的数据元素移动；(2)对于长度变化较大的线性表，要一次性地分配足够的存储空间，但这些空间常常又得不到充分的利用；(3)线性表的容量难以扩充。2.3.1、单链表约10min用一组地址任意的存储单元存放线性表中的数据元素(这组存储单元可以是连续的也可以是不连续的)。2.3.2、结点和单链表的C语言描述约10min2.3.3、单链表操作的实现约13min因此生成链表的过程是一

17、个结点“逐个插入”的过程。操作步骤：1、建立一个“空表”；2、输入数据元素an,建立结点并插入；3、输入数据元素an-1，建立结点并插入；4、依次类推,直至输入a1为止。2.3.4、其它形式的链表约5min1.循环链表2.双向链表2.3.5、有序表类型约5min2.4一元多项式的表示2.4.1一元多项式约20min在计算机中,可以用一个线性表来表示:P=(p0,p1,pn)抽象数据类型一元多项式的定义如下：ADTPolynomial数据对象：D=ailaiGTermSet,i=l,2,.,m,m0TermSet中的每个元素包含一个表示系数的实数和表示指数的整数数据关系：Rl=ai-1,aila

18、i-1,ai$D,i=2,.,n且ai-1中的指数值Vai中的指数值基本操作：CreatPolyn(P,m)操作结果：输入m项的系数和指数,建立一元多项式P。DestroyPolyn(P)初始条件：一元多项式P已存在。操作结果：销毁一元多项式P。PrintPolyn(P)初始条件：一元多项式P已存在。操作结果：打印输出一元多项式P。PolynLength(P)初始条件：一元多项式P已存在。操作结果：返回一元多项式P中的项数。AddPolyn(Pa,Pb)初始条件：一元多项式Pa和Pb已存在。操作结果：完成多项式相加运算，即：Pa=Pa+Pb，并销毁一元多项式Pb。SubtractPolyn(P

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

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

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

22、符，“”为退行符。例四、迷宫求解约10min假设以栈S记录“当前路径”，则栈顶中存放的是“当前路径上最后一个通道块”。“纳入路径”的操作即为“当前位置入栈；“从当前路径上删除前一通道块”的操作即为“出栈“。例五、表达式求值约10min任何一个表达式都是由操作数(operand)、运算符(operator)和界限符(delimiter)组成。例六、实现递归约10min递归函数的实现一个递归函数的运行过程类似于多个函数的嵌套调用，差别仅在于“调用函数和被调用函数是同一个函数”。为了保证“每一层的递归调用”都是对“本层”的数据进行操作，在执行递归函数的过程中需要一个“递归栈”。三、小结约5min1.

23、掌握栈和队列类型的特点，并能在相应的应用问题中正确选用它们。熟练掌握栈类型的两种实现方法，特别应注意栈满和栈空的条件以及它们的描述方法。四、作业约5min1、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，a12、栈的特点是()。课时授课计划2020-2020学年第一学期第3周授课日期9月27日三星期月日星期月日星期月日星期月日星期班级信管10-1基本课题队列教学目的与要求：1.熟练掌握循环队列和链队列的基本操作实现算法。理解递归算法执行过程中

24、栈的状态变化过程。教学重点：1链队的表示与实现教学难点：.1。链队的表示与实现作业及参考书：1栈与队列的比较2读程序段数据结构算法实现及解析/高一凡编著教具：多媒体板书课堂类型：讲授教学过程：引入展开举例小结作业一、引入约5min在日常生活中，为了维持正常的社会秩序而出现的常见现象是什么？是“排队“。在计算机程序中，模拟排队的数据结构是“队列“。二、讲课进程设计3.4队列1队列的定义约10min2队列的抽象类型定义约15min3.队列的基本操作：约20minInitQueue(Q)操作结果：构造一个空队列Q。DestroyQueue(Q)初始条件：队列Q已存在。操作结果：队列Q被销毁，不再存在

25、。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()队列类型的实现

26、4.链队列链式映象约15min5.循环队列顺序映象约20min队列在程序设计中的一个典型应用例子是作业排队问题。三、小结约5min1.熟练掌握循环队列和链队列的基本操作实现算法，特别注意队满和队空的描述方法。2.理解递归算法执行过程中栈的状态变化过程。四、作业约10min1、线性表、栈和队列都是()结构,可以在线性表的()位置插入和删除元素，对于栈只能在()插入和删除元素，对于队列只能在()插入元素和()删除元素。2、指出下述程序段的功能是什么?(1)voidDemo1(SeqStack*S)inti;arr64;n=0;while(StackEmpty(S)arrn+=Pop(S);for(

27、i=0,ii+)Push(S,arri);/Demo1课时授课计划2020-2020学年第一学期第4周授课日期月日星期月日星期月日星期月日星期月日星期班级信管10-1基本课题实验二栈和队列的总结复习教学目的与要求：1、深入了解栈和队列的特征，以便在实际问题背景下灵活运用它们；2、巩固这两种结构的构造方法，接触较复杂问题的递归算法设计。教学重点：巩固这两种结构的构造方法，接触较复杂问题的递归算法设计。教学难点：巩固这两种结构的构造方法，接触较复杂问题的递归算法设计。作业及参考书：数据结构算法实现及解析/高一凡编著教具：课堂类型：教学过程：停车场管理问题描述设停车场内只有一个的停放n辆汽车的狭长通

28、道，且只有一个大门可供汽车进出。汽车在停车场内按车辆到达测试数据设n=2,输入数据为：(A,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)。其中，A，表示到达；D，表示离去，E，表示输入结束。基本要求以栈模拟停车场,以队列模拟车场外的便道,按照从终端读入的输入数据序列进行模拟管理。每一组输入数据包括三个数据项：汽车“到达”或“离去”信息、汽车牌照号码及到达或离去的时刻,对每一组输入数据进行操作后的输出数据为：若是车辆到达,则输出汽车在停车场内或便道上的停车位置；若是车离去；则输出汽车在停

29、车场内停留的实现提示需另设一个栈,临时停放为给要离去的汽车让路而从停车场退出来的汽车,也用顺序存储结构实现。输入数据按到达或离去的时刻有序。栈中每个元素表示一辆汽车,包含两个数据项：汽车的牌照号码和进入停车场的时刻。选作内容(1)两个栈共享空间,思考应开辟数组的空间是多少？(2)汽车可有不同种类,则它们的占地面积不同,收费标准也不同,如1辆客车和1.5辆小汽车的占地面积相同,1辆十轮卡车占地面积相当于3辆小汽车的占地面积。汽车可以直接从便道上开走,此时派在它前面的汽车要先开走让路,然后再依次排到队尾。停放在便道上的汽车也收费,收费标准比停放在停车场的车低,请思考如何修改结构以满足这种要求。课时

30、授课计划2020-2020学年第一学期第4周授课日期10月8日日星期月日星期月日星期月日星期月日星期班级信管10-1基本课题串教学目的与要求：1、熟悉串七种基本操作的定义,并能利用这些基本操作实现传的其他各种操作的方法。2、熟悉掌握在串的定长顺序存储结构上实现串的各种操作的方法。3、掌握串的堆存储结构以及在其上实现串的各种操作的基本方法。教学重点：1、串七种基本操作的定义2、串的定长顺序存储3、串的堆存储结构教学难点：1、串七种基本操作的定义2、串的堆存储结构作业及参考书：对串的操作的应用数据结构算法实现及解析/高一凡编著教具：多媒体板书课堂类型：讲授教学过程：引入展开举例小结作业一、引入约5

31、min计算机上的非数值处理的对象基本上都是字符串数据。二、讲课进程设计4.1串的抽象数据类型的定义1.定义约10min串、串长、空串、子串、主串、位置、相等、空格串2.串的抽象数据类型的定义约10minStrAssign(T,chars)StrCopy(T,S)DestroyString(S)StrEmpty(S)StrCompare(S,T)StrLength(S)Concat(T,S1,S2)SubString(Sub,S,pos,len)Index(S,T,pos)Replace(S,T,V)StrInsert(S,pos,T)StrDelete(S,pos,len)ClearStrin

32、g(S)4.2串的表示和实现4.2.1、串的定长顺序存储表示约15min1.串联接2.求子串4.2.2、串的堆分配存储表示约20min通常,C语言中提供的串类型就是以这种存储方式实现的。系统利用函数malloc()和free()进行串值空间的动态管理，为每一个新产生的串分配一个存储区，称串值共享的存储空间为“堆”。4.2.3、串的块链存储表示约10min也可用链表来存储串值,由于串的数据元素是一个字符,它只有8位二进制数,因此用链表存储时,通常一个结点中存放的不是一个字符,而是一个子串。4.4串操作应用举例4.4.1文本编辑约20min可用于文本编辑的程序很多,功能强弱差别很大,但基本操作是一

33、致的：都包括串的查找,插入和删除等基本操作。对用户来讲,一个文本(文件)可以包括若干页,每页包括若干行,每行包括若干文字。对文本编辑程序来讲，可把整个文本看成一个长字符串，称文本串，页是文本串的子串，行又是页的子串。为简化程序复杂程度，可简单地把文本分成若干行。三、小结约5min1.熟悉串的七种基本操作的定义，并能利用这些基本操作来实现串的其它各种操作的方法。熟练掌握在串的定长顺序存储结构上实现串的各种操作的方法。了解串的堆存储结构以及在其上实现串操作的基本方法。了解串操作的应用方法和特点。四、作业约5min假设有如下的串说明：charsl30=“Stocktom,CA“，s230=“Marc

34、h51999”，s330,*p;(1)在执行下列语句后，s3的值是什么？strcopy(s3,s1);concat(s3,“,“);concat(s3,s2);(2)调用函数strcompare(sl,s2)的返回值是什么？(3)调用函数strcompare(s15,“ton“)的返回值是什么？调用函数strlength(concat(s1,s2)的返回值是什么？课时授课计划2020-2020学年第一学期第5周授课日期10月11日三星期月日星期月日星期月日星期月日星期班级信管10-1基本课题数组教学目的与要求：1、掌握数组的定义2、掌握数组的顺序表示方法教学重点：1、数组的定义2、数组的顺序表

35、示方法教学难点：数组的顺序表示方法作业及参考书：数据结构算法实现及解析/高一凡编著教具：多媒体板书课堂类型：讲授教学过程：引入展开举例一一小结一、引入约5min由前几章讨论的线性结构中的数据元素都是非结构的原子类型引入数组。二、讲课进程设计5.1数组的类型定义抽象数据类型定义约5minADTArray数据对象：数据关系：ADTArray二维数组的定义：约10min数据对象:D=aij|0ib1-1,0jb2-1数据关系：R=ROW,COLROW=ai,j,ai+l,j|0ib1-2,0jb2-1COL=ai,j,ai,j+ll0ib1-1,0j1)性质2:深度为k的二叉树上至多含2k-l个结点

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

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

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

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

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

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

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

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

44、点：1、树、森林与二叉树的转换方法2学会编写实现树的各种操作的算法。作业及参考书：树和森林的转换数据结构算法实现及解析/高一凡编著教具：多媒体板书课堂类型：讲授教学过程：引入展开举例小结作业一、引入约5min由前面树、二叉树的回顾引入二、讲课进程设计6.4树和森林641树的存储结构约25min1、双亲表示法以一组连续的存储空间存放树的结点，每个结点中附设一个指针指示其双亲结点在这连续的存储空间中的位置（下标，这种结构属静态链表）,可形式表示如下：typrdefstructtnodedatatypedata;intparent;treen2、孩子表示法用多重链表表示。有两种方法：同构：按最大度的

45、结点设置各结点结构，即一个数据域和d个指针域，这容易造成空间浪费；异构：结点有几棵子树设几个指针，这样操作困难。可将其子女链在一个单链表中。其形式描述如下：typrdefstructtagnode/*表结点*/intchild;structtagnode*next;node,*link;typedefstruct/*头结点*/datatypedata;linkheadptr;headnode;typedefheadnodechildlinkmaxnode;/*表头数组*/带双亲的孩子链表表示法：typedefstruct/*头结点*/datatypedata;intparent;linkhea

46、dptr;headnode1;3、孩子兄弟表示法该方法又称二叉树表示法，或二叉链表表示法，即以二叉链表作存储结构，结点的两个链域分别指向该结点的第一个孩子和下一个兄弟，分别命名为fch和nsib。可形式描述如下：typedefstructtreenodedatatypedata;structtreenode*fch,*nsib;treenode,*tree;树的这种表示本质上是二叉树的二叉链表表示。由于二叉树和树这种存储结构的一致性，从而导致树和二叉树可以相互转换。642森林与二叉树的相互转换约30min1、森林转为二叉树树（树林）转换成二叉树时结果是唯一的。其转换可以递归的描述如下：若树（树

47、林）为空，则二叉树为空；否则，树（树林）中第一棵树的根是二叉树的根，第一棵树除去根结点后的子树林是二叉树的左子树，树林中除去第一棵树后的树林形成二叉树的右子树。形象的说转换过程可用下面的“三步曲”来说明：三步曲：连线切线旋转连线：将兄弟结点连接起来切线：保留双亲到第一个子女的连线，将双亲到其它子女的连线切掉。旋转：以根为轴，平面向下顺时针方向旋转450。2、二叉树转为树林二叉树转换成树（树林）时结果也是唯一的。其转换可以递归的描述，若二叉树为空，则树（树林）为空；否则，二叉树的根是树（树林）中第一棵树的根，二叉树的左子树构成树（树林）中第一棵树除去根结点后的子树林，二叉树的右子树构成树林中除去

48、第一棵树后的树林。形象的说是上面三步曲的逆。643树和森林的遍历约30min树的遍历方法也可分为“宽度优先法”和“深度优先法”两类。前者指从（根）第一层开始，由上到下，从左往右逐个结点的遍历；后者又可分为先根次序和后根次序。（1）先根次序的遍历（相当于对其相应的二叉树的先序遍历）若树（森林）为空则空操作，否则：访问左面第一棵树的根；按先根次序从左到右遍历此根下的子树；按先根次序从左到右遍历除第一棵树外的树（森林）。（2）后根次序的遍历（相当于对其相应的二叉树的中序遍历）若树（森林）为空则空操作，否则：按后根次序从左到右遍历最左面的树下的子树；访问最左面树的根；按后根次序从左到右遍历除第一棵树外

49、的树（森林）；三、小结约7min1、树的存储2、树与森林之间的转换3、树和森林的遍历四、作业约3min1完成由树和森的转换课时授课计划2020-2020学年第一学期第8周授课日期11月3日五星期月日星期月日星期月日星期月日星期班级信管10-1基本课题哈夫曼树教学目的与要求：1、掌握哈夫曼树的构造方法2、掌握哈夫曼编码3、带权路径的计算4、了解最优树的特性教学重点：1、哈夫曼树的构造2、掌握建立最优树和哈夫曼编码的方法。教学难点：1、建立最优树和哈夫曼编码的方法2、带权路径的计算作业及参考书：1、构造一棵哈夫曼树并且计算其权值数据结构算法实现及解析/高一凡编著教具：/、多媒体板书课堂类型：讲授教

50、学过程：引入展开举例小结作业一、引入约5min由最优树概念的提出引入哈夫曼树二、讲课进程设计66哈夫曼树及其应用661最优二叉树（哈夫曼树-带权路径长度最短的树）1、哈夫曼树的基本概念约20min（1）路径从树中一个结点到另一个结点之间的分支。（2）路径长度路径上的分支数目称为路径长度。（3）树的路径长度从树根到每一结点的路径长度之和，称为树的路径长度，完全二叉树是路径长度最短的二叉树。（4）结点的带权路径长度从该结点到树根之间的路径长度和结点上权的乘积。（5）树的带权路径长度树中所有叶子结点的带权路径长度之和，通常记为WPL=wili，（6）哈夫曼树（最优二叉树）带权路径长度之和最小的二叉树

51、称为哈夫曼树（最优二叉树）（7）哈夫曼编码在哈夫曼树上，左分枝为0，右分枝为1，从根结点开始，直到叶子结点所组成的编码序列，称为叶子结点的哈夫曼编码。2、哈夫曼树在判定问题中的应用约15min将百分制转为五级记分制的例子。说明哈夫曼树判定次数最少的树（即带权路径长度最短、最节省计算（2）在F中删除这两棵子树，同时将新得到的二叉树加入F中。（3）重复（2）和（3），直到F中只剩一棵树（即哈夫曼树）为止。举例说明这一过程：应该说明，哈夫曼树的形态不是唯一的，但对具有一组权值的各哈夫曼树的WPL是唯一的。662哈夫曼编码1、哈夫曼编码提出的背景约lOmin(1)如何使电报编码变短，非前缀编码出现二义

52、性。(2)用二叉树可以构造前缀编码。(3)由哈夫曼树得到最优编码。2、构造哈夫曼树和哈夫曼编码的算法约2Omin前缀编码：任何一个字符的编码都不是同一字符集中另一个字符的编码的前缀。如ABCD四个字符的使用率由高到低，编码为A-0B-10C-110D-111利用赫夫曼树可以构造一种不等长的二进制编码，并且构造所得的赫夫曼编码是一种最优前缀编码，即使所传电文的总长度最短。哈夫曼编码算法的实现：由于哈夫曼树中没有度为1的结点，则一棵有n个叶子的哈夫曼树共有2xn1个结点，可以用一个大小为2xn1的一维数组存放哈夫曼树的各个结点。由于每个结点同时还包含其双亲信息和孩子结点的信息，所以构成一个静态三叉

53、链表。三、小结约5min1、构造哈夫曼树2、哈夫曼编码四、作业约5min1、求由带权9、1、3、5、6的5个叶子节点生成的哈夫曼树的带权路径长度。2、设哈夫曼树的叶节点数为nO，则它的节点总数为多少？课时授课计划2020-2020学年第一学期第8周授课日期10月27日五星期月日星期月日星期月日星期月日星期班级信管10-1基本课题树与二叉树复习习题课教学目的与要求：1熟悉二叉树结点的结构和对二叉树的基本操作。2掌握对二叉树每一种操作的具体实现。3学会利用递归方法编写对二叉树这种递归数据结构进行处理的算法。教学重点：1学会利用递归方法编写对二叉树这种递归数据结构进行处理的算法。教学难点：1、利用递

54、归方法编写对二叉树这种递归数据结构进行处理的算法。作业及参考书：数据结构算法实现及解析/高一凡编著教具：课堂类型：总结复习教学过程：提出问题对问题提示完成问题检查二叉树基本操作复习目的4熟悉二叉树结点的结构和对二叉树的基本操作。5掌握对二叉树每一种操作的具体实现。6学会利用递归方法编写对二叉树这种递归数据结构进行处理的算法。复习内容该程序的功能是实现二叉树结点的类型定义和对二叉树的基本操作。该程序包括二叉树结构类型以及每一种操作的具体的函数定义和主函数。/*定义DataType为char类型*/typedefcharDataType;/*二叉树的结点类型*/typedefstructBitNo

55、deDataTypedata;structBitNode*lchild,*rchild;BitNode,*BitTree;/*初始化二叉树，即把树根指针置空*/voidBinTreeInit(BitTree*BT)/*按先序次序建立一个二叉树*/voidBinTreeCreat(BitTree*BT)/*检查二叉树是否为空*/intBinTreeEmpty(BitTree*BT)/*按任一种遍历次序(包括按先序、中序、后序、按层次)输出二叉树中的所有结点*/voidBinTraverse(BitTree*BT)/*求二叉树的深度*/intBinTreeDepth(BitTreeBT)/*求二叉

56、树中所有结点数*/intBinTreeCount(BitTreeBT)/*清除二叉树，使之变为空树*/voidBinTreeClear(BitTree*课时授课计划2020-2020学年第一学期第11周授课日期11月8日三星期月日星期月日星期月日星期月日星期班级信管10-1基本课题图的定义和术语图的存储结构教学目的与要求：1、掌握图的定义及常用术语2、掌握图的二种存储表示法教学重点：1、图的常用术语2、图的数组表示及邻接表表示法教学难点：1、图的常用术语2、邻接表表示法作业及参考书：数据结构算法实现及解析/高一凡编著教具：多媒体板书课堂类型：讲授教学过程：引入展开举例小结作业一、引入约5min

57、由各城市之间的通信引出图二、讲课进程设计第七章图对图进行概述约5min图是一种比线性表和树都复杂的数据结构。在图结构中，结点之间的关系是任意的，图中任意两个元素之间都可能有关系。图的应用非常广泛。7.1图的定义和术语1、图的定义约5min图是一种数据结构，其形式化定义可写为Graph=(V,R)其中，V=x|xdatatypeR=VRVR=x,ylP(x,y)(x,yV)在图中，数据元素常称为顶点，V是顶点的有穷集合；R是边(弧)的有穷集合。2、抽象数据类型图的定义约5minADTGraph数据对象V：数据关系R：基本操作P：ADTGraph3、图的术语概念约15min(1)有向图、无向图弧：

58、x,y边(x,y)。有(无)向完全图稀疏图稠密图子图无向完全图：n个顶点n(n-1)/2条边；有向完全图：n个顶点n(n-l)条弧；权、网和边(弧)相关的数叫权，带权的图称网。邻接、邻接点无向图：一条边连起来的两个顶点，互称邻接点；有向图：若从顶点x到顶点y有一条弧，则说顶点x邻接到顶点y,而顶点y邻接自顶点x。度、出度、入度无向图中和顶点相关的边(e)的个数叫顶点的度。e=有向图中从顶点出发的弧的个数叫该顶点的出度，入到该顶点的弧的个数叫该顶点的入度。TD(v)=ID(v)+OD(v)(6)路径、路径长度、回路(环)、简单路径(7)连通、连通图、连通分量无向图顶点vl到顶点v2有路径，则说v

59、l和v2连通。若任意两个顶点都连通，则说该图是连通的。连通分量是无向图中的极大连通子图。(8)强连通图、强连通分量(9)生成树、有向树、生成森林一个连通图的生成树是一个极小连通子图，它含有图的全部顶点，但只有足以构成一棵树的n-l条边。若有向图中只有一个顶点的入度为0其余顶点的入度均为1，则该有向图称为有向树。有向图的生成森林由若干棵有向树组成，含有图的全部顶点，但只有足以构成若干棵不相交的有向树的弧。72图的存储结构721图的顺序存储结构-数组表示法约20min1、数组表示法用两个数组分别表示数据元素的(顶点)的信息和边(弧)的信息若顶点只有编号信息，边(弧)只是有无，则可用下面的邻接矩阵来

60、表示。2、邻接矩阵的定义有n个顶点的图G=(V,VR)的邻接矩阵为n阶方阵，其定义为：0若(vi,vj)或vi,vjVR3、无向图邻接矩阵的性质(1)无向图的邻接矩阵是对称矩阵；（2）顶点vi的度是邻接矩阵中第i行（或第i列）的元素（1）之和。4、有向图邻接矩阵的性质（1）有向图的邻接矩阵不一定是对称矩阵；（2）顶点vi的出度是邻接矩阵中第i行元素之和，入度是邻接矩阵中第i列的元素之和5、网的邻接矩阵将邻接矩阵中的0、1换成权值，就是网的邻接矩阵。6、邻接矩阵的优缺点容易实现图的前4个操作。容易判定顶点间有无边（弧），容易计算顶点的度（出度、入度）；缺点是所占空间只和顶点个数有关，和边数无关，