计算机类专业教育 > 数据结构与算法类
数据结构与算法实例教程
书号:9787113145613 套系名称:普通高等院校“十二五”规划教材
作者:付学良 李宏慧 出版日期:2012-04-01
定价:33.00 页码 / 开本:276 /16
策划编辑:吴宏伟 孟欣 责任编辑:孟欣 徐盼欣
适用专业:无 适用层次:高等院校
最新印刷时间:
资源下载
教学课件
教学素材
习题答案
教学案例(暂无)
教学设计(暂无)
教学视频(暂无)
内容简介
前言
目录
作者介绍
图书特色
本书是在教育部高等学校计算机科学与技术教学指导委员会关于“数据结构”课程的指导性大纲的指导下进行编写的。
本书结合内蒙古农业大学计算机与信息工程学院学生的实际情况,前半部分以案例驱动的方式引入每种数据结构,描述了它们的定义、抽象数据类型、存储结构和相关算法及应用;后半部分主要讨论查找和排序的各种实现方法及其综合分析比较。全书采用面向对象的C++作为数据结构和算法的描述语言,对于某种存储方式下的数据结构建立相应的类,类中成员函数就是对这种数据结构的操作,不涉及太多C++语言语法方面的知识,浅显易懂。
本书叙述清晰、语言简洁,注重基本知识的描述,既便于教学,又便于自学。
本书适合作为普通高等院校计算机相关专业本科、专科教材,也可以作为研究生入学考试和各类认证证书考试的复习参考书,还可供计算机应用工程技术人员学习参考。无
第1章 绪论 1
1.1 引言 1
1.2 数据结构的主要概念与术语 2
1.3 抽象数据类型的概念与描述 4
1.3.1 基本数据类型的概念 4
1.3.2 抽象数据类型 5
1.4 算法的度量 8
1.4.1 算法的定义 8
1.4.2 算法效率的度量 9
1.5 面向对象C++描述工具简介 11
1.5.1 函数的定义格式 11
1.5.2 函数模板 11
1.5.3 类的定义 12
小结 16
习题 17
第2章 线性表 18
2.1 案例引入及分析 18
2.1.1 学生基本信息管理 18
2.1.2 线性表的定义 18
2.1.3 线性表的存储结构 20
2.2 学生基本信息管理之顺序表的实现 22
2.2.1 学生基本信息管理之顺序表类定义 22
2.2.2 学生基本信息管理之顺序表操作实现 23
2.2.3 学生基本信息管理之顺序表的主程序的实现 28
2.2.4 顺序表的其他操作 30
2.3 学生基本信息管理之单链表实现 31
2.3.1 学生基本信息管理之单链表类定义 32
2.3.2 学生基本信息管理之单链表操作实现 32
2.3.3 学生基本信息管理之单链表的主程序的实现 40
2.3.4 单链表的其他操作 42
2.4 算法分析 44
2.5 循环链表和双向链表 46
2.5.1 循环链表 46
2.5.2 双向链表 47
2.5.3 双向链表的类定义 47
2.6 静态链表 51
2.7 顺序结构与链表结构的比较 54
小结 54
习题 55
第3章 堆栈 58
3.1 案例引入及分析 58
3.1.1 提交批改作业 58
3.1.2 堆栈的定义 58
3.1.3 堆栈的存储结构 59
3.2 提交批改作业的顺序实现 64
3.3 提交批改作业的链式实现 65
3.4 算法分析 67
3.5 堆栈的其他应用 67
3.5.1 堆栈与递归的实现 67
3.5.2 表达式求值 69
3.5.3 背包问题 72
小结 75
习题 75
第4章 队列 77
4.1 案例的引入及分析 77
4.1.1 看病排队候诊 77
4.1.2 队列的定义 77
4.1.3 队列的存储结构 78
4.2 看病排队候诊的顺序实现 83
4.3 看病排队候诊的链式实现 85
4.4 算法分析 87
4.5 队列的其他应用 87
4.5.1 二进制数转换为十进制数 87
4.5.2 十进制数转换为二进制数 88
小结 89
习题 90
第5章 串 91
5.1 案例引入及分析 91
5.1.1 大整数计算器 91
5.1.2 串的定义 91
5.1.3 串的存储结构 93
5.2 大整数计算器的顺序实现 97
5.3 大整数计算器的链式实现 99
5.4 算法分析 101
5.5 串的其他应用 101
5.5.1 简单模式匹配 101
5.5.2 KMP模式匹配 102
小结 106
习题 106
第6章 广义表和数组 108
6.1 案例引入及分析 108
6.1.1 本科生导师制问题 108
6.1.2 广义表的定义 108
6.1.3 广义表的存储结构 110
6.2 本科生导师制问题的实现 111
6.2.1 实现内容 111
6.2.2 实现过程 112
6.3 数组 120
6.3.1 数组的定义 120
6.3.2 数组的存储结构 122
6.4 矩阵的压缩存储 123
6.4.1 特殊矩阵的压缩存储 123
6.4.2 稀疏矩阵的压缩存储 124
小结 136
习题 136
第7章 树和二叉树 139
7.1 案例引入及分析 139
7.1.1 家谱管理 139
7.1.2 树和二叉树的定义 140
7.1.3 树和二叉树的存储结构 144
7.1.4 树与二叉树的转换 149
7.1.5 森林与二叉树的转换 151
7.1.6 树与森林的遍历 151
7.2 家谱管理的实现 152
7.3 遍历二叉树 154
7.3.1 前序遍历 154
7.3.2 中序遍历 155
7.3.3 后序遍历 156
7.3.4 按层次遍历 156
7.4 线索二叉树 157
7.5 树的其他应用——哈夫曼树及编码 161
7.5.1 哈夫曼树 161
7.5.2 哈夫曼编码 162
小结 163
习题 164
第8章 图 165
8.1 图的基本概念与术语 165
8.1.1 图的基本概念 165
8.1.2 图的基本术语 166
8.1.3 抽象数据类型 169
8.2 图的存储结构 171
8.2.1 邻接矩阵 171
8.2.2 邻接表 173
8.2.3 双链式存储结构 174
8.3 图的ADT设计与实现 179
8.4 图的遍历 180
8.4.1 深度优先搜索 181
8.4.2 广度优先搜索 183
8.5 图的连通性 184
8.5.1 无向图的连通分量和生成树 184
8.5.2 有向图的强连通分量 185
8.5.3 最小生成树 186
8.6 最短路径 192
8.6.1 单源最短路径 192
8.6.2 任意顶点间的最短路径 196
8.7 有向无环图及其应用 196
8.7.1 拓扑排序 196
8.7.2 关键路径 199
小结 202
习题 202
第9章 查找 207
9.1 查找的基本概念 207
9.2 静态查找表 208
9.2.1 顺序查找表 209
9.2.2 有序表的查找 209
9.2.3 静态索引顺序表的查找 212
9.3 动态查找表 213
9.3.1 二叉排序树和平衡二叉树 214
9.3.2 B-树和B+树 226
9.4 哈希表 233
9.4.1 哈希表与哈希函数 233
9.4.2 哈希函数的构造方法 234
9.4.3 解决冲突的方法 236
9.4.4 哈希表的查找及其效率分析 239
小结 241
习题 242
第10章 排序 245
10.1 排序的基本概念 245
10.2 插入排序 246
10.2.1 直接插入排序 246
10.2.2 折半插入排序 247
10.2.3 2--路插入排序 249
10.2.4 表插入排序 250
10.2.5 希尔排序 251
10.3 交换排序 252
10.3.1 冒泡排序 252
10.3.2 快速排序 253
10.4 选择排序 256
10.4.1 简单选择排序 256
10.4.2 堆排序 257
10.5 二路归并排序 259
10.6 基数排序 260
10.6.1 多关键字排序 260
10.6.2 链式基数排序 260
10.6.3 各种排序方法的比较 265
小结 266
习题 266