数据结构课件栈和队列2009级

第三章栈和队列

第三章栈和队列

3.1栈

3.2栈的应用举例

3.3栈与递归

3.4队列

3.5队列的应用3.1栈3.1.1栈的概念

3.1.2栈的顺序存储和实现

3.1.3栈的链式存储和实现

3.1.1栈的概念栈是限定仅能在表尾一端进行插入、删除操作的线性表；（a1,a2,...ai,…,an-1,an

）插入删除ana2a1栈的特点后进先出又称为后进先出表（LIFO表Last_inFirst_out)出栈进栈栈顶栈底ana2a13.1.1栈的概念栈的应用火车调度123基本操作初始化操作InitStack(&S)

功能：构造一个空栈S。销毁栈操作DestroyStack(&S)

功能：销毁一个已存在的栈。置空栈操作ClearStack(&S)

功能：将栈S置为空栈。判空操作StackEmpty(S)

功能：若栈S为空，则返回True，否则，栈不空返回False。ana2a1栈顶栈底

取栈顶元素操作GetTop(S,&e)

功能：取栈顶元素，并用e返回。

进栈操作Push(&S,e)

功能：元素e进栈。

退栈操作Pop(&S,&e)

功能：栈顶元素退栈，并用e返回。ana2a1栈顶栈底3.1.2栈的顺序存储和实现出栈进栈栈顶栈底ana2a1

顺序栈的类型定义#defineSTACK_INIT_SIZE100#defineSTACKINCREMENT10typedefstruct{

ElemType*base;//动态数组基址

intstacksize;//栈空间大小

}SqStack;SqStackS;ElemType*top//栈顶指针出栈进栈栈顶栈底ana2a1S.stacksizeS.topS.base

an

an-1a2a110099 n-110topbaseaabcdab空栈

a进栈

b,c,d进栈d,c出栈topbasetopbasetopbase

顺序栈的基本操作算法

约定：栈顶指针示栈顶元素的下一个位置

初始化操作InitStack(&S)功能：建空栈S.stacksizeS.topS.base100

99 n-110StatusInitList_Sq(SqStack&S){//建立空顺序栈S

S.base=(ElemType*)malloc(STACK_INIT_SIZE*sizeof(ElemType));

//为顺序栈动态分配存储空间

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

S.top=S.base;//栈顶指针初始化

S.stacksize=STACK_INIT_SIZE;returnOK;}//InitList_Sq

算法时间复杂度：O(1)S.stacksizeS.topS.base

an

an-1a2a110099 n-1100

销毁栈操作DestroyStack(&S)

功能：销毁一个已存在的栈NULLNULLStatusDestroyStack(SqStack&S){//销毁一个已存在的栈

free(S.base);

//释放栈空间

S.base=S.top=NULL;

S.stacksize=0;

returnOK;}//DestroyStack

置空操作ClearStack(&S)功能：将已存在的栈S，置成空栈99 n-110S.stacksizeS.topS.base

an

an-1a2a110099 n-110S.stacksizeS.topS.base

an

an-1a2a1100置空StatusDestroyStack(SqStack&S){//销毁一个已存在的栈

S.top=NULL;

//释放栈空间

returnOK;}//DestroyStack

进栈操作

Push(&S,e)

e进栈前e进栈后功能：将元素e压入栈顶S

an

an-1a2a1100

99 n-110S

ean

an-1a2a1100

99 n-110*S.top=e;S.top++;StatusPush(SqStack&S,ElemTypee){

//将元素e插入栈顶

*S.top=e;S.top++;

//元素e插入栈顶，修改栈顶指针

returnOK;

}//Pushif(S.top-S.base==S.stacksize)//栈满

{newbase=(ElemType*)realloc(S.base,

(S.stacksize+STACKINCREMENT)*sizeof(ElemType));

if(!newbase)exit(OVERFLOW);S.base=newbase;S.top=S.base+S.stacksize;

S.stacksize+=STACKINCREMENT;}//if

出栈操作

Pop(&S,&e)功能：栈顶元素退栈，并用e返回。出栈操作前出栈操作后eanS

an

an-1a2a110099 n-110S

an

an-1a2a110099 n-110--S.top;e=*S.top;StatusPop(SqStack&S,ElemType&e){//删除栈顶元素，并用e返回其值

if(S.top==S.base)returnERROR;//栈空

--S.top;e=*S.top;

//读取栈顶元素，修改栈顶指针

returnOK;

}//PopS

an

an-1a2a110099 n-1103.1.3栈的链式存储和实现Sanan-1a1栈底栈顶typedefstructLNode{

ElemTypedata;

StructSNode*next;

}SNode,*SLinkList;SLinkListS；

//S栈顶指针3.1.3栈的链式存储和实现出栈e栈顶Sanan-1a1栈底e入栈栈顶Sanan-1a1栈底顺序栈和链式栈的比较栈的特点：后进先出时间效率所有操作都时间复杂度都是O(1)顺序栈和链式栈在时间效率上难分伯仲空间效率顺序栈须说明一个固定的长度链式栈的长度可变，但增加结构性开销

3.2栈的应用举例迷宫求解——搜索(深度优先)行编辑程序表达式括号匹配的检验表达式求值实现递归其它退栈进栈栈顶栈底ana2a1

数制转换十进制数到八进制数的转换算法基于下面整数性质

N=(Ndivd)×d+

Nmodd43=5×8+3

例(1348)10=(2504)8

，其运算过程如下:=2×83+5×82+0×8+4

=(2504)8

=(21×8+0)×8+4

=(2×8+5)×8+0)×8+4

=168×8+41348=(1348div8)×8+1348mod8

voidconversion(){//输入一个非负十进制数，输出八进制数

InitStack(S);//建空栈

scanf(“%d”,N);//输入一个非负十进制整数

while(N){//N不等于零循环

Push(S,N%8);//余数进栈

N=N/8;//整除运算,N=商

}

while(!StackEmpty){//输出栈中的八制数位

Pop(S,e);Printf(“%d”,e);

}

DestroyStack(S);//释放栈空间

}//conversion

迷宫问题输入数据：迷宫结果数据：从入口到出口的一条路径入口出口1234入口出口1234迷宫问题迷宫问题求解迷宫问题的基本步骤若当前位置“可通”,则纳入路径,继续探索；若当前位置“不可通”,换个方向继续探索；若四周“均已探索”，则后退一步,换个方向继续探索;入口出口1234括号匹配问题在表达式中，正确的格式（［］（））［（［］［］）］在表达式中,不正确的格式：［（］）（））（（）main(){…x=2;y=3;

z=x*x+y*y;}表达式求值-算符优先算法表达式的构成

表达式::=操作数+运算符+界符5+6(1+2)–4212355+6(1+2)–42表达式的求值

(数学上)4=5+63-42=5+18-42=23-42=23-8=151）确定表达式中算符运算顺序

2）按照算符的运算顺序进行计算算符优先关系表(1、2是相邻算符,1

左,2右)

1、2的优先关系有：1<2

1=2

1>22

1

+-*/()#>><<<>>>

><<<>>>>>><>>>>>><>><<<<<=>>>>>><<<<<=+-*/()##5+6(1+2)-42#表达式求值基本思路+(

从左向右扫描表达式:#5+6(1+2)-42

•

遇操作数——保存

•

遇运算符j

——与左运算符i比较

–若i<j

则保存

–若i>j

则i可进行运算；

–若i=j

需要消去括号；5612+<<<#<>后保存运算符优先级高OPTR栈#OPND栈5+6×(1+25

读入表达式：+6×(1+2)-4#1+2=36×3=185+18=2323-8=15表达式求值示意图（算符优先算法）1823-15×24×2=84×832

算符优先算法OperandTypeEvaluateExpression(){//算术表达式求值的算符优先算法。设OPTR和OPND分别为运算符栈和操作数栈，OP为运算符集合。

InitStack(OPTR);Push(OPTR,#);InitStack(OPND);c=getchar();//读入算术表达式

while(c!=‘#’||GetTop(OPTR)!=‘#’){if(!In(c,OP))//若为操作数进栈OPND{Push(OPND,c);c=getchar()}else{//若为运算符

switch(Precede(GetTop(OPTR),c)){case<://运算符进栈并接收下一字符

Push(OPTR,c);c=getchar();break;case=://脱括号并接收下一字符

Pop(OPTR,x);c=getchar();break;case>:Pop(OPTR,theta);Pop(OPND,b);Pop(OPND,a);Push(OPND,Operate(a,theta,b));break;}//switch}//if}//whilereturnGetTop(OPND);}//EvaluateExpression

中缀表达式5+6(1+2)–425612++42

-1234

后缀表达式

前缀表达式-+56+12421234

表达式的三种表达方式55例求解n!的递归函数

intfact(intn){if(n==1)return1;elsereturn(n*fact(n-1));}3.3栈与递归A(){…A();…}递归函数递归函数的执行过程中栈的作用函数的调用数据传递控制转移main(){intn=3;f(n);}intf(intn){r=1;for(i=1;i<=n;i++)

r=r*i;return(r);}调用返回递归函数的执行过程中栈的作用主调函数时涉及的数据函数实参返回地址被调函数涉及的数据函数形参局部变量函数返回值函数数据区参数返回地址等局部变量递归函数的执行过程中栈的作用(被调)函数数据区的分配对于非递归函数，数据区的分配可以在程序运行前进行，直到整个程序运行结束才释放，这种分配称为静态分配。内存代码区域全程/静态区域动态区域intf(intn){r=1;for(i=1;i<=n;i++)

r=r*i;return(r);}main(){intn=3;f(n);}main(){intn=3;fact(n);}intfact(intn){if(n==1)return(1);

elsereturn(n*fact(n-1));}调用n=3返回intfact(intn){if(n==1)return(1);

elsereturn(n*fact(n-1));}调用n=2返回参数返回地址等局部变量递归函数的执行过程中栈的作用函数数据区的分配对于递归函数，必须每调用一次就分配一块新的数据区，以存放当前函数所使用的数据，当函数结束返回时随即释放。即所谓的动态分配。代码区域全程/静态区域动态区域内存

函数返回顺序main()fac