迷宫问题数据结构

迷宫问 题 快递公司问题件快递公司问题件货款处理关于圆的周长面积重点题型关于解方程组的题及答案关于南海问题 数据结构 一、 设计 领导形象设计圆作业设计ao工艺污水处理厂设计附属工程施工组织设计清扫机器人结构设计 内容与设计要求 1(设计内容: 1)问题描述 以一个M*N的长方阵表示迷宫，0和1分别表示迷宫中的通路和墙壁。设计一个程序，对任意设定的迷宫，求出一条从入口到出口的通路，或得出米有通路的结论。 2)基本要求 a.实现一个以链表作存储结构的栈类型，然后编写一个求解迷宫的非递归程序。求得的通路以三元组(i，j，d)的形式输出，其中:(i，j)指示迷宫中的一个坐标，d表示走到下一个坐标的方向。 b.编写递归形式的算法，求得迷宫中所有可能的通路。 3)测试数据 迷宫的测试数据如下:左上角(1,1)为入口，右下角(8,9)为出口。 0 0 1 0 0 0 1 0 0 0 1 0 0 0 1 0 0 0 0 0 1 1 0 1 0 1 1 1 0 0 1 0 0 0 0 1 0 0 0 0 0 1 0 0 0 1 0 1 0 1 1 1 1 0 0 1 1 1 0 0 0 1 0 1 1 1 0 0 0 0 0 0 4)实现提示 计算机解迷宫通常用的是“穷举求解”方法，即从入口出发，顺着某一个方向进行探索，若能走通，则继续往前进;否则，沿着原路退回，换一个方向继续探索，直至出口位置，求得一条通路。假如所有可能的通路都探索到而未能到达出口，则设定的迷宫没有通路。 可以二维数组存储迷宫数据，通常设定入口点的下标为(1，1)，出口点的下标为(m，n)。为处理方便起见，可在迷宫的四周加一圈障碍。对于迷宫中任一位置，均可约定有东、南、西、北四个方向可通。 2(设计要求: , 课程设计报告 规范 编程规范下载gsp规范下载钢格栅规范下载警徽规范下载建设厅规范下载 1)需求分析 a.程序的功能。 b.输入输出的要求。 2)概要设计 a.程序由哪些模块组成以及模块之间的层次结构、各模块的调用关系;每个模块的功能。 b.课题涉及的数据结构和数据库结构;即要存储什么数据，这些数据是什么样的结构，它们之间有什么关系等。 3)详细设计 a.采用C语言定义相关的数据类型。 b.写出各模块的类C码算法。 c.画出各函数的调用关系图、主要函数的流程图。 4)调试分析以及设计体会 a.测试数据:准备典型的测试数据和测试 方案 气瓶 现场处置方案 .pdf气瓶 现场处置方案 .doc见习基地管理方案.doc关于群访事件的化解方案建筑工地扬尘治理专项方案下载 ，包括正确的输入及输出结果和含有错误 的输入及输出结果。 b.程序调试中遇到的问题以及解决问题的方法。 c.课程设计过程经验教训、心得体会。 5)使用说明 用户使用手册:说明如何使用你编写的程序，详细列出每一步的操作步骤。 6)书写格式 见附带说明。 7)附录 a.参考书目 b.源程序清单(带注释) , 考核方式 指导老师负责验收程序的运行结果，并结合学生的工作态度、实际动手能力、创新精神和设计 报告等进行综合考评，并按优秀、良好、中等、及格和不及格五个等级给出每位同学的课程设计成 绩。具体考核标准包含以下几个部分: ? 平时出勤 (占10%) ? 系统需求分析、功能设计、数据结构设计及程序总体结构合理与否(占10%) ? 程序能否完整、准确地运行，个人能否独立、熟练地调试程序(占40%) ? 设计报告(占30%) 注意:不得抄袭他人的报告(或给他人抄袭)，一旦发现，成绩为零分。 ? 独立完成情况(占10%)。 , 课程验收要求 ? 运行所设计的系统。 ? 回答有关问题。 ? 提交课程设计报告。 ? 提交软盘(源程序、设计报告文档)。 ? 依内容的创新程度，完善程序情况及对程序讲解情况打分。 二、进度安排 第2周 星期一 星期二 星期三 星期四 星期五 星期六 星期日 上午 8:00~12:00 下午 ? ? ? 14:00~18:00 晚上 18:00~20:00 第3周 星期一 星期二 星期三 星期四 星期五 星期六 星期日 上午 8:00~12:00 下午 ? ? ? 14:00~18:00 晚上 18:00~20:00 附: 课程设计报告装订顺序:封面、任务书、目录、正文、评分、附件(A4大小的图纸及程序清单)。 正文的格式:一级标题用3号黑体,二级标题用四号宋体加粗,正文用小四号宋体;行距为22。 正文的内容:一、课题的主要功能;二、课题的功能模块的划分(要求画出模块图);三、主要功能的实现(至少要有一个主要模块的流程图);四、程序调试;五、总结;六、附件(所有程序的原代码，要求对程序写出必要的注释)。 正文总字数要求在500 0字 个人自传范文3000字为中华之崛起而读书的故事100字新时代好少年事迹1500字绑架的故事5000字个人自传范文2000字 以上(不含程序原代码)。 目录 1.需求分析.........................................................1 1.1程序的功能....................................................1 1.2输入输出的要求................................................1 2.概要设计.........................................................2 2.1模块的层次结构.................................................2 2.2模块间调用关系.................................................3 2.3模块的功能.....................................................4 3.详细设计.........................................................4 3.1c语言定义的相关数据类型........................................4 3.2各模块的类c算法...............................................5 3.3各函数调用关系图..............................................12 3.4主函数流程图..................................................13 4.调试分析与设计体会...............................................14 4.1测试数据.......................................................14 4.2出现的错误和解决方法...........................................16 4.3经验教训与心得体会............................................19 5.使用说明........................................................21 6.附录.............................................................23 6.1参考书目.......................................................23 6.2源代码.........................................................23 1.需求分析 1.1程序的功能: 用户可以任意设定的一个以M*N的长方阵;来表示迷宫，0和1分别表示迷宫中的通路和墙壁。用户可以手动输入设定迷宫，在屏幕上显示出迷宫。由递归算法求出迷宫的所有通路。由非递归穷举求解出迷宫的一条通路。通路以三元组(i，j，d)的形式输出，其中:(i，j)指示迷宫中的一个坐标，d表示走到下一个坐标的方向。如果有通路就求出一条从入口到出口的通路，或没有通路就得出没有通路的结论。 1.2输入输出要求: 首先进入界面输出提示请用户输入迷宫行数，列数。用户可以从键盘分别输入用户想建 立的迷宫的行数与列数，来确定迷宫的大小。 接着输出提示请用户输入迷宫的各行各列其中外围墙壁不用输入。注意的是迷宫是由0和1分别表示迷宫的通路和墙壁，所以用户设置迷宫的时候要注意输入的是否是0和1确保输入的正确。程序才不会出错。且最后一个数需要是0，迷宫每行相邻的两个数可以用空格隔开。列与列可以回车键换行。输入完毕后，界面显示输出设置的加有外围的迷宫。 接着输出的就是由递归算法求出的所有迷宫的通路以及由穷举求解迷宫中的一条通路，如果有通路时，通路输出形式是以通路以三元组(i，j，d)的形式输出，其中:(i，j)指示迷宫中的一个坐标，d表示走到下一个坐标的方向。每步之间由“--->”隔开。最后一步是输出“出口”形如:“(i，j，d)--->(i，j，d)--->.....--->出口”。如果没有通路就得出“该迷宫没有通路”。 2.概要设计: 2.1模块的层次结构图: 程序由四个模块组成，分别为:迷宫初始化模块，迷宫输出模块，递归求通路模块， 以及穷举求通路模块。 迷宫问题 穷递迷迷 举归宫宫 求求输初 通通出始 路路函化 函函数 函 数 数 数 图2-1:模块层次结构图 2.2模块间调用关系图: 开始 迷宫初始化模块 迷宫输出模块 递归求通路模块 有通路 Y 结束 N 穷举求通路函数 图2-2:模块间的调用图 2.3模块的功能: 迷宫初始化函数定义为int ** initMaze()。该函数的作用就是对迷宫的大小以及对迷宫有墙无墙的设定。其中还调用了加边函数addWall(maze);对设定的迷宫四周加上围墙。完成对迷宫进行初始化。 迷宫输出函数定义为void printMaze(int ** maze) 。该函数的作用就是将设定好的迷宫显示输出。 递归求通路函数的定义为void mazePath() 。该函数的作用就是采用递归的思想求出设定好的迷宫由入口到出口的所有通路，然后输出。 穷举求通路函数的定义为int mgpath(int xi,int yi,int xe,int ye)。该函数的作用就是采用了穷举遍历的方法求出设定好的迷宫由入口到出口的一条通路，然后输出。 3.详细设计 3.1C语言定义的相关数据类型: int m,n; int count; 整形变量m和n分别是存储迷宫的行数与列数。 整形变量count表示通路的条数。 int **maze = NULL; 整形二维指针变量 **maze来存储迷宫。 struct Element { int i; int j; int di;}; 使用结构体Element来表示节点，i表示节点行坐标j表示节点列坐标di表示下一 个要走节点的方向。 typedef struct LinkStack { struct Element element; struct LinkStack * next; struct LinkStack * prior; }LinkStack; LinkStack *top = NULL; LinkStack *head = NULL; 使用链栈来存储找到迷宫的通路。 3.2各模块的类c算法: 迷宫初始化模块: int ** initMaze() //对迷宫进行初始化的函数 { int i,j; int flag = 0; printf("请输入迷宫的行数 m="); scanf("%d",&m); printf("请输入迷宫的列数 n="); scanf("%d",&n); maze = (int **)malloc(sizeof(int *)*(m+2));//开辟存储空间 for(i=0; ielement.di; //di一开始就保存当前栈顶指针所指的节点的方向 LinkStack *node= (LinkStack *) malloc(sizeof(LinkStack)); //每一次递归都首先开辟节点 node->element.di = di; //保存节点寻找的方向 if(top == NULL) { head = (LinkStack *) malloc(sizeof(LinkStack)); //链表的头指针 head->element.i = 1; head->element.j = 0; head->element.di = 1; head->prior = NULL; top = head; node->element.i = 1; //入口节点 node->element.j = 1; >element.di = -1; node- } top->next = node; node->next = NULL; node->prior = top; top = node; //新开辟入口节点进栈 di = top->element.di; //取得当前栈顶指针所指的元素的方向 while(di<4 && find == 0) //寻找下一个可走节点 { di++; switch(di) {case0:i=top->prior->element.i-1;j=top->prior->element.j;break; case1:i=top->prior->element.i;j=top->prior->element.j+1;break; case2:i=top->prior->element.i+1;j=top->prior->element.j;break; case3:i=top->prior->element.i;j=top->prior->element.j-1;break; } if(maze[i][j] == 0)find = 1; //判断找到了下一个可走节点 } if(i == m && j == n) //判断找到的节点是否为出口 { top->element.i = m; //是出口节点进栈 top->element.j = n; top->prior->element.di = di; printf("%4d:",++count); LinkStack * n = head->next; //指向入口节点 while(n != NULL) //输出通路 { printf("(%d,%d,%d)",n->element.i,n->element.j,n->element.di) printf(" -> "); if((k + 1)%5 == 0) //每输出5个节点换一行 {printf("\n\t");} k++; n = n->next;} "); printf("出口 printf("\n"); maze[top->element.i][top->element.j] = 0; //当前节点没有可走的 下一个节点就将其变成可走 top = top->prior; //当前节点退栈释放 free(node); mazePath(); //新找到节点递归调用 } else {if(find == 1) {top->prior->element.di = di; //退栈时，当找到下一个可走的节 点后必须对当前节点的方向进行了更新 top->element.i = i; top->element.j = j; top->element.di = -1; maze[i][j] = -1; //避免重复走到该点 mazePath(); } else {maze[top->prior->element.i][top->prior->element.j] = 0; //让 它成为下条路径的可走路径 top = top->prior->prior; //退栈 free(node); mazePath(); } } 穷举求通路模块: int mgpath(int xi,int yi,int xe,int ye) { printf("非递归通路:\n"); int i,j; int find; int di; LinkStack *node= (LinkStack *) malloc(sizeof(LinkStack)); //开辟 入口节点 head = (LinkStack *) malloc(sizeof(LinkStack)); //链表的 头指针 head->element.i = 1; //头结点初始化 head->element.j = 0; head->element.di = 1; head->prior = NULL; top = head; node->element.i = xi; //入口节点进栈 node->element.j = yi; node->element.di = -1; maze[1][1]=1; //进栈后标记为不可走节点 top->next = node; head->next=node; node->next = NULL; node->prior = top; di= node->element.di; top=node; LinkStack * n = head->next; //n指向入口节点 while(top->prior!= NULL) { find=0; //find的初始化 di=top->element.di; while(di<4&&find==0) //寻找下一个可走节点 {di++; switch(di) { case 0:i=top->element.i-1;j=top->element.j;break; case 1:i=top->element.i;j=top->element.j+1;break; case 2:i=top->element.i+1;j=top->element.j;break; case 3:i=top->element.i,j=top->element.j-1;break; }if(maze[i][j]==0){find=1;top->element.di=di; //find为1表示为找到下一个可走节点 } if(find==1) { if(i==xe&&j==ye&&maze[i][j]==0) //如果 找到的节点是出口 { LinkStack *node1= (LinkStack *) malloc(sizeof(LinkStack)); //出口 节点入栈 top->element.di=di; node1->element.i=i; node1->element.j=j; node1->element.di=-1; top->next=node1; node1->next=NULL; node1->prior=top; top=node1; maze[i][j]=1; printf(" "); while(n!=NULL) //输出栈 { printf("(%d,%d,%d )",n->element.i,n->element.j,n->element.di);print f(" -> "); n=n->next; }printf("出口"); printf("\n"); return(0); } else //如果找到的点不是出口 { LinkStack *node1= (LinkStack *) malloc(sizeof(LinkStack)); //可走节 点入栈 top->element.di=di; node1->element.i=i; node1->element.j=j; node1->element.di=-1; top->next=node1; node1->next=NULL; node1->prior=top; top=node1; maze[i][j]=1; } } else //没有下一个可走节点就将该节点退栈 {maze[top->element.i][top->element.j]=0; top = top->prior; //退栈 free(top->next); } } return(0); //返回一个有效值 3.3各函数调用关系图: 开始 调用initMaze() 调用addWall(maze) 调用printMaze(maze) 调用mazePath() Y 输出没通路 Count==0 调用mgpath(1,1,m,n) N 结束 图3-1:各函数调用关系图 3.4主要函数流程图: 开始 建立头指针，top指向 入口节点进栈 Top指向当前节点 top->prior!= NULL Y di=top->element.di N di++ N di<4 Y N Y 找到下个可走节点 Y 节点是出口 节点进栈 输出通路 当前节点退栈，上一个节点 为当前节点 结束 图3-2:穷举法求通路流程图 4.调试分析: 4.1测试数据: 迷宫的测试数据如下:左上角(1,1)为入口，右下角(8,9)为出口。 0 0 1 0 0 0 1 0 0 0 1 0 0 0 1 0 0 0 0 0 1 1 0 1 0 1 1 1 0 0 1 0 0 0 0 1 0 0 0 0 0 1 0 0 0 1 0 1 0 1 1 1 1 0 0 1 1 1 0 0 0 1 0 1 1 1 0 0 0 0 0 0 这是一套正确的测试数据。 输出结果如下: 迷宫的随机数据如下:左上角(1,1)为入口，右下角(8,8)为出口。 0 0 0 1 1 1 1 1 0 1 0 1 1 1 1 1 0 1 0 0 1 1 1 1 0 1 1 0 0 0 0 0 0 0 0 1 1 1 1 0 1 1 0 1 1 1 1 0 1 1 0 0 0 1 1 0 1 1 1 1 0 0 0 0 输出结果如下: 4.2出现的错误和解决方法: 在调试的过程中，遇到了许多的小问题，例如词组的拼写错误，在编写 过程中汉英切换没注意，标点符号用的汉化的。或是语句结尾分号忘打了等 等。在编译的过程中都会提示出错。修改后都没问题。真正的问题就是隐藏 于程序中的逻辑问题。当程序编译连接完成后测试数据1如下:左上角(1,1) 为入口，右下角(3,3)为出口 0 1 1 0 1 1 0 0 0 这是一套正确的数据运行结果如下: 输出正确。运行的结果与预期是一样的，输出正确。 但当输入测试数据2如下:左上角(1,1)为入口，右下角(3,3)为出口 0 0 1 0 1 1 0 0 0 这也是一套正确的数据运行的结果如下: 输出错误。运行的结果却是与结果是不一样的，非递归求通路没有输出。不同的测试数据却有的能正确输出，有的却是错误的输出。为了检测出错误，我就在源代码242行出添加了一个语句printf("找到的节点为:%d,%d,%d",i,j,di);检测后输出“找到的节点为:1,2,1。有自己预算要走的通路节点，则可以推断出，程序当寻找到节点(1,2)时没有节点可走时，就没有继续往下寻找，根据程序就是在退栈的时候出现了错误。经过一番检查，发现要将退栈的节点错误了。语句为free(node);释放的就是开始节点(1,1)而不是想要释放的节点(1,2)。将语句改为free(top->next);程序正确了。由此也可想到测试数据1之所以会输出正确时因为该程序寻找通路时没有要退栈的节点。所以输出才没有出错。修改之后再测试数据2，运行结果如下: 输出才正确。 在数据测试的过程中，如果，m与n的值相等的情况下不会出错的，但是当m与n的值不相等时，就会出现错误，这个问题就是在Debug模式下出现Debug Error～DAMAGE:after Normal block (#46)错误，网上一搜，知道这是由越界访问内存，破坏了内存中其他数据而引起问题。但大部分帖子介绍这个问题都是由动态申请内存和动态释放引起。而我的程序中根本没有用过new和delete;也有一个帖子说数组越界也会发生这种情况，我又查了很多遍，数组都正常。只好继续调代码，最后被我跟到一个调用的释放二维指针数组maze空间释放上面出错了。最初释放内存时就是直接Free(maze);总是提示错误，后来一想maze为二维指针，应该分级释放，就把释放内存部分的代码改成了: if(maze != NULL) { for(i=0;i #include #include //*************参数定义**************** int m,n; int **maze = NULL; //表示迷宫 struct Element { //这里就是定义节点 int i; int j; int di; }; typedef struct LinkStack { //这里就是定义链栈... struct Element element; struct LinkStack * next; struct LinkStack * prior; }LinkStack; LinkStack *top = NULL; //栈顶指针,因为是链栈，所以栈顶指针要是一个指针变量 LinkStack *head = NULL; //链栈的头指针 int count=0; //路径计数 int mgpath(int xi,int yi,int xe,int ye); //**************迷宫输出函数**************** void printMaze(int ** maze) //输出迷宫 { int i,j; printf("您的迷宫图如下所示:\n"); for(i=0; i0 && i<(m+2-1)) { maze[i][0]=1; maze[i][n+2-1]=1; break; } if(i==m+2-1) { maze[i][j]=1; } } } } //********************迷宫初始化函数*********** int ** initMaze() { //对迷宫进行初始化的函数 int i,j; int flag = 0; printf("请输入迷宫的行数 m="); scanf("%d",&m); printf("请输入迷宫的列数 n="); scanf("%d",&n); maze = (int **)malloc(sizeof(int *) * (m+2)); //开辟迷宫的存储空间 printf("\n*****************************************\n"); for(i=0; ielement.di; //di一开始就保存当前栈顶指针所指的节点的方向 LinkStack *node= (LinkStack *) malloc(sizeof(LinkStack)); //每一次递归都首先开辟节点(因为 要查找元素，所以要先开辟节点) node->element.di = di; if(top == NULL) { head = (LinkStack *) malloc(sizeof(LinkStack)); //链表的头指针 head->element.i = 1; head->element.j = 0; head->element.di = 1; head->prior = NULL; top = head; node->element.i = 1; node->element.j = 1; node->element.di = -1; } top->next = node; node->next = NULL; node->prior = top; top = node; //新开辟节点进栈 di = top->element.di;//取得当前栈顶指针所指的元素的方向 while(di<4 && find == 0) { di++; switch(di) { case 0: i = top->prior->element.i - 1;j = top->prior->element.j;break; case 1: i = top->prior->element.i;j = top->prior->element.j + 1;break; case 2: i = top->prior->element.i + 1;j = top->prior->element.j;break; case 3: i = top->prior->element.i;j = top->prior->element.j - 1;break; } if(maze[i][j] == 0)find = 1; } if(i == m && j == n) { top->element.i = m; top->element.j = n; top->prior->element.di = di; printf("%4d:",++count); LinkStack * n = head->next; while(n != NULL) { printf("(%d,%d,%d ) ",n->element.i,n->element.j,n->element.di);//找到出口，输出路径 printf(" -> "); if((k + 1)%5 == 0) { printf("\n\t"); } k++; n = n->next; } printf("出口"); printf("\n"); maze[top->element.i][top->element.j] = 0; top = top->prior; //退栈 free(node); mazePath(); } else { if(find == 1) { top->prior->element.di = di; //退栈时，当找到下一个可走的节点后必须对当前节点的方向进行了更新 top->element.i = i; top->element.j = j; top->element.di = -1; maze[i][j] = -1; //避免重复走到该点 mazePath(); } else { maze[top->prior->element.i][top->prior->element.j] = 0; //让它成为下条路径的可走路径 top = top->prior->prior; //退栈 free(node); mazePath(); } } } //*******************穷举求解通路函数********************* int mgpath(int xi,int yi,int xe,int ye) { printf("非递归通路:\n"); int i,j; int find; int di; LinkStack *node= (LinkStack *) malloc(sizeof(LinkStack)); head = (LinkStack *) malloc(sizeof(LinkStack)); //链表的头指针 head->element.i = 1; head->element.j = 0; head->element.di = 1; head->prior = NULL; top = head; node->element.i = xi; //入口节点进栈 node->element.j = yi; node->element.di = -1; maze[1][1]=1; //进栈后标记为不可走节点 top->next = node; head->next=node; node->next = NULL; node->prior = top; di= node->element.di; top=node; LinkStack * n = head->next; while(top->prior!= NULL) { find=0;//find的初始化 di=top->element.di; while(di<4&&find==0) //寻找下一个可走节点 { di++; switch(di) { case 0:i=top->element.i-1;j=top->element.j;break; case 1:i=top->element.i;j=top->element.j+1;break; case 2:i=top->element.i+1;j=top->element.j;break; case 3:i=top->element.i,j=top->element.j-1;break; if(maze[i][j]==0){find=1;top->element.di=di;printf("find找到的点%d,%d,%d",i,j);} //find为1表示为找到下一个可走节点 } if(find==1) { if(i==xe&&j==ye&&maze[i][j]==0) //如果找到的节点是出口 { LinkStack *node1= (LinkStack *) malloc(sizeof(LinkStack)); //出口节点入栈 top->element.di=di; node1->element.i=i; node1->element.j=j; node1->element.di=-1; top->next=node1; node1->next=NULL; node1->prior=top; top=node1; maze[i][j]=1; printf(" "); while(n!=NULL) //输出栈 {printf("(%d,%d,%d)",n->element.i,n->element.j,n->element.di); printf(" -> "); n=n->next; } printf("出口"); printf("\n"); return(0); } else //如果找到的点不是出口 { LinkStack *node1= (LinkStack *) malloc(sizeof(LinkStack)); //可走节点入栈 top->element.di=di; node1->element.i=i; node1->element.j=j; node1->element.di=-1; top->next=node1; node1->next=NULL; node1->prior=top; top=node1; maze[i][j]=1; printf("找到的节点有%d,%d,%d",node1->element.i,node1->element.j,node1->element.di); } } else //没有下一个可走节点就将该节点退栈 { maze[top->element.i][top->element.j]=0; top = top->prior; //退栈 free(top->next); } } return(0); } //******************主函数************************** void main() { int i; initMaze(); mazePath(); if(count==0) {printf("************"); printf("\n该迷宫没有通路\n"); return; } printf("\n**************************\n"); mgpath(1,1,m,n); if(head != NULL) //释放内存 { free(head); } return; } 计算机与通信学院课程设计评分表 课题名称: 迷宫问题 项目评价 设计方案的合理性与创造性 设计与调试结果 设计说明书的质量 答辩陈述与回答问题情况 课程设计周表现情况 综合成绩 教师签名: 日 期: