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

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

2、能走的最短路找到，并很直觀的顯示在屏幕上的功能。指導(dǎo)教師簽字：、 日期：指導(dǎo)教師評語成績：指導(dǎo)教師簽字： 日期：課程設(shè)計所需軟件、硬件等電腦、C+6.0課程設(shè)計進度計劃起至日期工作內(nèi)容備注參考文獻、資料索引序號文獻、資料名稱編著者出版單位1 數(shù)據(jù)結(jié)構(gòu) 蔣秀英，欒曉春，燕孝飛 中國石油大學(xué)出版社2 數(shù)據(jù)結(jié)構(gòu)(C語言版)M, 嚴蔚敏等 清華大學(xué)出版社3 數(shù)據(jù)結(jié)構(gòu)用面向?qū)ο蠓椒ㄅcC+描述， 殷人昆等 清華大學(xué)出版社4 編程愛好者網(wǎng)站（迷宮問題）5編程論壇（迷宮問題）目 錄摘 要21引 言32設(shè)計目的與任務(wù)32.1設(shè)計目的是32.2設(shè)計任務(wù)是43設(shè)計方案與實施43.1總體設(shè)計思想43.2設(shè)計流程圖53

3、.3詳細設(shè)計63.4程序清單63.5程序調(diào)試與體會63.6運行結(jié)果（截圖）7結(jié)論 15致 謝15摘 要隨著計算機的高速發(fā)展，計算機能很簡便地解決很多問題。C語言編程也是解決問題的一種語言。而此我們的數(shù)據(jù)結(jié)構(gòu)程序設(shè)計是解決迷宮問題。求迷宮(老鼠吃奶酪)中從入口到出口的路徑是一個經(jīng)典的程序設(shè)計問題。“數(shù)據(jù)結(jié)構(gòu)”成為計算機程序設(shè)計的重要理論技術(shù)基礎(chǔ)，它不僅是計算機學(xué)科的核心課程，而且已成為其它理工專業(yè)的熱門選修課。主要包括線性表、樹和二叉樹以及圖等基本類型的數(shù)據(jù)結(jié)構(gòu)。數(shù)據(jù)結(jié)構(gòu)是一門研究非數(shù)值計算的程序設(shè)計問題中計算機的操作對象以及它們之間的關(guān)系和運算等的學(xué)科，包括數(shù)據(jù)的邏輯結(jié)構(gòu)、數(shù)據(jù)的存儲結(jié)構(gòu)和數(shù)據(jù)

4、的運算這三個方面的內(nèi)容，其中邏輯結(jié)構(gòu)可分為線性結(jié)構(gòu)和非線性結(jié)構(gòu)；存儲結(jié)構(gòu)可分為順序存儲和鏈式存儲兩類，圖則屬于邏輯結(jié)構(gòu)中的非線性結(jié)構(gòu)。廣度優(yōu)先搜索(BFS)用的隊列一步一步完成的，從而找到的是最短路徑。關(guān)鍵詞：隊列，廣度優(yōu)先，搜索，最短路徑，遍歷1引 言數(shù)據(jù)結(jié)構(gòu)是計算機科學(xué)與技術(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)。但我們這個程序沒有用棧，而是

5、用隊列替代棧的功能，使程序運行效率更加高。還用到求迷宮問題最平常的數(shù)據(jù)結(jié)構(gòu)算法，即廣度優(yōu)先搜索算法(BFS)，還保持了它的路徑，再從串中輸出圖。本課程設(shè)計總的思路要解決的問題是構(gòu)造迷宮，尋找路線，打印路徑。我們首先要做的是創(chuàng)建一個二維數(shù)組，用以來存儲圖，然后我們要想好怎樣利用BFS算法來尋找路線。把這個算法以及其他過程寫成調(diào)用函數(shù)，各自調(diào)用后調(diào)試程序。達到滿意結(jié)果后寫報告。2設(shè)計目的與任務(wù)2.1設(shè)計目的是根據(jù)課堂講授內(nèi)容，學(xué)生做相應(yīng)的自主練習(xí)，消化數(shù)據(jù)結(jié)構(gòu)課堂所講解的內(nèi)容；通過調(diào)試典型例題或習(xí)題積累調(diào)試C程序的經(jīng)驗；通過完成輔導(dǎo)教材中的編程題，逐漸培養(yǎng)學(xué)生的編程能力、用計算機解決實際問題的能力

6、、團體合作能力。2.2設(shè)計任務(wù)是它的任務(wù)就是訓(xùn)練學(xué)生對計算機數(shù)據(jù)對象進行分析的能力，選擇適當?shù)臄?shù)據(jù)結(jié)構(gòu)及相關(guān)算法的能力。 此程序的任務(wù)是實現(xiàn)把能走的最短路找到，并很直觀的顯示在屏幕上的功能。3設(shè)計方案與實施3.1總體設(shè)計思想(1) 迷宮形狀由0表示可通過，用1表示是障礙。為方便用0,1輸入。并把迷宮圖形保存在二維數(shù)組Map中。而打印出的圖形中 表示能過表示障礙.(2) 對探索過的位置加以標記Used，輸入起點終點后可由BFS（）來完成搜索。到目的點就可退出該調(diào)用程序。把每步路徑保存到Mark內(nèi)，通過反向進行退步可把完整的路徑保存在結(jié)構(gòu)體result數(shù)組re內(nèi)，通過標記的路徑可將串str作相應(yīng)的

7、改變就能輸出的帶路徑的圖。(3) 根據(jù)二維字符數(shù)組和加標記的位置坐標，輸出迷宮的圖形。(4) 該程序在獲取迷宮圖結(jié)構(gòu)后，可對迷宮任意入口到出口的路線進行搜索，主要由廣度優(yōu)先搜索完成該操作。它可以是100以內(nèi)大小的迷宮，有自行提供的迷宮圖，本課程設(shè)計是以二維數(shù)組作為迷宮的存儲結(jié)構(gòu)。而廣度優(yōu)先搜索(BFS)用的隊列一步一步完成的，從而找到的是最短路徑；該程序還能選擇是4方向還是8方向的迷宮走法。并能輸出打印3.2設(shè)計流程圖開始輸入迷宮圖形顯示迷宮圖形輸入起點終點是否符合題意輸出路徑節(jié)點輸出迷宮路線是否繼續(xù)？是否更換迷宮結(jié)束3.3詳細設(shè)計struct Pointint x,y,s;這個結(jié)構(gòu)體是用來做

8、廣度搜索的對每個迷宮節(jié)點有相應(yīng)的s(最短的步數(shù)，當然有些是不可達的)int move82 = 1,0,0,1,-1,0,0,-1,1,1,-1,-1,1,-1,-1,1 ;/int BFS(int step)/ 廣度搜索用來算出最短路徑的走法 并將走法保存在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ù)

9、 完成對Map迷宮圖的結(jié)構(gòu)int Judge()/判斷輸入的起點終點是否符合實際int main()/對上面函數(shù)的結(jié)合應(yīng)用3.4程序清單#include <stdlib.h>#include <iostream>#include <string>#include <queue>/ 這個是stl 它是一個方便的東西 #include <fstream>#include <conio.h>using namespace std;struct result int rx,ry;re100*100;int ri=-1;struct

10、 Pointint x,y,s;s,t;/s代表起點 t代表終點int mark100100; /用來標記怎么走到這個地方的 (保存的是方向的序號):0,1,2,3,4,5,6,7bool Used100100;/標記已經(jīng)走過的地方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) / 廣度搜索用來算出最短路徑的走法 并將走法保存在re結(jié)構(gòu)體中queue<Point> My;s.s =0;while(!My.empty()My.

11、pop();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 marku

12、s1.y 1;re+ri.rx=s1.x; reri.ry=s1.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&l

13、t;0|temp.x>=n|temp.y<0|temp.y>=n|Usedtemp.xtemp.y|Maptemp.xtemp.y)continue;elsemarktemp.xtemp.y = i;temp.s += 1 ;My.push(temp);Usedtemp.xtemp.y = true;printf("不好意思,起點至終點無路徑不可達!n");return 0;char str256*2563; /串保存圖int Initialization()/ 將str圖形初始化int i1,j1,xj;for(i1=0;i1<256*256;i1

14、+) strcpy(stri1," ");for(i1=0;i1<n;i1+)for(j1=0,xj=0;xj<n;j1=j1+2,xj+)if(Mapi1xj = 0) strcpy(str2*i1*(2*n-1)+j1,"");else strcpy(str2*i1*(2*n-1)+j1,"");return 1;int Format_Limit()/圖形打印格式限制for(int i =0; i <35-2*n&&(35-2*n)>0;i+)printf(" ");re

15、turn 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

16、_Limit();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.

17、x,t.y);Initialization();strcpy(str2*s.x*(2*n-1)+2*s.y,"起");strcpy(str2*t.x*(2*n-1)+2*t.y,"終");for(int wri=0;wri<ri;wri+) if(rewri.rx<rewri+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

18、.ry<rewri+1.ry) strcpy(str2*rewri.rx*(2*n-1)+2*rewri+1.ry-1,""); if(rewri.rx>rewri+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.ry>rewri+1.ry) strcpy(str2*rewri.rx*(2*n-1)+2*rewri.ry-1,"

19、;"); if(rewri.rx<rewri+1.rx&&rewri.ry<rewri+1.ry) strcpy(str2*rewri.rx*(2*n-1)+(2*n-1)+1+2*rewri.ry,""); if(rewri.rx<rewri+1.rx&&rewri.ry>rewri+1.ry) strcpy(str2*rewri.rx*(2*n-1)+(2*n-1)-1+2*rewri.ry,""); if(rewri.rx>rewri+1.rx&&rewri.r

20、y<rewri+1.ry) strcpy(str2*rewri.rx*(2*n-1)-(2*n-2)+2*rewri.ry,""); if(rewri.rx>rewri+1.rx&&rewri.ry>rewri+1.ry) strcpy(str2*rewri.rx*(2*n-1)-(2*n-1)-1+2*rewri.ry,""); Print_Maze_Figure();return 1;/隊列int Init()/ 從文件中植入數(shù)據(jù) 完成對Map迷宮圖的結(jié)構(gòu)FILE *pf;int i,j;pf = fopen(&qu

21、ot;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()/判斷輸入的起點終點是否符合實際bool flag = true;if(s.x<0|s.x>=n|s.y<0|s.y>=n)printf(&q

22、uot;起點越界,不符合!n");flag = false;else if(t.x<0|t.x>=n|t.y<0|t.y>=n)printf("終點越界,不符合!n");flag = false;else if(Maps.xs.y)printf("起點是墻,不符合!n");flag = false;else if(Mapt.xt.y)printf("終點是墻,不符合!n");flag = false;else if(s.x=t.x&&s.y=t.y)printf("起點是終點

23、,不符合!n");flag = false;if(!flag)printf("是則再輸入否則退出程序:(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("ttt<請按提示操作>n");next:system("pause"); system("cls&q

24、uot;); printf("是否使用系統(tǒng)提供的迷宮圖:(Y/N)n"); ch = getch(); if(ch = 'Y'|ch ='y') Init(); else printf("請輸入迷宮的大小:(n*n)");scanf("%d",&n);printf("t請輸入迷宮的結(jié)構(gòu)0,1表示0是路1是墻n");for(i = 0;i < n; i+)for(j = 0 ; j < n; j+)Usedij = false;scanf("%d"

25、;,&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("請輸入起點與終點:(x1 y1 x2 y2)");

26、scanf("%d %d %d %d",&s.x,&s.y,&t.x,&t.y);if(1=Judge()goto again;elseif(0=Judge()break;printf("請選擇4方向還是8方向的迷宮:");scanf("%d",&step);if(8=step)step=8;else step = 4;system("pause");system("cls");BFS(step);Save_Path();printf("是否繼續(xù)

27、(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')goto next;return 0;/*測試例子50 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

28、 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 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

29、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

30、 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

31、 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 0 15 15 80 0 14 0 80 1 0 1 0 1 0 11 0 1 0 1 0 1 11 0 1 1 1 1 1 11 0 0 0 1 0 1 00 1 1 1 1 1 0 11 0 1 1 1 1 1 10 1 1 1 0 1 0 11 0 1 0 1 0 1 00 0 7 9 80 0 0 0 1 0 1 0 1 1 1 0 1 1 1 01 1 1 0 0 0 1 0 1 1 1 0 1 1 1 00 0 0 1 0 0 0 0 0 1 0 0 1 1 1 00 0 0 0 0 0 0 0 0 0 0 1 0 1 0 00 0 0 1 0 0 1 0 1 1 1 0 0 0 0 11 1 1 0 1 0 1 0 0 0 0 1 0 1 0 00 0 0 0 0 0 0 0 0 0 0 1 0 1 0 00 0 0 0 0 1 0 1 1 1 1 0 1 1 1 00 0 0 1 0 1 0 1 0 0 0 0 1 1 0 00 0 0 0 1 0 1 0 1 0 0 1 0 0 0 10 1 0 0 0 0 0 1 0 0 0 0 1 1 0 00 0 0 0 1 1 1 0 0 0 1 0 0 0 1