李云清 杨庆红 揭安全第 1章 概论数据结构讨论的是数据的逻辑结构、存储方式以及相关操作的实现等问题，为学习后续专业课程打下基础。本章讲述数据结构的基本概念及相关术语，介绍数据结构、数据类型和抽象数据类型之间的联系，介绍了算法的特点及算法的时间与空间复杂性。
1.1数据结构
1.1.1数据结构随着计算机软、硬件的发展，计算机的应用范围在不断扩大，计算机所处理的数据的数量也在不断扩大，计算机所处理的数据已不再是单纯的数值数据，而更多的是非数值数据。
需要处理的数据并不是杂乱无章的，它们一定有内在的联系，只有弄清楚它们之间的本质的联系，
才能使用计算机对大量的数据进行有效的处理。
某电信公司的市话用户信息表格如下图所示：
序号 用户名 电话号码用户住址街道名 门牌号
00001 万方林 3800235 北京西路 1659
00002 吴金平 3800667 北京西路 2099
00003 王 冬 5700123 瑶湖大道 1987
00004 王 三 5700567 瑶湖大道 2008
00005 江 凡 8800129 学府大道 5035
这里序号、用户名、电话号码等项称为基本项，它是有独立意义的最小标识单位，而用户住址称为组合项，
组合项是由一个或多个基本项或组合项组成，是有独立意义的标识单位，每一行称为一个结点，每一个组合项称为一个字段。
使用计算机处理用户信息表中的数据时，必须弄清楚下面 3个问题：
1 数据的逻辑结构这些数据之间有什么样的内在联系？
除最前和最后两个结点之外,表中所有其它的结点都有且仅有一个和它相邻位于它之前的一个结点,也有且仅有一个和它相邻位于它之后的一个结点,这些就是用户信息表的逻辑结构 。
2 数据的存储结构将用户信息表中的所有结点存入计算机时,就必须考虑存储结构,使用 C语言进行设计时,常见的方式是用一个结构数组来存储整个用户信息表,每一个数组元素是一个结构,它对应于用户信息表中的一个结点 。 数据在计算机的存储方式称为存储结构 。
3 数据的运算集合数据处理必涉及到相关的运算，在上述用户信息表中，可以有删除一个用户、增加一个用户和查找某个用户等操作。应该明确指明这些操作的含义。比如删除操作，是删除序号为 5的用户还是删除用户名为王三的用户是应该明确定义的，如果需要可以定义两个不同的删除操作，为一批数据定义的所有运算（或称操作）构成一个运算（操作）集合。
对待处理的数据，只有分析清楚上面 3个方面的问题，才能进行有效的处理！
数据结构 就是指按一定的逻辑结构组成的一批数据,
使用某种存储结构将这批数据存储于计算机中,并在这些数据上定义了一个运算集合 。
1.1.2数据的逻辑结构数据的逻辑结构是数据和数据之间所存在的逻辑关系,它可以用一个二元组
B=（ K,R）
来表示，其中 K是数据、即结点的有限集合； R是集合 K上关系的有限集合，这里的关系是从集合 K到集合 K的关系，这里一般只涉及到一个关系的逻辑结构。
例如,有 5个人,分别记为 a,b,c,d,e,其中 a是 b的父亲,
b是 c的父亲,c是 d的父亲,d是 e的父亲,如果只讨论他们之间所存在的父子关系,则可以用下面的二元组形式化地予以表达 。
B=（ K,R）
其中,K={a,b,c,d,e}
R={r}
r={<a,b>,<b,c>,<c,d>,<d,e>}
逻辑结构的 图形表示 方式,对 K中的每个结点 ki用一个方框表示,而结点之间的关系用带箭头的线段表示,
这 5人之间的逻辑结构用图形的方式表达如下图 所示 。
若 ki∈ K,kj∈ R,<ki,kj > ∈ r，则称 ki是 kj的相对于关系 r的 前驱结点,kj是 ki的相对于关系 r的 后继结点,
因为一般只讨论具有一种关系的逻辑结构，即 R={r}，
所以简称 ki是 kj前驱,kj是 ki的后继。如果某个结点没有前驱结点，称之为 开始结点 ；如果某个结点没有后继结点，称之为 终端结点 ；既不是开始结点也不是终端结点的结点称为 内部结点 。
1.1.3数据的存储结构数据的逻辑结构是独立于计算机的,它与数据在计算机中的存储无关,要对数据进行处理,就必须将数据存储在计算机中 。 如果将数据在计算机中无规律地存储,那么在处理时是非常糟的,是没有用的 。 试想一下,如果一本英汉字典中的单词是随意编排的,
这本字典谁会用 ！
对于一个数据结构 B=（ K,R）,必须建立从结点集合到计算机某个存储区域 M的一个映象,这个映象要 直接或间接 地表达结点之间的关系 R。 数据在计算机中的存储方式称为数据的存储结构 。
数据的存储结构主要有 4种 。
数据的存储结构主要有 4种 。
1 顺序存储顺序存储通常用于存储具有线性结构的数据。将逻辑上相邻的结点存储在连续存储区域 M的相邻的存储单元中，使得逻辑相邻的结点一定是物理位置相邻。
对于一个数据结构 B=（ K,R）
其中 K={k1,k2,k3,k4,k5,k6,k7,k8,k9}
R={r}
r={<k1,k2>,<k2,k3>,<k3,k4>,<k4,k5>,<k5,k6>,<k6,k7>,<k7,
k8>,<k8,k9>}
它的顺序存储方式如图所示
2 链式存储链式存储方式是给每个结点附加一个指针段，一个结点的指针所指的是该结点的后继的存储地址，因为一个结点可能有多个后继，所以指针段可以是一个指针，也可以是一个多个指针。
例,数据的逻辑结构 B=（ K,R）
其中 K={k1,k2,k3,k4,k5}
R={r}
R={< k1,k2>,<k2,k3>,<k3,k4>,<k4,k5>}
这是一个线性结构，它的链式存储如图所示。
3 索引存储在线性结构中，设开始结点的索引号为 1，其它结点的索引号等于其前继结点的索引号加 1，则每一个结点都有唯一的索引号，索引号就是根据结点的索引号确定该结点的存储地址。
4 散列存储散列存储的思想是构造一个从集合 K到存储区域 M
的一个函数 h，该函数的定义域为 K，值域为 M,K中的每个结点 ki在计算机中的存储地址由 h(ki)确定。
1.1.4数据的运算集合对于一批数据，数据的运算是定义在数据的逻辑结构之上的，而运算的具体实现就依赖于数据的存储结构。
数据的运算集合要视情况而定,一般而言,数据的运算包括插入,删除,检索,输出,排序等 。
插入：在一个结构中增加一个新的结点 。
删除：在一个结构删除一个结点 。
检索：在一个结构中查找满足条件的结点 。
输出：将一个结构中所有结点的值打印,输出 。
排序：将一个结构中所有结点按某种顺序重新排列 。
在程序设计中，数据和运算是两个不可缺少的因素。所有的程序设计活动都是围绕着数据和其上的相关运算而进行的。从机器指令、汇编语言中的数据没有类型的概念，到现在的面向对象程序设计语言中抽象数据类型概念的出现，程序设计中的数据经历了一次次抽象，数据的抽象经历了三个发展阶段。
1.2数据类型和抽象数据类型
从无类型的二进制数到基本数据类型的产生
从基本数据类型到用户自定义类型的产生
从用户自定义类型到抽象数据类型的出现
1.2.1数据类型数据类型（或简称类型）反映了数据的取值范围以及对这类数据可以施加的运算。
1.2.2数据结构数据结构是计算机科学中广泛使用的一个术语,在计算机科学中具有非常重要的作用 。 数据结构包括三个方面的内容：一组数据中各数据之间的逻辑关系；这组数据在计算机中的存储方式；对这组数据所能施加的运算的集合 。 数据结构是数据存在的形式 。 所有的数据都是按照数据结构进行分类的 。 简单数据类型对应于简单的数据结构；构造数据类型对应于复杂的数据结构 。
1.2.3抽象数据类型抽象数据类型是与表示无关的数据类型，是一个数据模型及定义在该模型上的一组运算。对一个抽象数据类型进行定义时，必须给出它的名字及各运算的运算符名，即函数名，并且规定这些函数的参数性质。一旦定义了一个抽象数据类型及具体实现，程序设计中就可以像使用基本数据类型那样，十分方便地使用抽象数据类型。
1.2.4抽象数据类型的描述和实现抽象数据类型的描述包括给出抽象数据类型的名称、
数据的集合、数据之间的关系和操作的集合等方面的描述。抽象数据类型的设计者根据这些描述给出操作的具体实现，抽象数据类型的使用者依据这些描述使用抽象数据类型。
抽象数据类型描述的一般形式如下：
ADT 抽象数据类型名称 {
数据对象：
……
数据关系：
……
操作集合：
操作名 1：
……
……
操作名 n：
}ADT抽象数据类型名称
1.3 算法和算法分析
1.3.1算法为了求解某问题,必须给出一系列的运算规则,
这一系列的运算规则是有限的,表达了求解问题方法和步骤,这就是一个算法 。
一个算法可以用自然语言描述,也可以用高级程序设计语言描述,也可以用伪代码描述 。 本书采用 C语言对算法进行描述 。
算法具有五个基本特征：
① 有穷性,算法的执行必须在有限步内结束 。
② 确定性,算法的每一个步骤必须是确定的无二义性的 。
③ 输入,算法可以有 0个或多个输入 。
④ 输出,算法一定有输出结果
⑤可行性，算法中的运算都必须是可以实现的。
算法具有有穷性，程序不需要具备有穷性。一般的程序都会在有限时间内终止，但有的程序却可以不在有限时间内终止，如一个操作系统在正常情况下是永远都不会终止的。
1.3.2算法的时间和空间复杂性一个算法的优劣主要从算法的执行时间和所需要占用的存储空间两个方面衡量，算法执行时间的度量不是采用算法执行的绝对时间来计算的，因为一个算法在不同的机器上执行所花的时间不一样，在不同时刻也会由于计算机资源占用情况的不同，使得算法在同一台计算机上执行的时间也不一样，所以对于算法的时间复杂性，采用算法执行过程中其基本操作的执行次数，称为计算量来度量。
算法中基本操作的执行次数一般是与问题规模有关的，对于结点个数为 n的数据处理问题，用 T(n)
表示算法基本操作的执行次数。
在评价算法的时间复杂性时，不考虑两算法执行次数之间的细小区别，而只关心算法的本质差别。为此，引入一个所谓的 O() 记号，则
T1(n)=2n=O(n),T2(n)=n+1=O(n)。
一个函数 f(n)是 O(g(n))的，则一定存在正常数 c和
m，使对所有的 n>m，都满足 f(n)<c*g(n)。
下面的表格给出了一些具体函数的 O()的表示,如图所示 。 f(n) O(g(n)) 量级
35 O(1) 常数阶
2n+7 O(n) 线性阶
n2+10 O(n2) 平方阶
2n3+n O(n3) 立方阶算法的时间复杂性不仅和问题的规模大小有关，
还与问题数据的初始状态有关。
这样就有了算法在最好,最坏以及在平均状态下的时间复杂性的概念 。
① 算法在最好情况下的时间复杂性是指算法计算量的最小值 。
② 算法在最坏情况下的时间复杂性是指算法计算量的最大值 。
③ 算法的平均情况下的时间复杂性是指算法在所有可能的情况下的计算量经过加权计算出的平均值 。
本书在对算法进行分析时,会用到如下两个记号：
x?：表示不大于 x的最大整数；
x?：表示不小于 x的最小整数 。
第 2章 线性表及其顺序存储线性表是一种常用的数据结构，本章介绍线性表及其顺序存储，并对栈和队列及它们的顺序实现给出了详细的设计描述。
2.1线性表线性表是一个线性结构，它是一个含有 n≥0个结点的有限序列，对于其中的结点，有且仅有一个开始结点没有前驱但有一个后继结点，有且仅有一个终端结点没有后继但有一个前驱结点，其它的结点都有且仅有一个前驱和一个后继结点。一般地，一个线性表可以表示成一个线性序列,k1,k2,…,k n，其中 k1是开始结点,kn是终端结点。
2.2.1顺序表线性表采用顺序存储的方式存储就称之为顺序表。
顺序表是将表中的结点依次存放在计算机内存中一组地址连续的存储单元中。
如顺序表的每个结点占用 len个内存单元,用
location (ki)表示顺序表中第 i个结点 ki所占内存空间的第 1个单元的地址 。 则有如下的关系
location (ki+1) = location (ki) +len
location (ki) = location(k1) + (i-1)len
2.2顺序表顺序表的存储结构如下图所示：
存储结构要体现数据的逻辑结构，顺序表的存储结构中，内存中物理地址相邻的结点一定具有顺序表中的逻辑关系。
顺序表类型的描述如下：
ADT sequence_list{
数据集合 K,K={k1,k2,…,kn},n≥0,K中的元素是 datatype类型数据关系 R,R={r},r={ <ki,ki+1>| i=1,2,…,n-1}
操作集合：
(1) void init_sequence_list(sequence_list *slt) 顺序表的初始化 ------置空表
(2) void insert_sequence_list(sequence_list *slt,datatype x) 后部插入值为 x结点
(3) void print_sequence_list(sequence_list slt) 打印顺序表的各结点值
(4) int is_empty_sequence_list(sequence_list slt) 判断顺序表是否为空
(5) int find_num_sequence_list(sequence_list slt,datatype x) 查找值为 x结点位置
(6) int get_data_pos(sequence_list slt,int i) 取得顺序表中第 i个结点的值
(7) void insert_pos_sequence_list(sequence_list *slt,int position,datatype x)
(8) void delete_pos_sequence_list(sequence_list *slt,int position)
} ADT sequence_list；
2.2.2顺序表的实现用 C语言中的数组存储顺序表 。 C语言中数组的下标是从 0开始的,即数组中下标为 0的元素对应的是顺序表中的第 1个结点,数组中下标为 i的元素对应的是顺序表中的第 i+1个结点 。 为了方便,将顺序表中各结点的序号改为和对应数组元素的下标序号一致,即将顺序表中各结点的序号从 0开始编号 。 这样,一个长度为 n
的顺序表可以表示为
{k0,k1,k2,…,kn-1}
顺序表的存储结构的 C语言描述如下：
/********************************/
/*顺序表的头文件,文件名 sequlist.h*/
/********************************/
#define MAXSIZE 100
typedef int datatype;
typedef struct{
datatype a[MAXSIZE];
int size;
}sequence_list;
顺序表的几个基本操作的具体实现,
/********************************************/
/* 顺序表的初始化 ---置空表 */
/* 文件名 seqlinit.c,函数名 init_sequence_list() */
/*******************************************/
void init_sequence_list(sequence_list *slt)
{
slt->size=0;
}
算法 2.1顺序表的初始化 ---置空表
/**********************************************/
/* 在顺序表后部进行插入操作 */
/* 文件名 seqlinse.c,函数名 insert_sequence_list() */
/**********************************************/
void insert_sequence_list(sequence_list *slt,datatype x)
{
if(slt->size==MAXSIZE)
{printf("顺序表是满的 !");exit(1);}
slt->size=slt->size+1;
slt->a[slt->size]=x;
}
算法 2.2在顺序表后部进行插入操作
/**********************************************/
/* 打印顺序表的各结点值 */
/* 文件名 seqlprin.c,函数名 print_sequence_list() */
/*********************************************/
void print_sequence_list(sequence_list slt)
{
int i;
if(!slt.size) printf("\n顺序表是空的 !");
else
for(i=0;i<slt.size;i++) printf("%5d",slt.a[i]);
}
算法 2.3打印顺序表的各结点值
/**********************************************/
/* 判断顺序表是否为空 */
/* 文件名 seqlempt.c,函数名 is_empty_sequence_list() */
/**********************************************/
int is_empty_sequence_list(sequence_list slt)
{
return(slt.size==0? 0:1);
}
算法 2.4判断顺序表是否为空
/**********************************************/
/* 查找顺序表中值为 x的结点位置 */
/* 文件名 seqlfind.c,函数名 find_num_sequence_list() */
/**********************************************/
int find_num_sequence_list(sequence_list slt,datatype x)
{
int i=0;
while(slt.a[i]!=x&&i<slt.size) i++;
return(i<slt.size? i:-1);
}
算法 2.5查找顺序表中值为 x的结点位置
/*********************************************/
/* 取得顺序表中第 i个结点的值 */
/*文件名 seqlget.c,函数名 get_data_pos_sequence_list() */
/*********************************************/
int get_data_pos(sequence_list slt,int i)
{
if(i<0||i>=slt.size)
{printf("\n指定位置的结点不存在 !");exit(1);}
else
return slt.a[i];
}
算法 2.6取得顺序表中第 i个结点的值顺序表的插入运算是将一个值为 x的结点插入到顺序表的第 i个位置 0≤i≤n,即将 x插入到 ki-1和 ki之间,如果
i=n,则表示插入到表的最后,一般地可表示为：
插入前,{k0,k1,…,ki-1,ki,…,kn-1}
插入后,{k0,k1,…,k i-1,x,ki,…,k n-1}
插入过程的图示见下图：
/**********************************************/
/* 在顺序表的 position位置插入值为 x的结点 */
/* 文件名 seqlinse.c,函数名 insert_pos_sequence_list() */
/********************************************/
void insert_pos_sequence_list(sequence_list *slt,int
position,datatype x)
{ int i;
if(slt->size==MAXSIZE)
{printf("\n顺序表是满的 !没法插入 !");exit(1);}
if(position<0||position>slt->size)
{printf("\n指定的插入位置不存在 !");exit(1);}
for(i=slt->size;i>position;i--) slt->a[i]=slt->a[i-1];
slt->a[position]=x;
slt->size++;
}
算法 2.7在顺序表的 position位置插入值为 x的结点算法 2.7中,所花费的时间主要是元素后移操作,对于在第 i个位置上插入一个新的元素,需要移动 （ n-i）
个元素,设在第 i个位置上插入一个元素的概率为 pi,且在任意一个位置上插入元素的概率相等,即
p0=p1=p2=… =pn=1/n+1,则在一个长度为 n的顺序表中插入一个元素所需的平均移动次数为：
22
)1(
1
1)(
1
1)(
00
nnn
n
in
n
inp
n
i
n
i
i?
即在长度为 n的顺序表中插入一个元素平均需要移动表中的一半元素。该算法的时间复杂度为 O（ n）。
顺序表的删除操作是指删除顺序表中的第 i个结点,
0≤i≤n-1,一般地可表示为：
删除前,{k0,k1,…,ki-1,ki,ki+1,,…,kn-1}
删除后,{k0,k1,…,k i-1,ki+1,…,k n-1}
删除过程的图示见下图,
删除操作的具体实现见算法 2.8
/**********************************************/
/* 删除顺序表中第 position位置的结点 */
/* 文件名 seqldele.c,函数名 delete_pos_sequence_list() */
/**********************************************/
void delete_pos_sequence_list(sequence_list *slt,int position)
{
int i;
if(slt->size==0)
{printf("\n顺序表是空的 !");exit(1);}
if(position<0||position>=slt->size)
{printf("\n指定的删除位置不存在 !");exit(1);}
for(i=position;i<slt->size-1;i--) slt->a[i]=slt->a[i+1];
slt->size--;
}
算法 2.8删除顺序表中第 position位置的结点要删除顺序表中的第 i个结点,则需要称动 （ n-i-1）
个元素,设删除表中第 i个结点的概率为 qi,且在表中每一个位置删除的概率相等,即：
q0=q1=… =qn-1=1/n
则在一个长度为 n的顺序表中删除一个结点的平均移动次数为：
2
1
2
)1(1)1(1)1( 1
0
1
0
nnn
n
in
n
inq
n
i
n
i
i
这表明，在一个长为 n的顺序表中删除一个元素平均需要移动表中大约一半的元素。该算法的时间复杂度为 O（ n）。
2.3 栈2.3.1栈栈是一种特殊的线性表，对于这种线性表规定它的插入运算和删除运算均在线性表的同一端进行，进行插入和删除的那一端称为栈顶，另一端称为栈底。
栈的插入操作和删除操作也分别简称进栈和出栈。
如果栈中有 n个结点
{k0,k1,k2,…,k n-1}，
k0为栈底,kn-1是栈顶，
则栈中结点的进栈顺序为 k0,k1,k2,…,k n-1，
而出栈的顺序为 kn-1,
kn-2,…,k 1,k0。如图所示。
栈具有后进先出或先进后出
（ FILO,F
irst In
Last Out）
的性质栈类型的描述如下：
ADT sequence_stack {
数据集合 K,K={k1,k2,…,kn},n≥0,K中的元素是 datatype类型数据关系 R,R={r}
r={ <ki,ki+1>| i=1,2,…,n-1}
操作集合：
(1) void init_sequence_stack(sequence_stack *st) （ 顺序存储 ）
初始化
(2) int is_empty_stack(sequence_stack st) 判断栈 （ 顺序存储 ）
是否为空
(3) void print_sequence_stack(sequence_stack st) 打印栈 （ 顺序存储 ） 的结点值
(4) datatype get_top(sequence_stack st) 取得栈顶 （ 顺序存储 ） 结点值
(5) void push(sequence_stack *st,datatype x) 栈 （ 顺序存储 ）
的插入操作
(6) void pop(sequence_stack *st) 栈 （ 顺序存储 ） 的删除操作
} ADT sequence_stack
2.3.2顺序栈及其实现栈的实现方式一般有两种：顺序存储和链式存储。
本小节将给出栈的顺序存储实现。
栈的顺序存储方式就是在顺序表的基础上对插入和删除操作限制它们在顺序表的同一端进行，所以同顺序表一样也可用一维数组表示。
一般地，可以设定一个足够大的一维数组存储栈，
数组中下标为 0的元素就是栈底，对于栈顶，可以设一个指针 top指示它。
为了方便，设定 top所指的位置是下一个将要插入的结点的存储位置，这样，当 top=0时就表示是一个空的栈。一个栈的几种状态以及在这些状态下栈顶指针
top和栈中结点的关系如下图所示。
栈的顺序存储结构的 C语言描述如下：
/*****************************/
/* 栈 （ 顺序存储 ） 的头文件 */
/* 文件名 seqstack.h */
/*****************************/
#define MAXSIZE 100
typedef int datatype;
typedef struct{
datatype a[MAXSIZE];
int top;
}sequence_stack;
下面是顺序存储栈的几个基本操作的具体实现
/***********************************************************/
/* 栈 （ 顺序存储 ） 初始化 */
/* 文件名 seqsinit.c,函数名 init_sequence_stack() */
/***********************************************************/
void init_sequence_stack(sequence_stack *st)
{
st->top=0;
}
算法 2.9栈（顺序存储）初始化
/***************************************************/
/* 判断栈 （ 顺序存储 ） 是否为空 */
/* 文件名 seqsempt.c,函数名 is_empty_sequence_stack() */
/***************************************************/
int is_empty_stack(sequence_stack st)
{
return(st.top? 0:1);
}
算法 2.10判断栈（顺序存储）是否为空
/***************************************************/
/* 取得栈顶 （ 顺序存储 ） 结点值 */
/* 文件名 seqsfirs.c,函数名 get_top() */
/***************************************************/
datatype get_top(sequence_stack st)
{
if (empty_stack(st))
{printf("\n栈是空的 !");exit(1);}
else
return st.a[st.top-1];
}
算法 2.11取得栈顶（顺序存储）结点值
/***************************************************/
/* 栈 （ 顺序存储 ） 的插入操作 */
/* 文件名 seqspush.c,函数名 push() */
/***************************************************/
void push(sequence_stack *st,datatype x)
{
if(st->top==MAXSIZE)
{printf("\nThe sequence stack is full!");exit(1);}
st->a[st->top]=x;
st->top++;
}
算法 2.12 栈（顺序存储）的插入操作
/***************************************************/
/* 栈 （ 顺序存储 ） 的删除操作 */
/* 文件名 seqspop.c,函数名 pop() */
/***************************************************/
void pop(sequence_stack *st)
{
if(st->top==0)
{printf("\nThe sequence stack is empty!");exit(1);}
st->top--;
}
算法 2.13栈（顺序存储）的删除操作
2.3.3栈的应用之一 ------括号匹配设一个表达式中可以包含三种括号：小括号,中括号和大括号,各种括号之间允许任意嵌套,如小括号内可以嵌套中括号,大括号,但是不能交叉 。 举例如下：
([]{}) 正确的
([()]) 正确的
{([])} 正确的
{[(])} 不正确的
{(}[]) 不正确的如何去检验一个表达式的括号是否匹配呢？大家知道当自左向右扫描一个表达式时，凡是遇到的开括号
（或称左括号）都期待有一个和它对应的闭括号（或称右括号）与之匹配。
按照括号正确匹配的规则，在自左向右扫描一个表达式时，后遇到的开括号比先遇到的开括号更加期待有一个闭括号与之匹配。
可能会连续遇到多个开括号，且它们都期待寻求匹对的闭括号，所以必须将遇到的开括号存放好。又因为后遇到的开括号的期待程度高于其先前遇到的开括号的期待程度，所以应该将所遇到的开括号存放于一个栈中。这样，当遇到一个闭括号时，就查看这个栈的栈顶结点，如果它们匹配，则删除栈顶结点，如果不匹配，则说明表达式中括号是不匹配的，如果扫描它整个表达式后，这个栈是空的，则说明表达式中的括号是匹配的，否则表达式的括号是不匹配的。
判断表达式括号是否匹配的具体实现见算法 2.14。
/*******************************************/
/* 判断表达式括号是否匹配 */
/* 文件名 seqmatch.c,函数名 match_huohao() */
/*******************************************/
int match_kuohao(char c[])
{
int i=0;
sequence_stack s;
init_sequence_stack(&s);
while(c[i]!='#')
{
switch(c[i])
{
case '{':
case '[':
case '(':push(&s,c[i]);break;
case '}':if(!is_empty_sequence_stack(s)&&get_top(s)=='{'}
{pop(&s);break;} else return 0;
case ']':if(!is_empty_sequence_stack(s)&&get_top(s)=='[']
{pop(&s);break;} else return 0;
case ')':if(!is_empty_sequence_stack(s)&&get_top(s)=='(')
{pop(&s);break;} else return 0;
}
i++;
}
return (is_empty_sequence_stack(s));/*栈空则匹配,否则不匹配 */
}
算法 2.14判断表达式括号是否匹配
2.3.4栈的应用之二 ------算术表达式求值
2.4 队列
2.4.1 队列队列是一种特殊的线性表，它的特殊性在于队列的插入和删除操作分别在表的两端进行。插入的那一端称为队尾，删除的那一端称为队首。队列的插入操作和删除操作也分别简称进队和出队。
对于一个队列：
{k0,k1,k2,…,kn-1}
如果 k0那端是队首,kn-1那端是队尾，则 k0是这些结点中最先插入的结点，若要做删除操作,k0将首先被删除，所以说，队列是具有“先进先出”（ FIFO,First
In First Out）特点的线性结构。
队列类型的描述如下：
ADT sequence_queue {
数据集合 K,K={k1,k2,…,kn},n≥0,K中的元素是 datatype类型数据关系 R,R={r}
r={ <ki,ki+1>| i=1,2,…,n-1}
操作集合：
(1) void init_sequence_queue(sequence_queue *sq) 队列 （ 顺序存储 ） 初始化
(2) int is_empty_sequence_queue(sequence_queue sq) 判断队列 （ 顺序存储 ） 是否为空
(3) void print_sequence_queue(sequence_queue sq) 打印队列
（ 顺序存储 ） 的结点值
(4) datatype get_first(sequence_queue sq) 取得队列 （ 顺序存储 ） 的队首结点值
(5) void insert_sequence_queue (sequence_queue
*sq,datatype x) 队列 （ 顺序存储 ） 插入操作
(6) void delete_sequence_queue(sequence_queue *sq) 队列
（ 顺序存储 ） 的删除操作
} ADT sequence_queue;
2.4.2顺序队列及其实现队列的顺序存储在 C语言中可以用一维数组表示，
为了标识队首和队尾，需要附设两个指针 front和 rear，
front指示的是队列中最前面，即队首结点在数组中元素的下标,rear指示的是队尾结点在数组中元素的下标的下一个位置，也就是说 rear指示的是即将插入的结点在数组中的下标。
队列的几种状态,
下标下标下标下标下标队列的顺序存储结构的 C语言描述如下：
/*****************************/
/* 队列 （ 顺序存储 ） 的头文件 */
/* 文件名 seqqueue.h */
/*****************************/
#define MAXSIZE 100
typedef int datatype;
typedef struct{
datatype a[MAXSIZE];
int front;
int rear;
}sequence_queue;
顺序存储队列的几个基本操作的具体实现,
/************************************************/
/* 队列 （ 顺序存储 ） 初始化 */
/* 文件名 seqqinit.c,函数名 init_sequence_queue() */
/************************************************/
void init_sequence_queue(sequence_queue *sq)
{
sq->front=sq->rear=0;
}
算法 2.20队列（顺序存储）初始化
/***************************************************/
/* 判断队列 （ 顺序存储 ） 是否为空 */
/*文件名 seqqempt.c,函数名 is_empty_sequence_queue() */
/***************************************************/
int is_empty_sequence_queue(sequence_queue sq)
{
return (sq.front==sq.rear? 1:0);
}
算法 2.21判断队列（顺序存储）是否为空
/***************************************************/
/* 打印队列 （ 顺序存储 ） 的结点值 */
/* 文件名 seqqprin.c,函数名 print_sequence_queue() */
/***************************************************/
void print_sequence_queue(sequence_queue sq)
{
int i;
if(is_empty_sequence_queue(sq))
{
printf("\n顺序队列是空的 !");
}
else
for(i=sq.front;i<sq.rear;i++) printf("%5d",sq.a[i]);
}
算法 2.22打印队列（顺序存储）的结点值
/*********************************************/
/* 队列 （ 顺序存储 ） 的插入操作 */
/* 文件名 seqqinse.c,函数名 insert_sequence_queue() */
/********************************************/
void insert_sequence_queue(sequence_queue *sq,datatype x)
{
int i;
if(sq->rear==MAXSIZE)
{printf("\n顺序循环队列是满的 !");exit(1);}
sq->a[sq->rear]=x;
sq->rear=sq->rear+1;
}
算法 2.24队列（顺序存储）的插入操作
/***************************************************/
/* 队列 （ 顺序存储 ） 的删除操作 */
/* 文件名 seqqdele.c,函数名 delete_sequence_queue() */
/***************************************************/
void delete_sequence_queue(sequence_queue *sq)
{
if(sq->front==sq->rear)
{
printf("\n顺序队列是空的 ！ 不能做删除操作 ！ "); exit(1);
}
sq->front++;
}
算法 2.25队列（顺序存储）的删除操作在队列的几种状态图的（ e）状态中，队列是一种队满状态，将不能再插入新的结点，而实际上数组的前部还有许多空的位置。为了充分地利用空间，可以将队列看作一个循环队列，在数组的前部继续作插入运算，这就是循环队列。
下标下标
2.4.3顺序循环队列及其实现给定一个大小为 MAXSIZE的数组存储一个队列时，经过若干次插入和删除操作后，当队尾指指
rear=MAXSIZE时，呈现队列满的状态，而事实上数组的前部可能还有空闲的位置。为了有效利用空间，
将顺序存储的队列想象为一个环状，把数组中的最前和最后两个元素看作是相邻的，这就是循环队列。
循环队列的几种状态表示,
在（ b）状态中，如果再插入一个新的结点，则数组空间将被全部占用，队列已满，且 rear=front，而在
（ c）状态中，若删除一个结点队列成为空队列，此时也有 rear=front，这就是说循环队列满与空的条件都是
rear=front。
解决方法是牺牲一个数组元素的空间,即若数组的大小是 MAXSIZE,则该数组所表示的循环队列最多允许存储 MAXSIZE-1个结点 。 这样,循环队列满的条件是
(rear+1)%MAXSIZE=front
循环队列空的条件是 rear=front
循环队列的插入与删除操作的实现,
/***************************************************/
/* 循环队列 （ 顺序存储 ） 的插入操作 */
/* 文件名 secqinst.c,函数名 insert_sequence_cqueue() */
/***************************************************/
void insert_sequence_cqueue(sequence_queue *sq,datatype x)
{
int i;
if((sq->rear+1)%MAXSIZE==sq->front)
{printf("\n顺序循环队列是满的 ！ 无法进行插入操作 ！ ");exit(1);}
sq->a[sq->rear]=x;
sq->rear=(sq->rear+1)%MAXSIZE;
}
算法 2.27循环队列（顺序存储）的插入操作
/***************************************************/
/* 循环队列 （ 顺序存储 ） 的删除操作 */
/* 文件名 secqdele.c,函数名 delete_sequence_cqueue() */
/***************************************************/
void delete_sequence_cqueue(sequence_queue *sq)
{
if(sq->front==sq->rear)
{
printf(“\n循环队列是空的 ！ 无法进行删除 ！ "); exit(1);
}
sq->front=(sq->front+1)%MAXSIZE;
}
算法 2.28循环队列（顺序存储）的删除操作第 3章 线性表的链式存储线性表的存储方式除了常用的顺序存储外，采用链式方式存储也是一种常见的方式。本章将介绍一般线性表的几种链式存储实现方式，如单链表、带头结点单链表、循环单链表、双链表以及特殊的线性表 -----
-栈和队列的链式存储实现。
3.1链式存储数据结构的存储方式必须体现它的逻辑关系 。
在链式存储方式下，实现中除存放一个结点的信息外，
还需附设指针，用指针体现结点之间的逻辑关系。如果一个结点有多个后继或多个前驱，那么可以附设相应个数的指针，一个结点附设的指针指向的是这个结点的某个前驱或后继。
线性结构中，每个结点最多只有一个前驱和一个后继，这里暂且设定更关心它的后继，这样在存储时除了存放该结点的信息外，只要附设一个指针即可，该指针指向它的后继结点的存放位置。每个结点的存储形式是,info next
例,数据的逻辑结构 B=（ K,R）
其中 K={k1,k2,k3,k4,k5}
R={r}
R={< k1,k2>,<k2,k3>,<k3,k4>,<k4,k5>}
是一个线性结构，它的链式存储如图所示为了清晰,左图可以更简洁地用下图表示 。
3.2 单链表单链表是线性表链式存储的一种形式，其中的结点一般含有两个域，一个是存放数据信息的 info域，另一个是指向该结点的后继结点的存放地址的指针域 next。
一个单链表必须有一个首指针指向单链表中的第一个结点。图 3.3给出了空的单链表和非空的单链表的图示。
单链表类型的描述如下：ADT link_list{
数据集合 K,K={k1,k2,…,kn},n≥0,K中的元素是 datatype类型数据关系 R,R={r}
r={ <ki,ki+1>| i=1,2,…,n-1}
操作集合：
(1) node *init_link_list() 建立一个空的单链表
(2) void print_link_list(node *head) 输出单链表中各个结点的值
(3) node *insert_in_front_link_list(node *head,datatype x)
插入一个值为 x的结点作为单链表的第一个结点
(4) node *find_num_link_list(node *head,datatype x) 在单链表中查找一个值为 x的结点
(5) node *find_pos_link_list(node *head,int i) 在单链表中查找第 i
个结点
(6) node *insert_x_after_y(node *head,datatype x,datatype y)
在单链表中值为 y的结点后插入一个值为 x的新结点
(7) node *insert_x_after_i(node *head,datatype x,int i)
在单链表中第 i个结点后插入一个值为 x的新结点
(8) node *delete_num_link_list(node *head,datatype x) 在单链表中删除一个值为 x的结点
(9) node *delete_pos_link_list(node *head,int i) 在单链表中删除第 i个结点
} ADT link_list;
3.2.2单链表的实现单链表结构的 C语言描述如下：
/**********************************/
/*链表实现的头文件,文件名 slnklist.h */
/**********************************/
typedef int datatype;
typedef struct link_node{
datatype info;
struct link_node *next;
}node;
单链表几个基本操作的具体实现：
/*****************************************************/
/* 建立一个空的单链表 */
/* 文件名 slnkinit.c,函数名 init_link_list() */
/*****************************************************/
node *init_link_list() /*建立一个空的单链表 */
{
return NULL;
}
算法 3.1建立一个空的单链表
/*****************************************************/
/* 输出单链表中各个结点的值 */
/* 文件名 slnkprin.c,函数名 print_link_list() */
/*****************************************************/
void print_link_list(node *head)
{ node *p;
p=head;
if(!p) printf("\n单链表是空的 ！ ");
else
{ printf("\n单链表各个结点的值为,\n");
while(p) { printf("%5d",p->info);p=p->next;}
}
}
算法 3.2输出单链表中各个结点的值
/*****************************************************/
/* 在单链表中查找一个值为 x的结点 */
/* 文件名 slnkfinx.c,函数名 find_num_link_list() */
/*****************************************************/
node *find_num_link_list(node *head,datatype x)
{
node *p;
p=head;
while(p&&p->info!=x) p=p->next;
return p;
}
算法 3.3在单链表中查找一个值为 x的结点
/*****************************************************/
/* 在单链表中查找第 i个结点 */
/* 文件名 slnkfini.c,函数名 find_pos_link_list() */
/*****************************************************/
node *find_pos_link_list(node *head,int i)
{
int j=1;
node *p=head;
if(i<1){printf("\nError!\n");exit(1);}
while(p&&i!=j) { p=p->next ; j++; }
return p;
}
算法 3.4在单链表中查找第 i个结点单链表的插入过程见下图所示,
/*****************************************************/
/* 插入一个值为 x的结点作为单链表的第一个结点 */
/* 文件名 slnkinfx.c,函数名 insert_in_front_link_list() */
/*****************************************************/
node *insert_in_front_link_list(node *head,datatype x)
{
node *p;
p=(node*)malloc(sizeof(node)); /*分配空间 */
p->info=x; /*设置新结点的值 */
p->next=head; /*插入 (1)*/
head=p; /*插入 (2)*/
return head;
}
算法 3.5插入一个值为 x的结点作为单链表的第一个结点
/*****************************************************/
/* 在单链表中第 i个结点后插入一个值为 x的新结点 */
/* 文件名 slnkinix.c,函数名 insert_x_after_i() */
/****************************************************/
node *insert_x_after_i(node *head,datatype x,int i)
{
node *p,*q;
q=find_pos_link_list(head,i);/*查找第 i个结点 */
if(!q)
{printf("\n找不到第 %d个结点,不能进行插入 ！ ",i,x);exit(1);}
p=(node*)malloc(sizeof(node));/*分配空间 */
p->info=x;/*设置新结点 */
p->next=q->next;/*插入 (1)*/
q->next=p;/*插入 (2)*/
return head;
}
算法 3.7在单链表中第 i个结点后插入一个值为 x的新结点删除操作见下图所示：
node *delete_num_link_list(node *head,datatype x)
{
node *pre=NULL,*p;
if(!head) {printf("单链表是空的 ！ ");return head;}
p=head;
while(p&&p->info!=x)/*没有找到并且没有找完 */
{pre=p;p=p->next;}/*pre指向 p的前驱结点 */
if(!pre&&p->info==x)/*要删除的是第一个结点 */
head=head->next;/*删除 (1)*/
else
pre->next=p->next;
free(p);
return head;
}
算法 3.8在单链表中删除一个值为 x的结点链式存储的插入和删除操作比顺序存储方便，但不能随机访问某个结点！
3.3带头结点单链表
3.3.1带头结点单链表带头结点单链表见下图所示：
带头结点单链表类型的描述如下：ADT hlink_list{
数据集合 K,K={k1,k2,…,kn},n≥0,K中的元素是 datatype类型数据关系 R,R={r}
r={ <ki,ki+1>| i=1,2,…,n-1}
操作集合：
(1) node *init_hlink_list() 建立一个空的带头结点的单链表
(2) void print_hlink_list(node *head) 输出带头结点单链表中各个结点的值
(3) node *find_num_hlink_list(node *head,datatype x)
在带头结点单链表中查找一个值为 x的结点
(4) node *find_pos_hlink_list(node *head,int i) 在带头结点单链表中查找第 i个结点
(5) node *insert_in_front_hlink_list(node *head,datatype x)
插入一个值为 x的结点作为带头结点单链表的第一个结点
(6) node *insert_x_after_y(node *head,datatype x,datatype y)
在带头结点单链表中值为 y的结点后插入一个值为 x的新结点
7 sert_x_after_i(node *head,datatype x,int i)
在带头结点单链表中第 i个结点后插入一个值为 x的新结点
(8) node *delete_num_hlink_list(node *head,datatype x)
在带头结点单链表中删除一个值为 x的结点
(9) node *delete_pos_hlink_list(node *head,int i)
在带头结点单链表中删除第 i个结点
} ADT hlink_list;
3.3.2带头结点单链表的实现一般的单链表中，第一个结点由 head指示，而在带头结点单链表中,head指示的是所谓的头结点，它不是存储数据结构中的实际结点，第一个实际的结点是
head->next指示的。在带头结点单链表的操作实现时要注意这一点。
node *init_hlink_list()
{
node *head;
head=(node*)malloc(sizeof(node));
head->next=NULL;
return head;
}
算法 3.10建立一个空的带头结点单链表
void print_hlink_list(node *head)
{
node *p;
p=head->next;/*从第一个 （ 实际 ） 结点开始 */
if(!p) printf("\n带头结点单链表是空的 !");
else
{
printf("\n带头结点的单链表各个结点的值为,\n");
while(p) { printf("%5d",p->info);p=p->next;}
}
}
算法 3.11输出带头结点单链表中各个结点的值
/*****************************************************/
/* 在带头结点单链表中查找一个值为 x的结点 */
/* 文件名 hlnkfinx.c,函数名 find_num_hlink_list() */
/*****************************************************/
node *find_num_hlink_list(node *head,datatype x)
{
node *p;
p=head->next;/*从第一个 （ 实际 ） 结点开始 */
while(p&&p->info!=x) p=p->next;
return p;
}
算法 3.12在带头结点单链表中查找一个值为 x的结点
node *find_pos_hlink_list(node *head,int i)
{
int j=0;
node *p=head;
if(i<0){printf("\n带头结点的单链表中不存在第 %d个结点 ！
",i);return NULL;}
while(p&&i!=j)/*没有查找完并且还没有找到 */
{
p=p->next;j++;/*继续向后 （ 左 ） 查找,计数器加 1*/
}
return p;/*返回结果,i=0时,p指示的是头结点 */
}
算法 3.13在带头结点单链表中查找第 i个结点带头结点单链表的插入过程见图 3.7,
带头结点单链表的几个插入操作的具体实现见算法
3.14~算法 3.16。
node *insert_x_after_y(node *head,datatype x,datatype y)
{
node *p,*q;
q=find_num_hlink_list(head,y);/*查找值为 y的结点 */
if(!q)/*没有找到 */
{printf("\n没有找到值为 %d的结点,不能插入 %d!",y,x);return head;}
p=(node*)malloc(sizeof(node));/*为准备插入的新结点分配空间 */
p->info=x;/*为新结点设置值 x*/
p->next=q->next;/*插入 (1)*/
q->next=p;/*插入 (2)*/
return head;
}
算法 3.15在带头结点单链表中值为 y的结点后插入一个值为 x的新结点带头结点单链表的删除过程见图 3.8。
node *delete_num_hlink_list(node *head,datatype x)
{
node *pre=head,*q;/*首先 pre指向头结点 */
q=head->next;/*q从带头结点的第一个实际结点开始找值为 x
的结点 */
while(q&&q->info!=x)/*没有查找完并且还没有找到 */
{pre=q;q=q->next;}/*继续查找,pre指向 q的前驱 */
pre->next=q->next;/*删除 */
free(q);/*释放空间 */
return head;
}
算法 3.17在带头结点单链表中删除一个值为 x的结点
3.4 循环单链表
3.4.1 循环单链表无论是单链表，还是带头结点单链表，从表中的某个结点开始，只能访问到这个结点及其后面的结点，
不能访问到它前面的结点，除非再从首指针指示的结点开始访问。如果希望从表中的任意一个结点开始，
都能访问到表中的所有其它结点，可以设置表中最后一个结点的指针域指向表中的第一个结点，这种链表称为循环单链表。
循环单链表类型的描述 （略）
3.4.2循环单链表的实现单链表中某个结点 p是表中最后一个结点的特征是
p->next==NULL。 对于一个循环单链表,若首指针为
head,表中的某个结点 p是最后一个结点的特征应该是 p->next==head。
循环单链表的头文件和单链表的相同。
/*****************************************************/
/* 建立一个空的循环单链表 */
/* 文件名 clnkinit.c,函数名 init_clink_list() */
/*****************************************************/
node *init_clink_list() /*建立一个空的循环单链表 */
{
return NULL;
}
算法 3.19建立一个空的循环单链表
void print_clink_list(node *head)
{ node *p;
if(!head) printf("\n循环单链表是空的 ！ \n");
else
{printf("\n循环单链表各个结点的值分别为,\n");
printf("%5d",head->info);/*输出非空表中第一个结点的值 */
p=head->next;/*p指向第一个结点的下一个结点 */
while(p!=head)/*没有回到第一个结点 */
{printf("%5d",p->info);
p=p->next;
}
}
}
算法 3.21输出循环单链表中各个结点的值循环单链表的插入过程如图,
node *insert_x_after_i(node *head,datatype x,int i)
{ node *p,*q;
q=find_pos_clink_list(head,i);/*查找第 i个结点,q指向第 i个结点 */
if(!q)/*没有找到,则不进行插入 */
printf("\n表中不存在第 %d个结点,无法进行插入 !\n",i);
else
{ /*找到了第 i个结点,准备插入 x*/
p=(node*)malloc(sizeof(node));/*分配空间 */
p->info=x;/*设置新结点的值 */
p->next=q->next;/*插入,修改指针 (1)*/
q->next=p;/*插入,修改指针 (2)*/
}
return head;
}
算法 3.26在循环单链表中第 i个结点后插入一个值为 x的新结点循环单链表的删除过程如图,
node *delete_num_clink_list(node *head,datatype x)
{ node *pre=NULL,*q;/*q用于查找值为 x的结点,pre指向 q的前驱结点 */
if(!head)/*表为空,则无法做删除操作 */
{ printf(“\n循环单链表为空,无法做删除操作 ！,); return NULL; }
q=head;/*从第 1个结点开始准备查找 */
while(q->next!=head&&q->info!=x)/*没有找遍整个表并且没有找到 */
{ pre=q; q=q->next;/*pre为 q的前驱,继续查找 */
}/*循环结束后,pre为 q的前驱 */
if(q->info!=x)/*没找到 */ { printf("没有找到值为 %d的结点 ！ ",x); }
else /*找到了,下面要删除 q*/
{ pre->next=q->next;/*删除 q指向的结点 */ free(q);/*释放空间 */ }
return head;
}
算法 3.27在循环单链表中删除一个值为 x的结点
3.5 双链表
3.5.1 双链表前面的各种链式表中，一个结点的指针域是指向它的后继结点的，如果需要找一个结点 p的前驱结点，
则必须从表首指针开始查找，当某个结点 pre的指针域指向的是结点 p时，即 pre->next==p时，则说明 pre是
p的前驱结点。如果常常需要知道一个结点的前驱和后继结点，上述的链式表是不适合的。既然单链表中每个结点有一个指针域指向它的后继结点，那自然地想到再增设一个指针域指向它的前驱结点，这就构成了双链表。
双链表的结点包括三个域，一个是存放数据信息的 info域，另外两个是指针域，这里用 llink和 rlink表示，
llink指向它的前驱结点,rlink指向它的后继结点。
双链表的一般情形如图所示：
双链表类型的描述（略！）
3.5.2 双链表的实现双链表结构的 C语言描述如下：
/**********************************/
/* 双链表的头文件,文件名 dlnklist.h /
/**********************************/
typedef int datatype;
typedef struct dlink_node{
datatype info;
struct dlink_node *llink,*rlink;
}dnode;
void print_dlink_list(dnode *head)
{
dnode *p;
printf("\n"); p=head;
if(!p) printf("\n双链表是空的 !\n");
else
{
printf("\n双链表中各个结点的值为,\n");
while(p) { printf("%5d",p->info);p=p->rlink;}
}
}
算法 3.30 输出双链表中各个结点的值
dnode *find_pos_dlink_list(dnode *head,int i)
{
int j=1;
dnode *p=head;
if(i<1){printf("\n第 %d个结点不存在 !\n",i);return NULL;}
while(p&&i!=j)/*没有找完整个表并且没有找到 */
{ p=p->rlink;j++;/*继续沿着右指针向后查找,计数器加 1*/ }
if(!p){printf("\n第 %d个结点不存在 !\n",i);return NULL;}
return p;
}
算法 3.32查找双链表中第 i个结点双链表插入过程如下图所示：
/* 在双链表中第 i个结点后插入一个值为 x的新结点 */
dnode *insert_x_after_i(dnode *head,datatype x,int i)
{
dnode *p,*q;
p=(dnode*)malloc(sizeof(dnode));/*分配空间 */
p->info=x;/*设置新结点的值 */
if(i==0)/*在最前面插入一个值为 x的新结点 */
{ p->llink=NULL;/*新插入的结点没有前驱 */
p->rlink=head;/*新插入的结点的后继是原来双链表中的第一个结点 */
head=p;/*新结点成为双链表的第一个结点 */
return head;
}
q=find_pos_dlink_list(head,i);/*查找第 i个结点 */
if(!q)/*第 i个结点不存在 */
{printf("第 %d个结点不存在,无法进行插入 ",i);return head;}
if(q->rlink==NULL)/*在最后一个结点后插入 */
{
p->rlink=q->rlink;/*即为 NULL,新插入的结点没有后继 。 插入操作 (1)*/
p->llink=q;/*插入操作 (2)*/
q->rlink=p;/*插入操作 (4)*/
}/*注意不能和下面的一般情况一样处理，这里如执行下面的
(3)将出错！ */
else/*一般情况下的插入 */
{
p->rlink=q->rlink;/*插入操作 (1)*/
p->llink=q;/*插入操作 (2)*/
q->rlink->llink=p;/*插入操作 (3)*/
q->rlink=p;/*插入操作 (4)*/
}
return head;
}
算法 3.35 在双链表中第 i个结点后插入一个值为 x的新结点双链表删除操作图示,
/* 在双链表中删除一个值为 x的结点 */
dnode *delete_num_dlink_list(dnode *head,datatype x)
{ dnode *q;
if(!head)/*双链表为空,无法进行删除操作 */
{printf("双链表为空,无法进行删除操作 ");return head;}
q=head;
while(q&&q->info!=x) q=q->rlink;/*循环结束后 q指向的是值为 x
的结点 */
if(!q)
{
printf("\n没有找到值为 %d的结点 ！ 不做删除操作 ！ ",x);
}
if(q==head&&head->rlink)/*被删除的结点是第一个结点并且表中不只一个结点 */
{
head=head->rlink;
head->llink=NULL;
free(q);return head;
}
if(q==head&&!head->rlink)/*被删除的结点是第一个结点并且表中只有这一个结点 */
{
free(q);
return NULL;/*双链表置空 */
}
else
{ if(!q->rlink)/*被删除的结点是双链表中的最后一个结点 */
{ q->llink->rlink=NULL; free(q); return head; }
else/*q是在一个有 2个以上结点的双链表中的一个非开始,也非终端结点 */
{
q->llink->rlink=q->rlink;
q->rlink->llink=q->llink;
free(q); return head;
}
}
}
算法 3.36在双链表中删除一个值为 x的结点
3.6 链式栈
3.6.1 链式栈栈的链式存储称为链式栈。链式栈就是一个特殊的单链表，对于这特殊的单链表，它的插入和删除规定在单链表的同一端进行。链式栈的栈顶指针一般用
top表示，链式栈如下图所示。
链式栈类型的描述如下：
ADT link_stack{
数据集合 K,K={k1,k2,…,kn},n≥0,K中的元素是 datatype类型数据关系 R,R={r}
r={ <ki,ki+1>| i=1,2,…,n-1}
操作集合：
(1) node *init_link_stack() 建立一个空链式栈
(2) int empty_link_stack(node *top) 判断链式栈是否为空
(3) datatype get_top(node *top) 取得链式栈的栈顶结点值
(4) void print_link_stack(node *top) 输出链式栈中各个结点的值
(5) node *push_link_stack(node *top,datatype x) 向链式栈中插入一个值为 x
的结点
node *pop_link_stack(node *top)
/*删除链式栈的栈顶结点 */
} ADT link_stack;
3.6.2 链式栈的实现
datatype get_top(node *top)
{
if(!top) {printf("\n链式栈是空的 !");exit(1);}
return(top->info);
}
int empty_link_stack(node *top)
{
return (top? 0:1);
}
算法 3.40取得链式栈的栈顶结点值
/* 输出链式栈中各个结点的值 */
/* 文件名 lnksprin.c,函数名 print_link_stack() */
/*****************************************************/
void print_link_stack(node *top)
{
node *p;
p=top;
printf("\n");
if(!p) printf("\n链式栈是空的 !");
while(p) { printf("%5d",p->info);p=p->next;}
}
算法 3.41 输出链式栈中各个结点的值
/* 向链式栈中插入一个值为 x的结点 */
/* 文件名 lnkspush.c,函数名 push_link_stack() */
node *push_link_stack(node *top,datatype x)
{
node *p;
p=(node*)malloc(sizeof(node)); /*分配空间 */
p->info=x; /*设置新结点的值 */
p->next=top; /*插入 (1)*/
top=p; /*插入 (2)*/
return top;
}
算法 3.42向链式栈中插入一个值为 x的结点
/* 删除链式栈的栈顶结点 */
/* 文件名 lnkspop.c,函数名 pop_link_stack() */
node *pop_link_stack(node *top)
{
node *q;
if(!top) {printf("\n链式栈是空的 !");return NULL;}
q=top;/*指向被删除的结点 (1)*/
top=top->next;/*删除栈顶结点 (2)*/
free(q);
return top;
}
算法 3.43 删除链式栈的栈顶结点
3.7 链式队列
3.7.1 链式队列队列的链式存储称为链式队列。链式队列就是一个特殊的单链表，对于这种特殊的单链表，它的插入和删除规定在单链表的不同端进行。链式队列的队首和队尾指针分别用 front和 rear表示，链式队列如下图所示。
链式队列类型的描述如下：
ADT link_queue{
数据集合 K,K={k1,k2,…,kn},n≥0,K中的元素是 datatype类型数据关系 R,R={r}
r={ <ki,ki+1>| i=1,2,…,n-1}
操作集合：
(1) queue *init_link_queue() 建立一个空的链式队列
(2) int empty_link_queue(queue qu)判断链式队列是否为空
(3) void print_link_queue(queue *qu) 输出链式队列中各个结点的值
(4) datatype get_first(queue qu)取得链式队列的队首结点值
(5) queue *insert_link_queue(queue *qu,datatype x) 向链式队列中插入一个值为 x的结点
(6) queue *delete_link_queue(queue *qu) 删除链式队列中队首结点
} ADT link_queue;
3.7.2链式队列的实现：
链式队列的结点定义和单链表一样 。 队列必须有队首和队尾指针,因此增加定义一个结构类型,其中的两个域分别为队首和队尾指针 。 其定义如下：
typedef struct{
node *front,*rear; /*定义队首与队尾指针 */
}queue;
/* 建立一个空的链式队列 */
/* 文件名 lnkqinit.c,函数名 init_link_queue() */
/*****************************************************/
queue *init_link_queue() /*建立一个空的链式队列 */
{
queue *qu;
qu=(queue*)malloc(sizeof(queue)); /*分配空间 */
qu->front=NULL; /*队首指针设置为空 */
qu->rear=NULL; /*队尾指针设置为空 */
return qu;
}
算法 3.44建立一个空的链式队列
/*****************************************************/
/* 取得链式队列的队首结点值 */
/* 文件名 lnkqget.c,函数名 get_first() */
/*****************************************************/
datatype get_first(queue qu)
{
if(!qu.front) {printf("\n链式队列是空的 !");exit(1);}
return(qu.front->info);
}
算法 3.47取得链式队列的队首结点值链式队列的插入过程图示见下图：
/* 向链式队列中插入一个值为 x的结点 */
queue *insert_link_queue(queue *qu,datatype x)
{ node *p;
p=(node*)malloc(sizeof(node)); /*分配空间 */
p->info=x; /*设置新结点的值 */ p->next=NULL;
if (qu->front==NULL) qu->front=qu->rear=p;
else
{ qu->rear->next=p; /*队尾插入 */ qu->rear=p;
}
return qu;
}
算法 3.48向链式队列中插入一个值为 x的结点链式队列的删除过程图示见下图：
/* 删除链式队列中队首结点 */
queue *delete_link_queue(queue *qu)/*删除队首结点 */
{ node *q;
if(!qu->front) {printf("队列为空,无法删除 ！ ");return qu;}
q=qu->front; /*q指向队首结点 (1)*/
qu->front=q->next; /*队首指针指向下一个结点 (2)*/
free(q); /*释放原队首结点空间 */
if (qu->front==NULL) qu->rear=NULL; /*队列中的唯一结点被删除后,队列变空 (3)*/
return qu;
}
算法 3.49删除链式队列中队首结点
1.1数据结构
1.1.1数据结构随着计算机软、硬件的发展，计算机的应用范围在不断扩大，计算机所处理的数据的数量也在不断扩大，计算机所处理的数据已不再是单纯的数值数据，而更多的是非数值数据。
需要处理的数据并不是杂乱无章的，它们一定有内在的联系，只有弄清楚它们之间的本质的联系，
才能使用计算机对大量的数据进行有效的处理。
某电信公司的市话用户信息表格如下图所示：
序号 用户名 电话号码用户住址街道名 门牌号
00001 万方林 3800235 北京西路 1659
00002 吴金平 3800667 北京西路 2099
00003 王 冬 5700123 瑶湖大道 1987
00004 王 三 5700567 瑶湖大道 2008
00005 江 凡 8800129 学府大道 5035
这里序号、用户名、电话号码等项称为基本项，它是有独立意义的最小标识单位，而用户住址称为组合项，
组合项是由一个或多个基本项或组合项组成，是有独立意义的标识单位，每一行称为一个结点，每一个组合项称为一个字段。
使用计算机处理用户信息表中的数据时，必须弄清楚下面 3个问题：
1 数据的逻辑结构这些数据之间有什么样的内在联系？
除最前和最后两个结点之外,表中所有其它的结点都有且仅有一个和它相邻位于它之前的一个结点,也有且仅有一个和它相邻位于它之后的一个结点,这些就是用户信息表的逻辑结构 。
2 数据的存储结构将用户信息表中的所有结点存入计算机时,就必须考虑存储结构,使用 C语言进行设计时,常见的方式是用一个结构数组来存储整个用户信息表,每一个数组元素是一个结构,它对应于用户信息表中的一个结点 。 数据在计算机的存储方式称为存储结构 。
3 数据的运算集合数据处理必涉及到相关的运算，在上述用户信息表中，可以有删除一个用户、增加一个用户和查找某个用户等操作。应该明确指明这些操作的含义。比如删除操作，是删除序号为 5的用户还是删除用户名为王三的用户是应该明确定义的，如果需要可以定义两个不同的删除操作，为一批数据定义的所有运算（或称操作）构成一个运算（操作）集合。
对待处理的数据，只有分析清楚上面 3个方面的问题，才能进行有效的处理！
数据结构 就是指按一定的逻辑结构组成的一批数据,
使用某种存储结构将这批数据存储于计算机中,并在这些数据上定义了一个运算集合 。
1.1.2数据的逻辑结构数据的逻辑结构是数据和数据之间所存在的逻辑关系,它可以用一个二元组
B=（ K,R）
来表示，其中 K是数据、即结点的有限集合； R是集合 K上关系的有限集合，这里的关系是从集合 K到集合 K的关系，这里一般只涉及到一个关系的逻辑结构。
例如,有 5个人,分别记为 a,b,c,d,e,其中 a是 b的父亲,
b是 c的父亲,c是 d的父亲,d是 e的父亲,如果只讨论他们之间所存在的父子关系,则可以用下面的二元组形式化地予以表达 。
B=（ K,R）
其中,K={a,b,c,d,e}
R={r}
r={<a,b>,<b,c>,<c,d>,<d,e>}
逻辑结构的 图形表示 方式,对 K中的每个结点 ki用一个方框表示,而结点之间的关系用带箭头的线段表示,
这 5人之间的逻辑结构用图形的方式表达如下图 所示 。
若 ki∈ K,kj∈ R,<ki,kj > ∈ r，则称 ki是 kj的相对于关系 r的 前驱结点,kj是 ki的相对于关系 r的 后继结点,
因为一般只讨论具有一种关系的逻辑结构，即 R={r}，
所以简称 ki是 kj前驱,kj是 ki的后继。如果某个结点没有前驱结点，称之为 开始结点 ；如果某个结点没有后继结点，称之为 终端结点 ；既不是开始结点也不是终端结点的结点称为 内部结点 。
1.1.3数据的存储结构数据的逻辑结构是独立于计算机的,它与数据在计算机中的存储无关,要对数据进行处理,就必须将数据存储在计算机中 。 如果将数据在计算机中无规律地存储,那么在处理时是非常糟的,是没有用的 。 试想一下,如果一本英汉字典中的单词是随意编排的,
这本字典谁会用 ！
对于一个数据结构 B=（ K,R）,必须建立从结点集合到计算机某个存储区域 M的一个映象,这个映象要 直接或间接 地表达结点之间的关系 R。 数据在计算机中的存储方式称为数据的存储结构 。
数据的存储结构主要有 4种 。
数据的存储结构主要有 4种 。
1 顺序存储顺序存储通常用于存储具有线性结构的数据。将逻辑上相邻的结点存储在连续存储区域 M的相邻的存储单元中，使得逻辑相邻的结点一定是物理位置相邻。
对于一个数据结构 B=（ K,R）
其中 K={k1,k2,k3,k4,k5,k6,k7,k8,k9}
R={r}
r={<k1,k2>,<k2,k3>,<k3,k4>,<k4,k5>,<k5,k6>,<k6,k7>,<k7,
k8>,<k8,k9>}
它的顺序存储方式如图所示
2 链式存储链式存储方式是给每个结点附加一个指针段，一个结点的指针所指的是该结点的后继的存储地址，因为一个结点可能有多个后继，所以指针段可以是一个指针，也可以是一个多个指针。
例,数据的逻辑结构 B=（ K,R）
其中 K={k1,k2,k3,k4,k5}
R={r}
R={< k1,k2>,<k2,k3>,<k3,k4>,<k4,k5>}
这是一个线性结构，它的链式存储如图所示。
3 索引存储在线性结构中，设开始结点的索引号为 1，其它结点的索引号等于其前继结点的索引号加 1，则每一个结点都有唯一的索引号，索引号就是根据结点的索引号确定该结点的存储地址。
4 散列存储散列存储的思想是构造一个从集合 K到存储区域 M
的一个函数 h，该函数的定义域为 K，值域为 M,K中的每个结点 ki在计算机中的存储地址由 h(ki)确定。
1.1.4数据的运算集合对于一批数据，数据的运算是定义在数据的逻辑结构之上的，而运算的具体实现就依赖于数据的存储结构。
数据的运算集合要视情况而定,一般而言,数据的运算包括插入,删除,检索,输出,排序等 。
插入：在一个结构中增加一个新的结点 。
删除：在一个结构删除一个结点 。
检索：在一个结构中查找满足条件的结点 。
输出：将一个结构中所有结点的值打印,输出 。
排序：将一个结构中所有结点按某种顺序重新排列 。
在程序设计中，数据和运算是两个不可缺少的因素。所有的程序设计活动都是围绕着数据和其上的相关运算而进行的。从机器指令、汇编语言中的数据没有类型的概念，到现在的面向对象程序设计语言中抽象数据类型概念的出现，程序设计中的数据经历了一次次抽象，数据的抽象经历了三个发展阶段。
1.2数据类型和抽象数据类型
从无类型的二进制数到基本数据类型的产生
从基本数据类型到用户自定义类型的产生
从用户自定义类型到抽象数据类型的出现
1.2.1数据类型数据类型（或简称类型）反映了数据的取值范围以及对这类数据可以施加的运算。
1.2.2数据结构数据结构是计算机科学中广泛使用的一个术语,在计算机科学中具有非常重要的作用 。 数据结构包括三个方面的内容：一组数据中各数据之间的逻辑关系；这组数据在计算机中的存储方式；对这组数据所能施加的运算的集合 。 数据结构是数据存在的形式 。 所有的数据都是按照数据结构进行分类的 。 简单数据类型对应于简单的数据结构；构造数据类型对应于复杂的数据结构 。
1.2.3抽象数据类型抽象数据类型是与表示无关的数据类型，是一个数据模型及定义在该模型上的一组运算。对一个抽象数据类型进行定义时，必须给出它的名字及各运算的运算符名，即函数名，并且规定这些函数的参数性质。一旦定义了一个抽象数据类型及具体实现，程序设计中就可以像使用基本数据类型那样，十分方便地使用抽象数据类型。
1.2.4抽象数据类型的描述和实现抽象数据类型的描述包括给出抽象数据类型的名称、
数据的集合、数据之间的关系和操作的集合等方面的描述。抽象数据类型的设计者根据这些描述给出操作的具体实现，抽象数据类型的使用者依据这些描述使用抽象数据类型。
抽象数据类型描述的一般形式如下：
ADT 抽象数据类型名称 {
数据对象：
……
数据关系：
……
操作集合：
操作名 1：
……
……
操作名 n：
}ADT抽象数据类型名称
1.3 算法和算法分析
1.3.1算法为了求解某问题,必须给出一系列的运算规则,
这一系列的运算规则是有限的,表达了求解问题方法和步骤,这就是一个算法 。
一个算法可以用自然语言描述,也可以用高级程序设计语言描述,也可以用伪代码描述 。 本书采用 C语言对算法进行描述 。
算法具有五个基本特征：
① 有穷性,算法的执行必须在有限步内结束 。
② 确定性,算法的每一个步骤必须是确定的无二义性的 。
③ 输入,算法可以有 0个或多个输入 。
④ 输出,算法一定有输出结果
⑤可行性，算法中的运算都必须是可以实现的。
算法具有有穷性，程序不需要具备有穷性。一般的程序都会在有限时间内终止，但有的程序却可以不在有限时间内终止，如一个操作系统在正常情况下是永远都不会终止的。
1.3.2算法的时间和空间复杂性一个算法的优劣主要从算法的执行时间和所需要占用的存储空间两个方面衡量，算法执行时间的度量不是采用算法执行的绝对时间来计算的，因为一个算法在不同的机器上执行所花的时间不一样，在不同时刻也会由于计算机资源占用情况的不同，使得算法在同一台计算机上执行的时间也不一样，所以对于算法的时间复杂性，采用算法执行过程中其基本操作的执行次数，称为计算量来度量。
算法中基本操作的执行次数一般是与问题规模有关的，对于结点个数为 n的数据处理问题，用 T(n)
表示算法基本操作的执行次数。
在评价算法的时间复杂性时，不考虑两算法执行次数之间的细小区别，而只关心算法的本质差别。为此，引入一个所谓的 O() 记号，则
T1(n)=2n=O(n),T2(n)=n+1=O(n)。
一个函数 f(n)是 O(g(n))的，则一定存在正常数 c和
m，使对所有的 n>m，都满足 f(n)<c*g(n)。
下面的表格给出了一些具体函数的 O()的表示,如图所示 。 f(n) O(g(n)) 量级
35 O(1) 常数阶
2n+7 O(n) 线性阶
n2+10 O(n2) 平方阶
2n3+n O(n3) 立方阶算法的时间复杂性不仅和问题的规模大小有关，
还与问题数据的初始状态有关。
这样就有了算法在最好,最坏以及在平均状态下的时间复杂性的概念 。
① 算法在最好情况下的时间复杂性是指算法计算量的最小值 。
② 算法在最坏情况下的时间复杂性是指算法计算量的最大值 。
③ 算法的平均情况下的时间复杂性是指算法在所有可能的情况下的计算量经过加权计算出的平均值 。
本书在对算法进行分析时,会用到如下两个记号：
x?：表示不大于 x的最大整数；
x?：表示不小于 x的最小整数 。
第 2章 线性表及其顺序存储线性表是一种常用的数据结构，本章介绍线性表及其顺序存储，并对栈和队列及它们的顺序实现给出了详细的设计描述。
2.1线性表线性表是一个线性结构，它是一个含有 n≥0个结点的有限序列，对于其中的结点，有且仅有一个开始结点没有前驱但有一个后继结点，有且仅有一个终端结点没有后继但有一个前驱结点，其它的结点都有且仅有一个前驱和一个后继结点。一般地，一个线性表可以表示成一个线性序列,k1,k2,…,k n，其中 k1是开始结点,kn是终端结点。
2.2.1顺序表线性表采用顺序存储的方式存储就称之为顺序表。
顺序表是将表中的结点依次存放在计算机内存中一组地址连续的存储单元中。
如顺序表的每个结点占用 len个内存单元,用
location (ki)表示顺序表中第 i个结点 ki所占内存空间的第 1个单元的地址 。 则有如下的关系
location (ki+1) = location (ki) +len
location (ki) = location(k1) + (i-1)len
2.2顺序表顺序表的存储结构如下图所示：
存储结构要体现数据的逻辑结构，顺序表的存储结构中，内存中物理地址相邻的结点一定具有顺序表中的逻辑关系。
顺序表类型的描述如下：
ADT sequence_list{
数据集合 K,K={k1,k2,…,kn},n≥0,K中的元素是 datatype类型数据关系 R,R={r},r={ <ki,ki+1>| i=1,2,…,n-1}
操作集合：
(1) void init_sequence_list(sequence_list *slt) 顺序表的初始化 ------置空表
(2) void insert_sequence_list(sequence_list *slt,datatype x) 后部插入值为 x结点
(3) void print_sequence_list(sequence_list slt) 打印顺序表的各结点值
(4) int is_empty_sequence_list(sequence_list slt) 判断顺序表是否为空
(5) int find_num_sequence_list(sequence_list slt,datatype x) 查找值为 x结点位置
(6) int get_data_pos(sequence_list slt,int i) 取得顺序表中第 i个结点的值
(7) void insert_pos_sequence_list(sequence_list *slt,int position,datatype x)
(8) void delete_pos_sequence_list(sequence_list *slt,int position)
} ADT sequence_list；
2.2.2顺序表的实现用 C语言中的数组存储顺序表 。 C语言中数组的下标是从 0开始的,即数组中下标为 0的元素对应的是顺序表中的第 1个结点,数组中下标为 i的元素对应的是顺序表中的第 i+1个结点 。 为了方便,将顺序表中各结点的序号改为和对应数组元素的下标序号一致,即将顺序表中各结点的序号从 0开始编号 。 这样,一个长度为 n
的顺序表可以表示为
{k0,k1,k2,…,kn-1}
顺序表的存储结构的 C语言描述如下：
/********************************/
/*顺序表的头文件,文件名 sequlist.h*/
/********************************/
#define MAXSIZE 100
typedef int datatype;
typedef struct{
datatype a[MAXSIZE];
int size;
}sequence_list;
顺序表的几个基本操作的具体实现,
/********************************************/
/* 顺序表的初始化 ---置空表 */
/* 文件名 seqlinit.c,函数名 init_sequence_list() */
/*******************************************/
void init_sequence_list(sequence_list *slt)
{
slt->size=0;
}
算法 2.1顺序表的初始化 ---置空表
/**********************************************/
/* 在顺序表后部进行插入操作 */
/* 文件名 seqlinse.c,函数名 insert_sequence_list() */
/**********************************************/
void insert_sequence_list(sequence_list *slt,datatype x)
{
if(slt->size==MAXSIZE)
{printf("顺序表是满的 !");exit(1);}
slt->size=slt->size+1;
slt->a[slt->size]=x;
}
算法 2.2在顺序表后部进行插入操作
/**********************************************/
/* 打印顺序表的各结点值 */
/* 文件名 seqlprin.c,函数名 print_sequence_list() */
/*********************************************/
void print_sequence_list(sequence_list slt)
{
int i;
if(!slt.size) printf("\n顺序表是空的 !");
else
for(i=0;i<slt.size;i++) printf("%5d",slt.a[i]);
}
算法 2.3打印顺序表的各结点值
/**********************************************/
/* 判断顺序表是否为空 */
/* 文件名 seqlempt.c,函数名 is_empty_sequence_list() */
/**********************************************/
int is_empty_sequence_list(sequence_list slt)
{
return(slt.size==0? 0:1);
}
算法 2.4判断顺序表是否为空
/**********************************************/
/* 查找顺序表中值为 x的结点位置 */
/* 文件名 seqlfind.c,函数名 find_num_sequence_list() */
/**********************************************/
int find_num_sequence_list(sequence_list slt,datatype x)
{
int i=0;
while(slt.a[i]!=x&&i<slt.size) i++;
return(i<slt.size? i:-1);
}
算法 2.5查找顺序表中值为 x的结点位置
/*********************************************/
/* 取得顺序表中第 i个结点的值 */
/*文件名 seqlget.c,函数名 get_data_pos_sequence_list() */
/*********************************************/
int get_data_pos(sequence_list slt,int i)
{
if(i<0||i>=slt.size)
{printf("\n指定位置的结点不存在 !");exit(1);}
else
return slt.a[i];
}
算法 2.6取得顺序表中第 i个结点的值顺序表的插入运算是将一个值为 x的结点插入到顺序表的第 i个位置 0≤i≤n,即将 x插入到 ki-1和 ki之间,如果
i=n,则表示插入到表的最后,一般地可表示为：
插入前,{k0,k1,…,ki-1,ki,…,kn-1}
插入后,{k0,k1,…,k i-1,x,ki,…,k n-1}
插入过程的图示见下图：
/**********************************************/
/* 在顺序表的 position位置插入值为 x的结点 */
/* 文件名 seqlinse.c,函数名 insert_pos_sequence_list() */
/********************************************/
void insert_pos_sequence_list(sequence_list *slt,int
position,datatype x)
{ int i;
if(slt->size==MAXSIZE)
{printf("\n顺序表是满的 !没法插入 !");exit(1);}
if(position<0||position>slt->size)
{printf("\n指定的插入位置不存在 !");exit(1);}
for(i=slt->size;i>position;i--) slt->a[i]=slt->a[i-1];
slt->a[position]=x;
slt->size++;
}
算法 2.7在顺序表的 position位置插入值为 x的结点算法 2.7中,所花费的时间主要是元素后移操作,对于在第 i个位置上插入一个新的元素,需要移动 （ n-i）
个元素,设在第 i个位置上插入一个元素的概率为 pi,且在任意一个位置上插入元素的概率相等,即
p0=p1=p2=… =pn=1/n+1,则在一个长度为 n的顺序表中插入一个元素所需的平均移动次数为：
22
)1(
1
1)(
1
1)(
00
nnn
n
in
n
inp
n
i
n
i
i?
即在长度为 n的顺序表中插入一个元素平均需要移动表中的一半元素。该算法的时间复杂度为 O（ n）。
顺序表的删除操作是指删除顺序表中的第 i个结点,
0≤i≤n-1,一般地可表示为：
删除前,{k0,k1,…,ki-1,ki,ki+1,,…,kn-1}
删除后,{k0,k1,…,k i-1,ki+1,…,k n-1}
删除过程的图示见下图,
删除操作的具体实现见算法 2.8
/**********************************************/
/* 删除顺序表中第 position位置的结点 */
/* 文件名 seqldele.c,函数名 delete_pos_sequence_list() */
/**********************************************/
void delete_pos_sequence_list(sequence_list *slt,int position)
{
int i;
if(slt->size==0)
{printf("\n顺序表是空的 !");exit(1);}
if(position<0||position>=slt->size)
{printf("\n指定的删除位置不存在 !");exit(1);}
for(i=position;i<slt->size-1;i--) slt->a[i]=slt->a[i+1];
slt->size--;
}
算法 2.8删除顺序表中第 position位置的结点要删除顺序表中的第 i个结点,则需要称动 （ n-i-1）
个元素,设删除表中第 i个结点的概率为 qi,且在表中每一个位置删除的概率相等,即：
q0=q1=… =qn-1=1/n
则在一个长度为 n的顺序表中删除一个结点的平均移动次数为：
2
1
2
)1(1)1(1)1( 1
0
1
0
nnn
n
in
n
inq
n
i
n
i
i
这表明，在一个长为 n的顺序表中删除一个元素平均需要移动表中大约一半的元素。该算法的时间复杂度为 O（ n）。
2.3 栈2.3.1栈栈是一种特殊的线性表，对于这种线性表规定它的插入运算和删除运算均在线性表的同一端进行，进行插入和删除的那一端称为栈顶，另一端称为栈底。
栈的插入操作和删除操作也分别简称进栈和出栈。
如果栈中有 n个结点
{k0,k1,k2,…,k n-1}，
k0为栈底,kn-1是栈顶，
则栈中结点的进栈顺序为 k0,k1,k2,…,k n-1，
而出栈的顺序为 kn-1,
kn-2,…,k 1,k0。如图所示。
栈具有后进先出或先进后出
（ FILO,F
irst In
Last Out）
的性质栈类型的描述如下：
ADT sequence_stack {
数据集合 K,K={k1,k2,…,kn},n≥0,K中的元素是 datatype类型数据关系 R,R={r}
r={ <ki,ki+1>| i=1,2,…,n-1}
操作集合：
(1) void init_sequence_stack(sequence_stack *st) （ 顺序存储 ）
初始化
(2) int is_empty_stack(sequence_stack st) 判断栈 （ 顺序存储 ）
是否为空
(3) void print_sequence_stack(sequence_stack st) 打印栈 （ 顺序存储 ） 的结点值
(4) datatype get_top(sequence_stack st) 取得栈顶 （ 顺序存储 ） 结点值
(5) void push(sequence_stack *st,datatype x) 栈 （ 顺序存储 ）
的插入操作
(6) void pop(sequence_stack *st) 栈 （ 顺序存储 ） 的删除操作
} ADT sequence_stack
2.3.2顺序栈及其实现栈的实现方式一般有两种：顺序存储和链式存储。
本小节将给出栈的顺序存储实现。
栈的顺序存储方式就是在顺序表的基础上对插入和删除操作限制它们在顺序表的同一端进行，所以同顺序表一样也可用一维数组表示。
一般地，可以设定一个足够大的一维数组存储栈，
数组中下标为 0的元素就是栈底，对于栈顶，可以设一个指针 top指示它。
为了方便，设定 top所指的位置是下一个将要插入的结点的存储位置，这样，当 top=0时就表示是一个空的栈。一个栈的几种状态以及在这些状态下栈顶指针
top和栈中结点的关系如下图所示。
栈的顺序存储结构的 C语言描述如下：
/*****************************/
/* 栈 （ 顺序存储 ） 的头文件 */
/* 文件名 seqstack.h */
/*****************************/
#define MAXSIZE 100
typedef int datatype;
typedef struct{
datatype a[MAXSIZE];
int top;
}sequence_stack;
下面是顺序存储栈的几个基本操作的具体实现
/***********************************************************/
/* 栈 （ 顺序存储 ） 初始化 */
/* 文件名 seqsinit.c,函数名 init_sequence_stack() */
/***********************************************************/
void init_sequence_stack(sequence_stack *st)
{
st->top=0;
}
算法 2.9栈（顺序存储）初始化
/***************************************************/
/* 判断栈 （ 顺序存储 ） 是否为空 */
/* 文件名 seqsempt.c,函数名 is_empty_sequence_stack() */
/***************************************************/
int is_empty_stack(sequence_stack st)
{
return(st.top? 0:1);
}
算法 2.10判断栈（顺序存储）是否为空
/***************************************************/
/* 取得栈顶 （ 顺序存储 ） 结点值 */
/* 文件名 seqsfirs.c,函数名 get_top() */
/***************************************************/
datatype get_top(sequence_stack st)
{
if (empty_stack(st))
{printf("\n栈是空的 !");exit(1);}
else
return st.a[st.top-1];
}
算法 2.11取得栈顶（顺序存储）结点值
/***************************************************/
/* 栈 （ 顺序存储 ） 的插入操作 */
/* 文件名 seqspush.c,函数名 push() */
/***************************************************/
void push(sequence_stack *st,datatype x)
{
if(st->top==MAXSIZE)
{printf("\nThe sequence stack is full!");exit(1);}
st->a[st->top]=x;
st->top++;
}
算法 2.12 栈（顺序存储）的插入操作
/***************************************************/
/* 栈 （ 顺序存储 ） 的删除操作 */
/* 文件名 seqspop.c,函数名 pop() */
/***************************************************/
void pop(sequence_stack *st)
{
if(st->top==0)
{printf("\nThe sequence stack is empty!");exit(1);}
st->top--;
}
算法 2.13栈（顺序存储）的删除操作
2.3.3栈的应用之一 ------括号匹配设一个表达式中可以包含三种括号：小括号,中括号和大括号,各种括号之间允许任意嵌套,如小括号内可以嵌套中括号,大括号,但是不能交叉 。 举例如下：
([]{}) 正确的
([()]) 正确的
{([])} 正确的
{[(])} 不正确的
{(}[]) 不正确的如何去检验一个表达式的括号是否匹配呢？大家知道当自左向右扫描一个表达式时，凡是遇到的开括号
（或称左括号）都期待有一个和它对应的闭括号（或称右括号）与之匹配。
按照括号正确匹配的规则，在自左向右扫描一个表达式时，后遇到的开括号比先遇到的开括号更加期待有一个闭括号与之匹配。
可能会连续遇到多个开括号，且它们都期待寻求匹对的闭括号，所以必须将遇到的开括号存放好。又因为后遇到的开括号的期待程度高于其先前遇到的开括号的期待程度，所以应该将所遇到的开括号存放于一个栈中。这样，当遇到一个闭括号时，就查看这个栈的栈顶结点，如果它们匹配，则删除栈顶结点，如果不匹配，则说明表达式中括号是不匹配的，如果扫描它整个表达式后，这个栈是空的，则说明表达式中的括号是匹配的，否则表达式的括号是不匹配的。
判断表达式括号是否匹配的具体实现见算法 2.14。
/*******************************************/
/* 判断表达式括号是否匹配 */
/* 文件名 seqmatch.c,函数名 match_huohao() */
/*******************************************/
int match_kuohao(char c[])
{
int i=0;
sequence_stack s;
init_sequence_stack(&s);
while(c[i]!='#')
{
switch(c[i])
{
case '{':
case '[':
case '(':push(&s,c[i]);break;
case '}':if(!is_empty_sequence_stack(s)&&get_top(s)=='{'}
{pop(&s);break;} else return 0;
case ']':if(!is_empty_sequence_stack(s)&&get_top(s)=='[']
{pop(&s);break;} else return 0;
case ')':if(!is_empty_sequence_stack(s)&&get_top(s)=='(')
{pop(&s);break;} else return 0;
}
i++;
}
return (is_empty_sequence_stack(s));/*栈空则匹配,否则不匹配 */
}
算法 2.14判断表达式括号是否匹配
2.3.4栈的应用之二 ------算术表达式求值
2.4 队列
2.4.1 队列队列是一种特殊的线性表，它的特殊性在于队列的插入和删除操作分别在表的两端进行。插入的那一端称为队尾，删除的那一端称为队首。队列的插入操作和删除操作也分别简称进队和出队。
对于一个队列：
{k0,k1,k2,…,kn-1}
如果 k0那端是队首,kn-1那端是队尾，则 k0是这些结点中最先插入的结点，若要做删除操作,k0将首先被删除，所以说，队列是具有“先进先出”（ FIFO,First
In First Out）特点的线性结构。
队列类型的描述如下：
ADT sequence_queue {
数据集合 K,K={k1,k2,…,kn},n≥0,K中的元素是 datatype类型数据关系 R,R={r}
r={ <ki,ki+1>| i=1,2,…,n-1}
操作集合：
(1) void init_sequence_queue(sequence_queue *sq) 队列 （ 顺序存储 ） 初始化
(2) int is_empty_sequence_queue(sequence_queue sq) 判断队列 （ 顺序存储 ） 是否为空
(3) void print_sequence_queue(sequence_queue sq) 打印队列
（ 顺序存储 ） 的结点值
(4) datatype get_first(sequence_queue sq) 取得队列 （ 顺序存储 ） 的队首结点值
(5) void insert_sequence_queue (sequence_queue
*sq,datatype x) 队列 （ 顺序存储 ） 插入操作
(6) void delete_sequence_queue(sequence_queue *sq) 队列
（ 顺序存储 ） 的删除操作
} ADT sequence_queue;
2.4.2顺序队列及其实现队列的顺序存储在 C语言中可以用一维数组表示，
为了标识队首和队尾，需要附设两个指针 front和 rear，
front指示的是队列中最前面，即队首结点在数组中元素的下标,rear指示的是队尾结点在数组中元素的下标的下一个位置，也就是说 rear指示的是即将插入的结点在数组中的下标。
队列的几种状态,
下标下标下标下标下标队列的顺序存储结构的 C语言描述如下：
/*****************************/
/* 队列 （ 顺序存储 ） 的头文件 */
/* 文件名 seqqueue.h */
/*****************************/
#define MAXSIZE 100
typedef int datatype;
typedef struct{
datatype a[MAXSIZE];
int front;
int rear;
}sequence_queue;
顺序存储队列的几个基本操作的具体实现,
/************************************************/
/* 队列 （ 顺序存储 ） 初始化 */
/* 文件名 seqqinit.c,函数名 init_sequence_queue() */
/************************************************/
void init_sequence_queue(sequence_queue *sq)
{
sq->front=sq->rear=0;
}
算法 2.20队列（顺序存储）初始化
/***************************************************/
/* 判断队列 （ 顺序存储 ） 是否为空 */
/*文件名 seqqempt.c,函数名 is_empty_sequence_queue() */
/***************************************************/
int is_empty_sequence_queue(sequence_queue sq)
{
return (sq.front==sq.rear? 1:0);
}
算法 2.21判断队列（顺序存储）是否为空
/***************************************************/
/* 打印队列 （ 顺序存储 ） 的结点值 */
/* 文件名 seqqprin.c,函数名 print_sequence_queue() */
/***************************************************/
void print_sequence_queue(sequence_queue sq)
{
int i;
if(is_empty_sequence_queue(sq))
{
printf("\n顺序队列是空的 !");
}
else
for(i=sq.front;i<sq.rear;i++) printf("%5d",sq.a[i]);
}
算法 2.22打印队列（顺序存储）的结点值
/*********************************************/
/* 队列 （ 顺序存储 ） 的插入操作 */
/* 文件名 seqqinse.c,函数名 insert_sequence_queue() */
/********************************************/
void insert_sequence_queue(sequence_queue *sq,datatype x)
{
int i;
if(sq->rear==MAXSIZE)
{printf("\n顺序循环队列是满的 !");exit(1);}
sq->a[sq->rear]=x;
sq->rear=sq->rear+1;
}
算法 2.24队列（顺序存储）的插入操作
/***************************************************/
/* 队列 （ 顺序存储 ） 的删除操作 */
/* 文件名 seqqdele.c,函数名 delete_sequence_queue() */
/***************************************************/
void delete_sequence_queue(sequence_queue *sq)
{
if(sq->front==sq->rear)
{
printf("\n顺序队列是空的 ！ 不能做删除操作 ！ "); exit(1);
}
sq->front++;
}
算法 2.25队列（顺序存储）的删除操作在队列的几种状态图的（ e）状态中，队列是一种队满状态，将不能再插入新的结点，而实际上数组的前部还有许多空的位置。为了充分地利用空间，可以将队列看作一个循环队列，在数组的前部继续作插入运算，这就是循环队列。
下标下标
2.4.3顺序循环队列及其实现给定一个大小为 MAXSIZE的数组存储一个队列时，经过若干次插入和删除操作后，当队尾指指
rear=MAXSIZE时，呈现队列满的状态，而事实上数组的前部可能还有空闲的位置。为了有效利用空间，
将顺序存储的队列想象为一个环状，把数组中的最前和最后两个元素看作是相邻的，这就是循环队列。
循环队列的几种状态表示,
在（ b）状态中，如果再插入一个新的结点，则数组空间将被全部占用，队列已满，且 rear=front，而在
（ c）状态中，若删除一个结点队列成为空队列，此时也有 rear=front，这就是说循环队列满与空的条件都是
rear=front。
解决方法是牺牲一个数组元素的空间,即若数组的大小是 MAXSIZE,则该数组所表示的循环队列最多允许存储 MAXSIZE-1个结点 。 这样,循环队列满的条件是
(rear+1)%MAXSIZE=front
循环队列空的条件是 rear=front
循环队列的插入与删除操作的实现,
/***************************************************/
/* 循环队列 （ 顺序存储 ） 的插入操作 */
/* 文件名 secqinst.c,函数名 insert_sequence_cqueue() */
/***************************************************/
void insert_sequence_cqueue(sequence_queue *sq,datatype x)
{
int i;
if((sq->rear+1)%MAXSIZE==sq->front)
{printf("\n顺序循环队列是满的 ！ 无法进行插入操作 ！ ");exit(1);}
sq->a[sq->rear]=x;
sq->rear=(sq->rear+1)%MAXSIZE;
}
算法 2.27循环队列（顺序存储）的插入操作
/***************************************************/
/* 循环队列 （ 顺序存储 ） 的删除操作 */
/* 文件名 secqdele.c,函数名 delete_sequence_cqueue() */
/***************************************************/
void delete_sequence_cqueue(sequence_queue *sq)
{
if(sq->front==sq->rear)
{
printf(“\n循环队列是空的 ！ 无法进行删除 ！ "); exit(1);
}
sq->front=(sq->front+1)%MAXSIZE;
}
算法 2.28循环队列（顺序存储）的删除操作第 3章 线性表的链式存储线性表的存储方式除了常用的顺序存储外，采用链式方式存储也是一种常见的方式。本章将介绍一般线性表的几种链式存储实现方式，如单链表、带头结点单链表、循环单链表、双链表以及特殊的线性表 -----
-栈和队列的链式存储实现。
3.1链式存储数据结构的存储方式必须体现它的逻辑关系 。
在链式存储方式下，实现中除存放一个结点的信息外，
还需附设指针，用指针体现结点之间的逻辑关系。如果一个结点有多个后继或多个前驱，那么可以附设相应个数的指针，一个结点附设的指针指向的是这个结点的某个前驱或后继。
线性结构中，每个结点最多只有一个前驱和一个后继，这里暂且设定更关心它的后继，这样在存储时除了存放该结点的信息外，只要附设一个指针即可，该指针指向它的后继结点的存放位置。每个结点的存储形式是,info next
例,数据的逻辑结构 B=（ K,R）
其中 K={k1,k2,k3,k4,k5}
R={r}
R={< k1,k2>,<k2,k3>,<k3,k4>,<k4,k5>}
是一个线性结构，它的链式存储如图所示为了清晰,左图可以更简洁地用下图表示 。
3.2 单链表单链表是线性表链式存储的一种形式，其中的结点一般含有两个域，一个是存放数据信息的 info域，另一个是指向该结点的后继结点的存放地址的指针域 next。
一个单链表必须有一个首指针指向单链表中的第一个结点。图 3.3给出了空的单链表和非空的单链表的图示。
单链表类型的描述如下：ADT link_list{
数据集合 K,K={k1,k2,…,kn},n≥0,K中的元素是 datatype类型数据关系 R,R={r}
r={ <ki,ki+1>| i=1,2,…,n-1}
操作集合：
(1) node *init_link_list() 建立一个空的单链表
(2) void print_link_list(node *head) 输出单链表中各个结点的值
(3) node *insert_in_front_link_list(node *head,datatype x)
插入一个值为 x的结点作为单链表的第一个结点
(4) node *find_num_link_list(node *head,datatype x) 在单链表中查找一个值为 x的结点
(5) node *find_pos_link_list(node *head,int i) 在单链表中查找第 i
个结点
(6) node *insert_x_after_y(node *head,datatype x,datatype y)
在单链表中值为 y的结点后插入一个值为 x的新结点
(7) node *insert_x_after_i(node *head,datatype x,int i)
在单链表中第 i个结点后插入一个值为 x的新结点
(8) node *delete_num_link_list(node *head,datatype x) 在单链表中删除一个值为 x的结点
(9) node *delete_pos_link_list(node *head,int i) 在单链表中删除第 i个结点
} ADT link_list;
3.2.2单链表的实现单链表结构的 C语言描述如下：
/**********************************/
/*链表实现的头文件,文件名 slnklist.h */
/**********************************/
typedef int datatype;
typedef struct link_node{
datatype info;
struct link_node *next;
}node;
单链表几个基本操作的具体实现：
/*****************************************************/
/* 建立一个空的单链表 */
/* 文件名 slnkinit.c,函数名 init_link_list() */
/*****************************************************/
node *init_link_list() /*建立一个空的单链表 */
{
return NULL;
}
算法 3.1建立一个空的单链表
/*****************************************************/
/* 输出单链表中各个结点的值 */
/* 文件名 slnkprin.c,函数名 print_link_list() */
/*****************************************************/
void print_link_list(node *head)
{ node *p;
p=head;
if(!p) printf("\n单链表是空的 ！ ");
else
{ printf("\n单链表各个结点的值为,\n");
while(p) { printf("%5d",p->info);p=p->next;}
}
}
算法 3.2输出单链表中各个结点的值
/*****************************************************/
/* 在单链表中查找一个值为 x的结点 */
/* 文件名 slnkfinx.c,函数名 find_num_link_list() */
/*****************************************************/
node *find_num_link_list(node *head,datatype x)
{
node *p;
p=head;
while(p&&p->info!=x) p=p->next;
return p;
}
算法 3.3在单链表中查找一个值为 x的结点
/*****************************************************/
/* 在单链表中查找第 i个结点 */
/* 文件名 slnkfini.c,函数名 find_pos_link_list() */
/*****************************************************/
node *find_pos_link_list(node *head,int i)
{
int j=1;
node *p=head;
if(i<1){printf("\nError!\n");exit(1);}
while(p&&i!=j) { p=p->next ; j++; }
return p;
}
算法 3.4在单链表中查找第 i个结点单链表的插入过程见下图所示,
/*****************************************************/
/* 插入一个值为 x的结点作为单链表的第一个结点 */
/* 文件名 slnkinfx.c,函数名 insert_in_front_link_list() */
/*****************************************************/
node *insert_in_front_link_list(node *head,datatype x)
{
node *p;
p=(node*)malloc(sizeof(node)); /*分配空间 */
p->info=x; /*设置新结点的值 */
p->next=head; /*插入 (1)*/
head=p; /*插入 (2)*/
return head;
}
算法 3.5插入一个值为 x的结点作为单链表的第一个结点
/*****************************************************/
/* 在单链表中第 i个结点后插入一个值为 x的新结点 */
/* 文件名 slnkinix.c,函数名 insert_x_after_i() */
/****************************************************/
node *insert_x_after_i(node *head,datatype x,int i)
{
node *p,*q;
q=find_pos_link_list(head,i);/*查找第 i个结点 */
if(!q)
{printf("\n找不到第 %d个结点,不能进行插入 ！ ",i,x);exit(1);}
p=(node*)malloc(sizeof(node));/*分配空间 */
p->info=x;/*设置新结点 */
p->next=q->next;/*插入 (1)*/
q->next=p;/*插入 (2)*/
return head;
}
算法 3.7在单链表中第 i个结点后插入一个值为 x的新结点删除操作见下图所示：
node *delete_num_link_list(node *head,datatype x)
{
node *pre=NULL,*p;
if(!head) {printf("单链表是空的 ！ ");return head;}
p=head;
while(p&&p->info!=x)/*没有找到并且没有找完 */
{pre=p;p=p->next;}/*pre指向 p的前驱结点 */
if(!pre&&p->info==x)/*要删除的是第一个结点 */
head=head->next;/*删除 (1)*/
else
pre->next=p->next;
free(p);
return head;
}
算法 3.8在单链表中删除一个值为 x的结点链式存储的插入和删除操作比顺序存储方便，但不能随机访问某个结点！
3.3带头结点单链表
3.3.1带头结点单链表带头结点单链表见下图所示：
带头结点单链表类型的描述如下：ADT hlink_list{
数据集合 K,K={k1,k2,…,kn},n≥0,K中的元素是 datatype类型数据关系 R,R={r}
r={ <ki,ki+1>| i=1,2,…,n-1}
操作集合：
(1) node *init_hlink_list() 建立一个空的带头结点的单链表
(2) void print_hlink_list(node *head) 输出带头结点单链表中各个结点的值
(3) node *find_num_hlink_list(node *head,datatype x)
在带头结点单链表中查找一个值为 x的结点
(4) node *find_pos_hlink_list(node *head,int i) 在带头结点单链表中查找第 i个结点
(5) node *insert_in_front_hlink_list(node *head,datatype x)
插入一个值为 x的结点作为带头结点单链表的第一个结点
(6) node *insert_x_after_y(node *head,datatype x,datatype y)
在带头结点单链表中值为 y的结点后插入一个值为 x的新结点
7 sert_x_after_i(node *head,datatype x,int i)
在带头结点单链表中第 i个结点后插入一个值为 x的新结点
(8) node *delete_num_hlink_list(node *head,datatype x)
在带头结点单链表中删除一个值为 x的结点
(9) node *delete_pos_hlink_list(node *head,int i)
在带头结点单链表中删除第 i个结点
} ADT hlink_list;
3.3.2带头结点单链表的实现一般的单链表中，第一个结点由 head指示，而在带头结点单链表中,head指示的是所谓的头结点，它不是存储数据结构中的实际结点，第一个实际的结点是
head->next指示的。在带头结点单链表的操作实现时要注意这一点。
node *init_hlink_list()
{
node *head;
head=(node*)malloc(sizeof(node));
head->next=NULL;
return head;
}
算法 3.10建立一个空的带头结点单链表
void print_hlink_list(node *head)
{
node *p;
p=head->next;/*从第一个 （ 实际 ） 结点开始 */
if(!p) printf("\n带头结点单链表是空的 !");
else
{
printf("\n带头结点的单链表各个结点的值为,\n");
while(p) { printf("%5d",p->info);p=p->next;}
}
}
算法 3.11输出带头结点单链表中各个结点的值
/*****************************************************/
/* 在带头结点单链表中查找一个值为 x的结点 */
/* 文件名 hlnkfinx.c,函数名 find_num_hlink_list() */
/*****************************************************/
node *find_num_hlink_list(node *head,datatype x)
{
node *p;
p=head->next;/*从第一个 （ 实际 ） 结点开始 */
while(p&&p->info!=x) p=p->next;
return p;
}
算法 3.12在带头结点单链表中查找一个值为 x的结点
node *find_pos_hlink_list(node *head,int i)
{
int j=0;
node *p=head;
if(i<0){printf("\n带头结点的单链表中不存在第 %d个结点 ！
",i);return NULL;}
while(p&&i!=j)/*没有查找完并且还没有找到 */
{
p=p->next;j++;/*继续向后 （ 左 ） 查找,计数器加 1*/
}
return p;/*返回结果,i=0时,p指示的是头结点 */
}
算法 3.13在带头结点单链表中查找第 i个结点带头结点单链表的插入过程见图 3.7,
带头结点单链表的几个插入操作的具体实现见算法
3.14~算法 3.16。
node *insert_x_after_y(node *head,datatype x,datatype y)
{
node *p,*q;
q=find_num_hlink_list(head,y);/*查找值为 y的结点 */
if(!q)/*没有找到 */
{printf("\n没有找到值为 %d的结点,不能插入 %d!",y,x);return head;}
p=(node*)malloc(sizeof(node));/*为准备插入的新结点分配空间 */
p->info=x;/*为新结点设置值 x*/
p->next=q->next;/*插入 (1)*/
q->next=p;/*插入 (2)*/
return head;
}
算法 3.15在带头结点单链表中值为 y的结点后插入一个值为 x的新结点带头结点单链表的删除过程见图 3.8。
node *delete_num_hlink_list(node *head,datatype x)
{
node *pre=head,*q;/*首先 pre指向头结点 */
q=head->next;/*q从带头结点的第一个实际结点开始找值为 x
的结点 */
while(q&&q->info!=x)/*没有查找完并且还没有找到 */
{pre=q;q=q->next;}/*继续查找,pre指向 q的前驱 */
pre->next=q->next;/*删除 */
free(q);/*释放空间 */
return head;
}
算法 3.17在带头结点单链表中删除一个值为 x的结点
3.4 循环单链表
3.4.1 循环单链表无论是单链表，还是带头结点单链表，从表中的某个结点开始，只能访问到这个结点及其后面的结点，
不能访问到它前面的结点，除非再从首指针指示的结点开始访问。如果希望从表中的任意一个结点开始，
都能访问到表中的所有其它结点，可以设置表中最后一个结点的指针域指向表中的第一个结点，这种链表称为循环单链表。
循环单链表类型的描述 （略）
3.4.2循环单链表的实现单链表中某个结点 p是表中最后一个结点的特征是
p->next==NULL。 对于一个循环单链表,若首指针为
head,表中的某个结点 p是最后一个结点的特征应该是 p->next==head。
循环单链表的头文件和单链表的相同。
/*****************************************************/
/* 建立一个空的循环单链表 */
/* 文件名 clnkinit.c,函数名 init_clink_list() */
/*****************************************************/
node *init_clink_list() /*建立一个空的循环单链表 */
{
return NULL;
}
算法 3.19建立一个空的循环单链表
void print_clink_list(node *head)
{ node *p;
if(!head) printf("\n循环单链表是空的 ！ \n");
else
{printf("\n循环单链表各个结点的值分别为,\n");
printf("%5d",head->info);/*输出非空表中第一个结点的值 */
p=head->next;/*p指向第一个结点的下一个结点 */
while(p!=head)/*没有回到第一个结点 */
{printf("%5d",p->info);
p=p->next;
}
}
}
算法 3.21输出循环单链表中各个结点的值循环单链表的插入过程如图,
node *insert_x_after_i(node *head,datatype x,int i)
{ node *p,*q;
q=find_pos_clink_list(head,i);/*查找第 i个结点,q指向第 i个结点 */
if(!q)/*没有找到,则不进行插入 */
printf("\n表中不存在第 %d个结点,无法进行插入 !\n",i);
else
{ /*找到了第 i个结点,准备插入 x*/
p=(node*)malloc(sizeof(node));/*分配空间 */
p->info=x;/*设置新结点的值 */
p->next=q->next;/*插入,修改指针 (1)*/
q->next=p;/*插入,修改指针 (2)*/
}
return head;
}
算法 3.26在循环单链表中第 i个结点后插入一个值为 x的新结点循环单链表的删除过程如图,
node *delete_num_clink_list(node *head,datatype x)
{ node *pre=NULL,*q;/*q用于查找值为 x的结点,pre指向 q的前驱结点 */
if(!head)/*表为空,则无法做删除操作 */
{ printf(“\n循环单链表为空,无法做删除操作 ！,); return NULL; }
q=head;/*从第 1个结点开始准备查找 */
while(q->next!=head&&q->info!=x)/*没有找遍整个表并且没有找到 */
{ pre=q; q=q->next;/*pre为 q的前驱,继续查找 */
}/*循环结束后,pre为 q的前驱 */
if(q->info!=x)/*没找到 */ { printf("没有找到值为 %d的结点 ！ ",x); }
else /*找到了,下面要删除 q*/
{ pre->next=q->next;/*删除 q指向的结点 */ free(q);/*释放空间 */ }
return head;
}
算法 3.27在循环单链表中删除一个值为 x的结点
3.5 双链表
3.5.1 双链表前面的各种链式表中，一个结点的指针域是指向它的后继结点的，如果需要找一个结点 p的前驱结点，
则必须从表首指针开始查找，当某个结点 pre的指针域指向的是结点 p时，即 pre->next==p时，则说明 pre是
p的前驱结点。如果常常需要知道一个结点的前驱和后继结点，上述的链式表是不适合的。既然单链表中每个结点有一个指针域指向它的后继结点，那自然地想到再增设一个指针域指向它的前驱结点，这就构成了双链表。
双链表的结点包括三个域，一个是存放数据信息的 info域，另外两个是指针域，这里用 llink和 rlink表示，
llink指向它的前驱结点,rlink指向它的后继结点。
双链表的一般情形如图所示：
双链表类型的描述（略！）
3.5.2 双链表的实现双链表结构的 C语言描述如下：
/**********************************/
/* 双链表的头文件,文件名 dlnklist.h /
/**********************************/
typedef int datatype;
typedef struct dlink_node{
datatype info;
struct dlink_node *llink,*rlink;
}dnode;
void print_dlink_list(dnode *head)
{
dnode *p;
printf("\n"); p=head;
if(!p) printf("\n双链表是空的 !\n");
else
{
printf("\n双链表中各个结点的值为,\n");
while(p) { printf("%5d",p->info);p=p->rlink;}
}
}
算法 3.30 输出双链表中各个结点的值
dnode *find_pos_dlink_list(dnode *head,int i)
{
int j=1;
dnode *p=head;
if(i<1){printf("\n第 %d个结点不存在 !\n",i);return NULL;}
while(p&&i!=j)/*没有找完整个表并且没有找到 */
{ p=p->rlink;j++;/*继续沿着右指针向后查找,计数器加 1*/ }
if(!p){printf("\n第 %d个结点不存在 !\n",i);return NULL;}
return p;
}
算法 3.32查找双链表中第 i个结点双链表插入过程如下图所示：
/* 在双链表中第 i个结点后插入一个值为 x的新结点 */
dnode *insert_x_after_i(dnode *head,datatype x,int i)
{
dnode *p,*q;
p=(dnode*)malloc(sizeof(dnode));/*分配空间 */
p->info=x;/*设置新结点的值 */
if(i==0)/*在最前面插入一个值为 x的新结点 */
{ p->llink=NULL;/*新插入的结点没有前驱 */
p->rlink=head;/*新插入的结点的后继是原来双链表中的第一个结点 */
head=p;/*新结点成为双链表的第一个结点 */
return head;
}
q=find_pos_dlink_list(head,i);/*查找第 i个结点 */
if(!q)/*第 i个结点不存在 */
{printf("第 %d个结点不存在,无法进行插入 ",i);return head;}
if(q->rlink==NULL)/*在最后一个结点后插入 */
{
p->rlink=q->rlink;/*即为 NULL,新插入的结点没有后继 。 插入操作 (1)*/
p->llink=q;/*插入操作 (2)*/
q->rlink=p;/*插入操作 (4)*/
}/*注意不能和下面的一般情况一样处理，这里如执行下面的
(3)将出错！ */
else/*一般情况下的插入 */
{
p->rlink=q->rlink;/*插入操作 (1)*/
p->llink=q;/*插入操作 (2)*/
q->rlink->llink=p;/*插入操作 (3)*/
q->rlink=p;/*插入操作 (4)*/
}
return head;
}
算法 3.35 在双链表中第 i个结点后插入一个值为 x的新结点双链表删除操作图示,
/* 在双链表中删除一个值为 x的结点 */
dnode *delete_num_dlink_list(dnode *head,datatype x)
{ dnode *q;
if(!head)/*双链表为空,无法进行删除操作 */
{printf("双链表为空,无法进行删除操作 ");return head;}
q=head;
while(q&&q->info!=x) q=q->rlink;/*循环结束后 q指向的是值为 x
的结点 */
if(!q)
{
printf("\n没有找到值为 %d的结点 ！ 不做删除操作 ！ ",x);
}
if(q==head&&head->rlink)/*被删除的结点是第一个结点并且表中不只一个结点 */
{
head=head->rlink;
head->llink=NULL;
free(q);return head;
}
if(q==head&&!head->rlink)/*被删除的结点是第一个结点并且表中只有这一个结点 */
{
free(q);
return NULL;/*双链表置空 */
}
else
{ if(!q->rlink)/*被删除的结点是双链表中的最后一个结点 */
{ q->llink->rlink=NULL; free(q); return head; }
else/*q是在一个有 2个以上结点的双链表中的一个非开始,也非终端结点 */
{
q->llink->rlink=q->rlink;
q->rlink->llink=q->llink;
free(q); return head;
}
}
}
算法 3.36在双链表中删除一个值为 x的结点
3.6 链式栈
3.6.1 链式栈栈的链式存储称为链式栈。链式栈就是一个特殊的单链表，对于这特殊的单链表，它的插入和删除规定在单链表的同一端进行。链式栈的栈顶指针一般用
top表示，链式栈如下图所示。
链式栈类型的描述如下：
ADT link_stack{
数据集合 K,K={k1,k2,…,kn},n≥0,K中的元素是 datatype类型数据关系 R,R={r}
r={ <ki,ki+1>| i=1,2,…,n-1}
操作集合：
(1) node *init_link_stack() 建立一个空链式栈
(2) int empty_link_stack(node *top) 判断链式栈是否为空
(3) datatype get_top(node *top) 取得链式栈的栈顶结点值
(4) void print_link_stack(node *top) 输出链式栈中各个结点的值
(5) node *push_link_stack(node *top,datatype x) 向链式栈中插入一个值为 x
的结点
node *pop_link_stack(node *top)
/*删除链式栈的栈顶结点 */
} ADT link_stack;
3.6.2 链式栈的实现
datatype get_top(node *top)
{
if(!top) {printf("\n链式栈是空的 !");exit(1);}
return(top->info);
}
int empty_link_stack(node *top)
{
return (top? 0:1);
}
算法 3.40取得链式栈的栈顶结点值
/* 输出链式栈中各个结点的值 */
/* 文件名 lnksprin.c,函数名 print_link_stack() */
/*****************************************************/
void print_link_stack(node *top)
{
node *p;
p=top;
printf("\n");
if(!p) printf("\n链式栈是空的 !");
while(p) { printf("%5d",p->info);p=p->next;}
}
算法 3.41 输出链式栈中各个结点的值
/* 向链式栈中插入一个值为 x的结点 */
/* 文件名 lnkspush.c,函数名 push_link_stack() */
node *push_link_stack(node *top,datatype x)
{
node *p;
p=(node*)malloc(sizeof(node)); /*分配空间 */
p->info=x; /*设置新结点的值 */
p->next=top; /*插入 (1)*/
top=p; /*插入 (2)*/
return top;
}
算法 3.42向链式栈中插入一个值为 x的结点
/* 删除链式栈的栈顶结点 */
/* 文件名 lnkspop.c,函数名 pop_link_stack() */
node *pop_link_stack(node *top)
{
node *q;
if(!top) {printf("\n链式栈是空的 !");return NULL;}
q=top;/*指向被删除的结点 (1)*/
top=top->next;/*删除栈顶结点 (2)*/
free(q);
return top;
}
算法 3.43 删除链式栈的栈顶结点
3.7 链式队列
3.7.1 链式队列队列的链式存储称为链式队列。链式队列就是一个特殊的单链表，对于这种特殊的单链表，它的插入和删除规定在单链表的不同端进行。链式队列的队首和队尾指针分别用 front和 rear表示，链式队列如下图所示。
链式队列类型的描述如下：
ADT link_queue{
数据集合 K,K={k1,k2,…,kn},n≥0,K中的元素是 datatype类型数据关系 R,R={r}
r={ <ki,ki+1>| i=1,2,…,n-1}
操作集合：
(1) queue *init_link_queue() 建立一个空的链式队列
(2) int empty_link_queue(queue qu)判断链式队列是否为空
(3) void print_link_queue(queue *qu) 输出链式队列中各个结点的值
(4) datatype get_first(queue qu)取得链式队列的队首结点值
(5) queue *insert_link_queue(queue *qu,datatype x) 向链式队列中插入一个值为 x的结点
(6) queue *delete_link_queue(queue *qu) 删除链式队列中队首结点
} ADT link_queue;
3.7.2链式队列的实现：
链式队列的结点定义和单链表一样 。 队列必须有队首和队尾指针,因此增加定义一个结构类型,其中的两个域分别为队首和队尾指针 。 其定义如下：
typedef struct{
node *front,*rear; /*定义队首与队尾指针 */
}queue;
/* 建立一个空的链式队列 */
/* 文件名 lnkqinit.c,函数名 init_link_queue() */
/*****************************************************/
queue *init_link_queue() /*建立一个空的链式队列 */
{
queue *qu;
qu=(queue*)malloc(sizeof(queue)); /*分配空间 */
qu->front=NULL; /*队首指针设置为空 */
qu->rear=NULL; /*队尾指针设置为空 */
return qu;
}
算法 3.44建立一个空的链式队列
/*****************************************************/
/* 取得链式队列的队首结点值 */
/* 文件名 lnkqget.c,函数名 get_first() */
/*****************************************************/
datatype get_first(queue qu)
{
if(!qu.front) {printf("\n链式队列是空的 !");exit(1);}
return(qu.front->info);
}
算法 3.47取得链式队列的队首结点值链式队列的插入过程图示见下图：
/* 向链式队列中插入一个值为 x的结点 */
queue *insert_link_queue(queue *qu,datatype x)
{ node *p;
p=(node*)malloc(sizeof(node)); /*分配空间 */
p->info=x; /*设置新结点的值 */ p->next=NULL;
if (qu->front==NULL) qu->front=qu->rear=p;
else
{ qu->rear->next=p; /*队尾插入 */ qu->rear=p;
}
return qu;
}
算法 3.48向链式队列中插入一个值为 x的结点链式队列的删除过程图示见下图：
/* 删除链式队列中队首结点 */
queue *delete_link_queue(queue *qu)/*删除队首结点 */
{ node *q;
if(!qu->front) {printf("队列为空,无法删除 ！ ");return qu;}
q=qu->front; /*q指向队首结点 (1)*/
qu->front=q->next; /*队首指针指向下一个结点 (2)*/
free(q); /*释放原队首结点空间 */
if (qu->front==NULL) qu->rear=NULL; /*队列中的唯一结点被删除后,队列变空 (3)*/
return qu;
}
算法 3.49删除链式队列中队首结点
