《栈栈应用举例队列.ppt》由会员分享，可在线阅读，更多相关《栈栈应用举例队列.ppt（68页珍藏版）》请在三一文库上搜索。
1、3.1 栈 3.2 栈的应用举例 3.3 队列,第3章 栈和队列,重点: (1)栈、队列的定义、特点、性质和应用；(2)ADT栈、ADT队列的设计和实现以及基本操作及相关算法。 难点: (1)循环队列中对边界条件的处理；(2)分析栈和队列在表达式求值、括号匹配、数制转换、迷宫求解中的应用实例，提高利用栈和队列解决实际问题的应用水平。,本章重点难点,3.1 栈 3.2 栈的应用举例 3.3 队列,第3章 栈和队列,3.1 栈,3.1.1 抽象数据类型栈的定义 3.1.2 栈的表示和实现,3.1.1 抽象数据类型栈的定义,栈的定义,栈(Stack)是一种特殊的线性表，其插入和删除操作均在表的一端进
2、行，是一种运算受限的线性表。,栈顶(top)是栈中允许插入和删除的一端。 栈底(bottom)是栈顶的另一端。,栈的术语,栈的特点,栈的示意图,后进先出(Last In First Out，简称LIFO)。又称栈为后进先出表(简称LIFO结构)。,栈底,栈顶,入栈,出栈,3.1.1 抽象数据类型栈的定义,ADT Stack 数据对象： 数据关系：,抽象数据类型栈,基本操作：, ADT Stack,R1 | ai-1, aiD, i=2,.,n 约定an 端为栈顶，a1 端为栈底。,D ai | ai ElemSet, i=1,2,.,n, n0 ,见下页,3.1.1 抽象数据类型栈的定义,In
3、itStack(&S) /初始化栈,DestroyStack(&S) /销毁栈,ClearStack(&S) /清空栈,StackEmpty(S) /判栈空,StackLength(S) /求栈长度,GetTop(S, &e) /取栈顶元素,Push(&S, e) /入栈,Pop(&S, &e) /出栈,StackTravers(S, visit() /遍历栈,栈的基本操作,3.1.1 抽象数据类型栈的定义,3.1 栈,3.1.1 抽象数据类型栈的定义 3.1.2 栈的表示和实现,3.1.2 栈的表示和实现,/- 栈的顺序存储表示 - #define STACK_INIT_SIZE 100;
4、/存储空间初始分配量 #define STACKINCREMENT 10; /存储空间分配增量 typedef struct SElemType *base; /栈底指针 SElemType *top; /栈顶指针 int stacksize; /当前可使用最大容量 SqStack;,SqStack S;,顺序栈的C语言实现,3.1.2 栈的表示和实现,栈初始化过程演示,(1) 给栈S申请栈空间,(2) 设置基地址S.base和栈顶地址S.top,S.top,S.base,(3) 设置栈容量S.stacksize=STACK_INIT_SIZE,Status InitStack (SqStac
5、k ,3.1.2 栈的表示和实现,栈初始化算法,3.1.2 栈的表示和实现,入栈操作演示,(1) 如果栈满，给栈增加容量,(2) 将数据存入栈顶位置，栈顶后移一位,S.top,S.base,e,S.top,Status Push (SqStack ,3.1.2 栈的表示和实现,入栈操作演示,3.1.2 栈的表示和实现,DestroyStack(&S) /销毁栈,ClearStack(&S) /清空栈,StackEmpty(S) /判栈空,StackLength(S) /求栈长度,GetTop(S, &e) /取栈顶元素,Pop(&S, &e) /出栈,StackTravers(S, visit
6、() /遍历栈,其它栈操作讨论,Typedef struct SNode ElemType data; /数据域 struct Snode *next; /链域 SNode, *LinkStack;,3.1.2 栈的表示和实现,链栈的C语言类型定义,链栈的实现与链表的实现基本相同，头结点作为栈顶位置。,LinkStack *top; /栈顶指针,InitStack(&S) /初始化栈,DestroyStack(&S) /销毁栈,ClearStack(&S) /清空栈,StackEmpty(S) /判栈空,StackLength(S) /求栈长度,GetTop(S, &e) /取栈顶元素,Pus
7、h(&S, e) /入栈,Pop(&S, &e) /出栈,StackTravers(S, visit() /遍历栈,讨论链栈基本操作的实现,3.1.2 栈的表示和实现,3.2 栈的应用举例,3.2.1 数制转换 3.2.2 括号匹配的检验 3.2.3 行编辑程序问题 3.2.4 迷宫求解 3.2.5 表达式求值,3.2.1 数制转换,任何X进制数N转换成Y进制数其结果都是要化成如下形式。,进制转换原理：,转换的过程就是通过取余运算求出a0,a1,an，而先求出的是个位，十位，与我们写数的习惯先从高位写正好相反，通过栈先进后出的特点，很容易实现倒过来的过程。,过程如下： N N div 8 N
8、mod 8 1348 168 4 168 21 0 21 2 5 2 0 2,输出顺序,计算顺序,3.2.1 数制转换,例,将10进制1346转换成8进制,void conversion () InitStack(S); scanf (“%d“,N); while (N) Push(S, N % 8); N = N/8; while (!StackEmpty(S) Pop(S,e); printf ( “%d“, e ); / conversion,3.2.1 数制转换,10进制数N转换成8进制的算法,一个表达式中，包含三种括号“(”和“)”，“”和“”和“”和“”，这三种括号可以按任意的合法
9、次序使用。 设计算法检验表达式中所使用括号的合法性。,3.2.2 括号匹配的检验,问题描述,讨论：如果第一次遇到的右括号是“”，那么前面出现的左括号有什么特点。,问题讨论,结论：如果第一次遇到的右括号是“”，那么前面出现的左括号最后一个必然是“”，否则不合法。,算法过程,3.2.2 括号匹配的检验,当遇到左括号时，进栈，遇到右括号时出栈； (2) 当遇到某一个右括号时，栈已空，说明到目前为止，右括号多于左括号； (3) 从栈中弹出的左括号与当前检验的右括号类型不同，说明出现了括号交叉情况； (4) 算术表达式输入完毕，但栈中还有没有匹配的左括号，说明左括号多于右括号。,Status check
10、( ) char ch; InitStack(S); while (ch=getchar()!=#) switch (ch) case (ch=(|ch=|ch=):Push(S,ch);break; case (ch= ): if (StackEmpty(S) retrun FALSE; else Pop(S,e); if(e!= () return FALSE; break;,括号匹配检验算法,3.2.2 括号匹配的检验,case (ch= ): if (StackEmpty(S) retrun FALSE; else Pop(S,e); if(e!= ) return FALSE; br
11、eak; default:break; if (StackEmpty(S) return TRUE; else return FALSE; ,括号匹配检验算法,3.2.2 括号匹配的检验,3.2.3 行编辑程序问题,设立一个输入缓冲区，用以接受用户输入的一行字符，然后逐行存入用户数据区，并假设“#”为退格符，“”为退行符。,在用户输入一行的过程中，允许用户输入出差错，并在发现有误时可以及时更正。,解决办法,问题描述,假设从终端接受了这样两行字符： whli#ilr#e（s#*s) outchaputchar(*s=#+);,则实际有效的是下列两行： while (*s) putchar(*s+
12、);,例,3.2.3 行编辑程序问题,DestroyStack(S); ,void LineEdit() /利用字符栈S，从终端接收一行并传送至调 /用过程的数据区 InitStack(S); ch=getchar(); .,3.2.3 行编辑程序问题,行编辑问题算法,while (ch != EOF) /EOF为全文结束符,while (ch != EOF & ch != n) ,switch (ch) case # : Pop(S, c); break; case : ClearStack(S); break;/ 重置S为空栈 default : Push(S, ch); break; c
13、h = getchar(); / 从终端接收下一个字符,ClearStack(S); / 重置S为空栈 if (ch != EOF) ch = getchar();,栈中字符传送至调用过程的数据区；,3.2.3 行编辑程序问题,行编辑问题算法,入口,出口,3.2.4 迷宫求解,如图表示一个迷宫，有一个入口，一个出口，从一个位置可以向4个方向(东、南、西、北)走，白方块表示通道，蓝方块表示墙，求从入口到出口的路径。,问题描述,1,2,3,4,5,6,7,8,1,2,3,4,5,6,7,8,3.2.4 迷宫求解,求解方法,“穷举求解”方法：从入口出发，顺某一方向向前探索，若能走通，则继续往前走；否
14、则沿原路退回，换一个方向再继续探索，直至所有可能的通路都探索到为止。,为了保证在任何位置上都能沿原路退回，需要一个后进先出的结构来保存从入口到当前位置的路径。因此，求解迷宫通路算法需要应用“栈”来保存当前路径。,3.2.4 迷宫求解,四周墙壁解决办法如图,0,1,2,3,4,5,6,7,8,9,0,1,2,3,4,5,6,7,8,9,1,2,3,4,5,6,7,8,1,2,3,4,5,6,7,8,当前位置：在搜索过程中某一时刻所在图中某个方块位置。 当前位置可通：未承走到过的通道块，该方块既不在当前路径上，也不是曾经纳入过路径的通道块。,3.2.4 迷宫求解,0,1,2,3,4,5,6,7,8
15、,9,0,1,2,3,4,5,6,7,8,9,下一位置：当前位置四周4个方向(东、南、西、北)上相邻的方块。,当前位置,当前路径,3.2.4 迷宫求解,算法思想,(1)若当前位置“可通”，则纳入“当前路径”，并继续朝“下一位置”探索，即切换“下一位置”为“当前位置”，如此重复直至到达出口； (2)若当前位置“不可通”，则应顺着“来向”退回到“前一通道块”，然后朝着除了“来向”之外的其他方向继续探索； (3)若该通道块的四周4个方块均“不可通”，则应从“当前路径”上删除该通道块。,设定当前位置的初值为入口位置； do 若当前位置可通， 则将当前位置插入栈顶； 若该位置是出口位置，则算法结束； 否
16、则切换当前位置的东邻方块为 新的当前位置； 否则 . while (栈不空）；,迷宫路径求解算法,3.2.4 迷宫求解,若栈不空且栈顶位置尚有其他方向未被探索， 则设定新的当前位置为: 沿顺时针方向旋转找到的栈顶位置的下一相邻块；,若栈不空但栈顶位置的四周均不可通，则 删去栈顶位置； 若栈不空，则重新测试新的栈顶位置， 直至找到一个可通的相邻块或出栈至栈空；,若栈空，则表明迷宫没有通路。,迷宫路径求解算法,3.2.4 迷宫求解,0,1,2,3,4,5,6,7,8,9,0,1,2,3,4,5,6,7,8,9,3.2.4 迷宫求解,求解过程示例,3.2.5 表达式求值,一个表达式由操作数(oper
17、and)、运算符(operator)、界限符(delimiter)组成。写出“算符优先法”求值的算法。,问题描述,例,求3*(2+3*5)+6的值,设置两个栈，一个存操作数，栈名为OPND，一个存操作符，栈名为OPTR栈。 (1) 首先置操作数栈为空，表达式起始符#为运算符栈的栈底元素； (2)依次读入表达式中每个字符，若是操作数则进OPND栈，若是运算符则和OPTR栈的栈顶运算符比较优先权后作相应操作，直到整个表达式操作完毕。,3.2.5 表达式求值,算法求解过程,(1)若栈顶运算符小于输入运算符，输入运算符进栈OPTR； (2)若栈顶运算符等于输入运算符（只有栈顶是“（”，输入是“）”，或
18、者栈顶是“#”，输入是“#）”两种情况，分别去除一对括号，或结束。 (3)若栈顶运算符大于输入运算符，弹出栈顶运算符，从OPND中弹出两个操作数与弹出运算符计算后再存入OPND栈，继续。,3.2.5 表达式求值,算法求解过程,OperandType EvaluateExpression() initStack(OPTR);Push(OPTR,#); initStack(OPND);c=getchar(); while(c!=#)|GetTop(OPTR)!=#) if(!In(c,OP) Push(OPND,c);c=getchar(); else switch(Precede(GetTop(
19、OPTR),c),3.2.5 表达式求值,表达式求值算法,case : Push(OPTR,c);c=getchar();break; case =: Pop(OPTR,x);c=getchar;break;,3.2.5 表达式求值,case : Pop(OPTR,theta); Pop(OPND,a); Pop(OPND,b); Push(OPND,Operate(a,theta,b);break; /switch语句结束 /while 语句结束 return(GetTop(OPND); /算法结束,表达式求值算法,3.1 栈 3.2 栈的应用举例 3.3 队列,第3章 栈和队列,队列的定义
20、,3.4.1 抽象数据类型队列的定义,队列(Queue)是一种运算受限的特殊的线性表，它只允许在表的一端进行插入，而在表的另一端进行删除。,队尾(rear)是队列中允许插入的一端。 队头(front)是队列中允许删除的一端。,队列的术语,队列的特点,队列示意图,3.4.1 抽象数据类型队列的定义,队头,队尾,出队,出队,先进先出(First In First Out ，简称FIFO)。 又称队列为先进先出表。,ADT Queue 数据对象： 数据关系：,抽象数据类型栈,基本操作：, ADT Queue,见下页,3.1.1 抽象数据类型栈的定义,Dai | aiElemSet, i=1,2,.,
21、n, n0,R1 | ai-1, ai D, i=2,.,n 约定其中a1 端为队列头， an 端为队列尾,InitQueue(&Q) /初始化队列 DestroyQueue(&Q) /销毁队列 QueueEmpty(Q) /判队列是否空 QueueLength(Q) /求队列长度 GetHead(Q, &e) /取队头元素 ClearQueue(&Q) /清空队列 EnQueue(&Q, e) /入队列 DeQueue(&Q, &e) /出队列 QueueTravers(Q, visit() /遍历队列,队列的基本操作,3.1.1 抽象数据类型栈的定义,3.4.2 链队列,typedef s
22、truct QNode / 结点类型 QElemType data; struct QNode *next; QNode, *QueuePtr;,链队列结点实现,typedef struct / 链队列类型 QueuePtr front; / 队头指针 QueuePtr rear; / 队尾指针 LinkQueue;,链队列数据类型实现,Q.front Q.rear,带头结点的链队列示意图,3.4.2 链队列,头结点,空队列,Q.front Q.rear,Status InitQueue (LinkQueue ,3.4.2 链队列,带头结点的链队列初始化,Status EnQueue (Lin
23、kQueue ,3.4.2 链队列,带头结点的链队列入队算法,Status DeQueue (LinkQueue ,3.4.2 链队列,带头结点的链队列出队算法,DestroyQueue(&Q) /销毁队列 QueueEmpty(Q) /判队列是否空 QueueLength(Q) /求队列长度 GetHead(Q, &e) /取队头元素 ClearQueue(&Q) /清空队列 QueueTravers(Q, visit() /遍历队列,3.4.2 链队列,带头结点的链队列其它操作讨论,3.4.3 循环队列,循环队列属于顺序队列的一种，讨论在采用一般顺序队列时出现的问题。,顺序队列讨论,空队列
24、,A入队,B入队,C,D,E相继入队,Sq.rear,Sq.front,Sq.rear,Sq.front,Sq.rear,Sq.front,Sq.rear,Sq.front,队列满,A被删除(出队),B被删除,讨论结论：在采用一般顺序队列时出现假上溢现象？,C,D,E相继被删除,顺序队列讨论,3.4.3 循环队列,Sq.rear,Sq.front,Sq.front,Sq.rear,Sq.rear,Sq.front,Sq.front,Sq.rear,循环队列示意图,3.4.3 循环队列,Sq.front,Sq.rear,3.4.3 循环队列,#define MAXQSIZE 100 /最大队列长
25、度 typedef struct QElemType *base; / 动态分配存储空间 int front; / 头指针，若队列不空， / 指向队列头元素 int rear; / 尾指针，若队列不空，指向 队列尾元素 的下一个位置 SqQueue;,SqQueue Sq;,链队列数据类型实现,循环队列是顺序队列的一种特例，它是把顺序队列构造成一个首尾相连的循环表。指针和队列元素之间关系不变。,3.4.3 循环队列,循环队列的定义,0,1,maxsize-1,Sq.front,Sq.rear,3.4.3 循环队列,循环队列空状态和满状态的讨论,讨论结论： 循环队列空状态和满状态都满足Q.fro
26、nt=Q.rear,(1) 另设一个标志区别队列是空还是满；,3.4.3 循环队列,循环队列空状态和满状态的判别,例如：设一个变量count用来记录队列中元素个数，当count=0时队列为空，当count= MAXQSIZE时队列为满。,(2)队满条件：以队头指针在队列尾指针的下一位置作为队列呈满状态的标志，牺牲一个存储空间；,3.4.3 循环队列,循环队列空状态和满状态的判别,队满条件为： (sq.rear+1) mod maxsize=sq.front 队空条件为：sq.rear=sq.front,3.4.3 循环队列,循环队列空状态和满状态的判别,队列满,Status InitQueue
27、 (SqQueue ,3.4.3 循环队列,队列初始化算法,Status EnQueue (SqQueue ,3.4.3 循环队列,入队列算法,Status DeQueue (SqQueue ,3.4.3 循环队列,出队列算法,分析以下两种状态如何求队列长度,3.4.3 循环队列,Sq.front,Sq.rear,Sq.front,Sq.rear,int QueueLength(SqQueue Q) return (Q.rear-Q.front+MaxSize)%MaxSize; ,3.4.3 循环队列,求队列长度算法,本章小结,熟练掌握： (1)栈、队列的定义、特点和性质； (2)ADT栈、ADT队列的设计和实现以及基本操作及 相关算法。 重点学习： ADT栈和队列在表达式求值、括号匹配、数制转换、迷宫求解中的应用，提高利用栈和队列解决实际问题的应用水平。,