迷宮游戲數(shù)據(jù)結(jié)構(gòu)

迷宮游戲數(shù)據(jù)結(jié)構(gòu)計算機解迷宮問題通常用的是“窮舉求解”方法，即從入口出發(fā)，順著某一個方向進行探索，若能走通，則繼續(xù)往前進；否則沿著原路退回，換一個方向繼續(xù)探索，直至出口位置，求得一條通路。假如所有可能的通路都探索到而未能到達出口，則所設(shè)定的迷宮沒有通路。迷宮的入口點的下標(biāo)為（1，1），出口點的下標(biāo)為（m，n）。為處理方便起見，可在迷宮的四周加一圈障礙。對于迷宮的任一位置，均可約定有東、南、西、北四個方向可通。有一種簡單走出迷宮的方法，把手放在右邊的墻上開始前進，始終不要把手從墻上移開。如果迷宮向右拐，你也順著墻向右拐。只要不把手從墻上移開，最終就會到達迷宮的出口。當(dāng)然這樣得到的路徑可能不是一個最短的路徑，但它可以最終得到結(jié)果，換句話說，這種方法走不出迷宮的風(fēng)險是最小的。本設(shè)計是為了實現(xiàn)一個可視化迷宮，以及利用最短路徑算法尋找迷宮的出路以及將最短路徑打印在屏幕上，并且限制小老鼠不能穿越墻，只能在路徑上移動。而且可以根據(jù)自己的需要設(shè)計迷宮地圖。關(guān)鍵詞迷宮；棧；VC++6.0迷宮游戲數(shù)據(jù)結(jié)構(gòu)全文共迷宮游戲數(shù)據(jù)結(jié)構(gòu)全文共24頁，當(dāng)前為第1頁。目錄1課設(shè)題目 課設(shè)題目1.1課設(shè)題目編寫一個程序求解迷宮問題。迷宮由m行n列的二維數(shù)組設(shè)置，0表示無障礙，1表示有障礙。設(shè)入口為（1，1），出口為（m，n），每次只能從一個無障礙單元移到周圍四個方向上任一無障礙單元。編程實現(xiàn)對任意設(shè)定的迷宮，求出一條從入口到出口的通路，或得出沒有通路的結(jié)論。算法輸入：代表迷宮入口的坐標(biāo)算法輸出：穿過迷宮的結(jié)果。算法要點：創(chuàng)建迷宮，試探法查找路徑，輸出解1.2基本要求：1.求得的通路以三元組（i，j，d）的形式輸出，其中：（i，j）指示迷宮中的一個坐標(biāo)，d表示走到下一個坐標(biāo)的方向。2.輸出迷宮示意圖1.3需求分析迷宮游戲數(shù)據(jù)結(jié)構(gòu)全文共24頁，當(dāng)前為第3頁。1、本程序?qū)崿F(xiàn)迷宮的探索過程.以用戶和計算機對話的方式，即在計算機終端上顯示“提示信息”之后，由用戶在鍵盤上輸入演示程序中規(guī)定的運算命令，然后程序就探索路徑并輸出路徑。

2、本演示程序中，輸入形式以“回車符”為結(jié)束標(biāo)志，且允許出現(xiàn)重復(fù)字符。

3、利用二維指針實現(xiàn)迷宮位置的存儲，并用棧存貯探索路徑，每個結(jié)點含三個整形變量。輸入的形式以回車結(jié)束。

4、本程序中，用戶可以讀去文件里的迷宮，也可自己重新輸入迷宮，而且用戶可以輸入任意大小的迷宮，然后程序自動探索路徑，并輸出迷宮的路徑迷宮游戲數(shù)據(jù)結(jié)構(gòu)全文共24頁，當(dāng)前為第3頁。2程序總體設(shè)計2.1流程圖：1.功能結(jié)構(gòu)圖MMain主函數(shù)模塊輸出路徑模塊printpath（）輸出路徑模塊printpath（）獲取迷宮模塊探索路徑模塊獲取迷宮模塊探索路徑模塊Findpath（）存儲探索路徑模塊stack類讀文件R存儲探索路徑模塊stack類讀文件Readfile（）寫文件Writefile（）SStack類數(shù)據(jù)模塊數(shù)據(jù)模塊操作模塊操作模塊盤空函數(shù)isempty（）清空函數(shù)clear（）取棧頂函數(shù)getpop（）進棧與出棧函數(shù)push（）Pop（）盤空函數(shù)isempty（）清空函數(shù)clear（）取棧頂函數(shù)getpop（）進棧與出棧函數(shù)push（）Pop（）構(gòu)造與析構(gòu)函數(shù)stack（）~stack（）結(jié)點模塊Node*top結(jié)點數(shù)據(jù)類型模塊datatype類結(jié)點數(shù)據(jù)類型模塊datatype類迷宮游戲數(shù)據(jù)結(jié)構(gòu)全文共24頁，當(dāng)前為第4頁。迷宮游戲數(shù)據(jù)結(jié)構(gòu)全文共24頁，當(dāng)前為第4頁。2.畫出主要數(shù)據(jù)結(jié)構(gòu)的類圖class類名DataType//定義描述迷宮中當(dāng)前位置的類型數(shù)據(jù)成員訪問控制權(quán)限數(shù)據(jù)類型變量名;public: intx;//x代表當(dāng)前位置的行坐標(biāo)inty;//y代表當(dāng)前位置的列坐標(biāo)intdir;//dir表示移動到下一步的方向class類名Move//定義下一個位置的方向數(shù)據(jù)成員訪問控制權(quán)限數(shù)據(jù)類型變量名;public: intx;inty;class類名Node//結(jié)點數(shù)據(jù)成員訪問控制權(quán)限數(shù)據(jù)類型變量名;public:DataTypedata;Node*next;class類名stack數(shù)據(jù)成員訪問控制權(quán)限數(shù)據(jù)類型變量名;private:Node*top;//指向第一個結(jié)點的棧頂指針成員函數(shù)訪問控制權(quán)限返回值類型函數(shù)名(參數(shù)列表)public:stack();//構(gòu)造函數(shù)，置空棧~stack();//析構(gòu)函數(shù)voidPush(DataTypedata);//把元素data壓入棧中DataTypePop();//使棧頂元素出棧DataTypeGetPop();//取出棧頂元素voidClear();//把棧清空boolIsEmpty();//判斷棧是否為空，如果為空則返回1，否則返回0迷宮游戲數(shù)據(jù)結(jié)構(gòu)全文共24頁，當(dāng)前為第5頁。迷宮游戲數(shù)據(jù)結(jié)構(gòu)全文共24頁，當(dāng)前為第5頁。開始3.main函數(shù)流程圖開始顯示系統(tǒng)信息顯示系統(tǒng)信息選擇獲取迷宮的方式ch選擇獲取迷宮的方式chCh==Ch==’b’Ch==’a’Readfile()文件讀取Readfile()文件讀取自行輸入Writefile（）探索迷宮路徑是否存在探索迷宮路徑是否存在輸出迷宮路徑輸出迷宮路徑是否繼續(xù)游戲是否繼續(xù)游戲退出退出迷宮游戲數(shù)據(jù)結(jié)構(gòu)全文共24頁，當(dāng)前為第6頁。迷宮游戲數(shù)據(jù)結(jié)構(gòu)全文共24頁，當(dāng)前為第6頁。開始2.探索路徑函數(shù)findpath（）開始TTemp1.x=1Temp1.y=1入口進棧p.push入口進棧p.pushq.push是否非空是否非空temp2=q.getpop（）temp2=q.getpop（）PPq棧頂是否相等探索上下左右四個方位是否有路徑探索上下左右四個方位是否有路徑到達新位置到達新位置是否到達出口是否到達出口最后一個元素進棧輸出路徑最后一個元素進棧輸出路徑回復(fù)以改變的迷宮回復(fù)以改變的迷宮結(jié)束結(jié)束迷宮游戲數(shù)據(jù)結(jié)構(gòu)全文共24頁，當(dāng)前為第7頁。迷宮游戲數(shù)據(jù)結(jié)構(gòu)全文共24頁，當(dāng)前為第7頁。開始3.自行輸入迷宮函數(shù)writefile（）開始輸入長寬m，n輸入長寬m，n動態(tài)申請空間二位數(shù)組空間i<=mi<=m是否保存迷宮是否保存迷宮JJ<=ni++i++；j++輸入迷宮輸入保存迷宮的文件名輸入保存迷宮的文件名保存迷宮保存迷宮結(jié)束結(jié)束2.2概要設(shè)計1.①構(gòu)建一個二維數(shù)組maze[M+2][N+2]用于存儲迷宮矩陣②自動或手動生成迷宮，即為二維數(shù)組maze[M+2][N+2]賦值③構(gòu)建一個隊列用于存儲迷宮路徑迷宮游戲數(shù)據(jù)結(jié)構(gòu)全文共24頁，當(dāng)前為第8頁。④建立迷宮節(jié)點structpoint,用于存儲迷宮中每個節(jié)點的訪問情況迷宮游戲數(shù)據(jù)結(jié)構(gòu)全文共24頁，當(dāng)前為第8頁。⑤實現(xiàn)搜索算法⑥屏幕上顯示操作菜單2.本程序包含10個函數(shù)：(1)主函數(shù)main()(2)手動生成迷宮函數(shù)shoudong_maze()(3)打印迷宮路徑(若存在路徑)result_maze()(4)入隊enqueue()(5)出隊dequeue()(6)判斷隊列是否為空is_empty()(7)訪問節(jié)點visit()(8)搜索迷宮路徑mgpath()2.3運行結(jié)果及分析迷宮游戲數(shù)據(jù)結(jié)構(gòu)全文共24頁，當(dāng)前為第9頁。迷宮游戲數(shù)據(jù)結(jié)構(gòu)全文共24頁，當(dāng)前為第9頁。迷宮游戲數(shù)據(jù)結(jié)構(gòu)全文共24頁，當(dāng)前為第10頁。迷宮游戲數(shù)據(jù)結(jié)構(gòu)全文共24頁，當(dāng)前為第10頁?？偨Y(jié)通過這段時間的數(shù)據(jù)結(jié)構(gòu)課程設(shè)計，本人對計算機的應(yīng)用，數(shù)據(jù)結(jié)構(gòu)的作用以及C語言的使用都有了更深的了解。尤其是C語言的進步讓我深刻的感受到任何所學(xué)的知識都需要實踐，沒有實踐就無法真正理解這些知識以及掌握它們，使其成為自己的財富。在理論學(xué)習(xí)和上機實踐的各個環(huán)節(jié)中，通過自主學(xué)習(xí)和認(rèn)真聽老師講課分析，我收獲了不少。當(dāng)然也遇到不少的問題，也正是因為這些問題引發(fā)的思考給我?guī)Я耸斋@。從當(dāng)初不喜歡上機寫程序到現(xiàn)在能主動寫程序，從當(dāng)初拿著程序不只如何下手到現(xiàn)在知道如何分析問題，如何用專業(yè)知識解決實際問題的轉(zhuǎn)變，我發(fā)現(xiàn)無論是專業(yè)知識還是動手能力，自己都有很大程度的提高。在這段時間里，我對for、while等的循環(huán)函數(shù)用法更加熟悉，逐漸形成了較好的編程習(xí)慣。在老師的指導(dǎo)幫助下，同學(xué)們課余時間的討論中，這些問題都一一得到了解決。在程序的調(diào)試能力上，無形中得到了許多的提高。例如：頭文件的使用，變量和數(shù)組的范圍問題，定義變量時出現(xiàn)的問題等等。在實際的上機操作過程中，不僅是讓我們了解數(shù)據(jù)結(jié)構(gòu)的理論知識，更重要的是培養(yǎng)解決實際問題的能力，所以相信通過此次實習(xí)可以提高我們分析設(shè)計能力和編程能力，為后續(xù)課程的學(xué)習(xí)及實踐打下良好的基礎(chǔ)。時間過得真快，大學(xué)生活不知不覺就走過了一學(xué)期，這一學(xué)期的大學(xué)學(xué)習(xí)和課程實踐階段的提高，使我們本身知識得到提高的同時，也增強了我們對未來工作的信心，我們相信自己未來兩年半的學(xué)習(xí)更使我們有能力勝任將來的工作。迷宮游戲數(shù)據(jù)結(jié)構(gòu)全文共24頁，當(dāng)前為第11頁。迷宮游戲數(shù)據(jù)結(jié)構(gòu)全文共24頁，當(dāng)前為第11頁。源程序#include<iostream>usingnamespacestd;classT//定義描述迷宮中當(dāng)前位置的結(jié)構(gòu)類型{public:intx;//x代表當(dāng)前位置的行坐標(biāo)inty;//y代表當(dāng)前位置的列坐標(biāo)intdir;//0:無效,1:東,2:南,3:西,4:北};classLinkNode//鏈表結(jié)點{friendclassStack;public:Tdata;LinkNode*next;};classStack迷宮游戲數(shù)據(jù)結(jié)構(gòu)全文共24頁，當(dāng)前為第12頁。{迷宮游戲數(shù)據(jù)結(jié)構(gòu)全文共24頁，當(dāng)前為第12頁。private:LinkNode*top;//指向第一個結(jié)點的棧頂指針public:Stack();//構(gòu)造函數(shù)，置空棧~Stack()//析構(gòu)函數(shù){}voidPush(Te);//元素data入棧中TPop();//棧頂元素出棧TGetPop();//取出棧頂元素voidClear();//把棧清空boolempty();//判斷棧是否為空，如果為空則返回1，否則返回0};Stack::Stack()//構(gòu)造函數(shù)，置空棧{top=NULL;}voidStack::Push(Te)//元素x入棧中{LinkNode*P;P=newLinkNode;迷宮游戲數(shù)據(jù)結(jié)構(gòu)全文共24頁，當(dāng)前為第13頁。P->data=e;迷宮游戲數(shù)據(jù)結(jié)構(gòu)全文共24頁，當(dāng)前為第13頁。P->next=top;top=P;}TStack::Pop()//棧頂元素出棧{TTemp;LinkNode*P;P=top;top=top->next;Temp=P->data;deleteP;returnTemp;}TStack::GetPop()//取出棧頂元素{returntop->data;}voidStack::Clear()//把棧清空{(diào)迷宮游戲數(shù)據(jù)結(jié)構(gòu)全文共24頁，當(dāng)前為第14頁。top=NULL;迷宮游戲數(shù)據(jù)結(jié)構(gòu)全文共24頁，當(dāng)前為第14頁。}boolStack::empty()//判斷棧是否為空，如果為空則返回1，否則返回0{if(top==NULL)return1;elsereturn0;}intmove[4][2]={{0,1},{1,0},{0,-1},{-1,0}};//定義當(dāng)前位置移動的4個方向voidPrintPath(Stackp)//輸出路徑{cout<<"迷宮的路徑為\n";cout<<"括號內(nèi)的內(nèi)容分別表示為(行坐標(biāo),列坐標(biāo),數(shù)字化方向,方向)\n";Stackt;//定義一個棧，按從入口到出口存取路徑inta,b;Tdata;LinkNode*temp;temp=newLinkNode;//獲取空間temp->data=p.Pop();//取棧p的頂點元素，即第一個位置t.Push(temp->data);//第一個位置入棧tdeletetemp;//釋放空間迷宮游戲數(shù)據(jù)結(jié)構(gòu)全文共24頁，當(dāng)前為第15頁。while(!p.empty())//如果棧p非空，則反復(fù)轉(zhuǎn)移迷宮游戲數(shù)據(jù)結(jié)構(gòu)全文共24頁，當(dāng)前為第15頁。{temp=newLinkNode;temp->data=p.Pop();//獲取下一個位置//得到行走方向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表示elseif(b==1)temp->data.dir=2;//方向向右，用2表示elseif(a==-1)temp->data.dir=3;//方向向上，用3表示elseif(b==-1)temp->data.dir=4;//方向向左，用4表示t.Push(temp->data);//把新位置入棧deletetemp;}//輸出路徑，包括行坐標(biāo)，列坐標(biāo)，下一個位置方向while(!t.empty())//棧非空，繼續(xù)輸出{data=t.Pop();cout<<'('<<data.x<<','<<data.y<<','<<data.dir<<",";//輸出行坐標(biāo)，列坐標(biāo)switch(data.dir)//輸出相應(yīng)的方向{case1:cout<<"↓)\n";break;case2:cout<<"→)\n";break;case3:cout<<"↑)\n";break;迷宮游戲數(shù)據(jù)結(jié)構(gòu)全文共24頁，當(dāng)前為第16頁。case4:cout<<"←)\n";break;迷宮游戲數(shù)據(jù)結(jié)構(gòu)全文共24頁，當(dāng)前為第16頁。case0:cout<<")\n";break;}}}voidRestore(int**maze,intm,intn)//恢復(fù)迷宮{inti,j;for(i=0;i<m+2;i++)//遍歷指針for(j=0;j<n+2;j++){if(maze[i][j]==-1)//恢復(fù)探索過位置，即把-1恢復(fù)為0maze[i][j]=0;}}int**GetMaze(int&m,int&n)//返回存取迷宮的二維指針{int**maze;//定義二維指針存取迷宮inti=0,j=0;cout<<"請輸入迷宮的長和寬:";inta,b;cin>>a>>b;//輸入迷宮的長和寬迷宮游戲數(shù)據(jù)結(jié)構(gòu)全文共24頁，當(dāng)前為第17頁。cout<<"請輸入迷宮內(nèi)容:(0為通路，1為墻)\n";迷宮游戲數(shù)據(jù)結(jié)構(gòu)全文共24頁，當(dāng)前為第17頁。m=a;n=b;//m,n分別代表迷宮的行數(shù)和列數(shù)maze=newint*[m+2];//獲取長度等于行數(shù)加2的二級指針for(i=0;i<m+2;i++)//每個二維指針的空間{maze[i]=newint[n+2];}for(i=1;i<=m;i++)//輸入迷宮的內(nèi)容，0代表可通，1代表不通for(j=1;j<=n;j++)cin>>maze[i][j];for(i=0;i<m+2;i++)maze[i][0]=maze[i][n+1]=1;for(i=0;i<n+2;i++)maze[0][i]=maze[m+1][i]=1;returnmaze;//返回存貯迷宮的二維指針maze};boolMazepath(int**maze,intm,intn)//尋找迷宮maze中從（0，0）到（m,n）的路徑{Stackq,p;//定義棧p、q,分別存探索迷宮的過程和存儲路徑TTemp1,Temp2;迷宮游戲數(shù)據(jù)結(jié)構(gòu)全文共24頁，當(dāng)前為第18頁。intx,y,loop;迷宮游戲數(shù)據(jù)結(jié)構(gòu)全文共24頁，當(dāng)前為第18頁。Temp1.x=1;Temp1.y=1;q.Push(Temp1);//將入口位置入棧p.Push(Temp1);maze[1][1]=-1;//標(biāo)志入口位置已到達過while(!q.empty())//棧q非空，則反復(fù)探索{Temp2=q.GetPop();//獲取棧頂元素if(!(((p.GetPop().x)==(q.GetPop().x))&&((p.GetPop().y)==(q.GetPop().y))))p.Push(Temp2);//如果有新位置入棧，則把上一個探索的位置存入棧pfor(loop=0;loop<4;loop++)//探索當(dāng)前位置的4個相鄰位置{x=Temp2.x+move[loop][0];//計算出新位置x位置值y=Temp2.y+move[loop][1];//計算出新位置y位置值if(maze[x][y]==0)//判斷新位置是否可達{Temp1.x=x;Temp1.y=y;maze[x][y]=-1;//標(biāo)志新位置已到達過q.Push(Temp1);//新位置入棧}迷宮游戲數(shù)據(jù)結(jié)構(gòu)全文共24頁，當(dāng)前為第19頁。if((x==(m))&&(y==(n)))//成功到達出口迷宮游戲數(shù)據(jù)結(jié)構(gòu)全文共24頁，當(dāng)前為第19頁。{Temp1.x=m;Temp1.y=n;Temp1.dir=0;p.Push(Temp1);//把最后一個位置入棧PrintPath(p);//輸出路徑Restore(maze,m,n);//恢復(fù)路徑return1;//表示成功找到路徑}}if(p.GetPop().x==q.GetPop().x&&p.GetPop().y==q.GetPop().y)//如果沒有新位置入棧，則返回到上一個位置{p.Pop();q.Pop();}}return0;//表示查找失敗，即迷宮無路經(jīng)}intmain(){迷宮游戲數(shù)據(jù)結(jié)構(gòu)全文共24頁，當(dāng)前為第20頁。intm=0,n=0;//定義迷宮的長和寬迷宮游戲數(shù)據(jù)結(jié)構(gòu)全文共24頁，當(dāng)前為第20頁。int**maze;//定義二維指針存取迷宮maze=GetMaze(m,n);//調(diào)用GetMaze(int&m,int&n)函數(shù)，得到迷宮if(Mazepath(maze,m,n))//調(diào)用Mazepath(int**maze,intm,intn)函數(shù)獲取路徑cout<<"迷宮路徑探索成功!\n";elsecout<<"路徑不存在!\n";return0;}迷宮游戲數(shù)據(jù)結(jié)構(gòu)全文共24頁，當(dāng)前為第21頁。迷宮游戲數(shù)據(jù)結(jié)構(gòu)全文共24頁，當(dāng)前為第21頁。參考文獻[1]嚴(yán)蔚敏吳偉民數(shù)據(jù)結(jié)構(gòu)（C語言版）清華大學(xué)出版社，2000[2]文益民周學(xué)毛李健數(shù)據(jù)結(jié)構(gòu)與程序設(shè)計人民郵電出版社2008[3]譚浩強C程序設(shè)計（第三版）清華大學(xué)出版設(shè)2008[4]林銳韓永泉高質(zhì)量程序設(shè)計指南—C++/C語言第3版2007目錄TOC\o"1-2"\h\z\u第一章總論 1第一節(jié)項目名稱及承辦單位 1第二節(jié)研究工作的依據(jù)與范圍 2第三節(jié)簡要研究結(jié)論 3第四節(jié)主要經(jīng)濟技術(shù)指標(biāo) 5第二章項目提出的背景及必要性 7第一節(jié)項目提出的背景 7第二節(jié)項目建設(shè)的必要性 13第三章市場預(yù)測與需求分析 19第一節(jié)車用生物燃?xì)馐袌霭l(fā)展分析 19第二節(jié)有機肥市場分析 23第四章建設(shè)規(guī)模與產(chǎn)品方案 29第一節(jié)建設(shè)規(guī)模 29第二節(jié)產(chǎn)品方案 29第五章廠址選擇與建設(shè)條件 31第一節(jié)廠址方案 31迷宮游戲數(shù)據(jù)結(jié)構(gòu)全文共24頁，當(dāng)前為第22頁。第二節(jié)建設(shè)條件 32迷宮游戲數(shù)據(jù)結(jié)構(gòu)全文共24頁，當(dāng)前為第22頁。第六章工藝技術(shù)方案 40第一節(jié)項目組成 40第二節(jié)生產(chǎn)技術(shù)方案 40第三節(jié)生產(chǎn)設(shè)備 53第七章原輔材料供應(yīng) 56第一節(jié)原輔材料供應(yīng) 56第二節(jié)公用設(shè)施 58第八章工程建設(shè)方案 59第一節(jié)總圖運輸 59第二節(jié)建筑結(jié)構(gòu)工程 62第三節(jié)公用工程 70第九章環(huán)境保護、勞動安全衛(wèi)生 75第一節(jié)環(huán)境保護 75第二節(jié)勞動安全衛(wèi)生 77第十章節(jié)能與消防