《数据结构》课程设计总结

《数据结构》课程设计报告题目：老鼠走迷宫班级：姓名：学号：指导教师：__日期：2010年7月一、课程设计目标1、问题描述本程序是利用非递归的方法求出一条走出迷宫的路径，并将路径输出。首先由用户输入一组二维数组来组成迷宫，确认后程序自动运行，当迷宫有完整路径可以通过时，以0和1所组成的迷宫形式输出，标记所走过的路径结束程序；当迷宫无路径时，提示输入错误结束程序。2、问题分析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).结束程序二、概要设计1、方案确定多个函数进行组合，有显示图形函数、方向函数、自动创建迷宫函数、手动创建迷宫函数，迷宫的大小创建！2、程序设计模块设计连接图界面显示模块界面显示模块路径显示模块判断路径模块自动创建模块手动创建模块尺寸设计模块3、模块功能描述1、尺寸设计模块：确定界面大小；2、自动创建模块：自动创建游戏界面；3、手动创建模块：手动创建游戏界面；4、打印游戏界面（基于DOS）;5、判断路径模块：判断是否为通路；6、路径显示模块：打印通路；三、详细设计1、方法设计本程序主要用到了堆栈的出栈与入栈算法，在走迷宫的时候用到查找的相关知识，来判断路径问题，通过人机对话街界面，实现手动与随机两种方式生成迷宫界面，让程序更加人性化，增强了程序的可操行，通过功能函数的调用，将各个模块联系起来，实现整体的功能结合，以实现最终的整体效果。2、程序流程图图2输入矩阵尺寸图2输入矩阵尺寸判断尺寸创建方式主程序（判断路径）打印路径>10或<0<=10和>=1随即创建手动创建路径不通提示错误四、程序清单#include<stdio.h>#include<stdlib.h>typedefenum{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);StatusvoidMarkfoot(intmaze[12][12],PosTypeCurPos);PosTypeNextPos(PosTypeCurPos,intDir);voidprintpath(intmaze[12][12],SqStackS,intsize);//迷宫的建立voidmain(){SqStackS;intsize,maze[12][12];for(intn=0;n<10;n++){printf("创建一个正方形迷宫，请输入迷宫尺寸(注意不要大于10):\n");scanf("%d",&size);if(size<1||size>10){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.di<4){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;i<size+2;i++)maze[0][i]=1;for(i=1;i<size+1;i++){maze[i][0]=1;for(intj=1;j<size+1;j++)maze[i][j]=rand()%2;maze[i][size+1]=1;}for(i=0;i<size+2;i++)maze[size+1][i]=1;}//自动创建迷宫的算法elseif(select=='b'||select=='B'){printf("按行输入%d*%d数据,0代表可通,1代表不可通(每行以Enter结束):\n",size,size);for(inti=0;i<size+2;i++)maze[0][i]=1;for(i=1;i<size+1;i++){maze[i][0]=1;for(intj=1;j<size+1;j++)scanf("%d",&maze[i][j]);maze[i][size+1]=1;}for(i=0;i<size+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;i<size+2;i++)printf("%c",'#');printf("\n");for(i=1;i<size+1;i++){printf("%c",'#');for(intj=1;j<size+1;j++){printf("%d",maze[i][j]);}printf("%c",'#');printf("\n");}for(i=0;i<size+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;i<size+2;i++)printf("%c",'#');printf("\n");for(i=1;i<size+1;i++){printf("%c",'#');for(intj=1;j<size+1;j++){if(maze[i][j]==2)printf("%c",'0');elseprintf("");}printf("%c",'#');printf("\n");}for(i=0;i<size+2;i++)printf("%c",'#');printf("\n\n");}//创建边线，便于操作</我所负责>Status{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;}//显示