|
软件工程专业职教师资培养系列教材数据结构 内容简介
本书介绍数据结构的基本内容，包括线性表、栈和队列、串、数组和广义表、树和二叉树、图、排序、查找等。书中详细介绍了各种数据结构及其在相应结构下数据操作的实现方法和性能分析。本书借鉴理实一体化的编写理念，通过问题导入法，引入要教学的重点内容，以激发读者的学习兴趣，用通俗的语言讲述基础理论，通过举例表述算法的设计思想，用C语言描述算法，并通过算法的设计与实现解决引入的问题，强化读者使用数据结构与算法解决实际问题的能力。
软件工程专业职教师资培养系列教材数据结构 目录
目录
丛书序
前言
第1章 绪论 1
1.1 引例 1
1.2 基本概念 3
1.2.1 数据、数据元素、数据项和数据对象 3
1.2.2 数据结构 4
1.2.3 数据类型和抽象数据类型 6
1.3 算法和算法分析 9
1.3.1 算法的定义及算法描述 9
1.3.2 算法评价 10
1.3.3 算法的时间复杂度 12
1.3.4 算法的空间复杂度 16
小结 17
习题 18
上机实验题 20
第2章 C/C++语言知识 21
2.1 指针 21
2.1.1 指针变量 21
2.1.2 指针运算 22
2.1.3 数组与指针 27
2.2 结构体 31
2.2.1 结构体的定义 31
2.2.2 结构体数组 33
2.2.3 结构体指针 34
2.3 共用体 37
2.4 C++运算符 39
2.4.1 动态申请与释放内存运算符 39
2.4.2 引用 41
2.5 C程序分析 42
小结 44
习题 44
上机实验题 47
第3章 线性表 48
3.1 引例 48
3.2 线性表的概念及运算 49
3.2.1 线性表的定义 49
3.2.2 线性表的抽象数据类型定义 49
3.3 线性表的顺序表示和实现 50
3.3.1 线性表的顺序存储表示 50
3.3.2 顺序表基本运算的实现 51
3.4 引例中读书兴趣小组活动管理的顺序表解决 56
3.5 线性表的链式表示和实现 61
3.5.1 单链表的定义和表示 62
3.5.2 单链表基本运算的实现 62
3.5.3 顺序表和链表的比较 70
3.6 引例中读书兴趣小组活动管理的链表解决 71
3.7 链表知识的扩展 76
3.7.1 单循环链表 76
3.7.2 双向链表 77
3.8 线性表应用举例 78
小结 85
习题 86
上机实验题 89
第4章 栈和队列 90
4.1 引例 90
4.2 栈 92
4.2.1 栈的概念及运算 92
4.2.2 栈的顺序表示和实现 93
4.2.3 栈的链式表示和实现 95
4.3 引例中栈相关问题的解决 98
4.3.1 行编辑的解决 98
4.3.2 数制转换的解决 99
4.3.3 表达式求值的解决 100
4.3.4 递归实现的解决 107
4.4 队列 109
4.4.1 队列的概念及运算 109
4.4.2 队列的顺序表示和实现 111
4.4.3 队列的链式表示和实现 114
4.4.4 引例中银行个人业务模拟问题的解决 117
小结 119
习题 120
上机实验题 123
第5章 串 124
5.1 引例 124
5.2 串的概念及运算 124
5.2.1 串的定义 124
5.2.2 串的抽象数据类型定义 125
5.3 串的顺序表示和实现 126
5.3.1 串的顺序存储表示 126
5.3.2 顺序串基本运算的实现 127
5.4 串的链式表示和实现 129
5.4.1 串的链式存储表示 129
5.4.2 链串基本运算的实现 130
5.5 串的模式匹配 132
5.5.1 Brute-Force算法 132
5.5.2 KMP算法 134
5.6 引例的解决 138
5.6.1 名和姓对换问题的解决 138
5.6.2 文本文件中单词计数和查找问题的解决 139
小结 140
习题 140
上机实验题 142
第6章 数组和广义表 143
6.1 引例 143
6.2 数组 144
6.2.1 数组的概念及运算 144
6.2.2 数组的顺序存储表示 145
6.2.3 引例中求矩阵马鞍点问题的解决 146
6.3 特殊矩阵的压缩存储 147
6.3.1 对称矩阵 147
6.3.2 引例中求对称矩阵的和与乘积问题的解决 148
6.3.3 三角矩阵 150
6.3.4 引例中求三角矩阵的和与乘积问题的解决 151
6.3.5 对角矩阵 152
6.4 广义表 153
6.4.1 广义表的概念及运算 153
6.4.2 广义表的存储结构 155
6.4.3 引例中m元多项式表示问题的解决 157
小结 158
习题 158
上机实验题 160
第7章 树和二叉树 161
7.1 引例 161
7.2 树的概念及运算 162
7.2.1 树的定义 162
7.2.2 树的抽象数据类型定义 164
7.3 二叉树 165
7.3.1 二叉树的概念及运算 165
7.3.2 二叉树的性质 167
7.3.3 二叉树的存储结构 169
7.4 遍历二叉树 172
7.4.1 遍历二叉树的概念和实现 172
7.4.2 根据遍历序列确定二叉树 178
7.4.3 遍历算法应用 179
7.5 线索二叉树 182
7.5.1 线索二叉树的概念 182
7.5.2 线索二叉树的构造和遍历 184
7.6 树和森林 186
7.6.1 树的存储结构 186
7.6.2 树、森林与二叉树的相互转换 189
7.6.3 树与森林的遍历 191
7.7 引例的解决 193
7.7.1 哈夫曼树用于编码的原理和方法 193
7.7.2 引例中字符编码和译码问题的解决 196
7.7.3 引例中报文编码和译码问题的解决 202？
小结 202
习题 203
上机实验题 206
第8章 图 207
8.1 引例 207
8.2 图的概念及运算 210
8.2.1 图的定义 210
8.2.2 图的术语 211
8.2.3 图的抽象数据类型定义 215
8.3 图的存储结构 216
8.3.1 邻接矩阵法 216
8.3.2 邻接表法 219
8.4 图的遍历 222
8.4.1 图的深度优先遍历 222
8.4.2 图的广度优先遍历 225
8.4.3 引例中按中转次数查询*优航线的解决 228
8.5 *小生成树 231
8.5.1 *小生成树和通信网络建立 231
8.5.2 普里姆算法 231
8.5.3 克鲁斯卡尔算法 236
8.5.4 引例中通信网络建立问题的解决 240
8.6 *短路径 241
8.6.1 两类*短路径问题及应用 241
8.6.2 迪杰斯特拉算法 242
8.6.3 引例中按距离、飞行时间、票价查询*优航线的解决 246
8.6.4 弗洛伊德算法 248
8.6.5 引例中医院选址问题的解决 253
8.7 拓扑排序 254
8.7.1 拓扑排序和课程计划制定 254
8.7.2 拓扑排序算法 255
8.7.3 引例中课程计划制定问题的解决 258
8.8 关键路径 260
8.8.1 AOE 网和关键路径 260
8.8.2 关键路径算法 261
8.8.3 引例中工程工期计算问题的解决 268
小结 270
习题 270
上机实验题 273
第9章 查找 274
9.1 引例 274
9.2 查找的基本概念 277
9.3 线性表的查找 278
9.3.1 顺序查找 278
9.3.2 折半查找 279
9.4 树表的查找 282
9.4.1 二叉排序树 283
9.4.2 平衡二叉树 292
9.4.3 B-树 296
9.4.4 B+树 303
9.5 散列表 304
9.5.1 散列表的基本概念 304
9.5.2 散列函数的构造方法 305
9.5.3 处理冲突的方法 307
9.5.4 散列表的查找及其分析 308
9.6 引例的解决 312
9.6.1 手机选择中查找相关问题的解决 312
9.6.2 火车票信息查询中查找相关问题的解决 314
9.6.3 学生课程成绩管理中查找相关问题的解决 316
9.6.4 手机通讯录的解决 320
小结 321
习题 322
上机实验题 325
第10章 内部排序 326
10.1 引例 326
10.2 排序的基本概念 327
10.3 插入排序 328
10.3.1 直接插入排序 328
10.3.2 折半插入排序 329
10.3.3 希尔排序 330
10.4 交换排序 332
10.4.1 冒泡排序 332
10.4.2 快速排序 334
10.5 选择排序 337
10.5.1 简单选择排序 337
10.5.2 堆排序 338
10.6 归并排序 343
10.7 基数排序 345
10.7.1 多关键字排序 345
10.7.2 基数排序 346
10.8 内部排序方法的比较讨论 353
10.9 引例的解决 354
10.9.1 手机选择中排序相关问题的解决 354
10.9.2 火车票信息查询中排序相关问题的解决 355
10.9.3 学生课程成绩管理中排序相关问题的解决 357
小结 360
习题 360
上机实验题 363
参考文献 364
索引 365
|
