HNND《数据结构》课件(C语言).ppt

主讲：戴小鹏教授Mobile:13787032384QQ:357295461OFFice:6-208湖南农业大学信息科学技术学院,数据结构,每天早晨，叫起你的不是闹钟，而是梦想,远见的思维决定了未来的格局,写在前面的话,如何和我联系？办公室：6-208办公电话：84618000Mobile13787032384Email：hnds2010QQ:357295461作业题E-Mail:hndshw2010(密码12345678）出于仁义与道德，不要改本课程的网站：http:/210.43.224.200/wlkt/C808/Asp/Root/Index.asp?Mode=1DataRelationships:R=|C1,C2实数Operations:InitComplex(初始条件：复数T已知操作结果：E1,E2分别减C1,C2ADTComplex,抽象数据类型Complex的规格说明：,2、抽象数据类型(ADT),抽象数据类型Complex具体的表示和实现依赖于所采用的计算机语言。用户可以用某种高级语言的固有数据类型和自定义数据类型，并借助于过程和函数来表示和实现抽象数据类型Complex。C语言表示如下：,抽象数据类型Complex的表示：,2、抽象数据类型(ADT),structComplexrealRealPart;realImagPart;；,Operation在Complex上可定义下列操作1）函数InitComplex生成一个复数Z，Z=x+iyComplexInitComplex(realx,realy);2）函数Add求两个复数Z1与Z2之和。ComplexAdd(ComplexZ1,ComplexZ2);或ComplexAdd(ComplexZ,realR1,realR2);3）函数Sub，求两个复数Z1与Z2之差ComplexSub(ComplexZ1,ComplexZ2);或ComplexSub(ComplexZ,realR1,realR2);,2、抽象数据类型(ADT),继下页,Operation4）函数Multiply求两个复数之积ComplexMultiply(ComplexZ1,ComplexZ2);ComplexMultiply(ComplexZ,realR1,realR2);5）函数GetRealPart取复数Z的实部realGetRealPart(ComplexZ);6）函数GetImagPart取函数Z的虚部realGetImagPart(ComplexZ);,2、抽象数据类型(ADT),续上页,以上关于ADT的定义（规格说明、表示）没有涉及到实现。正象ADT的名字所暗示的那样，它是作为实现的公共特征的抽象。但是，从ADT的角度研究数据结构的最终目的仍在于应用，因此必须仔细考虑表示方法、算法、实现的技术及细节。而当ADT被实现时，ADT中的元素成了数据结构的一个实例,而那些操作就成了算法。由于在ADT的规格说明中，只指明了其功能而未指定要采用何种方法，因此，实现的独立性是显而易见的。,抽象数据类型Complex的实现：,2、抽象数据类型(ADT),ComplexCreate(realx,realy)ComplexZ;Z.RealPart=x;Z.ImagPart=y;returnZ;ComplexAdd(ComplexZ1,ComplexZ2)ComplexSum;Sum.RealPart=Z1.RealPart+Z2.RealPart;Sum.ImagPart=Z1.ImagPart+Z2.ImagPart;returnSum;(以下略),抽象数据类型Complex的C语言实现：,2、抽象数据类型(ADT),实现ADT,2、抽象数据类型(ADT),由于C语言是面向过程的语言，它能支持ADT的实现，但是不能很好的反映ADT的数据隐蔽原则。在Pascal语言中，库单元(Unit)是ADT的较好表示和实现。随着面向对象技术的成熟，用面向对象中的对象/类来描述和实现ADT是非常好的方法。这种方法在面向对象程序设计方面已经成熟，已经广泛应用于不同程序设计语言及开发环境当中（如：C+，ObjectPascal,VB,Java,PowerBuilder等等）。,下面是Complex采用C+的定义：classComplexprivate:realRealPart;realImagPart;public:Complex(realx,realy);/构造函数Complex(Complex/取虚部C+实现略,C+实现ADT,2、抽象数据类型(ADT),3、类C语言语法规则,类C语言是介于伪码语言和高级语言之间的一种算法描述语言。使用类C语言描述算法的好处：1.保持C结构清晰、明确直观等特色；2.但又略去一些次要环节，抓住主干精华。,2、类C语言语法规则,函数类型过程名(参数表)/算法说明语句组;return结果；/过程名当返回状态结果时，函数定义为Status类型。,1）算法以过程或函数的形式表示,3、类C语言语法规则,2）赋值语句,简单赋值变量名=表达式；,串联赋值变量1=变量2=表达式；,成组赋值(变量名1,变量名k)=(表达式1,表达式k);,结构名=结构名;,结构名=(值1,值k)；,3、类C语言语法规则,2）赋值语句,变换赋值变量1变量2；,if(条件)语句1;if(条件)语句1;else语句2；/可以嵌套,3）IF语句,3、类C语言语法规则,switch(表达式)case条件1：语句1；break;case条件n：语句n;break;default:语句n+1,4）Switch语句,switchcase条件1：语句1；break;case条件n：语句n;break;default:语句n+1,3、类C语言语法规则,For语句：for(处置表达式序列;条件;修改表达式系列)语句；While语句：while(条件)语句；Do-While语句：do语句;while(条件);,5）循环语句,3、类C语言语法规则,6）基本函数,7）布尔运算符,8）标识符,9）常量和类型,第二问题数据结构研究什么,？,运算,逻辑结构,存储结构,第三问题重新理解算法Algorithm,算法的概念算法的描述算法设计的要求算法效率的度量算法的存储空间需求,4、算法的描述和算法分析,算法,=,程序,？,算法是为了描述解决某一问题的方法，而不涉及具体的实现细节。,算法存在的辨证关系数据结构与算法的辨证关系,给定了数据的逻辑结构后，对同一逻辑结构而言，由于存储结构的不同，定义的运算也是不同的。如线性表是一种逻辑结构，若采用顺序存储方法表示，则称为顺序表；若采用链式存储方法表示，则称为链表。相同的运算在顺序表和链表上的实现方法是不同的。,算法的概念,4、算法的描述和算法分析,算法(Algorithm)是对特定问题求解步骤的一种描述，是能在计算机上经过有限时间完成的、毫不含糊的指令的有限序列。其中每一条指令表示一个或多个操作。,问题（Problem）是一个函数，或是输入和输出的一种联系。程序（Program）是用计算机程序设计语言实现的完成一定功能的代码。算法的实现一定是程序，但程序不一定是算法的实现。,4、算法的描述和算法分析,算法的五个重要特性,1）有穷性：执行有限步，每步均在有穷时间内完成。,2）确定性：对相同的输入，必产生相同的输出，即无二义性。,3）可行性：计算机可使用已实现的基本运算执行有限次来完成。,4）输入：零个或多个输入。,5）输出：一个或多个输出。,4、算法的描述和算法分析,关于算法性质的另一种描述1、正确性(Correctness)它必须完成所期望的功能，把每一次输入转化为正确的输出。2、具体步骤(ConcreteSteps)一个算法应该由一系列具体步骤组成。3、确定性(NoAmbiguity)下一步（通常是指算法描述中的下一步）应执行的步骤必须明确。4、有限性(Finite)一个算法必须由有限步组成。5、可终止性(Terminable)算法必须可以终止，即不能进入死循环。,算法的描述,4、算法的描述和算法分析,一个算法可以用各种不同的方法来进行描述。比如可使用某种高级语言、汇编语言甚至机器语言来描述某个算法，亦可使用伪码语言或框图等其它形式来描述它。,算法的描述,4、算法的描述和算法分析,描述算法的语言形式,1.文字形式:用中文或英文这样的文字来描述算法。,2.伪码形式:用一种仿程序设计语言的语言来描述算法。,3.程序设计语言形式:用某种程序设计语言描述算法。其优点是算法不用修改，直接作为程序语句键入计算机，计算机能调用和运行。这里我们采用上讲介绍的类C语言来描述算法,4、算法的描述和算法分析,例:设计一个把存储在数组中的有n个抽象数据元素a0,a1,an-1逆置的算法，即要求逆置后的数组中数据元素序列为an-1,a1,a0,并要求原数组中的数据元素值不能被改变。,voidReverse(intn,DataTypea,DataTypeb)inti;for(i=0;in;i+)bi=an-1-i;/把数组a的元素逆置后赋给数组b,4、算法的描述和算法分析,例1-2:设计一个把存储在数组中的有n个抽象数据元素a0,a1,an-1逆置的算法，即要求逆置后的数组中数据元素序列为an-1,a1,a0,并要求原数组中的数据元素值被改变。,voidReverse(intn,DataTypea)inti,m=n/2;DataTypetemp;for(i=0;im;i+)/进行m次调换temp=ai;ai=an-1-i;an-1-i=temp;,在程序设计中，对算法进行分析是十分重要的。对于一个具体的应用实例，通常可能有若干个算法可供选用，应判断哪一个算法在现有的计算机环境中对解决某个问题是最优的。,例5：写一函数，用以计算1+2+n的值，其中n为已知。longSumWork(intn)intsum=0;for(inti=1;i+;i=n)sum+=i;returnsum;,算法设计的要求,4、算法的描述和算法分析,longBetterSum(intn)return(n+1)*n/2;,算法设计的要求,4、算法的描述和算法分析,在计算机科学中，通常使用算法的计算（执行）时间和所需的存储空间来评价算法或程序的优劣。在选择算法时，除了要考虑算法的运算时间和所需内存外，往往还要考虑其它一些重要的因素，即所谓设计一个“好”的算法应考虑达到的下列目标。,1）正确性2）可读性3）健壮性4）效率与低存储量需求,算法设计的要求,4、算法的描述和算法分析,1）正确性(Correctness)能满足具体问题的需求。正确性对于选择算法来说，是首要的问题。正确性的四个层次：a.程序不含语法错误；b.程序对于输入数据能够得出满足规格说明要求的结果(要算对)；c.程序对于精心选择的典型、苛刻而带有刁难性的输入数据能够得出满足规格说明要求的结果；d.程序对于一切合法的输入数据都能产生满足规格说明要求的结果。,算法设计的要求,4、算法的描述和算法分析,2）可读性(Readability)希望一个算法易于理解、易于编码，也易于调试。3）健壮性(Robustness)对于异常的处理能力。能作出判断，并给出适当的提示或警告信息，以等待操作员的干预或能自动进行适当处理。4）效率(Efficiency)与低存储需求效率指算法执行时间。同一问题，算法执行时间越短，效率越高。存储量需求指算法执行过程中所需的最大存储空间。此所谓时（执行时间）、空（运行空间）效应。,算法效率的度量,4、算法的描述和算法分析,算法执行时间的度量时间复杂度执行时间取决于下列因素：a.选用哪种算法b.问题的规模（输入的大小/复杂程度）；c.所选用的语言；d.编译程序所产生可执行代码的质量；e.机器执行指令的速度。1）事后统计对算法程序的执行进行计时。（有缺陷）2）事前估计事先估算的主要因素问题的规模。,算法效率的度量,4、算法的描述和算法分析,一个算法是由控制结构（顺序、分支和循环）和原操作（指固有数据类型的操作）构成的，算法时间取决于两者的综合效果。但是，为便于比较同一问题的不同算法，通常的做法是：从算法中选取一种对于所研究的问题（或算法类型）来说是基本运算的原操作，以该基本运算重复执行的次数作为算法的时间量度的依据。,2）事前估计,算法效率的度量,4、算法的描述和算法分析,例6：两个nn矩阵相乘，令乘法运算作为基本运算for(i=1;i=n;i+)for(j=1;jn0，恒有n2+4n2n2,4、算法的描述和算法分析,大O运算规则规则一对于任何的常数k和任何的函数f，恒有kf(n)=O(f(n)，即大O忽略常数因子。规则二若f(n)=O(g(n)且g(n)=O(h(n)，则f(n)=O(h(n)，即大O的概念是传递的。规则三若定义maxf(n)，g(n)为f(n)与g(n)两者中增长率较快的函数，则有f(n)+g(n)=O(maxf(n),g(n).规则四若f1(n)=O(g1(n)且f2(n)=O(g2(n)，则f1(n)f2(n)=O(g1(n)g2(n)，即大O符合乘法规则。有关数学问题：/型不定式极限有关数学定理：罗比塔法则,例8求时间函数8nlog(n)+4n3/2的大O.(1)log(n)=O(n1/2)定义(2)nlog(n)=O(nn1/2)=O(n3/2)规则四(3)8nlog(n)=8O(n3/2)=O(n3/2)规则一(4)4n3/2=O(n3/2)规则一(5)8nlog(n)+4n3/2=O(max8nlog(n)，4n3/2）规则三max8nlog(n)，4n3/2=maxO(n3/2)，O(n3/2)=O(n3/2)8nlog(n)+4n3/2=O(O(n3/2)所以有=O(n3/2)规则二8nlog(n)+4n3/2=O(n3/2).,4、算法的描述和算法分析,例9:设数组a和b在前边部分已赋值，求如下两个n阶矩阵相乘运算算法的时间复杂度。,for(i=0;in;i+)for(j=0;jn;j+)cij=0;/基本语句1for(k=0;kn;k+)cij=cij+aik*bkj;/基本语句2,解:设基本语句的执行次数为f(n),有f(n)=c1n2+c2n3,因T(n)=f(n)=c1n2+c2n3cn3,其中c1,c2,c均为常数，所以该算法的时间复杂度为T(n)=O(n3),例：求两个方阵的乘积CA*Bdefinen自然数MATRIXMLT(floatAnn,floatBnn,floatCnn)inti,j,k;for(i=0;in;i+)for(j=0;jn;j+)Cij=0;for(k=0;kn;k+)Cij=Aik*Bkj,/n+1,/n(n+1),/n*n,/n*n*(n+1),/n*n*n,例10:设n为如下算法处理的数据个数，求如下算法的时间复杂度。for(i=1;i=n;i=2*i)couti=i;,解:设基本语句的执行次数为f(n),有2f(n)n,即有f(n)log2n。因T(n)=f(n)log2nclog2n,所以该算法的时间复杂度为T(n)=O(log2n)。,例11:下边的算法是用冒泡排序法对数字a中的n个整数类型的数据元素(a0an-1)，从小到大进行排序，求该算法的时间复杂度。,voidBubbleSort(inta,intn)inti,j,flag=1;inttemp;for(i=1;iaj+1)flag=1;temp=aj;aj=aj+1;aj+1=temp;,解:设基本语句的执行次数为f(n),最坏情况下有f(n)n+4*n2/2因T(n)=f(n)n+2*n2c*n2,其中c为常数，所以该算法的时间复杂度为T(n)=O(n2)。,算法的时间复杂度是衡量一个算法好坏的重要指标。一般来说，具有多项式时间复杂度的算法，是可接受、可实际使用的算法;具有指数时间复杂度的算法，是只有当n足够小时才可使用的算法。,例12下面的算法是在一个有n个数据元素的数组a中删除第I个位置的数组元素，要求当删除成功时数组元素个数减1，求该算法的时间复杂度。其中数组下标从0至n-1。,intDelete(inta,int/删除成功返回,解:假设删除任何位置上的数据元素都是等概率的,设Pi为删除第i个位置上数据元素的概率，则有Pi=1/n，设E为删除数组元素的平均次数，则有,因T(n)=E(n+1)/2c*n,其中c为常数，所以该算法的等概率平均时间复杂度为T(n)=O(n)。,例13:对比在数据元素个数为30000时，冒泡排序算法和快速排序算法的实际耗时。根据问题的要求，设计测试程序，并在计算机上实际运行。程序运行结果：冒泡排序:6.00秒；快速排序:0.00秒程序运行结果说明：系统中的difftime(end,start)函数以秒为单位计时，快速排序的实际耗时少于0.5秒，所以输出显示为0.00秒。程序运行结果说明，当数据元素个数足够大时，理论分析的快速排序算法优于冒泡排序算法的结果，和程序的实际测试结果吻合。,算法耗时的实际测试,算法的时间复杂度是衡量一个算法好坏的重要指标。一般来说，具有多项式时间复杂度（如O(n)、O(n2)、O(n6)、O(n8)等）的算法，是可接受、可实际使用的算法；而具有指数时间复杂度（如O(2n)、O(nn)、O(n！)等）的算法，是理论上可以计算，但实际上不可计算的问题，通常称作难解的问题。对于具有多项式时间复杂度的算法，无论数据元素个数多大（只要是有限的数值），算法都可以在有限的时间内运行完成；而对于难解的问题，当n足够小时，算法可以在有限的时间内运行完成，当n比较大时，其运行时间将是一个天文数字！,数据元素个数和时间复杂度,常数阶对数阶线性阶线性对数阶平方阶立方阶K次方阶指数阶,常见的时间复杂度，按数量级递增排序：,存储空间需求,4、算法的描述和算法分析,算法所需存储空间的度量空间复杂度（性）算法的空间复杂度S(n)就是一个算法或程序所需要的存储单元数。一个非递归程序，并且不含有动态数据结构，在它还未开始执行前，所需存储单元总数即已确定。为简化计算，在算法的空间复杂度分析中，将忽略程序中所有的简单变量和程序的执行代码本身所占的内存空间，而只统计与问题大小有关的数组等结构变量所需的内存量，有时当一些数据、结构变量要占用相当可观的常数量单元时，也可进行统计。含有动态数据结构的程序应统计内存分配过程的次数乘以该过程产生的动态变量所占单元的大小。递归调用情况较复杂，所需内存单元数等于递归调用的最大深度乘以该递归过程本身所需的内存量，后者包括简单变量、参数变量、调用时系统所需的辅助内存量等。,第四问题如何分析算法的优劣？,两个指标：时间复杂度空间复杂度,评价算法的优劣,主要考虑如下三点：执行算法所耗费的时间执行算法所耗费的存储空间，其中主要考虑辅助存储空间；算法应易于理解，易于编码，易于调试等等。,世界是平衡的,我们希望选用一个所占存储空间小、运行时间短、其它性能也好的算法。然而，实际上很难做到十全十美。原因是上述要求有时相互抵触，要节约算法的执行时间往往要以牺牲更多的空间为代价，而为了节省空间可能耗费更多的计算时间。因此我们只能根据具体情况有所侧重。若该程序使用次数较少，则力求算法简明易懂；对于反复多次使用的程序，应尽可能选用快速的算法；若待解决的问题数据量极大，机器的存储空间较小，则相应算法主要考虑如何节省空间。,关于空间复杂度的分析,例:数组的转置,关于时间复杂度的分析,一个算法所耗费的时间，应该是该算法中每条语句的执行时间之和，而每条语句的执行时间是该语句的执行次数(也称为频度(FrequencyCount)与该语句执行一次所需时间的乘积。常数阶O(1)对数阶O(1og2n)线性阶O(n)线性对数阶O(nlog2n)O(n2)、O(n3)、O(nk)、指数阶O(2n)。,第一章小结,基本内容*数据和数据结构等名词和术语的确定含义*抽象数据类型（ADT）*描述算法的类C语言*从时间和空间角度分析算法的方法,学习要点*熟悉各名词、术语的含义，掌握基本概念，特别是数据的逻辑结构和存储结构之间的关系*了解怎样以ADT的角度来描述数据结构*熟悉类C语言的书写规范*理解算法五要素*掌握计算语句频度和估算算法时间复杂度的方法,第一章小结,算法设计的基本步骤明确需求构造数学模型设计算法正确性验证算法效率的分析算法的实现程序的测试与排错编写文档资料,作业,请在下次课前完成第1章自测卷全部内容；（题目在hndshw2010中下载）复习C语言，重点是结构类型和递归概念,