第九章：抽象数据类型和算法

这一节比较重要，涉及如下知识点：

- 抽象数据类型(ADT)的概念
- 数据类型和数据结构
- 数组的实现，链表的实现
- 数组和列表
- 有序列表和无序列表
- 选择排序、冒泡排序、快速排序等算法
- 应用二分检索法
- 堆栈和队列的行为
- 二叉检索树

下面涉及的代码大多数用伪代码表示，也有用C表示的，主要融合了自己的观点和代码片段。

# 一. 抽象数据类型
>抽象数据类型需要通过固有数据类型（高级编程语言中已实现的数据类型）来实现。抽象数据类型是与表示无关的数据类型，是一个数据模型及定义在该模型上的一组运算。对一个抽象数据类型进行定义时，必须给出它的名字及各运算的运算符名，即函数名，并且规定这些函数的参数性质。一旦定义了一个抽象数据类型及具体实现，程序设计中就可以像使用基本数据类型那样，十分方便地使用抽象数据类型。

- 数据类型：一组值和能应用这组类型的值的基本操作，有点拗口，其实就是值和对应类型的操作
- 抽象数据类型： 比数据类型多了个*抽象*，它是**属性(数据和操作)明确地与实现分离的数据类型**

# 二. 数组VS列表

**列表**就是一个大容器，可以有序和无序，其表示形式有两种：**数组**和**链表**，栈和队列是两种特殊类型的列表。**

由此可见列表和数组的本质区别。列表是数据集合的统称，而数组是列表在结构上的具体表现形式。在不同的语言中，列表的概念可能有不同的讲法，所以不能一概而论！**

# 三.链式实现

>链表（Linked list）是一种常见的基础数据结构，是一种**线性表**，但是并不会按线性的顺序存储数据，而是**在每一个节点里存到下一个节点的指针(Pointer)**。由于不必须按顺序存储，**链表在插入的时候可以达到O(1)**的复杂度，比另一种线性表顺序表快得多，但是**查找一个节点或者访问特定编号的节点则需要O(n)**的时间，**而顺序表相应的时间复杂度分别是O(logn)和O(1)。**

使用链表结构可以**克服数组链表需要预先知道数据大小的缺点，链表结构可以充分利用计算机内存空间，实现灵活的内存动态管理。但是链表失去了数组随机读取的优点，同时链表由于增加了结点的指针域，空间开销比较大。**

链表有很多种不同的类型：单向链表，双向链表以及循环链表。

## 3.1 单向链表
链表中最简单的一种是单向链表，它包含两个域，一个信息域和一个指针域。这个链接指向列表中的下一个节点，而最后一个节点则指向一个空值。

![](https://raw.githubusercontent.com/BeginMan/BookNotes/master/CS/media/cs14.png)

## 3.2 双向链表
每个节点有两个连接：一个指向前一个节点，（当此“连接”为第一个“连接”时，指向空值或者空列表）；而另一个指向下一个节点，（当此“连接”为最后一个“连接”时，指向空值或者空列表）

![](https://raw.githubusercontent.com/BeginMan/BookNotes/master/CS/media/cs15.png)

## 3.3 循环链表
在一个 循环链表中, 首节点和末节点被连接在一起。这种方式在单向和双向链表中皆可实现。要转换一个循环链表，你开始于任意一个节点然后沿着列表的任一方向直到返回开始的节点。再来看另一种方法，循环链表可以被视为“无头无尾”。这种列表很利于节约数据存储缓存， 假定你在一个列表中有一个对象并且希望所有其他对象迭代在一个非特殊的排列下。

![](https://raw.githubusercontent.com/BeginMan/BookNotes/master/CS/media/cs16.png)

# 四. 排序算法
介绍几种常见的排序：选择排序，冒泡排序，快速排序

# 五. 堆栈与队列&二叉检索树
todo：补充中..

ref:

1. [百度百科 抽象数据类型](http://baike.baidu.com/view/178593.htm)
2. [列表和数组的区别](http://lionbule.iteye.com/blog/1327592)
3. [wiki 链表](https://zh.wikipedia.org/zh/%E9%93%BE%E8%A1%A8)
