數據結構迷宮課程設計

上傳人：奔*** IP屬地：河北更新時間：2024-03-01 格式：doc 頁數：23 大小：186.00KB 人氣指數：12 舉報 版權申訴

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

版權說明：本文檔由用戶提供并上傳，收益歸屬內容提供方，若內容存在侵權，請進行舉報或認領

文檔簡介

1、　　數據結構課程設計　　說明書　　學院：信息科學與工程學院 　　班級：計算機科學與技術 2009級6班 　　完

2、成人：姓名：學號： 　　指導教師： 　　2010年12月31日　　課程設計任務書　　一、課程設計題目：迷宮問題

3、 　　二、課程設計應解決的主要問題：　　（1）實現一個以鏈表做存儲結構的隊列類型； 　　（2）編寫一個求解迷宮的非遞歸程序； 　?。?）求得的通路以二元組的形式輸出，

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

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

6、設計的評價　　成績： 　　指導教師簽字： 　　年月日 　　目錄　　需求分析說明 …………………………………

7、………51.1求迷宮通路的總體功能要求………………………………51.2主函數模塊……………………………………………………51.3隊列的存儲功能及輸出結點功能…………………………51.4構建迷宮找出迷宮的通路…………………………………5　　1.5 測試數據…………………………………………………………………………..6　　概要設計說明 …………………

8、…………………………………62.1 模板的調用說明………………………………………………62.2 隊列的抽象數據類型定義…………………………………62.3 基本操作及函數功能………………………………………6　　詳細設計說明 ……………………………………………………73.1 主函數模塊…………………………………………………73.2 隊列的存儲功能及輸出結點功能………………………73.3

9、構建迷宮找出迷宮的通路…………………………………8　　調試分析 …………………………………………………………8　　用戶使用說明 ……………………………………………………8　　5.1程序運行的初始界面………………………………………………….......9　　5.2迷宮可通時

10、的界面……………………………………………………….10　　5.3迷宮不可通時的界面………………………………………………….11　　5.4迷宮沒有入口時的界面……………………………………………...12　　6課程設計總結 ……………………………………………………12　　7測

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

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

13、>　　⑵ 實現以鏈表作存儲結構的隊列類型。　　⑶ 實現建立一個隨機的迷宮，并且走出迷宮的操作。　　以下是各功能模塊的功能描述：　　1．主函數模塊　　本模塊的主要功能是初始化圖形界面，調用各模塊，實現走出迷宮

14、的功能。　　2．隊列的存儲功能及輸出結點功能　　本模塊的主要功能是建立隊列，實現隊列的各個基本操作，如構建一個空隊列，往隊尾插入元素，刪除隊頭元素，取隊尾元素，取隊頭元素，判斷隊列是否為空，遍歷隊鏈的每個元素，輸出每個元素，銷毀隊鏈。　　3．構建迷宮找出迷宮的通路　　本模

15、塊的主要功能是隨機初始化一個迷宮并輸出，實現走出迷宮的操作，再輸出走完后的迷宮及走出迷宮所走的路徑。　　測試數據　　1. （1，5）（4，8）　　2. （0，0）（9，9）　　3. （11，11）（11，11）

16、　　概要設計說明　　模板調用說明：　　隊列的抽象數據類型定義為：　　ADT Queue{　　數據對象： D={Ai | Ai ∈ElemSet,i=1,2,…,n, n&g

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

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

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

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

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

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

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

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

25、gt;　　2．隊列的存儲功能及輸出結點功能　　在實現隊列的存儲功能時，首先定義單鏈隊列的鏈式存儲結構，然后定義隊列的各種基本操作的函數，其中定義的函數有構造一個空隊列的函數InitQueue，銷毀隊列的函數DestroyQueue，向隊尾插入元素的函數EnQueue，刪除隊頭元素的函數DeQueue，取隊頭元素的函數GetHead，利用循環(huán)彈出隊尾元素的函數DeRear，判

26、斷隊列是否為空的函數QueueEmpty。　　在實現輸出隊列的結點功能時，定義了從隊頭到隊尾依次對隊列中每個元素調用函數visit()的遍歷函數QueueTraverse，及輸出隊列元素的輸出函數PrintQElem。　　3．構建迷宮找出迷宮的通路　　在實現構建迷宮的功能中，利用srand(time(NULL))

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

28、到的問題是當迷宮的路可通時，輸出的所走路徑是亂碼，主要問題是如果判斷出一個通道塊不可通時，已經把它放入隊列當中，如果再把它彈出時不能像棧那個樣直接調用出棧函數，因為棧是先進后出的存儲結構，最新壓入的元素就能直接取出，而對于隊列來說新入隊的元素放在了隊尾，而出隊函數是把隊頭元素給輸出，不是新入隊的元素。因此，如果要用隊列模擬棧的功能，要解決的問題是，從隊頭開始依次將隊列的隊頭元素給輸出，再把該元素放入隊列當中，只到遇到新插入的元素，只把它

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

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

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

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

33、迷宮時，用的是“窮舉求解”的方法，即從入中出發(fā)，順某一方向向前探索，若能走通，則繼續(xù)往前走；否則沿原路退回，換一個方向再繼續(xù)探索，直至所有可能的通路都探索到為止。為了保證在任何位置上都能沿原路退回，顯然需要用一個后進先出的結構來保存從入口到當前位置的路徑。因此，在求迷宮通路的算法中最好是應用“?！保绻谩瓣犃小钡脑?，就要用隊列來模擬棧的存儲結構特點。　　測試結果</b

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

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

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

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

38、lt;p>　　#define OK 1　　#define ERROR 0　　#define INFEASIBLE -1　　#define NULL 0 　　//墻或通路及前進方向符號定義<

39、p>　　#define WALL 0 //代表當前格子是墻　　#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 //代表當前格子是通路且是目標位置　　typedef int MazeType[10][10]; //最外鑿初始化成墻，實際含8*8個格子　　typedef int Status;　　typedef int ElemType; //迷宮數組中的元素類型　　//－－－

42、－－－－－－單鏈隊列--隊列的鏈式存儲結構－－－－－//　　typedef struct　　{　　int x;　　int y;<

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

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

45、QElemType data;　　struct QNode *next;　　}QNode,*QueuePtr; //隊列結點　　typedef struct　　{　　Queu

46、ePtr front; //隊頭指針　　QueuePtr rear; //隊尾指針　　}LinkQueue;　　Status InitQueue (LinkQueue &Q) //構造一個空隊列Q,隊列有一個頭結點　　{&

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

48、　　return OK;　　}//InitQueue　　Status DestroyQueue(LinkQueue &Q) //銷毀隊列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的新的對尾元素 　　{<p&

51、gt;　　QueuePtr p;　　p=(QueuePtr)malloc(sizeof(QNode));　　if(!p) exit (OVERFLOW); //存儲分配失敗　　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) 　　{　　//若隊列不空,則刪除Q的對頭元素,用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) //判斷刪除后隊列是否為空　　Q.rear =Q.

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

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

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

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

59、>　　e=p->data ; //取隊尾元素　　return OK;　　}//GetRear　　Status DeRear(LinkQueue &Q,QElemType &e)　　{//若隊列不空，利用循環(huán)彈出Q的隊尾元素，并返回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); //刪除隊頭元素　　EnQueue(Q,e); //將刪除的隊頭元素插入隊尾　　}　　DeQueue(Q,e);

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

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

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

65、t失敗，則操作失敗。　　QueuePtr p=Q.front->next ;　　if(Q.rear ==Q.front ) printf("空隊列\(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)); //使計算機自動讀取自己的時間獲得SEED值，獲得真正的隨機數　　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;//隨機取到0到RAND_MAX之間的任何數，對2取余是只產生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)　　{　　//移動到下一格,向下走一步　　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; //迷宮中的坐標

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

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

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

87、t;　　EnQueue(Q,e); //將坐標位置插入隊尾　　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、 //標志為從其向右走　　curpos=Nextpos(curpos,1); //坐標向右移動下個格　　curstep++;　　}　　}　　else

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

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

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

93、元素　　e.di++; 　　EnQueue(Q,e); //將新結點插入隊尾　　maze[e.seat.x][e.seat.y]=-e.di; //注意前進方向蹤跡與e.di互為相反數　　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("輸入迷宮的入口位置坐標從(0,0)到(9,9): ");　　scanf("%d,%d",&start.x,&

97、start.y);　　printf("輸入迷宮的出口位置坐標從(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); //遍歷隊列的每個元素并輸出　　}　　else　　{　　printf("迷宮不可通,

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

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

溫馨提示

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

數據結構迷宮課程設計

文檔簡介

溫馨提示

最新文檔

評論

數據結構迷宮課程設計

文檔簡介

溫馨提示

最新文檔

評論

免費下載