第1章 数据结构与算法 1
1.1引言 1
1.1.1为什么要学习数据结构 1
1.1.2数据结构课程的内容 4
1.2数据结构的概念 4
1.2.1基本概念和术语 4
1.2.2抽象数据类型 7
1.3数据结构的描述方法 8
1.3.1数据结构的C语言描述 8
1.3.2数据结构的C+++语言描述 9
1.3.3数据结构的Java语言描述 10
1.4算法 11
1.4.1算法及其特征 11
1.4.2算法的描述 12
1.4.3算法的性能分析 12
1.5典型例题 15
1.6本章小结 16
1.6.1知识点小结 16
1.6.2扩展学习导读 17
练习题 17
实验题 18
题目1比较算法复杂性描述函数的增长 18
题目2矩阵连乘算法的时间和空间复杂度 18
第2章 递归 19
2.1引言 19
2.1.1问题的提出 19
2.1.2什么是递归 19
2.2递归调用的实现原理 20
2.2.1递归算法的构成 20
2.2.2递归调用的内部过程 21
2.2.3递归的正确性证明 22
2.3递归转化为非递归 22
2.3.1递归转化为递推 22
2.3.2递归转化为回溯 23
2.3.3手工模拟递归 23
2.4典型例题 24
2.5本章小结 26
2.5.1知识点小结 26
2.5.2扩展学习导读 26
练习题 27
实验题 27
题目1全排列的递归实现 27
题目2八皇后问题 28
题目3比较递归与非递归算法的时空效率 28
第3章 线性结构 29
3.1引言 29
3.1.1问题的提出 29
3.1.2线性表的定义 30
3.1.3线性表的基本运算 30
3.2线性表的顺序存储与实现 31
3.2.1顺序表 31
3.2.2顺序表上基本运算的实现 33
3.2.3顺序表应用举例 36
3.3线性表的链式存储与实现 38
3.3.1单链表 38
3.3.2单链表上基本运算的实现 40
3.3.3循环链表 46
3.3.4双向链表 47
3.3.5链表应用举例 49
3.4顺序表和链表的比较 52
3.5堆栈 53
3.5.1堆栈的定义及基本运算 53
3.5.2堆栈的存储及运算实现 53
3.5.3堆栈的应用举例 57
3.6队列 66
3.6.1队列的定义及基本运算 66
3.6.2队列的存储及运算实现 67
3.6.3队列的应用举例 73
3.7其他线性结构及扩展 76
3.7.1字符串 76
3.7.2数组 81
3.7.3特殊矩阵 83
3.7.4稀疏矩阵 86
3.8典型例题 90
3.9本章小结 100
3.9.1知识点小结 100
3.9.2扩展学习导读 102
练习题 103
实验题 105
题目1 Josephus环问题 105
题目2一元多项式运算 106
题目3模拟停车场管理 107
第4章 树结构 109
4.1引言 109
4.1.1问题提出 109
4.1.2相关概念 110
4.2二叉树 113
4.2.1二叉树的基本运算 113
4.2.2二叉树的主要性质 114
4.2.3二叉树的存储 115
4.2.4二叉树基本运算的实现 118
4.3二叉树的遍历 120
4.3.1递归方法实现二叉树遍历 120
4.3.2非递归方法实现二叉树的三种遍历 122
4.3.3按层次遍历二叉树 125
4.4二叉树遍历的应用 126
4.4.1构造二叉树的二叉链表存储 126
4.4.2在二叉树中查找值为x的数据元素 127
4.4.3统计给定二叉树中叶子结点的数目 127
4.4.4表达式运算 128
4.4.5由遍历序列恢复二叉树 128
4.5线索二叉树 130
4.5.1线索二叉树的定义及其结构 130
4.5.2线索二叉树的创建 132
4.5.3线索二叉树的遍历 133
4.6最优二叉树 136
4.6.1最优二叉树的概念 136
4.6.2最优二叉树的构造 138
4.6.3最优二叉树的应用——哈夫曼编码 140
4.7树 143
4.7.1树的基本操作 143
4.7.2树的表示 143
4.7.3树的存储 144
4.7.4树和森林与二叉树之间的转换 148
4.7.5树或森林的遍历 150
4.7.6树的应用 151
4.8典型例题 152
4.9本章小结 163
4.9.1知识点小结 163
4.9.2扩展学习导读 165
练习题 166
实验题 168
题目 哈夫曼编码/译码器 168
第5章 图结构 170
5.1引言 170
5.1.1问题的提出 170
5.1.2相关概念 171
5.1.3图的基本操作 173
5.2图的存储 174
5.2.1邻接矩阵 174
5.2.2邻接表 176
5.3图的遍历 179
5.3.1深度优先搜索 179
5.3.2广度优先搜索 181
5.3.3遍历图的简单应用 183
5.4生成树和最小生成树 184
5.4.1生成树和生成森林 184
5.4.2最小生成树 185
5.4.3构造最小生成树的Pri n算法 186
5.4.4构造最小生成树的Kruskal算法 189
5.5最短路径 191
5.5.1单源点最短路径——Dijkstra算法 192
5.5.2每一对顶点之间的最短路径 195
5.6拓扑排序与关键路径 196
5.6.1有向无环图的概念 196
5.6.2 AOV网与拓扑排序 197
5.6.3 AOE网与关键路径 200
5.7典型例题 205
5.8本章小结 215
5.8.1知识点小结 215
5.8.2扩展学习导读 217
练习题 218
实验题 219
题目 校园导游程序 219
第6章 查找技术 221
6.1引言 221
6.1.1问题提出 221
6.1.2相关概念 221
6.2线性表查找 222
6.2.1顺序查找 223
6.2.2顺序存储的有序表查找 224
6.3树结构查找 227
6.3.1二叉排序树 227
6.3.2平衡二叉树 234
6.4散列表查找 240
6.4.1基本概念 240
6.4.2散列函数的构造方法 241
6.4.3处理冲突的方法 243
6.4.4散列表的性能分析 246
6.5查找方法的比较 247
6.6典型例题 247
6.7本章小结 251
6.7.1知识点小结 251
6.7.2扩展学习导读 252
练习题 253
实验题 254
题目1职工信息检索系统 254
题目2个人图书管理系统 255
第7章 排序技术 256
7.1引言 256
7.1.1问题的提出 256
7.1.2相关概念 256
7.2插入排序 258
7.2.1直接插入排序 258
7.2.2折半插入排序 259
7.2.3希尔排序 260
7.3交换排序 261
7.3.1冒泡排序 262
7.3.2快速排序 263
7.4选择排序 265
7.4.1简单选择排序 265
7.4.2树结构选择排序 266
7.4.3堆排序 267
7.5归并排序 270
7.6基数排序 273
7.6.1多关键码排序 273
7.6.2链式基数排序 273
7.7排序方法比较 275
7.7.1性能比较 275
7.7.2不同排序方法的适用情况 276
7.8典型例题 276
7.9本章小结 278
7.9.1知识点小结 278
7.9.2扩展学习导读 280
练习题 280
实验题 281
题目 各种内部排序的性能比较 281
第8章 扩展应用举例 283
8.1求最大子段和 283
8.1.1问题描述 283
8.1.2问题分析与解决 283
8.2表达式树的构造 287
8.2.1问题描述 287
8.2.2问题分析与解决 287
8.3由等价关系求划分 290
8.3.1问题描述 290
8.3.2问题分析与解决 290
8.4本章小结 293
8.4.1知识点小结 293
8.4.2扩展学习导读 293
练习题 294
实验题 294
题目1模拟银行排队办理业务 294
题目2 0-1背包问题 295
附录 296
附录A实验要求 296
附录B模拟试卷 298
模拟试卷一（本科水平） 298
模拟试卷二（本科水平） 300
模拟试卷三（研究生入学考试水平） 302
模拟试卷四（研究生入学考试水平） 304
附录C 2012年全国硕士研究生入学统一考试计算机科学与技术学科联考试卷（“数据结构”部分） 306
参考文献 312