大数据结构迷宫问题实验报告材料

1、实用标准文案©*#?建大*世仁埠茂CwnflyvyCdAgifl, MjiUqrrml>!Df FMi arMf tolinrmviwQftcm数据结构与算法设计迷宫问题实验报告实验二专业：物联网工程班级：物联网1班学号：15180118姓名：刘沛航实验目的本程序是利用非递归的方法求出一条走出迷宫的路径，弁将路径输出。首先由用户输入一组二维数组来组成迷宫，确认后程序自动运行，当迷宫有完整路径可以通过时，以 0和1所组成 的迷宫形式输出，标记所走过的路径结束程序；当迷宫无路径时， 提示输入错误结束程序。二、实验内容用一个m*m长方阵表示迷宫，0和1分别表示迷宫中的通路和 障碍。设

2、计一个程序对于任意设定的迷宫， 求出一条从入口到出口的 通路，或得出没有通路的结论。三、程序设计1、概要设计(1)设定栈的抽象数据类型定义ADT Stack 数据对象：D=ai|ai 属于 CharSet, i=1、2n, n>=0数据关系：R=<ai-1,ai>|ai-1,ai 属于 D , i=2,3，n 基本操作：InitStack(&S)操作结果：构造一个空栈Push (&S , e)初始条件：栈已经存在操作结果：将e所指向的数据加入到栈 s中Pop (&S,&e )初始条件：栈已经存在操作结果：若栈不为空，用 e返回栈顶元素，并删除栈

3、顶元素Getpop ( &S , &e)初始条件：栈已经存在操作结果：若栈不为空，用 e返回栈顶元StackEmpty(&S)初始条件：栈已经存在操作结果：判断栈是否为空。若栈为空，返回 1,否则返回0Destroy(&S)初始条件：栈已经存在操作结果：销毁栈s ADT Stack(2)设定迷宫的抽象数据类型定义ADT yanshu 数据对象：D=ai,j|ai,j 属于 '、 '*'、 '、 ' #' ,0<=i<=M,0<=j<=N数据关系：R=ROW,COLROW=<ai-1,j

4、 ,ai,j>|ai-1,j ,ai,j 属于 D, i=1,2,M,j=0,1，NCOL=<ai,j-1 ,ai,j>|ai,j-1 ,ai,j 属于 D,i=0,1，M, j=1,2,N基本操作：InitMaze(MazeType &maze, int aCOL, int row, int col)初始条件：二维数组int a口COL,已经存在，其中第1至第 m-1行，每行自第1到第n-1列的元素已经值，并以值0表示障 碍，值1表示通路。操作结果：构造迷宫的整形数组，以空白表示通路，字符0'表示障碍在迷宫四周加上一圈障碍MazePath (&maz

5、e) 初始条件：迷宫maze已被赋值操作结果：若迷宫maze中存在一条通路，则按如下规定改 变maze的状态；以字符*'表示路径上的位置。字符''表示 死胡同；否则迷宫的状态不变)PrintMaze (M ) 初始条件：迷宫M已存在操作结果：以字符形式输出迷宫)ADTmaze(3)本程序包括三个模块a、主程序模块 void main () 初始化； 构造迷宫； 迷宫求解； 迷宫输出；b、栈模块一一实现栈的抽象数据类型c、迷宫模块一一实现迷宫的抽象数据类型2、详细设计(1)坐标位置类型：typedef structintrow; /迷宫中的行 int col; /的列Po

6、sType;坐标(2)迷宫类型：typedef structint m,n;int arrRANGERANGE;MazeType;/迷宫类型void/设置迷宫的初值，包括边缘一圈的值Bool MazePath(MazeType &maze,PosType start, PosType end)求解迷宫 maze中，从入口 start到出口 end的一条路径/若存在，则返回true ,否则返回falseVoid PrintMaze ( MazeType maze )/将迷宫打印出来(3)栈类型：typedef structint step; /当前位置在路径上的"序号"

7、;PosType seat; 当前的坐标位置DirectiveType di; /往下一个坐标位置的方向SElemType;栈的元素类型typedef structSElemType *base;SElemType *top;int stacksize;SqStack;栈的基本操作设置如下：Void InitStack (SqStack & S)初始化，设 S为空栈(S.top=NUL )Void DestroyStack(Stack &S)销毁栈S,并释放空间Void ClearStack (SqStack & S)/将栈S清空Int StackLength (SqS

8、tack &S)/返回栈S的长度Status StackEmpty (SqStack &S )?、若S为空栈(S.top=NULL ),则返回TRUE,否则返回 FALSEStatue GetTop (SqStack &S , SElemType e)/r若栈S不空，则以e待会栈顶元素并返回TRUE,否则返回FALSEStatue Pop(SqStack&S, SElemType e)/若分配空间成功，则在 S的栈顶插入新的栈顶元素s并返回TRUE否则栈不变，并返回FALSEStatue Push(SqStack&S, SElemType &e)

9、/若分配空间程控，则删除栈顶并以e带回其值，则返回 TRUE否则返回FALSEVoid StackTraverse (SqStack &S , Status) ( *Visit) (SElemType e)/从栈顶依次对S中的每个节点调用函数Visit4求迷宫路径的伪码算法：Status MazePath(MazeType &maze,PosType start, PosType end)/球解迷宫 maze 中，从入 口 start 到出口 end的一条路径InitStack(s);PosType curpos = start;int curstep = 1;/ 探索第一部d

10、oif( Pass(maze,curpos) ) /如果当前位置可以通过，即是未曾走到的通道块FootPrint(maze,curpos); / 留下足迹e = CreateSElem(curstep,curpos,1); 创建元素Push(s,e);if( PosEquare(curpos,end) ) return TRUE;curpos =NextPos(curpos,1); /获得下一节点：当前位置的东邻curstep+;/ 探索下一步else/当前位置不能通过if(!StackEmpty(s)Pop(s,e);while(e.di=4 && !StackEmpty(s

11、) )MarkPrint(maze,e.seat); Pop(s,e); /留下不能通过的标记，并退回步if(e.di<4)e.di+; Push(s,e);/ 换一个方向探索curpos = NextPos(e.seat,e.di); 设定当前位置是该方向上的相块/if/ifelsewhile(!StackEmpty(s);return FALSE;/MazePath四、程序调试分析1 .首先呢，想自己读入数据的，回来发现那样，很麻烦，所以还 是事先定义一个迷宫。2 .栈的元素类型一开始有点迷惑，后来就解决了3 .本题中三个主要算法；InitMaze, MazePath和PrintMa

12、ze的时 间复杂度均为O (m*n)本题的空间复杂度也是 O (m*n) 五、用户使用说明1.本程序运行在windows系列的操作系统下，执行文件为:Maze_Test.exe)六、程序运行结果文档大全1.建立迷宫:2.通过1功能建立8*8的迷宫后，通过2功能继续建立迷宫内部： WUSERKPEKAHV 口- X2g*3=t；m；MeR*JaM*何雇用闭 口 51W01口潸ji*i£*iXiC*也口*Qot*1请输入迷宫的行黜列数 百音箱人逆育口堵中礴 於官结沟如二 礴人迷宫的起点和终点 播史转果 送出情选悻2适辅入让日内堵堂无救；10话侪找希人达5四地旺里元的行魏,列蠹；三棺展开;

13、2 34 55 26 47 68 6M 79 510 311 5建拓拼音场人法全：通过建立自己设定单元数目建立迷宫内墙。3 .通过3功能观察已建立的迷宫结构：4 .通过4功能确立迷宫起点和终点：（此处像我们随机选择4,4和2,7分别为起点终点）1C:U5tR5FEKAHBESKTCi 叫新建交件夫XPebuflWazr j«oe”*力士* *XCJ1;* 物 R 壬网 L珈-15 1 gg 11 沛航率 3CXA4* KX*XC* jQC*i二宦新区在百的行就列效 2请输入正有内向年厂扣 我酹懒吓 碗A迷宫的底点和终点 礴出结果 噬出清出至4；H略漏开：，4 4:空格隔开）Z，赵心起

14、占:j招刊现 请辅人终点的行瓢到敷澧我拼吉颖底等:5 .执行5功能，判断是否有路径走出迷宫:t:USER5FEKAHPESKTCiF1.薪珅克冲左但匕小川也上就”- X卜c±*T«t4*a«t *Hc*+* *dg；*物科网 场匕 15式 1 虚卞|沛布；M44* 其Hc*i*"*I*At4;情新3泮百的行就到前 2请输入正有内埼单元款 碓舌楸吓 储A 住目的起点和终点 就出结果噬出I南町圣s此之目，殳才从人口到出口的埼径，谢谢使用刘叶帆tUir 陆人口近出注国拼音镯入法全：这种情况无法走出迷宫。我们再次观察图像设4,4和1,6分别为起点终点，再运行 5

15、功能 XJ "Q'.UserspekahDeEicLCDea uqIVaze 后111薄人迷宫的比，列数 工请输人迷宫内清单元数 ；迷官结构加下4输入迷宫的越点植终点 司叶片中Q退出卜青:*j莘 5此迷宫从入口到出口的一聚珞座如下,00000Q.10013U15167L8031311C1100910-10110n80010nn谢亦使司利沛肮的程序:观察到可以成功解开迷宫步数从1依次开始七、程序清单#include<stdio.h>#include<stdlib.h>#include<string.h>#include<malloc.h

16、>/迷宫坐标位置类型typedef structint x;/ 行值int y;/ 列值PosType;#define MAXLENGTH 25 /设迷宫的最大行列为25typedef int MazeTypeMAXLENGTHMAXLENGTH; /迷宫数组行歹U typedef struct / 栈的元素类型 int ord; / 通道块在路径上的"序号"PosType seat;/通道块在迷宫中的"坐标位置"int di; /从此通道块走向下一通道块的"方向" (03表示东北) SElemType;/全局变量MazeTyp

17、e m; / 迷宫数组int curstep=1;/ 当前足迹，初值为1#define STACK_INIT_SIZE 10/存储空间初始分配量#define STACKINCREMENT 2/存储空间分配增量/栈的顺序存储表示typedef struct SqStackSElemType *base; /在栈构造之前和销毁之后，base的值为NULLSElemType *top;/ 栈顶指针int stacksize; /当前已分配的存储空间，以元素为单位SqStack; / 顺序栈/构造一个空栈S int InitStack(SqStack *S)/为栈底分配一个指定大小的存储空间(*S)

18、.base = (SElemType *)malloc(STACK_INIT_SIZE*sizeof(SElemType);if( !(*S).base ) exit(0);(*S).top = (*S).base; /栈底与栈顶相同表示一个空栈(*S).stacksize = STACK_INIT_SIZE;return 1;/若栈S为空栈(栈顶与栈底相同的)，则返回1,否则返回0。int StackEmpty(SqStack S) if(S.top = S.base)return 1;elsereturn 0;/插入元素e为新的栈顶元素。int Push(SqStack *S, SElem

19、Type e)if(*S).top - (*S).base >= (*S).stacksize) / 栈满，追加存储空间(*S).base = (SElemType *)realloc(*S).base ,(*S).stacksize + STACKINCREMENT) * sizeof(SElemType);if( !(*S).base )exit(0);(*S).top = (*S).base+(*S).stacksize;(*S).stacksize += STACKINCREMENT;*(*S).top)+=e;return 1;/若栈不空，则删除S的栈顶元素，用e返回其值，并返

20、回 1;否则返回0。int Pop(SqStack *S,SElemType *e)if(*S).top = (*S).base) return 0;*e = *-(*S).top;/这个等式的+ *优先级相同，但是它们的运算方式，是自右向左return 1;/定义墙元素值为0,可通过路径为1,不能通过路径为-1,通过路径为足迹/当迷宫 m的b点的序号为1(可通过路径),return 1;否则，return 0。int Pass(PosType b)if(mb.xb.y=1)return 1;elsereturn 0;void FootPrint(PosType a) /使迷宫 m的a点的序号

21、变为足迹(curstep),表示经过ma.xa.y=curstep;/根据当前位置及移动方向，返回下一位置PosType NextPos(PosType c,int di) PosType direc4=0,1,1,0,0,-1,-1,0; / 行增量，列增量/移动方向，依次为东南西北c.x+=direcdi.x;c.y+=direcdi.y; return c;/使迷宫m的b点的序号变为-1(不能通过的路径)void MarkPrint(PosType b)mb.xb.y=-1;/若迷宫maze中存在从入口 start到出口 end的通道，则求得一条/存放在栈中(从栈底到栈顶)，并返回1;否

22、则返回0int MazePath(PosType start,PosType end) SqStack S;PosType curpos;SElemType e;InitStack(&S);curpos=start; do if(Pass(curpos) /当前位置可以通过，即是未曾走到过的通道块 FootPrint(curpos);/ 留下足迹 e.ord=curstep;e.seat.x=curpos.x;e.seat.y=curpos.y;e.di=0;Push(&S,e); /入栈当前位置及状态curstep+; / 足迹加 1if(curpos.x=end.x&

23、;&curpos.y=end.y) /至1J达终点(出 口 )return 1;curpos=NextPos(curpos,e.di); else /当前位置不能通过 if(!StackEmpty(S) Pop(&S,&e); /退栈到前一位置curstep-;(北)while(e.di=3&&!StackEmpty(S) /前一位置处于最后一个方向 MarkPrint(e.seat);/留下不能通过的标记(-1)Pop(&S,&e); /退回一步curstep-;if(e.di<3)/没到最后一个方向(北) e.di+; /换下一

24、个方向探索 Push(&S,e); curstep+;/ 设定当前位置是该新方向上的相邻块 curpos=NextPos(e.seat,e.di); while(!StackEmpty(S); return 0;/输出迷宫的结构 void Print(int x,int y) int i,j;for(i=0;i<x;i+) for(j=0;j<y;j+) printf("%3d",mij); printf("n"); void main() PosType begin,end; int i,j,x,y,x1,y1,n,k; dosys

25、tem("cls");printf("*坨坨坨")；printf("printf("printf("printf("printf("printf("printf("nn请选择");scanf("%d",&n);switch(n)case 1:printf("请输入迷宫的行数 scanf("%d%d", &x, &y);清屏函数物联网 1 班 -15180118- 刘沛航1请输入迷宫的行数，列数n");2请输入迷宫内墙单元数n");3迷宫结卞如下n");4输入迷宫的起点和终点n");5输出结果n");0退出n");，列数(包括外墙)：(空格隔开)");for(i=0;i<x;i+)/定义周边值为0(同墙)m0i=0；mx-1i=0；/迷宫上面行的周边即上边墙迷宫下面