《数据结构(C语言描述)》(王路群 主编)第三章课件

第三章通常称，栈和队列是限定插入和删除只能在表的“端点”进行的线性表。线性表栈队列Insert(L,

i,x)Insert(S,n+1,x)Insert(Q,n+1,x)

1≤i≤n+1Delete(L,i)Delete(S,n)Delete(Q,1)

1≤i≤n栈和队列是两种常用的数据类型3.1栈的类型定义3.2栈的应用举例3.3栈类型的实现3.4队列的类型定义3.5队列类型的实现InitStack(&S)DestroyStack(&S)ClearStack(&S)StackEmpty(s)StackLength(S)GetTop(S,&e)Push(&S,e)Pop(&S,&e)StackTravers(S,visit())

InitStack(&S)

操作结果：构造一个空栈S。

DestroyStack(&S)

初始条件：栈S已存在。

操作结果：栈S被销毁。

StackEmpty(S)

初始条件：栈S已存在。

操作结果：若栈S为空栈，则返回TRUE，否则FALE。

StackLength(S)

初始条件：栈S已存在。

操作结果：返回S的元素个数，即栈的长度。ClearStack(&S)

初始条件：栈S已存在。

操作结果：将S清为空栈。Pop(&S,&e)

初始条件：栈S已存在且非空。

操作结果：删除S的栈顶元素，并用e返回其值。a1a2anan-1

……例一、数制转换

算法基于原理：

N=(Ndivd)×d+Nmodd

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

NNdiv8Nmod8

13481684

168210

2125

202计算顺序输出顺序voidconversion(){InitStack(S);

scanf("%d",N);

while(N){Push(S,N%8);N=N/8;

}

while(!StackEmpty(S))

{

Pop(S,e);

printf("%d",e);

}}//conversion例二、括号匹配的检验假设在表达式中（［］（））或［（［］［］）］等为正确的格式，［（］）或（［（））或(()])均为不正确的格式。则检验括号是否匹配的方法可用“期待的急迫程度”这个概念来描述。分析可能出现的不匹配的情况:到来的右括弧非是所“期待”的;例如：考虑下列括号序列：[([][])]12345678到来的是“不速之客”;直到结束，也没有到来所“期待”的括弧;Statusmatching(string&exp){

intstate=1;initstack(s);

while(i<=Length(exp)&&state){

switchofexp[i]{

case

左括弧:{Push(S,exp[i]);i++;break;}

case”)”:{

if(NOTStackEmpty(S)&&GetTop(S)=“(“{Pop(S,e);i++;}

else{state=0;}

break;}……}

if(StackEmpty(S)&&state)returnOK;…...例三、行编辑程序问题如何实现？“每接受一个字符即存入存储器”?

并不恰当！假设从终端接受了这样两行字符：

whli##ilr#e（s#*s)outcha@putchar(*s=#++);则实际有效的是下列两行：

while(*s)

putchar(*s++);

while(ch!=EOF&&ch!='\n'){

switch(ch){

case'#':Pop(S,c);break;

case'@':ClearStack(S);break;//重置S为空栈

default

:Push(S,ch);break;

}ch=getchar();//从终端接收下一个字符

}ClearStack(S);//重置S为空栈if(ch!=EOF)ch=getchar();}while(ch!=EOF){//EOF为全文结束符将从栈底到栈顶的字符传送至调用过程的数据区；11112222

232133

134

424

125

126

416

315

314

43$$$$$$$$求迷宫路径算法的基本思想是：若当前位置“可通”，则纳入路径，继续前进;若当前位置“不可通”，则后退，换方向继续探索;若四周“均无通路”，则将当前位置从路径中删除出去。设定当前位置的初值为入口位置；

do｛

若当前位置可通，

则｛将当前位置插入栈顶；

若该位置是出口位置，则算法结束；否则切换当前位置的东邻方块为新的当前位置；

｝

否则{

｝｝while(栈不空）；求迷宫中一条从入口到出口的路径的算法：

……限于二元运算符的表达式定义:

表达式::=(操作数)+(运算符)+(操作数)操作数::=简单变量|表达式简单变量::=标识符|无符号整数例五、表达式求值

表达式的三种标识方法：设

Exp=S1+OP+S2则称

OP+S1+S2为前缀表示法

S1+OP+S2为中缀表示法

S1+S2+OP为后缀表示法

例如:Exp=ab

+

(cd/e)f前缀式:+

ab

c/def中缀式:ab

+

cd/ef后缀式:ab

cde/f

+

结论:1）操作数之间的相对次序不变;2）运算符的相对次序不同;3）中缀式丢失了括弧信息，致使运算的次序不确定;

4)前缀式的运算规则为:连续出现的两个操作数和在它们之前且紧靠它们的运算符构成一个最小表达式;

5)后缀式的运算规则为:

运算符在式中出现的顺序恰为表达式的运算顺序;每个运算符和在它之前出现

且紧靠它的两个操作数构成一个最小表达式;如何从后缀式求值？先找运算符,再找操作数例如：

abcde/f+abd/ec-d/e(c-d/e)f如何从原表达式求得后缀式？

每个运算符的运算次序要由它之后的一个运算符来定，在后缀式中,优先数高的运算符领先于优先数低的运算符。分析“原表达式”和“后缀式”中的运算符:原表达式:a+bcd/ef后缀式:abc+de/f

从原表达式求得后缀式的规律为：1)设立暂存运算符的栈;2)设表达式的结束符为“#”,

予设运算符栈的栈底为“#”3)若当前字符是操作数，则直接发送给后缀式;4)若当前运算符的优先数高于栈顶运算符，则进栈;5)否则，退出栈顶运算符发送给后缀式;6)

“(”

对它之前后的运算符起隔离作用，“)”可视为自相应左括弧开始的表达式的结束符。从原表达式求得后缀式的规律为：voidtransform(charsuffix[],charexp[]){InitStack(S);Push(S,#);p=exp;ch=*p;

while(!StackEmpty(S)){if(!IN(ch,OP))Pass(Suffix,ch);else{}

if(ch!=#){p++;ch=*p;}else{Pop(S,ch);Pass(Suffix,ch);}

}//while}//CrtExptree……switch(ch){

case

(

:Push(S,ch);break;

case

)

:

Pop(S,c);

while(c!=

()

{Pass(Suffix,c);Pop(S,c)}

break;

defult:while(!Gettop(S,c)&&(precede(c,ch)))

{Pass(Suffix,c);Pop(S,c);}

if(ch!=

#)Push(S,ch);

break;

}

//switch例六、实现递归将所有的实在参数、返回地址等信息传递给被调用函数保存;为被调用函数的局部变量分配存储区;将控制转移到被调用函数的入口。当在一个函数的运行期间调用另一个函数时，在运行该被调用函数之前，

需先完成三项任务：保存被调函数的计算结果;释放被调函数的数据区;依照被调函数保存的返回地址将控制转移到调用函数。从被调用函数返回调用函数之前，应该完成下列三项任务：递归工作栈：递归过程执行过程中占用的数据区。递归工作记录：每一层的递归参数合成一个记录。当前活动记录：栈顶记录指示当前层的执行情况。当前环境指针：递归工作栈的栈顶指针。递归函数执行的过程可视为同一函数进行嵌套调用，例如：多个函数嵌套调用的规则是:此时的内存管理实行“栈式管理”后调用先返回！例如：voidmain(){voida(){voidb(){

………a();b();

……}//main}//a}//bMain的数据区函数a的数据区函数b的数据区voidhanoi(intn,charx,chary,charz){//将塔座x上按直径由小到大且至上而下编号为1至n//的n个圆盘按规则搬到塔座z上，y可用作辅助塔座。1if(n==1)2move(x,1,z);//将编号为１的圆盘从x移到z3else{4hanoi(n-1,x,z,y);//将x上编号为１至n-1的//圆盘移到y,z作辅助塔5move(x,n,z);//将编号为n的圆盘从x移到z6hanoi(n-1,y,x,z);//将y上编号为１至n-1的//圆盘移到z,x作辅助塔7}8}83abc返址nxyz52acb51abc71cabvoidhanoi(intn,charx,chary,charz){1if(n==1)2move(x,1,z);3else{4hanoi(n-1,x,z,y);5move(x,n,z);6hanoi(n-1,y,x,z);7}8}

3.3 栈类型的实现顺序栈链栈//-----栈的顺序存储表示-----

#defineSTACK_INIT_SIZE100;

typedefstruct{

SElemType

*base;

SElemType

*top;

intstacksize;

}

SqStack;类似于线性表的顺序映象实现，指向表尾的指针可以作为栈顶指针。

StatusInitStack(SqStack&S,intmaxsize){

//构造一个最大空间为maxsize的空顺序栈SS.base=new

ElemType[maxsize];

if(!S.base)exit(OVERFLOW);//存储分配失败

S.top=S.base;S.stacksize=maxsize;

returnOK;}

StatusPush(SqStack&S,SElemTypee){if(S.top-S.base>=S.stacksize)

//栈满

returnOVERFLOW;

*S.top++=e;

returnOK;}StatusPop(SqStack&S,SElemType&e){//若栈不空，则删除S的栈顶元素，//用e返回其值，并返回OK；//否则返回ERROR

if

(S.top

==

S.base)

returnERROR;e=*--S.top;

returnOK;}栈顶指针链栈∧a1an注意:链栈中指针的方向an-1ADTQueue{

数据对象：

D＝{ai|ai∈ElemSet,i=1,2,...,n,n≥0}

数据关系：

R1＝{<ai-1,ai>|ai-1,ai∈D,i=2,...,n}约定其中a1端为队列头，an端为队列尾基本操作：3.4队列的类型定义}

ADTQueue队列是一种运算受限制的线性表，元素的添加在表的一端进行，而元素的删除在表的另一端进行。允许添加元素的一端称为队尾（Rear）；允许删除元素的一端称为队头（Front）。向队列添加元素称为入队，从队列中删除元素称为出队。新入队的元素只能添加在队尾，出队的元素只能是删除队头的元素，队列的特点是先进入队列的元素先出队，所以队列也称作先进先出表或FIFO（First-In-First-Out）表。队列的基本操作：

InitQueue(&Q)DestroyQueue(&Q)QueueEmpty(Q)QueueLength(Q)GetHead(Q,&e)ClearQueue(&Q)DeQueue(&Q,&e)EnQueue(&Q,e)QueueTravers(Q,visit())InitQueue(&Q)

操作结果：构造一个空队列QDestroyQueue(&Q)

初始条件：队列Q已存在。

操作结果：队列Q被销毁，

不再存在。QueueEmpty(Q)

初始条件：队列Q已存在。

操作结果：若Q为空队列，则返回TRUE，否则返回FALSE。

QueueLength(Q)

初始条件：队列Q已存在。

操作结果：返回Q的元素个数，即队列的长度。

GetHead(Q,&e)

初始条件：Q为非空队列。

操作结果：用e返回Q的队头元素。a1a2an……

ClearQueue(&Q)

初始条件：队列Q已存在。

操作结果：将Q清为空队列。

EnQueue(&Q,e)

初始条件：队列Q已存在。

操作结果：插入元素e为Q的新的队尾元素。a1a2ane……

DeQueue(&Q,&e)

初始条件：Q为非空队列。

操作结果：删除Q的队头元素，并用e返回其值。a1a2an……

3.5队列类型的实现链队列——链式映象循环队列——顺序映象

typedefstructQNode{//结点类型

QElemTypedata;

structQNode*next;

}QNode,*QueuePtr;链队列——链式映象typedefstruct{//链队列类型QueuePtrfront;//队头指针QueuePtrrear;//队尾指针}LinkQueue;a1∧an…Q.frontQ.rearQ.frontQ.rear∧空队列

StatusInitQueue(LinkQueue&Q){//构造一个空队列Q

Q.front=Q.rear=newQNode;

if(!Q.front)exit(OVERFLOW);//存储分配失败Q.front->next=NULL;

returnOK;}

StatusEnQueue(LinkQueue&Q,QElemTypee){//插入元素e为Q的新的队尾元素p=newQNode;

if(!p)exit(OVERFLOW);//存储分配失败p->data=e;p->next=NULL;Q.rear->next=p;Q.rear=p;

returnOK;}

StatusDeQueue(LinkQueue&Q,QElemType&e){//若队列不空，则删除Q的队头元素，//用e返回其值，并返回OK；否则返回ERROR

if(Q.front==Q.rear)returnERROR;p=Q.front->next;e=p->data;Q.front->next=p->next;delete(p);returnOK;}if(Q.rear==p)Q.rear=Q.front;队列的顺序表示与堆栈类似，队列也可以简单的用一维数组表示。设数组名为Queue，其下标下界为0，上界为n-1。一般使用一个变量r指示队尾的下一个位置的下标值，叫做队尾指针；用另一个变量f指示队头的下标值，称为队头指针。队列中元素的数目等于零称为空队列，此时队头指针和队尾指针均为零，即f=r=0。假定有A～E5个元素先后进入队列，但A、B两个元素已陆续出队了，故队尾指针r=6，而队头指针f=3。1.入队（insert）

当给队列插入元素时，队尾指针r后移而队头指针不动，但有一个情况例外，即当向空队列插入第一个元素时，队头指针与队尾指针同时由0变为1。

设用下标从1到n的数组Q表示队列，且已知待添加的元素在变量x中。入队函数voidinsert(Q,intn,f,r,x){if(r==n-1)printf(“溢出!\n”);/*判断是否已到数组末端*/else{r=r+1；Q[r]=x; /*插入元素*/if(f==0)f=1;/*判断原来是否为空队列*/}}2.出队（Delete）

当从队列删除元素时，队头指针f后移而队尾指针r不动，但也有一个情况例外，即当删除了最后一个元素，队列成为了空队列时，队头指针与队尾指针同时变为0。假设要求将出队的元素值赋给变量x。出队函数voidDelete(Q,intf,r,n,x){if(f==0)printf(“下溢出!\n”);/*判断是否为空队列*/else{x=Q[f];/*取队头元素给x赋值*/if(f==r){f=0;/*若出队的是最后一个元素，变成空队列*/r=0;}elsef=f+1;/*队头指针后移*/}}3.队列存在的问题由于队列的入队操作是在两端进行的，随着元素的不断插入，删除，两端都向后移动，队列会很快移动到数组末端造成溢出，而前面的单元无法利用。解决办法：1)每次删除一个元素后，将整个队列向前移动一个单元，保持队列头总固定在数组的第一个单元。2)将所用的数组想象成是头尾相接的圆环，当队列的尾端到达数组的末端（第n个单元）时，如果再插入元素可继续使队列向数组的前端（第1个单元）延长，此队列称为循环队列。#defineMAXQSIZE100//最大队列长度typedefstruct{QElemType*base;//动态分配存储空间

intfront;//头指针，若队列不空，//指向队列头元素intrear;//尾指针，若队列不空，指向//队列尾元素的下一个位置

intqueuesize;}SqQueue;循环队列——顺序映象图中阴影部分为队列中元素。如何判断一个循环队列是满还是空？

StatusInitQueue(SqQueue&Q,

intmaxsize){//构造一个最大存储空间为maxsize的//空循环队列QQ.base=newElemType[maxsize];

if(!Q.base)exit(OVERFLOW);Q.queuesize=maxsize;Q.front=Q.rear=0;

returnOK;

}StatusEnQueue(SqQueue&Q,ElemTypee){//插入元素e为Q的新的队尾元素

if((Q.rear+1)%Q.queuesize==Q.front)

returnERROR;//队列满Q.base[Q.rear]=e;

Q.rear=(Q.rear+1)%Q.queuesize;

returnOK;}

StatusDeQueue(SqQueue&Q,ElemType&e){

//若队列不空，则删除Q的队头元素，//用e返回其值，并返回OK;否则返回ERRORif(Q.front==Q.rear)returnERROR;e=Q.base[Q.front];

Q.front=(Q.front+1)%Q.queuesize;

returnOK;}队列应用示例一、计算n行杨辉三角的值二、“划分无冲突子集问题”求解第1行11第2行121第3行1331第4行14641二项式系数值（杨辉三角）设第i-1行的值：(a[0]=0)a[1]..a[i](a[i+1]=0)则第i行的值：b[j]=a[j-1]+a[j],j=1,2,…,i+1利用循环队列计算二项式的过程：假设只计算四行，则队列的最大容量为5。1100q.frontq.rear11001q.frontq.rear11021q.frontq.rear11021q.frontq.rear10021q.frontq.rear10121q.frontq.rear10121q.frontq.rear10123q.frontq.rear10133q.frontq.rear10133q.frontq.reardo{DeQueue(Q,s);GetHead(Q,e);if(e!=0)printf(“%d”,e);EnQueue(Q,s+e);}while(e!=0);

某运动会设立N个比赛项目，每个运动员可以参加一至三个项目。试问如何安排比赛日程既可以使同一运动员参加的项目不安排在同一单位时间进行，又使总的竞赛日程最短。

若将此问题抽象成数学模型，则归属于“划分子集”问题。N个比赛项目构成一个大小为n的集合，有同一运动员参加的项目则抽象为“冲突”关系。

例如：某运动会设有9个项目:A={0，1，2，3，4，5，6，7，8}，七名运动员报名参加的项目分别为：（1，4，8）、（1，7）、（8，3）、（1，0，5）、（3，4）、（5，6，2）、（6，4）它们之间的冲突关系为:R={（1，4）,（4，8）,（1，8）,（1，7）,（8，3）,（1，0）,（0，5）,（1，5）,（3，4）,（5，6）,（5，2）,（6，2）,（6，4）}将集合A划分成k个互不相交的子集A1，A2，…，Ak（k≤n），使同一子集中的元素均无冲突关系，并要求划分的子集数目尽可能地少。“划分子集”问题即为:

对前述例子而言，问题即为:同一子集的项目为可以同时进行的项目，显然希望运动会的日程尽可能短。

可利用“过筛”的方法来解决划分子集问题。从第一个元素考虑起，凡不和第一个元素发生冲突的元素都可以和它分在同一子集中，然后再“过筛”出一批互不冲突的元素为第二个子集，依次类推，直至所有元素都进入某个子集为止。

012345678001000100011000110112000001100300001000140101001015111000100600101100070100000008010110000012345678145684588

010001000

010002100

010012101

020012101

为了减少重复察看R数组的时间，可另设一个数组clash[n]记录和当前已入组元素发生冲突的元素的信息。每次新开辟一组时，令clash数组各分量的值均为“0”，当序号为“i”的元素入组时，将和该元素发生冲突的信息记入clash数组。pre(前一个出队列的元素序号)=n;组号=0;全体元素入队列;while(队列不空){队头元素i出队列;if(i<pre)//开辟新的组{组号++;clash数组初始化;}if(i能入组){i入组，记下序号为i的元素所属组号;修改clash数组;

}elsei重新入队列;pre=i;}划分子集算法的基本思想:

1.掌握栈和队列类型的特点，并能在相应的应用问题中正确选用它们。2.熟练掌握栈类型的两种实现方法，特别应注意栈满和栈空的条件以及它们的描述方法。3.熟练掌握循环队列和链队列的基本操作实现算法，特别注意队满和队空的描述方法。

4.理解递归算法执行过程中栈的状态变化过程。QUICKQUIZ(3)一、基本知识题1.什么是栈？什么是队列？它们各自的特点是什么？2.线性表、栈、队列有什么异同？3.简述栈的入栈、出栈操作的过程。4.在循环队列中简述入队、出队操作的过程。二、算法设计题1.设用一维数组stack[n]表示一个堆栈，若堆栈中一个元素需占用length个数组单元（length>1），试写出其入栈、出栈操作的算法。2.试编写一个遍历及显示队列中元素的算法。

3.设一循环队列Queue，只有头指针front，不设尾指针，另设一个内含元素个数的计数器，试写出相应的入队、出队算法。4.设计一算法能判断一个算术表达式中的圆括号配对是否正确。（提示：对表达式进行扫描，凡遇到“（”就进栈，遇到“）”就退出栈顶的“（”，表达式扫描完毕时栈若为空则圆括号配对正确。）返回习题解答(3)一、基本知识题答案1.答：栈是限定在表的一端进行插入或删除操作的线性表；队列是元素的添加在表的一端进行，而元素的删除在表的另一端进行的线性表；栈的特点是后进先出，队列的特点是先进先出。2.答：栈和队列都是线性表，但是是受限的线性表，对插入、删除运算加以限制。栈是只允许在一端进行插入、删除运算，因而是后进先出表；而队列是只允许在一端进行插入、另一端进行删除运算，因而是先进先出表。3.答：栈的入栈、出栈操作均在栈顶进行，栈顶指针指向栈顶元素的下一个位置。入栈操作先将入栈元素放到栈顶指针所指示的位置上，然后将栈顶指针加1。出栈操作先将栈顶指针减1，然后从栈顶指针指向位置取值。

4.答：在循环队列中，设队首指针指向队首元素，队尾指针指向队尾元素后的一个空闲元素。在队列不满时，可执行入队操作，此时先送值到队尾指针指向的空闲元素，队尾指针再加1（要取模）。在队列不空时，可执行出队操作，此时先从队首指针指向处取值，队首指针再加1（要取模）。二、算法设计题答案1.解：用一整型变量top表示栈顶指针，top为0时表示栈为空。如果栈不空，则从