基本数据结构ADT及其实现

Answer 1

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）运行时间分析