NOIP高中信息技术竞赛资料-数据结构

第1章绪论

程序设计就是运用计算机解决现实世界中的实际问题。对于给定的一个实际

问题，在进行程序设计时，首先要把实际问题中用到的信息抽象为能够用计算机

表示的数据；其次要把抽象出来的这些数据建立一个数据模型，这个数据模型也

称为逻辑结构，即建立数据的逻辑结构；第三要把逻辑结构中的数据及数据之间

的关系存放到计算机中，即建立数据的存储结构；最终在所建立的存储结构上实

现对数据元素的各种操作，即算法的实现。

本章就是要使大家了解计算机中的数据表示，理解数据元素、逻辑结构、存

储结构和算法的有关概念；驾驭基本逻辑结构和常用的存储方法，能够选择合适

的数据的逻辑结构和存储结构；驾驭算法及算法的五个重要特性，能够对算法进

行时间困难度分析，从而选择一个好的算法，为后面的学习打下良好的基础。

1.1基本概念和术语

1.数据（data）：

是对客观事物的符号的表示，是全部能输入到计算机中并被计算机程序处理

的符号的总瞥。

2.数据元素（dataelement）:

是数据的基本单位，在计算机程序中通常作为一个整体来处理。一个数据元素由

多个数据项（dataitem）组成，数据项是数据不行分割的最小单位。

3.数据结构（datastructure）:

是相互之间存在一种或多种特定关系的数据元素的集合。数据结构是一个二

元组，记为：

data_structure=（D,S）.其中D为数据元素的集合，S是D上关系的集合。

数据元素相互之间的关系称为结构（structure）。依据数据元素之间关系的不同特

性，通常由下列四类基本结构：

（1）集合:数据元素间的关系是同属一个集合。（图1）

（2）线性结构:数据元素间存在一对一的关系。（图2）

（3）树形结构：结构中的元素间的关系是一对多的关系。（图3）

（4）图（网）状结构：结构中的元素间的关系是多对多的关系。（图4）

集合

°O线性

OO

O

OCWWWWW)

图1图2

树图

图3图4

1.2数据的逻辑结构和物理结构

1.逻辑结构：数据元素之间存在的关系(逻辑关系)叫数据的逻辑结构。即

上面给出的四种结构。

2.物理结构：数据结构在计算机中的表示(映象)叫数据的物理结构，又称

存储结构。

一种逻辑结构可映象成不同的存储结构：依次存储结构和非依次存储结构

(链式存储结构和散列结构)。

1.3算法及算法分析

1.算法：是对特定问题求解步骤的一种描述，是指令的有限序列。一个算

法是一系列将输入转换为输出的计算步骤。

2.算法的重要特性

①输入：一个算法应当有零个或多个输入。

②有穷性:一个算法必需在执行有穷步骤后正常结束，而不能形成无穷循环。

③确定性：算法中的每一条指令必需有精确的含义，不能产生多义性。

④可行性：算法中的每一条指令必需是切实可执行的，即原则上可以通过已

经实现的基本运算执行有限次来实现。

⑤输出：一个算法应当有一个或多个输出，这些输出是同输入有某个特定关

系的量。

3.算法的时间困难度

①定义：设问题的规模为n,把一个算法的时间耗费T(n)称为该算法的时间

困难度，它是问题规模为n的函数。

②算法的渐进时间困难度

设T(n)为一个算法的时间困难度，假如当n趋向无穷大时T(n)与函数_/(n)的

比值的极限是一个非零常数M,即记作T(n)=O(/(n)),则称0(/(n))为算法的渐进

时间困难度，简称时间困难度，也称T(n)与.*n)的数量级相同，通常，/(n)应当

是算法中频度最大的语句的频度。

③常用的算法的时间困难度的依次

O(l)<O(lgn)<O(n)<O(n•lgn)<O(n2)<O(n3)<...<0(2n)

④算法的时间困难度不仅仅依靠于问题的规模，还与输入实例的初始状态有

关。

例如：在数组中查找给定值K的算法如下：

(l)i=n-l;

(2)while(i>=0&&(A[i]!=k))

(3)i-;

(4)returni;

此算法中的语句(3)的频度不仅与问题规模n有关，还与输入实例中A的各

元素取值及K的取值有关：

若A中没有与K相等的元素，则语句(3)的频度/(n)=n；

若A的最终一个元素等于K,则语句⑶的频度.*n)是常数Oo

⑤最坏时间困难度和平均时间困难度

最坏状况下的时间困难度称为最坏时间困难度。一般不特殊说明，探讨的时

间困难度均是最坏状况下的时间困难度。

这样做的缘由是：最坏状况下的时间困难度是算法在任何输入实例上运行时

间的上界，这就保证了算法的运行时间不会比任何状况下更长。

平均时间困难度是指全部可能的输入实例均以等概率出现的状况下，算法的

期望运行时间。

例1求下列交换两个变量i和j的值的算法的时间困难度。

(1)i=10;

(2)j=20;

(3)t=i;

(4)i=j;

(5)j=t;

解：各行语句的执行次数均为1,所以该算法的时间耗费T(n)=l+1+1+1+1=5,该算法

的时间耗费T(n)与问题的规模n无关，因此，该算法的时间困难度T(n)=O(l)。

例2求两个n阶方阵的乘积C=AXB,其算法如下，计算该时间困难度。

程序段：

(1)for(i=0;i<n;i++)

(2)for(j=0;j<n;j++)

⑶{c[i][j]=O;

(4)for(k=0;k<n;k++)

(5)c[i]U]+=a[i][k]*b[k]U];

I

解：解法1

计算程序段中的每一行的执行次数。

第(1)行for(i=0;i<n;i++)中只考虑循环条件表达式i<n的执行次数(忽视初

始化表达式i=0和修正表达式i++的执行次数，下同)，表达式i<n共执行n+1

次(i为0到n-1时该表达式非零，共n次，i为n时该表达式为零，共1次，合

计执行n+1次)，所以，第⑴行共执行n+1次；

第(2)行for(j=0;j<n;j++),在第(1)行for(i=0;i<n;i++)中的表达式i<n非零时

(共n次)都要执行一遍，而每一遍同样要执行n+1次，所以，第⑵行共执行n

(n+1)次；

第⑶行c[i][j]=O;在表达式i<n和j<n均非零时执行，共执行n2次；

第(4)行for(k=0;k<n;k++)在表达式i<n和j<n均非零时执行一遍，而每一遍

同样要执行n+1次，所以，第⑷行共执行I?(n+1)次；

第(5)行疝[j]+=a皿k]*b[k][j];在表达式i<n、j<n和k<n均非零时执行，共

执行「次；

因此，各行执行次数分别为：n+1,n(n+1),n2,n2(n+1),n\

假如用T(n)表示该算法的时间耗费，则

T(n)=n+l+n(n+1)+n2+n2(n+1)+n3=2n'+3n2+2n+1

由此可知，该算法的时间耗费T(n)是矩阵阶数n的函数，T(n)=0(n3)。

解法2

只计算执行频度最高的行。

明显，在该程序段中，执行频度最高的行为c[iHj]+=a[i][k]*b[k][j];在表达

式i<n、j<n和k<n均非零时执行,而表达式i<n、j<n和k<n均有n次非零，所

以，该行共执行「次。因此，该算法的时间耗费T(n)是矩阵阶数n的函数，

T(n)=O(n3)o

【课堂实践】分析并计算下面程序段执行的时间困难度。

i=l;k=O;

while(i<=n-l)

(k+=10*i;

i++；

第2章线性表

线性表是最常用且最简洁的一种数据结构，一个线性表是n个数据元素的有

序系列，每个数据元素可以是一个数或一个符号，也可以使一页书，甚至其他更

困难的信息。如26个字母的字母表：(A,B,C,D..…,Z)在困难的线性表中，一个

数据元素可以由若干个数据项组成，在这种状况下，常把数据元素称为一个记录,

含有大量记录的线性表又称文件。如图

姓名学号性纲年M班级1笈康状区

王小林79063]男)8计91健康

陈红790632女20计91

曲建平790633男21计91拉采

张立立790634男17计91府经衰裂

IS2.1学生健康情况登记表

综合上述例子，可以将线性表描述为：

线性表是由n个数据元素的有限序列⑶,a、..,an)组成的，其中每一个数据元

素ai的具体含义可以按不同的状况和要求定义具体的内容，它可以是一个数、一

个符号、一串文字，甚至是其他更困难的信息。线性表中数据元素的个数n称为

线性表的长度。

2.1线性表的逻辑结构及基本运算

1.线性表简洁的定义

n个数据元素的有限序列其特点是除了表头和表尾外，表中的每一个元素有

且仅有唯一的前驱和唯一的后继，表头有且只有一个后继，表尾有且只有一个前

驱。线性表中的数据元素不仅可以进行访问，还可进行插入和删除。

若n=0,则表示一个空表，即没有任何数据元素的线性表；若n〉0,则除ai

和an外，有且仅有一个干脆前驱和一个干脆后继，即ai(其中l<i<n)是线性表中第

i个数据元素,在ai之前仅有一个数据元素M,而在&之后也仅有一个数据元素ai+io

称ai称为起始结点，an称为终端结点，i称为ai在线性表中的序号或位置。线性表

中结点的之间的关系就是上述的邻接关系，由于该关系是线性的，我们称线性表

是一种线性结构。

2.线性表的基本运算

(1)线性表初始化

格式:InitList(L)

初始条件：线性表L不存在。

操作结果：构造一个空的线性表L。

(2)求线性表的长度

格式:LengthList(L)

初始条件：线性表L存在。

操作结果：返回线性表L中全部元素的个数。

(3)取表元

格式：GetList(L,i)

初始条件：线性表L存在，且iWiWLengthList(L)。

操作结果：返回线性表L的第i个元素(ai)的值。

(4)按值查找

格式:LocateList(L,x)

初始条件：线性表L存在，x有确定的值。

操作结果：在线性表L中查找值为x的数据元素，并返回该元素在L中的位置。

若L中有多个元素的值与x相同，则返回首次找到的元素的位置；若L中没有值为

x的数据元素，返回一个特殊值(通常为-1)表示查找失败。

(5)插入操作

格式：InsertList(L,i,x)

初始条件：线性表L存在，i为插入位置(lWiWn+1,n为插入前的表长)。

操作结果：在线性表L的第i个元素(方)位置上插入值为x的新元素，原序号为

i,i+l,...,n的数据元素的序号插入后变为i+l,i+2,…,n+1,插入后表长=原表长+1。

(6)删除操作

格式：DeleteList(L,i)

初始条件：线性表L存在，i(iWiWn)为给定的待删除元素的位置值。

操作结果：在线性表L中删除序号为i的数据元素⑶)，删除后，原序号为

i+l,i+2,…,n的数据元素的序号变为i,i+l,删除后表长=原表长-1。

注：以上给出的是线性表的基本运算，并不是全部运算，其它运算可用这些

基本运算来实现，这些运算都是定义在逻辑结构层次上的运算，只有确定了存储

结构之后，才能具体实现这些运算。

例1假设两个线性表LA,LB分别代表两个集合A和B:求A=AUB

voidunion(List&La,List&Lb){

〃将全部在线性表Lb中，但不在La中的数插入到La中

La.len=ListLength(La);

Lb.len=ListLength(Lb);〃求两表的长度

for(i=l;i<=Lb.len;i++)

GetElem(Lb,i,e);〃取Lb中第i个的元素复制给e

If(!LocateElem(La,e,equal))

ListInsert(La,++La.Icn,e);〃若其中不存在相同的，则插入

}//union

例2已知线性表la,1b中的数据元素按值非递减有序排列，现要求将la,1b

归并为一个新的线性表1c且1c按值非递减。

例如la=(3,5,8,11),

Lb=(2,6,8,9,ll,15,20)

则lc=(2,3,5,6,8,8,9,l1,11,15,20)

分析：由于两表都是依据确定依次进行排列，全部设置2个指针，分别指向

a、b表，先分别比较比较最初指向的两数据，比较一下大小，谁小就放入到c

表中，然后数小的指针向下移动，再进行比较。直到2表有一表结束，再将剩余的

表存放到c中。

VoidMergeList(ListLa,ListLb,List&Lc){

〃已知线性表la和lb中的数据元素

InitList(Lc);〃初始化表c

Inti=j=l;k=0;

La.1en=UstLength(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++；

}〃if结束

}〃whie结束，其中-一表结束;

While(i〈=La.len){〃表B数据全访问完,表a未到最终

GetElem(La,i++,ai);

Listinsert(Lc,++k,ai);

)

While(j<=Lb.len){〃表a数据全访问完,表b未到最终

GetElem(Lb,j++,bj);

Listinsert(Lc,++k,bj);

)

”/程序结束

分析：上述2个算法的时间困难度(基本操作的执行时间)，例1为

O(ListLength(La)*ListLength(Lb)),例2的时间困难度为

O(ListLength(La)+ListLength(Lb))o

2.2线性表的依次存储结构

线性表的依次存储即用一组地址连续的存储单元依次存储线性表中的元

素。设线性表中每个元素需占用r个存储单元则

loc(ai+i)=loc(ai)+r

loc(ai)=loc(ai)+(i-1)*r

线性表的这种机内表示称做线性表的依次存储结构或依次映像，通常，称这

种存储结构的线性表为依次表。只要确定了存储线性表的起始位置，线性表中任

一数据元素可随机存储，所以线性表的依次结构是一种随机存储的存储结构。

.的优番如端*在切//======线性表的动态依次存储结构

内存状态数据元If在9

表中的位序

^defineL[ST_INIT_SIZE100//初始支配量

itdefineLISTINCREMENT10〃支配增量

Typedefstruct{

(•-1>/Elemtype*elem;〃存储空间基址

length;〃当前长度

4+(.-l)Zlistsize;〃当前支配的存储容量

b+U

}SqList；

b4-(max)en-1)Z

Elem表示基地址，length指示线性表的

困线性表的顺序存储结构示意图

2.2当前长度。上述的含义是为依次表支配一个

预定义大小的数据空间，并将当前的长度设为0；

StatusInitList_sq(SqList&L){

〃==创建一个空的线性表

L.e1em=(ElemType*)ma1loc(LIST_INIT_SIZE*sizeof(ElemType));//ElemType指数据类型,malloc

新支配空间

If(!L.elem)exit(OVERFLOW);〃存储支配失败

Llength：。;〃空表长度为0

L.listsize=LIST_INIT_SIZE;〃初始存储容量

Returnok；

}//InitList_sq

在这种存储方式下，简洁实现对表的遍历。要在表的尾部插入一个新元素，

也很简洁。但是要在表的中间位置插入一个新元素，就必需先将其后面的全部元

素都后移一个单元，才能腾出新元素所需的位置。

StatusListlnsert_sq(SqUst&L,intI,ElemTypee)(

〃在依次表中插入一个新元素e

If(i<l||i>L.length+1)returnError;

If(L.length>=L.listsize){〃当前存储空间已满，增加支配

Newbase=(ElemType*)realloc(L.elem,(LIST_INIT_SIZE+LISTINCREMENT)*sizeof(ElemType));//

ElemType指数据类型，realloc再次支配，L.elem存储基地址

}//if

q二&(L.elem[i-l]);//q为插入位置

for(p=&(L.elem[Llength-1]);p>=q;--p){

*(p+l)=*q;

}//for

*q=e;〃插入e

++L.length；

Returnok；

)

执行删除运算的情形类似。假如被删除的元素不是表中最终一个元素，则必

需将它后面的全部元素前移一个位置，以填补由于删除所造成的空缺。这两种运

算的时间困难度均为O(n)n为表的长度。

StatusListDelete_sq(SqList&L,intI,ElemType&e){

〃在依次表中插入一个新元素e

If(i<l||i>L.length+1)returnError;

p=也(L.elem[i-l]);//p为删除位置

q=L.elem+L.length-1;

for(++p;p<=q;++p){

*(p-l)=*p;

}//for

一L.length；

Returnok；

2.3线性表的链式存储结构

线性表依次结构的特点是逻辑关系上相邻的两个元素在物理位置上也相邻，因此可以随

机存储表中的任一元素，但是在插入删除时须移动大量元素。而线性表的链式存储由于其不

要求逻辑上相邻，因此它没有依次存储结构的弱点，但同时也失去了依次表可随机存取的优

点。

1.单链表

线性链表的特点是用一组随意的存储单元存储线性表的元素，用指针将存储

表元素的那些单元依次串联在一起。这种方法避开了在数组中用连续的单元存储

元素的缺点，因而在执行插入或删除运算时，不再须要移动元素来腾出空间或填

补空缺。然而我们为此付出的代价是，须要在每个单元中设置指针来表示表中元

素之间的逻辑关系，因而增加了额外的存储空间的开销。

为了将存储表元素的全部单元用指针串联起来，我们让每个单元包含一个元

素域和一个指针域如图所示：

........-।-----------其中，存储单元由两部分构成，即数据域存

数据域指针域储数据元素，指针域存储下一个元素所在的单元

假如表是ai,a2,...,an,那么含有元素小的那个单元中的指针应指向含有元素

ai+i的单元(i=l,2,…,n-1)。含有an的那个单元中的指针是空指针null。此夕卜,通常

我们还为每一个表设置一个表头单元header,其中的指针指向起先元素中所在的

单元，但表头单元header中不含任何元素。设置表头单元的目的是为了使表运

算中的一些边界条件更简洁处理。这一点我们在后面可以看到。假如我们情愿单

独地处理诸如在表的第一个位置上进行插人与删除操作等边界状况，也可以简洁

地用一个指向表的第一个单元的指针来代替表头单元。

上述这种用指针来表示表的结构通常称为单链接表，或简称为单链表或链

表。单链表的逻辑结构如图1所示。表示空表的单链表只有一个单元，即表头单

元header,其中的指针是空指针null。

header

表

图1单链表示意图

为了便于实现表的各种运算，在单链表中位置变量的意义与用数组实现的表

不同。在单链表中位置i是一个指针，它所指向的单元是元素a“所在的单元，

而不是元素ai所在的单元(i=2,3,…,n)。位置1是指向表头单元header的指针。位

置End(L)是指向单链表L中最终一个单元的指针。这样做的目的是为了避开在

修改单链表指针时须要找一个元素的前驱元素的麻烦，因为在单链表中只设置指

向后继元素的指针，而没有设置指向前驱元素的指针。

单链表存储结构

TypedefstructLnode{

ElemTypedata;

StructLnode"next;〃指向后继节点的指针

ILnode,*LinkList;〃线性链表的实质就是指针

基本运算

(1)ListInsert.L(L,i,e)

功能:在表L的位置p处插入元素x,并将原来占据位置p的元素及其后面

的元素都向后推移一个位置。例如,设L为al,a2,…,an,那么在执行Insert(x,p)

后,表L变为al,a2,…ap-l,x,ap,…,an。若p为End(L),那么表L变为

al,a2,...,an,x。若表L中没有彳立置p,则该运算无定义。

实现P为指向a节点的指针，s为指向X节点的指针:s->next=p->next;

p->next=s;

StatusListInsert-L(LinkLidt&L,int1,ElemTypee){

//在带头结点的单链线性表L中第i个位置之前插入元素e

p-Lij«0»

•Ail.(p&&.j<i-1){p-p->next,++j；>〃寻找第i-1个结点

if(fpl；j.11)returnERROR»〃i小于1或者大于表长加1

3—(LinkList)malloc(sizeof(IJlode))}〃生成新结点

a-je；snext-p—>next；〃捕入L中

p->nextst

returnOK；

}//ListInsertL

上述算法中，链表指针的修改状况见图2

temp

r->b

j4rpq…J

图2(a)是执行Insert运算之前的状况。我们要在指针p所指的单元之后插入

一个新元素X。图2(b)是执行Insert运算以后的结果，其中的虚线表示新的指针。

在上述Insert算法中，位置变量p指向单链表中一个合法位置，要插入的新元素

x应紧接在p所指单元的后面。指针p的合法性应在执行Insert运算之前判定。

往一个单链表中插入新元素通常在表头或表尾进行，因此p的合法性简洁判定。

Insert运算所需的时间明显为。(1)。

(2)Delete(p)

功能:从表L中删除位置p的下一元素。例如,当L为ai,a2,…,an时,执行

Delete(p)后，L变为ai,a2,...,ap-i,ap+i,…,an。当L中没有位置p或p=End(L)时，

该运算无定义。实现:p.next=p.next.next;

这个过程很简洁，其指针的修改如图3所示。

p

若要从一个表中删除一个元素X,但不知道它在表中的位置，则应先用

Locate(x,L)找出指示要删除的元素的位置，然后再用Delete删除该位置指示的元

素。Delete过程所需的时间明显也为。(1)。

2.静态链表

静态链表：用游标指示数组单元地址的下标值，它属整数类型数组元素是记

录类型，记录中包含一个表元素和一个作为游标的整数；具体说明如下：

typejid=record

data:datatype;

next:integer;

end;

varalist=array[O..maxsize]ofjid

游标即我们可以用游标来模拟指针，对于一个表L,我们用一个整型变量

Lhead(如Lhead=0)作为L的表头游标。。这样，我们就可以用游标来模拟指针，

实现单链表中的各种运算。当i>l时，表示第i个位置的位置变量p的值是数组

alist中存储表L的第i-1个元素next值，用p:=alist(p).next后移。照此，我们虽然

是用数组来存储表中的元素，但在作表的插人和删除运算时，不须要移动元素，

只要修改游标，从而保持了用指针实现表的优点。因此，有时也将这种用游标实

现的表称为静态链表。

3.循环链表

循环链表是另一种链式存储结构，特点是表中最终一个结点的指针域指向头

结点，整个链表形成一个环。因此，可由表中任一结点动身均可找到表中其他结

点。如图6所示的是一个单链的循环链表或简称为单循环链表。

(a)1

非空表

(b)

空表

图6单循环链表

在单循环链表上实现表的各种运算的算法与单链表的情形是类似的。它们仅

在循环终止条件上有所不同:前者是p或p'next指向表头单元;后者是p或pAnext

指向空(nil)。在单链表中我们用指向表头单元的指针表示一个表L,这样就可以

在。(1)时间内找到表L中的第一个元素。然而要找到表L中最终一个元素就要

花Q(n)时间遍历整个链表。在单循环链表中，我们也可以用指向表头单元的指

针展示一个表L。但是，假如我们用指向表尾的指针表示一个表L时，我们就可

以在0(1)时间内找到表上中最终一个元素。同时通过表尾单元中指向表头单元

的指针，我们也可以在。(1)时间内找到表L中的第一个元素。在许多状况下，

用这种表示方法可以简化一些关于表的运算。

4.双链表

单循环链表中，只有一个指示干脆后继的指针域，虽然从任一单元动身，可

以找到其前驱单元，但须要0(n)时间。假如我们希望能快速确定表中任一元素

的前驱和后继元素所在的单元，可以在链表的每个单元中设置两个指针，一个指

向后继，另一个指向前驱，形成图8所示的双向链表或简称为双链表。

图8双链表

由于在双链表中可以干脆确定一个单元的前驱单元和后继单元，我们可以用

一种更自然的方式表示元素的位置，即用指向双链表中第i个单元而不是指向其

前一个单元的指针来表示表的第i个位置。

双链表的单元类型定义如下。

〃---------线性袤的双向鞋表存储结构

typedefstructDuLNode{

EleaTypedata)

structIXiLNode*priori

structDuLNode«next；

}DuLNode,♦DuLinkList；

和单链的循环表类似，双链表也可以有相应的循环表。我们用一个表头单元

将双链表首尾相接，即将表头单元中的previous指针指向表尾，并将表尾单元的

next指针指向表头单元，构成如图9所示的双向循环链表。

图9双向循环链表

下面仅以双向循环链表为例给出三种基本运算的实现。

⑴在双向循环链表L的位置p处插入一个新元素x的过程Insert可实现如下。

StatusListinsertDuL(DuLinkList&L,inti,ElemTypee){

H在带头结点的双链循环线性表L中第i个位置之前插入元京。，

Hi的办法值为表长+L

if(!(p-GetElemPDuL(L.i)))〃在L中确定插入位置

returnEBROR；〃p=NULL,即插入位置不合法

if(!(s=(DuLinkList)malloc(sizeof(DuLNode)))>returnERRORj

s->data,

s->>prior=p->>prior«p->prior-next.S)

c-<>next=pip-sprier「si

returnOK；

}HListInsert.DuL

上述算法对链表指针的修改状况见图10。

图10在双向循环链表中插入一个元素

算法Insert中没有检查位置p的合法性，因此在调用Insert之前应保证位置

p的合法性。由于插入通常是在表的头尾两端进行的，所以简洁检查位置p的合

法性。

(2)从双向循环链表L中删除位置p处的元素可实现如下：

StatusListDelete.DuL(DuLinkList&L,iniEleroType&e){

//删除带头结点的双链循环战性表L的第i个元素，i的合法值为IWi《表长

if(I(p工GetEleaP-DuL(L,i)))〃在L中确定第i个元素的位置指针p

returnERROR।〃NULL,即第1个元素不存在

e=p->data?

p->prior->next=p->next»

D->next->>prior■p->prior»

frw(p)।return0K|

)HListDelete.DuL

上述算法对链表指针的修改状况见图11o

图11从双向循环链表中删除一个元素

5.链表的应用

例1：求(A-B)U(B-A)其中A,B代表两个集合(用静态链表)

例2求pl(x)+p2(x)(两个多项式的和)

练习题：

1.约瑟夫问题：

有M个猴子围成一圈，每个有一个编号，编号从1到M。打算从中选出一个

大王。经过协商，确定选大王的规则如下：从第一个起先，每隔N个，数到的

猴子出圈，最终剩下来的就是大王。

要求：从键盘输入M,N,编程计算哪一个编号的猴子成为大王。(程序)

2.求多项式的减与乘法.(程序)

第3章栈

栈是一种特殊的线性表，它的逻辑结构与线性表相同，只是其运算规则较线

性表有更多的限制，故又称它为运算受限的线性表。

3.1栈的概念及运算

栈(Stack)是限制仅在表的一端进行插入和删除运算的线性表。向栈中插

入元素称为进(入)栈，从栈中删除元素称为退(出)栈。

通常插入、删除的这一端称为栈顶，由于元素的进栈和退栈，使得栈顶的位

置经常是变动的，因此须要用一个整型量Top指示栈顶的位置，通常称Top为

栈顶指针；另一端称为栈底。

当表中没有元素时称为空栈，即Top=-1。

栈的修改是按后进先出的原则进行。每次删除的总是当前栈中“最新”的元

素，即最终插入的元素，而最先插入的是被放在栈的底部，要到最终才能删除。。

假设一个栈S中的元素为an,an」,..,ai,则称ai为栈底元素，an为栈顶元素。

栈中的元素按al,a2,..,an-i,an的次序进栈。在任何时候，出栈的元素都是栈顶元素。

换句话说，栈的修改是按后进先出的原则进行的，如图1所示。因此，栈又称为

后进先出(LastInFirstOut)表，简称为LIFO表。所以，只要问题满意LIFO原

则，就可以运用栈。

图1

栈的运算：为一种抽象数据类型，常用的栈运算有：

运算含义

inistack(S)使S成为一个空栈。

getTop(S)这是一个函数，函数值为S中的栈顶元素。

Pop(S)从栈S中删除栈顶元素，简称为抛栈。

Push(S,x)在S的栈顶插入元素x,简称为将元素x入栈。

c,8这是一个函数。当S为空栈时，函数值为true,

Empty。)否则函数值为false。

3.2栈的存储与实现

1.依次栈及基本操作的实现

由于栈是运算受限线性表，因此线性表的存储结构对栈也适用，而线性表有

依次存储和链式存储两种，所以，栈也有依次存储和链式存储两种。

(1)依次栈：栈的依次存储结构简称为依次栈，它是运算受限的依次表。

(2)依次栈的描述

#defineStackSize100〃假定栈空间最多为100个元素

typedefcharDataType;//假定栈元素的类型为字符类型

typedefstruct{

DataTypedata|StackSize];〃栈元素定义

inttop;〃栈指针定义

JSeqStack;

SeqStack*S;〃定义栈S

设S是SeqStack类型的指针变量，则栈顶指针可表示为S->top；若栈底位

置在向量的低端，则S->data⑼是栈底元素，栈顶元素可表示为S-〉data[S->top]。

留意：

①有元素x进栈时，须要先将S->top加1,然后再将元素进栈，即依次完成

下列操作：++S->top;S->data[S->top]=x;o

②当栈顶元素做退栈操作后，须要将S->top减1,即完成操作：S->top-；o

③条件S->top==StackSize-l表示栈满；S->top==-1表示栈空。

④当栈满时，再做进栈运算所产生的空间溢出现象称为上溢。上溢是一种出

错状态，应设法避开。

⑤当栈空时，做退栈运算所产生的溢出现象称为下溢。

3、依次栈上基本运算的算法

①置栈空

voidInitStack(SeqStack*S){〃将依次栈置空

S->top=-1;

}

②判栈空

假如栈S为空，则S->top==-l,此时应当返回1,而关系表达式S->top==-l

的值为1;假如栈S为非空，则S->top!=-l,此时应当返回0,而关系表达式

S->top==-l的值为0,因此，无论怎样只需返回S->top==-l的值。

intStackEmpty(SeqStack*S){

returnS->top==-l;

)

③判栈满

与判栈空的道理相同，只需返回S->top==StackSize-lo

intStackFull(SeqStack*S){

returnS->top==StackSize-1;

1

④进栈

进栈操作须要将栈和进栈元素的值作为函数参数，由于运用栈指针作为函数

参数，对栈进行操作，所以进栈函数不须要有返回值；进栈操作时，须要推断是

否栈满，当栈不满时，先将栈顶指针加1,再进栈。

intPush(SeqStack*S,DataTypex){

if(StackFull(S))

{puts("栈满)return0;)

S->data[++S->top]=x;〃栈顶指针加1后将x入栈

return1;

}

⑤退栈

退栈操作须要将栈指针作为函数参数，并返回栈顶元素的值，所以函数返回

值的类型为DataType；退栈操作时，须要推断是否栈空，当栈不空时，先退栈，

再将栈顶指针减1,可以先将栈顶元素的值记录下来，然后栈顶指针减1,最终

返回记录下来的值，也可以像给出的退栈函数那样来操作。

DataTypePop(SeqStack*S)(

if(StackEmpty(S))

{puts("栈空");return0;)

returnS->data[S->top--];〃返回栈顶元素并将栈顶指针减1

)

⑥取栈顶元素

取栈顶元素与退栈的区分在于，退栈须要变更栈的状态，而取栈顶元素不须

要变更栈的状态。

DataTypeStackTop(SeqStack*S){

if(StackEmpty(S))

{puts("栈空)return0;)

returnS->data[S->top];

I

由于栈的插入和删除操作具有它的特殊性，所以用依次存储结构表示的栈并

不存在插入删除数据元素时须要移动的问题，但栈容量难以扩充的弱点仍就没有

摆脱。

例元素al,a2,a3,a4依次进入依次栈，则下列不行能的出栈序列是

A.a4,a3,a2,alB.a3,a2,a4,al

C.a3,a4,a2,alD.a3,al,a4,a2

分析：对于A,由于元素al,a2,a3,a4依次进栈，而a4先出栈，说明al,

a2,a3已经入栈，所以出栈依次只能是a4,a3,a2,al,因此A是正确的出栈

序列；对于B,C,D,由于都是a3先出栈，说明al,a2已经入栈，所以al,

a2的相对位置确定是不变的,这就是a2确定在al之前出栈，比较上述三个答案,

只有D中的al出现在a2的前面，这明显是错误的。因此，答案为D。

2.链栈及基本操作的实现

若栈中元素的数目变更范围较大或不清楚栈元素的数目，就应当考虑运用链

式存储结构。用链式存储结构表示的栈称作“链栈”。链栈通常用一个无头结点

的单链表表示。

由于栈的插入删除操作只能在一端进行，而对于单链表来说，在首端插入删

除结点要比尾端相对地简洁一些，所以，我们将单链表的首端作为栈顶端，即将

单链表的头指针作为栈顶指针。链栈如图3.2。

top

栈顶栈底

图3.2链栈

(1)链栈：栈的链式存储结构称为链栈，它是运算受限的单链表，其插入

和删除操作仅限制在表头位置上进行，栈顶指针就是链表的头指针。

(2)链栈的描述

typedefcharDataType;〃假定栈元素的类型为字符类型

typcdefstructstacknodc{〃结点的描述

DataTypedata;

structstacknode*next;

JStackNode;

typedefstruct{〃栈的描述

StackNode*top;〃栈顶指针

)LinkStack;

LinkStack*S;〃定义指向链栈的指针S

设S是Linkstack类型的指针变量，则S是指向链栈的指针，链栈栈顶指针

可表示为S->top；链栈栈顶元素可表示为S->top->data0

设p是StackNode类型的指针变量，则p是指向链栈某结点的指针，该结点

的数据域可表示为p->data,该结点的指针域可表示为p->next。

留意：

①LinkStack结构类型的定义是为了便利在函数体中修改top指针本身。

②若要记录栈中元素个数，可将元素个数属性作为LinkStack类型中的成员

定义。

③条件S->top==NULL表示空栈，链栈没有栈满的状况。

3、链栈上基本运算的算法

①置栈空

voidInitStack(LinkStack*S){〃将链栈置空

S->top=NULL;

)

②判栈空

intStackEmpty(LinkStack*S){

returnS->top==NULL;

)

③进栈

voidPush(LinkStack*S,DataTypex){〃将元素x插入链栈头部

StackNode*p=(StackNode*)malloc(sizeof(StackNode));

p->data=x;

p->next二S->top;〃将新结点*p插入链栈头部

S-xop二p;〃栈顶指针指向新结点

)

④退栈

DataTypePop(LinkStack*S){

DataTypex;

StackNode*p=S->top;〃保存栈顶指针

if(StackEmpty(S))

{puts(“栈空”)；return0;}〃下溢，退出运行

x=p->data;〃保存栈顶结点数据

S->top=p->next;〃将栈顶结点从链上摘下

free(p);

returnx;

}

⑤取栈顶元素

DataTypeStackTop(LinkStack*S){

if(StackEmpty(S))

{puts(“栈空”'return0;}

returnS->top->data;

)

注：由于链栈中的结点是动态支配的，可以不考虑上溢，所以无须定义

StackFull运算。

3.3栈的应用

1.数值转换

十进制整数N向其它进制数d(二、八、十六)的转换是计算机实现计算的基

本问题。

转换法则：该转换法则对应于一个简洁算法原理:n=(ndivd)*d+nmodd

其中：div为整除运算,mod为求余运算

例如(1348)10=(2504)8,其运算过程如下：

nndiv8nmod8

13481684

168210

2125

202

接受静态依次栈方式实现

voidconversion(intn,intd){/*将十进制整数N转换为d(2或8)进制数*/

SqStackS;intk,*e;

S=Init_Stack();

while(n>0){k=n%d;push(S,k);n=n/d;

)/*求出全部的余数，进栈*/

while(S.top!=0){/*栈不空时出栈，输出*/

pop(S,e);

prints%Id",*e);

)

2.表达式的求值

问题:能否设计算法，编制一个程序，让计算机扫描如下表达式，并将其值

打印出来。

#3*(4+8)/2-5#

注：给表达式设置#，标记扫描的起先和结束。

这个表达式的计算依次是：3*(4+8)/2-5=3*12/2-5=36/2-5=18-5=13

任何一个表达式都是由操作数、运算符和界位符组成的，操作数可以使一些

常数也可以使一些变量或是常量的标示符，运算符则分为算数运算符、关系运算

符和逻辑运算符；基本界位符有左右括号和表达式结束。一般将运算符和界位符

看做是界符。

表3.1算符间的优先关系

+一#/()

+>><<<>>

—>><<<>>

*>>>><>>

/>>>><>>

(<<<<

)>>>>>

#<<S'♦<<ae

提示算法：为实现算符优先算法，可以实现2个工作栈，一个是操作数栈

opnd,用来存放操作数，如3、4、8等，另一个是运算符栈optr,用来存放运算

符。

首先将标记进运算符栈的栈底。

然后依次扫描，依据栈的