Question

数据结构

Answer 1

一什么是数据结构

      数据结构是指相互有关联的数据元素的集合。数据结构研究的内容包括以下3个方面，①数据集合中各数据元素之间所固有的逻辑关系，即数据的逻辑结构。②在对数据进行处理时，各数据元素在计算机中的存储关系，即数据的存储结构。③对各种数据结构进行的运算。

数据结构包含两个要素，即“数据”和“结构”。

    数据是需要处理的数据元素的集合，一般来说，这些数据元素，具有某个共同的特征。例如，早餐、午餐、晚餐这3个数据元素有一个共同的特征，即它们都是一日三餐的名称，从而构成了一日三餐名的集合。

      所谓“结构”，就是关系，是集合中各个数据元素之间存在的某种关系（或联系）。“结构”是数据结构研究的重点。根据数据元素之间的不同特性关系，可以分为4类结构：线性结构、树形结构、网状结构和集合。

      在数据处理领域中，通常把两两数据元素之间的关系用前后件关系（或直接前驱与直接后继关系）来描述。实际上，数据元素之间的任何关系都可以用前后件关系来描述。例如，再考虑一日三餐的时间顺序关系时，“早餐”是“午餐”的前件（或直接前驱），而“午餐”是“早餐”的后件（或直接后继）；同样，“午餐”是“晚餐”的前件，“晚餐”是“午餐”的后件。

      数据结构分为数据的逻辑结构和数据的存储结构。数据的逻辑结构指反映数据元素之间逻辑关系（即前后关系）的数据结构。数据的存储结构又称为数据的物理结构，是数据的逻辑结构在计算机存储空间中的存放方式。

二数据结构的表示

      数据的逻辑结构的数学形式定义——数据结构是一个二元组：

                  B=（D，R）

      其中，B表示数据结构，D是数据元素的集合，R是D上关系的集合，它反映了D中各数据元素之间的前后件关系，前后件关系也可以用一个二元组来表示。

三数据的存储结构

各数据元素在计算机存储空间中的位置关系与它们的逻辑关系不一定是相同的。下面介绍两种最主要的数据存储方式：

    ①顺序存储结构，这种存储方式主要用于线性的数据结构，它把逻辑上相邻的数据元素存储在物理上相邻的存储单元里，节点之间的关系由存储单元的邻接关系来体现。

    ②链式存储结构，链式存储结构就是在每个节点中至少包含一个指针域，用指针来体现数据元素之间在逻辑上的关系。

四数据结构的图形表示

      数据元素之间最基本的关系是前后件关系。一个数据结构除了用二元关系表示外，还可以用图形来表示。用中间标有元素值的方框表示数据元素，一般称之为数据节点，简称为节点。对于每一个二元组，用一条有向线段从前件指向后件。

      由前后件关系还可以引出以下3个基本概念，分别是：①根节点：数据结构中，没有前件的节点；②终端节点（或叶子节点）：数据结构中，没有后件的节点；③内部节点：数据结构中，除了根节点和终端节点以外的节点，统称为内部节点。

五线性结构与非线性结构

      根据数据结构中各数据元素之间前后件关系的复杂程度，一般将数据结构划分为两大类型，即线性结构和非线性结构。

      线性结构的含义：一个非空的数据结构，其满足一下两个条件：①有且只有一个跟节点；②每一个节点最多有一个前件，也最多有一个后件。

      非线性结构的含义：不满足以上两个条件的数据结构就称为非线性结构，非线性结构主要是指树形结构和网状结构。

      注意：在线性结构插入或删除任何一个节点后还应是线性结构；线性结构和非线性结构在删除结构中的所有节点后，都会产生空的数据结构。

      如果一个数据结构中没有数据元素，则称该数据结构为空的数据结构。在只有一个数据元素的数据结构中，删除该数据元素，就得到一个空的数据结构。