第七话:抽象数据类型ADT

数据组织更加灵活
服务器君一共花费了203.804 ms进行了6次数据库查询,努力地为您提供了这个页面。
试试阅读模式?希望听取您的建议

我们对已有的数据类型进行抽象,就有了抽象数据类型。

抽象数据类型(Abstract Date Type, ADT):是指一个数学模型及定义在该模型上的一组操作。抽象数据类型的定义仅取决于它的一组逻辑特性,而与其在计算机内部如何表示和实现无关。

  • 为什么有了数据类型,还要有抽象数据类型呢?
  • 各个计算机,不管是大型机、小型机、PC、平板电脑、PDA, 甚至智能手机都拥有“整数”类型,也需要整数间的运算,那么整型其实就是一个抽象数据类型,尽管它在上面提到的这些在不同计算机中实现方法上可能不一样,但由于其定义的数学特性相同,在计算机编程者看来,它们都是相同的。因此,“抽象”的意义在于数据类型的数学抽象特性。
  • 而且,抽象数据类型不仅仅指那些已经定义并实现的数据类型,还可以是计算机编程者在设计软件程序时自己定义的数据类型,比如我们编写关于计算机绘图或者地图类的软件系统,经常都会用到坐标。也就是说,总是有成对出现的x和y,在3D 系统中还有z出现,既然这三个整型数字是始终在一起出现,我们就定义一个叫point 的抽象数据类型,它有x、y、z三个整型变量,这样我们很方便地操作一个point数据变量就能知道这一点的坐标了。

根据抽象数据类型的定义,它还包括定义在该模型上的一组操作。就像“超级玛丽”这个经典的任天堂游戏,里面的游戏主角是马里奥(Mario)。我们给他定义了几种基本操作,走(前进、后退、上、下)、跳、打子弹等。

一个抽象数据类型定义了:一个数据对象、数据对象中各数据元素之间的关系及对数据元素的操作。至于,一个抽象数据类型到底需要哪些操作,这就只能由设计者根据实际需要来定。像马里奥, 可能开始只有两种操作,走和跳,后来发现应该要增加一种打子弹的操作,再后来发现有些玩家希望它可以走得快一点,就有了按住打子弹键后前进就会“跑”的操作。这都是根据实际情况来设计的。

事实上,抽象数据类型体现了程序设计中问题分解、抽象和信息隐藏的特性。抽象数据类型把实际生活中的问题分解为多个规模小且容易处理的问题,然后建立一个计算机能处理的数据模型,并把每个功能模块的实现细节作为一个独立的单元,从而使具体实现过程隐藏起来。

抽象数据类型(Abstract Data Type, ADT) 是一个数据结构以及定义在该结构上的一组操作的总称。它是对数据类型的抽象,抽象的意义在于数据类型不是高级程序语言支持的基本数据类型,而是自定义的数据类型。

  • 抽象数据类型(ADT)的定义和实现通常是分开的。定义只包含数据逻辑结构的定义和所允许的一组操作;使用者通过这些定义了的操作对ADT进行操作;另一方面,实现者根据这些定义来完成ADT的各种具体实现方式。

为了便于在之后的讲解中对抽象数据类型进行规范的描述,我们给出了描述抽象数据类型的标准格式:

ADT 抽象数据类型名
Data
    数据元素之间的逻辑关系的定义
Operation
    操作1:
      前置条件:执行此操作前数据所必须的状态
      输入: 执行此操作所需要的输入
      功能: 该操作将完成的功能
      输出: 此操作执行完成后产生的输出
      后置条件: 执行此操作后数据的状态
    操作2:
      .
      .
      .
    操作n:
      .
      .
      .
endADT

对抽象数据类型的定义,不涉及实现细节,形式上可繁可简。

延伸阅读

此文章所在专题列表如下:

  1. 第一话:你的数据结构怎么学的?
  2. 第二话:数据结构的历史与来由
  3. 第三话:关于数据结构的一些概念
  4. 第四话:数据的逻辑结构
  5. 第五话:数据的物理结构
  6. 第六话:关于数据类型
  7. 第七话:抽象数据类型ADT
  8. 第八话:补充数据结构基本概念的关系
  9. 第九话:数据结构与算法的关系
  10. 第10话:什么是算法?
  11. 第11话:算法的五个基本特征
  12. 第12话:什么样的算法才是好算法
  13. 第13话:算法的性能分析
  14. 第14话:如何计算算法的时间复杂度
  15. 第15话:算法的最坏情况与平均情况
  16. 第16话:算法的空间复杂度

本文地址:http://www.nowamagic.net/librarys/veda/detail/2180,欢迎访问原出处。

不打个分吗?

转载随意,但请带上本文地址:

http://www.nowamagic.net/librarys/veda/detail/2180

如果你认为这篇文章值得更多人阅读,欢迎使用下面的分享功能。
小提示:您可以按快捷键 Ctrl + D,或点此 加入收藏

阅读一百本计算机著作吧,少年

很多人觉得自己技术进步很慢,学习效率低,我觉得一个重要原因是看的书少了。多少是多呢?起码得看3、4、5、6米吧。给个具体的数量,那就100本书吧。很多人知识结构不好而且不系统,因为在特定领域有一个足够量的知识量+足够良好的知识结构,系统化以后就足以应对大量未曾遇到过的问题。

奉劝自学者:构建特定领域的知识结构体系的路径中再也没有比学习该专业的专业课程更好的了。如果我的知识结构体系足以囊括面试官的大部分甚至吞并他的知识结构体系的话,读到他言语中的一个词我们就已经知道他要表达什么,我们可以让他坐“上位”毕竟他是面试官,但是在知识结构体系以及心理上我们就居高临下。

所以,阅读一百本计算机著作吧,少年!

《代码大全(第2版)》 史蒂夫•迈克康奈尔 (Steve McConnell) (作者), 金戈 (译者)

代码大全(第2版)是著名IT畅销书作者、《IEEE Software》杂志前主编、具有20年编程与项目管理经验的Steve McConnell十余年前的经典著作的全新演绎:第2版做了全面的更新,增加了很多与时俱进的内容,包括对新语言、新的开发过程与方法论的讨论等等。这是一本百科全书式的软件构建手册,涵盖了软件构建活动的方方面面,尤其强调提高软件质量的种种实践方法。

更多计算机宝库...