目　录

第 1章　绪论　1
1.1　问题的引入　1
1.1.1　引言　1
1.1.2　数据结构课程研究内容　2
1.2　数据结构的基本概念　3
1.2.1　计算机领域中的数据　3
1.2.2　数据结构相关概念　4
1.3　抽象数据类型　5
1.3.1　数据类型　5
1.3.2　抽象数据类型　6
1.3.3　抽象数据类型的实现　8
1.4　C++语言　10
1.4.1　函数模板与函数重载　10
1.4.2　结构体及运用　14
1.4.3　类的基本概念及运用　16
1.5　算法描述与分析　19
1.5.1　什么是算法　19
1.5.2　算法描述工具——C++语言　20
1.5.3　算法分析技术　22
1.6　小结　25
习题1　26

第 2章　线性表　28
2.1　线性表的基本概念　28
2.1.1　线性表的定义　28
2.1.2　线性表的抽象数据类型　29
2.2　线性表的顺序存储结构及实现　29
2.2.1　线性表的顺序存储结构　29
2.2.2　顺序表类定义　31
2.2.3　顺序表的插入和删除　32
2.2.4　线性表的其他运算　36
2.3　线性表的链表存储结构及实现　37
2.3.1　单链表与指针　37
2.3.2　单链表类定义　40
2.3.3　链表的插入和删除　42
2.3.4　单链表的其他运算　47
2.4　循环链表和双向链表　50
2.4.1　循环链表　50
2.4.2　双向链表　51
2.4.3　顺序结构与链表结构的分析比较　53
2.5　一元多项式相加问题　53
2.5.1　多项式的链表存储结构　53
2.5.2　多项式相加的实现　54
2.6　线性表的C++源程序　55
2.6.1　顺序表类的实现　56
2.6.2　单链表类实现通信录问题　57
2.7　小结　61
习题2　61

第3章　栈和队列　63
3.1　栈　63
3.1.1　栈的定义　63
3.1.2　栈的抽象数据类型　64
3.2　栈的顺序存储结构及实现　65
3.2.1　栈的顺序存储结构　65
3.2.2　顺序栈类定义　66
3.3　栈的链表存储结构及实现　68
3.3.1　栈的链表存储结构　68
3.3.2　链表栈类定义　69
3.4　栈的应用　71
3.4.1　表达式的计算　71
3.4.2　子程序的嵌套调用　74
3.4.3　递归调用　74
3.4.4　n阶Hanoi塔问题　75
3.5　队列　77
3.5.1　队列的定义　77
3.5.2　队列的抽象数据类型　77
3.6　队列的顺序存储结构及实现　78
3.6.1　队列的顺序存储结构　78
3.6.2　循环队列类定义　80
3.7　队列的链表存储结构及实现　82
3.7.1　队列的链表存储结构　82
3.7.2　链表队列类定义　83
3.8　队列的应用　85
3.9　栈和队列的C++源程序　86
3.9.1　链表栈类的实现　86
3.9.2　链表队列类实现报数问题　88
3.10　小结　90
习题3　91

第4章　串　93
4.1　串的基本概念　93
4.1.1　串的定义　93
4.1.2　串的抽象数据类型　94
4.1.3　常用字符串函数　94
4.2　串的存储表示　95
4.2.1　串的定长顺序存储表示　95
4.2.2　串的堆分配存储表示　96
4.2.3　串的块链存储表示　96
4.3　串类及实现　97
4.3.1　串的类定义　98
4.3.2　串基本运算的实现　99
4.4　串的模式匹配　101
4.4.1　朴素模式匹配　101
4.4.2　KMP模式匹配　102
4.5　串的模式匹配C++源程序　106
4.6　小结　109
习题4　109

第5章　数组和广义表　110
5.1　数组的基本概念　110
5.1.1　数组的定义　110
5.1.2　数组的顺序表示　113
5.2　特殊矩阵　114
5.3　稀疏矩阵　117
5.3.1　数组元素的三元组　117
5.3.2　三元组顺序表　118
5.3.3　十字链表　123
5.4　迷宫问题　128
5.5　广义表　132
5.5.1　广义表的基本概念　132
5.5.2　广义表的存储结构　133
5.5.3　广义表类定义　136
5.6　矩阵运算和广义表的C++源程序　140
5.6.1　三元组表实现稀疏矩阵加法　140
5.6.2　头尾链表结构实现广义表　143
5.7　小结　145
习题5　145

第6章　树与二叉树　147
6.1　树的基本概念和术语　147
6.1.1　树的定义　147
6.1.2　树的抽象数据类型　148
6.1.3　树的表示形式　149
6.2　二叉树　149
6.2.1　二叉树的定义和性质　149
6.2.2　二叉树的存储结构　152
6.2.3　二叉树的二叉链表类定义　153
6.3　遍历二叉树　156
6.3.1　先根遍历　157
6.3.2　中根遍历　158
6.3.3　后根遍历　159
6.3.4　按层遍历　161
6.3.5　二叉树遍历算法的应用　162
6.4　线索二叉树　165
6.4.1　线索二叉树的基本概念　165
6.4.2　线索二叉树的逻辑表示图　166
6.4.3　线索化二叉树类　167
6.4.4　在中根线索树上查找前驱和后继　170
6.4.5　遍历中根线索二叉树　171
6.5　二叉树、树和森林　172
6.5.1　树的存储结构　172
6.5.2　树与二叉树的转换　173
6.5.3　森林与二叉树的转换　175
6.6　树和森林的孩子——兄弟表示及遍历　176
6.6.1　一般树的遍历　176
6.6.2　森林的遍历　178
6.7　树的应用　179
6.7.1　二叉排序树　179
6.7.2　哈夫曼树及应用　184
6.8　二叉树的C++源程序　189
6.8.1　二叉树的建立和遍历　189
6.8.2　哈夫曼树与编码　191
6.9　小结　193
习题6　193

第7章　图　195
7.1　图的基本概念　195
7.1.1　图的定义　195
7.1.2　图的术语　196
7.1.3　图的抽象数据类型　198
7.2　图的存储结构　199
7.2.1　图的邻接矩阵　199
7.2.2　图的邻接矩阵类　200
7.2.3　图的邻接链表　202
7.2.4　图的邻接链表类　203
7.3　图的遍历与图的连通性　207
7.3.1　图的深度优先遍历　207
7.3.2　图的广度优先遍历　209
7.3.3　非连通图和连通分量　211
7.4　图的**小生成树　212
7.4.1　**小生成树的概念　212
7.4.2　普里姆算法　213
7.4.3　克鲁斯卡尔算法　215
7.5　**短路径　216
7.5.1　单源顶点**短路径　216
7.5.2　每对顶点之间的**短路径　218
7.6　拓扑排序与关键路径　220
7.6.1　拓扑排序　220
7.6.2　关键路径　223
7.7　图的C++源程序　228
7.8　小结　231
习题7　231

第8章　查找　233
8.1　查找的基本概念　233
8.2　静态查找表　234
8.2.1　顺序表的查找　235
8.2.2　有序表的折半查找　236
8.2.3　静态索引结构　239
8.3　动态查找表　241
8.3.1　二叉排序树　241
8.3.2　平衡二叉树及动态平衡技术　245
8.3.3　B-树　247
8.3.4　B+树　251
8.4　哈希表及其查找　252
8.4.1　哈希表与哈希函数　252
8.4.2　构造哈希函数的常用方法　253
8.4.3　解决冲突的主要方法　255
8.4.4　哈希查找效率分析　261
8.5　查找的C++源程序　262
8.5.1　二叉排序树查找　262
8.5.2　哈希表及其查找　264
8.6　小结　266
习题8　267

第9章　排序　269
9.1　排序的基本概念　269
9.2　插入排序　270
9.2.1　直接插入排序　270
9.2.2　折半插入排序　271
9.2.3　希尔排序　272
9.3　交换排序　274
9.3.1　冒泡排序　274
9.3.2　快速排序　275
9.4　选择排序　279
9.4.1　简单选择排序　279
9.4.2　堆排序　279
9.5　归并排序　283
9.6　基数排序　285
9.7　排序的C++源程序　288
9.8　小结　290
习题9　291

第 10章　典型数据结构类模板　293
10.1　顺序栈类模板　293
10.2　循环队列类模板　295
10.3　使用类模板　297

第 11章　数据结构程序设计　298
11.1　从问题到程序的一般过程　298
11.1.1　问题分析　298
11.1.2　初步设计　298
11.1.3　程序编码　299
11.1.4　上机调试　299
11.1.5　实验报告　300
11.2　程序实例　301
11.2.1　统计短文中各字母的频度　301
11.2.2　城市间交通图**短路径问题　305

参考文献　312