湖南工业大学
课程设计
计算机与通信学院（系、部）2012~ 2013 学年第 2 学期课程名称数据结构课程设计指导教师xxxx 职称副教授
学生姓名xxx 专业班级计算机科学与技术学号xxxxxx
题目迷宫最短路径求法
成绩起止日期2013 年 6 月26 日～2013 年 6 月27 日
目录清单
湖南工业大学
课程设计任务书
2012 —2013 学年第2 学期
计算机与通信学院（系、部）计算机科学与技术专业1203 班级课程名称：数据结构课程设计
设计题目：求迷宫问题的最短路径
完成期限：自2013 年 6 月25 日至2013 年 6 月27 日共周
指导教师（签字）：年月日系（教研室）主任（签字）：年月日
数据结构课程设计
设计说明书
求迷宫的最短路径
起止日期：2013 年 6 月25 日至2013 年 6 月27 日
学生姓名xxx
班级计算机科学与技术1203
学号xxxx
成绩
指导教师(签字)
计算机与通信学院（部）
2013年6 月26 日
.4.
目录
1 课程设计简介 (6)
1.1 课程设计的目的 (6)
1.2 课程设计内容 (6)
2 数据结构的设计................................... 错误！未定义书签。
3 功能模块（或算法）描述........................... 错误！未定义书签。
4 程序运行结果 (10)
5心得体会 (15)
参考文献 (16)
.5.
1 课程设计简介
1.1课程设计的目的
通过实验，掌握如下内容：
1：进一步掌握指针、模板类、异常处理的使用；
2：掌握队列的操作和实现方法；
3：学习使用队列解决实际问题的能力；
4：学习使用图的广度优先搜索解决实际问题的能力。
1.2课程设计内容
2
利用数据结构的队列遍历求出迷宫问题的最短路径。
迷宫求解问题如下：
迷宫问题是实验心理学中的一个经典问题，心理学家把一只老鼠从一个无顶盖的大盒子的入口处赶进迷宫。迷宫中设置很多隔壁，对前进方向形成了多处障碍，心理学家在迷宫的唯一出口处放置了一块奶酪，吸引老鼠在迷宫中寻找通路以达到出口。
我们要解决的是如何找到一条迷宫的最短路径。
测试算法的迷宫由使用者设置，例如设置的迷宫如下图所示
1.3程序功能
打印老鼠走出迷宫的最短路径
2.程序算法及功能分析
2.1存储结构：
队列顺序存储
示意图如下：
2.2关键算法分析
核心算法思想：
1：如果采用直接递归的方式，用栈很容易实现路径的输出，但是这条路径不
一定是最短路径，为了改变算法，达到输出最短路径的目的，采用队列的实现
方式。
2：为查找最短路径，使用了图中的广度搜索。
算法的基本思路为：从迷宫入口点（1,1）出发，向四周搜索，几下所有一步能
到达的坐标点；然后依次再从这些点出发，再几下所有一步能到达的坐标点；
依此类推，直到到达迷宫的出口点（m,n）为止，然后从出口点沿着搜索路径
回溯到入口。
typedef struct
{
int x,y; // 行、列坐标
int pre; // 链域
}sqtype;
sqtype sq[r]; //作为队列的存储空间，记录被访问过的点
关键算法思想的描述和实现：
为寻求最短路径，采用广度优先搜索方法，使用队列实现路径存储，队列中每
个元素用结构存储体系，包含迷宫坐标，队列中的序号，队首指针front,队尾
指针rear,最后采用回溯的方法将路径打印出来。
算法1：
int SHORTPA TH(int maze[m2][n2]) //找迷宫maze的最短路径
{
int i,j,v,front,rear,x,y;
sq[1].x=1; //设定入口的行坐标
sq[1].y=1; //设定入口的纵坐标
sq[1].pre=0;
front=1; //进入迷宫时的队首指针
rear=1; //进入迷宫时的队尾指针
maze[1][1]=-1; //标记入口点已经到达
算法2：
遍历每个位置的四周，将没有走过的位置入队，形成树形的队列，通过出队操作就能找出最短路径
{
x=sq[front].x; y=sq[front].y; //(x，y)为出发点
for(v=0;v<8;v++) //搜索(x,y)的8个相邻点(i,j)是否可到达
{
i=x+move[v].x;
j=y+move[v].y;
if(maze[i][j]==0) //(i,j)为可到达点，将其入队
{
rear++;
sq[rear].x=i; sq[rear].y=j;
sq[rear].pre=front;
maze[i][j]=-1; //标记(i,j)已到达过的点
}
算法3：
广度优先搜索算法的实现，找到最短路径。广度优先算法在此相当于树的层次遍历，如下图：
在迷宫地图中，关键算法三通过不断调用算法二就能将地图中可以走的位置入队，形成类似上图的树形结构，之后广度搜索到的最浅深度即为最短路径。
if(maze[i][j]==0) //(i,j)为可到达点，将其入队
{
rear++;
sq[rear].x=i; sq[rear].y=j;
sq[rear].pre=front;
maze[i][j]=-1; //标记(i,j)已到达过的点
}
if((i==m)&&(j==n)) //到达出口
{
PRINTPATH(sq,rear); //打印路径
// RESTORE(maze); //恢复迷宫
return 1; //成功，返回1
}
算法4：
使用队列指针查找队首指针的方式，从队尾回溯到队首，标记出最短路径。
队列的元素示意如图：
int SHORTPA TH(int maze[m2][n2]) //找迷宫maze的最短路径
{
int i,j,v,front,rear,x,y;
sq[1].x=1;
sq[1].y=1;
sq[1].pre=0;
front=1;
rear=1;
maze[1][1]=-1; //标记入口点已经到达
while(front<=rear) //队列非空
{
x=sq[front].x; y=sq[front].y; //(x，y)为出发点
for(v=0;v<8;v++) //搜索(x,y)的8个相邻点(i,j)是否可到达
{
i=x+move[v].x;
j=y+move[v].y;
if(maze[i][j]==0) //(i,j)为可到达点，将其入队
{
rear++;
sq[rear].x=i; sq[rear].y=j;
sq[rear].pre=front;
maze[i][j]=-1; //标记(i,j)已到达过的点
}
if((i==m)&&(j==n)) //到达出口
{
PRINTPATH(sq,rear); //打印路径
// RESTORE(maze); //恢复迷宫
return 1; //成功，返回1
}
}
front ++; //出队，front指向新的出发点
} // 队空循环结束
return 0; //迷宫无路径，返回0
}
时间复杂度和空间复杂度
算法一盒二的时间复杂度与空间复杂度均为O（1）。
算法三占用空间为迷宫边长n的平方，故空间复杂度为O（n*n）.最多走n*n步，最少走1步，故时间复杂度为O（n*n/2）。
4 程序运行结果
1用代码创建3个文件夹，用于存放数据
。main(){
if((fp=fopen("c:\\book.txt","rb+"))==NULL){
printf("在c盘根目录下没有找到储存图书信息的book.txt文件\n请选择1--手动导入！2--创建此文件\n");
scanf("%d",&xuan);
switch(xuan){
case 2:if((fp=fopen("c:\\book.txt","wb+"))!=NULL)
printf("创建成功\n\n");
break;
case 1:printf("请把名为book.txt的文件复制到c盘根目录下\n\n");
}
}
if((fpj=fopen("c:\\jieyue.txt","rb+"))==NULL){
printf("在c盘根目录下没有找到储存借阅信息的jieyue.txt文件\n请选择1--手动导入！2--创建此文件\n");
scanf("%d",&xuan);
switch(xuan){
case 2:if((fpj=fopen("c:\\jieyue.txt","wb+"))!=NULL)
printf("创建成功\n\n");
break;
case 1:printf("请把名为jieyue.txt的文件复制到c盘根目录下\n\n");
}
}
if((fps=fopen("c:\\student.txt","rb+"))==NULL){
printf("在c盘根目录下没有找到储存学生信息的student.txt文件\n请选择1--手动导入！2--创建此文件\n");
scanf("%d",&xuan);
switch(xuan){
case 2:if((fps=fopen("c:\\student.txt","wb+"))!=NULL)
printf("创建成功\n\n");
break;
case 1:printf("请把名为student.txt的文件复制到c盘根目录下\n\n");
}
}
2,。进入界面
void menu()//菜单
{ system("cls");
printf("\n\n");
printf(" ************* 欢迎进入图书管理查询系统********\n");
for(i=0;i<80;i++)
printf("#");
printf("\n");
printf("\t\t1-----图书录入\t\t\t");
printf("2-----图书浏览\n\n");
printf("\t\t3-----图书查询\t\t\t");
printf("4-----修改删除图书\n\n");
printf("\t\t5-----借阅图书\t\t\t");
printf("6-----归还图书\n\n");
printf("\t\t7-----借阅查询\t\t\t\n");
printf("\n\t\t\t\t输入其他任意键退出\n");
printf("\n");
for(i=0;i<80;i++)
printf("#");
printf("\n\n");
}
2录入图书，输入图书的8种信息，图书名，图书编号，图书作者，出版日期，价格，出版社，类别，入库，成功后返回主菜单。
void end()//录入图书
{ system("cls");
bo boo,booq;
printf("请输入图书名(最多十个字符)：");
scanf("%s",https://www.doczj.com/doc/326033452.html,);
do{
i=1;
printf("请输入图书编号(最多十个字符)：");
scanf("%s",boo.num);
fread(&booq,sizeof(bo),1,fp);
while(!feof(fp)){
if(strcmp(booq.num,boo.num)==0){
printf("\n该编号已存在请重新输入\n\n");
i=0;
break;
}
fread(&booq,sizeof(bo),1,fp);
}
rewind(fp);
}while(i==0);
printf("请输入图书作者(最多十个字符)：");
scanf("%s",boo.writer);
printf("请输入图书出版日期（例如2001年5月3日出版则输入20010503）：");
scanf("%d",&boo.date);
printf("请输入图书价格：");
scanf("%f",&boo.price);
printf("请输入图书出版社(最多十个字符)：");
scanf("%s",boo.press);
printf("请输入图书类别(最多十个字符)：");
scanf("%s",boo.leibie);
printf("请输入图书入库数：");
scanf("%d",&boo.kucun);
boo.jiechu=0;
getchar();
fseek(fp,0,2);
fwrite(&boo,sizeof(bo),1,fp);
printf("\n录入成功！回到主菜单");
system("pause");
}
9 其他键自动退出
5心得体会
学了一个学期的C语言，功底还不扎实，再说C语言学的也并不好，刚做课程实际时，觉得自己肯定无法完成这项工作的，但经过慢慢的尝试探索，不断的发现错误改正错误，还是将其完成了，虽然并不完美
近一个礼拜中,我们有过山穷水尽的困惑；有过柳暗花明的惊喜；有过唇枪舌剑的辩论；有过相互鼓励的安慰。一个多礼拜的时间我们经历了很多，也收获了很多。与其说它是体力与脑力的作业，不如说它是合作精神和毅力的考验。经过这次课程设计，我学到了很多知识和技能，并学会了用所学的知识解决实际问题。
同过本次的课程设计，巩固了我的C语言知识，发现了自身的诸多不足之处，总之，这是一次很好的锻炼机会
参考文献
[4]谭浩强. C语言程序设计（第三版）［Ｍ］. 北京：清华大学出版社，2005
[5]廖雷、罗代忠. C语言程序设计基础实验教程［Ｍ］. 北京：高等教育出版社，2005
[6]谭浩强. C程序设计解题与上机指导(第三版) ［Ｍ］. 北京：清华大学出版社，2005
[7]廖雷等. C语言程序设计基础［Ｍ］. 北京：高等教育出版社，2004
[8]谭浩强，张基温，唐永炎. C语言程序设计教程. 北京: 高等教育出版社，2003
附源代码#include
#include
#include
FILE *fp,*fpj,*fps;
int i,xuan;
typedef struct book{
char name[10];
char num[10];
char writer[10];
int date;
char press[10];
float price;
char leibie[10];
int kucun;
int jiechu;
}bo;
typedef struct student{
char name[10];
char num[10];
int jie;
}st;
typedef struct jieyue{
char snum[10];
char bnum[10];
}ji;
void menu()//菜单
{ system("cls");
printf("\n\n");
printf(" ************* 欢迎进入图书管理查询系统********\n");
for(i=0;i<80;i++)
printf("#");
printf("\n");
printf("\t\t1-----图书录入\t\t\t");
printf("2-----图书浏览\n\n");
printf("\t\t3-----图书查询\t\t\t");
printf("4-----修改删除图书\n\n");
printf("\t\t5-----借阅图书\t\t\t");
printf("6-----归还图书\n\n");
printf("\t\t7-----借阅查询\t\t\t\n");
printf("\n\t\t\t\t输入其他任意键退出\n");
printf("\n");
for(i=0;i<80;i++)
printf("#");
printf("\n\n");
}
void end()//录入图书
{ system("cls");
bo boo,booq;
printf("请输入图书名(最多十个字符)：");
scanf("%s",https://www.doczj.com/doc/326033452.html,);
do{
i=1;
printf("请输入图书编号(最多十个字符)：");
scanf("%s",boo.num);
fread(&booq,sizeof(bo),1,fp);
while(!feof(fp)){
if(strcmp(booq.num,boo.num)==0){
printf("\n该编号已存在请重新输入\n\n");
i=0;
break;
}
fread(&booq,sizeof(bo),1,fp);
}
rewind(fp);
}while(i==0);
printf("请输入图书作者(最多十个字符)：");
scanf("%s",boo.writer);
printf("请输入图书出版日期（例如2001年5月3日出版则输入20010503）：");
scanf("%d",&boo.date);
printf("请输入图书价格：");
scanf("%f",&boo.price);
printf("请输入图书出版社(最多十个字符)：");
scanf("%s",boo.press);
printf("请输入图书类别(最多十个字符)：");
scanf("%s",boo.leibie);
printf("请输入图书入库数：");
scanf("%d",&boo.kucun);
boo.jiechu=0;
getchar();
fseek(fp,0,2);
fwrite(&boo,sizeof(bo),1,fp);
printf("\n录入成功！回到主菜单");
system("pause");
}
void print()//浏览图书
{ system("cls");
bo boo;
printf("书名编号作者价格出版社类别
原始库存借出\n");
fread(&boo,sizeof(bo),1,fp);
while(feof(fp)==0){
printf("%-10s%-10s%-10s%-10.2f%-10s%-10s%-10d%-4d\n",https://www.doczj.com/doc/326033452.html,,boo .num,boo.writer,boo.price,boo.press,boo.leibie,boo.kucun,boo.jiechu);
fread(&boo,sizeof(bo),1,fp);
}
printf("\n浏览图书完毕！回到主菜单");
算法分析与设计 查找迷宫的最短路径(深度算法) 计算机科学与技术12级 16班 2012/12/16
【摘要】：迷宫求解是一个古老的游戏，要在迷宫中找到出口，需要经过一连串的错误尝试才能找到正确的路径，有的时候甚至找不到路径。类似于给定一个m*n的矩形网格，设其左上角为起点S。一辆汽车从起点出发驶向右下角终点T。在若干网格处设置了障碍，表示该网格不可到达。设计一个算法，求汽车从起点S出发到达终点T的一条路线。用计算机求解这个问题时，我们通常采用的是回溯方法，即从入口出发，顺某方向向前探索，若能走通，则继续往前走；否则沿原路退回。换一个方向再继续探索，直至所有可能的通路都探索到为止。为了保证在任何位置上都能沿原路退回，显然需要用一个后进先出的结构来保存从入口到当前位置的路径。因此，在求迷宫通路的算法中应用“栈”也就是自然而然的事。当然还有其他的方法来解决，例如顺序表，深度优先遍历，广度优先遍历等。 【关键词】:最短路径; 时间复杂度;深度优先搜索 【Summary】Maze solving is an ancient game , you want to find the exit in the maze , need to go through a series of trial and error to find the right path , and sometimes not even find the path . A m * n rectangular grid , similar to a given set its upper-left corner as the starting point S . A car from the starting point towards the bottom right corner of the end of T . Set up barriers at certain grid , indicates that the grid is unreachable . Design an algorithm , find the car starting to reach the end point T, route from the starting point S . Use the computer to solve this problem , we usually use the backtracking method , that is, starting from the entrance , Shun forward to explore a direction , if we go through , and continue to move forward ; otherwise return along the same route . Continue to explore another direction , until all possible paths to explore to far . In order to ensure that in any position along the same route back , it is clear that the need to use a LIFO structure to save the path from the entrance to the current position . Therefore , in seeking labyrinth path algorithm application "stack" is the natural thing to do . Of course , there are other ways to solve , for example, the sequence table , depth-first traversal , breadth -first traversal . 【Key phrase】Shortest path ; time complexity ; deep-first search
实验报告 课程名称数据结构 实验名称迷宫最短路径 实验类型综合型 实验地点计405机房 实验日期2017.5.13 指导教师魏海平 专业软件工程 班级软件1601 学号1611030102 姓名寇春雷 辽宁石油化工大学计算机与通信工程学院
数据结构实验报告评分表
实验二迷宫最短路径 题目：迷宫最短路径 ⒈问题描述 从一个迷宫的入口到出口找出一条最短路经。用一个二维数组MAZE(1..m，1..n)模拟迷宫，数组元素为0表示该位置可以通过，数组元素为1表示该位置不可以通行。MAZE(1，1)和MAZE(m，n)分别为迷宫的入口和出口。 ⒉基本要求 (1)输入数据 a.输入迷宫的大小m行和n列，两者为整数 b.由随机数产生0或1，建立迷宫。 (2)输出数据 首先输出模拟迷宫的二维数组，若存在最短路经，则由出口回朔到入口打印这一条路径，如下所示：(m，n)，……，(i，j)，……，(1，1) 如无通道，则打印： THERE IS NO PATH. ⒊实现提示 (1)数据结构 ①为了在程序中判断方便，把迷宫扩展成为MAZE(0..m+1，0..n+1)，扩展部分的元素 设置为1，相当于在迷宫周围布上一圈不准通过的墙，这样，在迷宫的任一位置(I，j)上都有八个可以移动的方向。 ②用二维数组MOVE(1..8，1..2)存放八个方向上的位置量，如图所示： (i+MOVE[1，1]，j+MOVE[1，2]) ，2]) ，2]) ，2])
③为了标志已经通过的位置，采用一个标志数组MARK（1..m，1..n）初值为0，在寻 找路径的过程中，若通过了位置（i，j），则将MARK（i，j）置为为1。 ④为了记录查找过程中到达位置及其前一位置，建立一个Q（1..m*n-1，0..2）数组， 对于某一个数组元素Q(P)，其中，Q(P，0)和Q(P，1)记下到达位置i和j，Q(P，2)记下其出发点在Q数组中的下标。 （2）算法基本思想 将入口（1，1）作为第一个出发点，依次在八个反方向上搜索可通行的位置，形成第一层新的出发点，然后对第一层中各个位置分别搜索他所在八个方向上的可通行位置，形成第二层新的出发点，…，如此进行下去，直至达到出口(m，n)或者迷宫所有位置都搜索完毕为止。 具体实施：从(m，n)开始，将其记入Q数组，比如记入Q(1)，以它作为第一个出发点，依次对八个方向进行搜索，若下一个位置(I，j)可通行并且尚未经过（即MAZE(i，j)=0 且MARK(i，j)=0），则记入Q数组，如记在Q(P)，则在Q(P，2)中要记下其出发点在Q数组中的下标1，在八个方向上都搜索过以后，根据先进先出的原则Q从数组中重新取出一个位置作为新的出发点（这里，我们实际上把Q数组作为一个顺序表示的队列），重复以上过程，若能达到位置(m ，n)，表示找到最短路径；若Q数组中已经没有位置可以作为新的出发点了，则表示迷宫没有通路。 4.需求分析 (1)以二维数组maze[M+2][N+2]表示迷宫，其中maze[i][0]和maze[i][N+1](0= 中国计量学院实验报告 实验课程：算法与数据结构实验名称：迷宫的最优路径班级：学号： 姓名：实验日期：2013-5-20 一．实验题目： 输入一迷宫 查找并输出迷宫的最优路径 实验成绩：指导教师： 二．算法说明 1.定义一个结构体来表示起点和末点的坐标,定义一个数组来存放迷宫. struct elem { int x;//行 int y;//列 }; //定义结构体 int M[10][10]; 2.给数组中空白处赋上从起点到该处步骤的值. int find(int n) { for(i=0;i<9;i++) for(j=0;j<10;j++) { if(M[i][j]==n) { {if (M[i][j+1]==0) M[i][j+1]=n+1; else if(M[i][j+1]>n+1) M[i][j+1]=n+1;} {if (M[i+1][j]==0) M[i+1][j]=n+1; else if(M[i+1][j]>n+1) M[i+1][j]=n+1;} {if (M[i][j-1]==0) M[i][j-1]=n+1; else if(M[i][j-1]>n+1) M[i][j-1]=n+1;} {if (M[i-1][j]==0) M[i-1][j]=n+1; else if(M[i-1][j]>n+1) M[i-1][j]=n+1;} } } } 3.给最优路径附上特定的值,方便最后的输出. for (;;) { if(M[q.x+1][q.y]==(n-1)) {q.x++;M[q.x][q.y]=0;} else {if(M[q.x][q.y-1]==(n-1)) {q.y--;M[q.x][q.y]=0;} else {if(M[q.x-1][q.y]==(n-1)) {q.x--;M[q.x][q.y]=0;} else if(M[q.x][q.y+1]==(n-1)) {q.y++;M[q.x][q.y]=0;}}} n--; if(e.x==q.x&&e.y==q.y) {M[e.x][e.y]=0; break;} } 计算机科学与技术专业《数据结构与算法》 课程设计报告 设计题目：迷宫路径求解专业： 学号： 姓名： 指导老师： 完成日期： 一、需求分析 迷宫路径求解：利用二维数组创建一个迷宫。编写一个算法能够完成输出走出迷宫的所有的路径。 二、设计概要 maze[9][11]={ {1,1,1,1,1,1,1,1,1,1,1}, {1,0,1,1,1,1,1,0,0,0,1}, {1,0,0,0,0,1,0,0,1,0,1}, {1,0,1,1,0,1,0,1,1,0,1}, {1,0,0,1,0,0,0,1,0,0,1}, {1,1,0,1,1,1,0,1,0,1,1}, {1,1,0,1,1,1,0,1,0,1,1}, {1,1,0,0,0,0,0,0,0,0,1}, {1,1,1,1,1,1,1,1,1,1,1} }; 一个迷宫用m*n的二维数组存储，用“0”代表可以通行，用“1”代表墙壁，不可通行。迷宫有一个路口和一个出口，设入口坐标为（x1，y1），出口坐标（x2，y2）。从迷宫的一个位置向东、南、西、北任意一个方向移动一步，前面若为“0”，则可前进一步，否则通行受阻，不能前进，则按顺时针改变为下一个方向。用一个switch语句控制方向的选择, 如： switch(d) {case 0:i=stack[s].i-1;j=stack[s].j;break; /*向西*/ case 1:i=stack[s].i;j=stack[s].j+1;break; /*向南*/ case 2:i=stack[s].i+1;j=stack[s].j;break; /*向东*/ case 3:i=stack[s].i;j=stack[s].j-1;break; /*向北*/ } 在走的同时需要用一个与迷宫同样大小的二维数组mark来存储走过的路径。避免重走已经走不通的老路。 为了寻找从入口点到出口点的一条通路，首先从入口点出发，按照四个方向的次序，当可以向前移动一步时，就把当前的的坐标入栈，若从当前位置无法继续前进时就做出栈操作，从上一次的位置的下一个方向，向前试探前进。如果当前位置为出口时，则表明找到一条路径从入口到出口的路径，打印出路径。若做出栈时为空，且当前位置不是出口，则表明没有找到一条可以出去的路径。结束程序。 三、详细设计 1.数据类型的定义； struct BinTreeNode { int i; int j; int d; #include void PutOut_all(); //找所有路径和最短路径并输出所有路径 void PutOut_Grap(); //输出迷宫图形 void Migong(); //使用迷宫 void main() { cout<<"*******************欢迎使用迷宫系统 *******************\n"; while(1) { int i; cout<<"请选择你要的操作：\n" <<"1.使用系统自带迷宫\n" <<"2.使用新建迷宫\n" <<"0.退出\n"; cout<<"请输入："; cin>>i; switch(i) { case 1: Init_maze();Migong();break; case 2: NewCreat();Migong();break; case 0: return; 求迷宫中从入口到出口的 路径的算法及实现 涂海丽东华理工大学３４４０００ １．本次设计所用到的库函数有：输入输出函数（ｓｔｄｉｏ．ｈ）过程调用函数（ｐｒｏｃｅｓｓ．ｈ）动态存储分配函数（ｍａｌｌｏｃ．ｈ）。 ２．本程序的设计过程分三大块：主程序（ｍａｉｎ（））试探函数（ｓｅａｒｃｈ（））数据子文件（ｉｎｐｕｔ．ｃ）。主要过程就是：通过主程序调用数据文件，然后用一维数组来模拟二维数组进行动态存储，再从第一个入口开始，调用试探函数探测通路，把探测到的通路入栈，进入下一层调用。直到找出所有的通路，最后打印输出。 ｆｏｒ（ｉ＝－１ｉ＜＝１＋＋ｉ）／／在当前点的８各方向进行探测 ｆｏｒ（ｊ＝－１ｊ＜＝１＋＋ｊ）｛ｉｈ＝ｉ０＋ｉｊｈ＝ｊ０＋ｊｉｆ（（ｉ！＝０｜｜ｊ！＝０）ｉｈ＞＝０ｉｈ＜ｒｏｗ＆ｊｈ＞＝０ｊｈ＜ｃｏｌｔａｂ［ｉｈ］［ｊｈ］＝＝０） ｛／／判断条件ｉｅ１［ｉｒ］＝ｉｈ／／当前点入栈，进入下一层调用 ｉｅ２［ｉｒ］＝ｊｈｔａｂ［ｉｈ］［ｊｈ］＝１ｓｅａｒｃｈ（ｒｏｗ，ｃｏｌ，ｔａｂ，ｉｈ，ｊｈ，ｉｒ＋１，ｉｅ１，ｉｅ２，ｎｏ）ｔａｂ［ｉ ｈ］［ｊｈ］＝０｝｝｝ｍａｉｎ（）｛ＦＩＬＥ＊ｆｐｉｎｔｒｏｗ，ｃｏｌ，＊ｔａｂ１，＊＊ｔａｂ２，＊ｉｅ１，＊ｉｅ２，ｉｒ，ｎｏ，ｉ０，ｊ０，ｉ，ｊｉｆ（（ｆｐ＝ｆｏｐｅｎ（＂ｉｎｐｕｔ．ｃ＂，＂ｒ＂））＝＝ＮＵＬＬ）／／打开数据文件 ｛ｐｒｉｎｔｆ（＂ＴｈｅｏｐｅｎＥｒｒｏｒ！＂）ｅｘｉｔ（０）｝ｆｓｃａｎｆ（ｆｐ，＂％ｄ％ｄ＂，ｒｏｗ，ｃｏｌ）／／读入迷宫的矩阵行和列大小 ｔａｂ１＝（ｉｎｔ＊）ｍａｌｌｏｃ（（ｕｎｓｉｇｎｅｄ）ｃｏｌ＊ｒｏｗ＊ｓｉｚｅｏｆ（ｉｎｔ））／／申请动态存储区 ｔａｂ２＝（ｉｎｔ＊＊）ｍａｌｌｏｃ（（ｕｎｓｉｇｎｅｄ）ｒｏｗ＊ｓｉｚｅｏｆ（ｉｎｔ＊））／／ｔａｂ１一维数组来模拟ｔａｂ２二维 数组ｉｅ１＝（ｉｎｔ＊）ｍａｌｌｏｃ（（ｕｎｓｉｇｎｅｄ）ｃｏｌ＊ｓｉｚｅｏｆ（ｉｎｔ））ｉｅ２＝（ｉｎｔ＊）ｍａｌｌｏｃ（（ｕｎｓｉｇｎｅｄ）ｃｏｌ＊ｓｉｚｅｏｆ（ｉｎｔ））ｆｏｒ（ｉ＝０ｉ＜ｒｏｗ；ｉ＋＋）ｔａｂ２［ｉ］＝（ｔａｂ１［ｉ＊ｃｏｌ］）ｉ０＝０ｊ０＝０／／从入口（１，１）开始ｆｏｒ（ｉ＝０ｉ＜ｒｏｗ；＋＋ｉ）ｆｏｒ（ｊ＝０ｊ＜ｃｏｌ＋＋ｊ）ｆｓｃａｎｆ（ｆｐ，＂％ｄ＂，（ｔａｂ２［ｉ］［ｊ］））／／读入矩阵的内容 ｆｃｌｏｓｅ（ｆｐ）／／存入到ｔａｂ１中 三详细设计程序 ＃ｉｎｃｌｕｄｅ＜ｍａｌｌｏｃ．ｈ＞ ＃ｉｎｃｌｕｄｅ＜ｓｔｄｉｏ．ｈ＞＃ｉｎｃｌｕｄｅ＜ｐｒｏｃｅｓｓ．ｈ＞ｖｏｉｄｓｅａｒｃｈ（ｉｎｔｒｏｗ，ｉｎｔｃｏｌ，ｉｎｔ＊＊ｔａｂ，ｉｎｔｉ０，ｉｎｔｊ０，ｉｎｔｉｒ，ｉｎｔ＊ｉｅ１，ｉｎｔ＊ｉｅ２，ｉｎｔ＊ｎｏ）／／试探函数 ｛ｉｎｔｉ，ｊｈ，ｉｈ，ｊ，ｃｏｕｎｔｉｆ（ｉ０＝＝ｒｏｗ－１ｊ０＝＝ｃｏｌ－１）／／若能到达出口 ｛＋＋（＊ｎｏ）／／方法数加１ ｐｒｉｎｔｆ（＂＃－－－－－－－－－－－－－－－－Ｔｈｅ￣￣￣￣［％ｄ］ｔｈ￣￣￣￣￣Ｓｏｌｕｔｉｏｎ－－－－－－－－－－－－－－－－－－－－＃＼ｎ＂，＊ｎｏ）／／打印该种路径的出现顺序 ｐｒｉｎｔｆ（＂（％ｄ，％ｄ）＂，１，１）／／从入口开始打印 ｃｏｕｎｔ＝０／／输出换行计数 C语言课程设计报告题目：迷宫问题 姓名： 班级： 学号： 组员： 指导教师： 学院： 专业： 课程设计（报告）任务及评语 目录 第1章课程设计的目的与要求 (1) 1.1 课程设计目的 (1) 1.2 课程设计的实验环境 (1) 1.3 课程设计的预备知识 (1) 1.4 课程设计要求 (1) 第2章课程设计内容 (2) 2.1程序功能介绍 (2) 2.2程序整体设计说明 (2) 2.2.1设计思路 (2) 2.2.2数据结构设计及用法说明 (3) 2.2.3程序结构（流程图） (4) 2.2.4各模块的功能及程序说明 (6) 2.2.5程序结果 (7) 2.3程序源代码及注释 (7) 第3章课程设计总结 (17) 参考资料 (18) 第1章课程设计的目的与要求 1.1 课程设计目的 本课程设计是计算机科学与技术专业重要的实践性环节之一，是在学生学习完《程序设计语言(C)》课程后进行的一次全面的综合练习。本课程设计的目的和任务： 1. 巩固和加深学生对C语言课程的基本知识的理解和掌握 2. 掌握C语言编程和程序调试的基本技能 3. 利用C语言进行基本的软件设计 4. 掌握书写程序设计说明文档的能力 5. 提高运用C语言解决实际问题的能力 1.2 课程设计的实验环境 硬件要求能运行Windows 2000/XP操作系统的微机系统。C语言程序设计及相应的开发环境。 1.3 课程设计的预备知识 熟悉C语言及C语言开发工具。 1.4 课程设计要求 1. 分析课程设计题目的要求 2. 写出详细设计说明 3. 编写程序代码，调试程序使其能正确运行 4. 设计完成的软件要便于操作和使用 5. 设计完成后提交课程设计报告 最短路径及其他路径 #include void PutOut_Grap(); //输出迷宫图形 void Migong(); //使用迷宫 void main() { cout<<"*******************欢迎使用迷宫系统*******************\n"; while(1) { int i; cout<<"请选择你要的操作：\n" <<"1.使用系统自带迷宫\n" <<"2.使用新建迷宫\n" <<"0.退出\n"; cout<<"请输入："; cin>>i; switch(i) { case 1: Init_maze();Migong();break; case 2: NewCreat();Migong();break; case 0: return; default :cout<<"*****输入错误，请重新输入！*****\n";break; } } 迷宫最短路径问题新算法 摘要: 提出了求解迷宫最短路径问题的新算法, 该算法抛弃了 经典算法( 深度优先搜索和广度优先搜索) 中繁杂低效的递归、回溯思想。通过合理的变换, 将原问题转化为迷宫路径深度图的生成问题。最后对算法进行了严谨的分析和实例测 试, 显示出该算法易于理解、易于编程、时间空间复杂度低等优点。 关键词: 最短路径; 时间复杂度; 深度优先搜索; 广度优先搜索 New Algorithm for Solving Shortest Path of Maze Problem ZHANG Lin- feng, LV Hui, QU Jun- feng (The Missile Institute, Air Force Engineering University, Sanyuan, Shannxi 713800, China) Abstract: A new algorithm is presented for solving the shortest path of maze problem, which is not based on the inef- ficient recursive backtracking theory of classical algorithm (DFS- Depth First Search and BFS- Breadth First Search).By appropriate conversion, the algorithm changes the original problem into the creation of the maze graph problem.At last, an example is given, which shows that the new algorithm is easy to be understood and programmed as well as its low time and space complexity. Key words: shortest path; time complexity; Depth First Search; Breadth First Search 1 问题描述 迷宫最短路径(the shortest path of maze) 问题是一个典 型的搜索、遍历问题, 其程序设计思想在人工智能设计、机器人 设计等事务中均有应用。 如图 1 所示, 一个 N×M的大方块迷宫, 带斜线的单元格表 求迷宫问题就是求出从入口到出口的路径。在求解时, 通常用的是“穷举求解”的方法,即从入口出发,顺某一方向向前试探,若能走通, 则继续往前走；否则沿原路退回,换一个方向再继续试探, 直至所有可能的通路都试探完为止。为了保证在任何位置上都能沿原路退回（称为回溯）, 需要用一个后进先出的栈来保存从入口到当前位置的路径。 首先用如图3.3 所示的方块图表示迷宫。对于图中的每个方块,用空白表示通道,用阴影表示墙。所求路径必须是简单路径, 即在求得的路径上不能重复出现同一通道块。 为了表示迷宫, 设置一个数组mg,其中每个元素表示一个方块的状态, 为0 时表示对应方块是通道, 为1 时表示对应方块为墙, 如图3.3 所示的迷宫, 对应的迷宫数组mg如下: int mg[M+1][N+1]={ /*M=10,N=10*/ {1,1,1,1,1,1,1,1,1,1}, {1,0,0,1,0,0,0,1,0,1}, {1,0,0,1,0,0,0,1,0,1}, {1,0,0,0,0,1,1,0,0,1}, {1,0,1,1,1,0,0,0,0,1}, {1,0,0,0,1,0,0,0,0,1}, {1,0,1,0,0,0,1,0,0,1}, {1,0,1,1,1,0,1,1,0,1}, {1,1,0,0,0,0,0,0,0,1}, {1,1,1,1,1,1,1,1,1,1} }; 伪代码： c 语言描述如下： void mgpath() /* 路径为:(1,1)->(M-2,N-2)*/ { int i,j,di,find,k; top++; /* 初始方块进栈*/ Stack[top].i=1; Stack[top].j=1; Stack[top].di=-1; mg[1][1]=-1; while (top>-1) /* 栈不空时循环*/ { i=Stack[top].i; j=Stack[top].j; di=Stack[top].di; if (i==M-2 && j==N-2) /* 找到了出口, 输出路径*/ { printf(" 迷宫路径如下:\n"); for (k=0;k<=top;k++) { printf("\t(%d,%d)",Stack[k].i,Stack[k] .j); if ((k+1)%5==0) printf("\n"); } 算法分析与设计 查找迷宫的最短路径(广度算法) 计算机科学与技术12级 16班 2012/12/16 【摘要】本论文提出了求解迷宫最短路径问题的经典广度优先搜索。通过合理的变换, 将原问题转化为迷宫路径深度图的生成问题。最后对算法进行了严谨的分析和实例测试。迷宫求解是一个古老的游戏，要在迷宫中找到出口，需要经过一连串的错误尝试才能找到正确的路径，有的时候甚至找不到路径。类似于给定一个m*n的矩形网格，设其左上角为起点S。一辆汽车从起点出发驶向右下角终点T。在若干网格处设置了障碍，表示该网格不可到达。设计一个算法，求汽车从起点S出发到达终点T的一条路线。用计算机求解这个问题时，我们通常采用的是回溯方法，即从入口出发，顺某方向向前探索，若能走通，则继续往前走；否则沿原路退回。换一个方向再继续探索，直至所有可能的通路都探索到为止。为了保证在任何位置上都能沿原路退回，显然需要用一个后进先出的结构来保存从入口到当前位置的路径。因此，在求迷宫通路的算法中应用“栈”也就是自然而然的事。当然还有其他的方法来解决，例如顺序表，深度优先遍历，广度优先遍历等。 【关键词】:最短路径; 时间复杂度;广度优先搜索 【Summary】Maze solving is an ancient game , you want to find the exit in the maze , need to go through a series of trial and error to find the right path , and sometimes not even find the path . A m * n rectangular grid , similar to a given set its upper-left corner as the starting point S . A car from the starting point towards the bottom right corner of the end of T . Set up barriers at certain grid , indicates that the grid is unreachable . Design an algorithm , find the car starting to reach the end point T, route from the starting point S . Use the computer to solve this problem , we usually use the backtracking method , that is, starting from the entrance , Shun forward to explore a direction , if we go through , and continue to move forward ; otherwise return along the same route . Continue to explore another direction , until all possible paths to explore to far . In order to ensure that in any position along the same route back , it is clear that the need to use a LIFO structure to save the path from the entrance to the current position . Therefore , in seeking labyrinth path algorithm application "stack" is the natural thing to do . Of course , there are other ways to solve , for example, the sequence table , depth-first traversal , breadth -first traversal . 【Key phrase】Shortest path ; time complexity ; breadth-first search 设计题目:迷宫问题求解 问题描述 迷宫问题是取自心理学的一个古典实验。在该实验中，把一只老鼠从一个无顶大盒子的门放入，在盒子中设置了许多墙，对行进方向形成了多处阻挡。盒子仅有一个出口，在出口处放置一块奶酪，吸引老鼠在迷宫中寻找道路以到达出口。对同一只老鼠重复进行上述实验，一直到老鼠从入口走到出口，而不走错一步。老鼠经过多次试验最终学会走通迷宫的路线。设计一个计算机程序对任意设定的矩形迷宫如下图A所示，求出一条从入口到出口的通路，或得出没有通路的结论。图A ●任务： ●功能要求： (1) 建立一个大小为m×n的任意迷宫（迷宫数据可由用户输入或由程序自动生成），并在 屏幕上显示出来； （2）找出一条通路的二元组（i,j）数据序列，（i,j）表示通路上某一点的坐标。 （3）用一种标志（如数字8）在迷宫中标出该条通路； （4）在屏幕上输出迷宫和通路； （5）上述功能可用菜单选择。 需求分析： 1.迷宫的建立： 迷宫中存在通路和障碍，为了方便迷宫的创建，可用0表示通路，用1表示障碍，这样迷宫就可以用0、1矩阵来描述， 2.迷宫的存储： 迷宫是一个矩形区域，可以使用二维数组表示迷宫，这样迷宫的每一个位置都可以用其行列号来唯一指定，但是二维数组不能动态定义其大小，我们可以考虑先定义一个较大的二维数组maze[M+2][N+2],然后用它的前m行n列来存放元素，即可得到一个m×n的二维数组，这样(0,0)表示迷宫入口位置，(m-1,n-1)表示迷宫出口位置。 注：其中M，N分别表示迷宫最大行、列数，本程序M、N的缺省值为39、39，当然，用户也可根据需要，调整其大小。 3.迷宫路径的搜索： 首先从迷宫的入口开始，如果该位置就是迷宫出口，则已经找到了一条路径，搜索工作结束。否则搜索其上、下、左、右位置是否是障碍，若不是障碍，就移动到该位置，然后再从该位置开始搜索通往出口的路径；若是障碍就选择另一个相邻的位置，并从它开始搜索路径。为防止搜索重复出现，则将已搜索过的位置标记为2，同时保留搜索痕迹，在考虑进入下一个位置搜索之前，将当前位置保存在一个队列中，如果所有相邻的非障碍位置均被搜索过，且未找到通往出口的路径，则表明不存在从入口到出口的路径。这实现的是广度优先遍历的算法，如果找到路径，则为最短路径。 #include int pass(int maze[100][100],pos curpos) { if(maze[curpos.line][curpos.row]==0) return 1; else return 0; } void FootPrint( int maze[100][100],pos pos) { maze[pos.line][pos.row] = 1; } pos nextpos(int maze[100][100],SqStack curPos) { pos curpos=curPos.seat; switch(curPos.di) { case 1: ++curpos.line; break; case 2: ++curpos.row; break; case 3: --curpos.line; break; case 4: --curpos.row; break; } return curpos; } int MazePath(int maze[100][100],pos start,pos end) { pos curpos; SqStack e; top=0; curpos=start; e.di=1; e.seat=curpos; S[++top]=e; while(top!=0) { curpos=nextpos(maze,e); if(pass(maze,curpos)) 实验报告 课程名：数据结构（C语言版）实验名：迷宫问题II 姓名： 班级： 学号： 撰写时间：2014/10/10 一实验目的与要求 1. 了解栈的应用 2. 利用栈在迷宫中找到一条路 二实验内容 ?一个迷宫如图1所示, 是由若干个方格构成的一个矩形, 其中有唯一的 一个入口(用标示), 有唯一的一个出口(用△标示). 图中深色的方格无 法到达, 浅色的方格都是可以到达的. 每一次只能从当前方格前进到与当前方 格有公共边的方格中(因此前进方向最多有四个). ?本次实验的迷宫问题要求找到从入口到出口的最短的路. 图1：迷宫 三实验结果与分析 程序： #include int Qx[Znum+1], Qy[Znum+1], P[Znum+1], head=0, tail=0; for(i=0;i 数据结构课程设计指导 一、课程设计要求 课程设计是数据结构课程的一个综合实践练习，是有别于课程实验的一个独立实践教学环节。课程设计一般在课程结束后进行，教学时数为1周。具体要求如下： 1、结合实际问题进一步理解和深化课程理论知识，做到理论与实际相结合。 2、能对实际问题进行分析和抽象，并进行数据结构设计和算法设计，具有初步的分析问题和解决问题的能力。 3、了解软件工程的理论与方法，初步掌握软件开发过程中的需求分析、系统设计、编码、测试等基本方法和技能。 4、进一步强化编程训练，提高程序设计能力。 5、设计内容要有一定的深度和难度，达到一定工作量，代码量不低于500行。 二、课程设计内容 课程设计的主要工作如下： 1、问题定义与需求分析：根据设计题目的要求，对问题进行分析，确定系统的功能需求和性能需求。 2、数据结构与算法设计：对问题描述中涉及的数据对象定义相应的数据结构，包括逻辑结构、存储定义和主要操作。对主要算法要进行时间和空间复杂度分析。 3、概要设计：采用面向对象方法设计软件结构，定义类及类之间的关系。要求系统结构合理、易于实现。 4、详细设计：对数据结构和基本操作做进一步的求精，写出数据存储定义，用程序流程图或伪码对算法进行描述。 5、编码与测试：用C++编程实现系统，并设计测试用例对系统进行测试，修改程序中的错误，形成格式和风格良好的源程序清单。 6、设计结果分析：对系统应用效果进行分析，评价系统的先进性、实际应用价值及在在的问题。 7、撰写课程设计报告。 三、课程设计考核 课程设计考核内容包括设计作品和设计报告两个部分。设计作品包括可运行的源程序（刻录成光盘），系统使用说明，主要程序代码（打印附在课程报告内）。课程设计报告主要报告系统分析、设计和实现过程，内容如下： 1、问题定义及设计要求； 2、主要设计内容：详细报告课程设计中所做的主要工作，包括系统分析、概要设计、数据结构设计、算法设计及模块设计和编程及测试等。 3、总结与体会：写出本次课程设计的主要创新点及存在的问题。 4、参考文献：列出所参考的主要文献。 5、小组成员及分工。 课程设计成绩分两部分，设计报告占50％，设计作品占50％。评价因素主要有： 《数据结构与算法设计》 课程设计任务书 题目迷宫设计 学生姓名学号专业班级 设计内容与要求【问题描述】 在迷宫中求从入口到出口的一条简单路径。迷宫可用方块来表示，每个方块或者是通道或者是墙。“迷宫求解”这个经典的问题，应用栈这种数据结构设计一个方案，并在图形界面上实现从入口到出口的一条简单路径，设计这个游戏可以加强自己的编程能力，自己找通路时还可以加强观察能力。 【软件功能】 1、求解迷宫通路的图形界面演示程序，根据用户界面提示自定义迷宫。 2、根据用户界面提示，用键盘输入，Home键设置迷宫起点，End键设终点，上下左右箭头键移动，Enter键添加墙，Del键删除墙，完成后按F9键演示，演示完毕后可F5刷新题图，重新对地图的起点、终点、障碍进行设置，Esc 键退出； 3、在找迷宫通路的过程中，演示查找的过程并查找成功的一条路径。 4、用户可以通过界面上提供的菜单选项，选择“A*算法求最短路径”演示求解迷宫最短路径。 【算法思想】 1、以一个长方阵表示迷宫，采用数组对迷宫信息进行存储，数组的元素的值表示迷宫对应位置的内容。0表示迷宫对应位置可通过；1表示迷宫对应位置为墙；2表示迷宫对应位置为已经走过的足迹3，表示迷宫对应位置是从栈中弹出的点，并且不能再次通过；4表示迷宫对应位置为起点，保证起点不可通过。 2.在设计走迷宫算法的过程中，主要是利用栈对路径信息进行存储，类N ode，定义了栈中存储的节点元素的类型，栈中的元素采用链式存储的结构。 3、采用A*算法，找到起点到终点的最短路径； 4、采用回溯算法控制并绘制人物在迷宫图形界面窗口中的位置。 5、用java编程语言，有简单、美观的图形界面。 【提交成果】 1.“《数据结构与算法设计》课程设计任务书”一份，打印装袋； 2.“《数据结构与算法设计》课程设计报告”一份，打印装袋； 3、上面两项内容的word文档，通过电子邮件交到指导教师。 起止时间2012 年 6 月18日至2012 年7月 1 日指导教师签名2012年 6 月18 日系（教研室）主任签名2012年 6 月18 日学生签名 2012 年 6 月 18 日c语言实现迷宫最优路径选择
迷宫路径求解
迷宫-最短路径及所有路径的问题
求迷宫中从入口到出口的路径的算法及实现概要
C语言课程设计--迷宫
关于迷宫最短路径与所有路径的问题
迷宫最短路径问题新算法
求解迷宫问题(c语言,很详细哦)
算法分析与设计 查找迷宫的最短路径(广度算法)
迷宫求解-数据结构-课业设计
迷宫问题 输出路径
数据结构迷宫最短路径实验报告
数据结构课程设计指导书(2015)
迷宫算法设计
相关主题
文本预览