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

上传资料

关闭

关闭

关闭

封号提示

内容

首页 栈和队列其应用、迷宫求解

栈和队列其应用、迷宫求解.doc

栈和队列其应用、迷宫求解

tian鹏田
2017-09-29 0人阅读 举报 0 0 暂无简介

简介:本文档为《栈和队列其应用、迷宫求解doc》,可适用于IT/计算机领域

栈和队列其应用、迷宫求解课程设计(论文)任务书信息学院计算机专业班一、课程设计(论文)题目栈和队列其应用、迷宫求解二、课程设计(论文)工作自年月日起至年月日止。三、课程设计(论文)地点:、四、课程设计(论文)内容要求:(本课程设计的目的、使学生进一步理解和掌握课堂上所学各种基本抽象数据类型的逻辑结构、存储结构和操作实现算法以及它们在程序中的使用方法。、使学生掌握软件设计的基本内容和设计方法并培养学生进行规范化软件设计的能力。、使学生掌握使用各种计算机资料和有关参考资料提高学生进行程序设计的基本能力。(课程设计的任务及要求)基本要求:分析题目查阅相关资料算法设计、数据结构设计编写代码并调试完成课程设计报告。)创新要求:在基本要求达到后可进行创新设计。)课程设计论文编写要求()要按照书稿的规格打印誊写毕业论文()论文包括目录、绪论、正文、小结、参考文献、谢辞、附录等()毕业论文装订按学校的统一要求完成)答辩与评分标准:()完成问题的解决方法分析:分()算法思想(流程):分()数据结构:分()测试数据:分()回答问题:分。)参考文献:《C程序设计》(第二版)潭浩强著清华大学出版社出版《C程序设计》潭浩强著清华大学出版社出版《数据结构》(C语言版)严蔚敏、吴伟民著清华大学出版社出版)课程设计进度安排内容天数地点构思及收集资料图书馆编程与调试实验室撰写论文学生签名:年月日课程设计(论文)评审意见()完成问题分析(分):优()、良()、中()、一般()、差()()算法思想(分):优()、良()、中()、一般()、差()()数据结构(分):优()、良()、中()、一般()、差()()测试数据(分):优()、良()、中()、一般()、差()()回答问题(分):优()、良()、中()、一般()、差()()格式规范性及考勤是否降等级:是()、否()评阅人:赵海霞职称:讲师年月日目录一、课程设计目的二、课程设计内容三、基本题四、综合应用题五、测试数据六、课程设计总结七、参考文献本课程设计的目的、使学生进一步理解和掌握课堂上所学各种基本抽象数据类型的逻辑结构、存储结构和操作实现算法以及它们在程序中的使用方法。、使学生掌握软件设计的基本内容和设计方法并培养学生进行规范化软件设计的能力。、使学生掌握使用各种计算机资料和有关参考资料提高学生进行程序设计的基本能力。本课程设计的内容栈和队列其应用目的在于使读者深入了解栈和队列的特性以便在实际问题背景下灵活运用他们同时还将巩固对这两种结构的构造方法的掌握接触较复杂问题的递归算法设计。():算术表达式转波兰表达式和逆波兰表达式():栈列操作的验证(建栈、入栈、出栈、销毁栈)():判断表达式中括弧是否正确配对():队列元素倒置():判断字符串是否回文():字符串的基本操作(个基本函数实现)迷宫求解任务:可以输入一个任意大小的迷宫数据用非递归的方法求出一条走出迷宫的路径并将路径输出基本题栈和队列及其应用目的在于使读者深入了解栈和队列的特性以便在实际问题背景下灵活运用他们同时还将巩固对这两种结构的构造方法的掌握接触较复杂问题的递归算法设计ADTStack的表示和实现#include<malloch>#defineSTACKINITSIZE#defineSTACKINCREMENTtypedefstruct{char*basechar*topintstacksize}sqstackvoidInitStack(sqstacks){sbase=(char*)malloc(STACKINITSIZE*sizeof(char))if(!sbase)exit(OVERFLOW)stop=sbasesstacksize=STACKINITSIZE}voidpush(sqstacks,charc){if(stopsbase>=sstacksize){sbase=(char*)realloc(sbase,(sstacksizeSTACKINCREMENT)*sizeof(char))if(!sbase)exit(OVERFLOW)stop=sbasesstacksizesstacksize=STACKINCREMENT}*stop=c}voidpop(sqstacks,charc){if(!(stop==sbase))c=*stop}intstackEmpty(sqstacks){if(sbase==stop)return()return()}算术表达式转波兰表达式和逆波兰表达式#include<stdioh>#include<ctypeh>voidtransform(char*str,inta,int*n){inti*n=a=a='('for(i=stri){if(isdigit(stri)){a*n=a*n=while(isdigit(stri)){a*n=a*n*stri''i}}else{if(stri=='(')a*n=elseif(stri==')')a*n=elseif(stri=='*')a*n=elseif(stri=='')a*n=elseif(stri==''||stri==''){if(i==||(!isdigit(stri)stri!=')')){a*n=a*n=(*n)}if(stri=='')a*n=elsea*n=}a*n=strii}(*n)}a*n=a*n=')'(*n)}voidpoland(inta,intn,intp,int*m){intiintstack转化所用的栈intdepth栈的深度depth=*m=for(i=i<ni){if(ai==)stackdepth=ielseif(ai==)stackdepth=ielseif(ai==){while(astackdepth!=){depthp*m=astackdepthp*m=astackdepth(*m)}depth}elseif(ai==||ai==){while(astackdepth==||astackdepth==||astackdepth==){depthp*m=astackdepthp*m=astackdepth(*m)}stackdepth=i}elseif(ai==||ai==){while(astackdepth!=){depthp*m=astackdepthp*m=astackdepth(*m)}stackdepth=i}}}voidprintpoland(intp,intm){intifor(i=i<mi){if(pi==)printf("d",pi)elseprintf("c",pi)}putchar('n')}doubleevaluate(intp,intm){doublestack求值所用的栈intdepth栈的深度intidepth=for(i=i<mi){if(pi==)stackdepth=pielse{doublea,bb=stackdeptha=stackdepthif(pi==)stackdepth=a*belseif(pi==)stackdepth=abelseif(pi==)stackdepth=abelsestackdepth=ab}}returnstack}intaintnintpintmmain(){printf("*()n")transform("*()",a,n)poland(a,n,p,m)printpoland(p,m)printf("Theresultoftheexpressionislfn",evaluate(p,m))return}判断表达式中括弧是否正确配对#include<iostreamh>#include"sqstackh"voidcmp(sqstacks,chary,intstate,intstate){charxpop(s,x)cout<<xif(stop==sbase)state=if(x==y)state=elseif(x!=y)state=}voidmain(){sqstacksInitStack(s)intstate=,stateintj=,flag=charn,dfor(inti=i<statei){cin>>nif(int(n)==){flag=break}elsedi=ncharc=diswitch(c){case'<':push(s,c)breakcase'{':push(s,c)breakcase'':push(s,c)breakcase'(':push(s,c)breakcase'>':cmp(s,'<',state,state)breakcase'}':cmp(s,'{',state,state)breakcase')':cmp(s,'(',state,state)breakcase'':cmp(s,'',state,state)break}}if(state==)cout<<"goodmatchn"elsecout<<"errormatchn"}判断字符串是否回文#include<iostreamh>#include<stringh>#include"qnodeh"#include"sqstackh"intn=voidscan(linkqueueq,sqstacks){charkcin>>kwhile(k!='#'){enqueue(q,k)push(s,k)cin>>kn=n}}voidko(linkqueueq,sqstacks){charc,dinta,i=for(nn>n){a=daqueue(q,c)pop(s,d)if(c!=d)i=}if(i==)cout<<"no"<<endlelsecout<<"yes"<<endl}voidmain(){linkqueueqsqstacksinitqueue(q)initstack(s)scan(q,s)ko(q,s)}字符串的基本操作#include<stdioh>#include<stringh>voidmain(){charscharleft,rightintL,i,jintN,m=charccprintf("Pleaseenterthestringn")fgets(s,,stdin)L=strlen(s)printf("stringL=dn",L)printf("PleaseenterNn")scanf("d",N)if(N<L){strncpy(left,s,N)leftN=''strncpy(right,sLN,N)rightN=''printf("left:sn",left)printf("right:sn",right)}else{printf("left,right:sn",s)}printf("PleaseenterbeginlocationmandNn")scanf("dd",m,N)if(m>L)m=strncpy(right,sm,N)rightN=''printf("mid:sn",right)printf("enteraletter:n")scanf("s",cc)printf("Locations:")for(i=i<Li)if(si==cc)printf("d",i)printf("n")for(i=Li>=i)printf("c",si)printf("n")for(i=i<Li)if(si>='a'si<='z')si=si'a''A'printf("sn",s)}栈列操作的验证#include<iostreamh>#include<stdlibh>typedefintprioritytypedefintStatus#defineTRUE#defineFALSEtypedefcharelemtype*栈元素类型,用链表连接*typedefstructnode{elemtypechdatastructnode*next}*pnode*定义栈*typedefstructstack{pnodetopintlength}chstack*初始化栈*voidInitStack(stacks){stop=slength=}*栈不为空,出*StatusPush(stacks,elemtypee){pnodetemtem=newnodeif(!tem)returnFALSEtem>chdata=etem>next=stopstop=temslengthreturnTRUE}*栈不为空,入*StatusPop(stacks,elemtypee){pnodedele=stop>chdatadel=stopstop=stop>nextdeletedelslengthreturnTRUE}*做第一个'#'*voidFstack(stacks){elemtypeee='#'if(!Push(s,e))exit()}*取得栈顶元素,e带回*boolGettop(stacks,elemtypee){if(slength>=){e=stop>chdatareturntrue}returnfalse}*定义优先级,返回*prioritychpri(chare){switch(e){case'(':returncase')':returncase'':returncase'':returncase'*':returncase'#':returncase'':return}}boolIsOperator(chare){switch(e){case'(':breakcase')':breakcase'':breakcase'':breakcase'*':breakcase'':breakdefault:returnfalse}returntrue}*返回a>=b为真*boolPriCom(chara,charb){intaiintbiai=chpri(a)bi=chpri(b)return(ai>=bitrue:false)}*不包括空格,主要转换部分*voidconver(charsuff,charchconver){stackschar*pchar*psuffcharstacktopcharstackoutInitStack(s)Fstack(s)psuff=suffp=chconverwhile(p!=''){if(!IsOperator(*p))*psuff=*pelse{switch(*p){case'(':Push(s,*p)breakcase')':do{Gettop(s,stackout)*psuff=stackout}while(stacktop!='(')Gettop(s,stackout)*psuff=stackoutbreakdefault:Gettop(s,stacktop)if(PriCom(*p,stacktop))Push(s,*p)while(!PriCom(*p,stacktop)){Pop(s,stackout)*psuff=stackout}Push(s,*p)}endswitch}endelsep}endwhilewhile(stackout!='#'){Gettop(s,stackout)*psuff=stackout}}综合应用题迷宫求解任务:可以输入一个任意大小的迷宫数据用非递归的方法求出一条走出迷宫的路径并将路径输出#include<iostream>#include<fstream>#include<conioh>usingnamespacestdstructstep定义一个栈{intx,y,nxy表示步子坐标n表示步数}voidchange(char**maze,inthang,intlie){for(inti=i<hangi){for(intj=j<liej)switch(mazeij){case'':mazeij='#'breakcase'':case'':case'':mazeij=''break}}}voidsteptostep(char**maze,step*Step,inthang,intlie,intn){单步输出for(intk=k<=nk){for(inti=i<hangi){for(intj=j<liej){if(Stepkx==iStepky==j)cout<<""<<""elsecout<<mazeij<<""}cout<<endl}cout<<"这是第"<<k<<"步"<<endl<<endlgetch()}}voidout(char**maze,inthang,intlie,inti,intj)输出所走的路程{if(i==j==)若回到原点则表明无出路{cout<<endlcout<<"************************************************************"<<endlcout<<"|此迷宫没有出路所走路线如下图|"<<endlcout<<"************************************************************"<<endl}else否则有出路{cout<<endlcout<<"************************************************************"<<endlcout<<"|找到迷宫出路如图所示|"<<endlcout<<"************************************************************"<<endl}for(i=i<hangi)输出步子{for(j=j<liej)cout<<mazeij<<""cout<<endl}}voidcure(char**maze,inthang,intlie){inti=,j=,n=charQstep*Step定义一个存储路程的栈Step=newstephang*lie事先给其分配一定的空间hang*lie表示空间足够if(maze==''){cout<<"我进不去!!!"<<endl<<endlgetch()exit()}elsewhile(mazehanglie!='')由右、下、左、上的顺序判断是否走通{''表示走不通''表示已经走过但不通又回来的步子''表示已经走过并通了的步子if(mazeij!=''mazeij!=''mazeij!=''){if(i==j==){cout<<"入口"<<endl}elsecout<<"右"<<endlmazeij=''j=jnStepnx=iStepny=jcout<<i<<","<<j}elseif(mazeij!=''mazeij!=''mazeij!=''){cout<<"下"<<endlmazeij=''i=inStepnx=iStepny=jcout<<i<<","<<j}elseif(mazeij!=''mazeij!=''mazeij!=''){cout<<"左"<<endlmazeij=''j=jnStepnx=iStepny=jcout<<i<<","<<j}elseif(mazeij!=''mazeij!=''mazeij!=''){cout<<"上"<<endlmazeij=''i=inStepnx=iStepny=jcout<<i<<","<<j}else若走不通则返回上一步{if(i==j==)当回到入口时说明无通路结束循环breakelse{mazeij=''将走不通的点置为ni=Stepnx返回上一个点j=Stepnycout<<"返回"<<endl<<i<<","<<j输出返回信息}}if(i==hangj==lie)cout<<"(出口)"<<""<<"(共"<<n<<"步"<<")"}out(maze,hang,lie,i,j)cout<<endl<<endl<<endlcout<<"是否单步输出(yn):"cin>>Qcout<<endl<<endlif(Q=='y'){change(maze,hang,lie)steptostep(maze,Step,hang,lie,n)}}intmain(){char**maze定义一个迷宫空间可动态inthang,lie,i,jcharQcout<<"希望手动输入还是文件读入(s:手动输入,w:文件读入):"cin>>Qcout<<endl<<endlif(Q=='s'){cout<<"请输入矩阵的行列"<<endlcout<<"行数:"cin>>hangcout<<"列数:"cin>>liecout<<endlmaze=newchar*hang分配连续空间给迷宫for(i=i<hangi)mazei=newcharliecout<<"请输入迷宫表示通路表示墙"<<endlfor(i=i<=hangi)for(j=j<=liej)cin>>mazeij}elseif(Q=='w'){ifstreaminfile("F:migongtxt",ios::in)可用文件外部输入infile>>hanginfile>>liemaze=newchar*hang分配连续空间给迷宫for(i=i<hangi)mazei=newcharliefor(i=i<=hangi)for(j=j<=liej)infile>>mazeijcout<<"文件读取成功~"<<endl}for(i=i<hangi)mazei=''for(i=i<liei)mazei=''for(i=i<liei)mazehangi=''for(i=i<hangi)mazeilie=''cout<<endl<<endlcout<<"********************您输入的迷宫为******************************"<<endlcout<<"行数:"<<hang<<""<<"列数:"<<liecout<<""<<"入口:"<<","<<""<<"出口:"<<hang<<","<<lie<<endlfor(i=i<hangi){for(j=j<liej)cout<<mazeij<<""cout<<endl}cout<<endl<<endl<<"所走的步骤如下:"<<endlcure(maze,hang,lie)cout<<endl<<endl<<endlgetch()return}迷宫求解程序演示图运行程序可以选择输入迷宫的方式:有手动输入和文件输入两种方法可供选择。图选择手动输入输入所期望的迷宫的行数和列数然后就可以用和绘制迷宫。图输入一个迷宫之后按回车程序显示出用户所绘迷宫。并开始尝试走通该迷宫。图输入一个无法走通的迷宫。显示结果所走的步骤和所经历的路线。图单步显示每走一步的状况小点表示当前的位置。图如果迷宫可以走通则显示如图。每一步都清楚显示。图走通整个迷宫的路线如图中的小点所示。总结经过本次的数据结构课程设计我可以说是获益匪浅。学习程序设计是一个非常需要实践的过程这一次的课程设计正是给了我机会。通过设计的题目我不但巩固了平时所学更学到了平时没有注意到的一些技巧。这一次课程设计中我的基础题和综合应用题选的都是栈与队列的相关应用这说明我对其他知识的把握还没有到位。我明白在程序设计的道路上我才刚刚起步我所知道的不过是九牛一毛。学海无涯我要更加的努力。参考文献《C程序设计》(第二版)潭浩强著清华大学出版社出版《C程序设计》潭浩强著清华大学出版社出版《数据结构》(C语言版)严蔚敏、吴伟民著清华大学出版社出版

用户评价(0)

关闭

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

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

提示

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

文档小程序码

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

1

打开微信

2

扫描小程序码

3

发布寻找信息

4

等待寻找结果

我知道了
评分:

/32

栈和队列其应用、迷宫求解

VIP

在线
客服

免费
邮箱

爱问共享资料服务号

扫描关注领取更多福利