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

上傳人：奔*** IP屬地：河北更新時(shí)間：2024-03-01 格式：doc 頁數(shù)：23 大小：186.00KB 人氣指數(shù)：12 舉報(bào) 版權(quán)申訴

已閱讀1頁，還剩22頁未讀，繼續(xù)免費(fèi)閱讀

版權(quán)說明：本文檔由用戶提供并上傳，收益歸屬內(nèi)容提供方，若內(nèi)容存在侵權(quán)，請(qǐng)進(jìn)行舉報(bào)或認(rèn)領(lǐng)

文檔簡介

1、　　數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)　　說明書　　學(xué) 院：信息科學(xué)與工程學(xué)院 　　班級(jí)：計(jì)算機(jī)科學(xué)與技術(shù) 2009級(jí)6班 　　完

2、成人：姓名：學(xué) 號(hào)： 　　指導(dǎo)教師： 　　2010年12月31日　　課程設(shè) 計(jì) 任務(wù) 書　　一、課程設(shè)計(jì)題目：迷宮問題

3、 　　二、課程設(shè)計(jì)應(yīng)解決的主要問題：　?。?）實(shí)現(xiàn)一個(gè)以鏈表做存儲(chǔ)結(jié)構(gòu)的隊(duì)列類型； 　?。?）編寫一個(gè)求解迷宮的非遞歸程序； 　　（3）求得的通路以二元組的形式輸出，

4、寫清楚第幾步 　?。?）以方陣的形式輸出迷宮及其通路 　　三、任務(wù)發(fā)出日期： 2010-9-20 課程設(shè)計(jì)完成日期： 2011-01-07 　　小組分工說明<p&g

5、t;　　小組編號(hào) 43 題目：迷宮問題 　　小組分工情況：獨(dú)自一人完成題目要求　　組長簽字： 　　年月日　　指導(dǎo)教師對(duì)課程

6、設(shè)計(jì)的評(píng)價(jià)　　成績： 　　指導(dǎo)教師簽字： 　　年月日 　　目錄　　需求分析說明 …………………………………

7、………51.1求迷宮通路的總體功能要求………………………………51.2主函數(shù)模塊……………………………………………………51.3隊(duì)列的存儲(chǔ)功能及輸出結(jié)點(diǎn)功能…………………………51.4構(gòu)建迷宮找出迷宮的通路…………………………………5　　1.5 測(cè)試數(shù)據(jù)…………………………………………………………………………..6　　概要設(shè)計(jì)說明 …………………

8、…………………………………62.1 模板的調(diào)用說明………………………………………………62.2 隊(duì)列的抽象數(shù)據(jù)類型定義…………………………………62.3 基本操作及函數(shù)功能………………………………………6　　詳細(xì)設(shè)計(jì)說明 ……………………………………………………73.1 主函數(shù)模塊…………………………………………………73.2 隊(duì)列的存儲(chǔ)功能及輸出結(jié)點(diǎn)功能………………………73.3

9、構(gòu)建迷宮找出迷宮的通路…………………………………8　　調(diào)試分析 …………………………………………………………8　　用戶使用說明 ……………………………………………………8　　5.1程序運(yùn)行的初始界面………………………………………………….......9　　5.2迷宮可通時(shí)

10、的界面……………………………………………………….10　　5.3迷宮不可通時(shí)的界面………………………………………………….11　　5.4迷宮沒有入口時(shí)的界面……………………………………………...12　　6課程設(shè)計(jì)總結(jié) ……………………………………………………12　　7測(cè)

11、試結(jié)果 ……………………………………………….13　　8參考書目………………………………………………..13　　9程序代碼………………………………………………..14　　需求分析說明　　求迷宮通路的總體功能要求：

12、　　求迷宮中從入口到出口的所有路徑。由于計(jì)算機(jī)解迷宮時(shí)通常用的是“窮舉求解”的方法，即從入中出發(fā)，順某一方向向前探索，若能走通，則繼續(xù)往前走否則沿原路退回，換一個(gè)方向再繼續(xù)探索，直至所有可能的通路都探索到為止。　　基本功能如下：　?、?界面友好，易于操作。利用提示完成走出迷宮的任務(wù)。</p

13、>　　⑵ 實(shí)現(xiàn)以鏈表作存儲(chǔ)結(jié)構(gòu)的隊(duì)列類型。　　⑶ 實(shí)現(xiàn)建立一個(gè)隨機(jī)的迷宮，并且走出迷宮的操作。　　以下是各功能模塊的功能描述：　　1．主函數(shù)模塊　　本模塊的主要功能是初始化圖形界面，調(diào)用各模塊，實(shí)現(xiàn)走出迷宮

14、的功能。　　2．隊(duì)列的存儲(chǔ)功能及輸出結(jié)點(diǎn)功能　　本模塊的主要功能是建立隊(duì)列，實(shí)現(xiàn)隊(duì)列的各個(gè)基本操作，如構(gòu)建一個(gè)空隊(duì)列，往隊(duì)尾插入元素，刪除隊(duì)頭元素，取隊(duì)尾元素，取隊(duì)頭元素，判斷隊(duì)列是否為空，遍歷隊(duì)鏈的每個(gè)元素，輸出每個(gè)元素，銷毀隊(duì)鏈。　　3．構(gòu)建迷宮找出迷宮的通路　　本模

15、塊的主要功能是隨機(jī)初始化一個(gè)迷宮并輸出，實(shí)現(xiàn)走出迷宮的操作，再輸出走完后的迷宮及走出迷宮所走的路徑。　　測(cè)試數(shù)據(jù)　　1. （1，5）（4，8）　　2. （0，0）（9，9）　　3. （11，11）（11，11）

16、　　概要設(shè)計(jì)說明　　模板調(diào)用說明：　　隊(duì)列的抽象數(shù)據(jù)類型定義為：　　ADT Queue{　　數(shù)據(jù)對(duì)象： D={Ai | Ai ∈ElemSet,i=1,2,…,n, n&g

17、t;=0}數(shù)據(jù)關(guān)系：R1={<Ai-1,Ai>|Ai-1,Ai∈D,i=1,2,…,n}}　　約定其中a1端為隊(duì)列頭，an端為隊(duì)列尾。　　基本操作：　　Status InitQueue (LinkQueue &Q)//構(gòu)造一個(gè)空隊(duì)列Q,隊(duì)列有一個(gè)頭結(jié)點(diǎn)&

18、lt;/p>　　Status DestroyQueue(LinkQueue &Q) //銷毀隊(duì)列Q　　Status EnQueue(LinkQueue &Q,QElemType e)//插入元素e為Q的新的隊(duì)尾元素　　Status DeQueue(LinkQueue &Q,QElemType

19、&e)//若隊(duì)列不空,則刪除Q的對(duì)頭元素,用e返回其值,并返回OK;否則返回ERROR　　Status GetHead(LinkQueue Q,QElemType &e)//若隊(duì)列不空，則用e返回Q的隊(duì)頭元素，并返回OK；否則返回ERROR　　Status GetRear(LinkQueue Q,QElemType &e)//若隊(duì)

20、列不空，則用e返回Q的隊(duì)尾元素，并返回OK；否則返回ERROR　　Status DeRear(LinkQueue &Q,QElemType &e)//若隊(duì)列不空，利用循環(huán)彈出Q的隊(duì)尾元素，并返回OK；否則返回ERROR　　Status QueueEmpty(LinkQueue Q)//若隊(duì)列Q為空隊(duì)列，則返回TURE，否則返回FALSE&

21、lt;/p>　　Status QueueTraverse(LinkQueue Q,Status (*visit)(QElemType))//從隊(duì)頭到隊(duì)尾依次對(duì)隊(duì)列Q中每個(gè)元素調(diào)用函數(shù)visit()。一旦visit失敗，則操作失敗　　Status PrintQElem (QElemType e)//輸出隊(duì)列中的元素　　Statu

22、s MakeMaze(MazeType &maze)//生成迷宮,"0"表示通PATH，"1"表示不通WALL　　void PrintMaze(MazeType maze)//把迷宮輸出　　PosType Nextpos(PosType position,ElemType direction)移動(dòng)到下一格,

23、向下走一步　　StatusPassMaze(MazeType&maze,PosTypestart,PosTypeend,LinkQueue &Q)//找出迷宮的一條通路　　void main()//主函數(shù)，調(diào)用各個(gè)子函數(shù)　　詳細(xì)設(shè)計(jì)說明

24、　　1．主函數(shù)模塊　　首先調(diào)用InitQueue函數(shù)，構(gòu)造一個(gè)空隊(duì)列，然后調(diào)用MakeMaze函數(shù)，隨機(jī)生成一個(gè)迷宮，再調(diào)用PrintMaze函數(shù)，讓迷宮顯示在屏幕上，讓用戶輸入迷宮的入口和出口，再調(diào)用PassMaze，判斷迷宮是否有通路，如有則輸出迷宮可通及所走路徑。如沒有則輸出迷宮不可通及所走路徑。最后銷毀隊(duì)列，退出程序。</p&

25、gt;　　2．隊(duì)列的存儲(chǔ)功能及輸出結(jié)點(diǎn)功能　　在實(shí)現(xiàn)隊(duì)列的存儲(chǔ)功能時(shí)，首先定義單鏈隊(duì)列的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)，然后定義隊(duì)列的各種基本操作的函數(shù)，其中定義的函數(shù)有構(gòu)造一個(gè)空隊(duì)列的函數(shù)InitQueue，銷毀隊(duì)列的函數(shù)DestroyQueue，向隊(duì)尾插入元素的函數(shù)EnQueue，刪除隊(duì)頭元素的函數(shù)DeQueue，取隊(duì)頭元素的函數(shù)GetHead，利用循環(huán)彈出隊(duì)尾元素的函數(shù)DeRear，判

26、斷隊(duì)列是否為空的函數(shù)QueueEmpty。　　在實(shí)現(xiàn)輸出隊(duì)列的結(jié)點(diǎn)功能時(shí)，定義了從隊(duì)頭到隊(duì)尾依次對(duì)隊(duì)列中每個(gè)元素調(diào)用函數(shù)visit()的遍歷函數(shù)QueueTraverse，及輸出隊(duì)列元素的輸出函數(shù)PrintQElem。　　3．構(gòu)建迷宮找出迷宮的通路　　在實(shí)現(xiàn)構(gòu)建迷宮的功能中，利用srand(time(NULL))

27、使計(jì)算機(jī)自動(dòng)讀取自己的時(shí)鐘獲得SEED值，獲得真正的隨機(jī)數(shù)，利用循環(huán)調(diào)用函數(shù)rand()再對(duì)2取余，只獲得數(shù)0和1也就是迷宮中的墻和通路，再調(diào)用函數(shù)PrintQElem輸出初始迷宮。調(diào)用函數(shù)Nextpos，找通路的時(shí)候向前走一步，再調(diào)用函數(shù)PassMaze，找出迷宮的一條通路。 　　調(diào)試分析　　我在調(diào)試程序的過程中遇

28、到的問題是當(dāng)迷宮的路可通時(shí)，輸出的所走路徑是亂碼，主要問題是如果判斷出一個(gè)通道塊不可通時(shí)，已經(jīng)把它放入隊(duì)列當(dāng)中，如果再把它彈出時(shí)不能像棧那個(gè)樣直接調(diào)用出棧函數(shù)，因?yàn)闂Ｊ窍冗M(jìn)后出的存儲(chǔ)結(jié)構(gòu)，最新壓入的元素就能直接取出，而對(duì)于隊(duì)列來說新入隊(duì)的元素放在了隊(duì)尾，而出隊(duì)函數(shù)是把隊(duì)頭元素給輸出，不是新入隊(duì)的元素。因此，如果要用隊(duì)列模擬棧的功能，要解決的問題是，從隊(duì)頭開始依次將隊(duì)列的隊(duì)頭元素給輸出，再把該元素放入隊(duì)列當(dāng)中，只到遇到新插入的元素，只把它

29、彈出，就是把那個(gè)不可通的通道給彈出了，再往后退一步。修改過這個(gè)地方之后當(dāng)路徑可通時(shí)，輸出的所走路徑就不是亂碼而是真正所走的通道塊坐標(biāo)。　　用戶使用說明　　編譯程序，出現(xiàn)有迷宮的界面，如下圖1所示，按提示輸入迷宮的入口位置坐標(biāo)和出口位置坐標(biāo)，再運(yùn)行程序。如果迷宮有通路會(huì)輸出“迷宮可通，路徑蹤跡如下：”，輸出走過之后的迷

30、宮，然后再輸出具體路徑，如下圖2所示。如果迷宮不可通時(shí)，會(huì)輸出“迷宮不可通，路徑蹤跡如下：”，輸出走過之后的迷宮，如下圖3所示。如果迷宮沒有入口時(shí)，會(huì)輸出“當(dāng)前迷宮沒有入口”，“迷宮不可通，路徑蹤跡如下：”輸出迷宮，如下圖4所示。　　程序運(yùn)行的初始界面：　　圖1<b&g

31、t;　　迷宮可通時(shí)的界面：　　圖2　　迷宮不可通時(shí)的界面：　　圖3　　迷宮沒有入口時(shí)的界面：　　圖4</b&g

32、t;　　課程設(shè)計(jì)總結(jié)　　通過這次的課程設(shè)計(jì)作業(yè)，讓我真正的知道了棧的先進(jìn)后出的存儲(chǔ)結(jié)構(gòu)特點(diǎn)和隊(duì)列的先進(jìn)先出的存儲(chǔ)結(jié)構(gòu)特點(diǎn)的區(qū)別，而做迷宮求解的問題當(dāng)中最好用的存儲(chǔ)結(jié)構(gòu)是棧，如果用隊(duì)列做為存儲(chǔ)結(jié)構(gòu)，就要利用循環(huán)來讓隊(duì)列模擬棧的先進(jìn)后出的存儲(chǔ)結(jié)構(gòu)特點(diǎn)。　　還讓我知道了用計(jì)算機(jī)求解

33、迷宮時(shí)，用的是“窮舉求解”的方法，即從入中出發(fā)，順某一方向向前探索，若能走通，則繼續(xù)往前走；否則沿原路退回，換一個(gè)方向再繼續(xù)探索，直至所有可能的通路都探索到為止。為了保證在任何位置上都能沿原路退回，顯然需要用一個(gè)后進(jìn)先出的結(jié)構(gòu)來保存從入口到當(dāng)前位置的路徑。因此，在求迷宮通路的算法中最好是應(yīng)用“?！?，如果要用“隊(duì)列”的話，就要用隊(duì)列來模擬棧的存儲(chǔ)結(jié)構(gòu)特點(diǎn)。　　測(cè)試結(jié)果</b

34、>　　輸入（0，0）到（9，9）時(shí)，輸出結(jié)果為：“當(dāng)前迷宮沒有入口”，“迷宮不可通，路徑蹤跡如下：”并輸出迷宮。　　輸入（11，11）到（11，11）時(shí)，輸出結(jié)果為：“當(dāng)前迷宮沒有入口”，“迷宮不可通，路徑蹤跡如下：”并輸出迷宮。　　輸入（1，1）到（8，7）時(shí)，輸出結(jié)果為：“迷宮可通，路徑蹤跡如下：”并輸

35、出走過之后的迷宮及具體路徑。　　輸入（1，1）到（6，6）時(shí)，輸出結(jié)果為：“迷宮不可通，路徑足跡如下：”并輸出走過之后的迷宮。　　參考書目　　數(shù)據(jù)結(jié)構(gòu)（C語言版）嚴(yán)蔚敏吳偉民清華大學(xué)出版社　　數(shù)據(jù)結(jié)構(gòu)題集（C語言版）嚴(yán)蔚敏吳偉民

36、米寧清華大學(xué)出版社 　　程序代碼　　#include<stdio.h>　　#include<malloc.h>　　#include<stdlib.h>

37、　#include<time.h>　　#include<math.h>　　//函數(shù)狀態(tài)碼定義　　#define TRUE 1　　#define FALSE 0&

38、lt;p>　　#define OK 1　　#define ERROR 0　　#define INFEASIBLE -1　　#define NULL 0 　　//墻或通路及前進(jìn)方向符號(hào)定義<

39、p>　　#define WALL 0 //代表當(dāng)前格子是墻　　#define PATH 1 //代表是通路且未走過　　#define RIGHT -1 //代表是通路且從其向右走　　#define DOWN -2 //代表是通路且從其向下走&l

40、t;/p>　　#define LEFT -3 //代表是通路且從其向左走　　#define UP -4 //代表是通路且從其向上走　　#define BACK -5 //代表是通路且從其后退一步　　#define DESTINATION -

41、6 //代表當(dāng)前格子是通路且是目標(biāo)位置　　typedef int MazeType[10][10]; //最外鑿初始化成墻，實(shí)際含8*8個(gè)格子　　typedef int Status;　　typedef int ElemType; //迷宮數(shù)組中的元素類型　　//－－－

42、－－－－－－單鏈隊(duì)列--隊(duì)列的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)－－－－－//　　typedef struct　　{　　int x;　　int y;<

43、p>　　}PosType;//迷宮中坐標(biāo)的位置　　typedef struct{　　int ord; //通道塊在路徑上的序號(hào)　　PosType seat; //通道塊在迷宮中的坐標(biāo)位置

44、　int di; //從此通道塊走向下一通道塊的方向　　}QElemType; //隊(duì)列中元素類型　　typedef struct QNode　　{

45、QElemType data;　　struct QNode *next;　　}QNode,*QueuePtr; //隊(duì)列結(jié)點(diǎn)　　typedef struct　　{　　Queu

46、ePtr front; //隊(duì)頭指針　　QueuePtr rear; //隊(duì)尾指針　　}LinkQueue;　　Status InitQueue (LinkQueue &Q) //構(gòu)造一個(gè)空隊(duì)列Q,隊(duì)列有一個(gè)頭結(jié)點(diǎn)　　{&

47、lt;/b>　　Q.front=(QueuePtr)malloc(sizeof(QNode));　　Q.rear=Q.front;　　if(!Q.front) exit(OVERFLOW); //存儲(chǔ)分配失敗　　Q.front->next=NULL;

48、　　return OK;　　}//InitQueue　　Status DestroyQueue(LinkQueue &Q) //銷毀隊(duì)列Q　　{　　while(Q.front

49、)　　{　　Q.rear = Q.front->next;　　free(Q.front);　　Q.front = Q.rear;　　}</p&

50、gt;　　return OK;　　}//DestroyQueue　　Status EnQueue(LinkQueue &Q,QElemType e) //插入元素e為Q的新的對(duì)尾元素 　　{<p&

51、gt;　　QueuePtr p;　　p=(QueuePtr)malloc(sizeof(QNode));　　if(!p) exit (OVERFLOW); //存儲(chǔ)分配失敗　　p->data = e;　　p->nex

52、t = NULL;　　Q.rear ->next = p;　　Q.rear = p;　　return OK;　　}//EnQueue　　Status DeQueue(LinkQueue &Q,QElemType &a

53、mp;e) 　　{　　//若隊(duì)列不空,則刪除Q的對(duì)頭元素,用e返回其值,并返回OK;否則返回ERROR　　QueuePtr p;　　if (Q.front == Q.rear ) return ERROR;

54、;　　p=Q.front ->next ;　　e=p->data ;　　Q.front ->next =p->next ;　　if(Q.rear == p) //判斷刪除后隊(duì)列是否為空　　Q.rear =Q.

55、front ; //隊(duì)列已為空　　free (p);　　return OK;　　}//DeQueue　　Status GetHead(LinkQueue Q,QElemType &e) &

56、lt;p>　　{ 　　//若隊(duì)列不空，則用e返回Q的隊(duì)頭元素，并返回OK；否則返回ERROR　　QueuePtr p;　　if(Q.rear ==Q.front ) return ERROR;　　p=Q.front->

57、;next; 　　e=p->data ; //取隊(duì)頭元素　　return OK;　　}//GetHead　　Status GetRear(LinkQueue Q,QElemType &e) <b&g

58、t;　　{ 　　//若隊(duì)列不空，則用e返回Q的隊(duì)尾元素，并返回OK；否則返回ERROR　　QueuePtr p;　　if(Q.rear ==Q.front ) return ERROR;　　p=Q.rear; <p

59、>　　e=p->data ; //取隊(duì)尾元素　　return OK;　　}//GetRear　　Status DeRear(LinkQueue &Q,QElemType &e)　　{//若隊(duì)列不空，利用循環(huán)彈出Q的隊(duì)尾元素，并返回OK；否

60、則返回ERROR　　QueuePtr p;　　if(Q.rear ==Q.front ) return ERROR;　　p=Q.rear;　　while(Q.front->next!=p)<p

61、>　　{　　DeQueue(Q,e); //刪除隊(duì)頭元素　　EnQueue(Q,e); //將刪除的隊(duì)頭元素插入隊(duì)尾　　}　　DeQueue(Q,e);

62、 //將原來的隊(duì)尾元素彈出，相當(dāng)于棧的功能　　return OK;　　}//DeRear　　Status QueueEmpty(LinkQueue Q) 　　{&l

63、t;/p>　　//若隊(duì)列Q為空隊(duì)列，則返回TURE，否則返回FALSE　　if(Q.rear == Q.front ) 　　return TRUE;　　else 　　return FALSE;<

64、;/p>　　}//QueueEmpty　　Status QueueTraverse(LinkQueue Q,Status (*visit)(QElemType)) 　　{　　//從隊(duì)頭到隊(duì)尾依次對(duì)隊(duì)列Q中每個(gè)元素調(diào)用函數(shù)visit()。一旦visi

65、t失敗，則操作失敗。　　QueuePtr p=Q.front->next ;　　if(Q.rear ==Q.front ) printf("空隊(duì)列\(zhòng)n");　　else　　while(p!=NULL )

66、　　{　　(*visit) (p->data );　　p=p->next;　　}　　return OK;<p&g

67、t;　　}//QueueTraverse　　Status PrintQElem (QElemType e){　　printf("step:%d to (%d,%d)\n",e.ord,e.seat.x,e.seat.y);　　return OK;　　}

68、//PrintQElem　　//------------------- 迷宮求解的具體算法 ------------------//　　Status MakeMaze(MazeType &maze) 　　{

69、　//生成迷宮,"0"表示通PATH，"1"表示不通WALL　　PosType m;　　srand(time(NULL)); //使計(jì)算機(jī)自動(dòng)讀取自己的時(shí)間獲得SEED值，獲得真正的隨機(jī)數(shù)　　for(m.y=0;m.y<=9;m.y++)</p&

70、gt;　　{　　maze[0][m.y]=WALL;　　maze[9][m.y]=WALL;　　}　　for(m.x=1;m.x<=8;m.x++)

71、;　　{　　maze[m.x][0]=WALL;　　maze[m.x][9]=WALL;　　}　　for(m.x=1;m.x<=8;m.x++)

72、　　for(m.y=1;m.y<=8;m.y++)　　maze[m.x][m.y]=rand()%2;//隨機(jī)取到0到RAND_MAX之間的任何數(shù)，對(duì)2取余是只產(chǎn)生0，1，就是迷宮中的墻和路　　return OK;　　}//MakeMaze　　vo

73、id PrintMaze(MazeType maze)　　{　　//打印迷宮　　int x,y;　　printf(" ");</p&

74、gt;　　for(x=0;x<=9;x++)　　{　　printf(" %d",x);　　}　　printf("\n");<

75、;/p>　　for(x=0;x<=9;x++)　　{　　printf("%d",x);　　for(y=0;y<=9;y++)　　{<

76、;/p>　　switch(maze[x][y])　　{　　case WALL:printf("■");break;　　case PATH:printf(" ");break;<

77、p>　　case RIGHT:printf("→");break;　　case DOWN: printf("↓");break;　　case LEFT: printf("←");break;　　case UP: printf("↑&q

78、uot;);break;　　case BACK: printf("@ ");break;　　case DESTINATION:printf("◎");break;　　default:printf("error\n");exit(-1);

79、;　　}　　}　　printf("\n");　　}　　}//PrintMaze<p&g

80、t;　　PosType Nextpos(PosType position,ElemType direction)　　{　　//移動(dòng)到下一格,向下走一步　　PosType result;　　result=position;</p&

81、gt;　　switch (direction)　　{　　case 1:result.y++;break; //向右走　　case 2:result.x++;break; //向下走　　case 3:res

82、ult.y--;break; //向左走　　case 4:result.x--;break; //向上走　　}　　return result;　　}//Nextpos　　Status

83、PassMaze(MazeType &maze,PosType start,PosType end,LinkQueue &Q)　　{　　//找出迷宮的一條通路　　PosType curpos; //迷宮中的坐標(biāo)

84、　　QElemType e;　　int curstep=1;　　curpos=start;　　if(maze[curpos.x][curpos.y]!=PATH) 　　{ 　　printf(&

85、quot;當(dāng)前迷宮沒有入口\n"); 　　return FALSE;　　}　　do{ 　　if(maze[curpos.x][curpos.y]==PATH) //當(dāng)前位置可通&

86、lt;/p>　　{　　e.ord=curstep; //走過的第幾步　　e.seat=curpos; //通道塊在迷宮中的坐標(biāo)　　e.di=1; //將要往右走<p&g

87、t;　　EnQueue(Q,e); //將坐標(biāo)位置插入隊(duì)尾　　if(curpos.x==end.x&&curpos.y==end.y)　　{　　maze[curpos.x][curpos.y]=DESTINATION; //走出迷宮</p&

88、gt;　　return OK;　　}　　else　　{ 　　maze[curpos.x][curpos.y]=RIGHT;

89、 //標(biāo)志為從其向右走　　curpos=Nextpos(curpos,1); //坐標(biāo)向右移動(dòng)下個(gè)格　　curstep++;　　}　　}　　else

90、 //當(dāng)前位置不通　　{　　GetRear(Q,e);//返回隊(duì)尾元素　　while(!QueueEmpty(Q)&&e.di==4)　　{

91、　　maze[e.seat.x][e.seat.y]=BACK; //標(biāo)志為后退一步　　DeRear(Q,e); //將插入隊(duì)尾的元素彈出　　curstep--;　　if(QueueEmpty(Q)) break;　　GetRe

92、ar(Q,e); //取隊(duì)尾元素 　　}　　if(e.di<4) //隊(duì)尾位置有其他方向可以選擇　　{ 　　DeRear(Q,e); //彈出隊(duì)尾

93、元素　　e.di++; 　　EnQueue(Q,e); //將新結(jié)點(diǎn)插入隊(duì)尾　　maze[e.seat.x][e.seat.y]=-e.di; //注意前進(jìn)方向蹤跡與e.di互為相反數(shù)　　curpos=Nextpos(e.

94、seat,e.di);　　}　　}　　}while(!QueueEmpty(Q));　　return FALSE;　　}//PassMaze</p&

95、gt;　　void main(){　　MazeType maze;　　PosType start,end;　　LinkQueue Q;　　InitQueue(Q);　　MakeMaze(maze);</

96、p>　　printf("初始迷宮為：\n");　　PrintMaze(maze);　　printf("輸入迷宮的入口位置坐標(biāo)從(0,0)到(9,9): ");　　scanf("%d,%d",&start.x,&

97、start.y);　　printf("輸入迷宮的出口位置坐標(biāo)從(0,0)到(9,9): ");　　scanf("%d,%d",&end.x,&end.y);　　if(PassMaze(maze,start,end,Q)) //找迷宮通路

98、;　　{　　printf("迷宮可通,路徑蹤跡如下:\n");　　PrintMaze(maze); //輸出走過之后的迷宮　　printf("具體路徑為：\n");

99、;　　QueueTraverse(Q,PrintQElem); //遍歷隊(duì)列的每個(gè)元素并輸出　　}　　else　　{　　printf("迷宮不可通,

100、路徑蹤跡如下:\n");　　PrintMaze(maze);　　}　　DestroyQueue(Q); //銷毀隊(duì)列　　printf("-------------輸入任意鍵結(jié)束---------------\

眾賞文庫> 全部分類> 畢業(yè)設(shè)計(jì)

溫馨提示

1. 本站所有資源如無特殊說明，都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請(qǐng)下載最新的WinRAR軟件解壓。
2. 本站的文檔不包含任何第三方提供的附件圖紙等，如果需要附件，請(qǐng)聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
3. 本站RAR壓縮包中若帶圖紙，網(wǎng)頁內(nèi)容里面會(huì)有圖紙預(yù)覽，若沒有圖紙預(yù)覽就沒有圖紙。
4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
5. 眾賞文庫僅提供信息存儲(chǔ)空間，僅對(duì)用戶上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理，對(duì)用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯，并不能對(duì)任何下載內(nèi)容負(fù)責(zé)。
6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容，請(qǐng)與我們聯(lián)系，我們立即糾正。
7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時(shí)也不承擔(dān)用戶因使用這些下載資源對(duì)自己和他人造成任何形式的傷害或損失。

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

文檔簡介

溫馨提示

最新文檔

評(píng)論

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

文檔簡介

溫馨提示

最新文檔

評(píng)論

免費(fèi)下載