课程设计报告示例：迷宫求解.doc

安徽建筑大学课 程 设 计 报 告 课程名称： 数据结构与算法课程设计 题 目： 迷宫求解 院 系： 数理系 专 业： 信息与计算数学 班 级： 学 号： 姓 名： 时 间： 目 录一 、需求分析21. 问题描述：22. 基本要求2二、 概要设计31. 数据结构32. 程序模块33. 算法设计5三、详细设计71. 数据类型定义72. 函数实现代码73. 函数之间的调用关系7四、调试分析7五、用户手册8六、测试结果8七、参考文献9八、附录10迷宫求解题目：以一个m×n长方阵表示迷宫，0和1分别表示迷宫中的通路和障碍，设计一个程序，对任意设定的迷宫，求出一条从入口到出口的通路，或得出没有通路的结论。(1)以二维数组存储迷宫数据；(2)求得的通路以二元组( i , j )的形式输出，其中（i, j）指示迷宫中的一个坐标。一 、需求分析1. 问题描述：在迷宫中求出从入口到出口的路径。经分析，一个简单的求解方法是：从入口出发，沿某一方向进行探索，若能走通，则继续向前走；否则沿原路返回，换一方向再进行搜索，直到所有可能的通路都探索到为止。即所谓的回溯法。求迷宫中从入口到出口的所有路径是一个经典的程序设计问题。由于计算机解迷宫时，通常用的是“穷举求解”的方法，即从入口出发，顺某一方向向前探索，若能走通，则继续往前走；否则沿原路退回，换一个方向再继续探索，直至所有可能的通路都探索到为止。为了保证在任何位置上都能沿原路退回，显然需要用一个后进先出的结构来保存从入口到当前位置的路径。因此，在求迷宫通路的算法中应用“栈”也就是自然而然的事了。 假设“当前位置”指的是“在搜索过程中某一时刻所在图中某个方块位置”，则求迷宫中一条路径的算法的基本思想是：若当前位置"可通"，则纳入"当前路径"，并继续朝“下一位置”探索，即切换“下一位置”为“当前位置”，如此重复直至到达出口；若当前位置“不可通”，则应顺着“来向”退回到“前一通道块”，然后朝着除“来向”之外的其他方向继续探索；若该通道块的四周四个方块均“不可通”，则应从“当前路径”上删除该通道块。所谓“下一位置”指的是“当前位置”四周四个方向（东、南、西、北）上相邻的方块。2. 基本要求（1）以二维数组maze.adrm+1n+1表示迷宫，其中mg0j和mgm+1j(0 j n)及mgi0和mgin(0 i m)为添加的一圈障碍，数组中以元素值为0表示通路，1表示障碍，限定迷宫大小m,n 10。（2）用户以文件的形式输入迷宫的数据：文件中第一行的数据为迷宫的行数m和列数n;从第2行至第m+1行（每行n个数）为迷宫值，同一行的两个数之间用空白字符相隔。（3）迷宫入口为（1，1），出口为（m,n）。（4）每次移动只能从一个无障碍的单元到周围8个方向上任意无障碍的单元，编制程序给出一条通过迷宫的路径或报告一个“无法通过”的信息。（5）本程序只求出一条成功的通路。3 测试数据见下表，当入口为（1，1）时，出口为（8，8）用一个字符类型的二微数组表示迷宫，数组中的每个元素表示一个小方格，取值“0”（表示可以进出）或“1”（表示不可以进出）随机产生一个8*8的迷宫，其中使用迷宫障碍坐标如下：（1，3），（1，7），（2，3），（2，7），（3，5），（3，6），（4，3），（4，4），（5，4），（6，2），（6，6），（7，2），（7，3），（7，4），（7，6），（7，7），（8，1）。二、 概要设计1. 数据结构栈（stack）是限定仅在表尾进行插入或删除操作的线性表。因此，对栈来说，表尾端有特殊含义，称为栈顶（top）,相应的，表头端称为栈底（bottom）。不含元素的空表称为空栈。假设栈S=（a1,a2,，an），则称a1为栈底元素，an为栈顶元素。栈的修改是按后进先出的原则进行的。因此，栈又称为后进先出（List In First Out）的线性表。在迷宫问题中，假设以栈S记录“当前路径”，则栈顶中存放的是“当前路径上最后一个通道块”。由此，“纳入路径”的操作即为“当前位置入栈”；“从当前路径上删除前一通道块”的操作即为“出栈”。基本操作的函数原型说明。2. 程序模块栈的顺序存储表示#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;     3各模块之间的调用关系以及算法设计（1）Stack.h中调用的base.h#include <stdio.h>#include <stdlib.h>#include <string.h>#define TRUE 1#define FALSE 0#define OK 1#define ERROR 0#define OVERFLOW -2typedef int Status;（2）主程序maze.c中调用的stack.h#include "base.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;/DestroyStack3. 算法设计求迷宫中一条从入口到出口的路径的算法可简单描述如下： 设定当前位置的初值为入口位置； do 若当前位置可通， 则将当前位置插入栈顶； / 纳入路径 若该位置是出口位置，则结束；/ 求得路径存放在栈中 否则切换当前位置的东邻方块为新的当前位置； 否则 若栈不空且栈顶位置尚有其他方向未被探索， 则设定新的当前位置为: 沿顺时针方向旋转 找到的栈顶位置的下一相邻块； 若栈不空但栈顶位置的四周均不可通， 则 删去栈顶位置； / 从路径中删去该通道块 若栈不空，则重新测试新的栈顶位置， 直至找到一个可通的相邻块或出栈至栈空； while (栈不空）； 在此，尚需说明一点的是，所谓当前位置可通，指的是未曾走到过的通道块，即要求该方块位置不仅是通道块，而且既不在当前路径上（否则所求路径就不是简单路径），也不是曾经纳入过路径后又从路径上删除的通道块（否则只能在死胡同内转圈）。 typedef struct int ord; / 通道块在路径上的“序号” PosType seat; / 通道块在迷宫中的“坐标位置” int di; / 从此通道块走向下一通道块的“方向” SElemType; / 栈的元素类型 Status MazePath ( MazeType maze, PosType start, PosType end ) / 若迷宫maze中从入口 start到出口 end的通道， / 则求得一条存放在栈中（从栈底到栈顶），并返回 / TRUE；否则返回FALSE InitStack(S); curpos = start;/ 设定“当前位置”为“入口位置” curstep = 1; / 探索第一步 do if (Pass (curpos) / 当前位置可以通过，即是未曾走到过的通道块 FootPrint (curpos); / 留下足迹 e = ( curstep, curpos, 1 ); Push (S,e); / 加入路径 if ( curpos = end ) return (TRUE);/ 到达终点（出口） curpos = NextPos ( curpos, 1 );/ 下一位置是当前位置的东邻 curstep+; / 探索下一步 else / 当前位置不能通过 if (!StackEmpty(S) Pop (S,e); while (e.di=4 && !StackEmpty(S) MarkPrint (e.seat); Pop (S,e); / 留下不能通过的标记，并退回一步 / while if (e.di<4) e.di+; Push ( S, e);/ 换下一个方向探索 curpos = NextPos (curpos, e.di );/ 设定当前位置是该新方向上的相邻块 / if / if / else while ( !StackEmpty(S) ); return (FALSE); / MazePath三、详细设计1. 数据类型定义typedef struct int r; int c; char adrMAXLENMAXLEN; MazeType; /迷宫类型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)3. 函数之间的调用关系首先调用InitMaze(maze)，创建和初始化迷宫，初始化成功后输入迷宫的入口和出口坐标。接着迷宫求解调用MazePath(maze)并在其中调用可通位置的Pass(maze) 程序，并用FootPrint(maze,curpos)打印出足迹。如果非通，用MarkPrint(Maze)标记，直到最后，标记路径信息void PrintMaze(Maze)。四、调试分析 经过对程序的编制，调试和运行，使我更好的掌握了栈基本性质和有关迷宫问题的解决方法，熟悉了各种调用的数据类型，在调试和运行过程中使我更加的了解和熟悉程序运行的环境，提高了我对程序调试分析的能力和对错误的纠正能力五、用户手册1.运行环境，执行文件1编制，调试和运行程序总是依赖所使用的语言环境，当然也令支持语言的系统程序的基础环境即操作系统环境的影响，此课程设计以Turbo C为依据，作为运行环境。2.用户界面Turbo C 3.操作过程 点击Turbo C的快捷图标，进入Turbo C的开发环境，进入“File”子菜单，选取“New”，开始输入一个新文件，编写新的程序。判断改错之后，按<F2>存盘。 对文件进行编译和链接在程序编写后，需要将其编译成可执行文件，需要用“compile”中的F9进行编译和链接。然后看文件中是否存在错误，存在错误改正，直到没有错误。 运行 采用相关功能“compile”菜单，运行已形成好的可执行文件。如果源程序文件尚未编译或链接，选择此项目时系统也会进行编译和链接，如果程序中没有错误，再进行处理后的可执行文件。与此功能对应的快捷键为<Ctrl>+<F9>六、测试结果输入数据：当入口为（1，1）时，出口为（8，8）用一个字符类型的二微数组表示迷宫，数组中的每个元素表示一个小方格，取值“0”（表示可以进出）或“1”（表示不可以进出）随机产生一个8*8的迷宫，其中使用迷宫障碍坐标如下：（1，3），（1，7），（2，3），（2，7），（3，5），（3，6），（4，3），（4，4），（5，4），（6，2），（6，6），（7，2），（7，3），（7，4），（7，6），（7，7），（8，1），（-1，-1）输入过程如下图所示：输入时(-1，-1）结束，接着输入入口参数（1，1）然后输入出口参数（8，8），运行： 运行结果如下图所示：上图中”1”表示围墙和障碍物。”表示走过但不是通路.而”0”就是所要求的老鼠走过的最小路径.七、参考文献1 Richard F. Gilberg, Behrouz A. Forouzan. Data Structure. Brooks/Cole, Thomson Asia Pte Ltd, USA, 2000.2 严蔚敏, 吴伟民. 数据结构（第二版）. 北京：清华大学出版社, 1992.3 数据结构（C语言版） 李云清 杨庆红 揭安全 编著 人民邮电出版社4 C语言程序设计（第二版） 谭浩强 著 清华大学出版社5 数据结构课程设计 苏仕华 等编著 机械工业出版社八、附录原程序文件名清单:/base.h#include <stdio.h>#include <stdlib.h>#include <string.h>#define TRUE 1#define FALSE 0#define OK 1#define ERROR 0#define OVERFLOW -2typedef int Status;/stack.h#include "base.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;/DestroyStack/maze.c#include "stack.h"#define MAXLEN 10/迷宫包括外墙最大行列数目typedef struct int r; int c; char adrMAXLENMAXLEN;/可取' ''*' '' '#'MazeType; /迷宫类型Status InitMaze(MazeType &maze)/初始化迷宫若成功返回TRUE,否则返回FALSE int m,n,i,j; printf("Enter row and column numbers: "); 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;j<=maze.c;j+) maze.adrij=' '/初始化迷宫 printf("Enter block's coordinate(-1,-1) to end): "); scanf("%d%d",&m,&n);/接收障碍的坐标 while(m!=-1) if(m>maze.r | n>maze.c)/越界 exit(ERROR); maze.adrmn='1'/迷宫障碍用'#'标记 printf("Enter block's coordinate(-1,-1) to end): "); scanf("%d%d",&m,&n); /while return OK;/InitMaze Status Pass(MazeType maze,PostType curpos)/当前位置可通则返回TURE,否则返回FALSE if(maze.adrcurpos.rcurpos.c=' ')/可通 return TRUE; else return FALSE;/PassStatus FootPrint(MazeType &maze,PostType curpos)/若走过并且可通返回TRUE,否则返回FALSE/在返回之前销毁栈S maze.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)/曾走过但不是通路标记并返回OK maze.adrcurpos.rcurpos.c=''/""表示曾走过但不通 return OK;/MarkPrintStatus MazePath(MazeType &maze,PostType start,PostType end) /若迷宫maze存在从入口start到end的通道则求得一条存放在栈中 /并返回TRUE,否则返回FALSE Stack 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); /留下不能通过的标记,并退一步 /while if(e.di < 4) e.di+;/换下一个方向探索 Push(S,e); curpos=NextPos(e.seat,e.di);/设定当前位置是该/新方向上的相邻 /if /if /else while(!StackEmpty(S); if(!DestroyStack(S)/销毁失败 exit(OVERFLOW); else return FALSE;/MazePathvoid PrintMaze(MazeType &maze) /将标记路径信息的迷宫输出到终端(包括外墙) int i,j; printf("nShow maze path(*-pathway):nn"); printf(" "); for(i=0;i<=maze.r+1;i+)/打印列数名 printf("%4d",i); printf("nn"); for(i=0;i<=maze.r+1;i+) printf("%2d",i);/打印行名 for(j=0;j<=maze.c+1;j+) printf("%4c",maze.adrij);/输出迷宫/当前位置的标记 printf("nn"); /PrintM