1.2　数据结构的基本概念

【考点1】概述

（1）数据处理概述

①定义

数据处理是指对数据集合中的各元素以各种方式进行运算，包括插入、删除、查找、更改等运算，也包括对数据元素进行分析。

②关键问题

大量数据元素在计算机中如何组织，以便提高数据处理的效率，从而节省计算机的存储空间，这是进行数据结构处理的关键问题。

（2）数据结构研究概述

①研究问题

a．数据集合中各数据元素之间所固有的逻辑关系，即数据的逻辑结构；

b．在对数据进行处理时，各数据元素在计算机中的存储关系，即数据的存储结构；

c．对各种数据结构进行的运算。

②研究目的

主要目的在于提高数据处理效率，包括：

a．提高数据处理的速度；

b．尽量节省在数据处理过程中所占用的计算机存储空间。

【考点2】数据结构的概念

（1）数据结构的定义

数据结构是指相互有关联的数据元素的集合。

一个数据结构应包含：

①表述数据元素的信息；

②表示各数据元素之间的前后件关系。

（2）数据的逻辑结构

①定义

数据的逻辑结构是指反映数据元素之间逻辑关系的数据结构。

②要素

a．数据元素的集合，通常记为D；

b．D上的关系，通常记为R，它反映了D中各数据元素之间的前后件关系。

③表示

一个数据结构B可表示为：B＝（D，R）

为反映D中各数据元素之间的前后件关系，一般用二元组来表示。

（3）数据的存储结构

①定义

数据的逻辑结构在计算机存储空间中的存放形式。

【注意】

①各数据元素在计算机存储空间中的位置关系与它们的逻辑关系不一定是相同的，而且一般也不可能相同。

②在数据的存储结构中，不仅要存放各数据元素的信息，还需要存放各数据元素之间的前后件关系的信息。

③常用的存储结构有顺序、链接、索引等存储结构。

④采用不同的存储结构，其数据处理的效率是不同的。

【真题演练】

下列叙述中正确的是（　　）。[2014年3月真题]

A．有且只有一个根结点的数据结构一定是线性结构

B．每一个结点最多有一个前件也最多有一个后件的数据结构一定是线性结构

C．有且只有一个根结点的数据结构一定是非线性结构

D．有且只有一个根结点的数据结构可能是线性结构，也可能是非线性结构

【答案】D

【解析】逻辑结构分为线性结构和非线性结构，线性结构的特征有：①集合中必存在唯一的一个“第一个元素”；②集合中必存在唯一的一个“最后的元素”；③除第一元素之外，其他数据元素均有唯一的“前驱”；④除最后元素之外，其他数据元素均有唯一的“后继”。D项正确，如树形结构只有一个根结点，为非线性结构。答案选择D选项。

【考点3】数据结构的图形表示

（1）在数据结构的图形表示中，数据集合D中每个元素用中间标有元素值的方框表示，称为数据结点（简称结点）；对关系R中的每一个二元组，用一条有向线段从前件结点指向后件结点。

（2）在数据结构中，没有前件的结点称为根结点，没有后件的结点称为终端结点（也称叶子结点），其余结点都称为内部结点。

（3）数据结构中的元素结点可能是在动态变化的，这种变化体现在结点数量的增减以及各结点之间的前后件关系的动态变化上。

【考点4】线性结构与非线性结构

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

如果一个非空的数据结构满足下列两个条件：

（1）有且只有一个根结点；

（2）每一个结点最多有一个前件，也最多有一个后件。

则称该数据结构为线性结构，线性结构又称线性表。

【注意】在一个线性结构中插入或删除任何一个结点后还应是线性结构。如果一个数据结构不是线性结构，则称之为非线性结构。