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

1、計(jì)算機(jī)解迷宮問題通常用的是“窮舉求解”方法，即從入口出發(fā)，順著某一個(gè)方向進(jìn)行探索，若能走通，則繼續(xù)往前進(jìn)；否則沿著原路退回，換一個(gè)方向繼續(xù)探索，直至出口位置，求得一條通路。假如所有可能的通路都探索到而未能到達(dá)出口，則所設(shè)定的迷宮沒有通路。迷宮的入口點(diǎn)的下標(biāo)為（1，1），出口點(diǎn)的下標(biāo)為（m，n）。為處理方便起見，可在迷宮的四周加一圈障礙。對(duì)于迷宮的任一位置，均可約定有東、南、西、北四個(gè)方向可通。有一種簡(jiǎn)單走出迷宮的方法，把手放在右邊的墻上開始前進(jìn)，始終不要把手從墻上移開。如果迷宮向右拐，你也順著墻向右拐。只要不把手從墻上移開，最終就會(huì)到達(dá)迷宮的出口。當(dāng)然這樣得到的路徑可能不是一個(gè)最短的路徑，但它

2、可以最終得到結(jié)果，換句話說，這種方法走不出迷宮的風(fēng)險(xiǎn)是最小的。本設(shè)計(jì)是為了實(shí)現(xiàn)一個(gè)可視化迷宮，以及利用最短路徑算法尋找迷宮的出路以及將最短路徑打印在屏幕上，并且限制小老鼠不能穿越墻，只能在路徑上移動(dòng)。而且可以根據(jù)自己的需要設(shè)計(jì)迷宮地圖。關(guān)鍵詞 迷宮；棧；VC+ 6.0 目錄1 課設(shè)題目11.1課設(shè)題目.11.2基本要求：.11.3 需求分析12 程序總體設(shè)計(jì)22.1流程圖：.22.2概要設(shè)計(jì).62.3 運(yùn)行結(jié)果及分析7總結(jié)9源程序10參考文獻(xiàn)201 課設(shè)題目1.1課設(shè)題目編寫一個(gè)程序求解迷宮問題。迷宮由m行n列的二維數(shù)組設(shè)置，0表示無障礙，1表示有障礙。設(shè)入口為（1，1），出口為（m，n），每

3、次只能從一個(gè)無障礙單元移到周圍四個(gè)方向上任一無障礙單元。編程實(shí)現(xiàn)對(duì)任意設(shè)定的迷宮，求出一條從入口到出口的通路，或得出沒有通路的結(jié)論。算法輸入：代表迷宮入口的坐標(biāo)算法輸出：穿過迷宮的結(jié)果。算法要點(diǎn)：創(chuàng)建迷宮，試探法查找路徑，輸出解1.2基本要求：1.求得的通路以三元組（i，j，d）的形式輸出，其中：（i，j）指示迷宮中的一個(gè)坐標(biāo)，d表示走到下一個(gè)坐標(biāo)的方向。2.輸出迷宮示意圖1.3 需求分析1、本程序?qū)崿F(xiàn)迷宮的探索過程. 以用戶和計(jì)算機(jī)對(duì)話的方式，即在計(jì)算機(jī)終端上顯示“提示信息”之后，由用戶在鍵盤上輸入演示程序中規(guī)定的運(yùn)算命令，然后程序就探索路徑并輸出路徑。 2、本演示程序中，輸入形式以“回車符

4、”為結(jié)束標(biāo)志，且允許出現(xiàn)重復(fù)字符。3、利用二維指針實(shí)現(xiàn)迷宮位置的存儲(chǔ)，并用棧存貯探索路徑，每個(gè)結(jié)點(diǎn)含三個(gè)整形變量。輸入的形式以回車結(jié)束。4、本程序中，用戶可以讀去文件里的迷宮，也可自己重新輸入迷宮，而且用戶可以輸入任意大小的迷宮，然后程序自動(dòng)探索路徑，并輸出迷宮的路徑。2 程序總體設(shè)計(jì)2.1流程圖：1.功能結(jié)構(gòu)圖Main主函數(shù)模塊輸出路徑模塊printpath（）獲取迷宮模塊探索路徑模塊Findpath（）存儲(chǔ)探索路徑模塊stack類讀文件Readfile（）寫文件Writefile（）Stack類數(shù)據(jù)模塊操作模塊盤空函數(shù)isempty（）清空函數(shù)clear（）取棧頂函數(shù)getpop（）進(jìn)棧與

5、出棧函數(shù)push（）Pop（）構(gòu)造與析構(gòu)函數(shù)stack（）stack（）結(jié)點(diǎn)模塊Node*top結(jié)點(diǎn)數(shù)據(jù)類型模塊datatype類2.畫出主要數(shù)據(jù)結(jié)構(gòu)的類圖class 類名DataType /定義描述迷宮中當(dāng)前位置的類型數(shù)據(jù)成員訪問控制權(quán)限 數(shù)據(jù)類型 變量名; public:int x; /x代表當(dāng)前位置的行坐標(biāo) int y; /y代表當(dāng)前位置的列坐標(biāo) int dir; /dir表示移動(dòng)到下一步的方向 class 類名Move /定義下一個(gè)位置的方向數(shù)據(jù)成員訪問控制權(quán)限 數(shù)據(jù)類型 變量名; public:int x; int y;class 類名Node /結(jié)點(diǎn)數(shù)據(jù)成員訪問控制權(quán)限 數(shù)據(jù)類型

6、變量名; public: DataType data; Node *next;class 類名stack數(shù)據(jù)成員訪問控制權(quán)限 數(shù)據(jù)類型 變量名; private: Node *top; /指向第一個(gè)結(jié)點(diǎn)的棧頂指針成員函數(shù)訪問控制權(quán)限 返回值類型 函數(shù)名(參數(shù)列表) public: stack(); /構(gòu)造函數(shù)，置空棧 stack(); /析構(gòu)函數(shù) void Push(DataType data);/把元素data壓入棧中 DataType Pop(); /使棧頂元素出棧 DataType GetPop(); /取出棧頂元素 void Clear(); /把棧清空 bool IsEmpty();

7、 /判斷棧是否為空，如果為空則返回1，否則返回0開始 3.main函數(shù)流程圖 顯示系統(tǒng)信息選擇獲取迷宮的方式chCh= bCh=aReadfile()文件讀取自行輸入Writefile（）探索迷宮路徑是否存在輸出迷宮路徑是否繼續(xù)游戲退出開始2.探索路徑函數(shù)findpath（）Temp1.x=1Temp1.y=1入口進(jìn)棧p.pushq.push是否非空temp2=q.getpop（）P q棧頂是否相等探索上下左右四個(gè)方位是否有路徑到達(dá)新位置是否到達(dá)出口最后一個(gè)元素進(jìn)棧輸出路徑回復(fù)以改變的迷宮結(jié)束開始3.自行輸入迷宮函數(shù)writefile（）輸入長(zhǎng)寬m，n動(dòng)態(tài)申請(qǐng)空間二位數(shù)組空間i<=m是否

8、保存迷宮J<=ni+ ；j+輸入迷宮輸入保存迷宮的文件名保存迷宮結(jié)束2.2概要設(shè)計(jì)1.構(gòu)建一個(gè)二維數(shù)組mazeM+2N+2用于存儲(chǔ)迷宮矩陣自動(dòng)或手動(dòng)生成迷宮，即為二維數(shù)組mazeM+2N+2賦值構(gòu)建一個(gè)隊(duì)列用于存儲(chǔ)迷宮路徑建立迷宮節(jié)點(diǎn)struct point,用于存儲(chǔ)迷宮中每個(gè)節(jié)點(diǎn)的訪問情況實(shí)現(xiàn)搜索算法屏幕上顯示操作菜單 2.本程序包含10個(gè)函數(shù)： (1)主函數(shù) main()(2)手動(dòng)生成迷宮函數(shù) shoudong_maze()(3)打印迷宮路徑 (若存在路徑) result_maze()(4)入隊(duì) enqueue()(5)出隊(duì) dequeue()(6)判斷隊(duì)列是否為空 is_empty

9、()(7)訪問節(jié)點(diǎn) visit()(8)搜索迷宮路徑 mgpath()2.3 運(yùn)行結(jié)果及分析 總結(jié)通過這段時(shí)間的數(shù)據(jù)結(jié)構(gòu)課程設(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í)和認(rèn)真聽老師講課分析，我收獲了不少。當(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)

10、無論是專業(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)解決實(shí)際問題的能力，所以相信通過此次實(shí)習(xí)可以提高我們分析設(shè)計(jì)能力和編程能力，為后續(xù)課程的學(xué)習(xí)及實(shí)踐打下良好的基礎(chǔ)。時(shí)間過得真快，大學(xué)生活不知不覺就走過了一學(xué)期，這一學(xué)期的大學(xué)學(xué)習(xí)和課程實(shí)踐階段的提高，使我

11、們本身知識(shí)得到提高的同時(shí)，也增強(qiáng)了我們對(duì)未來工作的信心，我們相信自己未來兩年半的學(xué)習(xí)更使我們有能力勝任將來的工作。源程序#include<iostream>using namespace std; class T/定義描述迷宮中當(dāng)前位置的結(jié)構(gòu)類型public:int x;/x代表當(dāng)前位置的行坐標(biāo)int y;/y代表當(dāng)前位置的列坐標(biāo)int dir;/0:無效,1:東,2:南,3:西,4:北; class LinkNode/鏈表結(jié)點(diǎn)friend class Stack;public:T data;LinkNode *next; class Stackprivate:LinkNode *

12、top;/指向第一個(gè)結(jié)點(diǎn)的棧頂指針public:Stack();/構(gòu)造函數(shù)，置空棧Stack()/析構(gòu)函數(shù)void Push(T e);/元素data入棧中T Pop();/棧頂元素出棧T GetPop();/取出棧頂元素void Clear();/把棧清空bool empty();/判斷棧是否為空，如果為空則返回1，否則返回0; Stack:Stack()/構(gòu)造函數(shù)，置空棧top=NULL; void Stack:Push(T e)/元素x入棧中LinkNode *P;P=new LinkNode;P->data=e;P->next=top;top=P; T Stack:Pop(

13、)/棧頂元素出棧T Temp;LinkNode *P;P=top;top=top->next;Temp=P->data;delete P;return Temp; T Stack:GetPop()/取出棧頂元素return top->data; void Stack:Clear()/把棧清空top=NULL; bool Stack:empty()/判斷棧是否為空，如果為空則返回1，否則返回0if(top=NULL) return 1;else return 0; int move42=0,1,1,0,0,-1,-1,0;/定義當(dāng)前位置移動(dòng)的4個(gè)方向 void PrintPat

14、h(Stack p)/輸出路徑cout<<"迷宮的路徑為n"cout<<"括號(hào)內(nèi)的內(nèi)容分別表示為(行坐標(biāo),列坐標(biāo),數(shù)字化方向,方向)n"Stack t;/定義一個(gè)棧，按從入口到出口存取路徑int a,b;T data;LinkNode *temp;temp=new LinkNode;/獲取空間temp->data=p.Pop();/取棧p的頂點(diǎn)元素，即第一個(gè)位置t.Push(temp->data);/第一個(gè)位置入棧tdelete temp;/釋放空間while(!p.empty()/如果棧p非空，則反復(fù)轉(zhuǎn)移temp=n

15、ew LinkNode;temp->data=p.Pop();/獲取下一個(gè)位置/得到行走方向a=t.GetPop().x-temp->data.x;/行坐標(biāo)方向b=t.GetPop().y-temp->data.y;/列坐標(biāo)方向if(a=1) temp->data.dir=1;/方向向下，用1表示else if(b=1) temp->data.dir=2;/方向向右，用2表示else if(a=-1) temp->data.dir=3;/方向向上，用3表示else if(b=-1) temp->data.dir=4;/方向向左，用4表示t.Push(t

16、emp->data);/把新位置入棧delete temp;/輸出路徑，包括行坐標(biāo)，列坐標(biāo)，下一個(gè)位置方向while(!t.empty()/棧非空，繼續(xù)輸出data=t.Pop();cout<<'('<<data.x<<','<<data.y<<','<<data.dir<<","/輸出行坐標(biāo)，列坐標(biāo)switch(data.dir)/輸出相應(yīng)的方向 case 1:cout<<")n"break;case 2

17、:cout<<")n"break;case 3:cout<<")n"break;case 4:cout<<")n"break;case 0:cout<<")n"break; void Restore(int *maze,int m,int n)/恢復(fù)迷宮int i,j;for(i=0;i<m+2;i+)/遍歷指針for(j=0;j<n+2;j+) if(mazeij=-1)/恢復(fù)探索過位置，即把-1恢復(fù)為0mazeij=0; int* GetMaze(in

18、t &m,int &n)/返回存取迷宮的二維指針int *maze;/定義二維指針存取迷宮int i=0,j=0;cout<<"請(qǐng)輸入迷宮的長(zhǎng)和寬:"int a,b;cin>>a>>b;/輸入迷宮的長(zhǎng)和寬cout<<"請(qǐng)輸入迷宮內(nèi)容:(0為通路，1為墻)n"m=a;n=b;/m,n分別代表迷宮的行數(shù)和列數(shù)maze=new int *m+2;/獲取長(zhǎng)度等于行數(shù)加2的二級(jí)指針for(i= 0;i<m+2;i+)/每個(gè)二維指針的空間mazei=new intn+2;for(i=1;i<

19、=m;i+)/輸入迷宮的內(nèi)容，0代表可通，1代表不通for(j=1;j<=n;j+)cin>>mazeij;for(i=0;i<m+2;i+)mazei0=mazein+1=1;for(i=0;i<n+2;i+)maze0i=mazem+1i=1;return maze;/返回存貯迷宮的二維指針maze; bool Mazepath(int *maze,int m,int n)/尋找迷宮maze中從（0，0）到（m,n）的路徑Stack q,p;/定義棧p、q,分別存探索迷宮的過程和存儲(chǔ)路徑T Temp1,Temp2; int x,y,loop;Temp1.x=1

20、;Temp1.y=1;q.Push(Temp1);/將入口位置入棧p.Push(Temp1);maze11=-1;/標(biāo)志入口位置已到達(dá)過while(!q.empty()/棧q非空，則反復(fù)探索Temp2=q.GetPop();/獲取棧頂元素if(!(p.GetPop().x)=(q.GetPop().x)&&(p.GetPop().y)=(q.GetPop().y) p.Push(Temp2); /如果有新位置入棧，則把上一個(gè)探索的位置存入棧pfor(loop=0;loop<4;loop+)/探索當(dāng)前位置的4個(gè)相鄰位置x=Temp2.x+moveloop0;/計(jì)算出新位置x位置值y=Temp2.y+moveloop1;/計(jì)算出新位置y位置值if(mazexy=0)/判斷新位置是否可達(dá)Temp1.x=x;Temp1.y=y;mazexy=-1