1.1 引言

1.1.1 什么是数据结构

数据结构包含两方面的内容，其一是构成集合的数据元素，其二是数据元素之间存在的关系。数据结构也就是带有结构的数据元素的集合，结构指的是数据元素之间的相互关系，即数据的组织形式。由此可见，计算机所处理的数据并不是数据的杂乱堆积，而是具有内在联系的数据集合。如表1-1所示的成绩表就是一个数据结构（线性表），其中每一行表示一个数据元素，表中的所有行构成了一个数据元素集合，数据元素之间具有线性结构关系（详见第2章）。如图1-1所示是一软件公司员工职务组织结构图，其中每一个方框表示一位员工的信息（如职工号、姓名、性别、年龄和电话等），即一个数据元素，全部员工的信息构成了一个数据元素集合，数据元素之间具有树形结构关系（详见第5章）。如图1-2所示是城市交通示意图，其中每一个顶点表示一座城市，即一个数据元素，全部顶点构成了一个数据元素集合，每一条边表示两座城市间的交通线路，之间的距离用边上的值表示，数据元素之间具有图结构关系（详见第6章）。

表1-1 成绩表

1.1.2 数据结构研究什么

数据结构可定义为一个二元组：Data_Structure=（D,R）

其中D是数据元素的有限集合，R是D上关系的有限集合。

数据结构具体应包括3个方面：数据的逻辑结构、数据的物理结构和数据的运算集合。

1.逻辑结构

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

根据数据元素之间关系的不同特性，有下列4种基本的逻辑结构，如图1-3所示。

（1）集合结构。结构中的数据元素之间除了同属于一个集合的关系外，无任何其他关系。

（2）线性结构。结构中的数据元素之间存在着一对一的线性关系。

（3）树形结构。结构中的数据元素之间存在着一对多的层次关系。

（4）图状结构或网状结构。结构中的数据元素之间存在着多对多的任意关系。

由于集合的关系非常松散，因此可以用其他的结构代替。本书所讨论数据的逻辑结构如图1-4所示。

2.存储结构

存储结构（又称物理结构）是逻辑结构在计算机中的存储映像，是逻辑结构在计算机中的实现（或存储表示），它包括数据元素的表示和关系的表示。有数据结构Data_Structure=(D,R)，对于D中的每一个数据元素都对应有存储空间中的一个单元，D中全部元素对应的存储空间必须明显或隐含地体现关系R。逻辑结构与存储结构的关系为，存储结构是逻辑结构的映像与元素本身的映像。逻辑结构是抽象，存储结构是实现，两者综合起来建立了数据元素之间的结构关系。

数据元素之间的关系在计算机中有两种不同的表示方法，即顺序映像（顺序存储结构）与非顺序映像（非顺序存储结构）。数据结构在计算机中的映像，包括数据元素映像和关系映像。关系映像在计算机中可用顺序存储结构或非顺序存储结构两种不同方式来表示。

3.运算集合

讨论数据结构的目的是为了在计算机中实现所需的操作，施加于数据元素之上的一组操作构成了数据的运算集合，因此在结构上的运算集合是数据结构很重要的组成部分。

以表1-1所示的成绩表为例，该表的数据元素与数据元素之间是一种简单的线性关系，所以逻辑结构采用线性表。存储结构既可采用顺序存储结构，也可采用非顺序存储结构。对于成绩表，当学生退学或转出时要删除相应的数据元素，转入学生时要增加数据元素，发现成绩输入错误时要修改。这里的增加、删除和修改就构成了数据的操作集合。

综上所述，数据结构的内容可归纳为3个部分：逻辑结构、存储结构和运算集合。按某种逻辑关系组织起来的一批数据，依一定的映像方式把它存放在计算机存储器中，并在这些数据上定义一个运算的集合，就构成了一个数据结构。

《数据结构》是一门主要研究怎样合理地组织数据，建立合适的数据结构，提高计算机执行程序所用的时、空效率的学科。数据结构课程不仅讲授数据信息在计算机中的组织和表示方法，同时也训练用高效的设计算法解决复杂问题的能力。《数据结构》属于计算机专业的核心专业基础课，对于程序设计者来说掌握该课程的知识是非常必要的，数据结构贯穿程序设计的始末，缺乏数据结构功底的人，很难设计出高水平的应用程序。