数据结构（Java语言实现） 教案全套 陈锐 第1-8章 绪论、线性表-排序

教 案院（系：课程名称：数据结构教师姓名：授课时间:学年第一学期PAGEPAGE10目录课次内容页码1第1章绪论：预备知识补充；数据结构的研究内容;数据结构的基本概念与术语；22第1章绪论：数据类型和抽象数据类型；算法和算法分析；53第2章线性表：线性表的类型定义；104第2章线性表：线性表的顺序表示和实现；145第2章线性表：线性表的链式表示和实现；166第2章线性表：线性表的应用187第3章栈和队列：栈的定义、存储；228第3章栈和队列：栈的应用举例；栈与递归的实现；259第3章栈和队列：队列的定义、存储；队列的应用举例3210第4章串、数组和广义表：串的表示和实现；模式匹配算法；数组的存储；3411第4章串、数组和广义表：特殊矩阵和稀疏矩阵；广义表的逻辑结构和存储结构4212第5章树与二叉树：二叉树的定义和基本术语；二叉树的性质4513第5章树与二叉树：二叉树的存储结构5014第5章树与二叉树：遍历二叉树；线索二叉树；树和森林5215第5章树与二叉树：哈夫曼树及哈夫曼编码6016第6章图：图的定义和术语；图的存储结构6317第6章图：图的遍历；图的最小生成树；6618第6章图：最短路径；拓扑排序，关键路径7119第7章查找：基本概念，顺序查找；折半查找；7620第7章查找：二叉排序树，平衡二叉树8121第7章查找：散列表8522第8章排序：排序的基本概念，排序方法的分类；直接插入排序；折半插入排序，8923第8章排序：希尔排序；交换排序9224第8章排序：堆排序，归并排序；基数排序；排序方法总结比较94课次1计划课时2授课章节1;1.2数据结构的基本概念与术语；课程目标与毕业要求指标点课程目标：（1）理解数据结构与算法的基本概念，掌握常用基本数毕业要求指标点：1.3能够在对复杂工程问题的分析、推演中综合运用相关知识和数学模型方法。教学分析教学目标：1.了解数据结构研究的主要内容2.掌握数据结构中涉及的基本概念3.掌握算法、算法的时间复杂度及其分析的简易方法教学内容：数据结构的研究内容基本概念和术语抽象数据类型的表示与实现算法与算法分析教学重点：1.数据的逻辑结构2.数据的存储结构3.算法分析教学难点：1.算法分析教学方法、策略、过程设计教学方法：案例讲授+师生互动教学手段：PPT+板书由三个案例引入什么是数据结构？课后要求：作业：习题1.1，1.3预习：1.3数据类型和抽象数据类型；1.4算法和算法分析；实施情况、课后教学效果分析及下次课改进措施：附本课次教学内容：第一章 绪论数据结构讨论的范畴NiklausWirthAlgorithm+DataStructures=Programs程序设计:为计算机处理问题编制一组指令集算法:处理问题的策略数据结构:问题的数学模型例如:数值计算的程序设计问题结构静力分析计算─━线性代数方程组全球天气预报─━环流模式方程非数值计算的程序设计问题例一:求一组(n个)整数中的最大值算法:基本操作是“比较两个数的大小”模型：？例二：计算机对弈算法：对弈的规则和策略模型：？例三：足协的数据库管理算法：需要管理的项目？如何管理？用户界面？模型：？简言之，数据结构讨论描述现实世界实体的数学模型及其上的操作在计算机中的表示和实现。基本概念一、数据与数据结构数据:所有能被输入到计算机中，且被计算机处理的符号的集合是计算机操作的对象的总称是计算机处理的信息的某种特定的符号表示形式（Data1.1数据的逻辑结构1.3（2）BC3ABBA1.4（3）树形结构。该结构中的数据元素之间存在一种一对多的层次关系。这就像学校内部的组织结构，学校下面是教学院系、行政处室及一些研究所。树形结构如图1.5所示。（4）图结构。该结构中的数据元素是多对多的关系。城市之间的交通路线图就是多对CDACDB、、D1.6562集合 线性5621 3 9 ABCD139ABCDEF图1.3集合结构 图1.4性结构树A树ABCDEFG H I J K图DACEBF图1.5树形结构 图1.6图构abcdefghhead

图1.7顺序存储结构ab^h…ab^h图1.8链式存储结构课次2计划课时2授课章节第1章绪论：1.3数据类型和抽象数据类型；1.4算法和算法分析；课程目标与毕业要求指标点课程目标：（1）理解数据的逻辑结构和存储结构之间的关系，掌握运用数学知识进行算法性能分析的能力。毕业要求指标点：1.3能够在对复杂工程问题的分析、推演中综合运用相关知识和数学模型方法。教学分析教学内容:1、抽象数据类型2、算法与算法的衡量教学重点：1、算法与算法的衡量教学难点：1、抽象数据类型的定义2、算法效率的衡量方法和准则教学方法、策略、过程设计教学方法：讲授+师生互动教学手段：PPT+板书课后要求：作业：习题1.6预习：2.1线性表的类型定义实施情况、课后教学效果分析及下次课改进措施：附本课次教学内容：、抽象数据类型是指一个数学模型以及定义在此数学模型上的一组操作例如：矩阵+（求转置、加、乘、求逆、求特征值）构成一个矩阵的抽象数据类型数据结构+定义在此数据结构上的一组操作=抽象数据类型抽象数据类型的描述方法抽象数据类型可用（D，S，P）三元组表示其中，D是数据对象，S是D上的关系集，P是对D的基本操作集。ADT抽象数据类型名{}ADT抽象数据类型名其中，数据对象和数据关系的定义用伪码描述，基本操作的定义格式为基本操作名（参数表）初始条件：〈初始条件描述〉操作结果：〈操作结果描述〉基本操作有两种参数：赋值参数只为操作提供输入值；引用参数以&打头，除可提供输入值外，还将返回操作结果。例抽象数据类型三元组的定义：ADTComplex{数据对象：D＝{e1,e2｜e1,e2∈RealSet}数据关系：R1＝{<e1,e2>|e1是复数的实数部分,|e2是复数的虚数部分}基本操作：InitComplex(&Z,v1,v2)操作结果：构造复数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的和值。}ADTComplex抽象数据类型的两个特征:数据抽象数据封装将实体的外部特性和其内部实现细节分离，并且对外部养护隐藏其内部实现细节。抽象数据类型的表示和实现抽象数据类型可以通过固有数据类型(高级编程语言中已实现的数据类型)来实现抽象据型 类class数据象 据成员基本作 员函(法)例如，线性表的抽象数据类型描述如下：ADTList{数据对象：D={ai|ai∈ElemSet，i=1，2，…，n，n≥0}数据关系：R={<ai-1,ai>|ai-1，ai∈D，i=2，3，…，n}基本操作：InitList(&L)初始条件：表L不存在。操作结果：构造一个空的线性表。ClearList(&L)LLListLength(L)初始条件：表L已存在。操作结果：返回线性表L的元素个数。…}ADTList算法和算法的衡量一、算法算法是为了解决某类问题而规定的一个有限长的操作序列。一个算法必须满足以下五个重要特性：1．有穷性 对任意组合输值在行有穷步骤之一能束即：法的每个骤能有限时间内完；2．确定性 对每种情况下应行操作算法都确切规使算的行者或读都明其义及何行并且在何条件下，算法都有条执行路径；3．可行性 法的有操都须足基都可通已经现本操运有限次实现之；4．有输入 为法工对的值，常为算中一组量些输量要在算执过中入而有算表上以有输，际已嵌算法中；5．有输出它是一组与“输入”与确定关系的量值，是算法进行信息加工后得到的结果，这种确定关系即为算法的功能。二、算法设计的原则设计算法时，通常应考虑达到以下目标：1．正确性首先，算法应当满足以特定的“规格说明”方式给出的需求。其次，对算法是否“正确”的理解可以有以下四个层次：a．程序中不含语法错误；b．程序对于几组输入数据能够得出满足要求的结果；c．程序对于精心选择的、典型、苛刻切带有刁难性的几组输入数据能够得出满足要求的结果；d．程序对于一切合法的输入数据都能得出满足要求的结果；通常以第c层意义的正确性作为衡量一个算法是否合格的标准。2.可读性算法主要是为了人的阅读与交流，其次才是为计算机执行。因此算法应该易于人的理解；另一方面，晦涩难读的程序易于隐藏较多错误而难以调试；3．健壮性当输入的数据非法时，算法应当恰当地作出反映或进行相应处理，而不是产生莫处理出错的方法表示错误或错误性质的值4．高效率与低存储量需求通常，效率指的是算法执行时间；存储量指的是算法执行过程中所需的最大存储空间。两者都与问题的规模有关。三、算法效率的衡量方法和准则通常有两种衡量算法效率的方法:事后统计法缺点：1。必须执行程序2．其它因素掩盖算法本质事前分析估算法和算法执行时间相关的因素：1．算法选用的策略2．问题的规模3．编写程序的语言4．编译程序产生的机器代码的质量5．计算机执行指令的速度一个特定算法的“运行工作量”的大小，只依赖于问题的规模（通常用整数量n表示。记作：

假如，随着问题规模n的增长，算法执行时间的增长率和f(n)的增长率相同，则可T(n)=O(f(n))称T(n)为算法的(渐近)时间复杂度算法=控制结构+原操作（固有数据类型的操作）从算法中选取一种对于所研究的问题来说是基本操作的原操作，以该基本操作在算法中重复执行的次数作为算法运行时间的衡量准则四、算法的存储空间需求算法的空间复杂度S(n)=O(g(n))表示随着问题规模n的增大，算法运行所需存储量的增长率与g(n)的增长率相同。算法的存储量包括:1．输入数据所占空间;2．程序本身所占空间；3．辅助变量所占空间。若输入数据所占空间只取决与问题本身，和算法无关，则只需要分析除输入和程序之外的额外空间。若所需额外空间相对于输入数据量来说是常数，则称此算法为原地工作。若所需存储量依赖于特定的输入，则通常按最坏情况考虑。课次3计划课时2授课章节2.1线性表的类型定义课程目标与毕业要求指标点课程目标：（1）理解数据结构与算法的基本概念，掌握常用基本数（3）能够针对问题进行数据对象的抽象、分析、建模，并选择、构建合适的数据结构；（4）能够在软件开发过程中，针对特定需求综合应用数据结构、算法复杂性分析等知识设计算法。毕业要求指标点：1.3能够在对复杂工程问题的分析、推演中综合运用相关知识和数学模型方法。2.2能够运用相关科学原理和数学模型方法以合适的形式描述软件工程领域复杂工程问题。3.2能够针对复杂工程问题的特定需求进行模块/子系统设计，并在设计中体现创新意识。教学分析教学内容：1、线性表的定义和特点2、案例引入3、线性的类型定义教学重点：1、线性表的定义和特点2、线性的类型定义教学难点：1、案例引入教学方法、策略、过程设计教学方法：讲授+师生互动教学手段：PPT+板书通过排队的案例引入线性表。课后要求：作业：无预习：2.2线性表的顺序表示和实现实施情况、课后教学效果分析及下次课改进措施：附本课次教学内容：第二章 线性表线性结构是一个数据元素的有序（次序）集线性结构的基本特征:1．集合中必存在唯一的一个；2．集合中必存在唯一的一个；3．除最后元素在外，均有唯一的后继；4．除第一元素之外，均有唯一的前驱。线性表的类型定义抽象数据类型线性表的定义如下：ADTList{数据对象：D＝{ai|ai∈ElemSet,i=1,2,...,n,n≥0}数据关系：R1＝{<ai-1,ai>|ai-1,ai∈D,i=2,...,n}基本操作：{初始化}InitList(&L)操作结果：构造一个空的线性表L。{结构销毁}DestroyList(&L)初始条件：线性表L已存在。操作结果：销毁线性表L。ListEmpty(L)初始条件：线性表L已存在。LTRUE，。ListLength(L)初始条件：线性表L已存在。操作结果：返回L中元素个数。GetElem(L,i,&e)L已存在，1≤i≤LengthList(L)eLi个元素的值。LocateElem(L,e,compare())初始条件：线性表L已存在，compare()是元素判定函数。L中1个e满足compare(的元素的位序0。PriorElem(L,cur_e,&pre_e)初始条件：线性表L已存在。操作结果：若cur_e是L的元素，但不是第一个，则用pre_e返回它的前驱，否则操作失败，pre_e无定义。NextElem(L,cur_e,&next_e)初始条件：线性表L已存在。cur_eLnext_e否则操作失败，next_e无定义。ListTraverse(L,visit())初始条件：线性表L已存在。依次Lvisitvisit初始条件：线性表L已存在。操作结果：将L重置为空表。PutElem(L,i,&e)L已存在，1≤i≤LengthList(L)操作结果：LieListInsert(&L,i,e)初始条件：线性表L已存在，1≤i≤LengthList(L)+1操作结果：在L的第i个元素之前插入新的元素e，L的长度增1。ListDelete(&L,i,&e)初始条件：线性表L已存在且非空，1≤i≤LengthList(L)操作结果：删除L的第i个元素，并用e返回其值，L的长度减1。}ADTList2-1LALBAA＝A∪B。上述问题等价于：要求对线性表作如下操作：扩大线性表LA，将存在于线性表LB中而不存在于线性表LA中的数据元素插入到线性表LA中去。分下列三步进行：1．从线性表LB中依次取得每个数据元素;2．依值在线性表LA中进行查访;3．若不存在，则插入之。例2-2已知一个非纯集合B，试构造集合A，要求集合A中只包含集合B中所有值不相同的数据元素。解法一：同上例，分别以线性表LA和LB表示集合A和B，则首先初始化线性表LA为空表，之后的操作和例2-1完全相同。解法二：LB中的数据元素进行LB中的数据元素依其值从小到大有序排列，则值相同的数据元素必相邻。则上述操作中的第二步就不需要进行从头至尾的查询。2-3LALC也具有同样特性voidMergeList(ListLa,ListLb,List&Lc){//已知线性表La和Lb中的元素按值非递//减排列。归并La和Lb得到新的线性表//Lc，Lc的元素也按值非递减排列。InitList(Lc);i=j=1; k=0;La_len=ListLength(La);Lb_len=ListLength(Lb);while((i<=La_len)&&(j<=Lb_len)){//La和Lb均非空GetElem(La,i,ai); GetElem(Lb,j,bj);if(ai<=bj){ListInsert(Lc,++k,ai); ++i;}else{ListInsert(Lc,++k,bj); ++j;}}while(i<=La_len){GetElem(La,i++,ai);ListInsert(Lc,++k,ai);}while(j<=Lb_len){GetElem(Lb,j++,bj);ListInsert(Lc,++k,bj);}}//merge_list假设:GetElem和ListInsert这两个操作的执行时间和表长无关，LocateElem的执行时间和表长成正比，则算法的时间复杂度为O(ListLength(LA)＋ListLength(LB))课次4计划课时2授课章节2.2线性表的顺序表示和实现；课程目标与毕业要求指标点课程目标：（1）理解数据结构与算法的基本概念，掌握常用基本数据结构的逻辑结构、存储结构及其操作的实现，能进行算法的时间、空间复杂性分析；（3）能够针对问题进行数据对象的抽象、分析、建模，并选择、构建合适的数据结构；（4）能够在软件开发过程中，针对特定需求综合应用数据结构、算法复杂性分析等知识设计算法。毕业要求指标点：1.3能够在对复杂工程问题的分析、推演中综合运用相关知识和数学模型方法。2.2能够运用相关科学原理和数学模型方法以合适的形式描述软件工程领域复杂工程问题。3.2能够针对复杂工程问题的特定需求进行模块/子系统设计，并在设计中体现创新意识。教学分析教学内容:1、线性表顺序存储定义2、顺序表的基本操作3、顺序表的优缺点教学重点：1、线性表顺序存储定义2、顺序表的基本操作3、顺序表的特点教学难点：1、顺序表的基本操作教学方法、策略、过程设计教学方法：讲授+师生互动教学手段：PPT+板书通过案例引入顺序表的概念和特点课后要求：作业：无预习：2.3线性表的链式表示和实现实施情况、课后教学效果分析及下次课改进措施：附本课次教学内容：线性表类型的实现顺序映象用一组地址连续依次存放LOC(ai)=LOC(ai-1l (l)线性表中任意一个数据元素的存储位置都可以线性表中第一个数据元素a1的存储地址来表示，LOC(ai)=LOC(a1)+(i-1)l称第一个数据元素的存储地址为线性表的起始地址，称作线性表的基地址利用顺序表类实现线性表的其它操作SqListmerge(Sqlist&a,SqList&b){ElemType*ai,*bj;intm=a.Length();intn=b.Length();SqListc(m+n);inti=1;intj=1;intk=c.Length(); //k=0while((i<=m)&&(j<=n)){ai=a.getElem(i);bj=b.getElem(j);switch(compare(*ai,*bj)){case–1:case0:c.Insert(++k,ai);i++;break;case1:c.Insert(++k,bj);j++;break;default:;}//switch}//whilewhile(i<=m){ai=a.getElem(i++);c.Insert(++k,ai);}while(j<=n){bj=b.getElem(j++);c.Insert(++k,bj);}returnc;}//merge课次5计划课时2授课章节2.3线性表的链式表示和实现；课程目标与毕业要求指标点课程目标：（1）理解数据结构与算法的基本概念，掌握常用基本数（3）能够针对问题进行数据对象的抽象、分析、建模，并选择、构建合适的数据结构；（4）能够在软件开发过程中，针对特定需求综合应用数据结构、算法复杂性分析等知识设计算法。毕业要求指标点：1.3能够在对复杂工程问题的分析、推演中综合运用相关知识和数学模型方法。2.2能够运用相关科学原理和数学模型方法以合适的形式描述软件工程领域复杂工程问题。3.2能够针对复杂工程问题的特定需求进行模块/子系统设计，并在设计中体现创新意识。教学分析教学内容:1、线性表中链式存储结构的定义2、单链表存储结构及运算的实现3、循环链表、双链表及静态链表存储结构及其运算实现4、链表的优缺点教学重点：1、建立单链表及实现结点的插入和删除等基本运算2、循环链表及双链表存储结构及其运算实现教学难点：1、基本运算的实现，循环链表、双向链表的相关运算教学方法、策略、过程设计教学方法：讲授+师生互动教学手段：PPT+板书通过顺序表的缺点引入链表的概念课后要求：作业：习题2.2（3）预习：2.4线性表的应用实施情况、课后教学效果分析及下次课改进措施：实施情况、课后教学效果分析及下次课改进措施：课次6计划课时2授课章节2.4线性表的应用课程目标与毕业要求指标点课程目标：（1）理解数据结构与算法的基本概念，掌握常用基本数据结构的逻辑结构、存储结构及其操作的实现，能进行算法的时间、空间复杂性分析；（3）能够针对问题进行数据对象的抽象、分析、建模，并选择、构建合适的数据结构；（4）能够在软件开发过程中，针对特定需求综合应用数据结构、算法复杂性分析等知识设计算法。毕业要求指标点：1.3能够在对复杂工程问题的分析、推演中综合运用相关知识和数学模型方法。2.2能够运用相关科学原理和数学模型方法以合适的形式描述软件工程领域复杂工程问题。3.2能够针对复杂工程问题的特定需求进行模块/子系统设计，并在设计中体现创新意识。教学分析教学内容:1、线性表的合并2、有序表的合并教学重点：1、有序表的合并教学难点：1、有序表的合并教学方法、策略、过程设计教学方法：讲授+师生互动教学手段：PPT+板书通过分析讲解算法过程及代码课后要求：作业：无预习：3.1栈的定义、存储实施情况、课后教学效果分析及下次课改进措施：附本课次教学内容线性表的合并问题描述：假设利用两个线性表La和Lb分别表示两个集合A和B,现要求一个新的集合A=AB算法步骤：依次取出Lb中的每个元素，执行以下操作：（1）在La中查找该元素（2）如果找不到，则将其插入La的最后代码：voidunion(List&La,ListLb){La_len=ListLength(La);Lb_len=ListLength(Lb);for(i=1;i<=Lb_len;i++){GetElem(Lb,i,e);if(!LocateElem(La,e))

O(ListLength(LA)ListLength(LB))ListInsert(&La,++La_len,e);}}有序表的合并问题描述：已知线性表La和Lb中的数据元素按值非递减有序排列,现要求将La和Lb归Lc,Lc中的数据元素仍按值非递减有序排列.算法步骤（顺序表：Lc依次从La或Lb中“摘取”元素值较小的结点插入到Lc表的最后，直至其中一个表变空为止LaLbLc表的最后代码：voidMergeList_Sq(SqListLA,SqListLB,SqList&LC){pa=LA.elem; pb=LB.elem; //papbLC.length=LA.length+LB.length; //表长度为待合并两表的长度之和LC.elem=newElemType[LC.length]; //为合并后的新表分配一个数组空间pc=LC.elem; //指针pc指向新表的第一个元素pa_last=LA.elem+LA.length-1; //指针pa_last指向LA表的最后一个元素pb_last=LB.elem+LB.length-1; //指针pb_last指向LB表的最后一个元素while(pa<=pa_last&&pb<=pb_last){ //两个表都非空if(*pa<=*pb)*pc++=*pa++; //次“摘取”两表中值较小的结点else*pc++=*pb++; }while(pa<=pa_last) *pc++=*pa++; //LB表已到达表尾while(pb<=pb_last) *pc++=*pb++; //LA表已到达表尾}//MergeList_SqO(ListLength(LA)ListLength(LB))算法描述（链表：LcLa依次从La或Lb中“摘取”元素值较小的结点插入到Lc表的最后，直至其中一个表变空为止LaLbLc表的最后Lb表的表头结点O(ListLength(LA)ListLength(LB))思考1：要求合并后的表无重复数据，如何实现？思考2：将两个非递减的有序链表合并为一个非递增的有序链表，如何实现？要求结果链表仍使用原来两个链表的存储空间,不另外占用其它的存储空间。表中允许有重复的数据。算法步骤：LcLa依次从La或Lb中“摘取”元素值较小的结点插入到Lc表的表头结点之后，直至其中一个表变空为止LaLbLc表的表头结点之后Lb表的表头结点案例分析与实现（一元多项式的运算）（1）多项式创建①创建一个只有头结点的空链表。②根据多项式的项的个数n，循环n次执行以下操作：生成一个新结点*s；输入多项式当前项的系数和指数赋给新结点*s的数据域；q初始化，指向首元结点；pre，用于指向待找到的第一个大于输入项指数的结点的前驱，pre将输入项结点*s插入到结点*q之前。//（2）多项式相加①指针p1和p2初始化，分别指向Pa和Pb的首元结点。②p3指向和多项式的当前结点，初值为Pa的头结点。p1p2p1p2p1-n2-pn3p1->expnp2->expn时，则将两个结点中的系数相加，若和p1p2p1p2所指结点；p1->expnp2->expnp1所指结点插入到“和多项式”链表中去；p1->expnp2->expnp2所指结点插入到“和多项式”链表中去。④将非空多项式的剩余段插入到p3所指结点之后。⑤释放Pb的头结点。课次7计划课时2授课章节第3章栈和队列：3.1栈的定义、存储；课程目标与毕业要求指标点课程目标：（1）理解数据结构与算法的基本概念，掌握常用基本数据结构的逻辑结构、存储结构及其操作的实现，能进行算法的时间、空间复杂性分析；（3）能够针对问题进行数据对象的抽象、分析、建模，并选择、构建合适的数据结构；（4）能够在软件开发过程中，针对特定需求综合应用数据结构、算法复杂性分析等知识设计算法。毕业要求指标点：1.3能够在对复杂工程问题的分析、推演中综合运用相关知识和数学模型方法。2.2能够运用相关科学原理和数学模型方法以合适的形式描述软件工程领域复杂工程问题。3.2能够针对复杂工程问题的特定需求进行模块/子系统设计，并在设计中体现创新意识。教学分析教学内容:1式2、栈的表示和操作教学重点：12、栈的表示和操作教学难点：1、栈的表示和操作教学方法、策略、过程设计教学方法：讲授+师生互动教学手段：PPT+板书通过铁路调度引入栈的概念课后要求：作业：无预习：3.2栈的应用举例；3.3栈与递归的实现实施情况、课后教学效果分析及下次课改进措施：附本课次教学内容第三章栈和队列从数据结构的角度看:它们和线性表相同从数据类型的角度看:它们和线性表不同线性表栈队列Insert(L,i,x)(1in+1)Insert(S,n+1,x)Insert(Q,n+1,x)Delete(L,i)(1in)Delete(S,n)Delete(Q,1)3.1栈的类型定义ADTStack{数据对象：D＝{ai|ai∈ElemSet,i=1,2,...,n, n≥0}数据关系：R1＝{<ai-1,ai>|ai-1,ai∈D,i=2,...,n}约定an端为栈顶，a1端为栈底。基本操作：InitStack(&S)操作结果：构造一个空栈S。DestroyStack(&S)初始条件：栈S已存在。操作结果：栈S被销毁。ClearStack(&S)初始条件：栈S已存在。操作结果：将S清为空栈。StackEmpty(S)初始条件：栈S已存在。操作结果STRUE。StackLength(S)初始条件：栈S已存在。操作结果：返回S的元素个数，即栈的长度。GetTop(S,&e)初始条件：栈S已存在且非空。操作结果：用e返回S的栈顶元素。Push(&S,e)初始条件：栈S已存在。操作结果：插入元素e为新的栈顶元素。Pop(&S,&e)初始条件：栈S已存在且非空。操作结果：删除S的栈顶元素，并用e返回其值。}ADTStack3.3 栈类型的实现顺序栈类似于线性表的顺序映象实现，指向表尾的指针可以作为栈顶指针。链栈利用链表实现栈，注意链表中指针的方向是从栈顶到栈底。课次8计划课时2授课章节3.2栈的应用举例；3.3栈与递归的实现课程目标与毕业要求指标点课程目标：（1）理解数据结构与算法的基本概念，掌握常用基本数（3）能够针对问题进行数据对象的抽象、分析、建模，并选择、构建合适的数据结构；（4）能够在软件开发过程中，针对特定需求综合应用数据结构、算法复杂性分析等知识设计算法。毕业要求指标点：1.3能够在对复杂工程问题的分析、推演中综合运用相关知识和数学模型方法。2.2能够运用相关科学原理和数学模型方法以合适的形式描述软件工程领域复杂工程问题。3.2能够针对复杂工程问题的特定需求进行模块/子系统设计，并在设计中体现创新意识。教学分析教学内容:1值、递归问题等2、递归的定义3、递归的应用举例教学重点：1、递归的定义2、递归的应用举例教学难点：1、递归的应用举例教学方法、策略、过程设计教学方法：讲授+师生互动教学手段：PPT+板书案例讲解课后要求：作业：习题3.2（6）预习：3.4队列的定义、存储；3.5队列的应用举例实施情况、课后教学效果分析及下次课改进措施：实施情况、课后教学效果分析及下次课改进措施：附本课次教学内容栈的应用举例例一、数制转换十进制数N和其他d进制数的转换是计算机实现计算的基本问题，其解决方法很多，其中一个简单算法基于下列原理：N=(Ndivd)×d+Nmodd(其中：div为整除运算，mod为求余运算）（348)105048，其运算过程如下：N Ndiv8 Nmod8134816841682102125202假设现要编制一个满足下列要求的程序：对于输入的任意一个非负十进制整voidconversion(){//对于输入的任意一个非负十进制整数，打印输出//与其等值的八制数InitStack(S); //构造空栈scanf("%d",N);while(N){Push(S,N%8);N=N/8;}while(!StackEmpty(S)){Pop(S,e);printf("%d",e);}}//conversion例二、括号匹配的检验假设表达式中允许包含两种括号：圆括号和方括号，其嵌套的顺序随意，即［（）或［［］（）或（）或(()])均为不正确的格式。检验括号是否匹配的方法可用"期待的急迫程度"这个概念来描述。例如考虑下列括号序列：[ ( [ ] [ ] ) ]1 2 34 5 6 7 8分析可能出现的不匹配的情况:到来的右括弧非是所“期待”的;到来的是“不速之客”;直到结束，也没有到来所“期待”的。statusmatching(string&exp){//检验表达式中所含括弧是否正确嵌套，若是，则返回// OKERRORintstate=1;while(i<=length(exp)&&state){swithofexp[i]{case左括弧:{Push(S,exp[i]); i++; break;}case")":{if(！StackEmpty(S)&&GetTop(S)="("){Pop(S,e); i++;}else{state=0}break;}……}}if(&&StackEmpty(S)) returnOKelse returnERROR;}例三、行编辑程序问题每接受一个字符即存入用户数据区”不恰当。例如，可用一个退格符“#”表示前一个字符无效；可用一个退行符“@，表示当前行中的字符均无效。例如，假设从终端接受了这样两行字符：whli##ilr#e（s#*s)outcha@putchar(*s=#++);则实际有效的是下列两行：while(*s)putchar(*s++);voidLineEdit(){//利用字符栈S，从终端接收一行并传送至调用过程//的数据区。InitStack(S); //Schgetchar(); //从终端接收第一个字符while(ch!=EOF){//EOF为全文结束符while(ch!=EOF&&ch!='\n'){switch(ch){case'#':Pop(S,c);break;//仅当栈空时退栈case'@':ClearStack(S);break; //置S为空栈default:Push(S,ch); break;//有效字符进栈，未考虑栈满情形}chgetchar(); //}将从栈底到栈顶的字符传送至调用过程的数据区；ClearStack(S); //S为空栈if(ch!=EOF) ch=getchar();}DestroyStack(S);}例四、 迷宫求解需要用一个后进先出的结构来保存从入口到当前位置的路径假设迷宫如下图所示:############$$$####$$$###$$#####################################假设“当前位置”指的是“在搜索过程中某一时刻所在图中某个方块位置若当前位置可通"，则纳入"当前路径"，并继续朝“下一位置”探索，即切。所谓“下一位置”指的是“当前位置”四周四个方向（东、南、西、北）上相邻的方块S，则栈顶中存放的是“当前路径上最后一个“从当前路径上删。求迷宫中一条从入口到出口的路径的算法可简单描述如下：例五、表达式求值限于二元运算符的表达式定义:表达式::=(操作数)+(运算符)+(操作数)操作数::=简单变量|表达式简单变量::=标识符|无符号整数在计算机中，表达式可以有三种不同的标识方法设 Exp=S1+OP+S2则称OP+S1+S2为表达式的前缀表示法称S1+OP+S2为表达式的中缀表示法称S1+S2+OP为表达式的后缀表示法可见，它以运算符所在不同位置命名的。例如:Exp=ab+(cd/e)f前缀式: +abc/def中缀式: ab+cd/ef后缀式: abcde/f+结论:操作数之间的相对次序不变;运算符的相对次序不同;中缀式丢失了括弧信息，致使运算的次序不确定;前缀式的运算规则为:连续出现的两个操作数和在它们之前且紧靠它们的运算符构成一个最小表达式;后缀式的运算规则为:运算符在式中出现的顺序恰为表达式的运算顺序;每个运算符和在它之前出现且紧靠它的两个操作数构成一个最小表达式;如何从后缀式求值？先找运算符，后找操作数如何从原表达式求得后缀式？分析“原表达式”和“后缀式”中的运算符:原表达式: a+bcd/ef后缀式: abc+de/f运算符# ( + / 优先数-1 0 1 1 22 3;否则立即进行。表达式求值的规则:设立运算符栈和栈;设表达式的结束符为“#”,予设运算符栈的栈底为“#”若当前字符是操作数，则进操作数栈;若当前运算符的优先数高于栈顶运算符，则进栈;否则，退出栈顶运算符作相应运算;“(”对它之前后的运算符起隔离作用)”可视为自相应左括弧开始的表达式的结束符。栈与递归的实现在高级语言编制的程序中，调用函数与被调用函数之间的链接和信息交换必须通过栈例进行。当在一个函数的运行期间调用另一个函数之前先完成三件事:将所有的实在参数、返回地址等信息传递给被调用函数保存;为被调用函数的局部变量分配存储区;将控制转移到被调用函数的入口。从被调用函数返回调用函数之前，应该完成:保存被调函数的计算结果;释放被调函数的数据区;依照被调函数保存的返回地址将控制转移到调用函数。多个函数嵌套调用的规则是:后调用先返回此时的内存管理实行“栈式管理”递归过程指向过程中占用的数据区，称之为递归工作栈每一层的递归参数合成一个记录，称之为递归工作记录栈顶记录指示当前层的执行情况，称之为当前活动记录栈顶指针， 称之为当前环境指针例如:voidhanoi(intn,charx,chary,charz)//将塔座x上按直径由小到大且至上而下编号为1至n//的n个圆盘按规则搬到塔座z上，y可用作辅助塔座。1{2if(n==1)move(x1,z); //xzelse{hanoi(n-1,xz,y);//xn-1的圆//盘移到y,z作辅助塔move(xn,z); //nxzhanoi(n-1,xz);//yn-1的圆盘//移到z,x作辅助塔8 }9}课次9计划课时2授课章节3.4队列的定义、存储；3.5队列的应用举例课程目标与毕业要求指标点课程目标：（1）理解数据结构与算法的基本概念，掌握常用基本数据结构的逻辑结构、存储结构及其操作的实现，能进行算法的时间、空间复杂性分析；（3）能够针对问题进行数据对象的抽象、分析、建模，并选择、构建合适的数据结构；（4）能够在软件开发过程中，针对特定需求综合应用数据结构、算法复杂性分析等知识设计算法。毕业要求指标点：1.3能够在对复杂工程问题的分析、推演中综合运用相关知识和数学模型方法。2.2能够运用相关科学原理和数学模型方法以合适的形式描述软件工程领域复杂工程问题。3.2能够针对复杂工程问题的特定需求进行模块/子系统设计，并在设计中体现创新意识。教学分析教学内容:1、队列的定义2、队列的抽象类型定义3、链队列的定义及操作4、循环队列的定义及操作5、队列的案例教学重点：1、循环队列的定义及操作2、队列的案例教学难点：1、循环队列的定义及操作教学方法、策略、过程设计教学方法：讲授+师生互动教学手段：PPT+板书案例讲解课后要求：作业：无预习：第4章串、数组和广义表实施情况、课后教学效果分析及下次课改进措施：附本课次教学内容队列的定义、存储3.4.1队列的类型定义ADTQueue{数据对象：D＝{ai|ai∈ElemSet,i=1,2,...,n,n≥0}数据关系：R1＝{<ai-1,ai>|ai-1,ai∈D,i=2,...,n}约定其中a1端为队列头，an端为队列尾。基本操作：InitQueue(&Q)操作结果：构造一个空队列Q。DestroyQueue(&Q)初始条件：队列Q已存在。操作结果：队列Q被销毁，不再存在。ClearQueue(&Q)初始条件：队列Q已存在。操作结果：将Q清为空队列。QueueEmpty(Q)初始条件：队列Q已存在。操作结果：若Q为空队列，则返回TRUE，否则返回FALSE。QueueLength(Q)初始条件：队列Q已存在。操作结果：返回Q的元素个数，即队列的长度。GetHead(Q,&e)初始条件：Q为非空队列。操作结果：用e返回Q的队头元素。EnQueue(&Q,e)初始条件：队列Q已存在。操作结果：插入元素e为Q的新的队尾元素。DeQueue(&Q,&e)初始条件：Q为非空队列。操作结果：删除Q的队头元素，并用e返回其值。}ADTQueue课次10计划课时2授课章节44.1法；4.3数组的存储；课程目标与毕业要求指标点课程目标：（1）理解数据结构与算法的基本概念，掌握常用基本数（3）能够针对问题进行数据对象的抽象、分析、建模，并选择、构建合适的数据结构；（4）能够在软件开发过程中，针对特定需求综合应用数据结构、算法复杂性分析等知识设计算法。毕业要求指标点：1.3能够在对复杂工程问题的分析、推演中综合运用相关知识和数学模型方法。2.2能够运用相关科学原理和数学模型方法以合适的形式描述软件工程领域复杂工程问题。3.2能够针对复杂工程问题的特定需求进行模块/子系统设计，并在设计中体现创新意识。教学分析教学内容：1、串的定义2、串的类型定义、存储结构及运算3、串的模式匹配算法：BF和KMP4、数组的顺序表示和实现教学重点：1、串的模式匹配算法：BF和KMP2、数组的顺序表示和实现教学难点：KMP算法教学方法、策略、过程设计教学方法：讲授+师生互动教学手段：PPT+板书课后要求：作业：无预习：特殊矩阵和稀疏矩阵；广义表的逻辑结构和存储结构实施情况、课后教学效果分析及下次课改进措施：附本课次教学内容串的逻辑结构和线性表极为相似，区别仅在于串的数据对象约束为字符集。串的表示与实现串的抽象数据类型的定义如下：ADTString{数据对象：D＝{ai|ai∈CharacterSet,i=1,2,...,n,n≥0}数据关系：R1＝{<ai-1,ai>|ai-1,ai∈D,i=2,...,n}基本操作：StrAssign(&T,chars)初始条件：chars是字符串常量。charsT的值。StrCopy(&T,S)初始条件：串S存在。操作结果：由串S复制得串T。StrEmpty(S)初始条件：串S存在。STRUE，。StrCompare(S,T)初始条件：串S和T存在。操作结果：若ST，则返回值0；若ST，则返回值0；若ST，则返回值0。StrLength(S)初始条件：串S存在。操作结果：返回S的元素个数，称为串的长度。ClearString(&S)初始条件：串S存在。操作结果：将S清为空串。Concat(&T,S1,S2)初始条件：串S1和S2存在。操作结果：用T返回由S1和S2联接而成的新串。SubString(&Sub,S,pos,len)初始条件：串S存在，1≤pos≤StrLength(S)且0≤len≤StrLength(S)-pos+1。SubSposlen的子串。Index(S,T,pos)初始条件：串S和T存在，T是非空串，1≤pos≤StrLength(S)。ST值相同的子串,Spos;0。Replace(&S,T,V)初始条件：串S,T和V存在，T是非空串。VST相等的不重叠的子串。StrInsert(&S,pos,T)ST存在，1≤pos≤StrLength(S)＋1。SposT。StrDelete(&S,pos,len)初始条件：串S存在，1≤pos≤StrLength(S)-len+1。操作结果：从串S中删除第pos个字符起长度为len的子串。DestroyString(&S)S存在。操S被销毁。}ADTString13种StrAssignStrcopyStrCompareStrLength、ConcatSubString（ClearStringDestroyString外）可在这个最小操作子集上实现。算法的基本思想为：Si(ipos)T相Tii1S中不存在和串T相等的子串为止。即求使StrCompare(SubString(S,i,StrLength(T)),T)==0成立的i值。intIndex(StringS,StringT,intpos){//T为非空串。若主串S中第pos个字符之后存在与//T相等的子串，则返回第一个这样的子串在S中的//位置，否则返回0if(pos>0){n=StrLength(S); m=StrLength(T); i=pos;while(i<=n-m+1){SubString(sub,S,i,m);if(StrCompare(sub,T)!=0) ++i;elsereturni;}//while}//ifreturn0; //ST}//Index串的表示和实现一、串的定长顺序存储表示#define MAXSTRLEN 255//用户可在255以内定义最大串长typedefunsignedchar SString[MAXSTRLEN+1];//0号单元存放串的长度串按这种串的表示方法实现的串的运算时，其基本操作为“字符序列的复制”例如：串的联接算法中需分三种情况处理：StatusConcat(SStringS1,SStringS2,SString&T){//用T返回由S1和S2联接而成的新串。若未截断，//则返回TRUE，否则FALSE。if(S1[0]+S2[0MAXSTRLEN{ //T[1..S1[0]]=S1[1..S1[0]];T[S1[0]+1..S1[0]+S2[0]]=S2[1..S2[0]];T[0]=S1[0]+S2[0]; uncut=TRUE;}elseif(S1[0MAXSTRSIZE){ //T[1..S1[0]]=S1[1..S1[0]];T[S1[0]+1..MAXSTRLENS2[1..MAXSTRLEN－S1[0]];T[0]=MAXSTRLEN; uncut=}else{//S1[0]=MAXSTRSIZE截断(仅取S1)T[0..MAXSTRLEN]=S1[0..MAXSTRLEN];//T[0]==S1[0]==MAXSTRLENuncut=FALSE;}returnuncut;}//Concat二、串的堆分配存储表示typedefstruct{char*ch; ////存储区，否则ch为NULLint length; //长度}HString;这类串操作的实现算法为:先为新生成的串分配一个存储空间，然后进行串值的复制。在此不再举例。串的模式匹配算法这是串的一种重要操作，很多软件，若有“编辑”菜单项的话，则其中必有“查找”子菜单项。首先，回忆一下串匹配(查找)的定义:INDEX(S,T,pos)初始条件：串S和T存在，T是非空串，1≤pos≤StrLength(S)。ST值相同的子串,Spos;0。下面讨论以定长顺序结构表示串时的几种算法。BF算法intIndex(SStringS,SStringT,intpos){//返回子串T在主串S中第pos个字符之后的位置。//若不存在，则函数值为0。//其中，T非空，1≤pos≤StrLength(S)。i=pos; j=1;while(i<=S[0]&&j<=T[0]){if(S[i]==T[j++i; ++j;} //else{ii-j+2; j1;//}if(j>T[0]) return i-T[0];elsereturn0;}//IndexKMP(D.E.Knuth,V.R.Pratt,J.H.Morris)算法上述两种算法的时间复杂度为O(mn)KMP算法的时间复杂度可以达到O(m+n)当S[i]<>T[j]时，已经得到的结果: S[i-j+1..i-1]==T[1..j-1]若已知 T[j-k+1..j-1]==T[1..k-1]则有 S[i-k+1..i-1]==T[1..k-1]si-j+1ssi-j+1si-k+1si-1t1tj-k+1tj-1t1 s1 sitjtk其它情况p12 k-1 j-k1'当j时0next[j]Max{k|1kj且'ppp ''p定义：模式串的next函数intIndex_KMP(SStringS,SStringT,intpos){//利用模式串T的next函数求T在主串S中第pos个//字符之后的位置的KMP算法。其中，T非空，// i=pos; j=1;while(i<=S[0]&&j<=T[0]){if(j==0||S[i]==T[j]){++i; ++j;}//继续比较后继字符else jnext[j]; //}if(jT[0]) return i-T[0]; //匹配成功elsereturn0;}//Index_KMP求next函数值的过程是一个递推过程，分析如下：已知：next[1]=0；假设：next[j]=k；又T[j]=T[k]则： next[j+1]=k+1若： T[j]T[k]则需往前回朔，检查T[j]=T[？]这实际上也是一个匹配的过程，不同在于：主串和模式串是同一个串voidget_next(SString&T,int&next[]){//求模式串T的函数值并存入数组next。i=1; next[1]=0; j=0;while(i<T[0]){if(j==0||T[i]==T[j]){++i; ++j; next[i]=j;}else j=next[j];}}//get_nextADTArray{数据对象：D＝{aj1,j2,...,ji,...jn|ji=0,...,bi-1, i=1,2,..,n,n(>0)称为数组的维数，bi是数组第i维的长度，ji是数组元素的第i维下标，aj,...,j∈ElemSet}数据关系：R＝{R1,R2,...,Rn}Ri＝{<aj1,...ji,...jn,aj1,...,ji+1,...,jn>| 0jkbk-1,1kn 且ki, 0jibi-2,aj1,...,ji,...,jn,aj1,...ji+1,...,jn∈D, i=2,...,n}基本操作：InitArray(&A,n,bound1,...,boundn)操作结果：若维数n和各维长度合法，则构造相应的数组A，并返回OK。DestroyArray(&A)操作结果：销毁数组A。Value(A,&e,index1,...,indexn)初始条件：A是n维数组，e为元素变量，随后是n个下标值。操作结果：若各下标不超界，则e赋值为所指定的A的元素值，并返回OK。Assign(&A,e,index1,...,indexn)初始条件：A是n维数组，e为元素变量，随后是n个下标值。操作结果：若下标不超界，则将e的值赋给所指定的A的元素，并返回OK。}ADTArray数组的顺序表示和实现类型特点:只有引用型操作，没有加工型操作;数组是多维的结构，而存储空间是一个一维的结构。有两种顺序映象的方式:(低下标优先);(高下标优先);课次11计划课时2授课章节4.4特殊矩阵和稀疏矩阵；4.5广义表的逻辑结构和存储结构课程目标与毕业要求指标点课程目标：（1）理解数据结构与算法的基本概念，掌握常用基本数据结构的逻辑结构、存储结构及其操作的实现，能进行算法的时间、空间复杂性分析；（3）能够针对问题进行数据对象的抽象、分析、建模，并选择、构建合适的数据结构；（4）能够在软件开发过程中，针对特定需求综合应用数据结构、算法复杂性分析等知识设计算法。毕业要求指标点：1.3能够在对复杂工程问题的分析、推演中综合运用相关知识和数学模型方法。2.2能够运用相关科学原理和数学模型方法以合适的形式描述软件工程领域复杂工程问题。3.2能够针对复杂工程问题的特定需求进行模块/子系统设计，并在设计中体现创新意识。教学分析教学内容：1、特殊矩阵的压缩存储2、广义表的定义教学重点：广义表的定义教学难点：特殊矩阵的压缩存储教学方法、策略、过程设计教学方法：讲授+师生互动教学手段：PPT+板书课后要求：作业：习题4.2（3），（4）预习：第五章树和二叉树实施情况、课后教学效果分析及下次课改进措施：稀疏矩阵的压缩存储假设m行n列的矩阵含t个非零元素，则称 tmn为稀疏因子通常认为0.05的矩阵为稀疏矩阵若以常规方法，即以二维数组表示高阶的稀疏矩阵，则:零值元素占的空间很大;计算中进行了很多和零值的运算;解决问题的原则:尽可能少存或不存零值元素;尽可能减少没有实际意义的运算;运算方便;即:能尽可能快地找到与下标值(i,j)对应的非零值元;能尽可能快地找到同一行或同一列的非零值元;通常，有两类稀疏矩阵:特殊矩阵例如:三角矩阵对角矩阵它们的压缩存储处理相对地比较简单随机稀疏矩阵随机矩阵中的非零元分布不规则下面讨论(随机)稀疏矩阵的几种压缩存储处理方法一、三元组顺序表以行逻辑联接的顺序表表示稀疏矩阵时，两个稀疏矩阵相乘（QMN）的过程可大致描述如下：Q初始化;if Q是非零矩阵{ //逐行求积for(arow=1;arow<=M.mu;++arow){// Mctemp0; //累加器清零Qarowctemp[]中；ctemp[]Q.data中；}//forarow}//ifTriSeqMatrixProduct(TriSeqMatrixM,TriSeqMatrixN){//求矩阵乘积Q=MN，采用行逻辑链接存储表示。if(M.nu!=N.mu)returnERROR;sz=M.data.ListSize();TriSeqMatrixQ(M.mu,N.nu,0,sz); //Q初始化if(M.tu*N.tu0){ //Q是非零矩阵for(arow=1;arow<=M.mu;++arow){//处理M的每一行ctemp[]=0; //当前行各元素加器清零Q.rpos[arow]=Q.tu+1;//设置当前行第一个非零元在三元组表中的位序for(p=M.rpos[arow];p<M.rpos[arow+1];++p)//对当前行中每个非零元brow=M.data[p].j; //找到对应元在N中的行号if(brow<N.nu) t=N.rpos[brow+1];else {t=N.tu+1}//t指示该行中最后一个非零元的位置for(q=N.rpos[brow]; q<t; ++q){ccolN.data[q].j; //Q中列号ctemp[ccol]+=M.data[p].e*N.data[q].e;}//forq}//求得Q中第crow(=arow)行的非零元for(ccol=1;ccol<=Q.nu;++ccol)//压缩存储该行非零元if(ctemp[ccol{ //if(++Q.tu>Q.data.ListSize())Q.data.Resize(Q.data.ListSize+Q.nu);Q.data[Q.tu]={arow,ccol,ctemp[ccol]};}//if}//forarow}//ifreturn*Q;}//Product广义表广义表（列表： n个表元素组成的有限序列，记作S=,a1,2,…,a-1，LS是表名，ai是表元素，它可以是表(称为子表)，可以是数据元素(称为原子)。n为表的长度。n=0的广义表为空表。线性表的成分都是结构上不可分的单元素广义表的成分可以是单元素，也可以是有结构的表线性表是一种特殊的广义表广义表不一定是线性表，也不一定是线性结构（1）求表头GetHead(L)：非空广义表的第一个元素，可以是一个单元素，也可以是一个子表（2）求表尾GetTail(L)：非空广义表除去表头元素以外其它元素所构成的表。表尾一定是一个表课次12计划课时2授课章节第5章树与二叉树：二叉树的定义和基本术语；二叉树的性质课程目标与毕业要求指标点课程目标：（1）理解数据结构与算法的基本概念，掌握常用基本数（3）能够针对问题进行数据对象的抽象、分析、建模，并选择、构建合适的数据结构；（4）能够在软件开发过程中，针对特定需求综合应用数据结构、算法复杂性分析等知识设计算法。毕业要求指标点：1.3能够在对复杂工程问题的分析、推演中综合运用相关知识和数学模型方法。2.2能够运用相关科学原理和数学模型方法以合适的形式描述软件工程领域复杂工程问题。3.2能够针对复杂工程问题的特定需求进行模块/子系统设计，并在设计中体现创新意识。教学分析教学内容：1、树的定义2、树的基本术语3、二叉树的定义4、树和二叉树的抽象数据类型定义5、二叉树的性质教学重点：1、树的定义2、二叉树的性质教学难点：树和二叉树的抽象数据类型定义教学方法、策略、过程设计引入：通过文件结构引入介绍本章内容-树。过程：（1）树的定义（2）树的基本术语（3）二叉树的定义（4）树和二叉树的抽象数据类型定义（5）二叉树的性质1（6）二叉树的性质2（7）二叉树的性质3（8）二叉树的性质4（9）二叉树的性质5总结：回顾树、二叉树的定义及二叉树的五个性质。课后要求：思考：十字链表结构的特点。作业：无预习：遍历二叉树，线索二叉树，树和森林实施情况、课后教学效果分析及下次课改进措施：附本课次教学内容：第五章树和二叉树树的类型定义数据对象D：D是具有相同特性的数据元素的集合。数据关系R：若D为空集，则称为空树；否则:Droot,n>1m(m>0)T1,T2,…,Tm,其中每一棵子集本身又是一棵符合本定义的树，称为根root的子树。基本操作：查找：Root(T);Value(T,cur_e);Parent(T,cur_e);LeftChild(T,cur_e);RightSibling(T,cur_e);TreeEmpty(T); TreeDepth(T);Visit());插入：InitTree(&T); definition);Assign(T,cur_e,value);InsertChild(&T,&p,i,c);删除：ClearTree(&T); DestroyTree(&T);DeleteChild(&T,&p,i);DestroyTree(&T);有向树：１）有确定的根；２）树根和子树根之间为有向关系有序树和无序树的区别在于：子树之间是否存在次序关系？和线性结构的比较线性结构 树结构第一个数据元素 根结点(无前驱) (无前驱)最后一个数据元素 多个叶子结点(无后继) (无后继)其它数据元素 树中其它结点(一个前驱、一个后继) (一个前驱、多个后继)基本术语结点:数据元素+若干指向子树的分支结点的度:分支的个数树的度:树中所有结点的度的最大值叶子结点:度为零的结点分支结点:度大于零的结点从根到结点的路径：孩子结点、双亲结点、兄弟结点、祖先结点、子孙结点结点的层次:假设根结点的层次为1,第l层的结点的子树根结点的层次为l+1树的深度：树中叶子结点所在的最大层次森林：是m（m≥0）棵互不相交的树的集合任何一棵非空树是一个二元组Tree=（root，F）其中：root被称为根结点，F被称为子树森林二叉树的类型定义二叉树或为空树；或是由一个根结点加上两棵分别称为左子树和右子树的、互不相交的二叉树组成。二叉树的五种基本形态：二叉树的主要基本操作：查找：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);二叉树的重要特性：性质1：在二叉树的第i层上至多有2i-1个结点(i≥1)性质2：深度为k的二叉树上至多含2k-1个结点（k≥1）性质3：对任何一棵二叉树，若他含有n0个叶子结点、n2个度为2的结点，则必存在关系式：n0=n2+1两类特殊的二叉树：满二叉树：指的是深度为k且含有2k-1个结点的二叉树完全二叉树：树中所含的n个结点和满二叉树中编号为1至n的结点一一对应性质4：具有n个结点的完全二叉树的深度为log2n+1性质5：若对含n个结点的二叉树从上到下且从左至右进行1至n的编号，则对二叉树中任意一个编号为i的结点：i=1，则该结点是二叉树的根，无双亲,否则，编号为i/2的结点为其双亲结点;2i>n，则该结点无左孩子，否则，编号为2i的结点为其左孩子结点；2i+1>n，则该结点无右孩子结点，否则，编号为2i+1的结点为其右孩子结点。课次13计划课时2授课章节5.3二叉树的存储结构课程目标与毕业要求指标点课程目标：（1）理解数据结构与算法的基本概念，掌握常用基本数（3）能够针对问题进行数据对象的抽象、分析、建模，并选择、构建合适的数据结构；（4）能够在软件开发过程中，针对特定需求综合应用数据结构、算法复杂性分析等知识设计算法。毕业要求指标点：1.3能够在对复杂工程问题的分析、推演中综合运用相关知识和数学模型方法。2.2能够运用相关科学原理和数学模型方法以合适的形式描述软件工程领域复杂工程问题。3.2能够针对复杂工程问题的特定需求进行模块/子系统设计，并在设计中体现创新意识。教学分析教学内容：1、二叉树的顺序存储表示2教学重点：二叉树的链式存储表示：二叉链表教学难点：二叉树的链式存储表示：二叉链表教学方法、策略、过程设计引入：简单介绍本章内容。过程：首先回顾上一节提到的二叉树的定义和性质，抛出问题，二叉树在实际中是怎么存储的？开始介绍本节内容：（1）二叉树的顺序存储（2）二叉树顺序存储的优缺点（3）通过二叉树顺序存储的缺点引入二叉树的链式存储（4）二叉链表（5）三叉链表（6）双亲链表（7）线索链表总结：回顾二叉树的存储方式及优缺点。课后要求：思考：十字链表结构的特点。作业：无预习：回顾线性结构、树结构的遍历，预习图结构的遍历方法。实施情况、课后教学效果分析及下次课改进措施：课次14计划课时2授课章节遍历二叉树和线索二叉树树和森林课程目标与毕业要求指标点课程目标：（1）