绪论..................................................................................................................................................... 5
0.1基本概念............................................................................................................................... 5
0.2算法和算法的衡量............................................................................................................... 5
习题............................................................................................................................................. 6
第一章线性表................................................................................................................................... 8
1.1线性表的定义....................................................................................................................... 8
1.2线性表的实现....................................................................................................................... 8
1.2.1线性表的顺序存储结构............................................................................................ 8
1.2.2线性表的链式存储结构.......................................................................................... 10
习题........................................................................................................................................... 15
第二章栈、队列和数组................................................................................................................. 20
2.1栈......................................................................................................................................... 20
2.1.1栈的定义.................................................................................................................. 20
2.1.2栈的存储实现和运算实现...................................................................................... 20
2.1.3栈的应用举例.......................................................................................................... 21
2.2队列..................................................................................................................................... 24
2.2.1队列的定义及基本运算.......................................................................................... 24
2.2.2队列的存储实现及运算实现 .................................................................................. 24
2.3特殊矩阵的压缩存储......................................................................................................... 26
2.3.1数组.......................................................................................................................... 26
2.3.2特殊矩阵.................................................................................................................. 27
习题........................................................................................................................................... 29
第三章树与二叉树......................................................................................................................... 32
3.1树的概念............................................................................................................................. 32
3.2二叉树................................................................................................................................. 32
3.2.1定义与性质.............................................................................................................. 32
3.2.2二叉树的存储.......................................................................................................... 34
3.2.3二叉树的遍历.......................................................................................................... 35
3.2.4线索二叉树.............................................................................................................. 38
3.3树和森林............................................................................................................................. 41
3.3.1树的存储结构.......................................................................................................... 41
3.3.2森林和二叉树的转换.............................................................................................. 42
3.3.3树和森林的遍历...................................................................................................... 42
3.4哈夫曼（Huffman）树和哈夫曼编码............................................................................... 43
习题........................................................................................................................................... 44
第四章图......................................................................................................................................... 46
4.1图的概念............................................................................................................................. 46
4.2图的存储及基本操作......................................................................................................... 47
4.2.1邻接矩阵.................................................................................................................. 47
4.2.2邻接表...................................................................................................................... 48
4.3图的遍历............................................................................................................................. 49
4.3.1深度优先搜索.......................................................................................................... 49
4.3.2广度优先搜索.......................................................................................................... 50
4.4图的基本应用..................................................................................................................... 51
4.4.1最小生成树.............................................................................................................. 51
4.4.2最短路径.................................................................................................................. 52
4.4.3拓扑排序.................................................................................................................. 54
4.4.4关键路径.................................................................................................................. 55
习题........................................................................................................................................... 56
第五章查找..................................................................................................................................... 58
5.1查找的基本概念................................................................................................................. 58
5.2顺序查找法......................................................................................................................... 58
5.3折半查找法......................................................................................................................... 59
5.4动态查找树表..................................................................................................................... 60
5.4.1二叉排序树.............................................................................................................. 60
5.4.2平衡二叉树.............................................................................................................. 62
5.4.3B树及其基本操作、B+树的基本概念................................................................... 65
5.5散列表................................................................................................................................. 66
5.5.1散列表与散列方法.................................................................................................. 66
5.5.2常用的散列函数...................................................................................................... 66
5.5.3处理冲突的方法...................................................................................................... 67
5.5.4散列表的查找.......................................................................................................... 68
5.5.5散列表的查找分析.................................................................................................. 68
习题........................................................................................................................................... 69
第六章排序..................................................................................................................................... 71
6.1排序的基本概念................................................................................................................. 71
6.2插入排序............................................................................................................................. 71
6.2.1直接插入排序.......................................................................................................... 71
6.2.2折半插入排序.......................................................................................................... 72
6.3冒泡排序............................................................................................................................. 72
6.4简单选择排序..................................................................................................................... 73
6.5希尔排序............................................................................................................................. 73
6.6快速排序............................................................................................................................. 74
6.7堆排序................................................................................................................................. 76
6.8二路归并排序..................................................................................................................... 77
6.9基数排序............................................................................................................................. 78
6.10各种内部排序算法的比较............................................................................................... 79
习题........................................................................................................................................... 80
