数据结构是计算机专业教学计划中的核心课程,也是计算机及相关专业考研和水平等级考试的必考科目。要从事和计算机科学与技术相关的工作,尤其是计算机应用领域的开发和研制工作,必须具备坚实的数据结构基础。
《数据结构(C++版)(第2版)》介绍了数据结构、算法以及抽象数据类型的概念,介绍了线性表、栈、队列和串、数组、树和二叉树、图等常用数据结构,讨论了常用的查找、排序和索引技术,给出了较多的数据结构的应用实例。限于篇幅,把贯穿所有数据结构的综合案例放在了网站上,供读者下载。
《数据结构(C++版)(第2版)》内容丰富,层次清晰,讲解深入浅出,可作为计算机及相关专业本、专科数据结构课程的教材,也可供从事计算机软件开发和应用的工程技术人员阅读、参考。
目录
- □□章 绪论
- 1.1 数据结构在程序设计中的作用
- 1.2 本书讨论的主要内容
- 1.3 数据结构的基本概念
- 1.3.1 数据结构
- 1.3.2 抽象数据类型
- 1.4 算法及算法分析
- 1.4.1 算法及其描述方法
- 1.4.2 算法分析
- 思想火花--好算法是反复努力和重新修正的结果
- 习题
- 思考题
- 第2章 线性表
- 2.1 线性表的逻辑结构
- 2.1.1 线性表的定义
- 2.1.2 线性表的抽象数据类型定义
- 2.2 线性表的顺序存储结构及实现
- 2.2.1 线性表的顺序存储结构--顺序表
- 2.2.2 顺序表的实现
- 2.3 线性表的链接存储结构及实现
- 2.3.1 单链表
- 2.3.2 循环链表
- 2.3.3 双链表
- 2.4 顺序表和链表的比较
- 2.4.1 时间性能比较
- 2.4.2 空间性能比较
- 2.5 线性表的其他存储方法
- 2.5.1 静态链表
- 2.5.2 间接寻址
- 2.6 应用举例
- 2.6.1 顺序表的应用举例--大整数求和
- 2.6.2 单链表的应用举例--一元多项式求和
- 思想火花--好程序要能识别和处理各种输入
- 习题
- 思考题
- 第3章 栈和队列
- 3.1 栈
- 3.1.1 栈的逻辑结构
- 3.1.2 栈的顺序存储结构及实现
- 3.1.3 栈的链接存储结构及实现
- 3.1.4 顺序栈和链栈的比较
- 3.2 队列
- 3.2.1 队列的逻辑结构
- 3.2.2 队列的顺序存储结构及实现
- 3.2.3 队列的链接存储结构及实现
- 3.2.4 循环队列和链队列的比较
- 3.3 应用举例
- 3.3.1 栈的应用举例--表达式求值
- 3.3.2 队列的应用举例--火车车厢重排
- 思想火花--直觉可能是错误的
- 习题
- 思考题
- 第4章 字符串和多维数组
- 4.1 字符串
- 4.1.1 字符串的定义
- 4.1.2 字符串的存储结构
- 4.1.3 模式匹配
- 4.2 多维数组
- 4.2.1 数组的定义
- 4.2.2 数组的存储结构与寻址
- 4.3 矩阵的压缩存储
- 4.3.1 对称矩阵的压缩存储
- 4.3.2 三角矩阵的压缩存储
- 4.3.3 对角矩阵的压缩存储
- 4.3.4 稀疏矩阵的压缩存储
- 4.4 应用举例
- 4.4.1 字符串的应用举例--凯撒密码
- 4.4.2 数组的应用举例--幻方
- 思想火花--用常识性的思维去思考问题
- 习题
- 思考题
- 第5章 树和二叉树
- 5.1 树的逻辑结构
- 5.1.1 树的定义和基本术语
- 5.1.2 树的抽象数据类型定义
- 5.1.3 树的遍历操作
- 5.2 树的存储结构
- 5.2.1 双亲表示法
- 5.2.2 孩子表示法
- 5.2.3 双亲孩子表示法
- 5.2.4 孩子兄弟表示法
- 5.3 二叉树的逻辑结构
- 5.3.1 二叉树的定义
- 5.3.2 二叉树的基本性质
- 5.3.3 二叉树的抽象数据类型定义
- 5.3.4 二叉树的遍历操作
- 5.4 二叉树的存储结构及实现
- 5.4.1 顺序存储结构
- 5.4.2 二叉链表
- 5.4.3 三叉链表
- 5.4.4 线索链表
- 5.5 二叉树遍历的非递归算法
- 5.5.1 前序遍历非递归算法
- 5.5.2 中序遍历非递归算法
- 5.5.3 后序遍历非递归算法
- 5.6 树、森林与二叉树的转换
- 5.7 应用举例
- 5.7.1 二叉树的应用举例--哈夫曼树及哈夫曼编码
- 5.7.2 树的应用举例--八枚硬币问题
- 思想火花--调试程序与魔术表演
- 习题
- 思考题
- 第6章 图
- 6.1 图的逻辑结构
- 6.1.1 图的定义和基本术语
- 6.1.2 图的抽象数据类型定义
- 6.1.3 图的遍历操作
- 6.2 图的存储结构及实现
- 6.2.1 邻接矩阵
- 6.2.2 邻接表
- 6.2.3 十字链表
- 6.2.4 邻接多重表
- 6.2.5 邻接矩阵和邻接表的比较
- 6.3 □小生成树
- 6.3.1 MST性质
- 6.3.2 Prim算法
- 6.3.3 Kruskal算法
- 6.4 □短路径
- 6.4.1 Dijkstra算法
- 6.4.2 Floyd算法
- 6.5 有向无环图及其应用
- 6.5.1 AOV网与拓扑排序
- 6.5.2 AOE网与关键路径
- 6.6 应用举例
- 6.6.1 图的应用举例1--七桥问题
- 6.6.2 图的应用举例2--七巧板涂色
- 思想火花--数据模型在问题求解中的作用
- 习题
- 思考题
- 第7章 查找技术
- 7.1 概述
- 7.1.1 查找的基本概念
- 7.1.2 查找算法的性能
- 7.2 线性表的查找技术
- 7.2.1 顺序查找
- 7.2.2 折半查找
- 7.3 树表的查找技术
- 7.3.1 二叉排序树
- 7.3.2 平衡二叉树
- 7.4 散列表的查找技术
- 7.4.1 概述
- 7.4.2 散列函数的设计
- 7.4.3 处理冲突的方法
- 7.4.4 散列查找的性能分析
- 7.4.5 开散列表与闭散列表的比较
- 思想火花--把注意力集中于主要因素,不要纠缠于噪声
- 习题
- 思考题
- 第8章 排序技术
- 8.1 概述
- 8.1.1 排序的基本概念
- 8.1.2 排序算法的性能
- 8.2 插入排序
- 8.2.1 直接插入排序
- 8.2.2 希尔排序
- 8.3 交换排序
- 8.3.1 起泡排序
- 8.3.2 快速排序
- 8.4 选择排序
- 8.4.1 简单选择排序
- 8.4.2 堆排序
- 8.5 归并排序
- 8.5.1 二路归并排序的非递归实现
- 8.5.2 二路归并排序的递归实现
- 8.6 分配排序
- 8.6.1 桶式排序
- 8.6.2 基数排序
- 8.7 各种排序方法的比较
- 思想火花--学会“盒子以外的思考”
- 习题
- 思考题
- 第9章 索引技术
- 9.1 索引的基本概念
- 9.2 线性索引技术
- 9.2.1 稠密索引
- 9.2.2 分块索引
- 9.2.3 多重表
- 9.2.4 倒排表
- 9.3 树形索引
- 9.3.1 2-3树
- 9.3.2 B_树
- 9.3.3 B+树
- 思想火花--随处可见的索引
- 习题
- 附录A 预备知识
- A.1 数学术语
- A.2 级数求和
- A.3 集合
- A.4 关系
- 附录B C++语言基本语法
- B.1 程序结构
- B.2 数据类型
- B.3 控制语句
- B.4 输入与输出
- B.5 动态存储分配
- B.6 函数
- B.7 类与对象
- B.8 模板
- B.9 异常处理
- 附录C 词汇索引
- 参考文献