1.1 数据结构概述

1.1.1 什么是数据结构

计算机数据运算的一般过程如图1.1所示。数据是信息的载体，能够被计算机识别、存储和加工处理，数据包括文字、表格、图像等。例如，某个班的全部学生记录、a～z的字母集合、1～1000的所有素数等都是数据。信息是数据的内涵，即数据所表达的意义，例如，通过统计后产生某课程的平均分85，这里85是数据，表示某课程平均分的信息。

数据的基本单位是数据元素（有时称为元素、结点或记录等），通常把数据元素作为一个整体进行处理。例如，一个班的学生数据包括张三、李四等数据元素。

数据对象是具有相同类型的数据元素的集合，因为所有数据元素类型相同时处理起来更加方便，所以在数据结构中除特别指定外数据通常都是数据对象。

有时一个数据元素可以由若干个数据项（也可称为字段、域、属性）组成。数据项是具有独立意义的不可分割的最小标识单位。例如，在1～100的整数数据中，10就是一个数据元素；又比如在一个学生表中，一个学生记录可称为一个数据元素，而这个元素中的某一字段（如姓名）就是一个数据项。

【例1.1】组成数据的基本单位是________。

A．数据项

B．数据类型

C．数据元素

D．数据变量

解：数据是由数据元素组成的，数据元素是数据的基本单位。本题答案为C。

数据结构是相互之间存在一种或多种特定关系的数据元素的集合，如图1.2所示。这些数据元素不是孤立存在的，而是有着某种关系，这种关系构成了某种结构。在现实中，数据元素之间的关系多种多样，在“数据结构”课程中主要讨论数据元素之间的相邻关系。

归纳起来，数据结构一般包括以下三个方面的内容。

（1）数据元素之间的逻辑关系。所有元素的逻辑关系构成了数据逻辑结构。数据的逻辑结构是从逻辑关系上描述数据，它与数据的存储无关，是独立于计算机的。因此，数据的逻辑结构可以看作是从具体问题抽象出来的数学模型。

（2）数据元素（有时简称为元素）及其逻辑关系在计算机存储器内的表示，构成了数据存储结构。数据存储结构是逻辑结构用计算机语言实现的（也称为映像），它是依赖于计算机语言的。一般只在高级语言的层次上讨论存储结构。

（3）数据运算，即对数据施加的操作。数据运算的定义（指定运算的功能描述）是基于逻辑结构的，每种逻辑结构都有一组相应的运算。例如，最常用的运算有检索、插入、删除、更新、排序等；而数据运算的实现是基于存储结构的，通常是采用某种计算机语言实现的。

例如，一个学生成绩表Score如表1.1所示，它由多个学生成绩记录（即数据元素）组成，每个元素又包括多个数据项，其中，学号数据项是关键字，即学号唯一标识一个学生记录，现要求计算所有学生的平均分。

在这个求解问题中，表1.1给出了数据的逻辑结构，其数据运算是求所有学生的平均分。为了实现这个功能，先要设计对应的存储结构，即把Score表存放到计算机内存中，然后设计出实现求平均分的算法。

这里包含的学生成绩表逻辑结构，对应的存储结构设计和求平均分运算的实现都是数据结构所涉及的内容。

1.1.2 逻辑结构

数据元素之间的逻辑关系的整体称为数据的逻辑结构。现实中，数据元素的逻辑关系千变万化，而数据结构课程中讨论的逻辑关系主要是指数据元素之间的相邻关系，如果两个数据元素是相邻的，说明它们之间是有关系的，否则它们之间没有关系。实际上，这种相邻关系处理方法很容易推广到其他复杂关系的处理。

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

（1）集合：包含的所有数据元素同属于一个集合（数据元素之间没有关系，集合是一种最松散的逻辑结构）。

（2）线性结构：包含的数据元素之间存在一对一的关系。（3）树状结构：包含的数据元素之间存在一对多的关系。

（4）图形结构：包含的数据元素之间存在多对多的关系。也称为网状结构。

数据的逻辑结构可以采用多种方式描述，二元组是一种既常用也十分通用的数据逻辑结构表示方式。二元组表示如下。

      S=(D,R)
      D={di|1≤i≤n}
      R={rj|1≤j≤m}

其中，D是数据元素的有限集合，即D是由有限个数据元素所构成的集合，R是D上的关系的有限集合，即R是由有限个关系rj（1≤j≤m）所构成的集合，而每个关系都是指D→D的关系。

每个关系rj用序偶集合来表示，一个序偶表示两个元素之间的相邻关系，用尖括号表示有向关系，如<a，b>表示存在元素a到b之间的关系；用圆括号表示无向关系，如（a，b）表示既存在元素a到b之间的关系，又存在元素b到a之间的关系。

设rj是一个D到D的关系，rj∈R，若元素d∈D，d′∈D，且<d，d′>∈rj，则称d′是d的直接后继元素（简称后继元素），d是d′的直接前驱元素（简称前驱元素），这时d和d′是相邻的元素（都是相对rj而言的）；如果不存在一个d′使<d，d′>∈rj，则称d为rj的终端元素；如果不存在一个d′使<d′，d>∈rj，则称d为rj的开始元素；如果d既不是终端元素也不是开始元素，则称d是内部元素。

例如，表1.1数据的逻辑结构是怎么样的呢？从该表中可以看出，学号为201201的元素为开始元素（没有前驱元素），学号为201204的元素为终端元素（没有后继元素）。除此之外，所有元素都只有一个前驱元素和一个后继元素，如学号为201205的学生记录的唯一前驱元素为学号为201201的学生记录，唯一后继元素为学号为201206的学生记录。由此可知，这个表的逻辑结构为线性结构。

实际上，Score表本身就完整地描述了该数据的逻辑结构，也可以用如下二元组表示其逻辑结构（用学号表示相应的元素）。

      Score=(D,R)
      D={201201,201202,201204,201205,201206}
      R={r}        //这里只有一个逻辑关系，一些复杂的数据结构中可以有多个逻辑关系
      r={<201201,201205>,<201205,201206>,<201206,201202>,<201202,201204>}

数据逻辑结构的呈现形式称为数据的逻辑表示，除二元组外，数据逻辑结构还可以用相应的关系图来表示，称为逻辑结构图。

【例1.2】设数据的逻辑结构如下：

      B1=(D,R)
      D={1,2,3,4,5,6,7,8,9}
      R={r}
      r={<1,2>,<1,3>,<3,4>,<3,5>,<4,6>,<4,7>,<5,8>,<7,9>}

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

解：B1对应的逻辑结构图如图1.3所示。其中，1是开始结点，2、6、8、9是终端结点，除开始结点外，每个结点有唯一的前驱结点，除终端结点外，每个结点有一个或多个后继结点，所以它是一种树状结构。

【例1.3】设数据的逻辑结构如下：

      B2=(D,R)
      D={1,2,3,4,5,6}
      R={r}
      r={<1,2>,<2,4>,<1,3>,<3,4>,<3,5>,<3,6>,<5,6>}

试画出对应的逻辑结构图，说明是何种数据结构。

解：B2对应的逻辑结构图如图1.4所示，其中每个结点都有零个或多个前驱结点，每个结点都有零个或多个后继结点，所以它是一种图形结构。

1.1.3 存储结构

数据逻辑结构在计算机存储器中的表示称为数据的存储结构（或存储表示），也称为物理结构。通常情况下，同一种逻辑结构可以设计多种存储结构，在不同的存储结构中，实现同一种运算的算法可能不同。

逻辑结构、存储结构和运算三者之间的关系如图1.5所示。

把数据对象存储到计算机中时，通常要求既要存储各数据元素，又要存储数据元素之间的逻辑关系。在实际应用中，数据的存储方法是灵活多样的，可根据问题规模（通常是指元素个数的多少）和运算种类等因素适当选择。下面简要介绍主要的几种存储结构。

1．顺序存储结构

顺序存储结构是采用一组连续的存储单元存放所有的数据元素，而且逻辑上相邻的元素的存储单元也相邻。也就是说，元素之间的逻辑关系由存储单元地址间的关系隐含表示，即顺序存储结构将数据的逻辑结构直接映射到存储结构。

对于前面的逻辑结构Score，假设每个元素占用30B，且从100号单元开始由低地址向高地址方向存储，对应的顺序存储结构如图1.6所示。

顺序存储结构的主要优点是节省存储空间。因为分配给数据的存储单元全用于存放元素值，元素之间逻辑关系的表示没有占用额外的存储空间。用这种方法来存储线性结构的数据元素时，可实现对各数据元素的随机存取（所谓随机存取是指给定某元素的逻辑序号，能在常量时间内查找到对应的元素值）。

这是因为线性结构中每个数据元素对应一个序号（开始元素的序号为1，它的后继元素的序号为2……），序号为i的元素ai，其存储地址如下：

LOC（ai）=p+（i—1）×k

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

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

2．链式存储结构

顺序存储结构要求所有的元素在内存中相邻存放，因而需占用一片连续的存储空间；而链式存储结构不是这样，每个结点单独存储，无须占用一整块存储空间，但为了表示结点之间的关系，给每个结点附加指针字段，用于存放相邻结点的存储地址。

对于前面的逻辑结构Score，在设计其链式存储结构时，每个结点存放一个学生成绩记录，每个结点附加一个“下一个结点地址”即后继指针域，用于存放后继结点的首地址，则可得到如图1.7所示的Score的链式存储表示，head作为第一个结点的地址来标识整个链式存储结构。从图中可以看出，每个结点由两部分组成，一部分用于存放结点的数据，另一部分用于存放后继结点的首地址。

为了更清楚地反映链式存储结构，可采用更直观的图示来表示，如Score的链式存储结构可用如图1.8所示的方式表示。如要查找某学号的结点，需从head所指结点开始比较，在没有找到时依次沿后继指针域继续找下去。

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

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

3．索引存储结构

索引存储结构是在存储数据（称为主数据表）的同时，还建立附加的索引表。索引表中的每一项称为索引项，索引项的一般形式如下：

      （关键字，对应地址）

在索引表中，所有关键字有序排列（如递增），每个关键字的对应地址为该关键字的记录在数据表中的存储地址。

如图1.9所示的是Score对应的一种索引存储结构。在进行关键字（如学号）查找时，先在索引表中快速查找（因为索引表中按关键字有序排列，可以采用二分查找）到相应的关键字，然后通过对应地址在数据表中找到该记录的数据。

索引存储结构的优点是查找效率高，其缺点是需要建立索引表，从而增加了时间和空间开销。

4．哈希（散列）存储结构

哈希存储结构根据元素的关键字来确定其存储地址。具体做法是：以元素的关键字为自变量，通过某个哈希函数H（key）（或散列函数）计算出对应的函数值，再把该函数值当作该元素的存储地址。

对于前面的逻辑结构Score，假设哈希表长度m=6（存储单元的地址为0～5），记录个数n=5，以学号作为自变量，选用哈希函数如下：

h（学号）=学号—201201

对于每个学生记录，计算的存储地址如下。

于是得到如图1.10所示的哈希存储结构（其中2地址单元空闲）。如果要查找学号为id的学生记录，只需要求出h（id），以它为地址在该哈希表中直接找到该学号的学生记录。

哈希存储结构的优点是查找速度快，只要给出待查找结点的关键字，就有可能立即计算出对应记录的存储地址。

与前三种存储方法不同的是，哈希存储方法只存储数据元素本身，不存储数据元素之间的逻辑关系。哈希存储结构一般只用于要求对数据能够进行快速查找、插入的场合。采用哈希存储的关键是要选择一个好的哈希函数和处理“冲突”的办法。

1.1.4 数据运算

数据运算就是施加于数据的操作。数据运算包括运算定义和运算实现两部分，前者描述运算的功能，是抽象的，后者是在存储结构上设计对应运算的实现算法，是具体的。这种将运算定义和运算实现相互分离的做法即软件工程的思想，更加便于软件开发。

在数据结构中，运算实现与数据存储结构密切相关，选用好的存储结构可以提高运算实现的效率。

1.1.5 数据结构、数据类型和抽象数据类型

1．数据结构

数据结构是指带结构的数据元素的集合。一个数据结构包含数据逻辑结构、存储结构和数据运算三个方面。

2．数据类型

数据类型是高级程序设计语言中的一个基本概念，它和数据结构的概念密切相关。一方面，在程序设计语言中，每一个数据都属于某种数据类型。数据类型显式或隐含地规定了数据的取值范围、存储方式以及允许进行的运算。例如，在32位系统中，C语言的short int（短整型）数据类型隐含取值范围为—32 768～32 767，其运算有+、—、∗、/、%等。因此可以认为，数据类型是在程序设计语言中已经实现了的数据结构。另一方面，在程序设计过程中，当需要引入某种新的数据结构时，必须借助编程语言所提供的数据类型来描述数据的存储结构。

下面总结C/C++语言中常用的数据类型。

1）C/C++语言的基本数据类型

C/C++语言中的基本数据类型有int型、float型；double型和char型。int型可以有三个修饰符：short（短整数）、long（长整数）和unsigned（无符号整数）。

数据类型用于定义变量，如有定义语句：int n=10；在执行该语句时系统自动为变量n分配一个固定长度（如4B）的内存空间，如图1.11所示，程序员通过变量名n对这个内存空间进行存取操作（内存分成许多单元，每个单元都有一个地址，可以通过地址来对指定的单元进行操作，但这样做对于程序员来说十分麻烦，而通过变量名来操作内存单元非常方便），当超出作用范围时系统自动释放其内存空间，所以称之为自动变量。

2）C/C++语言的指针类型

C/C++语言允许直接对存放变量的地址进行操作。例如有以下定义：

      int i, ∗ p;

其中，i是整型变量，p是指针变量（它用于存放某个整型变量的地址）。表达式&i表示变量i的地址，将p指向整型变量i的运算为：p=&i。

对于指针变量p，表达式∗p是取p所指变量的值，例如：

      int i=2, ∗ p=&i;
      printf(＂%d\n＂,∗ p);

上述语句执行后，其内存结构如图1.12所示，通过表达式∗p输出变量i的值即2。

可以使用malloc（）函数为一个指针变量分配一片连续的空间（称为动态空间分配）。例如：

上述代码先定义字符指针变量p（此时它没有指向有效的字符数据，即p中的地址值没有意义），使用malloc（）函数为其分配长度为10个字符的空间，将该空间的首地址赋给p（尽管程序员不知道这个地址是多少，但p的值已经有意义了），再将字符串＂China＂放到这个空间中，如图1.13所示。p指向的是首字符'C'，所以第一个printf语句输出的∗p即字符'C'，而第二个printf语句输出的是整个字符串即＂China＂。

p变量是自动变量，当超出范围时，系统会自动释放它的空间，但p所指向的空间（用malloc函数分配的空间）是不能被系统自动释放的，所以必须显式用free（p）语句来释放p所指向的空间，这称为销毁，即垃圾回收。如果不做销毁操作，p所指向的内存空间在程序执行完毕仍被占用，这样可能很快造成内存消耗完，称为内存泄漏。所以本书后几章中介绍的每种数据结构都包含创建和销毁基本运算。

3）C/C++语言的数组类型

数组是同一数据类型的一组数据的有限序列。数组分为一维数组和多维数组。数组名标识一个数组，下标指示一个数组元素在该数组中的位置。

数组下标的最小值称为下界，在C语言中总是为0。数组下标的最大值称为上界，在C语言中数组上界为数组长度减1。例如，inta[10]语句定义了包含10个整数的数组a，其数组元素是a[0]～a[9]。

4）C/C++语言中的结构体类型

结构体是由一组称为结构体成员的数据项组成的，每个结构体成员都有自己的标识符，也称为数据成员域。例如，以下声明了一个teacher结构体类型：

结构体类型是用于定义结构体变量的，当定义一个结构体类型的变量时，系统按照结构体类型声明为对应的变量分配存储空间。例如，定义一个结构体变量t：

      struct teacher t;

t变量在内存中的存放方式如图1.14所示，引用no成员的方式是t.no，引用name成员的方式是t. name，引用age成员的方式是t.age，所有成员相邻存放，t变量所分配的内存空间大小为所有成员占用的内存空间之和。

可以使用结构体类型teacher定义其他变量，有以下代码：

其执行结果如下。

      1，陈华，34
      5，王强，48

5）C/C++语言中的共用体类型

共用体用于把不同的数据成员组织为一个整体，它们在内存中共享一段存储单元，但不同成员以不同的方式被解释。例如，声明一个共用体类型tag如下：

共用体类型是用于定义共用体变量的，当定义一个共用体类型的变量时，系统按照共用体类型声明为对应的变量分配存储空间。例如，定义一个共用体变量u：

      union tag u;

u变量在内存中的存放方式如图1.15所示，引用n成员的方式是u.n，引用ch成员的ch[0]元素的方式是u.ch[0]，所有成员共享相同的内存空间，u变量所分配的内存空间大小为所有成员占用的成员空间的最大值。

可以使用共用体类型tag定义其他变量，有以下代码：

通过赋值后，在共用体变量u的成员n的两个字节中，高位为65（0x41），低位为66 （0x42），分别对应u.ch[1]和u.ch[0]成员，所以printf输出为A和B两个字符（字符'A'的ASCII为十六进制数41，字符'B'的ASCII为十六进制数42）。

6）C语言中的自定义类型

C/C++语言中允许使用typedef关键字为一个数据类型指定一个别名，例如：

      typedef char ElemType;

该语句将char类型与ElemType等同起来。这样做有两个好处，一是方便程序调试，例如，将上述语句改为typedef int ElemType，则程序中所有ElemType都改为int类型了；二是可以简化代码，例如：

这样，StudType等同于学生结构体类型，可以使用该类型名定义变量：

      StudType s1,s2;

等同于：

      struct student s1,s2;

3．抽象数据类型

在数据结构中，抽象数据类型（Abstract Data Type，ADT）是指一个数学模型以及定义在此数学模型上的一组操作。抽象数据类型需要通过固有数据类型（高级编程语言中已实现的数据类型）来实现。对一个抽象数据类型进行定义时，必须给出抽象数据类型名称和包含的运算名称及其功能描述。一旦定义了一个抽象数据类型并具体实现，程序设计中就可以像使用基本数据类型那样，十分方便地使用该抽象数据类型。

从数据结构的角度看，一个求解问题可以通过抽象数据类型来描述，也就是说，抽象数据类型对一个求解问题从逻辑上进行了准确的定义，所以抽象数据类型由数据逻辑结构和运算定义两部分组成。从中看出，抽象数据类型是面向用户的，而抽象数据类型的实现是面向程序员的。

【例1.4】定义单个集合的抽象数据类型ASet，其中所有元素为正整数，包含创建一个集合、输出一个集合和判断一个元素是否为集合中元素的基本运算。

在此基础上再定义两个集合运算的抽象数据类型BSet，包含集合的并集、差集和交集运算。

解：抽象数据类型ASet的定义如下：

抽象数据类型BSet的定义如下：

通过上述两个抽象数据类型的定义，就将求解问题描述清楚了，下一步就是用C/C++等语言具体实现其功能。