1.1 数据结构课程的形成和发展 1
第一章 绪论 1
1.2 数据结构与算法 2
1.2.1 什么是数据结构 3
1.2.2 算法的概念和特性 4
1.2.3 数据结构与算法的关系 5
1.3 关于算法描述和分析的说明 5
习题一 7
2.1 基本概念和常用术语 8
第二章 线性表 8
2.2 线性表的存储结构(一)——向量 9
2.2.1 顺序分配 9
2.2.2 向量的插入和删除 10
2.3 线性表的存储结构(二)——线性链表 13
2.3.1 链式分配 13
2.3.2 线性链表的插入和删除 14
2.4.1 栈及其存储结构 18
2.4 栈和队列 18
2.4.2 栈的应用 22
2.4.3 队列及其存储结构 23
2.4.4 队列的应用 29
2.5 循环线性链表和双向链表 29
2.5.1 循环线性链表 29
2.5.2 双向链表和循环双向链表 31
2.6 单元多项式的存储和相加 34
习题二 39
第三章 串 42
3.1 串的定义和特性 42
3.2 串的存储结构 42
3.2.1 串的顺序存储结构 43
3.2.2 串的链式存储结构 44
3.2.3 串变量的存储 45
3.3 串的运算 45
3.3.1 串的联接 47
3.3.2 求子串 48
3.3.3 模式匹配 49
3.3.4 子串的插入和删除 55
3.3.5 串的置换 57
3.4 汉字串 59
习题三 62
第四章 数组和广义表 63
4.1 数组的顺序分配 63
4.2 稀疏矩阵的三元组表示法 65
4.3 数组的链式分配 71
4.3.1 稀疏矩阵的十字链表表示及矩阵相加 72
4.3.2 三维图形信息的压缩存储 77
4.4 迷宫问题 78
4.5 广义表 81
习题四 82
5.1 树的基本概念和术语 85
第五章 树 85
5.2 树的存储结构 87
5.3 二叉树 88
5.3.1 二叉树的定义和性质 88
5.3.2 二叉树的存储结构 90
5.4 二叉树与树、森林之间的转换 92
5.4.1 二叉树与树之间的转换 92
5.4.2 二叉树与森林之间的转换 93
5.5.1 二叉树链表结构的建立 95
5.5 遍历二叉树 95
5.5.2 前序遍历 98
5.5.3 中序遍历 99
5.5.4 后序遍历 102
5.6 线索树 104
5.6.1 建立线索树 105
5.6.2 检索结点 108
5.6.3 插入结点 110
5.7.1 二叉排序树 113
5.7 树的应用 113
5.7.2 哈夫曼树及其应用 117
习题五 123
第六章 图 125
6.1 基本概念 125
6.2 图的存储结构 127
6.2.1 邻接矩阵 127
6.2.2 邻接链表 127
6.3 图的遍历 128
6.3.1 深度优先搜索法 129
6.3.2 广度优先搜索法 132
6.4 生成树 132
6.4.1 生成树的概念 132
6.4.2 最小生成树 133
6.5 最短路径 139
6.5.1 从某个源点到其余各顶点的最短路径 140
6.5.2 每一对顶点间的最短路径 142
6.6 拓扑排序 145
6.6.1 AOV网 145
6.6.2 拓扑排序 146
6.7 关键路径 151
习题六 155
第七章 递归与回溯 158
7.1 递归的概念 158
7.2 递归算法在非数值运算中的应用 160
7.3 回溯算法 165
7.4 递推算法 170
习题七 172
第八章 查找 173
8.1 线性表的查找 173
8.1.1 顺序查找 173
8.1.2 折半查找 175
8.1.3 分块查找 178
8.2.1 二叉查找树和平衡树 180
8.2 树表查找 180
8.2.2 B树 184
8.3 哈希表及其查找 186
8.3.1 什么是哈希法 186
8.3.2 构造哈希函数的基本方法 187
8.3.3 解决冲突的几种方法 189
习题八 195
第九章 排序 196
9.1 插入排序 196
9.1.1 直接插入排序 196
9.1.2 希尔排序 198
9.2 交换排序 201
9.2.1 冒泡排序 201
9.2.2 快速排序 203
9.3 选择排序 205
9.3.1 直接选择排序 205
9.3.2 堆排序 207
9.4 归并排序 212
9.5 基数排序 216
9.6 外排序 221
9.6.1 外存信息的特性 221
9.6.2 文件及其组织 222
9.6.3 外排序的基本方法 223
习题九 225
10.1.1 问题的提出 227
10.1 存储管理 227
第十章 数据结构应用示例 227
10.1.2 动态存储分配和回收 228
10.1.3 不用单元收集和紧凑存储 233
10.2 学生成绩管理 233
10.2.1 数据结构的描述 234
10.2.2 各子程序的功能和实现 235
习题十 247
附录 若干算法程序 249