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

《数据结构之栈和队列应用学习教案.pptx》由会员分享，可在线阅读，更多相关《数据结构之栈和队列应用学习教案.pptx（21页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、会计学1数据结构之栈和队列数据结构之栈和队列(duli)应用应用第一页，共21页。前言(qin yn)Introduction 数据结构(sh j ji u)是计算机存储、组织数据的方式。是指相互之间存在一种或多种特定关系的数据元素的集合。通常情况下，精心选择的数据结构(sh j ji u)可以带来更高的运行或者存储效率。数据结构(sh j ji u)具体指同一类数据元素中，各元素之间的相互关系，包括三个组成成分，数据的逻辑结构，数据的存储结构和数据的运算。逻辑结构就是数据之间的关系。而按数据之间的关系来说，逻辑结构大概可以分为两种：线性结构和非线性结构（集合、树、网）。存储结构是逻辑结构的存

2、储映像。常见的存储结构有顺序存储、链式存储、索引存储以及散列存储（哈希表）。第1页/共21页第二页，共21页。线性表线性表线性表（线性表（Linear listLinear list）是最简单且最常用的一种数据结构。这种结构具有下列特点：）是最简单且最常用的一种数据结构。这种结构具有下列特点：存在一个唯一的没有前驱的（头）数据元素；存在一个唯一的没有前驱的（头）数据元素；存在一个唯一的没有后继的（尾）数据元素；存在一个唯一的没有后继的（尾）数据元素；每一个数据元素均有一个直接前驱和一个直接后继的数据元素。每一个数据元素均有一个直接前驱和一个直接后继的数据元素。例如：例如：英文字母表（英文字母表

3、（A A，B B，C C，Z Z）是一个长度为）是一个长度为2626的线性表，其中的每一个字母就是的线性表，其中的每一个字母就是(jish)(jish)一个数据元素；一个数据元素；某公司某公司20062006年每月产值表（年每月产值表（400400，420420，500500，600600，650650）(单位：万元单位：万元)是一个长度为是一个长度为1212的线性表，其中的每一个数值的线性表，其中的每一个数值就是就是(jish)(jish)一个数据元素。一个数据元素。ABCDEZ400420500600650第2页/共21页第三页，共21页。栈与队列栈与队列栈和队列也是线性表，不过是两种特殊

4、的线性表。栈和队列也是线性表，不过是两种特殊的线性表。栈只允许栈只允许(ynx)在表的一端进行插入或删除操作，而队列只允许在表的一端进行插入或删除操作，而队列只允许(ynx)在表的一端进行插入操作、而在另一端进行删除操作。因而，在表的一端进行插入操作、而在另一端进行删除操作。因而，栈和队列也可以被称作为操作受限的线性表。栈和队列也可以被称作为操作受限的线性表。栈：栈：topbottom进栈进栈出栈出栈ana2a1a0允许插入允许插入(chr)和删除的一端称为栈顶和删除的一端称为栈顶(top)，另一端称为栈底，另一端称为栈底(bottom)第一个进栈的元素第一个进栈的元素(yuns)在栈底，在栈

5、底，最后一个进栈的元素最后一个进栈的元素(yuns)在栈顶，在栈顶，第一个出栈的元素第一个出栈的元素(yuns)为栈顶元素为栈顶元素(yuns)，最后一个出栈的元素最后一个出栈的元素(yuns)为栈底元素为栈底元素(yuns)栈的特点：后进先出栈的特点：后进先出LIFO（Last In First Out）第3页/共21页第四页，共21页。栈与队列栈与队列栈和队列也是线性表，不过是两种特殊的线性表。栈和队列也是线性表，不过是两种特殊的线性表。栈只允许在表的一端进行插入或删除栈只允许在表的一端进行插入或删除(shnch)操作，而队列只允许在表的一端进行插入操作、而在另一端进行删除操作，而队列只允

6、许在表的一端进行插入操作、而在另一端进行删除(shnch)操作。因而，栈和队列操作。因而，栈和队列也可以被称作为操作受限的线性表。也可以被称作为操作受限的线性表。队列队列(duli)：出队出队进队进队队首队首(head)队尾队尾(tail)qn-1qi+1qiq1q0允许允许(ynx)插入的一端称为队尾（插入的一端称为队尾（tail），另一端称为队头），另一端称为队头(head)第一第一个个进队的进队的元素元素在队首，在队首，最后最后一个一个进队的进队的元素元素在队尾，在队尾，第一第一个个出队的出队的元素元素为队首元素为队首元素，最后最后一个一个出队的出队的元素元素为队尾元素为队尾元素队列的特

7、点：先进先出队列的特点：先进先出FIFO（First In First Out）第4页/共21页第五页，共21页。栈应用：括号匹配栈应用：括号匹配问题描述问题描述现在，有一行括号序列，请你检查这行括号是否配对。现在，有一行括号序列，请你检查这行括号是否配对。输入输入第一行输入一个数第一行输入一个数N（0N=100）,表示有表示有N组测试数据。后面的组测试数据。后面的N行输入多组输入数据，每组输入数据都是一个字符串行输入多组输入数据，每组输入数据都是一个字符串S(S的长度小于的长度小于10000，且，且S不是空串），测试数据组数少于不是空串），测试数据组数少于5组。数据保证组。数据保证S中只含有

8、中只含有(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(

9、)=()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页。问题描述问题描述某部队进行新兵队列训练，将新兵从一开始按顺序依次编号，并排成一行横队，训练的规则如下：从头开始一至二报数，凡报到二的出列，剩下的向某部队进行新兵队列训练，将新兵从一开始按顺序依次编号，并排成一行横队，训练的规则如下：从头开始一至二报数，凡报到二的出列，剩下的向小序号方向靠小序号方向靠拢，再从头开

10、始进行一至三报数，凡报到三的出列，剩下的向小序号方向靠拢，继续从头开始进行一至二报数，以后从头开始轮流进拢，再从头开始进行一至三报数，凡报到三的出列，剩下的向小序号方向靠拢，继续从头开始进行一至二报数，以后从头开始轮流进行一至二报数、一至三报数，直到剩下的人数不超过三人为止。行一至二报数、一至三报数，直到剩下的人数不超过三人为止。Input本题有多个测试数据组，第一行为组数本题有多个测试数据组，第一行为组数N，接着为，接着为N行新兵人数，新兵人数不超过行新兵人数，新兵人数不超过5000。Output共有共有N行，分别对应行，分别对应(duyng)输入的新兵人数，每行输出剩下的新兵最初的编号，编

11、号之间有一个空格。输入的新兵人数，每行输出剩下的新兵最初的编号，编号之间有一个空格。SampleInput22040SampleOutput171911937构建构建(ujin)队列队列1：构建构建(ujin)队列队列2：1357911131517191234567111213141516171819208910队列应用：新兵训练队列应用：新兵训练队首队首队首队首第6页/共21页第七页，共21页。问题描述问题描述某部队进行新兵某部队进行新兵(xnbn)队列训练，将新兵队列训练，将新兵(xnbn)从一开始按顺序依次编号，并排成一行横队，训练的规则如下：从头开始一至从一开始按顺序依次编号，并排成一

12、行横队，训练的规则如下：从头开始一至二报数，凡报到二的出列，剩下的向小序号方向靠二报数，凡报到二的出列，剩下的向小序号方向靠拢，再从头开始进行一至三报数，凡报到三的出列，剩下的向小序号方向靠拢，继续拢，再从头开始进行一至三报数，凡报到三的出列，剩下的向小序号方向靠拢，继续从头开始进行一至二报数，以后从头开始轮流进行一至二报数、一至三报数，直到剩下的人数不超过三人为止。从头开始进行一至二报数，以后从头开始轮流进行一至二报数、一至三报数，直到剩下的人数不超过三人为止。Input本题有多个测试数据组，第一行为组数本题有多个测试数据组，第一行为组数N，接着为，接着为N行新兵行新兵(xnbn)人数，新兵

13、人数，新兵(xnbn)人数不超过人数不超过5000。Output共有共有N行，分别对应输入的新兵行，分别对应输入的新兵(xnbn)人数，每行输出剩下的新兵人数，每行输出剩下的新兵(xnbn)最初的编号，编号之间有一个空格。最初的编号，编号之间有一个空格。SampleInput22040SampleOutput171911937构建构建(ujin)队列队列1：构建构建(ujin)队列队列2：1357911131517191379131519队列应用：新兵训练队列应用：新兵训练队首队首队首队首第7页/共21页第八页，共21页。问题描述问题描述某部队进行新兵队列训练，将新兵从一开始按顺序依次编号，并

14、排成一行横队，训练的规则如下：从头开始一至二报数，凡报到二的出列，剩下的向小序号方向靠某部队进行新兵队列训练，将新兵从一开始按顺序依次编号，并排成一行横队，训练的规则如下：从头开始一至二报数，凡报到二的出列，剩下的向小序号方向靠 拢，拢，再从头开始进行一至三报数，凡报到三的出列，剩下的向小序号方向靠拢再从头开始进行一至三报数，凡报到三的出列，剩下的向小序号方向靠拢(kolng)，继续从头开始进行一至二报数，以后从头开始轮流进行一至二报数、一至三报，继续从头开始进行一至二报数，以后从头开始轮流进行一至二报数、一至三报数，直到剩下的人数不超过三人为止。数，直到剩下的人数不超过三人为止。Input本

15、题有多个测试数据组，第一行为组数本题有多个测试数据组，第一行为组数N，接着为，接着为N行新兵人数，新兵人数不超过行新兵人数，新兵人数不超过5000。Output共有共有N行，分别对应输入的新兵人数，每行输出剩下的新兵最初的编号，编号之间有一个空格。行，分别对应输入的新兵人数，每行输出剩下的新兵最初的编号，编号之间有一个空格。SampleInput22040SampleOutput171911937构建构建(ujin)队列队列1：构建构建(ujin)队列队列2：1713191379131519队列应用：新兵训练队列应用：新兵训练队首队首队首队首第8页/共21页第九页，共21页。问题描述问题描述某

16、部队进行新兵队列训练，将新兵从一开始按顺序依次编号，并排成一行横队，训练的规则如下：从头开始一至二报数，凡报到二的出列，剩下的向某部队进行新兵队列训练，将新兵从一开始按顺序依次编号，并排成一行横队，训练的规则如下：从头开始一至二报数，凡报到二的出列，剩下的向小序号方向靠小序号方向靠拢，再从头开始进行一至三报数，凡报到三的出列，剩下的向小序号方向靠拢，继续从头开始进行一至二报数，以后从头开始轮流进拢，再从头开始进行一至三报数，凡报到三的出列，剩下的向小序号方向靠拢，继续从头开始进行一至二报数，以后从头开始轮流进行一至二报数、一至三报数，直到剩下的人数不超过三人为止。行一至二报数、一至三报数，直到

17、剩下的人数不超过三人为止。Input本题有多个测试数据组，第一行为组数本题有多个测试数据组，第一行为组数N，接着为，接着为N行新兵人数，新兵人数不超过行新兵人数，新兵人数不超过5000。Output共有共有N行，分别对应输入的新兵人数，每行输出行，分别对应输入的新兵人数，每行输出(shch)剩下的新兵最初的编号，编号之间有一个空格。剩下的新兵最初的编号，编号之间有一个空格。SampleInput22040SampleOutput171911937构建构建(ujin)队列队列1：构建构建(ujin)队列队列2：1713 191719队列应用：新兵训练队列应用：新兵训练队首队首队首队首第9页/共2

18、1页第十页，共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,i

19、nt 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页。栈应用：表达式计算栈应用：表达式计算问题描述问题描述输入一个只包含加

20、减乖除和括号的合法表达式，求表达式的值。其中除表示整除。输入一个只包含加减乖除和括号的合法表达式，求表达式的值。其中除表示整除。输入格式输入格式输入一行输入一行(yxng)，包含一个表达式。，包含一个表达式。输出格式输出格式输出这个表达式的值。输出这个表达式的值。样例输入样例输入1-2+3*(4-5)样例输出样例输出-4数据规模和约定数据规模和约定表达式长度不超过表达式长度不超过100，表达式运算合法且运算过程都在，表达式运算合法且运算过程都在int内进行。内进行。1-2+3*(4-5)0构建构建(ujin)符号栈：符号栈：获取获取(huq)表达式字符串表达式字符串构建操作数栈：构建操作数栈：

21、#+-*/()+-*/(#-*/(#-*/(#-*/(#-1-1运算运算+-3-3=-4-4值得注意的有几个地方：值得注意的有几个地方：数据存在负数（即数据存在负数（即“-”是单目运算符）是单目运算符）数据是多位数数据是多位数第14页/共21页第十五页，共21页。+-栈应用：表达式计算栈应用：表达式计算问题描述问题描述输入一个只包含加减乖除和括号的合法表达式，求表达式的值。其中除表示整除。输入一个只包含加减乖除和括号的合法表达式，求表达式的值。其中除表示整除。输入格式输入格式输入一行，包含一个表达式。输入一行，包含一个表达式。输出格式输出格式输出这个表达式的值。输出这个表达式的值。样例输入样例

22、输入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页。*-栈应用：表达式计算栈应用：表达式计算问题描述问题描述输入一个只包含加减乖除和括号的合法表达式，求表达式的值。其中除表示整除。输入一

23、个只包含加减乖除和括号的合法表达式，求表达式的值。其中除表示整除。输入格式输入格式输入一行，包含一个表达式。输入一行，包含一个表达式。输出格式输出格式输出这个表达式的值。输出这个表达式的值。样例输入样例输入1-2+3*(4-5)样例输出样例输出-4数据规模和约定数据规模和约定表达式长度表达式长度(chngd)不超过不超过100，表达式运算合法且运算过程都在，表达式运算合法且运算过程都在int内进行。内进行。1-2+3*(4-5)0构建构建(ujin)符号栈：符号栈：获取获取(huq)表达式字符串表达式字符串设计后缀表达式字符串设计后缀表达式字符串3 34 45 5构建数据栈：构建数据栈：运算运

24、算=-1-1+-1-1第16页/共21页第十七页，共21页。*栈应用：表达式计算栈应用：表达式计算问题描述问题描述输入一个只包含加减乖除和括号的合法表达式，求表达式的值。其中除表示整除。输入一个只包含加减乖除和括号的合法表达式，求表达式的值。其中除表示整除。输入格式输入格式输入一行，包含一个表达式。输入一行，包含一个表达式。输出输出(shch)格式格式输出输出(shch)这个表达式的值。这个表达式的值。样例输入样例输入1-2+3*(4-5)样例输出样例输出(shch)-4数据规模和约定数据规模和约定表达式长度不超过表达式长度不超过100，表达式运算合法且运算过程都在，表达式运算合法且运算过程都

25、在int内进行。内进行。1-2+3*(4-5)0构建构建(ujin)符号栈：符号栈：获取获取(huq)表达式字符串表达式字符串设计后缀表达式字符串设计后缀表达式字符串构建数据栈：构建数据栈：运算运算=-1-1+3 3-1-1-3-3第17页/共21页第十八页，共21页。栈应用：表达式计算栈应用：表达式计算问题描述问题描述输入一个只包含加减乖除和括号的合法表达式，求表达式的值。其中除表示整除。输入一个只包含加减乖除和括号的合法表达式，求表达式的值。其中除表示整除。输入格式输入格式输入一行，包含一个表达式。输入一行，包含一个表达式。输出格式输出格式输出这个表达式的值。输出这个表达式的值。样例输入样

26、例输入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页。栈应用：表达式计算栈应用：表达式计算问题描述问题描述输入一个只包含加减乖除和括号的合法表达式，求表达式的值。其中除表示整除。输入一个只包含加减乖除和括

27、号的合法表达式，求表达式的值。其中除表示整除。输入格式输入格式输入一行，包含一个表达式。输入一行，包含一个表达式。输出格式输出格式输出这个表达式的值。输出这个表达式的值。样例输入样例输入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页。