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

《数据结构严蔚敏ppt课件第3章.ppt》由会员分享，可在线阅读，更多相关《数据结构严蔚敏ppt课件第3章.ppt（109页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

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

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

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

4、的数据类型栈和队列是两种常用的数据类型3.1 栈栈3.2 栈的应用举例栈的应用举例3.4 队列队列 目目 录录3.3 栈与递归的实现栈与递归的实现3.1 栈栈一、栈的定义一、栈的定义 栈栈(stack)(stack)作为一种限定性线性表，是将线性表的插入插入和删除删除运算限制为仅在表的一端仅在表的一端进行。 通常将表中允许进行插入、删除操作的一端称为栈顶栈顶(Top)(Top)，因此栈顶的当前位置是动态变化的，它由一个称为栈顶指针的位置指示器指示。同时表的另一端为固定的一端，被称为栈底栈底(Bottom)(Bottom)。当栈中没有元素时称为空栈。栈的插入操作被形象地称为进栈或入栈，删除操作称

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

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

7、(&S，&e) 删除栈S中的栈顶元素，也称为”退栈”、 “删除”、 “弹出”。4.取栈顶元素：取栈顶元素： GETTOP(S，&e)取栈S中栈顶元素。5.判栈空：判栈空： EMPTY(S)判断栈S是否为空，若为空，返回值为1，否则返回值为0。三、三、栈的抽象数据类型描述栈的抽象数据类型描述 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初始化为空栈。 ClearStack(

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

9、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 1. 顺序栈顺序栈 顺序栈是用顺序存储结构实现的栈，即利用一组地址连续的存储单元

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

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

12、tus 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; / I

13、nitStack/ InitStack2.2.顺序栈基本操作的实现如下顺序栈基本操作的实现如下: :程序描述：程序描述：/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; S

14、ElemType *top; int stacksize; SqStack; 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

15、() /main() function SqStack S; if (InitStack(S) printf (Success! The stack has been created !n“); printf (.OK!n“); getch(); （2） 取顺序栈的栈顶元素取顺序栈的栈顶元素 Status GetTop ( SqStack S, SElemType &e ) / 如果栈如果栈 S 空，返回空，返回 ERROR；如果栈；如果栈 S 不空，用不空，用 e 返回栈返回栈 S 的栈的栈顶元素，并返回顶元素，并返回 OK 。if ( S.top = = S.base ) return E

16、RROR; / 如果栈如果栈 S 为空，则返回为空，则返回 ERROR e = *( S.top - 1); / 将栈顶指针减将栈顶指针减 1 后所指向的单元内的值赋给后所指向的单元内的值赋给 e return OK; / GetTop / GetTop（3）将元素压入顺序栈算法（将元素压入顺序栈算法（进栈）进栈）Status Push ( SqStack &S, SElemType e ) / 将元素将元素 e 插入到栈插入到栈 S 中，成为新的栈顶元素中，成为新的栈顶元素 if ( S.top - S.base S.stacksize ) / 如果栈满，则追加存储空间如果栈满，则追加存储空

17、间 S.base = ( SElemType S.base = ( SElemType * * ) realloc ( S.base, ) realloc ( S.base, ( S.stacksixe + STACKINCREMENT( S.stacksixe + STACKINCREMENT* * sizeof ( SElemType sizeof ( SElemType ) ); ) ); if ( ! S.base ) exit ( OVERFLOW ); / if ( ! S.base ) exit ( OVERFLOW ); / 追加存储空间失败追加存储空间失败 S.top = S

18、.base + S.stacksizeS.top = S.base + S.stacksize; / ; / 修改栈顶指针修改栈顶指针 S.stacksizeS.stacksize += STACKINCREMENT; / += STACKINCREMENT; / 修改当前栈的存储空间修改当前栈的存储空间 / if / if 结束结束 * *S.top += e; / S.top += e; / 先将先将 e e 送入栈顶，然后将栈顶指针加送入栈顶，然后将栈顶指针加 1 1 return OK; return OK; / Push / Push（4）将元素弹出顺序栈算法（将元素弹出顺序栈算法（

19、退栈）退栈）Status Pop ( SqStack &S, SElemType &e ) / 如果栈如果栈 S 空，返回空，返回 ERROR ；如果栈；如果栈 S 不空，删除不空，删除 S 栈顶元素，栈顶元素，用用 e 返回其值，并返回返回其值，并返回 OK 。 if ( S.top = = S.base ) return ERROR; / 如果栈如果栈 S 为空，则返回为空，则返回 ERROR e = *-S.top; / 先令先令 top 减减 1，再将，再将 top 所指单元值赋给所指单元值赋给 e return OK; / Pop / Pop（5） 判栈空否判栈空否 Int Empt

20、y ( SqStack S) / 如果栈如果栈 S 空，返回空，返回 1 ；如果栈；如果栈 S 不空，返回不空，返回 0 。if ( S.top = = S.base ) return 1; / 如果栈如果栈 S 为空，则返回为空，则返回 1else return 0; / 如果栈如果栈 S 为空，则返回为空，则返回 0 / / Empty end3栈的共享栈的共享有时，一个程序设计中，需要使用多个同一类型的栈,这时候，可能会产生一个栈空间过小，容量发生溢出，而另一个栈空间过大，造成大量存储单元浪费的现象。 为了充分利用各个栈的存储空间，这时可以采用多个栈共享存储单元，即给多个栈分配一个足够大

21、的存储空间，让多个栈实现存储空间优势互补。 栈 1 顶 栈 2 顶 栈 1 底 栈 2 底 图 3-3 两个栈共享存储单元示意图 栈空：栈空：top1=0,top2=M-1;top1=0,top2=M-1;栈满：栈满：top1+1=top2top1+1=top2两个栈共享存储单元可用如下两个栈共享存储单元可用如下C C语句描述：语句描述：#define MAXSIZE 100 #define DUSTACKSIZE MAXSIZE typedef struct DuSqStack SElemType dataMAXSIZE; int top1; /top1 is the pointer of

22、DuSqStack/top1 is the pointer of DuSqStack S1 S1 int top2; /top2 is the pointer of DuSqStack/top2 is the pointer of DuSqStack S2 S2 int flag;DuSqStack; /或：或：#define MAXSIZE 100Struct duseqstack elemtype datamaxsize; int top2 ; /两个栈的栈顶指针两个栈的栈顶指针 int flag; （1）两个栈共享存储单元的进栈算法）两个栈共享存储单元的进栈算法Status DuSqSt

23、ackPush ( DuSqStack &S, SElemType x ) / / 栈栈 S S 为共享顺序栈类型为共享顺序栈类型 DuSqStackDuSqStack，含，含 top1top1、top2 top2 和和 data data 数组域；数组域；/ / 此算法将元素此算法将元素 x x 放入栈放入栈 S S 中；如果两个栈满，则返回中；如果两个栈满，则返回 ERRORERROR if ( ( S.top1+1 ) = = ( S.top2 ) ) return ERROR; / / 如果两个栈满，则返回如果两个栈满，则返回 ERRORERROR else / / 如果栈未满，则进行

24、入栈操作如果栈未满，则进行入栈操作 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 S.dataS.top1 = x; / / 元素元素 x x 入栈入栈 S1S1 S.top1+; / / 修改栈修改栈 S1 S1 的栈顶指针的栈

25、顶指针 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（2）两个栈共享存储单元的退栈算法）两个栈共享存储单元的退栈算法Status DuSqStackPop ( DuSqStack

26、 &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 / / 如果如

27、果 flag flag 为为 1 1 或或 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 结束结束 else return ERROR; / / 如果栈如果栈 S1 S1 为空，则返回为空，则返回 ERRORERROR break; c

28、ase 2 : / / 标志位标志位 flag flag 为为 1 1 if ( S.top2next=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; retu

29、rn OK; / Push_L / Push_L（c）退栈运算）退栈运算Status Pop_L ( LinkStack &top, SElemType &e ) / 如果栈如果栈 S 空，返回空，返回 ERROR ；如果栈；如果栈 S 不空，删除不空，删除 S 的栈顶元素，的栈顶元素，用用 e 返回其值，并返回返回其值，并返回 OK 。 if ( ! top-next ) return ERROR; / 如果栈如果栈 S 为空，则返回为空，则返回 ERROR e = top-next-data; / 取出栈顶元素的值取出栈顶元素的值 q = top-next; / q 指向栈顶元素指向栈顶元

30、素 top-next = q-next; / top-next = q-next; / 删除栈顶元素删除栈顶元素 free (q); / free (q); / 释放栈顶元素所占的空间释放栈顶元素所占的空间 return OK;return OK; / Pop_L / Pop_L（d）取栈顶元素）取栈顶元素Status GetTop_L ( LinkStack top, SElemType &e ) / 如果栈如果栈 S 空，返回空，返回 ERROR；如果栈；如果栈 S 不空，用不空，用 e 返回栈返回栈 S 的的栈顶元素，并返回栈顶元素，并返回 OK 。 if ( ! top-next )

31、return ERROR; / 如果栈如果栈 S 为空，则返回为空，则返回 ERROR else / 如果栈如果栈 S 不空，则返回栈顶元素不空，则返回栈顶元素 e = top-next-data;e = top-next-data; return OK; return OK; / else / else 结束结束 / GetTop_L / GetTop_L（5）判栈空）判栈空int empty(LinkStack *top) if(top-next=NULL) return(1); else return(0);课课 前前 复复 习习设n 个元素的进栈序列是P1，P2，P3， Pn，其输出序

32、列是1,2，3，n，若P1=3，则P2的值 ()。 A、可能是2B、一定是2C、不可能是1D、一定是1 一、一、 数制转换数制转换 假设要将十进制数N转换为d进制数，一个简单的转换算法是重复下述两步， 直到N等于零： X = N mod d (其中mod为求余运算)N = N div d (其中div为整除运算) 计算过程从低位到高位，打印输出从高位到低位3.2 3.2 栈的应用举例栈的应用举例 栈在日常生活中和计算机程序设计中有着许多应用，下面仅介绍栈在计算机中的应用。void Conversion(int N)/*对于任意的一个非负十进制数N， 打印出与其等值的8进制数*/ Stack S

33、; 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); 算法算法3.1二、括号匹配问题二、括号匹配问题 假设表达式中允许包含三种括号假设表达式中允许包含三种括号:圆括号、圆括号、方括号和大括号。编写一个算法判断表达式中的方括号和大括号。编写一个算法判断表达式中的括号是否正确配对。括号是否正确配对。 解解:设置一个括号栈设置一个括号栈,扫描表达式：遇到左括号扫描表达式：遇到

34、左括号(包括包括(、和和)时进栈时进栈,遇到右括号时遇到右括号时,若栈是相匹若栈是相匹配的左括号配的左括号,则出栈则出栈,否则否则,返回返回0。 若表达式扫描结束若表达式扫描结束,栈为空栈为空,返回返回1表示括号正表示括号正确匹配确匹配,否则返回否则返回0。 int correct(char exp,int n) char stMaxSize; int top=-1,i=0,tag=1; while (i-1) tag=0; /*若栈不空若栈不空,则不配对则不配对*/ return(tag); 三、行编辑程序三、行编辑程序功能：接收用户从终端输入的数据或程序，并存入用户的数据区。算法思想：设输

35、入缓冲区为一个栈结构，每当从终端接收一个字符后先作如下判别：若它既不是退格符（#）也不是退行符（）,则将该字符入栈；若是退格符（#），则从栈顶删去一个字符；若是退行符（），则将栈清空。算法描述如下：算法描述如下：void 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);brea

36、k;/有效字符进栈，但未考虑栈满 ch=getchar(); clearstack(s); if(ch!=EOF) ch=getchar(); destroystack(s);五、五、 表达式求值表达式求值 表达式求值是高级语言编译中的一个基本问题， 是栈的典型应用实例。 任何一个表达式都是由操作数(operand)、 运算符(operator)和界限符(delimiter)组成的。操作数操作数既可以是常数， 也可以是被说明为变量或常量的标识符；运算符运算符可以分为算术运算符、 关系运算符和逻辑运算符三类；基基本界限符本界限符有左右括号和表达式结束符等。 1.1.无括号算术表达式求值无括号算术

37、表达式求值 表达式计算表达式计算 程序设计语言中都有计算表达式的问题， 这是语言编译中的典型问题。 (1) 表达式形式： 由运算对象、 运算符及必要的表达式括号组成； (2) 表达式运算： 运算时要有一个正确的运算形式顺序。由于某些运算符可能具有比别的运算符更高的优先级，因此表达式不可能严格的从左到右， 见图3.5。 图3.5 表达式运算及运算符优先级 图3.6 无括号算术表达式的处理过程 置空栈OVS、OPTR读字符WW是操作符OPTR栈空W优先级OPTR栈顶优先级取OVS顶、次顶和OPTR顶，形成运算结果T(i),然后退OVS顶、次顶和OPTR顶，将T(i)置入OVS栈顶进OVS进OPTR

38、栈W # 结束NYYYNYNN 2. 2. 算术表达式处理规则算术表达式处理规则 (1) 规定优先级表。 (2) 设置两个栈： OVS(运算数栈)和OPTR(运算符栈)。 (3) 自左向右扫描，遇操作数进OVS，遇操作符则与OPTR栈顶优先数比较：当前操作符OPTR栈顶, 当前操作符进OPTR栈；当前操作符OPTR栈顶，OVS栈顶、次顶和OPTR栈顶，退栈形成运算T(i)，T(i)进OVS栈。 例： 实现A/BC+D*E的运算过程时栈区变化情况如图3.7所示。 图3.7 A/BC+D*E运算过程的栈区变化情况示意图 CBAOVS/OPTROPTR生成BC，运算结果T(1)T(1)AOVS/OP

39、TROPTR/生成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(4)E*右边界#OPTR+* 3. 3. 带括号算术表达式带括号算术表达式 假设操作数是整型常数，运算符只含加、减、乘、除等四种运算符， 界限符有左右括号和表达式起始、结束符“”，如： （7+15）*（23-28/4）。 引入表达式起始、 结束符是为了方便。 要对一个简单的算术表达式求值， 首先要了解算术四则运算的规则， 即： (1) 从左算到右；(2) 先乘除， 后加减；(3) 先括号内， 后括号外。

40、 运算符和界限符可统称为算符，它们构成的集合命名为OPTR。根据上述三条运算规则，在运算过程中，任意两个前后相继出现的算符1和2之间的优先关系必为下面三种关系之一： 12， 1的优先权高于2。 表表 3-1 3-1 算符之间的优先关系算符之间的优先关系 实现算符优先算法时需要使用两个工作栈： 一个称作optr， 用以存放运算符；另一个称作opnd，用以存放操作数或运算的中间结果。 算法的基本过程如下： 首先初始化操作数栈opnd和运算符栈optr， 并将表达式起始符“”压入运算符栈； 依次读入表达式中的每个字符，若是操作数则直接进入操作数栈opnd， 若是运算符，则与运算符栈optr的栈顶运算

41、符进行优先权比较，并做如下处理： (1) 若栈顶运算符的优先级低于刚读入的运算符， 则让刚读入的运算符进optr栈； (2) 若栈顶运算符的优先级高于刚读入的运算符，则将栈顶运算符退栈，送入，同时将操作数栈opnd退栈两次，得到两个操作数a、b，对a、 b进行运算后， 将运算结果作为中间结果推入opnd栈； (3) 若栈顶运算符的优先级与刚读入的运算符的优先级相同，说明左右括号相遇，只需将栈顶运算符（左括号）退栈即可。 算法具体描述如下：算法具体描述如下： int ExpEvaluation()/*读入一个简单算术表达式并计算其值。 operator和operand分别为运算符栈和运算数栈，

42、OPS为运算符集合*/ InitStack(&opnd); InitStack(&optr); Push(&optr,); printf(nnPlease input an expression(Ending with ) :); c=getchar(); while(c!=|GetTop(optr)! =) /* GetTop()通过函数值返回栈顶元素*/ if(!In(c,OP) Push(&opnd,c); c=getchar(); else switch(Precede(GetTop(optr),c) case : Pop(&optr,&theta); Pop(&opnd,&b); P

43、op(&opnd,&a); v=Execute(a,theta,b); /* 对a和b进行op运算 */ Push(&opnd,v); break; return (GetTop(opnd); 例求表达式1+2*3-4/2的值，栈的变化如下。 步骤 操作数栈 运算符栈 说明 开始两栈均为空111进入操作数栈+进入运算符栈2进入操作数栈*进入运算符栈3进入操作数栈退栈2*3进入操作数栈退栈1+6进入操作数栈234567891+12+12+1117+*236+*+步骤 操作数栈 运算符栈 说明 107-进入运算符栈4进入操作数栈/进入运算符栈2进入操作数栈退栈4/2进入操作数栈退栈7-2进入操作数

44、栈111213141516177 4-7 4- /7 4 2- /77 2-5当然，算术表达式除了简单求值外，还会涉及到算术表达式的两种表示方法，即中缀表示法和后缀表示法。中缀表达式求值较麻烦（须考虑运算符的优先级，甚至还要考虑圆括号），而后缀表达式求值较方便（无须考虑运算符的优先级及圆括号）。下面将介绍算术表达式的中缀表示和后缀表示及它们的求值规律， 例如，对于下列各中缀表达式：（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 +

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

46、 现在用栈来实现该运算，栈的变化及输出结果如下步骤栈中元素 输出结果 说明1( （进栈2(1输出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 - 进栈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-

47、 进栈17* ( / ( -1 2 + 8 2 - 7 4输出418* ( /1 2 + 8 2 - 7 4 -退栈输出，退栈到（止19*1 2 + 8 2 - 7 4 - /退栈输出，退栈到（止20 1 2 + 8 2 - 7 4 - / * *退栈并输出步骤 栈中元素 输出结果 说明5.5.后缀表达式的求值后缀表达式的求值 将中缀表达式转换成等价的后缀表达式后，求值时，不需要再考虑运算符的优先级，只需从左到右扫描一遍后缀表达式即可。具体求值步骤为：设置一个栈，开始时，栈为空，然后从左到右扫描后缀表达式，若遇操作数，则进栈；若遇运算符，则从栈中退出两个元素，先退出的放到运算符的右边，后退出的

48、放到运算符左边，运算后的结果再进栈，直到后缀表达式扫描完毕。此时，栈中仅有一个元素，即为运算的结果。例，求后缀表达式：1 2 + 8 2 - 7 4 - / *的值，栈的变化情如下：步骤栈中元素 说明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进栈步骤栈中元素 说明113 6遇-号退栈4和7123 6 37-4=3的结果3进栈133遇/号退栈3和6143 26/3=2的结果2进栈15 遇*号退栈2和31663*2=6进栈176扫描完毕，运算结束 从上

49、可知，最后求得的后缀表达式之值为6，与用中缀表达式求得的结果一致，但后缀式求值要简单得多。五、五、 求解迷宫问题求解迷宫问题 求迷宫问题就是求出从入口到出口的路径。在求迷宫问题就是求出从入口到出口的路径。在求解时求解时, ,通常用的是通常用的是“穷举求解穷举求解”的方法的方法, ,即从入即从入口出发口出发, ,顺某一方向向前试探顺某一方向向前试探, ,若能走通若能走通, ,则继续往则继续往前走；否则沿原路退回前走；否则沿原路退回, ,换一个方向再继续试探换一个方向再继续试探, ,直至所有可能的通路都试探完为止。为了保证在直至所有可能的通路都试探完为止。为了保证在任何位置上都能沿原路退回任何位置

50、上都能沿原路退回( (称为回溯称为回溯),),需要用一需要用一个后进先出的栈来保存从入口到当前位置的路径。个后进先出的栈来保存从入口到当前位置的路径。 首先用如图首先用如图3.33.3所示的方块图表示迷宫。对所示的方块图表示迷宫。对于图中的每个方块于图中的每个方块, ,用空白表示通道用空白表示通道, ,用阴影表示用阴影表示墙。所求路径必须是简单路径墙。所求路径必须是简单路径, ,即在求得的路径上即在求得的路径上不能重复出现同一通道块。不能重复出现同一通道块。 为了表示迷宫为了表示迷宫,设置一个数组设置一个数组mg,其中每个元素表示其中每个元素表示一个方块的状态一个方块的状态,为为0时表示对应方