《数据结构与算法》教案

2第一节什么是数据结构一、数据结构概述一般来说，用计算机解决一个具体问题时，大致需经过以下几个步骤：1、从具体问题抽象出一个适当的数学模型。2、设计一个解此数据模型的算法。3、编出程序，进行测试、调整直至得到最终解答。如：求解梁架结构中应力的数学模型为线性方程组；预报人口增长情况的数学模型为微分方程。然而：更多的非数值计算问题无法用数学方程加以描述。特点：每个学生的信息占据一行，所有学生的信息按学号顺序依次排列构成一张表格；表中每个学生的信息依据学号的大小存在着一种前后关系，这就是我们所说的线性结构；对它的操作通常是插入某个学生的信息，删除某个学生的信息，更新某个学生的信息，按条件检索某个学生的信息等等。例子：P1例1.1学生健康情况管理。图书馆的书目检索系统自动化问题。查号系统自动化；仓库账目管理……例子：求一组（n个）整数中的最大值。算法：基本操作是“比较两个数的大小”。特点：在求解过程中，所处理的数据之间具有层次关系，这是我们所说的树形结构；对它的操作有：建立树形结构，输出最低层结点内容等等。另外例子：#字棋。教材P1例1.2人事档案管理。例子：计算机对弈。算法：对弈的规则和策略。其他例子：多叉路口交通灯的管理问题。教材P1例1.3在n个城市之间建立通信网络。特点课程之间的先后关系用图结构描述；通过实施创建图结构，按要求将图结构中的顶点进行线性排序。结论1、当今计算机应用的特点：所处理的数据量大且具有一定的关系；对其操作不再是单纯的数值计算，而更多地是需要对其进行组织、管理和检索。2、《数据结构》课程研究的主要内容。计算机的操作对象的关系更加复杂，不再是单纯的数值计算，而更多地是非数值性处理。数据结构描述现实世界实体的数学模型（非数值计算）及其上的操作在计算机中的表示和实现。数据结构研究非数值计算的程序设计问题中数据以及它们之间的逻辑关系和对数据的操作的一门课程。重点分析数据之间的抽象的相互关系，而不涉及数据的具体内容。二、数据结构的发展概况起源于程序设计的发展，程序设计经历三个阶段：无结构阶段；结构化程序设计阶段；面向对象阶段。教材中详述第二个阶段，即P2-4中（2）-（5）。三、数据结构与其他课程的关系数据结构是介于数学、计算机硬件和计算机软件三者之间的一门核心课程。第二节基本概念和术语一、数据是对客观事物的符号表示。在计算机科学中其含义是指所有能够输入到计算机中并被计算机程序处理的符号集合。含义极为广泛：图像、声音等。二、数据元素（节点）：数据的基本单位是数据集合中的一个实体，是计算机程序中加工处理的基本单位。如学籍管理中每个学生的信息；“树”中的每一点；“图”中的每一个圆圈。数据元素按其组成可分为简单型数据元素和复杂型数据元素。简单型数据元素由一个数据项组成，所谓数据项就是数据中不可再分割的最小单位；复杂型数据元素由多个数据项组成，它通常携带着一个概念的多方面信息。三、逻辑结构：数据元素之间的逻辑关系。数据结构中所说的“关系”实际上是指数据元素之间的逻辑关系，又称此为逻辑结构。如前后关系；上下层关系；先后关系。根据数据元素之间的逻辑结构可将数据结构分为三类：线性结构——一个对一个。如，线性表、栈、队列。树形结构——一个对多个。如，树。图状结构——多个对多个，如，图。四、存储结构（物理结构）是指数据结构在计算机存储器中的具体实现。与孤立的数据元素表示形式不同，数据结构中的数据元素不但要表示其本身的实际内容，还要表示清楚数据元素之间的逻辑结构。即数据元素的表示和关系的表示两部分。1、数据元素的表示：位数据域元素或结点（表示信息的最小单位）（子位串，对应于各数据项）（位串）2、关系的表示：即常见的存储结构顺序存储结构：特点是借助于数据元素的相对存储位置来表示数据元素之间的逻辑结构；P6图1.5a链式存储结构：特点是借助于指示数据元素地址的指针表示数据元素之间的逻辑结构。P6图1.5b数据的逻辑结构与存储结构密切相关：算法设计 逻辑结构 算法实现 存储结构 五、数据结构：带结构的数据元素的集合。简单地说，就是相互之间存在一种或多种特定关系的数据元素的集合。常见的数据结构有：线性结构、树形结构和图形结构。1、根据数据元素之间关系的不同特征，通常有下列四类基本结构：集合（散列）；线性结构（1：1）；树形结构（1：N）；图状结构（M：N）。2、数据结构的形式定义：数据结构是一个二元组（D，S）。其中D是数据元素的有限集，S是D上关系的有限集。例如：六.数据类型:数据的取值范围及其操作的总称。例:C语言中，提供int,char,float,double等基本数据类型，数组、结构体、共用体、枚举等构造数据类型，还有指针、空(void)类型等。用户也可用typedef自定义数据类型第二讲课题名称：第一章绪论 第3节抽象数据类型的表示和实现 第4节算法教学目标： 1、使学生了解数据类型的表示和实现； 2、使学生了解用类C语言对算法的表示和实现。教学重点和难点：类C语言的理解主要教学方法和手段：多媒体课件讲授教学课时：2课时课的类型：讲授课教学内容：第三节抽象数据类型的表示与实现为了表示一个算法，可以用不同的方法。常用的有自然语言、传统流程图、伪代码、PAD图等。1、用自然语言表示算法：通俗易懂，但文字冗长，易出现“歧义性”。如：“张先生对李先生说他的孩子考上了大学。”2、用流程图表示算法：直观形象，易于理解。三种基本结构的表示：顺序结构、先择结构、循环结构。只有一个入口，只有一个出口，结构内的每一部分都有机会被执行到，结构内不存在“死循环”。仅适用于小问题，现在已很少用。3、用伪代码表示算法：4、用计算机语言表示算法：如C或PASCAL5、用类C或类PASCAL语言算法描述：介于伪码与C之间选择算法描述语言的准则（1）该语言应该具有描述数据结构和算法的基本功能；（2）该语言应该尽可能地简捷，以便于掌握、理解；（3）使用该语言描述的算法应该能够比较容易地转换成任何一种程序设计语言。“类C”描述语言是通过对C语言进行精心筛选保留的一个核心子集，并为了便于描述，又做了若干扩展修改，从而，增强了语言的描述功能。以下对类C做简要说明。1.预定义常量及类型#defineTRUE1#defineFALSE0#defineOK1#defineERROR0#defineINFEASIBLE-1#defineOVERFLOW-2数据元素被约定为EntryType类型，用户需要根据具体情况，自行定义该数据类型。数据结构的表示（即存储结构的表示）使用类型定义（typedef）描述。2.算法描述为以下的函数形式：函数类型函数名（函数参数表）{语句序列；}为了简化函数的书写，提高算法描述的清晰度，我们规定除函数参数表中的参数需要说明数据类型外，函数中使用的局部变量可以不做变量说明，必要时给出相应的注释即可。另外，在书写算法时，应该养成对重点语句段落添加注解的良好习惯。一般而言：abcde等用作数据元素名；ijklmn等用作整型变量名；pqr等用作指针变量名；当函数返回值为函数结构状态代码时，函数定义为Status类型；除值调用方式外，增添C++的引用调用的参数传递方式（&）。3.在算法描述中可以使用的赋值语句形式有：简单赋值变量名=表达式；串联赋值变量名1=变量名2=...=变量名n=表达式；成组赋值（变量名1，...，变量名n）=（表达式1，...，表达式n）；变量名[]=表达式；变量名[始下标..终下标]=变量名[始下标..终下标]；结构赋值结构名1=结构名2；结构名=（值1，值2，...，值n）；条件赋值变量名=条件表达式?表达式1：表达式2；交换赋值变量名1«变量名2；4.在算法描述中可以使用的选择结构语句形式有：条件语句1if（表达式）语句；条件语句2if（表达式）语句；else语句；开关语句1switch（表达式）{case值1：语句序列1；break；case值2：语句序列2；break；...case值n：语句序列n；break；default：语句序列n+1；}开关语句2switch{case条件1：语句序列1；break；case条件2：语句序列2；break；...case条件n：语句序列n；break；default：语句序列n+1；}5.在算法描述中可以使用的循环结构语句形式有：for循环语句for（赋初值表达式;循环条件表达式;修改表达式序列）语句；while循环语句while（循环条件表达式）语句；do-while循环语句do{语句序列；}while（循环条件表达式）；6.在描述算法中可以使用的结束语句形式有：函数结束语句return表达式；return;case或循环结束语句break;异常结束语句exit（异常代码）；7.在算法描述中可以使用的输入输出语句形式有：输入语句scanf([格式串]，变量名1，...，变量名n)；输出语句printf([格式串]，表达式1，...，表达式n);方括号（[]）中的内容是可以省略的部分。8.在算法描述中使用的注释格式为：单行注释//文字序列9.在算法描述中可以使用的扩展函数有：求最大值max（表达式1，...，表达式n）求最小值min（表达式1，...，表达式n）求绝对值abs(表达式)求不足整数值floor(表达式)求进位整数值ceil(表达式)判定文件结束eof(文件变量)或eof判定行结束eoln(文件变量)或eoln10.逻辑运算约定与运算&&对于A&&B，当A的值为0时，不再对B求值。或运算||对于A||B，当A的值为非0时，不再对B求值。例子：【算法1-1】用类C描述将三个数值排序的算法。viodThree_Sort(int*x,int*y,int*z){//将x,y,z三个指针所指示的内容按从小到大的顺序重新排列if(*y<*x&&*y<*z)*x«*y;//挑选出最小的数值并换到x指针所指的存储单元中elseif(*z<*x&&*z<*y)*x«*z;if(*z<*y)*y«*z;//在y和z所指示的存储单元中挑选出较小者换到y中}第四节算法1.4.1算法的概念算法是解决某个特定问题的一种方法或一个过程。计算机对数据的操作可以分为数值性和非数值性两种类型。在数值性操作中主要进行的是算术运算；而在非数值性操作中主要进行的是检索、排序、插入、删除等等。算法是执行特定计算的有穷过程，是对特定问题求解步骤的一种描述，它是指令的有限序列，其中每一条指令表示一个或多个操作。算法应该具有下列五个特性（1）动态有穷：一个算法必须（对任何合法的输入值）在执行有穷步之后结束，且每一步都可在有穷时间内完成。算法必须是一个可执行完的步骤，但一个具有死循环的程序亦称之为程序，这是算法与程序的区别。有穷的概念不是纯数学的，而是在实际上合理和可以接受的。注意：算法和程序是有区别的，即程序未必能满足动态有穷。但在本课程中，只讨论满足动态有穷的程序，因此“算法”和“程序”是通用的。（2）确定性：算法中的每一步，必须有确切的含义，在他人理解时不会产生二义性。（“手举过头顶”）（3）可行性：算法中描述的每一步操作都可以通过已有的基本操作执行有限次实现。（4）输入：一个算法应该有零个或多个输入。（获得信息。）（5）输出：一个算法应该有一个或多个输出。这里所说的输出是指与输入有某种特定关系的量。（目的）举例问题：按从小到大的顺序重新排列x，y，z三个数值的内容。算法：（1）输入x，y，z三个数值；（2）从三个数值中挑选出最小者并换到x中；（3）从y，z中挑选出较小者并换到y中；（4）输出排序后的结果。=>算法就是一个具有次序、步骤清楚、最后一定会执行结束的可执行步骤。算法与程序不同之处在于上述第一条。1.4.2算法的设计要求(1)正确性：要求算法能够正确地执行预先规定的功能，并达到所期望的性能要求。(2)可读性：为了便于理解、测试和修改算法，算法应该具有良好的可读性。(3)健壮性：算法中拥有对输入数据、打开文件、读取文件记录、分配内存空间等操作的结果检测，并通过与用户对话的形式做出相应的处理选择。(4)时间与空间效率：算法的时间与空间效率是指将算法变换为程序后，该程序在计算机上运行时所花费的时间及所占据空间的度量。1.4.3算法效率的度量一、算法的时间效率算法的时间效率主要由两个因素决定：l 所需处理问题的数据量大小，数据量大，所花费的时间就多；l 在解决问题的过程中，基本操作的执行次数。时间特性的分析如果我们将一个算法所花费的时间设计成一个以数据量n为自变量的函数T(n)，这个函数在正整数定义域范围内一定是单调递增的。好的算法应该能够在数据量n增长的同时，函数T(n)的增长速度比较缓慢。P11例子。二、空间效率的分析一个算法的空间效率是指在算法的执行过程中，所占据的辅助空间数量。辅助空间就是除算法代码本身和输入输出数据所占据的空间外，算法临时开辟的存储空间单元。在有些算法中，占据辅助空间的数量与所处理的数据量有关，而有些却无关。后一种是较理想的情况。在设计算法时，应该注意空间效率。第三讲课题名称：第二章栈和队列 第1节栈 第2节栈的应用举例教学目标： 1、使学生了解栈的表示和实现； 2、使学生掌握栈的应用。教学重点和难点：栈的应用主要教学方法和手段：多媒体课件讲授教学课时：2课时课的类型：讲授课教学内容：从逻辑上看，栈和队列都属于线性结构，是两种特殊的线性表。其特殊性在于它们的操作是线性表操作的子集。确切地说就是，线性表上的插入、删除操作是不受限制的，而栈和队列上的插入、删除操作是受某种特殊的限制的。因此，栈和队列称作操作受限的线性表。3.1.1栈的定义栈是一种特殊的线性表。其特殊性在于限定插入和删除数据元素的操作只能在线性表的一端进行。如下所示：进行插入和删除的一端是浮动端，通常被称为栈顶，并用一个“栈顶指针”指示；而另一端是固定端，通常被称为栈底。我们经常将栈用下图形式描述：栈：插入和删除在一端进行的线性表。栈顶：进行插入和删除的浮动端。用栈顶指针指示。栈底：固定端。进栈（入栈）：数据存入。栈顶指针加1。出栈（退栈）：数据读出，栈顶指针减1。空栈：当栈中没有元素时，称栈为空栈。亦称为后进先出表（LIFO），亦称下推表。结论：后进先出（LastInFirstOut），简称为LIFO线性表。举例1：家里吃饭的碗，通常在洗干净后一个一个地落在一起存放，在使用时，若一个一个地拿，一定最先拿走最上面的那只碗，而最后拿出最下面的那只碗。举例2：在建筑工地上，使用的砖块从底往上一层一层地码放，在使用时，将从最上面一层一层地拿取。因此，栈结构的基本操作有以下五种：（1）初始化栈InitStack(S)（2）入栈Push(S,item)：将参数item中数据元素入栈S（3）出栈Pop(S,item)（4）获取栈顶元素内容GetTop(S,item)（5）判断栈是否为空StackEmpty(S)3.1.2栈的顺序存储栈的顺序存储结构是用一组连续的存储单元依次存放栈中的每个数据元素，并用起始端作为栈底；用一个变量来指示当前的栈顶位置。因此，栈的顺序存储的类型定义如下所示：#defineMAX_STACK10//栈的最大数据元素数目typedefstructstack{StackEntryitem[MAX_STACK];//存放栈中数据元素的存储单元inttop;//栈顶指针}STACK;栈的动态示意：上溢（满栈时进行入栈运算）与下溢（空栈时进行出栈运算）问题。3.1.3栈的链式存储若是栈中元素的数目变化范围较大或不清楚栈元素的数目，就应该考虑使用链式存储结构。人们将用链式存储结构表示的栈称作“链栈”。链栈通常用一个无头结点的单链表表示。由于栈的插入删除操作只能在一端进行，而对于单链表来说，在首端插入删除结点要比尾端相对地容易一些，所以，我们将单链表的首端作为栈顶端，即将单链表的头指针作为栈顶指针。栈的链式存储结构在C语言中可用下列类型定义实现：typestructnode{//链栈的结点结构StackEntryitem;//栈的数据元素类型structnode*next;//指向后继结点的指针}NODE;typedefstructstack{NODE*top;}STACK;3.1.4栈的应用举例【举例1】将从键盘输入的字符序列逆置输出比如，从键盘上输入：tsetasisihT；算法将输出：Thisisatest下面我们给出解决这个问题的完整算法。 typedefcharStackEntry; voidReverseRead() { STACKS;//定义一个栈结构S charch; InitStack(&S);//初始化栈 while((ch=getchar())!=’\n’) //从键盘输入字符，直到输入换行符为止 Push(&S,ch);//将输入的每个字符入栈 while(!StackEmpty(S)){ //依次退栈并输出退出的字符 Pop(&S,&ch); putchar(ch); } putchar(‘\n’); }【举例2】十进制数值转换成二进制使用展转相除法将一个十进制数值转换成二进制数值。即用该十进制数值除以2，并保留其余数；重复此操作，直到该十进制数值为0为止。最后将所有的余数反向输出就是所对应的二进制数值。比如：(692)10=(1010110100)2。【举例3】检验表达式中的括号匹配情况假设在一个算术表达式中，可以包含三种括号：圆括号“（”和“）”，方括号“[”和“]”和花括号“{”和“}”，并且这三种括号可以按任意的次序嵌套使用。比如，...[...{...}...[...]...]...[...]...(...)..。现在需要设计一个算法，用来检验在输入的算术表达式中所使用括号的合法性。算术表达式中各种括号的使用规则为：出现左括号，必有相应的右括号与之匹配，并且每对括号之间可以嵌套，但不能出现交叉情况。检验括号是否匹配的方法可用“期待的急迫程度”这个概念描述。而这个处理过程恰与栈的特点相吻合。由此，在算法中设置一个栈。我们可以利用一个栈结构保存每个出现的左括号，当遇到右括号时，从栈中弹出左括号，检验匹配情况。在检验过程中，若遇到以下几种情况之一，就可以得出括号不匹配的结论。（1）当遇到某一个右括号时，栈已空，说明到目前为止，右括号多于左括号；（2）从栈中弹出的左括号与当前检验的右括号类型不同，说明出现了括号交叉情况；（3）算术表达式输入完毕，但栈中还有没有匹配的左括号，说明左括号多于右括号。因此，在算法的开始和结束时，栈都应该是空的。P53-54:解决这个问题的完整算法。第四讲课题名称：第二章栈和队列 第3节队列 第4节队列的应用举例教学目标： 1、使学生了解队列的表示和实现； 2、使学生了解队列的应用。教学重点和难点：队列的理解主要教学方法和手段：多媒体课件讲授教学课时：2课时课的类型：讲授课教学内容：第三节3.3.1队列的定义队列特殊性在于限定插入在线性表的一端进行，删除在线性表的另外一端进行。如图所示： 队头 队尾3.3出队：队头，删除端，前端，front，front+1入队：队尾，插入端，后端，rear，rear+1插入端和删除端都是浮动的。通常我们将插入端称为队尾，用一个“队尾指针”rear指示；而删除端被称为队头，用一个“队头指针”front指示。结论：先进先出（FirstInFirstOut），简称为FIFO线性表。举例1：到医院看病，首先需要到挂号处挂号，然后，按号码顺序救诊。举例2：乘坐公共汽车，应该在车站排队，车来后，按顺序上车。举例3：在Windows这类多任务的操作系统环境中，每个应用程序响应一系列的“消息”，像用户点击鼠标；拖动窗口这些操作都会导致向应用程序发送消息。为此，系统将为每个应用程序创建一个队列，用来存放发送给该应用程序的所有消息，应用程序的处理过程就是不断地从队列中读取消息，并依次给予响应。下面我们给出队列结构的基本操作：（1）初始化队列InitQueue(Q)（2）入队EnQueue(Q,e):rear+1（3）出队DeQueue(Q,e):front+1（4）获取队头元素内容GetHead(Q,e)（5）判断队列是否为空QueueEmpty(Q)其他基本操作参看P46-473.3.3队列的链式存储在用链式存储结构表示队列时，需要设置队头指针和队尾指针，以便指示队头结点和队尾结点。为了操作方便，我们也给队列添加一个头结点，并令头指针指向头结点。由此，空的链队列的判决条件为头指针和尾指针均指向头结点。下面是在C语言中，实现队列链式存储结构的类型定义：typestructnode{//链式队列的结点结构QElemTypedata;//队列的数据元素类型structQNode*next;//指向后继结点的指针}Qnode,*QueuePtr;typedefstructqueue{//链式队列QueuePtr*front;//队头指针QueuePtr*rear;//队尾指针}LinkQueue;假设将要入队的新结点s已被创建。入队需要执行下面三条语句：s->next=NULL;//\新结点s的next域为空rear->next=s;//原尾指针指向的结点的next域指向srear=s;//尾指针指向s下面我们给出链式队列的基本操作算法。（1）初始化队列Q：创建头结点并将头指针与尾指针指向该结点voidInitQueue(LinkQueue*Q){Q->front=(QNode*)malloc(sizeof(QNode));if(Q->front==NULL)exit(ERROR);Q->rear=Q->front;Q.front.->next=NULL;}（2）入队voidEnQueue(LinkQueue*Q,QElemTypee){s=(QNode*)malloc(sizeof(QNode));if(!s)exit(ERROR);s->data=e;//以上三句为创建新结点ss->next=NULL;Q->rear->next=s;Q->rear=s;//以上三句为s入列操作}（3）出队voidDeQueue(LinkQueue*Q,QElemType*e){if(QueueEmpty(*Q))exit(ERROR);else{*e=Q->front->next->data;s=Q->front->next;Q->front->next=s->next;//修改指针free(s);}}（4）获取队头元素内容voidGetHead(LinkQueueQ,QElemType*e){if(QueueEmpty(Q))exit(ERROR);else*e=Q->front->next->data;}（5）判断队列Q是否为空intQueueEmpty(LinkQueueQ){if(Q->front==Q->rear)returnTRUE；elsereturnFALSE;}3.3.4队列的顺序存储和顺序栈类似，在队列的顺序存储结构中，除了用一组地址连续的存储单元依次存放从队列头到队列尾的元素之外，尚需附设两个指针front和rear分别指示队列头元素和尾元素的位置。队列的顺序存储结构如下图所示：问题1：当队空时，队头和队尾指针都为-1，队列将处于下图所示的状态：此时若进行入队操作，就需要让队头和队尾指针都增1，再将新数据元素放入该位置。也就是说，这样设置队头、队尾指针位置，在进行入队操作时，空队与非空队状态所需要执行的操作不完全一样。解决方法：在算法中，需要对这两种情况加以区分，这势必增加了算法的复杂性。因此，人们设想了一种解决方法，即让队头指针指向队列真正队头元素的前一个位置，如下图所示。问题2：由于顺序存储结构的存储空间属于静态分配，所以，在添加数据元素时，可能会出现没有剩余单元的情况。对于队列来说，这一点又有它的特殊性。如下图所示的队列。 即所谓“假溢出”现象。解决方法：将存储队列元素的一维数组首尾相接，形成一个环状。我们将这种形式表示的队列称之为循环队列。假设为队列开辟的数组单元数目为MAX_QUEUE，在C语言中，它的下标在0~MAX_QUEUE-1之间，若增加队头或队尾指针，可以利用取模运算（一个整数数值整除以另一个整数数值的余数）实现。如下所示：front=(front+1)%MAX_QUEUE；rear=(rear+1)%MAX_QUEUE；当front或rear为MAXQUEUE-1时，上述两个公式计算的结果就为0。这样，就使得指针自动由后面转到前面，形成循环的效果。各项基本操作算法。（1）初始化队列QvoidInitQueue(QUEUE*Q){Q.base=(QElemType*)malloc(MAX_QUEUE*sizeof(QElemType));if(!Q.base)exit(OVERFLOW);Q->front=-1;Q->rear=-1;}（2）入队溢出判断voidEnQueue(QUEUE*Q,QElemTypee){if((Q->rear+1)%MAX_QUEUE==Q->front)exit(OVERFLOW);else{Q->rear=(Q->rear+1)%MAX_QUEUE;Q.base[Q->rear]=e;}}3）出队voidDeQueue(QUEUE*Q,QElemType*e){if(QueueEmpty(*Q))exit(“Queueisempty.”);else{Q->front=(Q->front+1)%MAX_QUEUE;*e=Q.base[Q->front];}}（4）获取队头元素内容voidGetFront(QUEUEQ,QElemType*e){if(QueueEmpty(Q))exit(“Queueisempty.”);else*e=Q.base[(Q.front+1)%MAX_QUEUE];}（5）判断队列Q是否为空intQueueEmpty(QueueQ){if(Q.front==Q.rear)returnTRUE;elsereturnFALSE;}第四节【举例1】汽车加油站。随着城市里汽车数量的急速增长，汽车加油站也渐渐多了起来。通常汽车加油站的结构基本上是：入口和出口为单行道，加油车道可能有若干条。每辆车加油都要经过三段路程，第一段是在入口处排队等候进入加油车道；第二段是在加油车道排队等候加油；第三段是进入出口处排队等候离开。实际上，这三段都是队列结构。若用算法模拟这个过程，就需要设置加油车道队列3个和2个出口车道和入口车道队列。【举例2】模拟打印机缓冲区。在主机将数据输出到打印机时，会出现主机速度与打印机的打印速度不匹配的问题。这时主机就要停下来等待打印机。显然，这样会降低主机的使用效率。为此人们设想了一种办法：为打印机设置一个打印数据缓冲区，当主机需要打印数据时，先将数据依次写入这个缓冲区，写满后主机转去做其他的事情，而打印机就从缓冲区中按照先进先出的原则依次读取数据并打印，这样做即保证了打印数据的正确性，又提高了主机的使用效率。由此可见，打印机缓冲区实际上就是一个队列结构。【举例3】CPU分时系统在一个带有多个终端的计算机系统中，同时有多个用户需要使用CPU运行各自的应用程序，它们分别通过各自的终端向操作系统提出使用CPU的请求，操作系统通常按照每个请求在时间上的先后顺序，将它们排成一个队列，每次把CPU分配给当前队首的请求用户，即将该用户的应用程序投入运行，当该程序运行完毕或用完规定的时间片后，操作系统再将CPU分配给新的队首请求用户，这样即可以满足每个用户的请求，又可以使CPU正常工作。【举例4】农夫过河问题一个农夫带着一只狼、一只羊和一棵白菜，身处河的南岸。他要把这些东西全部运到北岸。问题是他只有一条小船，船小到只能容下他和一件物品，另外，只有农夫能撑船。显然：狼吃羊，羊吃白菜，狼不吃白菜。请问：农夫采取什么方案才能将所有的东西运过河呢？求解这个问题的最简单的方法是一步步进行试探，每一步都搜索所有可能的选择，对前一步合适的选择再考虑下一步的各种方案。用计算机实现上述求解的搜索过程可以采用两种不同的策略。一种是广度优先搜索：依赖的数据结构是队列。一种是深度优先搜索：依赖的数据结构是栈。广度优先的含义是：在搜索过程中，总是首先搜索下面一步的所有可能状态，然后再进一步考虑更后面的各种情况。搜索到的下面一步的所有可能状态，放在队列里，然后顺序取出来对其分别进行处理，处理过程中再把下一步的状态放在队列里……。由于先进先出原则，前一步情况处理完后，才开始后面一步各情况的处理。下面是具体解决方案。首先选择一个对问题中每个角色的位置进行描述的方法。用四位二进制数分别顺序表示农夫、狼、白菜、羊的位置：0表示在南岸；1表示在北岸。如：0101表示农夫和白菜在南岸，狼和羊在北岸。此时是否为一安全状态？农夫过河问题即为从0000到1111状态的动作序列问题。下图标出了送入队列的各个状态（位置分布）和搜索过程中经历结点的顺序编号。请注意广度优先搜索法在面临多个选择时采用怎样的访问顺序。即从初始状态0到最终状态15的动作序列为：农夫把羊带到北岸；农夫独自回到南岸；农夫把白菜带到北岸；农夫带羊返回南岸；农夫把狼带到北岸；农夫独自返回南岸；农夫把羊带到北岸。【举例5】离散事件模拟假设某银行有四个窗口对外接待客户。由于每个窗口在某个时刻只能接待一个客户，因此在客户人数众多时需在每个窗口前顺次排队，对于刚进入银行的客户，如果某个窗口的业务员正空闲，则可上前办理业务，反之，若四个窗口均有客户，他会排在人数最少的队伍后面。现在需要编制一个程序以模拟银行的这种业务活动并计算一天中客户在银行逗留的平均时间。逗留：指到达与离开的时间差。逗留的平均时间=所有客户逗留时间总和/客户数。事件：称客户到达银行和离开银行这两个时刻发生的事情为“事件”。（到达事件、离开事件）整个模拟程序将按事件发生的先后顺序进行处理，这样一种模拟程序称做事件驱动模拟。下面讨论模拟程序的实现。首先讨论模拟程序中需要的数据结构及其操作。1、处理的主要对象是“事件”。事件主要信息是事件类型和事件发生的时刻。客户到达事件：随客户到来自然形成客户离开事件：客户事务所需时间与等待时间决定由于程序驱动是按事件发生时刻的先后顺序进行，则事件表应是有序表，其主要操作是插入和删除事件。2、模拟程序中需要的另一种数据结构是表示客户排队的队列。四个窗口à四个队列。队列中有关客户的主要信息是客户到达的时刻和客户办理事务所需时间。每个队列中的头客户即为正在窗口办理事务的客户。（而每个头客户都存在一个将要驱动的客户离开事件。）因此，在任何时刻即将发生的事件只有下列五种可能：新的客户到达；1号窗口客户离开；2号窗口客户离开；3号窗口客户离开；4号窗口客户离开。从以上分析，这个模拟程序只需要两种数据结构：有序链表和队列。有序链表用于表达事件；队列用于表达客户排队状态。3、两个主要操作步骤的实现：（1）新客户到达事件的处理。在实际的银行中，客户到达的时刻及其办理事务所需时间都是随机的，在模拟程序中可用随机数来代替。随机数：其一为此时刻到达的客户办理事务所需时间durtime；其二为下一客户将到达的时间间隔intertime。（则下一客户到达时刻为occurtime+intertime）。所以：应产生一个新的客户到达事件插入事件表；刚到达的客户则应插入到当前所含元素最少的队列中；若该队列在插入前为空，则还产生一个客户离开事件插入事件表。（2）客户离开事件的处理：首先计算该客户在银行逗留的时间；然后从队列中删除该客户后查看队列是否为空；若不空，则设定一个新的队头客户离开事件。第五讲课题名称：第三章串 第1节串的逻辑结构 第2节串的表示和实现教学目标： 1、使学生了解串的概念； 2、使学生了解串的表示和实现。教学重点和难点：串的理解主要教学方法和手段：多媒体课件讲授教学课时：2课时课的类型：讲授课教学内容：第一节3.1.1串是由零个或多个字符组成的有限序列。它是一种在数据元素的组成上具有一定约束条件的线性表，即要求组成线性表的所有数据元素都是字符，所以，人们经常又这样定义串：串是一个有穷字符序列。串一般记作：s=‘a1a2...an’(n³0)其中，s是串的名称，用单引号或双引号括起来的字符序列是串的值；ai可以是字母、数字或其他字符；串中字符的数目n被称作串的长度。当n=0时，串中没有任何字符，其串的长度为0，通常被称为空串Ø。如：s1=‘’而：s2=‘’与之不同。s1中没有字符，是一个空串；而s2中有两个空格字符，它的长度等于2，它是由空格字符组成的串，一般称此为空格串。相关概念：子串、主串：串中任意连续的字符组成的子序列被称为该串的子串。包含子串的串又被称为该子串的主串。例如，有下列四个串a，b，c，d：a=“WelcometoBeijing”b=“Welcome”c=“Bei”d=“welcometo”?子串的位置：子串在主串中第一次出现的第一个字符的位置。两个串相等：两个串的长度相等，并且各个对应的字符也都相同。例如，有下列四个串a，b，c，d：a=“program”b=“Program”c=“pro”d=“program”串的逻辑结构与线性表极为相似，区别仅在于串的数据对象约束为字符集。即串中的每一个数据元素仅由一个字符组成。然而，串的基本操作和线性表有很大区别。线性表的操作大多以“单个元素”作为操作对象。如：在线性表中查找某个元素、求取某个数据元素、在某个位置上插入一个元素和删除一个元素…………串的基本操作通常以“串的整体”作为操作对象。如：在串中查找某个子串、求取一个子串、在串的某个位置上插入一个子串以及删除一个子串…………4.1.2串的基本操作：（1）创建串StrAssign(T,chars)：串赋值。即创建串T，并将chars的内容赋予它。即生成一个值等于chars的串T。（2）判断串是否为空StrEmpty(S)（3）计算串长度StrLength(S)（4）串连接Concat(T，S1，S2)：将串S2接在串S1后构成一个新串T（5）求子串SubString(sub,S,pos,len)：将串S中从第pos个字符开始的连续len个字符组成的新子串赋给sub串。（6）串的定位Index(S,T)：即求串T在S中位置。“串的模式匹配”S称为主串；T称为子串或模式串。（7）串复制strCopy(T,S)：串S存在，复制得串T。（8）串比较StrCompare(S,T):如果S>T则返回值>0；如果S=T则返回值=0；如果S<T则返回值<0。（9）串清空ClearString(S)：将串清空为空串。（10）串销毁DestroyString(s):与串清除之区别。以上五种黄色字体操作为串类型的最小操作子集。即：这些操作不可能利用其他串操作来实现，但是其他串操作均可在这个最小操作子集上实现。（串清除与串销毁除外）如：将s2串插入到串s1的第i个字符后面。SubString(s3,s1,1,i);SubString(s4,s1,i+1,Length(s1)-i);Concat(s3,s2);Concat(s3,s4);StrAssign(s1,s3);再如：删除串s中第i个字符开始的连续j个字符。SubString(s1,s,1,i-1);SubString(s2,s,i+j,Length(s)-i-j+1);Concat(s1,s2);StrAssign(s,s1);再如：Index(s1，s2，pos)串的定位函数的实现。可利用判等（串比较）、求串长和求子串等操作实现之。算法的基本思想是：在主串s1中取从第i（i的初值为pos）个字符起、长度和串s2相等的子串和串s2比较；若相等，则求得函数值为i，否则i值增1直至串s1中不存在和串s2相等的子串为止。作业：P764.44.54.6第二节4.2.1顺序存储结构串的顺序存储结构与线性表的顺序存储类似，用一组连续的存储单元依次存储串中的字符序列。在C语言中，有两种实现方式：1.第一种称为“定长顺序存储结构”是事先定义字符串的最大长度，字符串存储在一个定长的存储区中。类型定义如下所示：#defineMAX_STRING255//用户可在255以内定义最大串长typedefunsignedcharSString[MAX_STRING];//0号单元存放串的长度，字符从1号单元开始存放说明：1、串的实际长度可在这予定义长度的范围内随意。超过予定义长度的串值则被舍去，称之为“截断”。2、对串长有两种表示方法：（1）如上述定义描述的一样，以下标为0的数组分量存放串的实际长度。（2）在串值后面加一个不计入串长的结束标记字符。如\0。此时的串长为隐含值，显然不便于进行某些串操作。在这种存储结构表示时如何实现串的操作。下面以串联接和求子串为例讨论之。1、串联接Concat(s1,s2)联接后串s1的值的后一段和串s2的值相等，则只要进行相应的“串值复制”操作即可，只是需按前述约定，对超长部分实施“截断”操作。基于串s1和串s2长度的不同情况，串值的产生可能有以下三种情况：(1)s1[0]+s2[0]<=MAX_STRING得到的新串是正确的结果。(2)s1[0]<MAX_STRING而s1[0]+s2[0]>MAX_STRING则将串s2的一部分截断，得到的串只是包含s2的一个子串。(3)s1[0]=MAX_STRING则得到的串并非联接结果。算法见P63-64。2、求子串SubString(s1,s2,start,len)求子串的过程即为复制字符序列的过程，将串s2中从第start个字符开始长度为len的字符序列复制到串s1中。显然，本操作不会有需截断的情况，但是有可能产生用户给出的参数不符合操作的初始条件，当参数非法时，返回ERROR。算法见P64。总结：1、综上两个操作可见，在顺序存储结构中，实现串操作的原操作为“字符序列的复制”。2、另一操作特点是，如果在操作中出现串值序列的长度超过上界MAX_STRING时，约定用截尾法处理。这种情况不仅在求联接串时可能发生，在串的其他操作中，如插入、置换等也可能发生。克服这种弊端，唯有不限定串长的最大长度，即动态分配串值的存储空间。2.第二种称为“堆分配存储”。是在程序执行过程中，利用标准函数malloc和free动态地分配或释放存储字符串的存储单元，并以一个特殊的字符作为字符串的结束标志，它的好处在于：可以根据具体情况，灵活地申请适当数目的存储空间，从而提高存储资源的利用率。类型定义如下所示：typedefstruct{char*ch;//若是非空串，则按串长分配存储区，否则*ch为NULLintlength;//串长度}HString;这种存储结构表示时的串操作仍是基于“字符序列的复制”进行的。如：串复制StrCopy(&T,S)：若串T已存在，则先释放串T所占空间，当串S不空时，首先为串T分配大小和串S长度相等的存储空间，然后将串S的值复制到串T中。串插入StrInsert(&S,pos,T)：为串S重新分配大小等于串S和串T长度之和的存储空间，然后进行串值复制。不同的定义形式，算法中的处理也略有不同。下面我们给出在堆分配存储方式下串的几个基本操作的算法。（1）串的赋值StatusStrAssign(HString*s,char*chars){if(s->ch)free(s->ch);//若s已经存在，将它占据的空间释放掉for(len=0,c=chars;ch;len++,c++);//求chars串的长度if(!len){//空串s->ch=(char*)malloc(sizeof(char));s->ch[0]=’\0’;s->length=0;}else{s->ch=(char*)malloc((len+1)*sizeof(char));//分配空间if(!s->ch)returnERROR;s->ch[0..len]=chars[0..len];//对应的字符赋值,包括串结束标志s->length=len;//赋予字符串长度}returnOK;}2）判断串是否为空intStrEmpty(HStrings){if(!s.length)returnTRUE;elsereturnFALSE;}（3）求串的长度intStrLength(HStrings){returns.length;}4）串连接intConcat(HString*s1,HString*s2){HStrings;StrAssign(&s,s1->ch);//将s1原来的内容保留在s中len=StrLength(s1)+StrLength(s2);//计算s1和s2的长度之和free(s1->ch);//释放s1原来占据的空间s1->ch=(char*)malloc((len+1)*sizeof(char));//重新为s1分配空间if(!s1)returnERROR;else{//连接两个串的内容s1->ch[0..StrLength(s)-1]=s->ch[0..StrLength(s)-1)];s1->ch[StrLength(s)..len+1]=s2->ch[0..StrLength(s2)];s1->length=len;free(s->ch);//释放为临时串s分配的空间returnOK;}}（5）求子串StatusSubString(HString*s1,HString*s2,intstart,intlen){len2=StrLength(s2);//计算s2的长度if(start<1||start>len2||len2<=0||len>len2-start+1){//判断start和len的合理性，如果不合理则返回空串s1s1->ch=(char*)malloc(sizoef(char));s1->ch[0]=’\0’;s1->length=0;returnERROR;}s1->ch=(char*)malloc((len+1)*sizeof(char));if(!s1.ch)returnERROR;s1->ch[0..len-1]=s2.ch[start-1..start+len-2];s1->ch[len]=’\0’;//串尾s1->length=len;returnOK;}（6）串的定位**(串的模式匹配，即求子串s2中s1中的位置）intIndex(HStrings1,HStrings2){len1=StrLength(s1);len2=StrLength(s2);//计算s1和s2的长度i=0;j=0;//设置两个扫描指针while(i<len1&&j<len2){if(s1.ch[i]==s2.ch[j]){i++;j++;}else{i=i-j+1;j=0;}//对应字符不相等时，重新比较}if(j==len2)returni-len2+1;//找到s2在s1中的位置elsereturn0;}//P72图4.24.2.2链式存储结构由于串结构中每个数据元素为一个字符，所以最直接的链式存储结构是每个结点的数据域存放一个字符。优点是操作方便；不足之处是存储密度较低。所谓存储密度为： 由于串中的字符个数不一定是每个结点存放字符个数的整倍数，所以，需要在最后一个结点的空缺位置上填充特殊的字符。这种存储形式优点是存储密度高于结点大小为1的存储形式；不足之处是做插入、删除字符的操作时，可能会引起结点之间字符的移动，算法实现起来比较复杂。P68块链存储的类型定义。作业：P774.74.8第五讲课题名称：第四章数组和广义表 第1节数组的定义数组的顺序表示和实现矩阵的压缩存储教学目标： 1、使学生了解数组和矩阵的概念； 2、使学生了解数组和矩阵的表示和实现。教学重点和难点：数组的理解主要教学方法和手段：多媒体课件讲授教学课时：2课时课的类型：讲授课教学内容：第一节4.1数组的定义1、数组是我们很熟悉的一种数据结构，它可以看作线性表的推广。数组作为一种数据结构其特点是结构中的元素本身可以是具有某种结构的数据，但属于同一数据类型，比如：一维数组可以看作一个线性表，二维数组可以看作“数据元素是一维数组”的一维数组，三维数组可以看作“数据元素是二维数组”的一维数组，依此类推。2、由于数组中各元素具有统一的类型，并且数组元素的下标一般具有固定的上界和下界，因此，数组的处理比其它复杂的结构更为简单。多维数组是一维数组的推广。例如，二维数组A：AAm×n=a11a12…aa21a22…a…………am1am2…amn3、二维数组A可以看成是由m个行向量组成的向量，也可以看成是n个列向量组成的向量。4、数组一旦被定义，它的维数和维界就不再改变。因此，除了结构的初始化和销毁之外，数组只有存取元素和修改元素值的操作。第二节4．2.1数组顺序存放原因1、由于计算机的内存结构是一维的，因此用一维内存来表示多维数组，就必须按某种次序将数组元素排成一列序列，然后将这个线性序列存放在存储器中。2、数组一旦建立，结构中的元素个数和元素间的关系就不再发生变化。因此，一般采用顺序存储的方法来表示数组。4.2.2数组存放1、行优先顺序或以行为主序存储方式：将数组元素按行排列，第i+1个行向量紧接在第i个行向量后面。以二维数组为例，按行优先顺序存储的线性序列为：a11,a12,…,a1n,a21,a22,…a2n,……,am1,am2,…,amn在PASCAL、C等语言中，数组就是按行优先顺序存储的。AAm×n=a11a12…aa21a22…a…………am1am2…amn2、行优先顺序——先排最右的下标，从右到左，最后排最左下标。列优先顺序——先排最左下标，从右向左，最后排最左下标。例如：三维数组Am*n*p以行优先方式顺序存储，则LOC(aijk)=LOC(a111)+[(i-1)*m*n+(j-1)*n+(k-1)]*d4.2.3数组存储的特点只要知道开始结点的存放地址（即基地址）、维数和每维的上、下界，以及每个数组元素所占用的单元数，就可以将数组元素的存放地址表示为其下标的线性函数。因此，数组中的任一元素可以在相同的时间内存取，即顺序存储的数组是一个随机存取结构。第三节4.3.1相关概念1、压缩存储：为多个值相同的非零元素只分配一个存储空间；对零元素不分配空间。2、特殊矩阵：非零元素按照一定的规律分布。常见的特殊矩阵有对称矩阵、三角矩阵、对角矩阵等。对称矩阵：元素的值按照主对角线对称a1a1,1a1,2…a1,a2,1a2,2…a2,……ai,j…an,1an,2…an,naij=aji12341234213433144441对称矩阵3、三角矩阵：上(下)三角矩阵是指矩阵的下（上）三角（不包括对角线）中的元素均为常数或零的n阶矩阵，即非零元素的分布在矩阵中呈现为三角形。例如：一个4*4的三角矩阵。188818882188331844411234912349134991499914、上述各种特殊矩阵，其非零元素的分布都是有规律的，因此总能找到一种方法将它们压缩存储到一维数组中，并且一般都能找到矩阵中的元素与该一维数组元素的对应关系，通过这个关系，仍能对矩阵的元素进行随机存取。4.3.2稀疏矩阵定义：简单说，设矩阵A中有s个非零元素，若s远远小于矩阵元素的总数（即s<<m×n），则称A为稀疏矩阵。设在矩阵A中，有s个非零元素。令e=s/(m*n)，称e为矩阵的稀疏因子。通常认为e≤0.05时称之为稀疏矩阵。2、存储：在存储稀疏矩阵时，由于非零元素的分布一般是没有规律的，因此在存储非零元素的同时，还必须同时记下它所在的行和列的位置（i,j)。反之，一个三元组(i,j,aij)惟一确定了矩阵A的一个非零元。因此，稀疏矩阵可由表示非零元的三元组及其行列数唯一确定。假设以顺序存储结构来表示三元组表，则可得到稀疏矩阵的一种压缩存储方法——三元组顺序表。#definemaxsize10000typedefintdatatype;typedefstruct{inti,j;datatypev;}triple;/*三元组*/typedefstruct{tripledata[maxsize];intm,n,t;}tripletable;第六讲课题名称：第四章数组和广义表 第4节广义表的定义 第5节广义表的存储结构教学目标： 1、使学生了解广义表的概念； 2、使学生掌握广义表的存储结构。教学重点和难点：、广义表的应用主要教学方法和手段：多媒体课件讲授教学课时：2课时课的类型：讲授课教学内容：第一节4.4广义表是线性表的推广L=(a1,a2,...,an),n≥0,ai可以是单元素，也可以是一个表。例如：A=()B=(e)C=(a,(b,c,d))D=(A,B,C)E=(a,E)广义表的长度广义表的深度非空广义表表头(Head)：第一个元素表尾(Tail)：除第一个元素外其余元素构成的表链表存储C=(a,(b,c,d))D=(A,B,C)E=(a,E)第二节m元多项式的表示P(x,y,z)=x10y3z2+2x6y3z2+3x5y2z2+x4y4z+6x3y4z+2yz+15=(x10y3+2x6y3+3x5y2)z2+(x4y4+6x3y4+2y)z+15=Az2+Bz+15A(x,y)=x10y3+2x6y3+3x5y2=(x10+2x6)y3+3x5y2=Cy3+Dy2B(x,y)=x4y4+6x3y4+2y=(x4+6x3)y4+2y=Ey4+Fy

第七讲课题名称：第六章树和二叉树第1节树的定义和基本术语第2节二叉树教学目标： 1、使学生了解树的定义和基本术语等主要内容； 2、使学生了解二叉树的存储结构。教学重点和难点：二叉树的定义、基本运算以及存储结构。主要教学方法和手段：多媒体课件讲授教学课时：2课时课的类型：讲授课教学内容：第一节树的定义和基本术语1、树：是n（n≥0）个结点的有限集。当n=0时，称为空树；在任意一棵非空树中满足如下条件：(1)有且仅有一个特定的称为根（root）的结点，它没有直接前驱，但有零个或多个直接后继。(2)当n>1时，其余n-1个结点可以划分成m（m>0）个互不相交的有限集T1，T2，T3，…，Tm，其中Ti又是一棵树，称为根root的子树。每棵子树的根结点有且仅有一个直接前驱，但有零个或多个直接后继。由此可以看出，树的定义是递归。JJIACBDHGFEKLM2、树的结点：包含一个数据元素及若干指向子树的分支；结点的度：节点拥有的子树数（结点的孩子数目）；终端结点（叶子）：度为0的结点；非终端结点（分支结点）：度不为0的结点；结点的层次：树中根结点的层次为1，根结点子树的根为第2层，以此类推；树的度：树中所有结点度的最大值；树的深度：树中所有结点层次的最大值；孩子结点：结点的子树的根称为该结点的孩子；父结点：B是A的孩子，则A是B的父亲；兄弟结点：同一双亲的孩子结点；堂兄弟结点：其父结点在同一层上的结点；祖先结点：从根到该结点所经分支上的所有结点；子孙结点：以某结点为根的子树中任一结点都称为该结点的子孙。3、有序树和无序树：在树中，如果各子树Ti是按照一定的次序从左向右安排的，且相对次序是不能随意改变的，则称为有序树，否则称为无序树。森林：m（m≥0）棵互不相交的树的集合。将一棵非空树的根结点删去，树就变成一个森林；反之，给m棵独立的树增加一个根结点，并把这m棵树作为该结点的子树，森林就变成一棵树。第二节二叉树6.2.1二叉树的定义二叉树是由n(n>=0)个结点的有限集合构成，此集合或者为空集，或者由一个根结点及两棵互不相交的左右子树组成，并且左右子树都是二叉树。二叉树可以是空集合，根可以有空的左子树或空的右子树。二叉树不是树的特殊情况。二叉树结点的子树要区分左子树和右子树，即使只有一棵子树也要进行区分，说明它是左子树，还是右子树。这是二叉树与树的最主要的差别。二叉树的5种基本形态其中：(c)和（d）是不同的两棵二叉树。(a)(a)空二叉树AABABACB(b)只有根的二叉树(c)根和左子树(d)根和右子树(e)根和左右子树二叉树的5种基本形式6.2.2二叉树的性质1、性质1：在二叉树的第i层上至多有2i-1个结点证明：用数学归纳法1)当i=1时，整个二叉树只有一根结点，此时2i-1=20=1，结论成立。2)设i=k时结论成立，即第k层上结点总数最多为2k-1个。现证明当i=k+1时，结论成立：因为二叉树中每个结点的度最大为2，则第k+1层的结点总数最多为第k层上结点最大数的2倍，即2×2k-1=2(k+1)-1，故结论成立。2、性质2：深度为k的二叉树至多有2k-1个结点证明：因为深度为k的二叉树，其结点总数的最大值是将二叉树每层上结点的最大值相加，所以深度为k的二叉树的结点总数至多为深度为k的m叉树至多有个结点。3、性质3：任何一个二叉树中度为2的结点数目(n2)比度为0的结点数目(n0)少1，即n2＝n0-1。证明：设二叉树中结点总数为n，n1为二叉树中度为1的结点总数，设二叉树中分支数目为B。①n=n0+n1+n2除根结点外，每个结点均对应一个进入它的分支：②n=B+1二叉树中的分支都是由度为1和度为2的结点发出③B=n1+2n24、满二叉树深度为k且有2k-1个结点的二叉树。在满二叉树中，每层结点都是满的，即每层结点都具有最大结点数。满二叉树的顺序表示，即从二叉树的根开始，层间从上到下，层内从左到右，逐层进行编号（1，2，…，n）。高度为高度为3的满二叉树5、完全二叉树深度为k，结点数为n的二叉树，如果其结点1~n的位置序号分别与满二叉树的结点1~n的位置序号一一对应，则为完全二叉树，满二叉树必为完全二叉树，而完全二叉树不一定是满二叉树。6、性质4：一个有n个结点的完全二叉树的深度为ëlog2nû+1或élog2(n+1)ù证明：设n个结点的完全二叉树的深度为k，根据性质2有2k-1-1＜n≤2k-1可得2k-1≤n＜2k，即k-1≤log2n＜k因为k是整数，所以k-1=ëlog2nû，k=ëlog2nû+1,故结论成立。2k-1＜n+1≤2k→k-1＜log2(n+1)≤k→k=élog2(n+1)ù7、性质5：完全二叉树中的某结点编号为i，则1)若该结点有左孩子，则左孩编号为2i2）若该结点有右孩子，则右孩子结点编号为2i+13）若该结点有双亲，则双亲结点编号为ëi/2û6.2.3.1二叉树的顺序存储二叉树的顺序存储指的是用元素在数组中的下标表示一个结点与其孩子和父结点的关系.1、完全二叉树的顺序存储EDEDCFABABCDEF123456789101112#defineMAX_TREE_SIZE100typedefTelemTypeSqBiTree[MAX_TREE_SIZE];SqBiTreebt;2、非完全二叉树的顺序存储EEGFCDABABCDEFG12