下载

1下载券

加入VIP
  • 专属下载特权
  • 现金文档折扣购买
  • VIP免费专区
  • 千万文档免费下载

上传资料

关闭

关闭

关闭

封号提示

内容

首页 数据结构实验三栈和队列的应用

数据结构实验三栈和队列的应用.doc

数据结构实验三栈和队列的应用

孤独的薰衣草在江湖
2017-09-29 0人阅读 举报 0 0 暂无简介

简介:本文档为《数据结构实验三栈和队列的应用doc》,可适用于高等教育领域

数据结构实验三栈和队列的应用第三章栈和队列的应用【实验目的】(熟练掌握栈和队列的结构以及这两种数据结构的特点(能够在两种存储结构上实现栈的基本运算特别注意栈满和栈空的判断条件及描述方法(熟练掌握链队列和循环队列的基本运算并特别注意队列满和队列空的判断条件和描述方法第一节知识准备一、栈:基本概念栈是一种限定仅在表的一端进行插入与删除操作的线性表。允许进行插入与删除操作的这一端称为栈顶而另一端称为栈底不含元素的空表称为空栈插入与删除分别称进栈与出栈。由于插入与删除只能在同一端进行所以较先进入栈的元素在进行出栈操作时要比较后才能出栈。特别是最先进栈者最后才能出栈而最晚进栈者必最先出栈。因此栈也称作后进先出(LastInFirstOut)的线性表简称LIFO表。栈示意图见图栈的抽象数据类型定义:ADTStack{数据对象:D={|ElemSet,i=,,,n,n>=}数据关系:R={<,>|,D,i=,,n}基本操作:InitStack(S)构造一个空栈SStackEmpty(S)判断栈S是否为空StackLength(S)返回栈S的元素个数,即栈的长度GetTop(S,e)取栈S的栈顶元素Push(S,e)将元素e入栈Pop(S,e)删除S的栈顶元素并用e返回其值(即出栈)}ADTStack栈的表示:栈有两种存储表示方法:顺序存储结构和链式存储结构。()顺序存储结构:#defineSTACKINITSIZE存储空间初始分配量#defineSTACKINCREMENT存储空间分配增量typedefstruct{SElemType*base栈底指针SElemType*top栈顶指针intStackSize栈的当前容量}SqStack()链式存储结构:TypedefstructLnode{ElemTypedatastructLnode*next}Lnode,*LinkList二、队列:与栈相对应队列是一种先进先出的线性表。它只允许在表的一端进行插入而在另一端进行删除元素。允许插入的一端称队尾允许删除的一端称队头。插入与删除分别称为入队与出队。队列示意图见图:出队aa„„anan进队队头队尾图队列队列的抽象数据类型定义:ADTQueue{数据对象:D={|ElemSet,i=,,,n,n>=}数据关系:R={<,>|,D,i=,,n}基本操作:InitQueue(Q)构造一个空队列QQueueEmpty(Q)判断队列是否为空QueueLenght(Q)返回队列Q的元素个数即队列的长度GetHead(Q,e)取队列Q的队头元素并用e返回EnQueue(Q,e)将元素e入队列DeQueue(Q,e)删除非空队列Q的队头元素并用e返回其值}ADTQueue队列的表示:队列有两种表示方法:链队列、循环队列(顺序队列)。()链队列的表示:typedefstructQNode{QElemTypedatastructQNode*next}QNode,*QueuePtrtypedefstruct{QueuePtrfrontQueuePtrrear}LinkQueue()循环队列的表示(见第二节)第二节循环队列的表示和实现【问题描述】设计一个抽象数据类型队列的顺序表示和实现的演示程序。【数据描述】#defineMaxQsize最大队列长度typedefstruct{QElemType*base初始化的动态分配存储空间intfront头指针若队列不空指向队列头元素intrear尾指针若队列不空指向队列尾元素的下一个位置}SqQueue【算法描述】StatusInitQueue(SqQueueQ){构造一个空队列QQbase=(QelemType*)malloc(MaxQsize*sizeof(QelemType))if(!Qbase)exit(OVERFLOW)存储分配失败Qfront=Qrear=returnOK}StatusQueueEmpty(SqQueueQ){若队列Q为空队列则返回TRUE否则返回FALSEif(Qfront,,Qrear)returnTRUEelsereturnFALSE}intQueueLength(SqQueueQ){返回Q的元素个数即为队列的长度return(QrearQfrontMaxQsize)MaxQsize}StatusGetHead(SqQueueQ,QelemTypee){若队列不为空则用e返回Q的队头元素并返回OK否则返回ERRORif(Qfront==Qrear)returnERRORe=QbaseQfrontreturnOK}StatusEnQueue(SqQueueQ,QelemTypee){插入元素e为Q的新的队尾元素if((Qrear)MaxQsize==Qfront)returnERROR队列满QbaseQrear=eQrear=(Qrear)MaxQsizereturnOK}StatusDeQueue(SqQueueQ,QelemTypee){若队列不空则删除Q的队头元素用e返回其值并返回OK,否则返回ERRORif(Qrear==Qfront)returnERROR队列空e=QbaseQfrontQfront=(Qfront)MaxQsizereturnOK}【C源程序】#include<stdioh>#include<stdlibh>typedefintQElemTypetypedefintStatus#defineOK#defineTRUE#defineFALSE#defineERROR#defineOVERFLOW#defineMaxQsize*最大队列长度*typedefstruct{QElemType*base*初始化的动态分配存储空间*intfront*头指针若队列不空指向队列头元素*intrear*尾指针若队列不空指向队列尾元素的下一个位置*}SqQueueStatusInitQueue(SqQueue*Q){*构造一个空队列Q*(*Q)base=(QElemType*)malloc(MaxQsize*sizeof(QElemType))if(!(*Q)base)return(OVERFLOW)*存储分配失败*(*Q)front=(*Q)rear=returnOK}StatusQueueEmpty(SqQueueQ){*若队列Q为空队列则返回TRUE否则返回FALSE*if(Qfront==Qrear)returnTRUEelsereturnFALSE}intQueueLength(SqQueueQ){*返回Q的元素个数即为队列的长度*return(QrearQfrontMaxQsize)MaxQsize}StatusGetHead(SqQueueQ,QElemType*e){*若队列不为空则用e返回Q的队头元素并返回OK否则返回ERROR*if(Qfront==Qrear)returnERROR*e=QbaseQfrontreturnOK}StatusEnQueue(SqQueue*Q,QElemTypee){*插入元素e为Q的新的队尾元素*if(((*Q)rear)MaxQsize==(*Q)front)returnERROR*队列满*(*Q)base(*Q)rear=e(*Q)rear=((*Q)rear)MaxQsizereturnOK}StatusDeQueue(SqQueue*Q,QElemType*e){*若队列不空则删除Q的队头元素用e返回其值并返回OK,否则返回ERROR*if((*Q)rear==(*Q)front)returnERROR*队列空**e=(*Q)base(*Q)front(*Q)front=((*Q)front)MaxQsizereturnOK}main(){SqQueueQintselectQElemTypeeif(InitQueue(Q)==OVERFLOW)printf("分配失败即将退出程序~")else*否则显示队列操作的菜单并选择相应的基本操作*do{printf(":判断队列是否为空n")printf(":测试队列的长度n")printf(":取队头元素值n")printf(":向队列中插入一新元素n")printf(":删除队列中一元素n")printf(":结束n")scanf("d",select)switch(select){case:if(QueueEmpty(Q)==TRUE)printf("队列为空n")elseprintf("队列不为空n")breakcase:printf("队列长度为:dn",QueueLength(Q))breakcase:if(GetHead(Q,e)==ERROR)printf("队列为空n")elseprintf("队首元素为:dn",e)breakcase:scanf("d",e)if(EnQueue(Q,e)==ERROR)printf("队列满n")elseprintf("元素成功插入n")breakcase:if(DeQueue(Q,e)==ERROR)printf("队列空,无数据可删n")elseprintf("删除元素为:dn",e)breakcase:printf("操作结束n")breakdefault:printf("输入选择出错~n")}*switch*}while(select)}*mainend*【测试数据】读者根据运行提示和显示的功能菜单实现循环队列的基本操作。【说明】此题是使用动态顺序存储方式来存放循环队列。特别注意循环队列中队空和队满的判断条件。【实验题】请用链式存储方式表示队列并实现队列的基本操作。第三节计算表达式的值【问题描述】计算用运算符后缀法表示的表达式的值。后缀表达式也称逆波兰表达式比中缀表达式计算起来更方便简单些中缀表达式要计算就存在着括号的匹配问题所以在计算表达式值时一般都是先转换成后缀表达式再用后缀法计算表达式的值。如:表达式(ab*c)de用后缀法表示应为abc*de。只考虑四则算术运算且假设输入的操作数均为位十进制数()并且输入的后缀形式表达式不含语法错误。【数据描述】#defineadd*运算符加号‘’的ASCII码*#definesubs*运算符减号‘’的ASCII码*#definemult*运算符乘号‘*’的ASCII码*#definediv*运算符除号‘’的ASCII码*#defineMAXSIZEtypedefstruct{{intstkdataMAXSIZE用数组来表示栈空间定义长度为MAXSIZE的栈inttop栈顶指针}STKzonetypedefSTKzone*STKtypedefenum{true=,false=}booltypedefenum{ok,error}status【算法描述】用流程图表示见图。【C源程序】#include<stdioh>#defineadd*运算符加号‘’的ASCII码*#definesubs*运算符减号‘’的ASCII码*#definemult*运算符乘号‘*’的ASCII码*#definediv*运算符除号‘’的ASCII码*#defineMAXSIZEtypedefstruct{intstkdataMAXSIZE*用数组来表示栈空间定义长度为MAXSIZE的堆栈*inttop*栈顶*}STKzonetypedefSTKzone*STKtypedefenum{true=,false=}booltypedefenum{ok,error}statusSTKzoneexpSTKzoneSTKexpSTKSTKinitSTK(STKzone*stackzone){*执行栈初始化建栈指针*STKpp=stackzonep>top=}statuspush(int*term,STKpstk){*将一结构型数据送入栈中*if(pstk>top==MAXSIZE)returnerror*栈满进栈失败*pstk>stkdatapstk>top=*term(pstk>top)*栈顶指针移动*returnok}*push*boolemptySTK(STKpstk){*判断栈是否为空栈*return(pstk>top==)}statuspop(int*pdata,STKpstk){*从栈中取出一结构型数据*if(emptySTK(pstk))returnerror(pstk>top)*退栈**pdata=pstk>stkdatapstk>topreturnok}voidsynerror(){printf("n表达式语法错~")exit()}inteval(chartag,inta,inta){switch(tag){caseadd:return(aa)casesubs:return(aa)casemult:return(a*a)casediv:return(aa)}}main(){charcintopd,opd,temp,cexpSTK=initSTK(expSTKzone)printf("n后置表达式:")while((c=getchar())!='n'){if(c=='')continueif((c>)(c<))*判断是否是的字符*{putchar(c)c=c*把输入的字符型数字转换成数字*if(push(c,expSTK)==error)*运算分量进栈*{printf("n表达式太长n")exit()}}elseif((c==add)||(c==subs)||(c==mult)||(c==div)){putchar(c)if(pop(opd,expSTK)==error)*将运算量出栈*synerror()if(pop(opd,expSTK)==error)*将运算量出栈*synerror()temp=eval(c,opd,opd)*计算得到结果*push(temp,expSTK)*将运算结果进栈*}elsesynerror()*出现非法字符*}*while*if(pop(opd,expSTK)==error)synerror()if(!(emptySTK(expSTK)))synerror()printf(“=dn”,opd)}*mainend*【测试数据】输入:输出:=(即求的结果)输入:*输出:(即求(*)的结果)【说明】本算法中对后置法表示的表达式求值按如下规则进行:自左向右扫描每遇到一个`n元组(opd,opd,„,opdn,opr)(其中opd为操作数opr为n元运算符)就计算一次opr(opd,opd,„,opdn)的值其结果取代原来表达式中n元组的位置再从表达式开头重复上述过程直到表达式中不含运算符为止。【实验题】假设一个算术表达式中包含零对到多对圆括弧括弧对之间允许嵌套但不允许交叉编写一个算法并上机实现:判断输入的表达式是否正确配对。Statuscorrect(stringexpress)括弧配对正确返回ok否则返回error用栈实现一般表达式(即中缀表达式)到后缀表达式的转换。第四节模拟服务台前的排队现象问题【问题描述】某银行有一个客户办理业务站在单位时间内随机地有客户到达设每位客户的业务办理时间是某个范围内的随机值。设只有一个窗口一位业务人员要求程序模拟统计在设定时间内业务人员的总空闲时间和客户的平均等待时间。假定模拟数据已按客户到达的先后顺序依次存于某个正文数据文件中。对应每位客户有两个数据到达时间和需要办理业务的时间。【数据描述】typedefstruct{intarriveinttreat客户的信息结构}QNODEtypedefstructnode{QNODEdataStructnode*next队列中的元素信息}LNODELNODE*front,*rear队头指针和队尾指针【算法描述】{设置统计初值设置当前时钟时间为打开数据文件准备读读入第一位客户信息于暂存变量中do{约定每轮循环处理完一位客户if(等待队列为空并且还有客户){等待队列为空时累计业务员总等待时间时钟推进到暂存变量中的客户的到达时间暂存变量中的客户信息进队读取下一位客户信息于暂存变量}累计客户人数从等待队列出队一位客户将该客户的等待时间累计到客户的总等待时间设定当前客户的业务办理结束时间while(下一位客户的到达时间在当前客户处理结束之前){暂存变量中的客户信息进队读取下一位客户信息于暂存变量}时钟推进到当前客户办理结束时间}while(还有未处理的客户)计算统计结果并输出【C源程序】#include<stdioh>#include<stdlibh>#defineOVERFLOWtypedefstruct{intarriveinttreat*客户的信息结构*}QNODEtypedefstructnode{QNODEdatastructnode*next*队列中的元素信息*}LNODELNODE*front,*rear*队头指针和队尾指针*QNODEcurr,tempcharFnameFILE*fpvoidEnQueue(LNODE**hpt,LNODE**tpt,QNODEe){*队列进队*LNODE*p=(LNODE*)malloc(sizeof(LNODE))if(!p)exit(OVERFLOW)*存储分配失败*p>data=ep>next=if(*hpt==)*tpt=*hpt=pelse*tpt=(*tpt)>next=p}intDeQueue(LNODE**hpt,LNODE**tpt,QNODE*cp){*链接队列出队*LNODE*p=*hptif(*hpt==)return*队空**cp=(*hpt)>data*hpt=(*hpt)>nextif(*hpt==)*tpt=free(p)return}voidmain(){intdwait=,clock=,wait=,count=,have=,finishprintf("nenterfilename:")scanf("s",Fname)*输入装客户模拟数据的文件的文件名*if((fp=fopen(Fname,"r"))==){*打开数据文件*printf("cannotopenfiles",Fname)return}front=rear=have=fscanf(fp,"ds",temparrive,temptreat)do{*约定每轮循环处理一位客户*if(front==have==){*等待队列为空但还有客户*dwait=temparriveclock*累计业务员总等待时间*clock=temparrive*时钟推进到暂存变量中的客户的到达时间*EnQueue(front,rear,temp)*暂存变量中的客户信息进队*have=fscanf(fp,"dd",temparrive,temptreat)}count*累计客户人数*DeQueue(front,rear,curr)*出队一位客户信息*wait=clockcurrarrive*累计到客户的总等待时间*finish=clockcurrtreat*设定业务办理结束时间*while(have==temparrive<=finish){*下一位客户的到达时间在当前客户处理结束之前*EnQueue(front,rear,temp)*暂存变量中的客户信息进队*have=fscanf(fp,"dd",temparrive,temptreat)}clock=finish*时钟推进到当前客户办理结束时间*}while(have==||front!=)printf("结果:业务员等待时间dn客户平均等待时间fn",dwait,(double)waitcount)printf("模拟总时间:dn客户人数:d,n总等待时间:dn",clock,count,wait)getch()}*mainend*’【测试数据】设数据装在一个数据文件datadat中内容为:显示结果为:enterfilename:datadat结果:业务员等待时间客户平均等待时间模拟总时间:客户人数:,总等待时间:【说明】在计算程序中程序按模拟环境中的事件出同顺序逐一处理事件:当一个事件结束时下一个事件隔一段时间才发生则程序逻辑的模拟时钟立即推进到下一事件的发生时间如一个事件还未处理结束之前另有其他事件等待处理则这些事件就应依次排队等候处理。【实验题】进行医务室模定。假设只有一个医生在一小时内随机地来几个病人每个病人所需处理时间为分钟之间某个随机数。要求程序模拟统计在设定时间内医生的总空闲时间和病人的平均等待时间。第五节思考题背包问题。假设有一个背包可装入总重量为T的物件。现在n个物件其重量分别为w,w,„,wn,问能否从这n个物件中选择若干件放入背包使它们的重量之和恰为T。若能找到满足上述条件的一组解则称此问题有解否则无解。【简要分析】此题有两种解法可用递归算法或非递归算法。可以采用这样的选取方法:n个物件中选取一个wi得到剩下的重量为:S=Twi则判断S的值若S=则已找到一种解完成若S<,则此种解法造成无解则不选刚才的物件重选未选取的物件重新操作若S>,并且还有未选取的物件则再选取下一未选取的物件并按前面的方法继续执行。对递归算法若函数bb(s,n)为背包问题的解法则不包含物件wn时bb(s,n)的解是bb(s,n)即重量(指背包中余下的重量)不变选下一物件若选取中包含物件wn时bb(s,n)的解是bb(swn,n)即重量减少并再去选取下一物件。对非递归算法需建一堆栈空间从第一物件选起选中的就进栈保存未选中的就跳过再选下一个合适的物件进栈。直到使S为零并输出堆栈中的结果否则输出无解。操作系统作业调度模拟。【简要分析】假设有几个作业运行。如果都需要请求CPU则可以让作业按先后顺序排队每当CPU处是完一个作业后就可以接受新的作业这时队列中队头的作业先退出进行处理。后来的作业排在队尾。此题算法跟模拟服务台前的排队现象问题相似假定只有一个CPU但为了防止一个作业占用CPU太久可规定每个作业一次最长占用CPU的时间(称时间片)如果时间片到作业未完成则此作业重新进入等待队列等到下次占有CPU时继续处理。已知Ackermann函数定义如下:()写出Ack()的计算过程。()写出计算的非递归算法。(北京航空航天大学年硕士生入学考试))可用(m,n)表示。这样一直循环下去直到n=,则再将(m,)进栈又循环操作直到m=,则可计算出栈顶结点的值(即B=n)退栈(栈顶减)并将B回填到新的栈顶结点。这样按同样的方法去循环直到栈空则最后一次的B值就是我们的计算结果。,,n,)实际操作时(m,n)已进栈则结点(m,n,)进栈再求出Ack(m,,n,=n)则又要先将(m,=mn,)(其中m,,n,【简要分析】我们借助于栈来实现非递归算法。栈的作用是:保存调用函数前的实参值并保存计算出来的各中间值。令要求的结点为(m,n)则函数Ack(mn)求解时要先求出Ack(mn)则先将结点(m,n)进栈而要求解Ack(mn)函数时令新结点为(mApplicationsofStackandQueueChapterThreeObjectivesTobetterunderstandthestructureofstack,queueandthefeaturesofthesetwodatastructuresTobeabletoimplementbasiccomputationofstackupontwokindsofstructuresEspecially,payattentiontothequalificationforStackFullandStackEmptyTobetterunderstandbasiccomputationofLinkqueueandCircularqueueEspecially,paymoreattentiontothequalificationanddescriptionforQueueFull,QueueEmpty

VIP免券下载文档

用户评价(0)

关闭

新课改视野下建构高中语文教学实验成果报告(32KB)

抱歉,积分不足下载失败,请稍后再试!

提示

试读已结束,如需要继续阅读或者下载,敬请购买!

文档小程序码

使用微信“扫一扫”扫码寻找文档

1

打开微信

2

扫描小程序码

3

发布寻找信息

4

等待寻找结果

我知道了
评分:

/20

数据结构实验三栈和队列的应用

VIP

在线
客服

免费
邮箱

爱问共享资料服务号

扫描关注领取更多福利