数据结构课件

《数据结构课件》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、1.4抽象数据类型的表示与实现数据类型(DataType)是对数据的取值范围、数据的结构以及允许施加操作的一种描述。每一种计算机高级语言都定义有自己的数据类型。在通用的计算机高级语言中，一般都具有整数、实数、枚举、字符、字符串、指针、数组、记录、文件等数据类型。按照其复杂程度的不同，通常可以把它们分为两大类：简单类型（或原子类型）和结构类型。抽象数据类型(AbstractDataType，简称ADT)是指一个数学模型以及定义在该模型上的一组操作。抽象数据类型的定义仅取决于它的一组逻辑特性，而与其在计算机内部如何表示和实现无关，即不

2、论其内部结构如何变化，只要它的数学特性不变，都不影响其外部的使用。抽象数据类型和数据类型实质是一个概念。但抽象数据类型的含义更广，抽象程度更高，更符合面向对象程序设计对数据的要求。一般数据类型由具体语言系统内部定义，直接提供给编程者定义用户数据，因此称它们为预定义数据类型。抽象数据类型通常由编程者定义，包括定义它所使用的数据和在这些数据上所进行的操作。在定义抽象数据类型中的数据部分和操作部分时，要求只定义到数据的逻辑结构和操作说明，不考虑数据的存储结构和操作的具体实现，这样抽象层次更高，更能为其他用户提供良好的使用接口。抽象数据类

3、型和具体的语言是无关的，是一种纯数学意义上的数据类型或数据模型。由于采用抽象数据类型的观点讨论数据结构，数据结构的具体实现对外是不可见的，能够看到的只是有这样一个数据类型，它具有所期望的若干性质，提供了希望的各种操作。使用这个类型可以定义实际需要的数据对象，并且通过类型上的操作处理这些对象。抽象数据类型的好处是显而易见的。它实现了信息隐蔽，符合“模块化”程序设计的要求，也是面向对象程序设计思想的体现。这为设计和实现复杂的大型程序提供了强有力的支持，便于软件的工业化生产，提高了软件的复用性。一个含抽象数据类型的软件模块通常应包含定义

4、、表示和实现三个部分。抽象数据类型可细分为下列三种类型：和数据结构的形式定义相对应，抽象数据类型可用以下三元组表示其中，D是数据对象，S是上的关系集，P是对D的基本操作集。抽象数据类型伪程序语言格式为ADT抽象数据类型名{数据对象：<数据对象的定义>数据关系：<数据关系的定义>基本操作：<基本操作的定义>}ADT抽象数据类型名例1-6复数的抽象数据类型定义。ADTComplex{数据对象：D={r,i

5、r,i为实数}数据关系：R={}基本操作：InitComplex(re,im);//构造一个复数DestroyCmopl

6、ex();//销毁复数IsAscending();//如果复数的两个元素按升序排列，//则返回1，否则返回0IsDescending();//如果复数的两个元素按降序排列，//则返回1，否则返回0Max(&e);//用e返回复数的两个元素中值较大的一个Min(&e);//用e返回复数的两个元素中值较小的一个}ADTComplex算法效率的衡量方法和准则通常有两种衡量算法效率的方法:事后统计法事前分析估算法缺点：1．必须执行程序2．其它因素掩盖算法本质和算法执行时间相关的因素：1．算法选用的策略2．问题的规模3．编写程序的语言4．编

7、译程序产生的机器代码的质量5．计算机执行指令的速度一个特定算法的“运行工作量”的大小，只依赖于问题的规模（通常用整数量n表示），或者说，它是问题规模的函数。假如，随着问题规模n的增长，算法执行时间的增长率和f(n)的增长率相同，则可记作：T(n)=O(f(n))称T(n)为算法的(渐近)时间复杂度。如何估算算法的时间复杂度？从算法中选取一种对于所研究的问题来说是基本操作的原操作，以该基本操作在算法中重复执行的次数作为算法运行时间的衡量准则。为了能够衡量算法的相对时间复杂度，又使评价相对简单化，可以采用更为粗略也更为有效的评价办法。

8、通常的做法是，只要大致计算出频度最大的关键语句的数量级(Order)，也即计算出算法的渐进时间复杂度（有时也简称时间复杂度）就可以了。关键语句一般是循环语句或递归调用语句，它的频度在程序中一般是最大的。例1-7累加求和。intSum(intb[],intn){ints=0;for(inti=0;i

9、][N],intn)//实现矩阵a[n][n]和b[n][n]的加法，其和存入c[n][n]中{inti,j;for(i=0;i