数据结构课程设计报告―迷宫求解问题

课题设计1：迷宫求解一.需求分析：本程序是利用非递归的方法求出一条走出迷宫的路径，并将路径输出。首先由用户输入一组二维数组来组成迷宫，确认后程序自动运行，当迷宫有完整路径可以通过时，以0和1所组成的迷宫形式输出，标记所走过的路径结束程序；当迷宫无路径时，提示输入错误结束程序。二、概要设计：1.抽象数据类型定义：ADTFind{数据对象：D={ai?ai∈ElemSet,i=1,2,…,n,n≥0}数据关系：R1={ai-1,ai?ai-1,ai∈D}基本操作：find(&S)初始条件：已初始化栈S，且栈为空操作结果：从栈Ｓ中找出相对应的数据关系，并输出结果}ADTFind2.主程序的流程以及各程序模块之间的调用关系：(1).定义变量i、j、w、z为整形变量(2).输入迷宫二维数组maze(0:m,0:n)(3).调用子程序find()(4).结束程序三、相应的源程序如下：#includestdio.h#includestdlib.htypedefenum{ERROR,OK}Status;typedefstruct{introw,line;}PosType;typedefstruct{intdi,ord;PosTypeseat;}SElemType;typedefstruct{SElemType*base;SElemType*top;intstacksize;}SqStack;StatusInitStack(SqStack&S);StatusPush(SqStack&S,SElemType&a);StatusPop(SqStack&S,SElemType&a);StatusStackEmpty(SqStackS);StatusMazePath(intmaze[12][12],SqStack&S,PosTypestart,PosTypeend);voidInitmaze(intmaze[12][12],intsize);voidprintmaze(intmaze[12][12],intsize);StatusPass(intmaze[12][12],PosTypeCurPos);voidMarkfoot(intmaze[12][12],PosTypeCurPos);PosTypeNextPos(PosTypeCurPos,intDir);voidprintpath(intmaze[12][12],SqStackS,intsize);voidmain(void){SqStackS;intsize,maze[12][12];for(intn=0;n10;n++){printf(创建一个正方形迷宫，请输入迷宫尺寸(注意不要大于50):\n);scanf(%d,&size);if(size1||size10){printf(输入错误!);return;}Initmaze(maze,size);printmaze(maze,size);PosTypestart,end;printf(输入入口行坐标和列坐标:);scanf(%d,&start.row);scanf(%d,&start.line);printf(输入出口行坐标和列坐标:);scanf(%d,&end.row);scanf(%d,&end.line);if(MazePath(maze,S,start,end))printpath(maze,S,size);elseprintf(找不到通路!\n\n);}}StatusMazePath(intmaze[12][12],SqStack&S,PosTypestart,PosTypeend){PosTypecurpos;intcurstep;SElemTypee;InitStack(S);curpos=start;curstep=1;do{if(Pass(maze,curpos)){Markfoot(maze,curpos);e.di=1;e.ord=curstep;e.seat=curpos;Push(S,e);if(curpos.row==end.row&&curpos.line==end.line)returnOK;curpos=NextPos(curpos,1);curstep++;}else{if(!StackEmpty(S)){Pop(S,e);while(e.di==4&&!StackEmpty(S)){Markfoot(maze,e.seat);Pop(S,e);}if(e.di4){e.di++;Push(S,e);curpos=NextPos(e.seat,e.di);}}}}while(!StackEmpty(S));returnERROR;}voidInitmaze(intmaze[12][12],intsize){charselect;printf(选择创建方式A:自动生成B:手动创建\n);label:scanf(%c,&select);if(select=='a'||select=='A'){for(inti=0;isize+2;i++)maze[0][i]=1;for(i=1;isize+1;i++){maze[i][0]=1;for(intj=1;jsize+1;j++)maze[i][j]=rand()%2;maze[i][size+1]=1;}for(i=0;isize+2;i++)maze[size+1][i]=1;}elseif(select=='b'||select=='B'){printf(按行输入%d*%d数据,0代表可通,1代表不可通(每行以Enter结束):\n,size,size);for(inti=0;isize+2;i++)maze[0][i]=1;for(i=1;isize+1;i++){maze[i][0]=1;for(intj=1;jsize+1;j++)scanf(%d,&maze[i][j]);maze[i][size+1]=1;}for(i=0;isize+2;i++)maze[size+1][i]=1;}elseif(select=='\n')gotolabel;elseprintf(输入错误!);}voidprintmaze(intmaze[12][12],intsize){printf(\n\n);printf(显示所建的迷宫(#表示外面的墙):\n);for(inti=0;isize+2;i++)printf(%c,'#');printf(\n);for(i=1;isize+1;i++){printf(%c,'#');for(intj=1;jsize+1;j++){printf(%d,maze[i][j]);}printf(%c,'#');printf(\n);}for(i=0;isize+2;i++)printf(%c,'#');printf(\n);}voidprintpath(intmaze[12][12],SqStackS,intsize){printf(\n\n通路路径为:\n);SElemType*p=S.base;while(p!=S.top){maze[p-seat.row][p-seat.line]=2;p++;}for(inti=0;isize+2;i++)printf(%c,'#');printf(\n);for(i=1;isize+1;i++){printf(%c,'#');for(intj=1;jsize+1;j++){if(maze[i][j]==2)printf(%c,'0');elseprintf();}printf(%c,'#');printf(\n);}for(i=0;isize+2;i++)printf(%c,'#');printf(\n\n);}StatusPass(intmaze[12][12],PosTypeCurPos){if(maze[CurPos.row][CurPos.line]==0)returnOK;elsereturnERROR;}voidMarkfoot(intmaze[12][12],PosTypeCurPos){maze[CurPos.row][CurPos.line]=1;}PosTypeNextPos(PosTypeCurPos,intDir){PosTypeReturnPos;switch(Dir){case1:ReturnPos.row=CurPos.row;ReturnPos.line=CurPos.line+1;break;case2:ReturnPos.row=CurPos.row+1;ReturnPos.line=CurPos.line;break;case3:ReturnPos.row=CurPos.row;ReturnPos.line=CurPos.line-1;break;case4:ReturnPos.row=CurPos.row-1;ReturnPos.line=CurPos.line;break;}returnReturnPos;}StatusInitStack(SqStack&S){S.base=(SElemType*)malloc(100*sizeof(SElemType));if(!S.base)returnERROR;S.top=S.base;S.stacksize=100;returnOK;}StatusPush(SqStack&S,SElemType&a){*S.top++=a;returnOK;}StatusPop(SqStack&S,SElemType&a){if(S.top==S.base)returnERROR;a=*--S.top;returnOK;}StatusStackEmpty(SqStackS){if(S.top==S.base)returnOK;returnERROR;}以下为测试数据：输入一个矩阵，例如：1001100111100010101111000输入入口行坐标和列坐标：12输入出口行坐标和列坐标：55通路路径为：课题设计3：joseph环一.需求分析：利用单向循环链表存储结构模拟此过程，按照出列的顺序输出各个人的编号。首先创建一个空链表，初始化链表，构造出一个只有头结点的空链表，建立好一个约瑟夫环。1.输入的形式和输入值的范围本程序中，输入报数上限值m和人数上限l，密码，均限定为正整数，输入的形式为一个以“回车符”为结束标志的正整数。2.输出的形式从屏幕显示出列顺序。3.程序功能提供用户从键盘输入，Joseph约瑟夫环的必要数据，并显示出列顺序。二、概要设计以单向循环链表实现该结构。1.抽象数据类型的定义为：ADTLNode{数据对象：D={ai|ai∈CharSet，i=1，2，…，n，n≥0}数据关系：R1={<ai-1，ai>|ai∈D，I=2，…，n}三．源程序：#includestdio.h#includestdlib.htypedefstructNode{intkey;//每个人持有的密码intnum;//这个人的编号structNode*next;//指向下一个节点}Node,*Link;voidInitList(Link&L)//创建一个空的链表{L=(Node*)malloc(sizeof(Node));if(!L)exit(1);L-key=0;L-num=0;L-next=L;}voidCreater(intn,Link&L)//初始化链表{Linkp,q;q=L;for(inti=1;i=n;i++){p=(Node*)malloc(sizeof(Node));if(!p)exit(1);printf(thekey_%dis:,i);scanf(%d,&p-key);p-num=i;L-next=p;L=p;}L-next=q-next;free(q);}voidmain(){LinkL,p,q;