数据结构--迷宫问题求解.doc

Four short words sum up what has lifted most successful individuals above the crowd: a little bit more.-author-date数据结构-迷宫问题求解安徽大学学号 专业计算机科学与技术 姓名 实验日期 2017.6.20 教师签字 成绩实验报告【实验名称】迷宫问题的求解【实验目的】（1）通过本课程的学习，能熟练掌握几种基本数据结构的基本操作。 （2）能针对给定题目，选择相应的数据结构，分析并设计算法，进而给出问题的正确求解过程并编写代码实现。（3）用递归和非递归两种方式完成迷宫问题的求解。【实验原理】迷宫问题通常是用“穷举求解”方法解决，即从入口出发，顺着某一个方向进行探索，若能走通，则继续往前走；否则沿着原路退回，换一个方向继续探索，直至出口位置，求得一条通路。假如所有可能的通路都探索到而未能到达出口，则所设定的迷宫没有通路。栈是一个后进先出的结构，可以用来保存从入口到当前位置的路径。【实验内容】1 需求分析1.基本要求：（1）首先实现一个以链表作存储结构的栈类型，然后编写一个求解迷宫的非递归程序。求得的通路以三元组（i，j，d）的形式输出。其中：（i，j）指示迷宫中的一个坐标，d表示走到下一坐标的方向。如，对于教材第50页图3.4所示的迷宫，输出一条通路为：（1，1，1），（1，2，2），（2，2，2），（3，2，3），（3，1，2），（2）编写递归形式的算法，求得迷宫中所有可能的通路。（3）以方阵形式输出迷宫及其通路。 （4）按照题意要求独立进行设计，设计结束后按要求写出设计报告。 2.输入输出的要求： (i) 求得的通路以三元组（i，j，d）的形式输出，其中：（i，j）指示迷宫中的一个坐标，d表示走到下一个坐标的方向。 （ii）输出迷宫示意图 3.程序所能达到的功能： (i) 实现一个以链表作存储结构的栈类型，以非递归算法求出通路(ii)以一个递归算法，对任意输入的迷宫矩阵求出所有通路。2 概要设计1.构建一个二维数组mazeMN用于存储迷宫矩阵手动生成迷宫，即为二维数组mazeMN赋值构建一个栈用于存储迷宫路径 建立迷宫节点用于存储迷宫中每个节点的访问情况；非递归 本程序包含6个函数： (1)主函数 main() (2)生成迷宫 create_maze() (4)打印迷宫 print_maze() (5)搜索迷宫路径并用三元组输出路径 mgpath()(6)用图来输出路径print_tu(); 递归本程序包含3个函数： （1）主函数main(); （2）打印迷宫printmaze()； （3）搜索迷宫路径pass(int x,int y)；3. 详细设计1.非递归起点和终点的结构类型 typedef struct int h; int l;T;栈节点类型 typedef struct cell int row; int col;int dir;TCell; 1.生成迷宫void creat_maze(int a,int b)定义i,j为循环变量 for(i<a) for(j<b) 输入mazeij的值2.打印迷宫void print_maze(int m,int n) 用i,j循环变量，将mazeij输出3.搜索迷宫路径void mazepath(int maze,T s,T e) /参数传递迷宫和起点与终点 TCell SN1*N2; top=0; /建立栈 Stop.row=s.h; Stop.col=s.l; Stop.dir=-1; /起点入栈 while(top>=0) /判栈是否空 i,j为当前访问点的位置 if(i,j是终点坐标) 用循环输出栈里的元素； else 将(i,j),即访问点入栈，然后向四周寻找是否有通路，若有通路，将原访问点标记（赋值-1），选一条通路作为新访问点，入栈。 若没有通路，回溯，将栈顶元素出栈作为访问点，继续寻找通路。4.生成路线图Print_tu()i,j为循环变量for(i<a)for(j<b)if(mazeij=1);print（“#”） / # 表示墙else if(mazeij=0)print（“ ”）else print(“+”) / + 表示路径2.递归void printmaze() 用i,j循环变量，将mazeij输出void pass(int x,int y) 将访问点标记mazexy=-1； if(x,y是终点坐标) 调用printmaze()输出栈里的元素； if(x,y的左边是通路)递归调用pass（x,y-1）；if(x,y的右边是通路)递归调用pass（x,y+1）；if(x,y的上边是通路)递归调用pass（x-1,y）；if(x,y的下边是通路)递归调用pass（x+1,y）；4. 测试与分析【小结或讨论】这次的项目，加强了我动手、思考和解决问题的能力。巩固和加深了对数据结构的理解，提高综合运用本课程所学知识的能力培养了我查阅参考书，查阅手册及文献资料的能力。培养独立思考，深入研究，分析问题、解决问题的能力。通过实际编译系统的分析设计、编程调试，掌握应用软件的分析方法和工程设计方法。附页 源程序非递归#include<stdio.h>#include<stdlib.h>#define N1 10#define N2 10int mazeN1N2; /迷宫数组typedef struct /起点终点坐标int h;int l;T;typedef struct cellint row;int col;int dir;TCell; /栈的元素结构TCell SN1*N2; /栈void creat_maze(int a,int b) /建立迷宫int i,j;for(i=0;i<a;i+)for(j=0;j<b;j+)scanf("%d",&mazeij);void print_maze(int a,int b) /打印迷宫int i,j;for(i=0;i<a;i+)for(j=0;j<b;j+)printf(" %d",mazeij);printf("n");void print_tu(int a,int b) /打印迷宫路径图int i,j;for(i=0;i<a;i+)for(j=0;j<a;j+)if(mazeij=1)printf("#");else if(mazeij=0)printf(" ");elseprintf("+");printf("n");void mazepath(int mazeN1N2,T s,T e) /搜索路径int top=0;int i,j,k,find,di;Stop.row=s.h;Stop.col=s.l;Stop.dir=-1;mazes.hs.l=-1;while(top>=0)i=Stop.row;j=Stop.col;di=Stop.dir;if(i=e.h&&j=e.l)printf("输出迷宫路径三元组：n");for(k=0;k<=top;k+)printf(" %d %d %dn",Sk.row,Sk.col,Sk.dir);return;find=0;while(find=0&&di<4)di+;switch(di)case 0:i=Stop.row-1;j=Stop.col;break;case 1:i=Stop.row;j=Stop.col+1;break;case 2:i=Stop.row+1;j=Stop.col;break;case 3:i=Stop.row;j=Stop.col-1;break;if(mazeij=0) find=1;if(find=1)Stop.dir=di;top+;Stop.row=i;Stop.col=j;mazeij=-1;elsemazeStop.rowStop.col=0;top-;printf("没有路径n");int main() /主函数int a,b;T s,e;printf("输入迷宫的行数与列数：n");scanf("%d,%d",&a,&b);printf("输入迷宫数据:n");creat_maze(a,b);printf("输出迷宫：n");print_maze(a,b);printf("输入起点与终点：n");scanf("%d,%d",&s.h,&s.l);scanf("%d,%d",&e.h,&e.l);mazepath(maze,s,e);printf("输出迷宫图和路线:n");print_tu(a,b);递归#include<stdio.h>#include<stdlib.h>int maze99=1,1,1,1,1,1,1,1,1,1,0,0,0,0,0,0,0,1,1,0,1,1,0,1,1,0,1,1,0,1,0,0,1,0,0,1,1,0,1,0,1,0,1,0,1,1,0,0,0,0,0,1,0,1,1,1,0,1,1,0,1,1,1,1,0,0,0,0,0,0,0,1,1,1,1,1,1,1,1,1,1;void printmaze()int i,j;for(i=0;i<9;i+)for(j=0;j<9;j+)if(mazeij=1)printf("#");else if(mazeij=-1)printf("+");else printf(" ");printf("n");void pass(int x,int y)mazexy=-1;if(x=7&&y=7)printf("输出路径n");printmaze(); if(mazexy+1=0)pass(x,y+1);if(mazex+1y=0)pass(x+1,y);if(mazex-1y=0)pass(x-1,y);if(mazexy-1=0)pass(x,y-1);mazexy=0;int main()int inx=1,iny=1;printf("迷宫图是：n");printmaze();pass(inx,iny);-