欢迎来到淘文阁 - 分享文档赚钱的网站! | 帮助中心 好文档才是您的得力助手!
淘文阁 - 分享文档赚钱的网站
全部分类
  • 研究报告>
  • 管理文献>
  • 标准材料>
  • 技术资料>
  • 教育专区>
  • 应用文书>
  • 生活休闲>
  • 考试试题>
  • pptx模板>
  • 工商注册>
  • 期刊短文>
  • 图片设计>
  • ImageVerifierCode 换一换

    数据结构之栈和队列应用学习教案.pptx

    • 资源ID:71960727       资源大小:309.13KB        全文页数:21页
    • 资源格式: PPTX        下载积分:10金币
    快捷下载 游客一键下载
    会员登录下载
    微信登录下载
    三方登录下载: 微信开放平台登录   QQ登录  
    二维码
    微信扫一扫登录
    下载资源需要10金币
    邮箱/手机:
    温馨提示:
    快捷下载时,用户名和密码都是您填写的邮箱或者手机号,方便查询和重复下载(系统自动生成)。
    如填写123,账号就是123,密码也是123。
    支付方式: 支付宝    微信支付   
    验证码:   换一换

     
    账号:
    密码:
    验证码:   换一换
      忘记密码?
        
    友情提示
    2、PDF文件下载后,可能会被浏览器默认打开,此种情况可以点击浏览器菜单,保存网页到桌面,就可以正常下载了。
    3、本站不支持迅雷下载,请使用电脑自带的IE浏览器,或者360浏览器、谷歌浏览器下载即可。
    4、本站资源下载后的文档和图纸-无水印,预览文档经过压缩,下载后原文更清晰。
    5、试题试卷类文档,如果标题没有明确说明有答案则都视为没有答案,请知晓。

    数据结构之栈和队列应用学习教案.pptx

    会计学1数据结构之栈和队列数据结构之栈和队列(duli)应用应用第一页,共21页。前言(qin yn)Introduction 数据结构(sh j ji u)是计算机存储、组织数据的方式。是指相互之间存在一种或多种特定关系的数据元素的集合。通常情况下,精心选择的数据结构(sh j ji u)可以带来更高的运行或者存储效率。数据结构(sh j ji u)具体指同一类数据元素中,各元素之间的相互关系,包括三个组成成分,数据的逻辑结构,数据的存储结构和数据的运算。逻辑结构就是数据之间的关系。而按数据之间的关系来说,逻辑结构大概可以分为两种:线性结构和非线性结构(集合、树、网)。存储结构是逻辑结构的存储映像。常见的存储结构有顺序存储、链式存储、索引存储以及散列存储(哈希表)。第1页/共21页第二页,共21页。线性表线性表线性表(线性表(Linear listLinear list)是最简单且最常用的一种数据结构。这种结构具有下列特点:)是最简单且最常用的一种数据结构。这种结构具有下列特点:存在一个唯一的没有前驱的(头)数据元素;存在一个唯一的没有前驱的(头)数据元素;存在一个唯一的没有后继的(尾)数据元素;存在一个唯一的没有后继的(尾)数据元素;每一个数据元素均有一个直接前驱和一个直接后继的数据元素。每一个数据元素均有一个直接前驱和一个直接后继的数据元素。例如:例如:英文字母表(英文字母表(A A,B B,C C,Z Z)是一个长度为)是一个长度为2626的线性表,其中的每一个字母就是的线性表,其中的每一个字母就是(jish)(jish)一个数据元素;一个数据元素;某公司某公司20062006年每月产值表(年每月产值表(400400,420420,500500,600600,650650)(单位:万元单位:万元)是一个长度为是一个长度为1212的线性表,其中的每一个数值的线性表,其中的每一个数值就是就是(jish)(jish)一个数据元素。一个数据元素。ABCDEZ400420500600650第2页/共21页第三页,共21页。栈与队列栈与队列栈和队列也是线性表,不过是两种特殊的线性表。栈和队列也是线性表,不过是两种特殊的线性表。栈只允许栈只允许(ynx)在表的一端进行插入或删除操作,而队列只允许在表的一端进行插入或删除操作,而队列只允许(ynx)在表的一端进行插入操作、而在另一端进行删除操作。因而,在表的一端进行插入操作、而在另一端进行删除操作。因而,栈和队列也可以被称作为操作受限的线性表。栈和队列也可以被称作为操作受限的线性表。栈:栈:topbottom进栈进栈出栈出栈ana2a1a0允许插入允许插入(chr)和删除的一端称为栈顶和删除的一端称为栈顶(top),另一端称为栈底,另一端称为栈底(bottom)第一个进栈的元素第一个进栈的元素(yuns)在栈底,在栈底,最后一个进栈的元素最后一个进栈的元素(yuns)在栈顶,在栈顶,第一个出栈的元素第一个出栈的元素(yuns)为栈顶元素为栈顶元素(yuns),最后一个出栈的元素最后一个出栈的元素(yuns)为栈底元素为栈底元素(yuns)栈的特点:后进先出栈的特点:后进先出LIFO(Last In First Out)第3页/共21页第四页,共21页。栈与队列栈与队列栈和队列也是线性表,不过是两种特殊的线性表。栈和队列也是线性表,不过是两种特殊的线性表。栈只允许在表的一端进行插入或删除栈只允许在表的一端进行插入或删除(shnch)操作,而队列只允许在表的一端进行插入操作、而在另一端进行删除操作,而队列只允许在表的一端进行插入操作、而在另一端进行删除(shnch)操作。因而,栈和队列操作。因而,栈和队列也可以被称作为操作受限的线性表。也可以被称作为操作受限的线性表。队列队列(duli):出队出队进队进队队首队首(head)队尾队尾(tail)qn-1qi+1qiq1q0允许允许(ynx)插入的一端称为队尾(插入的一端称为队尾(tail),另一端称为队头),另一端称为队头(head)第一第一个个进队的进队的元素元素在队首,在队首,最后最后一个一个进队的进队的元素元素在队尾,在队尾,第一第一个个出队的出队的元素元素为队首元素为队首元素,最后最后一个一个出队的出队的元素元素为队尾元素为队尾元素队列的特点:先进先出队列的特点:先进先出FIFO(First In First Out)第4页/共21页第五页,共21页。栈应用:括号匹配栈应用:括号匹配问题描述问题描述现在,有一行括号序列,请你检查这行括号是否配对。现在,有一行括号序列,请你检查这行括号是否配对。输入输入第一行输入一个数第一行输入一个数N(0N=100),表示有表示有N组测试数据。后面的组测试数据。后面的N行输入多组输入数据,每组输入数据都是一个字符串行输入多组输入数据,每组输入数据都是一个字符串S(S的长度小于的长度小于10000,且,且S不是空串),测试数据组数少于不是空串),测试数据组数少于5组。数据保证组。数据保证S中只含有中只含有(hnyu),(,)四种字符四种字符输出输出每组输入数据的输出占一行,如果该字符串中所含的括号是配对的,则输出每组输入数据的输出占一行,如果该字符串中所含的括号是配对的,则输出Yes,如果不配对则输出如果不配对则输出No样例输入样例输入3()()()样例输出样例输出NoNoYes()0构建构建(ujin)栈:栈:获取获取(huq)符号字符串符号字符串(bool match(char str,int length)stack s;for(int i=0;ilength;i+)switch(stri)case(:case:s.push(stri);break;case):if(s.top()=()s.pop();else return false;break;case:if(s.top()=)s.pop();else return false;break;if(s.empty()return true;else return false;第5页/共21页第六页,共21页。问题描述问题描述某部队进行新兵队列训练,将新兵从一开始按顺序依次编号,并排成一行横队,训练的规则如下:从头开始一至二报数,凡报到二的出列,剩下的向某部队进行新兵队列训练,将新兵从一开始按顺序依次编号,并排成一行横队,训练的规则如下:从头开始一至二报数,凡报到二的出列,剩下的向小序号方向靠小序号方向靠拢,再从头开始进行一至三报数,凡报到三的出列,剩下的向小序号方向靠拢,继续从头开始进行一至二报数,以后从头开始轮流进拢,再从头开始进行一至三报数,凡报到三的出列,剩下的向小序号方向靠拢,继续从头开始进行一至二报数,以后从头开始轮流进行一至二报数、一至三报数,直到剩下的人数不超过三人为止。行一至二报数、一至三报数,直到剩下的人数不超过三人为止。Input本题有多个测试数据组,第一行为组数本题有多个测试数据组,第一行为组数N,接着为,接着为N行新兵人数,新兵人数不超过行新兵人数,新兵人数不超过5000。Output共有共有N行,分别对应行,分别对应(duyng)输入的新兵人数,每行输出剩下的新兵最初的编号,编号之间有一个空格。输入的新兵人数,每行输出剩下的新兵最初的编号,编号之间有一个空格。SampleInput22040SampleOutput171911937构建构建(ujin)队列队列1:构建构建(ujin)队列队列2:1357911131517191234567111213141516171819208910队列应用:新兵训练队列应用:新兵训练队首队首队首队首第6页/共21页第七页,共21页。问题描述问题描述某部队进行新兵某部队进行新兵(xnbn)队列训练,将新兵队列训练,将新兵(xnbn)从一开始按顺序依次编号,并排成一行横队,训练的规则如下:从头开始一至从一开始按顺序依次编号,并排成一行横队,训练的规则如下:从头开始一至二报数,凡报到二的出列,剩下的向小序号方向靠二报数,凡报到二的出列,剩下的向小序号方向靠拢,再从头开始进行一至三报数,凡报到三的出列,剩下的向小序号方向靠拢,继续拢,再从头开始进行一至三报数,凡报到三的出列,剩下的向小序号方向靠拢,继续从头开始进行一至二报数,以后从头开始轮流进行一至二报数、一至三报数,直到剩下的人数不超过三人为止。从头开始进行一至二报数,以后从头开始轮流进行一至二报数、一至三报数,直到剩下的人数不超过三人为止。Input本题有多个测试数据组,第一行为组数本题有多个测试数据组,第一行为组数N,接着为,接着为N行新兵行新兵(xnbn)人数,新兵人数,新兵(xnbn)人数不超过人数不超过5000。Output共有共有N行,分别对应输入的新兵行,分别对应输入的新兵(xnbn)人数,每行输出剩下的新兵人数,每行输出剩下的新兵(xnbn)最初的编号,编号之间有一个空格。最初的编号,编号之间有一个空格。SampleInput22040SampleOutput171911937构建构建(ujin)队列队列1:构建构建(ujin)队列队列2:1357911131517191379131519队列应用:新兵训练队列应用:新兵训练队首队首队首队首第7页/共21页第八页,共21页。问题描述问题描述某部队进行新兵队列训练,将新兵从一开始按顺序依次编号,并排成一行横队,训练的规则如下:从头开始一至二报数,凡报到二的出列,剩下的向小序号方向靠某部队进行新兵队列训练,将新兵从一开始按顺序依次编号,并排成一行横队,训练的规则如下:从头开始一至二报数,凡报到二的出列,剩下的向小序号方向靠 拢,拢,再从头开始进行一至三报数,凡报到三的出列,剩下的向小序号方向靠拢再从头开始进行一至三报数,凡报到三的出列,剩下的向小序号方向靠拢(kolng),继续从头开始进行一至二报数,以后从头开始轮流进行一至二报数、一至三报,继续从头开始进行一至二报数,以后从头开始轮流进行一至二报数、一至三报数,直到剩下的人数不超过三人为止。数,直到剩下的人数不超过三人为止。Input本题有多个测试数据组,第一行为组数本题有多个测试数据组,第一行为组数N,接着为,接着为N行新兵人数,新兵人数不超过行新兵人数,新兵人数不超过5000。Output共有共有N行,分别对应输入的新兵人数,每行输出剩下的新兵最初的编号,编号之间有一个空格。行,分别对应输入的新兵人数,每行输出剩下的新兵最初的编号,编号之间有一个空格。SampleInput22040SampleOutput171911937构建构建(ujin)队列队列1:构建构建(ujin)队列队列2:1713191379131519队列应用:新兵训练队列应用:新兵训练队首队首队首队首第8页/共21页第九页,共21页。问题描述问题描述某部队进行新兵队列训练,将新兵从一开始按顺序依次编号,并排成一行横队,训练的规则如下:从头开始一至二报数,凡报到二的出列,剩下的向某部队进行新兵队列训练,将新兵从一开始按顺序依次编号,并排成一行横队,训练的规则如下:从头开始一至二报数,凡报到二的出列,剩下的向小序号方向靠小序号方向靠拢,再从头开始进行一至三报数,凡报到三的出列,剩下的向小序号方向靠拢,继续从头开始进行一至二报数,以后从头开始轮流进拢,再从头开始进行一至三报数,凡报到三的出列,剩下的向小序号方向靠拢,继续从头开始进行一至二报数,以后从头开始轮流进行一至二报数、一至三报数,直到剩下的人数不超过三人为止。行一至二报数、一至三报数,直到剩下的人数不超过三人为止。Input本题有多个测试数据组,第一行为组数本题有多个测试数据组,第一行为组数N,接着为,接着为N行新兵人数,新兵人数不超过行新兵人数,新兵人数不超过5000。Output共有共有N行,分别对应输入的新兵人数,每行输出行,分别对应输入的新兵人数,每行输出(shch)剩下的新兵最初的编号,编号之间有一个空格。剩下的新兵最初的编号,编号之间有一个空格。SampleInput22040SampleOutput171911937构建构建(ujin)队列队列1:构建构建(ujin)队列队列2:1713 191719队列应用:新兵训练队列应用:新兵训练队首队首队首队首第9页/共21页第十页,共21页。队列应用:新兵训练队列应用:新兵训练void train(int num)bool t=false,flag=false;for(int i=0;inum;i+)st.push(i+1);while(1)if(numberOff(false,2)=true)t=false;break;if(numberOff(true,3)=true)t=true;break;while(!st.empty()if(flag)printf();printf(%d,st.front();st.pop();flag=true;printf(n);bool numberOff(bool t,int num)if(st.size()=3)return true;int n=0;t=!t;while(!s!t.empty()n=n%num+1;/n值在值在1和和2之间切换之间切换(qi hun);if(n!=num)st.push(s!t.front();s!t.pop();return false;queue s2;int main()int row,num;scanf(%d,&row);while(row-)scanf(%d,&num);train(num);return 0;第10页/共21页第十一页,共21页。栈应用:表达式计算栈应用:表达式计算问题描述问题描述输入一个只包含加减乖除和括号的合法表达式,求表达式的值。其中除表示整除。输入一个只包含加减乖除和括号的合法表达式,求表达式的值。其中除表示整除。输入格式输入格式输入一行输入一行(yxng),包含一个表达式。,包含一个表达式。输出格式输出格式输出这个表达式的值。输出这个表达式的值。样例输入样例输入1-2+3*(4-5)样例输出样例输出-4数据规模和约定数据规模和约定表达式长度不超过表达式长度不超过100,表达式运算合法且运算过程都在,表达式运算合法且运算过程都在int内进行。内进行。1-2+3*(4-5)0构建构建(ujin)符号栈:符号栈:获取获取(huq)表达式字符串表达式字符串构建操作数栈:构建操作数栈:#+-*/()+-*/(#-*/(#-*/(#-*/(#-1-1运算运算+-3-3=-4-4值得注意的有几个地方:值得注意的有几个地方:数据存在负数(即数据存在负数(即“-”是单目运算符)是单目运算符)数据是多位数数据是多位数第14页/共21页第十五页,共21页。+-栈应用:表达式计算栈应用:表达式计算问题描述问题描述输入一个只包含加减乖除和括号的合法表达式,求表达式的值。其中除表示整除。输入一个只包含加减乖除和括号的合法表达式,求表达式的值。其中除表示整除。输入格式输入格式输入一行,包含一个表达式。输入一行,包含一个表达式。输出格式输出格式输出这个表达式的值。输出这个表达式的值。样例输入样例输入1-2+3*(4-5)样例输出样例输出-4数据规模和约定数据规模和约定表达式长度不超过表达式长度不超过(chogu)100,表达式运算合法且运算过程都在,表达式运算合法且运算过程都在int内进行。内进行。1-2+3*(4-5)0构建构建(ujin)符号栈:符号栈:获取获取(huq)表达式字符串表达式字符串设计后缀表达式字符串设计后缀表达式字符串1 12 23 3*(4 45 5-构建数据栈:构建数据栈:运算运算=-1-1第15页/共21页第十六页,共21页。*-栈应用:表达式计算栈应用:表达式计算问题描述问题描述输入一个只包含加减乖除和括号的合法表达式,求表达式的值。其中除表示整除。输入一个只包含加减乖除和括号的合法表达式,求表达式的值。其中除表示整除。输入格式输入格式输入一行,包含一个表达式。输入一行,包含一个表达式。输出格式输出格式输出这个表达式的值。输出这个表达式的值。样例输入样例输入1-2+3*(4-5)样例输出样例输出-4数据规模和约定数据规模和约定表达式长度表达式长度(chngd)不超过不超过100,表达式运算合法且运算过程都在,表达式运算合法且运算过程都在int内进行。内进行。1-2+3*(4-5)0构建构建(ujin)符号栈:符号栈:获取获取(huq)表达式字符串表达式字符串设计后缀表达式字符串设计后缀表达式字符串3 34 45 5构建数据栈:构建数据栈:运算运算=-1-1+-1-1第16页/共21页第十七页,共21页。*栈应用:表达式计算栈应用:表达式计算问题描述问题描述输入一个只包含加减乖除和括号的合法表达式,求表达式的值。其中除表示整除。输入一个只包含加减乖除和括号的合法表达式,求表达式的值。其中除表示整除。输入格式输入格式输入一行,包含一个表达式。输入一行,包含一个表达式。输出输出(shch)格式格式输出输出(shch)这个表达式的值。这个表达式的值。样例输入样例输入1-2+3*(4-5)样例输出样例输出(shch)-4数据规模和约定数据规模和约定表达式长度不超过表达式长度不超过100,表达式运算合法且运算过程都在,表达式运算合法且运算过程都在int内进行。内进行。1-2+3*(4-5)0构建构建(ujin)符号栈:符号栈:获取获取(huq)表达式字符串表达式字符串设计后缀表达式字符串设计后缀表达式字符串构建数据栈:构建数据栈:运算运算=-1-1+3 3-1-1-3-3第17页/共21页第十八页,共21页。栈应用:表达式计算栈应用:表达式计算问题描述问题描述输入一个只包含加减乖除和括号的合法表达式,求表达式的值。其中除表示整除。输入一个只包含加减乖除和括号的合法表达式,求表达式的值。其中除表示整除。输入格式输入格式输入一行,包含一个表达式。输入一行,包含一个表达式。输出格式输出格式输出这个表达式的值。输出这个表达式的值。样例输入样例输入1-2+3*(4-5)样例输出样例输出-4数据规模和约定数据规模和约定(yudng)表达式长度不超过表达式长度不超过100,表达式运算合法且运算过程都在,表达式运算合法且运算过程都在int内进行。内进行。1-2+3*(4-5)0构建构建(ujin)符号栈:符号栈:获取获取(huq)表达式字符串表达式字符串设计后缀表达式字符串设计后缀表达式字符串构建数据栈:构建数据栈:运算运算=-1-1+-4-4-3-3第18页/共21页第十九页,共21页。栈应用:表达式计算栈应用:表达式计算问题描述问题描述输入一个只包含加减乖除和括号的合法表达式,求表达式的值。其中除表示整除。输入一个只包含加减乖除和括号的合法表达式,求表达式的值。其中除表示整除。输入格式输入格式输入一行,包含一个表达式。输入一行,包含一个表达式。输出格式输出格式输出这个表达式的值。输出这个表达式的值。样例输入样例输入1-2+3*(4-5)样例输出样例输出-4数据数据(shj)规模和约定规模和约定表达式长度不超过表达式长度不超过100,表达式运算合法且运算过程都在,表达式运算合法且运算过程都在int内进行。内进行。1-2+3*(4-5)0构建构建(ujin)符号栈:符号栈:获取获取(huq)表达式字符串表达式字符串设计后缀表达式字符串设计后缀表达式字符串构建数据栈:构建数据栈:运算运算-4-4需要思考一下数据是多位数时该怎么处理需要思考一下数据是多位数时该怎么处理需要思考一下数据是多位数时该怎么处理需要思考一下数据是多位数时该怎么处理?第19页/共21页第二十页,共21页。21THANK YOU第20页/共21页第二十一页,共21页。

    注意事项

    本文(数据结构之栈和队列应用学习教案.pptx)为本站会员(一***)主动上传,淘文阁 - 分享文档赚钱的网站仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对上载内容本身不做任何修改或编辑。 若此文所含内容侵犯了您的版权或隐私,请立即通知淘文阁 - 分享文档赚钱的网站(点击联系客服),我们立即给予删除!

    温馨提示:如果因为网速或其他原因下载失败请重新下载,重复下载不扣分。




    关于淘文阁 - 版权申诉 - 用户使用规则 - 积分规则 - 联系我们

    本站为文档C TO C交易模式,本站只提供存储空间、用户上传的文档直接被用户下载,本站只是中间服务平台,本站所有文档下载所得的收益归上传人(含作者)所有。本站仅对用户上传内容的表现方式做保护处理,对上载内容本身不做任何修改或编辑。若文档所含内容侵犯了您的版权或隐私,请立即通知淘文阁网,我们立即给予删除!客服QQ:136780468 微信:18945177775 电话:18904686070

    工信部备案号:黑ICP备15003705号 © 2020-2023 www.taowenge.com 淘文阁 

    收起
    展开