第一章 引论

第一节 抽象数据类型

一、程序设计的一个基本原则是抽象

二、抽象数据类型

第二节 数据结构

一、基本术语

二、数据的逻辑结构

三、数据的存储结构

第三节 算法的概念

第四节 算法设计基本技术

一、分治法

二、贪心法

三、动态规划法

四、基本检索与遍历技术

五、回溯法

第五节 算法分析

一、算法复杂度

二、时间复杂度

三、空间复杂度

四、分析算法的意义

习题

第二章 线性表

第一节 线性表

一、线性表的逻辑结构

二、线性表抽象数据类型

第二节 线性表的顺序存储结构

一、顺序表

二、顺序表类的实现

三、顺序存储结构的特点

第三节 线性表的链式存储结构

一、单链表

二、单链表类的实现

三、循环链表

四、双向链表

五、链式存储结构的特点

第四节 线性表的应用

一、一元多项式相加

二、约瑟夫问题

习题

第三章 栈和队列

第一节 栈

一、栈的基本概念

二、栈的顺序存储结构

三、栈的链式存储结构

四、顺序栈和链栈的比较

五、栈的应用

第二节 递归和递归消除

第三节 队列

一、队列的基本概念

二、队列的顺序存储

三、队列的链式存储

习题

第四章 串

第一节 基本概念

第二节 字符串的存储结构

一、顺序存储

二、链式存储

第三节 串类的实现

一、顺序串类的实现

二、链串类的实现

习题

第五章 数组和广义表

第一节 数组的逻辑结构定义

第二节 数组的顺序存储

第三节 矩阵的存储

一、特殊矩阵

二、稀疏矩阵

第四节 广义表的定义

第五节 广义表的存储

第六节 广义表的递归算法

一、广义表的深度

二、复制广义表

习题

第六章 树

第一节 树的基本概念

一、树的定义

二、树的逻辑表示方法

三、树的基本术语

四、树的性质

第二节 树的存储结构

—、双亲表示法

二、孩子表示法

三、孩子兄弟表示法

第三节 二叉树

一、二叉树的定义

二、二叉树的抽象数据类型

三、二叉树的性质

四、二叉树的存储结构

第四节 树、森林与二叉树的转换

第五节 树的遍历

一、二叉树的遍历

二、二叉树遍历的应用

三、树和森林的遍历

第六节 线索二叉树

一、中序线索树的建立

二、在中序线索树中查找某结点的直接前趋

三、在中序线索树中查找某结点的直接后继

四、中序线索树的遍历

五、在中序线索树中插入结点

第七节 树的应用

习题

第七章 图

第一节 图的定义和有关术语

第二节 图的存储结构

一、邻接矩阵

二、邻接表

第三节 图的遍历

一、深度优先遍历

二、广度优先遍历

第四节 生成树和最小生成树

一、无向连通图的生成树

二、带权无向连通图的最小生成树

第五节 最短路径

一、单源最短路径

二、每对顶点之间的最短路径

第六节 拓扑排序

一、拓扑排序

二、拓扑排序算法

第七节 关键路径

习题

第八章 集合与查找

第一节 集合及其运算

第二节 线性表及其查找

一、顺序查找

二、二分查找

三、其他线性表的查找

第三节 树结构的查找

一、二叉检索树

二、平衡二叉检索树

第四节 散列存储与散列查找

一、散列存储

二、散列函数

三、解决冲突

四、散列查找的效率

第五节 索引存储

习题

第九章 内部排序

第一节 基本概念

第二节 插入排序

一、直接插入排序

二、折半插入排序

三、希尔排序

第三节 选择排序

一、直接选择排序

二、堆排序

第四节 交换排序

一、冒泡排序

二、快速排序

第五节 归并排序

第六节 分配排序

一、桶排序

二、基数排序

第七节 内部排序方法的比较与选择

习题

第十章 文件与外排序

第一节 磁盘与文件管理

一、磁盘

二、文件的操作系统视图

三、文件

第二节 文件的组织技术

—、输入顺序文件

二、散列文件

三、线性结构索引文件

四、树结构索引文件

第三节 外排序

一、外排序过程概述

二、多路归并

三、置换-选择排序和最优归并

习题

第十一章 算法分析技术

第一节 对数与级数求和

一、对数

二、级数求和

第二节 递归过程与递归方程

一 、递归过程的分析

二、一类递归方程的解

第三节 算法复杂性分析示例

一、二分查找的时间复杂度

二、以比较为基础的检索的时间下界

三、快速排序的分析

四、排序算法的时间下界

五、二叉树遍历的复杂度

习题

第十二章 多项式时间可计算性

第一节 易解的问题和难解的问题

第二节 P与NP问题类

一、不确定性算法

二、P与NP问题类

第三节 NP完全性和COOK定理

一、多项式归约

二、NP困难和NP完全问题

三、S．A．COOK定理

第四节 若干NP完全问题

一、命题逻辑的可满足性问题和重言式问题

二、无向图的完全图(团集)问题、离集问题和顶点覆盖问题

三、有向图的回路的边集、顶集问题

四、H回路问题和旅行销售员问题

五、O-1整数规划问题

六、集合族的粘连问题、隔衬问题、集合覆盖问题

七、着色问题和离集、团集覆盖问题

八、集合的恰当覆盖及由它推出的一些NP完全性问题

九、装包问题、排序问题、等分问题及最大分割问题

习题

参考文献