算法和数据结构精品文稿.ppt

《算法和数据结构精品文稿.ppt》由会员分享，可在线阅读，更多相关《算法和数据结构精品文稿.ppt（79页珍藏版）》请在得力文库 - 分享文档赚钱的网站上搜索。

1、程序设计程序设计=计算机编程语言计算机编程语言+数据结构数据结构+算法算法数据结构是指数据的逻辑结构和存储结构，而算数据结构是指数据的逻辑结构和存储结构，而算法则是对数据运算的描述。法则是对数据运算的描述。程序设计的实质是对实际问题选择一种好的数程序设计的实质是对实际问题选择一种好的数据结构，加之设计一个好的算法。据结构，加之设计一个好的算法。第1页，本讲稿共79页算法的定义算法的定义算法的要素算法的要素算法的表示算法的表示算法与计算机程序的关系算法与计算机程序的关系算法设计的基本方法算法设计的基本方法对算法的评价对算法的评价第2页，本讲稿共79页算法的定义算法的定义一组明确的可执行步骤的有序

2、集合一组明确的可执行步骤的有序集合例：输入两个正整数例：输入两个正整数m m和和n(mn),n(mn),求它们的最大公求它们的最大公约数约数,记为记为god(m,n)god(m,n)。根据欧几里德算法：根据欧几里德算法：若若 r r 是是 m n m n 的余数的余数,则则 gcd(m,n)=gcd(n,r)gcd(m,n)=gcd(n,r)第3页，本讲稿共79页适合计算机实现的算法适合计算机实现的算法(辗转相除法辗转相除法)：如如 m=28,n=8,m=28,n=8,则则god(28,8)=god(8,4)=god(4,0)=4god(28,8)=god(8,4)=god(4,0)=4算法描

3、述算法描述算法描述算法描述自然语言：自然语言：自然语言：自然语言：1.1.输入输入m,n(mn)m,n(mn)；2.2.求求m/nm/n的余数的余数 r r；3.3.如果如果r0r0则将则将n n放入放入m m，r r放入放入n n，转第，转第2 2步继续；如步继续；如果果r=0r=0则转第则转第4 4步步4.4.输出最大公约数输出最大公约数n n。第4页，本讲稿共79页开始开始开始开始m mod nrm mod nrm mod nrm mod nrnmnmnmnmrnrnrnrn是是是是否否否否结束结束结束结束打印打印打印打印n n n n输入输入输入输入m,nm,nm,nm,nr=0?r=

4、0?r=0?r=0?流程图：第5页，本讲稿共79页算法的特征算法的特征n有穷性（有穷性（finitenessfiniteness）-能在有限时间内做完；能在有限时间内做完；n确定性（确定性（definitenessdefiniteness）-每一步骤都有明确定义；每一步骤都有明确定义；n可行性（可行性（effectivenesseffectiveness）-能实现和达到预期目的；能实现和达到预期目的；n信息性（信息性（informationinformation）-能提供足够的情报，具有输能提供足够的情报，具有输入、输出。入、输出。算法的要素算法的要素n精确精确,简单和抽象分级简单和抽象分级第

5、6页，本讲稿共79页算法的表示算法的表示n流程图流程图nN-SN-S图图n伪码伪码程序流程图 NS图 伪码第7页，本讲稿共79页算法与计算机程序算法与计算机程序n算法是逻辑步骤算法是逻辑步骤n计算机程序是使用某种编程语言表达算法计算机程序是使用某种编程语言表达算法第8页，本讲稿共79页算法设计的基本方法算法设计的基本方法n列举法列举法-根据提出的问题列举所有可能的情况，并根据提出的问题列举所有可能的情况，并用问题中给定的条件检验哪些是需要的，而哪些是不用问题中给定的条件检验哪些是需要的，而哪些是不需要的；需要的；n递推法递推法-从已知的初始条件出发，逐次地推出所要从已知的初始条件出发，逐次地推

6、出所要求的各中间结果和最后结果；求的各中间结果和最后结果；n减半递推法减半递推法-工程上常用的分治法，即将问题工程上常用的分治法，即将问题的规模减半来解，最后重复的规模减半来解，最后重复“减半减半”的过程；的过程；第9页，本讲稿共79页n递归法递归法 -首先将问题逐层分解最后归结为一些最简首先将问题逐层分解最后归结为一些最简单的问题，解决这些最简单问题后再沿着原来分解的逆单的问题，解决这些最简单问题后再沿着原来分解的逆过程逐步进行综合。过程逐步进行综合。n回溯法回溯法-在处理复杂数据结构时，通过对问题的分析在处理复杂数据结构时，通过对问题的分析找出一个解决问题的线索，然后沿着次线索逐步试探，若

7、找出一个解决问题的线索，然后沿着次线索逐步试探，若失败就逐步回退并换别的路线再进行试探；失败就逐步回退并换别的路线再进行试探；n归纳法归纳法-通过列举足够多的特殊情况发现其中一通过列举足够多的特殊情况发现其中一些规律，经过分析最终找出一般的关系；些规律，经过分析最终找出一般的关系；第10页，本讲稿共79页算法举例算法举例第11页，本讲稿共79页输入一个数 maxn=2当nmaxymax=xn=n+1输出其中的最大值 max 输入十个数，找出最大数输出（输入十个数，找出最大数输出（递推法递推法 ）第12页，本讲稿共79页假定一对刚出生的小兔子，一个月后就能长成大兔子，假定一对刚出生的小兔子，一个

8、月后就能长成大兔子，再过一个月后就开始生小兔子，并且也正好生一对兔子。再过一个月后就开始生小兔子，并且也正好生一对兔子。问在没有兔子死亡的情况下，一对初生的兔子一年后可问在没有兔子死亡的情况下，一对初生的兔子一年后可繁殖成多少对兔子。（繁殖成多少对兔子。（递推法递推法）解：用解：用 F F(n n)表示第表示第 n n 个月的兔子对数。个月的兔子对数。第一个月：第一个月：F F(1)=1(1)=1 第二个月：第二个月：F F(2)=(2)=F F(1)+0=1(1)+0=1 第三个月：第三个月：F F(3)=(3)=F F(2)+1=2(2)+1=2 第四个月：第四个月：F F(4)=(4)=

9、F F(3)+1=3(3)+1=3 第五个月：第五个月：F F(5)=(5)=F F(4)+2=5(4)+2=5 第六个月：第六个月：F F(6)=(6)=F F(5)+3=8(5)+3=8 第七个月：第七个月：F F(7)=(7)=F F(6)+5=13(6)+5=13第13页，本讲稿共79页递推到一年后即第十三个月，得递推到一年后即第十三个月，得 Fibonacci Fibonacci数列：数列：1 1，1 1，2 2，3 3，5 5，8 8，1313，2121，3434，5555，8989，144144，233 233 分析可知：分析可知：第第 n n 个月的兔子对数由两部分组成：一是第

10、个月的兔子对数由两部分组成：一是第 n n-1-1 个月个月的兔子对数；的兔子对数；二是第二是第 n n-2-2 个月的兔子对数个月的兔子对数 所以得递推关系为所以得递推关系为 F F(1)=1(1)=1 F F(2)=1(2)=1 F F(n n)=)=F F(n n-1)+-1)+F F(n-n-2)2)n n=3,4,=3,4,第14页，本讲稿共79页求求Fibonacci数列流程图数列流程图开始开始F1=1,F2=1,n=3n1i=i-1x=xixi=2(x+1)输出 i,xii=7,x=1结束NY开始第第7天：天：1第第6天：天：4第第5天：天：10第第4天：天：22第第3天：天：4

11、6第第2天：天：94第第1天：天：190第18页，本讲稿共79页0 0f(x1)f(x1)f(x2)f(x2)f(x3)f(x3)f(x4)f(x4)x1x1x2x2x3x3x4x4减半递推（迭代）法减半递推（迭代）法设方程设方程 f(x)=0 f(x)=0在区间在区间x1,x2x1,x2上有一个实根，且上有一个实根，且f(x1)f(x1)与与f(x2)f(x2)异号，用二分异号，用二分法求该方程在区间法求该方程在区间x1,x2x1,x2上的实根。上的实根。减半递推过程：减半递推过程：1.1.求中点：求中点：x3=1/2(x1+x2)x3=1/2(x1+x2)2.2.判判 f(x3)f(x3)

12、是否接近是否接近0 0？若接近若接近0 0，x3x3即为所求根即为所求根 若不接近若不接近0 0，则将原区间减半，则将原区间减半 舍弃与舍弃与f(x3)同号者：同号者：x2=x3 再求中点：再求中点：x4=1/2(x1+x3)如此重复得：如此重复得：x1,x2,xn-1,xn当当xn与与xn-1之差小于给定的误差之差小于给定的误差En时，时，xn即为近似解即为近似解迭代关系：迭代关系：迭代关系：迭代关系：x3=(x1+x2)/2 x3=(x1+x2)/2舍弃与舍弃与f(x3)同号者：同号者：f(x3)*f(x2)0:x2=x3;f(x3)*f(x2)0:x2=x3;/*/*为下一次迭代做准备为

13、下一次迭代做准备为下一次迭代做准备为下一次迭代做准备*/*/f(x3)*f(x1)0:x1=x3;f(x3)*f(x1)0:x1=x3;第19页，本讲稿共79页f(x3)*f(x1)10-4输出结果x3YN流程图流程图第20页，本讲稿共79页算法的评价算法的评价n时间复杂度：时间复杂度：指算法中包含简单操作的次数指算法中包含简单操作的次数假如，随着问题规模假如，随着问题规模 n n 的增长，算法执行时间的增长率和的增长，算法执行时间的增长率和 f(n)f(n)的增长率相同，则可记作：的增长率相同，则可记作：T(n)=O(f(n)T(n)=O(f(n)称称T(n)T(n)为算法的为算法的(渐近渐

14、近)时间复杂度时间复杂度一般以数量级的形式给出一般以数量级的形式给出如如(1),(log(1),(log2 2n n),(n),(n),(n),(n2 2)其中其中(1)(1)表示算法的时间复杂度为常量，它不随数据量表示算法的时间复杂度为常量，它不随数据量n n的改变而改变，如访问一个数据表中第一个元素时，的改变而改变，如访问一个数据表中第一个元素时，无论该表的大小如何，其时间复杂度均为无论该表的大小如何，其时间复杂度均为(1)(1)第21页，本讲稿共79页For i=1 to nFor i=1 to n1 do1 do y=y+1;y=y+1;/*/*/For j=0 to 2n do Fo

15、r j=0 to 2n do x=x+1;x=x+1;/*/*/语句语句的执行次数为：的执行次数为：n n1 1，语句语句的执行次数为：（的执行次数为：（n n1 1）（）（2n2n1 1）2n2n2 2n n1 1该程序段的时间复杂度为：该程序段的时间复杂度为：T T（n n）O O（n n1 12n2n2 2n n1 1）O O（n n2 2）第22页，本讲稿共79页空间复杂度空间复杂度空间复杂度主要考虑在算法运行过程中临时占用的存储空间复杂度主要考虑在算法运行过程中临时占用的存储空间的大小空间的大小假如，随着问题规模假如，随着问题规模 n n 的增大，算法运行所需存储量的的增大，算法运行

16、所需存储量的增长率与增长率与 g(n)g(n)的增长率相同，则可记作：的增长率相同，则可记作：S(n)=O(g(n)S(n)=O(g(n)称称S(n)S(n)为算法的空间复杂度为算法的空间复杂度第23页，本讲稿共79页数据结构的基本术语数据结构的基本术语数据的逻辑结构数据的逻辑结构数据的存储结构数据的存储结构第24页，本讲稿共79页基本术语基本术语n数据：信息的载体，它能够被计算机识别、存储和加数据：信息的载体，它能够被计算机识别、存储和加工处理。工处理。n数据元素：是数据的基本单位。数据元素：是数据的基本单位。n数据项：具有独立意义的最小数据单位，是对数据元数据项：具有独立意义的最小数据单位

17、，是对数据元素属性的描述，也称域或字段。素属性的描述，也称域或字段。n数据对象：指具有相同性质的数据元素的集合，是数据对象：指具有相同性质的数据元素的集合，是数据的一个子集。数据的一个子集。n数据处理：指对数据集合中的各元素，以各种方式进数据处理：指对数据集合中的各元素，以各种方式进行处理，包括对数据的插入、删除、查找、更新、排行处理，包括对数据的插入、删除、查找、更新、排序等基本运算，也包括对数据元素进行分析。序等基本运算，也包括对数据元素进行分析。第25页，本讲稿共79页数据结构的定义：数据结构的定义：互相有关联的数据元素的集合互相有关联的数据元素的集合一个数据结构应包含两方面信息：一个数

18、据结构应包含两方面信息：1.1.所有数据元素的信息所有数据元素的信息2.2.各数据元素之间的关系各数据元素之间的关系 第26页，本讲稿共79页数据结构研究的内容数据结构研究的内容1.1.数据集合中，各种数据元素之间所固有的逻数据集合中，各种数据元素之间所固有的逻辑关系，即辑关系，即数据的逻辑结构数据的逻辑结构。2.2.在对数据进行处理时，各数据元素在计算机中的存在对数据进行处理时，各数据元素在计算机中的存储关系，即储关系，即数据的存储结构数据的存储结构。3.3.对各种数据结构进行的运算，其中常用的有对各种数据结构进行的运算，其中常用的有检检索、插入、删除、排序索、插入、删除、排序等。等。第27

19、页，本讲稿共79页数据的逻辑结构数据的逻辑结构-反映数据元素之间的逻辑关系反映数据元素之间的逻辑关系一个数据结构可以表示为一个二元组：一个数据结构可以表示为一个二元组：B=B=（D D，R R）D D是数据元素的集合，是数据元素的集合，R R是定义在是定义在D D上的二元关系的集合，反映了上的二元关系的集合，反映了D D中各元素中各元素之间的前驱与后继关系之间的前驱与后继关系二个要素二个要素1.1.数据元素的集合数据元素的集合D D2.2.D D上的二元关系上的二元关系R R举例举例第28页，本讲稿共79页例例1.1.一年四季的数据结构。一年四季的数据结构。表示为：表示为：Season=Sea

20、son=（D D，R R）D=D=（春，夏，秋，冬）（春，夏，秋，冬）R=R=（春，夏），（夏，秋），（秋，冬）（春，夏），（夏，秋），（秋，冬）例例2.2.n n维向量维向量X=X=（x1x1，x2x2，xnxn）的数据结构。）的数据结构。表示为：表示为：X=X=（D D，R R）D=D=（x1x1，x2 x2，xnxn）R=R=（x1x1，x2x2），（），（x2x2，x3x3），（，（xn-1xn-1，xnxn）例例3.3.家庭成员的数据结构。家庭成员的数据结构。表示为：表示为：Family=Family=（D D，R R）D=D=（父亲，儿子，女儿）（父亲，儿子，女儿）R=R=（父亲，

21、儿子），（父亲，女儿）（父亲，儿子），（父亲，女儿）第29页，本讲稿共79页根据数据结构中各数据元素之间的根据数据结构中各数据元素之间的前驱前驱与与后继后继关系的复关系的复杂程度，逻辑上可以把数据结构分为杂程度，逻辑上可以把数据结构分为线性结构线性结构和和非非线性结构线性结构。一个非空的线性数据结构应满足两个条件：一个非空的线性数据结构应满足两个条件：有且仅有一个根结点（没有前驱的结点）；有且仅有一个根结点（没有前驱的结点）；每一个结点最多只有一个前驱，一个后继；每一个结点最多只有一个前驱，一个后继；如果一个数据结构不是线性的，则称为非线性结构（树如果一个数据结构不是线性的，则称为非线性结构（

22、树形结构、图形结构或网状结构）。形结构、图形结构或网状结构）。例例1 1、例、例2 2属于线性结构，例属于线性结构，例3 3为非线性结构。为非线性结构。第30页，本讲稿共79页n三种基本结构图示三种基本结构图示1.1.线性结构：元素之间是一对一的关系线性结构：元素之间是一对一的关系2.2.树形结构：元素之间是一对多的关系树形结构：元素之间是一对多的关系(非线性非线性)3.3.图形结构或网状结构：元素之间是多对多的关图形结构或网状结构：元素之间是多对多的关系系(非线性非线性)第31页，本讲稿共79页数据的存储结构：数据的存储结构：即数据的逻辑结构在计算机存即数据的逻辑结构在计算机存储空间中的存放

23、形式储空间中的存放形式常见四种：常见四种：1.1.顺序存储结构顺序存储结构2.2.链式存储结构链式存储结构3.3.索引存储结构索引存储结构4.4.散列存储结构散列存储结构第32页，本讲稿共79页线性表的基本概念线性表的基本概念线性表的顺序存储及其运算线性表的顺序存储及其运算线性表的链式存储及其运算线性表的链式存储及其运算第33页，本讲稿共79页线性表的基本概念线性表的基本概念n线性表是由线性表是由n n（n=0）个元素个元素a1a1，a2a2，anan组成组成的有限序列，记为：（的有限序列，记为：（a1a1，a2a2，anan）。）。数据元素（也称为结点）的个数数据元素（也称为结点）的个数 n

24、 n 称为线性表称为线性表的长度，的长度，n=0n=0时称此线性表为空表。时称此线性表为空表。n非空线性表（非空线性表（a a1 1,a,a2 2,a,an n）的结构特征：）的结构特征：若线性表非空，第一个元素无前驱；最后一个元素无后继；若线性表非空，第一个元素无前驱；最后一个元素无后继；其他元素仅有一个直接前驱和一个直接后继。其他元素仅有一个直接前驱和一个直接后继。第34页，本讲稿共79页线性表的顺序存储及其运算线性表的顺序存储及其运算n线性表的顺序存储线性表的顺序存储1.1.所有元素所占的存储空间连续所有元素所占的存储空间连续2.2.各数据元素在存储空间中按逻辑顺序依次存放各数据元素在存

25、储空间中按逻辑顺序依次存放 ADR(a ADR(ai i)=ADR(a)=ADR(a1 1)+(i-1)k)+(i-1)k第35页，本讲稿共79页n顺序表的基本运算顺序表的基本运算1.1.顺序表的插入顺序表的插入长度为长度为n n的顺序表（的顺序表（a a1 1,a,a2 2,a,ai i,a,an n），在第），在第i i个元素之前插入一个元素之前插入一个新元素个新元素 x x，插入后得到长度为，插入后得到长度为n+1n+1的顺序表的顺序表（a a1 1,a,a2 2,x x,a,ai i,a,an n）算法：从算法：从a an n到到 a ai i,依次后移，然后插入依次后移，然后插入x

26、x2.2.线性表的删除线性表的删除 将表的第将表的第i i（1in1in）个结点删去，使长度为）个结点删去，使长度为n n的线性表的线性表 （a1a1，ai-1ai-1，aiai，ai+1ai+1，anan）变成长度为变成长度为n-1n-1的线性表的线性表 （a1a1，ai-1ai-1，ai+1ai+1，anan）算法：从算法：从a ai+1i+1到到a an n,依次前移依次前移第36页，本讲稿共79页线性表的顺序存储结构具有简单、存储密度大、空线性表的顺序存储结构具有简单、存储密度大、空间利用率高、对表中任一元素可直接确定其存储地间利用率高、对表中任一元素可直接确定其存储地址（随机存取）、

27、效率高等优点；址（随机存取）、效率高等优点；但是也有明显的不足：在顺序表中进行插入与删除但是也有明显的不足：在顺序表中进行插入与删除等操作时，需大量移动数据元素，浪费时间。等操作时，需大量移动数据元素，浪费时间。对于对于大的大的线性表，特别是线性表，特别是元素变动频繁元素变动频繁的大线性表，的大线性表，不宜采用顺序存储结构，而是采用不宜采用顺序存储结构，而是采用链式链式存储结构。存储结构。第37页，本讲稿共79页线性表的链式存储及其运算线性表的链式存储及其运算n链式存储链式存储一个链表结点由两个域构成：数据域和指针域一个链表结点由两个域构成：数据域和指针域数据域存放数据元素值数据域存放数据元素

28、值指针域指向该结点的后继结点指针域指向该结点的后继结点通过每个结点的指针域将通过每个结点的指针域将n n个结点按其逻辑顺序连接在一起个结点按其逻辑顺序连接在一起而构成的数据存储结构，称为链式存储结构。而构成的数据存储结构，称为链式存储结构。用一个头指针专门用来指向线性链表中的第一个结点，线性用一个头指针专门用来指向线性链表中的第一个结点，线性链表中最后一个元素没有后继，指针域为空（用链表中最后一个元素没有后继，指针域为空（用NULLNULL或或0 0表表示）。示）。第38页，本讲稿共79页线性链表的物理存储状态线性链表的物理存储状态线性链表的逻辑存储状态线性链表的逻辑存储状态第39页，本讲稿共

29、79页单链表的基本运算单链表的基本运算1.1.单链表的结点插入单链表的结点插入 算法：算法：（1 1）找到）找到ai-1ai-1存储位置存储位置p p（2 2）确定要插入的新结点的位置）确定要插入的新结点的位置s s（3 3）在新结点的数据域中输入）在新结点的数据域中输入x x（4 4）新结点的指针域指向结点）新结点的指针域指向结点aiai。（5 5）结点）结点p p的指针域指向新结点的指针域指向新结点第40页，本讲稿共79页2.2.单链表的结点删除单链表的结点删除 算法：算法：（1 1）找到）找到ai-1ai-1的存储位置的存储位置p p（因为在单链表中结点（因为在单链表中结点aiai的存储

30、地址是在其直的存储地址是在其直接前趋结点接前趋结点ai-1ai-1的指针域中）的指针域中）（2 2）找到）找到aiai的存储位置的存储位置r r （3 3）令）令p p的指针域指向的指针域指向aiai的直接后继结点（即把的直接后继结点（即把aiai从链上摘下）从链上摘下）（4 4）释放结点）释放结点aiai的空间，将其归还给的空间，将其归还给 存储池存储池。第41页，本讲稿共79页栈及其基本运算栈及其基本运算队列及其基本运算队列及其基本运算第42页，本讲稿共79页栈及其基本运算栈及其基本运算n定义：堆栈（定义：堆栈（StackStack）可以看成是一种）可以看成是一种“特殊的特殊的”线性表，这

31、种线线性表，这种线性表上的插入和删除运算限定在表的某一端进行的。性表上的插入和删除运算限定在表的某一端进行的。(1)(1)通常称插入、删除的这一端为栈顶（通常称插入、删除的这一端为栈顶（TopTop），另一端称），另一端称为栈底（为栈底（BottomBottom）。）。(2)(2)当表中没有元素时称为空栈。当表中没有元素时称为空栈。(3)(3)栈为后进先出的线性表，简称为栈为后进先出的线性表，简称为LIFOLIFO表。表。栈的示意图第43页，本讲稿共79页n栈的顺序存储及其运算栈的顺序存储及其运算利用一组地址连续的存储单元依次存放自栈底到栈顶的数利用一组地址连续的存储单元依次存放自栈底到栈顶的

32、数据元素。据元素。通常，栈底指针指向栈空间的低地址一端通常，栈底指针指向栈空间的低地址一端1.1.入栈运算入栈运算n首先将栈顶指针加首先将栈顶指针加1 1（即（即toptop加加1 1）n然后将新元素插入到栈顶指针指向的位置。然后将新元素插入到栈顶指针指向的位置。n当栈顶指针已经指向存储空间的最后一个位置时，说当栈顶指针已经指向存储空间的最后一个位置时，说明栈空间已满，不可能再进行入栈操作。这种情况称明栈空间已满，不可能再进行入栈操作。这种情况称为栈的为栈的“上溢上溢”。上溢是一种出错状态，应设法避。上溢是一种出错状态，应设法避免。免。n第44页，本讲稿共79页栈在顺序存储结构下的运算第45页

33、，本讲稿共79页2.2.退栈运算退栈运算首先将栈顶元素（即栈顶指针指向的元素）赋给一个首先将栈顶元素（即栈顶指针指向的元素）赋给一个指定的变量指定的变量然后将栈顶指针减然后将栈顶指针减1 1（即（即toptop减减1 1）。）。当栈顶指针为当栈顶指针为0 0时，说明栈空，不可能进行退栈运算。时，说明栈空，不可能进行退栈运算。这种情况称为栈的这种情况称为栈的“下溢下溢”错误。错误。3.3.读栈顶运算读栈顶运算读栈顶元素是指将栈顶元素赋给一个指定的变量。读栈顶元素是指将栈顶元素赋给一个指定的变量。在这个运算中，栈顶指针不会改变。在这个运算中，栈顶指针不会改变。当栈顶指针为当栈顶指针为0 0时，说明

34、栈空，读不到栈顶元素。时，说明栈空，读不到栈顶元素。第46页，本讲稿共79页队列及其基本运算队列及其基本运算n定义：定义：是只允许在一端进行插入，而在另一是只允许在一端进行插入，而在另一端进行删除的运算受限的线性表。端进行删除的运算受限的线性表。n允许删除的一端称为队头（允许删除的一端称为队头（FrontFront），允许插），允许插入的一端称为队尾（入的一端称为队尾（RearRear）。）。n队列亦称作先进先出的线性表，简称为队列亦称作先进先出的线性表，简称为FIFOFIFO表。表。具有7个元素的队列示意图第47页，本讲稿共79页插入和删除队列元素示意图1.1.入队运算入队运算首先将新元素插

35、入到队尾指针指向的位置，然后将队尾指首先将新元素插入到队尾指针指向的位置，然后将队尾指针加针加1 1（即（即rearrear1 1）2.2.出队运算出队运算首先将队首指针指向的元素赋给指定的变量，然后将队首首先将队首指针指向的元素赋给指定的变量，然后将队首指针加指针加1 1（即（即frontfront1 1）第48页，本讲稿共79页循环队列及其运算循环队列及其运算n循环队列：将队列存储空间的最后一个位置绕到循环队列：将队列存储空间的最后一个位置绕到第一个位置，形成逻辑上的环状空间第一个位置，形成逻辑上的环状空间n初始状态为空：初始状态为空：rear=frontrear=frontn当队列满了，

36、也有：当队列满了，也有：rear=frontrear=front，需要一个标志变量，需要一个标志变量s s循环队列存储空间示意图第49页，本讲稿共79页循环队列出队运算循环队列出队运算n首先将队首指针指向的元素赋给指定的变量，然后将队首先将队首指针指向的元素赋给指定的变量，然后将队首指针加首指针加1 1（即（即frontfront1 1），并当），并当frontfrontm m1 1时置时置frontfront1 1，这时如果，这时如果frontfrontrearrear，则说明队空，应将，则说明队空，应将s s置置0 0。n当循环队列为空时，不能进行出队运算，这种情况称为当循环队列为空时，不

37、能进行出队运算，这种情况称为“下下溢溢”。循环队列及其删除运算示意图第50页，本讲稿共79页循环队列入队运算循环队列入队运算n首先将新元素插入到队尾指针指向的位置，然后将队尾指针首先将新元素插入到队尾指针指向的位置，然后将队尾指针加加1 1（即（即rearrear1 1），当），当rearrearm m1 1时置时置rearrear1 1，这时如果，这时如果s s0 0，则置，则置s s1 1，表示队列非空。，表示队列非空。n当循环队列非空（即当循环队列非空（即s s1 1）且）且fontfontrearrear时，说明循环队列已满，时，说明循环队列已满，不能进行入队运算，这种情况称为不能进行

38、入队运算，这种情况称为“上溢上溢”。循环队列及其插入除运算示意图第51页，本讲稿共79页树的基本概念树的基本概念二叉树及其基本性质二叉树及其基本性质二叉树的存储结构二叉树的存储结构二叉树的遍历二叉树的遍历第52页，本讲稿共79页 树型结构是以分支关系定义的层次结构，是一种重要的非线性结构。树型结构是以分支关系定义的层次结构，是一种重要的非线性结构。基本概念基本概念定义：树是定义：树是n n个结点的有限集个结点的有限集T T，具有明显的层次结构。其中：，具有明显的层次结构。其中：1.1.一个特定的结点称为该树的根（一个特定的结点称为该树的根（root root）结点）结点;2.2.结点之外的其余

39、结点可分为结点之外的其余结点可分为 m m（m 0 m 0）个互不相交的有限集）个互不相交的有限集合合 T1,T2,.,Tm T1,T2,.,Tm，且其中每一个集合本身又是一棵树，称，且其中每一个集合本身又是一棵树，称之为根的子树（之为根的子树（subtree subtree）。）。只有根结点的树只有根结点的树AHGFBEDCAKMJIL一般的树一般的树第53页，本讲稿共79页n基本术语基本术语结点的度结点的度树的度树的度叶子叶子分支结点分支结点双亲和孩子双亲和孩子结点的层结点的层树的深度树的深度兄弟和堂兄弟兄弟和堂兄弟祖先和子孙祖先和子孙有序树和无序树有序树和无序树森林森林HGFBEDCAK

40、MJIL树的图形表示树的图形表示结点的度：一个结点的子结点的度：一个结点的子树数目。树数目。结点结点A的度：的度：3结点结点C的度：的度：1结点结点M的度：的度：0树的度：所有结点中最大树的度：所有结点中最大的度。的度。树的度：树的度：3叶子：树中度为叶子：树中度为0的结点。的结点。叶子：叶子：E,K,L,G,H,M,J分支结点：树中度不为分支结点：树中度不为0的的结点。结点。分支结点：分支结点：A,B,F,C,D,I双亲和孩子：结点的子树的双亲和孩子：结点的子树的根称为该结点的孩子，相应根称为该结点的孩子，相应地，该结点称为孩子结点的地，该结点称为孩子结点的双亲双亲结点结点A是是B,C,D的

41、双亲，的双亲，B,C,D是结点是结点A的孩子的孩子结点的层：约定树的根节点结点的层：约定树的根节点的层为的层为1，其余结点的层是其，其余结点的层是其双亲的层加双亲的层加1结点结点A的层：的层：1结点结点B,C,D的层：的层：2结点结点E,F,G的层：的层：3树的深度：树中各结点的层树的深度：树中各结点的层的最大值。的最大值。图中的树的深度：图中的树的深度：4兄弟和堂兄弟：同一双亲的兄弟和堂兄弟：同一双亲的结点互称为兄弟，其双亲在结点互称为兄弟，其双亲在同一层但不属于同一双亲的同一层但不属于同一双亲的结点互称为堂兄弟。结点互称为堂兄弟。结点结点E,F,G是兄弟，是兄弟，G,H,I是是堂兄弟堂兄弟

42、祖先和子孙：一个结点的祖祖先和子孙：一个结点的祖先是指从该结点到树根所经先是指从该结点到树根所经分支上的所有结点。一个结分支上的所有结点。一个结点的子树上的所有结点称为点的子树上的所有结点称为该结点的子孙。该结点的子孙。E的祖先有的祖先有A和和B，而，而E、F、G、K、L是是B的子孙。的子孙。有序树和无序树：如果树中有序树和无序树：如果树中任一结点的各颗子树规定从任一结点的各颗子树规定从左至右是有序的，即不能互左至右是有序的，即不能互换位置，则称该树为有序树，换位置，则称该树为有序树，否则称为无序树。否则称为无序树。森林：森林：n（n0）棵互不相交）棵互不相交的树的集合称为森林。删去的树的集合

43、称为森林。删去一棵树的根结点便得到一个一棵树的根结点便得到一个森林；反过来，给一个森林森林；反过来，给一个森林加上一个结点，使原森林的加上一个结点，使原森林的各棵树成为所加结点的子树，各棵树成为所加结点的子树，便得到一棵树。便得到一棵树。第54页，本讲稿共79页二叉树是树形结构的一个重要类型。许多实际问题抽象二叉树是树形结构的一个重要类型。许多实际问题抽象出来的数据结构往往是二叉树的形式，即使是一般的树也出来的数据结构往往是二叉树的形式，即使是一般的树也能简单地转换为二叉树，而且二叉树的存储结构及其算法能简单地转换为二叉树，而且二叉树的存储结构及其算法都较为简单，因此二叉树显得特别重要。都较为

44、简单，因此二叉树显得特别重要。二叉树的定义二叉树的定义n定义：二叉树是定义：二叉树是n(n0)n(n0)个结点的有限集，它或者是空个结点的有限集，它或者是空集集(n=0)(n=0)，或者由一个根结点及两棵互不相交的、分别，或者由一个根结点及两棵互不相交的、分别称作这个根的左子树和右子树的二叉树组成。称作这个根的左子树和右子树的二叉树组成。第55页，本讲稿共79页NLR空树空树空树空树只含根结点只含根结点只含根结点只含根结点NNN右子树为空树右子树为空树右子树为空树右子树为空树左子树为空树左子树为空树左子树为空树左子树为空树左右子树均不为空树左右子树均不为空树左右子树均不为空树左右子树均不为空树

45、二叉树的五种基本形态：二叉树的五种基本形态：LR第56页，本讲稿共79页二叉树的基本性质二叉树的基本性质n性质性质1 1 在二叉树的第在二叉树的第i i层至多有层至多有2 2i-1i-1个结点个结点(i1)(i1)n性质性质2 2 深度为深度为k(k1)k(k1)的二叉树至多有的二叉树至多有2 2k k-1-1个结点个结点n性质性质3 3 对任何一棵二叉树对任何一棵二叉树T T，如果其叶子结点数为，如果其叶子结点数为n n0 0,度度为为2 2的结点数为的结点数为n n2 2，则，则n n0 0=n=n2 2+1+1第57页，本讲稿共79页123456789101112131415abcdef

46、ghij两类两类特殊特殊的二叉树：的二叉树：满二叉树：满二叉树：指的是深度指的是深度为为k k且含有且含有2 2k k-1-1个结点个结点的二叉树。的二叉树。完全二叉树完全二叉树：树中所含的树中所含的 n n 个结点和满二叉树中个结点和满二叉树中编号为编号为 1 1 至至 n n 的结点的结点一一对应。一一对应。第58页，本讲稿共79页n性质性质4 4 具有具有n(n1)n(n1)个结点的完全二叉树的深度为个结点的完全二叉树的深度为loglog2 2n+1(n+1(其中其中loglog2 2nn表示取表示取loglog2 2n n的整数部分的整数部分)n性质性质5 5 如果对一棵有如果对一棵有

47、n n个结点的完全二叉树的结点按顺序编个结点的完全二叉树的结点按顺序编号，则对任一结点号，则对任一结点i(1in),i(1in),有：有：（1 1）如果）如果i=1,i=1,则结点则结点i i是二叉树的根，无双亲；如果是二叉树的根，无双亲；如果i1i1，则，则其双亲是其双亲是i/2i/2（2 2）如果）如果2i2in n，则结点，则结点i i无左孩子；否则其左孩子是结点无左孩子；否则其左孩子是结点2i2i（3 3）如果）如果2i+12i+1n n，则结点，则结点i i无右孩子；否则其右孩子是结点无右孩子；否则其右孩子是结点2i+12i+1第59页，本讲稿共79页二叉树的存储结构二叉树的存储结构

48、n完全二叉树顺序存储完全二叉树顺序存储将完全二叉树中所有结点按编号顺将完全二叉树中所有结点按编号顺序依次存储在一个地址连续的存序依次存储在一个地址连续的存储单元中。储单元中。n一般二叉树的顺序存储一般二叉树的顺序存储 将一般二叉树添上一些将一般二叉树添上一些 虚结虚结点点，成为，成为 完全二叉树完全二叉树 将各结点按编号顺序依次存储在将各结点按编号顺序依次存储在一个地址连续的存储单元中，其一个地址连续的存储单元中，其中中 虚结点虚结点 用用 表示表示完全二叉完全二叉树树的的顺顺序存序存储结储结构构非完全二叉非完全二叉树树的的顺顺序存序存储结储结构构第60页，本讲稿共79页二叉树的顺序存储结构的

49、优缺点二叉树的顺序存储结构的优缺点 对完全二叉树而言，顺序存储结构既简单又对完全二叉树而言，顺序存储结构既简单又节省存储空间。节省存储空间。一般的二叉树采用顺序存储结构时，虽然简一般的二叉树采用顺序存储结构时，虽然简单，但易造成存储空间的浪费。最坏的情况下，单，但易造成存储空间的浪费。最坏的情况下，一个深度为一个深度为k k且只有且只有k k个结点的右单支树需要个结点的右单支树需要2 2k k-1-1个结点的存储空间个结点的存储空间,空间利用率仅为空间利用率仅为k/(2k/(2k k-1)-1)。在对顺序存储的二叉树做插入和删除结点操作在对顺序存储的二叉树做插入和删除结点操作时，要大量移动结点

50、。时，要大量移动结点。第61页，本讲稿共79页1.1.二叉树链式存储结构二叉树链式存储结构用链接方式存储二叉树时，用链接方式存储二叉树时，每个结点除了存储结点本每个结点除了存储结点本身的数据外，还应设置两身的数据外，还应设置两个指针域个指针域lchildlchild和和rchildrchild，分别指向该结点的左孩，分别指向该结点的左孩子和右孩子。子和右孩子。例：二叉树的二叉链表：例：二叉树的二叉链表：二叉二叉链链表表结结点的点的结结构构第62页，本讲稿共79页二叉树的遍历二叉树的遍历 “遍历遍历”是任何类型均有的操作。是任何类型均有的操作。对线性结构而言，只有一条搜索路径对线性结构而言，只有