数据结构严蔚敏第3章-课件.ppt

1、数据结构严蔚敏第3章第三章栈和队列数据结构严蔚敏第3章【课前思考】【课前思考】1.什么是线性结构？什么是线性结构？简单地说，线性结构是一个数据元素的序列。2.你见过餐馆中一叠一叠的盘子吗？如果它们是按你见过餐馆中一叠一叠的盘子吗？如果它们是按1,2,n 的次序往上叠的，那么使用时候的次序应的次序往上叠的，那么使用时候的次序应是什么样的？是什么样的？必然是依从上往下的次序，即n,2,1。它们遵循的是后进先出的规律，这正是本章要讨论的栈的结构特点。3.在日常生活中，为了维持正常的社会秩序而出现在日常生活中，为了维持正常的社会秩序而出现的常见现象是什么？的常见现象是什么？是排队。在计算机程序中，模拟

2、排队的数据结构是队列。数据结构严蔚敏第3章【学习目标】【学习目标】1.掌握栈和队列这两种抽象数据类型的特点，并能在相应的应用问题中正确选用它们。2.熟练掌握栈类型的两种实现方法。3.熟练掌握循环队列和链队列的基本操作实现算法。4.理解递归算法执行过程中栈的状态变化过程。数据结构严蔚敏第3章 栈和队列是在程序设计中被广泛使用的两种线性数据结构，因此本章的学习重点在于掌握这两种结构的特点，以便能在应用问题中正确使用。【知识点】【知识点】顺序栈、链栈、循环队列、链队列【重点和难点】【重点和难点】数据结构严蔚敏第3章【学习指南】【学习指南】在这一章中，主要是学习如何在求解应用问题中适当地应用栈和队列，

3、栈和队列在两种存储结构中的实现都不难，但应该对它们了如指掌，特别要注意它们的基本操作实现时的一些特殊情况，如栈满和栈空、队满和队空的条件以及它们的描述方法。本章要求必须完成的算法设计题为：3.15，3.17，3.19，3.22，3.27,3.28，3.30，3.31，3.32。其中前4个主要是练习栈的应用，后4个主要是有关队列的实现方法的练习。数据结构严蔚敏第3章通常称，栈和队列是限定插入和删除插入和删除只能只能在表的“端点端点”进行的线性表。线性表线性表 栈栈 队列队列Insert(L,i,x)Insert(S,n+1,x)Insert(Q,n+1,x)1in+1 Delete(L,i)De

4、lete(S,n)Delete(Q,1)1in栈和队列是两种常用的数据类型栈和队列是两种常用的数据类型数据结构严蔚敏第3章 目目 录录数据结构严蔚敏第3章3.1 栈栈一、栈的定义一、栈的定义 栈栈(stack)(stack)作为一种限定性线性表，是将线性表的插入插入和删除删除运算限制为仅在表的一端仅在表的一端进行。通常将表中允许进行插入、删除操作的一端称为栈顶栈顶(Top)(Top)，因此栈顶的当前位置是动态变化的，它由一个称为栈顶指针的位置指示器指示。同时表的另一端为固定的一端，被称为栈底栈底(Bottom)(Bottom)。当栈中没有元素时称为空栈。栈的插入操作被形象地称为进栈或入栈，删除

5、操作称为出栈或退栈。插入：最先放入栈中元素在栈底，最后放入的元素在栈顶；删除：最后放入的元素最先删除，最先放入的元素最后删除。栈是一种后进先出(Last In First OutLast In First Out)的线性表，简称为LIFO表。数据结构严蔚敏第3章ana2a1进栈出栈栈顶栈底进栈出栈(a)栈的示意图(b)铁路调序栈的表示图图3.1 栈栈ana2a1进栈出栈栈顶栈底进栈出栈(a)栈的示意图(b)铁路调序栈的表示数据结构严蔚敏第3章 例：设一个栈的输入序列为例：设一个栈的输入序列为A,B,C,D,则借助一则借助一个栈所得到的输出序列不可能是个栈所得到的输出序列不可能是 。(A)A,B

6、,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。数据结构严蔚敏第3章二、栈的主要操作二、栈的主要操作 1.初始化栈：初始化栈：InitStack(&S)将栈S置为一个空栈(不含任何元素)。2.进栈：进栈：PUSH(&S,X)将元素X插入到栈S中，也称为“入栈”、“插入

7、”、“压入”。3.出栈：出栈：POP(&S，&e)删除栈S中的栈顶元素，也称为”退栈”、“删除”、“弹出”。4.取栈顶元素：取栈顶元素：GETTOP(S，&e)取栈S中栈顶元素。5.判栈空：判栈空：EMPTY(S)判断栈S是否为空，若为空，返回值为1，否则返回值为0。数据结构严蔚敏第3章三、三、栈的抽象数据类型描述栈的抽象数据类型描述 ADT Stack 数据对象数据对象：D=ai|ai ElemSet，i=1,2,n,n 0 数据关系数据关系：R1=|ai-1,ai D,i=1,2,n 基本操作：基本操作：InitStack(&S)操作前提：S为未初始化的栈。操作结果：将S初始化为空栈。Cl

8、earStack(&S)操作前提：栈S已经存在。操作结果：将栈S置成空栈。StackEmpty(S)操作前提：栈S已经存在。操作结果：若栈S为空，则返回TRUE,否则FALSE。数据结构严蔚敏第3章 StackLength(S)操作前提：栈S已经存在。操作结果：返回S的元素个数即栈的长度。IsFull(S)操作前提：栈S已经存在。操作结果：判栈满函数，若S栈已满，则函数值为TRUE，否则为FALSE。StackTraverse(S,visit()操作前提：栈S已经存在且非空。操作结果：从栈底到栈顶依次对S底每个元素调用函数visit()。一旦visit()失败，则操作失效。数据结构严蔚敏第3章

9、 Push(&S,e)操作前提：栈S已经存在。操作结果：在S的顶部插入(亦称压入)元素e；若S栈未满，将e插入栈顶位置，若栈已满，则返回FALSE，表示操作失败，否则返回TRUE。Pop(&S,&e)操作前提：栈S已经存在。操作结果：删除(亦称弹出)栈S的顶部元素，并用e带回该值；若栈为空，返回值为FALSE，表示操作失败，否则返回TRUE。GetTop(S,&e)操作前提：栈S已经存在。操作结果：取栈S的顶部元素。与Pop(&S,&e)不同之处在于GetTop(S,&e)不改变栈顶的位置。ADT Stack数据结构严蔚敏第3章 1.顺序栈顺序栈 顺序栈是用顺序存储结构实现的栈，即利用一组地址

10、连续的存储单元依次存放一组地址连续的存储单元依次存放自栈底到栈顶的数据元素，同时由于栈的操作的特殊性，还必须附设一个位置指针位置指针toptop（栈顶指针）来动态地指示栈顶元素动态地指示栈顶元素在顺序栈中的位置位置。通常以top=0或 top=-1表示空栈。顺序栈的存储结构可以用C语言中的一维数组来表示。栈的顺序存储结构定义如下：四、四、栈的表示和实现栈的表示和实现 数据结构严蔚敏第3章#define STACK_INIT_SIZE 100/存储空间初始分配量#define STACKINCREMENT 10 /存储空间分配增量typedef struct SElemType*base;/在栈

11、构造前和销毁后base值为NULL SElemType*top;/栈顶指针 int stacksize;SqStack;/当前已分配存储空间或简单定义如下：#define M 100 int sM;int top;数据结构严蔚敏第3章图3.2 顺序栈中的进栈和出栈 Top指向栈顶元素指向栈顶元素初态：初态：top=-1;空栈，栈中无元素，进栈：进栈：top=top+1;stop=x;退栈：退栈：取stop;top=top-1;栈满：栈满：top=M-1;栈溢出（上溢），不能再进栈（错误状态）top=-1时不能退栈，下溢（正常状态，常作控制条件）数据结构严蔚敏第3章（1 1）构造空顺序栈算法）构

12、造空顺序栈算法:初始化栈初始化栈Status InitStack(SqStack&S)/构造一个空栈构造一个空栈 S SS.base=(SElemType*)malloc(STACK_INIT_SIZE*sizeof(SElemType);if(!S.base)exit(OVERFLOW);/为栈分配存储空间失败为栈分配存储空间失败S.top=S.base;/令栈顶指针令栈顶指针 =栈底指针栈底指针/设置栈的当前可使用的最大容量设置栈的当前可使用的最大容量S.stacksize=STACK_INIT_SIZE;return OK;/InitStack/InitStack2.2.顺序栈基本操作的

13、实现如下顺序栈基本操作的实现如下:数据结构严蔚敏第3章程序描述：程序描述：/This program is to initialize a stack#include#include#include#define STACK_INIT_SIZE 100#define STACKINCREMENT 10#define OK 1#define ERROR 0 typedef int SElemType;typedef struct/define structure SqStack()SElemType*base;SElemType*top;int stacksize;SqStack;数据结构严蔚敏

14、第3章 int InitStack(SqStack&S)/InitStack()sub-function S.base=(SElemType)malloc(STACK_INIT_SIZE*sizeof(SElemType);if(!S.base)printf(“Allocate space failure!n“);return(ERROR);S.top=S.base;S.stacksize=STACK_INIT_SIZE;return(OK);/InitStack()end void main()/main()function SqStack S;if(InitStack(S)printf(S

15、uccess!The stack has been created!n“);printf(.OK!n“);getch();数据结构严蔚敏第3章（2）取顺序栈的栈顶元素取顺序栈的栈顶元素 Status GetTop(SqStack S,SElemType&e)/如果栈如果栈 S 空，返回空，返回 ERROR；如果栈；如果栈 S 不空，用不空，用 e 返回栈返回栈 S 的栈的栈顶元素，并返回顶元素，并返回 OK。if(S.top=S.base)return ERROR;/如果栈如果栈 S 为空，则返回为空，则返回 ERROR e=*(S.top-1);/将栈顶指针减将栈顶指针减 1 后所指向的单元

16、内的值赋给后所指向的单元内的值赋给 e return OK;/GetTop/GetTop数据结构严蔚敏第3章（3）将元素压入顺序栈算法（将元素压入顺序栈算法（进栈）进栈）Status Push(SqStack&S,SElemType e)/将元素将元素 e 插入到栈插入到栈 S 中，成为新的栈顶元素中，成为新的栈顶元素 if(S.top-S.base S.stacksize)/如果栈满，则追加存储空间如果栈满，则追加存储空间 S.base=(SElemType S.base=(SElemType*)realloc(S.base,)realloc(S.base,(S.stacksixe+STAC

17、KINCREMENT(S.stacksixe+STACKINCREMENT*sizeof(SElemType);sizeof(SElemType);if(!S.base)exit(OVERFLOW);/if(!S.base)exit(OVERFLOW);/追加存储空间失败追加存储空间失败 S.top=S.base+S.stacksize;/S.top=S.base+S.stacksize;/修改栈顶指针修改栈顶指针 S.stacksize+=STACKINCREMENT;/S.stacksize+=STACKINCREMENT;/修改当前栈的存储空间修改当前栈的存储空间 /if /if 结束结

18、束 *S.top+=e;/S.top+=e;/先将先将 e e 送入栈顶，然后将栈顶指针加送入栈顶，然后将栈顶指针加 1 1 return OK;return OK;/Push/Push数据结构严蔚敏第3章（4）将元素弹出顺序栈算法（将元素弹出顺序栈算法（退栈）退栈）Status Pop(SqStack&S,SElemType&e)/如果栈如果栈 S 空，返回空，返回 ERROR；如果栈；如果栈 S 不空，删除不空，删除 S 栈顶元素，栈顶元素，用用 e 返回其值，并返回返回其值，并返回 OK。if(S.top=S.base)return ERROR;/如果栈如果栈 S 为空，则返回为空，则返

19、回 ERROR e=*-S.top;/先令先令 top 减减 1，再将，再将 top 所指单元值赋给所指单元值赋给 e return OK;/Pop/Pop数据结构严蔚敏第3章（5）判栈空否判栈空否 Int Empty(SqStack S)/如果栈如果栈 S 空，返回空，返回 1；如果栈；如果栈 S 不空，返回不空，返回 0。if(S.top=S.base)return 1;/如果栈如果栈 S 为空，则返回为空，则返回 1else return 0;/如果栈如果栈 S 为空，则返回为空，则返回 0/Empty end数据结构严蔚敏第3章3栈的共享栈的共享有时，一个程序设计中，需要使用多个同一类

20、型的栈,这时候，可能会产生一个栈空间过小，容量发生溢出，而另一个栈空间过大，造成大量存储单元浪费的现象。为了充分利用各个栈的存储空间，这时可以采用多个栈共享存储单元，即给多个栈分配一个足够大的存储空间，让多个栈实现存储空间优势互补。栈 1 顶 栈 2 顶 栈 1 底 栈 2 底 图 3-3 两个栈共享存储单元示意图 栈空：栈空：top1=0,top2=M-1;top1=0,top2=M-1;栈满：栈满：top1+1=top2top1+1=top2数据结构严蔚敏第3章两个栈共享存储单元可用如下两个栈共享存储单元可用如下C C语句描述：语句描述：#define MAXSIZE 100#define

21、 DUSTACKSIZE MAXSIZE typedef struct DuSqStack SElemType dataMAXSIZE;int top1;/top1 is the pointer of DuSqStack S1/top1 is the pointer of DuSqStack S1 int top2;/top2 is the pointer of DuSqStack S2/top2 is the pointer of DuSqStack S2 int flag;DuSqStack;/或：或：#define MAXSIZE 100Struct duseqstack elemtyp

22、e datamaxsize;int top2;/两个栈的栈顶指针两个栈的栈顶指针 int flag;数据结构严蔚敏第3章（1）两个栈共享存储单元的进栈算法）两个栈共享存储单元的进栈算法Status DuSqStackPush(DuSqStack&S,SElemType x)/栈栈 S S 为共享顺序栈类型为共享顺序栈类型 DuSqStackDuSqStack，含，含 top1top1、top2 top2 和和 data data 数组域；数组域；/此算法将元素此算法将元素 x x 放入栈放入栈 S S 中；如果两个栈满，则返回中；如果两个栈满，则返回 ERRORERROR if(S.top1+

23、1)=(S.top2)return ERROR;/如果两个栈满，则返回如果两个栈满，则返回 ERRORERROR else /如果栈未满，则进行入栈操作如果栈未满，则进行入栈操作 if(S.flag!=1)&(S.flag!=2)return ERROR;/如果如果 flag flag 不为不为 1,21,2，则返回，则返回 ERRORERROR else /如果如果 flag flag 为为 1 1 或或 2 2，则入栈，则入栈 switch(S.flag)case 1:/标志位标志位 flag flag 为为 1 1 数据结构严蔚敏第3章 S.dataS.top1=x;/元素元素 x x

24、入栈入栈 S1S1 S.top1+;/修改栈修改栈 S1 S1 的栈顶指针的栈顶指针 break;case 2:/标志位标志位 flag flag 为为 2 2 S.dataS.top2=x;/元素元素 x x 入栈入栈 S2S2 S.top2-;/修改栈修改栈 S2 S2 的栈顶指针的栈顶指针 break;/switch/switch 结束结束 return OK;/else/else 结束结束 /else/else 结束结束/DuSqStackPush/DuSqStackPush数据结构严蔚敏第3章（2）两个栈共享存储单元的退栈算法）两个栈共享存储单元的退栈算法Status DuSqSta

25、ckPop(DuSqStack&S,SElemType&x)/栈栈 S S 为共享顺序栈类型为共享顺序栈类型 DuSqStackDuSqStack，含，含 top1top1、top2 top2 和和 data data 数组域数组域/此算法删除栈此算法删除栈 S S 中栈顶元素，并用中栈顶元素，并用 x x 返回其值；如果栈空，返回其值；如果栈空，则返回则返回 ERRORERRORif(S.flag!=1)&(S.flag!=2)return ERROR;/如果如果 flag1,2flag1,2，则返回，则返回 ERRORERRORelelse /如果如果 flag flag 为为 1 1 或

26、或 2 2，则出栈，则出栈switch(S.flag)case 1:/标志位标志位 flag flag 为为 1 1 if(S.top1 0)/如果栈如果栈 S1 S1 不空，则对不空，则对 S1 S1 进行操作进行操作S.top1-;/修改栈修改栈 S1 S1 的栈顶指针的栈顶指针x=S.dataS.top1;/元素元素 x x 出栈出栈 /if/if 结束结束 数据结构严蔚敏第3章 else return ERROR;/如果栈如果栈 S1 S1 为空，则返回为空，则返回 ERRORERROR break;case 2:/标志位标志位 flag flag 为为 1 1 if(S.top2ne

27、xt=NULL;（b）进栈运算）进栈运算Status Push_L(LinkStack⊤SElemType e)/将元素将元素 e 插入到栈插入到栈 S 中，成为新的栈顶元素中，成为新的栈顶元素 q=(LinkStack)malloc(sizeof(SNode);if(!q)exit(OVERFLOW);/存储分配失败存储分配失败 q-data=e;q-next=top-next;top-next=q;return OK;/Push_L/Push_L数据结构严蔚敏第3章（c）退栈运算）退栈运算Status Pop_L(LinkStack&top,SElemType&e)/如果栈如果栈

28、S 空，返回空，返回 ERROR；如果栈；如果栈 S 不空，删除不空，删除 S 的栈顶元素，的栈顶元素，用用 e 返回其值，并返回返回其值，并返回 OK。if(!top-next)return ERROR;/如果栈如果栈 S 为空，则返回为空，则返回 ERROR e=top-next-data;/取出栈顶元素的值取出栈顶元素的值 q=top-next;/q 指向栈顶元素指向栈顶元素 top-next=q-next;/top-next=q-next;/删除栈顶元素删除栈顶元素 free(q);/free(q);/释放栈顶元素所占的空间释放栈顶元素所占的空间 return OK;return OK

29、;/Pop_L/Pop_L数据结构严蔚敏第3章（d）取栈顶元素）取栈顶元素Status GetTop_L(LinkStack top,SElemType&e)/如果栈如果栈 S 空，返回空，返回 ERROR；如果栈；如果栈 S 不空，用不空，用 e 返回栈返回栈 S 的的栈顶元素，并返回栈顶元素，并返回 OK。if(!top-next)return ERROR;/如果栈如果栈 S 为空，则返回为空，则返回 ERROR else /如果栈如果栈 S 不空，则返回栈顶元素不空，则返回栈顶元素 e=top-next-data;e=top-next-data;return OK;return OK;/

30、else /else 结束结束/GetTop_L/GetTop_L数据结构严蔚敏第3章（5）判栈空）判栈空int empty(LinkStack*top)if(top-next=NULL)return(1);else return(0);数据结构严蔚敏第3章课课 前前 复复 习习设n 个元素的进栈序列是P1，P2，P3，Pn，其输出序列是1,2，3，n，若P1=3，则P2的值()。A、可能是2B、一定是2C、不可能是1D、一定是1 数据结构严蔚敏第3章 一、一、数制转换数制转换 假设要将十进制数N转换为d进制数，一个简单的转换算法是重复下述两步，直到N等于零：X=N mod d (其中mod为

31、求余运算)N=N div d (其中div为整除运算)计算过程从低位到高位，打印输出从高位到低位3.2 3.2 栈的应用举例栈的应用举例 栈在日常生活中和计算机程序设计中有着许多应用，下面仅介绍栈在计算机中的应用。数据结构严蔚敏第3章void Conversion(int N)/*对于任意的一个非负十进制数N，打印出与其等值的8进制数*/Stack S;int x;/*S为顺序栈或链栈*/InitStack(&S);while(N0)x=N%8;Push(&S,x);/*将转换后的数字压入栈S*/N=N/8;while(！StackEmpty(S)Pop(&S,&x);printf(%d,x)

32、;算法算法3.1数据结构严蔚敏第3章二、括号匹配问题二、括号匹配问题 假设表达式中允许包含三种括号假设表达式中允许包含三种括号:圆括号、圆括号、方括号和大括号。编写一个算法判断表达式中的方括号和大括号。编写一个算法判断表达式中的括号是否正确配对。括号是否正确配对。解解:设置一个括号栈设置一个括号栈,扫描表达式：遇到左括号扫描表达式：遇到左括号(包括包括(、和和)时进栈时进栈,遇到右括号时遇到右括号时,若栈是相匹若栈是相匹配的左括号配的左括号,则出栈则出栈,否则否则,返回返回0。若表达式扫描结束若表达式扫描结束,栈为空栈为空,返回返回1表示括号正表示括号正确匹配确匹配,否则返回否则返回0。数据结

33、构严蔚敏第3章 int correct(char exp,int n)char stMaxSize;int top=-1,i=0,tag=1;while(i-1)tag=0;/*若栈不空若栈不空,则不配对则不配对*/return(tag);数据结构严蔚敏第3章三、行编辑程序三、行编辑程序功能：接收用户从终端输入的数据或程序，并存入用户的数据区。算法思想：设输入缓冲区为一个栈结构，每当从终端接收一个字符后先作如下判别：若它既不是退格符（#）也不是退行符（）,则将该字符入栈；若是退格符（#），则从栈顶删去一个字符；若是退行符（），则将栈清空。算法描述如下：算法描述如下：数据结构严蔚敏第3章void

34、 LineEdit()InitStack(s);ch=getchar();While(ch!=EOF)/EOF为全文结束符 while(ch!=EOF&ch!=“n”)switch(ch)case“#”:pop(s,c);break;/当栈非空时退栈 case“”:clearstack(s);break;/重置S为空栈 default:push(s,c);break;/有效字符进栈，但未考虑栈满 ch=getchar();clearstack(s);if(ch!=EOF)ch=getchar();destroystack(s);数据结构严蔚敏第3章五、五、表达式求值表达式求值 表达式求值是高级

35、语言编译中的一个基本问题，是栈的典型应用实例。任何一个表达式都是由操作数(operand)、运算符(operator)和界限符(delimiter)组成的。操作数操作数既可以是常数，也可以是被说明为变量或常量的标识符；运算符运算符可以分为算术运算符、关系运算符和逻辑运算符三类；基基本界限符本界限符有左右括号和表达式结束符等。数据结构严蔚敏第3章1.1.无括号算术表达式求值无括号算术表达式求值 表达式计算表达式计算 程序设计语言中都有计算表达式的问题，这是语言编译中的典型问题。(1)表达式形式：由运算对象、运算符及必要的表达式括号组成；(2)表达式运算：运算时要有一个正确的运算形式顺序。由于某些

36、运算符可能具有比别的运算符更高的优先级，因此表达式不可能严格的从左到右，见图3.5。数据结构严蔚敏第3章图3.5 表达式运算及运算符优先级 数据结构严蔚敏第3章图3.6 无括号算术表达式的处理过程 置空栈OVS、OPTR读字符WW是操作符OPTR栈空W优先级OPTR栈顶优先级取OVS顶、次顶和OPTR顶，形成运算结果T(i),然后退OVS顶、次顶和OPTR顶，将T(i)置入OVS栈顶进OVS进OPTR栈W#结束NYYYNYNN数据结构严蔚敏第3章 2.2.算术表达式处理规则算术表达式处理规则 (1)规定优先级表。(2)设置两个栈：OVS(运算数栈)和OPTR(运算符栈)。(3)自左向右扫描，遇

37、操作数进OVS，遇操作符则与OPTR栈顶优先数比较：当前操作符OPTR栈顶,当前操作符进OPTR栈；当前操作符OPTR栈顶，OVS栈顶、次顶和OPTR栈顶，退栈形成运算T(i)，T(i)进OVS栈。例：实现A/BC+D*E的运算过程时栈区变化情况如图3.7所示。数据结构严蔚敏第3章图3.7 A/BC+D*E运算过程的栈区变化情况示意图 CBAOVS/OPTROPTR生成BC，运算结果T(1)T(1)AOVS/OPTROPTR/生成A/T(1),运算结果T(2)T(2)/OPTR为空，进栈DT(2)右边界#OPTR*生成D*E，运算结果T(3)T(3)T(2)生成T(3)T(2)，得到T(4)T

38、(4)E*右边界#OPTR+*数据结构严蔚敏第3章 3.3.带括号算术表达式带括号算术表达式 假设操作数是整型常数，运算符只含加、减、乘、除等四种运算符，界限符有左右括号和表达式起始、结束符“”，如：（7+15）*（23-28/4）。引入表达式起始、结束符是为了方便。要对一个简单的算术表达式求值，首先要了解算术四则运算的规则，即：(1)从左算到右；(2)先乘除，后加减；(3)先括号内，后括号外。数据结构严蔚敏第3章 运算符和界限符可统称为算符，它们构成的集合命名为OPTR。根据上述三条运算规则，在运算过程中，任意两个前后相继出现的算符1和2之间的优先关系必为下面三种关系之一：12，1的优先权高

39、于2。数据结构严蔚敏第3章表表 3-1 3-1 算符之间的优先关系算符之间的优先关系 数据结构严蔚敏第3章 实现算符优先算法时需要使用两个工作栈：一个称作optr，用以存放运算符；另一个称作opnd，用以存放操作数或运算的中间结果。算法的基本过程如下：首先初始化操作数栈opnd和运算符栈optr，并将表达式起始符“”压入运算符栈；依次读入表达式中的每个字符，若是操作数则直接进入操作数栈opnd，若是运算符，则与运算符栈optr的栈顶运算符进行优先权比较，并做如下处理：数据结构严蔚敏第3章 (1)若栈顶运算符的优先级低于刚读入的运算符，则让刚读入的运算符进optr栈；(2)若栈顶运算符的优先级高

40、于刚读入的运算符，则将栈顶运算符退栈，送入，同时将操作数栈opnd退栈两次，得到两个操作数a、b，对a、b进行运算后，将运算结果作为中间结果推入opnd栈；(3)若栈顶运算符的优先级与刚读入的运算符的优先级相同，说明左右括号相遇，只需将栈顶运算符（左括号）退栈即可。数据结构严蔚敏第3章算法具体描述如下：算法具体描述如下：int ExpEvaluation()/*读入一个简单算术表达式并计算其值。operator和operand分别为运算符栈和运算数栈，OPS为运算符集合*/InitStack(&opnd);InitStack(&optr);Push(&optr,);printf(nnPleas

41、e input an expression(Ending with):);c=getchar();while(c!=|GetTop(optr)!=)/*GetTop()通过函数值返回栈顶元素*/数据结构严蔚敏第3章 if(!In(c,OP)Push(&opnd,c);c=getchar();else switch(Precede(GetTop(optr),c)case:Pop(&optr,&theta);数据结构严蔚敏第3章 Pop(&opnd,&b);Pop(&opnd,&a);v=Execute(a,theta,b);/*对a和b进行op运算*/Push(&opnd,v);break;re

42、turn(GetTop(opnd);例求表达式1+2*3-4/2的值，栈的变化如下。数据结构严蔚敏第3章步骤 操作数栈 运算符栈 说明 开始两栈均为空111进入操作数栈+进入运算符栈2进入操作数栈*进入运算符栈3进入操作数栈退栈2*3进入操作数栈退栈1+6进入操作数栈234567891+12+12+1117+*236+*+数据结构严蔚敏第3章步骤 操作数栈 运算符栈 说明 107-进入运算符栈4进入操作数栈/进入运算符栈2进入操作数栈退栈4/2进入操作数栈退栈7-2进入操作数栈111213141516177 4-7 4-/7 4 2-/77 2-5数据结构严蔚敏第3章当然，算术表达式除了简单求

43、值外，还会涉及到算术表达式的两种表示方法，即中缀表示法和后缀表示法。中缀表达式求值较麻烦（须考虑运算符的优先级，甚至还要考虑圆括号），而后缀表达式求值较方便（无须考虑运算符的优先级及圆括号）。下面将介绍算术表达式的中缀表示和后缀表示及它们的求值规律，例如，对于下列各中缀表达式：（1）3/5+8（2）18-9*(4+3)（3）(25+x)*(a*(a+b)+b)对应的后缀表达式为：(1)3 5 /8 +(2)18 9 4 3 +*-(3)25 x +a a b +*b +*数据结构严蔚敏第3章4.4.中缀表达式变成等价的后缀表达式中缀表达式变成等价的后缀表达式 将中缀表达式变成等价的后缀表达式，

44、表达式中操作数次序不变，运算符次序发生变化，同时去掉了圆括号。转换规则是：设立一个栈，存放运算符，首先栈为空，编译程序从左到右扫描中缀表达式，若遇到操作数，直接输出，并输出一个空格作为两个操作数的分隔符；若遇到运算符，则必须与栈顶比较，运算符级别比栈顶级别高则进栈，否则退出栈顶元素并输出，然后输出一个空格作分隔符；若遇到左括号，进栈；若遇到右括号，则一直退栈输出，直到退到左括号止。当栈变成空时，输出的结果即为后缀表达式。将中缀表达式(1+2)*(8-2)/(7-4)变成等价的后缀表达式。现在用栈来实现该运算，栈的变化及输出结果如下数据结构严蔚敏第3章步骤栈中元素 输出结果 说明1(（进栈2(1

45、输出13(+1+进栈4(+1 2输出25 1 2 +退栈输出，退栈到（止6*1 2 +*进栈7*(1 2 +（进栈8*(1 2 +（进栈9*(1 2 +8输出810*(-1 2 +8 -进栈数据结构严蔚敏第3章11*(-1 2 +8 2输出212*(1 2 +8 2 -退栈输出，退栈到（止13*(/1 2 +8 2 -/进栈14*(/(1 2 +8 2 -（进栈15*(/(1 2 +8 2 -7输出716*(/(-1 2 +8 2 -7-进栈17*(/(-1 2 +8 2 -7 4输出418*(/1 2 +8 2 -7 4 -退栈输出，退栈到（止19*1 2 +8 2 -7 4 -/退栈输出，

46、退栈到（止20 1 2 +8 2 -7 4 -/*退栈并输出步骤 栈中元素 输出结果 说明数据结构严蔚敏第3章5.5.后缀表达式的求值后缀表达式的求值 将中缀表达式转换成等价的后缀表达式后，求值时，不需要再考虑运算符的优先级，只需从左到右扫描一遍后缀表达式即可。具体求值步骤为：设置一个栈，开始时，栈为空，然后从左到右扫描后缀表达式，若遇操作数，则进栈；若遇运算符，则从栈中退出两个元素，先退出的放到运算符的右边，后退出的放到运算符左边，运算后的结果再进栈，直到后缀表达式扫描完毕。此时，栈中仅有一个元素，即为运算的结果。例，求后缀表达式：1 2 +8 2 -7 4 -/*的值，栈的变化情如下：数据

47、结构严蔚敏第3章步骤栈中元素 说明111进栈21 22进栈3 遇+号退栈2和1431+2=3的结果3进栈53 88进栈63 8 22进栈73遇-号退栈2和883 68-2=6的结果6进栈93 6 77进栈103 6 7 44进栈数据结构严蔚敏第3章步骤栈中元素 说明113 6遇-号退栈4和7123 6 37-4=3的结果3进栈133遇/号退栈3和6143 26/3=2的结果2进栈15 遇*号退栈2和31663*2=6进栈176扫描完毕，运算结束 从上可知，最后求得的后缀表达式之值为6，与用中缀表达式求得的结果一致，但后缀式求值要简单得多。数据结构严蔚敏第3章五、五、求解迷宫问题求解迷宫问题 求

48、迷宫问题就是求出从入口到出口的路径。在求迷宫问题就是求出从入口到出口的路径。在求解时求解时,通常用的是通常用的是“穷举求解穷举求解”的方法的方法,即从入即从入口出发口出发,顺某一方向向前试探顺某一方向向前试探,若能走通若能走通,则继续往则继续往前走；否则沿原路退回前走；否则沿原路退回,换一个方向再继续试探换一个方向再继续试探,直至所有可能的通路都试探完为止。为了保证在直至所有可能的通路都试探完为止。为了保证在任何位置上都能沿原路退回任何位置上都能沿原路退回(称为回溯称为回溯),),需要用一需要用一个后进先出的栈来保存从入口到当前位置的路径。个后进先出的栈来保存从入口到当前位置的路径。首先用如图

49、首先用如图3.33.3所示的方块图表示迷宫。对所示的方块图表示迷宫。对于图中的每个方块于图中的每个方块,用空白表示通道用空白表示通道,用阴影表示用阴影表示墙。所求路径必须是简单路径墙。所求路径必须是简单路径,即在求得的路径上即在求得的路径上不能重复出现同一通道块。不能重复出现同一通道块。数据结构严蔚敏第3章数据结构严蔚敏第3章 为了表示迷宫为了表示迷宫,设置一个数组设置一个数组mg,其中每个元素表示其中每个元素表示一个方块的状态一个方块的状态,为为0时表示对应方块是通道时表示对应方块是通道,为为1时表示时表示对应方块为墙对应方块为墙,如图如图3.3所示的迷宫所示的迷宫,对应的迷宫数组对应的迷宫

50、数组mg如下如下:int mgM+1N+1=/*M=10,N=10*/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;数据结构严蔚敏第3章while(while(栈不空栈不空)若当前位置可通若当前位置可通，则则 将当前位置插入栈顶；将当前位置插入栈