第 1 章 课 程 概 论 1.1 课程的初步认识 1.2 数据结构的基本概念 1.3 算法及算法分析 1.4 实习一： 常用算法

1.1 课程的初步认识 ［例 1］ 人事信息检索问题。当我们要查找某公司员工的信息时， 一般是给出该员工的编号或姓名，通过信息目录卡片和信息卡片来查得该员工的有关信息。但也有可能要查找某一种类别的员工信息。例如，我们要查找该公司的员工中具有“高级程序员”技术职称的人员信息，或者是属于某一行政分组的人员信息等。若利用计算机来实现人事信息检索，则计算机所处理的对象便是这些信息目录卡片及员工信息卡片中的信息。为此，在计算机中必须建立与存储与此相关的三张表。

一张是按员工编号排列的员工信息表，另两张分别是按技术职称与行政分组顺序排列的索引表。员工信息表中存放着编号、姓名、职称、职务及爱好等信息，在职称索引表中存放着职称与员工编号的对应信息，在组别索引表中存放着行政分组与员工编号的对应信息，如图1.1所示。 

图 1.1 程序中的数据结构 (a) 员工信息表；

图 1.1 程序中的数据结构 (b) 职称索引表； (c) 组别索引表

［例 2］ 八皇后问题。在八皇后问题中，处理过程不是根据某种确定的计算法则，而是利用试探和回溯的探索技术求解。为了求得合法布局，在计算机中要存储布局的当前状态。从最初的布局状态开始，一步步地进行试探， 每试探一步形成一个新的状态， 整个试探过程形成了一棵隐含的状态树，如图1.2所示（为了描述方便， 我们将八皇后问题简化为四皇后问题）。 回溯法求解过程实质上就是一个遍历状态树的过程。在这个问题中所出现的“树”也是一种数据结构，它可以应用在许多非数值计算的问题中。

图 1.2 四皇后问题中隐含的状态树

[例 3］ 交通咨询问题。在交通咨询系统中，我们可以采用一种图的结构来表示实际的交通网络。图中的顶点表示城市， 边表示城市间的交通联系，对边所赋予的权值可以表示两城市间的距离，或途中所需的时间，或交通费用等等。考虑到交通图的有向性（如航运，逆水和顺水时的船速就不一样），图中的边可以用弧线来表示，如图1.3所示。这个咨询系统可以回答旅客提出的各种问题。

例如，从某地到某地应如何走才最节省费用，也就是要求从某地到某地的最短路径。在这个问题中所使用的图也是一种数据结构。 图 1.3 一个表示交通网的图

1.2 数据结构的基本概念 1.2.1 基本术语 数据（Data）是信息的载体，它能够被计算机识别、存储和加工处理。它是计算机程序加工的原料。 例如，一个利用数值分析方法解代数方程的程序所用的数据是整数和实数，而一个编译程序或文本编辑程序所使用的数据是字符串。随着计算机软、硬件技术的发展，应用领域的扩大， 数据的含义也随之拓宽。如多媒体技术中所涉及的视频和音频信号，经采集转换后都能形成被计算机所接受的数据。

数据元素（Data Element）是数据的基本单位。在不同的条件下，数据元素又可称为元素、结点、顶点、 记录。例如， 在人事信息检索问题中，员工信息表的一个记录；在八皇后问题中，状态树的一个状态； 在交通咨询系统中，交通网的一个顶点等等。在数据元素是记录的情形下，一个数据元素又可由若干数据项（也称为字段、 域）组成， 数据项是具有独立含义的最小的单位。

数据元素类（Data Element Class）是具有相同性质的数据元素的集合。在某个具体问题中，数据元素都具有相同的性质（元素值不一定相等），属于同一数据元素类， 数据元素是数据元素类的一个实例。例如， 在交通咨询系统的交通网中， 所有的顶点是一个数据元素类，顶点A和顶点B各自代表一个城市， 是该数据元素类中的两个实例，其数据元素的值分别为A和B。

1.2.2 数据结构的概念 数据结构（Data Structure）是指互相之间存在着一种或多种关系的数据元素的集合。在任何问题中，数据元素之间都不会是孤立的， 在它们之间都存在着这样或那样的关系，这种数据元素之间的关系称为结构。根据数据元素间关系的不同特性， 通常有下列四类基本的结构： 

（1） 集合结构。在集合结构中，数据元素间的关系是“属于同一个集合”，集合是元素关系极为松散的一种结构。 （2） 线性结构。 该结构的数据元素之间存在着一对一的关系。 （3） 树形结构。 该结构的数据元素之间存在着一对多的关系。 （4） 图状结构。该结构的数据元素之间存在着多对多的关系，图状结构也称网状结构。图1.4表示上述四类基本结构的关系图。

(a) 集合； (b) 线性； (c) 树形； (d) 图状 图 1.4 四类基本结构的关系图 (a) 集合； (b) 线性； (c) 树形； (d) 图状

1.2.3 逻辑结构和物理结构 数据结构包括数据的逻辑结构和数据的物理结构。 数据的逻辑结构可以看作是从具体问题中抽象出来的数学模型，它与数据的存储无关，而我们研究数据结构的目的是为了在计算机中实现对它的操作，为此还需要研究如何在计算机中表示一个数据结构。 数据结构在计算机中的表示（又称映象）称为数据的物理结构，或称存储结构。 它所研究的是数据结构在计算机中的实现方法， 包括数据结构中元素的表示及元素间关系的表示。

数据的存储结构可采用顺序存储或链式存储的方法。  顺序存储方法是把逻辑上相邻的元素存储在物理位置相邻的存储单元中， 元素间的逻辑关系由存储单元的相邻关系来体现。 由此得到的存储表示称为顺序存储结构，顺序存储结构通常是借助于程序语言中的数组来实现的。  链式存储方法对逻辑上相邻的元素不要求其物理位置相邻，元素间的逻辑关系通过附设的指针字段来表示。由此得到的存储表示称为链式存储结构，链式存储结构通常是借助于程序语言中的指针类型来实现的。

1.2.4 数据结构形式定义 从上面所介绍的数据结构的概念中我们可以知道，一个数据结构有两个要素。一个是元素的集合，另一个是关系的集合。因此在形式上， 数据结构通常可以采用一个二元组来表示， 即 Data Structure =(D, R) 其中， D是数据元素的有限集， R是D上关系的有限集。

图 1.5 员工信息表中的数据结构

如果我们使用二元组来表示上述的线性结构， 则可表示为 LinearList =(D, R)，其中：  树形结构则可表示为 Tree =(D, R) 其中：  D={01, 02, 03, 04, 05, 06, 07, 08, 09, 10}  R＝{<01, 05>, <01, 06>, <05, 02>, …… <06, 10>}

图状结构则可表示为 Graph =(D, R) 其中：  D={01, 02, 03, 04, 05, 06, 07, 08, 09, 10, 网， 羽， 乒}  R＝{<01, 羽>, <01, 乒>, <05, 网>, <05, 乒>, <06, 网>}

1.3 算 法 1.3.1 算法的概念及描述 1. 算法（Algorithm）的定义 1.3 算 法 1.3.1 算法的概念及描述 1. 算法（Algorithm）的定义 Algorithm is a finite set of rules which gives a sequence of operation for solving a specific type of problem. (算法是规则的有限集合， 是为解决特定问题而规定的一系列操作。 )

2. 算法的特性  (1) 有限性：有限步骤之内正常结束， 不能形成无穷循环。 (2) 确定性： 算法中的每一个步骤必须有确定含义， 无二义性。  (3) 输入： 有多个或0个输入。 (4) 输出： 至少有一个或多个输出。  (5) 可行性： 原则上能精确进行， 操作可通过已实现的基本运算执行有限次而完成。在算法的五大特性中， 最基本的是有限性、 确定性和可行性。

3. 算法设计的要求 １） 算法的正确性 (1) 所设计的程序没有语法错误；  (2) 所设计的程序对于几组输入数据能够得出满足要求的结果； (3) 所设计的程序对于精心选择的典型、 苛刻而带有刁难性的几组输入数据能够得到满足要求的结果。  (4) 程序对于一切合法的输入数据都能产生满足要求的结果。

例如： 要求n个数的最大值问题， 给出示意算法如下：  max:=0;  for（i=1； i<=n; i++）  { scanf(″%f″, x);  if (x>max) max=x;  }

2） 可读性 3） 健壮性 4） 高效率和低存储量

1.3.2 对算法作性能评价 1. 性能评价 对问题规模和该算法在运行时所占的空间S与所耗费的时间T给出一个数量关系的评价。  1.3.2 对算法作性能评价 1. 性能评价 对问题规模和该算法在运行时所占的空间S与所耗费的时间T给出一个数量关系的评价。  问题规模N对不同的问题其含义不同，对矩阵是阶数， 对多项式运算是多项式项数，对图是顶点个数，对集合运算是集合中的元素个数。

2. 有关数量关系的计算 数量关系评价体现在时间——算法编程后在机器中所耗费的时间。 数量关系评价体现在空间——算法编程后在机器中所占的存储量。 1） 关于算法执行时间 一个算法的执行时间大致上等于其所有语句执行时间的总和， 对于语句的执行时间是指该条语句的执行次数和执行一次所需时间的乘积。 

2） 语句频度 语句频度是指该语句在一个算法中重复执行的次数。 例1-1 两个n×n阶矩阵相乘。

3） 算法的时间复杂度 原操作是指从算法中选取一种对所研究问题是基本运算的操作， 用随着问题规模增加的函数来表征, 以此作为时间量度。 而对于算法分析，我们关心的是算法中语句总的执行次数T(n)是关于问题规模n的函数，进而分析T(n)随n的变化情况并确定T(n)的数量级（Order of Magnitude）。在这里， 我们用“O”来表示数量级，这样我们可以给出算法的时间复杂度概念。 所谓算法的时间复杂度， 即是算法的时间量度，记作： T(n)=O(f(n))

它表示随问题规模n的增大，算法的执行时间的增长率和f(n)的增长率相同，称作算法的渐进时间复杂度，简称时间复杂度。 一般情况下， 随n的增大，T(n)的增长较慢的算法为最优的算法。 例如： 在下列三段程序段中，给出原操作x=x+1的时间复杂度分析。  （1） x=x+1 ； 其时间复杂度为O(1)， 我们称之为常量阶； （2） for (i=1; i<= n; i++) x=x+1; 其时间复杂度为O(n)， 我们称之为线性阶；

（3） for (i=1; i<= n; i++) for (j=1; j<= n; j++) x=x+1; 其时间复杂度为O(n2), 我们称之为平方阶。  此外算法还能呈现的时间复杂度有对数阶O(log2n), 指数阶O(2n)等。

4） 数据结构中常用的时间复杂度频率计数 数据结构中常用的时间复杂度频率计数有7个：  O(1) 常数型 O(n)线性型 O(n2)平方型 O(n3)立方型 O(2n)指数型 O(log2n)对数型 O(nlog2n)二维型 按时间复杂度由小到大递增排列成表1-3（当n充分大时）。 不同数量级的时间复杂度的形状如图1.6所示， 表1-3与图1.6是同一问题的不同表示形式。一般情况下，随n的增大，T(n)增长较慢的算法为最优的算法。从中我们应该选择使用多项式阶O(nk)的算法， 而避免使用指数阶的算法。

表1-1 常用的时间复杂度频率表

例如： 下列程序段： for (i=1; i< n; i++) for (j=i; j<= n; j++) x++; 有一个二重循环， 语句x++的执行频度为 n+(n-1)+(n-2)+…+3+2+1 =n(n+1)/2 而该语句执行次数关于n的增长率为n2, 即时间复杂度为O(n2)。

关于算法的存储空间需求，类似于算法的时间复杂度， 我们采用空间复杂度作为算法所需存储空间的量度，记作： S(n)=O(f(n)) 6） 算法的空间复杂度 关于算法的存储空间需求，类似于算法的时间复杂度， 我们采用空间复杂度作为算法所需存储空间的量度，记作： S(n)=O(f(n))