1.1.2　数据结构的基本概念和术语

①数据（Data）：是信息的载体，是描述客观事物的数、字符，以及所有能输入到计算机中、能被计算机程序识别和处理的符号的集合。数据又可分为数值性数据和非数值性数据两大类。数值性数据如整数、实数、复数等，一般用于工程和科学计算等；非数值性数据如字符、字符串、文字、图形、语音等。

②数据元素（Data Element）：是数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理。

③数据项（Data Item）：是具有独立含义的最小标识单位。有时，一个数据元素可由若干数据项组成。如整数集合中，10就可以称为是一个数据元素。又如在一个关系型数据库中，一个记录可称为一个数据元素，而这个元素中的某一字段就是一个数据项。

④数据对象（Data Object）：数据的子集。数据对象是具有相同性质的数据成员（数据元素）的集合。如整数数据对象N={0，1，2，…}，英文字母数据对象LETTER={'A'，'B'，…，Z'}。

⑤数据类型（Data Type）：是一个值的集合以及在这些值上定义的一组操作的总称。

⑥结构（Structure）：数据元素相互之间的关系称为结构，有以下4种类型的基本结构。

●　集合结构：结构中的数据元素之间除了“同属于一个集合”的关系外，别无其他关系。

●　线性结构：结构中的数据元素之间存在一对一的关系。

●　树状结构：结构中的数据元素之间存在一对多的关系。

●　图状结构或网状结构：结构中的数据元素之间存在多对多的关系。

以上4种类型的基本结构如图1-1所示。

⑦数据结构（Data Structure）：相互之间存在一种或多种特定关系的数据元素的集合。

数据结构的定义虽然没有统一的标准，但是它包括以下3方面的内容：逻辑结构、存储结构和对数据的操作。为了增加对数据结构的认识，举一个实例，如表1-1所示。

表1-1是一个班级学生的成绩表（也称成绩数据库），同时，它也构成一个数据结构。它由很多记录（数据元素）组成，每个元素又由多个数据列（字段、数据项）组成。那么这张表的逻辑结构是怎么样的呢？我们分析数据结构都是从结点（其实也就是元素、记录、顶点，虽然在各种情况下所用名字不同，但指的是同一个东西）之间的关系来分析的，对于这个表中的任意一个记录（结点），它只有一个直接前驱和一个直接后继（前驱、后继就是前相邻、后相继的意思），整个表只有一个开始结点和一个终端结点。所有这些就构成了这个表的逻辑结构，亦即逻辑结构就是数据元素之间的逻辑关系。

数据的逻辑结构通常分两大类：线性结构和非线性结构。

①线性结构：其特征是若结构为非空集，则该结构有且只有一个开始结点和一个终端结点，并且所有结点最多只有一个直接前驱和一个直接后继。线性表就是一个典型的线性结构。

②非线性结构：其逻辑特征是该结构中一个数据元素可能有多个直接前驱和直接后继。非线性结构中最普遍的是图结构。

数据的存储结构是指数据的逻辑结构在计算机存储空间中的存放形式。在数据的存储结构中，不仅要存放各数据元素的信息，还需要存放各数据元素之间的前后间关系的信息。数据的存储结构有时也称为数据的物理结构，它是逻辑结构在计算机存储器中的物理实现。

表1-1中的数据元素在计算机中可以采取不同的存储方式：①将数据元素连续存放在一片内存单元中；②将数据元素随机地存放在不同的内存单元中，再用指针将这些数据元素链接在一起。这两种存储方式就形成两种不同的存储结构。

常用的数据存储结构有以下4种基本形式：

1）顺序存储

该方法把逻辑上相邻的数据元素存储在物理位置上相邻的存储单元中，数据元素间的逻辑关系由存储单元的邻接关系来体现。由此得到的存储表示称为顺序存储结构（Sequential Storage Structure），通常借助程序语言的数组来实现。顺序存储方法主要应用于线性的数据结构。非线性的数据结构也可通过某种线性化的方法实现顺序存储。

2）链式存储

该方法不要求逻辑上相邻的数据元素在物理位置上也相邻，数据元素间的逻辑关系由附加的指针字段表示。由此得到的存储表示称为链式存储结构（Linked Storage Structure），通常借助于程序语言的指针类型来实现。

3）索引存储

该方法通常在存储数据元素信息的同时，还建立附加的索引表。索引表由若干索引项组成。若每个数据元素在索引表中都有一个索引项，则该索引表称为稠密索引（Dense Index）。若一组数据元素在索引表中只对应一个索引项，则该索引表称为稀疏索引（Spare Index）。索引项的一般形式是“（关键字，地址）”。关键字是能唯一标识一个数据元素的数据项。稠密索引中索引项的地址表示数据元素所在的存储位置；稀疏索引中索引项的地址表示一组数据元素的起始存储位置。

4）散列存储

该方法的基本思想是：根据数据元素的关键字直接计算该数据元素的存储地址。

以上4种基本存储方法既可单独使用，也可组合起来对数据结构进行存储。同一逻辑结构采用不同的存储方法，可以得到不同的存储结构。选择何种存储结构表示相应的逻辑结构，视具体要求而定，主要考虑运算方便及算法的时间和空间要求。

除了逻辑结构和物理结构外，数据结构的第三个内容是对数据的操作（运算），如一张表格，如何进行查找、增加、修改、删除记录等操作？这也就是数据的运算，它不仅仅是指加减乘除算术运算，在数据结构中，这些运算常常涉及算法问题。

算法（Algorithm）是对特定问题求解步骤的一种描述，由有限的指令序列组成，可完成某项特定的任务。为了保证正确地处理数据，学习数据结构必然要学习算法。要理解数据结构本身，重要的是理解实现数据结构操作的算法。算法和数据结构是相辅相成、缺一不可的两个方面。数据结构是算法处理的对象，也是设计算法的基础。一个具体问题的数据在计算机中往往可以采用多种不同的数据结构来表示；一个计算过程的实现又常常有多种可用的算法。因此，选择什么样的算法和数据结构就成为实现程序过程中最重要的一个课题。

（1）算法的5个重要特性

①有穷性：一个算法必须在执行有穷步之后结束。

②确定性：算法的每一个步骤，必须是确切地定义的。

③输入：一个算法有零个或多个输入。

④输出：一个算法有一个或多个输出。

⑤可行性：算法中执行的任何计算步都是可以被分解为基本的可执行的操作步，即每个计算步都可以在有限时间内完成（也称之为有效性）。

有的书把算法的特性中的输入/输出特性又称为“有足够的情报”，是指有足够条件的“输入”能让算法得到结果，这个情报也包括了结果。

（2）算法的两种基本要素

算法由数据对象的运算和操作、算法的控制结构两种基本要素组成。

①算法中对数据的运算和操作：算法实际上是按解题要求，从环境中能进行的所有操作中选择合适的操作所组成的一组指令序列。即算法是由计算机能够处理的操作所组成的指令序列。

②算法的控制结构：在算法中，操作的执行顺序又称算法的控制结构，一般的算法控制结构有3种：顺序结构、选择结构和循环结构。

（3）算法设计的基本方法

①列举法：基本思想是，根据提出的问题，列举出所有可能的情况，并用问题中给定的条件检验哪些是满足条件的，哪些是不满足条件的。

②归纳法：基本思想是，通过列举少量的特殊情况，经过分析，最后找出一般的关系。

③递推：是从已知的初始条件出发，逐次推出所要求的各个中间环节和最后结果。本质也是一种归纳，递推关系式通常是归纳的结果。

④递归：在解决一些复杂问题时，为了降低问题的复杂程序，通常是将问题逐层分解，最后归结为一些最简单的问题。分为直接递归和间接递归两种方法。

⑤减半递推技术：减半递推即将问题的规模减半，然后，重复相同的递推操作。

⑥回溯法：是一种选优搜索法，又称为试探法，按选优条件向前搜索，以达到目标。但当探索到某一步时，发现原先选择并不优或达不到目标，就退回一步重新选择，这种走不通就退回再走的技术为回溯法，而满足回溯条件的某个状态的点称为“回溯点”。

（4）算法分析

在使用算法对特定的问题进行求解时，往往涉及对算法的分析。算法分析（Algorithm Analysis）是指对算法的执行时间和所需内存空间的估算。同一问题的求解往往可以使用不同的算法。通过算法分析可以比较两个算法的效率高低。

①算法的时间复杂度：执行一个算法所花费的时间代价。当要解决的问题的规模以某种单位由1增至n时，对应算法所耗费的时间也以某种单位由f（1）增至f（n）。此时称该算法的时间复杂度为f（n）。

②算法的空间复杂度：执行一个算法所需占用的空间代价。当要解决的问题的规模以某种单位由1增至n时，对应算法所需占用的空间也以某种单位由g（1）增至g（n）。此时称该算法的空间复杂度为g（n）。

③问题的规模：指的是算法要解决的问题所要处理的数据量的大小。例如，对n个记录进行排序，n就是问题的规模。再例如，求n阶矩阵的转置矩阵，n也可以看作是问题的规模。时间单位一般规定为一个简单语句（如赋值语句、条件判断语句等）所用的时间。空间单位一般规定为一个简单变量（如整型、字符型、浮点型等）所占用的存储空间大小。

要全面地分析一个算法，应考虑该算法在最坏情况下的代价、最好情况下的代价、平均情况下的代价。然而，要全面准确地分析每一个算法是相当困难的，一般考虑这个算法在最坏情况下的代价。在多数情况下，只要得到一个估计值就足够了。

在描述算法分析的结果时，通常采用O表示法：即某个算法的时间代价（或空间代价）为O（f（n）），如果存在正常数c和n0，当问题的规模n≥n0时，该算法的时间代价（或空间代价）为T（n）≤c·f（n），这时也称该算法的时间（或空间）代价的增长率为f（n）。这种说法意味着，当n充分大时，该算法的复杂度不大于f（n）的一个常数倍。

采用O表示法简化了时间复杂度和空间复杂度的度量，其基本思想是关注复杂性的数量级，而忽略数量级的系数，这样在分析算法的复杂度时，可以忽略零星变量的存储空间和个别语句的执行时间，重点分析算法的主要代价。

常见的时间复杂度按数量级递增排列依次为常数阶O（1）、对数阶O（log2n）、线性阶O（n）、线性对数阶O（n log2n）、平方阶O（n2）、立方阶O（n3）、k次方阶O（nk）、指数阶O（2n）。

理解了逻辑结构、存储结构以及对数据的操作3个问题，即可理解数据结构的概念。

在不引起混淆的情况下，通常将数据的逻辑结构简称为数据结构，但要清楚的是，数据结构研究的不仅仅是数据的逻辑结构，还包含对数据的存储结构以及数据的操作的研究。