數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)報(bào)告---迷宮算法

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

數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)報(bào)告---迷宮算法_第1頁

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

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

文檔簡介

1、　　課程設(shè) 計(jì) 報(bào) 告　　課程設(shè)計(jì)名稱：數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)　　課程設(shè)計(jì)題目：迷宮算法 　　院（系）：計(jì)算機(jī)學(xué)院　　專業(yè)：計(jì)算機(jī)科學(xué)與技術(shù)　　班級： <

2、/p>　　學(xué) 號： 　　目錄　　1 課程設(shè)計(jì)介紹1　　1.1 課程設(shè)計(jì)內(nèi)容1　　1.2 課程設(shè)計(jì)要求1

3、　2 課程設(shè)計(jì)原理2　　2.1 課設(shè)題目粗略分析2　　2.2 原理圖介紹3　　2.2.1 功能模塊圖3　　2.2.2 流程圖分析3　　3 數(shù)據(jù)結(jié)構(gòu)分析9　　3.1 存儲結(jié)構(gòu)

4、9　　3.2 算法描述9　　4 調(diào)試與分析11　　4.1 調(diào)試過程11　　4.2程序執(zhí)行過程11　　參考文獻(xiàn)13　　附錄（關(guān)鍵部

5、分程序清單）14　　1 課程設(shè)計(jì)介紹　　1.1 課程設(shè)計(jì)內(nèi)容　　編寫算法能夠生成迷宮，并且求解迷宮路徑（求解出任意一條到出口的路徑即可）：　　迷宮用上下左右四種走法；　　迷宮的大小和復(fù)雜程

6、度可以由用戶定義；　　入口出口也由用戶自己選擇。　　1.2 課程設(shè)計(jì)要求　　不必演示求解過程，只需要輸出迷宮求解的路徑；　　參考相應(yīng)資料完成課設(shè)。　　2 課程設(shè)計(jì)原理

7、　　2.1 課設(shè)題目粗略分析　　根據(jù)課設(shè)題目要求，擬將整體程序分為四大模塊。以下是四個(gè)模塊的大體分析：　　1 建立迷宮：要建立迷宮首先就要建立存儲結(jié)構(gòu)，這里我用棧的方式建立的。根據(jù)用戶輸入的迷宮的大?。ㄎ以O(shè)置的最大值為25可以根據(jù)要求調(diào)解）；　　2 設(shè)置迷宮：這里將0設(shè)置圍墻，1是可以通過的路徑

8、，-1是不可以通過路徑，外墻是以設(shè)計(jì)好的，內(nèi)墻需要用戶來設(shè)置，障礙的難度可由用戶自行定義；　　3 尋找路徑：尋找路徑我設(shè)置了四個(gè)方向{0,1},{1,0},{0,-1},{-1,0}移動(dòng)方向,依次為東南西北，首先向東走，若不成功則轉(zhuǎn)換方向，成功則繼續(xù)前進(jìn)，將走過的路徑進(jìn)行標(biāo)記，然后存入棧中；　　4 輸出結(jié)果：輸出的結(jié)果分為兩種，一種是用戶建立的迷宮主要是

9、讓用戶檢查是否符合要求，第二種輸出的是尋找完后的路徑，路徑用1 2 3 4···來表示。　　2.2 原理圖介紹　　2.2.1 功能模塊圖　　圖2.1 功能模塊圖　　如圖2.1所示 <

10、;/b>　　2.2.2 流程圖分析　　建立迷宮　　圖2.2建立迷宮函數(shù)流程圖　　2. 設(shè)置迷宮　　圖2.3 設(shè)置迷宮函數(shù)流程圖

11、　　3. 尋找路徑　　圖2.4 尋找路徑函數(shù)流程圖　　4.輸出結(jié)果　　圖2.5 輸出結(jié)果函數(shù)流程圖　　3 數(shù)據(jù)結(jié)構(gòu)分析

12、;　　3.1 存儲結(jié)構(gòu)　　定義一個(gè)整型數(shù)組PosType用來存儲行列的值。　　typedef struct // 棧的元素類型 　　{　　int ord; // 通道塊在路徑

13、上的＂序號＂ 　　PosType seat; // 通道塊在迷宮中的＂坐標(biāo)位置＂ 　　int di; // 從此通道塊走向下一通道塊的＂方向＂(0～3表示東～北) 　　}SElemType; 　　棧的存儲結(jié)構(gòu)：

14、　　#define STACK_INIT_SIZE 10// 存儲空間初始分配量 　　#define STACKINCREMENT 2// 存儲空間分配增量 　　// 棧的順序存儲表示 　　typedef struct SqStack

15、;　　{　　SElemType *base;// 在棧構(gòu)造之前和銷毀之后，base的值為NULL 　　SElemType *top;// 棧頂指針 　　int stacksize;// 當(dāng)前已分配的存儲空間，以元素為單位 　　}SqStack

16、;// 順序棧　　3.2 算法描述　　1.棧的基本操作的算法，簡單算法說明如下：　　Status InitStack(SqStack *S)　　{//構(gòu)造一個(gè)空棧S，為棧底分配一個(gè)指定大小的存儲空間<

17、;p>　　(*S).base = (SElemType *)malloc(STACK_INIT_SIZE*sizeof(SElemType));　　if( !(*S).base ) exit(0);　　(*S).top = (*S).base;// 棧底與棧頂相同表示一個(gè)空棧　　(*S).sta

18、cksize = STACK_INIT_SIZE;　　return 1;　　}　　Status StackEmpty(SqStack S)　　{ // 若棧S為空棧（棧頂與棧底

19、相同的），則返回1，否則返回0。　　if(S.top == S.base) return 1;　　else return 0;　　}Status Push(SqStack *S, SElemType e)　　{//插入元素e為新的棧頂元素。</

20、p>　　if((*S).top - (*S).base >= (*S).stacksize) {// 棧滿，追加存儲空間　　(*S).base = (SElemType *)realloc((*S).base , ((*S).stacksize + STACKINCREMENT) * sizeof(SElemType));<p&g

21、t;　　if( !(*S).base ) exit(0);　　(*S).top = (*S).base+(*S).stacksize;　　(*S).stacksize += STACKINCREMENT;　　}　　*((*S).

22、top)++=e;　　return 1;　　}　　Status Pop(SqStack *S,SElemType *e)　　{//若棧不空，則刪除S的棧頂元素，用e返回其值，并返回1；否則返回

23、0。　　if((*S).top == (*S).base) return 0;　　*e = *--(*S).top;　　return 1;　　}

24、　查找路徑的算法，簡單算法說明如下：　　Status MazePath(PosType start,PosType end) 　　{ // 若迷宮maze中存在從入口start到出口end的通道，則求得一條 　　// 存放在棧中(從棧底到棧頂)，并返回1；否則返回0

25、　　InitStack(&S); curpos=start; curstep=1;　　do　　{　　if(Pass(curpos)){// 當(dāng)前位置可以通過，即是未曾走到過的通道塊

26、　　FootPrint(curpos); // 留下足跡 　　e =( curstep, curpos,1);　　Push(&S,e); // 入棧當(dāng)前位置及狀態(tài) 　　if(curpos.x==end.x&&curpos.y==end.y) // 到達(dá)終點(diǎn)(出口)

27、　　return 1;　　curpos=NextPos(curpos,e.di);　　}　　else{// 當(dāng)前位置不能通過 　　if(!StackEmpty(S)){</

28、p>　　Pop(&S,&e); // 退棧到前一位置 　　curstep--; // 前一位置處于最后一個(gè)方向(北) 　　while(e.di==3&&!StackEmpty(S))　　{&

29、lt;p>　　MarkPrint(e.seat); Pop(&S,&e); //留下不能通過的標(biāo)記(-1) , 退回一步　　}　　if(e.di<3) { // 沒到最后一個(gè)方向(北) 　　e.di++; Push(&S,e);// 換下一

30、個(gè)方向探索　　curpos=NextPos(e.seat,e.di); // 設(shè)定當(dāng)前位置是該新方向上的相鄰塊　　}　　}　　}<

31、;p>　　}while(!StackEmpty(S));　　return 0;　　}　　4 調(diào)試與分析　　4.1 調(diào)試過程</

32、b>　　在調(diào)試程序是主要遇到一下幾類問題：　　選擇存儲結(jié)構(gòu)的問題：剛接到課設(shè)題目的時(shí)候，我就在想用什么來實(shí)現(xiàn)迷宮的存儲。用線性表還是數(shù)組，最后綜合考慮決定用棧和數(shù)組結(jié)合的方式來實(shí)現(xiàn)，用數(shù)組來建立迷宮和輸出迷宮，用棧來查找路徑并將生成的路徑壓入到棧中，因?yàn)闂Ｓ邢热牒蟪龅膬?yōu)點(diǎn)，所以比較容易實(shí)現(xiàn)。　　如何建立迷宮

33、和怎么設(shè)置迷宮的問題：首先迷宮要有一定的范圍怎么才能讓迷宮有序的進(jìn)行，于是我將迷宮的外圍和障礙設(shè)置為0，所有的可走路徑設(shè)置為1，這樣迷宮就清晰可見。　　如何去尋找路徑問題：這是整個(gè)程序的核心。通過查找書籍得到了一個(gè)算法：若當(dāng)前位置“可通”，則納入當(dāng)前路徑，并繼續(xù)朝下一位置搜索，即切換下一位置為當(dāng)前位置，如此重復(fù)到達(dá)出口；若不可通，就退回到前一通道，然后繼續(xù)尋找其他方向；若均不可通，則刪除此路徑

34、。　　界面問題：這里就是運(yùn)用了switch(n)語句來實(shí)現(xiàn)的，這樣增加了程序的實(shí)用性。　　4.2程序執(zhí)行過程　　系統(tǒng)使用說明：　　1．出現(xiàn)界面后選擇1，進(jìn)行迷宮大小的設(shè)計(jì)（這里設(shè)計(jì)3*3大小的）：

35、如圖4.1所示　　圖4.1 　　2. 然后選擇2，開始設(shè)計(jì)迷宮的內(nèi)部：如圖4.2所示　　圖4.2　　選擇3，觀察設(shè)計(jì)的是否滿足你的要求：如圖4.3所示&l

36、t;b>　　圖4.3　　選擇4，輸入迷宮的起點(diǎn)和終點(diǎn)：如圖4.4所示　　圖4.4　　選擇5，查看結(jié)果（路徑由1.2.3.4.5表示出來）：如圖4.5所示　　圖4.5<

37、;/p>　　6．選擇0，退出程序。　　參考文獻(xiàn)　　[1] 嚴(yán)蔚敏，吳偉民.數(shù)據(jù)結(jié)構(gòu)[M].北京：清華大學(xué)出版社，2007. 　　[2] 胡圣榮, 周靄如, 羅穗萍.數(shù)據(jù)結(jié)構(gòu)教程與題解[M].北京：清華大學(xué)出版社，2011.&

38、lt;p>　　[3] 譚浩強(qiáng).C程序設(shè)計(jì)[M].北京：清華大學(xué)出版社，2005.　　[4] 袁平波.數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)指導(dǎo)[M].合肥：中國科學(xué)技術(shù)大學(xué)出版社.2010. 　　[5] 殷人昆.數(shù)據(jù)結(jié)構(gòu)[M].北京：清華大學(xué)出版社.2011.　　[6] 寧正元.算法與數(shù)據(jù)結(jié)構(gòu)習(xí)題精解和實(shí)驗(yàn)指導(dǎo)[M].北京. 清華大

39、學(xué)出版社.2007.　　[7] 陳媛.算法與數(shù)據(jù)結(jié)構(gòu).第2版[M].北京. 清華大學(xué)出版社.2011.　　附錄（關(guān)鍵部分程序清單）　　程序代碼　　#include<stdio.h><p&

40、gt;　　#include<stdlib.h>　　#include<string.h>　　#include<malloc.h>　　// 迷宮坐標(biāo)位置類型　　typedef struct <

41、;b>　　{　　int x;// 行值 　　int y;// 列值 　　}PosType;　　#define MAXLENGTH 25 // 設(shè)迷宮的最大行列為25 <p

42、>　　typedef int MazeType[MAXLENGTH][MAXLENGTH]; // 迷宮數(shù)組[行][列] 　　typedef struct // 棧的元素類型 　　{　　int ord; // 通道塊在路徑上的＂序號＂ <p

43、>　　PosType seat; // 通道塊在迷宮中的＂坐標(biāo)位置＂ 　　int di; // 從此通道塊走向下一通道塊的＂方向＂(0～3表示東～北) 　　}SElemType;　　// 全局變量 　　MazeType m; /

44、/ 迷宮數(shù)組　　int curstep=1; // 當(dāng)前足跡,初值為1 　　#define STACK_INIT_SIZE 10// 存儲空間初始分配量 　　#define STACKINCREMENT 2// 存儲空間分配增量 　　// 棧的順序存儲表示 </

45、p>　　typedef struct SqStack　　{　　SElemType *base;// 在棧構(gòu)造之前和銷毀之后，base的值為NULL 　　SElemType *top;// 棧頂指針

46、　int stacksize;// 當(dāng)前已分配的存儲空間，以元素為單位 　　}SqStack;// 順序棧　　//構(gòu)造一個(gè)空棧S　　int InitStack(SqStack *S)　　{<p&g

47、t;　　// 為棧底分配一個(gè)指定大小的存儲空間　　(*S).base = (SElemType *)malloc(STACK_INIT_SIZE*sizeof(SElemType));　　if( !(*S).base )　　exit(0);<p&

48、gt;　　(*S).top = (*S).base;// 棧底與棧頂相同表示一個(gè)空棧　　(*S).stacksize = STACK_INIT_SIZE;　　return 1;　　}　　// 若

49、棧S為空棧（棧頂與棧底相同的），則返回1，否則返回0。　　int StackEmpty(SqStack S)　　{　　if(S.top == S.base)　　return 1;

50、;　　else　　return 0;　　}　　//插入元素e為新的棧頂元素。　　int Push(SqStack *S, SElemT

51、ype e)　　{　　if((*S).top - (*S).base >= (*S).stacksize)// 棧滿，追加存儲空間　　{　　(*S).base = (SElemType *

52、)realloc((*S).base , 　　((*S).stacksize + STACKINCREMENT) * sizeof(SElemType));　　if( !(*S).base )　　exit(0);　　(*S).top

53、= (*S).base+(*S).stacksize;　　(*S).stacksize += STACKINCREMENT;　　}　　*((*S).top)++=e;　　return 1;<

54、;/p>　　}　　//若棧不空，則刪除S的棧頂元素，用e返回其值，并返回1；否則返回0。　　int Pop(SqStack *S,SElemType *e)　　{

55、if((*S).top == (*S).base)　　return 0;　　*e = *--(*S).top; // 這個(gè)等式的++ * 優(yōu)先級相同，但是它們的運(yùn)算方式，是自右向左　　return 1;<

56、p>　　}　　// 定義墻元素值為0,可通過路徑為1,不能通過路徑為-1,通過路徑為足跡　　// 當(dāng)迷宮m的b點(diǎn)的序號為1(可通過路徑)，return 1; 否則，return 0。　　int Pass(PosType b)&l

57、t;b>　　{ 　　if(m[b.x][b.y]==1)　　return 1;　　else　　return 0;

58、　　}　　void FootPrint(PosType a) // 使迷宮m的a點(diǎn)的序號變?yōu)樽阚E(curstep)，表示經(jīng)過　　{　　m[a.x][a.y]=curstep;<p

59、>　　}　　// 根據(jù)當(dāng)前位置及移動(dòng)方向，返回下一位置 　　PosType NextPos(PosType c,int di)　　{　　PosType direc[4]={{0,1},{1,

60、0},{0,-1},{-1,0}}; // {行增量,列增量} 　　// 移動(dòng)方向,依次為東南西北 　　c.x+=direc[di].x;　　c.y+=direc[di].y;　　return c;<p&

61、gt;　　}　　// 使迷宮m的b點(diǎn)的序號變?yōu)?1(不能通過的路徑)　　void MarkPrint(PosType b)　　{ 　　m[b.x][b.y]=-1;<

62、p>　　}　　// 若迷宮maze中存在從入口start到出口end的通道，則求得一條 　　// 存放在棧中(從棧底到棧頂)，并返回1；否則返回0 　　int MazePath(PosType start,PosType end) <p&g

63、t;　　{ 　　SqStack S;　　PosType curpos;　　SElemType e;　　InitStack(&S);　　curpos=start;

64、　　do　　{　　if(Pass(curpos))　　{// 當(dāng)前位置可以通過，即是未曾走到過的通道塊 　　FootPrint(curpos); // 留下足跡 </p&

65、gt;　　e.ord=curstep;　　e.seat.x=curpos.x;　　e.seat.y=curpos.y;　　e.di=0;　　Push(&S,e); // 入棧當(dāng)前位置及狀態(tài) </p&

66、gt;　　curstep++; // 足跡加1 　　if(curpos.x==end.x&&curpos.y==end.y) // 到達(dá)終點(diǎn)(出口) 　　return 1;　　curpos=NextPos(curpos,e.di);<

67、;/p>　　}　　else　　{// 當(dāng)前位置不能通過 　　if(!StackEmpty(S))　　{&l

68、t;p>　　Pop(&S,&e); // 退棧到前一位置 　　curstep--;　　while(e.di==3&&!StackEmpty(S)) // 前一位置處于最后一個(gè)方向(北)　　{　　M

69、arkPrint(e.seat); // 留下不能通過的標(biāo)記(-1) 　　Pop(&S,&e); // 退回一步 　　curstep--;　　}　　if(e.di<3) // 沒到最后一個(gè)方向(北) </p

70、>　　{　　e.di++; // 換下一個(gè)方向探索　　Push(&S,e); curstep++;// 設(shè)定當(dāng)前位置是該新方向上的相鄰塊　　curpos=NextPos(e.seat,e.di);&

71、lt;b>　　}　　}　　}　　}while(!StackEmpty(S));　　return 0;<

72、p>　　}　　// 輸出迷宮的結(jié)構(gòu) 　　void Print(int x,int y)　　{ 　　int i,j;<p&g

73、t;　　for(i=0;i<x;i++)　　{　　for(j=0;j<y;j++)　　printf("%3d",m[i][j]);　　printf("\n");

74、　　}　　}　　void main()　　{　　PosType begin,end;　　int

75、i,j,x,y,x1,y1,n,k;　　do{　　system("cls"); //清屏函數(shù)　　printf("

76、 <<<<<<<<<<<<<<<<welcome>>>>>>>>>>>>>>>> \n\n\n");　　printf("

77、 1請輸入迷宮的行數(shù),列數(shù)(包括外墻)\n");　　printf(" 2請輸入迷宮內(nèi)墻單元數(shù)\n");　　printf(" 3迷宮結(jié)構(gòu)如下\n");　　pri

78、ntf(" 4輸入迷宮的起點(diǎn)和終點(diǎn)\n");　　printf(" 5輸出結(jié)果\n");　　printf(" 0退出\n");</p&g

79、t;　　printf("\n\n請選擇 ");　　scanf("%d",&n);　　switch(n)　　{

80、;　　case 1:{　　printf("請輸入迷宮的行數(shù),列數(shù)(包括外墻)：(空格隔開)");　　scanf("%d%d", &x, &y);　　for(i=0;i<x;i++) // 定義周邊值為0(同墻)

81、;　　{　　m[0][i]=0;// 迷宮上面行的周邊即上邊墻 　　m[x-1][i]=0;// 迷宮下面行的周邊即下邊墻 　　}　　for(j=1;j<y-1;j+

82、+)　　{　　m[j][0]=0;// 迷宮左邊列的周邊即左邊墻 　　m[j][y-1]=0;// 迷宮右邊列的周邊即右邊墻 　　}　　for(i=1;

83、i<x-1;i++)　　for(j=1;j<y-1;j++)　　m[i][j]=1; // 定義通道初值為1 　　}break; 　　case 2:<p

84、>　　{printf("請輸入迷宮內(nèi)墻單元數(shù)：");　　scanf("%d",&j);　　printf("請依次輸入迷宮內(nèi)墻每個(gè)單元的行數(shù),列數(shù)：(空格隔開)\n");　　for(i=1;i<=j;i++)&l

85、t;p>　　{　　scanf("%d%d",&x1,&y1);　　m[x1][y1]=0; 　　}　　}break;

86、;　　case 3:{Print(x,y);printf("輸入0退出");scanf("%d",&k);}break;　　case 4:{ printf("請輸入起點(diǎn)的行數(shù),列數(shù)：（空格隔開）");　　scanf("%d%d&quo

87、t;,&begin.x,&begin.y);　　printf("請輸入終點(diǎn)的行數(shù),列數(shù)：（空格隔開）");　　scanf("%d%d",&end.x,&end.y);}break;　　case 5:{&

88、lt;/p>　　if(MazePath(begin,end)) // 求得一條通路 　　{　　printf("此迷宮從入口到出口的一條路徑如下:\n");　　Print(x,y); // 輸出此通路 &l

89、t;p>　　}　　else　　printf("此迷宮沒有從入口到出口的路徑\n");　　printf("輸入0退出");scanf("%d",&k);</p&

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

溫馨提示

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

數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)報(bào)告---迷宮算法

文檔簡介

溫馨提示

最新文檔

評論

數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)報(bào)告---迷宮算法

文檔簡介

溫馨提示

最新文檔

評論

免費(fèi)下載