• 注册
  • 资料 资料 关注:815 内容:484

    广东专插本指定教材《数据结构》王晓东第3版.pdf

  • 查看作者
  • 打赏作者
  • 当前位置: 插本指南 > 资料 > 正文
    官方

    内容简介

    本书是国家精品课程教材教育部计算机科学与技术教学指导委员会发布的”高等学校计算机科学与技术本科专业规范”为依据,以基本数据结构为知识单元而编写。全书共分12章,包括引论、表、栈、队列、排序与选择、树、图、集合、符号表、字典、优先队列、并查集等。 全书采用C语言作为描述语言,内容丰富,叙述简明,理论与实践并重,每章设有应用举例和算法实验题,并为任课教师免费提供电子课件和课程实验用数据。 读者对象:可作为高等学校计算机、电子信息、信息与计算科学、信息管理与信息系统等专业的数据结构课程教材,也适合工程技术人员和自学者学习参考。

    目录

    第1 章 引论 ············································································································································1
    1.1 算法及其复杂性的概念 ··········································································································1
    1.1.1 算法与程序 ························································································································1
    1.1.2 算法复杂性的概念 ·············································································································1
    1.1.3 算法复杂性的渐近性态·······································································································3
    1.2 算法的表达与数据表示 ··········································································································5
    1.2.1 问题求解 ···························································································································5
    1.2.2 表达算法的抽象机制 ··········································································································5
    1.3 抽象数据类型 ··························································································································8
    1.3.1 抽象数据类型的基本概念 ···································································································8
    1.3.2 使用抽象数据类型的好处 ···································································································9
    1.4 数据结构、数据类型和抽象数据类型 ··············································································· 10
    1.5 用C 语言描述数据结构与算法 ··························································································· 11
    1.5.1 变量和指针 ······················································································································ 11
    1.5.2 函数与参数传递 ·············································································································· 12
    1.5.3 结构 ······························································································································· 13
    1.5.4 动态存储分配 ················································································································· 14
    1.6 递归 ········································································································································ 15
    1.6.1 递归的基本概念 ·············································································································· 15
    1.6.2 间接递归 ························································································································ 17
    本章小结 ········································································································································· 18
    习题1 ·············································································································································· 18
    算法实验题1 ·································································································································· 19
    第2 章 表 ············································································································································· 21
    2.1 表的基本概念 ······················································································································· 21
    2.2 用数组实现表 ······················································································································· 22
    2.3 用指针实现表 ······················································································································· 26
    2.4 用间接寻址方法实现表 ······································································································· 30
    2.5 用游标实现表 ······················································································································· 32
    2.6 循环链表 ································································································································ 37
    2.7 双链表 ···································································································································· 39
    2.8 表的搜索游标 ······················································································································· 43
    2.8.1 用数组实现表的搜索游标 ································································································ 43
    2.8.2 单循环链表的搜索游标···································································································· 44
    VI
    2.9 应用举例 ································································································································ 45
    本章小结 ········································································································································· 47
    习题2 ·············································································································································· 47
    算法实验题2 ·································································································································· 49
    第3 章 栈 ············································································································································· 52
    3.1 栈的基本概念 ······················································································································· 52
    3.2 用数组实现栈 ······················································································································· 53
    3.3 用指针实现栈 ······················································································································· 55
    3.4 应用举例 ································································································································ 57
    本章小结 ········································································································································· 60
    习题3 ·············································································································································· 60
    算法实验题3 ·································································································································· 62
    第4 章 队列 ········································································································································· 64
    4.1 队列的基本概念 ··················································································································· 64
    4.2 用指针实现队列 ··················································································································· 64
    4.3 用循环数组实现队列 ··········································································································· 67
    4.4 应用举例 ································································································································ 70
    本章小结 ········································································································································· 74
    习题4 ·············································································································································· 74
    算法实验题4 ·································································································································· 75
    第5 章 排序与选择算法 ····················································································································· 78
    5.1 简单排序算法 ······················································································································· 78
    5.1.1 冒泡排序算法 ················································································································· 79
    5.1.2 插入排序算法 ················································································································· 79
    5.1.3 选择排序算法 ················································································································· 80
    5.1.4 简单排序算法的计算复杂性 ····························································································· 80
    5.2 快速排序算法 ······················································································································· 81
    5.2.1 算法基本思想及实现 ······································································································· 81
    5.2.2 算法的性能 ····················································································································· 82
    5.2.3 随机快速排序算法 ·········································································································· 83
    5.2.4 非递归快速排序算法 ······································································································· 83
    5.2.5 三数取中划分算法 ·········································································································· 84
    5.2.6 三划分快速排序算法 ······································································································· 85
    5.3 合并排序算法 ······················································································································· 86
    5.3.1 算法基本思想及实现 ······································································································· 86
    5.3.2 对基本算法的改进 ·········································································································· 87
    5.3.3 自底向上的合并排序算法 ································································································ 88
    5.3.4 自然合并排序算法 ·········································································································· 88
    5.3.5 链表结构的合并排序算法 ································································································ 89
    5.4 线性时间排序算法 ··············································································································· 90
    VII
    5.4.1 计数排序算法 ················································································································· 90
    5.4.2 桶排序算法 ····················································································································· 91
    5.4.3 基数排序算法 ················································································································· 92
    5.5 中位数与第k 小元素 ············································································································ 94
    5.5.1 平均情况下的线性时间选择算法 ······················································································ 94
    5.5.2 最坏情况下的线性时间选择算法 ······················································································ 95
    5.6 应用举例 ································································································································ 98
    本章小结 ······································································································································· 100
    习题5 ············································································································································ 100
    算法实验题5 ································································································································ 101
    第6 章 树 ··········································································································································· 104
    6.1 树的定义 ······························································································································ 104
    6.2 树的遍历 ······························································································································ 106
    6.3 树的表示法 ·························································································································· 108
    6.3.1 父结点数组表示法 ········································································································ 108
    6.3.2 儿子链表表示法 ············································································································ 108
    6.3.3 左儿子右兄弟表示法 ····································································································· 108
    6.4 二叉树的基本概念 ············································································································· 109
    6.5 二叉树的运算 ······················································································································ 111
    6.6 二叉树的实现 ······················································································································ 112
    6.6.1 二叉树的顺序存储结构··································································································· 112
    6.6.2 二叉树的结点度表示法··································································································· 113
    6.6.3 用指针实现二叉树 ········································································································· 113
    6.7 线索二叉树 ··························································································································· 118
    6.8 二叉搜索树 ··························································································································· 119
    6.9 线段树 ·································································································································· 128
    6.10 序列树 ································································································································ 134
    6.11 应用举例 ···························································································································· 142
    本章小结 ······································································································································· 147
    习题6 ············································································································································ 147
    算法实验题6 ································································································································ 149
    第7 章 散列表 ··································································································································· 154
    7.1 集合的基本概念 ················································································································· 154
    7.1.1 集合的定义和记号 ········································································································ 154
    7.1.2 定义在集合上的基本运算 ······························································································ 155
    7.2 简单集合的实现方法 ········································································································· 156
    7.2.1 用位向量实现集合 ········································································································ 156
    7.2.2 用链表实现集合 ············································································································ 158
    7.3 散列技术 ······························································································································ 161
    7.3.1 符号表 ·························································································································· 161
    VIII
    7.3.2 开散列 ·························································································································· 163
    7.3.3 闭散列 ·························································································································· 164
    7.3.4 散列函数及其效率 ········································································································ 168
    7.3.5 闭散列的重新散列技术·································································································· 169
    7.4 应用举例 ······························································································································ 170
    本章小结 ······································································································································· 171
    习题7 ············································································································································ 172
    算法实验题7 ································································································································ 173
    第8 章 优先队列 ······························································································································· 176
    8.1 优先队列的定义 ················································································································· 176
    8.2 优先队列的简单实现 ········································································································· 177
    8.3 优先级树和堆 ····················································································································· 177
    8.4 用数组实现堆 ····················································································································· 179
    8.5 可并优先队列 ····················································································································· 181
    8.5.1 左偏树的定义 ··············································································································· 182
    8.5.2 用左偏树实现可并优先队列 ··························································································· 182
    8.6 应用举例 ······························································································································ 185
    本章小结 ······································································································································· 190
    习题8 ············································································································································ 190
    算法实验题8 ································································································································ 191
    第9 章 并查集 ··································································································································· 194
    9.1 并查集的定义及其简单实现 ····························································································· 194
    9.2 用父结点数组实现并查集 ································································································· 195
    9.3 应用举例 ······························································································································ 198
    本章小结 ······································································································································· 201
    习题9 ············································································································································ 201
    算法实验题9 ································································································································ 202
    第10 章 图 ········································································································································· 205
    10.1 图的基本概念 ··················································································································· 205
    10.2 抽象数据类型图 ··············································································································· 208
    10.3 图的表示法 ························································································································ 209
    10.3.1 邻接矩阵表示法 ·········································································································· 209
    10.3.2 邻接表表示法 ·············································································································· 209
    10.3.3 紧缩邻接表表示法 ······································································································· 210
    10.4 用邻接矩阵实现图 ············································································································ 211
    10.4.1 用邻接矩阵实现赋权有向图 ·························································································· 211
    10.4.2 用邻接矩阵实现赋权无向图 ························································································· 213
    10.4.3 用邻接矩阵实现有向图 ································································································ 213
    10.4.4 用邻接矩阵实现无向图 ································································································ 213
    10.5 用邻接表实现图 ··············································································································· 214
    IX
    10.5.1 用邻接表实现有向图 ··································································································· 214
    10.5.2 用邻接表实现无向图 ··································································································· 217
    10.5.3 用邻接表实现赋权有向图 ···························································································· 218
    10.5.4 用邻接表实现赋权无向图 ···························································································· 221
    10.6 图的遍历 ···························································································································· 222
    10.6.1 广度优先搜索 ·············································································································· 222
    10.6.2 深度优先搜索 ·············································································································· 224
    10.7 最短路径 ···························································································································· 225
    10.7.1 单源最短路径 ·············································································································· 225
    10.7.2 Bellman-Ford 最短路径算法 ························································································· 228
    10.7.3 所有顶点对之间的最短路径 ························································································· 230
    10.8 无圈有向图 ························································································································ 231
    10.8.1 拓扑排序 ···················································································································· 231
    10.8.2 DAG 的最短路径 ········································································································· 233
    10.8.3 DAG 的最长路径 ········································································································· 234
    10.8.4 DAG 所有顶点对之间的最短路径 ················································································ 234
    10.9 最小支撑树 ························································································································ 235
    10.9.1 最小支撑树性质 ·········································································································· 235
    10.9.2 Prim 算法 ···················································································································· 235
    10.9.3 Kruskal 算法 ················································································································ 237
    10.10 图匹配 ······························································································································ 239
    10.11 应用举例 ·························································································································· 241
    本章小结 ······································································································································· 243
    习题10 ·········································································································································· 244
    算法实验题10 ······························································································································ 245
    参考文献 ··············································································································································· 250

  • 生成海报
  • 请登录之后再进行评论

    登录
    资料
  • 今日 0
  • 内容 484
  • 关注 815
  • 插本社区

  • 资料
    资料
    大家记得关注一下公众号《插本指南》,在插本指南公众号里面回复关键词,获取最新资料
  • 问答
    问答
    解决疑难杂症
  • 考试大厅
    考试大厅
    发布广东考试院官方信息,包括考试大纲,最新政策资讯那些等
  • 攻略
    攻略
    插本指南《攻略》版块,为广东提供广东专插本最详细的攻略!
  • 反馈
    反馈
    官方反馈,有意见可以提
  • 帖子间隔 侧栏位置:
    关闭窗口
    下载海报