湖南农大-《数据结构》课件(C语言) 第01章.pptVIP

第一章 绪论 围绕台  例2：整数的数学概念和施加于整数的运算构成一个ADT，不同计算机中实现可能不同，其数学特性是相同，因此对用户完全相同。 3、抽象数据类型(ADT) 例3：一个整数线性表的ADT应包含下列操作： ?插入一个整数到线性表尾 ?删除线性表中特定位置上的整数 ?在线性表中查找特定整数 ADT包括以下三部分内容： ADT的规格说明(Specification) ADT的表示(Representation) ADT的实现(Implementation) 用元组表示： ADT = ( 数据对象, 关系集, 处理集 ) 3、抽象数据类型(ADT) 3、抽象数据类型(ADT) 本书的表示格式： ADT 抽象数据类型名 { 数据对象：数据对象的定义 数据关系：数据关系的定义 基本操作：基本操作的定义 } ADT 抽象数据类型名 3、抽象数据类型(ADT) 3、抽象数据类型(ADT) 用伪码表示 基本操作名(参数表) 初始条件：初始条件描述 操作结果：操作结果描述 在具体实现时，完成任务的算法、数据类型、数据结构、程序的逻辑组织，甚至采用哪种程序设计语言都是可以自由选择的－－ 与具体实现无关。 ADT的主要目的之一是对用户隐蔽所有的表示方法，算法的详细细节、实现操作的具体代码以及其它所有对外界不必要的细节，都被局限于具体实现的模块内部，从而实现了信息的隐蔽。 ADT的一个重要优点是其简单性。ADT的目的是将数据的本质特征、它们的结构及操作同它们的非本质的具体表示及实现细节相区分开来，从而得到了简化。 3、抽象数据类型(ADT) 例4：在数据结构中，复数可定义为一种简单的抽象数据类型： Complex=(C,R) 其中C是含有两个实数的集合{C1,C2}， R={P}，P是定义在集合C上的一种关系{C1,C2}， 有序偶C1,C2表示C1是复数的实部，C2是复数的虚部。 3、抽象数据类型(ADT) Specification Complex 元素（Elements） 元素的集合为两个实数的笛卡儿乘积 Z = R × R 其中R表示实数集，Z表示复数集。 结构（Structure） Complex的元素之间不存在任何结构，每一个元素表示定义在复数域Z中的一个孤立的值。 抽象数据类型Complex的规格说明： 3、抽象数据类型(ADT) ADT Complex { Data Objects: D = { C1,C2 | C1,C2 ∈实数}; Data Relationships: R = {C1,C2|C1,C2 ∈实数} Operations: InitComplex( T, E1, E2 ) 操作结果：构造复数，E1,E2分别代替C1,C2。 Add( T, E1, E2 ); 初始条件：复数T已知 操作结果：E1,E2分别加C1,C2 Sub( T, E1, E2 ); 初始条件：复数T已知 操作结果： E1,E2分别减C1,C2 … … … } ADT Complex 抽象数据类型Complex的规格说明： 3、抽象数据类型(ADT) 抽象数据类型Complex具体的表示和实现依赖于所采用的计算机语言。用户可以用某种高级语言的固有数据类型和自定义数据类型，并借助于过程和函数来表示和实现抽象数据类型Complex。C语言表示如下： 抽象数据类型Complex的表示： 3、抽象数据类型(ADT) struct Complex{ real RealPart; real ImagPart; }； 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 R2 ); 3、抽象数据类型(ADT) 继下页 Operation 4）函数Multiply求两个复数之积 Complex Multiply( Complex Z1, Com