第1章 绪论 1
1.1 概述 1
1.1.1 数据结构的重要性和应用场合 1
1.1.2 数据结构的学习方法 3
1.2 数据结构的基本知识 3
1.2.1 数据结构的定义 3
1.2.2 元素的逻辑关系和物理关系 4
1.2.3 数据结构应用实例 4
1.2.4 抽象数据类型 7
1.3 算法和算法描述 9
1.3.1 算法的概念 9
1.3.2 算法的表达 9
1.4 算法的评价 11
1.4.1 时间复杂度和空间复杂度的概念 11
1.4.2 时间复杂度的估算规则 12
1.4.3 时间复杂度估算任务 13
1.4.4 常见的不同数量级时间复杂度 15
自测练习题 15
第2章 线性表和数组 17
2.1 线性表的逻辑结构 17
2.1.1 线性表的定义 17
2.1.2 线性表的基本操作 17
2.1.3 任务2.1：合并线性表——抽象描述 18
2.2 线性表的顺序存储结构的实现 18
2.2.1 顺序存储结构 18
2.2.2 基本操作的实现 19
2.2.3 动态分配的顺序存储结构介绍 21
2.2.4 任务2.2：合并线性表——C语言实现 22
2.3 线性表的链式存储结构的实现 25
2.3.1 单链表 25
2.3.2 单链表的基本操作 26
2.3.3 任务2.3：一元多项式的单链表表示 30
2.3.4 任务2.4：一元多项式相加 32
2.3.5 循环链表和双向链表 35
2.4 数组 38
2.4.1 数组的基本概念 38
2.4.2 数组的顺序存储结构 38
2.4.3 特殊矩阵的压缩存储 39
2.4.4 任务2.5：稀疏矩阵的转置 39
2.5 实训任务 42
2.5.1 实训任务2.1：超长正整数相加 42
2.5.2 实训任务2.2：求约瑟夫环的出列顺序 42
自测练习题 43
算法设计题 44
第3章 栈和队列 46
3.1 栈 46
3.1.1 栈的定义及其运算 46
3.1.2 任务3.1：表达式处理——抽象描述 46
3.1.3 栈的顺序存储结构的实现 48
3.1.4 栈的链式存储结构的实现 49
3.1.5 任务3.2：表达式处理——C语言实现 51
3.1.6 任务3.3：汉诺塔问题的递归实现 53
3.2 队列 55
3.2.1 队列的定义及运算 55
3.2.2 任务3.4：消息的加密和解密——改进的凯撒密码 56
3.2.3 队列的顺序存储结构的实现 57
3.2.4 任务3.5：消息的加密和解密——C语言实现 59
3.2.5 队列的链式存储结构的实现 61
3.3 拓展任务 63
3.3.1 任务3.6：算术表达式的求值 63
3.3.2 任务3.7：模拟停车场管理 68
3.4 实训任务 73
3.4.1 实训任务3.1：数制转换问题 73
3.4.2 实训任务3.2：手机短信息功能的模拟 73
自测练习题 74
算法设计题 75
第4章 树和二叉树 76
4.1 树 76
4.1.1 树的定义 76
4.1.2 树的基本术语 77
4.2 二叉树 78
4.2.1 二叉树的定义 78
4.2.2 二叉树的重要性质 78
4.2.3 二叉树的存储结构 79
4.2.4 任务4.1：建立二叉树的二叉链表 81
4.3 遍历二叉树 82
4.3.1 先根遍历二叉树 83
4.3.2 任务4.2：求二叉树的叶子结点数 85
4.3.3 中根遍历二叉树 88
4.3.4 任务4.3：打印二叉树 89
4.3.5 后根遍历二叉树 91
4.3.6 任务4.4：销毁二叉树 92
4.4 线索二叉树 94
4.4.1 线索二叉树的基本概念 94
4.4.2 中根线索二叉树 95
4.5 树和森林 97
4.5.1 树的存储结构 97
4.5.2 树与二叉树之间的转换 97
4.5.3 森林与二叉树的转换 98
4.5.4 树和森林的遍历 100
4.6 赫夫曼树及其应用 101
4.6.1 赫夫曼树的基本概念 101
4.6.2 任务4.5：构造赫夫曼树 101
4.6.3 任务4.6：赫夫曼编码 104
4.7 实训任务 106
4.7.1 实训任务4.1：二叉树遍历及应用 106
4.7.2 实训任务4.2：设计并输出赫夫曼编码 107
自测练习题 107
算法设计题 108
第5章 图 109
5.1 图的基本概念 109
5.1.1 图的定义 109
5.1.2 图的基本术语 110
5.2 图的存储结构 111
5.2.1 邻接矩阵表示法 111
5.2.2 任务5.1：建立无向图的邻接矩阵 112
5.2.3 邻接表 115
5.2.4 任务5.2：建立有向图的邻接表 116
5.3 图的遍历 118
5.3.1 连通图的深度优先搜索遍历 119
5.3.2 连通图的广度优先搜索遍历 120
5.3.3 任务5.3：求无向图的连通分量 121
5.4 图的最小生成树 123
5.4.1 生成树的概念 123
5.4.2 网络的最小生成树 124
5.4.3 任务5.4：局域网布线造价问题 128
5.5 最短路径 129
5.5.1 从某源点到其余顶点之间的最短路径 130
5.5.2 任务5.5：输出最短路径 132
5.5.3 求有向网中每一对顶点间的最短路径 134
5.6 有向无环图及其应用 136
5.6.1 拓扑排序 136
5.6.2 关键路径 139
5.7 实训任务 145
5.7.1 实训任务5.1：游览线路设计 145
5.7.2 实训任务5.2：交通咨询 146
自测练习题 147
算法设计题 148
第6章 排序 149
6.1 排序的基本概念 149
6.2 插入排序 150
6.2.1 直接插入排序 150
6.2.2 折半插入排序 151
6.2.3 希尔排序 152
6.3 交换排序 153
6.3.1 冒泡排序 153
6.3.2 任务6.1：字符串排序 154
6.3.3 快速排序 156
6.4 选择排序 157
6.4.1 简单选择排序 157
6.4.2 堆排序 159
6.4.3 任务6.2：实现堆排序 162
6.5 归并排序 164
6.6 基数排序 166
6.7 内部排序总结 169
6.8 多路归并用于外排序的简介 170
6.9 实训任务 172
6.9.1 实训任务6.1：成绩表排序 172
6.9.2 实训任务6.2：操作系统进程优先级排序 173
自测练习题 173
第7章 查找 174
7.1 查找的基本概念 174
7.2 静态查找表 175
7.2.1 顺序查找 175
7.2.2 折半查找 177
7.2.3 索引顺序的查找 179
7.3 动态查找表 180
7.3.1 二叉排序查找树 180
7.3.2 任务7.1：建立二叉排序树 183
7.3.3 平衡二叉树与动态平衡技术 185
7.3.4 B-树用于外部查找 187
7.4 哈希表及其查找 192
7.4.1 哈希函数与哈希表 192
7.4.2 构造哈希函数的常用方法 193
7.4.3 任务7.2：设计哈希函数 195
7.4.4 解决冲突的主要方法 196
7.4.5 哈希查找效率的分析 200
7.4.6 任务7.3：设计哈希表 201
7.5 实训任务 203
7.5.1 实训任务7.1：二叉排序树的应用 203
7.5.2 实训任务7.2：哈希表的应用 204
自测练习题 204
第8章 数据结构程序设计及其他 205
8.1 数据结构程序设计 205
8.1.1 算法书写规范 205
8.1.2 实习步骤规范 207
8.2 实习报告范例 208
8.3 其他数据结构和加密算法 211
自测练习题 214
第9章 Java中已实现数据结构的使用 215
9.1 Java中数据结构概述 215
9.1.1 Java中数据结构相关类体系 215
9.1.2 迭代器 217
9.2 链表的实现 219
9.2.1 任务9.1：建立一个链表LinkedList 219
9.2.2 任务9.2：遍历整个链表 219
9.2.3 任务9.3：对链表的常用操作的Java实现 220
9.2.4 程序改进 221
9.3 可变长数组的实现 221
9.3.1 任务9.4：教材管理软件的数据存储实现 221
9.3.2 任务9.5：全部教材信息的显示 222
9.3.3 任务9.6：教材订购方法的参数传递 223
9.4 任务9.7：将教材链表逆序输出 224
9.5 哈希表的实现 225
9.5.1 任务9.8：根据书号查询教材名 225
9.5.2 任务9.9：程序初始值存储和装入 228
9.6 自动排序的实现 231
9.6.1 任务9.10：教材名自动排序 231
9.6.2 任务9.11：将教材信息按教材名排序 232
9.6.3 任务9.12：将教材信息按教材价格排序 234
9.6.4 任务9.13：将教材信息对按关键字排序 234
9.6.5 任务9.14：显示满足条件的部分教材 236
自测练习题 237
参考文献 238