数据结构

　　“数据结构”是计算机专业的核心课程，是从事计算机软件开发和应用的人员必备的专业基础。随着计算机的日益普及，“数据结构”课程也在不断发展。本书按照“数据结构”课程教学大纲的要求，从面向对象的概念、对象类设计的风格和数据结构的层次开始。从线性结构到非线性结构，从简单到复杂，循序渐进，逐步深入地讨论了各种数据结构的内在的逻辑联系及它们在计算机中的实现方式和使用。此外，对常用的迭代、递推、递归、回溯等算法设计技术、搜索和排序算法等，都做了详尽的描述，并引入了简单的算法分析。全书采用了面向对象的观点讨论数据结构技术，并以兼有面向过程和面向对象双重特色的C++语言作为算法和数据结构的描述工具，强化基本知识与基本技能的双基训练。全书条理清晰，通俗易懂，图文并茂，适于自学。本书适用于计算机专业的本科学生使用，也可作为教师和有关科研人员的参考书。与本书配套的《数据结构例题分析及习题解答》一书已由清华大学出版社出版，此外，如果有需要用PowerPoint制作的教学幻灯片的教师，可与清华大学出版社联系。

暂缺《数据结构》作者简介

前言
第1章 绪论
本章要点
1.1 数据结构的概念及分类
1.1.1 数据与数据结构
1.1.2 数据结构的分类
1.2 抽象数据类型及面向对象概念
1.2.1 数据类型
1.2.2 数据抽象与抽象数据类型
1.2.3 面向对象的概念
1.2.4 用于描述数据结构的语言
1.3 算法定义
1.4 算法性能分析与度量
1.4.1 算法的性能标准
1.4.2 算法的后期测试
1.4.3 算法的事前估计
1.4.4 渐进的时间复杂度
1.4.5 渐进的空间复杂度
小结
习题
第2章 数组
本章要点
2.1 作为抽象数据类型的数组
2.1.1 在C＋＋中数组的定义和初始化
2.1.2 作为抽象数据类型的数组
2.1.3 数组的顺序存储方式
2.2 顺序表
2.2.1 线性表的概念
2.2.2 顺序表的定义和特点
2.2.3 顺序表的搜索、插入和删除
2.2.4 作为抽象数据类型，使用顺序表的事例
2.3 稀疏矩阵
2.3.1 稀疏矩阵的抽象数据类型
2.3.2 稀疏矩阵的压缩表示
2.4 字符串
2.4.1 字符串抽象数据类型和类定义
2.4.2 字符串操作的实现
小结
习题
第3章 链表
本章要点
3.1 单链表
3.1.1 单链表的概念
3.1.2 单链表的类定义
3.1.3 单链表中的插入与删除
3.1.4 带表头结点的单链表
3.1.5 单链表的模板类
3.1.6 静态链表
3.2 循环链表
3.3 多项式及其相加
3.3.1 多项式抽象数据类型与*this指针
3.3.2 多项式的表示
3.3.3 多项式的加法
3.4 双向链表
3.4.1 双向链表的概念
3.4.2 带表头结点的双向循环链表
3.4.3 双向循环链表的搜索、插入和删除算法
3.5 稀疏矩阵
小结
习题
第4章 栈和队列
本章要点
4.1 栈
4.1.1 栈的定义
4.1.2 顺序栈——栈的数组存储表示
4.1.3 链式栈——栈的链接存储表示
4.2 表达式的计算
4.2.1 表达式
4.2.2 应用后缀表示计算表达式的值
4.2.3 中缀表示与其他表示之间的转换
4.3 队列
4.3.1 队列的定义
4.3.2 循环队列——队列的顺序存储表示
4.3.3 链式队列——队列的链接存储表示
4.3.4 队列的应用举例——打印二项展开式（a＋b）i的系数
4.4 优先级队列
4.4.1 优先级队列的定义
4.4.2 优先级队列的存储表示和实现
小结
习题
第5章 递归
本章要点
5.1 递归的概念
5.2 递归过程与递归工作栈
5.2.1 递归工作栈
5.2.2 用栈实现递归过程的非递归算法
5.2.3 用迭代法实现递归过程
5.3 用回溯法求解迷宫问题
5.4 广义表
5.4.1 广义表的概念
5.4.2 广义表的表示及操作
5.4.3 广义表存储结构的实现
5.4.4 广义表的递归算法
小结
习题
第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.3 遍历二叉树
6.3.1 遍历二叉树的递归算法
6.3.2 应用遍历二叉树的事例
6.3.3 遍历二叉树的非递归算法
6.3.4 二叉树的计数
6.4 线索化二叉树
6.4.1 线索
6.4.2 中序线索化二叉树
6.5 堆
6.5.1 堆的定义
6.5.2 堆的建立
6.5.3 堆的插入与删除
6.6 树与森林
6.6.1 树的存储表示
6.6.2 森林与二叉树的转换
6.6.3 树的遍历
6.6.4 森林的遍历
6.7 霍夫曼树
6.7.1 路径长度
6.7.2 霍夫曼树
6.7.3 霍夫曼编码
小结
习题
第7章 集合与搜索
本章要点
7.1 集合及其表示
7.1.1 集合基本概念
7.1.2 用位向量实现集合抽象数据类型
7.1.3 用有序链表实现集合的抽象数据类型
7.1.4 并查集
7.2 静态搜索表
7.2.1 搜索的概念
7.2.2 静态搜索结构
7.2.3 顺序搜索
7.2.4 基于有序顺序表的折半搜索
7.3 二叉搜索树
7.3.1 定义
7.3.2 二叉搜索树上的搜索
7.3.3 二叉搜索树的插入
7.3.4 二叉搜索树的删除
7.3.5 二叉搜索树的搜索效率
7.4 AVL树
7.4.1 AVL树的定义
7.4.2 平衡化旋转
7.4.3 AVL树的插入和删除
7.4.4 AVL树的高度
小结
习题
第8章 图
本章要点
8.1 图的基本概念
8.1.1 图的基本概念
8.1.2 图的抽象数据类型
8.2 图的存储表示
8.2.1 邻接矩阵
8.2.2 邻接表
8.2.3 邻接多重表
8.3 图的遍历与连通性
8.3.1 深度优先搜索
8.3.2 广度优先搜索
8.3.3 连通分量
8.3.4 重连通分量
8.3.5 图的遍历举例：欧拉回路问题
8.4 最小生成树
8.4.1 克鲁斯卡尔算法
8.4.2 普里姆算法
8.5 单源最短路径问题
8.6 活动网络（activity network）
8.6.1 用顶点表示活动的网络
8.6.2 用边表示活动的网络
小结
习题
第9章 排序
本章要点
9.1 概述
9.2 插入排序
9.2.1 直接插入排序
9.2.2 折半插入排序
9.2.3 链表插入排序
9.2.4 希尔排序
9.3 交换排序
9.3.1 起泡排序
9.3.2 快速排序
9.4 选择排序
9.4.1 直接选择排序
9.4.2 锦标赛排序
9.4.3 堆排序
9.5 归并排序
9.5.1 归并
9.5.2 迭代的归并排序算法
9.5.3 递归的链表归并排序
9.6 基数排序
9.6.1 多排序码排序
9.6.2 链式基数排序
9.7 外排序
9.7.1 外排序的基本过程
9.7.2 k路平衡归并与败者树
9.7.3 初始归并段的生成
9.7.4 最佳归并树
小结
习题
第10章 索引与散列
本章要点
10.1 静态索引结构
10.1.1 线性索引
10.1.2 倒排表
10.1.3 m路静态搜索树
10.2 动态索引结构
10.2.1 动态的m路搜索树
10.2.2 B树
10.2.3 B树的插入
10.2.4 B树的删除
10.2.5 B＋树
10.3 散列
10.3.1 词典的抽象数据类型
10.3.2 散列表与散列方法
10.3.3 散列函数
10.3.4 处理冲突的闲散列方法
10.3.5 处理冲突的开散列方法——链地址法
10.3.6 散列表分析
10.4 可扩充散列
10.4.1 二叉Trie树
10.4.2 将二叉Trie树转换为目录表
10.4.3 目录表扩充与收缩
10.4.4 性能分析
小结
习题
附录A 用C＋＋描述面向对象程序
A.1 用模板定义C＋＋中的类
A.2 类中成员函数的实现
A.3 函数名重载和操作符重载
A.4 C＋＋中的主函数
附录B 教学进度与习题安排参考
附录C 词汇索引
参考文献