第 2章 基本数据结构及其运算
2.1 数据结构的基本概念
2.2 线 性 表
2.3 栈及其应用
2.4 队列及其应用
2.5 线性链表
2.6 数组与字符串
2.7 树与二叉树
2.8 图
2.9 索引存储结构
数据是计算机化的信息，即计算机处
理的对象是数据。
各数据之间的一定关系，称为数据的
逻辑结构,数据在计算机中的存储位置有
着一定的关系，称为数据的物理结构（或
存储结构）。
数据结构作为计算机的一门学科，它
研究的内容，通常要涉及以下三个方面的
问题：
① 数据的逻辑结构；
② 数据的存储结构；
③ 对各种数据结构进行的运算。
主要目的是为了提高数据处理的效
率。
包括两个方面：一是提高数据处理
的速度，二是尽量节省在数据处理过程
中所占用的计算机存储空间。
2.1 数据结构的基本概念
数据结构是指相互有关联的数据元素
的集合。
组成该数据结构（包括逻辑结构和存
储结构）的数据元素称为一个结点。
在数据处理领域中，每一个需要处理
的对象都可以抽象成数据元素。
在具有相同特征的数据元素集合中，
各个数据元素之间存在有某种关系，反映
了该集合中的数据元素所固有的一种结构。
数据元素之间的任何关系都可以用前
后件关系来描述。
? 1．数据的逻辑结构
所谓结构实际上就是指数据元素之间
的前后件关系。
一个数据结构应包含以下两方面的信
息：
① 表示数据元素的信息。
② 表示各数据元素之间的前后件关系
的信息。
数据元素之间的前后件关系是指它们
的逻辑关系，而与它们在计算机中的存储
位置无关。
数据结构实际上是数据的逻辑结构。
数据的逻辑结构，是指反映数据元素
之间逻辑关系的数据结构。
数据的逻辑结构有两个要素：一是数
据元素的集合，通常记为 D；二是 D上的
关系，它反映了 D中各数据元素之间的前
后件关系，通常记为 R。
即一个数据结构可以表示成
B = (D,R)
例 2.1 一年四季的数据结构可以
表示成
B = (D,R)
D = {春,夏,秋,冬 }
R = {(春,夏 ),(夏,秋 ),(秋,冬 )}
例 2.3 n维向量
X = (x1,x2,…,xn)
也是一种数据结构。即 X = (D,R)，其
中数据元素的集合为：
D = {x1,x2,…,xn}
关系为：
R = {(x1,x2),(x2,x3),…,( xn– 1,xn)}
例如,m× n的矩阵
是一个数据结构。在这个数据结构中，
矩阵的每一行
Ai = (ai1,ai2,…, ain),i= 1,2,…,m
可以看成是它的一个数据元素。即这
个数据结构的数据元素的集合为：
D = {A1,A2,…, Am}
D上的一个关系为：
R = {(A1,A2),(A2,A3),…, (Ai，
Ai+1),… Am – 1,Am}}
显然，数据结构 A中的每一个数据元
素 Ai（ i = 1,2,…,m）又是另一个数据结构，
即数据元素的集合为：
Di = {ai1,ai2,…, ain}
Di上的一个关系为：
Ri = {(ai1,ai2),(ai2,ai3),…, (ai，
ai,j + 1),…, (ai,n –1,ain)}
一个数据结构除了用二元关系表示外，
还可以直观地用图形表示。
反映家庭成员间辈份关系的数据结构
可以用图 2.2所示的图形表示。
例 2.4 用图形表示数据结构 B =（ D，
R），其中
D = {di |1≤i≤7} = {d1,d2,d3,d4，
d5,d6,d7}
R = {(d1,d3),(d1,d7),(d2,d4)，
(d3,d6),(d4,d5)}
这个数据结构的图形表示如图 2.3所示。
在数据结构中，没有前件的结点称为
根结点；没有后件的结点称为终端结点
（也称为叶子结点）。
通常，一个数据结构中的元素结点可
能是在动态变化的。
数据结构中的结点（即数据元素）个
数在动态地变化，而且，各数据元素之间
的关系也有可能在动态地变化。
如果在一个数据结构中一个数据元
素都没有，则称该数据结构为空的数据
结构。
在一个空的数据结构中插入一个新
的元素后就变为非空；在只有一个数据
元素的数据结构中，将该元素删除后就
变为空的数据结构。
将数据结构分为两大类型：线性结构
与非线性结构。
如果一个非空的数据结构满足下列两
个条件：
① 有且只有一个根结点；
② 每一个结点最多有一个前件，也最
多有一个后件。
则称该数据结构为线性结构。
线性结构又称线性表。
例如，图 2.4所示的数据结构显然是满
足上述两个条件的，但它不属于线性结构
这个类型，因为如果在这个数据结构中删
除结点 A后，就不满足上述的条件①。
一个数据结构不是线性结构，则称之
为非线性结构。
线性结构与非线性结构都可以是空的
数据结构。
如果对该数据结构的运算是按线性结
构的规则来处理的，则属于线性结构；否
则属于非线性结构。
? 2．数据的存储结构
一个数据结构中的各数据元素在计算
机存储空间中的位置关系与逻辑关系是有
可能不同的。
数据的逻辑结构在计算机存储空间中
的存放形式称为数据的存储结构 。
在数据的存储结构中，不仅要存放各
数据元素的信息，还需要存放各数据元素
之间的前后件关系的信息。
常用的存储结构有顺序、链接、索引、
散列等存储结构。
? （ 1）顺序存储结构
顺序存储结构主要用于线性结构。在
这种存储方式中，把逻辑上相邻的数据元
素结点存储在物理上相邻的存储单元中，
各结点之间的关系由存储单元的邻接关系
来体现。
图 2.5是将线性结构 {(K1,K2),(K2，
K3),(K3,K4),(K4,K5),(K5,K6)，
(K6,K7)}顺序地存放在存储单元中的示
意图。
? （ 2）链接存储结构
在链接存储结构中，每个存储结
点要有两部分组成：一部分用于存放
数据信息，另一部分用于存放指针。
其中指针用于指向该结点的前件
或后件。
利用链接存储方式也可以存储非线性
结构。
图 2.7（ a）和（ b）分别为一棵二叉树
的逻辑结构与链接存储结构的示意图。
? （ 3）索引存储结构
索引存储结构是指将数据元素按索引
函数值进行分组，具有相同索引函数值的
数据元素被分在同一组中，而同一组中的
元素再按某种存储方式（顺序存储或链接
存储）进行存储。
? （ 4）散列存储结构
散列存储结构是指根据数据元素的关
键字值来确定其存储地址。
2.2 线 性 表
?2.2.1 线性表顺序存储结构
线性表由一组数据元素构成。
数据元素可以是简单项（如上述例子
中的数、字母、季节名等）。在稍微复杂
的线性表中，一个数据元素还可以由若干
个数据项组成。
例如，某班的学生情况登记表,如表
2.1所示。
学生情况登记表就是一个文件，其中
每一个学生的情况就是一个记录。
综上所述，线性表是由 n（ n≥0）个数
据元素 a1,a2,…, an组成的一个有限序
列。表中的每一个数据元素，除了第一个
外，有且只有一个前件；除了最后一个外，
有且只有一个后件。即线性表或是一个空
表，或可以表示为：
(a1,a2,…, ai,…, an)
其中 ai(i = 1,2,…, n)是属于数据对
象的元素，通常也称其为线性表中的一个
结点。
非空线性表有如下一些结构特征：
① 有且只有一个根结点 a1，它无前件。
② 有且只有一个终端结点 an，它无后
件。
③ 除根结点与终端结点外，其他所有
结点有且只有一个前件，也有且只有一个
后件。线性表中结点的个数 n称为线性表
的长度。当 n = 0时，称为空表。
在计算机中存放线性表，一种最简单
的方法是顺序存储，也称为顺序分配。顺
序存储的线性表通常称为顺序表。
线性表的顺序存储结构具有以下两个
基本特点：
① 线性表中所有元素所占的存储空间
是连续的。
② 线性表中各数据元素在存储空间中
是按逻辑顺序依次存放的。
在计算机中的顺序存储结构如图
2.8所示。
在程序设计语言中，通常定义一个一
维数组来表示线性表的顺序存储空间。
因为程序设计语言中的一维数组与计
算机中实际的存储空间结构是类似的，这
就便于用程序设计语言对线性表进行各种
运算处理。
建立一个空线性表的顺序存储空间
（即初始化线性表的顺序存储空间）的 C
语言描述如下：
#include "stdlib.h"
void initsl(v,m,n) /*初始化顺序表 */
ET *v； /*v返回顺序表空间的首地址,ET表示元
素的数据类型 */
int m,*n； /*m为顺序表的空间容量（字节
数）,n返回线性表的长度 */
{ v=malloc(m*sizeof(ET))； /*申请顺序表空间 */
*n=0； /*线性表长度为 0*/
return；
}
?2.2.2 顺序表的插入与删除
? 1．顺序表的插入运算
首先举一个例子来说明如何在顺序存
储结构的线性表中插入一个新元素。
一般来说，设长度为 n的线性表为：
要在线性表的第 i个元素 ai之前插入一
个新元素 b，插入后得到长度为 n + 1的线
性表为：
则插入前后的两线性表中的元素满足
如下关系：
在线性表顺序存储的情况下，要插入
一个新元素，由于数据元素的移动而消耗
较多的处理时间，因此其效率是很低的，
特别是在线性表比较大的情况下更为突出。
下面是线性表在顺序存储结构下插入
算法的 C语言描述。
void insl(v,m,n,i,b) /*顺序表的插入 */
ET v[],b； /*v为顺序表空间,b为插
入的元素 */
int m,*n,i； /*m为顺序表空间容量,n
为指向线性表长度的指针,
i为插入元素的序号 */
{ if (*n==m) /*顺序表空间已满,上溢
错误,返回 */
{ printf("overflow \n")； return； }
if (i＞ *n–1) i=*n+1； /*在线性表的
最后插入 */
if (i＜ 1＝ i=1； /*在线性表的第 1个
元素之前插入 */
for (j=*n； j＜ =i； j––＝ /*插入位
置以后的元素依次往后移动一个位置 */
v[j]=v[j–1]；
v[i–1]=b； /*插入元素 b*/
*n= *n+1； /*线性表长度加 1*/
return；
}
? 2．顺序表的删除运算
首先举一个例子来说明如何在顺序存
储结构的线性表中删除一个元素。
一般来说，设长度为 n的线性表为：
现要删除第 i个元素，删除后得到长度
为 n– 1的线性表为：
则删除前后的两线性表中的元素满足
如下关系：
在线性表顺序存储的情况下，要删除
一个元素，由于数据元素的移动而消耗较
多的处理时间，其效率也是很低的，特别
是在线性表比较大的情况下更为突出。
下面是线性表在顺序存储结构下删除
算法的 C语言描述。
void desl(v,m,n,i) /*顺序表的删除 */
ET v[]； /*顺序表空间 */
int m,*n,i； /*m为顺序表空间容量,n
为指向线性表长度的指针,
i为删除元素的序号 */
{ if (*n==0) /*线性表为空,下溢错误,
返回 */
printf("underflow \n")；
return； }
if ((i＜ 1) | | (i＞ *n)) /*线性表中没有
这种下标的元素,返回 */
printf("Not this element in the list
\n")； return； }
for (j=i； j＜ =*n–1； j++＝ /*第 i个以
后的元素依次往前移动一个位置 */
v[j–1]=v[j]；
*n= *n–1； /*线性表长度减 1*/
return；
}
2.3 栈及其应用
?2.3.1 栈的基本概念
栈实际上也是线性表，只不过是一种
特殊的线性表。
栈 (stack)是限定在一端进行插入与删
除的线性表。
往栈中插入一个元素称为入栈运
算，从栈中删除一个元素（即删除栈
顶元素）称为退栈运算。
栈顶指针 top动态反映了栈中元
素的变化情况。
图 2.11是栈的示意图。
图 2.12中给出了具有嵌套调用关系的
五个程序，其中主程序要调用子程序
SUB1,SUB1要调用子程序 SUB2,SUB2
要调用子程序 SUB3,SUB3要调用子程序
SUB4,SUB4不再调用其他子程序了。
计算机系统在处理时要用一个栈来动
态记忆调用过程中的路径，其基本原则如
下：
① 在开始执行程序前，建立一个栈，
其初始状态为空。
② 当发生调用时，将当前调用的返回
点地址（在图 2.12中用语句标号表示）入
栈。
③ 当遇到从某个子程序返回时，从栈
顶取出返回点地址。
?2.3.2 栈的顺序存储及其运
算
在栈的顺序存储空间 S（ 1,m）中,S
（ bottom）通常为栈底元素（在栈非空的
情况下）,S（ top）为栈顶元素。 top = 0
表示栈空； top = m表示栈满。
建立一个空栈的顺序存储空间（即初
始化栈的顺序存储空间）的 C语言描述如
下：
#include "stdlib.h"
void init_stack(s,m,top) /*初始化栈空间 */
ET *s； /*栈空间 */
int m,*top； /*m为栈空间容量,top为栈顶指针 */
{ s=malloc(m*sizeof(ET))； /*申请容量为 m的栈
空间 */
*top=0； /*置栈空 */
return；
}
栈的基本运算有三种：入栈、退栈与
读栈顶元素。下面分别介绍在顺序存储结
构下栈的这三种运算。
? （ 1）入栈运算
入栈运算是指在栈顶位置插入一个新
元素。
入栈运算的 C语言描述。
void push(s,m,top,x) /*在容量为 m的栈 S中插入一
个元素 x（入栈运算） */
ET s[],x； /*s为栈空间,x为入栈元素 */
int m,*top； /*m为栈空间容量,top为栈顶指针 */
{ if (*top==m) /*栈满,上溢错误,返回 */
{ printf("Stack–overflow\n")； return； }
*top=*top+1； /*栈顶指针进一 */
s[*top–1]=x； /*将元素 x插入到栈顶位置 */
return；
}
? （ 2）退栈运算
退栈运算是指取出栈顶元素并赋给一
个指定的变量。这个运算有两个基本操作：
首先将栈顶元素（栈顶指针指向的元素）
赋给一个指定的变量，然后将栈顶指针退
一（即 top减 1）。
退栈运算的 C语言描述。
void pop(s,m,top,y) /*在容量为 m的栈 S中删除栈
顶元素（退栈运算） */
ET s[],*y； /*s为栈空间,y指向存放退栈元素的地
址 */
int m,*top； /*m为栈空间容量,top为栈顶指针 */
{ if (*top==0) /*栈空,下溢错误,返回 */
{ printf("Stack–underflow\n")； return； }
*y=s[*top–1]； /*读取栈顶元素 */
*top=*top–1； /*栈顶指针退一 */
return；
}
? （ 3）读栈顶元素
读栈顶元素是指将栈顶元素赋给一
个指定的变量。必须注意，这个运算不
删除栈顶元素，只是将它的值赋给一个
变量，因此，在这个运算中，栈顶指针
不会改变。
读栈顶元素算法的 C语言描述。
void top(s,m,top,y) /*读栈顶元素 */
ET s[],*y； /*s为栈空间,y指向存放栈顶元
素的地址 */
int m,*top； /*m为栈空间容量,top为栈顶
指针 */
{ if (*top==0) /*栈空错误,返回 */
{ printf("Stack empty \n")； return； }
*y=s[*top–1]； /*读取栈顶元素 */
return；
}
?2.3.3 栈的应用
2.3.1中讨论的子程序嵌套调用就是栈
的一个实际应用。
栈还用于实现递归调用过程、表达式
的处理和中断的处理。
? 1．递归过程的实现
例如，在本书的第 1章例 1.5中提到，
对于输入的参数 n，依次打印输出自然数 1
到 n。为了不使用局部变量，其 C函数如下：
#include "stdio.h"
wrt1(int n)
{ if (n!=0)
{ wrt1(n–1)； printf("%d\n",n)； }
return；
}
? 2．表达式的计算
在编译系统或解释系统中，常利用栈
来处理表达式的计算问题。
2.4 队列及其应用
?2.4.1 队列的基本概念
队列（ equeue）是指允许在一端进行
插入、而在另一端进行删除的线性表。
允许插入的一端称为队尾,允许删除
的一端称为排头 。
在队列这种数据结构中，最先插入的
元素将最先能够被删除，反之，最后插入
的元素将最后才能被删除。
往队列的队尾插入一个元素称为入队
运算，从队列的排头删除一个元素称为退
队运算。
图 2.16是在队列中进行插入与删除的
示意图。
与栈类似，在程序设计语言中，用一
维数组作为队列的顺序存储空间。
在操作系统中，用一个队列来组织管
理用户程序的排队执行，原则是：
① 初始时队列为空。
② 当有用户程序来到时，将该用户程
序加入到队列的末尾进行等待。
③ 当计算机系统执行完当前的用户程
序后，就从队列的头部取出一个用户程序
执行。
?2.4.2 循环队列及其运算
在实际应用中，队列的顺序存储结构
一般采用循环队列的形式。
所谓循环队列，就是将队列存储空间
的最后一个位置绕到第一个位置，形成逻
辑上的环状空间，供队列循环使用，如图
2.17所示。
由图 2.18中循环队列动态变化的过程
可以看出，当循环队列满时有 front = rear，
而当循环队列空时也有 front = rear。
为了能区分队列满还是队列空，通常
还需增加一个标志 s,s值的定义如下：
建立一个循环队列顺序存储空间（即
初始化循环队列顺序存储空间）的 C语言
描述如下：
#include "stdlib.h"
void init_queue(q,m,front,rear,s) /*初始化
循环队列 */
ET *q； /*循环队列空间 */
int m,*front,*rear,*s； /*m为循环队列容
量,front为排头指针,
rear为队尾指针,s为标
志 */
{ q=malloc(m*sizeof(ET))； /*申请容
量为 m的循环队列空间 */
*front=m； *rear=m； /*置头尾指
针初值 */
*s=0； /*置队列空标志 */
return；
}
? （ 1）入队运算
入队运算是指在循环队列的队尾加入
一个新元素。
这个运算有两个基本操作：首先将队
尾指针进一（即 rear = rear + 1）,并当 rear
= m + 1时置 rear = 1；然后将新元素插入
到队尾指针指向的位置。
下面是入队运算的 C语言描述。
/*在容量为 m的循环队列 Q中插入一个
元素 x（入队运算） */
void addcq(q,m,rear,front,s,x)
ET q[ ],x； /*q为循环队列空间,x为
入队的元素 */
int m,*rear,*front,*s； /*m为循环队
列容量,front为排头指针,
rear为队尾指针,s
为标志 */
{ if ((*s==1) && (*rear== *front)) /*队列
满,上溢错误,返回 */
{ printf("Queue–OVERFLOW \n")；
return； }
*rear= *rear+1； /*队尾指针进一 */
if (*rear==m+1) *rear=1； /*队尾指针循
环 */
q[*rear–1]=x； /*元素 x插入到队尾 */
*s=1； /*置队列非空标志 */
return；
}
? （ 2）退队运算
退队运算是指在循环队列的排头位置
退出一个元素并赋给指定的变量。这个运
算有两个基本操作：首先将排头指针进一
（即 front = front + 1）,并当 front = m + 1
时置 front = 1；然后将排头指针指向的元
素赋给指定的变量。
下面是退队运算的 C语言描述。
/*在容量为 m的循环队列中删除一个
元素（退队运算） */
void delcq(q,m,rear,front,s,y)
ET q[ ],*y； /*q为循环队列空间,y存
放退队的元素 */
int m,*rear,*front,*s； /*m为循环队
列容量,front为排头指针,
rear为队尾指针,s
为标志 */
{ if (*s==0) /*队列空,下溢错误,返回 */
{ printf("Queue–UNDERFLOW \n")；
return； }
*front= *front+1； /*排头指针进一 */
if (*front==m+1) *front=1； /*排头指针
循环 */
*y=q[*front–1]； /*读出排头元素 */
if (*front== *rear) *s=0； /*置队列空标
志 */
return；
}
?2.4.3 队列的应用
凡是按“先来先服务”（即“先进先
出”）原则处理的问题，都可以用队列结
构来解决。
下面再介绍三个用模拟队列结构来解
决的问题。
? 1．给工人分配工作的模拟
? 2.输入输出缓冲区的结构
为了解决上述这种两个设备操作速度
不匹配的矛盾，通常是在两个设备之间设
置一个缓冲区，如图 2.19所示。
利用循环队列结构的缓冲区，就解决
了计算机处理数据与打印机打印输出的速
度不匹配的矛盾，实现了两个设备之间数
据的正常传送。
? 3.汽车加油站的工作模拟
2.5 线性链表
?2.5.1 线性链表的基本概念
? 1．线性链表
线性表的链式存储结构称为线性链表。
为了适应线性表的链式存储结构，计算
机存储空间被划分为一个一个小块，每一
小块占若干字节，通常称这些小块为存储
结点。
将存储空间中的每一个存储结点分为
两部分：一部分用于存储数据元素的值，
称为数据域；另一部分用于存放下一个数
据元素的存储序号（即存储结点的地址），
即指向后件结点，称为指针域。
线性链表中存储结点的结构如图 2.20
所示。
指向线性表中第一个结点的指针
HEAD称为头指针。
当 HEAD = NULL（或 0）时称为
空表。
对于线性链表，可以从头指针开始，
沿各结点的指针扫描到链表中的所有结
点。
为了弥补线性单链表的这个缺点，在
某些应用中，对线性链表中的每个结点设
置两个指针，一个称为左指针（ Llink），
用以指向其前件结点；另一个称为右指针
（ Rlink），用以指向其后件结点。
这样的线性链表称为双向链表，其逻
辑状态如图 2.23所示。
? 2．带链的栈
栈也是线性表，也可以采用链式存储
结构。
图 2.24是栈在链式存储时的逻辑状态
示意图。
在实际应用中，带链的栈可以用来收
集计算机存储空间中所有空闲的存储结点，
这种带链的栈称为可利用栈。
如图 2.25所示 。
? 3．带链的队列
与栈类似，队列也是线性表，也可以
采用链式存储结构。
图 2.26（ a）是队列在链式存储时的逻
辑状态示意图。
图 2.26(b)是将新结点 p入队的示
意图。
图 2.26（ c）是将排头结点 p退出队列
的示意图。
?2.5.2 线性链表的基本运算
线性链表的运算主要有以下几个：
① 在线性链表中包含指定元素的结点
之前插入一个新元素。
② 在线性链表中删除包含指定元素的
结点。
③ 将两个线性链表按要求合并成一个
线性链表。
④ 将一个线性链表按要求进行分解。
⑤ 逆转线性链表。
⑥ 复制线性链表。
⑦ 线性链表的排序。
⑧ 线性链表的查找。
1.在线性链表中查找指定元素
对线性链表进行扫描查找，在线性链
表中寻找包含指定元素值的前一个结点。
? 2．线性链表的插入
线性链表的插入是指在链式存储结构
下的线性表中插入一个新元素。
为了要在线性链表中插入一个新元素，
首先要给该元素分配一个新结点，然后将
存放新元素值的结点链接到线性链表中指
定的位置。
? 3．线性链表的删除
线性链表的删除指在链式存储结构下
的线性表中删除包含指定元素的结点。
为了在线性链表中删除包含指定元素
的结点，首先要在线性链表中找到这个结
点，然后将要删除结点放回到可利用栈。
?2.5.3 循环链表
循环链表的结构与前面所讨论的线性
链表相比，具有以下两个特点：
①循环链表的头指针指向表头结点。
② 在循环链表中，所有结点的指针构
成了一个环状链。
图 2.29是循环链表的示意图。
在实际应用中，循环链表与线性单链
表相比主要有以下两个方面的优点：
① 在循环链表中，只要指出表中任何
一个结点的位置，就可以从它出发访问到
表中其他所有的结点。
② 由于在循环链表中设置了一个表头
结点，因此，在任何情况下，循环链表中
至少有一个结点存在，从而使空表与非空
表的运算统一。
?2.5.4 多项式的表示及其运算
设多项式为：
Pn(x) = anxn + an–1xn –1 + … + a1x + a0
在采用链表表示多项式时，对于多项
式中每一个非零系数的项构成链表中的一
个结点，而对于系数为零的项就不用表示。
多项式中非零系数项所构成的结点如图
2.30所示。
设只表示非零系数项的多项式为：
其中 ak≠0(k= 1,2,…,m),em＞ em–1＞ …
＞ e1≥0。
若用线性单链表表示，其逻辑状态如
图 2.31（ a）所示。
若用循环链表表示，其逻辑状态如图
2.31（ b）所示。
多项式的运算主要有以下五种：
① 多项式链表的生成。
② 多项式链表的释放。
③ 多项式的输出。
④ 多项式的相加。
⑤ 多项式的相乘。
下面以循环链表表示的多项式为例来
讨论各种运算。
? 1．多项式链表的生成
主要包括以下两步：
① 建立一个表头结点，其指数域值为
–1，指针域指向表头结点自身，头指针也
指向表头结点。
② 按降幂顺序以数偶形式依次输入多
项式中非零系数项的指数 ek和系数 ak(k =
m,m – 1,…, 1)，最后以输入指数值 –1
为结束。
? 2．多项式链表的释放
从表头结点开始，逐步释放链表中的
各结点。
? 3．多项式的输出
从表头结点后的第一个结点开始，以
数偶形式顺链输出各结点中的指数域与系
数域的内容。
? 4．多项式的相加
多项式相加的运算规则很简单，只
要从两个多项式链表的第一个元素结点
开始检测 。
? 5．多项式的相乘
2.6 数组与字符串
?2.6.1 数组的顺序存储结构
数学中的矩阵在程序设计语言中用二
维数组表示。
二维数组在计算机中是顺序存储的。
1.二维数组以行为主的顺序存储
二维数组以行为主的顺序存储是指将数组
中的元素一行接一行地顺序存储在计算机的连续
存储空间中。
例如，一个 m× n的矩阵
在计算机中以行为主的顺序存储形式如图
2.32所示。
2.二维数组以列为主的顺序存储
二维数组以列为主的顺序存储是指将数组
中的元素一列接一列地顺序存储在计算机的连续
存储空间中。
例如，一个 m× n的矩阵
在计算机中以列为主的顺序存储形式如图
2.33所示。
?2.6.2 规则矩阵的压缩
规则矩阵是指，矩阵中非零元素的
分布是有规律的。
在存储一个规则矩阵时，只需存储
非零元素即可，而对于大部分的零元素
或者重复的非零元素（如对称矩阵）不
必存储。
规则矩阵的这种存储方法称为压缩
存储。
? 1.下三角矩阵的压缩存储
存储的原则是：用一个一维数组以行
为主顺序存放下三角矩阵中的所有下三角
部分的元素。
设 n阶下三角矩阵为：
经压缩后，存放在一维数组 B中的形式如图
2.34（ a）所示。
下三角矩阵 A也可以用以列为主的方式压缩
存储在一维数组 B中，其存储形式如图 2.34（ b）
所示。
显然，在以列为主压缩存储的情况下，访
问下三角矩阵 A中的元素时其下标运算要比以行
为主压缩存储时稍为复杂一些。
因此，在实际应用时，一般采用以行为主
压缩存储下三角矩阵。
? 2.对称矩阵的压缩存储
对称矩阵的压缩存储与下三角矩阵完
全相同。
? 3.三对角矩阵的压缩存储
n阶三对角矩阵的形式为：
对于 n阶三对角矩阵，用一个长度
为 3n– 2的一维数组以行为主存放三条
对角线上的元素，其存储形式如图 2.35
（ a）所示。
在用一维数组 B以行为主存放三对角
矩阵 A中的元素 aij时，其访问公式为：
对于三对角矩阵，也可以用一维数组
B以列为主存放三条对角线上的元素，如
图 2.35（ b）所示。
在这种情况下，访问三对角矩阵 A中
元素 aij的公式为：
?2.6.3 一般稀疏矩阵的表示
如果一个矩阵中绝大多数的元素值为
零，只有很少的元素值非零，则称该矩阵
为稀疏矩阵。
在实际存储稀疏矩阵时，可以只存储
非零元素，而大量的零元素不存储，这就
是稀疏矩阵的压缩存储。
1.稀疏矩阵的三列二维数组表示
在压缩存储形式中，每一个非零元素
应包括以下三个信息：
① 非零元素所在的行号 i；
② 非零元素所在的列号 j；
③ 非零元素的值 V。
即每一个非零元素可以用下列三元组
表示：
（ i,j,V）
为了表示的惟一性，除了每一个非零
元素用一个三元组表示外，在所有表示非
零元素的三元组之前再添加一个三元组
（ I,J,t）
一般来说，具有 t个非零元素的稀疏矩
阵可以用 t + 1个三元组表示，其中第一个
三元组用以表示稀疏矩阵的总体信息，其
后的各三元组依次表示各非零元素，且按
以行为主的顺序排列。
为了使各三元组的结构更紧凑，通常
将这些三元组组织成三列二维表格的形式，
一般又表示成三列二维数组的形式，并简
称为三列二维数组。
具有 t个非零元素的稀疏矩阵，
其对应的三列二维数组为 t + 1行,3
列，共有 3(t + 1)个元素。
最后需要说明一点，在用三列二维数
组表示稀疏矩阵后，如果稀疏矩阵的运算
结果其非零元素的个数不发生变化（如矩
阵转置），则运算结果可直接采用三列二
维数组表示的形式；如果运算结果其非零
元素的个数发生了变化（如矩阵乘积），
则运算结果只能用一般的稀疏矩阵表示，
如有必要，则再用三列二维数组表示。
? 2．十字链表
稀疏矩阵还可以用链式结构来表示。
在用链式结构表示稀疏矩阵时，矩阵中的
每一个非零元素对应一个结点，每个结点
有五个域：行域、列域、值域、向下域与
向右域，如图 2.40所示。
用十字链表表示稀疏矩阵的结构特点
如下：
① 稀疏矩阵的每一行与每一列均用带
表头结点的循环链表表示。
② 表头结点中的行域与列域的值均置
为 0（即 row = 0,col = 0）。
③ 行、列链表的表头结点合用，且这
些表头结点通过值域（即 val）相链接，并
再增加一个结点作为它们的表头结点 H，
其行、列域值分别存放稀疏矩阵的行数与
列数。
例如，稀疏矩阵
?2.6.4 字符串
? 1．字符串的基本概念
字符串（ string）是字符的一个有限
序列，它本质上就是数据元素类型为字符
的线性表。字符串一般表示为：
"a1a2… ai… an"
对线性表的所有运算，对字符串也
适用。
字符串除了具有一般线性表所具有
的运算外，由于字符串具有多种数据类
型的特点，因此，对字符串的运算要比
一般的线性表更丰富。
① 连接运算。
② 取子串运算。
③ 删除子串运算。
④ 插入子串运算。
⑤ 求子串位置。
? 2．字符串匹配
在一般的编辑软件系统中，经常要遇
到在一个给定的文本中检测一个特定的字
符串的问题。这就是字符串匹配。字符串
匹配又称模式匹配。
（ 1）字符串匹配的简单算法
（ 2）字符串匹配的 KMP算法
2.7 树与二叉树
?2.7.1 树的基本概念
树（ tree）是一种简单的非线性
结构。
图 2.42表示了一棵一般的树。
在树的图形表示中，总是认为在用直
线连起来的两端结点中，上端结点是前件，
下端结点是后件，这样，表示前后件关系
的箭头就可以省略。
例如，图 2.43中的树表示了学校行政
关系结构；图 2.44中的树反映了一本书的
层次结构。
在树结构中，每一个结点只有一个前
件，称为父结点。
在树中，没有前件的结点只有一个，
称为树的根结点，简称为树的根。
在树结构中，每一个结点可以有多个
后件，它们都称为该结点的子结点。
没有后件的结点称为叶子结点。
在树结构中，一个结点所拥有的后件
个数称为该结点的度。
在树中，所有结点中的最大度称为树
的度。
树结构具有明显的层次关系，即树是
一种层次结构。
根结点在第 1层；
同一层上所有结点的所有子结点在下
一层。
树的最大层次称为树的深度。
在树中，以某结点的一个子结点为根
构成的树称为该结点的一棵子树。
在树中，叶子结点没有子树。
?2.7.2 二叉树及其基本性质
? 1．什么是二叉树
二叉树 (binary tree)是一种很有用的非
线性结构。二叉树具有以下两个特点：
（ 1）非空二叉树只有一个根结点；
（ 2）每一个结点最多有两棵子树，
且分别称为该结点的左子树与右子树。
图 2.46（ a）是一棵只有根结点
的二叉树，
图 2.46（ b）是一棵深度为 4的
二叉树。
?2．二叉树的基本性质
二叉树具有以下几个性质：
性质 1 在二叉树的第 k层上，最多有
2k–1（ k≥1）个结点。
根据二叉树的特点，这个性质是显然
的。
性质 2 深度为 m的二叉树最多有 2m–1
个结点。
性质 3 在任意一棵二叉树中，度为 0
的结点（即叶子结点）总是比度为 2的结
点多一个。
性质 4 具有 n个结点的二叉树，其深
度至少为 [log2n] + 1，其中 [log2n]表示取
log2n的整数部分。
? 3.满二叉树与完全二叉树
? （ 1）满二叉树
满二叉树是指除最后一层外，每一层
上的所有结点都有两个子结点。
? （ 2）完全二叉树
完全二叉树是指这样的二叉树：
除最后一层外，每一层上的结点数均
达到最大值；在最后一层上只缺少右
边的若干结点。
性质 5 具有 n个结点的完全二叉树的
深度为 [log2n] + 1。
性质 6 设完全二叉树共有 n个结点。
如果从根结点开始，按层序（每一层从左
到右）用自然数 1,2,…, n给结点进行
编号，则对于编号为 k(k = 1,2,…, n)的
结点有以下结论：
① 若 k = 1，则该结点为根结点，它没
有父结点；若 k＞ 1，则该结点的父结点编
号为 INT(k/2)。
② 若 2k≤n，则编号为 k的结点的左子
结点编号为 2k；否则该结点无左子结点
（显然也没有右子结点）。
③ 若 2k + 1≤n，则编号为 k的结点的右
子结点编号为 2k + 1；否则该结点无右子
结点。
?2.7.3 二叉树的存储结构
? 1．二叉链表
在计算机中，二叉树通常采用链式存
储结构。
与线性链表类似，用于存储二叉树中
各元素的存储结点也由两部分组成：数据
域与指针域。
用于存储二叉树的存储结点的指针域
有两个：一个用于指向该结点的左子结点
的存储地址，称为左指针域；另一个用于
指向该结点的右子结点的存储地址，称为
右指针域。
图 2.49为二叉树存储结点的示意图。
由于二叉树的存储结构中每一个存储
结点有两个指针域，因此，二叉树的链式
存储结构也称为二叉链表。
图 2.50 所示。
? 2．二叉链表的生成
二叉链表的生成是指根据给定的二叉
树在计算机中建立链式存储结构。
?2.7.4 二叉树的遍历
二叉树的遍历是指不重复地访问二叉
树中的所有结点。
二叉树的遍历可以分为三种：前序遍
历、中序遍历、后序遍历。
? 1．前序遍历
前序遍历（ DLR）是指在访问根结点、
遍历左子树与遍历右子树这三者中，首先
访问根结点，然后遍历左子树，最后遍历
右子树；并且，在遍历左、右子树时，仍
然先访问根结点，然后遍历左子树，最后
遍历右子树。
因此，前序遍历二叉树的过程是一个
递归的过程。
? 2．中序遍历
中序遍历（ LDR）是指在访问根结点、
遍历左子树与遍历右子树这三者中，首先
遍历左子树，然后访问根结点，最后遍历
右子树；并且，在遍历左、右子树时，仍
然先遍历左子树，然后访问根结点，最后
遍历右子树。
因此，中序遍历二叉树的过程也是一
个递归的过程。
? 3．后序遍历
后序遍历（ LRD）是指在访问根结点、
遍历左子树与遍历右子树这三者中，首先
遍历左子树，然后遍历右子树，最后访问
根结点；并且，在遍历左、右子树时，仍
然先遍历左子树，然后遍历右子树，最后
访问根结点。
因此，后序遍历二叉树的过程也是一
个递归的过程。
?2.7.5 穿线二叉树
? 1．穿线二叉树的概念
二叉树是一种非线性结构，对二叉树
的遍历，实际上是将二叉树这种非线性结
构按某种需要转化为线性序列，以便以后
在对二叉树进行某种处理时直接使用。
? 2．穿线二叉树的构造
对二叉树进行不同的遍历（前序遍历、
中序遍历、后序遍历）时，得到的遍历序
列也不同，因此，在二叉链表中链接遍历
序列的线索也是不同的。
图 2.52是中序线索二叉树的示意图，
图中的虚线表示线索。
? 3．穿线二叉树的遍历
二叉树经过一次遍历并生成遍历线索
以后，如果再次需要遍历，则只需要根据
遍历序列的线索进行即可。
?2.7.6 表达式的线性化
? 1．表达式树
在计算机中，可以用树结构来表示算
术表达式。
用树来表示算术表达式的原则如下：
① 表达式中的每一个运算符在树中对
应一个结点，称为运算符结点。
② 运算符的每一个运算对象在树中为
该运算符结点的子树（在树中的顺序为从
左到右）。
③ 运算对象中的单变量均为叶子结点。
根据以上原则，可以将表达式
a*(b+c/d)+e*h–g*f(s,t,x+y)
用如图 2.53所示的树来表示。
? 2．有序树的二叉树表示
如果对某个结点的所有子结点按从左
到右排上次序，则称该树为有序树。即：
在有序树中，某个结点的所有子结点从左
到右的次序是不能颠倒的。
将有序树转化成二叉树的原则如下：
① 有序树 T中的结点与二叉树 BT中的
结点一一对应。
② 有序树 T中某个结点 N的第一个子
结点（即最左边的子结点） N1，在二叉树
BT中为对应结点 N的左子结点。
③ 有序树 T中某个结点 N的第一个子
结点以后的其他子结点，在二叉树 BT中被
依次链接成一串起始于 N1的右子结点。
将图 2.53（ a）所示的有序树转化
成的二叉树如图 2.54所示。
? 3．表达式的线性化
表达式的线性化，是指将一般的表达
式化为波兰表示式（即后缀表示）。
利用树结构与二叉树结构对表达式线
性化的步骤如下：
① 将表达式用有序树表示，即构造表
达式树。
② 将表达式树化为二叉树。
③ 对相应的二叉树进行中序遍历，其
遍历序列即为表达式的波兰表示式。
2.8 图
图（ graph）是比线性表、树与二叉
树更为复杂的一种数据结构。
?2.8.1 图的基本概念
如果数据元素集合 D中的各数据元素
之间存在任意的前后件关系，则此数据结
构称为图。图通常用 G表示。
在图中，如果对于任意的两个结点 a
与 b，当结点 a是结点 b的前件，且结点 b也
是结点 a的前件时，则称该图为无向图。
如果对于任意的两个结点 a与 b，当结
点 a是结点 b的前件，结点 b不都是结点 a的
前件时，则称该图为有向图。
在有向图中，通常用带有箭头的边来
连接两个有关联的结点（由前件结点指向
后件结点）。
如图 2.55为两个有向图。
?2.8.2 图的存储结构
一般是根据对图的具体运算来选取合
适的存储结构。
? 1．关联矩阵
由上述关联矩阵可以明显地看出，无
向图的关联矩阵是对称矩阵，且对角线上
的元素均为 0。
这是因为，对于无向图来说，各结点
之间的前后件关系是对称的，且不考虑结
点自身之间的前后件关系。
有向图的关联矩阵不一定是对称的，
且其对角线上的元素也不一定是 0 。
关联矩阵也称为邻接矩阵。
? 2．求值矩阵
关联矩阵只表示了图的结构，即图中
各结点的后件关系。
但在许多实际问题中，还需要对两个
关联结点之间的值进行运算。
这就是说，除了要存储图中各结点值
以及各结点之间的关系外，还必须存储图
中每两个结点之间的求值函数。
为了完整地存储一个有值图，可以用
一维数组存储图中各结点的数据信息，用
关联矩阵存储图中任意两个结点之间的关
联信息，用求值矩阵存储图中任意两个结
点之间的求值函数。
例如，有 A,B,C,D,E,F,G，
H八个城市，它们的交通情况及运费如图
2.57所示。
? 3．邻接表
邻接表这种存储结构也称为“顺序 –
索引 –链接”存储结构。
假设图中共有 n个结点，其结点值分
别为 d1,d2,…, dn，并用自然数将它们
依次编号为 1,2,…, n。
首先，用一个顺序存储空间来存储图
中各结点的信息。
其次，对图中每一个结点 dk(k = 1，
2,…, n)构造一个单链表。
对于图 2.59所示的有值图，其邻
接表如图 2.60所示。
邻接表特别适合于表示结点数多但边
数较少的图。
? 4．邻接多重表
在邻接多重表中，每条边用一个存储
结点表示，每个存储结点由五个域组成，
如图 2.61所示。
?2.8.3 图的遍历
在实际应用中，往往需要从图的某一
结点出发访问到图中的所有结点。这一访
问过程称为图的遍历。
工程中常用的图遍历方法主要有纵向
优先搜索法和横向优先搜索法两种。
? 1．纵向优先搜索法
纵向优先搜索法遍历图的基本思想
如下。
从图中某一结点作为当前结点，然
后进行以下过程：
① 处理或输出当前结点，并记录当前
结点的查访标志。
② 若当前结点有后件结点，则取第一
个后件结点。若该后件结点未被查访过，
则以该后件结点为当前结点用纵向优先搜
索法进行查访。
? 2．横向优先搜索法
横向优先搜索法又称为广度优先搜索
法。其基本思想如下。
从图的某一个结点出发，首先依次访
问该结点的后件结点，然后再顺序访问这
些后件结点的所有未被访问过的后件结点。
依此类推，直到所有被访问结点的后件结
点均被访问过为止。
2.9 索引存储结构
?2.9.1 索引存储的概念
索引存储的结构有两部分组成，一是
存储各个子表，二是存储索引表。
为了实现索引存储，需要解决以下两
个问题：
① 对数据集合中的元素进行划分。
② 索引表的具体存储结构以及每个子
表的存储结构。
? 1．数据元素的划分
例 2.5 设有一个学生成绩表如表 2.2所
示。
? 2．索引存储的方式
索引存储包括索引表的存储以及各个子
表的存储。
2.9.2,顺序 -索引 -顺序”存储方式
在“顺序 -索引 -顺序”存储方式中，索
引表以及各子表均采用顺序分配的存储方法。
图 2.62是例 2.5中学生成绩表的“顺序 -
索引 -顺序”存储方式的物理状态。
?2.9.3,顺序 -索引 -链接”
存储方式
“顺序 -索引 -链接”存储方式是指用
顺序分配的方法存储索引表，而用链式分
配的方法存储各子表。
?2.9.4 多重索引存储结构
如果在索引存储结构中，其索引表本
身又是索引存储结构，则称为二重索引存
储结构。图 2.64（ a）为“顺序 -索引 -顺序 -
索引 -链接”方式的二重索引存储结构示意
图，图 2.64（ b）为“顺序 -索引 -链接 -索引
-链接”方式的二重索引存储结构示意图。
2.1 数据结构的基本概念
2.2 线 性 表
2.3 栈及其应用
2.4 队列及其应用
2.5 线性链表
2.6 数组与字符串
2.7 树与二叉树
2.8 图
2.9 索引存储结构
数据是计算机化的信息，即计算机处
理的对象是数据。
各数据之间的一定关系，称为数据的
逻辑结构,数据在计算机中的存储位置有
着一定的关系，称为数据的物理结构（或
存储结构）。
数据结构作为计算机的一门学科，它
研究的内容，通常要涉及以下三个方面的
问题：
① 数据的逻辑结构；
② 数据的存储结构；
③ 对各种数据结构进行的运算。
主要目的是为了提高数据处理的效
率。
包括两个方面：一是提高数据处理
的速度，二是尽量节省在数据处理过程
中所占用的计算机存储空间。
2.1 数据结构的基本概念
数据结构是指相互有关联的数据元素
的集合。
组成该数据结构（包括逻辑结构和存
储结构）的数据元素称为一个结点。
在数据处理领域中，每一个需要处理
的对象都可以抽象成数据元素。
在具有相同特征的数据元素集合中，
各个数据元素之间存在有某种关系，反映
了该集合中的数据元素所固有的一种结构。
数据元素之间的任何关系都可以用前
后件关系来描述。
? 1．数据的逻辑结构
所谓结构实际上就是指数据元素之间
的前后件关系。
一个数据结构应包含以下两方面的信
息：
① 表示数据元素的信息。
② 表示各数据元素之间的前后件关系
的信息。
数据元素之间的前后件关系是指它们
的逻辑关系，而与它们在计算机中的存储
位置无关。
数据结构实际上是数据的逻辑结构。
数据的逻辑结构，是指反映数据元素
之间逻辑关系的数据结构。
数据的逻辑结构有两个要素：一是数
据元素的集合，通常记为 D；二是 D上的
关系，它反映了 D中各数据元素之间的前
后件关系，通常记为 R。
即一个数据结构可以表示成
B = (D,R)
例 2.1 一年四季的数据结构可以
表示成
B = (D,R)
D = {春,夏,秋,冬 }
R = {(春,夏 ),(夏,秋 ),(秋,冬 )}
例 2.3 n维向量
X = (x1,x2,…,xn)
也是一种数据结构。即 X = (D,R)，其
中数据元素的集合为：
D = {x1,x2,…,xn}
关系为：
R = {(x1,x2),(x2,x3),…,( xn– 1,xn)}
例如,m× n的矩阵
是一个数据结构。在这个数据结构中，
矩阵的每一行
Ai = (ai1,ai2,…, ain),i= 1,2,…,m
可以看成是它的一个数据元素。即这
个数据结构的数据元素的集合为：
D = {A1,A2,…, Am}
D上的一个关系为：
R = {(A1,A2),(A2,A3),…, (Ai，
Ai+1),… Am – 1,Am}}
显然，数据结构 A中的每一个数据元
素 Ai（ i = 1,2,…,m）又是另一个数据结构，
即数据元素的集合为：
Di = {ai1,ai2,…, ain}
Di上的一个关系为：
Ri = {(ai1,ai2),(ai2,ai3),…, (ai，
ai,j + 1),…, (ai,n –1,ain)}
一个数据结构除了用二元关系表示外，
还可以直观地用图形表示。
反映家庭成员间辈份关系的数据结构
可以用图 2.2所示的图形表示。
例 2.4 用图形表示数据结构 B =（ D，
R），其中
D = {di |1≤i≤7} = {d1,d2,d3,d4，
d5,d6,d7}
R = {(d1,d3),(d1,d7),(d2,d4)，
(d3,d6),(d4,d5)}
这个数据结构的图形表示如图 2.3所示。
在数据结构中，没有前件的结点称为
根结点；没有后件的结点称为终端结点
（也称为叶子结点）。
通常，一个数据结构中的元素结点可
能是在动态变化的。
数据结构中的结点（即数据元素）个
数在动态地变化，而且，各数据元素之间
的关系也有可能在动态地变化。
如果在一个数据结构中一个数据元
素都没有，则称该数据结构为空的数据
结构。
在一个空的数据结构中插入一个新
的元素后就变为非空；在只有一个数据
元素的数据结构中，将该元素删除后就
变为空的数据结构。
将数据结构分为两大类型：线性结构
与非线性结构。
如果一个非空的数据结构满足下列两
个条件：
① 有且只有一个根结点；
② 每一个结点最多有一个前件，也最
多有一个后件。
则称该数据结构为线性结构。
线性结构又称线性表。
例如，图 2.4所示的数据结构显然是满
足上述两个条件的，但它不属于线性结构
这个类型，因为如果在这个数据结构中删
除结点 A后，就不满足上述的条件①。
一个数据结构不是线性结构，则称之
为非线性结构。
线性结构与非线性结构都可以是空的
数据结构。
如果对该数据结构的运算是按线性结
构的规则来处理的，则属于线性结构；否
则属于非线性结构。
? 2．数据的存储结构
一个数据结构中的各数据元素在计算
机存储空间中的位置关系与逻辑关系是有
可能不同的。
数据的逻辑结构在计算机存储空间中
的存放形式称为数据的存储结构 。
在数据的存储结构中，不仅要存放各
数据元素的信息，还需要存放各数据元素
之间的前后件关系的信息。
常用的存储结构有顺序、链接、索引、
散列等存储结构。
? （ 1）顺序存储结构
顺序存储结构主要用于线性结构。在
这种存储方式中，把逻辑上相邻的数据元
素结点存储在物理上相邻的存储单元中，
各结点之间的关系由存储单元的邻接关系
来体现。
图 2.5是将线性结构 {(K1,K2),(K2，
K3),(K3,K4),(K4,K5),(K5,K6)，
(K6,K7)}顺序地存放在存储单元中的示
意图。
? （ 2）链接存储结构
在链接存储结构中，每个存储结
点要有两部分组成：一部分用于存放
数据信息，另一部分用于存放指针。
其中指针用于指向该结点的前件
或后件。
利用链接存储方式也可以存储非线性
结构。
图 2.7（ a）和（ b）分别为一棵二叉树
的逻辑结构与链接存储结构的示意图。
? （ 3）索引存储结构
索引存储结构是指将数据元素按索引
函数值进行分组，具有相同索引函数值的
数据元素被分在同一组中，而同一组中的
元素再按某种存储方式（顺序存储或链接
存储）进行存储。
? （ 4）散列存储结构
散列存储结构是指根据数据元素的关
键字值来确定其存储地址。
2.2 线 性 表
?2.2.1 线性表顺序存储结构
线性表由一组数据元素构成。
数据元素可以是简单项（如上述例子
中的数、字母、季节名等）。在稍微复杂
的线性表中，一个数据元素还可以由若干
个数据项组成。
例如，某班的学生情况登记表,如表
2.1所示。
学生情况登记表就是一个文件，其中
每一个学生的情况就是一个记录。
综上所述，线性表是由 n（ n≥0）个数
据元素 a1,a2,…, an组成的一个有限序
列。表中的每一个数据元素，除了第一个
外，有且只有一个前件；除了最后一个外，
有且只有一个后件。即线性表或是一个空
表，或可以表示为：
(a1,a2,…, ai,…, an)
其中 ai(i = 1,2,…, n)是属于数据对
象的元素，通常也称其为线性表中的一个
结点。
非空线性表有如下一些结构特征：
① 有且只有一个根结点 a1，它无前件。
② 有且只有一个终端结点 an，它无后
件。
③ 除根结点与终端结点外，其他所有
结点有且只有一个前件，也有且只有一个
后件。线性表中结点的个数 n称为线性表
的长度。当 n = 0时，称为空表。
在计算机中存放线性表，一种最简单
的方法是顺序存储，也称为顺序分配。顺
序存储的线性表通常称为顺序表。
线性表的顺序存储结构具有以下两个
基本特点：
① 线性表中所有元素所占的存储空间
是连续的。
② 线性表中各数据元素在存储空间中
是按逻辑顺序依次存放的。
在计算机中的顺序存储结构如图
2.8所示。
在程序设计语言中，通常定义一个一
维数组来表示线性表的顺序存储空间。
因为程序设计语言中的一维数组与计
算机中实际的存储空间结构是类似的，这
就便于用程序设计语言对线性表进行各种
运算处理。
建立一个空线性表的顺序存储空间
（即初始化线性表的顺序存储空间）的 C
语言描述如下：
#include "stdlib.h"
void initsl(v,m,n) /*初始化顺序表 */
ET *v； /*v返回顺序表空间的首地址,ET表示元
素的数据类型 */
int m,*n； /*m为顺序表的空间容量（字节
数）,n返回线性表的长度 */
{ v=malloc(m*sizeof(ET))； /*申请顺序表空间 */
*n=0； /*线性表长度为 0*/
return；
}
?2.2.2 顺序表的插入与删除
? 1．顺序表的插入运算
首先举一个例子来说明如何在顺序存
储结构的线性表中插入一个新元素。
一般来说，设长度为 n的线性表为：
要在线性表的第 i个元素 ai之前插入一
个新元素 b，插入后得到长度为 n + 1的线
性表为：
则插入前后的两线性表中的元素满足
如下关系：
在线性表顺序存储的情况下，要插入
一个新元素，由于数据元素的移动而消耗
较多的处理时间，因此其效率是很低的，
特别是在线性表比较大的情况下更为突出。
下面是线性表在顺序存储结构下插入
算法的 C语言描述。
void insl(v,m,n,i,b) /*顺序表的插入 */
ET v[],b； /*v为顺序表空间,b为插
入的元素 */
int m,*n,i； /*m为顺序表空间容量,n
为指向线性表长度的指针,
i为插入元素的序号 */
{ if (*n==m) /*顺序表空间已满,上溢
错误,返回 */
{ printf("overflow \n")； return； }
if (i＞ *n–1) i=*n+1； /*在线性表的
最后插入 */
if (i＜ 1＝ i=1； /*在线性表的第 1个
元素之前插入 */
for (j=*n； j＜ =i； j––＝ /*插入位
置以后的元素依次往后移动一个位置 */
v[j]=v[j–1]；
v[i–1]=b； /*插入元素 b*/
*n= *n+1； /*线性表长度加 1*/
return；
}
? 2．顺序表的删除运算
首先举一个例子来说明如何在顺序存
储结构的线性表中删除一个元素。
一般来说，设长度为 n的线性表为：
现要删除第 i个元素，删除后得到长度
为 n– 1的线性表为：
则删除前后的两线性表中的元素满足
如下关系：
在线性表顺序存储的情况下，要删除
一个元素，由于数据元素的移动而消耗较
多的处理时间，其效率也是很低的，特别
是在线性表比较大的情况下更为突出。
下面是线性表在顺序存储结构下删除
算法的 C语言描述。
void desl(v,m,n,i) /*顺序表的删除 */
ET v[]； /*顺序表空间 */
int m,*n,i； /*m为顺序表空间容量,n
为指向线性表长度的指针,
i为删除元素的序号 */
{ if (*n==0) /*线性表为空,下溢错误,
返回 */
printf("underflow \n")；
return； }
if ((i＜ 1) | | (i＞ *n)) /*线性表中没有
这种下标的元素,返回 */
printf("Not this element in the list
\n")； return； }
for (j=i； j＜ =*n–1； j++＝ /*第 i个以
后的元素依次往前移动一个位置 */
v[j–1]=v[j]；
*n= *n–1； /*线性表长度减 1*/
return；
}
2.3 栈及其应用
?2.3.1 栈的基本概念
栈实际上也是线性表，只不过是一种
特殊的线性表。
栈 (stack)是限定在一端进行插入与删
除的线性表。
往栈中插入一个元素称为入栈运
算，从栈中删除一个元素（即删除栈
顶元素）称为退栈运算。
栈顶指针 top动态反映了栈中元
素的变化情况。
图 2.11是栈的示意图。
图 2.12中给出了具有嵌套调用关系的
五个程序，其中主程序要调用子程序
SUB1,SUB1要调用子程序 SUB2,SUB2
要调用子程序 SUB3,SUB3要调用子程序
SUB4,SUB4不再调用其他子程序了。
计算机系统在处理时要用一个栈来动
态记忆调用过程中的路径，其基本原则如
下：
① 在开始执行程序前，建立一个栈，
其初始状态为空。
② 当发生调用时，将当前调用的返回
点地址（在图 2.12中用语句标号表示）入
栈。
③ 当遇到从某个子程序返回时，从栈
顶取出返回点地址。
?2.3.2 栈的顺序存储及其运
算
在栈的顺序存储空间 S（ 1,m）中,S
（ bottom）通常为栈底元素（在栈非空的
情况下）,S（ top）为栈顶元素。 top = 0
表示栈空； top = m表示栈满。
建立一个空栈的顺序存储空间（即初
始化栈的顺序存储空间）的 C语言描述如
下：
#include "stdlib.h"
void init_stack(s,m,top) /*初始化栈空间 */
ET *s； /*栈空间 */
int m,*top； /*m为栈空间容量,top为栈顶指针 */
{ s=malloc(m*sizeof(ET))； /*申请容量为 m的栈
空间 */
*top=0； /*置栈空 */
return；
}
栈的基本运算有三种：入栈、退栈与
读栈顶元素。下面分别介绍在顺序存储结
构下栈的这三种运算。
? （ 1）入栈运算
入栈运算是指在栈顶位置插入一个新
元素。
入栈运算的 C语言描述。
void push(s,m,top,x) /*在容量为 m的栈 S中插入一
个元素 x（入栈运算） */
ET s[],x； /*s为栈空间,x为入栈元素 */
int m,*top； /*m为栈空间容量,top为栈顶指针 */
{ if (*top==m) /*栈满,上溢错误,返回 */
{ printf("Stack–overflow\n")； return； }
*top=*top+1； /*栈顶指针进一 */
s[*top–1]=x； /*将元素 x插入到栈顶位置 */
return；
}
? （ 2）退栈运算
退栈运算是指取出栈顶元素并赋给一
个指定的变量。这个运算有两个基本操作：
首先将栈顶元素（栈顶指针指向的元素）
赋给一个指定的变量，然后将栈顶指针退
一（即 top减 1）。
退栈运算的 C语言描述。
void pop(s,m,top,y) /*在容量为 m的栈 S中删除栈
顶元素（退栈运算） */
ET s[],*y； /*s为栈空间,y指向存放退栈元素的地
址 */
int m,*top； /*m为栈空间容量,top为栈顶指针 */
{ if (*top==0) /*栈空,下溢错误,返回 */
{ printf("Stack–underflow\n")； return； }
*y=s[*top–1]； /*读取栈顶元素 */
*top=*top–1； /*栈顶指针退一 */
return；
}
? （ 3）读栈顶元素
读栈顶元素是指将栈顶元素赋给一
个指定的变量。必须注意，这个运算不
删除栈顶元素，只是将它的值赋给一个
变量，因此，在这个运算中，栈顶指针
不会改变。
读栈顶元素算法的 C语言描述。
void top(s,m,top,y) /*读栈顶元素 */
ET s[],*y； /*s为栈空间,y指向存放栈顶元
素的地址 */
int m,*top； /*m为栈空间容量,top为栈顶
指针 */
{ if (*top==0) /*栈空错误,返回 */
{ printf("Stack empty \n")； return； }
*y=s[*top–1]； /*读取栈顶元素 */
return；
}
?2.3.3 栈的应用
2.3.1中讨论的子程序嵌套调用就是栈
的一个实际应用。
栈还用于实现递归调用过程、表达式
的处理和中断的处理。
? 1．递归过程的实现
例如，在本书的第 1章例 1.5中提到，
对于输入的参数 n，依次打印输出自然数 1
到 n。为了不使用局部变量，其 C函数如下：
#include "stdio.h"
wrt1(int n)
{ if (n!=0)
{ wrt1(n–1)； printf("%d\n",n)； }
return；
}
? 2．表达式的计算
在编译系统或解释系统中，常利用栈
来处理表达式的计算问题。
2.4 队列及其应用
?2.4.1 队列的基本概念
队列（ equeue）是指允许在一端进行
插入、而在另一端进行删除的线性表。
允许插入的一端称为队尾,允许删除
的一端称为排头 。
在队列这种数据结构中，最先插入的
元素将最先能够被删除，反之，最后插入
的元素将最后才能被删除。
往队列的队尾插入一个元素称为入队
运算，从队列的排头删除一个元素称为退
队运算。
图 2.16是在队列中进行插入与删除的
示意图。
与栈类似，在程序设计语言中，用一
维数组作为队列的顺序存储空间。
在操作系统中，用一个队列来组织管
理用户程序的排队执行，原则是：
① 初始时队列为空。
② 当有用户程序来到时，将该用户程
序加入到队列的末尾进行等待。
③ 当计算机系统执行完当前的用户程
序后，就从队列的头部取出一个用户程序
执行。
?2.4.2 循环队列及其运算
在实际应用中，队列的顺序存储结构
一般采用循环队列的形式。
所谓循环队列，就是将队列存储空间
的最后一个位置绕到第一个位置，形成逻
辑上的环状空间，供队列循环使用，如图
2.17所示。
由图 2.18中循环队列动态变化的过程
可以看出，当循环队列满时有 front = rear，
而当循环队列空时也有 front = rear。
为了能区分队列满还是队列空，通常
还需增加一个标志 s,s值的定义如下：
建立一个循环队列顺序存储空间（即
初始化循环队列顺序存储空间）的 C语言
描述如下：
#include "stdlib.h"
void init_queue(q,m,front,rear,s) /*初始化
循环队列 */
ET *q； /*循环队列空间 */
int m,*front,*rear,*s； /*m为循环队列容
量,front为排头指针,
rear为队尾指针,s为标
志 */
{ q=malloc(m*sizeof(ET))； /*申请容
量为 m的循环队列空间 */
*front=m； *rear=m； /*置头尾指
针初值 */
*s=0； /*置队列空标志 */
return；
}
? （ 1）入队运算
入队运算是指在循环队列的队尾加入
一个新元素。
这个运算有两个基本操作：首先将队
尾指针进一（即 rear = rear + 1）,并当 rear
= m + 1时置 rear = 1；然后将新元素插入
到队尾指针指向的位置。
下面是入队运算的 C语言描述。
/*在容量为 m的循环队列 Q中插入一个
元素 x（入队运算） */
void addcq(q,m,rear,front,s,x)
ET q[ ],x； /*q为循环队列空间,x为
入队的元素 */
int m,*rear,*front,*s； /*m为循环队
列容量,front为排头指针,
rear为队尾指针,s
为标志 */
{ if ((*s==1) && (*rear== *front)) /*队列
满,上溢错误,返回 */
{ printf("Queue–OVERFLOW \n")；
return； }
*rear= *rear+1； /*队尾指针进一 */
if (*rear==m+1) *rear=1； /*队尾指针循
环 */
q[*rear–1]=x； /*元素 x插入到队尾 */
*s=1； /*置队列非空标志 */
return；
}
? （ 2）退队运算
退队运算是指在循环队列的排头位置
退出一个元素并赋给指定的变量。这个运
算有两个基本操作：首先将排头指针进一
（即 front = front + 1）,并当 front = m + 1
时置 front = 1；然后将排头指针指向的元
素赋给指定的变量。
下面是退队运算的 C语言描述。
/*在容量为 m的循环队列中删除一个
元素（退队运算） */
void delcq(q,m,rear,front,s,y)
ET q[ ],*y； /*q为循环队列空间,y存
放退队的元素 */
int m,*rear,*front,*s； /*m为循环队
列容量,front为排头指针,
rear为队尾指针,s
为标志 */
{ if (*s==0) /*队列空,下溢错误,返回 */
{ printf("Queue–UNDERFLOW \n")；
return； }
*front= *front+1； /*排头指针进一 */
if (*front==m+1) *front=1； /*排头指针
循环 */
*y=q[*front–1]； /*读出排头元素 */
if (*front== *rear) *s=0； /*置队列空标
志 */
return；
}
?2.4.3 队列的应用
凡是按“先来先服务”（即“先进先
出”）原则处理的问题，都可以用队列结
构来解决。
下面再介绍三个用模拟队列结构来解
决的问题。
? 1．给工人分配工作的模拟
? 2.输入输出缓冲区的结构
为了解决上述这种两个设备操作速度
不匹配的矛盾，通常是在两个设备之间设
置一个缓冲区，如图 2.19所示。
利用循环队列结构的缓冲区，就解决
了计算机处理数据与打印机打印输出的速
度不匹配的矛盾，实现了两个设备之间数
据的正常传送。
? 3.汽车加油站的工作模拟
2.5 线性链表
?2.5.1 线性链表的基本概念
? 1．线性链表
线性表的链式存储结构称为线性链表。
为了适应线性表的链式存储结构，计算
机存储空间被划分为一个一个小块，每一
小块占若干字节，通常称这些小块为存储
结点。
将存储空间中的每一个存储结点分为
两部分：一部分用于存储数据元素的值，
称为数据域；另一部分用于存放下一个数
据元素的存储序号（即存储结点的地址），
即指向后件结点，称为指针域。
线性链表中存储结点的结构如图 2.20
所示。
指向线性表中第一个结点的指针
HEAD称为头指针。
当 HEAD = NULL（或 0）时称为
空表。
对于线性链表，可以从头指针开始，
沿各结点的指针扫描到链表中的所有结
点。
为了弥补线性单链表的这个缺点，在
某些应用中，对线性链表中的每个结点设
置两个指针，一个称为左指针（ Llink），
用以指向其前件结点；另一个称为右指针
（ Rlink），用以指向其后件结点。
这样的线性链表称为双向链表，其逻
辑状态如图 2.23所示。
? 2．带链的栈
栈也是线性表，也可以采用链式存储
结构。
图 2.24是栈在链式存储时的逻辑状态
示意图。
在实际应用中，带链的栈可以用来收
集计算机存储空间中所有空闲的存储结点，
这种带链的栈称为可利用栈。
如图 2.25所示 。
? 3．带链的队列
与栈类似，队列也是线性表，也可以
采用链式存储结构。
图 2.26（ a）是队列在链式存储时的逻
辑状态示意图。
图 2.26(b)是将新结点 p入队的示
意图。
图 2.26（ c）是将排头结点 p退出队列
的示意图。
?2.5.2 线性链表的基本运算
线性链表的运算主要有以下几个：
① 在线性链表中包含指定元素的结点
之前插入一个新元素。
② 在线性链表中删除包含指定元素的
结点。
③ 将两个线性链表按要求合并成一个
线性链表。
④ 将一个线性链表按要求进行分解。
⑤ 逆转线性链表。
⑥ 复制线性链表。
⑦ 线性链表的排序。
⑧ 线性链表的查找。
1.在线性链表中查找指定元素
对线性链表进行扫描查找，在线性链
表中寻找包含指定元素值的前一个结点。
? 2．线性链表的插入
线性链表的插入是指在链式存储结构
下的线性表中插入一个新元素。
为了要在线性链表中插入一个新元素，
首先要给该元素分配一个新结点，然后将
存放新元素值的结点链接到线性链表中指
定的位置。
? 3．线性链表的删除
线性链表的删除指在链式存储结构下
的线性表中删除包含指定元素的结点。
为了在线性链表中删除包含指定元素
的结点，首先要在线性链表中找到这个结
点，然后将要删除结点放回到可利用栈。
?2.5.3 循环链表
循环链表的结构与前面所讨论的线性
链表相比，具有以下两个特点：
①循环链表的头指针指向表头结点。
② 在循环链表中，所有结点的指针构
成了一个环状链。
图 2.29是循环链表的示意图。
在实际应用中，循环链表与线性单链
表相比主要有以下两个方面的优点：
① 在循环链表中，只要指出表中任何
一个结点的位置，就可以从它出发访问到
表中其他所有的结点。
② 由于在循环链表中设置了一个表头
结点，因此，在任何情况下，循环链表中
至少有一个结点存在，从而使空表与非空
表的运算统一。
?2.5.4 多项式的表示及其运算
设多项式为：
Pn(x) = anxn + an–1xn –1 + … + a1x + a0
在采用链表表示多项式时，对于多项
式中每一个非零系数的项构成链表中的一
个结点，而对于系数为零的项就不用表示。
多项式中非零系数项所构成的结点如图
2.30所示。
设只表示非零系数项的多项式为：
其中 ak≠0(k= 1,2,…,m),em＞ em–1＞ …
＞ e1≥0。
若用线性单链表表示，其逻辑状态如
图 2.31（ a）所示。
若用循环链表表示，其逻辑状态如图
2.31（ b）所示。
多项式的运算主要有以下五种：
① 多项式链表的生成。
② 多项式链表的释放。
③ 多项式的输出。
④ 多项式的相加。
⑤ 多项式的相乘。
下面以循环链表表示的多项式为例来
讨论各种运算。
? 1．多项式链表的生成
主要包括以下两步：
① 建立一个表头结点，其指数域值为
–1，指针域指向表头结点自身，头指针也
指向表头结点。
② 按降幂顺序以数偶形式依次输入多
项式中非零系数项的指数 ek和系数 ak(k =
m,m – 1,…, 1)，最后以输入指数值 –1
为结束。
? 2．多项式链表的释放
从表头结点开始，逐步释放链表中的
各结点。
? 3．多项式的输出
从表头结点后的第一个结点开始，以
数偶形式顺链输出各结点中的指数域与系
数域的内容。
? 4．多项式的相加
多项式相加的运算规则很简单，只
要从两个多项式链表的第一个元素结点
开始检测 。
? 5．多项式的相乘
2.6 数组与字符串
?2.6.1 数组的顺序存储结构
数学中的矩阵在程序设计语言中用二
维数组表示。
二维数组在计算机中是顺序存储的。
1.二维数组以行为主的顺序存储
二维数组以行为主的顺序存储是指将数组
中的元素一行接一行地顺序存储在计算机的连续
存储空间中。
例如，一个 m× n的矩阵
在计算机中以行为主的顺序存储形式如图
2.32所示。
2.二维数组以列为主的顺序存储
二维数组以列为主的顺序存储是指将数组
中的元素一列接一列地顺序存储在计算机的连续
存储空间中。
例如，一个 m× n的矩阵
在计算机中以列为主的顺序存储形式如图
2.33所示。
?2.6.2 规则矩阵的压缩
规则矩阵是指，矩阵中非零元素的
分布是有规律的。
在存储一个规则矩阵时，只需存储
非零元素即可，而对于大部分的零元素
或者重复的非零元素（如对称矩阵）不
必存储。
规则矩阵的这种存储方法称为压缩
存储。
? 1.下三角矩阵的压缩存储
存储的原则是：用一个一维数组以行
为主顺序存放下三角矩阵中的所有下三角
部分的元素。
设 n阶下三角矩阵为：
经压缩后，存放在一维数组 B中的形式如图
2.34（ a）所示。
下三角矩阵 A也可以用以列为主的方式压缩
存储在一维数组 B中，其存储形式如图 2.34（ b）
所示。
显然，在以列为主压缩存储的情况下，访
问下三角矩阵 A中的元素时其下标运算要比以行
为主压缩存储时稍为复杂一些。
因此，在实际应用时，一般采用以行为主
压缩存储下三角矩阵。
? 2.对称矩阵的压缩存储
对称矩阵的压缩存储与下三角矩阵完
全相同。
? 3.三对角矩阵的压缩存储
n阶三对角矩阵的形式为：
对于 n阶三对角矩阵，用一个长度
为 3n– 2的一维数组以行为主存放三条
对角线上的元素，其存储形式如图 2.35
（ a）所示。
在用一维数组 B以行为主存放三对角
矩阵 A中的元素 aij时，其访问公式为：
对于三对角矩阵，也可以用一维数组
B以列为主存放三条对角线上的元素，如
图 2.35（ b）所示。
在这种情况下，访问三对角矩阵 A中
元素 aij的公式为：
?2.6.3 一般稀疏矩阵的表示
如果一个矩阵中绝大多数的元素值为
零，只有很少的元素值非零，则称该矩阵
为稀疏矩阵。
在实际存储稀疏矩阵时，可以只存储
非零元素，而大量的零元素不存储，这就
是稀疏矩阵的压缩存储。
1.稀疏矩阵的三列二维数组表示
在压缩存储形式中，每一个非零元素
应包括以下三个信息：
① 非零元素所在的行号 i；
② 非零元素所在的列号 j；
③ 非零元素的值 V。
即每一个非零元素可以用下列三元组
表示：
（ i,j,V）
为了表示的惟一性，除了每一个非零
元素用一个三元组表示外，在所有表示非
零元素的三元组之前再添加一个三元组
（ I,J,t）
一般来说，具有 t个非零元素的稀疏矩
阵可以用 t + 1个三元组表示，其中第一个
三元组用以表示稀疏矩阵的总体信息，其
后的各三元组依次表示各非零元素，且按
以行为主的顺序排列。
为了使各三元组的结构更紧凑，通常
将这些三元组组织成三列二维表格的形式，
一般又表示成三列二维数组的形式，并简
称为三列二维数组。
具有 t个非零元素的稀疏矩阵，
其对应的三列二维数组为 t + 1行,3
列，共有 3(t + 1)个元素。
最后需要说明一点，在用三列二维数
组表示稀疏矩阵后，如果稀疏矩阵的运算
结果其非零元素的个数不发生变化（如矩
阵转置），则运算结果可直接采用三列二
维数组表示的形式；如果运算结果其非零
元素的个数发生了变化（如矩阵乘积），
则运算结果只能用一般的稀疏矩阵表示，
如有必要，则再用三列二维数组表示。
? 2．十字链表
稀疏矩阵还可以用链式结构来表示。
在用链式结构表示稀疏矩阵时，矩阵中的
每一个非零元素对应一个结点，每个结点
有五个域：行域、列域、值域、向下域与
向右域，如图 2.40所示。
用十字链表表示稀疏矩阵的结构特点
如下：
① 稀疏矩阵的每一行与每一列均用带
表头结点的循环链表表示。
② 表头结点中的行域与列域的值均置
为 0（即 row = 0,col = 0）。
③ 行、列链表的表头结点合用，且这
些表头结点通过值域（即 val）相链接，并
再增加一个结点作为它们的表头结点 H，
其行、列域值分别存放稀疏矩阵的行数与
列数。
例如，稀疏矩阵
?2.6.4 字符串
? 1．字符串的基本概念
字符串（ string）是字符的一个有限
序列，它本质上就是数据元素类型为字符
的线性表。字符串一般表示为：
"a1a2… ai… an"
对线性表的所有运算，对字符串也
适用。
字符串除了具有一般线性表所具有
的运算外，由于字符串具有多种数据类
型的特点，因此，对字符串的运算要比
一般的线性表更丰富。
① 连接运算。
② 取子串运算。
③ 删除子串运算。
④ 插入子串运算。
⑤ 求子串位置。
? 2．字符串匹配
在一般的编辑软件系统中，经常要遇
到在一个给定的文本中检测一个特定的字
符串的问题。这就是字符串匹配。字符串
匹配又称模式匹配。
（ 1）字符串匹配的简单算法
（ 2）字符串匹配的 KMP算法
2.7 树与二叉树
?2.7.1 树的基本概念
树（ tree）是一种简单的非线性
结构。
图 2.42表示了一棵一般的树。
在树的图形表示中，总是认为在用直
线连起来的两端结点中，上端结点是前件，
下端结点是后件，这样，表示前后件关系
的箭头就可以省略。
例如，图 2.43中的树表示了学校行政
关系结构；图 2.44中的树反映了一本书的
层次结构。
在树结构中，每一个结点只有一个前
件，称为父结点。
在树中，没有前件的结点只有一个，
称为树的根结点，简称为树的根。
在树结构中，每一个结点可以有多个
后件，它们都称为该结点的子结点。
没有后件的结点称为叶子结点。
在树结构中，一个结点所拥有的后件
个数称为该结点的度。
在树中，所有结点中的最大度称为树
的度。
树结构具有明显的层次关系，即树是
一种层次结构。
根结点在第 1层；
同一层上所有结点的所有子结点在下
一层。
树的最大层次称为树的深度。
在树中，以某结点的一个子结点为根
构成的树称为该结点的一棵子树。
在树中，叶子结点没有子树。
?2.7.2 二叉树及其基本性质
? 1．什么是二叉树
二叉树 (binary tree)是一种很有用的非
线性结构。二叉树具有以下两个特点：
（ 1）非空二叉树只有一个根结点；
（ 2）每一个结点最多有两棵子树，
且分别称为该结点的左子树与右子树。
图 2.46（ a）是一棵只有根结点
的二叉树，
图 2.46（ b）是一棵深度为 4的
二叉树。
?2．二叉树的基本性质
二叉树具有以下几个性质：
性质 1 在二叉树的第 k层上，最多有
2k–1（ k≥1）个结点。
根据二叉树的特点，这个性质是显然
的。
性质 2 深度为 m的二叉树最多有 2m–1
个结点。
性质 3 在任意一棵二叉树中，度为 0
的结点（即叶子结点）总是比度为 2的结
点多一个。
性质 4 具有 n个结点的二叉树，其深
度至少为 [log2n] + 1，其中 [log2n]表示取
log2n的整数部分。
? 3.满二叉树与完全二叉树
? （ 1）满二叉树
满二叉树是指除最后一层外，每一层
上的所有结点都有两个子结点。
? （ 2）完全二叉树
完全二叉树是指这样的二叉树：
除最后一层外，每一层上的结点数均
达到最大值；在最后一层上只缺少右
边的若干结点。
性质 5 具有 n个结点的完全二叉树的
深度为 [log2n] + 1。
性质 6 设完全二叉树共有 n个结点。
如果从根结点开始，按层序（每一层从左
到右）用自然数 1,2,…, n给结点进行
编号，则对于编号为 k(k = 1,2,…, n)的
结点有以下结论：
① 若 k = 1，则该结点为根结点，它没
有父结点；若 k＞ 1，则该结点的父结点编
号为 INT(k/2)。
② 若 2k≤n，则编号为 k的结点的左子
结点编号为 2k；否则该结点无左子结点
（显然也没有右子结点）。
③ 若 2k + 1≤n，则编号为 k的结点的右
子结点编号为 2k + 1；否则该结点无右子
结点。
?2.7.3 二叉树的存储结构
? 1．二叉链表
在计算机中，二叉树通常采用链式存
储结构。
与线性链表类似，用于存储二叉树中
各元素的存储结点也由两部分组成：数据
域与指针域。
用于存储二叉树的存储结点的指针域
有两个：一个用于指向该结点的左子结点
的存储地址，称为左指针域；另一个用于
指向该结点的右子结点的存储地址，称为
右指针域。
图 2.49为二叉树存储结点的示意图。
由于二叉树的存储结构中每一个存储
结点有两个指针域，因此，二叉树的链式
存储结构也称为二叉链表。
图 2.50 所示。
? 2．二叉链表的生成
二叉链表的生成是指根据给定的二叉
树在计算机中建立链式存储结构。
?2.7.4 二叉树的遍历
二叉树的遍历是指不重复地访问二叉
树中的所有结点。
二叉树的遍历可以分为三种：前序遍
历、中序遍历、后序遍历。
? 1．前序遍历
前序遍历（ DLR）是指在访问根结点、
遍历左子树与遍历右子树这三者中，首先
访问根结点，然后遍历左子树，最后遍历
右子树；并且，在遍历左、右子树时，仍
然先访问根结点，然后遍历左子树，最后
遍历右子树。
因此，前序遍历二叉树的过程是一个
递归的过程。
? 2．中序遍历
中序遍历（ LDR）是指在访问根结点、
遍历左子树与遍历右子树这三者中，首先
遍历左子树，然后访问根结点，最后遍历
右子树；并且，在遍历左、右子树时，仍
然先遍历左子树，然后访问根结点，最后
遍历右子树。
因此，中序遍历二叉树的过程也是一
个递归的过程。
? 3．后序遍历
后序遍历（ LRD）是指在访问根结点、
遍历左子树与遍历右子树这三者中，首先
遍历左子树，然后遍历右子树，最后访问
根结点；并且，在遍历左、右子树时，仍
然先遍历左子树，然后遍历右子树，最后
访问根结点。
因此，后序遍历二叉树的过程也是一
个递归的过程。
?2.7.5 穿线二叉树
? 1．穿线二叉树的概念
二叉树是一种非线性结构，对二叉树
的遍历，实际上是将二叉树这种非线性结
构按某种需要转化为线性序列，以便以后
在对二叉树进行某种处理时直接使用。
? 2．穿线二叉树的构造
对二叉树进行不同的遍历（前序遍历、
中序遍历、后序遍历）时，得到的遍历序
列也不同，因此，在二叉链表中链接遍历
序列的线索也是不同的。
图 2.52是中序线索二叉树的示意图，
图中的虚线表示线索。
? 3．穿线二叉树的遍历
二叉树经过一次遍历并生成遍历线索
以后，如果再次需要遍历，则只需要根据
遍历序列的线索进行即可。
?2.7.6 表达式的线性化
? 1．表达式树
在计算机中，可以用树结构来表示算
术表达式。
用树来表示算术表达式的原则如下：
① 表达式中的每一个运算符在树中对
应一个结点，称为运算符结点。
② 运算符的每一个运算对象在树中为
该运算符结点的子树（在树中的顺序为从
左到右）。
③ 运算对象中的单变量均为叶子结点。
根据以上原则，可以将表达式
a*(b+c/d)+e*h–g*f(s,t,x+y)
用如图 2.53所示的树来表示。
? 2．有序树的二叉树表示
如果对某个结点的所有子结点按从左
到右排上次序，则称该树为有序树。即：
在有序树中，某个结点的所有子结点从左
到右的次序是不能颠倒的。
将有序树转化成二叉树的原则如下：
① 有序树 T中的结点与二叉树 BT中的
结点一一对应。
② 有序树 T中某个结点 N的第一个子
结点（即最左边的子结点） N1，在二叉树
BT中为对应结点 N的左子结点。
③ 有序树 T中某个结点 N的第一个子
结点以后的其他子结点，在二叉树 BT中被
依次链接成一串起始于 N1的右子结点。
将图 2.53（ a）所示的有序树转化
成的二叉树如图 2.54所示。
? 3．表达式的线性化
表达式的线性化，是指将一般的表达
式化为波兰表示式（即后缀表示）。
利用树结构与二叉树结构对表达式线
性化的步骤如下：
① 将表达式用有序树表示，即构造表
达式树。
② 将表达式树化为二叉树。
③ 对相应的二叉树进行中序遍历，其
遍历序列即为表达式的波兰表示式。
2.8 图
图（ graph）是比线性表、树与二叉
树更为复杂的一种数据结构。
?2.8.1 图的基本概念
如果数据元素集合 D中的各数据元素
之间存在任意的前后件关系，则此数据结
构称为图。图通常用 G表示。
在图中，如果对于任意的两个结点 a
与 b，当结点 a是结点 b的前件，且结点 b也
是结点 a的前件时，则称该图为无向图。
如果对于任意的两个结点 a与 b，当结
点 a是结点 b的前件，结点 b不都是结点 a的
前件时，则称该图为有向图。
在有向图中，通常用带有箭头的边来
连接两个有关联的结点（由前件结点指向
后件结点）。
如图 2.55为两个有向图。
?2.8.2 图的存储结构
一般是根据对图的具体运算来选取合
适的存储结构。
? 1．关联矩阵
由上述关联矩阵可以明显地看出，无
向图的关联矩阵是对称矩阵，且对角线上
的元素均为 0。
这是因为，对于无向图来说，各结点
之间的前后件关系是对称的，且不考虑结
点自身之间的前后件关系。
有向图的关联矩阵不一定是对称的，
且其对角线上的元素也不一定是 0 。
关联矩阵也称为邻接矩阵。
? 2．求值矩阵
关联矩阵只表示了图的结构，即图中
各结点的后件关系。
但在许多实际问题中，还需要对两个
关联结点之间的值进行运算。
这就是说，除了要存储图中各结点值
以及各结点之间的关系外，还必须存储图
中每两个结点之间的求值函数。
为了完整地存储一个有值图，可以用
一维数组存储图中各结点的数据信息，用
关联矩阵存储图中任意两个结点之间的关
联信息，用求值矩阵存储图中任意两个结
点之间的求值函数。
例如，有 A,B,C,D,E,F,G，
H八个城市，它们的交通情况及运费如图
2.57所示。
? 3．邻接表
邻接表这种存储结构也称为“顺序 –
索引 –链接”存储结构。
假设图中共有 n个结点，其结点值分
别为 d1,d2,…, dn，并用自然数将它们
依次编号为 1,2,…, n。
首先，用一个顺序存储空间来存储图
中各结点的信息。
其次，对图中每一个结点 dk(k = 1，
2,…, n)构造一个单链表。
对于图 2.59所示的有值图，其邻
接表如图 2.60所示。
邻接表特别适合于表示结点数多但边
数较少的图。
? 4．邻接多重表
在邻接多重表中，每条边用一个存储
结点表示，每个存储结点由五个域组成，
如图 2.61所示。
?2.8.3 图的遍历
在实际应用中，往往需要从图的某一
结点出发访问到图中的所有结点。这一访
问过程称为图的遍历。
工程中常用的图遍历方法主要有纵向
优先搜索法和横向优先搜索法两种。
? 1．纵向优先搜索法
纵向优先搜索法遍历图的基本思想
如下。
从图中某一结点作为当前结点，然
后进行以下过程：
① 处理或输出当前结点，并记录当前
结点的查访标志。
② 若当前结点有后件结点，则取第一
个后件结点。若该后件结点未被查访过，
则以该后件结点为当前结点用纵向优先搜
索法进行查访。
? 2．横向优先搜索法
横向优先搜索法又称为广度优先搜索
法。其基本思想如下。
从图的某一个结点出发，首先依次访
问该结点的后件结点，然后再顺序访问这
些后件结点的所有未被访问过的后件结点。
依此类推，直到所有被访问结点的后件结
点均被访问过为止。
2.9 索引存储结构
?2.9.1 索引存储的概念
索引存储的结构有两部分组成，一是
存储各个子表，二是存储索引表。
为了实现索引存储，需要解决以下两
个问题：
① 对数据集合中的元素进行划分。
② 索引表的具体存储结构以及每个子
表的存储结构。
? 1．数据元素的划分
例 2.5 设有一个学生成绩表如表 2.2所
示。
? 2．索引存储的方式
索引存储包括索引表的存储以及各个子
表的存储。
2.9.2,顺序 -索引 -顺序”存储方式
在“顺序 -索引 -顺序”存储方式中，索
引表以及各子表均采用顺序分配的存储方法。
图 2.62是例 2.5中学生成绩表的“顺序 -
索引 -顺序”存储方式的物理状态。
?2.9.3,顺序 -索引 -链接”
存储方式
“顺序 -索引 -链接”存储方式是指用
顺序分配的方法存储索引表，而用链式分
配的方法存储各子表。
?2.9.4 多重索引存储结构
如果在索引存储结构中，其索引表本
身又是索引存储结构，则称为二重索引存
储结构。图 2.64（ a）为“顺序 -索引 -顺序 -
索引 -链接”方式的二重索引存储结构示意
图，图 2.64（ b）为“顺序 -索引 -链接 -索引
-链接”方式的二重索引存储结构示意图。
