超级盘数据结构三章栈队列

3.1栈的类型定义3.2栈的应用举例3.3栈的表示与实现3.4队列的定义3.5队列的表示与实现第三章栈和队列3.6

队列的应用通常称，栈和队列是限定插入和删除只能在表的“端点”进行的线性表。

线性表栈队列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

栈的类型定义

ADTStack

{

数据对象：

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

数据关系：

R1＝{<ai-1,ai>|ai-1,ai∈D,i=2,...,n}

约定an

端为栈顶元素，a1端为栈底元素。基本操作：

}ADTStack栈是一种只能在一端进行插入或删除操作的线性表。表中允许进行插入、删除操作的一端称为栈顶。

例:设一个栈的输入序列为A,B,C,D,则借助一个栈所得到的输出序列不可能是

。

(A)A,B,C,D (B)D,C,B,A (C)A,C,D,B (D)D,A,B,C

答:可以简单地推算,得容易得出D,A,B,C是不可能的,因为D先出来,说明A,B,C,D均在栈中,按照入栈顺序,在栈中顺序应为D,C,B,A,出栈的顺序只能是D,C,B,A。所以本题答案为D。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的元素个数，即栈的长度。

GetTop(S,&e)

初始条件：栈S已存在且非空。操作结果：用e返回S的栈顶元素。a1a2an……

ClearStack(&S)

初始条件：栈S已存在。

操作结果：将S清为空栈。

Push(&S,e)

初始条件：栈S已存在。

操作结果：插入元素e为新的栈顶元素。

a1a2ane……Pop(&S,&e)

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

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

……3.2

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

例一、数制转换

假设要将十进制数N转换为d进制数，一个简单的转换算法是重复下述两步，直到N等于零：X=Nmodd(其中mod为求余运算)N=Ndivd(其中div为整除运算)算法基于原理：

N=(Ndivd)×d+Nmodd

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

NNdiv8Nmod8

210

2125

202计算顺序输出顺序算法基于原理：

N=(Ndivd)×d+Nmoddvoidconversion(){InitStack(S);

scanf("%d",N);

while(N){

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

}

while(!StackEmpty(S)){

Pop(S,e);

printf("%d",e);

}}//conversionNNdiv8Nmod8

210

2125

202思考：当输入N为1348时入栈顺序：？出栈顺序：？例二、括号匹配的检验假设在表达式中（［］（））或［（［］［］）］等为正确的格式，［（］）或（［（））或（（）］)均为不正确的格式。则检验括号是否匹配的方法可用“期待的急迫程度”这个概念来描述。分析可能出现的不匹配的情况:到来的右括弧并非是所“期待”的；例如：考虑下列括号序列：

[([][])]12345678到来的是“不速之客”；直到结束，也没有到来所“期待”的括弧。算法的设计思想：1）凡出现左括弧，则进栈；2）凡出现右括弧，首先检查栈是否空若栈空，则表明该“右括弧”多余，否则和栈顶元素比较，若相匹配，则“左括弧出栈”

，否则表明不匹配。3）表达式检验结束时，若栈空，则表明表达式中匹配正确，否则表明“左括弧”有余。Statusmatching(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;…...例三、行编辑程序问题如何实现？“每接受一个字符即存入存储器”?

并不恰当！

设立一个输入缓冲区，用以接受用户输入的一行字符，然后逐行存入用户数据区，并假设“#”为退格符，“@”为退行符。

在用户输入一行的过程中，允许用户输入出差错，并在发现有误时可以及时更正。合理的作法是：例三、行编辑程序问题假设从终端接受了这样两行字符：

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为全文结束符将从栈底到栈顶的字符传送至调用过程的数据区；例四、迷宫求解通常用的是“穷举求解”的方法求解迷宫中一条路径的方法：从入口出发，沿某一方向进行探索，若能走通，则继续向前走；否则沿原路返回，换一方向再进行探索，直到所有可能的通路都探索到为止。这类方法统称回溯法。(a)迷宫的图形表示 (b)迷宫的二维数组表示

设定当前位置的初值为入口位置；

do｛若当前位置可通，则｛将当前位置插入栈顶；若该位置是出口位置，则算法结束；

否则切换当前位置的东邻方块为新的当前位置；｝

否则

{

｝while(栈不空）；求迷宫中一条从入口到出口的路径的算法：若栈不空且栈顶位置尚有其他方向未被探索，则设定新的当前位置为:沿顺时针方向旋转

找到的栈顶位置的下一相邻块；若栈不空但栈顶位置的四周均不可通，则｛删去栈顶位置；//从路径中删去该通道块

若栈不空，则重新测试新的栈顶位置，直至找到一个可通的相邻块或出栈至栈空；｝若栈空，则表明迷宫没有通路。例五、表达式求值

表达式求值是高级语言编译中的一个基本问题，是栈的典型应用实例。任何一个表达式都是由操作数(operand)、运算符(operator)和界限符(delimiter)组成的。操作数既可以是常数，也可以是被说明为变量或常量的标识符；运算符可以分为算术运算符、关系运算符和逻辑运算符三类；基本界限符有左右括号和表达式结束符等。算术表达式处理规则

(1)规定优先级表。

(2)设置两个栈：OVS(运算数栈)和OPTR(运算符栈)。

(3)自左向右扫描，遇操作数进OVS，遇操作符则与OPTR栈顶优先数比较：当前操作符>OPTR栈顶,当前操作符进OPTR栈；当前操作符≤OPTR栈顶，OVS栈顶、次顶和OPTR栈顶，退栈形成运算T(i)，T(i)进OVS栈。

表3-1算符之间的优先关系两个前后相继出现的算符θ1和θ2A/B↑C+D*E运算过程的栈区变化情况示意图自左向右扫描，遇操作数进OVS，遇操作符则与OPTR栈顶优先数比较：当前操作符>OPTR栈顶,当前操作符进OPTR栈当前操作符≤OPTR栈顶，OVS栈顶、次顶和OPTR栈顶，退栈形成运算T(i)，T(i)进OVS栈。例六、实现递归

栈非常重要的一个应用是在程序设计语言中用来实现递归。递归是指在定义自身的同时又出现了对自身的调用。如果一个函数在其定义体内直接调用自己，则称其为直接递归函数；如果一个函数经过一系列的中间调用语句，通过其它函数间接调用自己，则称其为间接递归函数。将所有的实在参数、返回地址等信息传递给被调用函数保存；为被调用函数的局部变量分配存储区；将控制转移到被调用函数的入口。

当在一个函数的运行期间调用另一个函数时，在运行该被调用函数之前，需先完成三项任务：从被调用函数返回调用函数之前，应该完成下列三项任务：保存被调函数的计算结果；释放被调函数的数据区；依照被调函数保存的返回地址将控制转移到调用函数。例如：voidmain(){voida(){voidb(){

………a();b();

……}//main}//a}//b多个函数嵌套调用r主程序srrrs子程序1rst子程序2rst子程序3后调用先返回！递归函数执行的过程可视为同一函数进行嵌套调用多个函数嵌套调用的规则是：内存管理实行“栈式管理”voidhanoi(intn,chara,charb,charc){//将塔座a上按直径由小到大且至上而下编号为1至n//的n个圆盘按规则搬到塔座c上，b可用作辅助塔座。1if(n==1)2move(a,1,c);//将编号为１的圆盘从a移到c3else{4hanoi(n-1,a,c,b);//将a上编号为１至n-1的

//圆盘移到b,c作辅助塔5move(a,n,c);//将编号为n的圆盘从x移到z6hanoi(n-1,b,a,c);//将b上编号为１至n-1的

//圆盘移到c,a作辅助塔7}8}

递归算法一般适用在三个场合1、数据的定义形式是递归的，如求n！；2、数据之间的逻辑关系（数据结构）是递归的，如单链表、树、图等的定义和操作；3、某些问题虽然没有明显的递归关系或结构，但问题的解法是不断重复执行一种操作，只是问题规模由大化小，直至某个原操作（基本操作）就结束，如汉诺塔问题。递归算法求解问题的要素递归算法就是算法中有直接或间接调用算法本身的算法。递归算法的要点如下：

(1)问题具有类同自身的子问题的性质，被定义项在定义中的应用具有更小的尺度。

(2)被定义项在最小尺度上有直接解。

设计递归算法的方法：

(1)寻找方法，将问题化为原问题的子问题求解（例n!=n*(n-1)!）。

(2)设计递归出口，确定递归终止条件

(例求解n!时，当n=1时，n!=1)。

#include<stdio.h>intfun(intn){ if(n==1) return(1); else return(fun(n-1)*n); }voidmain(){ printf("10!=%d\n",fun(10));}递归小结优点：结构清晰，可读性强，而且容易用数学归纳法来证明算法的正确性，因此它为设计算法、调试程序带来很大方便。缺点：递归算法的运行效率较低，无论是耗费的计算时间还是占用的存储空间都比非递归算法要多。3.3栈类型的表示与实现顺序栈链栈//-----栈的顺序存储表示

-----

#defineSTACK_INIT_SIZE100;

#defineSTACKINCREMENT10;

typedefstruct{

SElemType

*base;

SElemType

*top;

intstacksize;

}

SqStack;

类似于线性表的顺序映象实现，指向表尾的指针可以作为栈顶指针。栈底指针base：指向栈底元素的位置本课件top指向栈顶元素的下一个待插入元素的位置。栈顶指针top：栈非空时，指向栈顶(或待插入)元素的位置。

StatusInitStack(SqStack&S){//构造一个空栈SS.base=(ElemType*)malloc(STACK_INIT_SIZE*sizeof(ElemType));

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

S.top=S.base;S.stacksize=STACK_INIT_SIZE;

returnOK;}//栈顶指向栈底(空栈)//存储空间为初始分配量typedefstruct{

SElemType

*base;

SElemType

*top;

intstacksize;

}

SqStack;

StatusPush(SqStack&S,SElemTypee)

{//进栈

if(S.top-S.base>=S.stacksize){

//栈满，追加存储空间

S.base=(ElemType*)realloc(S.base,(S.stacksize+STACKINCREMENT)*

sizeof(ElemType));

if(!S.base)exit(OVERFLOW);

//存储分配失败

S.top=S.base+S.stacksize;

//修改栈顶指针，指向新的栈顶

S.stacksize+=STACKINCREMENT;

//更新当前已分配的存储空间

}

*S.top++=e;//

将e入栈，成为新的栈顶元素，栈顶指针上移1个存储单元

returnOK;}StatusPop(SqStack&S,SElemType&e)

{//出栈

//若栈不空，则删除S的栈顶元素，

//用e返回其值，并返回OK；

//否则返回ERROR

if

(S.top

==

S.base)

returnERROR;

e=*--S.top;//栈顶指针下移1个存储单元，将栈顶元素赋给e，

returnOK;}思考：栈空时s.top＝?

栈满时s.top＝?typedefstruct{

SElemType

*base;

SElemType

*top;

intstacksize;

}

SqStack;S.top==S.base+S.stacksizeS.top

==

S.base栈顶指针

S链栈∧a1an注意:链栈中指针的方向an-1思考：栈空S=?

栈满?TypedefstructStackNode

//栈结点类型定义

{SElemTypedata;

//数据域

structStackNode*next;

//指针域

}

StackNode,*LinkStack;

S==NULL

StatusInitStack(LinkStack&S){//构造一个空栈SS=NULL;returnOK;}TypedefstructStackNode

//栈结点类型定义

{SElemTypedata;

//数据域

structStackNode*next;

//指针域

}

StackNode,*LinkStack;

StatusPush(LinkStack&S,SElemTypee)

{//进栈//在栈顶插入新元素e

LinkStackp;//定义新结点pp=(SElemType*)malloc(sizeof(SElemType));

//生成新结点p

if(!p)exit(OVERFLOW);

//存储分配失败

p->data=e;//将新结点数据域置为ep->next=S;//将新结点p插入栈顶

S=p;//修改栈顶指针

returnOK;}TypedefstructStackNode

//栈结点类型定义

{SElemTypedata;

//数据域

structStackNode*next;

//指针域

}

StackNode,*LinkStack;

StatusPop(LinkStack&S,SElemType&e)

{//出栈//若栈不空，则删除S的栈顶元素，用e返回其值，并返回OK；//否则返回ERROR

LinkStackp;

if

(S

==NULL)

returnERROR;

e=S->data;//将栈顶元素赋给ep=S;S=S->next;free(p);

returnOK;}TypedefstructStackNode

//栈结点类型定义

{SElemTypedata;

//数据域

structStackNode*next;

//指针域

}

StackNode,*LinkStack;

队列的主要运算（1）设置一个空队列；（2）插入一个新的队尾元素，称为进队；（3）删除队头元素，称为出队；（4）读取队头元素；定义：一种特殊的线性结构，限定只能在表的一端进行插入，在表的另一端进行删除的线性表。队列具有先进先出（FIFO）特性。a1,

a2,

a3,

a4,…………

an-1,

an队首队尾允许插入的一端称为队尾，用尾指针(rear)指向队尾元素。允许删除的一端称为队首(也称队头)，用队首指针(front)指向队首元素位置。3.4队列的类型定义ADTQueue{

数据对象：

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队列的基本操作：

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

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

DestroyQueue(&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队列类型的实现链队列——链式映象循环队列——顺序映象typedefstruct{//链队列类型

QueuePtrfront;//队头指针

QueuePtrrear;//队尾指针}LinkQueue;a1∧an…Q.frontQ.rearQ.frontQ.rear∧空队列

typedefstructQNode{//结点类型

QElemTypedata;

structQNode*next;

}QNode,*QueuePtr;3.5.1链队列——链式映象LinkQueueQ

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

Q.front=Q.rear=

(QueuePtr)malloc(sizeof(QNode));

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

Q.front->next=NULL;

returnOK;}typedefstruct{//链队列类型

QueuePtrfront;//队头指针

QueuePtrrear;//队尾指针}LinkQueue;

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

p=(QueuePtr)malloc(sizeof(QNode));

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;

if(Q.rear==p)Q.rear=Q.front;

free(p);

returnOK;}#defineMAXQSIZE6//最大队列长度

typedefstruct{QElemType*base;//动态分配存储空间

intrear;//尾指针，若队列不空，指向

队列尾元素的下一个位置

intfront;//头指针，若队列不空，指向队列头元素}SqQueue;SqQueueQ;3.5.2循环队列——顺序映象为何引入循环队列?rearfrontbaseSqQueueQElemType00队空：front？rear队满：front？rear

假溢出Q循环队的入队和出队操作示意图将连续空间的前端和后端连接起来,形成一个环形的顺序表,即把存储队列元素的表从逻辑上看成一个环,称为循环队列。循环队列初始：Q.front=Q.rear=0出队：Q.front=(Q.front+1)％MaxSize入队:Q.rear=(Q.rear+1)％MaxSize引入循环队列如何区分队满与队空?思考：队满?队空?

循环队列引入循环队列如何区分队满与队空?办法1:

队列中留有一个空间队满条件:(Q.rear+1)%MAXQSIZE=Q.front队列空的条件为:

Q.rear=Q.front办法2:

设置标志位S

s=1非空，s=0空队列队列空的条件为

s==0队列满的条件为

(s==1)且Q.rear==Q.front

循环队列s＝0s＝1s＝1初始：Q.front=Q.rear=0初始：Q.front=Q.rear=0s＝0本课件一般采用办法1

[例]

循环队列用数组A[0，MaxSize-1]存放其元素，已知其头尾指针分别是front和rear，则当前队列元素个数为()。

A．(rear—front+MaxSize)％MaxSizeB．rear—front+1C．rear—front