迷宮設(shè)計(jì)實(shí)驗(yàn)報(bào)告

天津商業(yè)大學(xué)《數(shù)據(jù)結(jié)構(gòu)》課程設(shè)計(jì)匯報(bào)題目：迷宮問(wèn)題學(xué)院：信息工程學(xué)院專業(yè)：計(jì)算機(jī)科學(xué)與技術(shù)班級(jí)：13-01班姓名：王同組人員：譚陳指導(dǎo)教師：黃年12月26日目錄TOC\o"1-2"\h\z\u1.課程設(shè)計(jì)內(nèi)容 12.需求分析 13.概要設(shè)計(jì) 13.1抽象數(shù)據(jù)類型定義 13.2模塊劃分 14.詳細(xì)設(shè)計(jì) 14.1數(shù)據(jù)類型定義 14.2主要模塊算法描述 14.3函數(shù)之間調(diào)用關(guān)系 25.程序運(yùn)行說(shuō)明與測(cè)試 25.1用戶手冊(cè) 25.2測(cè)試結(jié)果及分析 26.課程設(shè)計(jì)總結(jié) 2附錄（源程序清單） 2課程設(shè)計(jì)內(nèi)容【問(wèn)題描述】以一個(gè)m×n長(zhǎng)方陣表示迷宮，0和1表示迷宮中通路和障礙。設(shè)計(jì)一個(gè)程序，對(duì)任意設(shè)定迷宮，求出一條入口到出口通路，或得出沒(méi)有通路結(jié)論?！净疽蟆渴紫葘?shí)現(xiàn)一個(gè)棧類型，然后編寫一個(gè)求解迷宮非遞歸程序。求得通路以三元組(i,j,d)形式輸出，其中：(i,j)指示迷宮中一個(gè)坐標(biāo)，d表示走到下一坐標(biāo)方向。如：對(duì)于以下數(shù)據(jù)迷宮，輸出一條通路為：(1,1,1)，（1,2,2）,（2,2,2）（3,2,3），（3,1,2）……需求分析(1)以二維數(shù)組maze[M+2][N+2]表示迷宮，其中maze[i][0]和maze[i][N+1](0=<i<=N+1)以及maze[0][j]和maze[M+1][j](0=<j<=M+1)為外加一圈圍墻。數(shù)組中元素0表示障礙1表示可經(jīng)過(guò)，迷宮大小可不限；(2)迷宮中數(shù)據(jù)均由用戶自由輸入；(3)迷宮出口和入口可由用戶自由設(shè)定；(4)本程序只求出一條成功通路；(5)程序執(zhí)行命令為：①創(chuàng)建迷宮②求解迷宮③輸出迷宮解3.概要設(shè)計(jì)3.1抽象數(shù)據(jù)類型定義(1)設(shè)定棧抽象數(shù)據(jù)類型定義：ADTStack{數(shù)據(jù)對(duì)象：D={ai|ai∈CharSet，i=1,2，…,n，n>=0}數(shù)據(jù)關(guān)系：R1{<a(i-1)>|a(i-1),ai∈D,i=2,3…n}基本操作：InitStack(&S)操作結(jié)果：結(jié)構(gòu)一個(gè)空棧S。DestroyStack(&S)初始結(jié)果：棧S已存在。操作結(jié)果：銷毀棧S。ClearStack(&S)初始結(jié)果：棧S已存在。操作結(jié)果：將S清為空棧。StackLength(S)初始結(jié)果：棧S已存在。操作結(jié)果：返回棧S長(zhǎng)度StackEmpty(S)初始條件：棧S已存在。操作結(jié)果：若S為空棧，則返回TRUE，不然返回FALSEGetTop(S,&e)初始條件：棧S已存在。操作結(jié)果：若棧S不空，則以e返回棧頂元素e。Push(&S,e)初始條件：棧S已存在。操作結(jié)果：在棧S棧頂插入新棧頂元素。Pop(&S,&e)初始條件：棧S已存在。操作結(jié)果：刪除S棧頂元素，并以e返回其值。StackTraverse(S,visit())初始條件：棧S已存在。操作結(jié)果：從棧底到棧頂依次對(duì)S中每個(gè)元素調(diào)用visit()}ADTStack(2)設(shè)定迷宮抽象數(shù)據(jù)類型為：ADTmaze{數(shù)據(jù)對(duì)象：D={a(i,j)|a(i,j)∈{0,1}，0=<i<=m+1,0=<j<=n+1,m,n<=10}數(shù)據(jù)關(guān)系：R={M，N}M={<a(i-1,j)，a(i,j)>|a(i-1,j)，a(i,j)∈D,i=1,2,…,m+1,j=0,1,…n+1}N={<a(i,j-1),a(i,j)>|a(i,j-1),a(i,j)∈D,I=0,1,…m+1,j=1,2,…n+1}基本操作：InitMaze(&M,maze,m,n)初始條件：二維數(shù)組maze[m+1][n+1]已存在，其中自第一行至第m+1行、每行中自第一列至第n+1列元素已經(jīng)有值，而且以值0表示通路，以值1表示障礙。操作結(jié)果：組成迷宮字符型數(shù)組，以字符0表示通路，以字符1障礙，并在迷宮四面加上一圈障礙。MazePath(&M) 初始條件：迷宮M已被賦值。操作結(jié)果：若迷宮M中存在一條通路，則按以下要求改變迷宮M狀態(tài)：以數(shù)字0代表可經(jīng)過(guò)，數(shù)字1代表不可經(jīng)過(guò)。模塊劃分(1)主程序模塊：voidmain(){intsto[M][N];structmarkstart,end;//start,end入口和出口坐標(biāo)intadd[4][2]={{0,1},{1,0},{0,-1},{-1,0}};//行增量和列增量方向依次為東西南北initmaze(sto);//建立迷宮printf("輸入入口橫坐標(biāo),縱坐標(biāo)[逗號(hào)隔開]\n");scanf("%d,%d",&start.x,&start.y);printf("輸入出口橫坐標(biāo),縱坐標(biāo)[逗號(hào)隔開]\n");scanf("%d,%d",&end.x,&end.y);MazePath(start,end,sto,add);//findpathsystem("PAUSE");}(2)棧模塊——實(shí)現(xiàn)棧抽象數(shù)據(jù)類型；(3)迷宮模塊——實(shí)現(xiàn)迷宮抽象數(shù)據(jù)類型，建立迷宮，求解迷宮一條路徑。4.詳細(xì)設(shè)計(jì)4.1數(shù)據(jù)類型定義(1)坐標(biāo)位置，類型：structmark//定義迷宮內(nèi)點(diǎn)坐標(biāo)類型{intx;inty;};(2)迷宮類型voidinitmaze(intmaze[M][N])//按照用戶輸入M行和N列二維數(shù)組（元素值為0或1）//設(shè)置迷宮maze初值，包含加上邊緣一圈值voidMazePath(structmarkstart,structmarkend,intmaze[M][N],intdiradd[4][2])//求解迷宮maze中從入口Start到出口end一條路徑//若存在，則返回TRUE，不然返回FALSE(3)棧類型structElement{intx,y;//x行,y列intd;//d下一步方向};typedefstructLStack//鏈棧{Elementelem;structLStack*next;}*PLStack;4.2主要模塊算法描述(1)求迷宮路徑偽碼算法voidMazePath(structmarkstart,structmarkend,intmaze[M][N],intdiradd[4][2]){inti,j,d;inta,b;Elementelem,e;PLStackS1,S2;InitStack(S1);InitStack(S2);maze[start.x][start.y]=2;//入口點(diǎn)作上標(biāo)識(shí)elem.x=start.x;elem.y=start.y;elem.d=-1;//開始為-1Push(S1,elem);while(!StackEmpty(S1))//棧不為空有路徑可走{Pop(S1,elem);i=elem.x;j=elem.y;d=elem.d+1;//下一個(gè)方向while(d<4)//試探東南西北各個(gè)方向{a=i+diradd[d][0];b=j+diradd[d][1];if(a==end.x&&b==end.y&&maze[a][b]==0)//假如到了出口{elem.x=i;elem.y=j;elem.d=d;Push(S1,elem);elem.x=a;elem.y=b;elem.d=886;//方向輸出為-1判斷是否到了出口Push(S1,elem);printf("\n0=東1=南2=西3=北886為則走出迷宮\n\n通路為:(行坐標(biāo),列坐標(biāo),方向)\n");while(S1)//逆置序列并輸出迷宮路徑序列{Pop(S1,e);Push(S2,e);}while(S2){Pop(S2,e);printf("-->(%d,%d,%d)",e.x,e.y,e.d);}return;//跳出兩層循環(huán)，原來(lái)用break,但發(fā)覺(jué)犯錯(cuò)，exit又會(huì)結(jié)束程序，選取return還是不錯(cuò)滴o(∩_∩)o...}if(maze[a][b]==0)//找到能夠前進(jìn)非出口點(diǎn){maze[a][b]=2;//標(biāo)識(shí)走過(guò)此點(diǎn)elem.x=i;elem.y=j;elem.d=d;Push(S1,elem);//當(dāng)前位置入棧i=a;//下一點(diǎn)轉(zhuǎn)化為當(dāng)前點(diǎn)j=b;d=-1;}d++;}}printf("沒(méi)有找到能夠走出此迷宮路徑\n");}(2)建立迷宮偽碼算法voidinitmaze(intmaze[M][N]){inti,j;intm,n;//迷宮行,列printf("請(qǐng)輸入迷宮行數(shù)m=");scanf("%d",&m);printf("請(qǐng)輸入迷宮列數(shù)n=");scanf("%d",&n);printf("\n請(qǐng)輸入迷宮各行各列:\n用空格隔開,0代表路,1代表墻\n",m,n);for(i=1;i<=m;i++)for(j=1;j<=n;j++)maze[i][j]=(int)(rand()%2);//scanf("%d",&maze[i][j]);printf("你建立迷宮為o(∩_∩)o...\n");for(i=0;i<=m+1;i++)//加一圈圍墻{maze[i][0]=1;maze[i][n+1]=1;}for(j=0;j<=n+1;j++){maze[0][j]=1;maze[m+1][j]=1;}for(i=0;i<=m+1;i++)//輸出迷宮{for(j=0;j<=n+1;j++)printf("%d",maze[i][j]);printf("\n");}}(3)主函數(shù)偽碼算法：voidmain(){intsto[M][N];structmarkstart,end;//start,end入口和出口坐標(biāo)intadd[4][2]={{0,1},{1,0},{0,-1},{-1,0}};//行增量和列增量方向依次為東西南北initmaze(sto);//建立迷宮printf("輸入入口橫坐標(biāo),縱坐標(biāo)[逗號(hào)隔開]\n");scanf("%d,%d",&start.x,&start.y);printf("輸入出口橫坐標(biāo),縱坐標(biāo)[逗號(hào)隔開]\n");scanf("%d,%d",&end.x,&end.y);MazePath(start,end,sto,add);//findpathsystem("PAUSE");}(4)棧初始化、判空、進(jìn)棧、和出棧等偽碼算法：intInitStack(PLStack&S)//結(jié)構(gòu)空棧{S=NULL;return1;}intStackEmpty(PLStackS)//判斷棧是否為空{(diào)if(S==NULL)return1;elsereturn0;}intPush(PLStack&S,Elemente)//壓入新數(shù)據(jù)元素{PLStackp;p=(PLStack)malloc(sizeof(LStack));p->elem=e;p->next=S;S=p;return1;}intPop(PLStack&S,Element&e)//棧頂元素出棧{PLStackp;if(!StackEmpty(S)){e=S->elem;p=S;S=S->next;free(p);return1;}elsereturn0;}4.3函數(shù)之間調(diào)用關(guān)系5.程序運(yùn)行說(shuō)明與測(cè)試5.1用戶手冊(cè)(1)本程序運(yùn)行環(huán)境為C語(yǔ)言運(yùn)行環(huán)境，新建文件后綴名：.cpp(2)進(jìn)入演示程序后，即顯示以下用戶界面：①、點(diǎn)擊組建進(jìn)行“編譯”；②、點(diǎn)擊運(yùn)行程序；(3)執(zhí)行程序出現(xiàn)界面后，按照提醒先迷宮行數(shù)和列數(shù)回車，深入輸入迷宮內(nèi)數(shù)據(jù)‘1’代表墻，‘0’代表路徑回車；輸入迷宮“入口”和“回車即可現(xiàn)實(shí)路徑，或者顯示沒(méi)有路徑可走。5.2測(cè)試數(shù)據(jù)(1)輸入行數(shù)：3；輸入列數(shù)：2輸入迷宮數(shù)據(jù)為：000000入口位置：11出口位置：32(2)輸入行數(shù)：3；輸入列數(shù)：4輸入迷宮數(shù)據(jù)：000000110000入口位置：11出口位置：34(3)輸入行數(shù)：4；輸入列數(shù)：9輸入迷宮數(shù)據(jù)：000000100010001000001110011001110100入口位置：11出口位置：49 (4)輸入行數(shù)：8；輸入列數(shù)：9輸入迷宮數(shù)據(jù)：001000100010001000001101011100100001000001000101011110011100010111000000入口位置：11出口位置：895.3測(cè)試結(jié)果及分析(1)(2)(3)(4)6.試驗(yàn)總結(jié)(1)此次算法包括迷宮求解路徑和迷宮建立函數(shù)；建立迷宮函數(shù)時(shí)可自由確定迷宮行數(shù)和列數(shù)，及迷宮內(nèi)數(shù)據(jù)也可自由輸入；但在建立迷宮數(shù)據(jù)時(shí)一開始使用是隨機(jī)函數(shù)，不過(guò)用此方法生成迷宮行數(shù)列數(shù)一致時(shí)迷宮也是一致，且找不著路徑；(2)本題中主要算法：MazePath和initmaze時(shí)間復(fù)雜度為O(m*n)，本題空間復(fù)雜度異為O(m*n)（棧所占最大空間）附：源程序清單#include<stdio.h>#include<stdlib.h>#defineM15#defineN15structmark//定義迷宮內(nèi)點(diǎn)坐標(biāo)類型{intx;inty;};structElement//"戀"棧元素，嘿嘿。。{intx,y;//x行,y列intd;//d下一步方向};typedefstructLStack//鏈棧{Elementelem;structLStack*next;}*PLStack;/*************棧函數(shù)****************/intInitStack(PLStack&S)//結(jié)構(gòu)空棧{S=NULL;return1;}intStackEmpty(PLStackS)//判斷棧是否為空{(diào)if(S==NULL)return1;elsereturn0;}intPush(PLStack&S,Elemente)//壓入新數(shù)據(jù)元素{PLStackp;p=(PLStack)malloc(sizeof(LStack));p->elem=e;p->next=S;S=p;return1;}intPop(PLStack&S,Element&e)//棧頂元素出棧{PLStackp;if(!StackEmpty(S)){e=S->elem;p=S;S=S->next;free(p);return1;}elsereturn0;}/***************求迷宮路徑函數(shù)***********************/voidMazePath(structmarkstart,structmarkend,intmaze[M][N],intdiradd[4][2]){inti,j,d;inta,b;Elementelem,e;PLStackS1,S2;InitStack(S1);InitStack(S2);maze[start.x][start.y]=2;//入口點(diǎn)作上標(biāo)識(shí)elem.x=start.x;elem.y=start.y;elem.d=-1;//開始為-1Push(S1,elem);while(!StackEmpty(S1))//棧不為空有路徑可走{Pop(S1,elem);i=elem.x;j=elem.y;d=elem.d+1;//下一個(gè)方向while(d<4)//試探東南西北各個(gè)方向{a=i+diradd[d][0];b=j+diradd[d][1];if(a==end.x&&b==end.y&&maze[a][b]==0)//假如到了出口{elem.x=i;elem.y=j;elem.d=d;Push(S1,elem);elem.x=a;elem.y=b;elem.d=886;//方向輸出為-1判斷是否到了出口Push(S1,elem);printf("\n0=東1=南2=西3=北886為則走出迷宮\n\n通路為:(行坐標(biāo),列坐標(biāo),方向)\n");while(S1)//逆置序列并輸出迷宮路徑序列{Pop(S1,e);Push(S2,e);}while(S2){Pop(S2,e);printf("-->(%d,%d,%d)",e.x,e.y,e.d);}return;//跳出兩層循環(huán)，原來(lái)用break,但發(fā)覺(jué)犯錯(cuò)，exit又會(huì)結(jié)束程序，選取return還是不錯(cuò)滴o(∩_∩)o...}if(maze[a][b]==0)//找到能夠前進(jìn)非出口點(diǎn){maze[a][b]=2;//標(biāo)識(shí)走過(guò)此點(diǎn)elem.x=i;elem.y=j;elem.d=d;Push(S1,elem);//當(dāng)前位置入棧i=a;//下一點(diǎn)轉(zhuǎn)化為當(dāng)前點(diǎn)j=b;d=-1;