欢迎观临
路漫漫其修远兮,吾将上下而求索

数据结构基础:抽象数据类型ADT

一、数据结构和数据类型

在编程学习中,数据结构和数据类型是两个基本的专有名词。其含义相关而不同,也偶尔会让人产生一些迷惑。下面通过其定义来理解其中的区别和联系。

数据结构的定义如下:

数据结构是计算机存储、组织数据的方式。数据结构是指相互之间存在一种或多种特定关系的数据元素的集合。通常情况下,精心选择的数据结构可以带来更高的运行或者存储效率。数据结构往往同高效的检索算法和索引技术有关。

数据结构大体有两种分类方式:逻辑结构和存储结构。按照逻辑结构可分为线性结构(如数组,链表等)和非线性结构(如树,图等),按照存储结构分为顺序存储结构,链式存储结构,索引存储结构和散列存储结构。

再来看看数据类型:

数据类型是一组性质相同的值的集合以及定义在这个值集合上的一组操作的总称。

数据类型是一种数学上的抽象概念,又称为抽象数据类型(abstract data type, ADT),其定义仅仅取决于它的逻辑特性,而与它在计算机中的表示和实现无关。比如对于map数据类型,其定义由其上定义的insert, delete, find, size等这些操作决定;而其底层实现可以是不同的数据结构。

按其值的不同特性,数据类型通常可以分为原子类型和结构类型。原子类型是指其值不可分解为其他类型的基础数据类型,以及其上定义的一组操作,如int, float, bool,char等;结构类型是指一种数据结构以及定义在这种结构上的一组操作。

从以上概念我们可以看出,数据结构和算法是实现抽象数据类型的方法。我们学习数据结构和算法,其实就是学习抽象数据类型的实现方法以及其应用。

二、经典数据结构和经典抽象数据类型

在计算机语言的发展和应用过程中,人们已经研究和总结出了许多经典的抽象数据类型及其实现方法。C++标准库STL中也有了各种ADT的实现。

  • 表ADT(table) : 大小为N,形如A1,A2,…AN的值集合。STL实现为<vector>,<list>,<array><forward_list>

  • 栈ADT(stack) :栈是限制插入和删除只能在末端进行的表,该末端称为栈顶。栈的特点是后进先出(LIFO)。STL实现为<stack>
    栈的应用可见:后缀表达式

  • 队列ADT(queue) :队列是限制只能在一端插入,在另一端删除的表。队列的特点是先进先出(FIFO)。STL实现为<queue><deque>

  • 树(tree) :树是一种抽象数据结构,由一个根节点与零到多个子树相连而形成的节点的集合。经典的树类数据结构有 二叉查找树AVL树红黑树B/B+树等。STL中依据二叉树实现的ADT为<set><map>
    关于树的更多细节:(待整理。)

  • 散列(hash) :散列是一种利用表和散列函数来实现的特殊表结构,是一种用于以常数平均时间执行插入、删除和查找的技术。其不支持任何需要排序信息的操作。STL中依据散列表实现的ADT有<unordered_set><unordered_map>
    关于散列的更多细节:(待整理。)

  • 堆(heap) :堆通常是指二叉堆。堆是一棵满足一定性质的二叉树。堆总是满足如下两个性质:1. 堆中某个节点的值总是不大于(或不小于)其父节点的值;2. 堆总是一棵完全二叉树。根节点最大的堆叫做最大堆或大根堆,根节点最小的堆叫做最小堆或小根堆。堆是实现优先队列的首选结构。STL中利用堆实现的ADT有<queue>中的priority_queue
    关于堆得更多细节:(待整理。)

赞(0) 打赏
未经允许不得转载:云海鹰影博客 » 数据结构基础:抽象数据类型ADT
分享到: 更多 (0)

欢迎留言 抢沙发

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

微信扫一扫打赏