1.2　数据结构的基本概念

考点1　概　述

（1）数据处理概述

①定义

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

②关键问题

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

（2）数据结构研究概述

①研究问题

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

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

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

②研究目的

数据结构研究和讨论上述3个问题的主要目的在于提高数据处理效率，包括：

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

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

考点2　数据结构的概念

（1）数据结构的定义

数据结构是指相互有关联的数据元素的集合，即它是反映数据元素之间关系的数据元素集合的表示。简言之，数据结构是指带有结构的数据元素的集合，这里的“结构”指数据元素之间的前后件关系。一个数据结构应包含以下两方面内容：

①表述数据元素的信息；

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

（2）数据的逻辑结构

①定义

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

②要素：

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

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

③表示

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

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

（3）数据的存储结构

①定义

数据的存储结构，也称数据的物理结构，是指数据逻辑结构在计算机存储空间中的存放形式。在数据的存储结构中，不仅要存放各数据元素的信息，而且要存放各数据元素之间的前后件信息。

②常用的存储结构：

a．顺序；

b．链接；

c．索引。

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

【真题演练】

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

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

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

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

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

【答案】D

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

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

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

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

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

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

根据数据结构中各数据元素之间的前后件关系的复杂程度，可将数据结构分为：

（1）线性结构（线性表）

一个非空的数据结构满足下列两个条件时，称其为线性结构：

①有且只有一个根结点；

②每个结点最多只有一个前件，也最多只有一个后件。

线性结构中插入或删除任何一个结点还应是线性结构，如果不满足这个条件就不能称之为线性结构。

（2）非线性结构

如果一个数据结构不是线性结构，则称之为非线性结构。

注：线性结构与非线性结构都可以是空的数据结构。一个空的数据结构属于线性结构还是非线性结构，需要根据对该数据结构的运算是否按照线性结构的规则来处理进行判断。