下载掌阅APP，畅读海量书库
立即打开
本节将介绍数据结构课程的研究内容、数据结构的基本概念，以及算法的概念、特性及评价方法。
数据结构（Data Structure）起源于程序设计。计算机解决问题时，一般要经过以下几个步骤：首先要将实际问题抽象出数学模型，然后针对数学模型设计出求解算法，最后编写程序上机调试，直到求出最终结果。数值计算问题的数学模型一般可由数学方程或数学公式来描述。
随着计算机科学技术的发展，计算机应用领域不再局限于数值计算，而是更多地应用于信息处理、智能控制、办公自动化等非数值计算领域。
对于非数值计算问题，如导学问题中涉及的学生信息管理、文件树形列表显示、道路最短路径求解等问题，它们的数学模型无法用数学方程或数学公式来描述，而是要用抽象出的数据模型来描述，并且要对这些模型设计相应的算法来求解。数据结构就是研究非数值计算问题中的数据以及它们之间的关系和操作算法的学科。数据结构主要包含3个方面的内容：数据的逻辑结构、数据的存储结构（物理结构）和数据的操作算法，如图1-3所示。
图1-3 数据结构研究的3个主要内容
1968年，数据结构作为一门独立的课程在美国开设，在这之前，它的某些内容已在其他课程中涉及。1968年，斯坦福大学的康纳德·克努特教授开创了数据结构的最初体系，他所著的 《计算机程序设计艺术》第一卷 《基本算法》是一本较系统地阐述数据的逻辑结构、存储结构及其操作算法的著作。后来各种版本的数据结构著作相继出现，如Pascal版、C版、C++版、Java版。我国于20世纪80年代初开设“数据结构”课程，该课程不仅是计算机专业教学计划中的核心课程之一，还是其他信息类专业的必修课。
20世纪60～80年代，计算机开始广泛应用于非数值计算领域，数据组织成为程序设计的重要问题。人们认识到程序设计规范的重要性，提出了结构化程序设计的思想。数据结构概念的引入对程序设计的规范化起到了重要作用。图灵奖获得者、瑞士计算机科学家尼古拉斯·沃斯教授曾提出“程序=数据结构+算法”，由此可以看出，数据结构和算法是构成程序的两个重要组成部分。
1. 相关术语
（1）数据
数据（Data）是信息的载体，是指所有能输入到计算机中并能被计算机程序识别和处理的符号集合。数据可以分为两大类：一类是整数、实数等数值数据，另一类是图形、图像、声音、文字等非数值数据。
（2）数据元素
数据元素（Data Element）是组成数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理。数据元素具有广泛的含义，一般来说，能独立、完整地描述问题的一切实体都是数据元素。数据元素又称为元素、结点、顶点或记录。构成数据元素的不可分割的最小单位称为数据项（Data Item）。数据元素是讨论数据时涉及的最小数据单位，其中的数据项一般不予考虑。
例如，问题1-4涉及的学生成绩表1-1中，一条学生记录就是一个数据元素或称为一个结点，其中的学号、姓名等就是数据项；问题1-5涉及的树形文件目录结构中，一个文件或文件夹称为一个数据元素或一个结点；问题1-6中涉及的城市地标建筑道路图中，一个地标建筑就是一个数据元素（或称为一个结点）。
（3）数据对象
数据对象（Data Object）是具有相同性质数据元素的集合，是数据的子集。在实际应用中处理的数据元素通常具有相同的性质。例如，学生成绩表中每个数据元素具有相同数目和类型的数据项，所有数据元素的集合就构成了一个数据对象。
2. 数据结构的三要素
数据结构的三要素包括数据的逻辑结构、存储结构和操作算法，如图1-4所示。
图1-4 数据结构三要素
（1）数据的逻辑结构
数据的逻辑结构（Logical Structure）是指数据元素之间的逻辑关系。逻辑关系是指数据元素之间的关联方式或邻接关系。数据的逻辑结构常用逻辑结构图来描述，其描述方法是将每一个数据元素看作一个结点，用圆圈表示，元素之间的逻辑关系用结点之间的连线表示。如果强调关系的方向性，则用带箭头的连线表示关系。
如图1-5所示，数据的逻辑结构分为4类。树结构和图结构也称为非线性结构。
图1-5 数据的逻辑结构分类
为了更确切地描述一种数据结构，通常采用如下的二元组形式化定义数据结构：
Data_Structure=（ D ， R ）
其中， D 是数据元素的有限集合， R 是 D 上关系的有限集合。
例如，有一种数据结构 T =（ D ， R ），其中：
D ={ a ， b ， c ， d ， e ， f ， g ， h ， i ， j }
R ={（ a ， b ），（ a ， c ），（ a ， d ），（ b ， e ），（ c ， f ），（ c ， g ），（ d ， h ），（ d ， i ），（ d ， j ）}
显然，数据结构 T 是一棵树形结构。
（2）数据的存储结构
数据的存储结构（Storage Structure）又称为物理结构，是数据元素及其逻辑结构在计算机中的表示。换言之，存储结构除了存储数据元素之外，必须隐式或显示地存储数据元素之间的逻辑关系。通常有两种存储结构：顺序存储结构和链式存储结构，如图1-6所示。
图1-6 数据的存储结构分类
顺序存储结构是指用一组连续的存储单元存储数据元素。数据元素之间的逻辑关系是由元素的存储位置来表示的。例如，线性表（ a ， b ， c ）的顺序存储示意图如图1-7所示。
链式存储结构是指用一组任意的存储单元存储数据元素。数据元素之间的逻辑关系是用指针来表示的。例如，线性表（ a ， b ， c ）的链接存储示意图如图1-8所示。
图1-7 线性表的顺序存储示意图
图1-8 线性表的链式存储示意图
数据的逻辑结构和存储结构是密切相关的。一般来说，一种数据的逻辑结构可以用多种存储结构来存储，而采用不同的存储结构，其数据处理的效率往往是不同的。
（3）数据的操作算法
对数据的操作有以下两个方面的含义：操作的定义和操作的实现，如图1-9所示。操作的定义取决于数据的逻辑结构，知道了问题中的数据及数据间的联系，就可以设计相应的数据操作方法。
图1-9 数据的操作
对数据的操作通常可以分为数值型计算和非数值型计算。对于数据的数值型操作在C/C++ 语言中都学习过，如整型、实型、字符型、指针、数组、结构体、类等数据类型（Da-ta Type）就规定了该类型数据的取值范围和对这些数据所能采取的操作。这里的数据类型是一组值的集合以及定义于这个值集上的一组操作的总称。例如，C/C++中的整型变量可以取的值是机器所能表示的最小负整数和最大正整数之间的任何一个整数，允许的操作有+、-、*、/、%、＜、＜=、＞、＞=、==、！=等。
常见的非数值型操作如下。
● 初始化：对存储结构设定初值或申请存储空间。
● 输出：输出所有数据元素的各数据项内容。
● 取值：获取指定数据元素的值。
● 置值：修改（更新）指定数据元素的值。
● 插入：增加数据元素。
● 删除：删除数据元素。
以上这些基本非数值型操作以及其他（如排序、求最短路径等）非数值型操作的实现与数据元素的存储形式密切相关，即数据操作算法的实现基于数据的存储结构。后续章节中将详细介绍各类问题操作算法的实现。
将一个数据结构以及定义在该结构上的一组操作的总称定义为抽象数据类型（Abstract Data Type，ADT）。数据类型和ADT的区别在于：数据类型是指高级程序设计语言支持的基本数据类型，而ADT是指自定义的数据类型。例如，本课程将要学习的表、栈、队列、树、图等结构就是一些不同的ADT。
1. 算法
（1）算法的概念
算法（Algorithm）是计算机求解特定问题的方法和步骤，是指令的有限序列。通常一个问题可以有多种算法，一个给定算法解决一个特定的问题。
算法具有以下5个重要特性：
1）输入。一个算法有零个或多个输入（即算法可以无输入），这些输入通常取自于某个特定的对象集合。
2）输出。一个算法有一个或多个输出（即算法必须要有输出），通常输出与输入之间有着某种特定的关系。
3）有穷性。一个算法必须（对任何合法的输入）在执行有穷步之后结束，且每一步都在有穷时间内完成。
4）确定性。算法中的每一条指令必须有确切的含义，不存在二义性，并且在任何条件下，对于相同的输入只能得到相同的输出。
5）可行性。算法描述的操作可以通过已经实现的基本操作执行有限次来实现。
算法与程序不同。程序（Program）是对一个算法使用某种程序设计语言的具体实现。原则上，任一算法可以用任何一种程序设计语言实现。算法的有穷性意味着不是所有的计算机程序都是算法。例如，操作系统是一个在无限循环中执行的程序，而不是一个算法，可以把操作系统的各个任务看成是一个单独的问题，每一个问题由操作系统中的一个子程序通过特定的算法来实现，得到输出结果后便终止。
（2）算法的评价
数据结构与算法之间存在着本质联系。本课程学习的目的就是要在某一种数据结构基础上学习算法设计方法，不但要设计正确的算法，而且要设计“好”的算法。什么样的算法是“好”的算法呢？通常一个“好”算法具有以下5个基本特性。
1）正确性。算法能满足具体问题的需求，即对于任何合法的输入，算法都会得出正确的结果。
2）健壮性（鲁棒性）。算法对非法输入的抵抗能力，即对于错误的输入，算法应能识别并做出处理，而不是产生错误动作或陷入瘫痪。
3）可读性。一个好的算法应该便于人们理解和相互交流。可读性好的算法有助于人们对算法的理解，反之，难懂的算法易于隐藏错误且难于调试和修改。
4）高效率。算法的效率通常是指算法的执行时间。对于同一个问题，如果有多个算法可以解决，则执行时间短的算法效率高。
5）低存储空间。算法需要的存储空间是指算法在执行过程中所需要的最大存储空间，它与问题规模有关。一个“好”算法应该占用较少的辅助空间。
（3）算法的描述方法
设计了一个算法之后，必须清楚准确地将所设计的求解步骤表达出来，即描述算法。算法的描述方法通常有自然语言、流程图、伪代码和程序设计语言等方法。下面以欧几里得算法（用辗转相除法求两个自然数 m 和 n 的最大公约数，并假设 m ≥ n ）为例进行介绍。
1）自然语言。用自然语言描述算法的最大优点是容易理解，缺点是容易出现二义性，并且算法通常都很冗长。欧几里得算法用自然语言描述如下：
①输入 m 和 n 。
②求 m 除以 n 的余数 r 。
③若 r 等于0，则 n 为最大公约数，算法结束；否则执行步骤④。
④将 n 的值放在 m 中，将 r 的值放在 n 中。
⑤重新执行步骤②。
2）流程图。用流程图描述算法的优点是直观易懂，缺点是严密性不如程序设计语言，灵活性不如自然语言。欧几里得算法用流程图描述如图1-10所示。
图1-10 用流程图描述算法
在计算机应用早期，使用流程图描述算法占有统治地位，但实践证明，除了一些非常简单的算法以外，这种描述方法使用起来非常不方便。
3）伪代码。伪代码是介于自然语言和程序设计语言之间的方法，计算机科学家对伪代码的书写形式没有做出严格的规定。它采用某一种程序设计语言的基本语法，操作指令可以结合自然语言来设计。算法中自然语言的成分有多少取决于算法的抽象级别。抽象级别高的伪代码自然语言多一些，抽象级别低的伪代码程序设计语言的语句多一些。只要具有一些程序设计语言基础的人都能阅读伪代码。欧几里得算法用C++伪代码描述如下：
伪代码不是一种实际的编程语言，但在表达能力上类似于编程语言，同时极小化了描述算法的不必要的技术细节，是比较合适的描述算法的方法，被称为“算法语言”。
本书采用基于C/C++语言的伪代码来描述算法，使得算法的描述简明清晰，既不拘泥于C/C++语言的实现细节，又容易转换为C/C++程序。
4）程序设计语言。用程序设计语言描述的算法能由计算机直接执行，缺点是抽象性差，使算法设计者拘泥于描述算法的具体细节，忽略了“好”算法和正确逻辑的重要性。此外，还要求算法设计者掌握程序设计语言及其编程技巧。欧几里得算法用C++语言书写的程序如下：
2. 算法分析
一种数据结构的优劣是由实现其各种操作的算法决定的。对数据结构的分析实质上就是对实现各种操作的算法进行分析。除了要验证算法是否正确解决问题外，还需要对算法的效率进行评价。对于一个实际问题的解决，可以提出若干算法，那么如何从这些可行的算法中找出最有效的算法呢？有了一个解决实际问题的算法，如何来分析它的性能呢？这些问题需要通过算法分析来确定。通常算法分析主要分析算法的时间代价和空间代价这两个主要指标。
可能有人认为，随着计算机功能的日益强大，程序的运行效率变得越来越不重要了。然而，计算机功能越强大，人们就越想去尝试解决更复杂的问题，而更复杂的问题需要更大的计算量。实际上，不仅需要算法，而且需要“好”算法。以破解密码的算法为例，理论上，通过穷举法列出所有可能的输入字符的组合情况可以破解任何密码，但是，如果密码较长或组合情况太多，这个破解算法就需要很长时间，可能几年、十几年甚至更多，这样的算法显然没有实际意义。所以，在选择和设计算法时要有效率的观念，这一点比提高计算机本身的速度更为重要。
（1）度量算法效率的方法
如何度量一个算法的效率呢？一种方法是事后统计的方法，先将算法实现，然后输入适当的数据运行，测算其时间和空间开销。事后统计的方法有以下缺点：
● 编写程序实现算法将花费较多的时间和精力。
● 所得实验结果依赖于计算机的软、硬件等环境因素，有时容易掩盖算法本身的优劣。
通常采用事前分析估算的方法——渐进复杂度（Asymptotic Complexity），它是对算法所消耗资源的一种估算方法。
（2）算法的时间复杂度
撇开与计算机软、硬件有关的因素，影响算法时间代价的最主要因素是问题规模。问题规模是指输入量的多少。一般来说，它可以从问题描述中得到。例如，对一个具有 n 个整数的数组进行排序，问题规模是 n ；对一个 m 行 n 列的矩阵进行转置，则问题规模是 m × n 。一个显而易见的事实是：几乎所有的算法，对于规模更大的输入都需要运行更长的时间。例如，需要更多时间来对更大的数组排序，更大的矩阵转置需要更长的时间。所以，运行算法所需要的时间是问题规模 n 的函数。
要精确地表示算法的运行时间函数常常是很困难的，即使能够给出，也可能是一个相当复杂的函数，函数的求解本身也是相当复杂的。算法时间分析度量的标准不是针对实际执行时间精确算出算法执行的具体时间，而是针对算法中基本语句的执行次数做出估计。设算法中基本语句执行的总次数是问题规模 n 的某个函数 f （ n ），因此算法时间量度记作： T （ n ）= O （ f （ n ）），它表示随着问题规模 n 的增大，算法执行时间增长率和 f （ n ）增长率相同，称为算法的渐近时间复杂度，简称时间复杂度（Time Complexity），通常用大 O 记号表示。这里的“ O ”是英文“Order”的缩写，但并不代表“顺序”的意思，而是一个数量级的概念，表示在计算任何算法的时间复杂度时忽略所有低次幂项和最高次幂项的系数。即
O （ a m n m + a m -1 n m -1 +…+ a 1 n + a 0 ）= O （ n m ）
例：求下列各程序段的时间复杂度。
1）for（i=1；i＜100；i++） s++；
该程序段的语句执行次数是常量，时间复杂度记为 O （1），称为常量阶。
2）for（i=0；i＜n；i++） s+=i；
该程序段基本语句s+=i，执行次数 f （ n ）= n ，因此它的时间复杂度 T （ n ）= O （ f （ n ））= O （ n ），称为线性阶。
3）for（i=0；i＜n；i++）
for（j=0；j＜n；j++）
s++；
该程序段基本语句s++；执行次数 f （ n ）= n + n +…+ n = n 2 ，时间复杂度 T （ n ）= O （ f （ n ））= O （ n 2 ），称为平方阶。
4）for（i=0；i＜n；i++）
for（j=i；j＜n；j++）
s++；
这是一个二重循环，基本语句s++；执行次数为 n +（ n -1）+（ n -2）+…+2+1= n （ n +1）/2。
该程序段的语句执行次数是 n 2 数量级，因此时间复杂度 T （ n ）= O （ n 2 ）。
5）for（i=1；i＜=n；i=2*i）
s++；
设该程序段基本语句s++的执行次数为 f （ n ），则有2 f （ n ） ≤ n ，即 f （ n ）≤log 2 n ，因此该段程序的时间复杂度为 O （log 2 n ），称为对数阶。
数据结构中常用的时间复杂度有以下7个： O （1）常量阶、 O （ n ）线性阶、 O （ n 2 ）平方阶、 O （ n 3 ）立方阶、 O （2 n ）指数阶、 O （log 2 n ）对数阶、 O （ n log 2 n ）二维阶。
（3）算法的空间复杂度
算法的存储空间需求类似于算法的时间复杂度，采用空间复杂度作为算法所需存储空间的量度，记作：
S （ n ）= O （ f （ n ））
其中， n 为问题的规模。一般情况下，一个程序在机器上执行时，除了需要寄存本身所用的指令、常数、变量和输入数据以外，还需要一些对数据进行操作的辅助存储空间。其中对于输入数据所占的具体存储量只取决于问题本身，与算法无关，因此只需要分析该算法在实现时所需要的辅助空间单元个数就可以。若算法执行时所需要的辅助空间相对于输入数据量而言是个常数，则称这个算法为原地工作，辅助空间为 O （1）。
算法执行时间的耗费和所占存储空间的耗费两者是矛盾的，难以兼得。即算法执行时间上的节省一定是以增加空间存储为代价的，反之亦然。不过，就一般情况而言，常常以算法执行时间作为算法优劣的主要衡量指标。