本书**章综述了数据结构的基本概念及算法分析初步;第二章至第七章分别讨论了线性表、栈、队列、数组、广义表、树、二叉树、图、串和集合等常用的数据结构,包括数据的逻辑结构、存储结构及有关运算;第八章和第九章讨论了在数据处理中常用的查找和排序的各种方法和算法;第十章介绍了常用的文件组织方法;第十一章简单介绍了常用算法设计方法。全书的选材注重于实际应用,略去一些理论推导和证明;采用通俗易懂的语言描述各种数据结构的定义;采用类C语言来描述数据结构和算法,尽量考虑C语言的特点。本书可作为计算机专业的教材或非计算机类各专业选修课的教材。

**章 绪论
1.2 算法的描述和分析
算法是解决某一特定类型问题的有具体步骤的方法。一个算法应该具有下列特性:
(1)有穷性。一个算法必须是在执行有限步之后结束。
(2)确定性。算法的每一步必须是确切地定义的,无二义性。对于每种情况,有待执行的运算必须被严格地和清楚地规定。
(3)可行性。算法应该是可行的,这意味着算法中描述的运算都是相当基本的,它们都是可以通过已经实现的基本运算执行有限次来实现的。
(4)输入。一个算法有O个或多个输入。它们是在算法开始前对算法给定的量。这些输入取自于特定的对象的集合。
(5)输出。一个算法有一个或多个输出。它们是同输入有某种特定关系的量。
一个算法可以用自然语言、计算机程序语言来说明,只是要求该说明必须**地描述计算过程。通常,描述算法采用介于自然语言和程序语言之间的伪语言,这样既可以利用程序语言的主要语句描述算法的计算过程,又不至于陷于具体程序语言的某些细节。为了便于读者上机验证算法和提高读者的编程能力,本书采用C语言描述算法。
求解同一个问题可能有多种不同的算法,判断一个算法的好坏,主要有以下几个标准:
(1)正确性。算法应满足具体问题的需求,正确反映求解问题对输入、输出和加工处理等方面的需求。
(2)可读性。算法应当便于阅读,以利于理解与修改。如:算法的结构清晰并加入注释,简要说明主要参数的使用规则,各程序段完成的功能等。
(3)健壮性。要求算法具有查错和处理功能。如对非法数据或执行过程中出现的异常状态进行检测、报错和纠正错误。
(4)效率。算法的效率主要指算法运行时所需要的计算机资源的多少,包括运行时间和存储空间的消耗。通常,求解同一个问题若有多种算法,则执行时间短的算法效率高,占用空间少的算法较好。但是算法的时间开销和空间开销经常是相互制约的,对高时间效率和低存储量的要求只能根据问题的性质折衷处理。
在算法是“正确的”前提下,对算法在计算机上执行耗费时间和所占空间的分析,常常是人们对算法进行评估和选择的重要依据。
算法分析是对一种算法所消耗的计算机资源的估算,算法设计者可以据此对解决同一个问题的多种算法的代价进行比较,还可以判断一种算法在实现时是否会遇到资源限制的问题。
……

**章 绪论
1.1 基本概念和术语
1.2 算法的描述和分析
习题
第二章 线性表
2.1 线性表的定义和运算
2.2 线性表的顺序存储结构
2.3 线性表的链式存储结构
2.4 栈
2.5 栈与递归
2.6 队列
2.7 循环链表和双向链表
2.8 一元多项式相加
习题
第三章 数组和广义表
3.1 数组
3.2 稀疏矩阵
3.3 广义表
习题
第四章 树和二叉树
4.1 树的定义和术语
4.2 二叉树
4.3 遍历二叉树
4.4 线索二叉树
4.5 树的存储结构和遍历
4.6 哈夫曼树
习题
第五章 图
5.1 图的概念及术语
5.2 图的存储结构
5.3 图的遍历
5.4 *小生成树
5.5 *短路径
5.6 拓扑排序
5.7 关键路径
习题
第六章 串
6.1 串的基本概念和存储结构
6.2 串的基本运算
6.3 模式匹配
习题
第七章 集合
7.1 集合的概念及主要运算
7.2 集合的存储表示
7.3 典型的集合结构
习题
第八章 查找
8.1 线性表查找
8.2 散列表和查找
8.3 二叉排序树
习题
第九章 排序
9.1 插入排序
9.2 选择排序
9.3 交换排序
9.4 基数排序
9.5 归并排序
9.6 内部排序方法的选择和使用
习题
第十章 文件
10.1 顺序文件
10.2 索引文件
10.3 散列文件
10.4 例排文件
习题
第十一章 常用算法设计方法
11.1 递推法
11.2 分治法
11.3 溯法
11.4 贪心法
11.5 动态规划法
习题
参考文献