9.7 小结

9.7 小结

数据结构是计算机科学的重要分支。选择合适的数据结构，可以简化问题，减少时间的浪费。
1. 线性表
线性表有两种存储方式，一种是顺序存储，另一种是链式存储。前者只需用一维数组实现，而后者既可以用数组实现，又可以用指针实现。
顺序表的特点是占用空间较小，查找和定位的速度很快，但是插入和删除元素的速度很慢（在尾部速度快）；链表和顺序表正好相反，它的元素插入和删除速度很快，但是查找和定位的速度很慢（同样，在首尾速度快）。
2. 栈和队列
栈和队列以线性表为基础。它们的共同点是添加、删除元素都有固定顺序，不同点是删除元素的顺序。队列从表头删除元素，而栈从表尾删除元素，所以说队列是先进先出表，堆栈是先进后出表。
栈和队列在搜索中有非常重要的应用。栈可以用来模拟深度优先搜索，而广度优先搜索必须用队列实现。
有时为了节省空间，栈的两头都会被利用，而队列会被改造成循环队列。
3. 二叉树
上面几种数据结构都是线性结构。而二叉树是一种很有用的非线性结构。二叉树可以采用以下的递归定义：
二叉树要么为空，要么由根结点、左子树和右子树组成。左子树和右子树分别是一棵二叉树。

计算机中的树和现实生活不同——计算机里的树是倒置的，根在上，叶子在下。
完全二叉树：一个完全二叉树的结点是从上到下、从左到右地填充的。如果高度为 h，那么 0～h-1 层一定已经填满，而第 h 层一定是从左到右连续填充的。
通常情况下，二叉树用指针实现。对于完全二叉树，可以用一维数组实现（事先从 0 开始编号）。
访问二叉树的所有结点的过程叫做二叉树的遍历。常用的遍历方式有前序遍历、中序遍历、后序遍历，它们都是递归完成的。
4. 树
树也可以采用递归定义：树要么为空，要么由根结点和 n（n≥0）棵子树组成。
森林由 m（m≥0）棵树组成。
二叉树不是树的一种，因为二叉树的子树中有严格的左右之分，而树没有。这样，树可以用父结点表示法来表示（当然，森林也可以）。并查集的合并、查询速度很快，它就是用父结点表示法实现的。
不过父结点表示法的遍历比较困难，所以常用“左儿子右兄弟”表示法把树转化成二叉树。
树的遍历和二叉树的遍历类似，不过不用中序遍历。它们都是递归结构，所以可以在上面实施动态规划。
树作为一种特殊的图，在图论中也有广泛应用。
树的表示方法有很多种。第一种是父节点表示法，它适合并查算法，但不便遍历。
第二种是子节点表表示法：

 

 

 第三种是“左儿子右兄弟”表示法：