迷宮問題有源代碼

1、西安郵電大學(xué)數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)報(bào)告題 目：迷宮問題院系名稱：計(jì)算機(jī)學(xué)院 專業(yè)名稱：軟件工程班 級(jí)：1101班 學(xué)生姓名：付添學(xué)號(hào)（8位）：04113035指導(dǎo)教師： 李培 設(shè)計(jì)起止時(shí)間：2012年12月3日2012年12月14日一. 設(shè)計(jì)目的僅僅認(rèn)識(shí)到隊(duì)列是一種特殊的線性表是遠(yuǎn)遠(yuǎn)不夠的，本次實(shí)習(xí)的目的在于使學(xué)生深入了解隊(duì)列的特征，以便在實(shí)際問題背景下靈活運(yùn)用它，同時(shí)還將鞏固這種數(shù)據(jù)結(jié)構(gòu)的構(gòu)造方法，是同學(xué)們棧的運(yùn)用更得心應(yīng)手，為以后就業(yè)打下很好的基礎(chǔ)。2. 設(shè)計(jì)內(nèi)容主要包括哈1.從鍵盤輸入迷宮。2.從文件讀出迷宮。3.走迷宮。4以坐標(biāo)形式輸出迷宮路徑。5.以形象的矩陣輸出路徑。三概要設(shè)計(jì)1功能模塊

2、圖；從文件讀入字符從鍵盤輸入迷宮從文件讀出迷宮走迷宮選擇輸出東邊有通路西邊有通路北邊有通路南邊有通路選擇一個(gè)走以形象矩陣輸出以坐標(biāo)形式輸出輸入數(shù)字選擇1, 2 3;2各個(gè)模塊詳細(xì)的功能描述。（1）savefile();/從鍵盤輸入迷宮從鍵盤輸入迷宮1表示墻0表示通路，并把01存入結(jié)構(gòu)體m1中用flag表示通路初始化通路的標(biāo)志域。（2）inread();/從文件讀出迷宮事先已將迷宮存入文件中，從文件讀出迷宮1表示墻0表示通路，并把01存入結(jié)構(gòu)體m1中用flag表示通路初始化通路的標(biāo)志域。（3）zoumigong();/走迷宮根據(jù)m1判斷該坐標(biāo)四周如果為墻并且標(biāo)志域?yàn)?則可走，將該坐標(biāo)入棧，將其標(biāo)

3、志域更改為1，更新坐標(biāo)，繼續(xù)判斷，知道更新坐標(biāo)等于出口坐標(biāo).棧中存放就是通路的逆序坐標(biāo)。(4)print1()/以坐標(biāo)形式輸出將棧中坐標(biāo)出棧，存入數(shù)組中以坐標(biāo)形式輸出。（5）print2（）/以矩陣形式輸出將棧中坐標(biāo)出棧，存入數(shù)組中以矩陣形式輸出。四詳細(xì)設(shè)計(jì)1 功能函數(shù)的調(diào)用關(guān)系Savefile(),inread()選擇一個(gè)輸入圖走迷宮zoumigong();Print1()坐標(biāo)形式輸出。Print2()矩陣形式輸出。2各功能函數(shù)的數(shù)據(jù)流程圖走迷宮判斷哪個(gè)方向可走。該坐標(biāo)西邊可有通路，該坐標(biāo)入站，標(biāo)志域賦1，更新坐標(biāo)該坐標(biāo)西邊可有通路，該坐標(biāo)入站，標(biāo)志域賦1，更新坐標(biāo)該坐標(biāo)西邊可有通路，該坐標(biāo)

4、入站，標(biāo)志域賦1，更新坐標(biāo)該坐標(biāo)西邊可有通路，該坐標(biāo)入站，標(biāo)志域賦1，更新坐標(biāo)3重點(diǎn)設(shè)計(jì)及編碼typedef structint mg200;int top;seqstack;typedef struct migongint m1;/存放墻int flag;/標(biāo)志域smaze2020;int empty(seqstack &s)/判棧空if(s.top=-1)return 0;elsereturn 1;void pop(seqstack &s,int &x1)/出棧if(s.top=-1)return ;x1=s.mgs.top;s.top-;void push(seq

5、stack &s,int y1,int x1)/入棧if(s.top=20)return ;s.top+;s.mgs.top=y1;s.top+;s.mgs.top=x1;void zumigong(seqstack &stack,smaze &maze,int &m,int &n)/走迷宮int i,j,cout;int x1,a,b,y1,x,y,x2,y2;printf("輸入入口的橫縱坐標(biāo)，空格隔開n");scanf("%d %d",&x,&y);printf("輸入出口的橫縱坐標(biāo)

6、，空格隔開n");scanf("%d %d",&x2,&y2);for(i=0;i<=m+1;i+)for(j=0;j<=n+1;j+)if(mazeij.m1=1)printf("");elseprintf("");printf("n");x1=x;y1=y;if(mazex1y1.m1=1)printf("此路不通：n");return ;if(mazex2y2.m1=1)printf("入口為墻。請(qǐng)重新輸入n");elsewhile

7、(x1!=x2|y1!=y2)if(mazex1y1+1.m1=0&&mazex1y1+1.flag=0)cout=0;elseif(mazex1+1y1.m1=0&&mazex1+1y1.flag=0)cout=1;elseif(mazex1-1y1.m1=0&&mazex1-1y1.flag=0)cout=2;elseif(mazex1y1-1.m1=0&&mazex1y1-1.flag=0)cout=3;elsecout=4;switch(cout)case 0:a=x1;b=y1;mazex1y1.flag=1;y1=y1

8、+1;push(stack,b,a);/列先入break;case 1:a=x1;b=y1;mazex1y1.flag=1;x1=x1+1;push(stack,b,a);break;case 2:a=x1;b=y1;mazex1y1.flag=1;x1=x1-1;push(stack,b,a);break;case 3:a=x1;b=y1;mazex1y1.flag=1;y1=y1-1;push(stack,b,a);break;case 4: mazex1y1.flag=1; if(empty(stack)!=0)pop(stack,x1);pop(stack,y1);break;else

9、printf("此路沒有通路：n");return ;push(stack,y2,x2);五測(cè)試數(shù)據(jù)及運(yùn)行結(jié)果1.正常測(cè)試數(shù)據(jù)和運(yùn)行結(jié)果1測(cè)試數(shù)據(jù)2,運(yùn)行結(jié)果1.坐標(biāo)形式2.矩陣形式3文件保存結(jié)果2. 異常測(cè)試數(shù)據(jù)及運(yùn)行結(jié)果六調(diào)試情況，設(shè)計(jì)技巧及體會(huì)1改進(jìn)方案設(shè)置標(biāo)志域使訪問判斷坐標(biāo)更方便。2.體會(huì)通過這段時(shí)間的課程設(shè)計(jì)，本人對(duì)計(jì)算機(jī)的應(yīng)用，數(shù)據(jù)結(jié)構(gòu)的作用以及C語言的使用都有了更深的了解。尤其是C語言的進(jìn)步讓我深刻的感受到任何所學(xué)的知識(shí)都需要實(shí)踐，沒有實(shí)踐就無法真正理解這些知識(shí)以及掌握它們，使其成為自己的財(cái)富。在理論學(xué)習(xí)和上機(jī)實(shí)踐的各個(gè)環(huán)節(jié)中，通過自主學(xué)習(xí)和請(qǐng)教老師，我收獲

10、了不少。當(dāng)然也遇到不少的問題，也正是因?yàn)檫@些問題引發(fā)的思考給我?guī)Я耸斋@。從當(dāng)初不喜歡上機(jī)寫程序到現(xiàn)在能主動(dòng)寫程序，從當(dāng)初拿著程序不只如何下手到現(xiàn)在知道如何分析問題，如何用專業(yè)知識(shí)解決實(shí)際問題的轉(zhuǎn)變，我發(fā)現(xiàn)無論是專業(yè)知識(shí)還是動(dòng)手能力，自己都有很大程度的提高。在這段時(shí)間里，我對(duì)for、while等的循環(huán)函數(shù)用法更加熟悉，逐漸形成了較好的編程習(xí)慣。在老師的指導(dǎo)幫助下，同學(xué)們課余時(shí)間的討論中，這些問題都一一得到了解決。在程序的調(diào)試能力上，無形中得到了許多的提高。例如：頭文件的使用，變量和數(shù)組的范圍問題，定義變量時(shí)出現(xiàn)的問題等等。在實(shí)際的上機(jī)操作過程中，不僅是讓我們了解數(shù)據(jù)結(jié)構(gòu)的理論知識(shí)，更重要的是培養(yǎng)

11、解決實(shí)際問題的能力，所以相信通過此次實(shí)習(xí)可以提高我們分析設(shè)計(jì)能力和編程能力，為后續(xù)課程的學(xué)習(xí)及實(shí)踐打下良好的基礎(chǔ)。在這次短短的課程實(shí)踐里，我們得到了李培老師的關(guān)心和幫助。她給了我們很多的信息，與我們一起探討問題，詢問我們遇到了哪些問題并耐心給予指導(dǎo)。當(dāng)我們遇到技術(shù)上難以解決的問題時(shí)，她就會(huì)指導(dǎo)我們解決問題7 參考文獻(xiàn)數(shù)據(jù)結(jié)構(gòu)C語言描述耿國(guó)華主編，高等教育社出版。#include<stdio.h>#include<stdlib.h>typedef structint mg200;int top;seqstack;typedef struct migongint m1;in

12、t flag;smaze2020;void inista(seqstack &s)s.top=-1;int empty(seqstack &s)if(s.top=-1)return 0;elsereturn 1;void pop(seqstack &s,int &x1)if(s.top=-1)return ;x1=s.mgs.top;s.top-;void push(seqstack &s,int y1,int x1)if(s.top=20)return ;s.top+;s.mgs.top=y1;s.top+;s.mgs.top=x1;void inre

13、ad(smaze &maze,int m,int n)char name20;int i,j;printf("輸入存放迷宮的文件名n");scanf("%s",name);FILE *fp=fopen(name,"rt");if(fp=NULL)printf("n打開文件%s失敗n");exit(1);for(i=1;i<m+1;i+) for(j=1;j<n+1;j+)fscanf(fp,"%d ",&mazeij.m1);if(mazeij.m1=0)mazeij

14、.flag=0;elsemazeij.flag=1;fclose(fp);for(i=0;i<=m+1;i+) mazei0.m1=1;mazei0.flag=1;/加兩堵列墻 mazein+1.m1=1;mazein+1.flag=1; for(j=0;j<=n+1;j+) /加兩堵行墻 maze0j.m1=1; mazem+1j.m1=1;maze0j.flag=1;mazem+1j.flag=1; for(i=0;i<=m+1;i+)for(j=0;j<=n+1;j+)if(mazeij.m1=1)printf("");elseprintf(&

15、quot;");printf("n");void zumigong(seqstack &stack,smaze &maze,int &m,int &n)int i,j,cout;int x1,a,b,y1,x,y,x2,y2;printf("輸入入口的橫縱坐標(biāo)，空格隔開n");scanf("%d %d",&x,&y);printf("輸入出口的橫縱坐標(biāo)，空格隔開n");scanf("%d %d",&x2,&y2);for(

16、i=0;i<=m+1;i+)for(j=0;j<=n+1;j+)if(mazeij.m1=1)printf("");elseprintf("");printf("n");x1=x;y1=y;if(mazex1y1.m1=1)printf("此路不通：n");return ;if(mazex2y2.m1=1)printf("入口為墻。請(qǐng)重新輸入n");elsewhile(x1!=x2|y1!=y2)if(mazex1y1+1.m1=0&&mazex1y1+1.flag=

17、0)cout=0;elseif(mazex1+1y1.m1=0&&mazex1+1y1.flag=0)cout=1;elseif(mazex1-1y1.m1=0&&mazex1-1y1.flag=0)cout=2;elseif(mazex1y1-1.m1=0&&mazex1y1-1.flag=0)cout=3;elsecout=4;switch(cout)case 0:a=x1;b=y1;mazex1y1.flag=1;y1=y1+1;push(stack,b,a);/列先入break;case 1:a=x1;b=y1;mazex1y1.flag

18、=1;x1=x1+1;push(stack,b,a);break;case 2:a=x1;b=y1;mazex1y1.flag=1;x1=x1-1;push(stack,b,a);break;case 3:a=x1;b=y1;mazex1y1.flag=1;y1=y1-1;push(stack,b,a);break;case 4: mazex1y1.flag=1; if(empty(stack)!=0)pop(stack,x1);pop(stack,y1);break;elseprintf("此路沒有通路：n");return ;push(stack,y2,x2);void

19、 print1(seqstack stack)char name20;int s120,s220,i=0,j=0,n=0;while(stack.top!=-1)n+;pop(stack,s1i);pop(stack,s2i);i+;j+;printf("以坐標(biāo)形式輸出迷宮路徑n");printf("迷宮路徑為:n");for(i=n-1;i>=1;i-)printf("<%d,%d> ",s1i,s2i);printf("<%d %d>n",s10,s20);printf("

20、;請(qǐng)輸入要保存路徑的文件名n");scanf("%s",name);FILE *fp=fopen(name,"wb");if(fp=NULL)printf("n打開文件%s失敗n",name);exit(1);fprintf(fp,"迷宮路徑：n");for(i=n-1;i>=0;i-)fprintf(fp,"<%d,%d> ",s1i,s2i);fclose(fp);printf("已成功保存于%s文件中",name);void print2(s

21、eqstack &stack,smaze &maze,int &m,int &n)int s120,s220,i=0,j=0,n1,n2;while(stack.top!=-1)pop(stack,s1i);pop(stack,s2j);n1=s1i;n2=s2j;mazen1n2.flag=2;i+;j+;printf("以形象的矩陣形式輸出迷宮路徑 ·表示走過的痕跡 表示迷宮路徑n");printf("如下所示n");for(i=0;i<=m+1;i+)for(j=0;j<=n+1;j+)if(m

22、azeij.m1=1)printf("");if(mazeij.m1=0&&mazeij.flag=0)printf("");if(mazeij.m1=0&&mazeij.flag=1)printf("·");if(mazeij.m1=0&&mazeij.flag=2)printf("");printf("n");void savefile(smaze maze,int &m,int &n) int i,j;char na

23、me20;printf("輸入迷宮：n");for(i=1;i<=m;i+)for(j=1;j<=n;j+)scanf("%d",&mazeij.m1);if(mazeij.m1=1)mazeij.flag=1;elsemazeij.flag=0;for(i=0;i<=m+1;i+) mazei0.m1=1;mazei0.flag=1;/加兩堵列墻 mazein+1.m1=1;mazein+1.flag=1; for(j=0;j<=n+1;j+) /加兩堵行墻 maze0j.flag=1; mazem+1j.flag=1;

24、maze0j.m1=1;mazem+1j.m1=1; printf("請(qǐng)輸入保存的文件名：n");scanf("%s",name);FILE *fp=fopen(name,"wt");if(fp=NULL)printf("n打開文件%s失敗n",name);exit(1);for(i=0;i<=m+1;i+)for(j=0;j<=n+1;j+)if(mazeij.m1=1)printf("");elseprintf("");printf("n"

25、);fprintf(fp,"迷宮路徑：n");for(i=1;i<=m;i+) for(j=1;j<=n;j+)fprintf(fp,"%d ",mazeij.m1);fputc('n',fp); fclose(fp);int print()int i;printf(" · n");printf(" · · n");printf(" · · n");printf(" · 軟件1班· n");printf(" · 付 · n");printf(" · 添 · n");printf(" · · n");print