第三章栈和队列

第三章栈和队列13.1栈的类型定义3.2栈的应用举例3.3栈类型的实现3.4队列的类型定义3.5队列类型的实现2通常称，栈和队列是限定插入和删除只能在表的“端点”进行的线性表。线性表栈队列ListInsert(L,

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

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

1≤i≤n栈和队列是两种常用的数据类型33.1栈的类型定义ADTStack

{

数据对象：D＝{ai|ai∈ElemSet,i=1,2,...,n,n≥0}

数据关系：R1＝{<ai-1,ai>|ai-1,ai∈D,i=2,...,n}约定an端为栈顶，a1端为栈底。基本操作：

}ADTStack4InitStack(&S)DestroyStack(&S)ClearStack(&S)StackEmpty(S)StackLength(S)GetTop(S,&e)Push(&S,e)Pop(&S,&e)StackTravers(S,visit())5

InitStack(&S)

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

DestroyStack(&S)

初始条件：栈S已存在。

操作结果：栈S被销毁。6

StackEmpty(S)

初始条件：栈S已存在。

操作结果：若栈S为空栈，

则返回TRUE，否则FALE。7

StackLength(S)

初始条件：栈S已存在。

操作结果：返回S的元素个数， 即栈的长度。8

GetTop(S,&e)

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

操作结果：用e返回S的栈顶元素。a1a2an……9

ClearStack(&S)

初始条件：栈S已存在。

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

初始条件：栈S已存在。

操作结果：插入元素e为新的栈 顶元素。a1a2ane……11Pop(&S,&e)

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

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

……123.2栈的应用举例例一、数制转换例二、括号匹配的检验例三、行编辑程序问题例四、表达式求值例五、实现递归13

例一、数制转换

算法基于原理：

N=(Ndivd)×d+Nmodd

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

NNdiv8Nmod8

13481684

168210

2125

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

scanf("%d",N);

while(N){

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

}

while(!StackEmpty(S)){

Pop(S,e);

printf("%d",e);

}}//conversion16例二、括号匹配的检验则检验括号是否匹配的方法可用“期待的急迫程度”这个概念来描述。假设在表达式中（［］（））或［（［］［］）］等为正确的格式。例如：考虑下列括号序列：[([][])]1234567817分析可能出现的不匹配的情况:到来的右括弧非是所“期待”的;到来的是“不速之客”;直到结束，也没有到来所“期待”的括弧;［（］）或(()])或（［（））均为不正确的格式。18算法的设计思想：1）凡出现左括弧，则进栈；2）凡出现右括弧，首先检查栈是否空若栈空，则表明该“右括弧”多余否则和栈顶元素比较，若相匹配，则“左括弧出栈”否则表明不匹配3）表达式检验结束时，若栈空，则表明表达式中匹配正确否则表明“左括弧”有余19Statusmatching(string&exp){

intstate=1;

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;…...20例三、行编辑程序问题如何实现？“每接受一个字符即存入存储器”?

并不恰当！21设立一个输入缓冲区，用以接受用户输入的一行字符，然后逐行存入用户数据区;并约定“#”为退格符，“@”为退行符。在用户输入一行的过程中，允许用户输入出差错，并在发现有误时可以及时更正。合理的作法是：22假设从终端接受了这样两行字符：

whli##ilr#e（s#*s)则实际有效的是：

while(*s)outcha@putchar(*s=#++);putchar(*s++);23

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为全文结束符将从栈底到栈顶的字符传送至调用过程的数据区；24限于二元运算符的表达式定义:

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

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

Exp=S1+

OP

+S2则称

OP

+S1+S2为前缀表示法

S1+

OP

+S2为中缀表示法

S1+S2+

OP为后缀表示法

26例如:Exp=ab

+

(cd/e)f前缀式:+

ab

c/def中缀式:ab

+

cd/ef后缀式:ab

cde/f

+结论:1）操作数之间的相对次序不变;2）运算符的相对次序不同;3）中缀式丢失了括弧信息，致使运算的次序不确定;4)前缀式的运算规则为:连续出现的两个操作数和在它们之前且紧靠它们的运算符构成一个最小表达式;5)后缀式的运算规则为:

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

且紧靠它的两个操作数构成一个最小表达式;27如何从后缀式求值？先找运算符，再找操作数例如：abcde/f+abd/ec-d/e(c-d/e)f28abc×d－ef/+×abbaa×bcdeedd/ed/ecc-d/effc-d/e（c-d/e）×f如何从后缀式求值？29如何从原表达式求得后缀式？

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

cd/e

f后缀式:abc+de/f

30a×b+(－c/d×e)f后缀式栈#×+(－/×ab×cde/－f#×+31从原表达式求得后缀式的规律为：1)设立暂存运算符的栈;2)设表达式的结束符为“#”,

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

6)“(”对它之前后的运算符起隔离作用，“)”可视为自相应左括弧开始的表达式的结束符。从原表达式求得后缀式的规律为：33voidtransform(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……34switch(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;

}

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

需先完成三项任务：36保存被调函数的计算结果;释放被调函数的数据区;依照被调函数保存的返回地址将控制转移到调用函数。从被调用函数返回调用函数之前，应该完成下列三项任务：37多个函数嵌套调用的规则是:此时的内存管理实行“栈式管理”后调用先返回！例如：voidmain(){voida(…){voidb(…){

………a(…);b(…);

……}//main}//a}//bMain的数据区函数a的数据区函数b的数据区38递归工作栈：递归过程执行过程中占用的数据区。递归工作记录：每一层的递归参数合成一个记录。当前活动记录：栈顶记录指示当前层的执行情况。当前环境指针：递归工作栈的栈顶指针。递归函数执行的过程可视为同一函数进行嵌套调用。39voidhanoi(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}P55403.2栈的应用举例例一、数制转换例二、括号匹配的检验例三、行编辑程序问题例四、表达式求值例五、实现递归413.3 栈类型的实现顺序栈链栈42//-----栈的顺序存储表示-----

#defineSTACK_INIT_SIZE100;

typedefstruct{

SElemType

*base;

SElemType

*top;

intstacksize;

}

SqStack;类似于线性表的顺序映象实现，指向表尾的指针可以作为栈顶指针。43baseStacksizetopTop=base空栈atopbctop栈top44

StatusInitStack(SqStack&S,intmaxsize){

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

ElemType[maxsize];

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

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

returnOK;}45

StatusPush(SqStack&S,SElemTypee){//若栈不满，则将e插入栈顶if(S.top-S.base>=S.stacksize)

//栈满

returnOVERFLOW;*S.top++=e;

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

if

(S.top

==

S.base)

returnERROR;

e=*--S.top;

returnOK;}47栈顶指针链栈∧a1an注意:链栈中指针的方向an-1栈底元素48

习题设将整数1、2、3、4依次进栈，但只要出栈时栈非空，则可将出栈操作按任何次序夹入其中，请回答下有问题：（1）若入栈出栈次序为push(1)，pop()，push(2)，push(3)，pop()，pop()，push(4)，pop()，则出栈的数字序列为什么？（2）请分析1、2、3、4的24种排列中，哪些序列可以通过相应的入出栈得到。49ADTQueue{

数据对象：

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队列的类型定义}

ADTQueue50队列的基本操作：

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

操作结果：构造一个空队列Q。

DestroyQueue(&Q)

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

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

不再存在。52QueueEmpty(Q)

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

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

QueueLength(Q)

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

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

GetHead(Q,&e)

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

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

DeQueue(&Q,&e)

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

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

56

EnQueue(&Q,e)

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

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

ClearQueue(&Q)

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

操作结果：将Q清为空队列。583.5队列类型的实现链队列——链式映象循环队列——顺序映象59

typedefstructQNode{//结点类型

QElemTypedata;

structQNode*next;

}QNode,*QueuePtr;链队列——链式映象60typedefstruct{

//链队列类型

QueuePtrfront;//队头指针

QueuePtrrear;//队尾指针}LinkQueue;a1∧an…Q.frontQ.frontQ.rear∧空队列Q.rear队头元素61

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

Q.front=Q.rear=

newQNode;

if(!Q.front)exit(OVERFLOW);//存储分配失败

Q.front->next=NULL;

returnOK;}62

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;}Q.frontQ.rear∧epa1∧an…63

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;64Q.frontQ.reara1∧注意：出队列操作的特殊情况∧if(Q.rear==p)Q.rear=Q.front;65#defineMAXQSIZE100//最大队列长度typedefstruct{QElemType*base;//动态分配存储空间

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

intqueuesize;}SqQueue;循环队列——顺序映象66注意：顺序队列的几种情况：abcQ.frontQ.rear1、一般情况：100Q.frontQ.rear02、初始化：67abcQ.frontQ.rearabQ.front注意：顺序队列的几种情况：3、特殊情况：cQ.reardQ.rearQ.frontdQ.rearQ.rear6