12数据结构的基本概念

很少有人能镇定地表达与他们的社会环境之偏见相左的意见。大多数人甚至无法形成这种意见。
1.2数据结构的基本概念
数据结构作为计算机的一门学科
主要研究和讨论以下三个方面的问题：
（1） 数据集合中各数据元素之间所固有的逻辑关系
即数据的逻辑结构；
（2） 在对数据进行处理时
各数据元素杂计算机中的存储关系
即数据的存储结构；
（3） 对各种数据结构进行的运算

1. 什么是数据结构
简单地说
数据结构是指互相有关联的数据元素的集合

在数据处理领域中
每一个需要处理的对象都可以抽象成数据元素
数据元素一般简称为元素

在具有相同特征的数据元素集合中
各个数据元素之间存在有某种关系
这种关系反映了该集合中的数据元素所固有的关系简单地用前后件关系来描述

前后件关系是数据元素之间的一个基本关系
但前后件关系所表示的实际意义是随对象的不同而不同

（1） 数据的逻辑结构
数据结构是反映数据严肃之间关系的数据元素集合的表示
更通俗的说
数据结构是指带有结构的数据元素的集合
在此
所谓结构实际上是数据元素之间的前后件关系

一个数据结构包含有以下两方面的信息：
（1） 表示数据元素的信息；
（2） 表示各数据元素之间的前后件关系

在上述的数据结构中
其中数据元素之间的前后件关系是指它们的逻辑关系
而与它们在计算机中的存储位置无关
因此
上面所述的数据结构实际上是数据的逻辑结构

（3） 数据的存储结构
数据的逻辑结构在计算机存储空间中的存放形式称为数据的存储结构
一个数据结构中的各数据元素在计算机存储空间中的位置关系与逻辑关系有可能是不同的

由于数据元素在计算机存储看见中的位置可能与逻辑关系不同
因此
为了表示存放在计算机存储空间中的各数据元素之间的逻辑关系
在数据的存储结构中
不仅要存放各数据元素的信息
还要存放各数据元素之间的前后件关系的信息

一般来说
一种数据的逻辑结构根据需要可以表示成多种存储结构
常用的存储结构有顺序、连接、索引等存储结构

2. 数据结构的图形表示
在数据结构的图形表示中
对于数据集合D中的每一个数据元素中间标有元素值的方框表示
一般称之为数据结点；为了进一步表示各数据元素之间的前后关系
对于关系R中的每一个二元组
用一条有向线段从前件接点指向后件接点

例如
一年四季的数据结构可以用如图1.1所示的图形来表示






图1.1一年四季数据结构的图形表示

又如
反映家庭成员间辈分关系的数据结构

可以用如图1.2所示的图形来表示


图1.2 家庭成员间辈分关系数据结构的图形表示

有时在不会引起误会的情况下
在前件结点到后件结点连线上的箭头可以省去
例如
在图1.2中
即使将"父亲"结点与"女儿"结点连线上的箭头去掉
同样表示了"父亲"是"儿子"与"女儿"的前件
"儿子"与"女儿"
均是"父亲"的后件
而不会引起误会

在数据结构中
没有前件的结点称为根结点；没有后件的结点称为终端结点
例如
在图1.1中所示的数据结构中
元素"春"所在的结点称为根结点
结点"冬"为终端结点

3. 线性结构与非线性结构
如果在一个数据结构中一个书记元素都没有
则称该数据结构为空的数据结构
一个空的数据结构中插入一个新的元素后就变为非空；在只有一个数据元素的数据结构中
将该元素删除后就变为空的数据结构

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

如果一个非空的数据结构满足下列两个条件：
（1） 有且只有一个根结点；
（2） 每一个结点最多有一个前件
也最多有一个后件

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

如果一个数据结构不是线性结构
则称之为非线性结构
例如
反映家庭成员间辈分关系的数据结构不是线性结构
而是非线性结构