迷宫求解实验报告 (2).doc

编程实训实验报告书专 业：计算机科学与技术 班 级： 1班 学 号： 31960144 姓 名：周* 指导教师：周* 日 期：2016年6月30日 目录一、需求分析31.任务要求32.软件功能分析33.数据准备3二、概要设计31.功能模块图42.模块间调用关系43.主程序模块54.抽象数据类型描述5三、详细设计61.存储结构定义62.各功能模块的详细设计7四、实现和调试71.主要的算法72.主要问题及解决83.测试执行及结果8五、改进9六、附录91需求分析1.1任务要求以一个m*n的长方阵表示迷宫，和分别表示迷宫中的通路和障碍。设计一个程序，对任意设定的迷宫，求出一条从入口到出口的通路，或得出没有通路的结论。1.2软件功能分析设计一个迷宫，通过该程序可以找出通往出口的最短路径。程序功能有三（）创建迷宫；（）求解迷宫；（）输出迷宫的解。1.3数据准备迷宫的测试数据如下：左上角(1,1)为入口，右下角(9,8)为出口。001000100010001000001101011100100001000001000101011110011100010111000000障碍物坐标：1 31 72 32 73 53 63 84 24 34 44 75 46 26 66 87 27 37 47 57 88 18 28 68 89 19 22 概要设计2.1功能模块图栈的顺序存储表示#define StackSize 100 /假定预分配的栈空间最多为100个元素 typedef char DataType;/假定栈元素的数据类型为字符 typedef struct DataType dataStackSize; int top; SeqStack;基本操作的算法描述（1） 置栈空 void InitStack（SeqStack *S） /将顺序栈置空 S-top=-1; （2） 判栈空 int StackEmpty（SeqStack *S） return S-top=-1; （3） 判栈满 int StackFull（SeqStack *SS） return S-top=StackSize-1; （4） 进栈 void Push（S，x） if (StackFull(S) Error(Stack overflow); /上溢，退出运行 S-data+S-top=x;/栈顶指针加1后将x入栈 （5） 退栈 DataType Pop（S） if(StackEmpty(S) Error(Stack underflow); /下溢，退出运行 return S-dataS-top-;/栈顶元素返回后将栈顶指针减1 （6） 取栈顶元素 DataType StackTop（S） if(StackEmpty(S) Error(Stack is empty); return S-dataS-top; 2.2模块间调用关系Stack.h中调用的base.h#include #include #include #define TRUE 1#define FALSE 0#define OK 1#define ERROR 0#define OVERFLOW -2typedef int Status;2.3主程序模块主程序maze.c中调用的stack.h#define INIT_SIZE 100 /存储空间初始分配量#define INCREMENT 10 /存储空间分配增量typedef struct /迷宫中r行c列的位置 int r; int c;PostType;typedef struct int ord; /当前位置在路径上的序号 PostType seat;/当前坐标 int di; /往下一坐标的方向SElemType; /栈元素类型typedef struct SElemType* base;/栈基址,构造前销毁后为空 SElemType* top;/栈顶 int stackSize; /栈容量Stack; /栈类型Status InitStack(Stack &S) /构造空栈s S.base=(SElemType*)malloc(INIT_SIZE *sizeof(SElemType); if(!S.base) exit(OVERFLOW);/存储分配失败 S.top=S.base; S.stackSize=INIT_SIZE; return OK;/InitStackStatus StackEmpty(Stack S) /若s为空返回TRUE,否则返回FALSE if(S.top=S.base) return TRUE; return FALSE;/StackEmptyStatus Push(Stack &S,SElemType e) /插入元素e为新的栈顶元素 if(S.top-S.base =S.stackSize)/栈满，加空间 S.base=(SElemType *)realloc(S.base,(S.stackSize+INCREMENT)*sizeof(SElemType); if(!S.base) exit(OVERFLOW); /存储分配失败 S.top=S.base+S.stackSize; S.stackSize+=INCREMENT; *S.top+=e; return OK;/pushStatus Pop(Stack &S,SElemType &e)/若栈不空删除栈/顶元素用e返回并返回OK，否则返回ERROR if(S.top=S.base) return ERROR; e=*-S.top; return OK;/PopStatus DestroyStack(Stack &S)/销毁栈S, free(S.base); S.top=S.base; return OK;/DestroyStack2.4抽象数据类型描述栈（stack）是限定仅在表尾进行插入或删除操作的线性表。因此，对栈来说，表尾端有特殊含义，称为栈顶（top）,相应的，表头端称为栈底（bottom）。不含元素的空表称为空栈。假设栈S=（a1,a2,，an），则称a1为栈底元素，an为栈顶元素。栈的修改是按后进先出的原则进行的。因此，栈又称为后进先出（List In First Out）的线性表。在迷宫问题中，假设以栈S记录“当前路径”，则栈顶中存放的是“当前路径上最后一个通道块”。由此，“纳入路径”的操作即为“当前位置入栈”；“从当前路径上删除前一通道块”的操作即为“出栈”。3 详细设计3.1存储结构定义typedef int Status;#define INIT_SIZE 100 /存储空间初始分配量#define INCREMENT 10 /存储空间分配增量typedef struct /迷宫中r行c列的位置int r;int c;PostType;typedef structint ord; /当前位置在路径上的序号PostType seat;/当前坐标int di; /往下一坐标的方向SElemType;/栈元素类型typedef structSElemType* base;/栈基址,构造前销毁后为空SElemType* top;/栈顶int stackSize; /栈容量Stack;/栈类型3.2各功能模块的详细设计l 初始化迷宫Status InitMaze(MazeType &maze)l 可通位置Status Pass(MazeType maze,PostType curpos)l 标记非通路Status MarkPrint(MazeType &maze,PostType curpos)l 迷宫maze从入口start到end的通道Status MazePath(MazeType &maze,PostType start,PostType end)l 标记路径信息void PrintMaze(MazeType &maze)4 实现和调试4.1主要的算法设定当前位置的初值为入口位置；do若当前位置可通，则将当前位置入栈；/纳入路径若该位置是出口位置，则结束；/求得路径存放在栈中否则切换当前位置的上方位置为新的当前位置；否则若栈不空且栈顶位置尚有其他方向未被探索，则设定新的当前位置为沿着顺时针方向旋转找到的栈顶位置的下一个相邻块；若栈不空但栈顶位置的四周均不可通，则删去栈顶位置；/后退一步，从路径中删去该通道块若栈不空，则重新测试新的栈顶位置，直至找到一个可通的相邻块或出栈至栈空；while(栈不空)栈空说明没有路径存在4.2主要问题及解决经过对程序的编制，调试和运行，使我更好的掌握了栈基本性质和有关迷宫问题的解决方法，熟悉了各种调用的数据类型，在调试和运行过程中使我更加的了解和熟悉程序运行的环境，提高了我对程序调试分析的能力和对错误的纠正能力。4.3测试执行及结果输入数据：当入口为（1，1）时，出口为（9，8）用一个字符类型的二微数组表示迷宫，数组中的每个元素表示一个小方格，取值“0”（表示可以进出）或“1”（表示不可以进出）随机产生一个9*8的迷宫，其中使用迷宫障碍坐标如下：1 31 72 32 73 53 63 84 24 34 44 75 46 26 66 87 27 37 47 57 88 18 28 68 89 19 2输入过程如下图所示：输入时(-1，-1）结束，接着输入入口参数（1，1）然后输入出口参数（9，8），运行：运行结果如下图所示：图中“1”表示围墙和障碍物。“”表示走过但不是通路.而“0”表示最短路径。5 改进通过不断的调试简短了程序并最终实现了功能。第一次写的程序出现错误，找不到路径，陷入死循环。经过多次改进，程序可以找到最短路径。再次改进后能标出走过的但非最短的路径，有了很大的进步。6 附录源程序代码#include #include #include #define TRUE 1#define FALSE 0#define OK 1#define ERROR 0#define OVERFLOW -2typedef int Status;#define INIT_SIZE 100 /存储空间初始分配量#define INCREMENT 10 /存储空间分配增量typedef struct /迷宫中r行c列的位置int r;int c;PostType;typedef structint ord; /当前位置在路径上的序号PostType seat;/当前坐标int di; /往下一坐标的方向SElemType;/栈元素类型typedef structSElemType* base;/栈基址,构造前销毁后为空SElemType* top;/栈顶int stackSize; /栈容量Stack;/栈类型Status InitStack(Stack &S)/构造空栈sS.base=(SElemType*)malloc(INIT_SIZE *sizeof(SElemType);if(!S.base) exit(OVERFLOW);/存储分配失败S.top=S.base;S.stackSize=INIT_SIZE;return OK;/InitStackStatus StackEmpty(Stack S) /若s为空返回TRUE,否则返回FALSEif(S.top=S.base)return TRUE;return FALSE;/StackEmptyStatus Push(Stack &S,SElemType e)/插入元素e为新的栈顶元素if(S.top-S.base =S.stackSize)/栈满，加空间 S.base=(SElemType *)realloc(S.base,(S.stackSize+INCREMENT)*sizeof(SElemType); if(!S.base) exit(OVERFLOW); /存储分配失败 S.top=S.base+S.stackSize; S.stackSize+=INCREMENT;*S.top+=e;return OK;/pushStatus Pop(Stack &S,SElemType &e)/若栈不空删除栈/顶元素用e返回并返回OK，否则返回ERRORif(S.top=S.base)return ERROR;e=*-S.top;return OK;/PopStatus DestroyStack(Stack &S)/销毁栈S,free(S.base);S.top=S.base;return OK;/DestroyStack#define MAXLEN 10/迷宫包括外墙最大行列数目typedef structint r;int c;char adrMAXLENMAXLEN;/可取 * #MazeType; /迷宫类型Status InitMaze(MazeType &maze)/初始化迷宫若成功返回TRUE,否则返回FALSEint m,n,i,j;printf(输入行和列数: );scanf(%d%d,&maze.r,&maze.c); /迷宫行和列数for(i=0;i=maze.c+1;i+)/迷宫行外墙maze.adr0i=1;maze.adrmaze.r+1i=1;/for for(i=0;i=maze.r+1;i+)/迷宫列外墙 maze.adri0=1; maze.adrimaze.c+1=1; for(i=1;i=maze.r;i+) for(j=1;jmaze.r | nmaze.c)/越界 exit(ERROR); maze.adrmn=1;/迷宫障碍用#标记 printf(输入障碍物坐标，以-1 -1结束: ); scanf(%d%d,&m,&n); /whilereturn OK;/InitMaze Status Pass(MazeType maze,PostType curpos)/当前位置可通则返回TURE,否则返回FALSEif(maze.adrcurpos.rcurpos.c= )/可通return TRUE;elsereturn FALSE;/PassStatus FootPrint(MazeType &maze,PostType curpos)/若走过并且可通返回TRUE,否则返回FALSE/在返回之前销毁栈Smaze.adrcurpos.rcurpos.c=0;/*表示可通return OK;/FootPrintPostType NextPos(PostType &curpos,int i)/指示并返回下一位置的坐标PostType cpos;cpos=curpos;switch(i) /1.2.3.4分别表示东,南,西,北方向 case 1 : cpos.c+=1; break;case 2 : cpos.r+=1; break; case 3 : cpos.c-=1; break; case 4 : cpos.r-=1; break; default: exit(ERROR); return cpos;/NextposStatus MarkPrint(MazeType &maze,PostType curpos)/曾走过但不是通路标记并返回OKmaze.adrcurpos.rcurpos.c=;/表示曾走过但不通return OK;/MarkPrintStatus MazePath(MazeType &maze,PostType start,PostType end) /若迷宫maze存在从入口start到end的通道则求得一条存放在栈中 /并返回TRUE,否则返回FALSEStack S;PostType curpos;int curstep;/当前序号,1.2.3.4分别表示东,南,西,北方向SElemType e;InitStack(S);curpos=start; /设置当前位置为入口位置curstep=1; /探索第一步do if(Pass(maze,curpos)/当前位置可以通过,/即是未曾走到过的通道 FootPrint(maze,curpos);/留下足迹 e.ord=curstep; e.seat=curpos; e.di=1; Push(S,e); /加入路径 if(curpos.r=end.r& curpos.c=end.c)if(!DestroyStack(S)/销毁失败exit(OVERFLOW);else return TRUE; /到达出口 else curpos=NextPos(curpos,1); /下一位置是当前位置的东邻 curstep+; /探索下一步 /else/if else /当前位置不通 if(!StackEmpty(S) Pop(S,e); while(e.di=4 & !StackEmpty(S) MarkPrint(maze,e.seat); Pop(S,e); /留下不能通过的标记,并退一步 /w