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

數(shù)據(jù)結(jié)構(gòu)課程設(shè)計 3 3 1二、設(shè)計目的與任務(wù) 11、設(shè)計目的是 2、設(shè)計任務(wù)是 2三、設(shè)計方案與實施 21、總體設(shè)計思想 22、設(shè)計流程圖 33、詳細設(shè)計 44、程序清單 45、程序調(diào)試與體會 46、運行結(jié)果(截圖) 5 參考文獻 附件 隨著計算機的高速發(fā)展，計算機能很簡便地解決很多問題。C語言編程也是解決問題的一種語言。而此我們的數(shù)據(jù)結(jié)構(gòu)程序設(shè)計是解決迷宮問題。求迷宮(老鼠吃奶酪)中步一步完成的，從而找到的是最短路徑。Keywords:Queue,Breadth-first,search,Shortestpath,Traversal《數(shù)據(jù)結(jié)構(gòu)》課程設(shè)計----迷宮求解設(shè)計《數(shù)據(jù)結(jié)構(gòu)》是計算機科學與技術(shù)專業(yè)和信息管理與信息系統(tǒng)專業(yè)的必修課之一，是一門綜合性的專業(yè)基礎(chǔ)課。本課程較系統(tǒng)地介紹了軟件設(shè)計中常用的數(shù)據(jù)結(jié)構(gòu)以及相應(yīng)的實現(xiàn)算法，如線性表、棧、隊列、樹和二叉樹，圖、檢索和排序等，并對性能進行分析和比較，內(nèi)容非常豐富。本課程設(shè)計我們要解決的問題是圖迷宮求解問題。本需要用到棧的相關(guān)數(shù)據(jù)結(jié)構(gòu)。但我們這個程序沒有用棧，而是用隊列替代棧的功能，使程序運行效率更加高。還用到求迷宮問題最平常的數(shù)據(jù)結(jié)構(gòu)算法，即廣度優(yōu)先搜索算法(BFS),還保持了它的路徑，再從串中輸出圖。本課程設(shè)計總的思路要解決的問題是構(gòu)造迷宮，尋找路線，打印路徑。我們首先要做的是創(chuàng)建一個二維數(shù)組，用以來存儲圖，然后我們要想好怎樣利用BFS算法來尋找路線。把這個算法以及其他過程寫成調(diào)用函數(shù)，各自調(diào)用后調(diào)試程序。達到滿意結(jié)果后寫報告。二、設(shè)計目的與任務(wù)根據(jù)課堂講授內(nèi)容，學生做相應(yīng)的自主練習，消化數(shù)據(jù)結(jié)構(gòu)課堂所講解的內(nèi)容；通過調(diào)試典型例題或習題積累調(diào)試C程序的經(jīng)驗；通過完成輔導(dǎo)教材中的編程題，逐漸培養(yǎng)學生的編程能力、用計算機解決實際問題的能力、團體合作能力。它的任務(wù)就是訓練學生對計算機數(shù)據(jù)對象進行分析的能力，選擇適當?shù)臄?shù)據(jù)結(jié)構(gòu)及相關(guān)算法的能力。此程序的任務(wù)是實現(xiàn)把能走的最短(1)迷宮形狀由0表示可通過，用1表示是障礙。為方便用0,1輸入。并把迷宮圖形保存在二維數(shù)組Map中。而打印出的圖形中‘●’表示能過‘口’表示障礙.(2)對探索過的位置加以標記Used[J[],輸入起點終點后可由BFS()來完成搜索。到目的點就可退出該調(diào)用程序。把每步路徑保存到Mark[][]內(nèi)，通過反向進行退步可把完整的路徑保存在結(jié)構(gòu)體result數(shù)組re[][]內(nèi)，通過標記的路徑可將串str作相應(yīng)的改變(3)根據(jù)二維字符數(shù)組和加標記的位置坐標，輸出迷宮的圖形。(4)該程序在獲取迷宮圖結(jié)構(gòu)后，可對迷宮任意入口到出口的路線進行搜索，主要由廣度優(yōu)先搜索完成該操作。它可以是100以內(nèi)大小的迷宮，有自行提供的迷宮圖，本課程設(shè)計是以二維數(shù)組作為迷宮的存儲結(jié)構(gòu)。而廣度優(yōu)先搜索(BFS)用的隊列一步一步完成的，從而找到的是最短路徑；該程序還能選擇是4方向還是8方向的迷宮走法。并開始開始輸入迷宮圖形輸入起點終點輸出路徑節(jié)點輸出迷宮路線是否繼續(xù)?是否更換迷宮結(jié)束這個結(jié)構(gòu)體是用來做廣度搜索的對每個迷宮節(jié)點有相應(yīng)的s(最短的步數(shù)，當然有些是不可達的)intmove[8][2]={{1,0},{0,1},{-1,0},{0,-1},{1,1},{-1,-1},{1,-1}intBFS(intstep)//廣度搜索用來算出最短路徑的走法并將走法保存在re數(shù)組結(jié)構(gòu)體中intFormat_Limit()//圖形打印格式限制intPPMFO//打印出迷宮圖形intSave_Path()//將路徑保存在str[][]中并打印出路徑迷宮圖形intInit()//從文件中植入數(shù)據(jù)完成對Map迷宮圖的結(jié)構(gòu)intJudge()//判斷輸入的起點終點是否符合實際intmainO//對上面函數(shù)的結(jié)合應(yīng)用4、程序清單見附件調(diào)試：在我組的集體努力下，課程設(shè)計終于完成，由于我們對數(shù)據(jù)結(jié)構(gòu)和c語言不是很了解，有時忽略了一些關(guān)鍵的細節(jié)，使得在編寫程序的過程中出現(xiàn)了一些問題。對于打字有時粗心導(dǎo)致出現(xiàn)一些難以發(fā)現(xiàn)的小錯誤，在我們的耐心，細致的調(diào)試下最終使得程序能夠運行，課程設(shè)計完滿完工。原因：把相關(guān)重要的變量重復(fù)定義以至賦過的值被覆蓋確定在復(fù)雜的事也變的簡單了。由于本程序較大，調(diào)試6、運行結(jié)果(截圖)“E:\數(shù)居結(jié)構(gòu)\Debug\迷宮求解，exe?請按任意鍵繼續(xù)...“E\數(shù)居結(jié)構(gòu)\Debug\迷宮求解.exe”X請按任意鍵繼續(xù)..."E:\數(shù)據(jù)結(jié)構(gòu)\Debug\迷宮求解.exe'到目的地了步數(shù)：68易一(2.請按任意鍵繼續(xù).,.c之個之個-(13,0)<-請按任意鍵繼續(xù)...是否使用系統(tǒng)提供的迷宮圖：(Y/N)請按任意鍵繼續(xù)...請按任意鍵繼續(xù)...[迷宮路徑圖]請輸入迷宮的結(jié)構(gòu)o,1表示0是路1是墻請按任意鍵繼續(xù)...[迷宮路徑圖’起起請按任意鍵繼續(xù)..“E:\數(shù)據(jù)結(jié)構(gòu)\Debug\迷宮求解.exe”是否顯示原始迷宮：(Y/N)請輸入起點與終點：(x1y1x2y2)001211終點越界，不符合!是則再輸入\否則退出程序：(Y/N)起點是墻，不符合!是則再輸入\否則退出程序：(Y/N)終點是墻，不符合!是則再輸入\否則退出程序：(Y/N)請輸入起點與終點：(x1y1x2y2)111200起點越界，不符合!是則再輸入\否則退出程序：(Y/N)請選擇4方向還是8方向的迷宮：8請按任意鍵繼續(xù)...要真正做出一個程序并不很容易，但只要用心去做，總會有收獲，特別是當我遇到一個問題，想辦法去解決，最后終于找到方法時，刻的體會到它的游戲可玩性。通過本次課程設(shè)計我們發(fā)現(xiàn)我們對于C語言和數(shù)據(jù)結(jié)構(gòu)還的資料和書籍，使我們的課設(shè)能夠按時順利的完成。還有周國柱同學全面承擔本次課程同時也感謝學校給我們這次機會，訓練我們靈活應(yīng)用所學數(shù)據(jù)結(jié)構(gòu)知識，獨立完成問題分析的能力，讓我們學會怎樣結(jié)合數(shù)據(jù)結(jié)構(gòu)理論知識去解決實際問題。學出版社年22期年11期[5]編程愛好者網(wǎng)站(迷宮問題)[6]編程論壇/thread-247790-1-7.html(迷宮問題){{intx,y,S;boolMap[100][100];/輸入0,1表示迷宮move[8][2]={{1,0},{0,1},{-1,0},{0,-1},{1,1},{-1,-1},{1,-1}intBFS(intstep)//廣度搜索用來算出最短路徑的走法并將走法保存在re結(jié)構(gòu)體中{while(!My.emptyO)My.for(intj=1;j<=s1.s;j++)printf("(%2d,%2d)<-",sl.x,sl.if(temp.x<0|temp.x>=n|temp.y<0|temp.y>=n||Used[temp.x][temp.yUsed[temp.x][temp.y]charstr[256*256][3];//串保存圖intInitialization()//將str]]圖形初始化1}intFormat_Limit()//圖形打印格式限制{}intPrint_Maze_Figure()//打印{for(xi=0,xj=0;xj<((2*n-1)*(2{printf("%s",str[xj]intPPMFO//打印出迷宮圖形{printf("fititt[迷宮為]nittit●表可走，口表不可走\n");intSave_Path)//將路徑保存在str[J[]中并打印出路徑迷宮圖形{printf("\t\t\t[迷宮路徑圖]n(%d,%d)至(%d,%d)t\t●表可走，口表不可走\n",s.x,s.y,t.x,t.y);strcpy(str[2*t.x*(2*n-1)+2*t.y],"終");if(re[wri].rx<re[wri+1].rx&&re[wri].rstrcpy(str[2*re[wri].rx*(2*n-1)+(2*n-1)+2*re[wri].ry],"tif(re[wri].rx=re[wri+1]rx&&re[wri]strcpy(str[2*re[wri].rx*(2*n-1)+2if(re[wri].rx>re[wri+1].rx&&re[wri].strcpy(str[2*re[wri].rx*(2*n-1)-(2*n-if(re[wri].rx==re[wri+1].rx&&re[wri]if(re[wri].rx<re[wri+1].rx&&re[wri]strcpy(str[2*re[wri].rx*(2*n-1)+(2*n-1if(re[wri].rx<re[wri+1].rx&&re[wri]strcpy(str[2*re[wri].rx*(2*n-1)+(2*n-1)-if(re[wri].rx>re[wri+1].rx&&re[wri].strcpy(str[2*re[wri].rx*(2*n-1)-(2*n-2if(re[wri].rx>re[wri+1].rx&&re[wri].strcpy(str[2*re[wri].rx*(2*n-1)-(2*n-1)-intInit()//從文件中植入數(shù)據(jù)完成對Map迷宮圖的結(jié)構(gòu){pf=fopen("maze.txt","r");了intJudge()//判斷輸入的起點終點是否符合實際{}{{printf("請選擇4方向還是8方向的迷宮：");printf("是否繼續(xù)(Y/N)\n");