《数据结构》教学重点.pdf

第1章 绪论【教学目的要求】熟悉各名词、术语的含义，掌握基本概念，特别是数据的逻辑结构和存储结构之间的关系。分清哪些是逻辑结构的性质，哪些是存储结构的性质。了解抽象数据类型的定义、表示和实现方法。掌握计算语句频度和估算算法时间复杂度的方法。【重点】数据结构的3个层次5个要素、抽象数据类型、算法分析。【难点】抽象数据类型、算法分析。【教学方法】多媒体教学和传统教学相结合。【课时安排】2 学时。【教学过程】K导入U当前，计算机所处理的数据不再是简单的数值，而是字符串、图形、图像、语音、视频等复杂的数据。而这些复杂的数据不仅量大，而且具有一定的结构。数据结构所研究的就是这些有结构的数据，因此，数据结构的知识不论对研制系统软件还是开发应用软件都非常重要，它是学习软件知识和提高软件设计水平的重要基础。本章主要介绍数据结构的概念、数据类型和抽象数据类型、算法和算法分析等知识。K讲解X1.1 数据结构的概念1.1.1 为什么要学习数据结构1.计算机处理的问题有：1）数值计算问题：解决问题的关键是数学分析和计算方法。2）非数值计算问题：设计合适的数据结构。2.计算机解决问题的步骤：具 体 问 题 驾 数 学 模 型 也 算 法 型 程序程序设计：为计算机处理问题编制一组指令集。算法：处理问题的策略。数据结构：问题的数学模型。学习数据结构的目的是为了了解计算机处理对象的特性，将实际问题中所涉及的处理对象在计算机中表示出来并对它们处理。同时，通过算法设计训练来提高学生的思维能力，通过程序设计的技能训练来提高学生的综合应用能力和专业素质。1-1-2相关概念和术语（1）数据：所有能被输入到计算机中，且被计算机处理的符号的总称，是计算机处理的信息的某种特定的符号表示形式。它可以是数值数据，也可以是非数值数据。（2）数据项：是具有独立含义的标识单位，是数据不可分割的最小单位。（3）数据元素：是数据的基本单位，它是数据项的集合。（4）数 据 对 象（数据元素类）：具有相同性质的数据元素的集合。（5）数据结构：包括数据的逻辑结构和数据的物理结构。数据的逻辑结构：是指相互之间存在一种或多种特定关系的数据元素的集合，它可看着是从具体问题抽象出来的数学模型，与数据的存储无关。它 通 常 有“集合结构、线性结构、树形结构、图形结构”四种基本结构。它的形式定义为：Data_Structures=（D,S）其中：D是数据元素的有限集，S是D上关系的有限集。令 数据的物理结构（又称数据的存储结构）：是指逻辑结构在存储器中的表示（又称映象），包括数据元素的表示和数据元素间关系的表示。数据元素的表示方法：用二进制位（bit）的位串表示数据元素。数据元素间关系的表示方法：顺序存储和链式存储。1-1-3数据结构课程的内容数据结构是介于数学、计算机硬件和软件之间的一门计算机科学与技术专业的核心课程,是高级程序设计语言、编译原理、操作系统等课程的基础。同时数据结构技术也广泛应用于信息科学、系统工程、应用数学及各种工程技术领域。数据结构的内容包括3个层次5个要素，如 表1-6所示：表1-6数据结构课程内容体系y面数据表示数据处理抽象逻辑结构基本运算实现存储结构算法评价不同数据结构的比较及算法分析1.2 数据类型和抽象数据类型1.2.1 数据类型在用高级程序语言编写的程序中，必须对程序中出现的每个变量、常量或表达式，明确说明它们所属的数据类型。因为类型明显或隐含地规定了在程序执行期间，变量或表达式所有可能取值的范围，以及在这些之上允许进行的操作。数据类型是一个值的集合和定义在此集合上的一组操作的总称。在用高级程序语言中，数据类型可分为：原子类型和结构类型。1.2.2 抽象数据类型（Abstract Data Type 简称 ADT）（1）抽象：是指抽出反映问题本质的东西，舍去其非本质的细节。在程序设计发展的几个阶段，通过一步步抽象，不断突出“做什么？”，而 将“怎么做？”隐藏起来，即将一切用户不必了解的细节封装起来，从而简化了问题。（2）抽象数据类型：是指一个数学模型以及定义在此数学模型上的一组操作，ADT有两个重要特征：数据抽象：用ADT描述程序处理的实体时，强调的是其本质的特征、其所能完成的功能以及它和外部用户的接口（即外界使用它的方法）数据封装：将实体的外部特性和其内部实现细节分离，并且对外部用户隐藏其内部实现细节。抽象数据类型的描述方法：抽象数据类型可用（D,S,P）三元组表示。其中，D是数据对象，S是D上的关系集，P是 对D的基本操作集。ADT抽象数据类型名数据对象：数据对象的定义数据关系：数据关系的定义基本操作：基本操作的定义 ADT抽象数据类型名其中，数据对象和数据关系的定义用伪码描述，基本操作的定义格式为基本操作名（参数表）初始条件：初始条件描述操作结果：操作结果描述基本操作有两种参数：赋值参数只为操作提供输入值；引用参数以&打头，除可提供输入值外，还将返回操作结果。“初始条件”描述了操作执行之前数据结构和参数应满足的条件，若不满足，则操作失败，并返回相应出错信息。“操作结果”说明了操作正常完成之后，数据结构的变化状况和应返回的结果。若初始条件为空，则省略之。抽象数据类型的表示和实现：需要通过固有数据类型（高级编程语言中已实现的数据类型）来实现。1.3 算法和算法分析1.3.1 算法特性算法是为了解决某类问题而规定的一个有限长的操作序列。个算法必须满足以下五个重要特性：（1）有穷性对于任意一组合法输入值，在执行有穷步骤之后一定能结束，即：算法中的每个步骤都能在有限时间内完成；（2）确定性对于每种情况下所应执行的操作，在算法中都有确切的规定，使算法的执行者或阅读者都能明确其含义及如何执行。并且在任何条件下，算法都只有一条执行路径；（3）可行性算法中的所有操作都必须足够基本，都可以通过已经实现的基本操作运算有限次实现之；（4）有输入作为算法加工对象的量值，通常体现为算法中的一组变量。有些输入量需要在算法执行过程中输入，而有的算法表面上可以没有输入，实际上已被嵌入算法之中；（5）有输出它是一组与“输入”与确定关系的量值，是算法进行信息加工后得到的结果，这种确定关系即为算法的功能。1.3.2 算法描述算法可使用自然语言、程序流程图、N-S 图、伪码语言等方法来描述。L3.3算法性能分析与度量对于同一个问题的不同算法，如何来评价这些算法的优劣？首先，选用的算法应是“正确的”。其次，主要考虑以下3点(1)执行算法所耗费的时间。(2)执行算法所耗费的存储空间，其中主要考虑辅助存储空间。(3)算法应易于理解、易于编码、易于调试。1.时间复杂度一个特定算法的“运行工作量”的大小，只依赖于问题的规模(通常用整数量n表 示)，或者说，它是问题规模的函数。假如，随着问题规模n的增长，算法执行时间的增长率和f(n)的增长率相同，则可记作：T(n)=O(f(n),称T(n)为算法的(渐近)时间复杂度如何估算算法的时间复杂度？算 法=控 制 结 构+原操作算法的执行时间=原操作的执行次数x原操作的执行时间。算法的执行时间与原操作执行次数之和成正比。从算法中选取一种对于所研究的问题来说是基本操作的原操作，以该基本操作在算法中重复执行的次数作为算法运行时间的衡量准则。例：for(i=1;i=n;+i)for(j=l；j=n;+j)ci,j=0;for(k=l;k=n;+k)ci,j+=ai,k*bk,j;)基本操作：乘法操作。时间复杂度：0(n3)按数量级递增排列，常见的时间复杂度为：0(l)0(log 2)O(n)O(n 蜒力 0(n2)0(n3)l a s t=l;r e t u r n L;)E l s er e t u r n -1;)2 .插入运算顺序表的插入是指在表的第i个位置上插入一个值为x的新元素，插入后使原表长为n的表(ai,a i-i,a .,a j成为表长为 n+1 的表(a i,a z,x,a”an)顺序表上完成这一运算的步骤如下：(1)将a i至a n顺序向后移动，为新元素让出位置。(2)将x置入空出的第i个位置。(3)修改l a s t t指针(相当于修改表长)，使之仍指向最后一个元素。顺序表的插入算法(见PI6)顺序表的插入.p p t此算法的时间复杂度为：O(n)3 .删除运算顺序表的删除是指将表中第i个元素从表中去掉，删除后使原表长为n的表，,a i,比,&+I，a n)成为表长为 n-1 的表(a i,a M,ai+i,an)顺序表上完成这一运算的步骤如下：(1)将a i+i至a n顺序向前移动，为新元素让出位置。(2)修改I s a t指针(相当于修改表长)，使之仍指向最后一个元素。顺序表的删除算法(见P18)此算法的时间复杂度为：0(n)4.按值查找顺序表中的按值查找是指在表中查找与给定值x相等的数据元素。顺序表上完成这一运算的方法是：从第一个元素山开始，依次和x比较，直到找到一个与x相等的数据元素,则返回它在顺序表中的序号；若查遍整个表都没有找到与x相等的元素，则返回-1。顺序表的按值查找算法(见P19)此算法的时间复杂度为：0(n)【作业布置】P38的习题2。【教学后记】通过本章教学，学生掌握了顺序表的定义及基本操作的实现。第2 章 2.3线性表的链式存储和运算实现【教学目的要求】使学生掌握单链表的定义及基本运算的实现；掌握循环链表和双向链表的定义。【重点】单链表的定义及基本运算的实现。【难点】单链表的运算实现。【教学方法】多媒体教学和传统教学相结合。【课时安排】4学时。【教学过程】K导入U上堂课学习过的线性表的顺序存储特点是用物理上相邻实现了逻辑上的相邻，它要求用连续的存储单元顺序存储线性表中和各元素，因此，对顺序表的插入、删除需要通过移动元素来实现，影响了运行效率。本堂课我们将介绍线性表链式存储结构，它不需要用连续的存储单元来实现。K讲解H2.3.1单链表用一组地址任意的存储单元存放线性表中的数据元素。以元素（数据元素的映象）+指针（指示后继元素存储位置的）=结点（表示数据元素）。以“结点的序列”表示线性表，称作链表。以线性表中第一个数据元素a l的存储地址作为线性表的地址，为线性表的头指针。链表是由一个个结点构成的，结点定义如下：typedef struct Node DataType data;/数据域datanextstruct Node*next;/指针域 LNode,*LinkList;说明：1.LNode是结点的类型。2.LinkList是指向LNode类型结点的指针类型。3.LNode*P表示定义了一个指向某结点的指针变量。4.P=new LNode;表示申请一块LNode类型的存储单元。p-data P-next5.上述P 所指向结点的数据域可表示为p-data,指针域可表示为P-nexto6.delteP;表示释放P 所指向的结点。2.3.2单链表上基本运算的实现1.建立单链表(1)在链表的头部插入结点建立单链表算法略(2)在链表的尾部插入结点建立单链表算法略单链表的建立.PPt2.求表长(1)设 L 是带头结点的单链表算法略(2)设 L 是不带头结点的单链表算法略3.查找操作(1)按序号查找 Get_Linklist(L,i)算法略(2)按值查找即定位 Locate_Linklist(L,x)4.插入(1)在某结点p 后面插入新结点操作如下：s-next=p-next;/插入 L 中 p-next=s;(2)在某结点p前面插入新结点先要找到结点p的前驱结点q,再在结点q的后面插入。(3)插入运算 Insert_LinkList(L,i,x)算法思路：查找第i-1个结点，若存在，继续，否则结束申请、填装新结点。将新结点插入，结束。算法略算法的时间复杂度为：O(n)5.删除(1)删除结点设p指向单链表中某结点，删 除p结点，操作如下：q-next=p-next;delete p;(2)删除运算 Delete_LinkList(L,i)算法思路：查找第i-1个结点，若存在，继续，否则结束若存在第i个结点则继续，否则结束。删除第i个结点，结束。算法略算法的时间复杂度为：0(n)2.3.3 循环链表最后一个结点的指针域的指针又指回第一个结点的链表。2.3.4 双向链表双向链表结点的定义如下：typedef struct DLnode DataType data;II 数据域struct DLNodeprior,*next;指向前驱和后驱的指针域 DLNode,*DLinkList;(1)在双向链表中插入一个结点设 p 是指向双向链表中某结点，s 指向待插入的值为x 的新结点，将 s 结点插入到p结点的前面，操作如下：0s-prior=p-prior;(2)p-prior-next=s;(3)s-next=p;p-prior=s;(2)在双向链表中删除指定结点设 p 是指向双向链表中某结点，删 除 p 结点。操作如下：(Dp-prior-next=p-next;(2)p-next-prior=p-prior;delete p;【作业布置】P39的习题6。【教学后记】通过本章教学，学生掌握了线性表的逻辑结构和线性表的顺序及链式存储，但对这二种存储的运算实现还不太理解，以后在教学中应加强学生对算法的理解和设计。第3章3.1栈【教学目的要求】使学生掌握栈的概念及基本运算操作，并能利用它解决实际问题。学会栈满和栈空的判断方法。【重点】栈的定义和判空与判满。【难点】栈的应用。【教学方法】多媒体教学和传统教学相结合。【课时安排】2学时。【教学过程】K导入U栈和队列是在软件设计中常用的两种数据结构，它们的用途非常广泛，这一节我们将先学习栈的有关基本知识及应用。K讲解H3.1 栈3.1.1 栈的定义及基本运算栈是限制在表的一端(表尾)进行插入和删除操作的线性表。允许进行插入和删除操作的这一端称为栈顶，另一个固定端(表头)称为栈底，当表中没有元素时称为空栈。对于栈，常做的基本操作有以下几种：Init_Stack(s)：栈初始化，构造一个 空 栈s。Empty_Stack(s)：判断栈空，若s为空栈，返 回1,否则返回0。Push_Stack(s,x)：入栈，插入新元素x为栈顶元素。Pop_Stack(s)：出栈，若栈不空，则删除s 的栈顶元素。Top_Stack(s)：读栈顶元素。Destroy_Stack(s)：销毁栈s,s 不再存在。Clear_Stack(s)：把 s 置为空栈。Length_Stack(s)：求栈的长度，返回s 的元素个数。3.1.2 栈的存储实现和运算实现1 .顺序栈利用顺序存储方式实现的栈称为顺序栈。类似于顺序表的定义。顺序栈的类型描述如下：#define MAXSIZE MAXSIZE为根据实际问题定义的足够大的整数typedef struct DateType datefMAXSIZE;int top;SeqStack;SeqStack*s;/定义一个指向顺序栈的指针变量。在上述存储结构上，栈基本操作的实现见P4142算法。2.链栈利用链式存储方式实现的栈称为链栈，注意链表中指针的方向是从栈顶到栈底。3.1.3 栈的应用举例例 3.1 数制转换问题十进制数N 和其他d 进制数的转换是计算机实现计算的基本问题，其解决方法很多，其中一个简单算法基于下列原理：N=(N/d)Xd+N%d,(其中：/为整除运算，为求余运算)。例 如:(3467)10=(6613)8,其运算过程如下：NN/8N%8346743334335415466606假设现要编制一个满足下列要求的程序：对于输入的任意一个非负十进制整数，打印输出与其等值的八进制数。由于上述计算过程是从低位到高位顺序产生八进制数的各个数位，而打印输出，一般来说应从高位到低位进行，恰好和计算过程相反。因此，若将计算过程中得到的八进制数的各位顺序进栈，则按出栈序列打印输出的即为与输入对应的八进制数。算法如下：Typedef int Datatype;void conversion(int N,int r)SeqStack s;Datatype x;Init_ SeqStack(&s);/构造空栈scanf(%d,N);while(N)Push_ SeqStack(&s,N%r);N=N/r;while(!Empty_SeqStack(&s)Pop_SeqStack(&s,&x);coutx;)coutendl;这是利用栈的后进先出特性的最简单的例子。在这个例子中，栈操作的序列是直线式的，即先-味地入栈，然后一味地出栈。也许，有的读者会提出疑问：用数组直接实现不也很简单吗？仔细分析上述算法不难看出，栈的引入简化了程序设计的问题，划分了不同的关注层次，使思考范围缩小了。而用数组不仅掩盖了问题的本质，还要分散精力去考虑数组下标增减等细节问题。例3.2迷宫问题(略)例3.3表达式求值(略讲)【作业布置】P62的习题2。【教学后记】通过本章教学，学生掌握了栈抽象数据类型的特点及栈满和栈空的判断条件，但用它解决实际问题还有待加强。第3章 3.2 队列【教学目的要求】使学生掌握队列的概念及基本运算操作，并能利用它解决实际问题。学会队列满和空的判断方法。【重点】队列的定义和判空与判满。【难点】循环队列。【教学方法】多媒体教学和传统教学相结合。【课时安排】2学时。【教学过程】K导入H上堂课我们学习了两种重要的数据结构之一：栈，本堂课我们将继续学习另外一种重要的数据结构，队列。K讲解3.2队列3.2.1 队列的定义及基本运算队列是一种“先进先出”的数据结构，即插入操作在表的一端进行，而删除操作在表的另一端进行。把允许进行插入操作的一端称队尾(re a r),允许进行删除操作的一端称队首(f ro n t)o对于队列，常做的基本操作有以下几种：Init_Queue(q)：队列初始化，构造一个空队列q。Empty_Queue(q)：判断队空，若q为空栈，返 回1,否则返回0。In_Queue(q,x)：入队，插入新元素x到队尾。Out_Queue(q,x)：出队，若队不空，则删除队首元素。Front_Queue(q,x)：读队首元素。3.2.2队列的存储实现和运算实现1.顺序队顺序存储的队列称顺序队。其类型定义如下：#define MAXSIZE.II MAXSIZE为根据实际问题定义的足够大的整数typedef struct DateType dateMAXSIZE;int rear,front;SeQueue;SeQueue*sq;/定义一个指向队列的指针变量。申请一个顺序队的存储空间：sq=new SeQueue;通常设队首指针指向队首元素前面一个位置，队尾指针指向队尾元素，则空队列时，操作为：sq-front=sq-rear=-l;在不考虑溢出的情况下，入队操作为：sq-rear+；sq-datasq-rear=x;在不考虑队空的情况下，出队操作为：sq-front+；x=sq-datasq-front;队中元素的个数：m=(sq-rear)-(sq-front)队满时：m=MAXSIZE队空时：m=0按照上述思想，随着入队、出队的进行，会使整个队列整体向后移动，这样就会出现“队尾指针移动到了最后，再有元素插入队列就会出现溢出”的现象，而实事上此时队列并非 真 的“满员”，此现象称为“假溢出”。解决办法：将队列的数据区data dataMAXSIZE-l,看成首尾相接的循环结构，首尾指针的关系不变，将 其 称 为“循环队列”，如图所示：因为是首尾相接的循环结构，入队时的队尾指针加1,操作修改为sq-rear=(sq-rear+l)%MAXSIZE出队时的队首指针加1,操作修改为sq-front=(sq-front+1 )%MAXSIZE按照上述思想，随着新元素的相继入队，会出现队满的情况，此时有sq-front=sq-rear随着元素的相继出队，会出现队空的情况，此时也有sq-front=sq-rear也 就 是 说“队满”和“队空”的判断条件是相同的，解决办法方法一：附设一个存储队列中元素个数的变量(如num)当num=O时，队空当 num=MAXSIZE 时 一，队满。方法二：少用一个元素空间，约 定 以“队列头指针在队列尾指针的下一位置上”作为队 列 呈“满”状态的标志。此时的状态是队尾指针加1,就会从后面赶上队首指针，此时队满的条件是：(sq-rear+l)%MAXSIZE=sq-front,与队空 sq-rear=sq-front 相区别。书上的循环队列及操作按方法一实现。循环队列的类型定义为：typedef struct DateType datefMAXSIZE;int rear,front;C-SeQueue;循环队列的基本运算算法见P57-58o【作业布置】P63的习题6。【教学后记】通过本章教学，学生掌握了队列抽象数据类型的特点及队满和队空的判断条件,也能将它应用于实际问题中。但对循环队列的基本操作实现算法及应用难以理解，以后应强化这知识的教学。第6章 6.1二叉树的定义与性质、6.2二叉树的基本操作与存储实现【教学目的要求】使学生熟练掌握二叉树的定义及相关概念，了解二叉树的性质及相应的证明方法；熟悉二叉树的各种存储结构的特点及适用范围，了解二叉树的基本操作及算法的实现。【重点】二叉树的定义和性质，满二叉树和完全二叉树的概念及其判定。【难点】二叉树基本操作的算法实现。【教学方法】多媒体教学和传统教学相结合。【课时安排】2课时。【教学过程】K导入U前面几章讨论的是数据结构都属于线性结构，从本章开始，将讨论非线性结构。本堂课我们将学习二叉树的定义与性质、及二叉树的基本操作与存储实现。K讲解6.1 二叉树的定义与性质6.1.1 二叉树的基本概念1.二叉树的定义二叉树是有限个特性相同的数据元素的集合，该集合或为空树；或 是 由 一个根结点及两棵互不相交的、被分别称为左子树和右子树的二叉树组成。二叉树的五种基本形态：X Z If2.二叉树的相关概念结点：数据元素+若干指向子树的分支。结点的度：结点所拥有的子树的个数。叶子结点：度为0 的结点。分支结点：度不为0 的结点。左孩子、右孩子、双亲、兄弟：树中一个结点X 的子树的根结点称为结点X 的孩子。在二叉树中，左子树的根称为左孩子、右子树的根称为右孩子。X 称为它孩子的双亲。具有同一个双亲的孩子结点互称为兄弟路径、路径长度：如果一棵树的一串结点nl,n2,.,nk有如下关系：结点n i是 ni+1的父结点（l n,则该结点无左孩子，否则，编号为2 i的结点为其左孩子结点；(3)若 2i+l n,则该结点无右孩子，否则，编号为2i+I的结点为其右孩子结点。6.2二叉树的基本操作与存储实现6.2.1二叉树的存储1.顺序存储结构用一组连续的存储单元存放二叉树中的结点。一般是按照二叉树结点从上至下、从左至右的顺序存储。对于一般二叉树，这种存储并不能反映二叉树中结点之间的逻辑关系，只有添加一些并不存在的空结点，使之成为完全二叉树的形式，才能反映出来，这样在最坏的情况下，一个深度为k 且只有k 个结点的单支树(树中不存在度为2 的结点)却需要长度为21M 的一维数组，大大浪费空间。所以这种顺序存储结构仅适用于完全二叉树和满二叉树。二叉树的顺序存储表示可描述为：#define Maxnode.typedef DateType SqBiTreefMaxnode;/0 号单元存储根结点SqBiTree bt;2.链式存储结构是指用链表来表示一棵二叉树，通常有下面二种形式：(1)二叉链表存储链表中每个结点由3 个域组成。结点的存储结构为：二叉树的二叉链表存储表示可描述为：typedef struct BiTNode DataType data;struct BiTNode*lchild,*rchild;/左右孩子指针 BiTNode,*BiTree;(2)三叉链表(略讲)链表中每个结点由4 个域组成。结点的存储结构为:Ichilddatarchildparent6.2.2 二叉树的基本操作及实现(见PHO-H.)略讲1 .二叉树的基本操作1)Initiate(bt)2)Create(x,Ibt,rbt)3)InsertL(bt,x,parent)4)InsertR(bt,x,parent)5)DeleteL(bt,parent)6)DeleteR(bt,parent)7)Search(bt,x)8)Traverse(bt)2 .算法的实现基于二叉链表存储结构的Create(x,Ibt,rbt)和DeleteL(bt,parent)实现算法。【算法6-2】建立一棵已生成左右子树的二叉树的算法。B i T re e C re ate(DataT y p e x,B i T re e I bt,B i T re e rbt)B i T re e p;P=n e w B i T N o d ei f(!p)re tu rn N U L L;p-d ata=x;p-l c h i l d=l bt;p-rc h i l d=rbt;re tu rn p;【算 法6-4】删除二叉树中某结点的左子树的算法。B i T re e De l e te L(B i T re e bt,B i T re e p are n t)B i T re e p;i f (p are n t=N U L L j p are n t-I c h i i d=N U L L)re tu rn N U L L;p二p are n t-l c h i I d;p are n t-l c h i 1 d=N U L L;d e l e te p;re tu rn bt;【作业布置】习 题P 1 3 7的 第1题 的(1)、(2)【教学后记】通过本章教学，学生掌握了二叉树的定义及相关概念，掌握了二叉树的基本性质，但因课时量不够，二叉树的基本操作的算法实现讲解太快，所以学生对二叉树的基本操作的算法实现掌握欠佳。第6章 6.3二叉树的遍历、6.4线索二叉树【教学目的要求】使学生熟练掌握二叉树遍历的三种方式及相应的递归定义和算法，了解遍历过程中 栈”的作用和状态，而且能灵活运用遍历算法实现二叉树的其它操作。理解的实质是建立结点与其在相应序列中的前驱或后继之间的直接联系，熟练掌握二叉树的线索化过程以及在中序线索化树上找给定结点的前驱和后继的方法。二叉树的线索化过程是基于对二叉树进行遍历，而线索二叉树上的线索又为相应的遍历提供了方便。【重点】二叉树遍历的三种方式，线索二叉树的定义及结构。【难点】二叉树遍历的算法实现，线索二叉树的基本操作实现。【教学方法】多媒体教学和传统教学相结合。【课时安排】2课时。【教学过程】K导入U遍历是二叉树中经常要用到的一种操作。遍历操作使非线性结构线性化。本堂课我们将学习二叉树的遍历和线索。K讲解U6.3 二叉树的遍历6.3.1 二叉树的遍历方法及递归实现二叉树的遍历是指按照某种顺序访问二叉树中的每个结点，使得每个结点均被访问一次且仅被访问一次。遍历是二叉树中常用的操作。若限定先左后右，则二叉树的遍历方式有三种：1.先序遍历(DLR)先序遍历的递归过程为：若二叉树为空，遍历结束；否则，步骤如下：1)访问根结点；2)先序遍历根结点的左子树；3)先序遍历根结点的右子树；例如：图6-3(b)所示的二叉树，按先序遍历所得到的结点序列为：A B D G C E F【算法6-5】二叉树先序遍历算法Viod preorder(BiTree bt)if(bt=NULL)return;Visit(bt-data);preorder(bt-lchild);preorder(bt-rchi Id);)2.中序遍历(LDR)中序遍历的递归过程为：若二叉树为空，遍历结束；否则，步骤如下：1)中序遍历根结点的左子树；2)访问根结点；3)中序遍历根结点的右子树；例如：图6-3(b)所示的二叉树，按中序遍历所得到的结点序列为：D G B A E C F【算法6-6】二叉树中序遍历算法(略)3.后序遍历后序遍历的递归过程为：若二叉树为空，遍历结束；否则，步骤如下：1）后序遍历根结点的左子树；2）后序遍历根结点的右子树；3）访问根结点；例如：图6-3（b）所示的二叉树，按中序遍历所得到的结点序列为：GD B EFC A【算法6-7】二叉树后序遍历算法（略）4.层次遍 历是指从二叉树的第一层（根结点）开始，从上至下逐层遍历，在同一层中，则按从左至若的顺序对结点逐个访问。例如：图60（b）所示的二叉树，按层次遍历所得到的结点序列为：A B C D EFG【算法6-8】二叉树层次遍历算法（略）6.3.2 二叉树遍历的非递归实现（略）6.3.3 由遍历序列恢复二叉树1.由二叉树先序序列和中序序列可以唯一地确定一棵二叉树，方法：在先序序列中，第一个结点是根结点，根结点在中序序列中将中序序列分成二个子序列，前一个子序列是根结点的左子树的中序序列，后一个子序列是根结点的右子树的中序序列，根据这二个子序列，在先序序列中找到对应的左子序列和右子序列。在先序序列中，左子序列的第一个结点是左子树的根结点，右子序列的第一个结点是右子树的根结点。这样便确定了二叉树的3 个结点，如此递归下去，当取尽先序序列中所有的结点时，便可以得到一棵二叉树。例如：已知一棵二叉树的先序序列和中序序列分别为A B C D E F G H I B C A E D G H FI试恢复该二叉树2.由二叉树后序序列和中序序列可以唯一地确定一棵二叉树，方法：（见 P118）思考：由二叉树先序序列和后序序列是否可以唯一地确定一棵二叉树？6.4 线索二叉树6.4.1 线索二叉树定义及结构1.线索二叉树的定义遍历二叉树的结果是：得到结点的-个线性序列。在该序列中，除第一个结点外，每个结点有且只有一个直接前驮，除最后一个结点外，每个结点有且只有一个直接后继，但二叉树中每个结点在这个序列中的直接前驱和H接后继在二叉树的存储结构中并没有反映出来，只能在对二叉树遍历的动态过程中得到这些信息。为了保留这些信息，可以利用二叉链表存储结构中的那些空指针域来指示。这些指向直接前驱和直接后继的指针，称 作“线索”。包 含“线索”的存储结构，称 作“线索链表”，与其相应的二叉树，称 作“线索二叉树”。2.线索二叉树的结构对线索链表中结点的约定：在二叉链表的结点中增加左、右两个标志域，并作如下规定：若该结点的左子树不空，则I c h i l d域的指针指向其左子树，且右标忐域的值为0；否则，I c h i l d域的指针指 向 其“前驱”，且左标志的值为1。若该结点的右子树不空，则r c h i l d域的指针指向其右子树，且右标志域的值为0;否则，r c h i l d域的指针指向其“后继”，且右标志的值 为1。即f 0 I c h i l d指向结点的左孩子l t a g=，结点的结构为：1 1 I c h i l d指向结点的前驱结点f 0 r c h i l d指向结点的右孩子r t a g=Ichild;If(p-ltag!=l)while(pre-rtag=O)pre=pre-rchild;return pre;)3.在中序线索二叉树上查找任意结点的中序后继结点对于中序线索二叉树上的任意结点，查找其中序的后继结点，有以下二种情况：1)如果该结点的右标志为1,则其右指针域所指向的结点便是它的后继。2)如果该结点的右标志为0,则沿着其右子树的左指针链向下查找，当某结点的左标志为1时，它就是所要找的后继。【算法6-1 4】中序线索二叉树上查找结点p的中序后继结点算法BiThrTree InPostNode(BiThrTree p)BiThrTree post;post=p-rchild;If(p-rtag!=l)while(post-ltag=0)post=post-lchild;return post;)4.在中序线索二叉树上查找任意结点的先序后继结点(略)IPrePostNode(BiThrTree head,BiThrTree p)5.在中序线索二叉树上查找任意结点的后序前驱结点(略)IPostPreNode(BiThrTree head,BiThrTree p)6.在中序线索二叉树上查找值为x 的结点在中序线索二叉树上查找值为x 的结点，实质就是在线索二叉树上进行遍历，将访问结点的操作具体写为用当前结点的值与x 比较的语句。【算法6-17在中序线索二叉树上查找值为x的结点算法BiThrTree Search(BiThrTree head,DataType x)BiThrTree p;p=head-(child;pre=p-lchild;while(p!=head&p-ltag=O)p=p-lchild;while(p!=head&p-data!=x)p=InPostNode(p);if(p=head)return NULL;elsereturn p;)7.在中序线索二叉树上的更新在中序线索二叉树上的更新是指：在线索二叉树中插入一个结点或者删除一个结点。在这里只讨论在中序线索二叉树中插入一个结点p,使它成为结点s 的右孩子。分二种情况进行分析：1)若 s 的右子树为空2)若s的右子树非空【算法6-18在中序线索二叉树中插入一个结点的算法void InsertThrRight(BiThrTree s9 BiThrTree p)BiThrTree w;p-rchild=s-rchild;p-rtag=s-rtag;p-lchild=s;p-Itag=l;s-rchild=p;s-rtag=0;if(p-rtag=0)w=InPostNode(p);w-lchild=p;)【作业布置】习题P138的12、P 139的20o【教学后记】通过本堂课教学，学生掌握了二叉树遍历的三种方式和二叉树的线索化过程以及在中序线索化树上找给定结点的前驱和后继的方法，但对二叉树遍历的算法实现和线索二叉树的基本操作的实现还不太理解，以后在教学中应加强学生对算法的理解和设计。第6章 6.6哈夫曼树【教学目的要求】使学生熟练掌握哈夫曼树的基本概念及构造方法；掌握哈夫曼编码及设计方法。【重点】哈夫曼树的构造方法和哈夫曼编码的设计方法。【难点】哈夫曼树的构造算法和哈夫曼编码算法。【教学方法】多媒体教学和传统教学相结合。【课时安排】2课时。【教学过程】K导入U在二叉树的许多应用问题中，特别是涉及算法分析和数据编码的应用中，路径长度是-种很重要的概念。哈夫曼树就是带权路径长度最小的二叉树。本堂课我们将学习哈夫曼树的基本概念、构造方法及算法，并在此基础上进一步学习哈夫曼编码。K讲解U6.6 哈夫曼树6.6.2 哈夫曼树的基本概念及其构造方法1.有关定义结点的路径长度：从根结点到该结点的路径上分支的数目。二叉树的路径长度：由根结点到所有叶子结点的路径长度之和。二叉树的带权路径长度：设二叉树具有n 个带权值的叶子结点，那么从根结点到各叶子结点的路径长度与相应结点权值的乘积之和。记为：WPL(T)=WkLkk=哈夫曼树(最优二叉树)：给定一组具有确定权值的叶子结点，可以构造出不同的带权二叉树，在这些二叉树中，带权路径长度最小的叉树称为哈夫曼树(最优二叉树)。2.如何构造哈夫曼树哈夫曼最早研究出一个带有一般规律的算法：(1)根据给定的 个权值 必,卬2,，卬 ，构造棵二叉树的集合尸其中每棵二叉树中均只含一个带权值为帅的根结点，其左、右子树为空树；(2)在尸中选取其根结点的权值为最小的两棵二叉树，分别作为左、右子树构造一棵新的二叉树，并置这棵新的二叉树根结点的权值为其左、右子树根结点的权值之和；(3)从产中删去这两棵树，同时加入刚生成的新树；(4)重复(2)和(3)两步，直至尸中只含一棵树为止。例子：(见书P132)6.6.3 哈夫曼树的构造算法(略)6.6.4 哈夫曼编码先看P134的例子讲解，由此引入哈夫曼编码的概念。哈夫曼编码：是指任何一个字符的编码都不是同一字符集中另一个字符的编码的前缀。它是一种最优前缀编码。求哈夫曼编码的方法：设需要编码的字符集合为dl,d2,.,dn,它们在电文中出现的次数或频率集合为wl,w2,.,wn,以数,d2,d