专栏：数据结构与算法分析
下一篇：（二）算法分析
文章目录
什么是数据结构(Data Structures)
??随着计算机运行速度的不断提高和存储容量的持续增长，计算机的功能日益强大，从而处理数据和解决问题的规模和复杂程度与日俱增。这不仅带来了需要认真研究的新课题，而且突出了原有数据结构和算法效率低下的缺点。为了解决这方面的问题，发展出了 “数据结构” 这一门学科。
??数据结构 这一门学科主要研究计算机组织和存储大量数据的方式。同时，数据结构 也是指相互之间存在一种或多种特定关系的数据元素的集合。
??
一、数据结构的基本概念和数据
??数据结构主要研究的是计算机组织和存储大量数据的方式，那数据是什么呢？
1. 数据(data)
??数据 是指所有能输入到计算机中并被计算机程序处理的信息的总称。一切能被编码的信息都可以称之为数据，如声音、图像等可以以某种方式编码成二进制数值后输入到计算机中进行处理。
2. 数据相关的基本概念
2.1 数据元素(data element)
??数据元素 是组成数据的，有一定意义的基本单位。数据元素在计算机程序中通常作为一个整体进行考虑和处理。
2.2 数据项(data item)
??一个数据元素可由多个数据项组成。例如一本书的书目信息为一个数据元素，书目信息中的每一项（如书名、作者名、出版社等）为一个数据项。数据项是数据的不可分割的最小单位。
2.3 数据对象(data object)
??数据对象 是性质相同的数据元素的集合，数据的子集。
?性质相同是指数据元素具有相同数量和类型的数据项。
2.4 数据结构(data structure)
??数据结构 相互之间存在一种或多种特定关系的数据元素的集合。
??在计算机中，数据元素并不是孤立、杂乱无序的，而是具有内在联系的数据集合。数据元素之间存在一种或多种特定关系，这种数据元素相互之间的关系称之为结构(structure)，通常有4类基本结构（逻辑结构）：① 集合 ② 线性结构 ③ 树形结构 ④ 图状结构 。
二、数据的逻辑机构和物理结构
??根据研究范围的不同，数据结构分为逻辑结构和存储结构，逻辑结构是指数据元素之间的关系，而存储结构是逻辑结构在计算机的中的表示方式。
1. 逻辑结构
??逻辑结构 是指在数据对象中，数据元素之间的相互关系。也是我们主要关注的问题。
??在具有相同特征的元素集合中，各个数据元素之间存在着某种关系。这种关系反映了该集合中数据元素所固有的一种结构，我们称之为 逻辑结构。
??逻辑结构分为以下四种：
??上面后三种逻辑结构主要分为 线性结构 和 非线性结构，线性结构中各元素之间的关系简单，相比之下，非线性结构元素之间的关系就复杂得多。
1.1 集合
??集合 中的数据元素除了同属于一个集合外，它们之间没有关系。如同数学中的集合。
1.2 线性结构
??线性结构 中的数据元素之间存在着一对一的线性关系。(关系表示中的箭头未画出，线性结构箭头指向为从左到右，即一存在关系的两个数据元素，左边为前件，右边为后件)
??线性结构存在着 唯一 的 “第一个元素” 和 “最后一个元素”，每一个元素都连接到它的前一个元素和后一个元素（“第一个元素”没有前一个元素，“最后一个元素”没有后一个元素）。
1.3 树形结构
??树形结构中的数据元素之间存在着一种一对多的层次关系。数据元素之间有明显的层次关系，并且每一层上的数据元素可能和下一层中的多个元素相关，但只能和上一层中的一个元素相关。
??线性结构是树形结构的特殊情况。
1.4 图状结构
??图状结构 的数据元素是多对多的关系。数据元素之间的关系可以是任意的，图中任意两个数据元素之间都可能相关。
??树形结构是图状结构的特殊情况。
2. 存储结构
??数据结构在计算机中的表示称为存储结构 ，又称 物理结构。 物理结构包含数据元素的表示和逻辑关系的表示。
??数据是数据元素的集合，数据元素最终是要存储在计算机的存储器中。
??存储器主要是指计算机内存，计算机是可以直接通过数据总线访问的，并非指像硬盘之类的外部存储器。
2.1 顺序存储 和非顺序存储
??这些存储结构分为两类，一种是顺序存储，一种是非顺序存储。
??在顺序存储中，数据元素按一定的顺序连续地存储在存储器中，这些元素的相对位置是固定的，只需要知道数据元素之间的逻辑关系和其中一个数据元素的存储位置，直接就能计算出全部数据元素的位置。
??在 非顺序存储 中，数据元素之间的相对位置并不固定，也不要求连续存储，需要通过额外的位置信息来得到数据元素在存储器中的位置。这个额外的位置信息可以是存储在某些存储单元上的位置数据，也可以是由公式计算得到。
??这个存储位置的连续，实际上是相对的。在操作系统上，我们看到的内存地址一般是虚拟地址，虚拟地址由系统转换到存储器上的实际地址，这个实际地址我们称为物理地址，由CPU的地址总线确定。系统一般对内存作分页管理，连续的虚拟地址也有可能被分配到不连续的内存页上。
??像嵌入式芯片这种，我们一般操作的直接就是内存的物理地址，内存地址没有经过系统转换，只要内存地址连续，存储位置就连续。
??所以这里存储位置连续只要求虚拟内存层面上的连续。
2.2 四种存储结构
??数据元素的存储结构一般来说有四种： 顺序存储 、 链式存储、索引存储 和 散列存储。
??有些书里则认为是只分为 顺序存储 和 链式存储 两种。如 严蔚敏的《数据结构（C语言版）》，以及其它根据这一教材改编的如 程杰《大话数据结构》等，徐士良《计算机软件技术基础》则提到这四种。这里就不多探究存储结构实际上到底是几种了，因为在外国教材中，Mark Allen Weiss著的《数据结构与算法分析 (C语言描述) 》， 还有著名的**《算法导论》**，《算法（第4版）》等，都没有专门提到存储结构的种类，只专注数据结构该如何实现。
??链式存储、索引存储和散列存储属于非顺序存储，因为这几种存储结构都需要提供额外位置信息才能知道数据元素的位置，并且数据元素的存储位置并不要求连续。
??存储结构中用得最多的是顺序存储结构和链式存储结构。
2.2.1 顺序存储结构
??顺序存储结构是把数据元素存放在地址连续的存储单元中，并按照某种固定的位置对应关系表示数据元素之间的逻辑关系。
??例如逻辑关系为线性结构的几个数据元素，以顺序存储的方式，将会被存储在一组地址连续的存储单元中，并且，假设每个元素需要占用 l l l个存储单元元素存储位置关系满足第 i + 1 i+1 i+1 个元素与第 i i i个元素存储位置相差为 l l l。
??一般来说，如果第 i i i 个元素的存储位置为 A i A_{i} Ai?，那么第 i + 1 i+1 i+1个元素的存储位置为 A i + l A_{i} + l Ai?+l。
??顺序存储结构在C/C++中对应数组。
??对于逻辑关系为树形结构的数据元素来说，我们可以按固定顺序给数据元素编号，然后按编号顺序存储在连续的存储单元中。
??数据元素编号与逻辑关系的对应关系为：与第
i
i
i个元素有关系的两个元素分别是第
2
i
2i
2i 个元素和第
2
i
+
1
2i+1
2i+1 个元素。
??顺序存储结构的数据元素是连续存放，元素位置计算方式简单，可以随机访问元素。并且现在CPU有多级缓存结构，会一次读取多个存储单元，连续存储有助于加快存取速度。缺点是元素的逻辑关系和存储位置直接关联，当需要删除或插入数据元素时，部分元素根据逻辑关系所对应的存储位置也相应发生改变，此时必须将这些元素移动到相应位置上。
2.2.2 链式存储结构
??链式存储结构为非顺序存储结构，元素在存储器上存储位置允许不连续，可以按任意顺序存放。与元素有逻辑关系的元素的存放位置，由额外的位置信息确定。在链式存储结构中，通常将数据元素和与其有逻辑关系的元素的位置信息一同存储，称为结点。
??结点中存放元素的存储区域称为数据域，而存放位置信息的存储区域称为指针域(指针是C/C++中的一种存储地址的变量类型)。
??如线性结构对应的链式存储中，结点中的指针域存放下一个元素的位置。
??在链式存储中，与某一个元素有逻辑关系的其它元素的位置，需要读取该元素对应结点的位置信息。如果想按顺序访问所有元素，需要从第一个结点开始逐个读取才能依次找到下一个元素的位置，直至访问完所有元素。
??链式存储中数据元素间的逻辑关系靠结点存储的位置信息确定，而与元素的存放位置无关。因此当逻辑关系改变时，只需要改变有关的几个结点的位置信息即可，而不需要大量地移动元素。
2.2.3 索引存储结构
??索引存储结构是将原来一个集合中的数据元素分成多个子集，各个子集的元素分别存储，再额外创建一个索引结构来保存子集所存储的位置信息。
??例如，将一张线性表分成多个子表进行存储，并创建一个用于查找元素所在的子表位置的索引表。搜索元素时，先在索引表中查找所在子表的存储位置，再到对应子表中进行查找。
??索引存储比较重要的是元素如何划分子集以及如何设计索引结构。子集的存储可以使用任意的存储结构，如顺序存储，链式存储等。索引结构通常采用顺序存储的索引表和链式存储的索引树。
??索引表本身存储的也是数据，如果用索引存储结构来存储，则构成二重索引存储结构，通过嵌套，可以形成多重索引结构。
??索引存储结构的优势在于，既有非顺序存储结构可不连续存储的优势，同时又不像链式存储结构那样查找元素需要依次访问结点，减少了访问次数。对外部存储器这种慢速设备进行搜索时，索引存储结构就很有优势。只需将小空间的索引表（树）读取到内存中，搜索完成后再去小范围查找对应文件，减少对外存的访问次数，提高查找效率。
2.2.4 散列存储结构
??散列存储结构是建立一个由元素关键字直接对应到存储位置的映射关系，然后由元素关键字来确定元素存储位置的一种存储结构。这个映射关系称为散列函数，散列的英文是 Hash，所以又音译为哈希函数。
??散列存储结构主要用于加快搜索，通过元素的关键字便可快速计算出元素的存储位置。
??散列存储结构最重要的是如果构建出合适的散列函数。如果函数映射出的位置过于分散，那么会造成过多的内存空间浪费。同时，不同元素的关键字通过散列函数映射得到的存储位置可能一致，此时又会有冲突问题，可以创建一个子表来存储冲突的元素，也可以通过再次计算等方式来重新安排元素的存储位置。
??如下图所示，用哈希存储结构存储元素时，取数据元素值的个位数作为关键字
k
e
y
key
key，散列函数取：
f
:
(
k
e
y
+
7
)
%
8
f:(key + 7) \% 8
f:(key+7)%8??即将
k
e
y
key
key 加 7 后对 8 取模得到元素的存储地址，这样就能将元素对应到 0~7之间的存储位置上(当然，这里并没有展示出现冲突的情况)。在查找元素时，直接以同样方式计算即可得到元素的存储位置，所以散列技术既是一个存储技术，也是一种查找技术。
专栏：数据结构与算法分析
下一篇：（二）算法分析