1、引言

    1抽象数据类型和数据结构的关系

    抽象数据类型（ADT）是一种比数据结构处于更高抽象层的数据类型，ADT使用数据结构来实现。

    2数据类型的定义和应用于数据的操作定义是ADT背后的一部分概念，隐藏数据上的操作是如何进行的。

    3分类：简单抽象数据类型和复杂抽象数据类型

    简单ADT：整数、实数、字符、指针；

    复杂ADT：需要建立。不需要详细说明实现过程的泛化操作成为抽象。

    抽象概念意味着：

    ①知道一个数据类型能做什么；

    ②如何去做是隐藏的。

    4定义

    抽象数据类型就是与对数据类型有意义的操作封装在一起的数据声明。然后，用它封装数据和操作并对用户隐藏。

    抽象数据类型：

    ①数据的定义；

    ②操作的定义；

    ③封装数据和操作。

    5抽象数据类型的模型

    抽象数据类型的模型分两个部分：数据类型和操作函数（公有的和私有的）；

    规则:

    ①数据结构（如数组、链表）在抽象数据类型里面，被公有和私有操作使用；

    ②应用程序只能通过接口访问公有操作；

    ③私有操作是抽象数据类型的内部用户使用的；

    ④虽然公有操作和接口应该独立于实现，但私有操作依赖于抽象数据类型实现时所选择的数据类型。    

    6抽象数据类型的实现

    计算机语言不提供抽象数据类型包。要使用抽象数据类型，首先要实现它们，把它们存储在库中。

    7几种复杂的数据类型

    ①栈

    ②队列

    ③广义线性表

    ④树（二叉树、二叉搜索树）

    ⑤图

2、栈

    1栈的定义

    栈是一种限制线性列表，该类型表的添加和删除操作只能在一端实现，称为栈顶。

    倒转的属性是栈被称为后进先出数据结构的原因。

    2栈的操作

    ①建栈

    ②入栈

    ③出栈

    ④空

    3栈的抽象数据类型

    4栈的应用

    ①倒转数据

    ②配对数据

    ③数据延迟使用

    ④回溯步骤

    5栈的实现

    ①使用数组实现：有带两个域的记录

    ②使用链表实现：有一个有栈名字的额外节点

3、队列

    1队列的定义

    2队列的操作

    3队列的抽象数据类型

    4队列的应用

    5队列的实现

4、广义线性表

    1广义线性表的定义

    2广义线性表的操作

    3广义线性表的抽象数据类型

    4广义线性表的应用

    5广义线性表的实现

5、树的基础知识

6、二叉树

    1二叉树的递归定义

    2二叉树的操作

    3二叉树的应用

    4二叉树的实现

7、二叉搜索树

    1二叉搜索树的定义

    2二叉搜索树的抽象数据类型

    3二叉搜索树的实现

8、图

    1图的定义

    2图的应用

计算机软考笔记之《抽象数据类型（ADT）》