《数据结构》课件语言

《《数据结构》课件语言》由会员分享，可在线阅读，更多相关《《数据结构》课件语言（139页珍藏版）》请在金锄头文库上搜索。

1、主讲：戴小鹏主讲：戴小鹏 教授教授 Mobile :13787032384Mobile :13787032384 QQ:357295461QQ:357295461 OFFice:6-208OFFice:6-208湖南农业大学信息科学技术学院湖南农业大学信息科学技术学院数据结构每天早晨，叫起你的不是闹钟，而是梦想远见的思维决定了未来的格局写在前面的话l l如何和我联系？如何和我联系？n n办公室：办公室：6-2086-208n n办公电话：办公电话：8461800084618000n nMobile 13787032384Mobile 13787032384n nEmailEmail：n nQQ

2、:357295461QQ:357295461n n作业题作业题E-Mail: (E-Mail: (密码密码 1234567812345678）出于仁义与道德，不要改）出于仁义与道德，不要改l l本课程的网站：本课程的网站：n nhttp:/210.43.224.200/wlkt/C808/Asp/Root/Index.asp?Mode=1Data Relationships: R = |C1,C2 实数Operations:InitComplex( 初始条件：复数T已知操作结果：E1,E2分别加C1,C2Sub( 初始条件：复数T已知操作结果： E1,E2分别减C1,C2 ADT Comple

3、x抽象数据类型抽象数据类型ComplexComplex的规格说明的规格说明：2 2、抽象数据类型、抽象数据类型(ADT)(ADT)抽象数据类型Complex具体的表示和实现依赖于所采用的计算机语言。用户可以用某 种高级语言的固有数据类型和自定义数据类 型，并借助于过程和函数来表示和实现抽象 数据类型Complex。C语言表示如下：抽象数据类型抽象数据类型ComplexComplex的表示的表示：2、抽象数据类型(ADT)struct Complexreal RealPart;real ImagPart; ；OperationOperation 在Complex上可定义下列操作1 1）函数）函数

4、InitComplexInitComplex生成一个复数生成一个复数Z Z，Z=Z=x+iyx+iy Complex InitComplex( real x, real y );2 2）函数函数AddAdd求两个复数求两个复数Z1Z1与与Z2Z2之和之和。Complex Add( Complex Z1, Complex Z2 );或Complex Add( Complex Z, real R1, real R2 );3 3）函数函数SubSub，求两个复数求两个复数Z1Z1与与Z2Z2之差之差 Complex Sub( Complex Z1, Complex Z2 );或Complex Sub

5、(Complex Z, real R1, real R2 );2 2、抽象数据类型、抽象数据类型(ADT)(ADT)继下页OperationOperation4 4）函数函数MultiplyMultiply求两个复数之积求两个复数之积Complex Multiply( Complex Z1, Complex Z2 );Complex Multiply( Complex Z, real R1, real R2);5 5）函数函数GetRealPartGetRealPart 取复数取复数Z Z的实部的实部real GetRealPart( Complex Z );6 6）函数函数GetImagPa

6、rtGetImagPart取函数取函数Z Z的虚部的虚部real GetImagPart( Complex Z );2 2、抽象数据类型、抽象数据类型(ADT)(ADT)续上页以上关于ADT的定义（规格说明、表示）没有涉及到 实现。正象ADT的名字所暗示的那样，它是作为实现的公 共特征的抽象。但是，从ADT的角度研究数据结构的最终 目的仍在于应用，因此必须仔细考虑表示方法、算法、 实现的技术及细节。而当ADT被实现时，ADT中的元素成 了数据结构的一个实例,而那些操作就成了算法。由于在ADT的规格说明中，只指明了其功能而未指定 要采用何种方法，因此，实现的独立性是显而易见的。抽象数据类型抽象数

7、据类型ComplexComplex的实现：的实现：2 2、抽象数据类型、抽象数据类型(ADT)(ADT)Complex Create( real x, real y ) Complex Z;Z.RealPart = x; Z.ImagPart = y;return Z; Complex Add( Complex Z1, Complex Z2 ) Complex Sum;Sum.RealPart = Z1.RealPart + Z2.RealPart;Sum.ImagPart = Z1.ImagPart + Z2.ImagPart;return Sum; (以下略) 抽象数据类型Complex的

8、C语言实现：2 2、抽象数据类型、抽象数据类型(ADT)(ADT)实现实现ADTADT2 2、抽象数据类型、抽象数据类型(ADT)(ADT)由于C语言是面向过程的语言，它能支持ADT 的实现，但是不能很好的反映ADT的数据隐蔽原则 。在Pascal语言中，库单元(Unit)是ADT的较好表 示和实现。随着面向对象技术的成熟，用面向对象中的对 象/类来描述和实现ADT是非常好的方法。这种方 法在面向对象程序设计方面已经成熟，已经广泛应 用于不同程序设计语言及开发环境当中（如：C+ ，Object Pascal, VB, Java, PowerBuilder等等）。 下面是Complex采用C+的

9、定义：class Complexprivate:real RealPart;real ImagPart;public:Complex( real x, real y );/构造函数Complex( Complex /拷贝构造函数Complex Add( Complex Z );/加法Complex Sub( Complex Z );/减法Complex Multiply( Complex Z );/乘法real GetRealPart( void );/取实部real GetImagPart( void );/取虚部 C+实现略C+C+实现实现ADTADT2 2、抽象数据类型、抽象数据类型(A

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

11、达式 ； 成组赋值 (变量名1,变量名k)=(表达式1, 表达式k);结构名 = 结构名;结构名 = (值1, ,值k)；3 3、类、类C C语言语法规则语言语法规则2 2）赋值语句）赋值语句变换赋值 变量1 变量2；if( 条件 ) 语句1;if( 条件 ) 语句1;else 语句2； /可以嵌套3 3）IFIF语句语句3 3、类、类C C语言语法规则语言语法规则switch( 表达式 ) case 条件1：语句1；break;case 条件n：语句n; break;default: 语句 n+1 4 4） SwitchSwitch语句语句switch case 条件1：语句1；break;

12、case 条件n：语句n; break;default: 语句 n+1 3 3、类、类C C语言语法规则语言语法规则For语句：for( 处置表达式序列; 条件; 修改表达式系列 ) 语句；While语句：while( 条件 ) 语句；Do-While语句：do语句;while ( 条件 );5 5） 循环语句循环语句3 3、类、类C C语言语法规则语言语法规则6 6）基本函数基本函数7 7）布尔运算符布尔运算符8 8）标识符标识符9 9）常量和类型常量和类型第二问题数据结构研究什么 ？运算逻辑结构存储结构第三问题重新理解算法 Algorithm 算法的概念算法的概念 算法的描述算法的描述 算

13、法设计的要求算法设计的要求 算法效率的度量算法效率的度量 算法的存储空间需求算法的存储空间需求4 4、算法的描述和算法分析、算法的描述和算法分析算法=程序？算法是为了描述解决某一 问题的方法，而不涉及具 体的实现细节。算法存在的辨证关系 数据结构与算法的辨证关系l给定了数据的逻辑结构后，对同一逻辑结构而言， 由于存储结构的不同，定义的运算也是不同的。n如线性表是一种逻辑结构，若采用顺序存储方法表示，则 称为顺序表；若采用链式存储方法表示，则称为链表。n相同的运算在顺序表和链表上的实现方法是不同的。 算法的概念算法的概念4 4、算法的描述和算法分析、算法的描述和算法分析算法(Algorithm)

14、是对特定问题求解步骤的一 种描述，是能在计算机上经过有限时间完成的、 毫不含糊的指令的有限序列。其中每一条指令表 示一个或多个操作。 问题（Problem）是一个函数，或是输入和 输出的一种联系。程序（Program）是用计算 机程序设计语言实现的完成一定功能的代码。算法的实现一定是程序，但程序不一定是算 法的实现。4 4、算法的描述和算法分析、算法的描述和算法分析算法的五个重要特性1 1）有穷性有穷性：执行有限步，每步均在：执行有限步，每步均在有穷时间有穷时间 内完成。内完成。2 2）确定性确定性：对相同的输入，必产生相同的输：对相同的输入，必产生相同的输 出，即出，即无二义性无二义性。3

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