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

课程设计(论文)任务书 信息 学院计算机专业20071. 班 一、课程设计(论文)题目 栈和队列其应用、迷宫求解 二、课程设计(论文)工作自 2009 年6月 22 日起至 2009 年 7月 5 日止。三、课程设计(论文) 地点: 5-401、402 四、课程设计(论文)内容要求：1本课程设计的目的1、使学生进一步理解和掌握课堂上所学各种基本抽象数据类型的逻辑结构、存储结构和操作实现算法，以及它们在程序中的使用方法。2、使学生掌握软件设计的基本内容和设计方法，并培养学生进行规范化软件设计的能力。3、使学生掌握使用各种计算机资料和有关参考资料，提高学生进行程序设计的基本能力。 2课程设计的任务及要求1）基本要求：1.分析题目，查阅相关资料；2.算法设计、数据结构设计； 3.编写代码并调试；4.完成课程设计报告。 2）创新要求： 在基本要求达到后，可进行创新设计。3）课程设计论文编写要求（1）要按照书稿的规格打印誊写毕业论文（2）论文包括目录、绪论、正文、小结、参考文献、谢辞、附录等（3）毕业论文装订按学校的统一要求完成4）答辩与评分标准： （1）完成问题的解决方法分析：20分； （2）算法思想（流程）：20分； （3）数据结构：20分；（4）测试数据：20分（5）回答问题：20分。5）参考文献： C程序设计（第二版） 潭浩强 著 清华大学出版社出版 C+程序设计 潭浩强 著 清华大学出版社出版 数据结构（C语言版） 严蔚敏、吴伟民 著 清华大学出版社出版 6）课程设计进度安排内容 天数地点构思及收集资料 图书馆编程与调试 实验室 撰写论文 学生签名： 2009年 6 月 22 日课程设计(论文)评审意见（1）完成问题分析（20分）：优（）、良（）、中（）、一般（）、差（）； （2）算法思想（20分）：优（）、良（）、中（）、一般（）、差（）； （3）数据结构（20分）：优（）、良（）、中（）、一般（）、差（）；（4）测试数据 （20分）：优（）、良（）、中（）、一般（）、差（）；（5）回答问题（20分）：优（）、良（）、中（）、一般（）、差（）；（6）格式规范性及考勤是否降等级：是（）、否（）评阅人： 赵海霞 职称： 讲师 2009年7 月 6 日目录一、课程设计目的 4二、课程设计内容 5三、基本题 6四、综合应用题 18五、测试数据 25六、课程设计总结 29七、参考文献 30本课程设计的目的1、 使学生进一步理解和掌握课堂上所学各种基本抽象数据类型的逻辑结构、存储结构和操作实现算法，以及它们在程序中的使用方法。2、使学生掌握软件设计的基本内容和设计方法，并培养学生进行规范化软件设计的能力。3、使学生掌握使用各种计算机资料和有关参考资料，提高学生进行程序设计的基本能力。本课程设计的内容栈和队列其应用 目的在于使读者深入了解栈和队列的特性，以便在实际问题背景下灵活运用他们；同时还将巩固对这两种结构的构造方法的掌握，接触较复杂问题的递归算法设计。（1）：算术表达式转波兰表达式和逆波兰表达式 （2）：栈列操作的验证（建栈、入栈、出栈、销毁栈） （3）：判断表达式中括弧是否正确配对 （4）：队列元素倒置 （5）：判断字符串是否回文 （6）：字符串的基本操作（5个基本函数实现）迷宫求解任务：可以输入一个任意大小的迷宫数据，用非递归的方法求出一条走出迷宫的路径，并将路径输出；基本题栈和队列及其应用目的在于使读者深入了解栈和队列的特性，以便在实际问题背景下灵活运用他们；同时还将巩固对这两种结构的构造方法的掌握，接触较复杂问题的递归算法设计ADT Stack 的表示和实现#include#define STACK_INIT_SIZE 30#define STACKINCREMENT 5typedef struct char * base;char* top;int stacksize;sqstack;void InitStack(sqstack &s) s.base=(char *)malloc(STACK_INIT_SIZE*sizeof(char);/if(!s.base) exit(OVERFLOW);s.top=s.base;s.stacksize=STACK_INIT_SIZE;void push(sqstack &s,char &c) if(s.top-s.base=s.stacksize) s.base=(char *) realloc(s.base,(s.stacksize+STACKINCREMENT)*sizeof(char);/if(!s.base) exit(OVERFLOW);s.top=s.base+s.stacksize;s.stacksize+=STACKINCREMENT;*s.top+=c;void pop(sqstack &s,char &c) if(!(s.top=s.base) c=*-s.top;int stackEmpty(sqstack s) if(s.base=s.top) return(1); return(0); 算术表达式转波兰表达式和逆波兰表达式#include #include void transform(char *str,int a2,int *n) int i; *n=1; a00=1; a01=(; for (i=0;stri;) if (isdigit(stri) a*n0=0; a*n1=0; while (isdigit(stri) a*n1=a*n1*10+stri-0; i+; else if (stri=() a*n0=1; else if (stri=) a*n0=2; else if (stri=*) a*n0=3; else if (stri=/) a*n0=4; else if (stri=+ | stri=-) if (i=0 | (!isdigit(stri-1) & stri-1!=) a*n0=0; a*n1=0; (*n)+; if (stri=+) a*n0=5; else a*n0=6; a*n1=stri; i+; (*n)+; a*n0=2; a*n1=); (*n)+; void poland(int a2,int n,int p2,int *m) int i; int stack1000;/转化所用的栈 int depth;/栈的深度 depth=0; *m=0; for (i=0;in;i+) if (ai0=0) stackdepth+=i; else if (ai0=1) stackdepth+=i; else if (ai0=2) while (astackdepth-10!=1) depth-; p*m0=astackdepth0; p*m1=astackdepth1; (*m)+; depth-; else if (ai0=3 | ai0=4) while (astackdepth-10=0 | astackdepth-10=3 | astackdepth-10=4) depth-; p*m0=astackdepth0; p*m1=astackdepth1; (*m)+; stackdepth+=i; else if (ai0=5 | ai0=6) while (astackdepth-10!=1) depth-; p*m0=astackdepth0; p*m1=astackdepth1; (*m)+; stackdepth+=i; void print_poland(int p2,int m) int i; for (i=0;im;i+) if (pi0=0) printf(%d,pi1); else printf(%c,pi1); putchar(n); double evaluate(int p2,int m) double stack1000;/求值所用的栈 int depth;/栈的深度 int i; depth=0; for (i=0;im;i+) if (pi0=0) stackdepth+=pi1; else double a,b; b=stack-depth; a=stack-depth; if (pi0=3) stackdepth+=a*b; else if (pi0=4) stackdepth+=a/b; else if (pi0=5) stackdepth+=a+b; else stackdepth+=a-b; return stack0; int a10002; int n; int p10002; int m; main() printf(5*(8-2)+9n);transform(5*(8-2)+9,a,&n); poland(a,n,p,&m); print_poland(p,m); printf(The result of the expression is %lfn,evaluate(p,m); return; 判断表达式中括弧是否正确配对#include#includesqstack.hvoid cmp(sqstack &s,char y,int &state1,int &state2)char x;pop(s,x); /coutx;if(s.top=s.base) state1=0;if(x=y) state2=1;else if(x!=y) state2=0;void main() sqstack s;InitStack(s);int state1=1,state2;int j=0,flag=1;char n,d15;for(int i=0;in; if(int(n)=19) flag=0;break; else di=n; char c=di;switch(c)case: cmp(s,state1,state2); break; case: cmp(s,state1,state2); break;case): cmp(s,(,state1,state2); break;case: cmp(s,state1,state2); break;if(state2=1) coutgood matchn;else couterror matchn;判断字符串是否回文#include#include#includeqnode.h#includesqstack.hint n=0;void scan(linkqueue &q,sqstack &s)char k;cink;while(k!=#)enqueue(q,k);push(s,k);cink;n=n+1;void ko(linkqueue &q,sqstack &s)char c,d;int a,i=1;for(n;n0;n-)a=daqueue(q,c);pop(s,d);if(c!=d) i=0;if(i=0) coutnoendl;else coutyesendl;void main()linkqueue q;sqstack s;initqueue(q);initstack(s);scan(q,s);ko(q,s);字符串的基本操作#include#include void main ()char s200;char left200,right200;int L,i,j;int N,m=0;char cc2;printf(Please enter the stringn);fgets(s,199,stdin);L = strlen(s);printf(string L=%dn,L);printf(Please enter N n);scanf(%d,&N);if (N L) m=0;strncpy(right, &sm,N); rightN=0;printf(mid: %sn,right);printf(enter a letter:n);scanf(%s,&cc0); printf(Locations: );for (i=0;i=0;i-) printf(%c,si);printf(n);for (i=0;i= a & si = z) si=si-a+A;printf(%sn,s);栈列操作的验证#include #include typedef int priority;typedef int Status;#define TRUE 1;#define FALSE 0;typedef char elemtype;/*栈元素类型,用链表连接*/typedef struct node elemtype chdata; struct node *next;*pnode;/*定义栈*/typedef struct stack pnode top; int length;chstack;/*初始化栈*/void InitStack(stack &s) s.top=NULL; s.length=0;/*栈不为空,出*/Status Push(stack &s,elemtype e) pnode tem; tem=new node; if(!tem) return FALSE; tem-chdata=e; tem-next=s.top; s.top=tem; s.length+; return TRUE;/*栈不为空,入*/Status Pop(stack &s,elemtype &e) pnode del; e=s.top-chdata; del=s.top; s.top=s.top-next; delete del; s.length-; return TRUE; /*做第一个#*/void Fstack(stack &s) elemtype e; e=#; if(!Push(s,e) exit(0);/*取得栈顶元素,e带回*/bool Gettop(stack &s,elemtype &e) if(s.length=1) e=s.top-chdata; return true; return false;/*定义优先级,返回*/priority chpri(char e) switch (e) case (: return 0; case ): return 0; case +: return 1; case -: return 1; case *: return 2; case #: return -1; case /: return 2; bool IsOperator(char e) switch (e) case (: break; case ): break; case +: break; case -: break; case *: break; case /: break; default: return false; return true;/*返回a=b为真*/bool PriCom(char a,char b) int ai; int bi; ai=chpri(a); bi=chpri(b); return (ai=bi? true:false);/*不包括空格,主要转换部分*/void conver(char suff,char chconver) stack s; char *p; char *psuff; char stacktop; char stackout; InitStack(s); Fstack(s); psuff=suff; p=chconver; while(p!=0) if(!IsOperator(*p) *psuff+=*p; else switch (*p) case(: Push(s,*p); break; case): do Gettop(s,stackout); *psuff+=stackout; while(stacktop!=(); Gettop(s,stackout); *psuff+=stackout; break; default: Gettop(s,stacktop); if( PriCom(*p,stacktop ) ) Push(s,*p); while( !PriCom(*p,stacktop) ) Pop(s,stackout); *psuff+=stackout; Push(s,*p); /endswitch /endelse p+; /endwhile while(stackout!=#) Gettop(s,stackout); *psuff+=stackout; 综合应用题迷宫求解任务：可以输入一个任意大小的迷宫数据，用非递归的方法求出一条走出迷宫的路径，并将路径输出；#include #include #include using namespace std;struct step /定义一个栈 int x,y,n; /x，y表示步子坐标，n表示步数;void change(char *maze,int hang,int lie) for(int i=0;ihang+2;i+) for(int j=0;jlie+2;j+) switch(mazeij) case 1: mazeij=#;break; case +: case 0: case .: mazeij= ;break; void step_to_step(char *maze,step *Step,int hang,int lie,int n) /单步输出 for(int k=0;k=n;k+) for(int i=0;ihang+2;i+) for(int j=0;jlie+2;j+) if(Stepk.x=i&Stepk.y=j) cout. ; else coutmazeij ; coutendl; cout这是第k+1步endlendl; getch(); void out(char *maze,int hang,int lie,int i,int j) /输出所走的路程 if(i=1&j=1) /若回到原点则表明无出路 coutendl; cout*endl; cout|-此迷宫没有出路，所走路线如下图-|endl; cout*endl; else /否则有出路 coutendl; cout*endl; cout|-找到迷宫出路，如图所示-|endl; cout*endl; for(i=0;ihang+2;i+) /输出步子 for(j=0;jlie+2;j+) coutmazeij ; coutendl; void cure(char *maze,int hang,int lie) int i=1,j=0,n=-1; char Q; step *Step; /定义一个存储路程的栈 Step=new step hang*lie; /事先给其分配一定的空间，hang*lie表示空间足够 if(maze11=1) cout555.我进不去!endlendl; getch(); exit(0); else while(mazehanglie!=.) /由右、下、左、上的顺序判断是否走通 /1表示走不通，+表示已经走过但不通又回来的步子，.表示已经走过并通了的步子 if(mazeij+1!=1&mazeij+1!=.&mazeij+1!=+) if(i=1&j=0) cout入口endl; else cout右endl; mazeij+1=.; j=j+1; n+; Stepn.x=i; Stepn.y=j; couti,j; else if(mazei+1j!=1&mazei+1j!=.&mazei+1j!=+) cout下endl; mazei+1j=.; i=i+1; n+; Stepn.x=i; Stepn.y=j; couti,j; else if(mazeij-1!=1&mazeij-1!=.&mazeij-1!=+) cout左endl; mazeij-1=.; j=j-1; n+; Stepn.x=i; Stepn.y=j; couti,j; else if(mazei-1j!=1&mazei-1j!=.&mazei-1j!=+) cout上endl; mazei-1j=.; i=i-1; n+; Stepn.x=i; Stepn.y=j; couti,j; else /若走不通则返回上一步 if(i=1&j=1) /当回到入口时，说明无通路，结束循环 break; else mazeij=+; /将走不通的点置为+ n-; i=Stepn.x; /返回上一个点 j=Stepn.y; cout返回endli,j; /输出返回信息 if(i=hang&j=lie) cout(出口) (共n+1步); out(maze,hang,lie,i,j); coutendlendlendl; coutQ; coutendlendl; if(Q=y) change(maze,hang,lie); step_to_step(maze,Step,hang,lie,n); int main() char *maze; /定义一个迷宫，空间可动态 int hang,lie,i,j; char Q; coutQ; coutendlendl; if(Q=s) cout请输入矩阵的行列endl; couthang; coutlie; coutendl; maze=new char *hang+2; /分配连续空间给迷宫 for(i=0;ihang+2;i+) mazei=new char lie+2; cout请输入迷宫，0表示通路，1表示墙endl; for(i=1;i=hang;i+) for(j=1;jmazeij; else if(Q=w) ifstream infile(F:migong.txt,ios:in); /可用文件外部输入