第3章 栈和队列_第1页
第3章 栈和队列_第2页
第3章 栈和队列_第3页
第3章 栈和队列_第4页
第3章 栈和队列_第5页
已阅读5页,还剩165页未读, 继续免费阅读

下载本文档

版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领

文档简介

3.1栈第3章栈和队列

3.2队列1/91栈是一种只能在一端进行插入或删除操作的线性表。3.1.1栈的定义端点1端点2栈只能选取同一个端点进行插入和删除操作线性表3.1栈2/91允许进行插入、删除操作的一端称为栈顶。表的另一端称为栈底。当栈中没有数据元素时,称为空栈。栈的插入操作通常称为进栈或入栈。栈的删除操作通常称为退栈或出栈。栈顶栈底栈示意图进栈出栈栈的几个概念3/913.1.1栈的定义栈的主要特点是“后进先出”,即后进栈的元素先出栈。栈也称为后进先出表。走进死胡同的5人要按相反次序退出假设死胡同的宽度恰好只够正一个人死胡同类似一个栈!例如:4/913.1.1栈的定义设一个栈的输入序列为a,b,c,d,则借助一个栈所得到的输出序列不可能是()。

A.c,d,b,a B.

d,c,b,a

C.a,c,d,b D.d,a,b,c

abcd选项D是不可能的?栈下一步不可能出栈a答案为D5/913.1.1栈的定义

【例3.3】一个栈的入栈序列为1,2,3,…,n,其出栈序列是p1,p2,p3,…,pn。若p1=3,则p2可能取值的个数是多少?A.n-3B.n-2C.n-1D.无法确定栈123?n

…

4不可能是1和3共有n-2可能1、2、3进栈,3出栈的结果:答案为B6/913.1.1栈的定义一个栈的入栈序列为1,2,3,…,n,其出栈序列是p1,p2,p3,…,pn。若p2=3,则p3可能取值的个数是()多少?A.n-3B.n-2C.n-1D.无法确定全国考研题p3可以取1:1进,2进,2出,3进,3出,1出,…。p3可以取2:1进,1出,2进,3进,3出,2出,…

。p3可以取4:1进,1出,2进,3进,3出,4进,4出,…

。p3可以取5:1进,1出,2进,3进,3出,4进,5进,5出,…

。…p3可以取除了3外的任何值,共有n-1种可能。答案为C。3?n

…321不可能是37/913.1.1栈的定义栈的几种基本运算如下:

InitStack(&s):初始化栈。构造一个空栈s。

DestroyStack(&s):销毁栈。释放栈s占用的存储空间。

StackEmpty(s):判断栈是否为空:若栈s为空,则返回真;否则返回假。

Push(&S,e):进栈。将元素e插入到栈s中作为栈顶元素。

Pop(&s,&e):出栈。从栈s中退出栈顶元素并赋给e。

GetTop(s,&e):取栈顶元素。通过e返回当前的栈顶元素。

栈抽象数据类型=逻辑结构+基本运算(运算描述)8/913.1.1栈的定义3.1.2栈的顺序存储结构及其基本运算实现

栈中元素逻辑关系与线性表的相同,栈可以采用与线性表相同的存储结构。逻辑结构存储结构栈顺序表链表顺序栈链栈9/91假设栈的元素个数最大不超过正整数MaxSize,所有的元素都具有同一数据类型ElemType,则可用下列方式来声明顺序栈类型SqStack:

typedefstruct{ElemTypedata[MaxSize];

inttop; //栈顶指针}

SqStack;10/913.1.2栈的顺序存储结构及其基本运算实现栈(a1,a2,…,ai,…,an)直接映射a1a2…ai…an…n-1MaxSize-101i-1n-1datatop顺序栈的示意图逻辑结构存储结构11/913.1.2栈的顺序存储结构及其基本运算实现例如:MaxSize=543210top(a)空栈4321a0top(b)a进栈e4d3c2b1a0top(c)b、c、d、e进栈4d3c2b1a0top(d)出栈一次总结:约定top总是指向栈顶元素,初始值为-1当top=MaxSize-1时不能再进栈-栈满进栈时top增1,出栈时top减112/913.1.2栈的顺序存储结构及其基本运算实现顺序栈4要素:栈空条件:top=-1栈满条件:top=MaxSize-1进栈e操作:top++;将e放在top处退栈操作:从top处取出元素e;top--;顺序栈的各种状态43210top(a)空栈4321a0top(b)a进栈e4d3c2b1a0top(c)b、c、d、e进栈4d3c2b1a0top(d)出栈一次13/913.1.2栈的顺序存储结构及其基本运算实现(1)初始化栈InitStack(&s)建立一个新的空栈s,实际上是将栈顶指针指向-1即可。voidInitStack(SqStack*&s){s=(SqStack*)malloc(sizeof(SqStack));

s->top=-1;}

stop注意:s为栈指针,top为s所指栈的栈顶指针14/913.1.2栈的顺序存储结构及其基本运算实现(2)销毁栈DestroyStack(&s)

释放栈s占用的存储空间。voidDestroyStack(SqStack*&s){

free(s);

s=NULL;}15/913.1.2栈的顺序存储结构及其基本运算实现(3)判断栈是否为空StackEmpty(s)

栈S为空的条件是s->top==-1。boolStackEmpty(SqStack*s){

return(s->top==-1);}16/913.1.2栈的顺序存储结构及其基本运算实现(4)进栈Push(&s,e)

在栈不满的条件下,先将栈指针增1,然后在该位置上插入元素e。boolPush(SqStack*&s,ElemTypee){if(s->top==MaxSize-1)

//栈满的情况,即栈上溢出

returnfalse;

s->top++;

//栈顶指针增1

s->data[s->top]=e;

//元素e放在栈顶指针处

returntrue;}aetopeatopPush(&s,e)17/913.1.2栈的顺序存储结构及其基本运算实现(5)出栈Pop(&s,&e)

在栈不为空的条件下,先将栈顶元素赋给e,然后将栈指针减1。boolPop(SqStack*&s,ElemType&e){if(s->top==-1)

//栈为空的情况,即栈下溢出

returnfalse;

e=s->data[s->top];

//取栈顶指针元素的元素

s->top--;

//栈顶指针减1

returntrue;}eatopatopPop(&s,&e)18/913.1.2栈的顺序存储结构及其基本运算实现(6)取栈顶元素GetTop(s,&e)

在栈不为空的条件下,将栈顶元素赋给e。boolGetTop(SqStack*s,ElemType&e){if(s->top==-1)

//栈为空的情况,即栈下溢出

returnfalse;

e=s->data[s->top]; //取栈顶指针元素的元素

returntrue;}eatopGetTop(s,&e)atope19/913.1.2栈的顺序存储结构及其基本运算实现

【例3.4】

设计一个算法利用顺序栈判断一个字符串是否是对称串。所谓对称串是指从左向右读和从右向左读的序列相同。字符串str的所有元素依次进栈,产生的连续出栈序列正好与str的顺序相反。如果str与连续出栈序列相同,则是对称串。算法设计思路顺序栈的应用算法设计20/913.1.2栈的顺序存储结构及其基本运算实现例如,str="abcba"str进栈并连续出栈序列str'="abcba"str=str',str是对称串21/913.1.2栈的顺序存储结构及其基本运算实现boolsymmetry(ElemTypestr[]){inti;ElemTypee;SqStack*st;

InitStack(st);

//初始化栈

for(i=0;str[i]!='\0';i++)

//将串所有元素进栈

Push(st,str[i]);

//元素进栈

for(i=0;str[i]!='\0';i++)

{Pop(st,e);

//退栈元素e

if(str[i]!=e)

//若e与当前串元素不同则不是对称串

{ DestroyStack(st); //销毁栈

returnfalse;

}

}

DestroyStack(st);

//销毁栈

returntrue;}22/913.1.2栈的顺序存储结构及其基本运算实现设计一个算法,利用栈将一个正十进制整数转换为二进制数并输出。十进制二进制:n=10102510%2=025%2=12221202%2=01%2=1低位高位用栈保存23/913.1.2栈的顺序存储结构及其基本运算实现#include"sqstack1.cpp" //包含整数栈的基本运算函数voidtrans(intn){inte;SqStack*st;InitStack(st);while(n>0){Push(st,n%2);n=n/2;}while(!StackEmpty(st))//输出对应的二进制数{Pop(st,e);printf("%d",e);}printf("\n");DestroyStack(st);}24/913.1.2栈的顺序存储结构及其基本运算实现假设输入序列是1、2、…、n。设计一个算法判断通过一个栈能否得到由a[0..n-1](为1、2、…、n的某个排列)指定出栈序列。例如,n=3,a[]={2,3,1}是合法出栈序列a[]={3,1,2}不是合法出栈序列25/913.1.2栈的顺序存储结构及其基本运算实现例如,n=3,a[]={2,3,1}栈12例如,n=3,a[]={3,1,2}栈1233栈空,是出栈序列栈不空,不是出栈序列k扫描a(k=0开始),i=1到n循环:{进栈i;while(a[k]==i)

{出栈i,k++;}}若栈空返回true;否则返回false;26/913.1.2栈的顺序存储结构及其基本运算实现boolValidseq(inta[],intn){inti,e,k=0;boolflag; //k扫描a的元素

SqStack*st;InitStack(st);for(i=1;i<=n;i++) //处理输入序列1、2、…、n{Push(st,i); //i进栈

while(!StackEmpty(st))

//栈不空循环

{GetTop(st,e); //取栈顶元素eif(a[k]==e) //匹配的情况

{Pop(st,e);k++; } elsebreak; //不匹配时退出while循环

}}flag=StackEmpty(st);DestroyStack(st);returnflag;}27/913.1.2栈的顺序存储结构及其基本运算实现若需要用到两个相同类型的栈,可用一个数组data[0..MaxSize-1]来实现这两个栈,这称为共享栈。01……MaxSize-1data共享栈28/913.1.2栈的顺序存储结构及其基本运算实现a1a2…an…bmb1…b201…n-1…MaxSize-1datatop1top2栈1栈2栈的一端不动,元素向另外一端伸展29/913.1.2栈的顺序存储结构及其基本运算实现a1a2…an…bmb1…b201…n-1…MaxSize-1datatop1top2栈1栈2typedefstruct{ElemTypedata[MaxSize]; //存放共享栈中元素inttop1,top2; //两个栈的栈顶指针}DStack; 共享栈类型:30/913.1.2栈的顺序存储结构及其基本运算实现a1a2…an…bmb1…b201…n-1…MaxSize-1datatop1top2栈1栈2共享栈4要素栈空条件,栈1空:top1==-1;栈2空:top2==MaxSize栈满条件:top1==top2-1元素x进栈操作,进栈1操作:top1++;data[top1]=x;进栈2操作:top2--;data[top2]=x;出栈x操作,出栈1操作,x=data[top1];top1--;出栈2操作,x=data[top2];top2++;31/913.1.2栈的顺序存储结构及其基本运算实现栈(a1,a2,…,ai,…,an)映射逻辑结构存储结构一个链栈的示意图a1a2an∧…s栈顶栈底3.1.3栈的链式存储结构及其基本运算的实现

采用链表存储的栈称为链栈,这里采用带头结点的单链表实现。32/91链栈的4要素:栈空条件:s->next=NULL栈满条件:不考虑进栈e操作:将存放e的结点插入到头结点之后退栈操作:取出头结点之后结点的元素并删除之a1a2an∧…s栈顶栈底33/913.1.3栈的链式存储结构及其基本运算实现链栈中数据结点的类型LinkStNode声明如下:typedefstructlinknode{ElemTypedata; //数据域

structlinknode*next; //指针域}

LinkStNode;34/913.1.3栈的链式存储结构及其基本运算实现在链栈中,栈的基本运算算法如下。

(1)初始化栈initStack(&s)

建立一个空栈s。实际上是创建链栈的头结点,并将其next域置为NULL。voidInitStack(LinkStNode*&s){s=(LinkStNode*)malloc(sizeof(LinkStNode));s->next=NULL;}∧s35/913.1.3栈的链式存储结构及其基本运算实现(2)销毁栈DestroyStack(&s)

释放栈s占用的全部存储空间。voidDestroyStack(LinkStNode*&s){

LinkStNode*p=s,*q=s->next;

while(q!=NULL)

{ free(p); p=q; q=p->next;

}

free(p); //此时p指向尾结点,释放其空间s=NULL;}36/913.1.3栈的链式存储结构及其基本运算实现(3)判断栈是否为空StackEmpty(s)

栈s为空的条件是s->next==NULL,即单链表中没有数据结点。boolStackEmpty(LinkStNode*s){

return(s->next==NULL);}∧s空栈的情况37/913.1.3栈的链式存储结构及其基本运算实现(4)进栈Push(&s,e)

建立存放e的结点排,将结点p插入到头结点之后。voidPush(LinkStNode*&s,ElemTypee){LinkStNode*p;

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

p->data=e; //新建元素e对应的结点p

p->next=s->next; //插入p结点作为开始结点

s->next=p;}38/91sa1a2an∧…pe3.1.3栈的链式存储结构及其基本运算实现(5)出栈Pop(&s,&e)

栈非空时,将头结点后继数据结点的数据域赋给e,然后将其删除。boolPop(LinkStNode*&s,ElemType&e){LinkStNode*p;

if(s->next==NULL) //栈空的情况returnfalse;

p=s->next; //p指向开始结点

e=p->data;

s->next=p->next; //删除p结点

free(p); //释放p结点

returntrue;}39/91sa1a2an∧…取结点值3.1.3栈的链式存储结构及其基本运算实现(6)取栈顶元素GetTop(s,&e)

在栈不为空的条件下,将栈顶元素赋给e。boolGetTop(SqStack*s,ElemType&e){if(s->next==NULL) //栈空的情况returnfalse;e=s->next->data;

//取首结点值returntrue;}40/913.1.3栈的链式存储结构及其基本运算实现将字符栈类型声明及其基本运算函数存放在sqstack.cpp文件中#include"sqstack.cpp"//包含栈的基本运算函数intmain(){ElemTypee;SqStack*st;InitStack(st);printf("栈st空否:%d\n",StackEmpty(st));

Push(st,'a');

Push(st,'b');

Push(st,'c');printf("栈st空否:%d\n",StackEmpty(st));printf("出栈顺序:");while(!StackEmpty(st)){Pop(st,e);printf("%c",e);}printf("\n");

DestroyStack(st);}41/913.1.3栈的链式存储结构及其基本运算实现

【例3.5】编写一个算法判断输入的表达式中括号是否配对(假设只含有左、右圆括号)。

一个表达式中的左右括号是按最近位置配对的。所以利用一个栈来进行求解。这里采用链栈。算法设计思路链栈的应用算法设计42/913.1.3栈的链式存储结构及其基本运算实现例如:exp=“(()))”②‘(‘进栈(⑤遇到’)’,栈为空,返回false表达式括号不配对情况的演示①‘(‘进栈(③遇到’)’,栈顶为’(‘,退栈④遇到’)’,栈顶为’(‘,退栈43/913.1.3栈的链式存储结构及其基本运算实现例如:exp=“(())”②‘(‘进栈((①‘(‘进栈③遇到’)’,栈顶为’(‘,退栈④遇到’)’,栈顶为’(‘,退栈栈空且exp扫描完,返回true表达式括号配对情况的演示44/913.1.3栈的链式存储结构及其基本运算实现boolMatch(charexp[],intn){inti=0;chare;boolmatch=true;LinkStNode*st;

InitStack(st);

//初始化栈

while(i<n&&match)

//扫描exp中所有字符

{

if(exp[i]=='(')Push(st,exp[i]);45/913.1.3栈的链式存储结构及其基本运算实现elseif(exp[i]==')')

//当前字符为右括号

{if(GetTop(st,e)==true)

{if(e!='(')

//栈顶元素不为'('时不匹配

match=false;

else

Pop(st,e);

//将栈顶元素出栈

}

elsematch=false;

//无法取栈顶元素时不匹配

}i++;

//继续处理其他字符

}46/913.1.3栈的链式存储结构及其基本运算实现if(!StackEmpty(st))

match=false;DestroyStack(st);

//销毁栈

returnmatch;}注意:只有在表达式扫描完毕且栈空时返回true。47/913.1.3栈的链式存储结构及其基本运算实现栈和队列都是存放多个数据的容器。通常用于存放临时数据:如果后放入的数据先处理,则使用栈。如果先放入的数据先处理,则使用队列。3.1.4栈的应用48/91问题描述1、简单表达式求值这里限定的简单表达式求值问题是:用户输入一个包含“+”、“-”、“*”、“/”、正整数和圆括号的合法算术表达式,计算该表达式的运算结果。49/913.1.4栈的应用数据组织简单表达式采用字符数组exp表示,其中只含有“+”、“-”、“*”、“/”、正整数和圆括号。为了方便,假设是合法的算术表达式,例如,exp=“1+2*(4+12)”;在设计相关算法中用到栈,这里采用顺序栈存储结构。50/913.1.4栈的应用运算符位于两个操作数中间的表达式称为中缀表达式。例如,"1+2*3"就是一个中缀表达式。运算算法设计中缀表达式的运算规则:“先乘除,后加减,从左到右计算,先括号内,后括号外”。因此,中缀表达式不仅要依赖运算符优先级,而且还要处理括号。51/913.1.4栈的应用算术表达式的另一种形式是后缀表达式或逆波兰表达式,就是在算术表达式中,运算符在操作数的后面。

如"1+2*3"的后缀表达式为"123*+"。

后缀表达式特点:没有括号,已考虑了运算符的优先级。只有操作数和运算符,而且越放在前面的运算符来越优先执行。52/913.1.4栈的应用在算术表达式中,如果运算符在操作数的前面,称为前缀表达式,如"1+2*3"的前缀表达式为"+1*23"。中缀表达式:1+2*3后缀表达式:123*+前缀表达式:+1*23运算数的相对次序相同53/913.1.4栈的应用中缀表达式的求值过程:将中缀算术表达式转换成后缀表达式。对该后缀表达式求值。54/913.1.4栈的应用(1)将算术表达式转换成后缀表达式exp

postexp运算符栈扫描exp的所有字符:数字字符直接放在postexp中运算符通过一个栈来处理优先级55/913.1.4栈的应用exp

postexp情况1(没有括号)exp=运算符栈postexp:1+2+3“”优先级比较优先级相同:先进栈的先退栈即先执行,只有大于栈顶优先级才能直接进栈“1+2+3”

“12+3+”exp扫描完毕,所有运算符退栈56/91转换完毕3.1.4栈的应用exp

postexp情况2(有括号)exp=2*(14“”+3)-运算符栈postexp:(:一个子表达式开始,进栈开始时,任何运算符都进栈栈顶为(:任何运算符进栈):退栈到(只有大于栈顶的优先级,才进栈;否则退栈postexp=“213+*4-”57/91转换完毕3.1.4栈的应用while(从exp读取字符ch,ch!='\0'){ch为数字:将后续的所有数字均依次存放到postexp中,

并以字符'#'标志数值串结束;ch为左括号'(':将此括号进栈到Optr中;ch为右括号')':将Optr中出栈时遇到的第一个'('以前的运算符依次出

栈并存放到postexp中,然后将左括号'('出栈;ch为其他运算符:if(栈空或者栈顶运算符为'(')直接将ch进栈;elseif(ch的优先级高于栈顶运算符的优先级)

直接将ch进栈;else

依次出栈并存入到postexp中,直到栈顶运算符优先级小于ch的

优先级,然后将ch进栈;}若exp扫描完毕,则将Optr中所有运算符依次出栈并存放到postexp中。58/913.1.4栈的应用while(从exp读取字符ch,ch!='\0'){ch为数字:将后续的所有数字均依次存放到postexp中,

并以字符'#'标志数值串结束;ch为左括号'(':将此括号进栈到Optr中;ch为右括号')':将Optr中出栈时遇到的第一个左括号'('以前的运算符

依次出栈并存放到postexp中,然后将左括号'('出栈;ch为'+'或'-':出栈运算符并存放到postexp中,直到栈空或者栈顶为'(',

然后将'+'或'-'进栈;ch为'*'或'/':出栈运算符并存放到postexp中,直到栈空或者栈顶

为'('、'+'或'-',然后将'+'或'-'进栈;}若exp扫描完毕,则将Optr中所有运算符依次出栈并存放到postexp中。针对简单表达式exp:59/913.1.4栈的应用voidtrans(char*exp,charpostexp[]) {chare;

SqStack*Optr; //定义运算符栈指针InitStack(Optr); //初始化运算符栈inti=0; //i作为postexp的下标while(*exp!='\0') //exp表达式未扫描完时循环{switch(*exp){case'(': //判定为左括号

Push(Optr,'('); //左括号进栈 exp++; //继续扫描其他字符 break;算法:将算术表达式exp转换成后缀表达式postexp。60/913.1.4栈的应用case')': //判定为右括号

Pop(Optr,e); //出栈元素e while(e!='(') //不为'('时循环 {postexp[i++]=e; //将e存放到postexp中

Pop(Optr,e); //继续出栈元素e } exp++; //继续扫描其他字符 break;61/913.1.4栈的应用case'+':

//判定为加或减号case'-':

while(!StackEmpty(Optr)) //栈不空循环{GetTop(Optr,e); //取栈顶元素eif(e!='(') //e不是'('{postexp[i++]=e; //将e存放到postexp中

Pop(Optr,e); //出栈元素e}else //e是'(时退出循环 break; }

Push(Optr,*exp); //将'+'或'-'进栈 exp++; //继续扫描其他字符 break;62/913.1.4栈的应用case'*': //判定为'*'或'/'号case‘/’:

while(!StackEmpty(Optr)) //栈不空循环{GetTop(Optr,e); //取栈顶元素e if(e=='*'||e=='/') {postexp[i++]=e; //将e存放到postexp中

Pop(Optr,e); //出栈元素e } else //e为非‘*’或‘/’时退出循环 break; }

Push(Optr,*exp); //将'*'或'/'进栈 exp++; //继续扫描其他字符 break;63/913.1.4栈的应用

default:

//处理数字字符 while(*exp>='0'&&*exp<='9')//判定为数字字符 {postexp[i++]=*exp; exp++; } postexp[i++]='#'; //用#标识一个数值串结束 }}

while(!StackEmpty(Optr)) //此时exp扫描完毕,栈不空时循环{Pop(Optr,e); //出栈元素e

postexp[i++]=e; //将e存放到postexp中}postexp[i]='\0'; //给postexp表达式添加结束标识

DestroyStack(Optr); //销毁栈}64/913.1.4栈的应用(2)后缀表达式求值postexp

值操作数栈扫描postexp的所有字符:数字符:转换为数值并进栈运算符:退栈两个操作数,计算,将结果进栈65/913.1.4栈的应用while(从postexp读取字符ch,ch!='\0'){ch为'+':从Opnd栈中出栈两个数值a和b,计算c=b+a;将c进栈;ch为'-':从Opnd栈中出栈两个数值a和b,计算c=b-a;将c进栈;ch为'*':从Opnd栈中出栈两个数值a和b,计算c=b*a;将c进栈;ch为'/':从Opnd栈中出栈两个数值a和b,若a不零,计算c=b/a;将c进栈;ch为数字字符:将连续的数字串转换成数值d,将d进栈;}返回Opnd栈的栈顶操作数即后缀表达式的值;66/913.1.4栈的应用doublecompvalue(char*postexp) {doubled,a,b,c,e;SqStack1*Opnd; //定义操作数栈

InitStack1(Opnd); //初始化操作数栈while(*postexp!='\0') //postexp字符串未扫描完时循环{switch(*postexp){case'+': //判定为'+'号

Pop1(Opnd,a); //出栈元素aPop1(Opnd,b); //出栈元素bc=b+a; //计算c

Push1(Opnd,c); //将计算结果c进栈break;算法:计算后缀表达式postexp的值。67/913.1.4栈的应用 case'-': //判定为'-'号

Pop1(Opnd,a); //出栈元素a Pop1(Opnd,b); //出栈元素b c=b-a; //计算c

Push1(Opnd,c); //将计算结果c进栈 break; case'*': //判定为'*'号

Pop1(Opnd,a); //出栈元素a Pop1(Opnd,b); //出栈元素b c=b*a; //计算c

Push1(Opnd,c); //将计算结果c进栈 break;68/913.1.4栈的应用 case'/': //判定为'/'号

Pop1(Opnd,a); //出栈元素a Pop1(Opnd,b); //出栈元素b if(a!=0) {c=b/a; //计算c

Push1(Opnd,c); //将计算结果c进栈 break; } else {printf("\n\t除零错误!\n"); exit(0); //异常退出 } break;69/913.1.4栈的应用

default:

//处理数字字符d=0; //转换成对应的数值存放到d中 while(*postexp>='0'&&*postexp<='9') { d=10*d+*postexp-'0'; postexp++; }

Push1(Opnd,d); //将数值d进栈 break;}postexp++; //继续处理其他字符}

GetTop1(Opnd,e); //取栈顶元素eDestroyStack1(Opnd); //销毁栈returne; //返回e}70/913.1.4栈的应用设计求解程序intmain(){charexp[]="(56-20)/(4+2)"; //可将exp改为键盘输入charpostexp[MaxSize];

trans(exp,postexp);printf("中缀表达式:%s\n",exp);printf("后缀表达式:%s\n",postexp);printf("表达式的值:%g\n",compvalue(postexp));return0;}建立如下主函数调用上述算法:71/913.1.4栈的应用运行结果中缀表达式:(56-20)/(4+2)后缀表达式:56#20#-4#2#+/表达式的值:672/913.1.4栈的应用问题描述2、用栈求解迷宫问题给定一个M×N的迷宫图、入口与出口、行走规则。求一条从指定入口到出口的路径。所求路径必须是简单路径,即路径不重复。73/913.1.4栈的应用

行走规则:上、下、左、右相邻方块行走。其中(i,j)表示一个方块方位0方位2方位1方位3i,ji-1,ji,j+1i,j-1i+1,j74/913.1.4栈的应用0123456789入口出口

例如,M=8,N=8,图中的每个方块,用空白表示通道,用阴影表示障碍物。为了算法方便,一般在迷宫外围加上了一条围墙。一条迷宫路径012

3

45

678975/913.1.4栈的应用数据组织设置一个迷宫数组mg,其中每个元素表示一个方块的状态,为0时表示对应方块是通道,为1时表示对应方块不可走。

76/913.1.4栈的应用intmg[M+2][N+2]={{1,1,1,1,1,1,1,1,1,1},{1,0,0,1,0,0,0,1,0,1},{1,0,0,1,0,0,0,1,0,1},{1,0,0,0,0,1,1,0,0,1},{1,0,1,1,1,0,0,0,0,1},{1,0,0,0,1,0,0,0,0,1},{1,0,1,0,0,0,1,0,0,1},{1,0,1,1,1,0,1,1,0,1},{1,1,0,0,0,0,0,0,0,1},{1,1,1,1,1,1,1,1,1,1}};01234567890123456789M×N77/913.1.4栈的应用在算法中用到的栈采用顺序栈存储结构,即将栈声明为:typedefstruct{inti; //当前方块的行号intj; //当前方块的列号intdi; //di是下一可走相邻方位的方位号}Box; //定义方块类型typedefstruct{Boxdata[MaxSize];inttop; //栈顶指针}StType; //声明顺序栈类型i,jx,ydi78/913.1.4栈的应用试探顺序:从方位0开始,顺时针方向方位0方位2方位1方位3i,ji-1,ji,j+1i,j-1i+1,j算法设计79/913.1.4栈的应用i,jijdiij-1栈将(i,j,-1)进栈初始时,入口(i,j)作为当前方块。所有走过的方块都会进栈!80/913.1.4栈的应用如果一个当前方块(i,j)找到一个相邻可走方块(x,y),就继续从(x,y)走下去。i,jx,y方位dijdiijd栈将(x,y,-1)进栈xy-181/913.1.4栈的应用

如果一个当前方块(i,j)没有找到任何相邻可走方块,表示此时无路可走,将其退栈。i,j××××ijdiijd栈将(i,j,d)退栈

82/913.1.4栈的应用求解迷宫路径的过程:前一方块××当前方块回溯找其他可能的相邻方块所有相邻方块都不能走83/913.1.4栈的应用boolmgpath(intxi,intyi,intxe,intye){Boxpath[MaxSize],e;inti,j,di,i1,j1,k;boolfind;StType*st; //定义栈stInitStack(st); //初始化栈顶指针e.i=xi;e.j=yi;e.di=-1; //设置e为入口Push(st,e); //方块e进栈

mg[xi][yi]=-1; //入口的迷宫值置为-1避免重复用栈求一条迷宫路径的算法:(xi,yi)

(xe,ye)012345012345●●i

j

di11-1一个栈为了避免重复,当一个方块进栈时,将迷宫值改为-184/913.1.4栈的应用while(!StackEmpty(st)) //栈不空时循环{GetTop(st,e); //取栈顶方块ei=e.i;j=e.j;di=e.di;if(i==xe&&j==ye) //找到了出口,输出该路径{printf("一条迷宫路径如下:\n");k=0;while(!StackEmpty(st)){Pop(st,e); //出栈方块e path[k++]=e; //将e添加到path数组中}85/913.1.4栈的应用while(k>=1){k--; printf("\t(%d,%d)",path[k].i,path[k].j);if((k+2)%5==0) //每输出每5个方块后换一行printf("\n");}printf("\n");DestroyStack(st); //销毁栈returntrue; //输出一条迷宫路径后返回true}i

j

di11-1112-113-124-123-1121233-1143-1144-1↓→→↓→↓86/913.1.4栈的应用

find=false;while(di<4&&!find)//找相邻可走方块(i1,j1){ di++; switch(di) { case0:i1=i-1;j1=j;break; case1:i1=i;j1=j+1;break; case2:i1=i+1;j1=j;break; case3:i1=i;j1=j-1;break; } if(mg[i1][j1]==0)find=true;

//找到一个相邻可走方块,设置find为真}→从入口(1,1)出发找到一个可走方块(1,2)87/913.1.4栈的应用if(find) //找到了一个相邻可走方块(i1,j1){st->data[st->top].di=di; //修改原栈顶元素的di值e.i=i1;e.j=j1;e.di=-1;Push(st,e); //相邻可走方块e进栈mg[i1][j1]=-1;

//(i1,j1)迷宫值置为-1避免重复}→从入口(1,1)出发找到一个可走方块(1,2):将(1,2,-1)进栈i

j

di111一个栈12-188/913.1.4栈的应用else //没有路径可走退栈{ Pop(st,e); //将栈顶方块退栈

mg[e.i][e.j]=0;

//让退栈方块变为1}}DestroyStack(st); //销毁栈returnfalse; //表示没有可走路径}(2,4)方块没有通路i

j

di一个栈24-1

…退栈疑难解答:这里不将mg[栈顶方块]设置为0,程序执行也是正确的(因为只求一条路径),但从原理上应该这样做,回退后需要恢复环境!89/913.1.4栈的应用设计求解程序intmain(){if(!mgpath(1,1,M,N))printf("该迷宫问题没有解!");return0;}设计如下主函数调用上述算法:90/913.1.4栈的应用运行结果迷宫路径如下: (1,1)(1,2)(2,2)(3,2)(3,1) (4,1)(5,1)(5,2)(5,3)(6,3) (6,4)(6,5)(5,5)(4,5)(4,6) (4,7)(3,7)(3,8)(4,8)(5,8) (6,8)(7,8)(8,8)求解结果如下:显然,这个解不是最优解,即不是最短路径。为什么?91/913.1.4栈的应用3.1栈第3章栈和队列

3.2队列92/71

队列简称队,它也是一种运算受限的线性表。3.2.1队列的定义

队列只能选取一个端点进行插入操作,另一个端点进行删除操作端点1端点2线性表3.2队列93/71进行插入的一端称做队尾(rear)。进行删除的一端称做队首或队头(front)。向队列中插入新元素称为进队或入队,新元素进队后就成为新队尾元素。从队列中删除元素称为出队或离队,元素出队后,其后继元素就成为队首元素。队尾队头队列示意图出队进队队列的几个概念3.2.1队列的定义

94/71队列的主要特点是先进先出,所以又把队列称为先进先出表。假如5个人过独木桥只能按上桥的次序过桥独木桥类似一个队列例如:3.2.1队列的定义

95/71队列的基本运算如下:

InitQueue(&q):初始化队列。构造一个空队列q。

DestroyQueue(&q):销毁队列。释放队列q占用的存储空间。

QueueEmpty(q):判断队列是否为空。若队列q为空,则返回真;否则返回假。

enQueue(&q,e):进队。将元素e进队作为队尾元素。

deQueue(&q,&e):出队。从队列q中出队一个元素,并将其值赋给e。队列抽象数据类型=逻辑结构+基本运算(运算描述)3.2.1队列的定义

96/71队列中元素逻辑关系与线性表的相同,队列可以采用与线性表相同的存储结构。逻辑结构存储结构队列顺序表链表顺序队链队3.2.2队列的顺序存储结构及其基本运算实现

97/71typedefstruct{ElemTypedata[MaxSize];

intfront,rear;//队首和队尾指针}

SqQueue;顺序队类型SqQueue声明如下:

因为队列两端都在变化,所以需要两个指针来标识队列的状态。3.2.2队列的顺序存储结构及其基本运算实现98/71队列(a1,a2,…,ai,…,an)映射…a1…an……fMaxSize-1ff+1rdatafront顺序队的示意图逻辑结构存储结构0rrear3.2.2队列的顺序存储结构及其基本运算实现99/71例如:MaxSize=543210rear(a)空队(b)a进队(c)b、c、d、e进队(d)全部出队总结约定rear总是指向队尾元素元素进队,rear增1约定front指向当前队中队头元素的前一位置元素出队,front增1当rear=MaxSize-1时不能再进队front4321a0frontreare4d3c2b1a0frontrear43210frontrear3.2.2队列的顺序存储结构及其基本运算实现100/71顺序队的4要素(初始时front=rear=-1):队空条件:front=rear队满条件:rear=MaxSize-1元素e进队:rear++;data[rear]=e;元素e出队:front++;e=data[front];队列的各种状态43210rearfront4321a0frontreare4d3c2b1a0frontrear43210frontrear(a)空队(b)a进队(c)b、c、d、e进队(d)全部出队3.2.2队列的顺序存储结构及其基本运算实现101/711、顺序队中实现队列的基本运算算法(1)初始化队列InitQueue(q)构造一个空队列q。将front和rear指针均设置成初始状态即-1值。voidInitQueue(SqQueue*&q){q=(SqQueue*)malloc(sizeof(SqQueue));

q->front=q->rear=-1;}43210rearfront3.2.2队列的顺序存储结构及其基本运算实现102/71(2)销毁队列DestroyQueue(q)释放队列q占用的存储空间。voidDestroyQueue(SqQueue*&q){free(q);

q=NULL;}3.2.2队列的顺序存储结构及其基本运算实现103/71(3)判断队列是否为空QueueEmpty(q)

若队列q满足q->front==q->rear条件,则返回true;否则返回false。boolQueueEmpty(SqQueue*q){

return(q->front==q->rear);}3.2.2队列的顺序存储结构及其基本运算实现104/71(4)进队列enQueue(q,e)

在队不满时,先将队尾指针rear循环增1,然后将元素添加到该位置。boolenQueue(SqQueue*&q,ElemTypee){if(q->rear==MaxSize-1)

//队满上溢出

returnfalse;

q->rear++;

q->data[q->rear]=e;

returntrue;}4321a0frontrear43210rearfront空队时元素a进队:105/71(5)出队列deQueue(q,e)

在队q不为时将队首指针front循环增1,并将该位置的元素值赋给e。booldeQueue(SqQueue*&q,ElemType&e){if(q->front==q->rear)

//队空下溢出

returnfalse;

q->front++;

e=q->data[q->front];

returntrue;}4d3c2b10frontrear出队一个元素:4d3c210frontrear3.2.2队列的顺序存储结构及其基本运算实现106/712、环形队列(或循环队列)中实现队列的基本运算c4b3a210frontrear这是因为采用rear==MaxSize-1作为队满条件的缺陷。当队满条件为真时,队中可能还有若干空位置。这种溢出并不是真正的溢出,称为假溢出。还有两个位置,为何不能进队?3.2.2队列的顺序存储结构及其基本运算实现107/71

把数组的前端和后端连接起来,形成一个环形的顺序表,即把存储队列元素的表从逻辑上看成一个环,称为环形队列或循环队列。原来如此,简单!c4b3a210frontrear01234frontabcrear当rear=4时,下一步到位置0,可以进队解决方案例如当rear=4时,不能再进队3.2.2队列的顺序存储结构及其基本运算实现108/7101234frontabcdrear实际上内存地址一定是连续的,不可能是环形的,这里是通过逻辑方式实现环形队列,也就是将rear++和front++改为:rear=(rear+1)%MaxSizefront=(front+1)%MaxSize环形队列(循环队列):3.2.2队列的顺序存储结构及其基本运算实现109/7101234frontrear(a)空队01234frontabcrear(b)a、b、c进队01234frontbcrear(c)出队一次01234frontrear(d)出队2次3.2.2队列的顺序存储结构及其基本运算实现110/71现在约定rear=front为队空,以下两种情况都满足该条件:那么如何设置队满的条件呢?01234frontrear初始状态01234frontrear进队5个元素addcb3.2.2队列的顺序存储结构及其基本运算实现111/71约定:rear=front为队空条件,(rear+1)%MaxSize=front为队满条件进队一个元素时到达队头,就认为队满了。这样做会少放一个元素,牺牲一个元素空间3.2.2队列的顺序存储结构及其基本运算实现112/71通过相对值|front-rear|标识不同的队列状态。若data数组的容量为m,则队列有m+1种状态,分别是队空、队中有1个元素、队中有2个元素、…、队中有m个元素(队满)。front和rear的取值为0~m-1,这样|front-rear|只有m个值。队列m+1种状态不能用|front-rear|区分,有两种状态不能区分。原因说明3.2.2队列的顺序存储结构及其基本运算实现113/71队空条件:front=rear队满条件:(rear+1)%MaxSize=front进队e操作:rear=(rear+1)%MaxSize;将e放在rear处出队操作:front=(front+1)%MaxSize;取出front处元素e;环形队列的4要素:

在环形队列中,实现队列的基本运算算法与非环形队列类似,只是改为上述4要素即可。3.2.2队列的顺序存储结构及其基本运算实现114/71

【例3.7】对于环形队列来说,如果知道队头指针和队列中元素个数,则可以计算出队尾指针。也就是说,可以用队列中元素个数代替队尾指针。

设计出这种环形队列的初始化、入队、出队和判空算法。3.2.2队列的顺序存储结构及其基本运算实现115/71count=(3-0)=3MaxSize=501234frontrearabc01234frontrearabccount=(1-3)=-2

count=rear-front?已知front、rear,求队中元素个数count=?count=(1-3+MaxSize)=3count=(3-0+MaxSize)=8

count=(3-0+MaxSize)%MaxSize=3

count=(1-3+MaxSize)%MaxSize=3

3.2.2队列的顺序存储结构及其基本运算实现116/71已知front、rear,求队中元素个数count:

count=(rear-front+MaxSize)%MaxSize已知front、count,求rear:

rear=(front+count)%MaxSize已知rear、count,求front:

front=(rear-count+MaxSize)%MaxSize3.2.2队列的顺序存

温馨提示

  • 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
  • 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
  • 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
  • 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
  • 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
  • 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
  • 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

评论

0/150

提交评论