数据结构—C++实现 (2008 年度畅销榜NO.2569 )

数据结构是计算机专业教学计划中的一门核心课程，也是信息管理、通信电子、自动控制等与计算机技术关系密切的专业的一门基础课程。要从事和计算机科学与技术相关的工作，尤其是计算机应用领域的开发和研制工作，必须具备坚实的数据结构的基础。本书对C++语言作了简单介绍，叙述了抽象数据类型和面向对象的概念，介绍了线性表、栈、队列、数组、广义表、树和图等数据结构，并且介绍了查找和排序的方法。全书用C++语言描述并实现了所有数据结构的类和程序，并附有习题，便于教学。\r\n 本书是为高等院校开设“数据结构”课程编写的教材，可作为计算机专业本科生教材使用，也可供从事计算机软件开发和应用的工程技术人员阅读、参考。\r\n

1 绪论\r\n\r\n1.1 (算法十数据结构)＝程序\r\n1.2 数据结构的基本概念\r\n1.2.1 两个简单的数据结构实例\r\n1.2.2 什么是数据结构\r\n1.3 C++语言基础\r\n1.3.1 程序结构\r\n1.3.2 数据声明和作用域\r\n1.3.3 输入／输出\r\n1.3.4 函数\r\n1.3.5 参数传递\r\n1.3.6 函数各重载\r\n1.3.7 动态内存分配\r\n1.3.8 结构与联合\r\n1.4 算法性能与复杂度\r\n1.4.1 算法的定义\r\n1.4.2 算法的性能标准\r\n1.4.3 算法的复杂度\r\n习题1\r\n\r\n2 抽象数据类型和C++类\r\n\r\n2.1 抽象数据类型\r\n2.1.1 从数据类型到抽象数据类型\r\n2.1.2 封装和信息隐藏\r\n2.1.3 抽象数据类型描述\r\n2.2 类与对象的基本概念\r\n2.2.1 类与对象\r\n2.2.2 消息与合作\r\n2.2.3 多态性\r\n2.3 面向对象的程序设计方法\r\n2.4 C++类与对象\r\n2.5 构造函数和析构函数\r\n2.6 工具函数\r\n2.7 继承\r\n2.8 this指针的使用\r\n2.9 虚函数、多态性以及动态联编\r\n2.9.1 虚函数和多态性\r\n2.9.2 动态联编\r\n2.10 模板类\r\n习题2\r\n\r\n3 线性表\r\n\r\n3.1 线性表的定义\r\n3.2 线性表的顺序表示\r\n3.2.1 顺序表的类定’义\r\n3.2.2 顺序表插入、删除算法的复杂度分析\r\n3.2.3 顺序表的应用\r\n3.3 线性表的链表表示\r\n3.3.1 单链表\r\n3.3.2 单循环链表\r\n3.3.3 双向循环链表\r\n3.3.4 静态链表\r\n3.4 多项式抽象数据类型\r\n3.4.1 多项式表示\r\n3.4.2 多项式相加\r\n习题3\r\n\r\n4 栈、队列和递归\r\n\r\n4.1 栈\r\n4.1.1 顺序栈\r\n4.1.2 链式栈\r\n4.1.3 表达式的计算\r\n4.2 队列\r\n4.2.1 循环队列\r\n4.2.2 链队列\r\n4.3 递归\r\n4.3.1 递归的概念\r\n4.3.2 递归过程与递归工作栈\r\n4.3.3 消除递归\r\n4.3.4 迷宫问题\r\n习题4\r\n\r\n5 串、数组和广义表\r\n\r\n5.1 字符串\r\n5.1.1 字符串的定义、存储结构和操作\r\n5.1.2 串的操作\r\n5.1.3 常用的C十十字符串函数\r\n5.1.4 串类及其实现\r\n5.1.5 模式匹配算法\r\n5.2 数组\r\n5.2.1 C十十中数组的定义\r\n5.2.2 数组的抽象数据类型表示\r\n5.2.3 数组的顺序存储结构\r\n5.3 稀疏矩阵\r\n5.3.1 三元组顺序表\r\n5.3.2 十字链表\r\n5.4 广义表\r\n5.4.1 广义表的定义\r\n5.4.2 广义表的存储结构\r\n5.4.3 n元多项式的表示\r\n5.4.4 广义表的递归算法\r\n习题5\r\n\r\n6 树和森林\r\n\r\n6.1 树的概念\r\n6.1.1 树的定义\r\n6.1.2 树的术语\r\n6.1.3 树的表示形式\r\n6.1.4 树的基本操作和抽象数据类型\r\n6.2 二叉树\r\n6.2.1 二叉树的定义\r\n6.2.2 二叉树的性质\r\n6.2.3 二叉树的基本操作和抽象数据类型\r\n6.3 二叉树的存储结构\r\n6.3.1 数组表示法\r\n6.3.2 链表表示法\r\n6.3.3 二叉树的二叉链表类声明\r\n6.4 遍历二叉树\r\n6.4.1 前序遍历\r\n6.4.2 中序遍历\r\n6.4.3 后序遍历\r\n6.4.4 层序遍历\r\n6.5 线索二叉树\r\n6.5.1 线索二又树的定义\r\n6.5.2 线索二叉树的类定义\r\n6.5.3 中序线索二叉树\r\n6.6 二叉树的应用\r\n6.6.1 堆\r\n6.6.2 哈夫曼树\r\n6.7 树和森林\r\n6.7.1 树的存储结构\r\n6.7.2 树、森林和二叉树的转换\r\n6.7.3 树的遍历\r\n6.7.4 森林的遍历\r\n6.8 等价类及其表示\r\n6.8.1 等价关系与等价类\r\n6.8.2 并查集\r\n习题6\r\n\r\n7 图\r\n\r\n7.1 图的基本概念\r\n7.1.1 图的定义\r\n7.1.2 图的术语\r\n7.1.3 图的基本操作和抽象数据类型\r\n7.2 图的存储结构\r\n7.2.1 邻接矩阵\r\n7.2.2 邻接表\r\n7.2.3 邻接多重表\r\n7.2.4 十字链表\r\n7.3 图的遍历与连通性\r\n7.3.1 深度优先遍历\r\n7.3.2 广度优先遍历\r\n7.3.3 连通分量\r\n7.4 最小生成树\r\n7.4.1 克鲁斯卡尔算法\r\n7.4.2 普里姆算法\r\n7.5 最短路径\r\n7.5.1 弧上权值为非负情形的单源点最短路径问题\r\n7.5.2 弧上权值为任意值的单源点最短路径问题\r\n7.5.3 所有顶点之间的最短路径\r\n7.6 活动网络\r\n7.6.1 用顶点表示活动的网络\r\n7.6.2 用边表示活动的网络(AOE网络)\r\n习题7\r\n\r\n8 查找\r\n\r\n8.1 基本概念\r\n8.2 顺序表\r\n8.2.1 顺序表的查找\r\n8.2.2 有序表的折半查找\r\n8.3 索引顺序表\r\n8.3.1 索引顺序表\r\n8.3.2 倒排表\r\n8.4 二叉排序树\r\n8.4.1 二叉排序树定义\r\n8.4.2 二叉排序树上的查找\r\n8.4.3 二叉排序树的插入\r\n8.4.4 二叉排序树的删除\r\n8.4.5 二叉排序树查找的性能分析\r\n8.5 平衡二叉树\r\n8.5.1 平衡二叉树的定义\r\n8.5.2 平衡旋转\r\n8.5.3 平衡二叉树的插入和删除\r\n8.6 B-树\r\n8.6.1 动态的m路查找树\r\n8.6.2 B-树\r\n8.6.3 B-树的插入\r\n8.6.4 B-树的删除\r\n8.6.5 B+树\r\n8.7 散列表查找\r\n8.7.1 散列表的基本概念\r\n8.7.2 散列函数\r\n8.7.3 处理溢出的闭散列方法\r\n8.7.4 处理溢出的开散列方法——链地址法\r\n8.7.5 散列表分析\r\n习题8\r\n\r\n9 排序\r\n\r\n9.1 基础知识\r\n9.1.1 基本概念\r\n9.1.2 排序表的抽象数据类型描述和类定义\r\n9.2 交换排序\r\n9.2.1 冒泡排序\r\n9.2.2 快速排序\r\n9.3 插入排序\r\n9.3.1 直接插入排序\r\n9.3.2 折半插入排序\r\n9.3.3 希尔排序\r\n9.4 选择排序\r\n9.4.1 直接选择排序\r\n9.4.2 锦标赛排序\r\n9.4.3 堆排序\r\n9.5 归并排序\r\n9.5.1 归并\r\n9.5.2 两路归并排序\r\n9.5.3 递归的归并排序\r\n9.6 基数排序\r\n9.6.1 多关键字排序\r\n9.6.2 链式基数排序\r\n9.7 各种排序方法的选择和使用\r\n习题9\r\n主要参考文献