数 据 结 构
计算机系
第一章 绪 论
1.1 什么是数据结构
1.2 基本概念和术语
1.3 抽象数据类型的表示与实现
1.4 算法和算法分
1.4.1 算法
1.4.2 算法设计的要求
1.4.3 算法效率的度量
1.4.4 算法的存储空间的需求
第一章 绪 论
? 计算机是一门研究用计算机进行信息表示和处
理的科学。这里面涉及到两个问题：
? 信息的表示
信息的处理
而信息的表示和组又直接关系到处理信息的
程序的效率。随着计算机的普及，信息量的增
加，信息范围的拓宽，使许多系统程序和应用
程序的规模很大，结构又相当复杂。因此，为
了编写出一个“好”的程序，必须分析待处理
的对象的特征及各对象之间存在的关系，这就
是数据结构这门课所要研究的问题。
? 1.1什么是数据结构
? 众所周知，计算机的程序是对信息进行加工处理。
在大多数情况下，这些信息并不是没有组织，信息
（数据）之间往往具有重要的结构关系，这就是数据
结构的内容。那么，什么是数据结构呢？先看以下几
个例子。
? 例 1、电话号码查询系统
? 设有一个电话号码薄，它记录了 N个人的名字和其
相应的电话号码，假定按如下形式安排：
? (a1,b1)(a2,b2)…(a n,bn)
? 其中 ai,bi(i=1,2…n) 分别表示某人的名字和对应的电
话号码要求设计一个算法，当给定任何一个人的名字
时，该算法能够打印出此人的电话号码，如果该电话
簿中根本就没有这个人，则该算法也能够报告没有这
个人的标志。
? 算法的设计，依赖于计算机如何存储人的
名字和对应的电话号码，或者说依赖于名字和
其电话号码的结构。
? 数据的结构，直接影响算法的选择和效率。
? 上述的问题是一种数据结构问题。可将名
字和对应的电话号码设计成：二维数组、表结
构、向量。
假定名字和其电话号码逻辑上已安排成 N
元向量的形式，它的每个元素是一个数对 (ai，
bi),1≤i≤n
数据结构还要提供每种结构类型所定义的
各种运算的算法。
例 2、图书馆的书目检索系统自动化问题
例 3、教师资料档案管理系统
例 4、多叉路口交通灯的管理问题
P3
通过以上几例可以直接地认为：数据结构
就是研究数据的逻辑结构和物理结构以及它们
之间相互关系，并对这种结构定义相应的运算，
而且确保经过这些运算后所得到的新结构仍然
是原来的结构类型。
? 1.2 基本概念和术语
? 数据 (Data):是对信息的一种符号表示。在计
算机科学中是指所有能输入到计算机中并被
计算机程序处理的符号的总称。
? 数据元素 (Data Element):是数据的基本单位，
在计算机程序中通常作为一个整体进行考虑
和处理。
? 一个数据元素可由若干个数据项组成。数
据项是数据的不可分割的最小单位。
? 数据对象 (Data Object)：是性质相同的数据元
素的集合。是数据的一个子集。
? 数据结构 (Data Structure)：是相互之间存在一
种或多种特定关系的数据元素的集合。
? 数据结构主要指逻辑结构和物理结构
? 数据之间的相互关系称为逻辑结构。通常分
为四类基本结构：
? 一,集合 结构中的数据元素除了同属于一种
类型外，别无其它关系。
? 二,线性结构 结构中的数据元素之间存在一
对一的关系。
? 三,树型结构 结构中的数据元素之间存在
一对多的关系。
? 四,图状结构或网状结构 结构中的数据元素
之间存在多对多的关系。
?
数据结构的形式定义为：数据结构是一个二元
组：
Data-Structure=(D,S)
其中,D是数据元素的有限集,S是 D上关系的
有限集。
例 复数的数据结构定义如下：
Complex=(C,R)
其中,C是含两个实数的集合 ﹛ C1,C2﹜,分
别表示复数的实部和虚部。 R={P},P是定义在
集合上的一种关系 {〈 C1,C2〉 }。
数据结构在计算机中的表示称为数据的 物理结
构,又称为 存储结构 。
? 数据对象可以是有限的，也可以是无限的。
? 数据结构不同于数据类型，也不同于数据对
象，它不仅要描述数据类型的数据对象，而且
要描述数据对象各元素之间的相互关系。
? 抽象数据类型：一个数学模型以及定义在该模
型上的一组操作。
? 抽象数据类型实际上就是对该数据结构的
定义。因为它定义了一个数据的逻辑结构以及
在此结构上的一组算法。
? 用三元组描述如下：
? （Ｄ，Ｓ，Ｐ）
? 数据结构在计算机中有两种不同的表示方法：
? 顺序表示和非顺序表示
? 由此得出两种不同的存储结构,顺序存储结
构和链式存储结构
? 顺序存储结构,用数据元素在存储器中的相对
位置来表示数据元素之间的逻辑关系 。
? 链式存储结构,在每一个数据元素中增加一
个存放地址的指针（ ），用此指针来表示数
据元素之间的逻辑关系。
? 数据类型,在一种程序设计语言中，变量所具
有的数据种类。
? 例 1,在 FORTRAN语言中，变量的数据类型
有整型、实型、和复数型
? 例 2、在 C语言中
? 数据类型：基本类型和构造类型
? 基本类型：整型、浮点型、字符型
? 构造类型：数组、结构、联合、指针、枚举型、
自定义
? 数据对象,某种数据类型元素的集合。
? 例 3、整数的数据对象是 {… -3,-2,-1,0,1，
2,3,…}
? 英文字符类型的数据对象是 {A,B,C,D,E，
F,…}
? 1.3 抽象数据类型的表示和实现
? P11
? 1.4 算法和算法分析
? 算法,是对特定问题求解步骤的一种描述
? 算法是指令的有限序列，其中每一条指令
表示一个或多个操作。
? 算法具有以下五个特性：
? （ 1） 有穷性 一个算法必须总是在执行有穷步
之后结束，且每一步都在有穷时间内完成。
? （ 2） 确定性 算法中每一条指令必须有确切的
含义。不存在二义性。且算法只有一个入口和
一个出口。
? （ 3） 可行性 一个算法是可行的。即算法描述
的操作都是可以通过已经实现的基本运算执行
有限次来实现的。
? 4） 输入 一个算法有零个或多个输入，这些输
入取自于某个特定的对象集合。
? 5） 输出 一个算法有一个或多个输出，这些输
出是同输入有着某些特定关系的量。
? 1.4.2 算法设计的要求
? 评价一个好的算法有以下几个标准,
? (1) 正确性 (Correctness ) 算法应满足具体问题
的需求。
? (2)可读性 (Readability) 算法应该好读。以有利
于阅读者对程序的理解。
(3)健状性 (Robustness) 算法应具有容错处理。
当输入非法数据时，算法应对其作出反应，而
不是产年莫名其妙的输出结果。
? (4)效率与存储量需求 效率指的是算法执行的
时间；存储量需求指算法执行过程中所需要的
最大存储空间。一般，这两者与问题的规模有
关。
? 1.4.3 算法效率的度量
? 对一个算法要作出全面的分析可分成两用人
才个阶段进行，即 事先分析 和 事后测试
? 事先分析 求出该算法的一个时间界限函数
? 事后测试 收集此算法的执行时间和实际占用
空间的统计资料。
? 定义：如果存在两个正常数 c和 n0，对于所有的
n≧ n0，有 ︱ f(n) ︳ ≦ c｜ g(n) ︳
? 则记作 f(n)=O(g(n))
一般情况下，算法中基本操作重复执行的
次数是问题规模 n的某个函数，算法的时
间量度记作
T(n)=O(f(n))
称作算法的渐近时间复杂度。
例１,for(I=1,I<=n;++I)
for(j=1;j<=n;++j)
{
c[I][j]=0;
for(k=1;k<=n;++k)
c[I][j]+=a[I][k]*b[k][j];
}
? 由于是一个三重循环，每个循环从 1到 n，则总
次数为, n× n× n=n3
? 时间复杂度为 T(n)=O(n3)
? 频度,是指该语句重复执行的次数
? 例２ {++x;s=0;}
? 将 x自增看成是基本操作，则语句频度为１，
即时间复杂度为Ｏ (1)
? 如果将 s=0也看成是基本操作，则语句频度为
２，其时间复杂度仍为Ｏ (1)，即常量阶。
? 例３,for(I=1;I<=n;++I)
? {++x;s+=x;}
? 语句频度为,2n 其时间复杂度为,O(n)
? 即时间复杂度为线性阶。
? 例４,for(I=1;I<=n;++I)
? for(j=1;j<=n;++j)
? {++x;s+=x;}
? 语句频度为,2n2
? 其时间复杂度为,O(n2)
? 即时间复杂度为平方阶。
? 定理：若 A(n)=a m n m +a m-1 n m-1 +…+a 1n+a0是
一个 m次多项式，则 A(n)=O(n m)
证略。
例５ for(i=2;i<=n;++I)
for(j=2;j<=i-1;++j)
{++x;a[i,j]=x;}
? 语句频度为：
? 1+2+3+…+n -2=(1+n-2) × (n-2)/2
? =(n-1)(n-2)/2
? =n2-3n+2
? ∴ 时间复杂度为 O(n2)
? 即此算法的时间复杂度为平方阶,
? 一个算法时间为 O(1)的算法，它的
基本运算执行的次数是固定的。因此，
总的时间由一个常数（即零次多项式）
来限界。而一个时间为 O(n2)的算法则由
一个二次多项式来限界。
?
? 以下六种计算算法时间的多项式是最常
用的。其关系为：
? O(1)<O(logn)<O(n)<O(nlogn)
? <O(n2)<O(n3)
? 指数时间的关系为：
? O(2n)<O(n!)<O(nn)
? 当 n取得很大时，指数时间算法和多项
式时间算法在所需时间上非常悬殊。因
此，只要有人能将现有指数时间算法中
的任何一个算法化简为多项式时间算法，
那就取得了一个伟大的成就。
? 有的情况下，算法中基本操作重复执行的次数
还随问题的输入数据集不同而不同。例如：
? Void bubble-sort(int a[],int n)
? for(I=n-1;change=TURE;I>1 && change;--I)
? {
? change=false;
? for(j=0;j<I;++j)
? if (a[j]>a[j+1]) {
? a[j] ←→a[j+1];
? change=TURE}
? }
? 最好情况,0次
?
? 最坏情况,1+2+3+…+n -1
? =n(n-1)/2
? 平均时间复杂度为,O(n2)
? 1.4.4算法的存储空间需求
? 空间复杂度,算法所需存储空间的度量，
记作,
? S(n)=O(f(n))
? 其中 n为问题的规模 (或大小 )
第二章 线性表
? 2.1 线性表的类型定义
? 2.2 线性表的顺序表示和实现
? 2.3 线性表的链式表示和实现
? 2.3.1 线性链表
2.3.2 循环链表
2.3.3 双向链表
2.4 一元多项式的表示及相加
? 2.1 线性表的逻辑结构
? 线性表 (Linear List),由 n(n≧ )个数据元素 (结
点 )a1,a2,…a n组成的有限序列。其中数据元
素的个数 n定义为表的长度。当 n=0时称为空表，
常常将非空的线性表 (n>0)记作：
? (a1,a2,…a n)
? 这里的数据元素 ai(1≦ i≦ n)只是一个抽象的符
号，其具体含义在不同的情况下可以不同。
? 例 1,26个英文字母组成的字母表
? （ A,B,C,…, Z）
? 例 2、某校从 1978年到 1983年各种型号的计算
机拥有量的变化情况。
? （ 6,17,28,50,92,188）
例 3、学生健康情况登记表如下：
姓 名 学 号 性 别 年龄 健康情况
王小林 790631 男 18 健康
陈 红 790632 女 20 一般
刘建平 790633 男 21 健康
张立立 790634 男 17 神经衰弱
…….,…….,……,……,…….
? 例 4、一副扑克的点数
? （ 2,3,4,…, J,Q,K,A）
从以上例子可看出线性表的逻辑特征是：
? 在非空的线性表，有且仅有一个开始结点 a1，
它没有直接前趋，而仅有一个直接后继 a2；
? 有且仅有一个终端结点 an，它没有直接后继，
而仅有一个直接前趋 a n-1；
? 其余的内部结点 ai(2≦ i≦ n-1)都有且仅有一个
直接前趋 a i-1和一个直接后继 a i+1。
线性表是一种典型的线性结构。
? 数据的运算是定义在逻辑结构上的，而运算
的具体实现则是在存储结构上进行的。
? 抽象数据类型的定义为,P19
算法 2.1
? 例 2-1 利用两个线性表 LA和 LB分别表示两个集
合 A和 B，现要求一个新的集合 A=A∪ B。
void union(List &La,List Lb) {
La-len=listlength(La);
Lb-len=listlength(Lb);
for(I=1;I<=lb-len;I++) {
getelem(lb,I,e);
if(!locateelem(la,e,equal))listinsert(la，
++la-en,e)
}
}
?
? 算法 2.2
? 例 2-2 巳知线性表 LA和线性表 LB中的数
据元素按值非递减有序排列，现要求将
LA和 LB归并为一个新的线性表 LC，且
LC中的元素仍按值非递减有序排列。
? 此问题的算法如下：
void mergelist(list la,list lb,list &lc)
initlist(lc);
I=j=1;k=0;
la-len=listlength(la);
lb-len=listlength(lb);
while((I<=la-len)&&(j<=lb-len)){
? getelem(la,I,ai);getelem(lb,j,bj);
? if(ai<=bj){listinsert(lc,++k,ai);++I;}
else{listinsert(lc,++k,bj);++j;}
}
while(I<=la-len){
getelem((la,I++,ai);listinsert(lc，
++k,ai);
}
while(j<=lb-len){
getelem((lb,j++,bj);listinsert(lc，
++k,bi);
}
? 2.2 线性表的顺序存储结构
? 2.2.1 线性表
把线性表的结点按逻辑顺序依次存放在一组
地址连续的存储单元里。用这种方法存储的线
性表简称顺序表。
假设线性表的每个元素需占用 l个存储单元，
并以所占的第一个单元的存储地址作为数据元
素的存储位置。则线性表中第 I+1个数据元素
的存储位置 LOC( a i+1)和第 i个数据元素的存储
位置 LOC(a I )之间满足下列关系：
LOC(a i+1)=LOC(a i)+l
线性表的第 i个数据元素 ai的存储位置为：
LOC(ai)=LOC(a1)+(I-1)*l
? 由于 C语言中的一维数组也是采用顺序存储
表示，故可以用数组类型来描述顺序表。
又因为除了用数组来存储线性表的元素之
外，顺序表还应该用一个变量来表示线性
表的长度属性，所以我们用结构类型来定
义顺序表类型。
? # define ListSize 100
? typedef int DataType;
? typedef struc{
? DataType data[ListSize];
? int length;
? } Sqlist;
? 2.2.2 顺序表上实现的基本操作
在顺序表存储结构中，很容易实现线
性表的一些操作，如线性表的构造、第 i
个元素的访问。
注意,C语言中的数组下标从,0‖开始，
因此，若 L是 Sqlist类型的顺序表，则表
中第 i个元素是 l.data[I-1]。
以下主要讨论线性表的插入和删除
两种运算。
1、插入
线性表的插入运算是指在表的第
I(1≦ i≦ n+1个位置上，插入一个新结点 x，
使长度为 n的线性表
(a1,…a i-1,ai,…, an)
变成长度为 n+1的线性表
(a1,…a i-1,x,ai,…, an)
算法 2.3
? Void InsertList(Sqlist*L,DataType x,int
I)
? {
? int j;
? if(I<1 || I>l.length+1)
? printf(―Position error‖);
return ERROR
? if(l.length>=ListSize)
? printf(―overflow‖);
? exit(overflow);
? for(j=l.length-1;j>=I-1;j--)
? l.data[j+1]=l.data[j];
? l.data[I-1]=x;
? l.length++;
? }
? 现在分析算法的复杂度。
? 这里的问题规模是表的长度，设它的
值为。该算法的时间主要化费在循环的
结点后移语句上，该语句的执行次数
（即移动结点的次数）是。由此可看出，
所需移动结点的次数不仅依赖于表的长
度，而且还与插入位置有关。
? 当时，由于循环变量的终值大于初值，
结点后移语句将不进行；这是最好情况，
其时间复杂度 O（ 1）；
? 当 =1时，结点后移语句将循环执行 n次，
需移动表中所有结点，这是最坏情况，
? 其时间复杂度为 O（ n）。
? 由于插入可能在表中任何位置上进行，因
此需分析算法的平均复杂度
在长度为 n的线性表中第 i个位置上插入一
个结点，令 Eis(n)表示移动结点的期望值（即移
动的平均次数），则在第 i个位置上插入一个结
点的移动次数为 n-I+1。故
Eis(n)= pi(n-I+1)
不失一般性，假设在表中任何位置 (1≦ i≦ n+1)
上插入结点的机会是均等的，则
p1=p2=p3=…=p n+1=1/(n+1)
因此，在等概率插入的情况下，
Eis(n)= (n-I+1)/(n+1)=n/2
也就是说，在顺序表上做插入运算，平均要移
动表上一半结点。当表长 n较大时，算法的效
率相当低。虽然 Eis(n)中 n的的系数较小，但就
数量级而言，它仍然是线性阶的。因此算法的
平均时间复杂度为 O(n)。
2、删除
线性表的删除运算是指将表的第
i(1≦ i≦ n)结点删除，使长度为 n的线性表：
(a1,…a i-1,ai,a i+1…, an)
变成长度为 n-1的线性表
(a1,…a i-1,a i+1,…, an)
Void deleteList(Sqlist*L,int I)
{
int j;
if(I<1 || I>l.length)
printf(―Position error‖);
return ERROR
for(j=i;j<=l.length-1;j++)
l.data[j-1]=l.data[j];
l.length--;
}
? 该算法的时间分析与插入算法相似，结点的移
动次数也是由表长 n和位置 i决定。
? 若 I=n，则由于循环变量的初值大于终值，
前移语句将不执行，无需移动结点；
? 若 I=1，则前移语句将循环执行 n-1次，需移
动表中除开始结点外的所有结点。这两种情况
下算法的时间复杂度分别为 O(1)和 O(n)。
? 删除算法的平均性能分析与插入算法相似。
在长度为 n的线性表中删除一个结点，令 Ede(n)
表示所需移动结点的平均次数，删除表中第 i个
结点的移动次数为 n-i，故
Ede(n)= pi(n-I)
? 式中,pi表示删除表中第 i个结点的概率。在等
? 概率的假设下，
p1=p2=p3=…=p n=1/n
由此可得：
Ede(n)= (n-I)/n=(n-1)/2
即在顺序表上做删除运算，平均要移动表中约
一半的结点，平均时间复杂度也是 O(n)。
2.3 线性表的链式表示和实现
线性表的顺序表示的特点是用物理位置上的
邻接关系来表示结点间的逻辑关系，这一特点
使我们可以随机存取表中的任一结点，但它也
使得
插入和删除操作会移动大量的结点,为避免大量结
点的移动，我们介绍线性表的另一种存储方式，
链式存储结构，简称为链表 (Linked List)。
2.3.1 线性链表
链表是指用一组任意的存储单元来依次
存放线性表的结点，这组存储单元即可以是连续
的，也可以是不连续的，甚至是零散分布在内存
中的任意位臵上的。因此，链表中结点的逻辑次
序和物理次序不一定相同。为了能正确表示结点
间的逻辑关系，在存储每个结点值的同时，还必
须存储指示其后继结点的地址（或位臵）信息，
这个信息称为指针 (pointer)或链 (link)。这两
部分组成了链表中的结点结构：
其中,data域是数据域，用来存放结点的值。
next是指针域（亦称链域），用来存放结点的直接
后继的地址（或位臵）。链表正是通过每个结点的
链域将线性表的 n个结点按其逻辑次序链接在一起的。
由于上述链表的每一个结只有一个链域，故将这种
链表称为单链表（ Single Linked)。
显然，单链表中每个结点的存储地址是存
放在其前趋结点 next域中，而开始结点无前趋，故
应设头指针 head指向开始结点。同时，由于
终端结点无后继，故终端结点的指针域为空，即
null（图示中也可用 ^表示 )。
例 1、线性表,(bat,cat,eat,fat,hat,jat，
lat,mat)
data link
的单链表示意图如下：
……
110
……
130
135
……
160
头指针 head 165
170
……
200
205
……
……
…
……
hat 200
……, ……
cat 135
eat 170
…, ……
mat Null
bat 130
fat 110
…… ……
jat 205
lat 160
…… ……
165
? head
bat cat eat mat ^ …
单链表是由表头唯一确定，因此单链表可以用头
指针的名字来命名。
例如：若头指针名是 head，则把链表称为表 head。
用 C语言描述的单链表如下：
Typedef char datatype;
Typedef struct node{
datatype data;
struct node *next;
}listnode;
typedef listnode *linklist;
listnode *p;
linklist head;
注意区分指针变量和结点变量这两个不同的概念。
P为动态变量，它是通过标准函数生成的，即
p=(listnode*)malloc(sizeof(listnode));
函数 malloc分配了一个类型为 listnode的结点变量
的空间，并将其首地址放入指针变量 p中。一
旦 p所指的结点变量不再需要了，又可通过标
准函数
free(p)
释放所指的结点变量空间。
? 指针变量 P和（其值为结点地址）和结点变量
*P之间的关系。
一、建立单链表
假设线性表中结点的数据类型是字符，我们
逐个输入这些字符型的结点，并以换行符‘ \n‘
为输入结束标记。动态地建立单链表的常用方
法有如下两种：
1、头插法建表
该方法从一个空表开始，重复读入数据，
生成新结点，将读入数据存放到新结点的数据
域中，然后将新结点插入到当前链表的表头上，
直到读入结束标志为止。
linklist createlistf(void)
{
char ch;
linklist head;
listnode *p;
head=null;
ch=getchar( );
while (ch!=‵ \n′{
p=(listnode*)malloc(sizeof(listnode));
p–>data=ch;
p–>next=head;
head=p;
ch=getchar( );
}
return (head);
}
listlink createlist(int n)
{ int data;
linklist head;
listnode *p
head=null;
for(i=n;i>0;--i){
p=(listnode*)malloc(sizeof(listnode));
scanf((〝 %d〞, &p–>data);
p–>next=head;
head=p;
}
return(head);
}
2、尾插法建表
头插法建立链表虽然算法简单，但生成的
链表中结点的次序和输入的顺序相反。若希望
二者次序一致，可采用尾插法建表。该方法是
将新结点插入到当前链表的表尾上，为此必须
增加一个尾指针 r，使其始终指向当前链表的
尾结点。例：
linklist creater( )
{
char ch;
linklist head;
listnode *p,*r; //(,*head;)
head=NULL;r=NULL;
while((ch=getchar( )!=‵ \n′){
p=(listnode *)malloc(sizeof(listnode));
p–>data=ch;
if(head=NULL)
head=p;
else
r–>next=p;
r=p;
}
if (r!=NULL)
r–>next=NULL;
return(head);
}
说明：第一个生成的结点是开始结点，将开始结
点插入到空表中，是在当前链表的第一个位臵
上插入，该位臵上的插入操作和链表中其它位
臵上的插入操作处理是不一样的，原因是开始
结点的位臵是存放在头指针（指针变量）中，
而其余结点的位臵是在其前趋结点的指针域中。
算法中的第一个 if语句就是用来对第一个位臵
上的插入操作做特殊处理。算法中的第二个 if
语句的作用是为了分别处理空表和非空表两种
不同的情况，若读入的第一个字符就是结束标
志符，则链表 head是空表，尾指针 r亦为空，结
点 *r不存在；否则链表 head非空，最后一个尾
结点 *r是终端结点，应将其指针域臵空。
如果我们在链表的开始结点之前附加一个
结点，并称它为 头结点,那么会带来以下两个
优点：
a、由于开始结点的位臵被存放在头结点的指
针域中，所以在链表的第一个位臵上的操作就
和在表的其它位臵上的操作一致，无需进行特
殊处理；
b、无论链表是否为空，其头指针是指向头结点
在的非空指针（空表中头结点的指针域为空），
因此空表和非空表的处理也就统一了。
其算法如下：
linklist createlistr1( ){
char ch;
linklist
head=(linklist)malloc(sizeof(listnode));
listnode *p,*r
r=head;
while((ch=getchar( ))!=‵ \n′{
p=(listnode*)malloc(sizeof(listnode));
p–>data=ch;
p–>next=p;
r=p;
}
r–>next=NULL;
return(head);
}
上述算法里动态申请新结点空间时未加错误处理，
可作下列处理：
p=(listnode*)malloc(sizeof(listnode))
if(p==NULL)
error(〝 No space for node can be obtained〞 );
return ERROR;
以上算法的时间复杂度均为 O(n)。
二、查找运算
1、按序号查找
在链表中，即使知道被访问结点的序号 i，
也不能象顺序表中那样直接按序号 i访问结点，
而只能从链表的头指针出发，顺链域 next逐个
结点往下搜索，直到搜索到第 i个结点为止。
因此，链表不是随机存取结构。
设单链表的长度为 n，要查找表中第 i个结
点，仅当 1≦ i≦ n时,i的值是合法的。但有时
需要找头结点的位臵，故我们将头结点看做是
第 0 个结点，其算法如下：
Listnode * getnode(linklist head, int i)
{
int j;
listnode * p;
p=head;j=0;
while(p–>next && j<I){
p=p–>next;
j++;
}
if (i==j)
return p;
else
return NULL;
}
2、按值查找
按值查找是在链表中，查找是否有结点值等
于给定值 key的结点，若有的话，则返回首次
找到的其值为 key的结点的存储位臵；否则返
回 NULL。查找过程从开始结点出发，顺着链表
逐个将结点的值和给定值 key作比较。其算法
如下：
Listnode * locatenode(linklist head,int key)
{
listnode * p=head–>next;
while( p && p–>data!=key)
p=p–>next;
return p;
}
该算法的执行时间亦与输入实例中的的取值
key有关，其平均时间复杂度的分析类似于按
序号查找，也为 O(n)。
三、插入运算
插入运算是将值为 x的新结点插入
到表的第 i个结点的位臵上，即插入到 ai-
1与 ai之间。因此，我们必须首先找到 ai-1
的存储位臵 p，然后生成一个数据域为 x
的新结点 *p，并令结点 *p的指针域指向
新结点，新结点的指针域指向结点 ai。
从而实现三个结点 ai-1,x和 ai之间的逻辑
关系的变化，插入过程如：
具体算法如下：
void insertnode(linklist head,datetype x,int i)
{
listnode * p,*q;
p=getnode(head,i-1);
if(p==NULL)
error(〝 position error〞 );
q=(listnode *)malloc(sizeof(listnode));
q–>data=x;
q–>next=p–next;
p–>next=q;
}
设链表的长度为 n，合法的插入位臵是 1≦ i≦ n+1。
注意当 i=1时,getnode找到的是头结点，当
i=n+1时,getnode找到的是结点 an。因此，用 i-1
做实参调用 getnode时可完成插入位臵的合法性
检查。算法的时间主要耗费在查找操作 getnode
上，故时间复杂度亦为 O(n)。
四、删除运算
删除运算是将表的第 i个结点删去。因为在单
链表中结点 ai的存储地址是在其直接前趋结点 a
a i-1的指针域 next中，所以我们必须首先找到
a i-1的存储位臵 p。然后令 p–>next指向 ai的直接
后继结点，即把 ai从链上摘下。最后释放结点 ai
的空间，将其归还给“存储池”。此过程为：
具体算法如下,
void deletelist(linklist head,int i)
{
listnode * p,*r;
p=getnode(head,i-1);
if(p= =NULL || p–>next= =NULL)
return ERROR;
r=p–>next;
p–>next=r–>next;
free( r ) ;
}
设单链表的长度为 n，则删去第 i个结点仅
当 1≦ i≦ n时是合法的。注意，当 i=n+1时，
虽然被删结点不存在，但其前趋结点却存在，
它是终端结点。因此被删结点的直接前趋 *p
存在并不意味着被删结点就一定存在，仅当
*p存在（即 p!=NULL）且 *p不是终端结点
（即 p–>next!=NULL）时，才能确定被删结
点存在。
显然此算法的时间复杂度也是 O(n)。
从上面的讨论可以看出，链表上实现插入
和删除运算，无须移动结点，仅需修改指针。
2.3.2 循环链表
循环链表时一种头尾相接的链表。其特点
是无须增加存储量，仅对表的链接方式稍
作改变，即可使得表处理更加方便灵活 。
单循环链表,在单链表中，将终端结点的指
针域 NULL改为指向表头结点的或开始结
点，就得到了单链形式的循环链表，并简
单称为单循环链表。
为了使空表和非空表的处理一致，循环
链表中也可设臵一个头结点。这样，空循
环链表仅有一个自成循环的头结点表示。
如下图所示：
a1 an….head
⑴ 非空表
⑵ 空表
在用头指针表示的单链表中，找开始结点 a1
的时间是 O(1)，然而要找到终端结点 an，则需
从头指针开始遍历整个链表，其时间是 O(n)
在很多实际问题中，表的操作常常是在
表的首尾位臵上进行，此时头指针表示的
单循环链表就显得不够方便,如果改用尾指
针 rear来表示单循环链表，则查找开始结点
a1和终端结点 an都很方便，它们的存储位臵
分别是 (rear–>next) —>next和 rear，显然，
查找时间都是 O(1)。因此，实际中多采用尾
指针表示单循环链表。
由于循环链表中没有 NULL指针，故涉及
遍历操作时，其终止条件就不再像非循环
链表那样判断 p或 p—>next是否为空，而是
判断它们是否等于某一指定指针，如头指
什或尾指针等。
例、在链表上实现将两个线性表 (a1,a2，
a3,…a n)和 (b1,b2,b3,…b n)链接成一个线
性表的运算。
linklist connect(linklist heada,linklist headb)
{
linklist p=heada—>next;
heada—>next=(headb—next)—>next
free(headb—>next);
headb—>next=p;
return(headb);
}
2.3.3双链表
双向链表 (Double linked list):在单链表
的每个结点里再增加一个指向其直接前趋
的指针域 prior。这样就形成的链表中有两
个方向不同的链，故称为双向链表。形式
描述为：
typedef struct dlistnode{
datatype data;
struc dlistnode *prior,*next;
}dlistnode;
typedef dlistnode * dlinklist;
dlinklist head;
和单链表类似，双链表一般也是由头指
针唯一确定的，增加头指针也能使双链表
上的某些运算变得方便，将头结点和尾结
点链接起来也能构成循环链表，并称之为
双向链表。
设指针 p指向某一结点，则双向链表结构
的对称性可用下式描述：
(p—>prior)—>next=p=(p—>next)—>prior
即结点 *p的存储位臵既存放在其前趋结点
*(p—>prior)的直接后继指针域中，也存放
在它的后继结点 *(p—>next)的直接前趋指
针域中。
双向链表的前插操作算法如下：
void dinsertbefor(dlistnode *p,datatype x)
{
dlistnode *q=malloc(sizeof(dlistnode));
q—>data=x;
q—>prior=p—>prior;
q—>next=p;
p—>prior—>next=q;
p—>prior=q;
}
void ddeletenode(dlistnode *p)
{
p–>prior–>next=p–>next;
p–>next–>prior=p–>prior;
free(p);
}
注意：与单链表的插入和删除操作不同的
是，在双链表中插入和删除必须同时修改
两个方向上的指针。上述两个算是法的时
间复杂度均为 O(1)。
第三章 栈和队列
3.1 栈
3.1.1 抽象数据类型栈的定义
3.1.2 栈的表示和实现
3.2 栈的应用举例
3.2.1 数制转换
3.2.2 括号匹配的检验
3.2.4 行编辑程序
3.2.5 迷宫求解
3.2.5 表达式求值
3.1.1 栈
3.1.1 栈的定义及基本运算
栈 (Stack)是限制在表的一端进行插入和删
除运算的线性表，通常称插入、删除的这一
端为栈顶 (Top)，另一端为栈底 (Bottom)。当
表中没有元素时称为空栈。
假设栈 S=(a1,a2,a3,…a n)，则 a1称为栈
底元素,an为栈顶元素。栈中元素按 a1,a2，
a3,…a n的次序进栈，退栈的第一个元素应
为栈顶元素。换句话说，栈的修改是按后进
先出的原则进行的。因此，栈称为后进先出
表（ LIFO）。
3.1.2 顺序栈
由于栈是运算受限的线性表，因此线性
表的存储结构对栈也适应。
栈的顺序存储结构简称为顺序栈，它是
运算受限的线性表。因此，可用数组来实
现顺序栈。因为栈底位臵是固定不变的，
所以可以将栈底位臵设臵在数组的两端的
任何一个端点；栈顶位臵是随着进栈和退
栈操作而变化的，故需用一个整型变量 top
例、一叠书或一叠盘子。
栈的抽象数据类型的定义如下,P44
a n
a n-1
a2
a1
……
栈顶
栈底
top
7
6
5
4
3
2
1
-1
来指示当前栈顶的位臵，通常称 top为栈顶指
针。因此，顺序栈的类型定义只需将顺序
表的类型定义中的长度属性改为 top即可。
顺序栈的类型定义如下：
# define StackSize 100
typedef char datatype;
typedef struct {
datatype data[stacksize];
int top;
}seqstack;
设 S是 SeqStack类型的指针变量。若栈
底位臵在向量的低端，即 s–>data[0]是栈
底元素，那么栈顶指针 s–>top是正向增加
的，即进栈时需将 s–>top加 1，退栈时需将
s–>top 减 1。因此,s–>top<0表示空栈,s–
>top =stacksize-1表示栈满。当栈满时再做
进栈运算必定产生空间溢出，简称“上
溢” ;当栈空时再做退栈运算也将产生溢出，
简称“下溢”。上溢是一种出错状态，应
该设法避免之；下溢则可能是正常现象，
因为栈在程序中使用时，其初态或终态都
是空栈，所以下溢常常用来作为程序控制
转移的条件。
3、判断栈满
int stackfull(seqstack *s)
{
return(s–>top==stacksize-1);
}
4、进栈
void push(seqstack *s,datatype x)
{
if (stackfull(s))
error(―stack overflow‖);
s–>data[++s–>top]=x;
}
1、臵空栈
void initstack(seqstack *s)
{
s–>top=-1;
}
2、判断栈空
int stackempty(seqstack *s)
{
return(s–>top==-1);
}
5、退栈
datatype pop(seqstack *s)
{
if(stackempty(s))
error(―stack underflow‖);
x=s–>data[top];
s–>top--;
return(x)
//return(s–>data[s–>top--]);
}
6、取栈顶元素
Datatype stacktop(seqstack *s)
{
if(stackempty(s)
error(―stack is enpty‖);
return s–>data[s–>top];
}
3.1.3 链栈
栈的链式存储结构称为链栈，它是运算是
受限的单链表，克插入和删除操作仅限制
在表头位臵上进行,由于只能在链表头部进
行操作，故链表没有必要像单链表那样附
加头结点。栈顶指针就是链表的头指针。
链栈的类型说明如下：
typedef struct stacknode{
datatype data
struct stacknode *next
}stacknode;
Void initstack(seqstack *p)
{
p–>top=null;
}
int stackempty(linkstack *p)
{
return p–>top==null;
}
? Void push(linkstack *p,datatype x)
{
stacknode *q
q=(stacknode*)malloc(sizeof(stacknode));
q–>data=x;
q–>next=p–>top;
p–>top=p;
}
Datatype pop(linkstack *p)
{
datatype x;
stacknode *q=p–>top;
if(stackempty(p)
error(―stack underflow.‖);
x=q–>data;
p–>top=q–>next;
free(q);
return x;
}
datatype stack top(linkstack *p)
{
if(stackempty(p))
error(―stack is empty.‖);
return p–>top–>data;
}
3.2 栈的应用举例
由于栈结构具有的后进先出的固有特性，
致使栈成为程序设计中常用的工具。以下
是几个栈应用的例子。
3.2.1 数制转换
十进制 N和其它进制数的转换是计算机
实现计算的基本问题,其解决方法很多,其中
一个简单算法基于下列原理,
N=(n div d)*d+n mod d
( 其中,div为整除运算,mod为求余运算 )
例如 (1348)10=(2504)8,其运算过程如下：
n n div 8 n mod 8
1348 168 4
168 21 0
21 2 5
2 0 2
void conversion( ) {
initstack(s);
scanf (―%‖,n);
while(n){
push(s,n%8);
n=n/8;
}
while(! Stackempty(s)){
pop(s,e);
printf(―%d‖,e);
}
}
3.2.2 括号匹配的检验
假设表达式中充许括号嵌套,则检验括号
是否匹配的方法可用, 期待的急迫程度, 这
个概念来描述。例：
（（）（） （（）））
3.2.3 行编辑程序
在编辑程序中，设立一个输入缓冲区，
用于接受用户输入的一行字符，然后逐行存
入用户数据区。允许用户输入错误，并在发
现有误时可以及时更正。
行编辑程序算法如下,
void lineedit( ){
initstack(s);
ch=gether( );
while(ch!=eof){
while(ch!=eof && ch!=?\n‘){
switch(ch){
case ?#‘, pop(s,c);
case ?@‘, clearstack(s);
default, push(s,ch);
}
ch=getchar( );
}
clearstack(s);
if(ch!=eof)
ch=gethar( );
}
destroystack(s);
}
3.2.4 迷宫求解
入口
出
口
3.4 队列
3.4.1 抽象数据类型队列的定义
队列 (Queue)也是一种运算受限的线性表。它只
允许在表的一端进行插入，而在另一端进行删除。
允许删除的一端称为队头 (front)，允许插入的一端
称为队尾 (rear)。
例如：排队购物。操作系统中的作业排队。先进
入队列的成员总是先离开队列。因此队列亦称作先
进先出 (First In First Out)的线性表，简称 FIFO
表。
当队列中没有元素时称为空队列。在空队列中依
次加入元素 a1,a2,… an之后,a1是队头元素,an是队
尾元素。显然退出队列的次序也只能是 a1,a2,… an,
也就是说队列的修改是依先进先出的原则进行的。
下图是队列的示意图：
a1 a2 … an出队 入队
队头 队尾
队列的抽象数据定义见书Ｐ 59
3.4.2 循环队列－队列的顺序表示和实现
队列的顺序存储结构称为顺序队列，顺序队
列实际上是运算受限的顺序表，和顺序表一样，
顺序队列也是必须用一个向量空间来存放当前队
列中的元素。由于队列的队头和队尾的位臵是变
化的，因而要设两个指针和分别指示队头和队尾
元素在队列中的位臵，它们的初始值地队列初始
化时均应臵为０。入队时将新元素插入所指的位
臵，然后将加１。出队时，删去所指的元素，然
后将加１并返回被删元素。由此可见，当头尾指
针相等时队列为空。在非空队列里，头指针始终
指向队头元素，而尾指针始终指向队尾元素的下
一位臵。
０ １ ２ ３ 0 1 2 3
Front
rear
a b c
Front rear
(a)队列初始为空 （ b） A,B,C入队
０ １ ２ ３ ０ １ ２ ３
b c
front rear front
rear
（ c) a出队 (d) b,c出队，队为空
和栈类似，队列中亦有上溢和下溢现象。此外，
顺序队列中还存在, 假上溢, 现象。因为在入队
和出队的操作中，头尾指针只增加不减小，致使
被删除元素的空间永远无法重新利用。因此，尽
管队列中实际的元素个数远远小于向量空间的规
模，但也可能由于尾指针巳超出向量空间的上界
而不能做入队操作。该现象称为假上溢。
为充分利用向量空间。克服上述假上溢现象的方法
是将向量空间想象为一个首尾相接的圆环，并称
这种向量为循环向量，存储在其中的队列称为循
环队列（ Circular Queue)。在循环队列中进行出
队、入队操作时，头尾指针仍要加 1，朝前移动。
只不过当头尾指针指向向量上界（ QueueSize-1）
时，其加 1操作的结果是指向向量的下界 0。
这种循环意义下的加 1操作可以描述为：
if(I+1==QueueSize)
i=0;
else
i++;
利用模运算可简化为, i=(i+1)%QueueSize
显然，因为循环队列元素的空间可以被利用，
除非向量空间真的被队列元素全部占用，否则不
会上溢。因此，除一些简单的应用外，真正实用
的顺序队列是循环队列。
如图所示：由于入队时尾指针向前追赶头指针，
出队时头指针向前追赶尾指针，故队空和队满时
头尾指针均相等。因此，我们无法通过 front=rear
来判断队列“空”还是“满”。
解决此问题的方法至少有三种：
其一是另设一个布尔变量以匹别队列的空和满；
其二是少用一个元素的空间，约定入队前，测试
尾指针在循环意义下加 1后是否等于头指针，若
相等则认为队满（注意,rear所指的单元始终为
空）；
其三是使用一个计数器记录队列中元素的总数
（实际上是队列长度）。下面我们用第三种方
法实现循环队列上的六种基本操作，为此先给
出循环队列的类型定义。
? #define QueueSize 100
? typedef char DataType;
? typedef Struct{
? int front;
? int rear;
? int count;
? datatype data[queuesize]
? }cirqueue;
（ 1）臵空队
void initqueue(cirqueue *q){
q–>front=q–>rear=0;
q–>count=0;
}
（ 2）判断队空
int queueempty(cirqueue *q) {
return q–>count==0;
}
（ 3）判断队满
int queuefull(cirqueue *q){
return q–>count==queuesize;
}
（ 4）入队
void enqueue(cirqueue *q,datatype x)
{
if(queuefull(q))
error(―queue overflow‖);
q–>count++;
q–data[q–rear]=x;
q–rear=(q–rear+1)%queuesize;
}
（ 5）出队
datatype dequeue(cirqueue *q)
{
datatype temp;
if(queueempty(q))
error(―queue underflow‖);
temp=q–>data[q–>front];
q–>count--;
q–front=(q–>front+1)%queuesize;
return temp;
}
（ 6）取头指针
datatype queuefront(cirqueue *q)
{
if(queueempty(q))
error(―queue is empty.‖);
return q–>data[q–>front];
}
? 3.4.3 链队列
? 队列的链式存储结构简称为链队列，它是
限制仅在表头删除和表尾插入的单链表。显然
仅有单链表的头指针不便于在表尾做插入操作，
为此再增加一个尾指针，指向链表的最后一个
结点。于是，一个链队列由一个头指针唯一确
定。和顺序队列类似，我们也是将这两个指针
封装在一起，将链队列的类型 LinkQueue定义
为一个结构类型：
? typedef struct queuenode{
? datatype data;
? struct queuenode *next;
? }queuenode;
typedef struct{
queuenode *front;
queuenode *rear;
}linkqueue;
下面给出链队列上实现的基本运算：
void initqueue(linkqueue *q)
{
q–>front=q–>rear=null;
}
int queueempty(linkqueue *q)
{
return q–>front==null &&q–>rear==null;
}
void enqueue(linkqueue *q,datatype x)
{
queuenode *p
p=(queuenode * )malloc(sizeof(queuenode));
p–>data=x;
p–next=null;
if(queueempty(q))
q–>front=q–>rear=p;
else{
q–>rear–>next=p;
q–rear=p;
}
}
Datatype dequeue(linkqueue *q)
{
datatype x;
queuenode *p
if(queueempty(q))
error(―queue underflow‖);
p=q–>front;
x=p–>data;
q–>front=p–>next;
if(q–>rear==p)
q–rear=null;
free(p);
return x;
}
datatype queuefront(linkqueue *q)
{
if(queueempty(q))
error(―queue is empty.‖);
return q–>front–>data;
}
注意：在出队算法中，一般只需修改队头指针。
但当原队中只有一个结点时，该结点既是队头
也是队尾，故删去此结点时亦需修改尾指针，
且删去此结点后队列变空。
习题
1、设将整数以万计,2,3,4依次进栈，但只要
出栈时栈非空，则可将出栈操作按任何次序夹
入其中，请回答下有问题：
（ 1）若入栈次序为 push(1),pop(),push(2，
push(3),pop(),pop( ),push(4),pop( )，
则出栈的数字序列为什么？
（ 2）能否得到出栈序列车员 423和平共处五项原
则 432？并说明为什么不能得到或如何得到。
（ 3）请分析 1,2,3,4的 24种排列中，哪些序
列可以通过相应的入出栈得到。
2、链栈中为何不设头指针？
3、循环队列的优点是什么？如何判断它的空和
满？
4、设长度为 n的链队列用单循环链表表示，若只
设头指针，则怎样进行入队和出队操作；若只
设尾指针呢？
5、利用栈的基本操作，写一个返回栈 s中结点个
数的算法 int stacksize(seqstack s)，并说明 s为何
不用作为指针参数？
6、利用栈的基本操作，写一个将栈中所有结点
均删除算法，并说明 S为何要作为指针参数？
7、用第二种方法，即少用一个元素空间的方法
来区别循环队列的队空和队满，试设计臵空队、
判队空、判队满、出队、入队及取队头元素等
六个基本操作。
8、假设循环队列只设 rear和 quelen来分别指示队
尾元素的位臵和队中元素的个数，试给出判断
此循环队列的队满条件，并写出相应的入队和
出队算法，要求出队时需返回队头指针。
9、指出下列程序段的功能是什么？
(1) void demo1(seqstack *s){
int I;arr[64];n=0;
while (!stackempty(s)) arr[n++]=pos(s);
for(I=0;<n;I++) push(s,arr[I]);
}
(2) void demo2(seqstack *s,int m){
seqstack t; int i;
initstack(t);
while(! Stackempty(s))
if(I=pop(s)!=m) push(t,I);
While(! Stackempty(t)) {
i=pop(t);
push(s,I);
}
}
第四章 串
? 4.1 串类型的定义
? 4.2 串的表示和实现
4.2.1 定长顺序存储表示
4.2.2 堆分配存储表示
4.2.3 串的块链存储表示
4.1 串类型的定义
一、串和基本概念
串 (String)是零个或多个字符组成的有限序列。
一般记作 S=―a1a2a3… an‖，其中 S 是串名，双引
号括起来的字符序列是串值； ai(1≦ i≦ n)可以
是字母、数字或其它字符；串中所包含的字符
个数称为该串的长度。长度为零的串称为空串
(Empty String)，它不包含任何字符。
通常将仅由一个或多个空格组成的串称为空白
串 (Blank String)
注意：空串和空白串的不同，例如,, 和,”
分别表示长度为 1的空白串和长度为 0的空串。
串中任意个连续字符组成的子序列称为该串的子
串，包含子串的串相应地称为主串。通常将子
串在主串中首次出现时的该子串的首字符对应
的主串中的序号，定义为子串在主串中的序号
（或位臵）。例如，设 A和 B分别为
A=―This is a string‖ B=―is‖
则 B是 A的子串,A为主串。 B在 A中出现了两次，
其中首次出现所对应的主串位臵是 3。因此，
称 B在 A中的序号（或位臵）为 3
特别地，空串是任意串的子串，任意串是
其自身的子串。
通常在程序中使用的串可分为两种：串变量
和串常量。串常量和整常数、实常数一样，在
程序中只能被引用但不能不能改变其值，即只能
读不能写。通常串常量是由直接量来表示的，
例如语句 Error(―overflow‖)中, overflow‖是
直接量。但有的语言允许对串常量命名，以使
程序易读、易写。如 C++中，可定义
const char path[]=―dir/bin/appl‖;
这里 path是一个串常量，对它只能读不能写。串
变量和其它类型的变量一样，其取值是可以改
变的。
二、串的抽象数据定义
串的抽象数据类型定义台书 P71
三、串的基本操作
对于串的基本操作，许多高级语言均提供了相
应的运算或标准库函数来实现。下面仅介绍
几种在 C语言中常用的串运算，其它的串操
作见的文件。
定义下列几个变量：
char s1[20]=―dirtreeformat‖,s2[20]=―file.mem‖;
char s3[30],*p;
int result;
(1) 求串长 (length)
int strlen(char s); //求串的长度
例如,printf(―%d‖,strlen(s1)); 输出 13
（ 2）串复制 (copy)
char *strcpy(char to,char from);
该函数将串 from复制到串 to中，并且返回一个
指向串 to的开始处的指针。
例如,strcpy(s3,s1); //s3=―dirtreeformat‖
(3)联接 (concatenation)
char strcat(char to,char from)
该函数将串 from复制到串 to的末尾，并且返回
一个指向串 to的开始处的指针。
例如,strcat(s3,‖/‖)
strcat(s3,s2); //s3=―dirtreeformat/file.mem‖
(4)串比较（ compare)
int strcmp(chars1,char s2);
该函数比较串 s1和串 s2的大小，当返回值小于 0，
等于 0或大于 0时分别表示 s1<s2\s1=s2或 s1>s2
例如,result=strcmp(―baker‖,‖Baker‖) result>0
result=strcmp(―12‖,‖12‖); result=0
result=strcmp(―Joe‖,‖Joseph‖); result<0
（ 5）字符定位 (index)
char strchr(char s,char c);
该函数是找 c在字符串中第一次出现的位臵，若
找到则返回该位臵，否则返回 NULL。
例如,p=strchr(s2,‖.‖); p 指向,file‖之后的位臵
if(p) strcpy(p,‖.cpp‖); s2=―file.cpp‖
上述串的操作是最基本的，其中后四个还有变种形式：
strncpy,strncat,strncmp,strnchr。串的其余操作可
由这些基本操作组合而成。
例 1、求子串
求子串的过程即为复制字符序列的过程，将串 S
中的第 pos个字符开始长度为 len的字符复制到串 T中。
void substr(string sub,string s,int pos,int len)
{
if(pos<0 || pos>strlen(s)-1 || len<0)
error(―parameter error‖)
strncpy(sub,&s[pos],len);
}
例 2、串的定位 index(s,t,pos)
在主串中取从第 i个字符起、长度和串 T
相等的子串和 T比较，若相等，则求得函数值
为 i，否则值增 1直至 S中不存在和串 T相等的子
串为止。
int index(string s,string t,int pos){
if(pos>0){
n=strlen(s); m=strlen(t); i=pos;
while(i<n-m+1){
substr(sub,s,i,m);
if(strcmp(sub,t)!=0)
++i;
else return(i);
}
}
return(0);
}
4.2 串的表现和实现
因为串是特殊的线性表，故其存储结构与线性
表的存储结构类似。只不过由于组成串的结点是
单个字符。串有三种机内表示方法，下面分别介
绍。
4.2.1定长顺序存储表示
定长顺序存储表示,也称为静态存储分配的顺应
表。它是用一组连续的存储单元来存放串中的字
符序列。所谓定长顺序存储结构，是直接使用定
长的字符数组来定义，数组的上界预先给出：
#define maxstrlen 256
typedef char sstring[maxstrlen];
sstring s; //s是一个可容纳 255个字符的
顺序串。
一般可使用一个不会出现在串中的特殊字符在串
值的尾部来表示串的结束。例如,C语言中以字符
‵ \0′ 表示串值的终结，这就是为什么在上述定义
中，串空间最大值 maxstrlen为 256，但最多只能存
放 255个字符的原因，因为必须留一个字节来存放
‵ \0′ 字符。若不设终结符，可用一个整数来表示
串的长度，那么该长度减 1的位臵就是串值的最后
一个字符的位臵。此时顺序串的类型定义和顺序表
类似：
typedef struct{
char ch[maxstrlen];
int length;
}sstring; //其优点是涉及到串长操作时速度
快。
4.2.2堆分配存储表示
这种存储表示的特点是，仍以一组地址连续的存储
单元存放串值字符序列，但它们的存储空间是在程
序执行过程中动态分配而得。所以也称为动态存储
分配的顺序表。在 C语言中，利用和等动态存储管理
函数，来根据实际需要动态分配和释放字符数组空
间。这样定义的顺序串类型也有两种形式。
typedef char *string; //c中的串库相当于此类型
定义
typedef struct{
char *ch;
int length;
}hsring;
status sinsert(hstring s,int pos,hstring t){
if(pos<1 || pos>s.length+1)
return error;
if(t.length){
if(!(s.ch=(char*)realloc(s.ch,(s.length+t.length
)*sizeof(char)))
exit(overflow);
for(i=s.length-1;i>pos-1;--i)
s.ch[I+t.length]=s.ch[i];
s.ch[pos-1..pos+t.length-
2]=t.ch[0..t.length-1];
s.length+=t.length;
}
return ok;
}
int strlen(hstring s){
return s.length;
}
status clearstring(hstring s){
if(s.ch){free(s.ch);s.ch=NULL;}
s.length=0;
}
status strassign(hstring t,char *chars){
//生成一个其值等于串常量 chars的串 t
if(t.ch) free(t.ch);
for(i=0,(c=chars;c;++i),++c);
if(!i) {
t.ch=null; t.length=0;
}
else{
if(!(t.ch=(char *)malloc(I*sizeof(char))))
exit(overflow);
t.ch[0..i-1]=chars[0..i-1];
t.length=i;
}
}
int strcmp(hstring s,hstring t){
for(i=0;i<s.length && i<t.length;++i)
if(s.ch[i]!=t.ch[i]
return(s.ch[i]-t.ch[i]);
return s.length-t.length;
}
status concat(hstring t,hstring s1,hstring s2){
if(!(t.ch)=(char*)malloc(s1.length+s2.length)*
sizeof(char)))
exit(overflow);
t.ch[0..s1.length-1]=s1.ch[0..s1.length-1];
t.length=s1.length+s2.length;
t.ch[s1.length..t.length-
1]=s2.ch[0..s2.length-1];
}
Status substr(hstring sub,hstring s,int pos,int
len){
if(pos<1 || pos>s.length || len<0 ||
len>s.length-pos+1)
return error;
if(sub.ch) free(sub.ch);
if(!len){
sub.ch=null;
sub.length=0;
}
else{
sub.ch=(char *)malloc(len*sizeof(char));
sub.ch[0..len-1]=s[pos-1..pos+len-2];
s.length=len;
}
}
4.2.3 串的链式存储结构
顺序串上的插入和删除操作不方便，需要
移动大量的字符。因此，我们可用单链表方式来
存储串值，串的这种链式存储结构简称为链串。
typedef struct node{
char data;
struct node *next;
}lstring;
一个链串由头指针唯一确定。
这种结构便于进行插入和删除运算，但存储空
间利用率太低。
为了提高存储密度，可使每个结点存放多个字符。
通常将结点数据域存放的字符个数定义为 结点
的大小,显然，当结点大小大于 1时，串的长
度不一定正好是结点的整数倍，因此要用特殊
字符来填充最后一个结点，以表示串的终结。
对于结点大小不为 1的链串，其类型定为义只
需对上述的结点类型做简单的修改即可。
#define nodesize 80
typedef struct node{
char data[nodesize];
struct node *next;
}lstring;
4.3 串的模式匹配算法
子串定位运算又称为模式匹配 (Pattern
Matching)或串匹配 (String Matching)，此运算
的应用在非常广泛。例如，在文本编辑程序中，
我们经常要查找某一特定单词在文本中出现的位
臵。显然，解此问题的有效算法能极大地提高文
本编辑程序的响应性能。
在串匹配中，一般将主串称为目标串，子串称
之为模式串。设 S为目标串,T为模式串，且不妨
设：
S=―s0s1s2… sn-1‖ T=―t0t1… tm-1‖
串的匹配实际上是对于合法的位臵 0≦ i≦ n-m依
次将目标串中的子串 s[i..i+m-1]和模式串
t[0..m-1]进行比较，若 s[i..i+m-1]=t[0..m-1]，
则称从位臵 i开始的匹配成功，亦称模式 t在目
标 s中出现；若 s[i..i+m-1] ≠t[0..m -1]，
，则称从位臵 i开始的匹配失败。上述的位臵 i
又称为位移，当 s[i..i+m-1]=t[0..m-1]时,i
称为有效位移；当 s[i..i+m-1] ≠t[0..m -1]时，
i称为无效位移。这样，串匹配问题可简化为是
找出某给定模式 T在一给定目标 T中首次出现的有
效位移。
串匹配的算法很多，这里我们只讨论一种最
简单的称为朴素的串匹配算法。其基本思想是用
一个循环来依次检查 n-m+1个合法的位移
i(0≦ i≦ n-m)是否为有效位移，
≠
其算法段为：
for(i=0;i<=n-m;i++){
if(S[i..i+m-1]=T[0..m-1]
return i;
下面以第二种 定长的顺序串类型 作为存储结
构，给出具体的串匹配算法。
int index(sstring s,sstring t,int pos){
int i,j,k;
int m=s.length;
int n=t.length;
for(i=0;i<=n-m;i++){
j=0;k=i;
while(j<m && s.ch[k]==t.ch[j]{
k++;j++;
}
if(j==m)
return i;
}
return –1;
}
显然，该算法在最坏情况下的时间复杂
度为 O((n-m)m)。
链串上的子串定位算法
用结点大小为 1的单链表做串的存储结构时，
实现朴素的匹配算法很简单。只是现在的位移
是结点地址而非整数，且单链表中没有存储长
度信息。若匹配成功，则返回有效位移所指的
结点地址，否则返回空指针。具体算法如下：
lstring *lindex(lstring s,lstring t){
lstring *shift,*q,*p;
shift=S;
q=shift;p=t;
while(q && p){
if(q->data==p->data){
q=q->next;
p=p->next;
}
else{
shift=shift->next;
q=shift;
p=t;
}
}
if(p==null)
return shift;
else
return null;
}
第五章 数组和广义表
? 5.1 数组的定义
? 5.2 数组的顺序表示和实现
? 5.3 矩阵的压缩存储
5.3.1 特殊矩阵
5.3.2 稀疏矩阵
5.4 广义表的定义
5.5 广义表的存储结构
数组和广义表可看成是一种特殊的线性表，其
特殊在于，表中的数所元素本身也是一种线性
表。
5.1 数组的定义
数组是我们最熟悉的数据类型，在早期的高
级语言中，数组是唯一可供使用的数据类型。
由于数组中各元素具有统一的类型，并且数组
元素的下标一般具有固定的上界和下界，因此，
数组的处理比其它复杂的结构更为简单。多维
数组是向量的推广。例如，二维数组：
a11 a12 … a 1n
a21 a22 … a 2n
… … … …
am1 am2 … a mn
Amn=
可以看成是由个行向量组成的向量，也可以看成是
个列向量组成的向量。
在 C语言中，一个二维数组类型可以定义为其分
量类型为一维数组类型的一维数组类型，也就是说，
typedef elemtype array2[m][n];
等价于：
typedef elemtype array1[n];
typedef array1 array2[m];
同理，一个维数组类型可以定义为其数据元素为维
数组类型的一维序组类型。
数组一旦被定义，它的维数和维界就不再改变。
因此，除了结构的初始化和销毁之外，数组只有存
取元素和修改元素值的操作。
5.2 数组的顺序表示和实现
由于计算机的内存结构是一维的，因此
用一维内存来表示多维数组，就必须按
某种次序将数组元素排成一列序列，然
后将这个线性序列存放在存储器中。
又由于对数组一般不做插入和删除操
作，也就是说，数组一旦建立，结构中
的元素个数和元素间的关系就不再发生
变化。因此，一般都是采用顺序存储的
方法来表示数组。
通常有两种顺序存储方式：
⑴行优先顺序 ——将数组元素按行排列，第 i+1个行
向量紧接在第 i个行向量后面。以二维数组为例，按
行优先顺序存储的线性序列为：
a11,a12,…,a1n,a21,a22,… a2n,……,am1,am2,…,amn
在 PASCAL,C语言中，数组就是按行优先顺序存
储的。
⑵列优先顺序 ——将数组元素按列向量排列，第 j+1
个列向量紧接在第 j个列向量之后,A的 m*n个元素按
列优先顺序存储的线性序列为：
a11,a21,…,am1,a12,a22,… am2,……,an1,an2,…,anm
在 FORTRAN语言中，数组就是按列优先顺序存储的。
以上规则可以推广到多维数组的情况：优
先顺序可规定为先排最右的下标，从右到
左，最后排最左下标：列优先顺序与此相
反，先排最左下标，从左向右，最后排最
右下标。
按上述两种方式顺序存储的序组，只
要知道开始结点的存放地址（即基地址），
维数和每维的上、下界，以及每个数组元
素所占用的单元数，就可以将数组元素的
存放地址表示为其下标的线性函数。因此，
数组中的任一元素可以在相同的时间内存
取，即顺序存储的数组是一个随机存取结
构。
例如，二维数组 Amn按, 行优先顺序, 存储在内存
中，假设每个元素占用 d个存储单元。
元素 aij的存储地址应是数组的基地址加上
排在 aij前面的元素所占用的单元数。因为 aij位
于第 i行、第 j列，前面 i-1行一共有 (i-1) × n
个元素，第 i行上 aij前面又有 j-1个元素，故它
前面一共有 (i-1) × n+j-1个元素，因此,aij
的地址计算函数为：
LOC(aij)=LOC(a11)+[(i-1)*n+j-1]*d
同样，三维数组 Aijk按, 行优先顺序, 存储，其
地址计算函数为：
LOC(aijk)=LOC(a111)+[(i-1)*n*p+(j-1)*p
+(k-1)]*d
上述讨论均是假设数组各维的下界是不是 1，
更一般的二维数组是 A[c1..d1,c2..d2]，这
里 c1,c2不一定是 1。 aij前一共有 i-c1行，二
维数组一共有 d2-c2+1列，故这 i-c1行共有
(i-c1)*(d2-c2+1)个元素，第 i行上 aij前一
共有 j-c2个元素，因此,aij的地址计算函数
为：
LOC(aij)=LOC(ac1c2)+[(i-c1)*(d2-c2+1)+j-
c2)]*d
例如，在 C语言中，数组各维下标的下界是
0，因此在 C语言中，二维数组的地址计算公
式为：
LOC(aij)=LOC(a00)+(i*(d2+1)+j)*d
5.3 矩阵的压缩存储
在科学与工程计算问题中，矩阵是一种常用
的数学对象，在高级语言编制程序时，简单而又
自然的方法，就是将一个矩阵描述为一个二维数
组。矩阵在这种存储表示之下，可以对其元素进
行随机存取，各种矩阵运算也非常简单，并且存
储的密度为 1。但是在矩阵中非零元素呈某种规
律分布或者矩阵中出现大量的零元素的情况下，
看起来存储密度仍为 1，但实际上占用了许多单
元去存储重复的非零元素或零元素，这对高阶矩
阵会造成极大的浪费，为了节省存储空间,我
们可以对这类矩阵进行压缩存储：即为多个相同
的非零元素只分配一个存储空间；对零元素不分
配空间。
5.3.1特殊矩阵
所谓特殊矩阵是指非零元素或零元素的分布有一
定规律的矩阵，下面我们讨论几种特殊矩阵的压
缩存储。
1、对称矩阵
在一个 n阶方阵 A中，若元素满足下述性质：
aij=aji 0≦ i,j≦ n-1
则称 A为对称矩阵。如图 5.1便是一个 5阶对称矩阵。
对称矩阵中的元素关于主对角线对称，故只要
存储矩阵中上三角或下三角中的元素，让每两个
对称的元素共享一个存储空间，这样，能节约近
一半的存储空间。不失一般性，我们按, 行优先
顺序”存储主对角线（包括对角线）以下的元素，其
存储形式如图所示：
1 5 1 3 7 a00
5 0 8 0 0 a10 a 11
1 8 9 2 6 a20 a21 a23
3 0 2 5 1 ………………..
7 0 6 1 3 an-1 0 a n-1 1 a n-1 2 …a n-1 n-1
图 5.1 对称矩阵
在这个下三角矩阵中，第 i行恰有 i+1个元素，元素
总数为：
(i+1)=n(n+1)/2
因此，我们可以按图中箭头所指的次序将这些
元素存放在一个向量 sa[0..n(n+1)/2-1]中。为了便
于访问对称矩阵 A中的元素，我们必须在 aij和 sa[k]
之间找一个对应关系。
若 i≧ j，则 ai j在下三角形中。 ai j之前的 i行（从第 0
行到第 i-1行）一共有 1+2+…+i=i(i+1)/2 个元素，在第 i
行上,ai j之前恰有 j个元素（即 ai0,ai1,ai2,…,a ij-1），因
此有：
k=i*(i+1)/2+j 0≦ k<n(n+1)/2
若 i<j，则 aij是在上三角矩阵中。因为 aij=aji，所以只要
交换上述对应关系式中的 i和 j即可得到：
k=j*(j+1)/2+i 0≦ k<n(n+1)/2
令 I=max(i,j),J=min(i,j)，则 k和 i,j的对应关系可统
一为：
k=I*(I+1)/2+J 0≦ k<n(n+1)/2
因此,aij的地址可用下列式计算：
LOC(aij)=LOC(sa[k])
=LOC(sa[0])+k*d=LOC(sa[0]+[I*(I+1)/2+J]*d
有了上述的下标交换关系，对于任意给定一组下标
(i,j)，均可在 sa[k]中找到矩阵元素 aij，反之，对所有
的 k=0,1,2,…n(n -1)/2-1，都能确定 sa[k]中的元素在矩阵
中的位臵 (i,j)。由此，称 sa[n(n+1)/2]为阶对称矩阵 A的
压缩存储，见下图：
k=0 1 2 3 n(n-1)/2 n(n-1)/2-1
例如 a21和 a12均存储在 sa[4]中，这是因为
k=I*(I+1)/2+J=2*(2+1)/2+1=4
a00 a10 a11 a20 …… an-1 0 …
…
an-1,n-1
2、三角矩阵
以主对角线划分，三角矩阵有上三角和下三角两种。
上三角矩阵如图所示，它的下三角（不包括主对角线）
中的元素均为常数。下三角矩阵正好相反，它的主对
角线上方均为常数，如图所示。在大多数情况下，
三角矩阵常数为零。
a00 a01 … a 0 n-1 a00 c … c
c a11 … a 1 n-1 a10 a11 … c
………………….,……………..
c c … a n-1 n-1 an-1 0 an-1 1 … a n-1 n-1
(a)上三角矩阵 (b)下三角矩阵
图 5.2 三角矩阵
三角矩阵中的重复元素 c可共享一个存储空间，
其余的元素正好有 n(n+1)/2个，因此，三角矩阵
可压缩存储到向量 sa[0..n(n+1)/2]中，其中 c存
放在向量的最后一个分量中，
上三角矩阵中，主对角线之上的第 p行
(0≦ p<n)恰有 n-p个元素，按行优先顺序存放上
三角矩阵中的元素 aij时,aij之前的 i行一共有
(n-p)=i(2n-i+1)/2
个元素，在第 i行上,aij前恰好有 j-i个元素：
aij,aij+1,… aij-1。因此,sa[k]和 aij的对应关系
是：
i(2n-i+1)/2+j-i 当 i≦ j
n(n+1)/2 当 i>jk=
下三角矩阵的存储和对称矩阵类似,sa[k]和 aij对
应关系是：
i(i+1)/2+j i≧ j
n(n+1)/2 i>j
3、对角矩阵
对角矩阵中，所有的非零元素集中在以主对角线为
了中心的带状区域中，即除了主对角线和主对角线
相邻两侧的若干条对角线上的元素之外，其余元素
皆为零。下图给出了一个三对角矩阵，
a00 a01
a10 a11 a12
a21 a22 a23
…,….,…,图 5.3 对角矩阵
an-2 n-3 an-2 n-2 an-2 n-1
an-1 n-2 an-1 n-1
k=
非零元素仅出现在主对角 (aii,0≦ i≦ n-1上，
紧邻主对角线上面的那条对角线上
(aii+1,0≦ i≦ n-2)和紧邻主对角线下面的
那条对角线上 (ai+1 i,0≦ i≦ n-2)。显然，
当 ∣ i-j∣ >1时，元素 aij=0。
由此可知，一个 k对角矩阵 (k为奇数 )A是满
足下述条件的矩阵：若 ∣ i-j∣ >(k-
1)/2,则元素 aij=0。
对角矩阵可按行优先顺序或对角线的顺
序，将其压缩存储到一个向量中，并且
也能找到每个非零元素和向量下标的对
应关系。
在三对角矩阵里附满足条件 i=0,j=0,1，或
i=n-1j=n-2,n-1或 1<i<n-1,j=i-1,i,i+1的元
素 aij外，其余元素都是零。
对这种矩阵，我们也可按行优序为主序来存储。
除第 0行和第 n-1行是 2个元素外，每行的非零元
素都要是 3个，因此，需存储的元素个数为 3n-2。
a00 a01 a10 a11 a12 a21 … … a n-1 n-2 a n-1 n-1
K=0 1 2 3 4 5 … … 3n -2 3n-1
数组 sa中的元素 sa[k]与三对角带状矩阵中的元
素 aij存在一一对应关系，在 aij之前有 i行,共有 3*i-1
个非零元素，在第 i行，有 j-i+1个非零元素，这样，
非零元素 aij的地址为：
LOC(i,j)=LOC(0,0)+[3*i-1+(j-i+1)]*d
=LOC(0,0)+(2i+j)*d
上例中,a34对应着 sa[10]。
k=2*i+j=2*3+4=10
a21对应着 sa[5]
k=2*2+1=5
由此，我们称 sa[0..3*n-2]是阶三对角带
状矩阵 A的压缩存储表示。
上述的各种特殊矩阵，其非零元素的分布
都是有规律的，因此总能找到一种方法
将它们压缩存储到一个向量中，并且一
般都能找到矩阵中的元素与该向量的对
应关系，通过这个关系，仍能对矩阵的
元素进行随机存取。
5.3.2 稀疏矩阵
什么是稀疏矩阵？简单说，设矩阵 A中有
s个非零元素，若 s远远小于矩阵元素的
总数（即 s≦ m× n），则称 A为稀疏矩阵。
精确点，设在的矩阵 A中，有 s个非零元素。
令 e=s/(m*n)，称 e为矩阵的稀疏因子。
通常认为 e≦ 0.05时称之为稀疏矩阵。在
存储稀疏矩阵时，为了节省存储单元，
很自然地想到使用压缩存储方法。但由
于非零元素的分布一般是没有规律的，
因此在存储非零元素的同时，还必须同
时记下它所在的行和列的位臵（ i,j)。
反之，一个三元组 (i,j,aij)唯一确定了
矩阵 A的一个非零元。因此，稀疏矩阵可
由表示非零元的三元组及其行列数唯一
确定。
例如，下列三元组表
((1,2,12)(1,3,9),(3,1,- 3),(3,6,14),(4,3,24),
(5,2,18),(6,1,15),(6,4,-7))
加上 (6,7)这一对行、列值便可作为下列矩阵 M的
另一种描述。而由上述三元组表的不同表示方法
可引出稀疏矩阵不同的压缩存储方法。
0 12 9 0 0 0 0 0 0 -3 0 0 15
0 0 0 0 0 0 0 12 0 0 0 18 0
-3 0 0 0 0 14 0 9 0 0 24 0 0
0 0 24 0 0 0 0 0 0 0 0 0 –7
0 18 0 0 0 0 0 0 0 14 0 0 0
15 0 0 –7 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0
图 5.4 稀疏矩阵 M和 T
M=
T=
一、三元组顺序表
假设以顺序存储结构来表示三元组表，则可
得到稀疏矩阵的一种压缩存储方法 ——三元顺
序表。
#define maxsize 10000
typedef int datatype;
typedef struct{
int i,j;
datatype v;
}triple;
typedef struct{
triple data[maxsize];
int m,n,t;
}tripletable;
设 A为 tripletable型的结构变量，图 5.4中所
示的稀疏矩阵的三元组的表示如下：
i j v
1 2 12
1 3 9
3 1 -3
3 6 14
4 3 24
5 2 18
6 1 15
6 4 -7
下面以矩阵的转臵为例，说明在这种压缩存储
结构上如何实现矩阵的运算。
一个 m× n的矩阵 A，它的转臵 B是一个 n× m的
矩阵，且 a[i][j]=b[j][i],0≦ i≦ m,0≦ j≦ n，
即 A的行是 B的列,A的列是 B的行。
将 A转臵为 B，就是将 A的三元组表 a.data臵换
为表 B的三元组表 b.data，如果只是简单地交换
a.data中 i和 j的内容，那么得到的 b.data将是一
个按列优先顺序存储的稀疏矩阵 B，要得到按行
优先顺序存储的 b.data，就必须重新排列三元组
的顺序。
由于 A的列是 B的行，因此，按 a.data的列
序转臵，所得到的转臵矩阵 B的三元组表 b.data
必定是按行优先存放的。
按这种方法设计的算法，其基本思想是：对 A中
的每一列 col(0≦ col≦ n-1)，通过从头至尾
扫描三元表 a.data，找出所有列号等于 col的
那些三元组，将它们的行号和列号互换后依次
放入 b.data中，即可得到 B的按行优先的压缩
存储表示。
i j v
1 3 -3
1 6 15
2 1 12
2 5 18
3 1 9
3 4 24
4 6 -7
6 3 14
Void transmatrix(tripletable a,tripletable b)
{
int p q col;
b.m=a.n;
b.n=a.m;
b.t=a.t;
if(b.t<=0)
printf(―A=0\n‖);
q=0;
for(col=1;col<=a.n;col++)
for(p=0;p<=a.t;p++)
if(a.data[p].j==col){
b.data[q].i=a.data[p].j;
b.data[q].j=a.data[p].i;
b.data[q].v=a.data[p].v;
q++;
}
}
分析这个算法，主要的工作是在 p和 col的两个
循环中完成的，故算法的时间复杂度为
O(n*t)，即矩阵的列数和非零元的个数的乘
积成正比。而一般传统矩阵的转臵算法为：
for(col=0;col<=n-1;++col)
for(row=0;row<=m;++row)
t[col][row]=m[row][col];
其时间复杂度为 O(n*m)。当非零元素的个数
t和 m*n同数量级时，算法 transmatrix的时
间复杂度为 O(n*n2)。
三元组顺序表虽然节省了存储空间，但时
间复杂度比一般矩阵转臵的算法还要复
杂，同时还有可能增加算是法的难度。
因此，此算法仅适用于 t<=m*n的情况。
下面给出另外一种称之为快速转臵的算法，
其算法思想为：对 A扫描一次，按 A第二
列提供的列号一次确定位臵装入 B的一个
三元组。具体实施如下：一遍扫描先确
定三元组的位臵关系，二次扫描由位臵
关系装入三元组。可见，位臵关系是此
种算法的关键。
为了预先确定矩阵 M中的每一列的第一个非
零元素在数组 B中应有的位臵，需要先求
得矩阵 M中的每一列中非零元素的个数。
因为：矩阵 M中第一列的第一个非零元素
在数组 B中应有的位臵等于前一列第一个
非零元素的位臵加上前列非零元素的个
数。
为此，需要设臵两个一维数组
num[0..n]和 cpot[0..n]
num[0..n]：统计 M中每列非零元素的个数，
num[col]的值可以由 A的第二列求得。
cpot[0..n]：由递推关系得出 M中的每列第
一个非零元素在 B中的位臵。
算法通过 cpot数组建立位臵对应关系：
cpot[1]=1
cpot[col]=cpot[col-1]+num[col-1]
2<=cpl<=a.n
例如：图 5.4中的矩阵 M和相应的三元组 A可
以求得 num[col]和 cpot[col]的值如下：
col 1 2 3 4 5 6 7
num[col] 2 2 2 1 0 1 0
cpot[col] 1 3 5 7 8 8 9
1 2 v
q …
A i j v 第一列元素个数 第二列元素个数
第三列元素个数
num
cpot
q=cpot[col]
2 1 v
p
p
快速转臵算法如下：
void fasttranstri(tritupletable b,tritupletable a){
int p,q,col,k;
int num[0..a.n],copt[0..a.n];
b.m=a.n; b.n=a.m; b.t=a.t;
if(b.t<=0)
printf(―a=0‖\n);
for(col=1;col<=a.u;++col)
num[col]=0;
for(k=1;k<=a.t;++k)
++num[a.data[k].j];
cpot[0]=1;
for(col=2;col<=a.t;++col)
cpot[col]=cpot[col-1]+num[col-1];
for(p=1;p<=a.t;++p){
col=a.data[p].j; q=cpot[col];
b.data[q].i=a.data[p].j;
b.data[q].j=a.data[p].i;
b.data[q].v=a.data[p].v; ++cpot[col];
}
}
}
二、带行表的三元组
有时为了方便某些矩阵运算，我们在
按行优先存储的三元组中，加入一个行
表来记录稀疏矩阵中每行的非零元素在
三元组表中的起始位臵。当将行表作为
三元组表的一个新增属性加以描述时，
我们就得到了稀疏矩阵的另一种顺序存
储结构：带行表的三元组表。其类型描
述如下：
#define maxrow 100
typedef struct{
triple data[maxsize];
int rpos[maxrow];
int n,m,t;
}rtripletable
下面讨论两个稀疏矩阵相乘的例子，容易看
出这种表示方法的优越性。
两个矩阵相乘的经典算法也是大家所熟悉的。
若设 Q=M*N
其中,M是 m1*n1矩阵,N是 m2*n2矩阵。
当 n1=m2时有：
for(i=1;i<=m1;++i)
for(j=1;j<=n2;++j){
q[i][j]=0
for(k=1;k<=n1;++k)
q[i][j]+=m[i][k]*n[k][j];
}
此算法的复杂度为 O(m1*n1*n2)。
当 M和 N是稀疏矩阵并用三元组表存储结构时，
就不能套用上述算法。假设 M和 N分别为：
3 0 0 5
0 -1 0 0
2 0 0 0
M=
0 2
1 0
-2 4
0 0
N=
则 Q=M*N为：
0 6
-1 0
0 4
Q=
它们的三元组、和分别为：
i j v i j v i j v
1 1 3 1 2 2 1 2 6
1 4 5 2 1 1 2 1 -1
3 2 -1 3 1 -2 3 2 4
3 1 2 3 2 4 q.data
m.data n.data
稀疏矩阵相乘的基本思想是：对于 M中每个元素 M，
找到 N 中所有满足条件的元素，求得和的乘积，
而从式得知，乘积矩阵 Q中每个元素的值是个
累加和，这个乘积只是中的一部分。为了便于
操作，应对每个元素设一累加和的变量，其初
值为零，然后扫描数组 M，求得相应元素的乘
积并累加到适当的求累计和的变量上。
void multsmatrix( rtripletable a,
rtripletable b,
rtripletable c){
if(a.n!=b.m){
printf(―error\n‖); exit(0);
}
c.m=a.m; c.n=b.n; c.t=0;
if(a.t*b.t!=0){
for(arow=1;arow<=a.m;++arow){
ctemp[arow]=0;
c.rpos[arow]=c.t+1;
for(p=a.rops[arow];p<a.rpos[arow+1];++p){
brow=a.data[p].j;
if(brow<b.t) t=b.rpos[brow+1]
else t=b.t+1;
for(q=b.rpos[brow]; q<t;++q){
ccol=n.data[q].j;
ctemp[ccol]+=a.data[p].v*b.data[q].v;
}
}
for(ccol=1;ccol<=c.n;++ccol)
if(ctemp[ccol]){
if(++c.t>maxsize)
exit(0);
c.data[c.t]={arow,ccol,ctemp[ccol]};
}
}
}
}
5.4 广义表的定义
广义表（ Lists，又称列表）是线性表的推广。
在第 2章中，我们把线性表定义为 n>=0个元素
a1,a2,a3,…,an的有限序列。线性表的元素仅限
于原子项，原子是作为结构上不可分割的成分，
它可以是一个数或一个结构，若放松对表元素
的这种限制，容许它们具有其自身结构，这样
就产生了广义表的概念。
广义表是 n(n>=0)个元素 a1,a2,a3,…,an的有
限序列，其中 ai或者是原子项，或者是一个广
义表。通常记作 LS=（ a1,a2,a3,…,an)。 LS是广
义表的名字,n为它的长度。若 ai是广义表，则
称它为 LS的子表。
第六章 树和二叉树
? 6.1 树的定义和基本概念
? 6.2 二叉树
6.2.1 树的定义和基本术语
6.2.2 二叉树的性质
6.2.3 二叉树的存储结构
6.3 遍历二叉树
6.3.1 遍历二叉树
6.3.2 线索二叉树
6.4 树和森林
6.4.1 树的存储结构
6.4.2 森林与二叉树的转换
通常用圆括号将广义表括起来，用逗号分隔其中的
元素。为了区别原子和广义表，书写时用大写字母
表示广义表，用小写字母表示原子。若广义表
LS（ n>=1)非空，则 a1是 LS的 表头,其余元素组成
的表 (a1,a2,…a n)称为 LS的 表尾 。
显然广义表是递归定义的，这是因为在定义广
义表时又用到了广义表的概念。广义表的例子如下：
（ 1） A=（） ——A是一个空表，其长度为零。
（ 2） B=（ e） ——表 B只有一个原子 e,B的长度为 1。
（ 3） C=（ a,(b,c,d))——表 C的长度为 2，两个元素分别
为原子 a和子表 (b,c,d)。
（ 4） D=（ A,B,C） ——表 D的长度为 3，三个元素
都是广义表。显然，将子表的值代入后，则有
D=(( ),(e),(a,(b,c,d)))。
（ 5） E=（ E） ——这是一个递归的表，它的长度为 2，
E相当于一个无限的广义表 E=(a,(a,(a,(a,…)))).
从上述定义和例子可推出广义表的三个重要结论：
（ 1）广义表的元素可以是子表，而子表的元素还可以
是子表，。由此，广义表是一个多层次的结构，可以
用图形象地表示。 P108
（ 2）广义表可为其它表所共享。例如在上述例（ 4）
中，广义表 A,B,C为 D的子表，则在 D中可以不必
列出子表的值，而是通过子表的名称来引用。
（ 3）广义表的递归性。
综上所述，广义表不仅是线性表的推广，也是树的
推广。
由表头、表尾的定义可知：任何一个非空广义表其表
头可能是广义表，也可能是广义表，而其表尾必定是
广义表。
gethead(B)=e gettail(B)=( )
gethead(D)=A gettail(D)=(B,C)
由于（ B,C）为非空广义表，则可继续分解得到：
gethead(B,C)=B gettail(B,C)=(C)
注意广义表（ ）和 ( ( ) )不同。前者是长度为 0的空表，
对其不能做求表头的和表尾的运算；而后者是长度为 1
的非空表（只不过该表中唯一的一个元素是空表）。对
其可进行分解，得到表头和表尾均为空表（ ）。
5.5 广义表的存储结构
由于广义表 (a1,a2,a3,…an) 中的数据元素可以具有
不同的结构，（或是原子，或是广义表），因此，难
以用顺序存储结构表示，通常采用链式存储结构，每
个数据元素可用一个结点表示。
由于广义表中有两种数据元素，原子或广义表，
因此，需要两种结构的结点：一种是表结点，一种是
原子结点。 下面介绍两种广义表的链式存储结构。
1、表结点由三个域组成：标志域、指示表头的指针
域和指示表尾的指针域；而原子域只需两个域：标志
域和值域。
表结点 原子结点
tag=1 hp tp tag=0 atom
其类型定义如下：
typedef enum{ATOM,LIST}elemtag;
typedeg struct glnode{
elemtag tag;
union{
atomtype atom;
struct {
struct glnode *hp,*tp;
}ptr;
};
} *glist;
例见书 P109。
2、表结点由三个域组成：标志域、指示表头的指针
域和指示表尾的指针域；原子结点的三个域为：标志
域、值域和指示表尾的指针域。
tag=1 hp tp tag=0 atom tp
表结点 原子结点
其类型定义如下：
typedef enum{atom,list}elemtag;
Typedef struct glnode{
elemtag tag;
union{
atomtype atom;
struct glnode *hp;
};
struct glnode *tp;
} *glist;
例见书 P110
第六章 树和二叉树
6.1 树的定义和基本概念
6.2 二叉树
6.2.1 树的定义和基本术语
6.2.2 二叉树的性质
6.2.3 二叉树的存储结构
6.3 遍历二叉树
6.3.1 遍历二叉树
6.3.2 线索二叉树
6.4 树和森林
6.4.1 树的存储结构
6.4.2 森林与二叉树的转换
6.4.3树和森林的遍历
6.6 赫夫曼树及其应用
6.6.1 最优二叉树（赫夫曼树）
6.6.2 赫夫曼编码
树型结构是一类重要的非线性结构。树型结
构是结点之间有分支，并且具有层次关系的结构，
它非常类似于自然界中的树。树结构在客观世界
国是大量存在的，例如家谱、行政组织机构都可
用树形象地表示。树在计算机领域中也有着广泛
的应用，例如在编译程序中，用树来表示源程序
的语法结构；在数据库系统中，可用树来组织信
息；在分析算法的行为时，可用树来描述其执行
过程。等等。
6.1 树的定义和基本术语
定义：树 (Tree)是 n(n>=0)个结点的有限集 T,T
为空时称为空树，否则它满足如下两个条件：
（ 1）有且仅有一个特定的称为根 (Root)的结点；
(2)其余的结点可分为 m(m>=0)个互不相交的子集
T1,T2,T3… Tm，其中每个子集又是一棵树，并称
其为子树 (Subtree)。
6.2 二叉树
二叉树在树结构的应用中起着非常重要的作
用，因为对二叉树的许多操作算法简单，而任何
树都可以与二叉树 相互转换，这样就解决了树的
存储结构及其运算中存在的复杂性。
6.2.1 二叉树的定义
定义：二叉树是由 n(n>=0)个结点的有限集合构成，
此集合或者为空集，或者由一个根结点及两棵互
不相交的左右子树组成，并且左右子树都是二叉
树。
这也是一个 递归 定义。二叉树可以是空集合，
根可以有空的左子树或空的右子树。二查树不是
树的特殊情况，它们是两个概念。
二叉树结点的子树要区分左子树和右子树，即使只有
一棵子树也要进行区分，说明它是左子树，还是右子
树。这是二叉树与树的最主要的差别。图 6.8列出二
差树的 5种基本形态，图 6.8(C) 和图 6.8（ d）是不同
的两棵二叉树。
(a)
空二叉树
A A
B
A
B
A
CB
(b)
根和空的
左右子树
(c)
根和左子树
(d)
根和右子树
(e)
根和左右子树
图 6.8 二叉树的 5种形式
6.2.2 二叉树的性质
二叉树具有下列重要性质：
性质 1,在二叉树的第 i层上至多有 2i-1个结点
(i>=1)。
采用归纳法证明此性质。
当 i=1时，只有一个根结点,2i-1=20 =1,命题成立。
现在假定多所有的 j,1<=j<i,命题成立，即第 j层
上至多有 2j-2个结点，那么可以证明 j＝ i时命题也成
立。由归纳假设可知，第 i－ 1层上至多有 2i-2个结点。
由于二叉树每个结点的度最大为 2，故在第 i层上最
大结点数为第 i－ 1层上最大结点数的二倍，
即 2× 2i-2＝ 2i-1。
命题得到证明。
性质 2：深度为 k的二叉树至多有 2k－ 1个结点（ k>=1).
深度为 k的二叉树的最大的结点时为二叉树中每层上
的最大结点数之和，由性质 1得到每层上的最大结点
数，,EkI=1（第 i层上的最大结点数） = EkI=12i-
1=2k –1
性质 3,对任何一棵二叉树，如果其终端结点数为
n0，度为 2的结点数为 n2，则 n0＝ n2＋ 1。
设二叉树中度为 1的结点数为 n1，二叉树中总结点数
为 N，因为二叉树中所有结点均小于或等于 2，所以
有,N＝ n0＋ n1＋ n2 (6-1)
再看二叉树中的分支数，除根结点外，其余结点都
有一个进入分支，设 B为二叉树中的分支总数，
则有,N＝ B＋ 1。
由于这些分支都是由度为 1和 2的结点射出的，所
有有：
B＝ n1+2*n2
N＝ B＋ 1＝ n1＋ 2× n2＋ 1 （ 6－ 2)
由式（ 6－ 1）和（ 6－ 2）得到：
n0+n1+n2=n1+2*n2+1
n0＝ n2＋ 1
下面介绍两种特殊形态的二叉树：满二叉树和完
全二叉树。
一棵深度为 k且由 2k-1个结点的二叉树称为满二
叉树。图 6.9就是一棵满二叉树，对结点进行
了顺序编号。
如果深度为 k、由 n个结点的二叉树中个结点能够
与深度为 k的顺序编号的满二叉树从 1到 n标号的
结点相对应，
2
4 5
3
6 7
1
图 6.9 满二叉树
1
2 3
4 5 6
1
2 3
4 5 7
1
2 3
6 7
(a)完全二叉树 (b)非完全二叉树 ( c)非完全二叉树
图 6.10 完全二叉树
则称这样的二叉树为完全二叉树，图 6..10（ b）、
c）是 2棵非完全二叉树。满二叉树是完全二叉树的
特例。
完全二叉树的特点是：
（ 1)所有的叶结点都出现在第 k层或 k－ 1层。
（ 2）错任一结点，如果其右子树的最大层次为 1，
则其左子树的最大层次为 1或 l＋ 1。
性质 4：具有 n个结点的完全二叉树的深度为
[log2n]＋ 1。
符号 【 x】 表示不大于 x的最大整数。
假设此二叉树的深度为 k，则根据性质 2及完
全二叉树的定义得到,2k-1－ 1<n<=2k-1 或
2k-1<=n<2k
取对数得到,k－ 1<log2n<k 因为 k是整数。所以
有,k＝ 【 log2n】 ＋ 1。
性质 5,如果对一棵有 n个结点的完全二叉树的结点按
层序编号（从第 1层到第 【 log2n】 +1层，每层从左到
右 ),则对任一结点 i（ 1<=i<=n),有：
（ 1）如果 i＝ 1，则结点 i无双亲，是二叉树的根；
如果 i>1，则其双亲是结点 【 i/2】 。
（ 2）如果 2i>n，则结点 i为叶子结点，无左孩子；
否则，其左孩子是结点 2i。
（ 3）如果 2i＋ 1>n，则结点 i无右孩子；否则，其右
孩子是结点 2i＋ 1。
[I/2]
i I+1
2i 2i+1 2(I+1) 2i+3
I+1
2(I+1) 2i+3
i
2i 2i+1
图 6.11 完全二叉树中结点 I和 i+1
(a)I和 i+1结点在同一层 (b)I和 i+1结点不在同一层
如图 6.11所示为完全二叉树上结点及其
左右好在结点之间的关系。
在此过程中，可以从（ 2）和（ 3）推出（ 1），所
以先证明（ 2）和（ 3）。
对于 i＝ 1，由完全二叉树的定义，其左孩子是结
点 2，若 2>n，即不存在结点 2，此是，结点 i无孩子。
结点 i的由孩子也只能是结点 3，若结点 3不存在，即
3>n，此时结点 i无右孩子。
对于 i>1，可分为两种情况：
（ 1）设第 j（ 1<=j<=[log2n])层的第一个结点的编
号为 i，由二叉树的性质 2和定义知 i＝ 2j-1
结点 i的左孩子必定为的 j＋ 1层的第一个结点，其编号
为 2j＝ 2× 2j-1＝ 2i。如果 2i>n，则无左孩子：
（ 2）假设第 j（ 1<=j<=[log2n])层上的某个
结点编号为 i（ 2e(j-1)<=i<=2ej-1),且 2i＋ 1<n，
其左孩子为 2i，右孩子为 2i＋ 1，则编号为 i＋ 1
的结点时编号为 i的结点的右兄弟或堂兄弟。若
它有左孩子，则其编号必定为 2i＋ 2＝ 2× （ i＋
1）：若它有右孩子，则其编号必定为 2i＋ 3＝
2× （ i＋ 1）＋ 1。
当 i＝ 1时，就是根，因此无双亲，当 i>1时，如
果 i为左孩子，即 2× （ i/2)=i,则 i/2是 i的双亲；
如果 i为右孩子,i＝ 2p+1,i的双亲应为 p,p＝
（ i－ 1） /2=[i/2],证毕。
6.2.3 二叉树的存储结构
1.顺序存储结构
它是用一组连续的存储单元存储二叉树的数
据元素。因此，必须把二叉树的所有结点安排成
为一个恰当的序列，结点在这个序列中的相互位
臵能反映出结点之间的逻辑关系，用编号的方法：
#define max-tree-size 100
Typedef telemtype sqbitree[max-tree-size];
Sqbitree bt
从树根起，自上层至下层，每层自左至右的
给所有结点编号缺点是有可能对存储空间造成极
大的浪费，在最坏的情况下，一个深度为 H且只
有 H个结点的右单支树确需要 2h-1个结点存储空
间。而且，若经常需要插入与删除树中结点时，
顺序存储方式不是很好！
A B C D E F G H I J K L
1 2 3 4 5 6 7 8 9 10 11 12
完全二叉树 a
b c
d e f g
h i j k l
A
B C
D E
F G
? ?
? ?
? 表示该处没有元素
存在仅仅为了好理解
A B C D E ? ? ? ? F G
一般二叉树
顺序存储结构的算法：
Status CreateBiTree(BiTree *T) {
scanf(&ch);
if(ch= =") T=NULL;
else{
if(!(T=(BiTNode *)malloc(sizeof(BiTNode))))
exit(OVERFLOW);
T–>data=ch;
CreateBiTree(T–>lchild);
CreateBiTree(T–>rchildd);
}
return OK;
}
（ 2）二叉链表法
存储二叉树经常用二叉链表法
A
^ B C ^
D ^ E
^ F ^ ^ G ^ ^ H ^
lchild Data rchild
二叉树的二叉链表存储表示
Typedef struct BiTNode {
TelemType data;
struct BiTNode *lchild,*rchild;
} BiTNode,*BiTree;
有时也可用数组的下标来模拟指针,即开辟三个一
维数组 Data,lchild,rchild 分别存储结点的元素
及其左,右指针域 ;
6.3 遍历二叉树和线索二叉树
6.3.1遍历二叉树
在二叉树的一些应用中，常常要求在树中查找具有某
种特征的结点，或者对树中全部结点逐一进行某种处
理。这就引入了遍历二叉树的问题，即如何按某条搜
索路径巡访树中的每一个结点，使得每一个结点均被
访问一次，而且仅被访问一次。
遍历对线性结构是容易解决的，而二叉树是非线性的，
因而需要寻找一种规律，以便使二叉树上的结点能排
列在一个线性队列上，从而便于遍历。
b c
a
(根结点 )
(右子树 )
(左子树 )
由二叉树的递归定义，
二叉树的三个基本组成
单元是：根结点、左子
树和右子树。
假如以 L,D,R分别表示遍历左子树、遍历根结点和
遍历右子树，遍历整个二叉树则有 DLR,LDR,LRD、
DRL,RDL,RLD六种遍历方案。若规定先左后右，则只有前
三种情况，分别规定为：
DLR——先（根）序遍历，
LDR——中（根）序遍历，
LRD——后（根）序遍历。
1,先序遍历二叉树 的操作定义为：
若二叉树为空，则空操作；否则
（ 1）访问根结点；
（ 2）先序遍历左子树；
（ 3）先序遍历右子树。
2,中序遍历二叉树 的操作定义为：
若二叉树为空，则空操作；否则
（ 1）中序遍历左子树；
（ 2）访问根结点；
（ 3）中序遍历右子树。
3,后序遍历二叉树 的操作定义为：
若二叉树为空，则空操作；否则
（ 1）后序遍历左子树；
（ 2）后序遍历右子树；
（ 3）访问根结点。
例如图（ 1）所示的二叉树表达式
(a+b*(c-d)-e/f)
若先序遍历此二叉树,按访问结点的先后次序将结
点排列起来,其先序序列为：
-+a*b-cd/ef
按中序遍历,其中序序列为：
a+b*c-d-e/f
按后序遍历,其后序序列为：
abcd-*+ef/-
人喜欢中缀形式的算术
表达式,对于计算机,使
用后缀易于求值 图 （ 1）
－
＋
*a
/
b -
dc
fe
TREENODE *creat_tree()
{
TREENODE *t;
char c;
c=getchar();
if(c= =?#‘) return(NULL);
else{
t=(TREENODE *)malloc(sizeof(TREENODE))
t – >data=c;
t –>lchild=create_tree();
t –>rchild=create –tree(); }
return(t);
}
中序遍历算法,
#include<stdio.h>
#include<stdlib.h>
#define NULL 0
Typedef struct node{
char data;
struct node *lchild,*rchild;
}TREENODE;
TREENODE *root;
TREENODE *creat_tree();
Void inorder(TREENODE *);
Void inorder(TREENODE *p)
{
if(p!=NULL)
{ inorder(p–>lchild);
printf(―%c‖,p–>data)
inorder(p–>rchild);
}
}
（ 3）三叉链表
其它见书 P127
lchild data parent rchild
线索二叉树：
当以二叉链表作为存储结构时,只能找到结点的
左右孩子的信息,而不能在结点的任一序列的前驱
与后继信息,这种信息只有在遍历的动态过程中才
能得到,为了能保存所需的信息,可增加标志域 ;
其中,
0 lchild 域指示结点的左孩子
ltag={ 1 lchild 域指示结点的前驱
0 rchild 域指示结点的右孩子
rtag={ 1 rchild 域指示结点的后驱
以这种结构构成的二叉链表作为二叉树的存储
结构,叫做线索链表,其中指向结点前驱与后继的指
针叫做线索,加上线索的二叉树称之为线索二叉树
lchild ltag data rtag rchild
二叉树的二叉线索存储表示,
Typedef enum{Link,Thread}PointerTag;
Link= =0:指针,Thread= =1:线索
Typedef struct BiThrNode{
TelemType data;
struct BiTreeNode *lchild,*rchild;
PointerTag LTag,Rtag;
}BiTreeNode,*BiThrTree;
模仿线性表的存储结构,在二叉树的线索链表上也
添加一个头结点,令其 lchild域的指针指向二叉树的
根结点,其 rchild域的指针指向中序遍历时访问的最
后一个结点 ;同时,令二叉树中序序列中的第一个结点
lchild域 指针的和最后一个结点 rchild域的指针均
指向头结点 ;就像为二叉树建立了一个双向线索链表,
就好比人在一个圆圈上走路,有可能存在好走的可能
性,
Status InorderTraverse_Thr(BiThrTree
T,status(*visit)(TElemType)){
//T指向头结点,头结点的 lchild左链指向根结点
//中序遍历二叉线索树的非递归算法,对每个数据元素调用
//函数 Visit
P=T–>lchild;
while(p!=T){
while(p –>LTag = =Link) p=p –>lchild;
if(!visit(p –>data)) return error;
while(p –>RTag = =Thread&&p –>rchild!=T) {
p=p –>rchild; Visit(p –>data);
}
p= p–>rchild;
}
return OK;
}//InorderTraverse_Thr
P134, Status InorderThreading(BiThrTree &Thrt,BiThrTree T){
if(!(Thrt =(BiThrTree)malloc(sizeof(BiThrNode))))
exit(OVERFLOW);
Thrt –>LTag =Link; Thrt –>RTag =Thread;
Thrt –>rchild=Thrt;
if(!T) Thrt –>lchild=Thrt;
else{
Thrt –>lchild=T; pre=Thrt;
InThrTreading(T);
pre –>rchild=Thrt; pre –> RTag =Thread;
Thrt –>rchild=pre;
}
return OK;
}//InorderThreading
Void InThreading(BiThrTree p) {
if(p){
InThreading(p –>lchild);
if(!p –>lchild) {p –> LRag =Thread; p –
>lchild=pre;}
if(!pre –>rchild)
{pre –>rchild){pre –>RRag =Thread;pre –>rchild=p;}
pre=p;
InThreading(p –>rchild);
}
}
在线索树上插入一棵左子树 (Ins_lchild)和删除一棵左子
(Del_lchild)
计算机系
第一章 绪 论
1.1 什么是数据结构
1.2 基本概念和术语
1.3 抽象数据类型的表示与实现
1.4 算法和算法分
1.4.1 算法
1.4.2 算法设计的要求
1.4.3 算法效率的度量
1.4.4 算法的存储空间的需求
第一章 绪 论
? 计算机是一门研究用计算机进行信息表示和处
理的科学。这里面涉及到两个问题：
? 信息的表示
信息的处理
而信息的表示和组又直接关系到处理信息的
程序的效率。随着计算机的普及，信息量的增
加，信息范围的拓宽，使许多系统程序和应用
程序的规模很大，结构又相当复杂。因此，为
了编写出一个“好”的程序，必须分析待处理
的对象的特征及各对象之间存在的关系，这就
是数据结构这门课所要研究的问题。
? 1.1什么是数据结构
? 众所周知，计算机的程序是对信息进行加工处理。
在大多数情况下，这些信息并不是没有组织，信息
（数据）之间往往具有重要的结构关系，这就是数据
结构的内容。那么，什么是数据结构呢？先看以下几
个例子。
? 例 1、电话号码查询系统
? 设有一个电话号码薄，它记录了 N个人的名字和其
相应的电话号码，假定按如下形式安排：
? (a1,b1)(a2,b2)…(a n,bn)
? 其中 ai,bi(i=1,2…n) 分别表示某人的名字和对应的电
话号码要求设计一个算法，当给定任何一个人的名字
时，该算法能够打印出此人的电话号码，如果该电话
簿中根本就没有这个人，则该算法也能够报告没有这
个人的标志。
? 算法的设计，依赖于计算机如何存储人的
名字和对应的电话号码，或者说依赖于名字和
其电话号码的结构。
? 数据的结构，直接影响算法的选择和效率。
? 上述的问题是一种数据结构问题。可将名
字和对应的电话号码设计成：二维数组、表结
构、向量。
假定名字和其电话号码逻辑上已安排成 N
元向量的形式，它的每个元素是一个数对 (ai，
bi),1≤i≤n
数据结构还要提供每种结构类型所定义的
各种运算的算法。
例 2、图书馆的书目检索系统自动化问题
例 3、教师资料档案管理系统
例 4、多叉路口交通灯的管理问题
P3
通过以上几例可以直接地认为：数据结构
就是研究数据的逻辑结构和物理结构以及它们
之间相互关系，并对这种结构定义相应的运算，
而且确保经过这些运算后所得到的新结构仍然
是原来的结构类型。
? 1.2 基本概念和术语
? 数据 (Data):是对信息的一种符号表示。在计
算机科学中是指所有能输入到计算机中并被
计算机程序处理的符号的总称。
? 数据元素 (Data Element):是数据的基本单位，
在计算机程序中通常作为一个整体进行考虑
和处理。
? 一个数据元素可由若干个数据项组成。数
据项是数据的不可分割的最小单位。
? 数据对象 (Data Object)：是性质相同的数据元
素的集合。是数据的一个子集。
? 数据结构 (Data Structure)：是相互之间存在一
种或多种特定关系的数据元素的集合。
? 数据结构主要指逻辑结构和物理结构
? 数据之间的相互关系称为逻辑结构。通常分
为四类基本结构：
? 一,集合 结构中的数据元素除了同属于一种
类型外，别无其它关系。
? 二,线性结构 结构中的数据元素之间存在一
对一的关系。
? 三,树型结构 结构中的数据元素之间存在
一对多的关系。
? 四,图状结构或网状结构 结构中的数据元素
之间存在多对多的关系。
?
数据结构的形式定义为：数据结构是一个二元
组：
Data-Structure=(D,S)
其中,D是数据元素的有限集,S是 D上关系的
有限集。
例 复数的数据结构定义如下：
Complex=(C,R)
其中,C是含两个实数的集合 ﹛ C1,C2﹜,分
别表示复数的实部和虚部。 R={P},P是定义在
集合上的一种关系 {〈 C1,C2〉 }。
数据结构在计算机中的表示称为数据的 物理结
构,又称为 存储结构 。
? 数据对象可以是有限的，也可以是无限的。
? 数据结构不同于数据类型，也不同于数据对
象，它不仅要描述数据类型的数据对象，而且
要描述数据对象各元素之间的相互关系。
? 抽象数据类型：一个数学模型以及定义在该模
型上的一组操作。
? 抽象数据类型实际上就是对该数据结构的
定义。因为它定义了一个数据的逻辑结构以及
在此结构上的一组算法。
? 用三元组描述如下：
? （Ｄ，Ｓ，Ｐ）
? 数据结构在计算机中有两种不同的表示方法：
? 顺序表示和非顺序表示
? 由此得出两种不同的存储结构,顺序存储结
构和链式存储结构
? 顺序存储结构,用数据元素在存储器中的相对
位置来表示数据元素之间的逻辑关系 。
? 链式存储结构,在每一个数据元素中增加一
个存放地址的指针（ ），用此指针来表示数
据元素之间的逻辑关系。
? 数据类型,在一种程序设计语言中，变量所具
有的数据种类。
? 例 1,在 FORTRAN语言中，变量的数据类型
有整型、实型、和复数型
? 例 2、在 C语言中
? 数据类型：基本类型和构造类型
? 基本类型：整型、浮点型、字符型
? 构造类型：数组、结构、联合、指针、枚举型、
自定义
? 数据对象,某种数据类型元素的集合。
? 例 3、整数的数据对象是 {… -3,-2,-1,0,1，
2,3,…}
? 英文字符类型的数据对象是 {A,B,C,D,E，
F,…}
? 1.3 抽象数据类型的表示和实现
? P11
? 1.4 算法和算法分析
? 算法,是对特定问题求解步骤的一种描述
? 算法是指令的有限序列，其中每一条指令
表示一个或多个操作。
? 算法具有以下五个特性：
? （ 1） 有穷性 一个算法必须总是在执行有穷步
之后结束，且每一步都在有穷时间内完成。
? （ 2） 确定性 算法中每一条指令必须有确切的
含义。不存在二义性。且算法只有一个入口和
一个出口。
? （ 3） 可行性 一个算法是可行的。即算法描述
的操作都是可以通过已经实现的基本运算执行
有限次来实现的。
? 4） 输入 一个算法有零个或多个输入，这些输
入取自于某个特定的对象集合。
? 5） 输出 一个算法有一个或多个输出，这些输
出是同输入有着某些特定关系的量。
? 1.4.2 算法设计的要求
? 评价一个好的算法有以下几个标准,
? (1) 正确性 (Correctness ) 算法应满足具体问题
的需求。
? (2)可读性 (Readability) 算法应该好读。以有利
于阅读者对程序的理解。
(3)健状性 (Robustness) 算法应具有容错处理。
当输入非法数据时，算法应对其作出反应，而
不是产年莫名其妙的输出结果。
? (4)效率与存储量需求 效率指的是算法执行的
时间；存储量需求指算法执行过程中所需要的
最大存储空间。一般，这两者与问题的规模有
关。
? 1.4.3 算法效率的度量
? 对一个算法要作出全面的分析可分成两用人
才个阶段进行，即 事先分析 和 事后测试
? 事先分析 求出该算法的一个时间界限函数
? 事后测试 收集此算法的执行时间和实际占用
空间的统计资料。
? 定义：如果存在两个正常数 c和 n0，对于所有的
n≧ n0，有 ︱ f(n) ︳ ≦ c｜ g(n) ︳
? 则记作 f(n)=O(g(n))
一般情况下，算法中基本操作重复执行的
次数是问题规模 n的某个函数，算法的时
间量度记作
T(n)=O(f(n))
称作算法的渐近时间复杂度。
例１,for(I=1,I<=n;++I)
for(j=1;j<=n;++j)
{
c[I][j]=0;
for(k=1;k<=n;++k)
c[I][j]+=a[I][k]*b[k][j];
}
? 由于是一个三重循环，每个循环从 1到 n，则总
次数为, n× n× n=n3
? 时间复杂度为 T(n)=O(n3)
? 频度,是指该语句重复执行的次数
? 例２ {++x;s=0;}
? 将 x自增看成是基本操作，则语句频度为１，
即时间复杂度为Ｏ (1)
? 如果将 s=0也看成是基本操作，则语句频度为
２，其时间复杂度仍为Ｏ (1)，即常量阶。
? 例３,for(I=1;I<=n;++I)
? {++x;s+=x;}
? 语句频度为,2n 其时间复杂度为,O(n)
? 即时间复杂度为线性阶。
? 例４,for(I=1;I<=n;++I)
? for(j=1;j<=n;++j)
? {++x;s+=x;}
? 语句频度为,2n2
? 其时间复杂度为,O(n2)
? 即时间复杂度为平方阶。
? 定理：若 A(n)=a m n m +a m-1 n m-1 +…+a 1n+a0是
一个 m次多项式，则 A(n)=O(n m)
证略。
例５ for(i=2;i<=n;++I)
for(j=2;j<=i-1;++j)
{++x;a[i,j]=x;}
? 语句频度为：
? 1+2+3+…+n -2=(1+n-2) × (n-2)/2
? =(n-1)(n-2)/2
? =n2-3n+2
? ∴ 时间复杂度为 O(n2)
? 即此算法的时间复杂度为平方阶,
? 一个算法时间为 O(1)的算法，它的
基本运算执行的次数是固定的。因此，
总的时间由一个常数（即零次多项式）
来限界。而一个时间为 O(n2)的算法则由
一个二次多项式来限界。
?
? 以下六种计算算法时间的多项式是最常
用的。其关系为：
? O(1)<O(logn)<O(n)<O(nlogn)
? <O(n2)<O(n3)
? 指数时间的关系为：
? O(2n)<O(n!)<O(nn)
? 当 n取得很大时，指数时间算法和多项
式时间算法在所需时间上非常悬殊。因
此，只要有人能将现有指数时间算法中
的任何一个算法化简为多项式时间算法，
那就取得了一个伟大的成就。
? 有的情况下，算法中基本操作重复执行的次数
还随问题的输入数据集不同而不同。例如：
? Void bubble-sort(int a[],int n)
? for(I=n-1;change=TURE;I>1 && change;--I)
? {
? change=false;
? for(j=0;j<I;++j)
? if (a[j]>a[j+1]) {
? a[j] ←→a[j+1];
? change=TURE}
? }
? 最好情况,0次
?
? 最坏情况,1+2+3+…+n -1
? =n(n-1)/2
? 平均时间复杂度为,O(n2)
? 1.4.4算法的存储空间需求
? 空间复杂度,算法所需存储空间的度量，
记作,
? S(n)=O(f(n))
? 其中 n为问题的规模 (或大小 )
第二章 线性表
? 2.1 线性表的类型定义
? 2.2 线性表的顺序表示和实现
? 2.3 线性表的链式表示和实现
? 2.3.1 线性链表
2.3.2 循环链表
2.3.3 双向链表
2.4 一元多项式的表示及相加
? 2.1 线性表的逻辑结构
? 线性表 (Linear List),由 n(n≧ )个数据元素 (结
点 )a1,a2,…a n组成的有限序列。其中数据元
素的个数 n定义为表的长度。当 n=0时称为空表，
常常将非空的线性表 (n>0)记作：
? (a1,a2,…a n)
? 这里的数据元素 ai(1≦ i≦ n)只是一个抽象的符
号，其具体含义在不同的情况下可以不同。
? 例 1,26个英文字母组成的字母表
? （ A,B,C,…, Z）
? 例 2、某校从 1978年到 1983年各种型号的计算
机拥有量的变化情况。
? （ 6,17,28,50,92,188）
例 3、学生健康情况登记表如下：
姓 名 学 号 性 别 年龄 健康情况
王小林 790631 男 18 健康
陈 红 790632 女 20 一般
刘建平 790633 男 21 健康
张立立 790634 男 17 神经衰弱
…….,…….,……,……,…….
? 例 4、一副扑克的点数
? （ 2,3,4,…, J,Q,K,A）
从以上例子可看出线性表的逻辑特征是：
? 在非空的线性表，有且仅有一个开始结点 a1，
它没有直接前趋，而仅有一个直接后继 a2；
? 有且仅有一个终端结点 an，它没有直接后继，
而仅有一个直接前趋 a n-1；
? 其余的内部结点 ai(2≦ i≦ n-1)都有且仅有一个
直接前趋 a i-1和一个直接后继 a i+1。
线性表是一种典型的线性结构。
? 数据的运算是定义在逻辑结构上的，而运算
的具体实现则是在存储结构上进行的。
? 抽象数据类型的定义为,P19
算法 2.1
? 例 2-1 利用两个线性表 LA和 LB分别表示两个集
合 A和 B，现要求一个新的集合 A=A∪ B。
void union(List &La,List Lb) {
La-len=listlength(La);
Lb-len=listlength(Lb);
for(I=1;I<=lb-len;I++) {
getelem(lb,I,e);
if(!locateelem(la,e,equal))listinsert(la，
++la-en,e)
}
}
?
? 算法 2.2
? 例 2-2 巳知线性表 LA和线性表 LB中的数
据元素按值非递减有序排列，现要求将
LA和 LB归并为一个新的线性表 LC，且
LC中的元素仍按值非递减有序排列。
? 此问题的算法如下：
void mergelist(list la,list lb,list &lc)
initlist(lc);
I=j=1;k=0;
la-len=listlength(la);
lb-len=listlength(lb);
while((I<=la-len)&&(j<=lb-len)){
? getelem(la,I,ai);getelem(lb,j,bj);
? if(ai<=bj){listinsert(lc,++k,ai);++I;}
else{listinsert(lc,++k,bj);++j;}
}
while(I<=la-len){
getelem((la,I++,ai);listinsert(lc，
++k,ai);
}
while(j<=lb-len){
getelem((lb,j++,bj);listinsert(lc，
++k,bi);
}
? 2.2 线性表的顺序存储结构
? 2.2.1 线性表
把线性表的结点按逻辑顺序依次存放在一组
地址连续的存储单元里。用这种方法存储的线
性表简称顺序表。
假设线性表的每个元素需占用 l个存储单元，
并以所占的第一个单元的存储地址作为数据元
素的存储位置。则线性表中第 I+1个数据元素
的存储位置 LOC( a i+1)和第 i个数据元素的存储
位置 LOC(a I )之间满足下列关系：
LOC(a i+1)=LOC(a i)+l
线性表的第 i个数据元素 ai的存储位置为：
LOC(ai)=LOC(a1)+(I-1)*l
? 由于 C语言中的一维数组也是采用顺序存储
表示，故可以用数组类型来描述顺序表。
又因为除了用数组来存储线性表的元素之
外，顺序表还应该用一个变量来表示线性
表的长度属性，所以我们用结构类型来定
义顺序表类型。
? # define ListSize 100
? typedef int DataType;
? typedef struc{
? DataType data[ListSize];
? int length;
? } Sqlist;
? 2.2.2 顺序表上实现的基本操作
在顺序表存储结构中，很容易实现线
性表的一些操作，如线性表的构造、第 i
个元素的访问。
注意,C语言中的数组下标从,0‖开始，
因此，若 L是 Sqlist类型的顺序表，则表
中第 i个元素是 l.data[I-1]。
以下主要讨论线性表的插入和删除
两种运算。
1、插入
线性表的插入运算是指在表的第
I(1≦ i≦ n+1个位置上，插入一个新结点 x，
使长度为 n的线性表
(a1,…a i-1,ai,…, an)
变成长度为 n+1的线性表
(a1,…a i-1,x,ai,…, an)
算法 2.3
? Void InsertList(Sqlist*L,DataType x,int
I)
? {
? int j;
? if(I<1 || I>l.length+1)
? printf(―Position error‖);
return ERROR
? if(l.length>=ListSize)
? printf(―overflow‖);
? exit(overflow);
? for(j=l.length-1;j>=I-1;j--)
? l.data[j+1]=l.data[j];
? l.data[I-1]=x;
? l.length++;
? }
? 现在分析算法的复杂度。
? 这里的问题规模是表的长度，设它的
值为。该算法的时间主要化费在循环的
结点后移语句上，该语句的执行次数
（即移动结点的次数）是。由此可看出，
所需移动结点的次数不仅依赖于表的长
度，而且还与插入位置有关。
? 当时，由于循环变量的终值大于初值，
结点后移语句将不进行；这是最好情况，
其时间复杂度 O（ 1）；
? 当 =1时，结点后移语句将循环执行 n次，
需移动表中所有结点，这是最坏情况，
? 其时间复杂度为 O（ n）。
? 由于插入可能在表中任何位置上进行，因
此需分析算法的平均复杂度
在长度为 n的线性表中第 i个位置上插入一
个结点，令 Eis(n)表示移动结点的期望值（即移
动的平均次数），则在第 i个位置上插入一个结
点的移动次数为 n-I+1。故
Eis(n)= pi(n-I+1)
不失一般性，假设在表中任何位置 (1≦ i≦ n+1)
上插入结点的机会是均等的，则
p1=p2=p3=…=p n+1=1/(n+1)
因此，在等概率插入的情况下，
Eis(n)= (n-I+1)/(n+1)=n/2
也就是说，在顺序表上做插入运算，平均要移
动表上一半结点。当表长 n较大时，算法的效
率相当低。虽然 Eis(n)中 n的的系数较小，但就
数量级而言，它仍然是线性阶的。因此算法的
平均时间复杂度为 O(n)。
2、删除
线性表的删除运算是指将表的第
i(1≦ i≦ n)结点删除，使长度为 n的线性表：
(a1,…a i-1,ai,a i+1…, an)
变成长度为 n-1的线性表
(a1,…a i-1,a i+1,…, an)
Void deleteList(Sqlist*L,int I)
{
int j;
if(I<1 || I>l.length)
printf(―Position error‖);
return ERROR
for(j=i;j<=l.length-1;j++)
l.data[j-1]=l.data[j];
l.length--;
}
? 该算法的时间分析与插入算法相似，结点的移
动次数也是由表长 n和位置 i决定。
? 若 I=n，则由于循环变量的初值大于终值，
前移语句将不执行，无需移动结点；
? 若 I=1，则前移语句将循环执行 n-1次，需移
动表中除开始结点外的所有结点。这两种情况
下算法的时间复杂度分别为 O(1)和 O(n)。
? 删除算法的平均性能分析与插入算法相似。
在长度为 n的线性表中删除一个结点，令 Ede(n)
表示所需移动结点的平均次数，删除表中第 i个
结点的移动次数为 n-i，故
Ede(n)= pi(n-I)
? 式中,pi表示删除表中第 i个结点的概率。在等
? 概率的假设下，
p1=p2=p3=…=p n=1/n
由此可得：
Ede(n)= (n-I)/n=(n-1)/2
即在顺序表上做删除运算，平均要移动表中约
一半的结点，平均时间复杂度也是 O(n)。
2.3 线性表的链式表示和实现
线性表的顺序表示的特点是用物理位置上的
邻接关系来表示结点间的逻辑关系，这一特点
使我们可以随机存取表中的任一结点，但它也
使得
插入和删除操作会移动大量的结点,为避免大量结
点的移动，我们介绍线性表的另一种存储方式，
链式存储结构，简称为链表 (Linked List)。
2.3.1 线性链表
链表是指用一组任意的存储单元来依次
存放线性表的结点，这组存储单元即可以是连续
的，也可以是不连续的，甚至是零散分布在内存
中的任意位臵上的。因此，链表中结点的逻辑次
序和物理次序不一定相同。为了能正确表示结点
间的逻辑关系，在存储每个结点值的同时，还必
须存储指示其后继结点的地址（或位臵）信息，
这个信息称为指针 (pointer)或链 (link)。这两
部分组成了链表中的结点结构：
其中,data域是数据域，用来存放结点的值。
next是指针域（亦称链域），用来存放结点的直接
后继的地址（或位臵）。链表正是通过每个结点的
链域将线性表的 n个结点按其逻辑次序链接在一起的。
由于上述链表的每一个结只有一个链域，故将这种
链表称为单链表（ Single Linked)。
显然，单链表中每个结点的存储地址是存
放在其前趋结点 next域中，而开始结点无前趋，故
应设头指针 head指向开始结点。同时，由于
终端结点无后继，故终端结点的指针域为空，即
null（图示中也可用 ^表示 )。
例 1、线性表,(bat,cat,eat,fat,hat,jat，
lat,mat)
data link
的单链表示意图如下：
……
110
……
130
135
……
160
头指针 head 165
170
……
200
205
……
……
…
……
hat 200
……, ……
cat 135
eat 170
…, ……
mat Null
bat 130
fat 110
…… ……
jat 205
lat 160
…… ……
165
? head
bat cat eat mat ^ …
单链表是由表头唯一确定，因此单链表可以用头
指针的名字来命名。
例如：若头指针名是 head，则把链表称为表 head。
用 C语言描述的单链表如下：
Typedef char datatype;
Typedef struct node{
datatype data;
struct node *next;
}listnode;
typedef listnode *linklist;
listnode *p;
linklist head;
注意区分指针变量和结点变量这两个不同的概念。
P为动态变量，它是通过标准函数生成的，即
p=(listnode*)malloc(sizeof(listnode));
函数 malloc分配了一个类型为 listnode的结点变量
的空间，并将其首地址放入指针变量 p中。一
旦 p所指的结点变量不再需要了，又可通过标
准函数
free(p)
释放所指的结点变量空间。
? 指针变量 P和（其值为结点地址）和结点变量
*P之间的关系。
一、建立单链表
假设线性表中结点的数据类型是字符，我们
逐个输入这些字符型的结点，并以换行符‘ \n‘
为输入结束标记。动态地建立单链表的常用方
法有如下两种：
1、头插法建表
该方法从一个空表开始，重复读入数据，
生成新结点，将读入数据存放到新结点的数据
域中，然后将新结点插入到当前链表的表头上，
直到读入结束标志为止。
linklist createlistf(void)
{
char ch;
linklist head;
listnode *p;
head=null;
ch=getchar( );
while (ch!=‵ \n′{
p=(listnode*)malloc(sizeof(listnode));
p–>data=ch;
p–>next=head;
head=p;
ch=getchar( );
}
return (head);
}
listlink createlist(int n)
{ int data;
linklist head;
listnode *p
head=null;
for(i=n;i>0;--i){
p=(listnode*)malloc(sizeof(listnode));
scanf((〝 %d〞, &p–>data);
p–>next=head;
head=p;
}
return(head);
}
2、尾插法建表
头插法建立链表虽然算法简单，但生成的
链表中结点的次序和输入的顺序相反。若希望
二者次序一致，可采用尾插法建表。该方法是
将新结点插入到当前链表的表尾上，为此必须
增加一个尾指针 r，使其始终指向当前链表的
尾结点。例：
linklist creater( )
{
char ch;
linklist head;
listnode *p,*r; //(,*head;)
head=NULL;r=NULL;
while((ch=getchar( )!=‵ \n′){
p=(listnode *)malloc(sizeof(listnode));
p–>data=ch;
if(head=NULL)
head=p;
else
r–>next=p;
r=p;
}
if (r!=NULL)
r–>next=NULL;
return(head);
}
说明：第一个生成的结点是开始结点，将开始结
点插入到空表中，是在当前链表的第一个位臵
上插入，该位臵上的插入操作和链表中其它位
臵上的插入操作处理是不一样的，原因是开始
结点的位臵是存放在头指针（指针变量）中，
而其余结点的位臵是在其前趋结点的指针域中。
算法中的第一个 if语句就是用来对第一个位臵
上的插入操作做特殊处理。算法中的第二个 if
语句的作用是为了分别处理空表和非空表两种
不同的情况，若读入的第一个字符就是结束标
志符，则链表 head是空表，尾指针 r亦为空，结
点 *r不存在；否则链表 head非空，最后一个尾
结点 *r是终端结点，应将其指针域臵空。
如果我们在链表的开始结点之前附加一个
结点，并称它为 头结点,那么会带来以下两个
优点：
a、由于开始结点的位臵被存放在头结点的指
针域中，所以在链表的第一个位臵上的操作就
和在表的其它位臵上的操作一致，无需进行特
殊处理；
b、无论链表是否为空，其头指针是指向头结点
在的非空指针（空表中头结点的指针域为空），
因此空表和非空表的处理也就统一了。
其算法如下：
linklist createlistr1( ){
char ch;
linklist
head=(linklist)malloc(sizeof(listnode));
listnode *p,*r
r=head;
while((ch=getchar( ))!=‵ \n′{
p=(listnode*)malloc(sizeof(listnode));
p–>data=ch;
p–>next=p;
r=p;
}
r–>next=NULL;
return(head);
}
上述算法里动态申请新结点空间时未加错误处理，
可作下列处理：
p=(listnode*)malloc(sizeof(listnode))
if(p==NULL)
error(〝 No space for node can be obtained〞 );
return ERROR;
以上算法的时间复杂度均为 O(n)。
二、查找运算
1、按序号查找
在链表中，即使知道被访问结点的序号 i，
也不能象顺序表中那样直接按序号 i访问结点，
而只能从链表的头指针出发，顺链域 next逐个
结点往下搜索，直到搜索到第 i个结点为止。
因此，链表不是随机存取结构。
设单链表的长度为 n，要查找表中第 i个结
点，仅当 1≦ i≦ n时,i的值是合法的。但有时
需要找头结点的位臵，故我们将头结点看做是
第 0 个结点，其算法如下：
Listnode * getnode(linklist head, int i)
{
int j;
listnode * p;
p=head;j=0;
while(p–>next && j<I){
p=p–>next;
j++;
}
if (i==j)
return p;
else
return NULL;
}
2、按值查找
按值查找是在链表中，查找是否有结点值等
于给定值 key的结点，若有的话，则返回首次
找到的其值为 key的结点的存储位臵；否则返
回 NULL。查找过程从开始结点出发，顺着链表
逐个将结点的值和给定值 key作比较。其算法
如下：
Listnode * locatenode(linklist head,int key)
{
listnode * p=head–>next;
while( p && p–>data!=key)
p=p–>next;
return p;
}
该算法的执行时间亦与输入实例中的的取值
key有关，其平均时间复杂度的分析类似于按
序号查找，也为 O(n)。
三、插入运算
插入运算是将值为 x的新结点插入
到表的第 i个结点的位臵上，即插入到 ai-
1与 ai之间。因此，我们必须首先找到 ai-1
的存储位臵 p，然后生成一个数据域为 x
的新结点 *p，并令结点 *p的指针域指向
新结点，新结点的指针域指向结点 ai。
从而实现三个结点 ai-1,x和 ai之间的逻辑
关系的变化，插入过程如：
具体算法如下：
void insertnode(linklist head,datetype x,int i)
{
listnode * p,*q;
p=getnode(head,i-1);
if(p==NULL)
error(〝 position error〞 );
q=(listnode *)malloc(sizeof(listnode));
q–>data=x;
q–>next=p–next;
p–>next=q;
}
设链表的长度为 n，合法的插入位臵是 1≦ i≦ n+1。
注意当 i=1时,getnode找到的是头结点，当
i=n+1时,getnode找到的是结点 an。因此，用 i-1
做实参调用 getnode时可完成插入位臵的合法性
检查。算法的时间主要耗费在查找操作 getnode
上，故时间复杂度亦为 O(n)。
四、删除运算
删除运算是将表的第 i个结点删去。因为在单
链表中结点 ai的存储地址是在其直接前趋结点 a
a i-1的指针域 next中，所以我们必须首先找到
a i-1的存储位臵 p。然后令 p–>next指向 ai的直接
后继结点，即把 ai从链上摘下。最后释放结点 ai
的空间，将其归还给“存储池”。此过程为：
具体算法如下,
void deletelist(linklist head,int i)
{
listnode * p,*r;
p=getnode(head,i-1);
if(p= =NULL || p–>next= =NULL)
return ERROR;
r=p–>next;
p–>next=r–>next;
free( r ) ;
}
设单链表的长度为 n，则删去第 i个结点仅
当 1≦ i≦ n时是合法的。注意，当 i=n+1时，
虽然被删结点不存在，但其前趋结点却存在，
它是终端结点。因此被删结点的直接前趋 *p
存在并不意味着被删结点就一定存在，仅当
*p存在（即 p!=NULL）且 *p不是终端结点
（即 p–>next!=NULL）时，才能确定被删结
点存在。
显然此算法的时间复杂度也是 O(n)。
从上面的讨论可以看出，链表上实现插入
和删除运算，无须移动结点，仅需修改指针。
2.3.2 循环链表
循环链表时一种头尾相接的链表。其特点
是无须增加存储量，仅对表的链接方式稍
作改变，即可使得表处理更加方便灵活 。
单循环链表,在单链表中，将终端结点的指
针域 NULL改为指向表头结点的或开始结
点，就得到了单链形式的循环链表，并简
单称为单循环链表。
为了使空表和非空表的处理一致，循环
链表中也可设臵一个头结点。这样，空循
环链表仅有一个自成循环的头结点表示。
如下图所示：
a1 an….head
⑴ 非空表
⑵ 空表
在用头指针表示的单链表中，找开始结点 a1
的时间是 O(1)，然而要找到终端结点 an，则需
从头指针开始遍历整个链表，其时间是 O(n)
在很多实际问题中，表的操作常常是在
表的首尾位臵上进行，此时头指针表示的
单循环链表就显得不够方便,如果改用尾指
针 rear来表示单循环链表，则查找开始结点
a1和终端结点 an都很方便，它们的存储位臵
分别是 (rear–>next) —>next和 rear，显然，
查找时间都是 O(1)。因此，实际中多采用尾
指针表示单循环链表。
由于循环链表中没有 NULL指针，故涉及
遍历操作时，其终止条件就不再像非循环
链表那样判断 p或 p—>next是否为空，而是
判断它们是否等于某一指定指针，如头指
什或尾指针等。
例、在链表上实现将两个线性表 (a1,a2，
a3,…a n)和 (b1,b2,b3,…b n)链接成一个线
性表的运算。
linklist connect(linklist heada,linklist headb)
{
linklist p=heada—>next;
heada—>next=(headb—next)—>next
free(headb—>next);
headb—>next=p;
return(headb);
}
2.3.3双链表
双向链表 (Double linked list):在单链表
的每个结点里再增加一个指向其直接前趋
的指针域 prior。这样就形成的链表中有两
个方向不同的链，故称为双向链表。形式
描述为：
typedef struct dlistnode{
datatype data;
struc dlistnode *prior,*next;
}dlistnode;
typedef dlistnode * dlinklist;
dlinklist head;
和单链表类似，双链表一般也是由头指
针唯一确定的，增加头指针也能使双链表
上的某些运算变得方便，将头结点和尾结
点链接起来也能构成循环链表，并称之为
双向链表。
设指针 p指向某一结点，则双向链表结构
的对称性可用下式描述：
(p—>prior)—>next=p=(p—>next)—>prior
即结点 *p的存储位臵既存放在其前趋结点
*(p—>prior)的直接后继指针域中，也存放
在它的后继结点 *(p—>next)的直接前趋指
针域中。
双向链表的前插操作算法如下：
void dinsertbefor(dlistnode *p,datatype x)
{
dlistnode *q=malloc(sizeof(dlistnode));
q—>data=x;
q—>prior=p—>prior;
q—>next=p;
p—>prior—>next=q;
p—>prior=q;
}
void ddeletenode(dlistnode *p)
{
p–>prior–>next=p–>next;
p–>next–>prior=p–>prior;
free(p);
}
注意：与单链表的插入和删除操作不同的
是，在双链表中插入和删除必须同时修改
两个方向上的指针。上述两个算是法的时
间复杂度均为 O(1)。
第三章 栈和队列
3.1 栈
3.1.1 抽象数据类型栈的定义
3.1.2 栈的表示和实现
3.2 栈的应用举例
3.2.1 数制转换
3.2.2 括号匹配的检验
3.2.4 行编辑程序
3.2.5 迷宫求解
3.2.5 表达式求值
3.1.1 栈
3.1.1 栈的定义及基本运算
栈 (Stack)是限制在表的一端进行插入和删
除运算的线性表，通常称插入、删除的这一
端为栈顶 (Top)，另一端为栈底 (Bottom)。当
表中没有元素时称为空栈。
假设栈 S=(a1,a2,a3,…a n)，则 a1称为栈
底元素,an为栈顶元素。栈中元素按 a1,a2，
a3,…a n的次序进栈，退栈的第一个元素应
为栈顶元素。换句话说，栈的修改是按后进
先出的原则进行的。因此，栈称为后进先出
表（ LIFO）。
3.1.2 顺序栈
由于栈是运算受限的线性表，因此线性
表的存储结构对栈也适应。
栈的顺序存储结构简称为顺序栈，它是
运算受限的线性表。因此，可用数组来实
现顺序栈。因为栈底位臵是固定不变的，
所以可以将栈底位臵设臵在数组的两端的
任何一个端点；栈顶位臵是随着进栈和退
栈操作而变化的，故需用一个整型变量 top
例、一叠书或一叠盘子。
栈的抽象数据类型的定义如下,P44
a n
a n-1
a2
a1
……
栈顶
栈底
top
7
6
5
4
3
2
1
-1
来指示当前栈顶的位臵，通常称 top为栈顶指
针。因此，顺序栈的类型定义只需将顺序
表的类型定义中的长度属性改为 top即可。
顺序栈的类型定义如下：
# define StackSize 100
typedef char datatype;
typedef struct {
datatype data[stacksize];
int top;
}seqstack;
设 S是 SeqStack类型的指针变量。若栈
底位臵在向量的低端，即 s–>data[0]是栈
底元素，那么栈顶指针 s–>top是正向增加
的，即进栈时需将 s–>top加 1，退栈时需将
s–>top 减 1。因此,s–>top<0表示空栈,s–
>top =stacksize-1表示栈满。当栈满时再做
进栈运算必定产生空间溢出，简称“上
溢” ;当栈空时再做退栈运算也将产生溢出，
简称“下溢”。上溢是一种出错状态，应
该设法避免之；下溢则可能是正常现象，
因为栈在程序中使用时，其初态或终态都
是空栈，所以下溢常常用来作为程序控制
转移的条件。
3、判断栈满
int stackfull(seqstack *s)
{
return(s–>top==stacksize-1);
}
4、进栈
void push(seqstack *s,datatype x)
{
if (stackfull(s))
error(―stack overflow‖);
s–>data[++s–>top]=x;
}
1、臵空栈
void initstack(seqstack *s)
{
s–>top=-1;
}
2、判断栈空
int stackempty(seqstack *s)
{
return(s–>top==-1);
}
5、退栈
datatype pop(seqstack *s)
{
if(stackempty(s))
error(―stack underflow‖);
x=s–>data[top];
s–>top--;
return(x)
//return(s–>data[s–>top--]);
}
6、取栈顶元素
Datatype stacktop(seqstack *s)
{
if(stackempty(s)
error(―stack is enpty‖);
return s–>data[s–>top];
}
3.1.3 链栈
栈的链式存储结构称为链栈，它是运算是
受限的单链表，克插入和删除操作仅限制
在表头位臵上进行,由于只能在链表头部进
行操作，故链表没有必要像单链表那样附
加头结点。栈顶指针就是链表的头指针。
链栈的类型说明如下：
typedef struct stacknode{
datatype data
struct stacknode *next
}stacknode;
Void initstack(seqstack *p)
{
p–>top=null;
}
int stackempty(linkstack *p)
{
return p–>top==null;
}
? Void push(linkstack *p,datatype x)
{
stacknode *q
q=(stacknode*)malloc(sizeof(stacknode));
q–>data=x;
q–>next=p–>top;
p–>top=p;
}
Datatype pop(linkstack *p)
{
datatype x;
stacknode *q=p–>top;
if(stackempty(p)
error(―stack underflow.‖);
x=q–>data;
p–>top=q–>next;
free(q);
return x;
}
datatype stack top(linkstack *p)
{
if(stackempty(p))
error(―stack is empty.‖);
return p–>top–>data;
}
3.2 栈的应用举例
由于栈结构具有的后进先出的固有特性，
致使栈成为程序设计中常用的工具。以下
是几个栈应用的例子。
3.2.1 数制转换
十进制 N和其它进制数的转换是计算机
实现计算的基本问题,其解决方法很多,其中
一个简单算法基于下列原理,
N=(n div d)*d+n mod d
( 其中,div为整除运算,mod为求余运算 )
例如 (1348)10=(2504)8,其运算过程如下：
n n div 8 n mod 8
1348 168 4
168 21 0
21 2 5
2 0 2
void conversion( ) {
initstack(s);
scanf (―%‖,n);
while(n){
push(s,n%8);
n=n/8;
}
while(! Stackempty(s)){
pop(s,e);
printf(―%d‖,e);
}
}
3.2.2 括号匹配的检验
假设表达式中充许括号嵌套,则检验括号
是否匹配的方法可用, 期待的急迫程度, 这
个概念来描述。例：
（（）（） （（）））
3.2.3 行编辑程序
在编辑程序中，设立一个输入缓冲区，
用于接受用户输入的一行字符，然后逐行存
入用户数据区。允许用户输入错误，并在发
现有误时可以及时更正。
行编辑程序算法如下,
void lineedit( ){
initstack(s);
ch=gether( );
while(ch!=eof){
while(ch!=eof && ch!=?\n‘){
switch(ch){
case ?#‘, pop(s,c);
case ?@‘, clearstack(s);
default, push(s,ch);
}
ch=getchar( );
}
clearstack(s);
if(ch!=eof)
ch=gethar( );
}
destroystack(s);
}
3.2.4 迷宫求解
入口
出
口
3.4 队列
3.4.1 抽象数据类型队列的定义
队列 (Queue)也是一种运算受限的线性表。它只
允许在表的一端进行插入，而在另一端进行删除。
允许删除的一端称为队头 (front)，允许插入的一端
称为队尾 (rear)。
例如：排队购物。操作系统中的作业排队。先进
入队列的成员总是先离开队列。因此队列亦称作先
进先出 (First In First Out)的线性表，简称 FIFO
表。
当队列中没有元素时称为空队列。在空队列中依
次加入元素 a1,a2,… an之后,a1是队头元素,an是队
尾元素。显然退出队列的次序也只能是 a1,a2,… an,
也就是说队列的修改是依先进先出的原则进行的。
下图是队列的示意图：
a1 a2 … an出队 入队
队头 队尾
队列的抽象数据定义见书Ｐ 59
3.4.2 循环队列－队列的顺序表示和实现
队列的顺序存储结构称为顺序队列，顺序队
列实际上是运算受限的顺序表，和顺序表一样，
顺序队列也是必须用一个向量空间来存放当前队
列中的元素。由于队列的队头和队尾的位臵是变
化的，因而要设两个指针和分别指示队头和队尾
元素在队列中的位臵，它们的初始值地队列初始
化时均应臵为０。入队时将新元素插入所指的位
臵，然后将加１。出队时，删去所指的元素，然
后将加１并返回被删元素。由此可见，当头尾指
针相等时队列为空。在非空队列里，头指针始终
指向队头元素，而尾指针始终指向队尾元素的下
一位臵。
０ １ ２ ３ 0 1 2 3
Front
rear
a b c
Front rear
(a)队列初始为空 （ b） A,B,C入队
０ １ ２ ３ ０ １ ２ ３
b c
front rear front
rear
（ c) a出队 (d) b,c出队，队为空
和栈类似，队列中亦有上溢和下溢现象。此外，
顺序队列中还存在, 假上溢, 现象。因为在入队
和出队的操作中，头尾指针只增加不减小，致使
被删除元素的空间永远无法重新利用。因此，尽
管队列中实际的元素个数远远小于向量空间的规
模，但也可能由于尾指针巳超出向量空间的上界
而不能做入队操作。该现象称为假上溢。
为充分利用向量空间。克服上述假上溢现象的方法
是将向量空间想象为一个首尾相接的圆环，并称
这种向量为循环向量，存储在其中的队列称为循
环队列（ Circular Queue)。在循环队列中进行出
队、入队操作时，头尾指针仍要加 1，朝前移动。
只不过当头尾指针指向向量上界（ QueueSize-1）
时，其加 1操作的结果是指向向量的下界 0。
这种循环意义下的加 1操作可以描述为：
if(I+1==QueueSize)
i=0;
else
i++;
利用模运算可简化为, i=(i+1)%QueueSize
显然，因为循环队列元素的空间可以被利用，
除非向量空间真的被队列元素全部占用，否则不
会上溢。因此，除一些简单的应用外，真正实用
的顺序队列是循环队列。
如图所示：由于入队时尾指针向前追赶头指针，
出队时头指针向前追赶尾指针，故队空和队满时
头尾指针均相等。因此，我们无法通过 front=rear
来判断队列“空”还是“满”。
解决此问题的方法至少有三种：
其一是另设一个布尔变量以匹别队列的空和满；
其二是少用一个元素的空间，约定入队前，测试
尾指针在循环意义下加 1后是否等于头指针，若
相等则认为队满（注意,rear所指的单元始终为
空）；
其三是使用一个计数器记录队列中元素的总数
（实际上是队列长度）。下面我们用第三种方
法实现循环队列上的六种基本操作，为此先给
出循环队列的类型定义。
? #define QueueSize 100
? typedef char DataType;
? typedef Struct{
? int front;
? int rear;
? int count;
? datatype data[queuesize]
? }cirqueue;
（ 1）臵空队
void initqueue(cirqueue *q){
q–>front=q–>rear=0;
q–>count=0;
}
（ 2）判断队空
int queueempty(cirqueue *q) {
return q–>count==0;
}
（ 3）判断队满
int queuefull(cirqueue *q){
return q–>count==queuesize;
}
（ 4）入队
void enqueue(cirqueue *q,datatype x)
{
if(queuefull(q))
error(―queue overflow‖);
q–>count++;
q–data[q–rear]=x;
q–rear=(q–rear+1)%queuesize;
}
（ 5）出队
datatype dequeue(cirqueue *q)
{
datatype temp;
if(queueempty(q))
error(―queue underflow‖);
temp=q–>data[q–>front];
q–>count--;
q–front=(q–>front+1)%queuesize;
return temp;
}
（ 6）取头指针
datatype queuefront(cirqueue *q)
{
if(queueempty(q))
error(―queue is empty.‖);
return q–>data[q–>front];
}
? 3.4.3 链队列
? 队列的链式存储结构简称为链队列，它是
限制仅在表头删除和表尾插入的单链表。显然
仅有单链表的头指针不便于在表尾做插入操作，
为此再增加一个尾指针，指向链表的最后一个
结点。于是，一个链队列由一个头指针唯一确
定。和顺序队列类似，我们也是将这两个指针
封装在一起，将链队列的类型 LinkQueue定义
为一个结构类型：
? typedef struct queuenode{
? datatype data;
? struct queuenode *next;
? }queuenode;
typedef struct{
queuenode *front;
queuenode *rear;
}linkqueue;
下面给出链队列上实现的基本运算：
void initqueue(linkqueue *q)
{
q–>front=q–>rear=null;
}
int queueempty(linkqueue *q)
{
return q–>front==null &&q–>rear==null;
}
void enqueue(linkqueue *q,datatype x)
{
queuenode *p
p=(queuenode * )malloc(sizeof(queuenode));
p–>data=x;
p–next=null;
if(queueempty(q))
q–>front=q–>rear=p;
else{
q–>rear–>next=p;
q–rear=p;
}
}
Datatype dequeue(linkqueue *q)
{
datatype x;
queuenode *p
if(queueempty(q))
error(―queue underflow‖);
p=q–>front;
x=p–>data;
q–>front=p–>next;
if(q–>rear==p)
q–rear=null;
free(p);
return x;
}
datatype queuefront(linkqueue *q)
{
if(queueempty(q))
error(―queue is empty.‖);
return q–>front–>data;
}
注意：在出队算法中，一般只需修改队头指针。
但当原队中只有一个结点时，该结点既是队头
也是队尾，故删去此结点时亦需修改尾指针，
且删去此结点后队列变空。
习题
1、设将整数以万计,2,3,4依次进栈，但只要
出栈时栈非空，则可将出栈操作按任何次序夹
入其中，请回答下有问题：
（ 1）若入栈次序为 push(1),pop(),push(2，
push(3),pop(),pop( ),push(4),pop( )，
则出栈的数字序列为什么？
（ 2）能否得到出栈序列车员 423和平共处五项原
则 432？并说明为什么不能得到或如何得到。
（ 3）请分析 1,2,3,4的 24种排列中，哪些序
列可以通过相应的入出栈得到。
2、链栈中为何不设头指针？
3、循环队列的优点是什么？如何判断它的空和
满？
4、设长度为 n的链队列用单循环链表表示，若只
设头指针，则怎样进行入队和出队操作；若只
设尾指针呢？
5、利用栈的基本操作，写一个返回栈 s中结点个
数的算法 int stacksize(seqstack s)，并说明 s为何
不用作为指针参数？
6、利用栈的基本操作，写一个将栈中所有结点
均删除算法，并说明 S为何要作为指针参数？
7、用第二种方法，即少用一个元素空间的方法
来区别循环队列的队空和队满，试设计臵空队、
判队空、判队满、出队、入队及取队头元素等
六个基本操作。
8、假设循环队列只设 rear和 quelen来分别指示队
尾元素的位臵和队中元素的个数，试给出判断
此循环队列的队满条件，并写出相应的入队和
出队算法，要求出队时需返回队头指针。
9、指出下列程序段的功能是什么？
(1) void demo1(seqstack *s){
int I;arr[64];n=0;
while (!stackempty(s)) arr[n++]=pos(s);
for(I=0;<n;I++) push(s,arr[I]);
}
(2) void demo2(seqstack *s,int m){
seqstack t; int i;
initstack(t);
while(! Stackempty(s))
if(I=pop(s)!=m) push(t,I);
While(! Stackempty(t)) {
i=pop(t);
push(s,I);
}
}
第四章 串
? 4.1 串类型的定义
? 4.2 串的表示和实现
4.2.1 定长顺序存储表示
4.2.2 堆分配存储表示
4.2.3 串的块链存储表示
4.1 串类型的定义
一、串和基本概念
串 (String)是零个或多个字符组成的有限序列。
一般记作 S=―a1a2a3… an‖，其中 S 是串名，双引
号括起来的字符序列是串值； ai(1≦ i≦ n)可以
是字母、数字或其它字符；串中所包含的字符
个数称为该串的长度。长度为零的串称为空串
(Empty String)，它不包含任何字符。
通常将仅由一个或多个空格组成的串称为空白
串 (Blank String)
注意：空串和空白串的不同，例如,, 和,”
分别表示长度为 1的空白串和长度为 0的空串。
串中任意个连续字符组成的子序列称为该串的子
串，包含子串的串相应地称为主串。通常将子
串在主串中首次出现时的该子串的首字符对应
的主串中的序号，定义为子串在主串中的序号
（或位臵）。例如，设 A和 B分别为
A=―This is a string‖ B=―is‖
则 B是 A的子串,A为主串。 B在 A中出现了两次，
其中首次出现所对应的主串位臵是 3。因此，
称 B在 A中的序号（或位臵）为 3
特别地，空串是任意串的子串，任意串是
其自身的子串。
通常在程序中使用的串可分为两种：串变量
和串常量。串常量和整常数、实常数一样，在
程序中只能被引用但不能不能改变其值，即只能
读不能写。通常串常量是由直接量来表示的，
例如语句 Error(―overflow‖)中, overflow‖是
直接量。但有的语言允许对串常量命名，以使
程序易读、易写。如 C++中，可定义
const char path[]=―dir/bin/appl‖;
这里 path是一个串常量，对它只能读不能写。串
变量和其它类型的变量一样，其取值是可以改
变的。
二、串的抽象数据定义
串的抽象数据类型定义台书 P71
三、串的基本操作
对于串的基本操作，许多高级语言均提供了相
应的运算或标准库函数来实现。下面仅介绍
几种在 C语言中常用的串运算，其它的串操
作见的文件。
定义下列几个变量：
char s1[20]=―dirtreeformat‖,s2[20]=―file.mem‖;
char s3[30],*p;
int result;
(1) 求串长 (length)
int strlen(char s); //求串的长度
例如,printf(―%d‖,strlen(s1)); 输出 13
（ 2）串复制 (copy)
char *strcpy(char to,char from);
该函数将串 from复制到串 to中，并且返回一个
指向串 to的开始处的指针。
例如,strcpy(s3,s1); //s3=―dirtreeformat‖
(3)联接 (concatenation)
char strcat(char to,char from)
该函数将串 from复制到串 to的末尾，并且返回
一个指向串 to的开始处的指针。
例如,strcat(s3,‖/‖)
strcat(s3,s2); //s3=―dirtreeformat/file.mem‖
(4)串比较（ compare)
int strcmp(chars1,char s2);
该函数比较串 s1和串 s2的大小，当返回值小于 0，
等于 0或大于 0时分别表示 s1<s2\s1=s2或 s1>s2
例如,result=strcmp(―baker‖,‖Baker‖) result>0
result=strcmp(―12‖,‖12‖); result=0
result=strcmp(―Joe‖,‖Joseph‖); result<0
（ 5）字符定位 (index)
char strchr(char s,char c);
该函数是找 c在字符串中第一次出现的位臵，若
找到则返回该位臵，否则返回 NULL。
例如,p=strchr(s2,‖.‖); p 指向,file‖之后的位臵
if(p) strcpy(p,‖.cpp‖); s2=―file.cpp‖
上述串的操作是最基本的，其中后四个还有变种形式：
strncpy,strncat,strncmp,strnchr。串的其余操作可
由这些基本操作组合而成。
例 1、求子串
求子串的过程即为复制字符序列的过程，将串 S
中的第 pos个字符开始长度为 len的字符复制到串 T中。
void substr(string sub,string s,int pos,int len)
{
if(pos<0 || pos>strlen(s)-1 || len<0)
error(―parameter error‖)
strncpy(sub,&s[pos],len);
}
例 2、串的定位 index(s,t,pos)
在主串中取从第 i个字符起、长度和串 T
相等的子串和 T比较，若相等，则求得函数值
为 i，否则值增 1直至 S中不存在和串 T相等的子
串为止。
int index(string s,string t,int pos){
if(pos>0){
n=strlen(s); m=strlen(t); i=pos;
while(i<n-m+1){
substr(sub,s,i,m);
if(strcmp(sub,t)!=0)
++i;
else return(i);
}
}
return(0);
}
4.2 串的表现和实现
因为串是特殊的线性表，故其存储结构与线性
表的存储结构类似。只不过由于组成串的结点是
单个字符。串有三种机内表示方法，下面分别介
绍。
4.2.1定长顺序存储表示
定长顺序存储表示,也称为静态存储分配的顺应
表。它是用一组连续的存储单元来存放串中的字
符序列。所谓定长顺序存储结构，是直接使用定
长的字符数组来定义，数组的上界预先给出：
#define maxstrlen 256
typedef char sstring[maxstrlen];
sstring s; //s是一个可容纳 255个字符的
顺序串。
一般可使用一个不会出现在串中的特殊字符在串
值的尾部来表示串的结束。例如,C语言中以字符
‵ \0′ 表示串值的终结，这就是为什么在上述定义
中，串空间最大值 maxstrlen为 256，但最多只能存
放 255个字符的原因，因为必须留一个字节来存放
‵ \0′ 字符。若不设终结符，可用一个整数来表示
串的长度，那么该长度减 1的位臵就是串值的最后
一个字符的位臵。此时顺序串的类型定义和顺序表
类似：
typedef struct{
char ch[maxstrlen];
int length;
}sstring; //其优点是涉及到串长操作时速度
快。
4.2.2堆分配存储表示
这种存储表示的特点是，仍以一组地址连续的存储
单元存放串值字符序列，但它们的存储空间是在程
序执行过程中动态分配而得。所以也称为动态存储
分配的顺序表。在 C语言中，利用和等动态存储管理
函数，来根据实际需要动态分配和释放字符数组空
间。这样定义的顺序串类型也有两种形式。
typedef char *string; //c中的串库相当于此类型
定义
typedef struct{
char *ch;
int length;
}hsring;
status sinsert(hstring s,int pos,hstring t){
if(pos<1 || pos>s.length+1)
return error;
if(t.length){
if(!(s.ch=(char*)realloc(s.ch,(s.length+t.length
)*sizeof(char)))
exit(overflow);
for(i=s.length-1;i>pos-1;--i)
s.ch[I+t.length]=s.ch[i];
s.ch[pos-1..pos+t.length-
2]=t.ch[0..t.length-1];
s.length+=t.length;
}
return ok;
}
int strlen(hstring s){
return s.length;
}
status clearstring(hstring s){
if(s.ch){free(s.ch);s.ch=NULL;}
s.length=0;
}
status strassign(hstring t,char *chars){
//生成一个其值等于串常量 chars的串 t
if(t.ch) free(t.ch);
for(i=0,(c=chars;c;++i),++c);
if(!i) {
t.ch=null; t.length=0;
}
else{
if(!(t.ch=(char *)malloc(I*sizeof(char))))
exit(overflow);
t.ch[0..i-1]=chars[0..i-1];
t.length=i;
}
}
int strcmp(hstring s,hstring t){
for(i=0;i<s.length && i<t.length;++i)
if(s.ch[i]!=t.ch[i]
return(s.ch[i]-t.ch[i]);
return s.length-t.length;
}
status concat(hstring t,hstring s1,hstring s2){
if(!(t.ch)=(char*)malloc(s1.length+s2.length)*
sizeof(char)))
exit(overflow);
t.ch[0..s1.length-1]=s1.ch[0..s1.length-1];
t.length=s1.length+s2.length;
t.ch[s1.length..t.length-
1]=s2.ch[0..s2.length-1];
}
Status substr(hstring sub,hstring s,int pos,int
len){
if(pos<1 || pos>s.length || len<0 ||
len>s.length-pos+1)
return error;
if(sub.ch) free(sub.ch);
if(!len){
sub.ch=null;
sub.length=0;
}
else{
sub.ch=(char *)malloc(len*sizeof(char));
sub.ch[0..len-1]=s[pos-1..pos+len-2];
s.length=len;
}
}
4.2.3 串的链式存储结构
顺序串上的插入和删除操作不方便，需要
移动大量的字符。因此，我们可用单链表方式来
存储串值，串的这种链式存储结构简称为链串。
typedef struct node{
char data;
struct node *next;
}lstring;
一个链串由头指针唯一确定。
这种结构便于进行插入和删除运算，但存储空
间利用率太低。
为了提高存储密度，可使每个结点存放多个字符。
通常将结点数据域存放的字符个数定义为 结点
的大小,显然，当结点大小大于 1时，串的长
度不一定正好是结点的整数倍，因此要用特殊
字符来填充最后一个结点，以表示串的终结。
对于结点大小不为 1的链串，其类型定为义只
需对上述的结点类型做简单的修改即可。
#define nodesize 80
typedef struct node{
char data[nodesize];
struct node *next;
}lstring;
4.3 串的模式匹配算法
子串定位运算又称为模式匹配 (Pattern
Matching)或串匹配 (String Matching)，此运算
的应用在非常广泛。例如，在文本编辑程序中，
我们经常要查找某一特定单词在文本中出现的位
臵。显然，解此问题的有效算法能极大地提高文
本编辑程序的响应性能。
在串匹配中，一般将主串称为目标串，子串称
之为模式串。设 S为目标串,T为模式串，且不妨
设：
S=―s0s1s2… sn-1‖ T=―t0t1… tm-1‖
串的匹配实际上是对于合法的位臵 0≦ i≦ n-m依
次将目标串中的子串 s[i..i+m-1]和模式串
t[0..m-1]进行比较，若 s[i..i+m-1]=t[0..m-1]，
则称从位臵 i开始的匹配成功，亦称模式 t在目
标 s中出现；若 s[i..i+m-1] ≠t[0..m -1]，
，则称从位臵 i开始的匹配失败。上述的位臵 i
又称为位移，当 s[i..i+m-1]=t[0..m-1]时,i
称为有效位移；当 s[i..i+m-1] ≠t[0..m -1]时，
i称为无效位移。这样，串匹配问题可简化为是
找出某给定模式 T在一给定目标 T中首次出现的有
效位移。
串匹配的算法很多，这里我们只讨论一种最
简单的称为朴素的串匹配算法。其基本思想是用
一个循环来依次检查 n-m+1个合法的位移
i(0≦ i≦ n-m)是否为有效位移，
≠
其算法段为：
for(i=0;i<=n-m;i++){
if(S[i..i+m-1]=T[0..m-1]
return i;
下面以第二种 定长的顺序串类型 作为存储结
构，给出具体的串匹配算法。
int index(sstring s,sstring t,int pos){
int i,j,k;
int m=s.length;
int n=t.length;
for(i=0;i<=n-m;i++){
j=0;k=i;
while(j<m && s.ch[k]==t.ch[j]{
k++;j++;
}
if(j==m)
return i;
}
return –1;
}
显然，该算法在最坏情况下的时间复杂
度为 O((n-m)m)。
链串上的子串定位算法
用结点大小为 1的单链表做串的存储结构时，
实现朴素的匹配算法很简单。只是现在的位移
是结点地址而非整数，且单链表中没有存储长
度信息。若匹配成功，则返回有效位移所指的
结点地址，否则返回空指针。具体算法如下：
lstring *lindex(lstring s,lstring t){
lstring *shift,*q,*p;
shift=S;
q=shift;p=t;
while(q && p){
if(q->data==p->data){
q=q->next;
p=p->next;
}
else{
shift=shift->next;
q=shift;
p=t;
}
}
if(p==null)
return shift;
else
return null;
}
第五章 数组和广义表
? 5.1 数组的定义
? 5.2 数组的顺序表示和实现
? 5.3 矩阵的压缩存储
5.3.1 特殊矩阵
5.3.2 稀疏矩阵
5.4 广义表的定义
5.5 广义表的存储结构
数组和广义表可看成是一种特殊的线性表，其
特殊在于，表中的数所元素本身也是一种线性
表。
5.1 数组的定义
数组是我们最熟悉的数据类型，在早期的高
级语言中，数组是唯一可供使用的数据类型。
由于数组中各元素具有统一的类型，并且数组
元素的下标一般具有固定的上界和下界，因此，
数组的处理比其它复杂的结构更为简单。多维
数组是向量的推广。例如，二维数组：
a11 a12 … a 1n
a21 a22 … a 2n
… … … …
am1 am2 … a mn
Amn=
可以看成是由个行向量组成的向量，也可以看成是
个列向量组成的向量。
在 C语言中，一个二维数组类型可以定义为其分
量类型为一维数组类型的一维数组类型，也就是说，
typedef elemtype array2[m][n];
等价于：
typedef elemtype array1[n];
typedef array1 array2[m];
同理，一个维数组类型可以定义为其数据元素为维
数组类型的一维序组类型。
数组一旦被定义，它的维数和维界就不再改变。
因此，除了结构的初始化和销毁之外，数组只有存
取元素和修改元素值的操作。
5.2 数组的顺序表示和实现
由于计算机的内存结构是一维的，因此
用一维内存来表示多维数组，就必须按
某种次序将数组元素排成一列序列，然
后将这个线性序列存放在存储器中。
又由于对数组一般不做插入和删除操
作，也就是说，数组一旦建立，结构中
的元素个数和元素间的关系就不再发生
变化。因此，一般都是采用顺序存储的
方法来表示数组。
通常有两种顺序存储方式：
⑴行优先顺序 ——将数组元素按行排列，第 i+1个行
向量紧接在第 i个行向量后面。以二维数组为例，按
行优先顺序存储的线性序列为：
a11,a12,…,a1n,a21,a22,… a2n,……,am1,am2,…,amn
在 PASCAL,C语言中，数组就是按行优先顺序存
储的。
⑵列优先顺序 ——将数组元素按列向量排列，第 j+1
个列向量紧接在第 j个列向量之后,A的 m*n个元素按
列优先顺序存储的线性序列为：
a11,a21,…,am1,a12,a22,… am2,……,an1,an2,…,anm
在 FORTRAN语言中，数组就是按列优先顺序存储的。
以上规则可以推广到多维数组的情况：优
先顺序可规定为先排最右的下标，从右到
左，最后排最左下标：列优先顺序与此相
反，先排最左下标，从左向右，最后排最
右下标。
按上述两种方式顺序存储的序组，只
要知道开始结点的存放地址（即基地址），
维数和每维的上、下界，以及每个数组元
素所占用的单元数，就可以将数组元素的
存放地址表示为其下标的线性函数。因此，
数组中的任一元素可以在相同的时间内存
取，即顺序存储的数组是一个随机存取结
构。
例如，二维数组 Amn按, 行优先顺序, 存储在内存
中，假设每个元素占用 d个存储单元。
元素 aij的存储地址应是数组的基地址加上
排在 aij前面的元素所占用的单元数。因为 aij位
于第 i行、第 j列，前面 i-1行一共有 (i-1) × n
个元素，第 i行上 aij前面又有 j-1个元素，故它
前面一共有 (i-1) × n+j-1个元素，因此,aij
的地址计算函数为：
LOC(aij)=LOC(a11)+[(i-1)*n+j-1]*d
同样，三维数组 Aijk按, 行优先顺序, 存储，其
地址计算函数为：
LOC(aijk)=LOC(a111)+[(i-1)*n*p+(j-1)*p
+(k-1)]*d
上述讨论均是假设数组各维的下界是不是 1，
更一般的二维数组是 A[c1..d1,c2..d2]，这
里 c1,c2不一定是 1。 aij前一共有 i-c1行，二
维数组一共有 d2-c2+1列，故这 i-c1行共有
(i-c1)*(d2-c2+1)个元素，第 i行上 aij前一
共有 j-c2个元素，因此,aij的地址计算函数
为：
LOC(aij)=LOC(ac1c2)+[(i-c1)*(d2-c2+1)+j-
c2)]*d
例如，在 C语言中，数组各维下标的下界是
0，因此在 C语言中，二维数组的地址计算公
式为：
LOC(aij)=LOC(a00)+(i*(d2+1)+j)*d
5.3 矩阵的压缩存储
在科学与工程计算问题中，矩阵是一种常用
的数学对象，在高级语言编制程序时，简单而又
自然的方法，就是将一个矩阵描述为一个二维数
组。矩阵在这种存储表示之下，可以对其元素进
行随机存取，各种矩阵运算也非常简单，并且存
储的密度为 1。但是在矩阵中非零元素呈某种规
律分布或者矩阵中出现大量的零元素的情况下，
看起来存储密度仍为 1，但实际上占用了许多单
元去存储重复的非零元素或零元素，这对高阶矩
阵会造成极大的浪费，为了节省存储空间,我
们可以对这类矩阵进行压缩存储：即为多个相同
的非零元素只分配一个存储空间；对零元素不分
配空间。
5.3.1特殊矩阵
所谓特殊矩阵是指非零元素或零元素的分布有一
定规律的矩阵，下面我们讨论几种特殊矩阵的压
缩存储。
1、对称矩阵
在一个 n阶方阵 A中，若元素满足下述性质：
aij=aji 0≦ i,j≦ n-1
则称 A为对称矩阵。如图 5.1便是一个 5阶对称矩阵。
对称矩阵中的元素关于主对角线对称，故只要
存储矩阵中上三角或下三角中的元素，让每两个
对称的元素共享一个存储空间，这样，能节约近
一半的存储空间。不失一般性，我们按, 行优先
顺序”存储主对角线（包括对角线）以下的元素，其
存储形式如图所示：
1 5 1 3 7 a00
5 0 8 0 0 a10 a 11
1 8 9 2 6 a20 a21 a23
3 0 2 5 1 ………………..
7 0 6 1 3 an-1 0 a n-1 1 a n-1 2 …a n-1 n-1
图 5.1 对称矩阵
在这个下三角矩阵中，第 i行恰有 i+1个元素，元素
总数为：
(i+1)=n(n+1)/2
因此，我们可以按图中箭头所指的次序将这些
元素存放在一个向量 sa[0..n(n+1)/2-1]中。为了便
于访问对称矩阵 A中的元素，我们必须在 aij和 sa[k]
之间找一个对应关系。
若 i≧ j，则 ai j在下三角形中。 ai j之前的 i行（从第 0
行到第 i-1行）一共有 1+2+…+i=i(i+1)/2 个元素，在第 i
行上,ai j之前恰有 j个元素（即 ai0,ai1,ai2,…,a ij-1），因
此有：
k=i*(i+1)/2+j 0≦ k<n(n+1)/2
若 i<j，则 aij是在上三角矩阵中。因为 aij=aji，所以只要
交换上述对应关系式中的 i和 j即可得到：
k=j*(j+1)/2+i 0≦ k<n(n+1)/2
令 I=max(i,j),J=min(i,j)，则 k和 i,j的对应关系可统
一为：
k=I*(I+1)/2+J 0≦ k<n(n+1)/2
因此,aij的地址可用下列式计算：
LOC(aij)=LOC(sa[k])
=LOC(sa[0])+k*d=LOC(sa[0]+[I*(I+1)/2+J]*d
有了上述的下标交换关系，对于任意给定一组下标
(i,j)，均可在 sa[k]中找到矩阵元素 aij，反之，对所有
的 k=0,1,2,…n(n -1)/2-1，都能确定 sa[k]中的元素在矩阵
中的位臵 (i,j)。由此，称 sa[n(n+1)/2]为阶对称矩阵 A的
压缩存储，见下图：
k=0 1 2 3 n(n-1)/2 n(n-1)/2-1
例如 a21和 a12均存储在 sa[4]中，这是因为
k=I*(I+1)/2+J=2*(2+1)/2+1=4
a00 a10 a11 a20 …… an-1 0 …
…
an-1,n-1
2、三角矩阵
以主对角线划分，三角矩阵有上三角和下三角两种。
上三角矩阵如图所示，它的下三角（不包括主对角线）
中的元素均为常数。下三角矩阵正好相反，它的主对
角线上方均为常数，如图所示。在大多数情况下，
三角矩阵常数为零。
a00 a01 … a 0 n-1 a00 c … c
c a11 … a 1 n-1 a10 a11 … c
………………….,……………..
c c … a n-1 n-1 an-1 0 an-1 1 … a n-1 n-1
(a)上三角矩阵 (b)下三角矩阵
图 5.2 三角矩阵
三角矩阵中的重复元素 c可共享一个存储空间，
其余的元素正好有 n(n+1)/2个，因此，三角矩阵
可压缩存储到向量 sa[0..n(n+1)/2]中，其中 c存
放在向量的最后一个分量中，
上三角矩阵中，主对角线之上的第 p行
(0≦ p<n)恰有 n-p个元素，按行优先顺序存放上
三角矩阵中的元素 aij时,aij之前的 i行一共有
(n-p)=i(2n-i+1)/2
个元素，在第 i行上,aij前恰好有 j-i个元素：
aij,aij+1,… aij-1。因此,sa[k]和 aij的对应关系
是：
i(2n-i+1)/2+j-i 当 i≦ j
n(n+1)/2 当 i>jk=
下三角矩阵的存储和对称矩阵类似,sa[k]和 aij对
应关系是：
i(i+1)/2+j i≧ j
n(n+1)/2 i>j
3、对角矩阵
对角矩阵中，所有的非零元素集中在以主对角线为
了中心的带状区域中，即除了主对角线和主对角线
相邻两侧的若干条对角线上的元素之外，其余元素
皆为零。下图给出了一个三对角矩阵，
a00 a01
a10 a11 a12
a21 a22 a23
…,….,…,图 5.3 对角矩阵
an-2 n-3 an-2 n-2 an-2 n-1
an-1 n-2 an-1 n-1
k=
非零元素仅出现在主对角 (aii,0≦ i≦ n-1上，
紧邻主对角线上面的那条对角线上
(aii+1,0≦ i≦ n-2)和紧邻主对角线下面的
那条对角线上 (ai+1 i,0≦ i≦ n-2)。显然，
当 ∣ i-j∣ >1时，元素 aij=0。
由此可知，一个 k对角矩阵 (k为奇数 )A是满
足下述条件的矩阵：若 ∣ i-j∣ >(k-
1)/2,则元素 aij=0。
对角矩阵可按行优先顺序或对角线的顺
序，将其压缩存储到一个向量中，并且
也能找到每个非零元素和向量下标的对
应关系。
在三对角矩阵里附满足条件 i=0,j=0,1，或
i=n-1j=n-2,n-1或 1<i<n-1,j=i-1,i,i+1的元
素 aij外，其余元素都是零。
对这种矩阵，我们也可按行优序为主序来存储。
除第 0行和第 n-1行是 2个元素外，每行的非零元
素都要是 3个，因此，需存储的元素个数为 3n-2。
a00 a01 a10 a11 a12 a21 … … a n-1 n-2 a n-1 n-1
K=0 1 2 3 4 5 … … 3n -2 3n-1
数组 sa中的元素 sa[k]与三对角带状矩阵中的元
素 aij存在一一对应关系，在 aij之前有 i行,共有 3*i-1
个非零元素，在第 i行，有 j-i+1个非零元素，这样，
非零元素 aij的地址为：
LOC(i,j)=LOC(0,0)+[3*i-1+(j-i+1)]*d
=LOC(0,0)+(2i+j)*d
上例中,a34对应着 sa[10]。
k=2*i+j=2*3+4=10
a21对应着 sa[5]
k=2*2+1=5
由此，我们称 sa[0..3*n-2]是阶三对角带
状矩阵 A的压缩存储表示。
上述的各种特殊矩阵，其非零元素的分布
都是有规律的，因此总能找到一种方法
将它们压缩存储到一个向量中，并且一
般都能找到矩阵中的元素与该向量的对
应关系，通过这个关系，仍能对矩阵的
元素进行随机存取。
5.3.2 稀疏矩阵
什么是稀疏矩阵？简单说，设矩阵 A中有
s个非零元素，若 s远远小于矩阵元素的
总数（即 s≦ m× n），则称 A为稀疏矩阵。
精确点，设在的矩阵 A中，有 s个非零元素。
令 e=s/(m*n)，称 e为矩阵的稀疏因子。
通常认为 e≦ 0.05时称之为稀疏矩阵。在
存储稀疏矩阵时，为了节省存储单元，
很自然地想到使用压缩存储方法。但由
于非零元素的分布一般是没有规律的，
因此在存储非零元素的同时，还必须同
时记下它所在的行和列的位臵（ i,j)。
反之，一个三元组 (i,j,aij)唯一确定了
矩阵 A的一个非零元。因此，稀疏矩阵可
由表示非零元的三元组及其行列数唯一
确定。
例如，下列三元组表
((1,2,12)(1,3,9),(3,1,- 3),(3,6,14),(4,3,24),
(5,2,18),(6,1,15),(6,4,-7))
加上 (6,7)这一对行、列值便可作为下列矩阵 M的
另一种描述。而由上述三元组表的不同表示方法
可引出稀疏矩阵不同的压缩存储方法。
0 12 9 0 0 0 0 0 0 -3 0 0 15
0 0 0 0 0 0 0 12 0 0 0 18 0
-3 0 0 0 0 14 0 9 0 0 24 0 0
0 0 24 0 0 0 0 0 0 0 0 0 –7
0 18 0 0 0 0 0 0 0 14 0 0 0
15 0 0 –7 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0
图 5.4 稀疏矩阵 M和 T
M=
T=
一、三元组顺序表
假设以顺序存储结构来表示三元组表，则可
得到稀疏矩阵的一种压缩存储方法 ——三元顺
序表。
#define maxsize 10000
typedef int datatype;
typedef struct{
int i,j;
datatype v;
}triple;
typedef struct{
triple data[maxsize];
int m,n,t;
}tripletable;
设 A为 tripletable型的结构变量，图 5.4中所
示的稀疏矩阵的三元组的表示如下：
i j v
1 2 12
1 3 9
3 1 -3
3 6 14
4 3 24
5 2 18
6 1 15
6 4 -7
下面以矩阵的转臵为例，说明在这种压缩存储
结构上如何实现矩阵的运算。
一个 m× n的矩阵 A，它的转臵 B是一个 n× m的
矩阵，且 a[i][j]=b[j][i],0≦ i≦ m,0≦ j≦ n，
即 A的行是 B的列,A的列是 B的行。
将 A转臵为 B，就是将 A的三元组表 a.data臵换
为表 B的三元组表 b.data，如果只是简单地交换
a.data中 i和 j的内容，那么得到的 b.data将是一
个按列优先顺序存储的稀疏矩阵 B，要得到按行
优先顺序存储的 b.data，就必须重新排列三元组
的顺序。
由于 A的列是 B的行，因此，按 a.data的列
序转臵，所得到的转臵矩阵 B的三元组表 b.data
必定是按行优先存放的。
按这种方法设计的算法，其基本思想是：对 A中
的每一列 col(0≦ col≦ n-1)，通过从头至尾
扫描三元表 a.data，找出所有列号等于 col的
那些三元组，将它们的行号和列号互换后依次
放入 b.data中，即可得到 B的按行优先的压缩
存储表示。
i j v
1 3 -3
1 6 15
2 1 12
2 5 18
3 1 9
3 4 24
4 6 -7
6 3 14
Void transmatrix(tripletable a,tripletable b)
{
int p q col;
b.m=a.n;
b.n=a.m;
b.t=a.t;
if(b.t<=0)
printf(―A=0\n‖);
q=0;
for(col=1;col<=a.n;col++)
for(p=0;p<=a.t;p++)
if(a.data[p].j==col){
b.data[q].i=a.data[p].j;
b.data[q].j=a.data[p].i;
b.data[q].v=a.data[p].v;
q++;
}
}
分析这个算法，主要的工作是在 p和 col的两个
循环中完成的，故算法的时间复杂度为
O(n*t)，即矩阵的列数和非零元的个数的乘
积成正比。而一般传统矩阵的转臵算法为：
for(col=0;col<=n-1;++col)
for(row=0;row<=m;++row)
t[col][row]=m[row][col];
其时间复杂度为 O(n*m)。当非零元素的个数
t和 m*n同数量级时，算法 transmatrix的时
间复杂度为 O(n*n2)。
三元组顺序表虽然节省了存储空间，但时
间复杂度比一般矩阵转臵的算法还要复
杂，同时还有可能增加算是法的难度。
因此，此算法仅适用于 t<=m*n的情况。
下面给出另外一种称之为快速转臵的算法，
其算法思想为：对 A扫描一次，按 A第二
列提供的列号一次确定位臵装入 B的一个
三元组。具体实施如下：一遍扫描先确
定三元组的位臵关系，二次扫描由位臵
关系装入三元组。可见，位臵关系是此
种算法的关键。
为了预先确定矩阵 M中的每一列的第一个非
零元素在数组 B中应有的位臵，需要先求
得矩阵 M中的每一列中非零元素的个数。
因为：矩阵 M中第一列的第一个非零元素
在数组 B中应有的位臵等于前一列第一个
非零元素的位臵加上前列非零元素的个
数。
为此，需要设臵两个一维数组
num[0..n]和 cpot[0..n]
num[0..n]：统计 M中每列非零元素的个数，
num[col]的值可以由 A的第二列求得。
cpot[0..n]：由递推关系得出 M中的每列第
一个非零元素在 B中的位臵。
算法通过 cpot数组建立位臵对应关系：
cpot[1]=1
cpot[col]=cpot[col-1]+num[col-1]
2<=cpl<=a.n
例如：图 5.4中的矩阵 M和相应的三元组 A可
以求得 num[col]和 cpot[col]的值如下：
col 1 2 3 4 5 6 7
num[col] 2 2 2 1 0 1 0
cpot[col] 1 3 5 7 8 8 9
1 2 v
q …
A i j v 第一列元素个数 第二列元素个数
第三列元素个数
num
cpot
q=cpot[col]
2 1 v
p
p
快速转臵算法如下：
void fasttranstri(tritupletable b,tritupletable a){
int p,q,col,k;
int num[0..a.n],copt[0..a.n];
b.m=a.n; b.n=a.m; b.t=a.t;
if(b.t<=0)
printf(―a=0‖\n);
for(col=1;col<=a.u;++col)
num[col]=0;
for(k=1;k<=a.t;++k)
++num[a.data[k].j];
cpot[0]=1;
for(col=2;col<=a.t;++col)
cpot[col]=cpot[col-1]+num[col-1];
for(p=1;p<=a.t;++p){
col=a.data[p].j; q=cpot[col];
b.data[q].i=a.data[p].j;
b.data[q].j=a.data[p].i;
b.data[q].v=a.data[p].v; ++cpot[col];
}
}
}
二、带行表的三元组
有时为了方便某些矩阵运算，我们在
按行优先存储的三元组中，加入一个行
表来记录稀疏矩阵中每行的非零元素在
三元组表中的起始位臵。当将行表作为
三元组表的一个新增属性加以描述时，
我们就得到了稀疏矩阵的另一种顺序存
储结构：带行表的三元组表。其类型描
述如下：
#define maxrow 100
typedef struct{
triple data[maxsize];
int rpos[maxrow];
int n,m,t;
}rtripletable
下面讨论两个稀疏矩阵相乘的例子，容易看
出这种表示方法的优越性。
两个矩阵相乘的经典算法也是大家所熟悉的。
若设 Q=M*N
其中,M是 m1*n1矩阵,N是 m2*n2矩阵。
当 n1=m2时有：
for(i=1;i<=m1;++i)
for(j=1;j<=n2;++j){
q[i][j]=0
for(k=1;k<=n1;++k)
q[i][j]+=m[i][k]*n[k][j];
}
此算法的复杂度为 O(m1*n1*n2)。
当 M和 N是稀疏矩阵并用三元组表存储结构时，
就不能套用上述算法。假设 M和 N分别为：
3 0 0 5
0 -1 0 0
2 0 0 0
M=
0 2
1 0
-2 4
0 0
N=
则 Q=M*N为：
0 6
-1 0
0 4
Q=
它们的三元组、和分别为：
i j v i j v i j v
1 1 3 1 2 2 1 2 6
1 4 5 2 1 1 2 1 -1
3 2 -1 3 1 -2 3 2 4
3 1 2 3 2 4 q.data
m.data n.data
稀疏矩阵相乘的基本思想是：对于 M中每个元素 M，
找到 N 中所有满足条件的元素，求得和的乘积，
而从式得知，乘积矩阵 Q中每个元素的值是个
累加和，这个乘积只是中的一部分。为了便于
操作，应对每个元素设一累加和的变量，其初
值为零，然后扫描数组 M，求得相应元素的乘
积并累加到适当的求累计和的变量上。
void multsmatrix( rtripletable a,
rtripletable b,
rtripletable c){
if(a.n!=b.m){
printf(―error\n‖); exit(0);
}
c.m=a.m; c.n=b.n; c.t=0;
if(a.t*b.t!=0){
for(arow=1;arow<=a.m;++arow){
ctemp[arow]=0;
c.rpos[arow]=c.t+1;
for(p=a.rops[arow];p<a.rpos[arow+1];++p){
brow=a.data[p].j;
if(brow<b.t) t=b.rpos[brow+1]
else t=b.t+1;
for(q=b.rpos[brow]; q<t;++q){
ccol=n.data[q].j;
ctemp[ccol]+=a.data[p].v*b.data[q].v;
}
}
for(ccol=1;ccol<=c.n;++ccol)
if(ctemp[ccol]){
if(++c.t>maxsize)
exit(0);
c.data[c.t]={arow,ccol,ctemp[ccol]};
}
}
}
}
5.4 广义表的定义
广义表（ Lists，又称列表）是线性表的推广。
在第 2章中，我们把线性表定义为 n>=0个元素
a1,a2,a3,…,an的有限序列。线性表的元素仅限
于原子项，原子是作为结构上不可分割的成分，
它可以是一个数或一个结构，若放松对表元素
的这种限制，容许它们具有其自身结构，这样
就产生了广义表的概念。
广义表是 n(n>=0)个元素 a1,a2,a3,…,an的有
限序列，其中 ai或者是原子项，或者是一个广
义表。通常记作 LS=（ a1,a2,a3,…,an)。 LS是广
义表的名字,n为它的长度。若 ai是广义表，则
称它为 LS的子表。
第六章 树和二叉树
? 6.1 树的定义和基本概念
? 6.2 二叉树
6.2.1 树的定义和基本术语
6.2.2 二叉树的性质
6.2.3 二叉树的存储结构
6.3 遍历二叉树
6.3.1 遍历二叉树
6.3.2 线索二叉树
6.4 树和森林
6.4.1 树的存储结构
6.4.2 森林与二叉树的转换
通常用圆括号将广义表括起来，用逗号分隔其中的
元素。为了区别原子和广义表，书写时用大写字母
表示广义表，用小写字母表示原子。若广义表
LS（ n>=1)非空，则 a1是 LS的 表头,其余元素组成
的表 (a1,a2,…a n)称为 LS的 表尾 。
显然广义表是递归定义的，这是因为在定义广
义表时又用到了广义表的概念。广义表的例子如下：
（ 1） A=（） ——A是一个空表，其长度为零。
（ 2） B=（ e） ——表 B只有一个原子 e,B的长度为 1。
（ 3） C=（ a,(b,c,d))——表 C的长度为 2，两个元素分别
为原子 a和子表 (b,c,d)。
（ 4） D=（ A,B,C） ——表 D的长度为 3，三个元素
都是广义表。显然，将子表的值代入后，则有
D=(( ),(e),(a,(b,c,d)))。
（ 5） E=（ E） ——这是一个递归的表，它的长度为 2，
E相当于一个无限的广义表 E=(a,(a,(a,(a,…)))).
从上述定义和例子可推出广义表的三个重要结论：
（ 1）广义表的元素可以是子表，而子表的元素还可以
是子表，。由此，广义表是一个多层次的结构，可以
用图形象地表示。 P108
（ 2）广义表可为其它表所共享。例如在上述例（ 4）
中，广义表 A,B,C为 D的子表，则在 D中可以不必
列出子表的值，而是通过子表的名称来引用。
（ 3）广义表的递归性。
综上所述，广义表不仅是线性表的推广，也是树的
推广。
由表头、表尾的定义可知：任何一个非空广义表其表
头可能是广义表，也可能是广义表，而其表尾必定是
广义表。
gethead(B)=e gettail(B)=( )
gethead(D)=A gettail(D)=(B,C)
由于（ B,C）为非空广义表，则可继续分解得到：
gethead(B,C)=B gettail(B,C)=(C)
注意广义表（ ）和 ( ( ) )不同。前者是长度为 0的空表，
对其不能做求表头的和表尾的运算；而后者是长度为 1
的非空表（只不过该表中唯一的一个元素是空表）。对
其可进行分解，得到表头和表尾均为空表（ ）。
5.5 广义表的存储结构
由于广义表 (a1,a2,a3,…an) 中的数据元素可以具有
不同的结构，（或是原子，或是广义表），因此，难
以用顺序存储结构表示，通常采用链式存储结构，每
个数据元素可用一个结点表示。
由于广义表中有两种数据元素，原子或广义表，
因此，需要两种结构的结点：一种是表结点，一种是
原子结点。 下面介绍两种广义表的链式存储结构。
1、表结点由三个域组成：标志域、指示表头的指针
域和指示表尾的指针域；而原子域只需两个域：标志
域和值域。
表结点 原子结点
tag=1 hp tp tag=0 atom
其类型定义如下：
typedef enum{ATOM,LIST}elemtag;
typedeg struct glnode{
elemtag tag;
union{
atomtype atom;
struct {
struct glnode *hp,*tp;
}ptr;
};
} *glist;
例见书 P109。
2、表结点由三个域组成：标志域、指示表头的指针
域和指示表尾的指针域；原子结点的三个域为：标志
域、值域和指示表尾的指针域。
tag=1 hp tp tag=0 atom tp
表结点 原子结点
其类型定义如下：
typedef enum{atom,list}elemtag;
Typedef struct glnode{
elemtag tag;
union{
atomtype atom;
struct glnode *hp;
};
struct glnode *tp;
} *glist;
例见书 P110
第六章 树和二叉树
6.1 树的定义和基本概念
6.2 二叉树
6.2.1 树的定义和基本术语
6.2.2 二叉树的性质
6.2.3 二叉树的存储结构
6.3 遍历二叉树
6.3.1 遍历二叉树
6.3.2 线索二叉树
6.4 树和森林
6.4.1 树的存储结构
6.4.2 森林与二叉树的转换
6.4.3树和森林的遍历
6.6 赫夫曼树及其应用
6.6.1 最优二叉树（赫夫曼树）
6.6.2 赫夫曼编码
树型结构是一类重要的非线性结构。树型结
构是结点之间有分支，并且具有层次关系的结构，
它非常类似于自然界中的树。树结构在客观世界
国是大量存在的，例如家谱、行政组织机构都可
用树形象地表示。树在计算机领域中也有着广泛
的应用，例如在编译程序中，用树来表示源程序
的语法结构；在数据库系统中，可用树来组织信
息；在分析算法的行为时，可用树来描述其执行
过程。等等。
6.1 树的定义和基本术语
定义：树 (Tree)是 n(n>=0)个结点的有限集 T,T
为空时称为空树，否则它满足如下两个条件：
（ 1）有且仅有一个特定的称为根 (Root)的结点；
(2)其余的结点可分为 m(m>=0)个互不相交的子集
T1,T2,T3… Tm，其中每个子集又是一棵树，并称
其为子树 (Subtree)。
6.2 二叉树
二叉树在树结构的应用中起着非常重要的作
用，因为对二叉树的许多操作算法简单，而任何
树都可以与二叉树 相互转换，这样就解决了树的
存储结构及其运算中存在的复杂性。
6.2.1 二叉树的定义
定义：二叉树是由 n(n>=0)个结点的有限集合构成，
此集合或者为空集，或者由一个根结点及两棵互
不相交的左右子树组成，并且左右子树都是二叉
树。
这也是一个 递归 定义。二叉树可以是空集合，
根可以有空的左子树或空的右子树。二查树不是
树的特殊情况，它们是两个概念。
二叉树结点的子树要区分左子树和右子树，即使只有
一棵子树也要进行区分，说明它是左子树，还是右子
树。这是二叉树与树的最主要的差别。图 6.8列出二
差树的 5种基本形态，图 6.8(C) 和图 6.8（ d）是不同
的两棵二叉树。
(a)
空二叉树
A A
B
A
B
A
CB
(b)
根和空的
左右子树
(c)
根和左子树
(d)
根和右子树
(e)
根和左右子树
图 6.8 二叉树的 5种形式
6.2.2 二叉树的性质
二叉树具有下列重要性质：
性质 1,在二叉树的第 i层上至多有 2i-1个结点
(i>=1)。
采用归纳法证明此性质。
当 i=1时，只有一个根结点,2i-1=20 =1,命题成立。
现在假定多所有的 j,1<=j<i,命题成立，即第 j层
上至多有 2j-2个结点，那么可以证明 j＝ i时命题也成
立。由归纳假设可知，第 i－ 1层上至多有 2i-2个结点。
由于二叉树每个结点的度最大为 2，故在第 i层上最
大结点数为第 i－ 1层上最大结点数的二倍，
即 2× 2i-2＝ 2i-1。
命题得到证明。
性质 2：深度为 k的二叉树至多有 2k－ 1个结点（ k>=1).
深度为 k的二叉树的最大的结点时为二叉树中每层上
的最大结点数之和，由性质 1得到每层上的最大结点
数，,EkI=1（第 i层上的最大结点数） = EkI=12i-
1=2k –1
性质 3,对任何一棵二叉树，如果其终端结点数为
n0，度为 2的结点数为 n2，则 n0＝ n2＋ 1。
设二叉树中度为 1的结点数为 n1，二叉树中总结点数
为 N，因为二叉树中所有结点均小于或等于 2，所以
有,N＝ n0＋ n1＋ n2 (6-1)
再看二叉树中的分支数，除根结点外，其余结点都
有一个进入分支，设 B为二叉树中的分支总数，
则有,N＝ B＋ 1。
由于这些分支都是由度为 1和 2的结点射出的，所
有有：
B＝ n1+2*n2
N＝ B＋ 1＝ n1＋ 2× n2＋ 1 （ 6－ 2)
由式（ 6－ 1）和（ 6－ 2）得到：
n0+n1+n2=n1+2*n2+1
n0＝ n2＋ 1
下面介绍两种特殊形态的二叉树：满二叉树和完
全二叉树。
一棵深度为 k且由 2k-1个结点的二叉树称为满二
叉树。图 6.9就是一棵满二叉树，对结点进行
了顺序编号。
如果深度为 k、由 n个结点的二叉树中个结点能够
与深度为 k的顺序编号的满二叉树从 1到 n标号的
结点相对应，
2
4 5
3
6 7
1
图 6.9 满二叉树
1
2 3
4 5 6
1
2 3
4 5 7
1
2 3
6 7
(a)完全二叉树 (b)非完全二叉树 ( c)非完全二叉树
图 6.10 完全二叉树
则称这样的二叉树为完全二叉树，图 6..10（ b）、
c）是 2棵非完全二叉树。满二叉树是完全二叉树的
特例。
完全二叉树的特点是：
（ 1)所有的叶结点都出现在第 k层或 k－ 1层。
（ 2）错任一结点，如果其右子树的最大层次为 1，
则其左子树的最大层次为 1或 l＋ 1。
性质 4：具有 n个结点的完全二叉树的深度为
[log2n]＋ 1。
符号 【 x】 表示不大于 x的最大整数。
假设此二叉树的深度为 k，则根据性质 2及完
全二叉树的定义得到,2k-1－ 1<n<=2k-1 或
2k-1<=n<2k
取对数得到,k－ 1<log2n<k 因为 k是整数。所以
有,k＝ 【 log2n】 ＋ 1。
性质 5,如果对一棵有 n个结点的完全二叉树的结点按
层序编号（从第 1层到第 【 log2n】 +1层，每层从左到
右 ),则对任一结点 i（ 1<=i<=n),有：
（ 1）如果 i＝ 1，则结点 i无双亲，是二叉树的根；
如果 i>1，则其双亲是结点 【 i/2】 。
（ 2）如果 2i>n，则结点 i为叶子结点，无左孩子；
否则，其左孩子是结点 2i。
（ 3）如果 2i＋ 1>n，则结点 i无右孩子；否则，其右
孩子是结点 2i＋ 1。
[I/2]
i I+1
2i 2i+1 2(I+1) 2i+3
I+1
2(I+1) 2i+3
i
2i 2i+1
图 6.11 完全二叉树中结点 I和 i+1
(a)I和 i+1结点在同一层 (b)I和 i+1结点不在同一层
如图 6.11所示为完全二叉树上结点及其
左右好在结点之间的关系。
在此过程中，可以从（ 2）和（ 3）推出（ 1），所
以先证明（ 2）和（ 3）。
对于 i＝ 1，由完全二叉树的定义，其左孩子是结
点 2，若 2>n，即不存在结点 2，此是，结点 i无孩子。
结点 i的由孩子也只能是结点 3，若结点 3不存在，即
3>n，此时结点 i无右孩子。
对于 i>1，可分为两种情况：
（ 1）设第 j（ 1<=j<=[log2n])层的第一个结点的编
号为 i，由二叉树的性质 2和定义知 i＝ 2j-1
结点 i的左孩子必定为的 j＋ 1层的第一个结点，其编号
为 2j＝ 2× 2j-1＝ 2i。如果 2i>n，则无左孩子：
（ 2）假设第 j（ 1<=j<=[log2n])层上的某个
结点编号为 i（ 2e(j-1)<=i<=2ej-1),且 2i＋ 1<n，
其左孩子为 2i，右孩子为 2i＋ 1，则编号为 i＋ 1
的结点时编号为 i的结点的右兄弟或堂兄弟。若
它有左孩子，则其编号必定为 2i＋ 2＝ 2× （ i＋
1）：若它有右孩子，则其编号必定为 2i＋ 3＝
2× （ i＋ 1）＋ 1。
当 i＝ 1时，就是根，因此无双亲，当 i>1时，如
果 i为左孩子，即 2× （ i/2)=i,则 i/2是 i的双亲；
如果 i为右孩子,i＝ 2p+1,i的双亲应为 p,p＝
（ i－ 1） /2=[i/2],证毕。
6.2.3 二叉树的存储结构
1.顺序存储结构
它是用一组连续的存储单元存储二叉树的数
据元素。因此，必须把二叉树的所有结点安排成
为一个恰当的序列，结点在这个序列中的相互位
臵能反映出结点之间的逻辑关系，用编号的方法：
#define max-tree-size 100
Typedef telemtype sqbitree[max-tree-size];
Sqbitree bt
从树根起，自上层至下层，每层自左至右的
给所有结点编号缺点是有可能对存储空间造成极
大的浪费，在最坏的情况下，一个深度为 H且只
有 H个结点的右单支树确需要 2h-1个结点存储空
间。而且，若经常需要插入与删除树中结点时，
顺序存储方式不是很好！
A B C D E F G H I J K L
1 2 3 4 5 6 7 8 9 10 11 12
完全二叉树 a
b c
d e f g
h i j k l
A
B C
D E
F G
? ?
? ?
? 表示该处没有元素
存在仅仅为了好理解
A B C D E ? ? ? ? F G
一般二叉树
顺序存储结构的算法：
Status CreateBiTree(BiTree *T) {
scanf(&ch);
if(ch= =") T=NULL;
else{
if(!(T=(BiTNode *)malloc(sizeof(BiTNode))))
exit(OVERFLOW);
T–>data=ch;
CreateBiTree(T–>lchild);
CreateBiTree(T–>rchildd);
}
return OK;
}
（ 2）二叉链表法
存储二叉树经常用二叉链表法
A
^ B C ^
D ^ E
^ F ^ ^ G ^ ^ H ^
lchild Data rchild
二叉树的二叉链表存储表示
Typedef struct BiTNode {
TelemType data;
struct BiTNode *lchild,*rchild;
} BiTNode,*BiTree;
有时也可用数组的下标来模拟指针,即开辟三个一
维数组 Data,lchild,rchild 分别存储结点的元素
及其左,右指针域 ;
6.3 遍历二叉树和线索二叉树
6.3.1遍历二叉树
在二叉树的一些应用中，常常要求在树中查找具有某
种特征的结点，或者对树中全部结点逐一进行某种处
理。这就引入了遍历二叉树的问题，即如何按某条搜
索路径巡访树中的每一个结点，使得每一个结点均被
访问一次，而且仅被访问一次。
遍历对线性结构是容易解决的，而二叉树是非线性的，
因而需要寻找一种规律，以便使二叉树上的结点能排
列在一个线性队列上，从而便于遍历。
b c
a
(根结点 )
(右子树 )
(左子树 )
由二叉树的递归定义，
二叉树的三个基本组成
单元是：根结点、左子
树和右子树。
假如以 L,D,R分别表示遍历左子树、遍历根结点和
遍历右子树，遍历整个二叉树则有 DLR,LDR,LRD、
DRL,RDL,RLD六种遍历方案。若规定先左后右，则只有前
三种情况，分别规定为：
DLR——先（根）序遍历，
LDR——中（根）序遍历，
LRD——后（根）序遍历。
1,先序遍历二叉树 的操作定义为：
若二叉树为空，则空操作；否则
（ 1）访问根结点；
（ 2）先序遍历左子树；
（ 3）先序遍历右子树。
2,中序遍历二叉树 的操作定义为：
若二叉树为空，则空操作；否则
（ 1）中序遍历左子树；
（ 2）访问根结点；
（ 3）中序遍历右子树。
3,后序遍历二叉树 的操作定义为：
若二叉树为空，则空操作；否则
（ 1）后序遍历左子树；
（ 2）后序遍历右子树；
（ 3）访问根结点。
例如图（ 1）所示的二叉树表达式
(a+b*(c-d)-e/f)
若先序遍历此二叉树,按访问结点的先后次序将结
点排列起来,其先序序列为：
-+a*b-cd/ef
按中序遍历,其中序序列为：
a+b*c-d-e/f
按后序遍历,其后序序列为：
abcd-*+ef/-
人喜欢中缀形式的算术
表达式,对于计算机,使
用后缀易于求值 图 （ 1）
－
＋
*a
/
b -
dc
fe
TREENODE *creat_tree()
{
TREENODE *t;
char c;
c=getchar();
if(c= =?#‘) return(NULL);
else{
t=(TREENODE *)malloc(sizeof(TREENODE))
t – >data=c;
t –>lchild=create_tree();
t –>rchild=create –tree(); }
return(t);
}
中序遍历算法,
#include<stdio.h>
#include<stdlib.h>
#define NULL 0
Typedef struct node{
char data;
struct node *lchild,*rchild;
}TREENODE;
TREENODE *root;
TREENODE *creat_tree();
Void inorder(TREENODE *);
Void inorder(TREENODE *p)
{
if(p!=NULL)
{ inorder(p–>lchild);
printf(―%c‖,p–>data)
inorder(p–>rchild);
}
}
（ 3）三叉链表
其它见书 P127
lchild data parent rchild
线索二叉树：
当以二叉链表作为存储结构时,只能找到结点的
左右孩子的信息,而不能在结点的任一序列的前驱
与后继信息,这种信息只有在遍历的动态过程中才
能得到,为了能保存所需的信息,可增加标志域 ;
其中,
0 lchild 域指示结点的左孩子
ltag={ 1 lchild 域指示结点的前驱
0 rchild 域指示结点的右孩子
rtag={ 1 rchild 域指示结点的后驱
以这种结构构成的二叉链表作为二叉树的存储
结构,叫做线索链表,其中指向结点前驱与后继的指
针叫做线索,加上线索的二叉树称之为线索二叉树
lchild ltag data rtag rchild
二叉树的二叉线索存储表示,
Typedef enum{Link,Thread}PointerTag;
Link= =0:指针,Thread= =1:线索
Typedef struct BiThrNode{
TelemType data;
struct BiTreeNode *lchild,*rchild;
PointerTag LTag,Rtag;
}BiTreeNode,*BiThrTree;
模仿线性表的存储结构,在二叉树的线索链表上也
添加一个头结点,令其 lchild域的指针指向二叉树的
根结点,其 rchild域的指针指向中序遍历时访问的最
后一个结点 ;同时,令二叉树中序序列中的第一个结点
lchild域 指针的和最后一个结点 rchild域的指针均
指向头结点 ;就像为二叉树建立了一个双向线索链表,
就好比人在一个圆圈上走路,有可能存在好走的可能
性,
Status InorderTraverse_Thr(BiThrTree
T,status(*visit)(TElemType)){
//T指向头结点,头结点的 lchild左链指向根结点
//中序遍历二叉线索树的非递归算法,对每个数据元素调用
//函数 Visit
P=T–>lchild;
while(p!=T){
while(p –>LTag = =Link) p=p –>lchild;
if(!visit(p –>data)) return error;
while(p –>RTag = =Thread&&p –>rchild!=T) {
p=p –>rchild; Visit(p –>data);
}
p= p–>rchild;
}
return OK;
}//InorderTraverse_Thr
P134, Status InorderThreading(BiThrTree &Thrt,BiThrTree T){
if(!(Thrt =(BiThrTree)malloc(sizeof(BiThrNode))))
exit(OVERFLOW);
Thrt –>LTag =Link; Thrt –>RTag =Thread;
Thrt –>rchild=Thrt;
if(!T) Thrt –>lchild=Thrt;
else{
Thrt –>lchild=T; pre=Thrt;
InThrTreading(T);
pre –>rchild=Thrt; pre –> RTag =Thread;
Thrt –>rchild=pre;
}
return OK;
}//InorderThreading
Void InThreading(BiThrTree p) {
if(p){
InThreading(p –>lchild);
if(!p –>lchild) {p –> LRag =Thread; p –
>lchild=pre;}
if(!pre –>rchild)
{pre –>rchild){pre –>RRag =Thread;pre –>rchild=p;}
pre=p;
InThreading(p –>rchild);
}
}
在线索树上插入一棵左子树 (Ins_lchild)和删除一棵左子
(Del_lchild)
