21世纪高职高专新概念教材数据结构( C语言描述)
王路群 主编前 言二十一世纪是科学技术高速发展的信息时代,而计算机是处理信息的主要工具,因此,人们已经认识到,计算机知识已成为人类当代文化的一个重要组成部分 。
计算机科学技术以惊人的速度向前发展,它的广泛应用已从传统的数值计算领域发展到各种非数值计算领域 。 在非数值计算领域里,数据处理的对象已从简单的数值发展到一般的符号,进而发展到具有一定结构的数据 。 在这里,面临的主要问题是:针对每一种新的应用领域的处理对象,如何选择合适的数据表示 ( 构构 ),如何有效地组织计算机存贮,并在此基础上又如何有效地实现对象之间的,运算,关系 。 传统的解决数值计算的许多理论,
方法和技术已不能满足解决非数值计算问题的需要,必须进行新的探索 。 数据结构就是研究和解决这些问题的重要基础理论 。 因此,,数据结构,课程已成为计算机类专业的一门重要专业基础课 。
数据结构是程序设计的中级课程,
主要培养学生分析数据、组织数据的能力,告诉学生如何编写效率高、结构好的程序。本书作为计算机大专系列教材之一,在内容的选取、概念的引入、文字的叙述以及例题和习题的选择等方面,都力求遵循面向应用、逻辑结构简明合理、由浅入深、深入浅出、循序渐进、便于自学的原则,突出其实用性与应用性。全书共分十章。书中,安排了相当的篇幅来介绍这些基本数据结构的实际应用。
进入章节
1
引言
2
数据结构的发展简史及其在计算机科学中所处的地位
3
什么是数据结构
4
基本概念和术语
5
算法和算法的描述第一章 绪论本章介绍了数据结构这门学科诞生的背景、
发展历史以及在计算机科学中所处的地位,
重点介绍了数据结构有关的概念和术语,
读者学习本章后应能掌握数据、数据元素、
逻辑结构、存储结构、
数据处理、数据结构、
算法设计等基本概念,
并了解如何评价一个算法的好坏。
1.1 引言众所周知,二十世纪四十年代,电子数字计算机问世的直接原因是解决弹道学的计算问题 。 早期,电子计算机的应用范围,几乎只局限于科学和工程的计算,其处理的对象是纯数值性的信息,
通常,人们把这类问题称为数值计算 。
近三十年来,电子计算机的发展异常迅猛,这不仅表现在计算机本身运算速度不断提高,信息存储量日益扩大,价格逐步下降,
更重要的是计算机广泛地应用于情报检索,企业管理,系统工程等方面,已远远超出了科技计算的范围,而渗透到人类社会活动的一切领域 。 与此相应,计算机的处理对象也从简单的纯数值性信息发展到非数值性的和具有一定结构的信息 。
因此,再把电子数字计算机简单地看作是进行数值计算的工具,
把数据仅理解为纯数值性的信息,就显得太狭隘了 。 现代计算机科学的观点,是把计算机程序处理的一切数值的,非数值的信息,
乃至程序统称为数据 ( Data),而电子计算机则是加工处理数据
( 信息 ) 的工具 。
由于数据的表示方法和组织形式直接关系到程序对数据的处理效率,而系统程序和许多应用程序的规模很大,结构相当复杂,处理对象又多为非数值性数据。因此,单凭程序设计人员的经验和技巧已难以设计出效率高、可靠性强的程序。于是,就要求人们对计算机程序加工的对象进行系统的研究,即研究数据的特性以及数据之间存在的关系 ——数据结构( Date Structure)。
1.2 数据结构的发展简史及其在计算机科学中所处的地位发展史:
1,,数据结构,作为一门独立的课程在国外是从 1968年才开始设立的。
2,1968年美国唐 ·欧 ·克努特教授开创了数据结构的最初体系,他所著的,计算机程序设计技巧,第一卷,基本算法,是第一本较系统地阐述数据的逻辑结构和存储结构及其操作的著作。
地位:
1.,数据结构,在计算机科学中是一门综合性的专业基础课。
2,数据结构是介于数学、计算机硬件和计算机软件三者之间的一门核心课程。
3,数据结构这一门课的内容不仅是一般程序设计 ( 特别是非数值性程序设计 ) 的基础,而且是设计和实现编译程序,操作系统,数据库系统及其他系统程序的重要基础 。
1.3 什么是数据结构计算机解决一个具体问题时,大致需要经过下列几个步骤:首先要从具体问题中抽象出一个适当的数学模型,然后设计一个解此数学模型的算法( Algorithm),最后编出程序、进行测试、调整直至得到最终解答。寻求数学模型的实质是分析问题,从中提取操作的对象,并找出这些操作对象之间含有的关系,然后用数学的语言加以描述。
计算机算法与数据的结构密切相关,算法无不依附于具体的数据结构,数据结构直接关系到算法的选择和效率 。
运算是由计算机来完成,这就要设计相应的插入,删除和修改的算法 。 也就是说,数据结构还需要给出每种结构类型所定义的各种运算的算法 。
直观定义:数据结构是研究程序设计中计算机操作的对象以及它们之间的关系和运算的一门学科 。
1.4 基本概念和术语
1.数据数据是人们利用文字符号、数字符号以及其他规定的符号对现实世界的事物及其活动所做的描述。在计算机科学中,数据的含义非常广泛,我们把一切能够输入到计算机中并被计算机程序处理的信息,包括文字、表格、图象等,都称为数据。例如,
一个个人书库管理程序所要处理的数据可能是一张如 表 1-1所示的表格。
表 1-1 个人书库
2,结点结点也叫数据元素,它是组成数据的基本单位 。 在程序中通常把结点作为一个整体进行考虑和处理 。 例如,在 表 1-1所示的个人书库中,为了便于处理,把其中的每一行 ( 代表一本书 ) 作为一个基本单位来考虑,故该数据由 10个结点构成 。
一般情况下,一个结点中含有若干个字段 ( 也叫数据项 ) 。 例如,
在 表 1-1所示的表格数据中,每个结点都有登录号,书号,书名,
作者,出版社和价格等六个字段构成 。 字段是构成数据的最小单位 。
3,逻辑结构结点和结点之间的逻辑关系称为数据的逻辑结构 。
在 表 1-1所示的表格数据中,各结点之间在逻辑上有一种线性关系,
它指出了 10个结点在表中的排列顺序 。 根据这种线性关系,可以看出表中第一本书是什么书,第二本书是什么书,等等 。
4,存储结构数据在计算机中的存储表示称为数据的存储结构 。
在 表 1-1所示的表格数据在计算机中可以有多种存储表示,例如,
可以表示成数组,存放在内存中;也可以表示成文件,存放在磁盘上,等等 。
5,数据处理数据处理是指对数据进行查找,插入,删除,合并,排序,统计以及简单计算等的操作过程 。 在早期,计算机主要用于科学和工程计算,进入八十年代以后,计算机主要用于数据处理 。 据有关统计资料表明,现在计算机用于数据处理的时间比例达到 80%以上,随着时间的推移和计算机应用的进一步普及,计算机用于数据处理的时间比例必将进一步增大 。
6,数据结构 ( Data Structure)
数据结构是研究数据元素 ( Data Element) 之间抽象化的相互关系和这种关系在计算机中的存储表示 ( 即所谓数据的逻辑结构和物理结构 ),并对这种结构定义相适应的运算,设计出相应的算法,而且确保经过这些运算后所得到的新结构仍然是原来的结构类型 。
为了叙述上的方便和避免产生混淆,通常我们把数据的逻辑结构统称为数据结构,把数据的物理结构统称为存储结构 ( Storage
Structure) 。
7,数据类型数据类型是指程序设计语言中各变量可取的数据种类 。 数据类型是高级程序设计语言中的一个基本概念,它和数据结构的概念密切相关 。
一方面,在程序设计语言中,每一个数据都属于某种数据类型 。
类型明显或隐含地规定了数据的取值范围,存储方式以及允许进行的运算 。 可以认为,数据类型是在程序设计中已经实现了的数据结构 。
另一方面,在程序设计过程中,当需要引入某种新的数据结构时,
总是借助编程语言所提供的数据类型来描述数据的存储结构 。
8.算法简单地说就是解决特定问题的方法(关于算法的严格定义,在此不作讨论)。特定的问题可以是数值的,也可以是非数值的。
解决数值问题的算法叫做数值算法,科学和工程计算方面的算法都属于数值算法,如求解数值积分,求解线性方程组、求解代数方程、求解微分方程等。
解决非数值问题的算法叫做非数值算法,数据处理方面的算法都属于非数值算法。例如各种排序算法、查找算法、插入算法、删除算法、遍历算法等。
数值算法和非数值算法并没有严格的区别。
一般说来,在数值算法中主要进行算术运算,而在非数值算法中主要进行比较和逻辑运算。另一方面,特定的问题可能是递归的,
也可能是非递归的,因而解决它们的算法就有递归算法和非递归算法之分。从理论上讲,任何递归算法都可以通过循环,堆栈等技术转化为非递归算法。
1.5 算法和算法的描述
1.5.1 算法算法是执行特定计算的有穷过程 。 这个过程有 5个特点:
1.动态有穷:当执行一个算法时,不论是何种情况,在经过了有限步骤后,这个算法一定要终止。
2.确定性:算法中的每条指令都必须是清楚的,指令无二义性 。
3.输入:具有 0个或 0个以上由外界提供的量 。
4.输出:产生 1个或多个结果 。
5.可行性:每条指令都充分基本,原则上可由人仅用笔和纸在有限的时间内也能完成 。
注意:算法和程序是有区别的,即程序未必能满足动态有穷 。 在本书中,我们只讨论满足动态有穷的程序,因此,算法,和
,程序,
是通用的 。
1.5.2 算法的描述一个算法可以用自然语言,数字语言或约定的符号来描述,也可以用计算机高级程序语言来描述,如 Pascal语言,C语言或伪代码等 。 本书选用 C语言作为描述算法的工具 。 现简单说明 C语言的语法结构如下:
1,预定义常量和类型:
# define TRUE 1;
# define FALSE -1;
# define ERROR NULL;
2,函数的形式
[数据类型 ] 函数名 ( [形式参数 ])
[形式参数说明; ]
{ 内部数据说明;
执行语句组;
} /*函数名 */〈
函数的定义主要由函数名和函数体组成,函数体用花括号
,{”和,}”括起来。函数中用方括号括起来的部分为可选项,函数名之间的圆括号不可省略。函数的结果可由指针或别的方式传递到函数之外。执行语句可由各种类型的语句所组成,两个语句之间用“;”号分隔。可将函数中的表达式的值通过 return语句返回给调用它的函数。最后的花括号,}”之后的 /*函数名 */为注释部分,可舍。
3,赋值语句简单赋值:
〈 变量名 〉 =〈 表达式 〉,它表示将表达式的值赋给左边的变量;
〈 变量 〉 ++,它表示变量加 1后赋值给变量;
〈 变量 〉 --,它表示变量减 1后赋值给变量;
成组赋值:
1.( 〈 变量 1〉,〈 变量 2〉,〈 变量 3〉,…〈 变量 k〉 ) =( 〈 表达式 1〉,〈 表达式 2〉,〈 表达式 3〉,…〈 表达式 k〉 ) ;
2.〈 数组名 1〉 [下标 1…下标 2]=〈 数组名 2〉 [下标 1…下标 2]
串联赋值:
〈 变量 1〉 =〈 变量 2〉 =〈 变量 3〉 =…=〈 变量 k〉 = 〈 表达式 〉 ;
条件赋值:
〈 变量名 〉 =〈 条件表达式 〉? 〈 表达式 1〉,〈 表达式 2〉 ;
交换赋值:
〈 变量 1〉 ←→ 〈 变量 2〉,表示变量 1和变量 2互换;
4,条件选择语句
if ( 〈 表达式 〉 ) 语句;
if ( 〈 表达式 〉 ) 语句 1;
else 语句 2;情况语句
switch ( 〈 表达式 〉 )
{ case 判断值 1; 语句组 1;
break;
case 判断值 2;语句组
2;
break;
……
case 判断值 n;语句组 n;
break;
[default:语句组;
break; ] }
注意,switch case语句是先计算表达式的值,然后用其值与判断值相比较,若它们相一致时,就执行相应的
case下的语句组;若不一致,
则执行 default下的语句组;
其中的方括号代表可选项 。
5.循环语句
⑴ for语句
for( 〈 表达式 1〉 ; 〈 表达式 2〉 ; 〈 表达式 3〉 ) {循环体语句; }
首先计算表达式 1的值,然后求表达式 2的值,若结果非零则执行循环体语句,最后对表达式 3运算,如此循环,直到表达式 2
的值为零时止。
⑵ while语句
while ( 〈 条件表达式 〉 )
{ 循环体语句;
}
while循环首先计算条件表达式的值,若条件表达式的值非零,
则执行循环体语句,然后再次计算条件表达式,重复执行,直到条件表达式的值为假时退出循环,执行该循环之后的语句 。
⑶ do-while语句
do { 循环体语句
} while( 〈 条件表达式 〉 )
该循环语句首先执行循环体语句 。 然后再计算条件表达式的值,
若条件表达式成立,则再次执行循环体,再计算条件表达式的值,
直到条件表达式的值为零,即条件不成立时结束循环 。
6,输入,输出语句输入语句:用函数 scanf实现,特别当数据为字符时,用 getchar
函数实现 。
输出语句:用 printf函数实现,当要输出字符数据时,用 putchar
函数实现 。
7,其他一些语句
( 1) return表达式或 return:用于函数结束 。
( 2) break语句:可用在循环语句或 case语句中结束循环过程或跳出情况语句 。
( 3) exit语句:表示出现异常情况时,控制退出语句 。
8,注释形式可用 /*字符串 */ 或者 单行注释 或 //文字序列 。
9,一些基本的函数如,max函数,用于求一个或几个表达式中的最大值;
min函数,用于求一个或几个表达式中的最小值;
abs函数,用于求表达式的绝对值;
eof函数,用于判定文件是否结束;
eoln函数,用于判断文本行是否结束 。
例 计算 f=1 ! +2 ! +3 !
+…+n!,用 C语言描述 。
void factorsum( n)
int n; {int i,j; int f,w;
f=0;
for ( i=1,i〈 =n; i++)
{w=1;
for ( j=1,j〈 =i; j++)
w=w*j;
f=f+w; }
return;
}
上述算法所用到的运算有乘法,加法,赋值和比较,其基本运算为乘法操作 。 在上述算法的执行过程中,对外循环变量 i的每次取值,内循环变量 j循环 i次 。 因为内循环每执行一次,内循环体语句
w=w*j只作一次乘法操作,
即当内循环变量 j循环 i次时,
内循环体的语句 w=w*j作 i次乘法 。 所以,整个算法所作的乘法操作总数是,f( n)
=1+2+3+…n=n( n-1) /2。
1.5.3 算法评价设计一个好的算法应考虑以下几个方面:
1.正确性
,正确,的含义在通常的用法中有很大的差别,大体可分为以下四个层次:①程序不含语法错误;②程序对于几组输入数据能够得出满足规格说明要求的结果;③程序对于精心选择的典型、苛刻而带有刁难性的几组数据能够得出满足规格说明要求的结果;④程序对一切合法的输入数据都能产生满足规格说明要求的结果 。
2,运行时间运行时间是指一个算法在计算机上运算所花费的时间 。 它大致等于计算机执行一种简单操作 ( 如赋值操作,转向操作,比较操作等等 ) 所需要的时间与算法中进行简单操作次数的乘积 。
通常把算法中包含简单操作次数的多少叫做算法的时间复杂性,
它是一个算法运行时间的相对量度 。
3,占用的存储空间一个算法在计算机存储器上所占用的存储空间,包括存储算法本身所占用的存储空间,算法的输入、输出数据所占用的存储空间和算法运行过程中临时占用的存储空间。
分析一个算法所占用的存储空间要从各方面综合考虑。
算法在运行过程中所占用的存储空间的大小被定义为算法的空间复杂性。它包括局部变量所占用的存储空间和系统为了实现递归所使用的堆栈这两个部分。算法的空间复杂性一般以数量级的形式给出。
4,简单性最简单和最直接的算法往往不是最有效的,但算法的简单性使得证明其正确性比较容易,同时便于编写,修改,阅读和调试,所以还是应当强调和不容忽视的 。 不过对于那些需要经常使用的算法来说,高效率 ( 即尽量减少运行时间和压缩存储空间 ) 比简单性更为重要 。
本章小结本章主要介绍了如下一些基本概念:
数据结构,数据结构是研究数据元素之间抽象化的相互关系和这种关系在计算机中的存储表示 ( 即所谓数据的逻辑结构和物理结构 ),并对这种结构定义相适应的运算,设计出相应的算法,而且确保经过这些运算后所得到的新结构仍然是原来的结构类型 。
数据,数据是人们利用文字符号,数字符号以及其他规定的符号对现实世界的事物及其活动所做的描述 。
在计算机科学中,数据的含义非常广泛,我们把一切能够输入到计算机中并被计算机程序处理的信息,包括文字,表格,图象等,都称为数据 。
结点,结点也叫数据元素,它是组成数据的基本单位 。
逻辑结构,结点和结点之间的逻辑关系称为数据的逻辑结构 。
存储结构,数据在计算机中的存储表示称为数据的存储结构 。
数据处理,数据处理是指对数据进行查找,插入,删除,合并,排序,统计以及简单计算等的操作过程 。
数据类型,数据类型是指程序设计语言中各变量可取的数据种类 。 数据类型是高级程序设计语言中的一个基本概念,它和数据结构的概念密切相关 。
习 题 一
1,简述下列术语:数据,结点,逻辑结构,存储结构,数据处理,
数据结构和数据类型 。
2,试根据以下信息:校友姓名,性别,出生年月,毕业时间,所学专业,现在工作单位,职称,职务,电话等,为校友录构造一种适当的数据结构 ( 作图示意 ),并定义必要的运算和用文字叙述相应的算法思想 。
3,什么是算法? 算法的主要特点是什么?
4,如何评价一个算法?
1
线性表的逻辑结构本章学习导读线性表 ( Linear list)是最简单且最常用的一种数据结构。这种结构具有下列特点:存在一个唯一的没有前驱的(头)数据元素;存在一个唯一的没有后继的(尾)数据元素;此外,每一个数据元素均有一个直接前驱和一个直接后继数据元素。通过本章的学习,读者应能掌握线性表的逻辑结构和存储结构,以及线性表的基本运算以及实现算法。 2
线性表的顺序存储结构3
线性表的链式存储结构4
一元多项式的表示及相加
2.1 线性表的逻辑结构线性表由一组具有相同属性的数据元素构成 。 数据元素的含义广泛,在不同的具体情况下,可以有不同的含义 。 例如:英文字母表 ( A,B,C,…,Z) 是一个长度为 26的线性表,其中的每一个字母就是一个数据元素;再如,某公司 2000年每月产值表 ( 400,
420,500,…,600,650) (单位:万元 )是一个长度为 12的线性表,其中的每一个数值就是一个数据元素 。 上述两例中的每一个数据元素都是不可分割的,在一些复杂的线性表中,每一个数据元素又可以由若干个数据项组成,在这种情况下,通常将数据元素称为记录 ( record),例如,图 2-1的某单位职工工资表就是一个线性表,表中每一个职工的工资就是一个记录,每个记录包含八个数据项:职工号,姓名,基本工资 …… 。
职工号 姓名基本工资岗位工资奖金应发工资扣款实发工资
1201 张强 540 300 200 1040 20 1020
1301 周敏 500 200 200 900 20 880
1202 徐黎 芬 550 300 200 1050 30 1020
1105 黄承 振 530 250 200 980 20 960
┇ ┇ ┇ ┇ ┇ ┇ ┇ ┇
图 2-1 职工工资表矩阵也是一个线性表,但它是一个比较复杂的线性表 。 在矩阵中,我们可以把每行看成是一个数据元素,也可以把每列看成是一个数据元素,而其中的每一个数据元素又是一个线性表 。
综上所述,一个线性表是 n≥0个数据元素 a0,a1,a2,…,an-1的有限序列 。 如果 n>0,则除 a0和 an-1外,有且仅有一个直接前趋和一个直接后继数据元素,ai( 0≤i≤n-1) 为线性表的第 i个数据元素,它在数据元素 ai-1之后,在 ai+1之前 。 a0为线性表的第一个数据元素,而 an-1
是线性表的最后一个数据元素;若 n=0,则为一个空表,表示无数据元素 。 因此,线性表或者是一个空表 ( n=0),或者可以写成,( a0,
a1,a2,…,ai-1,ai,ai+1,…,an-1) 。
抽象数据类型线性表的定义如下:
LinearList=(D,R)
其中,D={ ai| ai∈ ElemSet,i=0,1,2,…,n-1 n≥1}
R={<ai-1,ai>| ai-1,ai∈ D,i=0,1,2,…,n-1}
Elemset为某一数据对象集; n为线性表的长度。
线性表的主要操作有如下几种:
1,Initiate(L) 初始化:构造一个空的线性表 L。
2,Insert(L,i,x) 插入:在给定的线性表 L中,在第 i个元素之前插入数据元素 x。线性表 L长度加 1。
3,Delete(L,i) 删除:在给定的线性表 L中,删除第 i个元素。线性表 L的长度减 1。
4,Locate(L,x) 查找定位:对给定的值 x,若线性表 L中存在一个元素 ai
与之相等,则返回该元素在线性表中的位置的序号 i,否则返回 Null(空)

5,Length(L) 求长度:对给定的线性表 L,返回线性表 L的数据元素的个数。
6,Get(L,i) 存取:对给定的线性表 L,返回第 i( 0≤i≤Length(L)-1)个数据元素,否则返回 Null。
7,Traverse(L) 遍历:对给定的线性表 L,依次输出 L的每一个数据元素

8,Copy(L,C) 复制:将给定的线性表 L复制到线性表 C中。
9,Merge(A,B,C) 合并:将给定的线性表 A和 B合并为线性表 C。
上面我们定义了线性表的逻辑结构和基本操作 。 在计算机内,线性表有两种基本的存储结构:顺序存储结构和链式存储结构 。 下面我们分别讨论这两种存储结构以及对应存储结构下实现各操作的算法 。
2.2 线性表的顺序存储结构在计算机中用一组地址连续的存储单元依次存储线性表的各个数据元素,称作线性表的顺序存储结构 。
2.2.1 线性表的顺序存储结构在线性表的顺序存储结构中,其前后两个元素在存储空间中是紧邻的,且前驱元素一定存储在后继元素的前面 。 由于线性表的所有数据元素属于同一数据类型,所以每个元素在存储器中占用的空间大小相同,因此,要在该线性表中查找某一个元素是很方便的 。 假设线性表中的第一个数据元素的存储地址为 Loc(a0),每一个数据元素占 d字节,则线性表中第 i个元素 ai在计算机存储空间中的存储地址为:
Loc(ai)= Loc(a0)+id
在程序设计语言中,通常利用数组来表示线性表的顺序存储结构。这是因为数组具有如下特点:( 1)数据中的元素间的地址是连续的;( 2)
数组中所有元素的数据类型是相同的。而这与线性表的顺序存储空间结构是类似的。
1,一维数组若定义数组 A[n]={ a0,a1,a2,…,an-1},假设每一个数组元素占用 d个字节,则数组元素 A[0],A[1],A[2],…,A[n-1]的地址分别为 Loc(A[0]),
Loc(A[0])+d,Loc(A[0])+2d,…,Loc(A[0])+( n-1) d 。其结构如图 2-2所示。
若定义数组 A[n][m],表示此数组有 n行 m列,如下图 2-3所示 。
0 1 2 … j … m -1
0 a00 a01 a02 … a 0j … a 0 m-1
1 a10 a11 a12 … a 1j … a 1 m-1
2 a20 a21 a22 … a 2j … a 2 m-1
i ai0 ai1 ai2 … a ij … a i m-1
n-1 an-1,0 an-1,1 an-1,2 … a n-1,j … a n-1,m-1
图 2-3 二维数组
2,二维数组在 C语言中,二维数组的保存是按照行方式存储的,先将第一行元素排好,接着排第二行元素,直至所有行的元素排完 。 如图 2-4所示 。
图 2-4 二维数组存储示意图
2.2.2 线性表在顺序存储结构下的运算可用 C语言描述顺序存储结构下的线性表 ( 顺序表 ) 如下:
#define TRUE 1
#define FALSE 0
#define MAXNUM <顺序表最大元素个数 >
Elemtype List[MAXNUM] ; /*定义顺序表 List*/
int num=-1; /*定义当前数据元素下标,并初始化 */
我们还可将数组和表长封装在一个结构体中:
struct Linear_list {
Elemtype List[MAXNUM]; /*定义数组域 */
int length; /*定义表长域 */
}
1,顺序表的插入操作在 长 度 为 num(0≤num≤MAXNUM-2) 的 顺 序 表 List 的第
i(0≤i≤num+1)个数据元素之前插入一个新的数据元素 x时,
需将最后一个即第 num个至第 i个元素 ( 共 num-i+1个元素 )
依次向后移动一个位置,空出第 i个位置,然后把 x插入到第 i个存储位置,插入结束后顺序表的长度增加 1,返回
TRUE值;若 i< 0或 i> num+1,则无法插入,返回 FALSE。
如图 2-5 所示 。
在 长 度 为 num(0≤num≤MAXNUM-2) 的 顺 序 表 List 的第
i(0≤i≤num+1)个数据元素之前插入一个新的数据元素 x时,
需将最后一个即第 num个至第 i个元素 ( 共 num-i+1个元素 )
依次向后移动一个位置,空出第 i个位置,然后把 x插入到第 i个存储位置,插入结束后顺序表的长度增加 1,返回
TRUE值;若 i< 0或 i> num+1,则无法插入,返回 FALSE。
如图 2-5所示 。
0 a0
1 a1
2 a2
┇ ┇
i-1 ai-1
i ai
i+1 ai+1
i+2 ai+2
┇ ┇
num anum
0 a0
1 a1
2 a2
┇ ┇
i-1 ai-1
i x
i+1 ai
i+2 ai+1
┇ ┇
num anum
插入
x
图 2-5 在数组中插入元素其算法如下:
【 算法 2.1 顺序表的插入 】
int Insert(Elemtype List[],int *num,int i,Elemtype x)
{/*在顺序表 List[]中,*num为表尾元素下标位置,在第 i个元素前插入数据元素 x,若成功,返回 TRUE,否则返回 FALSE。 */
int j;
if (i<0||i>*num+1)
{printf(“Error!”); /*插入位置出错 */
return FALSE;}
if (*num>=MAXNUM-1)
{printf(“overflow!”);
return FALSE; /*表已满 */}
for (j=*num;j>=i;j--)
List[j+1]=List[j]; /*数据元素后移 */
List[i]=x; /*插入 x*/
(*num)++; /*长度加 1*/
return TRUE;}
注,顺序表 List的最大数据元素个数为 MAXNUM,num标识为顺序表的当前表尾 ( num≤MAXNUM-1) 。
2.顺序表的删除操作
0 a0
1 a1
2 a2
┇ ┇
i-1 ai-1
i ai+1
i+1 ai+2
┇ ┇
num anum
0 a0
1 a1
2 a2
┇ ┇
i-1 ai-1
i ai
i+1 ai+1
┇ ┇
num anum
图 2-6 在数组中删除元素在长度为 num(0≤num≤MAXNUM-1)的顺序表 List,删除第 i(0≤i≤num)个数据元素,需将第 i至第 num个数据元素的存储位置 ( num-i+1) 依次前移,
并使顺序表的长度减 1,返回 TRUE值,若 i< 0或 i> num,则无法删除,
返回 FALSE值,如图 2-6所示 。
其算法如下:
【 算法 2.2 顺序表的删除 】
int Delete(Elemtype List[],int *num,int i)
{/*在线性表 List[]中,*num为表尾元素下标位置,删除第 i个元素,线性表的元素减 1,若成功,则返回 TRUE;否则返回 FALSE。 */
int j;
if(i<0||i>*num)
{printf(“Error!”); return FALSE; /*删除位置出错 ! */ }
for(j=i+1;j<=*num;j++)
List[j-1]=List[j]; /*数据元素前移 */
(*num)--; /*长度减 1*/
return TRUE; }
从上述两个算法来看,很显然,在线性表的顺序存储结构中插入或删除一个数据元素时,其时间主要耗费在移动数据元素上 。 而移动元素的次数取决于插入或删除元素的位置 。
假设 Pi是在第 i个元素之前插入一个元素的概率,则在长度为 n的线性表中插入一个元素时所需移动元素次数的平均次数为
)(
0
inpE
n
i
ii n s
假设 qi是删除第 i个元素的概率,则在长度为 n的线性表中删除一个元素时所需移动元素次数的平均次数为如果在线性表的任何位置插入或删除元素的概率相等,即则可见,在顺序存储结构的线性表中插入或删除一个元素时,平均要移动表中大约一半的数据元素 。 若表长为 n,则插入和删除算法的时间复杂度都为 O(n)。
在顺序存储结构的线性表中其他的操作也可直接实现,在此不再讲述 。
)1(1
0

inqE n
i
id e l
1
1
np inq i 1?
2)(1
1
0
nin
nE
n
i
i n s
2
1)1(1 1
0

nin
nE
n
i
d e l
例:将有序线性表 La={2,4,6,7,9},Lb={1,5,7,8},合并为 Lc={1,2,4,5,6,7,7,8,9}。
分析,Lc中的数据元素或者是 La中的数据元素,或者是 Lb中的数据元素,则只要先将 Lc置为空表,然后将 La或 Lb中的元素逐个插入到 Lc中即可 。 设两个指针 i和 j分别指向 La和 Lb中的某个元素,若设 i当前所指的元素为 a,j当前所指的元素为 b,则当前应插入到 Lc中的元素 c为 c={a 当a ≤b时b 当a>
b时,很显然,指针 i和 j的初值均为 1,在所指元素插入 Lc后,i,j在 La或 Lb中顺序后移 。
算法如下:
void merge(Elemtype La[],Elemtype Lb[],Elemtype **Lc)
{ int i,j,k;
int La_length,Lb_length;
i=j=0;k=0;
La_length=Length(La);Lb_length(Lb)=Length(Lb);/*取表 La,Lb的长度 */
Initiate(Lc); /*初始化表 Lc*/
While (i<=La_length&&j<=Lb_length)
{ a=get(La,i);b=get(Lb,j);
if(a<b) {insert(Lc,++k,a);++i;}
else {insert(Lc,++k,b);++j;}
} /*将 La和 Lb的元素插入到 Lc中 */
while (i<=La_length) { a=get(La,i);insert(Lc,++k,a);}
while (j<=lb_length) { b=get(La,i);insert(Lc,++k,b); } }
3,顺序表存储结构的特点线性表的顺序存储结构中任意数据元素的存储地址可由公式直接导出,
因此顺序存储结构的线性表是可以随机存取其中的任意元素 。 也就是说定位操作可以直接实现 。 高级程序设计语言提供的数组数据类型可以直接定义顺序存储结构的线性表,使其程序设计十分方便 。
但是,顺序存储结构也有一些不方便之处,主要表现在:
( 1) 数据元素最大个数需预先确定,使得高级程序设计语言编译系统需预先分配相应的存储空间 。
( 2) 插入与删除运算的效率很低 。 为了保持线性表中的数据元素的顺序
,在插入操作和删除操作时需移动大量数据 。 这对于插入和删除操作频繁的线性表,以及每个数据元素所占字节较大的问题将导致系统的运行速度难以提高 。
( 3) 顺序存储结构的线性表的存储空间不便于扩充 。 当一个线性表分配顺序存储空间后,如果线性表的存储空间已满,但还需要插入新的元素
,则会发生,上溢,错误 。 在这种情况下,如果在原线性表的存储空间后找不到与之连续的可用空间,则会导致运算的失败或中断 。
2.3 线性表的链式存储结构从线性表的顺序存储结构的讨论中可知,对于大的线性表,特别是元素变动频繁的大线性表不宜采用顺序存储结构,而应采用本节要介绍的链式存储结构 。
线性表的链式存储结构就是用一组任意的存储单元 ( 可以是不连续的 )
存储线性表的数据元素 。 对线性表中的每一个数据元素,都需用两部分来存储:一部分用于存放数据元素值,称为数据域;另一部分用于存放直接前驱或直接后继结点的地址 ( 指针 ),称为指针域,我们把这种存储单元称为结点 。
在链式存储结构方式下,存储数据元素的结点空间可以不连续,各数据结点的存储顺序与数据元素之间的逻辑关系可以不一致,而数据元素之间的逻辑关系由指针域来确定 。
链式存储方式可用于表示线性结构,也可用于表示非线性结构 。
2.3.1 线性链表
1,线性链表线性链表是线性表的链式存储结构,是一种物理存储单元上非连续,非顺序的存储结构,数据元素的逻辑顺序是通过链表中的指针链接次序实现的
。 因此,在存储线性表中的数据元素时,一方面要存储数据元素的值,另一方面要存储各数据元素之间的逻辑顺序,为此,将每一个存储结点分为两部分:一部分用于存储数据元素的值,称为数据域;另一部分用于存放下一个数据元素的存储结点的地址,即指向后继结点,称为指针域 。
此种形式的链表因只含有一个指针域,又称为单向链表,简称单链表 。 图
2-7(a)所示为一个空线性链表 。 图 2-6(b)所示为一个非空线性链表 ( a0,a1
,a2,…,an-1) 。
a0 a1 an-1head head …
(a) (b)
图 2-7 线性链表的存储结构上图中,通常在线性链表的第一结点之前附设一个称为头结点的结点 。 头结点的数据域可以不存放任何数据,也可以存放链表的结点个数的信息 。
对空线性表,附加头结点的指针域为空 ( NULL或 0表示 ),用 ∧ 表示 。 头指针 head指向链表附加头结点的存储位置 。 对于链表的各种操作必须从头指针开始 。
在 C语言中,定义链表结点的形式如下:
struct 结构体名
{ 数据成员表;
struct 结构体名 * 指针变量名; }
例如,下面定义的结点类型中,数据域包含三个数据项:学号,姓名,成绩 。
Struct student
{ char num[8]; /*数据域 */
char name[8]; /*数据域 */
int score; /*数据域 */
struct student *next; /*指针域 */
}
假设 h,p,q为指针变量,可用下列语句来说明:
struct student *h,*p,*q;
在 C语言中,用户可以利用 malloc函数向系统申请分配链表结点的存储空间,该函数返回存储区的首地址,如:
p=(struct student *)malloc(sizeof(struct student));
指针 p指向一个新分配的结点。
如果要把此结点归还给系统,则用函数 free(p)来实现。
2,线性链表的基本操作下面给出的单链表的基本操作实现算法都是以图 2-7所示的带头结点的单链表为数据结构基础 。
单链表结点结构定义为:
Typedef struct slnode
{ Elemtype data;
struct slnode *next;
}slnodetype;
slnodetype *p,*q,*s;
( 1) 初始化
【 算法 2.3 单链表的初始化 】
int Initiate(slnodetype * *h)
{ if((*h=(slnodetype*)malloc(sizeof(slnodetype)))==NULL) return FALSE;
(*h)->next=NULL;
return TRUE; }
注意,形参 h定义为指针的指针类型,若定义为指针类型,将无法带回函数中建立的头指针值 。
( 2) 单链表的插入操作
1) 已知线性链表 head,在 p指针所指向的结点后插入一个元素 x。
在一个结点后插入数据元素时,操作较为简单,不用查找便可直接插入 。
操作过程如图 2-8所示 。
head
p
p
s
head
(a) 插入前
…a0 a1 a
i an-1
…a
i+1
(b) 插入后图 2-8 单链表的后插入
x
xs
an-1ai …a0 a1 …
相关语句如下:
【 算法 2.4 单链表的后插入 】
{ s=(slnodetype*)malloc(sizeof(slnodetype));
s->data=x;
s->next=p->next;p->next=s;}
2) 已知线性链表 head,在 p指针所指向的结点前插入一个元素 x。
前插时,必须从链表的头结点开始,找到 P指针所指向的结点的前驱。设一指针 q从附加头结点开始向后移动进行查找
,直到 p的前趋结点为止。然后在 q指针所指的结点和 p指针所指的结点之间插入结点 s。
操作过程如图 2-9所示 。
相关语句如下:
【 算法 2.5 单链表的结点插入 】
{q=head;
while(q->next!=p) q=q->next;
s=(slnodetype*)malloc(sizeof(slnodetype));
s->data=x;
s->next=p;
q->next=s;}
(b)插入后图 2-9 单链表的前插入
s x
pa
0 ai-1 ai an-1
… …
qhead
x
0a ai-1 an-1aihead … …
q p
s
( a)插入前
【 算法 2.6 单链表的前插入 】
int insert(slnodetype *h,int i,Elemtypex)
{/*在链表 h中,在第 i个数据元素插入一个数据元素 x */
slnodetype *p,*q,*s;
int j=0;
p=h;
while(p!=NULL&&j<i-1) { p=q->next;j++; /*寻找第 i-1个结点 */
}
if ( j!=i-1){printf(“Error!”);return FALSE; /*插入位置错误 */}
if ((s=(slnodetype*)malloc(sizeof(slnodetype)))==NULL) return FALSE;
s->data=x;
s->next=p->next;
q->next=s;
return TRUE;}
例:下面 C程序中的功能是,首先建立一个线性链表 head={3,5,7,9},
其元素值依次为从键盘输入正整数 ( 以输入一个非正整数为结束 ) ;在线性表中值为 x的元素前插入一个值为 y的数据元素 。 若值为 x的结点不存在,则将 y插在表尾 。
#include“stdlib.h”
#include“stdio.h”
struct slnode
{int data;
struct slnode *next;} /*定义结点类型 */
main()
{int x,y,d;
struct slnode *head,*p,*q,*s;
head=NULL; /*置链表空 */
q=NULL;
scanf(“%d”,&d); /*输入链表数据元素 */
while(d>0)
{p=(struct slnode*)malloc(sizeof(struct slnode)); /*申请一个新结点 */
p->data=d;
p->next=NULL;
if(head==NULL) head=p; /*若链表为空,则将头指针指向当前结点 p*/
else q->next=p; /*链表不为空时,则将新结点链接在最后 */
q=p; /*将指针 q指向链表的最后一个结点 */
scanf(“%d”,&d);}
scanf(“%d,%d”,&x,&y);
s=(struct slnode*)malloc(sizeof(struct slnode));
s->data=y;
q=head;p=q->next;
while((p!=NULL)&&(p->data!=x)) {q=p;p=p->next;} /*查找元素为 x的指针 */
s->next=p;q->next=s; /*插入元素 y*/
}
( 3) 单链表的删除操作若要删除线性链表 h中的第 i个结点,首先要找到第 i个结点并使指针 p指向其前驱第 i-1个结点,然后删除第 i个结点并释放被删除结点空间 。 操作过程如图 2-10所示 。
其算法如下:
【 算法 2.7 单链表的删除 】
int Delet(slnodetype*h,int i)
{ /*在链表 h中删除第 i个结点 */
slnodetype *p,*s;
int j;
p=h;j=0;
while(p->next!=NULL&&j<i-1)
{ p=p->next;j=j+1; /*寻找第 i-1个结点,p指向其前驱 */}
if(j!=i-1)
{printf(“Error!”); /*删除位置错误 !*/
return FALSE; }
s=p->next;
p->next=p->next->next; /*删除第 i个结点 */
free(s); /*释放被删除结点空间 */
return TRUE;
}
head … …
head … …
(b)删除并释放第 i个结点图 2-10 在线性链表中删除一个结点的过程
aiai-1 ai+1 an-1
p
(a) 寻找第 i个结点指向其前驱 p
p s
an-1ai+1aiai-1
(p!=NULL&&j<i-1)与 (p->next!=NULL&&j<i-1)
的不同 。
从线性链表的插入与删除算法中,我们可以看到要取链表中某个结点,
必须从链表的头结点开始一个一个地向后查找,即我们不能直接存取线性链表中的某个结点,这是因为链式存储结构不是随机存储结构 。 虽然在线性链表中插入或删除结点不需要移动别的数据元素,但算法寻找第 i-1个或第 i个结点的时间复杂度为 O(n)。
例:假设已有线性链表 La,编制算法将该链表逆置 。
利用头结点和第一个存放数据元素的结点之间不断插入后继元素结点 。
如图 2-11所示 。
请读者比较插入算法与删除算法中所用的条件算法如下:
void converse(slnodetype *head)
{slnodetype *p,*q;
p=head->next;
head->next=NULL;
while(p!=NULL)
{ q=p->next;
p->next=head->next;
head->next=p;
p=q;
}
a0 a1 an-1a3 …
p q
a0 a1 an-1a3 …
p q
a1 a0 an-1a3 …
p q
a0 a1 an-1a
3
…head
head
head
head
图 2-11 单链表逆置
2.3.2 循环链表循环链表 (Circular Linked List)是另一种形式的链式存储结构 。 是将单链表的表中最后一个结点指针指向链表的表头结点,整个链表形成一个环,这样从表中任一结点出发都可找到表中其他的结点 。 图 2-12( a) 为带头结点的循环单链表的空表形式,图 2-12( b) 为带头结点的循环单链表的一般形式 。
带头结点的循环链表的操作实现算法和带头结点的单链表的操作实现算法类同,差别在于算法中的条件在单链表中为 p!=null或 p->next!=null;而在循环链表中应改为 p!=head或 p->next!=head。
在循环链表中,除了头指针 head外,有时还加了一个尾指针 rear,尾指针
read指向最后一结点,从最后一个结点的指针又可立即找到链表的第一个结点 。 在实际应用中,使用尾指针代替头指针来进行某些操作,往往更简单 。
head
(a)循环链表的空表形式
head … …
(b)循环链表的一般形式图 2-12 循环链表
a0 a1 an-1ai
例:将两个循环链表首尾相接 。 La为第一个循环链表表尾指针,Lb为第二个循环链表表尾指针 。 合并后 Lb为新链表的尾指针 。
Void merge(slnodetype *La,slnodetype *Lb)
{ slnodetype *p;
p=La->next;
Lb->next= La->next;
La->next=p->next;
free(p);
}
(a)
a0 a1 an-1
b0 b1 bn-1
a0 a1 a
n-1
a0 a1 a
n-1
La
Lb
Lb(b)图 2-13 循环链表的合并




如图 2-13所示,在这个算法中,时间复杂度为 O(1)。
2.3.3 双向链表
1,双向链表在单链表的每个结点中只有一个指示后继的指针域,因此从任何一个结点都能通过指针域找到它的后继结点;若需找出该结点的前驱结点,则此时需从表头出发重新查找 。 换句话说,在单链表中,查找某结点的后继结点的执行时间为 O(1),而查找其前驱结点的执行时间为 O(n)。 我们可用双向链表来克服单链表的这种缺点,在双向链表中,每一个结点除了数据域外,还包含两个指针域,一个指针
( next) 指向该结点的后继结点,另一个指针 ( prior) 指向它的前驱结点 。 双向链表的结构可定义如下:
typedef struct node
{Elemtype data;
struct node *prior,*next;} dlnodetype;
prior next
head (a) 空双向链表a
0 a1

… an-1
head
(b) 非空的双向链表图 2-14 双向链表和单链的循环表类似,双向链表也可以有循环表,让头结点的前驱指针指向链表的最后的一个结点,让最后一个结点的后继指针指向头结点。图 2-14为双向链表示意图,其中图 (b)是一个循环双向链表。
若 p为指向双向链表中的某一个结点 ai的指针,则显然有:
p->next->prior==p->prior->next==p
在双向链表中,有些操作如:求长度、取元素、定位等,因仅需涉及一个方向的指针,故它们的算法与线性链表的操作相同;但在插入、删除时,则需同时修改两个方向上的指针,两者的操作的时间复杂度均为 O(n)。
2,双向链表的基本操作
( 1) 在双向链表中插入一个结点在双向链表的第 i个元素前插入一个结点时,可用指针 p指该结点 ( 称 p结点
),先将新结点的 prior指向 p结点的前一个结点,其次将 p结点的前一个结点的 next指向新结点,然后将新结点的 next指向 p结点,最后将 p结点的
prior指向新结点 。 操作过程如图 2-15所示 。
(a)插入前 ( b)插入后图 2-15 在双向链表中插入结点
ai-1 ai
s ∧ x ∧
p
ai-1 ai
p
① ② ③ ④
s x
其算法如下:
【 算法 2.8 双向链表的插入 】
int insert_dul(dlnodetype *head,int i,Elemtype x)
{/*在带头结点的双向链表中第 i个位置之前插入元素 x*/
dbnodetype *p,*s;
int j;
p=head;
j=0;
while (p!=NULL&&j<i)
{ p=p->next;
j++; }
if(j!=i||i<1)
{printf(“Error!”);
return FALSE;}
if((s=(dlnodetype *)malloc(sizeof(dlnodetype)))==NULL) return FALSE;
s->data=x;
s->prior=p->prior; /*图中步骤 ① */
p->prior->next=s; /*图中步骤 ② */
s->next=p; /*图中步骤 ③ */
p->prior=s; /*图中步骤 ④ */
return TRUE;}
讨论:我们在双向链表中进行插入操作时,还需注意下面两种情况:
1) 当在链表中的第一个结点前插入新结点时,新结点的 prior应为空
,原链表第一个结点的 prior应指向新结点,新结点的 next应指向原链表的第一个结点 。
2) 当在链表的最后一个结点后插入新结点时,新结点的 next应为空
,原链表的最后一个结点的 next应指向新结点,新结点的 prior应指向原链表的最后一个结点 。
( 2) 在双向链表中删除一个结点在双向链表中删除一个结点时,可用指针 p指向该结点 ( 称 p结点 )
,然后将 p结点的前一个结点的 next指向 p结点的下一个结点,再将 p
的下一个结点的 prior指向 p的上一个结点 。 如图 2-16所示,
图 2-16 在双向链表中删除一个结点


ai-1 ai ai+1
p
【 算法 2.9 双向链表的删除 】
int Delete_dl(dlnodetype *head,int i)
{ dlnodetype *p,*s;
int j;
p=head;
j=0;
while (p!=NULL&&j<i)
{ p=p->next;
j++; }
if(j!=i||i<1)
{ printf(“Error!”);
return FALSE;}
s=p;
p->prior->next=p->next; /*图中步骤 ① */
p->next->prior=p->prior; /*图中步骤 ② */
free(s);
return TRUE;}
讨论:我们在双向链表中进行删除操作时,还需注意下面两种情况:
1) 当删除链表的第一个结点时,应将链表开始结点的指针指向链表的第二个结点,同时将链表的第二个结点的 prior置为 NULL

2) 当删除链表的最后一个结点时,只需将链表的最后一个结点的上一个结点的 next置为 NULL即可 。
上面我们详细讲解了链式存储结构,链式存储结构克服了顺序存储结构的缺点:它的结点空间可以动态申请和释放;它的数据元素的逻辑次序靠结点的指针来指示,不需要移动数据元素

但是链式存储结构也有不足之处:
( 1) 每个结点中的指针域需额外占用存储空间 。 当每个结点的数据域所占字节不多时,指针域所占存储空间的比重就显得很大 。
( 2) 链式存储结构是一种非随机存储结构 。 对任一结点的操作都要从头指针依指针链查找到该结点,这增加了算法的复杂度

2.4 一元多项式的表示及相加符号多项式的表示及其操作是线性表处理的典型用例,在数学上,一个一元多项式 Pn(x)可以表示为,
Pn(x)=a0+a1x+a2x2+… +anxn (最多有 n+1项 )
aixi是多项式的第 i项 ( 0≤i≤n),其中 ai为系数,x为变量,i为指数 。
它有 n+1个系数,因此,在计算机里,它可用一个线性表 P来表示:
P=( a0,a1,a2,…,an)
假设 Qn(x)是一元 m次多项式,同样可用线性表 Q来示:
Q=( b0,b1,b2,…,bm)
若 m<n,则两个多项式相加的结果 Rn(x)= Pn(x)+ Qn(x)可用线性表 R来表示:
R=( a0+ b0,a1+ b1,a2+b2,…,a m+ bm,am+1,…,a n)
我们可以对 P,Q和 R采用顺序存储结构,也可以采用链表存储结构 。
使用顺序存储结构可以使多项式相加的算法十分简单 。 但是,当多项式中存在大量的零系数时,这种表示方式就会浪费在量存储空间 。 为了有效而合理地利用存储空间,可以用链式存储结构来表示多项式 。
采用链式存储结构表示多项式时,多项式中每一个非零系数的项构成链表中的一个结点,而对于系数为零的项则不需表示。
一般情况下,一元多项式 (只表示非零系数项 )可写成:
其中 ak≠0( k=1,2,…m ),em> em-1> … > e0≥0
则采用链表表示多项式时,每个结点的数据域有两项,ak表示系数,em
表示指数。(注意:表示多项式的链表应该是有序链表)
假设多项式 A17(x)=8+3x+9x10+5x17与 B10(x)=8x+14x7-9x10已经用单链表表示,其头指针分别为 Ah与 Bh,如图 2-17所示。
多项式链表中的每一个非零项结点结构用 C语言描述如下:
struct poly
{ int exp; /*指数为正整数 */
double coef; /*系数为双精度型 */
struct poly *next; /*指针域 */
}
将两个多项式相加为 C17(x)=8+11x+14x7+5x17,其运算规则如下:假设指针 qa和 qb分别指向多项式 A17(x)和多项式 B8(x)中当前进行比较的某个结点,则比较两个结点的数据域的指数项,有三种情况:
( 1) 指针 qa所指结点的指数值<指针 qb所指结点的指数值时,则保留 qa指针所指向的结点,qa指针后移;
( 2) 指针 qa所指结点的指数值>指针 qb所指结点的指数值时,则将
qb指针所指向的结点插入到 qa所指结点前,qb指针后移;
( 3) 指针 qa所指结点的指数值=指针 qb所指结点的指数值时,将两个结点中的系数相加,若和不为零,则修改 qa所指结点的系数值,同时释放 qb所指结点;反之,从多项式 A17(x)的链表中删除相应结点,
并释放指针 qa和 qb所指结点 。
-1 8 0 3 1 9 10 5 17 ∧Ah
-1 8 1 14 7 -9 10 ∧Bh
图 2-17 多项式表的单链存储结构
【 算法 2.10 多项式相加 】
struct poly *add_poly(struct poly *Ah,struct poly *Bh)
{struct poly *qa,*qb,*s,*r,*Ch;
qa=Ah->next;qb=Bh->next; /*qa和 qb分别指向两个链表的第一结点 */
r=qa;Ch=Ah; /*将链表 Ah作为相加后的和链表 */
while(qa!=NULL&&qb!=NULL) /*两链表均非空 */
{ if (qa->exp==qb->exp) /*两者指数值相等 */
{x=qa->coef+qb->coef;
if(x!=0)
{ qa->coef=x;r->next=qa;r=qa;
s=qb++;free(s);qa++;
} /*相加后系数不为零时 */
else {s=qa++;free(s);s=qb++;free(s);} /*相加后系数为零时 */
}
else if(qa->exp<qb->exp){ r->next=qa;r=qa;qa++;} /*多项式 Ah的指数值小 */
else {r->next=qb;r=qb;qb++;} /*多项式
Bh的指数值小 *
}
if(qa==NULL) r->next=qb;
else r->next=qa;
/*链接多项式 Ah或 Bh中的剩余结点 */
return (Ch);
}
本章小结本章主要介绍了如下一些基本概念:
线性表,一个线性表是 n≥0个数据元素 a0,a1,a2,…,an-
1的有限序列 。
线性表的顺序存储结构,在计算机中用一组地址连续的存储单元依次存储线性表的各个数据元素,称作线性表的顺序存储结构 。
线性表的链式存储结构,线性表的链式存储结构就是用一组任意的存储单元 ——结点 ( 可以是不连续的 ) 存储线性表的数据元素 。 表中每一个数据元素,都由存放数据元素值的数据域和存放直接前驱或直接后继结点的地址 ( 指针 ) 的指针域组成 。
循环链表,循环链表 (Circular Linked List)是将单链表的表中最后一个结点指针指向链表的表头结点,整个链表形成一个环,从表中任一结点出发都可找到表中其他的结点 。
循环链表,循环链表 (Circular Linked List)是将单链表的表中最后一个结点指针指向链表的表头结点,整个链表形成一个环,从表中任一结点出发都可找到表中其他的结点 。
双向链表,双向链表中,在每一个结点除了数据域外,
还包含两个指针域,一个指针( next)指向该结点的后继结点,另一个指针( prior)指向它的前驱结点。
除上述基本概念以外,学生还应该了解:线性表的基本操作(初始化、插入、删除、存取、复制、合并)、顺序存储结构的表示、线性表的链式存储结构的表示、一元多项式 Pn(x),掌握顺序存储结构(初始化、插入操作
、删除操作)、单链表(单链表的初始化、单链表的插入、单链表的删除)。
习 题 二
1,什么是顺序存储结构? 什么是链式存储结构?
2,线性表的顺序存储结构和链式存储结构各有什么特点?
3,设线性表中数据元素的总数基本不变,并很少进行插入或删除工作
,若要以最快的速度存取线性表中的数据元素,应选择线性表的何种存储结构? 为什么?
4,线性表的主要操作有哪些?
5,简述数组与顺序存储结构线性表的区别和联系 。
6,顺序表和链表在进行插入操作时,有什么不同?
7,画出下列数据结构的图示,① 顺序表 ② 单链表 ③ 双链表 ④ 循环链表
8,试给出求顺序表长度的算法 。
9,若顺序表 A中的数据元素按升序排列,要求将 x插入到顺序表中的合适位置,以保证表的有序性,试给出其算法 。
10,试将一个无序的线性表 A=(11,16,8,5,14,10,38,23)转换成一个按升序排列的有序线性表 ( 用链表实现 ) 。
1

2
算术表达式求值
3
队列第三章 栈和队列本章学习导读从数据结构上看,栈和队列也是线性表,不过是两种特殊的线性表。栈只允许在表的一端进行插入或删除操作
,而队列只允许在表的一端进行插入操作、而在另一端进行删除操作。因而,栈和队列也可以被称作为操作受限的线性表。通过本章的学习,读者应能掌握栈和队列的逻辑结构和存储结构,以及栈和队列的基本运算以及实现算法。
3.1 栈在各种程序设计语言中都有子程序 ( 或称函数,过程 ) 调用功能 。 而子程序也可以调用其它的子程序,甚至可以直接或间接地调用自身,
这种调用关系就是递归 。 下面以求阶乘的递归方法为例,来分析计算机系统是如何处理这种递归调用关系的 。
求 n! 的递归方法的思路是:
相应的 C语言函数是:
float fact(int n)
{float s;
if (n= =0||n= =1) s=1;
else s=n*fact(n-1);
return (s); }
在该函数中可以理解为求 n! 用 fact(n)来表示,则求 (n-1)! 就用 fact(n-
1)来表示 。
若求 5!,则有
main()
{printf(“5!=%f\n”,fact(5)); }
)1(
)1,0(
)!1(*
1!

n
n
nnn
图 3-1给出了递归调用执行过程 。 从图中可看到 fact函数共被调用 5次,
即 fact(5),fact(4),fact(3),fact(2),fact(1)。 其中,fact(5)为主函数调用,其它则为在 fact函数内的调用 。 每一次递归调用并未立即得到结果,而是进一步向深度递归调用,直到 n=1或 n=0时,函数 fact才有结果为 1,然后再一一返回计算,最终得到结果 。
主函数
mani()
printf(“fact(5)”) 第一层调用
n=5
s=5*fact(4) 第二层调用
n=4
s=4*fact(3) 第三层调用
n=3
S=3*fact(2) 第四层调用
n=2
S=2*fact(1)
第五层调用
n=1
S=1
fact(1)
=1
fact(2)
=2
fact(3)
=6
fact(4)
=24
fact(5)=
120
输出
s=120.00
图 3-1 递归调用过程示意图计算机系统处理上述过程时,其关键是要正确处理执行过程中的递归调用层次和返回路径,也就是要记住每一次递归调用时的返回地址 。 在系统中是用一个线性表动态记忆调用过程中的路径,其处理原则为:
( 1) 在开始执行程序前,建立一个线性表,其初始状态为空 。
( 2) 当发生调用 ( 递归 ) 时,将当前的调用的返回点地址插入到线性表的末尾;
( 3) 当调用 ( 递归 ) 返回时,其返回地址从线性表的末尾取出 。
根据以上的原则,可以给出线性表中的元素变化状态如图 3-2所示 (
以递归调用时 n值的变化为例 ),
5 45
45 3 45 3 2 45 3 2 1
图 3-2 递归调用时线性表状态
3.1.1 栈的定义及其运算
1,栈的定义栈 ( stack) 是一种只允许在一端进行插入和删除的线性表,它是一种操作受限的线性表 。 在表中只允许进行插入和删除的一端称为栈顶 ( top),另一端称为栈底 (bottom)。 栈的插入操作通常称为入栈或进栈 (push),而栈的删除操作则称为出栈或退栈 (pop)。 当栈中无数据元素时,称为空栈 。
根据栈的定义可知,栈顶元素总是最后入栈的,因而是最先出栈;栈底元素总是最先入栈的,因而也是最后出栈 。 这种表是按照后进先出 ( LIFO,
last in first out ) 的原则组织数据的,因此,栈也被称为,后进先出,的线性表 。
a0
a1
an-1
入栈 出栈栈顶 top
栈底
bottom 图 3-3栈的示意图



图 3-3是一个栈的示意图,通常用指针 top指示栈顶的位置,用指针 bottom
指向栈底 。 栈顶指针 top动态反映栈的当前位置 。
2,栈的基本运算
( 1) initStack(s) 初始化:初始化一个新的栈 。
( 2) empty(s) 栈的非空判断:若栈 s不空,则返回 TRUE;否则,
返回 FALSE。
( 3) push(s,x) 入栈:在栈 s的顶部插入元素 x,若栈满,则返回
FALSE;否则,返回 TRUE。
( 4) pop(s) 出栈:若栈 s不空,则返回栈顶元素,并从栈顶中删除该元素;否则,返回空元素 NULL。
( 5) getTop(s) 取栈元素:若栈 s不空,则返回栈顶元素;否则返回空元素 NULL。
( 6) setEmpty(s) 置栈空操作:置栈 s为空栈 。
栈是一种特殊的线性表,因此栈可采用顺序存储结构存储,也可以使用链式存储结构存储 。
3.1.2 栈的顺序存储结构
1,顺序栈的数组表示与第二章讨论的一般的顺序存储结构的线性表一样,利用一组地址连续的存储单元依次存放自栈底到栈顶的数据元素,这种形式的栈也称为顺序栈
。 因此,我们可以使用一维数组来作为栈的顺序存储空间 。 设指针 top指向栈顶元素的当前位置,以数组小下标的一端作为栈底,通常以 top=0时为空栈,在元素进栈时指针 top不断地加 1,当 top等于数组的最大下标值时则栈满 。
top=0 top=1
A
top=5
A
C
D
B
E
top=3
A
BC
图 3-4 栈的存储结构
( a)空栈;( b)插入元素 A后;( c
)插入元素 B,C,D,E后;( d)删除元素 E,D后
( a) ( b) ( c) ( d)
图 3-4展示了顺序栈中数据元素与栈顶指针的变化 。
用 C语言定义的顺序存储结构的栈如下:
# define MAXNUM <最大元素数 >
typedef struct {
Elemtype stack[MAXNUM];
int top; } sqstack;
鉴于 C语言中数组的下标约定是从 0开始的,因而使用 C语言的一维数组作为栈时,应设栈顶指针 top=-1时为空栈 。
2,顺序栈的基本运算算法
( 1) 初始化栈
【 算法 3.1 栈的初始化 】
int initStack(sqstack *s)
{/*创建一个空栈由指针 S指出 */
if ((s=(sqstack*)malloc(sizeof(sqstack)))= =NULL) return FALSE;
s->top= -1;
return TRUE;
}
( 2) 入栈操作
【 算法 3.2 入栈操作 】
int push(sqstack *s,Elemtype x)
{/*将元素 x插入到栈 s中,作为 s的新栈顶 */
if(s->top>=MAXNUM-1) return FALSE; /*栈满 */
s->top++;
s->stack[s->top]=x;
return TRUE;
}
( 3) 出栈操作
【 算法 3.3 出栈操作 】
Elemtype pop(sqstack *s)
{/*若栈 s不为空,则删除栈顶元素 */
Elemtype x;
if(s->top<0) return NULL; /*栈空 */
x=s->stack[s->top];
s->top--;
return x;
}
( 4) 取栈顶元素操作
【 算法 3.4 取栈顶元素 】
Elemtype gettop(sqstack *s)
{/*若栈 s不为空,则返回栈顶元素 */
if(s->top<0) return NULL; /*栈空 */
return (s->stack[s->top]);
}
取栈顶元素与出栈不同之处在于出栈操作改变栈顶指针 top的位置,而取栈顶元素操作不改变栈的栈顶指针 。
( 5) 判栈空操作
【 算法 3.5 判栈空操作 】
int Empty(sqstack *s)
{/*栈 s为空时,返回为 TRUE;非空时,返回为 FALSE*/
if(s->top<0) return TRUE;
return FALSE;
}( 6) 置空操作
【 算法 3.6 栈置空操作 】
void setEmpty(sqstack *s)
{/*将栈 s的栈顶指针 top,置为 -1*/
s->top= -1;
}
3.1.3 多栈共享邻接空间在计算机系统软件中,各种高级语言的编译系统都离不开栈的使用 。 常常一个程序中要用到多个栈,为了不发生上溢错误,就必须给每个栈预先分配一个足够大的存储空间,但实际中很难准确地估计 。 另一面方面,若每个栈都预分配过大的存储空间,势必会造成系统空间紧张 。 若让多个栈共用一个足够大的连续存储空间,则可利用栈的动态特性使它们的存储空间互补 。 这就是栈的共享邻接空间 。
1,双向栈在一维数组中的实现栈 的共 享中最 常见的 是两 栈的共 享 。 假设两 个栈共 享一 维数 组
stack[MAXNUM],则可以利用栈的,栈底位置不变,栈顶位置动态变化,
的特性,两个栈底分别为 -1和 MAXNUM,而它们的栈顶都往中间方向延伸
。 因此,只要整个数组 stack[MAXNUM]未被占满,无论哪个栈的入栈都不会发生上溢 。
C语言定义的这种两栈共享邻接空间的结构如下:
Typedef struct {
Elemtype stack[MAXNUM];
int lefttop; /*左栈栈顶位置指示器 */
int righttop; /*右栈栈顶位置指示器 */ } dupsqstack;
两个栈共享邻接空间的示意图如图 3-5所示 。 左栈入栈时,栈顶指针加 1,右栈入栈时,栈顶指针减 1。
自由区
lefttop rightto
0 MAXNU
M-1
图 3-5 两个栈共享邻接空间
char status;
status=’L’; /*左栈 */
status=’R’; /*右栈 */
在进行栈操作时,需指定栈号,status=’L’为左栈,status=’R’为右栈;判断栈满的条件为:
s->lefttop+1= =s->rigthtop;
为了识别左右栈,必须另外设定标志:
2,共享栈的基本操作
( 1) 初始化操作
【 算法 3.7 共享栈的初始化 】
int initDupStack(dupsqstack *s)
{/*创建两个共享邻接空间的空栈由指针 S指出 */
if ((s=(dupsqstack*)malloc(sizeof(dupsqstack)))= =NULL) return FALSE;
s->lefttop= -1;
s->righttop=MAXNUM;
return TRUE;
}
( 2) 入栈操作
【 算法 3.8 共享栈的入栈操作 】
int pushDupStack(dupsqstack *s,char status,Elemtype x)
{*把数据元素 x压入左栈 ( status=’L’) 或右栈 ( status=’R’) */
if(s->lefttop+1= =s->righttop) return FALSE; /*栈满 * / if(status=’L’) s-
>stack[++s->lefttop]=x; /*左栈进栈 */
elseif(status=’R’) s->stack[--s->lefttop]=x; /*右栈进栈 */
else return FALSE; /*参数错误 */
return TRUE;
}
( 3) 出栈操作
【 算法 3.9 共享栈的出栈操作 】
Elemtype popDupStack(dupsqstack *s,char status)
{/*从左栈 ( status=’L’) 或右栈 ( status=’R’) 退出栈顶元素 */
if(status==’L’)
{ if (s->lefttop<0)
return NULL; /*左栈为空 */
else return (s->stack[s->lefttop--]); /*左栈出栈 */
}
else if(status==’R’)
{ if (s->righttop>MAXNUM-1)
return NULL; /*右栈为空 */
else return (s->stack[s->righttop++]); /*右栈出栈 */
}
else return NULL; /*参数错误 */
3.1.4 栈的链式存储结构栈也可以采用链式存储结构表示,这种结构的栈简称为链栈 。 在一个链栈中,栈底就是链表的最后一个结点,而栈顶总是链表的第一个结点 。 因此,新入栈的元素即为链表新的第一个结点,只要系统还有存储空间,就不会有栈满的情况发生 。 一个链栈可由栈顶指针
top唯一确定,当 top为 NULL时,是一个空栈 。 图 3-6给出了链栈中数据元素与栈顶指针 top的关系 。
链栈的 C语言定义为:
typedef struct Stacknode
{
Elemtype data;
Struct Stacknode *next;
}slStacktype;
B
A ∧
top B
A ∧
top C
A ∧top
图 3-6 链栈的存储结构图
( a)含有两个元素 A,B的栈;( b)插入元素 C后的栈;( c)删除元素 C,B后的栈
( a) ( b) ( c)
( 1) 入栈操作
【 算法 3.10 单个链栈的入栈操作 】
int pushLstack(slStacktype *top,Elemtype x)
{/*将元素 x压入链栈 top中 */
slStacktype *p;
if((p=(slStacktype *)malloc(sizeof(slStacktype)))= =NULL) return FALSE; /*
申请一个结点 */
p->data=x; p->next=top; top=p; return TRUE;
}
( 2) 出栈操作
【 算法 3.11 单个链栈的出栈操作 】
Elemtype popLstack(slStacktype *top)
{/*从链栈 top中删除栈顶元素 */
slStacktype *p;
Elemtype x;
if (top= =NULL) return NULL; /*空栈 */
p=top; top=top->next;
x=p->data;free(p);return x;
}
2,多个链栈的操作在程序中同时使用两个以上的栈时,使用顺序栈共用邻接空间很不方便,
但若用多个单链栈时,操作极为方便,这就涉及多个链栈的操作 。 我们可将多个单链栈的栈顶指针放在一个一维数组
slStacktype *top[M];
之中,让 top[0],top[1],…,top[i],…,top[M-1]指向 M个不同的链栈,
操作时只需确定栈号 i,然后以 top[i]为栈顶指针进行栈操作,就可实现各种操作 。
( 1) 入栈操作
【 算法 3.12 多个链栈的入栈操作 】
int pushDupLs(slStacktype *top[M],int i,Elemtype x)
{/*将元素 x压入链栈 top[i]中 */
slStacktype *p;
if((p=(slStacktype *)malloc(sizeof(slStacktype)))= =NULL) return FALSE; /*
申请一个结点 */
p->data=x; p->next=top[i]; top[i]=p; return TRUE;
}
( 2) 出栈操作
【 算法 3.13 多个链栈的出栈操作 】
Elemtype popDupLs(slStacktype *top[M],int i)
{/*从链栈 top[i]中删除栈顶元素 */
slStacktype *p;
Elemtype x;
if (top[i]= =NULL) return NULL; /*空栈 */
p=top[i]; top[i]=top[i]->next;
x=p->data;free(p);return x;
}
在上面的两个算法中,当指定栈号 i(0≤i≤M-1)时,则只对第 i个链栈操作
,不会影响其它链栈 。
3.2 算术表达式求值表达式求值是程序设计语言编译中的一个最基本问题 。 它的实现方法是栈的一个典型的应用实例 。
在计算机中,任何一个表达式都是由操作数 ( operand),运算符 ( operator
) 和界限符 ( delimiter) 组成的 。 其中操作数可以是常数,也可以是变量或常量的标识符;运算符可以是算术运算体符,关系运算符和逻辑符;界限符为左右括号和标识表达式结束的结束符 。 在本节中,仅讨论简单算术表达式的求值问题 。 在这种表达式中只含加,减,乘,除四则运算,所有的运算对象均为单变量 。 表达式的结束符为,#”。
算术四则运算的规则为:
( 1) 先乘除,后加减;
( 2) 同级运算时先左后右;
( 3) 先括号内,后括号外 。
计算机系统在处理表达式前,首先设置两个栈:
( 1) 操作数栈 ( OPRD),存放处理表达式过程中的操作数 。
( 2) 运算符栈 ( OPTR),存放处理表达式过程中的运算符 。 开始时,在运算符栈中先在栈底压入一个表达式的结束符,#”。
表 3-1给出了 +,-,*,/,(,),和 #的算术运算符间的优先级的关系 。
计算机系统在处理表达式时,从左到右依次读出表达式中的各个符号
( 操作数或运算符 ),每读出一个符号后,根据运算规则作如下的处理:
( 1) 假如是操作数,则将其压入操作数栈,并依次读下一个符号 。
( 2) 假如是运算符,则:
1) 假如读出的运算符的优先级大于运算符栈栈顶运算符的优先级,则将其压入运算符栈,并依次读下一个符号 。
2) 假如读出的是表达式结束符,#”,且运算符栈栈顶的运算符也为
,#”,则表达式处理结束,最后的表达式的计算结果在操作数栈的栈顶位置 。
3) 假如读出的是,(,,则将其压入运算符栈 。
4) 假如读出的是,),,则:
A) 若运算符栈栈顶不是,(,,则从操作数栈连续退出两个操作数,
从运算符栈中退出一个运算符,然后作相应的运算,并将运算结果压入操作数栈,然后继续执行 A) 。
B) 若运算符栈栈顶为,(,,则从运算符栈退出,(,,依次读下一个符号 。
5)假如读出的运算符的优先级不大于运算符栈栈顶运算符的优先级,
则从操作数栈连续退出两个操作数,从运算符栈中退出一个运算符,然后作相应的运算,并将运算结果压入操作数栈。此时读出的运算符下次重新考虑(即不读入下一个符号)。
图 3-7给出了表达式 5+(6-4/2)*3的计算过程,最后的结果为 T4,置于 OPRD的栈顶 。
图 3-7 表达式的计算过程
(c)读出 ),作运算
T1=4/2=2
top 62
5
top -
#
(
+
(d)作运算 T2=6-2=4
OPRD
top
5
4
OPTR
top
+
#
(
(h)重新考虑 #,作运算
T4=5+18=23
OPRDtop
23
OPTR
top #
(g)读 #,作运算
T3=6*3=18
OPTR
top +
#
OPRD
top 185
(a)初始状态
OPTROPRDtop
top #
(b)读出 5,+,(,6,-,4,/,2OPTR
top /
-
(
+
#
OPRD
top
5
2
4
6
(e)退 ( OPTROPRD
top 54 top
#
+
(f)读出 *,3
OPRD
top 3
5
4
OPTR
top
#
+
*
OPRD OPTR
以上讨论的表达式一般都是运算符在两个操作数中间 ( 除单目运算符外 ),这种表达式被称为中缀表达式 。 中缀表达式有时必须借助括号才能将运算顺序表达清楚,处理起来比较复杂 。 在编译系统中,对表达式的处理采用的是另外一种方法,即将中缀表达式转变为后缀表达式,然后对后缀式表达式进行处理,后缀表达式也称为逆波兰式 。
波兰表示法 ( 也称为前缀表达式 ) 是由波兰逻辑学家 ( Lukasiewicz)
提出的,其特点是将运算符置于运算对象的前面,如 a+b表示为 +ab;
逆波兰式则是将运算符置于运算对象的后面,如 a+b表示为 ab+。 中缀表达式经过上述处理后,运算时按从左到右的顺序进行,不需要括号
。 得到后缀表达式后,我们在计算表达式时,可以设置一个栈,从左到右扫描后缀表达式,每读到一个操作数就将其压入栈中;每到一个运算符时,则从栈顶取出两个操作数进行运算,并将结果压入栈中,
一直到后缀表达式读完 。 最后栈顶就是计算结果 。
3.3 队列在日常生活中队列很常见,如,我们经常排队购物或购票,排队是体现了,先来先服务,( 即,先进先出,) 的原则 。
队列在计算机系统中的应用也非常广泛 。 例如:操作系统中的作业排队 。 在多道程序运行的计算机系统中,可以同时有多个作业运行,它们的运算结果都需要通过通道输出,若通道尚未完成输出,则后来的作业应排队等待,每当通道完成输出时,则从队列的队头退出作业作输出操作,而凡是申请该通道输出的作业都从队尾进入该队列 。
计算机系统中输入输出缓冲区的结构也是队列的应用 。 在计算机系统中经常会遇到两个设备之间的数据传输,不同的设备通常处理数据的速度是不同的,当需要在它们之间连续处理一批数据时,高速设备总是要等待低速设备,这就造成计算机处理效率的大大降低 。 为了解决这一速度不匹配的矛盾,通常就是在这两个设备之间设置一个缓冲区
。 这样,高速设备就不必每次等待低速设备处理完一个数据,而是把要处理的数据依次从一端加入缓冲区,而低速设备从另一端取走要处理的数据 。
3.3.1 队列的定义及其运算
1,队列的定义队列 ( queue) 是一种只允许在一端进行插入,而在另一端进行删除的线性表,它是一种操作受限的线性表 。 在表中只允许进行插入的一端称为队尾 ( rear),只允许进行删除的一端称为队头 (front)。 队列的插入操作通常称为入队列或进队列,而队列的删除操作则称为出队列或退队列 。 当队列中无数据元素时,称为空队列 。
根据队列的定义可知,队头元素总是最先进队列的,也总是最先出队列;
队尾元素总是最后进队列,因而也是最后出队列 。 这种表是按照先进先出
( FIFO,first in first out ) 的原则组织数据的,因此,队列也被称为,先进先出,表 。
假若队列 q={a0,a1,a2,…,an-1},进队列的顺序为 a0,a1,a2,…,an-1
,则队头元素为 a0,队尾元素为 an-1。
入列出列 a0 a1 a2 ai an-1
front rear
图 3-8 队列的示意图
… …
图 3-8是一个队列的示意图,通常用指针 front指示队头的位置,用指针 rear指向队尾。
2,队列的基本运算
( 1) initQueue(q) 初始化:初始化一个新的队列 。
( 2) empty(q) 队列非空判断:若队列 q不空,则返回 TRUE;否则,返回 FALSE。
( 3) append(q,x) 入队列:在队列 q的尾部插入元素 x,使元素 x成为新的队尾 。 若队列满,则返回 FALSE;否则,返回 TRUE。
( 4) delete(s) 出队列:若队列 q不空,则返回队头元素,并从队头删除该元素,队头指针指向原队头的后继元素;否则,返回空元素 NULL。
( 5) getHead(q) 取队头元素:若队列 q不空,则返回队头元素;否则返回空元素 NULL。
( 6) length(q) 求队列长度:返回队列的长度 。
队列是一种特殊的线性表,因此队列可采用顺序存储结构存储,也可以使用链式存储结构存储 。
3.3.2 队列的顺序存储结构
1,顺序队列的数组表示队列的顺序存储结构可以简称为顺序队列,也就是利用一组地址连续的存储单元依次存放队列中的数据元素 。 一般情况下,我们使用一维数组来作为队列的顺序存储空间,另外再设立两个指示器:一个为指向队头元素位置的指示器 front,另一个为指向队尾的元素位置的指示器 rear。
C语言中,数组的下标是从 0开始的,因此为了算法设计的方便,在此我们约定:初始化队列时,空队列时令 front=rear=-1,当插入新的数据元素时,尾指示器 rear加 1,而当队头元素出队列时,队头指示器 front加 1。 另外还约定,在非空队列中,头指示器 front总是指向队列中实际队头元素的前面一个位置,而尾指示器 rear总是指向队尾元素 。
图 3-9 队列的存储结构
( a)空队列;( b)元素 A入列后;( c)元素 B,C
,D,E入列后;( d)元素 E,D出队列后
front=-
10
front=-1
A
front=-1
A
C
D
B
E rear=4
D
( a) ( b) ( c) ( d)rear=-1
rear=0
rear=4 E
front=2
图 3-9给出了队列中头尾指针的变化状态 。
2,顺序队列的基本运算算法
( 1) 初始化队列
【 算法 3.14 顺序队列的初始化 】
int initQueue(sqqueue *q)
{/*创建一个空队列由指针 q指出 */
if ((q=(sqqueue*)malloc(sizeof(sqqueue))= =NULL) return FALSE;
q->front= -1;
q->rear=-1;
return TRUE;
}
( 2) 入队列操作
【 算法 3.15 顺序队列的入队列操作 】
int append(sqqueue *q,Elemtype x)
{/*将元素 x插入到队列 q中,作为 q的新队尾 */
if(q->rear>=MAXNUM-1)return FALSE; /*队列满 */
q->rear++;
q->queue[q->rear]=x;
return TRUE;
}
( 3) 出队列操作
【 算法 3.16 顺序队列的出队列操作 】
Elemtype delete(sqqueue *q)
{/*若队列 q不为空,则返回队头元素 */
Elemtype x;
if(q->rear= =q->front) return NULL; /*队列空 */
x=q->queue[++q->front];
return x;
}
( 4) 取队头元素操作
【 算法 3.17 顺序队列的取头元素操作 】
Elemtype getHead(sqqueue *q)
{/*若队列 q不为空,则返回队头元素 */
if(q->rear= =q->front) return NULL; /*队列空 */
return (q->queue[s->front+1]);
}
( 5) 判队列非空操作
【 算法 3.18 顺序队列的非空判断操作 】
int Empty(sqqueue *q)
{/*队列 q为空时,返回 TRUE;否则返回 FALSE*/ if (q->rear= =q-
>front) return TRUE;
return FALSE;
( 6) 求队列长度操作
【 算法 3.19 顺序队列的求长度操作 】
int length(sqqueue *q)
{/*返回队列 q的元素个数 */
return(q->rear-q->front);
3,循环队列
MAXNUM
-1 0
1
rear
front
图 3-10 循环队列示意在顺序队列中,当队尾指针已经指向了队列的最后一个位置时,此时若有元素入列,就会发生,溢出,。 在图 3-9( c) 中队列空间已满,若再有元素入列,则为溢出;在图 3-9( d) 中,虽然队尾指针已经指向最后一个位置,但事实上队列中还有 3个空位置 。 也就是说,队列的存储空间并没有满,但队列却发生了溢出,我们称这种现象为假溢出 。 解决这个问题有两种可行的方法:
( 1) 采用平移元素的方法,当发生假溢出时,就把整个队列的元素平移到存储区的首部,然后再插入新元素 。 这种方法需移动大量的元素,因而效率是很低的 。
( 2) 将顺序队列的存储区假想为一个环状的空间,如图 3-10所示 。 我们可假想 q->queue[0]接在 q->queue[MAXNUM-1]的后面 。 当发生假溢出时,
将新元素插入到第一个位置上,这样做,虽然物理上队尾在队首之前,但逻辑上队首仍然在前 。 入列和出列仍按,先进先出,的原则进行,这就是循环队列 。
很显然,方法二中不需要移动元素,操作效率高,空间的利用率也很高

在循环队列中,每插入一个新元素时,就把队尾指针沿顺时针方向移动一个位置 。 即:
q->rear=q->rear+1;
if(q->rear= =MAXNUM) q->rear=0;
在循环队列中,每删除一个元素时,就把队头指针沿顺时针方向移动一个位置 。 即:
q->front=q->front+1;
if(q->front= =MAXNUM) q->front=0;
0
1
23
4
5front
rear(b)
A
B
C
0
1
23
4
5front
rear
(a)
0
1
23
4
5
A
B
CD
E
F
front
rear
(c)
图 3-11 循环队列示意图
( a)队列空;( b)队列非空;
(c)队列满图 3-11所示,为循环队列的三种状态,图 3-11( a) 为队列空时,有 q-
>front= =q->rear;图 3-11( b) 为队列满时,也有 q->front= =q->rear;因此仅凭 q->front= =q->rear不能判定队列是空还是满 。
为了区分循环队列是空还是满,我们可以设定一个标志位 s:
s= 0时为空队列,s=1时队列非空 。
用 C语言定义循环队列结构如下:
typedef struct
{Elemtype queue[MAXNUM];
int front; /*队头指示器 */
int rear; /*队尾指示器 */
int s; /*队列标志位 */
}qqueue;
下面给出循环队列的初始化,入队列及出队列的算法 。
( 1) 初始化队列
【 算法 3.20 循环队列的初始化 】
int initQueue(qqueue *q)
{/*创建一个空队列由指针 q指出 */
if ((q=(qqueue*)malloc(sizeof(qqueue)))= =NULL) return FALSE;
q->front= MAXNUM;
q->rear=MAXNUM;
q->s=0;
return TRUE;
}
( 2) 入队列操作
【 算法 3.21 循环队列的入队列操作 】
int append(qqueue*q,Elemtypex)
{/*将元素 x插入到队列 q中,作为 q的新队尾 */
if (( q->s= =1)&&(q->front= =q->rear)) return FALSE; /*队列满 */
q->rear++;
if (q->rear= =MAXNUM) q->rear=0;
q->queue[q->rear]=x;
q->s=1; /*置队列非空 */
return TRUE;
}
( 3) 出队列操作
【 算法 3.22 循环队列的出队列操作 】
Elemtype delete(qqueue *q)
{/*若队列 q不为空,则返回队头元素 */
Elemtype x;
if (q->s= =0) retrun NULL; /*队列为空 */
q->front++;
if (q->front= =MAXNUM) q->front=0;
x=q->queue[q->front];
if (q->front = =q->rear) q->s=0; /*置队列空 */
return x; }
3.3.3 队列的链式存储结构在 C语言中不可能动态分配一维数据来实现循环队列 。 如果要使用循环队列,
则必须为它分配最大长度的空间 。 若用户无法预计所需队列的最大空间,
我们可以采用链式结构来存储队列 。
1,链队列的表示用链表表示的队列简称为链队列,在一个链队列中需设定两个指针 (头指针和尾指针 )分别指向队列的头和尾 。 为了操作的方便,和线性链表一样,我们也给链队列添加一个头结点,并设定头指针指向头结点 。 因此,空队列的判定条件就成为头指针和尾指针都指向头结点 。
图 3-12( a) 所示为一个空队列;图 3-12( b) 所示为一个非空队列 。
rear
front ∧…∧front
rear
图 3-12 链队列示意图用 C语言定义链队列结构如下:
typedef struct Qnode
{Elemtype data;
struct Qnode *next;
}Qnodetype; /*定义队列的结点 */
typedef struct
{ Qnodetype*front;/*头指针 */
Qnodetype *rear; /*尾指针 */
}Lqueue;
2,链队列的主要运算算法
( 1) 初始化队列
【 算法 3.23 链队列的初始化 】
int initLqueue(Lqueue *q)
{/*创建一个空链队列 q*/
if ((q->front=(Qnodetype*)malloc(sizeof(Qnodetype)))= =NULL) return FALSE;
q->rear=q->front;
q->front->next=NULL;
return TRUE;
}
( 2) 入队列操作
【 算法 3.24 链队列的入队列操作 】
int Lappend(Lqueue *q,Elemtype x)
{/*将元素 x插入到链队列 q中,作为 q的新队尾 */
Qnodetype *p;
if ((p=(Qnodetype*)malloc(sizeof(Qnodetype)))= =NULL) return FALSE;
p->data=x;
p->next=NULL; /*置新结点的指针为空 */
q->rear->next=p; /*将链队列中最后一个结点的指针指向新结点 */
q->rear=p; /*将队尾指向新结点 */
return TRUE;
}
( 3) 出队列操作
【 算法 3.25 链队列的出队列操作 】
Elemtype Ldelete(Lqueue *q)
{/*若链队列 q不为空,则删除队头元素,返回其元素值 */
Elemtype x;
Qnodetype *p;
if(q->front->next= =NULL) return NULL; /*空队列 */
P=q->front->next; /*取队头 */
q->front->next=p->next; /*删除队头结点 */
x=p->data;
free(p);
return x;
}
3.3.4 其它队列除了栈和队列之外,还有一种限定性数据结构,它们是双端队列
( double-ended queue) 。
端 1 端 2
插入删除图 3-13 双端队列的示意图
a1 a2 aia0 an-1删除插入 … …
双端队列是限定插入和删除操作在线性表的两端进行,我们可以将它看成是栈底连在一起的两个栈,但它与两个栈共享存储空间是不同的 。 共享存储空间中的两个栈的栈顶指针是向两端扩展的,因而每个栈只需一个指针;而双端队列允许两端进行插入和删除元素,因而每个端点必须设立两个指针,如图 3-13所示 。
在实际使用中,还有输出受限的双端队列 ( 即一个端点允许插入和删除,
另一个端点只允许插入 ) ;输入受限的双端队列 ( 即一个端点允许插入和删除,另一个端点只允许删除 ) 。 如果限定双端队列从某个端点插入的元素只能从该端点删除,则双端队列就蜕变为两个栈底相邻接的栈了 。
尽管双端队列看起来比栈和队列更灵活,但实际中并不比栈和队列实用,
故在此不再深入讨论 。
本章小结本章主要介绍了如下一些基本概念:
栈,是一种只允许在一端进行插入和删除的线性表,它是一种操作受限的线性表 。 在表中只允许进行插入和删除的一端称为栈顶 ( top),另一端称为栈底 (bottom)。 栈顶元素总是最后入栈的,因而是最先出栈;栈底元素总是最先入栈的,因而也是最后出栈 。 因此,栈也被称为,后进先出
” 的线性表 。
栈的顺序存储结构,利用一组地址连续的存储单元依次存放自栈底到栈顶的各个数据元素,称为栈的顺序存储结构 。
双向栈,使两个栈共享一维数组 stack[MAXNUM],利用栈的,栈底位置不变,栈顶位置动态变化,的特性,将两个栈底分别设为 -1和 MAXNUM,而它们的栈顶都往中间方向延伸的栈称为双向栈 。
栈的链式存储结构,栈的链式存储结构就是用一组任意的存储单元(可以是不连续的)存储栈中的数据元素,这种结构的栈简称为链栈。在一个链栈中,栈底就是链表的最后一个结点,而栈顶总是链表的第一个结点。
队列,队列( queue)是一种只允许在一端进行插入,而在另一端进行删除的线性表,它是一种操作受限的线性表
。在表中只允许进行插入的一端称为队尾( rear),只允许进行删除的一端称为队头 (front)。队头元素总是最先进队列的,也总是最先出队列;队尾元素总是最后进队列,
因而也是最后出队列。因此,队列也被称为“先进先出”
表。
队列的顺序存储结构,利用一组地址连续的存储单元依次存放队列中的数据元素,称为队列的顺序存储结构 。
队列的链式存储结构,队列的链式存储结构就是用一组任意的存储单元 ( 可以是不连续的 ) 存储队列中的数据元素,
这种结构的队列称为链队列 。 在一个链队列中需设定两个指针 (头指针和尾指针 )分别指向队列的头和尾 。
除上述基本概念以外,学生还应该了解:栈的基本操作 (
初始化,栈的非空判断,入栈,出栈,取栈元素,置栈空操作 ),栈的顺序存储结构的表示,栈的链式存储结构的表示
,队列的基本操作 ( 初始化,队列非空判断,入队列,出队列,取队头元素,求队列长度 ),队列的顺序存储结构,队列的链式存储结构,掌握顺序栈 ( 入栈操作,出栈操作 ),
链栈 ( 入栈操作,出栈操作 ),顺序队列 ( 入队列操作,出队列操作 ),链队列 ( 入队列操作,出队列操作 ) 。
习 题 三
1,简述栈和线性表的区别和联系 。
2,何为栈和队列? 简述两者的区别和联系 。
3,若依次读入数据元素序列 {a,b,c,d}进栈,进栈过程中允许出栈,试写出各种可能的出栈元素序列 。
4,将下列各算术运算式表示成波兰式和逆波兰式:
(A*(B+C)+D)*E-F*G
A*(B-D)+H/(D+E)-S/N*T
(A-C)*(B+D)+(E-F)/(G+H)
5,写出算术运算式 3+4/25*8-6的操作数栈和运算符栈的变化情况 。
6,若堆栈采用链式存储结构,初始时为空,试画出 a,b,c,d四个元素依次进栈后栈的状态,然后再画出此时的栈顶元素出栈后的状态 。
7,试写出函数 Fibonacci数列:
F1=0 (n=1)
F2=1,(n=2)

Fn=Fn-1+Fn-2 (n>2)
的递归算法和非递归算法 。
8,在一个类型为 staticlist的一维数组 A[0… m-1]存储空间建立二个链接堆栈,其中前 2个单元的 next域用来存储二个栈顶指针,从第 3个单元起作为空闲存储单元空间提供给二个栈共同使用 。 试编写一个算法把从键盘上输入的 n个整型数 (n<=m-2,m>2)按照下列条件进栈:
( 1) 若输入的数小于 100,则进第一个栈;
( 2) 若输入的数大于等于 100,则进第三个栈;
9,试证明:若借助栈由输入序列 1,2,3,…,n得到输出序列 P1,P2,
P3,…,Pn(它是输入序列的一个排列 ),则在输出序列中不可能出现这样的情况:存在 i<j<k,使得 Pj<Pk<Pi。
10,对于一个具有 m个单元的循环队列,写出求队列中元素个数的公式 。
11,简述设计一个结点值为整数的循环队列的构思,并给出在队列中插入或删除一个结点的算法 。
12.有一个循环队列 q(n),进队和退队指针分别为 r和 f;有一个有序线性表 A[M],请编一个把循环队列中的数据逐个出队并同时插入到线性表中的算法。若线性表满则停止退队并保证线性表的有序性。
13,设有栈 stack,栈指针 top=n-1,n>0;有一个队列 Q(m),其中进队指针
r,试编写一个从栈 stack中逐个出栈并同时将出栈的元素进队的算法 。
1 串的基本概念
2 串的存储结构
3 串的基本运算及其实现
4 文本编辑第四章 串本章学习导读在计算机的各方面应用中,非数值处理问题的应用越来越多 。 如在汇编程序和编译程序中,源程序和目标程序都是作为一种字符串数据进行处理的 。 在事务处理系统中,用户的姓名和地址及货物的名称,规格等也是字符串数据 。
字符串一般简称为串,可以将它看作是一种特殊的线性表,这种线性表的数据元素的类型总是字符型的,字符串的数据对象约束为字符集 。 在一般线性表的基本操作中,大多以,单个元素,作为操作对象,而在串中,则是以,串的整体,或一部分作为操作对象 。 因此,一般线性表和串的操作有很大的不同 。 本章主要讨论串的基本概念,存储结构和一些基本的串处理操作 。
4.1 串的基本概念
4.1.1 串的定义串 ( 或字符串 ) ( String) 是由零个或多个字符组成的有限序列 。 一般记作
s=〃 c0c1c2… cn-1〃 (n≥0)
其中,s为串名,用双引号括起来的字符序列是串的值;
ci(0≤i≤n-1)可以是字母,数字或其它字符;双引号为串值的定界符,不是串的一部分;字符串字符的数目 n称为串的长度 。 零个字符的串称为空串,通常以两个相邻的双引号来表示空串 ( Null string),如,s=〃〃
,它的长度为零;仅由空格组成的的串称为空格串,如,s=〃 └┘〃 ;若串中含有空格,在计算串长时,空格应计入串的长度中,如,s=〃 I’m a
student〃 的长度为 13。
请读者注意,在 C语言中,用单引号引起来的单个字符与单个字符的串是不同的,如 s1=' a'与 s2=〃 a〃 两者是不同的,s1表示字符,而 s2表示字符串 。
4.1.2 主串和子串一个串的任意个连续的字符组成的子序列称为该串的子串,包含该子串的串称为主串 。 称一个字符在串序列中的序号为该字符在串中的位置,子串在主串中的位置是以子串的第一个字符在主串中的位置来表示的 。 当一个字符在串中多次出现时,以该字符第一次在主串中出现的位置为该字符在串中的位置 。
例如,s1,s2,s3为如下的三个串,s1=〃 I’m a student〃 ;s2=〃
student〃 ;s3=〃 teacher〃 。
则它们的长度分别为 13,7,7;串 s3是 s1的子串,子串 s3在 s1中的位置为 7,也可以说 s1是 s3的主串;串 s2不是 s1的子串,串 s2和 s3
不相等 。
4.2 串的存储结构对串的存储方式取决于我们对串所进行的运算,如果在程序设计语言中,串的运算只是作为输入或输出的常量出现,则此时只需存储该串的字符序列,这就是串值的存储 。 此外,一个字符序列还可赋给一个串变量,操作运算时通过串变量名访问串值 。 实现串名到串值的访问,在 C语言中可以有两种方式:一是可以将串定义为字符型数组,数组名就是串名,串的存储空间分配在编译时完成,程序运行时不能更改 。 这种方式为串的静态存储结构
。 另一种是定义字符指针变量,存储串值的首地址,通过字符指针变量名访问串值,串的存储空间分配是在程序运行时动态分配的,这种方式称为串的动态存储结构 。
4.2.1 串值的存储我们称串是一种特殊的线性表,因此串的存储结构表示也有两种方法:静态存储采用顺序存储结构,动态存储采用的是链式存储和堆存储结构 。
1,串的静态存储结构类似于线性表的顺序存储结构,用一组地址连续的存储单元存储串值的字符序列 。 由于一个字符只占 1个字节,而现在大多数计算机的存储器地址是采用的字编址,一个字 ( 即一个存储单元 ) 占多个字节,因此顺序存储结构方式有两种:
( 1) 紧缩格式:即一个字节存储一个字符 。 这种存储方式可以在一个存储单元中存放多个字符,充分地利用了存储空间 。 但在串的操作运算时,若要分离某一部分字符时,则变得非常麻烦 。
d a t a


s t r
u c t u
r e \0

4
-
1
串值的紧缩格式存储图 4-1所示是以 4个字节为一个存储单元的存储结构,每个存储单元可以存放 4个字符 。
对于给定的串 s=〃 data└┘structure〃,在 C语言中采用字符' \0'作串值的结束符 。 串 s的串值连同结束符的长度共 15,只需 4个存储单元 。
图 4-1 串值的紧缩格式存储用字符数组存放字符串时,其结构用 C语言定义如下:
#define MAXNUM <允许的最大的字符数 >
typedef struct {
char str[MAXNUM];
int length; /*串长度 */
} stringtype; /*串类型定义 */
由上述讨论可知,串的顺序存储结构有两大不足之处:一是需事先预定义串的最大长度,这在程序运行前是很难估计的。二是由于定义了串的最大长度,使得串的某些操作受限,如串的联接运算等。

4
-
2
串值的非紧缩格式存储
( 2) 非紧缩格式:这种方式是以一个存储单元为单位,每个存储单元仅存放一个字符 。 这种存储方式的空间利用率较低,如一个存储单元有 4个字节,则空间利用率仅为 25%。 但这种存储方式中不需要分离字符,因而程序处理字符的速度高 。 图 4-2即为这种结构的示意图 。
2,串的动态存储结构我们知道,串的各种运算与串的存储结构有着很大的关系,在随机取子串时,顺序存储方式操作起来比较方便,而对串进行插入,删除等操作时,就会变得很复杂 。 因此,有必要采用串的动态存储方式 。
串的动态存储方式采用链式存储结构和堆存储结构两种形式:
( 1) 链式存储结构串的链式存储结构中每个结点包含字符域和结点链接指针域,字符域用于存放字符,指针域用于存放指向下一个结点的指针,因此,串可用单链表表示 。
用链表存放字符串时,其结构用 C语言定义如下:
typedef struct node{
char str;
struct node *next;
} slstrtype;
用单链表存放串,每个结点仅存储一个字符,如图 4-3所示,因此,每个结点的指针域所占空间比字符域所占空间要大得多 。 为了提高空间的利用率,我们可以使每个结点存放多个字符,称为块链结构,如图
4-4所示每个结点存放 4个字符 。
用块链存放字符串时,其结构用 C语言定义如下:
typedef struct node{
char str[4];
struct node *next;
} slstrtype;
( 2) 堆存储结构堆存储结构的特点是,仍以一组空间足够大的,地址连续的存储单元存放串值字符序列,但它们的存储空间是在程序执行过程中动态分配的 。
每当产生一个新串时,系统就从剩余空间的起始处为串值分配一个长度和串值长度相等的存储空间 。
在 C语言中,存在一个称为,堆,的自由空间,由动态分配函数 malloc()
分配一块实际串长所需的存储空间,如果分配成功,则返回这段空间的起始地址,作为串的基址 。 由 free()释放串不再需要的空间 。
用堆存放字符串时,其结构用 C语言定义如下:
typedef struct{
char *str;
int length;
} HSstrtype;
4.2.2 串名的存储映象串名的存储映象就是建立了串名和串值之间的对应关系的一个符号表 。
在这个表中的项目可以依据实际需要来设置,以能方便地存取串值为原则 。
如:
s1=〃 data〃
s2=〃 structure〃
假若一个单元仅存放 1个字符,则上面两个串的串值顺序存储如图 4-5所示 。
若符号表中每行包含有串名,串值的始地址,尾地址,则如图 4-6( a)
所示,也可以不设尾地址,而设置串和长度值 。 则如图 4-6( b) 所示 。
对于链式存储串值的方式,如果要建立串变量的符号表,则只需要存入一个链表的表头指针即可。
4.3 串的基本运算及其实现串的基本运算有赋值,联接,求串长,求子串,求子串在主串中出现的位置,判断两个串是否相等,删除子串等 。 在本节中,我们尽可能以 C语言的库函数表示其中的一些运算,若没有库函数,则用自定义函数说明 。
4.3.1 串的基本运算
( 1) strcpy(str1,str2) 字符串拷贝 ( 赋值 ),把 str2指向的字符串拷贝到 str1
中,返回 str1。 库函数和形参说明如下:
char * strcpy(char * str1,char * str2)
( 2) strcat(str1,str2) 字符串的联接:把字符串 str2接到 str1后面,str1最后的结尾符' \0'被取消 。 返回 str1。 库函数和形参说明如下:
char * strcat(char * str1,char * str2)
( 3) strlen(str) 求字符串的长度:统计字符串 str中字符的个数 ( 不包括'
\0' ),返回字符的个数,若 str为空串,则返回值为 0。 库函数和形参说明如下:
unsigned int strlen(char *str)
( 4) strstr(str1,str2) 子串的查询:找出子串 str2在主串 str1第一次出现的位置(不包括子串 str2的结尾符),返回该位置的指针,若找不到,返回空指针
NULL。库函数和形参说明如下:
char * strstr(char * str1,char * str2)
( 5) strcmp(str1,str2) 字符串的比较:比较两个字符串 str1,str2
。 若 str1< str2,则返回负数;若 str1> str2,则返回正数;若 str1= str2,
则返回 0。 库函数和形参说明如下:
int strcmp(char * str1,char * str2)
( 6) substr(str1,str2,m,n) 求子串:在字符串 str1中,从第 m个字符开始,取 n个长度的子串 str2;若 m> strlen(str)或 n≤0,则返回空值 NULL
。 自定义函数和形参说明如下:
int strstr(char * str1,char *str2,int m,int n)
( 7) delstr(str,m,n) 字符串的删除:在字符串 str中,删除从第 m个字符开始的 n个长度的子串 。 自定义函数和形参说明如下:
Void delstr(char *str,int m,int n)
( 8) Insstr(str1,m,str2 ) 字符串的插入:在字符串 str1第 m个位置之前开始,插入字符串 str2。 返回 str1。 自定义函数和形参说明如下:
Void insstr(char *str1,int m,char *str2)
对字符串的置换可以通过求串长,删除子串,字符串的联接等基本运算来实现 。
4.3.2 串的基本运算及其实现本小节中,我们将讨论串值在静态存储方式和动态存储方式下
,其运算如何实现 。
如前所述,串的存储可以是静态的,也可以是动态的 。 静态存储在程序编译时就分配了存储空间,而动态存储只能在程序执行时才分配存储空间 。 不论在哪种方式下,都能实现串的基本运算 。 本节讨论求子串运算在三种存储方式下的实现方法 。
1,在静态存储结构方式下求子串
C语言中用字符数组存储字符串时,结构定义如下:
#define MAXNUM 80
typedef struct {
char str[MAXNUM];
int length; /*串长度 */
} stringtype; /*串类型定义 */
求主串 s1中第 m个字符起,长度为 n的子串 s2,若存在子串 s2,
则返回 TRUE; 若 m> strlen(s1)或 m<1或 n≤0,则返回 FALSE。 算法如下
【 算法 4-1 在静态存储方式中求子串 】
int substr(stringtype s1,stringtype * s2,int m,int n)
{int j,k;j=s1.length;
if(m<=0||m>j||n<0) {(*s2).str[0]='\0';(*s2).length=0;return FALSE; }/*参数错误 */
k=strlen(&s1.str[m-1]) ;/*求子串的长度 */
if (n>k) (*s2).length=k;
else (*s2).length=n; /*置子串的串长 */
for(j=0;j<=(*s2).length;j++,m++) (*s2).str[j]=s1.str[m-1];
(*s2).str[j]=’\0’;/*置结束标记 */
return TRUE;
}
上述算法中使用数组存放字符串,串长用显式方式给出 。
2,在动态存储结构方式下求子串
( 1) 在链式存储结构方式下假设链表中每个结点仅存放一个字符,则单链表定义如下
typedet struct node{
char str;
struct node *next;
} slstrtype;
求子串运算的算法如下:
【 算法 4-2 在链式存储方式中求子串 】
int substr(slstrtype s1,slstrtype *s2,int m,int n)
{slstrtype *p,*q,*v;
int length1,j;
p=&s1;
for(lenght1=0;p->next!=NULL;p=p->next) length1++;/*求主串和串长 */
if(m<=0||m>length1||n<0) {s2=NULL;return FALSE;}/*参数错误 */
p=s1.next;
for(j=0;j<m;j++)p=p->next;/*找到子串和起始位置 */
s2=(slstrtype *)malloc(sizeof(slstrtype));/*分配子串和第一个结点 */
v=s2;q=v;
for(j=0;j<n&&p->next!=NULL;j++) /*建立子串 */
{ q->str=p->str;
p=p->next;
q=(slstrtype *)malloc(sizeof(slstrtype));
v->next=q;
v=q;
}
q->str=’\0’;q->next=NULL; /*置子串和尾结点 */
return TRUE;
}
( 2) 在堆存储结构方式下堆存储结构用 C语言定义为:
typedet struct{
char *str;
int length;
} HSstrtype;
求子串操作可有两种方法实现,一种是子串与主串共享法,另一种是子串的重新赋值法 。
1) 共享法主串与及子串在堆中只有一个存储映象,这样做可以节省存储空间,算法如下:
【 算法 4-3 共享法求子串 】
int substr(HSstrtype s1,HSstrtype *s2,int m,int n)
{ int j,k;
j=s1.length;
if(m<=0||m>j||n<0) {s2->length=0;return FALSE;}/*参数错误 */
k=strlen(s1.str+m);/*主串第 m个位置开始之后的串长 */
if (n>k) s2->length=k;
else s2->.length=n; /*置子串的串长 */
s2->str=s1.str+m;/*置子串的串首地址
return TRUE;
}
2)重新赋值法将子串存放在与主串不同的堆中 。 算法如下:
【 算法 4-4 重新赋值法求子串 】
int substr(HSstrtypes1,HSstrtype *s2,int m,int n)
{ int j,k;
j=s1.length;
if(m<=0||m>j||n<0) {s2->length=0;return FALSE;}/*参数错误 */
k=strlen(s1.str+m);/*主串第 m个位置开始之后的串长 */
if (n>k) s2->length=k;
else s2->length=n; /*置子串的串长 */
k=s2->length;
for(j=0;j<k;j++)
s2->str[j]=s1.str[m++];/*复制字符 */
s2->str[j]=’\0’;/*置结束符 */
return TRUE;
}
4.4 文本编辑文本编辑是串的一个很典型的应用 。 它被广泛用于各种源程序的输入和修改,也被应用于信函,报刊,公文,书籍的输入,修改和排版
。 文本编辑的实质就是修改字符数据的形式或格式 。 在各种文本编辑程序中,它们把用户输入的所有文本都作为一个字符串 。 尽管各种文本编辑程序的功能可能有强有弱,但是它们的基本的操作都是一致的
,一般包括串的输入,查找,修改,删除,输出等 。
例如有下列一段源程序:
main()
{int a,b,c;
scanf(〃 %d,%d〃,&a,&b);
c=a+b;
printf(“%d”,c);
}
我们把这个源程序看成是一个文本,为了编辑的方便,总是利用换行符把文本划分为若干行,还可以利用换页符将文本组成若干页,这样整个文本就是一个字符串,简称为文本串,其中的页为文本串的子串,行又是页的子串 。 将它们按顺序方式存入计算机内存中,如表 4-2所示 ( 图中 ↙ 表回车符 ) 。
在输入程序的同时,文本编辑程序先为文本串建立相应的页表和行表,
即建立各子串的存储映象 。 串值存放在文本工作区,而将页号和该页中的起始行号存放在页表中,行号,串值的存储起始地址和串的长度记录在行表,由于使用了行表和页表,因此新的一页或一行可存放在文本工作区的任何一个自由区中,页表中的页号和行表中的行号是按递增的顺序排列的,如表 4-3所示 。 设程序的行号从 110开始 。
下面我们就来讨论文本的编辑 。
( 1) 插入一行时,首先在文本末尾的空闲工作区写入该行的串值,然后,在行表中建立该行的信息,插入后,必须保证行表中行号从小到大的顺序 。 若插入行 145,则行表中从 150开始的各行信息必须向下平移一行 。
( 2) 删除一行时,则只要在行表中删除该行的行号,后面的行号向前平移 。 若删除的行是页的起始行,则还要修改相应页的起始行号 ( 改为下一行 ) 。
( 3) 修改文本时,在文本编辑程序中设立了页指针,行指针和字符指针,分别指示当前操作的页,行和字符 。 若在当前行内插入或删除若干字符,则要修改行表中当前行的长度 。 如果该行的长度超出了分配给它的存储空间,则应为该行重新分配存储空间,同时还要修改该行的起始位置 。
对页表的维护与行表类似,在此不再叙述,有兴趣的同学可设计其中的算法 。
本章小结本章主要介绍了如下一些基本概念:
串,串 ( 或字符串 ) ( String) 是由零个或多个字符组成的有限序列 。
主串和子串,一个串的任意个连续的字符组成的子序列称为该串的子串,
包含该子串的串称为主串 。
串的静态存储结构,类似于线性表的顺序存储结构,用一组地址连续的存储单元存储串值的字符序列的存储方式称为串的顺序存储结构 。
堆存储结构,用一组空间足够大的,地址连续的存储单元存放串值字符序列,但其存储空间在程序执行过程中能动态分配的存储方式称为堆存储结构

串的链式存储结构,类似于线性表的链式存储结构,采用链表方式存储串值字符序列的存储方式称为串的顺序存储结构 。
串名的存储映象,串名的存储映象就是建立串名和串值之间的对应关系的一个符号表 。
除上述基本概念以外,学生还应该了解串的基本运算 ( 字符串拷贝 ( 赋值
,字符串的联接,求字符串的长度,子串的查询,字符串的比较 ),串的静态存储结构的表示,串的链式存储结构的表示,串的堆存储结构的表示,能在各种存储结构方式中求字符串的长度,能在各种存储结构方式中利用 C语言提供的串函数进行操作 。
习 题 四
1,简述空串与空格串,串变量与串常量,主串与子串,串名与串值每对术语的区别?
2,两个字符串相等的充要条件是什么?
3,串有哪几种存储结构?
4,已知两个串,s1=”fg cdb cabcadr”,s2=”abc”,试求两个串的长度,判断串 s2是否是串 s1的子串,并指出串 s2在串 s1中的位置 。
5,已知,s1=〃 I’m a student〃,s2=〃 student〃,s3=〃 teacher〃,试求下列各运算的结果:
strstr(s1,s2);
strlen(s1);
strcat(s2,s3);
delstr(s1,4,10);
6,设 s1=”AB”,s2=”ABCD”,s3=”EFGHIJK,试画出堆存储结构下的存储映象图 。
7,试写出将字符串 s2中的全部字符拷贝到字符串 s1中的算法,不允许利用库函数 strcpy()。
8,设 s1和 s2是用结点大小为 1的单链表表示的串,试写出找出 s2中第一个不在
s1中出现的字符的算法 。
9,设字符串采用块链存储结构,块链中每个结点存放 m( m=4) 个字符,试写出实现字符串删除的算法 。
第五章 多维数组和广义表
1 多维数组
2 多维数组的存储结构
3 特殊矩阵及其压缩存储
4 稀疏矩阵
5 广义表本章小结本章学习导读本章主要介绍多维数组的概念及在计算机中的存放,特殊矩阵的压缩存储及相应运算,广义表的概念和存储结构及其相关运算的实现 。 通过本章学习,要求掌握如下内容:
1,多维数组的定义及在计算机中的存储表示;
2,对称矩阵,三角矩阵,对角矩阵等特殊矩阵在计算机中的压缩存储表示及地址计算公式;
3,稀疏矩阵的三元组表示及转置算法实现;
4,稀疏矩阵的十字链表表示及相加算法实现;
5,广义表存储结构表示及基本运算 。
5.1 多维数组
5.1.1 多维数组的概念数组是大家都已经很熟悉的一种数据类型,几乎所有高级语言程序设计中都设定了数组类型 。 在此,我们仅简单地讨论数组的逻辑结构及在计算机内的存储方式

1,一维数组一维数组可以看成是一个线性表或一个向量 ( 第 2章已经介绍 ),它在计算机内是存放在一块连续的存储单元中,适合于随机查找 。 这在第 2章的线性表的顺序存储结构中已经介绍 。
2,二维数组二维数组可以看成是向量的推广 。 例如,设 A是一个有 m行 n列的二维数组,则 A
可以表示为:
a 00 a 01 …… a 0n - 1
a 10 a 11 …… a 1n - 1
…………………………,
A=
a m - 1 0 a m - 1 1 …… a m - 1 n - 1
在此,可以将二维数组 A看成是由 m个行向量 [X0,X1,…,Xm-1]T组成,
其中,Xi=( ai0,ai1,…,,ain-1),0≤i≤m-1;也可以将二维数组 A看成是由 n
个列向量 [y0,y1,……,yn-1]组成,其中 yi=(a0i,a1i,…,.,am-1i),0≤i≤n-1。
由此可知二维数组中的每一个元素最多可有两个直接前驱和两个直接后继 ( 边界除外 ),故是一种典型的非线性结构 。
3,多维数组同理,三维数组最多可有三个直接前驱和三个直接后继,三维以上数组可以作类似分析 。 因此,可以把三维以上的数组称为多维数组,多维数组可有多个直接前驱和多个直接后继,故多维数组是一种非线性结构 。
5.1.2 多维数组在计算机内的存放怎样将多维数组中元素存入到计算机内存中呢? 由于计算机内存结构是一维的 ( 线性的 ),因此,用一维内存存放多维数组就必须按某种次序将数组元素排成一个线性序列,然后将这个线性序列顺序存放在存储器中,具体实现方法在下一节介绍 。
5.2 多维数组的存储结构由于数组一般不作插入或删除操作,也就是说,一旦建立了数组,
则结构中的数组元素个数和元素之间的关系就不再发生变动,即它们的逻辑结构就固定下来了,不再发生变化 。 因此,采用顺序存储结构表示数组是顺理成章的事了 。 本章中,仅重点讨论二维数组的存储,三维及三维以上的数组可以作类似分析 。
多维数组的顺序存储有两种形式 。
1,存放规则行优先顺序也称为低下标优先或左边下标优先于右边下标 。 具体实现时,按行号从小到大的顺序,先将第一行中元素全部存放好,再存放第二行元素,第三行元素,依次类推 ……
在 BASIC语言,PASCAL语言,C/C++语言等高级语言程序设计中,
都是按行优先顺序存放的 。 例如,对刚才的 Am× n二维数组,可用如下形式存放到内存,a00,a01,… a0n-1,a10,a11,...,a1 n-1,…,am-1 0
,am-1 1,…,am-1 n-1。 即二维数组按行优先存放到内存后,变成了一个线性序列 ( 线性表 ) 。
因此,可以得出多维数组按行优先存放到内存的规律:最左边下标变化最慢,最右边下标变化最快,右边下标变化一遍,与之相邻的左边下标才变化一次 。 因此,在算法中,最左边下标可以看成是外循环,
最右边下标可以看成是最内循环 。
2,地址计算由于多维数组在内存中排列成一个线性序列,因此,若知道第一个元素的内存地址,如何求得其他元素的内存地址? 我们可以将它们的地址排列看成是一个等差数列,假设每个元素占 l个字节,元素 aij 的存储地址应为第一个元素的地址加上排在 aij 前面的元素所占用的单元数,而 aij 的前面有 i行 (0~i-1)共 i× n个元素,而本行前面又有 j个元素,故 aij的前面一共有 i× n+j个元素,
设 a00的内存地址为 LOC(a00),则 aij的内存地址按等差数列计算为 LOC(aij)=LOC(a00)+( i× n+j) × l。 同理,三维数组 Am× n× p按行优先存放的地址计算公式为:
LOC(aijk)=LOC(a000)+(i× n× p+j× p+k)× l。
5.2.2 列优先顺序
1,存放规则列优先顺序也称为高下标优先或右边下标优先于左边下标 。 具体实现时,
按列号从小到大的顺序,先将第一列中元素全部存放好,再存放第二列元素,第三列元素,依次类推 ……
在 FORTRAN语言程序设计中,数组是按列优先顺序存放的 。 例如,对前面提到的 Am× n二维数组,可以按如下的形式存放到内存,a00,a10…,
am-10,a01,a11,…,am-1 1,…,a0 m-1,a1m-1,...,am-1 n-1。 即二维数组按列优先存放到内存后,也变成了一个线性序列 ( 线性表 ) 。
因此,可以得出多维数组按列优先存放到内存的规律:最右边下标变化最慢,最左边下标变化最快,左边下标变化一遍,与之相邻的右边下标才变化一次 。 因此,在算法中,最右边下标可以看成是外循环,最左边下标可以看成是最内循环 。
2,地址计算同样与行优先存放类似,若知道第一个元素的内存地址,则同样可以求得按列优存放的某一元素 aij的地址 。
对二维数组有,LOC(aij)=LOC(a00)+(j× m+i)× l
对三维数组有,LOC(aijk)=LOC(a000)+(k× m× n+j× m+i)× l
5.3 特殊矩阵及其压缩存储矩阵是一个二维数组,它是很多科学与工程计算问题中研究的数学对象 。 矩阵可以用行优先或列优先方法顺序存放到内存中,但是,当矩阵的阶数很大时将会占较多存储单元 。 而当里面的元素分布呈现某种规律时,这时,从节约存储单元出发,可考虑若干元素共用一个存储单元,即进行压缩存储 。 所谓压缩存储是指:为多个值相同的元素只分配一个存储空间,值为零的元素不分配空间 。 但是压缩存储时,节约了存储单元,但怎样在压缩后找到某元素呢? 因此还必须给出压缩前的下标和压缩后下标之间变换公式,才能使压缩存储变得有意义 。
1,对称矩阵若一个 n阶方阵 A中元素满足下列条件:
aij=aji 其中 0 ≤i,j≤n-1,则称 A为对称矩阵 。
例如,图 5-1是一个 3*3的对称矩阵 。
5.3.1 特殊矩阵
2,三角矩阵
( 1) 上三角矩阵即矩阵上三角部分元素是随机的,而下三角部分元素全部相同 ( 为某常数 C) 或全为 0,具体形式见图 5-2( a) 。
图 5-1 一个对称矩阵
A=
643
452
321
( 2) 下三角矩阵即矩阵的下三角部分元素是随机的,而上三角部分元素全部相同 ( 为某常数 C)
或全为 0,具体形式见图 5-2( b) 。
( a) 上三角矩阵 ( b) 下三角矩阵图 5-2 三角矩阵
111110
1110
00
...
............
...
...
nnnn aaa
caa
cca
11
1111
100100
.,,.,,.,,.,,
.,,
.,,

nn
n
n
accc
aac
aaa
3,对角矩阵若矩阵中所有非零元素都集中在以主对角线为中心的带状区域中,区域外的值全为 0,则称为对角矩阵 。 常见的有三对角矩阵,五对角矩阵,七对角矩阵等 。
例如,图 5-3为 7× 7的三对角矩阵 ( 即有三条对角线上元素非 0) 。
图 5-3 一个 7× 7的三对角矩阵
6665
565554
454443
343332
232221
121110
0100
00000
0000
0000
0000
0000
0000
00000
aa
aaa
aaa
aaa
aaa
aaa
aa
5.3.2 压缩存储
11121110
222120
1110
00
.,,
.,,.,,.,,.,,.,,
nnnnn
aaaa
aaa
aa
a
( a)一个下三角矩阵
( b)下三角矩阵的压缩存储形式矩阵及用下三角压缩存储图 5-4 对称
a 00 a 1 0 a 11 a 20 a 2 1 a 22 a 30 a 31 …… a n -1 n -3 a n -1 n -2 a n -1 n -1
0 1 2 3 4 5 6 7 …… 2 )1(?nn - 3 2 )1(?nn - 2 2 )1(?nn - 1
3,对角矩阵我们仅讨论三对角矩阵的压缩存储,五对角矩阵,七对角矩阵等读者可以作类似分析 。
在一个 n?n的三对角矩阵中,只有 n+n-1+n-1个非零元素,故只需
3n-2个存储单元即可,零元已不占用存储单元 。
故可将 n?n三对角矩阵 A压缩存放到只有 3n-2个存储单元的 s向量中
,假设仍按行优先顺序存放,
s[k]与 a[i][j]的对应关系为:
3i或 3j 当 i=j
k= 3i+1或 3j-2 当 i=j-1
3i-1 或 3j+2 当 i=j+1
5.4 稀疏矩阵在上节提到的特殊矩阵中,元素的分布呈现某种规律,故一定能找到一种合适的方法,将它们进行压缩存放 。 但是,在实际应用中
,我们还经常会遇到一类矩阵:其矩阵阶数很大,非零元个数较少
,零元很多,但非零元的排列没有一定规律,我们称这一类矩阵为稀疏矩阵 。
按照压缩存储的概念,要存放稀疏矩阵的元素,由于没有某种规律,除存放非零元的值外,还必须存储适当的辅助信息,才能迅速确定一个非零元是矩阵中的哪一个位置上的元素 。 下面将介绍稀疏矩阵的几种存储方法及一些算法的实现 。
5.4.1 稀疏矩阵的存储
1,三元组表在压缩存放稀疏矩阵的非零元同时,若还存放此非零元所在的行号和列号,
则称为三元组表法,即称稀疏矩阵可用三元组表进行压缩存储,但它是一种顺序存储 ( 按行优先顺序存放 ) 。 一个非零元有行号,列号,值,为一个三元组,整个稀疏矩阵中非零元的三元组合起来称为三元组表 。
此时,数据类型可描述如下:
#define maxsize 100 /*定义非零元的最大数目 */
struct node /*定义一个三元组 */
{
int i,j; /*非零元行,列号 */
int v; /*非零元值 */
};
struct sparmatrix /*定义稀疏矩阵 */
{
int rows,cols ; /*稀疏矩阵行,列数 */
int terms; /*稀疏矩阵非零元个数 */
node data [maxsize]; /*三元组表 */
};
2,带行指针的链表把具有相同行号的非零元用一个单链表连接起来,稀疏矩阵中的若干行组成若干个单链表,合起来称为带行指针的链表 。 例如,图 5-6的稀疏矩阵 M的带行指针的链表描述形式见图 5-9。
0 1 20
行指针
1 ^
3
4
5
2
0 2 9 ^
2 5 4 ^
5 3 -7 ^
2 0 -3 ^
3 2 24 ^
4 1 18 ^
5 0 15 ^
图 5-9 带行指针的链表
3,十字链表当稀疏矩阵中非零元的位置或个数经常变动时,三元组就不适合于作稀疏矩阵的存储结构,此时,采用链表作为存储结构更为恰当 。
十字链表为稀疏矩阵中的链接存储中的一种较好的存储方法,在该方法中,
每一个非零元用一个结点表示,结点中除了表示非零元所在的行,列和值的三元组 ( i,j,v) 外,还需增加两个链域:行指针域 ( rptr),用来指向本行中下一个非零元素;列指针域 ( cptr),用来指向本列中下一个非零元素 。 稀疏矩阵中同一行的非零元通过向右的 rptr指针链接成一个带表头结点的循环链表 。 同一列的非零元也通过 cptr指针链接成一个带表头结点的循环链表 。
因此,每个非零元既是第 i行循环链表中的一个结点,又是第 j列循环链表中的一个结点,相当于处在一个十字交叉路口,故称链表为十字链表 。
另外,为了运算方便,我们规定行,列循环链表的表头结点和表示非零元的结点一样,也定为五个域,且规定行,列,域值为 0(因此,为了使表头结点和表示非零元的表结点不发生混淆,三元组中,输入行和列的下标不能从 0
开始 !!!而必须从 1开始 ),并且将所有的行,列链表和头结点一起链成一个循环链表 。
在行 ( 列 ) 表头结点中,行,列域的值都为 0,故两组表头结点可以共用,
即第 i行链表和第 i列链表共用一个表头结点,这些表头结点本身又可以通过
V域 ( 非零元值域,但在表头结点中为 next,指向下一个表头结点 ) 相链接
。 另外,再增加一个附加结点 ( 由指针 hm指示,行,列域分别为稀疏矩阵的行,列数目 ),附加结点指向第一个表头结点,则整个十字链表可由 hm
指针惟一确定 。
例如,图 5-6的稀疏矩阵 M的十字链表描述形式见图 5-10。
十字链表的数据类型描述如下:
struct linknode
{ int i,j;
struct linknode *cptr,*rptr;
union vnext /*定义一个共用体 */
{ int v; /*表结点使用 V域,表示非零元值 */
struct linknode next; /*表头结点使用 next域 */
} k; }
6 7
0 0 0 0
0 0
0 0 0 0 0 0
0 0
hm
0 1 12
0 2 9 0 0
0 0
0 0 2 0 -3
2 5 14
0 0 3 2 24
0 0 4 1 18
0 0 5 0 15
5 3 -7
图 5-10 稀疏矩阵的十字链表
5.4.2 稀疏矩阵的运算
1,稀疏矩阵的转置运算下面将讨论三元组表上如何实现稀疏矩阵的转置运算 。
转置是矩阵中最简单的一种运算 。 对于一个 m?n的矩阵 A,它的转置矩阵 B是一个 n?m 的,且 B[i][j]=A[j][i],0≤i<n,0≤j<m。 例如,图 5-6给出的
M矩阵和图 5-7给出的 N矩阵互为转置矩阵 。
在三元组表表示的稀疏矩阵中,怎样求得它的转置呢?从转置的性质知道,将 A转置为 B,就是将 A的三元组表 a.data变为 B的三元组表 b.data,
这时可以将 a.data中 i和 j的值互换,则得到的 b.data是一个按列优先顺序排列的三元组表,再将它的顺序适当调整,变成行优先排列,即得到转置矩阵 B。 下面将用两种方法处理:
( 1) 按照 A的列序进行转置由于 A的列即为 B的行,在 a.data中,按列扫描,则得到的 b.data必按行优先存放。但为了找到 A的每一列中所有的非零的元素,每次都必须从头到尾扫描 A的三元组表(有多少列,则扫描多少遍),这时算法描述如下:
#define maxsize 100
struct node
{
int i,j; /*定义三元组的行,列号 */
int v; /*三元组的值 */
};
struct sparmatrix
{
int rows,cols; /*稀疏矩阵的行,列数 */
int terms; /*稀疏矩阵的非零元个数 */
struct node data[maxsize]; /*存放稀疏矩阵的三元组表 */
};
void transpose(struct sparmatrix a)
{
struct sparmatrix b; /*b为 a的转置 */
int ano,bno=0,col,i;
b.rows=a.cols; b.cols=a.rows;
b.terms=a.terms;
if (b.terms>0)
{
for ( col=0; col<a.cols; col++) /*按列号扫描 */
for( ano=0;ano<a.terms;ano++) /*对三元组扫描 */
if (a.data[ano].j==col) /*进行转置 */
{ b.data[bno].j=a.data[ano].i;
b.data[bno].i=a.data[ano].j;
for( i=0;i<a.terms;i++) /*输出转置后的三元组结果 */
printf("%5d%5d%5d\n",b.data[i].i,b.data[i].j,b.data[i].v);
}
void main()
{
int i;
struct sparmatrix a;
scanf("%d%d%d",&a.rows,&a.cols,&a.terms); /*输入稀疏矩阵的行,列数及非零元的个数 */
for( i=0;i<a.terms;i++)
scanf("%d%d%d",&a.data[i].i,&a.data[i].j,&a.data[i].v); /*输入转置前的稀疏矩阵的三元组 */
for(i=0;i<a.terms;i++)
printf("%5d%5d%5d\n",a.data[i].i,a.data[i].j,a.data[i].v); /*输出转置前的三元组结果 */
transpose( a); /*调用转置算法 */
}
分析这个算法,主要工作在 col和 ano二重循环上,故算法的时间复杂度为
O(a.cols*a.terms)。 而通常的 m× n阶矩阵转置算法可描述为:
for(col=0; col<n; col++)
for (row=0;row<m;row++)
b[col][row]=a[row][col];
它的时间复杂度为 O(m× n)。 而一般的稀疏矩阵中非零元个数 a.terms远大于行数 m,故压缩存储时,进行转置运算,虽然节省了存储单元,但增大了时间复杂度,故此算法仅适应于 a.terns<<a.rows?a.cols的情形 。
( 2) 按照 A的行序进行转置即按 a.data中三元组的次序进行转置,并将转置后的三元组放入 b中恰当的位置 。 若能在转置前求出矩阵 A的每一列 col( 即 B中每一行 ) 的第一个非零元转置后在 b.data中的正确位置 pot[col]( 0≤col<a.cols),那么在对 a.data的三元组依次作转置时,只要将三元组按列号 col放置到 b.data[pot[col]]中,之后将 pot[col]内容加 1
,以指示第 col列的下一个非零元的正确位置 。 为了求得位置向量 pot,只要先求出 A的每一列中非零元个数 num[col],然后利用下面公式:
pot[col]=pot[col-1]+num[col-1] 当 1≤col<a.cols
pot[0]=0
为了节省存储单元,记录每一列非零元个数的向量 num可直接放入 pot中,即上面的式子可以改为,pot[col]=pot[col-1]+pot[col],其中 1≤col<acols。
于是可用上面公式进行迭代,依次求出其他列的第一个非零元素转置后在 b.data
中的位置 pot[col]。 例如,对前面图 5-6给出的稀疏矩阵 M,有:
每一列的非零元个数为
pot[1]=2 第 0列非零元个数
pot[2]=2 第 1列非零元个数
pot[3]=2 第 2列非零元个数
pot[4]=1 第 3列非零元个数
pot[5]=0 第 4列非零元个数
pot[6]=1 第 5列非零元个数
pot[7]=0 第 6列非零元个数每一列的第一个非零元的位置为
pot[0]=0 第 0列第一个非零元位置
pot[1]=pot[0]+pot[1]=2第 1列第一个非零元位置
pot[2]=pot[1]+pot[2]=4第 2列第一个非零元位置
pot[3]=pot[2]+pot[3]=6第 3列第一个非零元位置
pot[4]=pot[3]+pot[4]=7第 4列第一个非零元位置
pot[5]=pot[4]+pot[5]=7第 5列第一个非零元位置
pot[6]=pot[5]+pot[6]=8第 6列第一个非零元位置则 M稀疏矩阵的转置矩阵 N的三元组表很容易写出 ( 见图 5-
8),算法描述如下:
#define maxsize 100
struct node
{
int i,j;
int v;
};
struct sparmatrix
{
int rows,cols;
int terms;
struct node data[maxsize];
};
void fastrans(struct sparmatrix a)
{
struct sparmatrix b;
int pot[maxsize],col,ano,bno,t,i;
b.rows=a.cols; b.cols=a.rows;
b.terms=a.terms;
if(b.terms>0)
{
for(col=0;col<=a.cols;col++)
pot[col]=0;
for( t=0;t<a.terms;t++) /*求出每一列的非零元个数 */
{
col=a.data[t].j;
pot[col+1]=pot[col+1]+1;
}
pot[0]=0;
for(col=1;col<a.cols;col++) /*求出每一列的第一个非零元在转置后的位置 */
pot[col]=pot[col-1]+pot[col];
for( ano=0;ano<a.terms;ano++) /*转置 */
{ col=a.data[ano].j;
bno=pot[col];
b.data[bno].j=a.data[ano].i;
b.data[bno].i=a.data[ano].j;
b.data[bno].v=a.data[ano].v;
pot[col]=pot[col]+1;
}
}
for( i=0;i<a.terms;i++)
printf("%d\t%d\t%d\n",b.data[i].i,b.data[i].j,b.data[i].v); /*输出转置后的三元组 */
}
void main()
{ struct sparmatrix a;
int i;
scanf("%d%d%d",&a.rows,&a.cols,&a.terms); /*输入稀疏矩阵的行,列数及非零元的个数 */
for( i=0;i<a.terms;i++)
printf("%d\t%d\t%d\n",b.data[i].i,b.data[i].j,b.data[i].v); /*输出转置后的三元组 */
}
void main()
{ struct sparmatrix a;
int i;
scanf("%d%d%d",&a.rows,&a.cols,&a.terms); /*输入稀疏矩阵的行,列数及非零元的个数 */
for( i=0;i<a.terms;i++)
scanf("%d%d%d",&a.data[i].i,&a.data[i].j,&a.data[i].v); /*输入转置前的三元组 */
for(i=0;i<a.terms;i++)
printf("%d\t%d\t%d\n",a.data[i].i,a.data[i].j,a.data[i].v); /*输出转置前的三元组 */
fastrans(a); /*调用快速转置算法 */
}
该算法比按列转置多用了辅助向量空间 pot,但它的时间为四个单循环,故总的时间复杂度为 O(a.cols+a.terms),比按列转置算法效率要高 。
2,稀疏矩阵的相加运算当稀疏矩阵用三元组表进行相加时,有可能出现非零元素的位置变动,这时候,不宜采用三元组表作存储结构,而应该采用十字链表较方便 。
( 1) 十字链表的建立下面分两步讨论十字链表的建立算法:
第一步,建立表头的循环链表:
依次输入矩阵的行,列数和非零元素个数,m,n和 t。 由于行,列链表共享一组表头结点,因此,表头结点的个数应该是矩阵中行,列数中较大的一个 。 假设用 s 表示个数,即 s=max( m,n) 。 依次建立总表头结点 ( 由 hm
指针指向 ) 和 s个行,列表头结点,并使用 next域使 s+1个头结点组成一个循环链表,总表头结点的行,列域分别为稀疏矩阵的行,列数目,s个表头结点的行列域分别为 0。 并且开始时,每一个行,列链表均是一个空的循环链表,即 s个行,列表头结点中的行,列指针域 rptr和 cptr均指向头结点本身 。
第二步,生成表中结点:
依次输入 t个非零元素的三元组 ( i,j,v),生成一个结点,并将它插入到第 i
行链表和第 j列链表中的正确位置上,使第 i个行链表和第 j个列链表变成一个非空的循环链表 。
在十字链表的建立算法中,建表头结点,时间复杂度为 O(s),插入 t个非零元结点到相应的行,列链表的时间复杂度为 O( t*s),故算法的总的时间复杂度为 O(t*s)。
( 2) 用十字链表实现稀疏矩阵相加运算假设原来有两个稀疏矩阵 A和 B,如何实现运算 A=A+B呢? 假设原来 A
和 B都用十字链表作存储结构,现要求将 B中结点合并到 A中,合并后的结果有三种可能,1) 结果为 aij+bij; 2) aij( bij=0) ; 3) bij( aij=0)
。 由此可知当将 B加到 A中去时,对 A矩阵的十字链表来说,或者是改变结点的 v域值 ( aij+bij≠0),或者不变 ( bij=0),或者插入一个新结点 ( aij=0),还可能是删除一个结点 ( aij+bij=0) 。
于是整个运算过程可以从矩阵的第一行起逐行进行 。 对每一行都从行表头出发分别找到 A和 B在该行中的第一个非零元结点后开始比较,然后按上述四种不同情况分别处理之 。 若 pa和 pb分别指向 A和 B的十字链表中行值相同的两个结点,则 4种情况描述为:
1) pa->j=pb->j 且 pa->k.v+pb->k.v≠0,则只要将 aij+bij的值送到 pa所指结点的值域中即可,其他所有域的值都不变化 。
2) pa->j=pb->j且 pa->k.v+pb->k.v=0,则需要在 A矩阵的链表中删除 pa所指的结点 。 这时,需改变同一行中前一结点的 rptr域值,以及同一列中前一结点的 cptr域值 。
3) pa->j<pb->j且 pa->j≠0,则只要将 pa指针往右推进一步,并重新加以比较即可 。
4) pa->j>pb->j或 pa->j=0,则需在 A矩阵的链表中插入 pb所指结点 。
下面将对矩阵 B加到矩阵 A上面的操作过程大致描述如下,
设 ha和 hb分别为表示矩阵 A和 B的十字链表的总表头; ca和 cb分别为指向 A
和 B的行链表的表头结点,其初始状态为,ca=ha->k.next ; cb=hb-
>k.next;
pa和 pb分别为指向 A和 B的链表中结点的指针 。 开始时,pa=ca->rptr;
pb=cb->rptr;然后按下列步骤执行:
① 当 ca->i=0时,重复执行 ②,③,④ 步,否则,算法结束;
② 当 pb->j≠0时,重复执行 ③ 步,否则转第 ④ 步;
③ 比较两个结点的列序号,分三种情形:
a,若 pa->j<pb->j 且 pa->j≠0,则令 pa指向本行下一结点,即 qa=pa; pa=pa-
>rptr; 转 ② 步 ;
b,若 pa->j>pb->j或 pa->j=0,则需在 A中插入一个结点 。 假设新结点的地址为 P,则 A的行表中指针变化为,qa->rptr=p;p->rptr=pa;
同样,A的列表中指针也应作相应改变,用 hl[j]指向本列中上一个结点,则
A的列表中指针变化为,p->cptr=hl[j]->cptr; hl[j]->cptr=p;转第 ② 步;
c,若 pa->j=pb->j,则将 B的值加上去,即 pa->k.v=pa->k.v+bp->k.v,此时若
pa->k.v≠0,则指针不变,否则,删除 A中该结点,于是行表中指针变为:
qa->rptr=pa->rptr; 同时,为了改变列表中的指针,需要先找同列中上一个结点,用 hl[j]表示,然后令 hl[j]->cptr=pa->cptr,转第 ② 步 。
④ 一行中元素处理完毕后,按着处理下一行,指针变化为,ca=ca->k.next;
cb=cb->k.next;转第 1)步 。
5.5 广义表
5.5.1 基本概念广义表是第 2章提到的线性表的推广 。 线性表中的元素仅限于原子项,即不可以再分,而广义表中的元素既可以是原子项,也可以是子表 ( 另一个线性表 ) 。
1,广义表的定义广义表是 n≥0个元素 a1,a2,…,an的有限序列,其中每一个 ai或者是原子,或者是一个子表。广义表通常记为 LS=(a1,a2,…,a n),其中 LS为广义表的名字,n为广义表的长度,每一个 ai为广义表的元素。但在习惯中,一般用大写字母表示广义表
,小写字母表示原子。
2,广义表举例
( 1) A=( ),A为空表,长度为 0。
( 2) B=(a,( b,c) ),B是长度为 2的广义表,第一项为原子,第二项为子表 。
( 3) C=(x,y,z),C是长度为 3的广义表,每一项都是原子 。
( 4) D=(B,C),D是长度为 2的广义表,每一项都是上面提到的子表 。
( 5) E=(a,E),是长度为 2的广义表,第一项为原子,第二项为它本身 。
3,广义表的表示方法
( 1) 用 LS=(a1,a2,…,an)形式,其中每一个 ai为原子或广义表例如,A=(b,c)
B=(a,A)
E=(a,E)
都是广义表 。
( 2) 将广义表中所有子表写到原子形式,并利用圆括号嵌套例如,上面提到的广义表 A,B,C可以描述为:
A(b,c)
B(a,A(b,c))
E(a,E(a,E( … ) ))
( 3) 将广义表用树和图来描述上面提到的广义表 A,B,C的描述见图 5-11。
4,广义表的深度一个广义表的深度是指该广义表展开后所含括号的层数 。
例如,A=(b,c)的深度为 1,B=(A,d)的深度为 2,C=(f,B,h)的深度为 3;
.
( a) A=(b,c) ( b) B=(a,A) ( c) C=(A,B)
图 5-11 广义表用树或图来表示
BA
C
b ac
A
b c
B
a A
b c
5,广义表的分类
( 1) 线性表:元素全部是原子的广义表 。
( 2) 纯表:与树对应的广义表,见图 5-11的 (a)和 (b)

( 3) 再入表:与图对应的广义表 (允许结点共享 ),见图 5-11的 (c)。
( 4) 递归表:允许有递归关系的广义表,例如
E=(a,E)。
这四种表的关系满足:
递归表?再入表?纯表?线性表
5.5.2 存储结构由于广义表的元素类型不一定相同,因此,难以用顺序结构存储表中元素,通常采用链接存储方法来存储广义表中元素,并称之为广义链表 。 常见的表示方法
1,单链表表示法即模仿线性表的单链表结构,每个原子结点只有一个链域 link,结点结构是:
其中 atom是标志域,若为 0,则表示为子表,若为 1,则表示为原子,
data/slink域用来存放原子值或子表的指针,link存放下一个元素的地址 。
数据类型描述如下:
#define elemtype char
struct node1
{ int atom;
struct node1 *link;
union
{
struct node1 *slink;
elemtype data;
} ds;
a t o m d a t a / s l i n k l i n k
例如,设 L=(a,b)
A=(x,L)=(x,(a,b))
B=(A,y)=((x,(a,b)),y)
C=(A,B)=((x,(a,b)),((x,(a,b)),y))
可用如图 5-12的结构描述广义表 C,设头指针为 hc。
用此方法存储有两个缺点:其一,在某一个表 (或子表 )中开始处插入或删除一个结点,修改的指针较多,耗费大量时间;其二,删除一个子表后,它的空间不能很好地回收 。
hc
A B
A
L
1 y ^
0 ^
0 ^
0
0
1 x
1 a 1 b ^
图 5-12 广义表的单链表表示法
2,双链表表示法每个结点含有两个指针及一个数据域,每个结点的结构如下:
其中,link1指向该结点子表,link2指向该结点后继 。
数据类型描述如下:
struct node2
{ elemtype data;
struct node2 *link1,*link2;
}
例如,对图 5-12用单链表表示的广义表 C,可用如图 5-13所示的双链表方法表示

图 5-13 广义表的双链表表示法
l i n k 1 d a t a l i n k 2
hc
^ y ^
^ b ^
L ^
^ a
x
A
B ^A
5.5.3 基本运算广义表有许多运算,现仅介绍如下几种:
1,求广义表的深度 depth(LS)
假设广义表以刚才的单链表表示法作存储结构,则它的深度可以递归求出 。
即广义表的深度等于它的所有子表的最大深度加 1,设 dep表示任一子表的深度
,max表示所有子表中表的最大深度,则广义表的深度为,depth=max+1,算法描述如下:
int depth(struct node1 *LS)
{
int max=0,dep;
while(LS!=NULL)
{ if(LS->atom==0) //有子表
{ dep=depth(LS->ds.slink);
if(dep>max) max=dep;
}
LS=LS->link;
}
return max+1;
}
该算法的时间复杂度为 O(n)。
2,广义表的建立 creat(LS)
假设广义表以单链表的形式存储,广义表的元素类型 elemtype 为字符型 char,广义表由键盘输入,假定全部为字母,输入格式为:元素之间用逗号分隔,表元素的起止符号分别为左,右圆括号,空表在其圆括号内使用一个,#”字符表示,最后使用一个分号作为整个广义表的结束 。
本章小结
1,多维数组在计算机中有两种存放形式:行优先和列优先 。
2,行优先规则是左边下标变化最慢,右边下标变化最快,右边下标变化一遍,与之相邻的左边下标才变化一次 。
3,列优先规则是右边下标变化最慢,左边下标变化最快,左边下标变化一遍,与之相邻的右边下标才变化一次 。
4,对称矩阵关于主对角线对称 。 为节省存储单元,可以进行压缩存储,对角线以上的元素和对角线以下的元素可以共用存储单元,故 n?n
的对称矩阵只需 个存储单元即可 。
5,三角矩阵有上三角矩阵和下三角矩阵之分,为节省内存单元,可以采用压缩存储,n?n的三角矩阵进行压缩存储时,只需 +1个存储单元即可 。
6,稀疏矩阵的非零元排列无任何规律,为节省内存单元,进行压缩存储时,可以采用三元组表示方法,即存储非零元素的行号,列号和值 。 若干个非零元有若干个三元组,若干个三元组称为三元组表 。
7,广义表为线性表的推广,里面的元素可以为原子,也可以为子表
,故广义表的存储采用动态链表较方便 。
1,按行优先存储方式,写出三维数组 A[3][2][4]在内存中的排列顺序及地址计算公式 ( 假设每个数组元素占用 L个字节的内存单元,
a[0][0][0]的内存地址为 Loc(a[0][0][0])) 。
2,按列优先存储方式,写出三维数组 A[3][2][4]在内存中的排列顺序及地址计算公式 ( 假设每个数组元素占用 L个字节的内存单元,
a[0][0][0]的内存地址为 Loc(a[0][0][0])) 。,
3,设有上三角矩阵 An?n,它的下三角部分全为 0,将其上三角元素按行优先存储方式存入数组 B[m]中 (m足够大 ),使得 B[k]=a[i][j],且有
k=f1(i)+f2(j)+c。 试推出函数 f1,f2及常数 c( 要求 f1和 f2中不含常数项
) 。
4,若矩阵 Am?n中的某个元素 A[i][j]是第 i行中的最小值,同时又是第 j
列中的最大值,则称此元素为该矩阵中的一个马鞍点 。 假设以二维数组存储矩阵 Am?n,试编写求出矩阵中所有马鞍点的算法,并分析你的算法在最坏情况下的时间复杂度 。
5,试写一个算法,查找十字链表中某一非零元素 x。
习题五
6,给定矩阵 A如下,写出它的三元组表和十字链表 。
7,对上题的矩阵,画出它的带行指针的链表,并给出算法来建立它 。
8,试编写一个以三元组形式输出用十字链表表示的稀疏矩阵中非零元素及其下标的算法 。
9,给定一个稀疏矩阵如下:
用快速转置实现该稀疏矩阵的转置,写出转置前后的三元组表及开始的每一列第一个非零元的位置 pot[col]的值 。
1 0 0 0 0
0 0 2 3 0
A = 0 4 0 0 5
0 0 0 0 0
0 0 0 0 6
0860078065
99000000
0000400
008833061
0000000
2008500
00700230
09000011?
10,广义表是线性结构还是非线性结构?为什么?
11,求下列广义表的运算的结果
( 1) head((p,h,w))
( 2) tail ((b,k,p,h))
( 3) head(((a,b),(c,d)))
( 4) tail (((b),(c,d)))
( 5) head (tail(((a,b),(c,d))))
( 6) tail (head (((a,b),(c,d))))
( 7) head (tail (head(( (a,d),(c,d)))))
( 8) tail (head (tail (((a,b),(c,d)))))
12,画出下列广义表的图形表示
( 1) A(b,(A,a,C(A)),C(A))
( 2) D(A( ),B(e),C(a,L(b,c,d)))
13,画出第 12题的广义表的单链表表示法和双链表表示法 。