1.2　数据结构的基本概念

视频二维码（扫码观看）

数据结构作为计算机的一门学科，主要研究和讨论以下三个方面的问题：

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

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

（3）对各种数据结构进行的运算。

讨论以上问题的目的：

（1）提高数据处理的速度；

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

一、什么是数据结构

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

数据元素具有广泛的含义：

描述一年四季的季节名：春、夏、秋、冬

表示数值的各个数：18、11、35、23、16…

表示家庭成员的各成员名：父亲、儿子、女儿

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

【注意】作为某种处理，其中的数据元素一般具有某种共同特征，一般情况下，在具有相同特征的数据元素集合中，各个数据元素之间存在有某种关系，这种关系反映了该集合中的数据元素所固有的一种结构。

1数据的逻辑结构

（1）定义

反映数据元素之间逻辑关系的数据结构。一个数据结构应包含以下两方面的信息：

①表示数据元素的信息；

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

（2）数据的逻辑结构有两个要素：

一是数据元素的集合，通常记为D；

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

即一个数据结构可以表示成B＝（D，R）。

【例4】一年四季的数据结构可以表示成

B＝（D，R）

D＝{春，夏，秋，冬}

R＝{（春，夏），（夏，秋），（秋，冬）}

2数据的存储结构

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

【注意】

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

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

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

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

二、数据结构的图形表示

一个数据结构除了用二元关系表示外，还可以直观地用图形表示。

（1）对于数据集合D中的每一个数据元素用中间标有元素值的方框表示，一般称之为数据结点，并简称为结点；

（2）对于关系R中的每一个二元组，用一条有向线段从前件结点指向后件结点，有时箭头可省去。

图1-1　一年四季数据结构的图形表示图（线性）

图1-2　家庭成员间关系数据结构的图形表示（树型结构）

【考题】下列叙述中正确的是（　　）。

A．线性表是线性结构

B．栈与队列是非线性结构

C．循环链表是非线性结构

D．二叉树是线性结构

【答案】A

【解析】选项A正确；选项B，栈和队列都是线性结构，二者区别是，栈只允许在一端插入和删除，队列只允许在一端插入，在另一端删除；选项C，循环链表是线性表的链式存储结构；选项D，二叉树是一种典型的非线性结构。

三、线性结构与非线性结构

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

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

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

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

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

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

【考题】设数据集合为D＝{1，3，5，7，9}，D上的关系为R。下列数据结构B＝（D，R）中为非线性结构的是（　　）。

A．R＝{（5，1），（7，9），（1，7），（9，3）}

B．R＝{（9，7），（1，3），（7，1），（3，5）}

C．R＝{（1，9），（9，7），（7，5），（5，3）}

D．R＝{（1，3），（3，5），（5，9）}

【答案】D

【解析】如果一个非空的数据结构满足下列两个条件：①有且只有一个根结点；②每一个结点最多有一个前件，也最多有一个后件。则该数据结构为线性结构。

选项A：5是根结点，5的后件是1，1的后件是7，7的后件是9，9的后件是3，故选项A是线性结构；

选项B：9是根结点，9的后件是7，7的后件是1，1的后件是3，3的后件是5，故选项B是线性结构；

选项C：1是根结点，1的后件是9，9的后件是7，7的后件是5，5的后件是3，故选项C是线性结构；

选项D：1是根结点，1的后件是3，3的后件是5，5的后件是9，7也是根结点，没有前件也没有后件，线性数据结构第一个条件不满足，故选项D是非线性结构，即选项D正确。