数据结构基础（第五版） 课件 第04章 栈

第4章栈第4章栈4.1栈的定义和操作4.2栈的存储和实现4.2.1顺序栈4.2.2链式栈4.3栈的应用举例4.3.1进制转换4.3.2表达式转换和求值——中缀表达式转后缀并求值4.3.3函数调用栈4.3.4非递归求解Hanoi问题4.3.5递归函数的展开分析2重难点栈和线性表、队列的关系——操作受限的含义顺序栈的定义及相关操作链式栈的定义及相关操作利用栈的特点解决应用问题中缀表达式转后缀并求值函数调用及递归的本质——系统栈(栈内存区、栈帧)递归问题的非递归实现——使用自定义栈34.1栈的定义和操作栈(stack)的定义：栈是一个操作受限的线性表。栈是限制在表的一端进行插入和删除的线性表。允许插入和删除的一端称为栈顶(top)，另一端称为栈底(bottom)特点：后进先出(LIFO)或先进后出(FILO)只在表的一端(栈顶)进行插入和删除操作4

topbottom4.1栈的定义和操作生活中的栈54.1栈的定义和操作栈的基本操作1．进栈：intpush(&s,x)2．出栈：intpop(&s,&x)3．读取栈顶元素：intreadTop(s,&x)4.判栈空：int

isSEmpty(s)5.

判栈满：int

isSFull(s)6.显示栈元素：voidshowStack(s)64.2栈的存储和实现——顺序栈顺序栈——用一组地址连续的存储单元(数组)依次存放从栈底到栈顶的元素，同时附设一个栈顶指针，用来指示栈顶元素在栈中的位置。7栈底(bottom)栈顶(top)栈底栈顶栈底栈顶4.2栈的存储和实现——顺序栈伪代码4-1固定长度顺序栈的定义和初始化8#defineN40typedef

struct{

ElemTypedata[N]; //data数组中存放进栈元素

inttop;

//top指示栈顶元素的位置}SeqStack;

//定义顺序栈的类型SeqStackvoidinit(SeqStack&s){

s.top=-1;

} //初始化顺序栈为空intmain(){

SeqStackstack;//stack为局部变量，存放于栈内存区

init(stack);

//...... //后续操作

return

0;}左侧代码中stack的内存布局若将栈的空间置于堆内存区topbottom4.2栈的存储和实现——顺序栈伪代码4-2动态分配顺序栈的定义和初始化9#defineN40typedef

struct{

ElemType*pData;//pData所指数组中存放进栈元素

int

stackSize;

//stackSize记录pData所指数组的长度

int

top;

//top指示栈顶元素的位置}SeqStack;

//定义顺序栈的类型SeqStackvoidinit(SeqStack&s){

//动态分配pData所指的数组空间

s.pData=(ElemType*)malloc(sizeof(ElemType)*N);

s.stackSize=N; //当前栈中数组的长度为N

s.top=-1;

//初始化顺序栈为空}4.2栈的存储和实现——顺序栈伪代码4-2动态分配顺序栈的定义和初始化10intmain(){

//stack为局部变量，存放于栈内存区

SeqStackstack;

//开辟空间并初始化顺序栈stack为空

init(stack);

//......//后续操作

return

0;}4.2栈的存储和实现——顺序栈顺序栈的基本操作伪代码4-3顺序栈的判栈空11intisSEmpty(SeqStacks)//判断顺序栈s是否为空{

if(s.top==-1)

return

1; //栈为空，则返回1

else

return

0; //否则，返回0}4.2栈的存储和实现——顺序栈顺序栈的基本操作伪代码4-4顺序栈的判栈满12intisSFull(SeqStacks)//判断顺序栈s是否为满{

if(s.top==s.stackSize-1)

return

1; //栈为满，则返回1

else

return

0; //否则，返回0}4.2栈的存储和实现——顺序栈顺序栈的基本操作伪代码4-5顺序栈的进栈操作13//进栈一个元素x到顺序栈s中intpush(SeqStack&s,ElemTypex){

//如果栈已满，则不能继续进栈

if(isSFull(s))

return

0; //进栈失败，返回0

//先让s.top自增，再将进栈元素存入s.top指示的位置

s.top=s.top+1;

s.pData[s.top]=x;

return

1; //进栈成功，返回1}4.2栈的存储和实现——顺序栈顺序栈的基本操作伪代码4-6顺序栈的出栈操作14//从顺序栈s中出栈一个元素给xintpop(SeqStack&s,ElemType&x){

if(isSEmpty(s))

//如果栈为空

return

0;

//出栈失败

x=s.pData[s.top];

//通过x带回出栈元素

s.top--;

//栈顶指针自增

return

1;

//出栈成功}4.2栈的存储和实现——顺序栈顺序栈的基本操作伪代码4-7读取顺序栈的栈顶元素(栈中内容、栈顶指针均不变)15//读取顺序栈s的栈顶元素给xintreadTop(SeqStacks,ElemType

&x){

if(s.top==-1)

//如果栈为空

return

0;

//读取栈顶失败

x=s.pData[s.top];

//通过x带回栈顶元素

return

1;

//读取栈顶成功}返回值一定是整型么？这份代码是错误的！DataTypereadTop(SeqStacks){

if(isEmpty(s)) //若栈空，则返回0

return

0;

else

//否则返回栈顶元素

return

s.data[s.top];}下面这种读取栈顶元素的方法怎么样？上面函数的调用形式：intstatus=readTop(stack,ret);4.2栈的存储和实现——顺序栈顺序栈的基本操作伪代码4-7读取顺序栈的栈顶元素(栈中内容、栈顶指针均不变)16//读取顺序栈s的栈顶元素给*pxintreadTop(SeqStacks,ElemType*px){

if(s.top==-1)

//如果栈为空

return

0;

//读取栈顶失败

*px=s.pData[s.top];

//通过x带回栈顶元素

return

1;

//读取栈顶成功}上面函数的调用形式：intstatus=readTop(stack,&ret);4.2栈的存储和实现——链式栈伪代码4-8链式栈的定义及初始化17typedef

struct_StackNode{

ElemTypedata;

//数据域

struct_StackNode*next; //指针域}StackNode;

//定义链式栈的结点类型StackNodetypedef

struct{

StackNode*top; //栈顶指针}LinkStack;

//定义链式栈的类型LinkStackvoidinit(LinkStack&s){

s.top=NULL; //初始化链式栈为空}4.2栈的存储和实现——链式栈伪代码4-8链式栈的定义及初始化18intmain(){

LinkStackstack; //stack为局部变量，存放于栈内存区

init(stack);

//初始化链式栈stack为空

//...... //后续操作

return

0;}图中的s为stack的引用，因此s.top即为stack.top。4.2栈的存储和实现——链式栈链式栈的基本操作伪代码4-9链式栈的判栈空19intisSEmpty(LinkStacks) //判断链式栈s是否为空{

if(s.top==NULL)

return

1; //栈为空，则返回1

else

return

0; //否则，返回0}4.2栈的存储和实现——链式栈链式栈的基本操作伪代码4-10链式栈的进栈操作20voidpush(LinkStack&s,ElemTypex)//将元素x进栈到s中{

StackNode*pNew;

//给待进栈的新结点开辟空间

pNew=(StackNode*)malloc(sizeof(StackNode));

pNew->data=x;

//构造待进栈的新结点

pNew->next=s.top; //将新结点插入到原栈顶结点之前

s.top=pNew;

//新结点成为新的栈顶结点}

∧s.topxpNew4.2栈的存储和实现——链式栈链式栈的基本操作伪代码4-11链式栈的出栈操作21//从栈s中出栈一个元素，将其赋值给xintpop(LinkStack&s,ElemType&x){

StackNode*p;

if(isSEmpty(s)) //如果栈为空

return

0;

//出栈失败，返回0

p=s.top;

s.top=p->next; //设置新的栈顶结点

x=p->data;

//用x带回出栈元素的值

free(p);

//释放原栈顶结点的空间

return

1;

//出栈成功，返回1}

∧s.top

p4.2栈的存储和实现——链式栈链式栈的基本操作伪代码4-12显示链式栈中的所有元素22voidshowLinkStack(LinkStacks)//显示栈中所有元素{

StackNode*p;

if(s.top==NULL)

{

printf("当前链式栈为空！\n");

return;

}

for(p=s.top;p!=NULL;p=p->next)

{

printf("%s\t%s\t%c\t%d\t%.2f\n",

p->data.stuId,p->data.name,

p->data.gender,p->data.age,p->data.score);

}}假设栈中元素的类型为Student4.3栈的应用举例4.3.1进制转换4.3.2表达式转换和求值中缀表达式转后缀(运算符栈)后缀表达式求值(运算数栈)4.3.3函数调用栈4.3.4非递归求解Hanoi问题4.3.5递归函数的展开分析234.3.1进制转换

24商余数∴(138)10

=(10001010)24.3.1进制转换伪代码4-13十进制整数num，转换为base进制25voidconversion(intnum,intbase){

intx;

SeqStacks;

init(s); //初始化栈

while(num>0)

{

push(s,num%base); //除base取余

num=num/base; //将num更新为商

}

printf("转换后的%d进制值为：",base);

while(pop(s,x))//出栈成功，则执行循环

{

charb=x>=10?x-10+'A':x+'0';

printf("%c",b);//出栈元素，转成字符后，直接输出

}}4.3.1进制转换——非负十进制整数，转为二进制形式voiddec2binV1(intn){

SeqStacks;

int

e;

initSeqStack(s);

while(n) //依次进栈，直到商为0

{

push(s,n%2);

n=n/2;

}

while(!isSEmpty(s)) //依次出栈，直到栈空

{

pop(s,e); //参数e为引用

printf("%d",e);

}}264.3.1进制转换——非负十进制整数，转为二进制形式intdec2binV2(intn,intbin[]){

SeqStacks;

int

e,i=0;

initSeqStack(s);

while(n) //依次进栈，直到商为0

{

push(s,n%2);

n=n/2;

}

while(!isEmpty(s)) //依次出栈，直到栈为空

{

pop(s,e);

bin[i++]=e; //printf("%d",e);

}

return

i;}274.3.1进制转换——非负十进制整数，转为任意进制intdec2anyBase(intn,int

base,char

ret[]){

SeqStacks;

int

e,i=0;

initSeqStack(s);

while(n) //依次进栈，直到商为0

{

push(s,n%base);

n=n/base;

}

while(!isEmpty(s)) //依次出栈，直到栈为空

{

pop(s,e);

//pop(s,&e);

ret[i++]=e<10?e+'0':e-10+'A';

}

return

i;}284.3.2表达式转换和求值一个表达式由操作数(也称运算对象)、操作符

(也称运算符)和分界符(括号)组成。算术表达式举例：(a+b)*(c–d)–d/e29a+b左操作数右操作数双目运算符运算规则：先算乘除，后算加减；先算括号内，后算括号外；从左到右，依次计算。4.3.2表达式转换和求值算术表达式的三种表示形式：中缀(infix)表达式<操作数><操作符><操作数>，如A+B前缀(prefix)表达式<操作符><操作数><操作数>，如+AB运算符放在操作数的前面，又称为波兰式后缀(postfix)表达式<操作数><操作数><操作符>，如AB+运算符放在操作数的后面，又称为逆波兰式304.3.2表达式转换和求值——中缀表达式转后缀中缀表达式：(a+b)*(c–d)–e/f等价的后缀表达式：ab+cd–*ef/–等价的前缀表达式：–*+ab–cd/ef后缀和前缀表达式的共同特点是：表达式中没有括号，运算符不存在优先级的差别。314.3.2表达式转换和求值——中缀表达式转后缀中缀表达式(6+22)/4-(17-(9-4))/332对应的后缀表达式622+4/1794--3/-如果没有括号，运算顺序将完全不同6+22/4-17-9-4/36+22/4-17-9-4/3对应的后缀表达式6224/

+

17

-

9

-

4

3

/

-4.3.2表达式转换和求值——中缀表达式转后缀中缀表达式(6+22)/4-(17-(9-4))/333对应的后缀表达式622+4/1794--3/-如果没有括号，运算顺序将完全不同6+22/4-17-9-4/36+22/4-17-9-4/3对应的后缀表达式6224/

+

17

-

9

-

4

3

/

-4.3.2表达式转换和求值——中缀表达式转后缀中缀表达式转后缀的过程从左向右扫描中缀表达式；遇到运算对象时，直接输出到后缀表达式遇到运算符时，和栈顶运算符比较优先级栈为空，当前运算符进栈；栈顶为左括号，当前运算符进栈；栈顶运算符优先级低，当前运算符进栈；栈顶运算符优先级较高或相等，应一直出栈并输出，直到栈为空或栈顶运算符的优先级较低，然后再将当前运算符进栈。中缀表达式：(6+22)/4–(17–(9–4))/3后缀表达式：34543210622+4/1794––3/–(6+22)/4–(17–(9–4))/3遇到运算符为右括号时一直出栈并输出，直到左括号出栈并丢弃；运算符栈4.3.2表达式转换和求值——中缀表达式转后缀3552+94–*183/–52①5+2=7794②9–4=55③7*5=3535183④18/3=6629⑤35-6=29运算数栈出栈运算时，先出栈的元素放后面，后出栈的元素放前面。4.3.2表达式转换和求值——后缀表达式求值后缀表达式求值的过程从左向右扫描后缀表达式；遇到运算对象时，直接进栈遇到运算符时，就出栈两个操作数进行计算3652+94-*183/-94-751833567*183/-=183/-=35-===29该后缀表达式对应的中缀表达式(5+2)*(9–4)–18/3*/-后缀表达式：4.3.3函数调用栈374.3.3函数调用栈——函数的递归调用为什么使用递归调用使用递归编写程序，使许多复杂的问题大大简化。递归是程序设计中的一个强有力的工具。以下三种情况常用到递归问题的定义是递归的数据结构是递归的问题的解法是递归的384.3.3函数调用栈——递归调用工作栈函数的调用和返回，导致栈内存中栈帧的变化递归——函数自己调用自己每次调用自己，都跳转到同一份代码的开头；每个栈帧中，记录不同的执行现场。394.3.4非递归求解Hanoi问题——尾递归和非尾递归两种方法求n的阶乘如果函数中所有的递归调用都在函数末尾，则称这种情况为尾递归。尾递归一般很容易改写为非递归形式，即改用循环来实现。40intfac(intn){

if(n==0||n==1)

return

1;

returnn*fac(n-1);}intfac(intn){

inti,ret=1;

for(i=1;i<=n;i++)

ret*=i;

returnret;}伪代码4-14递归求n的阶乘伪代码4-15用循环求n的阶乘

4.3.4非递归求解Hanoi问题——尾递归和非尾递归两种方法求斐波那契(Fibonacci)数列41int

fibV1(intn){

if(n<=1)

return

1;

return

fibV1(n-1)+fibV1(n-2);}伪代码4-16末尾递归调用自己两次int

fibV2(intn,intnum1,intnum2){

if(n<=1)

returnnum2;

return

fibV2(n-1,num2,num1+num2);}伪代码4-17末尾递归调用自己一次

求斐波那契(Fibonacci)数列的函数，也可以仅用循环，即可实现非递归。4.3.4非递归求解Hanoi问题——尾递归和非尾递归斐波那契(Fibonacci)数列递归调用的示意图42fib(3)fib(4)fib(2)fib(2)fib(1)fib(1)fib(0)fib(1)fib(0)＋＋＋＋101211310源杆中间杆(临时杆)目标杆4.3.4非递归求解Hanoi问题——非尾递归(必须用栈)Hanoi问题源杆上有n个盘子(顺序：大的在下，小的在上)n个盘子要全部移动到目标杆上移动过程中始终保证大的盘子在下，小的盘子在上每次只能移动一个盘子，移动过程中能借助临时杆求盘子的移动顺序。434.3.4非递归求解Hanoi问题——非尾递归(必须用栈)伪代码4-18递归求解Hanoi问题44voidhanoi(intn,charx,chary,charz){

static

ints=1;

if(n==1)//如果只有一个盘子

printf("第%d步：%c-->%c\n",s++,x,z);

else

{

//先移动上面的n-1个盘子到中间杆

hanoi(n-1,x,z,y);

//再移动最下面的那个盘子到目标杆

printf("第%d步：%c-->%c\n",s++,x,z);

//最后将n-1个盘子从中间杆移动到目标杆

hanoi(n-1,y,x,z);

}}4.3.4非递归求解Hanoi问题——非尾递归(必须用栈)454.3.4非递归求解Hanoi问题——非尾递归(必须用栈)464.3.5递归函数的展开分析程序4-2递归函数recursion()47#include<stdio.h>void

recursion(){

charc=getchar();

putchar(c);

if(c!='*')

recursion();

putchar(c);}intmain(){

recursion();

return

0;}//若输入为ABC*，请分析并写出输出结果。4.3.5递归函数的展开分析48补充：表达式中括号匹配的检验括号配对的三种失配情况：当扫描到右括号时，栈为空——无左括号相配；栈不为空，但右括号与当前栈顶元素不配对；扫描结束，但栈不空——有剩余左括号未匹配完。49补充：表达式中括号匹配的检验括号匹配的过程50(…{…}…)…[…{…(…)...

[…]