• 注册
  • 资料 资料 关注:384 内容:198

    广东专插本指定教材《数据结构》王晓东第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

      请登录之后再进行评论

      登录

      插本社区

    • 资料
      资料
      这里可以求你想要的资料,直接发布想要的资料(真题)名字就好啦,注意,在这里求资料,一定要关注《插本指南》公众号,才可以接受到官方的通知
    • 问答
      问答
      解决疑难杂症
    • 考试大厅
      考试大厅
      官方考试系统
    • 攻略
      攻略
      插本指南《攻略》版块,为广东提供广东专插本最详细的攻略!
    • 反馈
      反馈
      官方反馈,有意见可以提
    • 发表内容
    • 做任务
    • 实时动态
    • 到底部