第1章 绪论 1
1.1数据结构概述 1
1.2基本概念和术语 4
1.3算法和算法分析 6
1.3.1算法的特性 6
1.3.2算法的描述方法 6
1.3.3算法性能分析与度量 9
本章小结 10
习题一 10
第2章 线性表 13
2.1线性表的基本概念 13
2.2线性表的存储结构 15
2.2.1线性表的顺序存储结构 15
2.2.2线性表的链式存储结构 19
2.3循环链表 26
2.4双向链表 27
2.5单链表应用举例 28
2.6一元多项式的表示及相加 30
本章小结 31
习题二 32
第3章 栈和队列 34
3.1栈 34
3.1.1栈的定义 34
3.1.2栈的存储结构 35
3.1.3栈的应用举例 37
3.2队列 44
3.2.1队列的定义 44
3.2.2队列的存储结构 45
3.2.3队列应用举例 50
本章小结 52
习题三 53
第4章串 55
4.1串的基本概念 55
4.2串的顺序存储结构 57
4.3串的链式存储结构 63
4.4串的堆存储结构 64
4.4.1串名的存储映像 64
4.4.2堆存储结构 65
4.4.3基于堆结构的基本运算 65
本章小结 67
习题四 67
第5章 数组和广义表 69
5.1数组的基本概念 69
5.2数组的顺序存储 69
5.3矩阵的压缩存储 72
5.3.1特殊矩阵 72
5.3.2稀疏矩阵 74
5.4广义表 79
5.4.1广义表的基本概念 80
5.4.2广义表的存储结构 81
5.4.3广义表基本操作的实现 83
本章小结 85
习题五 86
第6章 树和二叉树 88
6.1树的基本概念 88
6.1.1树的定义 88
6.1.2树的表示 89
6.1.3树的基本术语 90
6.2二叉树 90
6.2.1二叉树的定义和基本操作 90
6.2.2二叉树的性质 91
6.2.3二叉树的存储结构 94
6.3二叉树的运算 95
6.3.1二叉树的基本操作 95
6.3.2遍历二叉树 97
6.3.3线索二叉树 98
6.4树和森林 101
6.4.1树的存储结构 101
6.4.2树、森林和二叉树的转换 103
6.4.3树和森林的遍历 105
6.5哈夫曼树及其应用 106
6.5.1哈夫曼树 106
6.5.2哈夫曼编码 107
本章小结 110
习题六 110
第7章图 112
7.1图的定义和术语 112
7.2图的存储结构 115
7.2.1邻接矩阵 115
7.2.2邻接表和逆邻接表 118
7.2.3十字链表 120
7.2.4邻接多重表 121
7.3图的遍历 123
7.3.1深度优先搜索遍历 123
7.3.2广度优先搜索遍历 124
7.4生成树和最小生成树 125
7.4.1基本概念 125
7.4.2普里姆算法 127
7.4.3克鲁斯卡尔算法 128
7.5有向无环图及其应用 130
7.5.1 AOV网与拓扑排序 130
7.5.2 AOE网与关键路径 132
7.6最短路径 134
7.6.1从某一顶点到其余各顶点的最短路径 135
7.6.2每对顶点之间的最短路径 137
本章小结 139
习题七 139
第8章 查找 141
8.1查找的基本概念 141
8.2静态查找表 142
8.2.1顺序查找 142
8.2.2折半查找 144
8.2.3索引查找 146
8.3动态查找表 147
8.3.1二叉排序树和平衡二叉树 147
8.3.2 B-树 156
8.4哈希表 160
8.4.1哈希函数 160
8.4.2哈希函数的构造方法 161
8.4.3处理冲突的方法 162
8.4.4哈希表的查找 164
本章小结 164
习题八 165
第9章 排序 167
9.1排序的定义 167
9.2插入排序 168
9.2.1直接插入排序 168
9.2.2希尔排序 170
9.3交换排序 172
9.3.1冒泡排序 172
9.3.2快速排序 173
9.4选择排序 175
9.4.1简单选择排序 175
9.4.2树形选择排序 175
9.4.3堆排序 176
9.5二路归并排序 178
9.6基数排序 179
9.6.1多关键字排序 180
9.6.2链式基数排序 180
9.7各种内部排序方法的比较 183
9.8外部排序 184
9.8.1外部排序的方法 184
9.8.2多路平衡归并的实现 185
本章小结 187
习题九 187
参考文献 189