第1章 绪论 1
1.1数据结构概述 1
1.1.1学习数据结构的必要性 1
1.1.2数据结构的基本概念和术语 2
1.1.3数据类型与抽象数据类型 5
1.2“HELLO，WORLD！”程序实例 7
1.2.1C语言的编写风格 7
1.2.2C语言预备知识 10
1.3“数组元素排序”实例 12
1.3.1算法的特性 14
1.3.2算法的评价标准 14
1.3.3算法度量及分析 15
小结 18
思考与练习 19
Ⅰ 线性结构 22
第2章 线性表 22
2.1“银行排队”顺序存储实例 22
2.1.1线性表的定义 23
2.1.2线性表的基本操作 24
2.1.3顺序表 24
2.2“学生健康登记”链式存储实例 27
2.2.1单链表的定义 28
2.2.2单链表的基本操作 29
2.3其他链表 32
2.3.1循环链表 32
2.3.2双向链表 33
小结 35
思考与练习 35
第3章 栈和队列 38
3.1“回文”实例 38
3.1.1栈的定义及基本运算 39
3.1.2栈的存储实现和运算实现 40
3.1.3栈与递归 47
3.2“杨辉三角形”实例 49
3.2.1队列的定义及基本运算 51
3.2.2队列的存储实现和运算实现 51
小结 58
思考与练习 58
第4章 串 60
4.1串的基本概念 60
4.1.1串的定义和术语 60
4.1.2串的基本运算 61
4.2“文本加密”实例 62
4.2.1串的顺序存储 64
4.2.2顺序串的基本运算 65
4.2.3串的链式存储 69
4.2.4模式匹配 69
小结 73
思考与练习 73
第5章 内部排序 75
5.1排序的基本概念 75
5.2“学生成绩插入排序”实例 76
5.2.1直接插入排序 77
5.2.2希尔排序 79
5.3“学生成绩交换排序”实例 81
5.3.1冒泡排序 83
5.3.2快速排序 85
5.4“学生成绩选择排序”实例 87
5.4.1直接选择排序 88
5.4.2堆排序 90
5.5其他排序介绍 95
5.5.1有序序列的合并 95
5.5.2二路归并排序 96
5.5.3基数排序 98
5.6各种排序的比较 99
小结 101
思考与练习 102
第6章 查找 104
6.1“学生成绩不及格的查找”实例 104
6.1.1顺序查找 106
6.1.2折半查找 107
6.2“学生成绩及格的查找”实例 109
6.2.1索引查找的概念 110
6.2.2分块查找 111
6.3“学生成绩优秀的查找”实例 112
6.3.1哈希表与哈希方法 113
6.3.2哈希函数的构造方法 115
6.3.3处理冲突的方法 117
6.3.4哈希表的查找分析 120
小结 120
思考与练习 121
Ⅱ 树形结构 124
第7章 二叉树 124
7.1“高校篮球比赛”实例 124
7.1.1二叉树的基本概念 126
7.1.2二叉树的主要性质 126
7.1.3二叉树的存储 128
7.2“高校篮球总决赛”实例 130
7.2.1遍历二叉树 131
7.2.2线索二叉树的定义及结构 133
7.2.3线索二叉树的基本操作 133
7.3“学生成绩及格的查找”实例 135
7.3.1二叉排序树 136
7.3.2平衡二叉树 139
7.4“报文”实例 144
7.4.1哈夫曼树的基本概念 146
7.4.2哈夫曼编码 147
小结 147
思考与练习 148
第8章 树 150
8.1“高校教师讲课比赛”实例一 150
8.1.1树的定义及相关术语 152
8.1.2树的表示 153
8.1.3树的基本操作 154
8.1.4树的存储结构 154
8.2“高校教师讲课比赛”实例二 156
8.2.1树转换为二叉树 158
8.2.2树的遍历 159
8.2.3森林 159
8.3树表动态查找 161
8.3.1B-树和B+树 161
8.3.2键树 167
小结 169
思考与练习 169
Ⅲ 复杂结构 172
第9章 图 172
9.1“城际铁路”实例 172
9.1.1图的定义和术语 173
9.1.2图的存储表示 176
9.2“游乐园路线”实例 180
9.2.1图的遍历 181
9.2.2最小生成树 184
9.2.3最短路径 189
9.3有向无环图的应用 191
9.3.1拓扑排序 191
9.3.2关键路径 193
小结 196
思考与练习 196
第10章 数组、矩阵和广义表 199
10.1“学生考勤的全勤天数”实例 199
10.1.1数组的逻辑结构 199
10.1.2数组的内存映像 201
10.2“学生考勤的放假天数”实例 202
10.2.1对称矩阵 203
10.2.2三角矩阵 203
10.3“学生考勤的请假天数”实例 204
10.3.1稀疏矩阵的三元组表存储 205
10.3.2稀疏矩阵的十字链表存储 208
10.3.3广义表的定义 212
10.3.4广义表的存储 213
10.3.5广义表的运算 214
小结 215
思考与练习 216
Ⅳ 文件结构 220
第11章 文件 220
11.1文件的基本概念 220
11.1.1文件及其类别 220
11.1.2文件记录的逻辑结构和物理结构 221
11.1.3文件组织与操作 221
11.2顺序文件 222
11.3散列文件 223
11.4索引文件 224
11.4.1ISAM文件 225
11.4.2VSAM文件 226
11.5多关键字文件 227
11.5.1多重表文件 228
11.5.2倒排文件 228
小结 228
思考与练习 229
第12章 外部排序 231
12.1外部排序的基本思想 231
12.2外部排序的方法 232
小结 236
思考与练习 236
附录A“数据结构”实训指导 238
附录B教学实验报告参考格式 251
附录C课程应用与学习实验 254
附录D“数据结构”模拟试题 262
各章思考与练习参考答案 270
参考文献 296