3．5．3　数据结构

如今，计算机已深入到人类社会的各个领域，计算机的应用不再局限于科学计算，而更多地用于控制、管理及数据处理等非数值计算的处理工作。比如在图书馆的图书管理系统、人机对奕、多叉路口交通信号灯管理中，计算机加工处理的对象不是纯粹数值，而是字符、表、图像等各种具有一定结构的数据。因此，在程序设计过程中，必须分析在这些数据元素之间存在的一种或多种特定关系，以及作用于其上的函数或运算。

数据结构的研究不仅涉及到计算机硬件（存储设备和存取方法等）、计算机软件（数据元素在存储器中的分配），还要考虑到信息检索过程中如何组织数据，以方便查找和存储数据元素。数据结构是一门介于数学、计算机硬件、计算机软件三者之间的核心课程。

通常，研究数据结构一般包括三个方面的内容，即数据的逻辑结构、数据的存储结构和定义在这些数据上的运算。

逻辑结构中描述的是数据元素之间的逻辑关系。通常有下列四类基本结构：集合、线性结构、树型结构、网状（图）结构。

线性结构中，在数据元素非空的有限集合的前提下，要求：存在唯一的一个被称做“第一个”的数据元素；存在唯一的一个被称为“最后一个”的数据元素；除第一个元素以外，集合中的每一个数据元素均只有一个前驱；除最后一个元素之外，集合中每一个数据元素均只有一个后继。其中的数据元素可以是一个数字或是一条记录，甚至其他更复杂的信息。由于数据元素之间有明确的顺序关系，这个集合将构成一个有方向的线性链表，如图3．19所示。

图3．19　有方向的线性链表

如果要描述人类社会的族谱或各种社会组织关系，这种关系将不是线性的，可以用“树”来形象描述。如图3．20所示，这是某公司组织结构图，它很像一株倒悬着的树，从树根到大分枝、小分枝直到叶子，把数据联系起来。树中每个分叉点称为“结点”，起始结点称为“树根”，任意两个结点间的连接关系称为“树枝”，结点下面不再有分枝的称为“树叶”。结点的前趋结点称为该结点的“双亲”，结点的后趋结点称为该结点的“子女”或“孩子”，同一结点的“孩子”之间互称“兄弟”。当然其中的数据元素可以是一个数字或是一条记录，甚至其它更复杂的信息。

图3．20　某公司组织结构的树型描述

假如一位旅客要从济南出发到福州，他希望选择一条途中中转次数最少的路线。假设他每到一个城市都要换车。由于城市和城市之间存在道路，则可以使用“图”这种结构来解决这个问题。如图3．21所示，我们需要从顶点“济南”出发，搜索每一条可以到达福州的路径，这个问题就是搜索一条由济南到福州含边最少的路径。

图3．21　城市和城市之间的图形描述

数据的存储结构实质上是它的逻辑结构在计算机存储器上的实现，是数据结构在计算机中的表示（映像）。数据元素在计算机中有两种不同的表示方法，顺序存储和非顺序存储，因此会得到两种不同的存储结构———顺序存储结构和链式存储结构。顺序存储是数据元素在存储器中按照先后顺序进行存放，非顺序存储是借助于数据元素存储地址（指针）表示数据元素间的逻辑关系。

不同数据结构有其相应的运算，常见的运算有数据检索、插入、删除、更改、排序等。