數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)迷宮求解

1、26湖南人文科技學(xué)院課程設(shè)計(jì)湖南人文科技學(xué)院計(jì)算機(jī)系數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)課程名稱:數(shù)據(jù)結(jié)構(gòu)課程代碼:題 目:迷宮求解年級(jí)/專業(yè)/班:09級(jí)計(jì)算機(jī)科學(xué)與技術(shù)1班學(xué)生姓名:學(xué) 號(hào) :指導(dǎo)老師:開(kāi)題時(shí)間:2010-12-21完成時(shí)間:2010-12-26目 錄摘 要3abstract3一、引 言1二、設(shè)計(jì)目的與任務(wù)11、設(shè)計(jì)目的是12、設(shè)計(jì)任務(wù)是2三、設(shè)計(jì)方案與實(shí)施21、總體設(shè)計(jì)思想22、設(shè)計(jì)流程圖33、詳細(xì)設(shè)計(jì)44、程序清單45、程序調(diào)試與體會(huì)46、運(yùn)行結(jié)果（截圖）5五、致 謝13參考文獻(xiàn)14附件14摘 要隨著計(jì)算機(jī)的高速發(fā)展，計(jì)算機(jī)能很簡(jiǎn)便地解決很多問(wèn)題。c語(yǔ)言編程也是解決問(wèn)題的一種語(yǔ)言。而此我們的

2、數(shù)據(jù)結(jié)構(gòu)程序設(shè)計(jì)是解決迷宮問(wèn)題。求迷宮(老鼠吃奶酪)中從入口到出口的路徑是一個(gè)經(jīng)典的程序設(shè)計(jì)問(wèn)題。“數(shù)據(jù)結(jié)構(gòu)”成為計(jì)算機(jī)程序設(shè)計(jì)的重要理論技術(shù)基礎(chǔ)，它不僅是計(jì)算機(jī)學(xué)科的核心課程，而且已成為其它理工專業(yè)的熱門選修課。主要包括線性表、樹(shù)和二叉樹(shù)以及圖等基本類型的數(shù)據(jù)結(jié)構(gòu)。數(shù)據(jù)結(jié)構(gòu)是一門研究非數(shù)值計(jì)算的程序設(shè)計(jì)問(wèn)題中計(jì)算機(jī)的操作對(duì)象以及它們之間的關(guān)系和運(yùn)算等的學(xué)科，包括數(shù)據(jù)的邏輯結(jié)構(gòu)、數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)和數(shù)據(jù)的運(yùn)算這三個(gè)方面的內(nèi)容，其中邏輯結(jié)構(gòu)可分為線性結(jié)構(gòu)和非線性結(jié)構(gòu)；存儲(chǔ)結(jié)構(gòu)可分為順序存儲(chǔ)和鏈?zhǔn)酱鎯?chǔ)兩類，圖則屬于邏輯結(jié)構(gòu)中的非線性結(jié)構(gòu)。廣度優(yōu)先搜索(bfs)用的隊(duì)列一步一步完成的，從而找到的是最短路

3、徑。關(guān)鍵詞：隊(duì)列，廣度優(yōu)先，搜索，最短路徑，遍歷abstractwith the rapid development of the computer,the computer can very easily solve many problems. c programming language is a language problem. our data structure and this program is designed to solve maze problems.find the maze(mouse eat cheese) to the exit path from the

4、entrance is a classic programming problem.data structure has become the important theory and the foundation of computer programming.it is not only the core curriculum of computer science,but also has became the hottest elective course of other tech professional. mainly including linear list, trees a

5、nd binary tree and graph, and other basic types of data structure.data structure is the study of the non-numerical calculation program design problem in computer operation objects and their relationship and operation，including data logical structure, data storage structure and the data of operation

6、this three aspects, and the logical structure can be divided into linear structure and nonlinear structure.storage structure can be divided into sequenced store and chain store two kinds.graph belongs to the logical structure of nonlinear structure.it is breadth-first search (bfs) with the queue for

7、 find the shortest path1、總體設(shè)計(jì)思想(1) 迷宮形狀由0表示可通過(guò)，用1表示是障礙。為方便用0,1輸入。并把迷宮圖形保存在二維數(shù)組map中。而打印出的圖形中 表示能過(guò)表示障礙.(2) 對(duì)探索過(guò)的位置加以標(biāo)記used，輸入起點(diǎn)終點(diǎn)后可由bfs（）來(lái)完成搜索。到目的點(diǎn)就可退出該調(diào)用程序。把每步路徑保存到mark內(nèi)，通過(guò)反向進(jìn)行退步可把完整的路徑保存在結(jié)構(gòu)體result數(shù)組re內(nèi)，通過(guò)標(biāo)記的路徑可將串str作相應(yīng)的改變就能輸出的帶路徑的圖。(3) 根據(jù)二維字符數(shù)組和加標(biāo)記的位置坐標(biāo)，輸出迷宮的圖形。(4) 該程序在獲取迷宮圖結(jié)構(gòu)后，可對(duì)迷宮任意入口到出口的路線進(jìn)行搜索，主要

8、由廣度優(yōu)先搜索完成該操作。它可以是100以內(nèi)大小的迷宮，有自行提供的迷宮圖，本課程設(shè)計(jì)是以二維數(shù)組作為迷宮的存儲(chǔ)結(jié)構(gòu)。而廣度優(yōu)先搜索(bfs)用的隊(duì)列一步一步完成的，從而找到的是最短路徑；該程序還能選擇是4方向還是8方向的迷宮走法。并能輸出打印2、設(shè)計(jì)流程圖開(kāi)始輸入迷宮圖形顯示迷宮圖形輸入起點(diǎn)終點(diǎn)是否符合題意輸出路徑節(jié)點(diǎn)輸出迷宮路線是否繼續(xù)？是否更換迷宮結(jié)束3、詳細(xì)設(shè)計(jì)struct pointint x,y,s;這個(gè)結(jié)構(gòu)體是用來(lái)做廣度搜索的對(duì)每個(gè)迷宮節(jié)點(diǎn)有相應(yīng)的s(最短的步數(shù)，當(dāng)然有些是不可達(dá)的)int move82 = 1,0,0,1,-1,0,0,-1,1,1,-1,-1,1,-1,-1,

9、1 ;/int bfs(int step)/ 廣度搜索用來(lái)算出最短路徑的走法 并將走法保存在re數(shù)組結(jié)構(gòu)體中int initialization()/ 將str圖形初始化int format_limit()/圖形打印格式限制int print_maze_figure()/打印出圖形int ppmf()/ 打印出迷宮圖形int save_path()/ 將路徑保存在str中并打印出路徑迷宮圖形int init()/ 從文件中植入數(shù)據(jù) 完成對(duì)map迷宮圖的結(jié)構(gòu)int judge()/判斷輸入的起點(diǎn)終點(diǎn)是否符合實(shí)際int main()/對(duì)上面函數(shù)的結(jié)合應(yīng)用4、程序清單見(jiàn)附件5、程序調(diào)試與體會(huì)調(diào)試：在

10、我組的集體努力下，課程設(shè)計(jì)終于完成，由于我們對(duì)數(shù)據(jù)結(jié)構(gòu)和c語(yǔ)言不是很了解，有時(shí)忽略了一些關(guān)鍵的細(xì)節(jié)，使得在編寫程序的過(guò)程中出現(xiàn)了一些問(wèn)題。對(duì)于打字有時(shí)粗心導(dǎo)致出現(xiàn)一些難以發(fā)現(xiàn)的小錯(cuò)誤，在我們的耐心，細(xì)致的調(diào)試下最終使得程序能夠運(yùn)行，課程設(shè)計(jì)完滿完工。1、問(wèn)題一：求出起點(diǎn)到終點(diǎn)的路徑 現(xiàn)象：求出的結(jié)果總是無(wú)任何現(xiàn)象原因：把相關(guān)重要的變量重復(fù)定義以至賦過(guò)的值被覆蓋2、 問(wèn)題二：常量轉(zhuǎn)義字符現(xiàn)象：出現(xiàn)不正常字符常量原因：字符常量形式弄錯(cuò)3、問(wèn)題三：輸入起點(diǎn)終點(diǎn)時(shí)，未判斷下標(biāo)越界就使用數(shù)據(jù)現(xiàn)象： 原因：未判斷下標(biāo)越界就使用數(shù)據(jù)體會(huì)：在復(fù)雜的程序，都可以拆成一個(gè)個(gè)簡(jiǎn)單的小部分，逐個(gè)擊破，再拼湊起來(lái)，在復(fù)

11、雜的事也變的簡(jiǎn)單了。由于本程序較大，調(diào)試時(shí)多人協(xié)作能更容易找出程序的錯(cuò)誤并修改。6、運(yùn)行結(jié)果（截圖）將程序員錄入后,讓其運(yùn)行。將會(huì)出現(xiàn)一個(gè)菜單的界面，執(zhí)行各種操作均有其對(duì)應(yīng)的代碼。要執(zhí)行何種操作只需輸入對(duì)應(yīng)的指令即可進(jìn)行，在每步操作后均會(huì)有相應(yīng)的提示。操作簡(jiǎn)單方便實(shí)用，下面即為一些操作的示意圖。運(yùn)行程序后出界面，運(yùn)行結(jié)果如圖所示。#include #include #include #include / 這個(gè)是stl 它是一個(gè)方便的東西 #include #include using namespace std;struct result int rx,ry;re100*100;int ri=

12、-1;struct pointint x,y,s;s,t;/s代表起點(diǎn) t代表終點(diǎn)int mark100100; /用來(lái)標(biāo)記怎么走到這個(gè)地方的 (保存的是方向的序號(hào)):0,1,2,3,4,5,6,7bool used100100;/標(biāo)記已經(jīng)走過(guò)的地方bool map100100;/輸入0，1表示迷宮int move82 = 1,0,0,1,-1,0,0,-1,1,1,-1,-1,1,-1,-1,1 ;/int n,m;int bfs(int step) / 廣度搜索用來(lái)算出最短路徑的走法 并將走法保存在re結(jié)構(gòu)體中queue my;s.s =0;while(!my.empty()my.pop(

13、);my.push(s);point temp,s1;while(!my.empty()s1 = my.front();my.pop();if(s1.x = t.x&s1.y=t.y)int u;re+ri.rx=s1.x; reri.ry=s1.y;printf(到目的地了n步數(shù):%dn(%2d,%2d) - ,s1.s,s1.x,s1.y);for(int j = 1 ;j = s1.s;j+)u = s1.x;s1.x = s1.x - move marks1.xs1.y0;s1.y = s1.y - move markus1.y 1;re+ri.rx=s1.x; reri.ry=s1.

14、y;printf(%2d,%2d) - ,s1.x,s1.y);if(j+1)%5=0)printf(n);printf(n);system(pause); system(cls);return 1;for(int i =0 ;i step ; i+)temp.x = s1.x + movei0;temp.y = s1.y + movei1;temp.s = s1.s;if(temp.x=n|temp.y=n|usedtemp.xtemp.y|maptemp.xtemp.y)continue;elsemarktemp.xtemp.y = i;temp.s += 1 ;my.push(temp)

15、;usedtemp.xtemp.y = true;printf(不好意思,起點(diǎn)至終點(diǎn)無(wú)路徑不可達(dá)!n);return 0;char str256*2563; /串保存圖int initialization()/ 將str圖形初始化int i1,j1,xj;for(i1=0;i1256*256;i1+) strcpy(stri1, );for(i1=0;i1n;i1+)for(j1=0,xj=0;xjn;j1=j1+2,xj+)if(mapi1xj = 0) strcpy(str2*i1*(2*n-1)+j1,);else strcpy(str2*i1*(2*n-1)+j1,);return 1

16、;int format_limit()/圖形打印格式限制for(int i =0; i 0;i+)printf( );return 1;int print_maze_figure()/打印出圖形int i,xi,xj;format_limit();for(i =0 ;i = n*2;i+)printf();printf(n);for(xi=0,xj=0;xj(2*n-1)*(2*n-1);xj+,xi+)if(0 = xi)format_limit();printf(); printf(%s,strxj); if(xi=2*n-2) printf(n);xi=-1; format_limit(

17、);for(i =0 ;i = n*2 ;i+)printf();printf(n);return 1;int ppmf()/ 打印出迷宮圖形printf(tttt迷宮為nttt 表可走，表不可走 n);initialization();print_maze_figure();return 1;int save_path()/ 將路徑保存在str中并打印出路徑迷宮圖形printf(ttt 迷宮路徑圖n(%d,%d)至(%d,%d)tt 表可走，表不可走 n,s.x,s.y,t.x,t.y);initialization();strcpy(str2*s.x*(2*n-1)+2*s.y,起);st

18、rcpy(str2*t.x*(2*n-1)+2*t.y,終);for(int wri=0;wriri;wri+) if(rewri.rxrewri+1.rx&rewri.ry=rewri+1.ry) strcpy(str2*rewri.rx*(2*n-1)+(2*n-1)+2*rewri.ry,); if(rewri.rx=rewri+1.rx&rewri.ryrewri+1.rx&rewri.ry=rewri+1.ry) strcpy(str2*rewri.rx*(2*n-1)-(2*n-1)+2*rewri.ry,); if(rewri.rx=rewri+1.rx&rewri.ryrewr

19、i+1.ry) strcpy(str2*rewri.rx*(2*n-1)+2*rewri.ry-1,); if(rewri.rxrewri+1.rx&rewri.ryrewri+1.ry) strcpy(str2*rewri.rx*(2*n-1)+(2*n-1)+1+2*rewri.ry,); if(rewri.rxrewri+1.ry) strcpy(str2*rewri.rx*(2*n-1)+(2*n-1)-1+2*rewri.ry,); if(rewri.rxrewri+1.rx&rewri.ryrewri+1.rx&rewri.ryrewri+1.ry) strcpy(str2*rew

20、ri.rx*(2*n-1)-(2*n-1)-1+2*rewri.ry,); print_maze_figure();return 1;/隊(duì)列int init()/ 從文件中植入數(shù)據(jù) 完成對(duì)map迷宮圖的結(jié)構(gòu)file *pf;int i,j;pf = fopen(maze.txt,r);if(pf=null)return 0;fscanf(pf,%d,&n);for(i = 0;i n; i+)for(j = 0 ; j n; j+)usedij = false;fscanf(pf,%d,&mapij);fclose(pf);return 1;int judge()/判斷輸入的起點(diǎn)終點(diǎn)是否符合實(shí)

21、際bool flag = true;if(s.x=n|s.y=n)printf(起點(diǎn)越界,不符合!n);flag = false;else if(t.x=n|t.y=n)printf(終點(diǎn)越界,不符合!n);flag = false;else if(maps.xs.y)printf(起點(diǎn)是墻,不符合!n);flag = false;else if(mapt.xt.y)printf(終點(diǎn)是墻,不符合!n);flag = false;else if(s.x=t.x&s.y=t.y)printf(起點(diǎn)是終點(diǎn),不符合!n);flag = false;if(!flag)printf(是則再輸入否則退出程

22、序:(y/n)n);char ch20;scanf(%s,ch);if(ch0 = y|ch0 =y)return 1;else return 0;return 2;int main()char ch;int i,j,step;printf(tttn);next:system(pause); system(cls); printf(是否使用系統(tǒng)提供的迷宮圖:(y/n)n); ch = getch(); if(ch = y|ch =y) init(); else printf(請(qǐng)輸入迷宮的大小:(n*n);scanf(%d,&n);printf(t請(qǐng)輸入迷宮的結(jié)構(gòu)0,1表示0是路1是墻n);fo

23、r(i = 0;i n; i+)for(j = 0 ; j n; j+)usedij = false;scanf(%d,&mapij); bool flag=true;while(flag)for(i =0 ;i n;i+)for(j =0 ;j n ;j+)usedij = false;ri = -1;system(pause);system(cls);printf(是否顯示原始迷宮:(y/n)n);ch = getch();if(ch = y|ch =y)ppmf();again:printf(請(qǐng)輸入起點(diǎn)與終點(diǎn):(x1 y1 x2 y2);scanf(%d %d %d %d,&s.x,&s

24、.y,&t.x,&t.y);if(1=judge()goto again;elseif(0=judge()break;printf(請(qǐng)選擇4方向還是8方向的迷宮:);scanf(%d,&step);if(8=step)step=8;else step = 4;system(pause);system(cls);bfs(step);save_path();printf(是否繼續(xù)(y/n)n);ch = getch();if(ch != y&ch !=y) flag = false;if(flag)printf(是否更換迷宮(y/n)n);ch = getch();if(ch = y|ch =y)

25、goto next;return 0;/*測(cè)試?yán)?0 0 0 0 01 1 1 1 00 0 0 0 00 1 1 1 10 0 0 0 00 0 4 4 4160 0 0 0 0 0 0 0 0 0 0 0 0 0 0 01 1 1 1 1 1 1 1 1 1 1 1 1 1 1 00 0 0 0 0 0 0 0 0 0 0 0 0 0 1 00 1 1 1 1 1 1 1 1 1 1 1 1 0 1 00 1 0 0 0 0 0 0 0 0 0 0 1 0 1 00 1 0 1 1 1 1 1 1 1 1 0 1 0 1 00 1 0 1 0 0 0 0 0 0 1 0 1 0 1 00

26、 1 0 1 0 1 1 1 1 0 1 0 1 0 1 00 1 0 1 0 1 0 1 1 0 1 0 1 0 1 00 1 0 1 0 1 0 0 0 0 1 0 1 0 1 00 1 0 1 0 1 1 1 1 1 1 0 1 0 1 00 1 0 1 0 0 0 0 0 0 0 0 1 0 1 00 1 0 1 1 1 1 1 1 1 1 1 1 0 1 00 1 0 0 0 0 0 0 0 0 0 0 0 0 1 00 1 1 1 1 1 1 1 1 1 1 1 1 1 1 00 0 0 0 0 0 0 0 0 0 0 0 0 0 0 00 0 8 6 40 1 0 1 0 1 0 1 0 1 0 1 0 1 0 11 0 1 0 1 0 1 0 1 0 1 0 1 0 1 00 1 0 1 0 1 0 1 0 1 0 1 0 1 0 11 0 1 0 1 0 1 0 1 0 1 0 1 0 1 00 1 0 1 0 1 0 1 0 1 0 1 0 1 0 11 0 1 0 1 0 1 0 1 0 1 0 1 0 1 00 1 0 1 0 1 0 1 0 1 0 1 0 1 0 11 0 1 0 1 0 1 0 1 0 1 0 1 0 1 00 1 0 1 0 1 0 1 0 1 0 1 0 1 0 11 0 1 0 1 0 1 0 1 0 1 0 1 0 1 00