数据结构框架

1.绪论：专门研究数据的特性和数据之间存在的关系，以及如何在计算机中有效地存取数据和处理数据。“数据结构”是设计和实现编译程序、操作系统、数据库系统和大型应用程序的重要基础，它也是介于数学、计算机硬件和计算机软件之间的一门核心课程。

1.1什么是数据结构 1.2算法和算法分析

2.线性表：线性表是实际应用中最基本、最简单、最常用的一种数据结构，例如，26个英文字母表(A, B, …, Z)就是一个线性表，表中的元素是单个字母。线性表的基本特点是，数据元素之间具有一种线性关系，即除第一个元素外，集合中的每个元素均有且只有一个直接前驱元素；除最后一个元素外，集合中的每个元素均有且只有一个直接后继元素。

2.1线性表的类型定义 2.2线性表的顺序存储结构 2.3线性表的链式存储结构 2.4线性表的应用–多项式相加与josephus问题

3.栈与队列：栈与队列是两种特殊的线性表，它们的逻辑结构与线性表的逻辑结构相同，但在运算操作方面较线性表有更多的限制，它们是重要的线性数据结构，通常被称为运算受限的线性表。在面向对象的程序设计中，它们是多型数据类型。

3.1栈 3.2栈的应用举例 3.3栈与递归 3.4队列

4.串：现实世界中的实体有多种形式，如数值、文字符号序列、图形、图像、声音等，其中文字（符号）序列称为字符串，简称串。串是一种常用的数据结构，用于描述非数值的简单信息，它在现实世界中屡见不鲜，如人名、产品名、事物名称、车牌号、文献、源程序等。从数据元素间的逻辑关系看，串是线性表，但从操作方式与种类看，它与线性表有许多不同。在计算机中，串被认为是一种特殊的线性表——元素为文字符号的线性表。由于现实问题中经常使用串，所以对串应选择合适的存储结构，并提供灵活多样的基本操作。

4.1串的逻辑结构 4.2串的存储结构 4.3串函数与串的类定义 4.4串模式匹配 4.5串的应用–文本编辑

5.多维数组与广义表：多维数组与广义表均可看成是线性表的一种扩展，即表中的数据元素本身也是一个数据结构，元素的值是可再分解的。它们的逻辑特征是，一个数据元素可能有多个直接前驱和多个直接后继。尽管C++支持多维数组，但它无法保证数组下标的合法性。同时，C++也未能提供数组的输入、输出以及简单的算术运算（如数组赋值和数组相加）。为了克服这些不足，本章针对一维数组设计了类Array1D。

5.1数组 5.2类Array1D 5.3矩阵的存储 5.4十字链表 5.5广义表

6.树结构和二叉树：树结构中每个元素最多只有一个前驱，但可能有多个后继，体现出明显的层次关系。

6.1树的相关概念 6.2树的存储结构与遍历 6.3二叉树

7.图：图（Graph）是一种比树更复杂的非线性结构。在这种结构中，任意两个结点之间都可能有关系，即结点之间的连接关系是任意的，因此图可用来描述更复杂的数据对象。图在人工智能、数学、物理、化学、电信、生物和计算机科学等领域都有着广泛的应用。本章利用图论的知识来讨论如何在计算机上实现图的操作，主要学习图的存储结构以及图的操作实现等。 7.1图的定义和术语 7.2图的对象抽象模型 7.3图的存储结构 7.4图的遍历 7.5图的连通性问题 7.6有向无环图及其应用

8.查找：查找运算在各种数据结构中的使用频率非常高，同时也是很多系统软件及应用程序的核心功能。当要处理的数据量非常庞大时，查找算法的效率就显得更加重要，尤其对于一些实时查询的应用。本章将系统地讨论一种广泛应用于实际问题的数据结构——查找表，主要介绍查找表的基本概念和一些基本的查找算法。

8.1查找表的相关概念 8.2静态查找表 8.3动态查找表 8.4哈希表

9.排序：查找运算在各种数据结构中的使用频率非常高，同时也是很多系统软件及应用程序的核心功能。当要处理的数据量非常庞大时，查找算法的效率就显得更加重要，尤其对于一些实时查询的应用。本章将系统地讨论一种广泛应用于实际问题的数据结构——查找表，主要介绍查找表的基本概念和一些基本的查找算法。

9.1排序的基本概念 9.2 插入排序 9.3交换排序 9.4选择排序 9.5归并排序 9.6基数排序 9.7内排序方法的比较和讨论

10.文件组织和外排序：尽管数据管理技术早已从文件系统发展到数据库系统，但因为文件系统是数据库系统的基础，从专用、高效和系统软件开发的角度来看，文件系统仍有其不可取代的地位。在数据处理方面，特别是事务型的软件编制工作，都涉及有关文件的知识。通常，将存储在主存储器（内存）中的记录集合称为表，存储在辅助存储器（外存）中的记录集合称为文件。如何有效地组织文件中的数据，提供方便而高效的文件数据读取方法，是本章所要讨论的内容。

10.1外存储器概述 10.2文件的基本概念 10.3顺序文件 10.4索引文件 10.5 isam文件和vsam文件 10.6散列文件

10.7多关键字文件 10.8外部排序

11.贪婪算法：先从最优化概念开始，然后介绍该算法在货箱装船问题、背包问题、拓扑排序问题、二分覆盖问题、最短路径问题、最小代价生成树问题中应用时的求解方案 11.1最优化问题 11.2算法思想 11.3应用

12.分而治之算法：它是一种对复杂问题进行分解并逐一解决的方法，在算法设计中也常用到。本章将重点介绍分而治之方法在解决最小最大问题、排序问题、选择问题及计算几何问题等方面的应用

13.动态规划：

14.回溯：一种可靠的问题求解方法是对其所有的候选解进行逐一检查，以此来获得所需要的解。但当一个问题的候选解数量非常大（如指数级）时，上述方法不太适用，因为即便使用最快的计算机也只能解决规模很小的问题。对候选解进行系统检查的方法有多种，其中回溯法和分枝定界法是较常用的两种方法，它们能够避免对很大的候选解集合进行检查，同时也能够保证在算法运行结束时找到所需要的解，因此它被称为“通用解题法”。本章主要讨论回溯方法，这种方法被用来设计货箱装船、背包、最大完备子图等问题的求解算法

15.分支定界法：分枝定界法和前面介绍的回溯法相似，也是在解空间中求出问题的解，但不同的是，分枝定界法一般采用广度优先或最小耗费方法来搜索解空间的树结构。本章通过采用与第14章相同的应用例子来进行讨论，以便更容易地比较分枝定界法与回溯法的异同。相对而言，分枝定界法的解空间比回溯法的大得多，因此当内存容量有限时，回溯法成功的可能性更大。