到底什么是ADT呢.abstract data type

类的基础：抽象数据类型抽象数据类型（ADT,abstractdatatype）是指一些数据以及对这些数据所进行的 *** 作的集合。这些 *** 作既向程序的其余部分描述了这些数据是怎么样的，也允许程序的其余部分改变这些数据。“抽象数据类型”概念中“数据”一词的用法有些随意。一个ADT可能是一个图形窗体以及所有能影响该窗体的 *** 作；也可以是一个文件以及对这个文件进行的 *** 作；或者是一张保险费率表以及相关 *** 作等等。要想理解面向对象编程，首先要理解ADT。不懂ADT的程序员开发出来的类只是名义上的“类”而已——实际上这种“类”只不过就是把一些稍有点儿关系的数据和子程序堆在一起。然而在理解ADT之后，程序员就能写出在一开始很容易实现、日后也易于修改的类来。传统的编程教科书在讲到抽象数据类型时，总会用一些数学中的事情打岔。这些书往往会像这么写：“你可以把抽象数据类型想成一个定义有一组 *** 作的数学模型。”这种书会给人一种感觉，好像你从不会真正用到抽象数据类型似的——除非拿它来催眠。把抽象数据类型解释得这么空洞是完全丢了重点。抽象数据类型可以让你像在现实世界中一样 *** 作实体，而不必在低层的实现上摆弄实体，这多令人兴奋啊。你不用再向链表中插入一个节点了，而是可以在电子表格中添加一个数据单元格，或向一组窗体类型中添加一个新类型，或给火车模型加挂一节车厢。深入挖掘能在问题领域工作（而非在底层实现领域工作）的能量吧！ExampleoftheNeedforanADT需要用到ADT的例子为了讨论，这里先举一个例子，看看ADT在什么情况下会非常有用。有了例子之后我们将继续深入细节探讨。假设你正在写一个程序，它能用不同的字体、字号和文字属性（如粗体、斜体等）来控制显示在屏幕上的文本。程序的一部分功能是控制文本的字体。如果你用一个ADT，你就能有捆绑在相关数据上的一组 *** 作字体的子程序——有关的数据包括字体名称、字号和文字属性等。这些子程序和数据集合为一体，就是一个ADT。如果不使用ADT，你就只能用一种拼凑的方法来 *** 纵字体了。举例来说，如果你要把字体大小改为12磅（point），即高度碰巧为16个像素（pixel），你就要写类似这样的代码：currentFont.size=16如果你已经开发了一套子程序库，那么代码可能会稍微好看一些：currentFont.size=PointsToPixels(12)或者你还可以给该属性起一个更特定的名字，比如说：currentFont.sizeOnPixels=PointsToPixels(12)但你是不能同时使用currentFont.sizeInPixels和currentFont.sizeInPoints，因为如果同时使用这两项数据成员，currentFont就无从判断到底该用哪一个了。而且，如果你在程序的很多地方都需要修改字体的大小，那么这类语句就会散布在整个程序之中。如果你需要把字体设为粗体，你或许会写出下面的语句，这里用到了一个逻辑or运算符和一个16进制常量0x02：currentFont.attribute=CurrentFont.attributeor0x02如果你够幸运的话，也可能代码会比这样还要干净些。但使用拼凑方法的话，你能得到的最好结果也就是写成这样：currentFont.attribute=CurrentFont.attributeorBOLD或者是这样：currentFont.bold=True就修改字体大小而言，这些做法都存在一个限制，即要求调用方代码直接控制数据成员，这无疑限制了currentFont的使用。如果你这么编写程序的话，程序中的很多地方就会到处充斥着类似的代码。BenefitsofUsingADTs使用ADT的益处问题并不在于拼凑法是种不好的编程习惯。而是说你可以采用一种更好的编程方法来替代这种方法，从而获得下面这些好处：可以隐藏实现细节把关于字体数据类型的信息隐藏起来，意味着如果数据类型发生改变，你只需在一处修改而不会影响到整个程序。例如，除非你把实现细节隐藏在一个ADT中，否则当你需要把字体类型从粗体的第一种表示变成第二种表示时，就不可避免地要更改程序中所有设置粗体字体的语句，而不能仅在一处进行修改。把信息隐藏起来能保护程序的其余部分不受影响。即使你想把在内存里存储的数据改为在外存里存储，或者你想把所有 *** 作字体的子程序用另一种语言重写，也都不会影响程序的其余部分。改动不会影响到整个程序如果想让字体更丰富，而且能支持 *** 作（例如变成小型大写字母、变成上标、添加删除线等）时，你只需在程序的一处进行修改即可。这一改动也不会影响到程序的其余部分。让接口能提供信息像currentFont.size=16这样的语句是不够明确的，因为此处16的单位既可能是像素也可能是磅。语句所处的上下文环境并不能告诉你到底是哪一种单位。把所有相似的 *** 作都集中到一个ADT里，就可以让你基于磅数或像素数来定义整个接口，或者把二者明确地区分开，从而有助于避免混淆。更容易提高性能如果你想提高 *** 作字体时的性能，就可以重新编写出一些更好的子程序，而不用来回修改整个程序。让程序的正确性更显而易见验证像currentFont.attribute=current-Font.attributeor0x02这样的语句是否正确是很枯燥的，你可以替换成像currentFont.SetBoldOn()这样的语句，验证它是否正确就会更容易一些。对于前者，你可能会写错结构体或数据项的名字，或者用错运算符（用了and而不是or），也可能会写错数值（写成了0x20而不是0x02）。但对于后者，在调用current-Font.SetBoldOn()时，唯一可能出错的地方就是写错方法（成员函数）名字，因此识别它是否正确就更容易一些。程序更具自我说明性你可以改进像currentFont.attributeor0x02这样的语句——把0x02换成BOLD或“0x02所代表的具体含义”，但无论怎样修改，其可读性都不如currentFont.SetBoldOn()这条语句。Woodfield、Dunsmore和Shen曾做过这样一项研究，他们让一些计算机科学专业的研究生和高年级本科生回答关于两个程序的问题：第一个程序按功能分解为8个子程序，而第二个程序分解为抽象数据类型中的8个子程序（1981）。结果，按那些使用抽象数据类型程序的学生的得分比使用按功能划分的程序的学生高出超过30%。无须在程序内到处传递数据在刚才那个例子里，你必须直接修改current-Font的值，或把它传给每一个要 *** 作字体的子程序。如果你使用了抽象数据类型，那么就不用再在程序里到处传递currentFont了，也无须把它变成全局数据。ADT中可以用一个结构体来保存currentFont的数据，而只有ADT里的子程序才能直接访问这些数据。ADT之外的子程序则不必再关心这些数据。你可以像在现实世界中那样 *** 作实体，而不用在底层实现上 *** 作它你可以定义一些针对字体的 *** 作，这样，程序的绝大部分就能完全以“真实世界中的字体”这个概念来 *** 作，而不再用数组访问、结构体定义、True与False等这些底层的实现概念了。这样一来，为了定义一个抽象数据类型，你只需定义一些用来控制字体的子程序——多半就像这样：currentFont.SetSizeInPoints(sizeInPoints)currentFont.SetSizeInPixels(sizeInPixels)currentFont.SetGBoldOn()currentFont.SetBoldOff()currentFont.SetItalicOn()currentFont.SetItalicOff()currentFont.SetTypeFace(faceName)这些子程序里的代码可能很短——很可能就像你此前看到的那个用拼凑法控制字体时所写的代码。这里的区别在于，你已经把对字体的 *** 作都隔离到一组子程序里了。这样就为需要 *** 作字体的其他部分程序提供了更好的抽象层，同时它也可以在针对字体的 *** 作发生变化时提供一层保护。

ADT是一些 *** 作的集合。抽象数据类型是数学的抽象，在ADT的定义中不涉及如何实现 *** 作的结合。

对诸如表、集合、图和它们的 *** 作一起可以看作是抽象数据类型，就像整数、实数是数据类型一样。对于集合ADT，可以有诸如并（union）、交（intersection）、获取大小（size）以及取余（complement）等 *** 作。

1）表ADT的数据结构

形如A1, A2, ..., An的表。表的大小是n。大小为0的表为空表。

对除空表外的任何表，说Ai+1后继Ai并称Ai-1前驱Ai。表中第一个元素是A1，最后一个元素是An。不定义A1的前驱元和An的后继元。元素Ai在表中的位置为i。

2）表ADT上进行的 *** 作的集合

表的大小实现需要已知（除非实现位动态数组）

插入和删除是昂贵的，最坏情况为O(N)

链表允许不连续存储。

链表有一系列不在内存中相连的结构组成。每一个结构均含有表元素和指向包含该元素后继元的结构的指针（Next指针）。

实现时，采用带有表头的链表：

1）链表的声明和一些简单的判断

2）查找

3）删除

4）插入

5）删除整个链表

使用数组（适合稠密）和链表（适合稀疏）实现。

栈是限制插入和删除只能在一个位置上进行的表，该位置是表的末端，叫做栈的顶。

任何实现表的方法都能实现栈。

通过在表顶端插入来实现push，通过删除表顶端元素实现pop。

针对括号类的检查：

后缀表达式： a b c * + d e * f + g * +

将中缀表达式 a + b * c + (d * e + f) * g

转成后缀表达式 a b c * + d e * f + g * +

a + b * c + (d * e + f) * g：

函数调用是，需要存储当前所有重要信息（活动记录、栈帧），诸如寄存器的值和返回地址。

将这些信息放到栈中，然后控制转移到新函数，新函数可以自由地用它的一些值代替这些寄存器。

栈溢出：许多系统中是不检测溢出的。由于有太多同时在运行着的函数，用尽栈空间情况总是可能发生的。

当栈太大是，可能触及到你的程序部分。

发生栈溢出一般是由失控递归（忘记基准情形）引起的。

消除递归一般方法是使用一个栈，而且仅当你能够把最低限度的最小值放到栈上时，这个方法才值得一用。

队列也是表，插入在一端（队尾rear），删除在另一端（对头front）。

同栈一样，任何表的实现都是合法的。

处理用概率的方法计算用户排队预计等待时间、等待服务的队列能够排多长，以及其他一些诸如此列的问题将用到被称为排队类的整个数学分支。

问题的答案依赖于用户加入队列的频率以及一旦用户得到服务时处理服务花费的时间。这两个参数作为概率分布函数给出。

如果有k个接线员，直接解决比较困难，可以用模拟的方法（使用一个队列）进行进行求解。

模拟方法：（当k变大时需要模拟）

将任务按照顺序放到一个队列中，用一个线程池（多个处理线程）轮流冲任务队列中取出任务进行处理。

散列(hashing)是一种用于以常数平均时间执行插入、删除、查找的技术。

那些需要元素间任何排序信息的 *** 作将不会得到有效支持。因此诸如FindMin、FindMax等 *** 作都是哈希表不支持的。

实现参见： http://www.jianshu.com/p/6dfd8c4c2b50

参见 http://www.jianshu.com/p/bdd7442f54e2

参考 红黑树专题

参考 2-3-4树及2-3树的总结

优先队列是允许至少下列两种 *** 作的数据结构：

1）Insert

2）DeleteMin 找出、返回和删除优先队列中最小的元素

参见 http://www.jianshu.com/p/f62787325788

一些应用涉及将n个元素分成一组不相交的集合。这些应用经常需要进行两种特别的 *** 作：寻找包含给定元素的唯一集合和合并两个集合。

支持以下三个 *** 作：

1）表示方法

每个集合用一个链表来表示。

2） *** 作

UNION的一种方法：总是将较短的表拼接到较长的链表中。

1）基础表示法

使用有根树来表示集合，树中每个结点包含一个成员，每棵树代表一个集合。

在一个不相交集合森林（disjoint-set forest）中，每个成员仅指向它的父节点。

2）按秩合并与路径压缩

3）运行时间分析

Abstract Data Type，抽象数据类型，是指数据结构作为一个软件组件的实现。ADT的接口用一种类型和该类型上的一组 *** 作来定义，每个 *** 作由它的输入和输出定义。

ADT并不会指定数据类型如何实现，这些实现细节对于ADT的用户来说是隐藏的，并且通过封装（encapsulation）来阻止外部对他的访问。

数据结构（Data Structure）是ADT的实现，在诸如c++之类的面向对象语言中，ADT及其实现组成了类（class）。同ADT联系在一起的每个 *** 作均由一个成员函数（member function）来实现。数据结构是指存储在计算机内存中的数据，文件结构是指外存储器中数据的组织。

对于使用同一ADT的两个应用程序，可能存在一个应用程序使用的ADT特殊方法比另一个多的情况或者这两个程序对该ADT的 *** 作有不同的时间需求。正是由于应用程序的需求存在差异，才使一个给定ADT有多种实现形式的可能性。

问题：从直觉上讲，问题无非是一个需要完成的任务，即一组输入就有一组对应的输出。

算法：算法是指解决问题的一种方法或者一个过程。

程序：一个计算机程序被认为是使用某种程序设计语言对一种算法的具体实现。

---