《数据结构与算法分析》全册配套课件4

《数据结构与算法分析》全册配套课件42DataStructuresandAlgorithmsAnalysis数据结构与算法分析3

第一章绪论

1.1

引言

1.2数据结构的有关基本概念；

1.3算法及算法分析（算法评价）

4数据结构的发展概况和地位《数据结构》作为一门独立的课程在国外是从1968年才开始的。《数据结构》是计算机科学中一门综合性的专业基础课。5程序=算法+数据结构程序是对所要解决问题的各个对象和处理规则的描述，或者说是数据结构和算法的描述（NiklausWirth1984）6课程地位计算机科学与技术专业本科生的专业基础课程之一计算机专业本科生必修的学位课程计算机专业研究生入学考试必考科目计算机软件技术资格和水平考试内容全国计算机等级考试（三级、四级）内容7课程地位（续）为操作系统、数据库系统、编译原理、计算机网络等后续课程提供了必要的知识基础为提高程序设计能力、逻辑思维能力和分析问题、解决问题的能力提供了必要的技能训练8本课程研究的问题数据：数据是信息的载体，是描述客观事物的数、字符、以及所有能输入到计算机中，被计算机程序识别和处理的符号的集合。数值性数据非数值性数据数值问题—对以数学方式表示的问题求数值解。例如，代数方程计算、矩阵计算、线性方程组求解、数值积分、微分方程求解等；非数值问题—求非数值解。例如，排序查找、模式匹配等。数据结构的研究问题：非数值数据之间的结构关系，及如何表示，如何存储，如何处理9

数值问题与非数值问题1）数值问题例1已知：游泳池的长len和宽wide，求面积area◆设计求解问题的方法◆编程main(){ intlen,wide,area;

scanf(“%d%d%\n”,&l,&w);

area=len*wide;

printf(“area=%d”,area);}◆

建模型：

问题涉及的对象：游泳池的长len宽wide，面积area；

对象之间的关系：area=lenwide10例3多叉路口交通灯管理问题CEDABABACADBABCBDDADBDCEAEBECED图11学习数据结构的必要性数据结构是指数据的组织 更有效的程序计算机功能越强大尝试更复杂的问题（应用）更复杂的问题需要更大的计算量工作越复杂就越偏离人们的日常经验12数据的组织对于任意组织的一组数据项能够查找出指定的数据项，将这些数据项处理成任何期望得到的顺序，或者更改任何特定数据项的值。同一个程序，选择不同的数据结构和算法可能会产生很大的差异，有的可能在几秒钟就运行完毕，也有可能需要几天时间才能完成。13效率Efficiency一种解决方案如果能在所要求的资源限制（resourceconstraints）内将问题解决好，则称该算法是有效率的（efficient）空间Space时间Time一种算法的代价（cost）是指这种算法消耗的资源量14数据结构的选择选择数据结构的步骤：分析问题，以确定解决方案会遇到的资源限制确定必须支持的基本操作，并度量每种操作的资源限制选择最适合这些需求的数据结构15考虑的问题开始时是将所有数据都插入数据结构，还是与其它操作混合在一起插入?数据是否要删除?所有数据是按一些定义明确的顺序来处理，还是允许随机访问?16数据结构的原则每个数据结构都将代价与效益联系在一起很少有一个数据结构在所有情况下都比其它算法好一个数据结构需要：一定的空间存储它的每一个数据项，一定的时间来执行单个基本操作，一定的程序设计工作。17数据结构的原则(cont)每一个问题都有可利用空间和时间的约束只有对问题的特性进行仔细分析之后，才能得到执行这项任务最好的数据结构。一个银行业务的例子：新开帐户：花费几分钟交易：几秒钟注销帐户：整夜18课程的目的加强一个概念：每一个数据结构都有其相关的代价和效益学会常用的数据结构这些数据结构形成了一个程序员的基本数据结构工具箱了解如何评价一个数据结构或算法的代价（cost）这些技术也使得程序员能够判断自己或别人发明的新数据结构的价值。19教学目的学会分析研究计算机加工的数据结构的特性，以便为应用涉及的数据选择适当的逻辑结构、存储结构及相应的算法，并初步掌握算法的时间分析和空间分析技术本课程的学习过程也是复杂程序设计的训练过程，要求学生编写的程序结构清楚和正确易读，符合软件工程的规范。为今后的程序设计作一些铺垫20

第一章绪论

1.1

引言

1.2数据结构的有关基本概念

1.3算法及算法分析（算法评价）

21术语类型（type）是一组值的集合数据项（dataitemorelement）是一条信息或者一个记录数据类型（datatype）是指一种类型和定义在该类型上的一组操作数据项又称为数据类型的成员简单数据项不包含子结构复杂数据项可能包含多项信息22抽象数据类型抽象数据类型（ADT）：根据一组值的集合定义的数据类型和该数据类型上的一组操作集每个ADT操作由它的输入和输出定义。封装：隐藏实现细节23数据结构数据结构是ADT的实际实现与ADT联系在一起的每个操作由一个或多个子程序来实现数据结构通常涉及数据在内存中的组织方式文件结构是指在外存储器（如磁盘驱动器）上数据的组织24抽象化ADT：复杂问题的抽象化：隐喻标志的层次化Ex:晶体管门电路CPU.ADT在程序中通过特定的数据结构实现，然而在设计使用ADT的那部分程序时，我们只关心数据类型上的操作，而不关心数据结构的实现25逻辑vs.物理形式数据项有逻辑形式和物理形式。逻辑形式：用ADT来给出数据项的定义Ex:数学意义上的integers：+,-物理形式：数据结构中对数据项的实现。Ex:16/32bitintegers,overflow.26数据类型ADT:类型操作数据项:

逻辑形式数据项:

物理形式数据结构:存储空间子程序27问题问题：一个需要完成的工作。即一组输入就有一组相应的输出。问题的定义将包含对任何可行方案所需资源的限制。问题数学的函数函数是输入（domain

）和输出（range）之间的一种映射关系。函数的输入可以是一个值，或者是一个信息的集合。这些值组成的输入称为函数的参数。每一个特定的输入，每次函数计算得到的输出就必然相同。28算法与程序算法：解决问题的一种方法或者一个过程。如果将问题看做函数，那么算法就是把输入转换为输出一个输入到输出的映射一个问题可以用多种算法来解决29计算机软件计算机软件是与计算机系统操作有关的程序、规程、规则及任何与之有关的文档及数据。它由两部分组成：一是机器可执行的程序及有关数据；二是机器不可执行的，与软件开发、运行、维护、使用和培训有关的文档。30小结有效性代价与效益数据结构的定义程序＝算法＋数据结构31第一章绪论

1.1引言

1.2算法及算法分析（算法评价）

32什么是算法？算法是对解决问题的方法的一种精确描述。并非所有问题都有算法，有些问题经研究可行，则可能有相应算法；而有些问题经研究不可行，则没有相应算法。因此，算法研究在某种意义上就是可行性研究。33算法的性质算法可以理解为动作序列的有限集合仅有一个初始动作每个动作的后继动作是确定的算法的终止表示问题得到解答或问题没有解答34算法是为了解决某类问题而规定的一个有限长的操作序列。一个算法必须满足以下五个重要特性：1．有穷性

2．确定性3．可行性4．有输入5．有输出算法的性质351．有穷性对于任意一组合法输入值，在执行有穷步骤之后一定能结束，即：算法中的每个步骤都能在有限时间内完成。

2．确定性

对于每种情况下所应执行的操作，在算法中都有确切的规定，使算法的执行者或阅读者都能明确其含义及如何执行。并且在任何条件下，算法都只有一条执行路径。363．可行性算法中的所有操作都必须足够基本，都可以通过已经实现的基本操作运算有限次实现之。4．有输入作为算法加工对象的量值，通常体现为算法中的一组变量。有些输入量需要在算法执行过程中输入，而有的算法表面上可以没有输入，实际上已被嵌入算法之中。37

5．有输出它是一组与“输入”有确定关系的量值，是算法进行信息加工后得到的结果，这种确定关系即为算法的功能。38算法设计的原则设计算法时，通常应考虑达到以下目标：1．正确性2.可读性3．健壮性4．高效率与低存储量需求391．正确性

首先，算法应当满足以特定的“规格说明”方式给出的需求。

其次，对算法是否“正确”的理解可以有以下四个层次：a．程序中不含语法错误；b．程序对于几组输入数据能够得出满足要求的结果；40

c．程序对于精心选择的、典型、苛刻且带有刁难性的几组输入数据能够得出满足要求的结果；通常以第

c层意义的正确性作为衡量一个算法是否合格的标准。

d．程序对于一切合法的输入数据都能得出满足要求的结果；412.可读性

算法主要是为了人的阅读与交流，其次才是为计算机执行，因此算法应该易于人的理解；另一方面，晦涩难读的程序易于隐藏较多错误而难以调试。423．健壮性

当输入的数据非法时，算法应当恰当地作出反映或进行相应处理，而不是产生莫名奇妙的输出结果。并且，处理出错的方法不应是中断程序的执行，而应是返回一个表示错误或错误性质的值，以便在更高的抽象层次上进行处理。434．高效率与低存储量需求

通常，效率指的是算法执行时间；存储量指的是算法执行过程中所需的最大存储空间，两者都与问题的规模有关。44第一章绪论

1.1引言

1.2算法及算法分析（算法评价）

45算法分析与算法复杂度算法分析的任务是对设计出的每一个具体的算法，利用数学工具，讨论其复杂度，探讨具体算法对问题的适应性算法的复杂度分时间复杂度和空间复杂度。计算机理论科学中，按照计算复杂性研究问题求解的难易性，可把问题分为P类、NP类和NP-完全类。46算法的效率对于一个问题通常有多种解法（算法），应该选择哪一种呢？计算机程序设计的核心有两个目标（有时它们互相冲突）设计一种容易理解、编码和调试的算法设计一种能有效利用计算机资源的算法47算法的效率(cont)目标1涉及到软件工程原理目标2涉及到数据结构与算法分析本课程主要讲的是与目标2有关的问题怎样度量算法的代价、效率呢？48如何度量效率?实验比较（运行程序）渐近算法分析AsymptoticAlgorithmAnalysis关键资源:影响运行时间的因素:对很多算法而言，运行时间依赖与输入的规模执行算法所需要的时间T写成输入规模n的函数，记为T(n)49怎样比较两种算法解决问题的效率呢？实验比较用源程序分别实现这两种算法，然后输入适当的数据运行，测算两个程序各自的开销这是一种事后统计的方法渐近算法分析(asymptoticalgorithmanalysis)，简称算法分析(algorithmanalysis)可以估算出当问题规模变大时，一种算法及实现它的程序的效率和开销这是一种事前分析估算的方法50“规模”与“基本操作”判断算法性能的一个基本考虑是处理一定“规模”(size)的输入时该算法所需执行的“基本操作”(basicoperation)数“规模”一般是指输入量的数目比如，在排序问题中，问题的规模可以用被排序元素的个数来衡量51“规模”与“基本操作”（续）一个“基本操作”必须具有这样的性质：完成该操作所需时间与操作数的具体取值无关在大多数高级语言中，下列操作是基本操作：赋值运算简单算术运算简单布尔运算简单I／O操作函数返回n个整数累加不是基本操作因为其代价依赖于n的值(即大小)52运行时间和增长率由于影响运行时间的最主要因素一般是输入的规模，所以经常把执行算法所需要的时间T写成输入规模n的函数，记为T(n)我们总是假设T(n)为非负值算法的增长率(growthrate)是指当输入规模增长时，算法代价的增长速率53最佳、最差和平均情况不是相同规模的所有输入的运行时间都相同顺序搜索法（Sequentialsearch）从一个n元一维数组中找出一个给定的值K:从第一个元素开始，依次检索每一个元素，直到找到K为止最佳情况:最差情况:平均情况:54请用通俗的例子谈谈 对增长率和平均情况

两个概念的理解请邮件告诉我（lixhong@263.net）55GrowthRateGraph565.1.1时间复杂性（续）

更快的计算机，还是更快的算法?57时间复杂度对解题速度的影响O(n)解题速度n=10n=30n=60n0.01ms0.03ms0.06msn20.1ms0.9ms3.6msn50.1s24.3s13.0min2n1.0ms17.9min366.0世纪3n0.059s6.5年1.3×1013世纪58阿达尔定律设f为求解某个问题的计算存在的必须串行执行的操作占整个计算的百分比，p处理机的数目，Sp

为并行计算机系统最大的加速能力（单位：倍），则设f=1%，p，则Sp=100。串行计算与并行计算59算法分析的任务是对设计出的每一个具体的算法，利用数学工具，讨论其复杂度，探讨具体算法对问题的适应性算法的时间复杂度规模基本操作增长率平均情况效率请把下列的术语融入到上句中，对算法分析的任务进行更加清晰的说明60渐近分析:大O定义:对于非负函数T(n)，若存在两个正常数c和n0，使得当n>n0时有T(n)≤cf(n)，则称T(n)在集合O(f(n))中。用法:这个算法[最佳、平均、最差]情况（下的增长率的上限）在O(n2)中.含意:对于问题的所有[最佳、平均、最差情况]输入，只要输入规模足够大(即

n>n0),该算法总能在cf(n)步以内完成.61上限:大O

(cont)增长率的上限用符号O表示，称为大O表示法(big-Ohnotation).Example:IfT(n)=3n2thenT(n)isinO(n2).希望最“紧”（即最小）的上限:虽然T(n)=3n2

可以说它在O(n3)中,我们更喜欢用O(n2).62上限的例子例1:考虑找出整数数组中某个元素的顺序检索法(averagecost).如果访问并检查数组中的一个元素需要时间cs(cs为常数)，那么在平均情况下T(n)=csn/2。当n>1时，csn/2<=csn，所以根据定义，T(n)在O(n)中，n0=1，c=cs63上限的例子例2:某一算法平均情况下

T(n)=c1n2+c2n.c1、c2为正数。当n>1，c1n2+c2n<=c1n2+c2n2<=(c1+c2)n2.因此取c=c1+c2andn0=1，有T(n)<=cn2.所以根据定义,T(n)在isinO(n2)中.例子3:T(n)=c.我们说它在O(1)中.64Big-Omega定义:对于非负函数T(n)，若存在两个正常数c和andn0

，使得当n>n0时有T(n)>=cg(n)，则称T(n)在集合(g(n))中意义:对于问题的所有[最佳、平均、最差情况]输入，只要输入规模足够大(即

n>n0),该算法的完成至少需要cf(n)步.下限.65Big-OmegaExample例1：假定T(n)=c1n2+c2n.(c1，c2>0)则有

c1n2+c2n>=c1n2foralln>1.因此，取c=c1，n0=1，有T(n)>=cn2.所以,根据定义,

T(n)在(n2)中也可以说T(n)在(n)中我们希望找到一个最“紧”的可能限制.（最大下限）66ThetaNotation上限和下限描述了算法运行时间的范围当上、下限相等时，可以用表示法定义:如果非负函数T(n)既在O(h(n))中，又在(h(n))中，则称算法T(n)是(h(n))。这时也说T(n)与h(n)同阶67ACommonMisunderstanding“算法最佳情况是输入规模为1时，因为这时运行最快”。错误！大O指的是当n趋近于时的增长率最佳情况指的是在规模为n的所有输入中哪个输入运行最快。68ACommonMisunderstanding混淆了最差情况和上限上限指的是增长率最差情况指的是给定规模的所有可能输入中最差的输入，消耗（运行）的时间最大69SimplifyingRulesIff(n)isinO(g(n))andg(n)isinO(h(n)),thenf(n)isinO(h(n)).Iff(n)isinO(kg(n))foranyconstantk>0,thenf(n)isinO(g(n)).Iff1(n)isinO(g1(n))andf2(n)isinO(g2(n)),then(f1+f2)(n)isinO(max(g1(n),g2(n))).Iff1(n)isinO(g1(n))andf2(n)isinO(g2(n))thenf1(n)f2(n)isinO(g1(n)g2(n)).70程序运行时间的计算(1)Example1:a=b;Thisassignmenttakesconstanttime,soitis(1).Example2:sum=0;for(i=1;i<=n;i++)sum+=n;时间代价为(1)时间代价为71程序运行时间的计算(2)Example3:sum=0;for(i=1;i<=n;i++)for(j=1;j<=i;j++)sum++;for(k=0;k<n;k++)A[k]=k;时间代价为常量c1时间代价为c2n时间代价为72程序运行时间的计算(3)Example4:sum1=0;for(i=1;i<=n;i++)for(j=1;j<=n;j++)sum1++;sum2=0;for(i=1;i<=n;i++)for(j=1;j<=i;j++)sum2++;时间代价为(n2)时间代价为(n2)73程序运行时间的计算(4)Example5:sum1=0;for(k=1;k<=n;k*=2)for(j=1;j<=n;j++)sum1++;sum2=0;for(k=1;k<=n;k*=2)for(j=1;j<=k;j++)sum2++;第一段程序的时间代价为(nlogn)第二段程序的时间代价为(n)外层for循环当i=1,2,22,

…,

2k=n时执行,总共执行1+k次，因为k=logn,所以总共执行1+logn次。又内层循环执行次数恒为n，所以第一段程序的总时间代价可表示为n(1+logn),即Θ(nlogn)外层for循环当i=1,2,22,

…,

2k=n时执行,而内层循环执行k次，所以第二段程序的总时间代价可表示为1+2+22+

…+

2k=,由公式2.9可知，其和为2k+1-1,因为k=logn,所以总时间代价为2n-1,即Θ(n)74其他控制语句while循环、do-while循环分析方法与for循环类似if语句最差情况时间代价是then和else部分中时间代价较大的那一个对于平均情况代价也是如此假设n的取值与执行哪一条指令的概率无关switch语句最差情况时间代价是所有分支中开销最大的一个子程序调用加上执行子程序的时间75问题的分析问题代价的上限：已知最优算法的代价上限问题代价的下限：所有可能算法的代价下限（包括尚未设计出来的算法）76多参数问题ComputetherankorderingforallCpixelvaluesinapictureofPpixels.for(i=0;i<C;i++)//Initializecountcount[i]=0;for(i=0;i<P;i++)//Lookatallpixelscount[value(i)]++;//Incrementcountsort(count);//SortpixelcountsIfweusePasthemeasure,thentimeis(PlogP).Moreaccurateis(P+ClogC).77空间代价与分析时间代价类似渐近分析中增长率的概念对于空间代价同样适用时间代价是相对于处理某个数据结构的算法而言的空间代价是相对于该数据结构本身而言的78空间/时间权衡原则

(space/timetradeoffprinciple)以时间换空间信息压缩存储以空间换时间查找表基于磁盘的空间/时间权衡原则在磁盘上的存储代价越小，程序运行得越快79小结算法分析的动机、基本符号和基本技术增长率的概念增长率的上限和下限的概念能够区分一种算法的代价和一个问题的代价80第一部分小结数据结构和算法效率代价和效益数据结构的定义；ADT算法分析动机：增长率基本符号：O、、81什么情况下，可以直接用

表示算法的复杂度？即什么情况下，算法的下限和上限相等。

请邮件告诉我（lixhong@263.net）82习题讲解写出下列程序段平均情况下时间代价的表示式。假设所有变量类型都为int：a=b+c; d=a+e;(b)sum=0; for(i=0;i<3;i++) for(j=0;j<n;j++) sum++;(c)sum=0; for(i=0;i<n*n;i++) sum++;时间代价为(1)时间代价为(n)时间代价为(n2)83(d)假设数组A中含有n个元素，函数Random花的时间是常数值，sort需要执行nlogn步。for(i=0;i<n;i++){ for(j=0;j<n;j++) A[i]=Random(n); sort(A,n);}(e)假设数组A中元素为从0到n－1的任意一个排列。sum3=0;for(i=0;i<n;i++) for(j=0;A[j]!=i;j++) sum3++;时间代价为(n2logn)时间代价为=(n2)84(f)sum=0;if(EVEN(n))

for(i=0;i<n;i++) sum++;else sum=sum+n;

时间代价为(n)85课堂练习1.Theprimarypurposeofmostcomputerprogramsisa)toperformamathematicalcalculation.b)tostoreandretrieveinformation.c)tosortacollectionofrecords.d)alloftheabove.e)noneoftheabove.2.AnalgorithmmustbeordoallofthefollowingEXCEPT:a)correctb)composedofconcretestepsc)ambiguousd)composedofafinitenumberofstepse)terminate863.Asymptoticanalysisrefersto:a)Thecostofanalgorithminitsbest,worst,oraveragecase.b)Thegrowthincostofanalgorithmastheinputsizegrowstowardsinfinity.c)Thesizeofadatastructure.d)Thecostofanalgorithmforsmallinputsizes4.Pickthegrowthratethatcorrespondstothemostefficientalgorithmasngetslarge:a)5nb)20lognc)2n^2d)2^n87树数据结构与算法88引言

前述我们所研究的数据结构线性表是线性结构。本章将研究的树型结构是一种动态的，非线性的，可描述结构层次特性的数据结构。这种结构是按分枝关系把信息联系起来的数据组织形式。在日常生活中这种结构是不少见的，如：89家谱图(谱系图)ChangChang父祖父祖母Chang母外祖父外祖母90行政机构图中央人民政府湖南省湖北省……上海市长沙………全省各地市………各市、县、区91UNIX文件目录92XML文件结构93树型的网络拓扑结构94编译程序中使用语法树95树型结构小节客观世界中广泛存在树结构树结构也在计算科学领域中被广泛的（创造和）应用以上各例的数据(信息)组织形式，均称为树型结构。当然它与植物树有所不同，(它的根在上，枝在下)96树的定义和基本术语97树的定义一棵树(tree)T是由一个或一个以上结点组成的有限集其中有一个特定的结点R称为T的根结点。集合(T－{R})中的其余结点可被划分为n≥0个互不相交的子集T1，T2，…,Tn，其中每个子集本身又是一棵树，并且其相应的根结点R1，R2，…,Rn是R的子结点子集Ti(1≤i≤n)称为树T的子树(subtree)。子树可如下排序：Ti排在Tj之前，当且仅当i<j为方便起见,子树从左到右排列,其中T1被称为R的最左子树,R1被称为R的最左子结点98ABCDEFGHIJMKLA(B(E,F(K,L)),

C(G),

D(H,I,J(M))

)T1T3T2树根例如:99结点:结点的度:树的度:叶子结点:分支结点:数据元素+若干指向子树的分支分支的个数树中所有结点的度的最大值度为零的结点度大于零的结点DHIJM100(从根到结点的)路径：孩子结点、双亲结点兄弟结点、堂兄弟祖先结点、子孙结点结点的层次:树的深度：由从根到该结点所经分支和结点构成ABCDEFGHIJMKL假设根结点的层次为1，第l层的结点的子树根结点的层次为l+1树中叶子结点所在的最大层次101任何一棵非空树是一个二元组

Tree=（root，F）其中：root被称为根结点

F被称为子树森林森林：是m（m≥0）棵互不相交的树的集合ArootBCDEFGHIJMKLF102对比树型结构和线性结构的结构特点103~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~线性结构树型结构第一个数据元素

(无前驱)

根结点

(无前驱)最后一个数据元素

(无后继)多个叶子结点

(无后继)其它数据元素(一个前驱、一个后继)其它数据元素(一个前驱、多个后继)104树的ADT105数据对象D：D是具有相同特性的数据元素的集合。

若D为空集，则称为空树。否则:(1)在D中存在唯一的称为根的数据元素root；

(2)当n>1时，其余结点可分为m(m>0)个互不相交的有限集T1,T2,…,Tm，其中每一棵子集本身又是一棵符合本定义的树，称为根root的子树。

数据关系R：106

基本操作：查找类

插入类删除类107

Root(T)//求树的根结点

查找类：Value(T,cur_e)//求当前结点的元素值

Parent(T,cur_e)//求当前结点的双亲结点LeftChild(T,cur_e)//求当前结点的最左孩子RightSibling(T,cur_e)//求当前结点的右兄弟TreeEmpty(T)//判定树是否为空树TreeDepth(T)//求树的深度TraverseTree(T,Visit())//遍历108InitTree(&T)//初始化置空树

插入类：CreateTree(&T,definition)//按定义构造树Assign(T,cur_e,value)//给当前结点赋值InsertChild(&T,&p,i,c)//将以c为根的树插入为结点p的第i棵子树109

ClearTree(&T)//将树清空

删除类：DestroyTree(&T)//销毁树的结构DeleteChild(&T,&p,i)//删除结点p的第i棵子树110树结点的ADT//GeneraltreenodeADTtemplate<classElem>classGTNode{public:GTNode(constElem&);//Constructor~GTNode();//DestructorElemvalue();//ReturnvalueboolisLeaf();//TRUEifisaleafGTNode*parent();//Returnparent

GTNode*leftmost_child();//FirstchildGTNode*right_sibling();//RightsiblingvoidsetValue(Elem&);//Setvalue

voidinsert_first(GTNode<Elem>*n);voidinsert_next(GTNode<Elem>*n);

voidremove_first();//Removefirstchildvoidremove_next();//Removesibling};111树的ADT//GeneraltreenodeADTtemplate<classElem>classGenTree{private：voidprinthelp(GTNode*);//printhelperfunctionpublic:GenTree();//constructor~GenTree();//Destructorvoidclear();//SendnodestofreestoreGTNode*root();//Returntheroot//CombinetwosubtreeVoidnewroot(Elem&,GTNode<Elem>*,GTNode<Elem>*);Voidprint();//Printatree};112二叉树的定义和性质113二叉树BinaryTrees二叉树(binarytree)是结点(node)的有限集合，这个集合或者为空(empty)，或者由一个根结点(root)以及两棵二叉树组成,这两棵二叉树分别称作这个根的左子树(leftsubtree)和右子树(rightsubtree),这两棵二叉树分别与根结点相连且彼此不相交.

114115二叉树的五种基本形态N空树只含根结点NNNLRR右子树为空树L左子树为空树左右子树均不为空树116二叉树的特性(性质1)特性一：在二叉树中，第i层上的结点数最多为2i1(i≥1);证明(归纳法)：当i=1时，只有一个结点，2i1=20=1(归纳基础)归纳假设：假定对所有的j,1≤j<i

命题成立，即第j层上结点总数最多为2j1个结点。那么，可以证明j=i时命题成立。117归纳步骤：由归纳假设可知，i1层上的结点总数最多为2i2。由于二叉树每个结点的度最大为2，所以第i层上的结点最大数为第i1层上结点最大数的2倍，即22i2，从而得证，i层上最大结点数为2i1.118特性二：深度为k的二叉树至多有2k1个结点.(k≥1)证明：深度为k的二叉树结点最大数为每一层结点最大数之和。由特性一得：二叉树的特性(性质2)119特性三：对任一棵二叉树，若叶结点数为n0,度为2的结点数为n2，则有n0=n2+1成立证明：设度为1的结点数为n1，则二叉树的结点总数为：n=n0+n1+n2

…………(1)二叉树的特性(性质3)120设二叉树的分支总数为B，除根结点外，每一个结点都有一个分支进入，则B=n1又因为度为1的结点发出一个分支，度为2的结点发出2个分支所以：B=n1+2n2从而得n=n1+2n2+1…………(2)由(1),(2)式得n0=n2+1成立.121FullandCompleteBinaryTrees满二叉树(fullbinarytree)的每一个结点或者是一个分支结点，并恰有两个非空子结点；或者是叶结点.完全二叉树(completebinarytree)从根结点起每一层的结点从左到右连续填充,除了最下面一层以外其余各层都是满的,并且最下面一层的结点都集中在该层的最左边.122特性四：具有n个结点的完全二叉树，其深度为：

k=log2n+1证：根据性质2和完全二叉树的定义，设完全二叉树的深度为k，则2k11

<n≤2k1深度为k1的完全二叉树的最大结点数深度为k的完全二叉树的最大结点数即2k1≤

n<2k于是有k1≤log2n<kk为整数k=log2n

+1得证完全二叉树的特性(性质4)123特性五：如果对一棵有n个结点的完全二叉树(其深度为log2n+1)的结点按层次自上而下，从左至右编号，则对任一编号为i的结点(1≤i≤n)有2)若2i≤n

则结点i的左孩子是编号为2i的结点;否则结点i无左孩子（结点i为叶子结点）。1)若i=1,则该结点为根结点，无双亲，若i1,则结点i的双亲是编号为i/2

的结点。记为parent(i)=i/2

完全二叉树的特性(性质5)3)若2i+1≤n

则结点i的右孩子是结点2i+1;否则结点i无右孩子。12448925106371结点3×2＋1<10,所以结点3的左孩子序号为3*2=6，右孩子结点序号为3×2＋1＝7。结点10的双亲结点序号为10/2＝5例子125满二叉树定理Theorem:非空满二叉树的叶结点数等于其分支结点数加1.126满二叉树定理证明1Theorem:非空满二叉树的叶结点数等于其分支结点数加1.证明(byMathematicalInduction数学归纳法):初始情况:没有分支结点的非空二叉树有一个叶结点。有一个分支结点的满二叉树有两个叶结点，即当n=0及n=1时定理成立.归纳假设:设任意一棵有n-1个分支结点的满二叉树T有n个叶结点.127满二叉树定理证明1(续)归纳步骤:假设树T有n个分支结点，取一个左右子结点均为叶结点的分支结点I。去掉I的两个子结点，则I成为叶结点，把新树记为T'，T'有n-1个分支结点.根据归纳假设，T‘有n个叶结点的满二叉树.现在把两个叶结点归还给I,我们又得到树T,它有n个分支结点。但原先的叶结点I现在变成了分支结点，所以叶结点只增加了一个,于是，树T有n个分支结点和n+1个叶结点.因此，根据归纳原理，定理对任意的n≥0成立。128满二叉树定理证明2Theorem:非空满二叉树的叶结点数等于其分支结点数加1.证明2:设分支结点数为n,根据满二叉树的定义,每一个分支结点都有两个非空子结点,所以共有2n个非空子结点,加上根结点,该二叉树总共有2n+1个结点,除去n个分支结点,剩下n+1个叶结点129满二叉树定理的推论Theorem:一棵非空二叉树空子树的数目等于其结点数目加1.Proof:Replaceallnullpointerswithapointertoanemptyleafnode.Thisisafullbinarytree.130满二叉树定理的推论的证明1证明1：设二叉树T，将其所有空子树换成叶结点，把新的二叉树记为T‘。所有原来树T的结点现在是树T’的分支结点。由于树T中的分支结点要么有两个非空子结点,要么有一个非空子结点和一个空子树,而这个空子树在T‘中已换成了非空子结点;并且树T中的每个叶结点都有两个空子树,在树T’中都换成了两个非空子结点,所以树T‘中的每个分支结点都有两个非空子结点,所以树T’是满二叉树。根据满二叉树定理，新添加的叶结点数目等于树T的结点数目加1，而每个新添加的叶结点对应树T的一棵空子树，因此树T中空子树的数目等于树T中结点数目加1。131满二叉树定理的推论的证明2Theorem:一棵非空二叉树空子树的数目等于其结点数目加1.证明2：假设树T有n个结点,其中有一个是根结点，其余n-1个都是非空子结点。如果把空子树也算作子结点的话，那么每个结点都有两个子结点,n个结点就有2n个子结点。既然非空子结点数目为n-1，所以必有有n+1个子结点为空。132二叉树的ADT133数据对象D：D是具有相同特性的数据元素的集合。

若D为空集，则称为空树。否则:(1)在D中存在唯一的称为根的数据元素root；

(2)当n>1时，其余结点可分为不相交的有限集Tl、Tr，其中每一个子集本身又是一棵符合本定义的二叉树，称为根root的子树。

数据关系R：134二叉树结点的ADT//Binarytreenodeabstractclasstemplate<classElem>classBinNode{public:virtualElem&val()=0;//Returnthenode'selementvirtualvoidsetVal(constElem&)=0;//Setthenode'selementvirtualBinNode*left()const=0;//Returnthenode'sleftchildvirtualvoidsetLeft(BinNode*)=0;//Setthenode'sleftchildvirtualBinNode*right()const=0;//Returnthenode'srightchildvirtualvoidsetRight(BinNode*)=0;//Setthenode'srightchildvirtualboolisLeaf()=0;//Returntrueiffthenodeisaleaf};135BinaryTreeNodeClass(1)//Binarytreenodeclasstemplate<classElem>classBinNodePtr:publicBinNode<Elem>{private:Elemit;//Thenode'svalueBinNodePtr*lc;//PointertoleftchildBinNodePtr*rc;//Pointertorightchildpublic:BinNodePtr(){lc=rc=NULL;}BinNodePtr(Eleme,BinNodePtr*l=NULL,BinNodePtr*r=NULL){it=e;lc=l;rc=r;}

136BinaryTreeNodeClass(2)

Elem&val(){returnit;}voidsetVal(constElem&e){it=e;}inlineBinNode<Elem>*left()const{returnlc;}voidsetLeft(BinNode<Elem>*b){lc=(BinNodePtr*)b;}inlineBinNode<Elem>*right()const{returnrc;}voidsetRight(BinNode<Elem>*b){rc=(BinNodePtr*)b;}boolisLeaf(){return(lc==NULL)&&(rc==NULL);}};137

二叉树的主要基本操作：查找类插入类删除类138

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());139

InitBiTree(&T);Assign(T,&e,value);CreateBiTree(&T,definition);InsertChild(T,p,LR,c);140ClearBiTree(&T);DestroyBiTree(&T);DeleteChild(T,p,LR);要点回顾树型结构是一种动态的，非线性的，可描述结构层次特性的数据结构树ADT的设计，包括树节点ADT和树ADT的设计二叉树的性质是很重要的142课堂练习定义一个结点的度数（degree）为其非空子结点的数目。用归纳法证明任何二叉树中度数为2的结点的数目为叶结点数目减1.请下课时，提交你的练习结果给我，谢谢。并请写好你的学号和姓名。143课后思考你认为二叉树ADT的基本操作中，最基础且重要的操作是什么；在将来利用二叉树来实现程序时，什么操作你认为是首先要搞清楚的。从数据结构的角度，你认为掌握二叉树的性质有什么作用请邮件告诉我（lixhong@263.net）144树的存储结构。

课后预习145检索（查找）数据结构与算法146何谓查找表？查找表是由同一类型的数据元素(或记录)构成的集合。

由于“集合”中的数据元素之间存在着松散的关系，因此查找表是一种应用灵便的结构。147对查找表经常进行的操作1）查询某个“特定的”数据元素是否在查找表中；2）检索某个“特定的”数据元素的各种属性；3）在查找表中插入一个数据元素；4）从查找表中删去某个数据元素。148仅作查询和检索操作的查找表。静态查找表有时在查询之后，还需要将“查询”结果为“不在查找表中”的数据元素插入到查找表中；或者，从查找表中删除其“查询”结果为“在查找表中”的数据元素。动态查找表查找表可分为两类149是数据元素（或记录）中某个数据项的值，用以标识（识别）一个数据元素（或记录）。关键字若此关键字可以识别唯一的一个记录，则称之谓“主关键字”。若此关键字能识别若干记录，则称之谓“次关键字”。150检索的方式精确匹配查询（exact-matchquery）模糊匹配查询（fuzzy-matchquery）范围查询（rangequery）151根据给定的某个值，在查找表中确定一个其关键字等于给定值的数据元素或（记录）。

精确匹配查找若查找表中存在这样一个记录，则称“查找成功”。查找结果给出整个记录的信息，或指示该记录在查找表中的位置；否则称“查找不成功”。查找结果给出“空记录”或“空指针”。152检索的方法1.顺序表和线性表方法(lists,tables,arrays).2.根据关键码值直接访问方法(hashing)3.树索引方法.153

由于查找表中的数据元素之间不存在明显的组织规律，因此不便于查找。为了提高查找的效率，需要在查找表中的元素之间人为地附加某种确定的关系，换句话说，

用另外一种结构来表示查找表。如何进行查找？查找的方法取决于查找表的结构。154查找方法目录基于顺序（线性）结构的查找基于有序顺序（线性）结构的查找155基于线性结构的检索156顺序检索问45是否已经保存？11132050323360459053477123456789101112位置值157ListFindFunction//ReturntrueiffKisinlistboolfind(List<int>&L,intK){intit;for(L.setStart();L.getValue(it); L.next())if(K==it)returntrue;//Founditreturnfalse;//Notfound}Cost：对一个未排序的线性表进行顺序检索，在平均情况和最差情况下需要(n)158顺序检索（2）问保存的值中最大值是多少？11132050323360459053477123456789101112位置值111320505050606090909090159在数组中找最大值//Findlargestvalueintlargest(intarray[],intn){intcurrlarge=0;//Largestvalueseenfor(inti=1;i<n;i++)//Foreachvalif(array[currlarge]<array[i])currlarge=i;//Rememberposreturncurrlarge;//Returnlargest}160

定义：

查找算法的平均查找长度

(AverageSearchLength)

为确定记录在查找表中的位置，需和给定值

进行比较的关键字个数的期望值

其中:n

为表长，Pi

为查找表中第i个记录的概率，且，Ci为找到该记录时，曾和给定 值比较过的关键字的个数。分析顺序查找的时间性能161在等概率查找的情况下，

顺序表查找的平均查找长度为：对顺序表而言，Ci=n-i+1ASL=nP1+(n-1)P2++2Pn-1+Pn162

若查找概率无法事先测定，则查找过程采取的改进办法是，在每次查找之后，将刚刚查找到的记录直接移至表尾的位置上。在不等概率查找的情况下，ASLss

在

Pn≥Pn-1≥···≥P2≥P1时取极小值163顺序查找表的查找算法简单，但平均查找长度较大，特别不适用于表长较大的查找表。164基于有序顺序结构的检索165二分查找法问45是否已经保存？41113203233455053607790123456789101112位置值166BinarySearch//Returnpositionofelementinsorted//arrayofsizenwithvalueK.intbinary(intarray[],intn,intK){intl=-1;intr=n;//l,rarebeyondarrayboundswhile(l+1!=r){//Stopwhenl,rmeetinti=(l+r)/2;//Checkmiddleif(K<array[i])r=i;//Lefthalfif(K==array[i])returni;//Founditif(K>array[i])l=i;//Righthalf}returnn;//Searchvaluenotinarray}167假设n=2h-1并且查找概率相等则

在n>50时，可得近似结果

一般情况下，表长为n的折半查找的判定树的深度和含有n个结点的完全二叉树的深度相同。168字典检索检索一般不从辞典的中间开始。如果要查找的词以's'开头，查找者会估计到以's'开头的条目从词典的四分之三处开始。这样，他就会先翻到词典的四分之三处，然后根据所看到的内容决定接下来向哪里翻。也就是说，人们一般根据关键码值预期分布的知识“计算出”接下来向哪里翻。这种经过计算的二分法检索的形式称为词典检索(dictionarysearch)或者插值检索(interpolationsearch)169自组织线性表170根据访问频率排列列表根据估算的访问频率排列记录.执行顺序检索访问第一条记录的代价:1访问第二条记录的代价:2预期的检索代价:171例子(1)(1)每一条记录被访问的机会都相同.172例子(2)(2)指数频率173Zipf分布应用:自然语言(如英语)中单词使用频率的分布.城市中的人口规模的分布,等.80/20规则:80%的访问都是对20%的记录进行的.当按照80/20规则分布时,174自组织线性表自组织线性表根据实际的记录访问模式在线性表中修改记录顺序.自组织线性表使用启发式规则决定如何重新排列线性表.这些启发式规则类似于管理缓冲池的规则.175启发式规则计数方法:为每条记录保存一个访问计数,而且一直按照这个顺序维护记录.(类似于缓冲池替代策略中的“最不频繁使用”LFU法.)移至前端法:如果找到一条记录就把它放到线性表的最前面,而把其他记录后退一个位置.转置:把找到的记录与它在线性表中的前一条记录交换位置.176例子假定有8条记录，其关键码值为A到H，而且最初以字母顺序排列 访问序列FDFGEGFAFGE（12次访问）线性表根据计数法组织最后结果FGDEABCH总代价是45次比较根据移至前端启发式规则最后结果EGFDABCH总代价是54次比较根据转置启发式规则最后结果ABFDGECH总代价是62次比较177文本压缩的例子应用:文本压缩.线性表是根据移至前端规则自组织的.如果单词前面已经出现，就传送这个单词在线性表中的位置.如果单词是第一次出现，就传送这个单词.ThecaronthelefthitthecarIleft.Thecaron3lefthit35I5.这种压缩方法的思想类似于Ziv-lempel编码算法.178集合的检索179集合的检索Fordensesets(smallrange,highpercentageofelementsinset).可以使用逻辑上的位操作.例子:为了寻找数字0到15之间奇素数集合,计算:0011010100010100&0101010101010101180分块和索引（索引顺序查找）181分块查找的存储结构表分为b块，每一块中的关键字不一定有序，但前一块中的最大关键字必须小于后一块中的最小关键字，即表是“分块有序”的。抽取各块中的最大关键字及其起始位置构成一个索引表,由于表R是分块有序的，所以索引表是一个递增有序表。

182分块查找的基本思想1）首先查找索引表

索引表是有序表，可采用二分查找或顺序查找，以确定待查的结点在哪一块。

2）然后在已确定的块中进行顺序查找

由于块内无序，只能用顺序查找。

183分块查找的优点在表中插入或删除一个记录时，只要找到该记录所属的块，就在该块内进行插入和删除运算。因块内记录的存放是任意的，所以插入或删除比较容易，无须移动大量记录。分块查找的主要代价是增加一个辅助数组的存储空间和将初始表分块排序的运算。184要点回顾查找的方法取决于查找表的结构顺序查找的通用性二分查找（差值查找）的优点和局限性自组织，集合，分块和索引185BST和AVL

B树和键树课后预习186第11章图数据结构与算法分析187188189190191图的应用为计算机与通信网络的互连建模把一张地图表示为一组位置以及位置之间的距离，以求得位置之间得最短路径为网络的流量能力建模寻找从开始状态到目标状态得路径，如人工智能问题的求解为计算机算法建模，显示程序状态的变化为复杂活动各子任务的完成寻找较优顺序，如大型建筑的建造为家族、商业或军事组织和自然科学分类中的各种关系建模192网型结构小节客观世界中广泛存在网状结构图结构也在计算科学领域中被广泛的（创造和）应用以上各例的数据(信息)组织形式，均称为网状结构。193图的定义和基本术语194图Graphs图可以用G=(V,E)来表示,每个图都包括一个顶点集(vertices)V,和一个边集合(edges)E,其中E中的每条边都是V中某一对顶点之间的连接.顶点总数记为|V|,边的总数记为|E|.195图Graphs如果图中的边限定为从一个顶点指向另一个顶点,则此图称为有向图(directedgraph或digraph)。如果图中的边没有方向,则称之为无向图(undirectedgraph)。如果图中各顶点均带有标号,则称之为标号图(labeledgraph)。一条边所连接的两个顶点是相邻的(adjacent),称为邻接点(neighbors)。连接一对邻接点u、v的边被称为与顶点u、v相关联(incident)的边,记作(u,v)。每条边都可能附有值或权(weight)。边上标有权的图称为带权图(weightedgraph)196顶点的度在无向图中，与顶点vi(viV(G))相关联的边的条数称为vi的度，记为TD(vi)在有向图中，顶点的度为顶点的入度、出度之和入度等于以vi为头的弧的数目出度等于以vi为尾的弧的数目n为图G的顶点数197路径Paths和回路Cycles路径:如果顶点序列

v1,v2,…,vn

从

vi

到

vi+1(1<=i<n)的边均存在，则称顶点序列v1,v2,…,vn

构成一条长度为

n-1的路径(path).如果路径上的各个顶点都不同，则称这个路径为简单路径(simplepath).一条路径将某个顶点vi连接到它本身，且其长度大于或等于3，则称此路径为回路(cycle).如果构成回路