抽象数据类型(ADT)是什么?

抽象数据类型(Abstract Data Type,ADT)是将数据对象、数据对象之间的关系和数据对象的基本操作封装在一起的一种表达方式,它和工程中的应用是一致的。

在工程项目中,开始编程之前,首先列出程序需要完成的功能任务,先不用管具体怎么实现,实现细节在项目后期完成,一开始只是抽象出有哪些基本操作。把这些操作项封装为抽象数据类型,等待后面具体实现这些操作。而其他对象如果想调用这些操作,只需要按照规定好的参数接口调用,并不需要知道具体是怎么实现的,从而实现了数据封装和信息隐藏。

在 C++ 中可以用类的声明表示抽象数据类型,用类的实现来实现抽象数据类型的具体操作。

ADT三元素示意图

抽象数据类型可以用以下的三元组来表示:

ADT抽象数据类型名{
    数据对象:<数据对象的定义>
    数据关系:<数据关系的定义>
    基本操作:<基本操作的定义>
} ADT抽象数据类型名

例如,线性表的抽象数据类型的定义:

ADT List{
    数据对象:D={ai|ai∈Elemset, i=1,2,…,n, n≥0}
    数据关系:R={<ai−1,ai>|ai−1,ai∈D, i=2,…,n}
    基本操作:
    InitList(&L)
        操作结果:构造一个空的线性表 L
    DestroyList(&L)
        初始条件:线性表已存在
        操作结果:销毁线性表L
    ClearList(&L)
        初始条件:线性表已存在
        操作结果:置线性表L为空表
    ListEmpty(L)
        初始条件:线性表已存在
        操作结果:若线性表L为空表,则返回TRUE,否则返回FALSE
    ListLenght(L)
        初始条件:线性表已存在
        操作结果:返回线性表L数据元素个数
    GetElem(L, i, &e)
        初始条件:线性表已存在(1≥i≥ListLenght(L))
        操作结果:用e返回线性表L中第i个数据元素的值
    locatElem(L, e, comare())
        初始条件:线性表已存在,comare()是数据元素判定函数
        操作结果:返回线性表L中第1个与e满足关系comare()的数据元素的位序
    PriorElem(L, cur_e, &pre_e)
        初始条件:线性表已存在
        操作结果:若cur_e是线性表L的数据元素,且不是第一个,则用pre_e返回它的前驱,否则操作失败,pre_e无定义
    NextElem(L, cur_e, &next_e)
        初始条件:线性表已存在
        操作结果:若cur_e是线性表L的数据元素,且不是第最后一个,则用next_e返回它的后继,否则操作失败,next_e无定义
    ListInsert(&L, i, e)
        初始条件:线性表已存在(1≥i≥ListLenght(L)+1)
        操作结果:在线性表L中第i个数据元素之前插入新元素e,L长度加1
    ListDelete(&L, i, &e)
        初始条件:线性表已存在(1≥i≥ListLenght(L))
        操作结果:删除线性表L中第i个数据元素,用e返回其值,L长度减1
    ListTraverse(L, visit())
        初始条件:线性表已存在
        操作结果:依次对线性表L的每个数据元素调用visit()函数,一旦visit()失败,则操作失败
}ADT List

为什么要使用抽象数据类型?

抽象数据类型的主要作用是数据封装和信息隐藏,让实现与使用相分离。数据及其相关操作的结合称为数据封装。对象可以对其他对象隐藏某些操作细节,从而使这些操作不会受到其他对象的影响,这就是信息隐藏。

抽象数据类型独立于运算的具体实现,使用户程序只能通过抽象数据类型定义的某些操作来访问其中的数据,实现了信息隐藏。

为什么很多教材中没有使用抽象数据类型?

既然抽象数据类型符合工程化需要,可以实现数据封装和信息隐藏,为什么很多数据结构教材中的程序并没有使用抽象数据类型呢?因为很多人觉得数据结构难以理解,学习起来非常吃力,因此仅仅将数据结构的基本操作作为重点,把每一个基本操作讲解清楚,使读者学会和掌握数据结构的基本操作,便完成了数据结构书的基本任务。

在实际工程中,需要根据实际情况融会贯通,灵活运用,这是后续话题。目前要掌握的就是各种数据结构的基本操作,本教程也将基本操作作为重点讲述,并结合实例讲解数据结构的应用。

数据结构和算法相辅相成,密不可分,在学习数据结构之前,首先要了解什么是算法、好算法的衡量标准,以及算法复杂度的计算方法。

原创文章,作者:奋斗,如若转载,请注明出处:https://blog.ytso.com/23669.html

(0)
上一篇 2021年7月20日
下一篇 2021年7月20日

相关推荐

发表回复

登录后才能评论