栈栈的应用举例队列.ppt
《栈栈的应用举例队列.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 迷宫求解,求解方法,“穷举求解”方法:从入口出发,顺某一方向向前探索,若能走通,则继续往前走;否
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 应用 举例 队列
链接地址:https://www.31doc.com/p-2699070.html