第一章 线性表 1
1.1线性表及表的基本运算 1
1.1.1线性表 1
1.1.2线性表的基本运算 2
1.2线性表的顺序存贮 3
1.2.1顺序存贮的数组实现 3
1.2.2插入、删除与定位算法 5
1.2.3例——多项式的顺序存贮 9
1.3顺序存贮的栈和队列 14
1.3.1栈的概念及其基本操作 14
1.3.2多个栈共享邻接空间 18
1.3.3队列概念及其基本操作 21
1.3.4环形队列及其插入、删除算法 25
1.4.1迷宫问题 27
1.4栈的应用举例 27
1.4.2计算算术表达式的值 34
1.4.3栈与递归 44
1.5线性表的链接存贮 53
1.5.1线性链表 53
1.5.2线性链表的插入与删除 55
1.5.3链接栈与链接队列 61
1.5.4可利用栈 63
1.5.5链接存贮的应用——多项式相加 65
1.5.6环形链表和双向链表 70
1.6线性表的其他存贮方式 76
1.6.1压缩存贮 76
1.6.2索引存贮 79
1.6.3散列存贮 84
1.7线性表的查找 85
1.7.1顺序查找法 86
1.7.2二分查找法 88
1.7.3分块查找法 90
习题 92
第二章 数组 96
2.1数组的顺序分配 96
2.1.1二维数组的顺序分配 96
2.1.2三角矩阵与带状矩阵 97
2.1.3多维数组 101
2.2稀疏矩阵 104
2.2.1三元组表示法 105
2.2.2三元组表示的运算——矩阵的转置 106
2.2.3链接存贮——十字链表 110
2.2.4十字链表表示的稀疏矩阵的运算 112
习题 120
3.1串的基本概念 122
第三章 串 122
3.2串的存贮结构 123
3.2.1顺序存贮 123
3.2.2链接存贮 125
3.3串的运算 126
3.4模式匹配 128
习题 134
第四章 内部排序 135
4.1插入排序（insertionsort） 136
4.2选择排序（selectionsort） 138
4.3冒泡排序（bubblesort） 139
4.4希尔排序（Shellsort） 141
4.5合并排序（mergesort） 144
4.5.1排序文件的合并 144
4.5.2两路合并排序 145
4.6快速排序（quicksort） 147
4.7基数排序（radixsort） 150
4.7.1基数排序 151
4.7.2多关键字排序 155
4.8排序可能达到的速度 155
4.9用链表处理的重排算法 156
4.9.1链表排序的重排 156
4.9.2表格排序的重排 162
习题 166
第五章 树 168
5.1树的基本概念 168
5.2树的存贮结构 172
5.3树的遍历 178
5.4树的线性表示 182
5.5二叉树 186
5.6二叉树的遍历 191
5.7.1按层次的存贮形式 200
5.7二叉树的顺序存贮 200
5.7.2按前序的存贮形式 201
5.8穿线树 208
习题 219
第六章 图 222
6.1定义 222
6.2图的存贮结构 224
6.2.1邻接矩阵 224
6.2.2邻接表 225
6.3图的遍历与求图的连通分量 228
6.3.1深度优先搜索法 229
6.3.2广度优先搜索法 231
6.3.3求图的？？分量 233
6.4生成树和最小（代价）生成树 234
6.5最短路径和传递闭包 239
6.5.1从某个源点到其他各顶点的最短路径 240
6.5.2求每一对顶点之间的最短路径 244
6.5.3传递闭包 247
6.6拓扑排序 250
6.6.1拓扑排序的定义 250
6.6.2拓扑排序 251
6.7关键路径 256
习题 264
第七章 查找 268
7.1查找树 268
7.2丰满树和平衡树 276
7.3最佳查找树 290
7.4Huffman算法和Hu-Tucker算法 298
7.5B——树 305
7.6Trie结构的查找 314
7.7解答树 319
7.7.1背包问题 320
7.7.2？后问题 330
7.8HASH查找 336
7.8.1HASH函数 337
7.8.2解决冲突的方法 338
习题 344
第八章 外部排序 346
8.1外部存贮设备 346
8.1.1磁带存贮设备 346
8.1.2磁盘存贮设备 349
8.2磁盘文件的排序 349
8.3磁带文件的排序 354
8.3.1平衡合并排序 356
8.3.2多阶段合并排序 357
习题 364
参考文献 365