|
关于我们
 书单推荐 新书推荐 |
数据结构（C语言描述）（第3版） 
定 价：49 元
9 7 3 8 4 7 4 1 4 2 2 1 8 读者对象:高等院校计算机及相关专业的学生 
本书是国家精品课程教材，以教育部计算机科学与技术教学指导委员会发布的"高等学校计算机科学与技术本科专业规范”为依据，以基本数据结构为知识单元而编写。全书共分12章，包括引论、表、栈、队列、排序与选择、树、图、集合、符号表、字典、优先队列、并查集等。 全书采用C语言作为描述语言，内容丰富，叙述简明，理论与实践并重，每章设有应用举例和算法实验题，并为任课教师免费提供电子课件和课程实验用数据。 读者对象：可作为高等学校计算机、电子信息、信息与计算科学、信息管理与信息系统等专业的数据结构课程教材，也适合工程技术人员和自学者学习参考。
王晓东，男，1957年出生，山东人，中共党员，现任福建工程学院副院长，教授，博士生导师，福建省计算机学会理事长。先后担任福州大学计算机系主任、数学与计算机科学学院院长，2007年8月起担任泉州师范学院副院长。主讲课程：算法与数据结构、算法设计与分析、文献阅读与选题报告。
第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
你还可能感兴趣
我要评论
|
