数据结构(用C++语言描述)

第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．3．1 算法定义

1．3．2 算法描述

1．3．3 算法性能分析与度量

1．3．4 常见的算法类型

本章总结

练习

实验

 

第2章 线性表

2．1 线性表的逻辑结构

2．1．1 线性表的定义

2．1．2 线性表的抽象数据类型定义

2．2 线性表的顺序表示和实现

2．2．1 线性表的顺序表示

2．2．2 顺序表表示

2．2．3 顺序表基本操作的实现

2．2．4 顺序表应用举例

2．3 线性表的链式表示和实现

2．3．1 单向链表的概念

2．3．2 链表的类定义

2．3．3 链表基本操作的实现

2．3．4 双向链表

2．3．5 链表应用实例

2．4 链表和顺序表的选取

本章总结

练习

实验

 

第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 队列的抽象数据类型

3．3．3 队列的存储及操作实现

3．3．4 双端队列

3．3．5 队列的应用

本章总结

练习

实验

 

第4章 数组和广义表

4．1 数组

4．1．1 多维数组的概念与存储表示

4．1．2 特殊矩阵及压缩存储

4．2 稀疏矩阵的压缩存储

4．2．1 稀疏矩阵的三元组表示

4．2．2 稀疏矩阵的链式存储法

4．3 广义表

4．3．1 广义表的基本概念

4．3．2 广义表的存储结构

本章总结

练习

实验

 

第5章 串

5．1 串的基本概念及抽象数据类型

5．1．1 串的基本概念

5．1．2 串的抽象数据类型

5．1．3 C++有关串的库函数

5．1．4 串的存储结构

5．2 串的顺序存储结构及基本操作实现

5．2．1 串的顺序存储结构

5．2．2 串的基本操作及实现

5．2．3 串的模式匹配

5．3 串的链式存储

本章总结

练习

实验

 

第6章 树和二叉树

6．1 树的定义及表示

6．1．1 树的定义

6．1．2 树的表示

6．2 二叉树

6．2．1 二叉树的定义

6．2．2 二叉树的抽象数据类型

6．2．3 二叉树的存储结构

6．2．4 二叉树结点类操作实现

6．2．5 二叉树类操作实现

6．3 二叉树遍历及其应用

6．3．1 二叉树遍历的递归算法

6．3．2 二叉树遍历的应用

6．3．3 二叉树遍历的非递归算法

6．4 线索二叉树

6．4．1 线索二叉树定义

6．4．2 线索二叉树存储结构

6．4．3 线索二叉树基本操作

6．5 树和森林

6．5．1 树的存储表示

6．5．2 树和森林的遍历

6．6 Huffman树及其应用

6．6．1 优二叉树概念

6．6．2 优二叉树的构造

6．6．3 Huffman树的应用：Huffman编码

本章总结

练习

实验

 

第7章 图

7．1 图的基本概念

7．1．1 图的定义和术语

7．1．2 图的抽象数据类型

7．2 图的存储结构

7．2．1 图的邻接矩阵表示

7．2．2 图的邻接表表示

7．2．3 图的十字链表表示

7．2．4 图的邻接多重表表示

7．3 图的遍历

7．3．1 深度优先搜索

7．3．2 广度优先搜索

7．4 小生成树

7．4．1 Prim算法

7．4．2 Kruskal算法

7．5 短路径

7．5．1 路径的概念

7．5．2 从一个顶点到其余各顶点的短路径

7．5．3 每对顶点之间的短路径

7．6 DAG及其应用

7．6．1 AOV网络与拓扑排序

7．6．2 AOE网络与关键路径

本章总结

练习

实验

 

第8章 查找

8．1 查找的基本概念

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 B树

8．3．5 B+树

8．4 散列表查找

8．4．1 散列表的基本概念

8．4．2 哈希函数的构造方法

8．4．3 处理冲突方法

本章总结

练习

实验

 

第9章 内部排序

9．1 排序的概念及算法性能分析

9．1．1 排序的概念

9．1．2 排序算法的性能分析

9．1．3 排序表类定义

9．2 插入排序

9．2．1 直接插入排序

9．2．2 希尔排序

9．3 交换排序

9．3．1 冒泡排序

9．3．2 快速排序

9．4 选择排序

9．4．1 直接选择排序

9．4．2 堆排序

9．5 归并排序

9．5．1 归并

9．5．2 归并排序算法

9．6 基数排序

9．6．1 基数排序思想

9．6．2 LSD基数排序

9．7 各种内部排序方法比较

本章总结

练习

实验

 

附录 实验总结

参考文献