数 据 结 构计算机系第一章 绪 论
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)
