1.1 什么是数据结构

 

数据的组织形式和表示方式直接关系到计算机对数据的处理效率，因此，为了更好地进行程序设计，有效地利用计算机，就需要对计算机程序加工处理的对象进行系统和深入地研究。研究各种数据的特性以及数据之间存在的关系，进而根据实际应用的要求，合理地组织和存储数据，设计出相应的算法，这就是“数据结构”要讨论的问题。

本章主要内容

&        数据结构的逻辑结构、存储结构和数据运算三方面的相互关系

&        抽象数据类型的表示与实现，总结了C/C++语言中常用的数据类型

&        算法定义及特性

&        使用C语言进行算法描述

&        算法的时间复杂度分析

1.1  什么是数据结构

自1946年第一台计算机问世以来，计算机产业的飞速发展已远远超出了人们的预料，在某些生产线上，几秒钟就能生产出一块微型计算机芯片，产量猛增，价格低廉，这就使得计算机的应用范围迅速扩展。如今，计算机已深入到人类社会的各个领域。计算机的应用已不再局限于科学计算，而更多地用于控制、管理及数据处理等非数值计算的处理工作。与此相应，计算机加工处理的对象由纯粹的数值发展到字符、表格和图像等多种具有一定结构的数据，这就给程序设计带来了一些新的问题。为了编写出一个“好”的程序，必须分析要处理对象的特性以及各处理对象之间的关系。

数据是对客观事物的符号表示，在计算机科学中是指所有能输入到计算机中并被计算机程序处理的符号的总称，它是计算机程序加工的“原料”。例如，一个班的全部学生记录、a～z的字母集合、1～1 000的所有素数等都称为数据。

数据元素（也称为节点）是数据的基本单位，在程序中通常作为一个整体进行考虑和处理。有时一个数据元素可以由若干个数据项组成。数据项是具有独立含义的最小标识单位。例如，在整数集合中，“10”就可称为一个数据元素。又如，在一个数据库（关系数据库）中，一个记录可称为一个数据元素，而这个元素中的某个字段就是一个数据项。

数据结构是相互之间存在一种或多种特定关系的数据元素的集合。这些数据元素不是孤立存在的，而是有着某种关系，这种关系称为结构。

1.1.1  数据的逻辑结构

数据元素之间的逻辑关系称为数据的逻辑结构。根据数据元素之间逻辑关系的不同特性，分为下列4类基本结构：

·    集合。结构中的数据元素同属于一个集合（集合类型由于元素之间的关系过于松散，数据结构课程中较少讨论）。

·    线性结构。线性结构中的数据元素存在一对一的关系。

·    树形结构。树形结构中的数据元素存在一对多的关系。

·    图形结构。图形结构中的数据元素存在多对多的关系。

在大多数情况下，数据的逻辑结构可以用二元组来表示：

S=(D,R)

其中，D是数据节点的有限集合；R是D上的关系的有限集合。其中每个关系都是从D到D的关系。在表示每个关系时，用尖括号表示有向关系，如<a,b>表示存在节点a到节点b之间的关系；用圆括号表示无向关系，如(a,b)表示既存在节点a到节点b之间的关系，又存在节点b到节点a之间的关系。设r是一个D到D的关系，r∈R，若d，d'∈K，且<d,d'>∈r，则称d'是d的后继节点，d是d'的前驱节点，这时d和d'是相邻的节点（都是相对r而言的）；如果不存在一个d'，使<d,d'>∈r，则称d为r的终端节点；如果不存在一个d'，使<d',d>∈r，则称d为r的开始节点；如果d既不是终端节点也不是开始节点，则称d是内部节点。

例如，一个城市表（见表1-1）就可称之为一个数据结构，它由很多记录（这里的数据元素就是记录）组成，每个元素又包括多个字段（数据项）。那么这个表的逻辑结构是怎么样的呢？分析数据结构都是从数据元素之间的关系开始分析，对于这个表中任意一个记录，它只有一个前驱节点和一个后继节点，整个表只有一个开始节点和一个终端节点。当知道了这些关系之后，就能明白这个表的逻辑结构即为线性结构。其逻辑结构表示如下：

City=(D,R)

D={北京,上海,武汉,西安,南京}

R={r}

r={<北京,上海>,<上海,武汉>,<武汉,西安>,<西安,南京>}

表1-1  城市表

数据的逻辑结构可以用相应的关系图来表示，称之为逻辑结构图。

【例1-1】设数据逻辑结构如下：

B1=(D,R)

D={1,2,3,4,5,6,7,8,9}                               /*数据节点的有限集合*/

R={r}                                               /*D上的关系的有限集合*/

r={<1,2>,<1,3>,<3,4>,<3,5>,<4,6> ,<4,7>,<5,8>,<7,9>}    /*尖括号表示有向关系*/

图1-1  逻辑结构图

试画出对应的逻辑结构图，并给出哪些是开始节点，哪些是终端节点，说明是何种数据结构。

解：B1对应的逻辑结构如图1-1所示。其中，1是开始节点；2，6，8，9是终端节点。它是一种树形结构。

1.1.2  数据的存储结构

数据在计算机中的存储表示称为数据的存储结构，也称为物理结构。

把数据存储到计算机中时，通常要求既存储各节点的数值，又存储节点之间的逻辑关系。在实际应用中，数据的存储方法是灵活多样的，可根据问题规模（通常是指节点数目的多少）和运算种类等因素适当选择。本书将介绍4种基本的存储结构，即顺序存储结构、链式存储结构、索引存储结构和散列存储结构。下面简要介绍这些存储结构的特点。

1．顺序存储结构

顺序存储结构是把逻辑上相邻的元素存储在一组连续的存储单元中，其元素之间的逻辑关系由存储单元地址间的关系隐含表示。

对于前面的逻辑结构City，假定每个元素占用30个存储单元，数据从第100个存储单元开始由低地址向高地址方向存放，对应的顺序存储结构如表1-2所示。

表1-2  顺序存储结构

顺序存储结构的主要优点是节省存储空间。因为分配给数据的存储单元全部用于存放节点的数据值，节点之间的逻辑关系没有占用额外的存储空间。用这种方法来存储线性结构的数据元素时，可实现对各数据元素的随机访问。这是因为线性结构中每个数据元素都对应一个序号（开始节点的序号为1，其后继节点的序号为2，……），可以根据节点的序号i，计算出节点的存储地址：

Loc(i)=q+(i-1)×p

其中，p是每个元素所占的单元数；q是第一个元素节点所占单元的首地址。

顺序存储结构的主要缺点是不便于修改。在对节点进行插入、删除运算时，可能要移动一系列的节点。

2．链式存储结构

链式存储结构是给每个节点附加指针字段，用于存放相邻节点的存储地址。假定给逻辑结构City中的每个节点附加一个“下一个节点地址”即后继指针字段，用于存放后继节点的首地址，则可得到如表1-3所示的City的链式存储结构。表中，每个节点占用两个连续的存储单元，一个存放节点的数值，另一个存放后继节点的首地址。

表1-3  链式存储结构

链式存储结构的主要优点是便于修改，在进行插入、删除运算时，仅需修改节点的指针字段值，不必移动节点。

与顺序存储结构相比，链式存储结构的主要缺点是存储空间的利用率较低，因为分配给数据的存储单元有一部分被用来存放节点之间的逻辑关系了。另外，由于逻辑上相邻的节点在存储器中不一定相邻，因此，在使用这种方法存储的线性结构中不能对节点进行随机访问。

3．索引存储结构

索引存储结构是在存储节点信息的同时，建立了附加的索引表。索引表中的每一项称为索引项，索引项的一般形式是：（关键字，地址）。关键字唯一标识一个节点；地址作为指向节点的指针。对于线性结构来说，各节点的地址在索引表中是按节点的序号依次排列的。如表1-4是City的一种索引存储结构的表示。

表1-4  索引存储结构

续上表

在进行关键字查找时，可以先在索引表中快速查找（因为索引表中按关键字有序排列，可以采用对分查找）到相应的关键字，然后通过地址找到节点表中对应的记录。

线性结构采用索引存储后，可以对节点进行随机访问。在进行插入、删除运算时，由于只需移动存储在索引表中节点的存储地址，而不必移动存储在节点表中节点的数值，所以仍可保持较高的运算效率（这是因为在一般情况下节点中总包含有多个字段，移动一个节点的数值要比移动一个节点的地址花费更多的时间）。

索引存储结构的缺点是为建立索引表而增加了时间和空间的开销。

4．散列存储结构

散列存储结构是根据节点的值确定节点的存储地址。具体做法：以节点中某个字段的值为自变量，通过某个函数（称为散列函数）计算出对应的函数值i，再把i当作节点的存储地址。

对于City结构，假设以城市名的值作为自变量key，选用函数：

H(key)=ASC(LEFT(Hz(key),1)) mod 8

来计算节点的存储地址。

其中，Hz(key)表示提取汉字x的拼音串，ASC(LEFT(Hz(key),1))表示取汉字串key中第一个拼音字符的ASCII码，mod是取模运算，计算结果如表1-5所示。

表1-5  计算结果

于是，可以得到如表1-6所示的City的散列存储结构。

表1-6  散列存储结构

散列存储结构的优点是查找速度快，只要给出待查找节点的数值，就有可能立即算出节点的存储地址。

与前3种存储方法不同的是，散列存储方法只存储节点的数值，不存储节点之间的逻辑关系。散列存储方法一般只用于要求对数据能够进行快速查找、插入的场合。采用散列存储结构的关键是要选择一个好的散列函数和处理“冲突”的办法。本书第7章将详细介绍这种存储方法。

在使用高级语言编程时，可以用编程语言提供的数据类型来描述数据的存储结构。例如，用“一维数组”表示一组连续的存储单元，来实现顺序存储结构、索引存储结构和散列存储结构；用C/C++语言中的“指针”来实现链式存储结构。

1.1.3  数据的运算

数据运算就是对数据的操作。例如，有一张表格，需要对其进行查找、添加、修改、删除记录等工作。在数据结构中，运算不仅仅是加、减、乘、除这些算术运算，还常常涉及算法问题。算法的实现与数据的存储结构密切相关。