数据结构

数据结构是一门讨论"描述现实世界实体的数学模型(非数值计算)及其上的操作在计算机中如何表示和实现"的学科。

1 基本概念与术语

数据: 是所有能被输入到计算机中，且能被计算机处理的符号(数字、字符等)的集合，它是计算机操作对象的总称。是计算机处理的信息的某种特定的符号表示形式。

数据元素: 是数据(集合)中的一个"个体"，在计算机中通常作为一个整体进行考虑和处理，是数据结构中讨论的"基本单位"。有两类数据元素：一类是不可分割的"原子"型数据元素，如：整数"5"，字符 "N" 等；另一类是由多个款项构成的数据元素，其中每个款项被称为一个"数据项"。例如描述一个学生的信息的数据元素可由下列6个数据项组成。其中的出身日期又可以由三个数据项："年"、"月"和"日"组成，则称"出身日期"为"组合项"，而其它不可分割的数据项为"原子项"。数据项是数据结构中讨论的"最小单位"。

关键字: 指的是能识别一个或多个数据元素的数据项。若能起唯一识别作用，则称之为 "主" 关键字，否则称之为 "次" 关键字。在由多个数据项构成的数据元素中必定存在关键字。类似于学生的学号，不重复，因此可称为“主”关键字，而姓名有可能重名，因此可以称之为“次”关键字。

数据对象: 是具有相同特性的数据元素的集合，如：整数、实数等。它是数据的一个子集。在同一个数学模型中的数据元素必然具有相同特性。

1.1 数据结构

1.1.1 定义与分类

在客观世界中存在的各个事物之间存在着千丝万缕的"联系"，因此在计算机对它进行处理的时候必然也要将这种关系描述进去，如数学方程就是变量之间的约束关系的一种描述，在此称这种关系为结构，因此，数据结构是一堆数据元素和这些数据元素之间的关系的总和。即使数据元素集合相同，而其上的关系不同，则构成的数据结构不同。

数据结构是一个二元组

$LaTeX: Data\_Structures = ( D,S )$

其中：D是数据元素的有限集，S是D上关系的有限集。

按关系或结构分，数据结构可归结为以下四类：线性结构、树形结构、图状结构和集合结构。

线性结构是数据元素一对一的线性关系。
树形结构是数据元素一对多的层次关系。
图状结构是数据元素的网络结构。
集合结构中数据元素无关系。

数据结构应该包括数据的"逻辑结构"和数据的"物理结构"两个方面（层次）。

数据逻辑结构是对数据元素之间存在的逻辑关系的描述，它可以用一个数据元素的集合和定义在此集合上的若干关系表示。
数据物理结构是数据逻辑结构在计算机中的表示和实现，故又称数据"存储结构"。

1.1.2 存储结构

存储结构中关系的表示：

其一为"顺序映象"。以 "y 相对于 x 的存储位置" 表示 "y 是x的后继"，例如，令 y 的存储位置和 x 的存储位置之间相差一个预设常量C，C本身是个隐含值，由此得到的数据存储结构为"顺序存储结构"。
其二为"链式映象"。以和x绑定在一起的附加信息(指针)表示后继关系，这个指针即为 y 的存储地址，由此得到的数据存储结构为"链式存储结构"。

对每一个数据结构而言，必定存在与它密切相关的一组操作。若操作的种类和数目不同，即使逻辑结构相同，数据结构能起的作用也不同。不同的数据结构其操作集不同，但下列操作必不可缺：

结构的生成；
结构的销毁；
在结构中查找满足规定条件的数据元素；
在结构中插入新的数据元素；
删除结构中已经存在的数据元素；
遍历。

1.2 数据类型，抽象数据类型

数据结构中的数据类型，即抽象数据类型（Abstract Data Type 简称 ADT），是指一个数学模型以及定义在此数学模型上的一组操作。它具有两个特性：

数据抽象：用ADT描述程序处理的实体时，强调的是其本质的特征、其所能完成的功能以及它和外部用户的接口（即外界使用它的方法）。
数据封装：将实体的外部特性和其内部实现细节分离，并且对外部用户隐藏其内部实现细节。

抽象数据类型的形式描述为：

$LaTeX: ADT = ( D,S,P )$

其中：D 是数据对象，S 是 D 上的关系集，P 是 D 的基本操作集。

约定俗成：在以后均以如上相同形式描述抽象数据类型。其形式定义为：

ADT 抽象数据类型名 {
　数据对象： 数据对象的定义 
　数据关系： 数据关系的定义 
　基本操作： 基本操作的定义 
} ADT 抽象数据类型名

其中，数据对象和数据关系的定义用伪码描述，基本操作的定义格式为

基本操作名　（参数表）
初始条件：〈初始条件描述〉
操作结果：〈操作结果描述〉

基本操作有两种参数：赋值参数只为操作提供输入值；引用参数以&打头，除可提供输入值外，还将返回操作结果。
"初始条件"描述了操作执行之前数据结构和参数应满足的条件，若不满足，则操作失败，并返回相应出错信息。
"操作结果"说明了操作正常完成之后，数据结构的变化状况和应返回的结果。

1.3 算法

1.3.1 算法定义与特性

是对问题求解过程的一种描述，是为解决一个或一类问题给出的一个确定的、有限长的操作序列。严格说来，一个算法必须满足以下五个重要特性：

有穷性对于任意一组合法的输入值，在执行有穷步骤之后一定能结束。这里有两重意思，即算法中的操作步骤为有限个，且每个步骤都能在有限时间内完成。
确定性对于每种情况下所应执行的操作，在算法中都有确切的规定，使算法的执行者或阅读者都能明确其含义及如何执行。并且在任何条件下，算法都只有一条执行路径。确定性表现在对算法中每一步的描述都没有二义性，只要输入相同，初始状态相同，则无论执行多少遍，所得结果都应该相同。
可行性算法中的所有操作都必须足够基本，都可以通过已经实现的基本操作运算有限次实现之。可行性指的是，序列中的每个操作都是可以简单完成的，其本身不存在算法问题，例如，"求x和y的公因子"就不够基本。
有输入作为算法加工对象的量值，通常体现为算法中的一组变量。但有些算法的字面上可以没有输入，实际上已被嵌入算法之中。输入值即为算法的操作对象，但操作的对象也可以由算法自身生成。
有输出它是一组与"输入"有确定关系的量值，是算法进行信息加工后得到的结果，这种确定关系即为算法的功能。

在设计算法时，通常应考虑以下原则：首先说设计的算法必须是"正确的"，其次应有很好的"可读性"，还必须具有"健壮性"，最后应考虑所设计的算法具有"高效率与低存储量"。

1.3.2 算法的描述

数据结构的表示(存储结构)都用类型定义 (typedef) 的方式描述。基本数据元素类型约定为 ElemType，由用户在使用该数据类型时再自行具体定义。

基本操作的算法都用以下形式的函数描述：

　函数类型 函数名(函数参数表)
　{
　　// 算法说明
　　语句序列
　} // 函数名

除了函数的参数需要说明类型外，算法中使用的辅助变量可以不作变量说明，必要时对其作用给予注释。

1.3.3 算法效率的衡量方法

和算法执行时间相关的因素有：1）算法所用"策略"；2）算法所解问题的"规模"；3）编程所用"语言"；4）"编译"的质量；5）执行算法的计算机的"速度"。显然，后三条受着计算机硬件和软件的制约，既然是"估算"，仅需考虑前两条。

一个算法的"运行工作量"通常是随问题规模的增长而增长，因此比较不同算法的优劣主要应该以其"增长的趋势"为准则。假如，随着问题规模 n 的增长，算法执行时间的增长率和f(n)的增长率相同，则可记作：

$LaTeX: T(n) = O(f(n))$

称T(n)为算法的(渐近)时间复杂度。

" $LaTeX: O$ "的数学含义是，若存在两个常量 C 和n₀，当n>n₀时，

$LaTeX: |T(n)| \leq C|f(n)|$

则记作

$LaTeX: T(n) = O(f(n))$

它表明算法的执行时间是和f(n)"同数量级"的。 "渐近"是相对其它时间复杂度而言，但由于在本课程中不讨论其它类型的时间复杂度，故以后均简称时间复杂度。

估算算法的时间复杂度：

任何一个算法都是由一个"控制结构"和若干"原操作"组成的，因此一个算法的执行时间可以看成是所有原操作的执行时间之和

∑( 原操作(i)的执行次数X原操作(i)的执行时间 )

则算法的执行时间与所有原操作的执行次数之和成正比。"原操作"指的是固有数据类型的操作，显然每个原操作的执行时间和算法无关，相对于问题的规模是常量。同时由于算法的时间复杂度只是算法执行时间增长率的量度，因此只需要考虑在算法中"起主要作用"的原操作即可，称这种原操作为"基本操作"，它的重复执行次数和算法的执行时间成正比。

从算法中选取一种对于所研究的问题来说是基本操作的原操作，以该基本操作在算法中重复执行的次数作为算法时间复杂度的依据。这种衡量效率的办法所得出的不是时间量，而是一种增长趋势的量度。它与软硬件环境无关，只暴露算法本身执行效率的优劣。

算法时间复杂度取决于最深循环内包含基本操作的语句的重复执行次数，称语句重复执行的次数为语句的"频度"。

1.3.4 算法的存储空间需求

算法的存储量指的是算法执行过程中所需的最大存储空间。算法执行期间所需要的存储量应该包括以下三部分：(1)输入数据所占空间；(2)程序本身所占空间；(3)辅助变量所占空间。

类似于算法的时间复杂度，通常以算法的空间复杂度作为算法所需存储空间的量度。定义算法空间复杂度为

$LaTeX: S (n) = O(g(n))$

表示随着问题规模n的增大，算法运行所需辅助存储量的增长率与g(n)的增长率相同。

有些算法所需辅助空间都只是若干简单变量，和问题规模无关。这类所需额外空间相对于输入数据量来说是常量的算法，被称作是原地工作的算法。

也和算法时间复杂度的考虑类似，若算法所需存储量依赖于特定的输入，则通常按最坏情况考虑。

程序代码本身所占空间对不同算法通常不会有数量级之差别，因此在比较算法时可以不加考虑；算法的输入数据量和问题规模有关，若输入数据所占空间只取决于问题本身，和算法无关，则在比较算法时也可以不加考虑；由此只需要分析除输入和程序之外的额外空间。

2 线性表

请参见线性表。

3 参见

数据结构-清华大学视频教程