前言
第1章 绪论1
1.1 引言1
1.1.1 为什么要学习数据结构1
1.1.2 “数据结构”课程的内容4
1.2 数据结构的概念5
1.2.1 基本概念和术语5
1.2.2 抽象数据类型7
1.3 算法8
1.3.1 算法及其特征8
1.3.2 算法的描述9
1.3.3 算法的性能分析9
1.4 递归12
1.4.1 递归的概念12
1.4.2 递归调用的实现原理13
1.4.3 递归转换为非递归15
1.4.4 递归应用举例16
1.5 本章知识点小结17
练习题18
实验题20
题目1 比较算法复杂性描述函数的
增长20
题目2 全排列的递归实现21
题目3 皇后问题21
第2章 基本线性结构22
2.1 线性表22
2.1.1 问题提出22
2.1.2 线性表的定义23
2.1.3 线性表的基本运算23
2.2 线性表的顺序存储24
2.2.1 顺序表24
2.2.2 顺序表上基本运算的实现26
2.2.3 顺序表应用举例29
2.3 线性表的链式存储31
2.3.1 单链表31
2.3.2 单链表上基本运算的实现33
2.3.3 循环链表39
2.3.4 双向链表39
2.3.5 链表应用举例41
2.4 顺序表和链表的比较44
2.5 堆栈45
2.5.1 堆栈的定义45
2.5.2 堆栈的存储及基本运算的
实现46
2.5.3 堆栈应用举例49
2.6 队列58
2.6.1 队列的定义58
2.6.2 队列的存储及基本运算的
实现59
2.6.3 队列应用举例64
2.7 本章知识点小结67
练习题68
实验题72
题目1 Josephus环问题72
题目2 模拟停车场管理73
第3章 线性结构的扩展75
3.1 字符串75
3.1.1 字符串的基本概念75
3.1.2 顺序串76
3.1.3 模式匹配79
3.2 多维数组与特殊矩阵84
3.2.1 多维数组84
3.2.2 特殊矩阵86
3.2.3 稀疏矩阵90
3.3 广义表99
3.3.1 广义表的基本概念99
3.3.2 广义表的存储101
3.4 本章知识点小结103
练习题104
实验题107
题目 格式化文本107
第4章 树结构110
4.1 引言110
4.1.1 问题提出110
4.1.2 相关概念111
4.2 二叉树113
4.2.1 二叉树的概念113
4.2.2 二叉树的主要性质114
4.2.3 二叉树的存储116
4.2.4 二叉树基本运算的实现119
4.3 二叉树的遍历121
4.3.1 递归方法实现二叉树的遍历121
4.3.2 非递归方法实现二叉树的遍历123
4.3.3 队列方法实现二叉树的层次遍历126
4.4 二叉树遍历的应用127
4.4.1 构造二叉树的二叉链表存储127
4.4.2 在二叉树中查找值为x的数据元素128
4.4.3 统计给定二叉树中叶子结点的数目128
4.4.4 由遍历序列恢复二叉树129
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 最优二叉树的应用——哈夫曼编码141
4.7 树和森林143
4.7.1 树的基本操作与表示143
4.7.2 树的存储144
4.7.3 树和森林与二叉树之间的转换148
4.7.4 树或森林的遍历150
4.7.5 树的应用151
4.8 本章知识点小结153
练习题155
实验题159
题目 哈夫曼编码/译码器159
第5章 图结构161
5.1 引言161
5.1.1 问题提出161
5.1.2 相关概念162
5.1.3 图的基本操作165
5.2 图的存储方法165
5.2.1 邻接矩阵165
5.2.2 邻接表167
*5.2.3 十字链表169
*5.2.4 邻接多重表171
5.3 图的遍历173
5.3.1 深度优先搜索173
5.3.2 广度优先搜索175
5.3.3 应用图的遍历判定图的连通性177
5.4 生成树与最小生成树178
5.4.1 生成树和生成森林178
5.4.2 最小生成树179
5.4.3 构造最小生成树的Prim
算法180
5.4.4 构造最小生成树的Kruskal
算法183
5.5 最短路径186
5.5.1 从一个源点到其他各点的最短路径186
*5.5.2 每一对顶点之间的最短路径——弗洛伊德算法189
5.6 拓扑排序193
5.6.1 有向无环图的概念193
5.6.2 AOV网与拓扑排序194
5.7 关键路径198
5.7.1 AOE网与关键路径198
5.7.2 关键路径的确定199
5.8 本章知识点小结203
练习题206
实验题208
题目 校园导游程序208
第6章 查找210
6.1 引言210
6.1.1 问题提出210
6.1.2 相关概念210
6.2 线性表查找212
6.2.1 顺序查找212
6.2.2 在顺序存储的有序表上查找214
6.3 树表查找218
6.3.1 二叉排序树218
6.3.2 平衡二叉树224
*6.3.3 B树和B+树230
6.4 散列表查找236
6.4.1 散列表236
6.4.2 常用的散列函数237
6.4.3 处理冲突的方法及散列表的构造238
6.4.4 散列表上的查找242
6.4.5 散列表上的插入244
6.4.6 散列表上的删除245
6.5 本章知识点小结245
练习题246
实验题249
题目1 职工信息检索系统249
题目2 个人图书管理系统250
第7章 排序252
7.1 引言252
7.1.1 问题提出252
7.1.2 相关概念252
7.2 插入排序254
7.2.1 直接插入排序254
7.2.2 折半插入排序256
7.2.3 希尔排序256
7.3 交换排序258
7.3.1 冒泡排序258
7.3.2 快速排序259
7.4 选择排序261
7.4.1 简单选择排序261
7.4.2 树型选择排序262
7.4.3 堆排序263
7.5 归并排序266
7.5.1 两个有序表的合并266
7.5.2 二路归并排序的迭代算法267
7.5.3 二路归并排序的递归算法268
*7.6 基数排序268
7.6.1 多关键码排序268
7.6.2 链式基数排序269
7.7 排序方法比较272
7.8 本章知识点小结274
练习题275
实验题278
题目 各种内部排序的性能比较278
第8章 扩展应用举例279
8.1 求最大子段和279
8.1.1 问题描述279
8.1.2 问题分析与解决279
8.2 表达式树的构造283
8.2.1 问题描述283
8.2.2 问题分析与解决283
8.3 由等价关系求划分287
8.3.1 问题描述287
8.3.2 问题分析与解决287
8.4 本章知识点小结289
练习题290
实验题290
题目1 模拟银行排队办理业务290
题目2 0-1背包问题291
附录292
附录A 实验要求292
实验题目294
附录B 模拟试卷295
模拟试卷一295
模拟试卷二296
模拟试卷三299
模拟试卷四301
参考文献304