數(shù)據(jù)結構迷宮求解(代碼參數(shù))課程設計

棗莊學院信息科學與工程學院

課程設計任務書題目： 迷宮求解課程設計 學號： 姓名： 專業(yè)：網(wǎng)絡工程 課程：數(shù)據(jù)結構 指導教師： 職稱： 完成時間：2011年12月----2011年12月棗莊學院信息科學與工程學院制年月日課程設計任務書及成績評定課程設計的任務和具體要求根據(jù)課堂講授內(nèi)容，學生做相應的自主練習，消化數(shù)據(jù)結構課堂所講解的內(nèi)容；通過調(diào)試典型例題或習題積累調(diào)試C程序的經(jīng)驗；通過完成輔導教材中的編程題，逐漸培養(yǎng)學生的編程能力、用計算機解決實際問題的能力、團體合作能力。它的任務就是訓練學生對計算機數(shù)據(jù)對象進行分析的能力，選擇適當?shù)臄?shù)據(jù)結構及相關算法的能力。此程序的任務是實現(xiàn)把能走的最短路找到，并很直觀的顯示在屏幕上的功能。指導教師簽字：_ 、— 日期：_指導教師評語成績： 指導教師簽字： 日期：

課程設計所需軟件、硬件等電腦、C++6.0課程設計進度計劃起至日期工作內(nèi)容備注參考文獻、資料索引序號文獻、資料名稱編著者出版單位數(shù)據(jù)結構 蔣秀英，欒曉春，燕孝飛中國石油大學出版社數(shù)據(jù)結構（C語言版）[M], 嚴蔚敏等清華大學出版社數(shù)據(jù)結構一用面向對象方法與C++描述，殷人昆等 清華大學出版社編程愛好者網(wǎng)站（迷宮問題）編程論壇/thread-247790T-7.html（迷宮問題）TOC\o"1-5"\h\z摘要 2\o"CurrentDocument"1引言 3\o"CurrentDocument"2設計目的與任務 3\o"CurrentDocument"2.1設計目的是 3\o"CurrentDocument"2.2設計任務是 4\o"CurrentDocument"3設計方案與實施 4\o"CurrentDocument"3.1總體設計思想 4\o"CurrentDocument"3.2設計流程圖 5\o"CurrentDocument"3.3詳細設計 6\o"CurrentDocument"3.4程序清單 6\o"CurrentDocument"3.5程序調(diào)試與體會 6\o"CurrentDocument"3.6運行結果（截圖） 7結論 15致謝 15隨著計算機的高速發(fā)展，計算機能很簡便地解決很多問題。C語言編程也是解決問題的一種語言。而此我們的數(shù)據(jù)結構程序設計是解決迷宮問題。求迷宮(老鼠吃奶酪)中從入口到出口的路徑是一個經(jīng)典的程序設計問題?！皵?shù)據(jù)結構”成為計算機程序設計的重要理論技術基礎，它不僅是計算機學科的核心課程，而且已成為其它理工專業(yè)的熱門選修課。主要包括線性表、樹和二叉樹以及圖等基本類型的數(shù)據(jù)結構。數(shù)據(jù)結構是一門研究非數(shù)值計算的程序設計問題中計算機的操作對象以及它們之間的關系和運算等的學科，包括數(shù)據(jù)的邏輯結構、數(shù)據(jù)的存儲結構和數(shù)據(jù)的運算這三個方面的內(nèi)容，其中邏輯結構可分為線性結構和非線性結構；存儲結構可分為順序存儲和鏈式存儲兩類，圖則屬于邏輯結構中的非線性結構。廣度優(yōu)先搜索(BFS)用的隊列一步一步完成的，從而找到的是最短路徑。關鍵詞：隊列，廣度優(yōu)先，搜索，最短路徑，遍歷1引言《數(shù)據(jù)結構》是計算機科學與技術專業(yè)和信息管理與信息系統(tǒng)專業(yè)的必修課之一，是一門綜合性的專業(yè)基礎課。本課程較系統(tǒng)地介紹了軟件設計中常用的數(shù)據(jù)結構以及相應的實現(xiàn)算法，如線性表、棧、隊列、樹和二叉樹，圖、檢索和排序等，并對性能進行分析和比較，內(nèi)容非常豐富。本課程設計我們要解決的問題是圖迷宮求解問題。本需要用到棧的相關數(shù)據(jù)結構。但我們這個程序沒有用棧，而是用隊列替代棧的功能，使程序運行效率更加高。還用到求迷宮問題最平常的數(shù)據(jù)結構算法，即廣度優(yōu)先搜索算法(BFS)，還保持了它的路徑，再從串中輸出圖。本課程設計總的思路要解決的問題是構造迷宮，尋找路線，打印路徑。我們首先要做的是創(chuàng)建一個二維數(shù)組，用以來存儲圖，然后我們要想好怎樣利用BFS算法來尋找路線。把這個算法以及其他過程寫成調(diào)用函數(shù)，各自調(diào)用后調(diào)試程序。達到滿意結果后寫報告。2設計目的與任務2.1設計目的是根據(jù)課堂講授內(nèi)容，學生做相應的自主練習，消化數(shù)據(jù)結構課堂所講解的內(nèi)容；通過調(diào)試典型例題或習題積累調(diào)試C程序的經(jīng)驗；通過完成輔導教材中的編程題，逐漸培養(yǎng)學生的編程能力、用計算機解決實際問題的能力、團體合作能力。2.2設計任務是它的任務就是訓練學生對計算機數(shù)據(jù)對象進行分析的能力，選擇適當?shù)臄?shù)據(jù)結構及相關算法的能力。此程序的任務是實現(xiàn)把能走的最短路找到，并很直觀的顯示在屏幕上的功能。3設計方案與實施3.1總體設計思想迷宮形狀由0表示可通過，用1表示是障礙。為方便用0,1輸入。并把迷宮圖形保存在二維數(shù)組Map中。而打印出的圖形中‘?'表示能過‘□'表示障礙.對探索過的位置加以標記Used[][],輸入起點終點后可由BFS()來完成搜索。到目的點就可退出該調(diào)用程序。把每步路徑保存到Mark[][]內(nèi)，通過反向進行退步可把完整的路徑保存在結構體result數(shù)組re[][]內(nèi)，通過標記的路徑可將串str作相應的改變就能輸出的帶路徑的圖。根據(jù)二維字符數(shù)組和加標記的位置坐標，輸出迷宮的圖形。該程序在獲取迷宮圖結構后，可對迷宮任意入口到出口的路線進行搜索，主要由廣度優(yōu)先搜索完成該操作。它可以是100以內(nèi)大小的迷宮，有自行提供的迷宮圖，本課程設計是以二維數(shù)組作為迷宮的存儲結構。而廣度優(yōu)先搜索(BFS)用的隊列一步一步完成的，從而找到的是最短路徑；該程序還能選擇是4方向還是8方向的迷宮走法。并能輸出打印

3.2設計流程圖3.3詳細設計struetPoint{intx,y,s;}這個結構體是用來做廣度搜索的對每個迷宮節(jié)點有相應的s（最短的步數(shù)，當然有些是不可達的）intmove[8][2]={{1,0},{0,1},{—1,0},{0,—1},{1,1},{—1,—1},{1,—1},{—1,1}};//intBFS(intstep)//廣度搜索用來算出最短路徑的走法并將走法保存在re數(shù)組結構體中intInitialization()//將str[][]圖形初始化intFormat_Limit()//圖形打印格式限制intPrint_Maze_Figure()//打印出圖形intPPMF()//打印出迷宮圖形intSave_Path()//將路徑保存在str[][]中并打印出路徑迷宮圖形intInit()//從文件中植入數(shù)據(jù)完成對Map迷宮圖的結構intJudge()//判斷輸入的起點終點是否符合實際intmain()//對上面函數(shù)的結合應用3.4程序清單#include<stdlib.h>#include<iostream>#include<string>#include〈queue〉//這個是stl它是一個方便的東西#include<fstream>#include<conio.h>usingnamespacestd;struetresult{intrx,ry;}re[100*100];intri=-1;struetPoint{intx,y,s;}s,t;//s代表起點t代表終點intmark[100][100];//用來標記怎么走到這個地方的(保存的是方向的序號)：0,1,2,3,4,5,6,7boolUsed[100][100];//標記已經(jīng)走過的地方boolMap[100][100];//輸入0,1表示迷宮intmove[8][2]={{1,0},{0,1},{—1,0},{0,—1},{1,1},{—1,—1},{1,—1},{—1,1}};//intn,m;intBFS(intstep)//廣度搜索用來算出最短路徑的走法并將走法保存在re結構體中{queue<Point>My;s.s=0;while(!My.empty())My.pop();My.push(s);Pointtemp,sl;while(!My.empty()){s1=My.front();My.popO;if(sl.x==t.x&&sl.y二二t.y){intu;re[++ri].rx二sl.x;re[ri].ry二sl.y;printf(“到目的地了\n步數(shù):％d\n(%2d,%2d)〈- "，s1.s,s1.x,s1.y);for(intj二1;j<=s1.s;j++){u=s1.x;s1.x=s1.x-move[mark[s1.x][s1.y]][0];s1.y=s1.y-move[mark[u][s1.y]][1];re[++ri].rx二s1.x;re[ri].ry=s1.y;printf(“(％2d,%2d)〈- "，s1.x,s1.y);if((j+1)%5==0)printf("\n");}printf("\n");system("pause");system("cls");return1;}for(inti=0;i<step;i++)temp.x=sl.x+move[i][0];temp.y=sl.y+move[i][l];temp.s=sl.s;if(temp.x<0||temp.x>二n||temp.y<0||temp.y>二n||Used[temp.x][temp.y]||Map[temp.x][temp.y])continue;else{mark[temp.x][temp.y]=i;temp.s+=1;My.push(temp);Used[temp.x][temp.y]=true;}}}printf("不好意思，起點至終點無路徑不可達?。。?！\n");return0;}charstr[256*256][3]; //串保存圖intInitialization()//將str[][]圖形初始化{intil,jl,xj;for(il=0;il<256*256;il++)strcpy(str[il],"");for(il=O;il<n;il++){for(jl=0,xj=0;xj<n;jl二jl+2,xj++){if(Map[il][xj]==0)strcpy(str[2*il*(2*nT)+jl],"?")；elsestrcpy(str[2*il*(2*nT)+jl],"D");}}return1;}intFormat_Limit()//圖形打印格式限制{for(inti=0;i<35-2*n&&(35-2*n)>0;i++)printf(“")；return1;}intPrint_Maze_Figure()//打印出圖形{inti,xi,xj;Format_Limit();for(i=0;i<=n*2;i++)printf("□");printf("\n");for(xi=0,xj=0;xj<((2*nT)*(2*nT));xj++,xi++){if(0==xi){Format_Limit();printf("h);}printf("%s",str[xj]);if(xi==2*n-2){printf("□、『)；xi=-1;}}Format_Limit();for(i=0;i<=n*2;i++)printf("□");printf("\n");return1;}intPPMF()//打印出迷宮圖形{printf("\t\t\t\t[迷宮為]\n\t\t\t?表可走，□表不可走\n");Initialization();Print_Maze_Figure();return1;}intSave_Path()//將路徑保存在str[][]中并打印出路徑迷宮圖形{printf("\t\t\t [迷宮路徑圖]\n(%d,%d)至(%d,%d)\t\t?表可走，□表不可走\n",s.x,s.y,t.x,t.y);Initialization();strcpy(str[2*s.x*(2*n-1)+2*s.y]，"起")；strcpy(str[2*t.x*(2*n-1)+2*t.y],"終")；for(intwri=O;wri<ri;wri++){if(re[wri].rx<re[wri+1].rx&&re[wri].ry==re[wri+1].ry)strcpy(str[2*re[wri].rx*(2*n-1)+(2*n-1)+2*re[wri].ry],"t");if(re[wri].rx==re[wri+1].rx&&re[wri].ry<re[wri+1].ry)strcpy(str[2*re[wri].rx*(2*n-1)+2*re[wri+1].ry-1],"?")；if(re[wri].rx>re[wri+1].rx&&re[wri].ry==re[wri+1].ry)strcpy(str[2*re[wri].rx*(2*n-1)-(2*n-1)+2*re[wri].ry],"I");if(re[wri].rx==re[wri+1].rx&&re[wri].ry>re[wri+1].ry)strcpy(str[2*re[wri].rx*(2*n-1)+2*re[wri].ry-1],"f");if(re[wri].rx<re[wri+1].rx&&re[wri].ry<re[wri+1].ry)strcpy(str[2*re[wri].rx*(2*n-1)+(2*n-1)+1+2*re[wri].ry]," \");if(re[wri].rx<re[wri+1].rx&&re[wri].ry>re[wri+1].ry)strcpy(str[2*re[wri].rx*(2*n-1)+(2*n-1)-1+2*re[wri].ry]," /");if(re[wri].rx>re[wri+1].rx&&re[wri].ry<re[wri+1].ry)strcpy(str[2*re[wri].rx*(2*n-1)-(2*n-2)+2*re[wri].ry],"/");if(re[wri].rx>re[wri+1].rx&&re[wri].ry>re[wri+1].ry)strcpy(str[2*re[wri].rx*(2*n—l)—(2*n—l)T+2*re[wri].ry],〃 \〃）;}Print_Maze_Figure();return1;}//隊列intInit()//從文件中植入數(shù)據(jù)完成對Map迷宮圖的結構{FILE*pf;inti,j;pf=fopen("maze.txt","r");if(pf==NULL)return0;fscanf(pf,"%d"，&n);for(i=0;i<n;i++)for(j=0;j<n;j++){Used[i][j]=false;fscanf(pf,"%d"，&Map[i][j]);}fclose(pf);return1;}intJudge()//判斷輸入的起點終點是否符合實際{boolflag=true;if(s.x<0||s.x>二n||s.y<0||s.y>二n){printf(“起點越界，不符合!\n");flag=false;}elseif(t.x<0||t.x>二n||t.y<0||t.y>二n){printf(“終點越界，不符合！\n");flag=false;}elseif(Map[s.x][s.y]){printf(“起點是墻，不符合！\n");flag=false;}elseif(Map[t.x][t.y]){printf(“終點是墻，不符合！\n");flag=false;}elseif(s.x==t.x&&s.y==t.y){printf(“起點是終點，不符合！\n");flag=false;}if（!flag）{ printf（〃是則再輸入\\否則退出程序：（Y/N）\n〃）;charch[20];scanf("%s",ch);if(ch[O]=='Y'||ch[O]=='y')return1;elsereturn0;}return2;}intmain(){charch;inti,j,step;printf("\t\t\t〈請按提示操作>\n");next:system("pause");system("cls");printf(〃是否使用系統(tǒng)提供的迷宮圖：(Y/N)\n〃)；ch=getch();if(ch二二，Y'||ch二二,y，)Init();else{printf(〃請輸入迷宮的大小：(n*n)〃)；scanf(〃%d〃，&n);printf(〃\t請輸入迷宮的結構0,1表示0是路1是墻\n");for(i=0;i<n;i++)for(j=0;j<n;j++){Used[i][j]=false;scanf(〃％d〃，&Map[i][j]);}}boolflag二true;while(flag){for(i=0;i<n;i++)for(j=0;j<n;j++)Used[i][j]=false;ri=-1;system("pause");system("cls");printf("是否顯示原始迷宮：(Y/N)\n");ch=getch();if(ch二二，Y'||ch二二,y，)PPMF();again:printf("請輸入起點與終點：(xly1x2y2)");scanf("%d%d%d%d",&s.x,&s.y,&t.x,&t.y);if(1==Judge())gotoagain;elseif(0==Judge())break;printf("請選擇4方向還是8方向的迷宮：")；scanf("%d"，&step);if(8==step)step=8;elsestep=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，)gotonext;}}return0;}/*測試例子5000001111000000TOC\o"1-5"\h\z01 1 1 100 0 0 000 4 4 41600 0 0 0 0 0 0 0 0 0 0 0 0 0 011 1 1 1 1 1 1 1 1 1 1 1 1 1 000 0 0 0 0 0 0 0 0 0 0 0 0 1 001 1 1 1 1 1 1 1 1 1 1 1 0 1 001 0 0 0 0 0 0 0 0 0 0 1 0 1 001 0 1 1 1 1 1 1 1 1 0 1 0 1 001 0 1 0 0 0 0 0 0 1 0 1 0 1 001 0 1 0 1 1 1 1 0 1 0 1 0 1 001 0 1 0 1 0 1 1 0 1 0 1 0 1 001 0 1 0 1 0 0 0 0 1 0 1 0 1 001 0 1 0 1 1 1 1 1 1 0 1 0 1 001 0 1 0 0 0 0 0 0 0 0 1 0 1 001 0 1 1 1 1 1 1 1 1 1 1 0 1 001 0 0 0 0 0 0 0 0 0 0 0 0 1 001 1 1 1 1 1 1 1 1 1 1 1 1 1 000 0 0 0 0 0 0 0 0 0 0 0 0 0 000 8 6 401 0 1 0 1 0 1 0 1 0 1 0 1 0 110 1 0 1 0 1 0 1 0 1 0 1 0 1 001 0 1 0 1 0 1 0 1 0 1 0 1 0 110 1 0 1 0 1 0 1 0 1 0 1 0 1 001 0 1 0 1 0 1 0 1 0 1 0 1 0 110 1 0 1 0 1 0 1 0 1 0 1 0 1 001 0 1 0 1 0 1 0 1 0 1 0 1 0 110 1 0 1 0 1 0 1 0 1 0 1 0 1 001 0 1 0 1 0 1 0 1 0 1 0 1 0 110 1 0 1 0 1 0 1 0 1 0 1 0 1 001 0 1 0 1 0 1 0 1 0 1 0 1 0 110 1 0 1 0 1 0 1 0 1 0 1 0 1 001 0 1 0 1 0 1 0 1 0 1 0 1 0 110 1 0 1 0 1 0 1 0 1 0 1 0 1 0

0100011101010010001000000000100000010101010101010101010101010101001515801408TOC\o"1-5"\h\z10 1 0 1 0 101 0 1 0 1 101 1 1 1 1 100 0 1 0 1 011 1 1 1 0 101 1 1 1 1 111 1 0 1 0 101 0 1 0 1 007 9 800 0 1 0 1 0 1 1 1 0 1 1 1 011 0 0 0 1 0 1 1 1 0 1 1 1 000 1 0 0 0 0 0 1 0 0 1 1 1 000 0 0 0 0 0 0 0 0 1 0 1 0 000 1 0 0 1 0 1 1 1 0 0 0 0 111 0 1 0 1 0 0 0 0 1 0 1 0 000 0 0 0 0 0 0 0 0 1 0 1 0 000 0 0 1 0 1 1 1 1 0 1 1 1 000 1 0 1 0 1 0 0 0 0 1 1 0 000 0 1 0 1 0 1 0 0 1 0 0 0 110 0 0 0 0 1 0 0 0 0 1 1 0 000 0 1 1 1 0 0 0 1 0 0 0 1 000 1 0 0 0 0 1 0 1 0 0 1 0 011 0 0 1 1 1 0 0 0 1 0 1 0 000 1 1 0 0 0 0 0 1 0 0 0 0 010 0 0 0 1 0 0 0 0 1 0 1 0 01101541101582141242141280015400158

*/3.5程序調(diào)試與體會調(diào)試：經(jīng)過幾天的努力，課程設計終于完成，由于我對數(shù)據(jù)結構和c語言不是很了解，有時忽略了一些關鍵的細節(jié)，使得在編寫程序的過程中出現(xiàn)了一些問題。對于打字有時粗心導致出現(xiàn)一些難以發(fā)現(xiàn)的小錯誤，在我的耐心，細致的調(diào)試下最終使得程序能夠運行，課程設計完滿完工。1、 問題一：求出起點到終點的路徑現(xiàn)象：求出的結果總是無任何現(xiàn)象原因：把相關重要的變量重復定義以至賦過的值被覆蓋2、 問題二：常量轉義字符現(xiàn)象：出現(xiàn)不正常字符常量原因：’\'字符常量形式弄錯3、 問題三：輸入起點終點時，未判斷下標越界就使用數(shù)據(jù)原因：未判斷下標越界就使用數(shù)據(jù)體會：在復雜的程序，都可以拆成一個個簡單的小部分，逐個擊破，再拼湊起來,在復雜的事也變的簡單了。

3.6運行結果（截圖）將程序員錄入后，讓其運行。將會出現(xiàn)一個菜單的界面，執(zhí)行各種操作均有其對應的代碼。要執(zhí)行何種操作只需輸入對應的指令即可進行，在每步操作后均會有相應的提示。操作簡單方便實用，下面即為一些操作的示意圖。運行程序后出界面，運行結果如圖所示。賦"E:\SES構已迷宮求fi.exe"是否顯示原始迷宮：(Y/N)□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□走口可□口口1不口兩表□口口宮□口迷?—走口可□口口表口□■□□■□□■□□■□□□□□□□■????□?????????□?□□□?□□□■□□■?□□□■■■□?□?■■■■□□??■■■□????■□□□□□□?□□?□□?□□?□□□□□?□□?□□?□□?□□□□□?□□□□□?□□?□倩輸入起點.與終點.：(siylk2y2)011015倩選擇4方向還是塔方向的迷宮:4倩按任意鍵繼續(xù)...□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□數(shù)據(jù)錯構\Debug\j￡宮求lft.exe"到目的地了歩數(shù)低(0,15)<-(1,15)<-(2,15)<-(3,15)<-(3,14)<-(4,14)<-(5,14)<-(5,15)<-(乞15)<-(7,15)<-(8,15)<-(8,14)<-(9,14)<-(10,14)<-(10,15)<-(11,15)<-(12,15)<-(13,15)<-(14,15)<-(14,14)<-(14,13)<-(14,12)<-(13,12)<-(12,12)<-(12,11)<-(11,11)<-(10,11)<-(10,10)<-(10,9)<-(11,9)<-(12,9)<-(13,9)<-(14,9)<-(14,8)<-(14,7)<-(14,6)<-(14,5)<-(15,5)<-(15,4)<-(15,3)<-(15,2)<-(14,2)<-(14,1)<-(14,0)<-(13,0)<-(12,0)<-(12,1)<-(12,2)<-(11,2)<-(10,2)<-(9,2)<-(8,2)<-(7,2)<-(7,3)<-(7,4)<-(6,4)<-(6,5)<-(6,6)<-(6,7)<-(&7)<-(4,7)<-(3,7)<-(3,8)<-(3,9)<-(3,10)<-(2,10)<-(2,11)<-(1,11)<-(0,11)<-請按任意鍵繼續(xù).?.C：c"E:\SES構\D曰迷宮求解.田ce；"□?□□表□□口J走□□□□□□起?J?□□□□□□□□□□□[終[f[?[t[?[t[?[?□□□□□□??□?J□□□?■<—?■<—?□?□??□□□?■■?□[■???□?□??[????□?□?t[?[□□□□?□□□■H?[□■■??□□?f[?[?□??□???□[□??f??□□t??[?■t■□?■■□f[?[■□t?□■?□?f[?[□?t??□1?□?t[?[??t?□?1??■t[■[□□□□□口孵走口[M可□口

表口□□）至（□□■o,□■15）□□?□□□??????■■?□□□□□口口□□□□口□□―>□□―>□□―>■□—?口―>■□□□―>□?□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□口JO是否繼續(xù)(Y/N)是否更換迷宮(Y/N)倩按任意鍵繼續(xù)...曲"E：\數(shù)據(jù)踣構\Debug\迷宮^ft.exe"是否使用系統(tǒng)提洪的迷宮圖：(丫顱)請按任意鍵繼續(xù)???C：c"E：\數(shù)據(jù)結構\D已bug\迷宮求fi.exe"是否顯示原始迷宮:(Y/N)表□可□瞇宮□□70表□]走□□■□□■?□走□?□□?口」□□□□□□□□□■□□□□■■?□?□□□■□?□?????□??□?????????□??□??□?□□□??□■□?□?■■■□■■■■???■■■□■???□?□□□□?□?□?□?□????□??□?□?□??□?■■■??□■■■■□■■□□□?■■□■■□□□?□□?□□□□□□□□□□□?□□?□□?□□□□□?□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□