软件技术基础-ppt.ppt

1、软件技术基础,为什么要学习软件技术基础,通信专业是最接近计算机专业的领域 大多数综合类高校将通信划入计算机系或电子工程系 通信领域中大量使用计算机技术 通信是计算机越来越不可缺少的能力 软件技术基础是我专业为数不多的计算机相关的课程,为什么要学习软件技术基础,软件技术基础,计算机通信网,TCP/IP协议原理,网络软件设计,交换原理,嵌入式系统设计,多媒体通信,软件无线电技术,综合设计,前 言,一、课程内容 二、课程安排 三、学习目的,一、课程内容,数据结构：计算机软件基础，描述计算机内数据的逻辑关系，是计算机操控对象的抽象模型 操作系统：计算机核心软件的集合，是计算机系统的逻辑抽象。 数据库

2、：计算机数据处理的延伸发展。帮助用户有效地组织大量数据。 程序设计方法：软件开发的一般步骤和方法。,二、课程安排,数据结构-20学时 操作系统-20学时 数据库-自学 软件工程-软件项目管理 上机-20学时(自行安排),数据结构： 基本概念（2学时） 线性表（4学时） 堆栈、队列、数组和串（4学时） 非线性结构（树、图）（6学时） 检索和排序(4学时),操作系统： OS概述（2学时） 处理机管理（6学时） 存储管理（4学时） 作业管理，设备管理，文件管理（4学时） 复习+考试（4学时）,三、学习目的,1、了解软件技术基础知识。 2、掌握数据结构的概念，几种基本结构， 检索和排序方法，能编写正确

3、算法、 编写简单程序。 3、掌握操作系统的概念， 处理机管理，存储器管理等 4、了解数据库的概念，基本原理。,9,数据结构,软件技术基础,10,数据结构的基本概念 算法的概念和描述 算法的简单分析,11,为什么要学习数据结构？ 什么是程序、软件？ N.沃思（Niklaus Wirth)教授提出： 程序=算法+数据结构,一、数据结构的概念,以上公式说明了如下两个问题： （1）数据上的算法决定如何构造和组织数据（算法数据结构）。 （2）算法的选择依赖于作为基础的数据结构（数据结构算法）。,软件=程序+文档（软件工程的观点）,12,电子计算机的主要用途： 早期： 主要用于数值计算。 线性方程的求解

4、该类问题涉及的运算对象是简单的整型、实型或布尔型数据。程序设计者的主要精力集中于程序设计的技巧，无须重视数据结构。 后来： 处理逐渐扩大到非数值计算领域（能处理多种复杂的具有一定结构关系的数据）。,13,数值计算解决问题的一般步骤： 数学模型选择计算机语言编出程序测试最终解答。 数值计算的关键是：如何得出数学模型（方程）？ 程序设计人员比较关注程序设计的技巧。 非数值计算问题： 数据元素之间的相互关系一般无法用数学方程加以描述,描述非数值计算问题的数学模型不再是数学方程，而是诸如表、树、图之类的数据结构,14,例1 书目自动检索系统,书目文件,15,例2 计算机和人对弈问题,16,例3 多叉路

5、口交通灯管理问题,17,例4 田径赛的时间安排问题（无向图的着色问题） ： 设有六个比赛项目，规定每个选手至多可参加三个项目，有五人报名参加比赛（如下表所示）设计比赛日程表，使得在尽可能短的时间内完成比赛。,18,（1）设用如下六个不同的代号代表不同的项目： 跳高 跳远 标枪 铅球 100米 200米 A B C D E F （2）用顶点代表比赛项目 不能同时进行比赛的项目之间连上一条边。 （3）某选手比赛的项目必定有边相连（不能同时比赛）。,19,只需安排四个单位时间进行比赛,20,求解非数值计算的问题： 主要考虑的是设计出合适的数据结构及相应的算法。 即：首先要考虑对相关的各种信息如何表示

6、、组织和存储？ 因此，可以认为：数据结构是一门研究非数值计算的程序设计问题中计算机的操作对象以及它们之间的关系和操作的学科。,21,数据结构课程的形成和发展： 形成阶段： 60年代初期，“数据结构”有关的内容散见于操作系统、编译原理和表处理语言等课程。1968年，“数据结构”被列入美国一些大学计算机科学系的教学计划。 发展阶段： 数据结构的概念不断扩充，包括了网络、集合代数论、关系等“离散数学结构”的内容。 70年代后期，我国高校陆续开设该课程。,22,数据结构课程所处的地位：,23,什么是数据结构？ 几个概念： 数据(Data):是对信息的一种符号表示。在计算机科学中是指所有能输入（识别）到

7、计算机中（存储）并被计算机程序处理（加工）的符号的总称。 数据元素(Data Element):是数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理。 一个数据元素可由若干个数据项组成。数据项是数据的不可分割的最小单位。 数据对象(Data Object)：是性质相同的数据元素的集合。是数据的一个子集。,24,数据对象 (data object),具有相同性质的数据元素的集合。 整数数据对象 N = 0, 1, 2, 字母字符数据对象 C= A, B, C, F ,25,什么是数据结构？ 形式定义： 某一数据对象的所有数据成员之间的关系。记为： Data_Structure = D,

8、 S 其中，D 是某一数据对象， S 是该对象中所有数据成员之间的关系的有限集合。 这是对操作对象的一种数学描述，其“关系”描述的是数据元素之间的逻辑关系，因而又称为数据的逻辑结构。,26,数据的逻辑结构分类 根据数据元素间关系的基本特性，有四种基本数据结构 （集合）数据元素间除“同属于一个集合”外，无其 它关系 线性结构一个对一个，如线性表、栈、队列 树形结构一个对多个，如树 图状结构多个对多个，如图,27,数据的逻辑结构,从逻辑关系上描述数据，与数据的存储无关； 从具体问题抽象出来的数据模型； 与数据元素本身的形式、内容无关； 与数据元素的相对位置无关。,28,数据的存储结构（物理结构）,

9、数据结构在计算机中的表示。 数据的存储结构依赖于计算机语言。 顺序存储表示 链接存储表示 索引存储表示 散列存储表示,29,30,1536,元素2,1400,元素1,1346,元素3,元素4,1345,链式存储,head,head,31,索引存储结构：将全部记录分别存放在存储器的不同位置，系统为整个记录建立一张索引表，表中登记了每条记录的长度、逻辑记录号和在存储器中位置。通过索引表来访问记录。 散列存储结构：在记录的存储位置和它的关键字之间建立一个确定的对应关系，使每个关键字和结构中一个唯一的存储位置相对应。由关键字作某种运算后直接确定元素的地址。,32,存储结构,存储结构两方面的内容： （1

10、）数据元素自身值的表示（数据域） （2）该结点与其它结点关系的域（链域） 同一种逻辑结构可采用不同的存储方法（以上四种之一或组合），这主要考虑的是运算方便及算法的时空要求。,33,数据结构的三个方面（层次）小结： 逻辑结构- 数据元素间抽象化的相互关系（简称为数据结构）。 与数据的存储无关，独立于计算机，它是从具体问题抽出来的数学模型。 存储结构（物理结构）- 数据元素及其关系在计算机存储器中的存储方式。 是逻辑结构用计算机语言的实现，它依赖于计算机语言。 运算（算法or数据操作的集合） 检索、排序、插入、删除、修改等,34,数据的逻辑结构,数据的存储结构,数据的运算：检索、排序、插入、删除、

11、修改等,线性结构,非线性结构,顺序存储,链式存储,线性表,栈,队,树形结构,图形结构,数据结构的三个方面：,35,数据结构的命名,由于数据结构具有三个层次，故在对数据结构命名的时候可以将数据的逻辑结构、存储结构甚至操作结合起来给数据结构进行命名。,线性表,22,36,数据结构的三个方面的含义之： 逻辑结构存储结构小结： （1）数据的逻辑结构、存储结构和数据的运算（算法）构成了数据结构三个方面的含义。 （2）程序设计的实质是对实际问题选择一个好的数据结构，加之设计一个好的算法。而好的算法在很大程度上取决于描述实际问题的数据结构。,37,二、算法的概念和描述： 什么是算法？ 所谓算法（Algori

12、thm)是描述计算机解决给定问题的操作过程（解题方法），即为解决某一特定问题而由若干条指令组成的有穷序列。 一个算法可以被认为是用来解决一个计算问题的工具。一个算法是一系列将输入转换为输出的计算步骤。,38,一个算法必须满足以下五个准则： （1）有穷性-执行了有限条指令后一定要终止。 （2）确定性（无二义）- 算法的每一步操作都必须有确切定义，不得有任何歧义性。 （3）可（能）行性- 算法的每一步操作都必须是可行的，即每步操作均能通过已经实现的基本运算在有限次内完成。 （4）输入数据- 一个算法有n（n=0)个初始数据的输入。 （5）输出数据- 一个算法有一个或多个与输入有某种关系的有效信息的

13、输出。,39,算法的描述和实现 描述-可采用自然语言、数学语言或约定的符号语言。 实现-必须借助程序设计语言提供的数据类型及其运算。 本课的描述-采用C语言。,40,算法的评价准则（首先，算法必须是“正确”的） （1）执行算法所耗费的时间（效率要高）。 （2）执行算法所耗费的存储空间（主要考虑辅存空间；低存储要求）。 （3）算法的可读性、易维护性要好（易于理解，易于编码，易于调试）。 （4）健壮性,41,程序正确性的四个层面： （1）不含语法错误 （2）程序对于n组输入数据能够得出满足规格说明要求的结果。 （3）程序对于精心选择的典型、边界性的n组输入数据能得出满足规格说明要求的结果。 （4）

14、程序对于一切合适的输入数据都能得出满足规格说明要求的结果（穷举）。,42,算法效率的度量 程序运行所耗费的时间(由下列因素决定)： 算法所选用的策略 问题的规模 书写程序所采用的语言 编译程序所产生的机器代码的质量 机器执行指令的速度 一个算法耗费的时间=算法中每条语句的执行时间之和。,三、算法的简单分析,43,若不考虑机器硬、软件因素，可以认为算法“运行工作量”的大小是问题规模的函数。 问题的规模（size)- 算法求解问题的输入量（或初始数据量）。 不考虑机器软硬件环境时算法的时间耗费： 设：执行每条语句所需时间为单位时间，则： 一个算法耗费的时间=所有语句的频度之和。,44,时间复杂度,

15、时间复杂度T(n)- 即：时间耗费，它是算法求解问题n的函数。 渐近时间复杂度- 即当问题的规模n时的时间复杂度T(n)的数量级（阶），记作：T(n)=O(f(n) 评价一个算法的时间性能，主要标准是算法的渐近时间复杂度,45,例 x=1; for (i=1;i=n;i+) for (j=1;j=i;j+) for (k=1;k=j;k+) x+; 由于内循环的执行次数虽与规模n无直接关系，但与外循环的变量取值有关。因此从内层向外层循环分析执行次数。,46,47,即: T(n)=n(n+1)(2n+1)/6+n(n+1)/2/2 所以： T(n)=O(n3/6+低次项) 取T(n)的数量级阶，

16、得最后结果为： T(n)=O(n3),48,分析以下程序段的时间复杂度 for (i=1;in;i+) y=y+1; for (j=0; j=(2*n); j+) x+; ,/* 1 * /,/* 2 * /,49,分析：语句的频度指的是该语句重复执行的次数。一个算法中所有语句的频度之和构成了该算法的运行时间。 语句1的频度是：n-1 语句2的频度是：,则该程序段的时间复杂度： T(n)=,50,分析以下程序段的时间复杂度 i=1; while (i=n) i=i*2 语句1的频度是：1 设语句2的频度是f(n)，则有： 即 ，取最大值 则该程序段的时间复杂度为：,/* 1 * /,/* 2

17、* /,51,常见函数的时间复杂度按数量递增排列及增长率。,常数阶O(1) 对数阶O(log2n) 线性阶O(n) 线性对数阶O(nlog2n) 平方阶O(n2) 立方阶O(n3) k次方阶O(nk) 指数阶O(2n),52, 本章小结 数据、数据结构等基本概念 数据结构的三个方面的内容 线性和非线性结构的逻辑特征 数据存储的四种基本方法 算法、算法的时间复杂度及其分析的简易方法,数据结构,-线性结构,54,1.线性表的定义： 是由n(n=0)个数据元素（结点）a1,a2,a3, an组成的有限序列。 其中： n为数据元素的个数，也称为表的长度。 当n=0 时，称为空表。 非空的线性表(n0)

18、 记作： （ a1,a2,a3, an）, 线性表的定义及运算,55,（1）初始化（INITIATE(L)） （2）存取(GET(L,i) （3）插入(INSERT(L,i,x) （4）删除(DELETE(L,i) （5）查找(LOCATE(L,x) （6）合并 （7）分解 （8）排序(SORT(L) （9）求线性表的长度(LENGTH(L),基本运算,4. 线性表的运算,数据的运算是定义在逻辑结构上的，而具体的实现则在存储结构上进行。,56, 线性表的顺序存储结构（顺序表） 1.顺序表的定义： -用一组连续的存储单元（地址连续）依次存放线性表的各个数据元素。 即：在顺序表中逻辑结构上相邻的数

19、据元素，其物理位置也是相邻的。 用数组来实现线性表的顺序存储,57,2.顺序表中数据元素的存储地址 若一个数据元素仅占一个存储单元，则其存储方式参见下图。,58,3.顺序表的特点,逻辑关系上相邻的两个元素在物理位置上也相邻,59,5.顺序表的几种基本运算 （1）插入运算 在第i（1=i=n)个元素之前插入一个新的数据元素x。使： 长度为n的线性表变为长度为n+1的线性表 （a1,a2,ai-1,ai,an）,（a1,a2,ai-1,x,ai,an）,60,x,61,插入算法分析： 上述算法for循环语句的执行次数为n-i+1; 若i=1,需移动全部n个结点（最坏：O(n)） 若i=n+1（在表

20、尾插入）,无需用移动结点，直接插入即可。（最好O(1)） 移动结点的平均次数：,62,按等概率考虑： 可能的插入位置为i=1,2,n,n+1共n+1个，则pi=1/(n+1) 所以,顺序表插入算法平均约需移动一半结点。,63,（2）删除算法 -将线性表的第i（1=i=n)个结点删除，使： 长度为n的线性表变为长度为n-1的线性表。 （a1,a2,ai-1,ai,ai+1,an）,（a1,a2,ai-1,ai+1,an）,64,65,删除算法分析： 上述算法for循环语句的执行次数为n-i; 若i=1,最坏：O(n) 若i=n,无需用移动结点，直接删除即可。(最好O(1) 移动结点的平均次数：,

21、66,按等概率考虑： 可能的删除位置为i=1,2,n共n个，则pi=1/n 所以,顺序表删除算法平均约需移动一半结点。 小结：顺序表插入、删除算法平均约需移动一半结点，当n很大时，算法的效率较低。,67,优点： （1）无须为表示结点间的逻辑关系而增加额外的存储空间。 （2）通过元素在数组中的下标，可以随机访问表中的任一结点。 （3）查找快 缺点： （1）插入和删除平均须移动一半结点。 （2）存储分配只能预先进行（静态）,顺序表的优、缺点：,过大 浪费 过小 溢出,68,线性表的链式存储结构：（链表linked list）,链表： 所谓线性链表就是链式存储的线性表。节点中只有一个指针域，指出其后

22、继节点的存储位置，最后一个节点无后继，指针域为空。(记为NIL或) 链表的特点： 链表中结点的逻辑次序和物理次序不一定相同。即：逻辑上相邻未必在物理上相邻。 结点之间的相对位置由链表中的指针域指示，而结点在存储器中的存储位置是随意的。,-线性表的链式存储结构,线性表元素：a1、a2、a3、a4.,69,-线性表的链式存储结构,线性表的链式存储结构：（链表linked list）,结点的组成：,数据域 指针域,数据域-表示数据元素自身值。 指针域（链域）-表示与其它结点关系。 通过链域，可将n个结点按其逻辑顺序链接在一起（不论其物理次序如何）,70,Struct node int data; s

23、truct node * next; ; Struct node *p;,指针p与指向的结点关系示意图,p 结点 (*p),单链表的描述：,说明： p-指向链表中某一结点的指针。 *p-表示由指针p所指向的结点。 (*p).data或p-data-表示由p所指向结点的数据域。 (*p).next或p-next-表示由p所指向结点的指针域。,71,带头结点的单链表,表的第一个结点和其它结点的操作一致。,（表）头结点（在第一个结点之前附设） -其指针域 存贮指向第一个结点的指针（即第一个结点的存贮位置）。 头结点的数据域：可有可无 头结点的指针域：指向第一个结点的指针。,Head,空表,a1,an

24、 ,头结点,开始结点,非空表,Head,72,设指针p指向单链表的某一结点，指针s指向等到插入的、其值为x的新结点。 实现方法（两种）： 后插-将新结点*s插入结点*p之后。 前插-将新结点*s插入结点*p之前。,单链表的基本运算之 （3）插入运算,73,算法思想： 取一新结点，将其数据域置为新结点，再修改有关结点的链域： 把原p结点的直接后继结点作为s结点的直接后继，s结点作为p结点的直接后继。,单链表的基本运算（3）插入运算之 - 后插操作,P,s-next=p-next;,p-next=s;,74,Void INSERTAFTER（P，X） /*将值为X的新结点插入*P之后*/ node

25、 *p; elemtype x; s=（node *）malloc(sizeof(node); /生成新结点*/ s-data=x; s-next=p-next;p-next=s;/*将*s插入*p之后*/ /*INSERTAFTER */,单链表的基本运算（3）插入运算之 后插算法：,后插算法的时间复杂度：O（1）,75,单链表的基本运算之(4)删除运算 - 删除单链表中*p的后继,思想：先找到被删结点（第i个）的前趋结点，即第i-1个结点*p,然后删除*p的后继。 主要执行时间是搜索删除位置，时间复杂度为O(n),76,循环链表,循环链表是指链表的最后一个节点的指针值指向第一个节点，整个链

26、表形成一个环。 特点：（1）表中最后一个结点的指针指向第一个结点或表头结点（如有表头结点的话）。 (2) 从表中任一结点出发均可找到表中其它结点。 h . (非空表） h (空表）,a1,an,77,（2）循环链表的运算与线性链表基本一致。 两者判断是否到表尾的条件不同： 线性表：判断某结点的链域是否为空。 循环链表：判断某结点的链域值是否等于头指针。,78,栈和队列,79,栈和队列,两种操作受限的线性表 两种应用广泛的抽象数据类型(ADT),80,栈,81,栈：限制在一端进行插入、删除操作的线性表,限定插入或删除操作只能在表尾(栈顶)进行，分别称为进栈(PUSH)和出栈(POP)。指示栈顶位

27、置的指针称为栈顶指针。,栈的定义和术语,栈底：不可对栈进行输入、输出的一端 栈的长度：栈中元素的个数 空栈：元素个数为0的栈,栈又称为“后进先出”(Last In First Out -LIFO)线性表,栈可采用顺序存储结构或链表结构来实现，分别称为顺序栈和链栈,82,栈的基本操作： SETNULL(s) ：初始化(initstack) EMPTY(s)：判断是否为空 PUSH(s,x)：进栈 POP(s)：出栈 TOP(s)：取栈顶元素 LENGTH(s)：求栈中元素个数,83,例： 对于一个栈，给出输入项A、B、C，如果输入项序列 由ABC组成，试给出所有可能的输出序列。,A进 A出 B进

28、 B出 C进 C出 ABC A进 A出 B进 C进 C出 B出 ACB A进 B进 B出 A出 C进 C出 BAC A进 B进 B出 C进 C出 A出 BCA A进 B进 C进 C出 B出 A出 CBA,不可能产生输出序列CAB?,1进栈算法 判断栈是否为满，若已满，返回函数值为1 若栈未满，栈顶指针加1(top加1) 将x送人栈顶指针所指位置，返回函数值0. 2出栈算法 判断栈是否为空，若栈空，则返回函数值1 若栈不空，将栈顶元素赋给变量(若不需要栈顶，此步跳去) 将栈顶指针退一(top减1，返回函数值0),85,栈的表示和实现,栈的顺序存储表示-顺序栈 利用一组地址连续的存储单元内依次存放

29、从栈底到栈顶的各数据元素 用指针top来指示栈顶元素的位置,随着进栈和退栈操作而变化的 top为-1时表示空栈,typedef struct stack_type elemtype stackMAXNUM; int top; stacktype; stacktype s;,最多元素个数,86,栈的表示和实现,栈的链式表示-链栈 链式栈无栈满问题，空间可扩充，通过指针连接所有栈中的元素 链式栈的栈顶在链头，表头结点即栈顶元素 插入与删除仅在栈顶处执行 适合于多栈操作,data,next,top,栈顶,栈底,链栈的结点定义 typedef int elemtype; typedef struct

30、node elemtype data; struct node *next; ;,a1,ai-1,ai,87,队列,88,队列,类似于排队机制的结构 队列是特殊的线性表， 节点的插入仅限于在表尾进行， 节点的删除仅限于在表头进行,入队,出队,队头,队尾,89,队列,特点： （1）对队列的操作在表的两端进行 （2）仅在队尾加入节点入队enqueue （3）仅在队首移出节点出队dequeue （4）遵循“先进先出”的原则FIFO,队列也可以采用顺序存储结构或链表结构来实现，分别称为顺序队列和链队列,90,队列的表示和实现,队列的顺序表示-顺序队列 用一组连续的存储单元依次存放从队首到队尾的元素，

31、初始化时，font和rear均置为0； 指针front指向队首元素前一位置，rear指向队尾元素,typedef struct queue_type elemtype queueMAXNUM+1; int front; int rear; queuetype; queuetype Q;,0,1,2,3,4,5,Q.front,Q.rear,空队列,91,顺序队列的实现及插入、删除,当front = rear = 0时表示空队列 当插入新元素到队尾时，rear加1 当删除队首元素时，front加1 front = rear可能表示队空，也可能表示队满 （应另设标志以便区别队空状态） 这种顺序队列

32、空间利用率低，考虑采用循环队列,J1, J2 , J3相继入队,0,1,2,3,4,5,J1, J2 相继出队,J3,0,1,2,3,4,5,J4 , J5相继入队队列满,J4,J5,J2,J1,J3,92,循环队列及其实现,0,1,2,3,4,MAXNUM,Q.front,Q.rear,假满,c,b,a,考虑队满条件，即当Q.rear=MAXNUM时，是否整个存储空间都已占用？,a,b,c,d,Q.front,Q.rear,MAXNUM-1,0,1,循环队列,循环队列 为了提高队列的空间利用率，提出循环队列 结构与顺序队列相同，只是界线处理稍有不同,MAXNUM,93,模运算,入队，rear

33、指针变化： Q.rear （Q.rear1）MAXNUM 出队，front指针变化： Q.front（ Q.front 1）MAXNUM,94,Q.front,Q.rear,一般情况,J3,J4,J5,0,1,2,3,4,5,Q.front,Q.rear,队空时,Q.front,Q.rear,包含一个元素的队列,J3,0,1,2,3,4,5,删除此元素,95,队满和队空时，均有Q.front=Q.rear。 因此，只凭Q.front=Q.rear还无法区分是满还是空。 如何判定队满还是空？是循环队列要解决的新问题。,队满时,Q.front,Q.rear,J3,J4,J5,0,1,2,3,4,5

34、,J8,J7,J6,有一个空位置的队列,Q.front,Q.rear,J3,J4,J5,0,1,2,3,4,5,J7,J6,插入一个元素,96,方法一 ：用一个计数变量来记载队列中的元素个数。 初始化队列时c=0; 当入队时，计数变量1（ c=c+1 ） 当出队时，计数变量1 （c=c-1） 当计数变量MAXNUM时，队满 当计数变量0时，队空,方法二：设一个标志位用来区别队列是空还是满。 初始化队列时：Q.front=Q.rear，标志位为false 入队后，使Q.front=Q.rear，则置标志位为true 出队后，将标志位置为false 当Q.front=Q.rear, 且标志位为tr

35、ue时，队满。 当Q.front=Q.rear, 但标志位为false时，队空。 其他为非空非满。,97,队列的表示和实现,队列的链式表示-链队列 用链表表示队列，附设队首指针front和队尾指针rear,struct node elemtype data; struct node *next; ; struct qtype node * front; node *rear; Q;,Q.front,Q.rear,data,next,队首,队尾,头结点,98,链队列的实现,x,x,x,y,y,空队,元素x入队,元素y入队,元素x出队,99,队列的应用,操作系统中的作业、进程排队 银行业务模拟 等

36、等,数据结构,非线性结构,树与二叉树 图,树和二叉树,树是一类重要的非线性数据结构，是以分支关系定义的层次结构 3.1 树的定义 定义 定义：树(tree)是一个或多个（n）结点元素的有限集T，其中： 有且仅有一个特定的结点，称为树的根(root) 当n1时，其余结点可分为m(m0)个互不相交的有限集T1,T2,Tm，其中每一个集合本身又是一棵树，称为根的子树(subtree) 特点： 树中至少有一个结点根 树中各子树是互不相交的集合,根,子树,基本术语 结点(node)表示树中的元素，包括数据项及若干指向其子树的分支 结点的度(degree)结点拥有的子树数目 叶子(leaf)度为0的结点，

37、没有后继的结点 分支结点非叶子结点（非终端结点，或度不为0的节点） 孩子(child)某结点子树的根称为该结点的孩子 双亲(parents)孩子结点的上层结点叫该结点的双亲 兄弟(sibling)同一双亲的孩子互为兄弟 树的度一棵树中度最大的结点度数 结点的层次(level)从根结点算起，根为第一层，它的孩子为第二层，除根结点外，其他层数等于它的父结点的层数加1 深度(depth)树中结点的最大层次数 有序树与无序树有序树：兄弟有长幼之分，从左至右。交换兄弟位置，变成不同的树。 森林(forest)m(m0)棵互不相交的树的集合,结点A的度：3 结点B的度：2 结点M的度：0,叶子：K，L，F

38、，G，M，I，J,结点A的孩子：B，C，D 结点B的孩子：E，F,结点I的双亲：D 结点L的双亲：E,结点B，C，D为兄弟 结点K，L为兄弟,树的度：3,结点A的层次：1 结点M的层次：4,树的深度：4,3.2 二叉树 定义 定义：二叉树是n(n0)个结点的有限集，它或为空树(n=0)，或由一个根结点和两棵分别称为左子树和右子树的互不相交的二叉树构成 特点 每个结点至多有二棵子树(即不存在度大于2的结点) 二叉树的子树有左、右之分，且其次序不能任意颠倒 基本形态,对比树的定义： 空二叉树 树的定义中没有空树的概念 不多于2个孩子 树的节点可以有任意个子树 子树有左右之分 无序树可不区分左右,二

39、叉树就是一棵特殊的树（？）否,二叉树性质 性质1：,在二叉树的i层上，最多有2i-1个节点,性质2：深度为k的二叉树至多有 2k-1个结点(k1),性质3：对任何一棵二叉树T，如果其终端结点数为n0，度为2的结点数为n2，则n0=n2+1,几种特殊形式的二叉树 满二叉树,定义： 特点：每一层上的结点数都是最大结点数（所有分支结点都存在左子树和右子树，并所有叶结点都在同一层） 完全二叉树 定义：深度为k，有n个结点的二叉树当且仅当其每一个结点都与深度为k的满二叉树中编号从1至n的结点一一对应时，称为完全二叉树 特点 叶子结点只可能在层次最大的两层上出现 对任一结点，若其右分支下子孙的最大层次为L

40、，则其左分支下子孙的最大层次必为L 或L+1,性质4：,具有n个节点的完全二叉树的深度为log2n的下取整加1,3.3二叉树和树的存储结构 二叉树的存储结构 顺序存储结构 实现：按满二叉树的结点层次编号，依次存放二叉树中的数据元素 特点： 结点间关系蕴含在其存储位置中 浪费空间，适于存满二叉树和完全二叉树,链式存储结构 二叉链表,typedef struct node elemtype data; struct node *lchild, *rchild; JD;,在n个结点的二叉链表中，有n+1个空指针域,空指针个数：2*n0+1*n1+0*n2 =2n0+n1 =n0+n1+n0 =n0+

41、n1+n2+1 =n+1,将树转换成二叉树 加线：在兄弟之间加一连线 抹线：对每个结点，除了其左孩子外，去除其与其余孩子之间的关系 旋转：以树的根结点为轴心，将整树顺时针转45,树转换成的二叉树其右子树一定为空,孩子兄弟表示法（二叉树表示法） 实现：用二叉链表作树的存储结构，链表中每个结点的两个指针域分别指向其第一个孩子结点和下一个兄弟结点 特点 操作容易 破坏了树的层次,typedef struct node datatype data; struct node *fch, *nsib; JD;,b,树与二叉树转换,将二叉树转换成树 加线：若p结点是双亲结点的左孩子，则将p的右孩子，右孩子的

42、右孩子，沿分支找到的所有右孩子，都与p的双亲用线连起来 抹线：抹掉原二叉树中双亲与右孩子之间的连线 调整：将结点按层次排列，形成树结构,二叉树的遍历 按一定次序系统地访问该结构中的所有节点，使每个节点恰好被访问一次。 方法 先序遍历：先访问根结点,然后分别先序遍历左子树、右子树 中序遍历：先中序遍历左子树，然后访问根结点，最后中序遍历右子树 后序遍历：先后序遍历左、右子树，然后访问根结点 按层次遍历：从上到下、从左到右访问各结点,LDR、LRD、DLR RDL、RLD、DRL,3.4 树和二叉树的遍历,先序遍历：,中序遍历：,后序遍历：,层次遍历：,-,+,a,*,b,-,c,d,/,e,f,

43、-,+,a,*,b,-,c,d,/,e,f,-,+,a,*,b,-,c,d,/,e,f,-,+,a,*,b,-,c,d,/,e,f,仅知二叉树的先序序列“abcdefg” 不能唯一确定一棵二叉树， 如果同时已知二叉树的中序序列“cbdaegf”,则会如何？,由二叉树的先序和中序序列建树,二叉树的先序序列,二叉树的中序序列,左子树,左子树,右子树,右子树,根,根,a b c d e f g,c b d a e g f,例如:,a,a,b,b,c,c,d,d,e,e,f,f,g,g,a,b,c,d,e,f,g,先序序列中序序列,根据：前序遍历序列 ABHFDECKG 中序遍历序列 HBDFAEKC

44、G ,树的遍历 遍历按一定规律走遍树的各个顶点，且使每一顶点仅被访问一次，即找一个完整而有规律的走法，以得到树中所有结点的一个线性排列 常用方法 先根（序）遍历：先访问树的根结点，然后依次先根遍历根的每棵子树 后根（序）遍历：先依次后根遍历每棵子树，然后访问根结点 按层次遍历：先访问第一层上的结点，然后依次遍历第二层，第n层的结点,先序遍历：,后序遍历：,层次遍历：,A,B,E,F,I,G,C,D,H,J,K,L,N,O,M,E,I,F,G,B,C,J,K,N,O,L,M,H,D,A,A,B,C,D,E,F,G,H,I,J,K,L,M,N,O,树的遍历和二叉树遍历的对应关系 ？,先根遍历,后根

45、遍历,树,二叉树,森林,先序遍历,先序遍历,中序遍历,中序遍历,中根遍历 中序遍历,LDR,DLR,先根遍历 先序遍历,LRD,后根遍历 后序遍历,利用递归的遍历算法,若二叉树为空，遍历结束，否则： （1）按中序遍历方式遍历根结点的左子树 （2）访问根结点； （3）按中序遍历方式遍历根结点的右子树,若二叉树为空，遍历结束，否则： （1）访问根结点； （2）按先序遍历方式遍历根结点的左子树 （3）按先序遍历方式遍历根结点的右子树,若二叉树为空，遍历结束，否则： （1）按后序遍历方式遍历根结点的左子树 （2）按后序遍历方式遍历根结点的右子树 （3）访问根结点；,void inorder( bnod

46、e *BT ) if(BT=NULL) return; else if( BT-LC != NULL) inorder (BT-LC); visite(BT); if( BT-RC != NULL) inorder(BT-RC); ,void postorder(bnode *BT ) if(BT=NULL) return; else if( BT-LC != NULL) postorder (BT-LC); if( BT-RC != NULL) postorder(BT-RC); visite(BT); ,void preorder( bnode *BT ) if(BT=NULL) retu

47、rn; else visite(BT); if( BT-LC != NULL) preorder (BT-LC); if( BT-RC != NULL) preorder(BT-RC); ,Typedef struct btreenod elemtype data; struct btreenode *LC; struct btreenode *RC; bnode;,void preorder(bnode *bt) if(bt!=NULL) printf(%dt,bt-data); preorder(bt-LC); preorder(bt-RC); ,返回,返回,返回,返回,A,C,B,D,返

48、回,先序序列：A B D C,中序遍历非递归算法,void inorder(bnode *bt) int i=0; bnode *p,*sM; p=bt; do while(p!=NULL) si+=p; p=p-LC; if(i0) p=s-i; printf(%dt,p-data); p=p-RC; while(i0|p!=NULL); ,中序遍历二叉树的非递归算法1 Status InOrderTraverse(BiTree T,Status(*Visit)(TElemType e) InitStack(S); Push(S,T);/根指针进栈 While(!StackEmpty(S)

49、while(GetTop(S,p),中序遍历二叉树的非递归算法2 Status InOrderTraverse(BiTree T,Status(*Visit)(TElemType e) InitStack(S);p=t; While(p|!StackEmpty(S) if(p)Push(S,p);p=p -lchild; /根指针进栈，遍历左子树 else/根指针退栈，访问根结点，遍历右子树 Pop(S,p); p=p -rchild; /else /while return OK; ,Level-by-level traversal,void Level_by_level(bnode *ro

50、ot) bnode *qitem; if (root != NULL) Queue Q; Q.append(root); while (!Q.empty() Q.retrieve( ,3.5 遍历算法的应用举例,2、统计二叉树中叶子结点的个数,3、求二叉树的深度(后序遍历),1、查询二叉树中某个结点,5、按先序遍历序列建立二叉树,4、二叉树中结点个数,在二叉树不空的前提下,和根结点的元素进行比较,若相等,则找到返回 TRUE;,否则在左子树中进行查找,若找到, 则返回 TRUE;,否则继续在右子树中进行查找,若找到,则返回 TRUE,否则返回 FALSE;,1、查询二叉树中某个结点,Statu

51、s Preorder (bnode *T, ElemType x, bnode *p) / 若二叉树中存在和 x 相同的元素，则 p 指向该结点并返回 OK, / 否则返回 FALSE ,if (T) if (T-data=x) p = T; return OK, /if else return FALSE;,else if (Preorder(T-LC, x, p) return OK; else return(Preorder(T-RC, x, p) ; /else,2、统计二叉树中叶子结点的个数,算法基本思想:,先序(或中序或后序)遍历二叉树，在遍历过程中查找叶子结点，并计数。 由此，需

52、在遍历算法中增添一个“计数”的参数，并将算法中“访问结点” 的操作改为:若是叶子，则计数器增1。,void CountLeaf (bnode *T, int *count) if ( T ) if (!T-LC) / if / CountLeaf,3、求二叉树的深度(后序遍历),算法基本思想:,从二叉树深度的定义可知，二叉树的深度应为其左、右子树深度的最大值加1。由此，需先分别求得左、右子树的深度，算法中“访问结点”的操作为:求得左、右子树深度的最大值，然后加 1 。,首先分析二叉树的深度和它的左、右子树深度之间的关系。,int Depth (bnode *T ) / 返回二叉树的深度 if

53、( !T ) depthval = 0; else depthLeft = Depth( T-LC ); depthRight= Depth( T-LR); depthval = 1 + (depthLeft depthRight ? depthLeft : depthRight); return depthval; ,4、二叉树中结点个数,算法基本思想:,先序(或中序或后序)遍历二叉树，在遍历过程中碰到结点，就计数。 由此，需在遍历算法中增添一个“计数”的参数，碰到一个结点，计数器增1。,int btsize (bnode *T ) / 返回二叉树的深度 if ( !T ) size = 0

54、; else sizeLeft = btsize( T-LC); sizeRight= btsize( T-RC ); size = 1 + sizeLeft+sizeRight; return size; ,5、按先序遍历序列建立二叉树,设输入次序：（以先根为序）,ABC_ _ DEF _ _ G _ _ _ H _ I _ JK _ _ L _ _,A,B,C,_,_,D,E,F,_,_,G,_,_,_,H,_,I,_,J,K,_,_,L,_,_,每一个空格“_”表示一个空指针,利用先根遍历算法框架，建立二叉树,根据输入的情况，将新节点放在指定的位置，然后从新节点开始下一个过程,若希望建立

55、如下二叉树对应的存储结构，应输入的字符序列是,按先序序列建立二叉树的算法,Status CreateBiTree(bnode *T) /按先序次序输入二叉树中的结点值(一个字符)， /空格表示空树， /构造二叉链表表示的二叉树T scanf( ,3.6 二叉排序树,二叉排序树(二叉查找树)： 若此树不为空（1）若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值；（2）若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值；（3）它的左右子树也分别为二叉排序树（树中结点采用二叉链表结构）,从空树开始，经过一系列查找插入操作后，可生成一棵二叉排序树,二叉排序树,二叉排序树的特点 中

56、序遍历二叉排序树可得到一个关键字的有序序列（即：可以通过输入一个无序序列，而通过构造二叉排序树后进行遍历的方法实现排序） 二叉排序树的插入过程不需要移动其他记录 具有相同n个结点的二叉排序树会因为构造的时候关键字插入的顺序不同而不同(下页说明) 二叉排序树的查找算法具有折半查找的特性，同时又采用了链式存储结构，因此是动态查找表的适宜表示,如：查找的关键序列分别为27,32,16,14、 16,14,27,32和14,16,27, 32, 生成二叉排序树分别如下：,27,16,32,14,16,14,27,32,14,16,27,32,二叉排序树的插入(创建)算法,Status InsertBS

57、T(BiTree ,Status SearchBST(BiTree T, KeyType key, BiTree f, BiTree ,Void Creat_Binary_Sort_tree(bnode *proot) bnode *p,*q; elemtype k; int i,n; *proot=NULL; printf(“input n:”); scanf(“%d”,while(q!=NULL) if(q-datak) if(q-LC!=NULL) q=q-LC; else q-LC=p; q=NULL; else if(q-RC!=NULL) q=q-RC; else q-RC=p; q