第1章 绪论 1
1.1数据结构的概念 1
1.1.1数据结构的重要性 1
1.1.2基本概念和术语 3
1.1.3数据结构课程的形成和发展 6
1.2抽象数据类型 7
1.2.1数据类型 7
1.2.2抽象数据类型 7
1.3算法和算法分析 8
1.3.1算法的特性 8
1.3.2算法设计的要求 9
1.3.3算法的性能分析与度量 9
小结 11
习题1 12
实训1熟悉基本编程 15
第2章 线性表 16
2.1线性表的逻辑结构 16
2.1.1线性表的定义 16
2.1.2线性表的基本操作 17
2.2线性表的顺序存储结构及运算 18
2.2.1顺序表 18
2.2.2顺序表基本运算的实现 19
2.2.3顺序表的应用举例 22
2.3线性表的链式存储结构及运算 24
2.3.1单链表 24
2.3.2单链表基本运算的实现 26
2.3.3循环链表 30
2.3.4双向链表 31
2.3.5静态链表 32
2.3.6链表的应用举例 35
小结 36
习题2 37
实训2一元多项式的表示 44
第3章栈和队列 45
3.1栈 45
3.1.1栈的定义及基本运算 45
3.1.2顺序栈基本运算的实现 46
3.1.3栈的应用举例 50
3.2递归 53
3.3队列 55
3.3.1 队列的定义及基本运算 55
3.3.2循环队列基本运算的实现 56
3.3.3链队列基本运算的实现 60
3.3.4队列应用举例 62
小结 63
习题3 64
实训3栈和队列的抽象数据类型实现 71
第4章串、数组和广义表 72
4.1串 72
4.1.1串的定义和基本运算 72
4.1.2串的存储 75
4.1.3串的模式匹配算法 79
4.2数组 83
4.2.1数组的定义和存储结构 83
4.2.2矩阵的压缩存储 85
4.3广义表 92
4.3.1广义表的定义和基本运算 92
4.3.2广义表的存储结构 93
小结 95
习题4 96
实训4矩阵和数组的应用与实现 103
第5章 树和二叉树 104
5.1树 104
5.1.1树的定义 104
5.1.2树的其他表示方式 105
5.1.3树的基本术语 105
5.2二叉树 107
5.2.1二叉树的定义 107
5.2.2二叉树的性质 109
5.2.3二叉树的基本操作 110
5.3二叉树的存储 112
5.3.1顺序存储结构 112
5.3.2链式存储结构 113
5.4二叉树的遍历 115
5.4.1二叉树的遍历方法 115
5.4.2二叉树遍历的递归实现 117
5.4.3二叉树遍历的应用 118
5.4.4二叉树遍历的非递归实现 121
5.4.5二叉树的层次遍历 124
5.5线索二叉树 124
5.5.1线索二叉树的定义 125
5.5.2线索二叉树的操作 126
5.6哈夫曼树 128
5.6.1哈夫曼树 128
5.6.2哈夫曼树在判定问题中的应用 131
5.6.3哈夫曼编码 132
5.7树和森林 135
5.7.1树的存储 135
5.7.2树和二叉树的转换 138
5.7.3森林和二叉树的转换 140
5.7.4树和森林的遍历 141
小结 142
习题5 143
实训5二叉树的常见操作 151
第6章 图 152
6.1图的定义 152
6.1.1图的概述 152
6.1.2图的定义 153
6.1.3图的抽象数据类型 155
6.2图的存储结构 156
6.2.1邻接矩阵 157
6.2.2邻接表 158
6.2.3十字链表 161
6.2.4邻接多重表 163
6.3图的遍历 164
6.3.1深度优先搜索遍历 164
6.3.2广度优先搜索遍历 166
6.3.3图的遍历生成树 168
6.3.4图的连通分量 169
6.4最小生成树 170
6.4.1普里姆（Prim）算法 171
6.4.2克鲁斯卡尔（Kruskal）算法 173
6.5图的关键路径 176
6.5.1拓扑排序 176
6.5.2关键路径 179
6.6图的最短路径 183
6.6.1单源最短路径 184
6.6.2任意顶点之间的最短路径 187
小结 189
习题6 190
实训6图的遍历 198
第7章 查找 199
7.1查找的基本概念 199
7.2静态查找表 202
7.2.1顺序查找 202
7.2.2折半查找 203
7.2.3插值查找和斐波那契查找 207
7.2.4索引查找 208
7.3动态查找表 209
7.3.1 二叉排序树 209
7.3.2平衡二叉树 214
7.3.3 B-树和B+树 224
7.4哈希表查找 236
7.4.1哈希表的概念 236
7.4.2哈希函数的构造方法 237
7.4.3处理冲突的方法 240
7.4.4哈希表的查找及性能分析 242
小结 244
习题7 245
实训7常见查找方法的实现 252
第8章 排序 253
8.1排序的基本概念 253
8.2插入排序 255
8.2.1直接插入排序 255
8.2.2其他插入排序 257
8.2.3希尔排序 262
8.3交换排序 264
8.3.1冒泡排序 264
8.3.2快速排序 266
8.4选择排序 271
8.4.1简单选择序 271
8.4.2堆排序 272
8.5归并排序 277
8.6基数排序 281
8.7内部排序的比较 286
8.8外部排序 288
8.8.1外部排序的方法 288
8.8.2多路平衡归并的实现 289
小结 292
习题8 293
实训8常见内部排序方法的实现 299
附录 300
附录一“数据结构”课程设计大纲 300
附录二课程设计参考题目 301
附录三2011年全国计算机专业统考大纲数据结构部分 305
附录四ACM简介 308
参考文献 311