数据结构集中上机实验报告.doc

XX大学信息与计算科学专业2008级数据结构集中上机设计题目： 迷宫求解（非递归求解） 设计时间： 2010-2011学年第一学期姓名班级学号成绩目录一、实验内容2二、需求分析2三、总体设计2（一）存储结构2（二）流程图3四、详细设计3（一）基本算法解析3（二）为实现算法，需要的象的数据类型4(三)函数的调用关系5（四）算法时间、空间复杂度5五、代码5六、运行结果分析10（一）迷宫路径探索成功10（二）迷宫路径未找到的情况13（三）程序的优缺点与改进13七、参考文献14八、心得体会14一、实验内容任务：可以输入一个任意大小的迷宫数据，用非递归的方法求出一条走出迷宫的路径，并将路径输出。二、需求分析1、可以输入一个任意大小的迷宫数据，用非递归的方法求出一条走出迷宫的路径，并将路径输出；要求使用非递归算法。2、用户可以根据自己的需求进行输入所需的迷宫，其中1表示迷宫的墙壁，0表示迷宫的通路，从而建立迷宫。3、可以自行输入迷宫的入口和出口坐标。4、程序执行的命令包括：（1）构造栈函数。其中包括了构造空栈InitStack；压入新数据元素Push；栈顶元素出栈Pop。（2）构造求迷宫路径函数。其中定义了二维数组mazeMN存取迷宫数据；输出找到的通路MazePath。（3）建立一个迷宫initmaze。其中包括输入迷宫行数列数以及各行各列；加一圈围墙并输出迷宫。三、总体设计（一）存储结构：首先用二维数组存储迷宫数据，迷宫数据由用户输入。一个以链表结构作存储结构的栈类型，然后编写一个求解迷宫的非递归程序。求得的通路以三元组（i,j,d）形式输出，其中（i,j）指示迷宫中的一个坐标，d表示走到下一坐标的方向（东南西北所用代表数字，自行定义）。1 从入口出发，顺着某一个方向进行探索，若能走通，继续往前走，否则沿原路退回，换 一个方向继续探索，直至出口位置，求得一条通路。假如所有可能的通路都探索到但没能到达出口，则所设置的迷宫没有通路。迷宫的入口点的下标（a,b），出口点的下标（m,n）。为方便，可在迷宫周围加一周障碍。对于迷宫的任意位置，均可约定有东西南北4个方向可以走通。经过的位置把0变成-1，输出迷宫路径。2本程序有三个模块;（1） 主程序模块（2） 三个模块即其对象，实现栈链表抽象数据类型（3） 迷宫存储迷宫，寻路径，输出迷宫。（二）流程图存取迷宫mazeMN输入迷宫的行和列的内容求取一条路径MazePath迷宫无路径显示结果while(S1)Pop(S1,e);Push(S2,e); while(S2) Pop(S2,e); printf(-(%d,%d,%d),e.x,e.y,e.d)END函数Push,Pop调用函数MazePath，Push,Pop调用if(a=end.x&b=end.y&mazeab=0)Push(S1,elem);四、详细设计（一）基本算法解析：首先用二维数组存储迷宫数据，迷宫数据由用户输入。一个以链表结构作存储结构的栈类型，然后编写一个求解迷宫的非递归程序。求得的通路以三元组（i,j,d）形式输出，其中（i,j）指示迷宫中的一个坐标，d表示走到下一坐标的方向（东南西北所用代表数字，自行定义）。迷宫的过程可以模拟成一个搜索的过程。每到一处，总让它按东西南北四个方向顺序试探下一个位置，如果某方向可以通过，并且不曾到达，则前进一步，在新的位置上继续进行探索。如果4个方向都走不通或者曾经到达过，则退回一步，在原来的位置上继续试探下一位置。 每前进一步或后退一步，都要进行判断，若前进到了出口处，则说明找到了一条通路，若退回到了入口处，则说明不存在通路。用一个二维指针数组迷宫表示迷宫，数组中每个元素取值“0”（表示通路）或“1”（表示墙壁）。迷宫的入口点在位置（a,b）处，出口点在位置（m,n）处。设计一个模拟走迷宫的算法，为期寻找一条从入口点到出口点的通路。二维数组的0行m+1列元素全置成“1”，表示迷宫的外墙，第一行第一列元素和第m行m列元素置成“0”，表示迷宫的入口和出口。 假设当前所在位置是（x,y）。延某个方向前进一步，它可能到达的位置最多有4。如果用结构体Element elem记录4方向上行下标增量和列下标增量，则沿第i个方向前进一步，可能到达的新位置坐标可利用结构体Element elem确定while(!StackEmpty(S1) /栈不为空 有路径可走 Pop(S1,elem); i=elem.x; j=elem.y; d=elem.d+1; 从迷宫的入口位置开始，沿图示方向顺序依次进行搜索。定义一个栈，按从入口到出口存取路径，在搜索过程中，每前进一步，如果有新位置入栈，则把上一个探索的位置存入栈中，当前位置“-1”（表示这个位置在通路上），并将该位置的坐标压入栈中。如果没有新位置入栈，则返回到上一个位置。一直到达出口。总之，入口出发，顺着某一个方向进行探索，若能走通，则继续往前进，否则沿着原路返回，换一个方向继续探索，直至出口位置，求得一条通路。假如所有可能的通路都探索到而未能到达出口，则所设定的迷宫没有通路。迷宫的入口点在位置（1,1），出口点在位置（m,n）。为处理方便，可在迷宫的四周加一周障碍。对于迷宫的任一位置，均可定为东南西北四个方向可通。（二）为实现算法，需要的象的数据类型InitStack() 构造空栈StackEmpty() 判断栈是否为空Push() 压入新数据元素Pop() 栈顶元素出栈m 迷宫的行数n 迷宫的列数d 0=东 1=南 2=西 3=北typedef struct Lstack Element elem; 链栈struct LStack *next; *PLStack; (三)函数的调用关系 main initmaze mazePath InitStack Push Pop （四）算法时间、空间复杂度1）本算法在空间上主要开辟了一个二维数组，规模都是迷宫（m+2）*（n+2）。一个是栈，一个是迷宫路径记录，输入时候调用栈。2)在时间上为简单的链表栈的存储结构，二维指针initmaze函数算法时间复杂度为O（m+2）*（n+2），Mazepath为O（1），（m为行数n为列数）。五、代码/*以一个m*n的长方阵表示迷宫，0和1分别表示迷宫中的通路和障碍，设计一个程序对任意设定的迷宫，求出一条从入口到出口的通路，或得出没有通路的结论。首先实现一个以链表结构作存储结构的栈类型，然后编写一个求解迷宫的非递归程序。求得的通路以三元组（i,j,d）形式输出，其中（i,j）指示迷宫中的一个坐标，d表示走到下一坐标的方向。*/#include #include #define M 15 #define N 15 struct mark /定义迷宫内点的坐标类型 int x; int y; ; struct Element /栈元素 int x,y; /x行,y列 int d; /d下一步的方向 ; typedef struct LStack /链栈 Element elem; struct LStack *next; *PLStack; /*栈函数*/ int InitStack(PLStack &S)/构造空栈 S=NULL; return 1; int StackEmpty(PLStack S)/判断栈是否为空 if(S=NULL) return 1; else return 0; int Push(PLStack &S, Element e)/压入新数据元素 PLStack p; p=(PLStack)malloc(sizeof(LStack); p-elem=e; p-next=S; S=p; return 1; int Pop(PLStack &S,Element &e) /栈顶元素出栈 PLStack p; if(!StackEmpty(S) e=S-elem; p=S; S=S-next; free(p); return 1; else return 0; /*求迷宫路径函数*/ void MazePath(struct mark start,struct mark end,int mazeMN,int diradd42) int i,j,d;int a,b; Element elem,e; PLStack S1, S2; InitStack(S1); InitStack(S2); mazestart.xstart.y=2; /入口点作上标记 elem.x=start.x; elem.y=start.y; elem.d=-1; /开始为-1 Push(S1,elem); while(!StackEmpty(S1) /栈不为空 有路径可走 Pop(S1,elem); i=elem.x; j=elem.y; d=elem.d+1; /下一个方向 while(d(%d,%d,%d),e.x,e.y,e.d); return; /跳出循环 if(mazeab=0) /找到可以前进的非出口的点 mazeab=2; /标记走过此点 elem.x=i; elem.y=j; elem.d=d; Push(S1,elem); /当前位置入栈 i=a; /下一点转化为当前点 j=b; d=-1; d+; printf(没有找到可以走出此迷宫的路径n); /*建立迷宫*/ void initmaze(int mazeMN) int i,j; int m,n; /迷宫行,列 /M printf(请输入迷宫的行数 m=); scanf(%d,&m); printf(请输入迷宫的列数 n=); scanf(%d,&n); printf(n请输入迷宫的各行各列:n用空格隔开,0代表路,1代表墙n,m,n); for(i=1;i=m;i+) for(j=1;j=n;j+) scanf(%d,&mazeij); printf(你建立的迷宫为(最外圈为墙).n); for(i=0;i=m+1;i+) /加一圈围墙 mazei0=1; mazein+1=1; for(j=0;j=n+1;j+) maze0j=1; mazem+1j=1; for(i=0;i=m+1;i+) /输出迷宫 for(j=0;j=n+1;j+) printf(%d ,mazeij); printf(n); void main() int stoMN; struct mark start,end; /start,end入口和出口的坐标 int add42=0,1,1,0,0,-1,-1,0;/行增量和列增量 方向依次为东西南北 /M initmaze(sto);/建立迷宫 printf(输入入口的横坐标,纵坐标逗号隔开n); scanf(%d,%d,&start.x,&start.y); printf(输入出口的横坐标,纵坐标逗号隔开n); scanf(%d,%d,&end.x,&end.y); MazePath(start,end,sto,add); /find path system(PAUSE); 六、运行结果分析（一）迷宫路径探索成功初始界面测试数据迷宫6行（输入“6”点击Enter得到下一界面）测试数据迷宫8列（输入“8”点击Enter得到下一界面）测试数据6行8列迷宫0 1 0 1 1 0 1 10 0 1 1 1 0 1 01 0 1 1 0 1 0 01 0 0 0 1 0 1 10 0 0 1 1 1 1 01 1 0 0 1 0 1 1（输入上述迷宫，点击Enter得到下一界面）测试数据迷宫入口（1,1）（输入“1，1”点击Enter得到下一界面）测试数据迷宫出口（6,3）（输入“6，3”点击Enter得到下一界面）如上图，我们可以得到：当迷宫为0 1 0 1 1 0 1 10 0 1 1 1 0 1 01 0 1 1 0 1 0 01 0 0 0 1 0 1 10 0 0 1 1 1 1 01 1 0 0 1 0 1 1迷宫入口为（1,1）出口为（6,3）时迷宫路径为，（括号内的内容分别表示为（行坐标，列坐标，数字化方向（0=东 1=南 2=西 3=北） 迷宫路径探索成功！（二）迷宫路径未找到的情况在上述测试的数据当中，我们把迷宫出口改为（6,5）得到的运行结果如下图：（三）程序的优缺点与改进1、该程序在输出上显得有些繁琐。更改方向可以考虑用一个二维数组来记录4方向上行下标增量和列下标增量，则沿第i个方向前进一步，可能到达的新位置坐标可以利用该数组确定；2、输出时可以考虑编写一个输出函数，到时直接调用这个输出函数就好。假如恢复迷宫函数，输出迷宫路径后再恢复迷宫原始位置；3、对于手动输入，如果迷宫数据太大时，就很麻烦，而且很费时间，可以用随机产生函数，自动生成迷宫。七、参考文献1、数据结构 C语言 严蔚敏 清华大学出版社 20022、C语言程序设计 谭浩强 清华大学出版社 20053、C语言通用范例开发金典柳盛2008八、心得体会为期大半学期的数据结构的集中上机接近尾声，在这大半学期里，虽然最后只做了一道题，但真的学到很多。通过两年来的学习，我觉得这样的集中上机是非常有意义的。数据结构是学习计算机的必学课程，是信息与计算科学专业的一门主要专业基础课程，通过这次实验上机我们学会在VC的环境下去实现数据结构中的算法。在学习了理论知识之后，如何去具体的处理数据结构中编程的问题，如何把我们的理论运用到实践中去，这样的集中上机为我们提供了这样一个实践平台。通过这次实验，我收获颇多。首先是对C语言的认识有了进一步的提升。过这次上机实验对数据结构有了更进一步的巩固。其次，通过这次上机实验，我对非递归算法有了更深一层的理解。在做本次课程设计的过程中我感触最深的当属查阅书籍，为了让自己的设计更加完善，更加符合标准一次次的翻阅相关书籍浏览网页是十分必要的。要很要的掌握编程不能仅仅通过几个简单的程序编写，更需要大量积累和深入才可能。求迷宫路径需要使用链表的栈，靠进栈和出栈来存取路径数据，在编写程序时，带着问题去反复进行实践。通过这次上机实验，我对数据结构有了进一步的巩固，更进一步为学习和解决科学与工程中的实际问题打好基础，使