算法与数据结构：C语言描述

1绪论.

1.1从问题到程序

1.1.1问题分析与抽象

1.1.2程序的设计与实现

1.2抽象数据类型

1.2.1什么是抽象数据类型

1.2.2意义与作用

1.2.3举例

1.3数据结构

1.3.1什么是数据结构

1.3.2数据结构的分类

1.3.3结点与结构

1.3.4外存数据的组织

1.4算法

1.4.1什么是算法

1.4.2算法的设计

1.4.3算法的精化

1.4.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.4应用举例

2.4.1Josephus问题

2.4.2采用顺序表模拟

2.4.3采用循环链表模拟

2.5矩阵

2.5.1矩阵的顺序表示

2.5.2稀疏矩阵的表示方法

2.6广义表与动态存储管理

2.6.1广义表

2.6.2结点的动态分配与回收

2.6.3废料收集与存储压缩

小结

习题

3字符串

3.1字符串及其抽象数据类型

3.1.1基本概念

3.1.2抽象数据类型

3.2字符串的实现

3.2.1顺序表示

3.2.2链接表示

3.3模式匹配

3.3.1朴素的模式匹配

3.3.2无回溯的模式匹配

小结

习题

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迷宫问题

4.3.3表达式计算

4.4队列及其抽象数据类型

4.4.1基本概念

4.4.2抽象数据类型

4.5队列的实现

4.5.1顺序表示

4.5.2链接表示

4.6队列的应用

小结

习题

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.4二叉树的应用

5.4.1堆与优先队列

5.4.2哈夫曼树及其应用

5.5树及其抽象数据类型

5.5.1基本概念

5.5.2抽象数据类型

5.5.3树的周游

5.6树的实现

5.6.1父指针表示法

5.6.2子表表示法

5.6.3长子-兄弟表示法

5.6.4树的其他表示法..

5.7树林

5.7.1树林的周游

5.7.2树林的存储表示

5.7.3树林与二叉树的转换

小结

习题

6集合与字典

6.1集合及其抽象数据类型

6.1.1基本概念

6.1.2主要运算

6.1.3抽象数据类型

6.2集合的实现

6.2.1集合的位向量表示

6.2.2集合的单链表表示

6.3字典及其抽象数据类型

6.3.1基本概念

6.3.2抽象数据类型

6.4字典的顺序表示

6.4.1存储结构

6.4.2算法的实现

6.4.3有序顺序表与二分法检索

6.5字典的散列表示

6.5.1基本概念

6.5.2散列函数

6.5.3碰撞的处理

6.5.4散列文件

小结

习题

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.3.3二叉排序树的插入和构造

7.3.4二叉排序树的删除

7.4最佳二叉排序树

7.4.1基本概念

7.4.2等概率的检索

7.4.3不等概的情况

7.5平衡二叉排序树

7.5.1基本概念

7.5.2调整平衡的模式

7.5.3实现

7.6索引文件

7.6.1多分树

7.6.2B树

7.6.3B+树

小结

习题

8排序

8.1基本概念

8.2插入排序

8.2.1直接插入排序

8.2.2二分法插入排序

8.2.3表插入排序

8.2.4Shell排序

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外排序

小结

习题

9图

9.1基本概念及其抽象数据类型

9.1.1基本概念

9.1.2抽象数据类型

9.2图的周游

9.2.1深度优先周游

9.2.2广度优先周游

9.3存储表示

9.3.1邻接矩阵表示法

9.3.2邻接表表示法

9.3.3两种表示的比较

9.4最小生成树

9.4.1最小生成树及其性质

9.4.2最小生成树的构造

9.5最短路径

9.5.1Dijkstra算法

9.5.2Floyd算法

9.6拓扑排序

9.6.1AOV网

9.6.2拓扑排序

9.7关键路径

9.7.1AOE网

9.7.2关键路径

小结

习题

10算法分析与设计

10.1算法分析技术

10.1.1空间代价分析

10.1.2时间代价分析

10.2算法设计技术

10.2.1分治法

10.2.2贪心法

10.2.3动态规划法

10.2.4回溯法

10.2.5分枝界限法与0/1背包问题

小结

习题

参考文献

索引

算法清单

后记...