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

1、主讲：戴小鹏 教授 Mobile QQ:357295461 OFFice:6-208 湖南农业大学信息科学技术学院,数据结构,每天早晨，叫起你的不是闹钟，而是梦想,远见的思维决定了未来的格局,写在前面的话,如何和我联系？ 办公室：6-208 办公电话：84618000 MobileEmail： QQ:357295461 作业题E-Mail: (密码12345678）出于仁义与道德，不要改 本课程的网站： 00/wlkt/C808/Asp/Root/Index.asp?Mode=1 Data Relation

2、ships: R = |C1,C2 实数 Operations: InitComplex( 初始条件：复数T已知 操作结果： E1,E2分别减C1,C2 ADT Complex,抽象数据类型Complex的规格说明：,2、抽象数据类型(ADT),抽象数据类型Complex具体的表示和实现依赖于所采用的计算机语言。用户可以用某种高级语言的固有数据类型和自定义数据类型，并借助于过程和函数来表示和实现抽象数据类型Complex。C语言表示如下：,抽象数据类型Complex的表示：,2、抽象数据类型(ADT),struct Complex real RealPart; real ImagPart; ；

3、,Operation 在Complex上可定义下列操作 1）函数InitComplex生成一个复数Z，Z=x+iy Complex InitComplex( real x, real y ); 2）函数Add求两个复数Z1与Z2之和。 Complex Add( Complex Z1, Complex Z2 ); 或Complex Add( Complex Z, real R1, real R2 ); 3）函数Sub，求两个复数Z1与Z2之差 Complex Sub( Complex Z1, Complex Z2 ); 或Complex Sub(Complex Z, real R1, real

4、R2 );,2、抽象数据类型(ADT),继下页,Operation 4）函数Multiply求两个复数之积 Complex Multiply( Complex Z1, Complex Z2 ); Complex Multiply( Complex Z, real R1, real R2); 5）函数GetRealPart 取复数Z的实部 real GetRealPart( Complex Z ); 6）函数GetImagPart取函数Z的虚部 real GetImagPart( Complex Z );,2、抽象数据类型(ADT),续上页,以上关于ADT的定义（规格说明、表示）没有涉及到实现。

5、正象ADT的名字所暗示的那样，它是作为实现的公共特征的抽象。但是，从ADT的角度研究数据结构的最终目的仍在于应用，因此必须仔细考虑表示方法、算法、实现的技术及细节。而当ADT被实现时，ADT中的元素成了数据结构的一个实例,而那些操作就成了算法。 由于在ADT的规格说明中，只指明了其功能而未指定要采用何种方法，因此，实现的独立性是显而易见的。,抽象数据类型Complex的实现：,2、抽象数据类型(ADT),Complex Create( real x, real y ) Complex Z; Z.RealPart = x; Z.ImagPart = y; return Z; Complex Ad

6、d( Complex Z1, Complex Z2 ) Complex Sum; Sum.RealPart = Z1.RealPart + Z2.RealPart; Sum.ImagPart = Z1.ImagPart + Z2.ImagPart; return Sum; (以下略) ,抽象数据类型Complex的C语言实现：,2、抽象数据类型(ADT),实现ADT,2、抽象数据类型(ADT),由于C语言是面向过程的语言，它能支持ADT的实现，但是不能很好的反映ADT的数据隐蔽原则。在Pascal语言中，库单元(Unit)是ADT的较好表示和实现。 随着面向对象技术的成熟，用面向对象中的对象/

7、类来描述和实现ADT是非常好的方法。这种方法在面向对象程序设计方面已经成熟，已经广泛应用于不同程序设计语言及开发环境当中（如：C+，Object Pascal, VB, Java, PowerBuilder等等）。,下面是Complex采用C+的定义： class Complex private: real RealPart; real ImagPart; public: Complex( real x, real y );/构造函数 Complex( Complex /取虚部 C+实现略,C+实现ADT,2、抽象数据类型(ADT),3、类C语言语法规则,类C语言是介于伪码语言和高级语言之间的

8、一种算法描述语言。 使用类C语言描述算法的好处： 1. 保持C结构清晰、明确直观等特色； 2. 但又略去一些次要环节，抓住主干精华。,2、类C语言语法规则,函数类型 过程名(参数表) /算法说明 语句组; return 结果； /过程名 当返回状态结果时，函数定义为Status类型。,1）算法以过程或函数的形式表示,3、类C语言语法规则,2）赋值语句,简单赋值 变量名 = 表达式；,串联赋值 变量1 = 变量2 = = 表达式；,成组赋值 (变量名1,变量名k)=(表达式1,表达式k);,结构名 = 结构名;,结构名 = (值1, ,值k)；,3、类C语言语法规则,2）赋值语句,变换赋值 变量

9、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语句,switch case 条件1：语句1；break; case 条件n：语句n; break; default: 语句 n+1 ,3、类C语言语法规则,For语句： for( 处置表达式序列; 条件; 修改表达式系列 ) 语句； While语句： while( 条件 ) 语句； Do-Whil

10、e语句： do 语句; while ( 条件 );,5） 循环语句,3、类C语言语法规则,6）基本函数,7）布尔运算符,8）标识符,9）常量和类型,第二问题数据结构研究什么,？,运算,逻辑结构,存储结构,第三问题重新理解算法Algorithm, 算法的概念 算法的描述 算法设计的要求 算法效率的度量 算法的存储空间需求,4、算法的描述和算法分析,算法,=,程序,？,算法是为了描述解决某一问题的方法，而不涉及具体的实现细节。,算法存在的辨证关系数据结构与算法的辨证关系,给定了数据的逻辑结构后，对同一逻辑结构而言，由于存储结构的不同，定义的运算也是不同的。 如线性表是一种逻辑结构，若采用顺序存储方

11、法表示，则称为顺序表；若采用链式存储方法表示，则称为链表。 相同的运算在顺序表和链表上的实现方法是不同的。, 算法的概念,4、算法的描述和算法分析,算法(Algorithm)是对特定问题求解步骤的一种描述，是能在计算机上经过有限时间完成的、毫不含糊的指令的有限序列。其中每一条指令表示一个或多个操作。,问题（Problem）是一个函数，或是输入和输出的一种联系。程序（Program）是用计算机程序设计语言实现的完成一定功能的代码。 算法的实现一定是程序，但程序不一定是算法的实现。,4、算法的描述和算法分析,算法的五个重要特性,1）有穷性：执行有限步，每步均在有穷时间内完成。,2）确定性：对相同的

12、输入，必产生相同的输出，即无二义性。,3）可行性：计算机可使用已实现的基本运算执行有限次来完成。,4）输入：零个或多个输入。,5）输出：一个或多个输出。,4、算法的描述和算法分析,关于算法性质的另一种描述 1、正确性(Correctness) 它必须完成所期望的功能，把每一次输入转化为正确的输出。 2、具体步骤(Concrete Steps) 一个算法应该由一系列具体步骤组成。 3、确定性(No Ambiguity) 下一步（通常是指算法描述中的下一步）应执行的步骤必须明确。 4、有限性(Finite) 一个算法必须由有限步组成。 5、可终止性(Terminable) 算法必须可以终止，即不能

13、进入死循环。,算法的描述,4、算法的描述和算法分析,一个算法可以用各种不同的方法来进行描述。比如可使用某种高级语言、汇编语言甚至机器语言来描述某个算法，亦可使用伪码语言或框图等其它形式来描述它。,算法的描述,4、算法的描述和算法分析,描述算法的语言形式,1.文字形式:用中文或英文这样的文字来描述算法。,2.伪码形式:用一种仿程序设计语言的语言来描述算法。,3.程序设计语言形式:用某种程序设计语言描述算法。其优点是算法不用修改，直接作为程序语句键入计算机，计算机能调用和运行。这里我们采用上讲介绍的类C语言来描述算法,4、算法的描述和算法分析,例:设计一个把存储在数组中的有n个抽象数据元素a0,

14、a1,an-1逆置的算法，即要求逆置后的数组中数据元素序列为an-1 , , a1 , a0 ,并要求原数组中的数据元素值不能被改变。,void Reverse(int n, DataType a, DataType b) int i; for(i=0;in;i+) bi=an-1-i; /把数组a的元素逆置后赋给数组b ,4、算法的描述和算法分析,例1-2:设计一个把存储在数组中的有n个抽象数据元素a0, a1,an-1逆置的算法，即要求逆置后的数组中数据元素序列为an-1 , , a1 , a0 ,并要求原数组中的数据元素值被改变。,void Reverse(int n, DataType

15、 a) int i,m=n/2; DataType temp; for(i=0;im;i+) /进行m次调换 temp=ai; ai=an-1-i; an-1-i=temp; ,在程序设计中，对算法进行分析是十分重要的。对于一个具体的应用实例，通常可能有若干个算法可供选用，应判断哪一个算法在现有的计算机环境中对解决某个问题是最优的。,例5：写一函数，用以计算1+2+n的值，其中n为已知。 long SumWork( int n ) int sum = 0; for( int i = 1; i+; i = n ) sum += i; return sum ; ,算法设计的要求,4、算法的描述和算

16、法分析,long BetterSum( int n ) return (n+1)*n/2; ,算法设计的要求,4、算法的描述和算法分析,在计算机科学中，通常使用算法的计算（执行）时间和所需的存储空间来评价算法或程序的优劣。 在选择算法时，除了要考虑算法的运算时间和所需内存外，往往还要考虑其它一些重要的因素，即所谓设计一个“好”的算法应考虑达到的下列目标。,1）正确性 2）可读性 3）健壮性 4）效率与低存储量需求,算法设计的要求,4、算法的描述和算法分析,1）正确性(Correctness) 能满足具体问题的需求。正确性对于选择算法来说，是首要的问题。 正确性的四个层次： a. 程序不含语法错

17、误； b. 程序对于输入数据能够得出满足规格说明要求的结果 (要算对)； c. 程序对于精心选择的典型、苛刻而带有刁难性的输入 数据能够得出满足规格说明要求的结果； d. 程序对于一切合法的输入数据都能产生满足规格说明 要求的结果。,算法设计的要求,4、算法的描述和算法分析,2）可读性(Readability) 希望一个算法易于理解、易于编码，也易于调试。 3）健壮性(Robustness) 对于异常的处理能力。能作出判断，并给出适当的提示或警告信息，以等待操作员的干预或能自动进行适当处理。 4）效率(Efficiency)与低存储需求 效率指算法执行时间。同一问题，算法执行时间越短，效率越高

18、。存储量需求指算法执行过程中所需的最大存储空间。此所谓时（执行时间）、空（运行空间）效应。,算法效率的度量,4、算法的描述和算法分析,算法执行时间的度量时间复杂度 执行时间取决于下列因素： a. 选用哪种算法 b. 问题的规模（输入的大小/复杂程度）； c. 所选用的语言； d. 编译程序所产生可执行代码的质量； e. 机器执行指令的速度。 1）事后统计 对算法程序的执行进行计时。（有缺陷） 2）事前估计 事先估算的主要因素问题的规模。,算法效率的度量,4、算法的描述和算法分析,一个算法是由控制结构（顺序、分支和循环）和原操作（指固有数据类型的操作）构成的，算法时间取决于两者的综合效果。但是，

19、为便于比较同一问题的不同算法，通常的做法是：从算法中选取一种对于所研究的问题（或算法类型）来说是基本运算的原操作，以该基本运算重复执行的次数作为算法的时间量度的依据。,2）事前估计,算法效率的度量,4、算法的描述和算法分析,例6： 两个nn矩阵相乘，令乘法运算作为基本运算 for( i = 1; i = n; i+ ) for( j = 1; j = n; j+ ) Cij = 0; for( k = 1; k = n; k+ ) Cij += Aik * Bkj; ; 整个算法执行时间与乘法操作重复执行的次数n3成正比，记作 T(n)=O(n3). 两个nn矩阵相乘的时间复杂度为O(n3).

20、,算法效率的度量,4、算法的描述和算法分析,定义：某算法执行时间T(n)是O(f(n)，意指存在正的常数M和n0，使对于一切n n0，T(n) Mf(n)都成立。如果一个程序的时间复杂度是O(f(n)，就说该程序的运行时间增加率的一个上界为f(n)，或说T(n)是f(n)的大O函数。,例7：设T(n)=n2+4n，则有f(n)=n2，即有： n2 + 4n = O(n2). 因为存在M=2，n0=4，使对于一切nn0，恒有 n2 +4n2 n2,4、算法的描述和算法分析,大O运算规则 规则一 对于任何的常数k和任何的函数f，恒有kf(n)=O(f(n)，即大O忽略常数因子。 规则二 若f(n)

21、=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) 8

22、nlog(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;

23、jn;j+) cij=0; /基本语句1 for(k=0;kn;k+) cij=cij+aik*bkj; /基本语句2 ,解:设基本语句的执行次数为f(n),有f(n)=c1n2+ c2n3,因 T(n)= f(n)=c1n2+ c2n3c n3, 其中c1 , c2 , c均为常数，所以该算法的时间复杂度为 T(n)=O(n3),例：求两个方阵的乘积 CA*B define n 自然数 MATRIXMLT(float Ann,float Bnn,float Cnn) int i, j, k; for(i=0;in;i+) for(j=0;jn;j+) Cij=0; for( k=0;kn;k

24、+) 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) log2n c log2 n,所以该算法的时间复杂度为 T(n)=O(log2n)。,例11:下边的算法是用冒泡排序法对数字a中的n个整数类型的数据元素(a0an-1)，从小到大进行排序，求该算法的时间复杂度。,void BubbleSort(int a,i

25、nt n) int i,j,flag=1; int temp; 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* n2 c* n2, 其中c为常数，所以该算法的时间复杂度为 T(n)=O(n2)。,算法的时间复杂度是衡量一个算法好坏的重要指标。一般来说，具有多项式时间复杂度的算法，是可接受、可实际使用的算法;具有指数时间复杂度的算法，是只有当n足够小时才可使用的算法。,例12 下面的算法是在一个有n个数据元素的数组a中删除第I个位置

26、的数组元素，要求当删除成功时数组元素个数减1，求该算法的时间复杂度。其中数组下标从0至n-1。,int Delete(int a, int /删除成功返回 ,解:假设删除任何位置上的数据元素都是等概率的,设Pi为删除第i个位置上数据元素的概率，则有Pi=1/n，设E为删除数组元素的平均次数，则有,因T(n)=E(n+1)/2 c*n,其中c为常数，所以该算法的等概率平均时间复杂度为 T(n)= O(n)。,例13: 对比在数据元素个数为30000时，冒泡排序算法和快速排序算法的实际耗时。 根据问题的要求，设计测试程序，并在计算机上实际运行。 程序运行结果：冒泡排序: 6.00 秒；快速排序:

27、0.00 秒 程序运行结果说明：系统中的difftime (end,start)函数以秒为单位计时，快速排序的实际耗时少于0.5 秒，所以输出显示为0.00 秒。程序运行结果说明，当数据元素个数足够大时，理论分析的快速排序算法优于冒泡排序算法的结果，和程序的实际测试结果吻合。,算法耗时的实际测试,算法的时间复杂度是衡量一个算法好坏的重要指标。一般来说，具有多项式时间复杂度（如O(n)、O(n2)、O(n6)、O(n8)等）的算法，是可接受、可实际使用的算法；而具有指数时间复杂度（如O(2n)、O(nn)、O(n！)等）的算法，是理论上可以计算，但实际上不可计算的问题，通常称作难解的问题。 对于

28、具有多项式时间复杂度的算法，无论数据元素个数多大（只要是有限的数值），算法都可以在有限的时间内运行完成；而对于难解的问题，当n足够小时，算法可以在有限的时间内运行完成，当n比较大时，其运行时间将是一个天文数字！,数据元素个数和时间复杂度,常数阶 对数阶 线性阶 线性对数阶 平方阶 立方阶 K次方阶 指数阶,常见的时间复杂度，按数量级递增排序：,存储空间需求,4、算法的描述和算法分析,算法所需存储空间的度量空间复杂度（性） 算法的空间复杂度S(n)就是一个算法或程序所需要的存储单元数。 一个非递归程序，并且不含有动态数据结构，在它还未开始执行前，所需存储单元总数即已确定。为简化计算，在算法的空间复杂度分析中，将忽略程序中所有的简单变量和程序的执行代码本身所占的内存空间，而只统计与问题大小有关的数组等结构变量所需的内存量，有时当一些数据、结构变量要占用相当可观的常数量单元时，也可进行统