第2章　数据结构与算法概述

2.1　知识介绍

数据是信息的载体，是描述客观事物的数据、字符，以及所有能输入到计算机中并被计算机程序识别和处理的符号的集合。

在程序中要指定数据的类型和数据的组织形式，即数据结构（Data Structure）。它研究的是关系，即数据元素之间存在的一种或多种特定关系的集合。在程序中还要指定操作步骤，即算法（Algorithm）。

我们把数据结构分为逻辑结构和物理结构，前者指数据对象中数据元素之间的相互关系；后者指数据的逻辑结构在计算机中的存储方式。

4大逻辑结构如下。

（1）集合结构：其中的元素除了同属一个集合外，之间没有特别的关系。

（2）线性结构：其中的元素有一对一的关系。

（3）树形结构：其中的元素有一对多的层次关系。

（4）图形结构：其中的元素是多对多的关系。

物理结构指数据元素在计算机存储器中的存储形式，主要相对内存而言，硬盘、软盘、光盘等外部存储器的数据组织常用文件结构来描述。数据元素的存储结构形式主要有顺序存储和链式存储，前者把数据元素存放在地址连续的存储单元中，数据间的逻辑关系和物理关系一致，如数组；后者把数据元素放在任意的存储单元中，这组存储单元可以是连续的或非连续的。

线性表（Linear List）是数据结构的一种，一个线性表是n个具有相同特性的数据元素的有限序列。数据元素是一个抽象的符号，其具体含义在不同的情况下一般不同。

栈作为一种数据结构，是一种只能在一端进行插入和删除操作的特殊线性表。它按照先进后出的原则存储数据，先进入的数据被压入栈底。最后进入的数据被压在栈顶，需要读数据时从栈顶开始弹出数据（最后一个数据被第1个读出）。栈具有记忆作用，其插入与删除操作不需要改变栈底指针。

队列是一种特殊的线性表，只允许在表的前端（Front），即队头执行删除操作；在表的后端（Rear），即队尾执行插入操作。和栈一样，队列是一种操作受限制的线性表。队列中没有元素时称为“空队列”，队列中的数据元素称为“队列元素”。在队列中插入一个队列元素称为“入队”，从队列中删除一个队列元素称为“出队”。因为队列只允许在一端插入，在另一端删除，所以只有最早进入队列的元素才能最先从队列中删除，故队列又称为“先进先出（First In First Out，FIFO）线性表”。

树（Tree）是包含n（n>=0）个节点的有穷集，其中每个元素称为“节点”（Node），有一个特定的节点称为“根节点”或“树根”（Root）。

除根节点之外的其余数据元素被分为m（m≥0）个互不相交的集合T1，T2，……，Tm-1，其中每一个集合Ti（1<=i<=m）本身也是一棵树，被称为“原树的子树”（Subtree）。

图（Graph）是由顶点的有穷非空集合和顶点之间边的集合组成，通常表示为G（V,E）。其中G表示一个图，V是图G中顶点的集合；E是图G中边的集合。

说明如下。

（1）图中数据元素称为“顶点”（Vertext）。

（2）在图中不允许没有顶点，若V是图的顶点集合，那么V是非空有穷集合。

（3）图的任意两个顶点之间都可能有关系，用边来表示，边集可以为空。

为解决一个问题而采取的方法和步骤称为“算法”，计算机算法是其能够执行的算法，可分为如下两大类。

（1）数值运算算法：求解数值。

（2）非数值运算算法：运用在事务管理领域。

算法包括如下5个主要的性质。

（1）有穷性：一个算法应包含有限的操作步骤，而不能是无限的。

（2）确定性：算法中每一个步骤应当是确定的，而不应当是含糊和模棱两可的。

（3）输入：有零个或多个输入。

（4）输出：有一个或多个输出。

（5）有效性：算法中每一个步骤应当能有效地执行，并得到确定的结果。

算法的描述建立在语言基础之上，在将算法转化为高级语言源程序之前通常先采用文字或图形工具来描述。文字工具如自然语言和伪代码等，图形工具如流程图和N-S流程图等，也可以直接使用程序设计语言来描述。

一个算法的优劣可以用空间复杂度与时间复杂度来衡量，前者指依据算法编写程序后在计算机中运行时所耗费的时间大小；后者指依据算法编写成程序后在计算机中运行时所需的空间大小。