数据结构与算法设计[电子资源.图书]

第1章 结论

1. 1　问题求解

1. 2　算法表达中的抽象机制

1. 3　抽象数据类型

1. 3. 1　抽象数据类型的基本概念

1. 3. 2　使用抽象数据类型的好处

1. 3. 3　数据结构.数据类型和抽象数据类型

1. 4　用C＋＋描述数据结构与算法

1. 4. 1　变量.指针和引用

1. 4. 2　函数与参数传递

1. 4. 3　C＋＋的类

1. 4. 4　类的对象

1. 4. 5　构造函数与桥构函数

1. 4. 6　运算符重载

1. 4. 7　友元函数

1. 4. 8　内联函数

1. 4. 9　结构

1. 4. 10 联合

1. 4. 11　异常

1. 4. 12　模板

1. 4. 13　动态存储分配

1. 5　算法复杂性分析

1. 5. 1　算法与程序

1. 5. 2　算法复杂性的概念

1. 5. 3　算法复杂性的渐近性态

习题一

第2章　表

2. 1　ADT表

2. 2　用数组实现表

2. 3　用指针实现表

2. 4　用间接寻址方法实现表

2. 5　用游标实现表

2. 6　循环链表

2. 7　双链表

习题二

第3章　栈

3. 1 ADT栈

3. 2 用数组实现栈

3. 3　用指针实现栈

3. 4　等价类划分问题

习题三

第4章　队列

4. 1 ADT队列

4. 2　用指针实现队列

4. 3　用循环数组实现队列

4. 4　电路布线问题

习题四

第5章 串

5. 1 ADT串

　 5. 2　用数组实现串

　5. 3　用指针实现串

　 5. 4　串的块链表示法

　5. 5　串的堆结构

　5. 6　模式匹配

　 5. 6. 1　朴素的模式匹配算法

　 5. 6. 2　模式匹配的KMP算法

　习题五

第6章　排序与选择

　 6. 1　简单排序算法

　 6. 1. 1　冒泡排序

　 6. 1. 2　插入排序

　6. 1. 3　选择排序

　 6. 1. 4　简单排序算法的计算复杂性

　6. 2　快速排序算法

　 6. 2. 1 算法基本思想及实现

　6. 2. 2　算法的性能

　 6. 2. 3　随机快速排序算法

　6. 3　合并排序算法

　 6. 3. 1　算法基本思想及实现

　6. 3. 2　消除递归

　 6. 3. 3　自然合并排序

　6. 4　线性时间排序算法

　 6. 4. 1 计数排序

　6. 4. 2　桶排序

　 6. 5　中位数与第是小元素

　 6. 5. 1　平均情况下的线性时间选择算法

　 6. 5. 2　最坏情况下的线性时间选择算法

　 习题六

第7章　树

　 7. 1　树的定义

7. 2　树的遍历

7. 3　树的表示法

7. 3. 1　父结点数组表示法

7. 3. 2　儿子链表表示法

7. 3. 3　在儿子右兄弟表示法

7. 4 二叉树

7. 5 ADT二叉树

7. 6　二叉树的实现

7. 6. 1　二叉树的顺序存储结构

7. 6. 2　二叉树的结点度表示法

7. 6. 3　用指针实现二叉树

7. 7 线索二叉树

习题七

第8章 图

8. 1　图的基本概念

8. 2　抽象数据类型ADT图

8. 3　图的表示法

8. 3. 1　邻接矩阵表示法

8. 3. 2　邻接表表示法

8. 3. 3　紧缩邻接表

8. 4　用邻接矩阵实现图

8. 4. 1　用邻接矩阵实现赋权有向图

8. 4. 2　用邻接矩阵实现赋权无向图

8. 4. 3　用邻接矩阵实现有向图

8. 4. 4　用邻接矩阵实现无向图

8. 5　用邻接表实现图

8. 5. 1　邻接表基类

8. 5. 2　用邻接表实现有向图

8. 5. 3　用邻接表实现无向图

8. 5. 4　用邻接表实现赋权有向图

8. 5. 5　用邻接表实现赋权无向图

8. 6　图的退伍

8. 6. 1　图的搜索游标

8. 6. 2　广度优先搜索

8. 6. 3　深度优先搜索

8. 7　最短路径

8. 7. 1　单源最短路径

8. 7. 2　所有顶点对之间的最短路径

8. 8　最小生成树

8. 8. 1 最小生成树性质

8. 8. 2 Prim算法

8. 8. 3 Kruskal算法

8. 9　图匹配

习题八

第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. 3. 3　用二叉搜索树实现有序字典

9. 3. 4　AVL树

9. 3. 5　红黑树

9. 4　优先队列

9. 4. 1 优先队列的定义

9. 4. 2　用字典实现代先队列

9. 4. 3　优先级树和堆

9. 4. 4　用数组实现推

9. 4. 5　可并优先队列

9. 5　并查集

9. 5. 1　并查集的定义及其简单实现

9. 5. 2　用父亲数组实现并查集

习题九

第10章　算法设计策略

10. 1　递归与分治策略

10. 1. 1　递归的概念

10. 1. 2　分治法的基本思想

10. 1. 3　二分搜索技术

10. 1. 4　棋盘覆盖问题

10. 2　动态规划

10. 2. 1　矩阵连乘问题

10. 2. 2　动态规划算法的基本要素

10. 2. 3　最大子段和问题

10. 3　贪心算法

10. 3. 1　活动安排问题

10. 3. 2　贪心算法的基本要素

10. 3. 3　哈夫曼编码算法

10. 4　回溯法

10. 4. 1　回溯法的算法框架

10. 4. 2　符号三角形问题

10. 4. 3　圆排列问题

10. 4. 4　连续邮资问题

10. 4. 5　回溯法的效率分析

10. 5　分支限界法

10. 5. 1　分支限界法的基本思想

10. 5. 2　装载问题

10. 5. 3　批处理作业调度问题

习题十

参考文献