数据结构——C++语言描述
| 作者 |
| 陈慧南 |
| 丛书名 |
| 出版社 |
| 电子工业出版社 |
| ISBN |
| 9787121366321 |
| 简要 |
| 简介 |
| 内容简介 作者依据ACM/IEEE的《计算机科学课程体系规范2013》，参考了近年来国内外很多优秀教材，对《数据结构——使用C++语言描述》一书从教材结构和内容方面都做了很大调整，编写了本教材。本次编写保留了经典数据结构和算法知识，引入更多高级数据结构的内容。本教材重视问题求解，反映抽象、封装和信息隐蔽等现代软件设计理念，重视算法的时间和空间分析，包括查找和排序时间的下界分析。数据结构和算法使用C++语言描述。本教材重视实践性和程序设计。书中算法都有完整的C++程序，构思精巧、结构清晰、注释详细，并且所有程序都已在VC++环境下编译通过并能正确运行。它们既是很好的学习数据结构和算法的示例，也是很好的C++程序设计示例。本教材配有大量的实例和图示，并有丰富的习题和实习题，易教易学。本教材涵盖计算机学科专业考研大纲数据结构部分的考查内容。 |
| 目录 |
第1章 概论\t1 1.1 问题求解方法\t1 1.1.1 问题和问题求解\t1 1.1.2 问题求解过程\t1 1.1.3 计算机求解问题的过程\t2 1.2 什么是数据结构\t2 1.2.1 算法与数据结构\t2 1.2.2 数据结构基本概念\t3 1.2.3 数据的逻辑结构\t4 1.2.4 数据的存储表示\t5 1.2.5 数据结构的操作\t6 1.3 数据抽象和抽象数据类型\t7 1.3.1 数据抽象和过程抽象\t7 1.3.2 模块化、封装与信息隐蔽\t7 1.3.3 数据类型和抽象数据类型\t8 1.4 面向对象方法\t10 1.4.1 面向对象方法的由来\t10 1.4.2 面向对象方法的基本思想\t10 1.4.3 面向对象方法的基本要素\t11 1.4.4 抽象数据类型和面向对象方法\t12 1.4.5 C++语言对抽象数据类型的支持\t13 1.5 描述数据结构和算法\t13 1.5.1 数据结构的规范\t13 1.5.2 实现数据结构\t14 1.6 算法分析的基本方法\t15 1.6.1 算法及其性能标准\t15 1.6.2 算法的时间复杂度\t16 1.6.3 渐近时间复杂度\t18 1.6.4 最好、最坏和平均情况时间复杂度\t19 1.6.5 算法按时间复杂度分类\t19 1.6.6 算法的空间复杂度\t19 本章小结\t20 习题1\t20 第2章 数组和链表\t22 2.1 两种基本的存储表示方式\t22 2.2 结构和类\t22 2.2.1 结构\t22 2.2.2 结构表示元素\t23 2.3 指针和动态存储分配\t24 2.3.1 指针\t24 2.3.2 动态存储分配\t25 2.3.3 静态变量和动态变量\t26 2.4 数组\t26 2.4.1 一维数组\t26 2.4.2 二维数组\t27 2.4.3 多维数组\t28 2.4.4 数组和指针\t28 2.4.5 固定长度数组和可变长度数组\t28 2.5 链表\t29 2.5.1 指向结构的指针\t30 2.5.2 单链表\t30 2.5.3 带表头结点的单链表\t33 2.5.4 单循环链表\t33 2.5.5 双向链表\t33 2.6 采用模拟指针的链表\t35 2.6.1 结点结构\t35 2.6.2 可用空间表\t35 2.7 异常处理\t37 本章小结\t38 习题2\t38 第3章 栈和队列\t40 3.1 栈\t40 3.1.1 栈ADT\t40 3.1.2 栈的顺序表示\t41 3.1.3 栈的链接表示\t44 3.2 队列\t47 3.2.1 队列ADT\t47 3.2.2 队列的顺序表示\t48 3.2.3 队列的链接表示\t51 3.3 表达式计算\t51 3.3.1 表达式\t51 3.3.2 中缀表达式转换为后缀表达式\t52 3.3.3 计算后缀表达式的值\t55 3.4 演示与测试\t58 本章小结\t61 习题3\t61 第4章 递归\t63 4.1 递归和递归算法\t63 4.1.1 递归的概念\t63 4.1.2 递归算法示例\t64 4.2 归纳证明\t66 4.3 递推关系\t67 4.4 实现递归\t67 4.4.1 函数调用和系统栈\t68 4.4.2 递归函数的性能\t69 4.4.3 尾递归\t69 4.4.4 消去递归\t70 本章小结\t70 习题4\t70 第5章 线性表和串\t72 5.1 线性表\t72 5.1.1 线性表ADT\t72 5.1.2 线性表的顺序表示\t73 5.1.3 线性表的链接表示\t76 5.1.4 两种存储表示的比较\t79 5.2 一元多项式算术运算\t80 5.2.1 多项式ADT\t80 5.2.2 多项式的链接表示\t80 5.2.3 项结点类\t81 5.2.4 多项式类\t82 5.2.5 多项式的输入和输出\t83 5.2.6 多项式相加\t84 5.2.7 多项式相乘\t85 5.2.8 重载运算符\t86 5.3 串\t86 5.3.1 串ADT\t86 5.3.2 串的存储表示\t87 5.3.3 串运算的实现\t88 5.3.4 简单模式匹配算法\t89 5.3.5 KMP算法\t91 本章小结\t95 习题5\t95 第6章 数组和广义表\t97 6.1 数组作为抽象数据类型\t97 6.1.1 数组ADT\t97 6.1.2 一维数组的C++类\t98 6.2 矩阵\t99 6.2.1 矩阵的概念\t99 6.2.2 矩阵ADT\t99 6.2.3 矩阵的二维数组表示\t100 6.3 特殊矩阵\t101 6.3.1 对称矩阵\t101 6.3.2 带状矩阵\t102 6.4 稀疏矩阵\t103 6.4.1 稀疏矩阵的三元组表\t103 6.4.2 稀疏矩阵转置\t105 6.4.3 稀疏矩阵相加\t107 6.4.4 稀疏矩阵相乘\t108 6.5 稀疏矩阵的正交链表\t109 6.5.1 正交链表结构\t109 6.5.2 正交链表结点类\t110 6.5.3 正交链表类\t111 6.5.4 建立正交链表\t111 6.5.5 输出正交链表\t113 6.6 广义表\t113 6.6.1 广义表的概念\t113 6.6.2 广义表ADT\t114 6.6.3 广义表的存储表示\t115 6.6.4 广义表算法\t116 本章小结\t116 习题6\t117 第7章 树\t118 7.1 树的基本概念\t118 7.1.1 树的定义\t118 7.1.2 基本术语\t119 7.2 二叉树\t120 7.2.1 二叉树的定义\t120 7.2.2 二叉树的性质\t121 7.2.3 二叉树ADT\t122 7.2.4 二叉树的存储表示\t123 7.2.5 二叉树类\t123 7.2.6 实现二叉树的基本操作\t124 7.3 二叉树的遍历\t126 7.3.1 二叉树遍历算法\t126 7.3.2 二叉树遍历的递归算法\t128 7.3.3 二叉树遍历的应用实例\t129 7.4 二叉树遍历的非递归算法\t131 7.4.1 遍历器类\t131 7.4.2 中序遍历器类\t132 7.4.3 后序遍历器类\t134 7.5 二叉线索树\t136 7.5.1 二叉线索树的定义\t136 7.5.2 构造中序线索树\t137 7.5.3 遍历中序线索树\t138 7.6 树和森林\t139 7.6.1 森林与二叉树的转换\t139 7.6.2 树和森林的存储表示\t141 7.6.3 树和森林的遍历\t142 本章小结\t143 习题7\t143 第8章 树的应用\t145 8.1 堆\t145 8.1.1 堆的定义\t145 8.1.2 堆的顺序表示\t145 8.1.3 向下调整和建堆操作\t145 8.2 优先权队列\t147 8.2.1 优先权队列ADT\t147 8.2.2 优先权队列类\t148 8.2.3 实现优先权队列\t148 8.3 哈夫曼树和哈夫曼编码\t150 8.3.1 树的路径长度\t151 8.3.2 哈夫曼算法\t152 8.3.3 哈夫曼树类\t152 8.3.4 构造哈夫曼树\t153 8.3.5 哈夫曼编码\t155 8.3.6 哈夫曼编码算法\t156 8.4 并查集和等价关系\t156 8.4.1 并查集ADT\t157 8.4.2 并查集的存储表示\t157 8.4.3 并查集类\t158 8.4.4 Union和Find函数\t159 8.4.5 改进的Union和Find函数\t159 8.4.6 按等价关系分组\t160 本章小结\t161 习题8\t161 第9章 字典和查找\t162 9.1 字典及其表示\t162 9.1.1 字典\t162 9.1.2 字典查找\t163 9.1.3 字典ADT\t163 9.1.4 字典的存储表示\t164 9.2 顺序查找\t165 9.2.1 无序表的顺序查找\t165 9.2.2 有序表的顺序查找\t165 9.2.3 平均查找长度\t166 9.2.4 自组织表\t166 9.3 二分查找\t167 9.3.1 二分查找算法\t167 9.3.2 对半查找算法\t168 9.3.3 二叉判定树\t169 9.3.4 斐波那契查找算法\t170 9.3.5 插值查找\t172 9.4 分块查找\t172 9.5 查找算法的时间复杂度下界\t173 本章小结\t174 习题9\t174 第10章 二叉查找树\t175 10.1 二叉查找树表示字典\t175 10.1.1 二叉查找树的定义\t175 10.1.2 二叉查找树的查找操作\t176 10.1.3 二叉查找树的插入操作\t177 10.1.4 二叉查找树的删除操作\t178 10.1.5 二叉查找树的高度\t179 10.2 二叉平衡树\t179 10.2.1 二叉平衡树的定义\t179 10.2.2 二叉平衡树类\t180 10.2.3 二叉平衡树的平衡旋转\t181 10.2.4 二叉平衡树的插入操作\t185 10.2.5 二叉平衡树的删除操作\t187 10.2.6 二叉平衡树的高度\t189 10.3 伸展树\t190 10.3.1 自调节树和伸展树\t190 10.3.2 伸展树的伸展操作\t191 10.3.3 伸展树类\t193 10.3.4 旋转的实现\t193 10.3.5 伸展树的插入操作\t194 10.3.6 分摊时间分析\t195 10.4 红黑树\t195 10.4.1 红黑树的定义\t195 10.4.2 红黑树的查找操作\t196 10.4.3 红黑树的插入操作\t196 10.4.4 红黑树的删除操作\t198 10.4.5 红黑树的高度\t199 本章小结\t199 习题10\t199 第11章 多叉查找树\t201 11.1 m叉查找树\t201 11.2 B树\t202 11.2.1 B树的定义\t203 11.2.2 B树的高度\t203 11.2.3 B树的查找操作\t203 11.2.4 B树的插入操作\t204 11.2.5 B树的删除操作\t206 11.2.6 B树类\t207 11.2.7 B树的查找操作\t208 11.2.8 B树的插入函数\t209 11.2.9 B树的删除函数\t210 11.3 键树\t212 11.3.1 键树的定义\t212 11.3.2 双链树\t213 11.3.3 Trie树\t214 11.3.4 Trie树的查找操作\t216 11.3.5 Trie树的插入操作\t216 11.3.6 Trie树的删除操作\t217 11.3.7 Trie树性能分析\t217 本章小结\t218 习题11\t218 第12章 跳表和散列表\t219 12.1 跳表\t219 12.1.1 跳表的概念\t219 12.1.2 跳表类\t221 12.1.3 跳表的查找函数\t222 12.1.4 跳表的插入函数\t223 12.1.5 跳表的删除函数\t224 12.1.6 性能分析\t224 12.2 散列表\t224 12.2.1 散列技术\t225 12.2.2 散列函数\t226 12.2.3 拉链法\t227 12.2.4 开地址法\t228 12.2.5 线性探查法\t228 12.2.6 其他开地址法\t231 12.2.7 性能分析\t233 本章小结\t233 习题12\t234 第13章 图\t235 13.1 图的基本概念\t235 13.1.1 图的定义与术语\t235 13.1.2 图的抽象数据类型\t237 13.2 图的存储结构\t238 13.2.1 图的矩阵表示\t238 13.2.2 图的邻接矩阵实现\t239 13.2.3 图的邻接表表示\t241 13.2.4 图的邻接表实现\t242 13.2.5 有向图的正交链表表示\t245 13.2.6 无向图的邻接多重表表示\t245 13.3 图的遍历\t246 13.3.1 扩充的图类\t246 13.3.2 1 |
有问题微信扫码联系