计算机类专业教育 > 数据结构与算法类
实用数据结构基础(第四版）
书号：9787113207489 套系名称：普通高等院校计算机类专业规划教材. 精品系列
作者：陈元春 王中华 张 亮 王 勇 出版日期：2015-09-01
定价：37.00 页码 / 开本：308 /16
策划编辑：周海燕 责任编辑：周海燕 彭立辉
适用专业：无 适用层次：高等学校
最新印刷时间：
资源下载
教学课件
教学素材
习题答案(暂无)
教学案例(暂无)
教学设计(暂无)
教学视频(暂无)
内容简介
前言
目录
作者介绍
图书特色
本书对数据结构的概念和原理进行了阐述，对数据结构的基本运算进行了分析，并给出了详细的实现过程。全书共分11章，内容包括：绪论、线性表、栈、队列、串、多维数组和广义表、树和二叉树、图、查找、排序、数据结构课程设计等，并在附录部分介绍了数据结构实验系统的组装。
本书集教学内容、习题、实验和课程设计于一体，书中的重要算法均给出了完整的C/C++语言源程序，并全部在VC++环境中运行通过，一书在手就能方便地进行“数据结构”课程的理论学习和实验、课程设计等实践性环节的训练。
本书适合作为高等院校计算机类专业数据结构课程的教材，也可以作为成人教育、自学考试和从事计算机应用的工程技术人员的参考用书。无
第 1 章 绪论......................................................................................................... 1
1.1 什么是数据结构.......................................................................................... 1
1.1.1 从数据结构实验演示系统认识数据结构.......................................... 1
1.1.2 数据结构研究的内容........................................................................ 2
1.2 数据的逻辑结构.......................................................................................... 5
1.2.1 基本概念.......................................................................................... 5
1.2.2 逻辑结构的描述............................................................................... 6
1.3 数据的存储结构.......................................................................................... 7
1.4 算法和算法的效率....................................................................................... 8
1.4.1 算法................................................................................................. 8
1.4.2 算法的效率...................................................................................... 9
1.4.3 算法效率的评价..............................................................................10
小结...................................................................................................................11
实验...................................................................................................................12
验证性实验1 数组、指针、结构体练习...................................................12
自主设计实验1 学生成绩分析程序...........................................................14
习题1.................................................................................................................14
第 2 章 线性表 ................................................................................................... 18
2.1 线性表的定义与运算..................................................................................18
2.1.1 线性表的定义..................................................................................18
2.1.2 线性表的基本操作..........................................................................19
2.2 线性表的顺序存储......................................................................................20
2.2.1 顺序表.............................................................................................20
2.2.2 顺序表上基本运算的实现...............................................................21
2.3 线性表的链式存储......................................................................................25
2.3.1 线性链表.........................................................................................25
2.3.2 线性链表上基本运算的实现...........................................................26
2.3.3 循环链表.........................................................................................33
2.3.4 双向链表.........................................................................................34
小结...................................................................................................................35
实验...................................................................................................................36
验证性实验2 线性表子系统......................................................................36
自主设计实验2 多项式求和......................................................................39
实用数据结构基础 第四版
2
习题2.................................................................................................................40
第 3 章 栈 .......................................................................................................... 46
3.1 栈的定义和运算.........................................................................................46
3.1.1 栈的定义和特性..............................................................................46
3.1.2 栈的运算.........................................................................................47
3.2 栈的存储和实现.........................................................................................47
3.2.1 顺序栈.............................................................................................47
3.2.2 链栈................................................................................................50
3.3 栈的应用举例.............................................................................................51
3.3.1 数制转换.........................................................................................52
3.3.2 表达式求值.....................................................................................53
3.3.3 子程序调用.....................................................................................56
3.3.4 递归调用.........................................................................................57
3.3.5 中断处理和现场保护.......................................................................58
小结...................................................................................................................59
实验...................................................................................................................59
验证性实验3 栈子系统.............................................................................59
自主设计实验3 后缀表达式求值..............................................................63
习题3.................................................................................................................64
第 4 章 队列....................................................................................................... 68
4.1 队列的定义和运算......................................................................................68
4.1.1 队列的定义和特性..........................................................................68
4.1.2 队列的基本运算..............................................................................69
4.2 队列的存储和实现......................................................................................69
4.2.1 顺序队列.........................................................................................69
4.2.2 链队列.............................................................................................73
4.3 队列应用举例.............................................................................................75
小结...................................................................................................................77
实验...................................................................................................................77
验证性实验4 队列子系统..........................................................................77
自主设计实验4 循环队列的实现和运算...................................................81
习题4.................................................................................................................81
第 5 章 串 .......................................................................................................... 86
5.1 串的定义和运算.........................................................................................86
5.1.1 串的定义.........................................................................................86
5.1.2 串的输入与输出..............................................................................87
5.1.3 串的运算.........................................................................................88
目 录
3
5.2 串的表示和实现.........................................................................................88
5.2.1 定长顺序存储..................................................................................88
5.2.2 链接存储.........................................................................................89
5.2.3 串的堆分配存储结构.......................................................................90
5.3 串运算的实现.............................................................................................91
小结...................................................................................................................95
实验...................................................................................................................95
验证性实验5 串子系统.............................................................................95
自主设计实验5 字符串分割处理..............................................................99
习题5...............................................................................................................100
第 6 章 多维数组和广义表................................................................................ 105
6.1 多维数组..................................................................................................105
6.1.1 逻辑结构.......................................................................................105
6.1.2 存储结构.......................................................................................105
6.2 特殊矩阵的压缩存储................................................................................107
6.2.1 对称矩阵.......................................................................................108
6.2.2 三角矩阵.......................................................................................108
6.3 稀疏矩阵..................................................................................................110
6.3.1 稀疏矩阵的存储............................................................................110
6.3.2 稀疏矩阵的算法............................................................................113
6.4 广义表......................................................................................................116
6.4.1 广义表的定义和运算.....................................................................116
6.4.2 广义表的首尾存储法.....................................................................118
6.4.3 广义表的算法................................................................................119
小结.................................................................................................................121
实验.................................................................................................................121
验证性实验6 稀疏矩阵和广义表子系统.................................................121
自主设计实验6 稀疏矩阵十字链表的存储..............................................128
习题6...............................................................................................................128
第 7 章 树和二叉树.......................................................................................... 132
7.1 树的定义和术语.......................................................................................132
7.1.1 树的定义及表示法........................................................................132
7.1.2 基本术语.......................................................................................133
7.2 二叉树......................................................................................................134
7.2.1 二叉树的定义................................................................................134
7.2.2 二叉树的性质................................................................................135
7.2.3 二叉树的存储................................................................................136
7.3 遍历二叉树和线索二叉树.........................................................................140
7.3.1 遍历二叉树...................................................................................140
实用数据结构基础 第四版
4
7.3.2 恢复二叉树...................................................................................142
7.3.3 线索二叉树...................................................................................144
7.4 二叉树的转换...........................................................................................146
7.4.1 一般树转换为二叉树.....................................................................146
7.4.2 森林转换为二叉树........................................................................148
7.4.3 二叉树转换为树和森林.................................................................148
7.5 二叉树的应用...........................................................................................150
7.5.1 二叉树的基本应用........................................................................150
7.5.2 标识符树与表达式........................................................................151
7.6 哈夫曼树及其应用....................................................................................153
7.6.1 哈夫曼树的引入............................................................................153
7.6.2 哈夫曼树的建立............................................................................155
7.6.3 哈夫曼编码...................................................................................157
小结.................................................................................................................158
实验.................................................................................................................159
验证性实验7 二叉树子系统....................................................................159
自主设计实验7 标识符树与表达式求值.................................................165
习题7...............................................................................................................166
第 8 章 图 ........................................................................................................ 172
8.1 图的定义和基本操作................................................................................172
8.1.1 图的定义.......................................................................................172
8.1.2 图的相关术语................................................................................173
8.1.3 图的基本操作................................................................................175
8.2 图的存储表示...........................................................................................175
8.2.1 邻接矩阵.......................................................................................175
8.2.2 邻接表...........................................................................................177
8.2.3 十字链表.......................................................................................179
8.3 图的遍历..................................................................................................181
8.3.1 深度优先搜索................................................................................181
8.3.2 广度优先搜索................................................................................182
8.4 图的连通性...............................................................................................183
8.4.1 无向图的连通分量和生成树.........................................................183
8.4.2 最小生成树...................................................................................185
8.5 最短路径..................................................................................................187
8.6 有向无环图及其应用................................................................................189
8.6.1 拓扑排序.......................................................................................190
8.6.2 关键路径.......................................................................................191
小结.................................................................................................................193
实验.................................................................................................................194
验证性实验8 图子系统...........................................................................194
自主设计实验8 最小生成树....................................................................198
目 录
5
习题8...............................................................................................................199
第 9 章 查找..................................................................................................... 203
9.1 查找的基本概念.......................................................................................203
9.2 静态查找表...............................................................................................204
9.2.1 顺序查找.......................................................................................204
9.2.2 二分查找.......................................................................................206
9.2.3 分块查找.......................................................................................209
9.3 动态查找表...............................................................................................209
9.3.1 二叉排序树...................................................................................209
9.3.2 平衡二叉树...................................................................................214
9.4 哈希表......................................................................................................217
9.4.1 哈希表与哈希方法........................................................................217
9.4.2 哈希函数的构造方法.....................................................................218
9.4.3 处理冲突的方法............................................................................219
小结.................................................................................................................221
实验.................................................................................................................221
验证性实验9 查找子系统........................................................................221
自主设计实验9 哈希查找........................................................................226
习题9...............................................................................................................227
第 10 章 排序................................................................................................... 231
10.1 概述........................................................................................................231
10.2 插入排序................................................................................................232
10.2.1 直接插入排序..............................................................................232
10.2.2 二分插入排序..............................................................................234
10.2.3 希尔排序.....................................................................................235
10.3 快速排序法.............................................................................................236
10.3.1 冒泡排序.....................................................................................236
10.3.2 快速排序.....................................................................................238
10.4 选择排序................................................................................................240
10.4.1 简单选择排序..............................................................................241
10.4.2 树形选择排序..............................................................................242
10.4.3 堆排序.........................................................................................243
10.5 归并排序................................................................................................245
10.6 各种排序方法的比较..............................................................................246
小结.................................................................................................................247
实验.................................................................................................................247
验证性实验10 排序子系统......................................................................247
自主设计实验10 双向冒泡排序..............................................................254
习题10 .............................................................................................................254
实用数据结构基础 第四版
6
第 11 章 数据结构课程设计.............................................................................. 259
11.1 课程设计的目的与内容..........................................................................259
11.1.1 课程设计的目的..........................................................................259
11.1.2 课程设计的内容..........................................................................260
11.1.3 课程设计报告..............................................................................260
11.1.4 课程设计的考核..........................................................................261
11.2 课程设计的要求.....................................................................................262
11.3 课程设计题目.........................................................................................263
课题1 多项式运算...................................................................................263
课题2 浮点数的IEEE 754标准格式转换................................................264
课题3 稀疏矩阵的运算...........................................................................264
课题4 非递归求解Hanoi问题................................................................266
课题5 迷宫问题......................................................................................268
课题6 非递归方式遍历二叉树................................................................268
课题7 中缀表达式转后缀并求值............................................................269
课题8 求字符串中最大长度的对称子串.................................................270
课题9 二叉树的中序线索化及其非栈非递归遍历...................................271
课题10 求二叉树中任意两个结点间的距离............................................271
课题11 把二叉排序树转换成有序的双向链表........................................272
课题12 在二叉树中找出和为某一值的所有路径.....................................272
课题13 判断整数序列是否为二叉排序树的后序遍历序列......................273
课题14 有向无环图的判定及拓扑排序...................................................273
课题15 求AOE网的关键路径................................................................274
课题16 求有向图的强连通分量..............................................................275
课题17 基于十字链表有向图的遍历.......................................................276
课题18 求最小生成树.............................................................................277
课题19 Dijkstra算法求最短路径............................................................278
课题20 双拼输入法的快速定位..............................................................278
课题21 连通问题....................................................................................279
课题22 哈希查找的实现与分析..............................................................281
课题23 文件记录读取并排序..................................................................282
课题24 平衡二叉树的构造及输出...........................................................283
课题25 马对棋盘方格的遍历..................................................................283
课题26 求两个字符串的扩展距离...........................................................285
课题27 求汽车最少加油次数问题...........................................................285
课题28 大整数运算.................................................................................286
附录 A 数据结构实验系统的组装...................................................................... 287
参考文献............................................................................................................ 292