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

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

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

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

文檔簡介

1、　　數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)　　設(shè)計(jì)說明書　　2012年3月2日　　數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)評閱書　　注：指導(dǎo)教師成績60%，答辯成績40%，總成績合成后按

2、五級制記入。　　課程設(shè)計(jì)任務(wù)書　　2011—2012學(xué)年第二學(xué)期　　課程設(shè)計(jì)名稱：數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì) 　　設(shè) 計(jì) 題

3、目：迷宮問題求解 　　完成期限：自 2012 年 2 月 20 日至 2012 年 3 月 2 日共 2 周 　　設(shè)計(jì)依據(jù)、要求及主要內(nèi)容（可另加附頁）：<b&g

4、t;　　設(shè)計(jì)要求:　　設(shè)計(jì)內(nèi)容：輸入一個(gè)任意大小的迷宮數(shù)據(jù)，設(shè)置入口、出口及障礙，借助棧結(jié)構(gòu)求解走出迷宮的路徑并輸出。　　邏輯設(shè)計(jì)：對問題描述中涉及的操作對象定義相應(yīng)的數(shù)據(jù)類型，并按照以數(shù)據(jù)結(jié)構(gòu)為中心的原則劃分模塊，定義主程序模塊和各抽象數(shù)據(jù)類型。邏輯設(shè)計(jì)的結(jié)果應(yīng)寫出每個(gè)抽象數(shù)據(jù)類型的定義（包括數(shù)據(jù)結(jié)構(gòu)的描述和每個(gè)基本操作的功能說明）

5、，各個(gè)主要模塊的算法，并畫出模塊之間的調(diào)用關(guān)系圖；　　詳細(xì)設(shè)計(jì)：定義相應(yīng)的存儲結(jié)構(gòu)并寫出各函數(shù)的偽碼算法。在這個(gè)過程中，要綜合考慮系統(tǒng)功能，使得系統(tǒng)結(jié)構(gòu)清晰、合理、簡單和易于調(diào)試，抽象數(shù)據(jù)類型的實(shí)現(xiàn)盡可能做到數(shù)據(jù)封裝，基本操作的規(guī)格說明盡可能明確具體。詳細(xì)設(shè)計(jì)的結(jié)果是對數(shù)據(jù)結(jié)構(gòu)和基本操作做出進(jìn)一步的求精，寫出數(shù)據(jù)存儲結(jié)構(gòu)的類型定義，寫出函數(shù)形式的算法框架；

6、;　　程序編碼：把詳細(xì)設(shè)計(jì)的結(jié)果進(jìn)一步求精為程序設(shè)計(jì)語言程序。同時(shí)加入一些注解和斷言，使程序中邏輯概念清楚；　　程序調(diào)試與測試：采用自底向上，分模塊進(jìn)行，即先調(diào)試低層函數(shù)。能夠熟練掌握調(diào)試工具的各種功能，設(shè)計(jì)測試數(shù)據(jù)確定疑點(diǎn)，通過修改程序來證實(shí)它或繞過它。調(diào)試正確后，認(rèn)真整理源程序及其注釋，形成格式和風(fēng)格良好的源程序清單和結(jié)果；　　結(jié)果分析：程序運(yùn)行結(jié)果

7、包括正確的輸入及其輸出結(jié)果和含有錯(cuò)誤的輸入及其輸出結(jié)果。算法的時(shí)間、空間復(fù)雜性分析；　　編寫課程設(shè)計(jì)報(bào)告；　　以上要求中前三個(gè)階段的任務(wù)完成后，先將設(shè)計(jì)說明數(shù)的草稿交指導(dǎo)老師面審，審查合格后方可進(jìn)入后續(xù)階段的工作。設(shè)計(jì)工作結(jié)束后，經(jīng)指導(dǎo)老師驗(yàn)收合格后將設(shè)計(jì)說明書打印裝訂，并進(jìn)行答辯。<p

8、>　　指導(dǎo)教師（簽字）：教研室主任（簽字）： 　　批準(zhǔn)日期：年月日　　摘要　　由計(jì)算機(jī)解迷宮時(shí)，通常用的是窮舉求解的方法，即從入口出發(fā)，順某一方向向前探索，若能走通，則繼續(xù)

9、往前走；否則沿原路反回，換一個(gè)方向繼續(xù)探索，直至所有可行的通路都探索到為止。為了保證在任何位置上都能沿原路返回，顯然需要用一個(gè)后進(jìn)先出的結(jié)構(gòu)來保存從入口到當(dāng)前位置的路徑。顯然要用到棧。　　關(guān)鍵詞：迷宮；窮舉；棧； 　　目錄　　1 課題描述··

10、····································

11、3;···································1</p&

12、gt;　　2 問題分析和任務(wù)定義································

13、;······························2　　3 數(shù)據(jù)結(jié)構(gòu)分析·

14、;····································

15、83;······························ 3　　3.1存儲結(jié)構(gòu)·

16、;····································

17、83;··································3

18、　　3.2算法描述·································

19、3;····································&#

20、183;·3　　4 流程圖 ·····························

21、3;···································6</p&

22、gt;　　5 程序編碼································

23、3;····································&#

24、183;···10　　6 程序測試與運(yùn)行過程··························

25、3;··································19

26、　　6.1程序調(diào)試·································

27、3;····································19

28、　　6.2程序運(yùn)行過程·······························&#

29、183;··································19

30、　　7 結(jié)果分析·································&

31、#183;····································

32、;···25　　總結(jié)·····························

33、····································

34、3;···········26　　參考文獻(xiàn)····················

35、83;····································&

36、#183;···············27　　1 課題描述　　本課程設(shè)計(jì)是解決迷宮求解的問題，從入口出發(fā)，順某一方向向前探索，若能走通，則繼續(xù)往前走；否則沿原路退

37、回，換一個(gè)方向再繼續(xù)探索，直至所有可能的通路都探索到為止。為了保證在任何位置上都能沿原路退回，顯然需要用一個(gè)后進(jìn)先出的結(jié)構(gòu)來保存從入口到當(dāng)前位置的路徑。因此，在求迷宮通路的算法中要應(yīng)用“?！钡乃枷爰僭O(shè)“當(dāng)前位置”指的是“在搜索過程中的某一時(shí)刻所在圖中某個(gè)方塊位置”，則求迷宮中一條路徑的算法的基本思想是：若當(dāng)前位置“可通”，則納入“當(dāng)前路徑”，并繼續(xù)朝“下一位置”探索，即切換“下一位置”為“當(dāng)前位置”，如此重復(fù)直至到達(dá)出口；若當(dāng)前位置“不

38、可通”，則應(yīng)順著“來向”退回到“前一通道塊”，然后朝著除“來向”之外的其他方向繼續(xù)探索；若該通道塊的四周4個(gè)方塊均“不可通”，則應(yīng)從“當(dāng)前路徑”上刪除該通道塊。所謂“下一位置”指的是當(dāng)前位置四周4個(gè)方向（東、南、西、北）上相鄰的方塊。假設(shè)以棧S記錄“當(dāng)前路徑”，則棧頂中存放的是“當(dāng)前路徑上最后一個(gè)通道塊”。由此，“納入路徑”的操作即為“當(dāng)前位置入?！?；“從當(dāng)前路徑上刪除前一通道塊”的操作即為“出?！?。<p&

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

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

41、符合要求，第二種輸出的是尋找完后的路徑，路徑用1 2 3 4···來表示。　　3 數(shù)據(jù)結(jié)構(gòu)分析　　3.1存儲結(jié)構(gòu)　　定義一個(gè)整型數(shù)組PosType用來存儲行列的值。　　typedef struct /

42、/ 棧的元素類型 　　{　　int ord; // 通道塊在路徑上的＂序號＂ 　　PosType seat; // 通道塊在迷宮中的＂坐標(biāo)位置＂ 　　int di; // 從此通道塊走向下一通道塊的＂方向＂(0～3表示東～北) <

43、;/p>　　}SElemType; 　　棧的存儲結(jié)構(gòu)：　　#define STACK_INIT_SIZE 10// 存儲空間初始分配量 　　#define STACKINCREMENT 2// 存儲空間分配增量 <

44、p>　　// 棧的順序存儲表示 　　typedef struct SqStack　　{　　SElemType *base;// 在棧構(gòu)造之前和銷毀之后，base的值為NULL 　　SElemType *top;// 棧頂指

45、針 　　int stacksize;// 當(dāng)前已分配的存儲空間，以元素為單位 　　}SqStack;// 順序棧　　3.2算法描述　　1.棧的基本操作的算法，簡單算法說明如下：　　Sta

46、tus InitStack(SqStack *S)　　{//構(gòu)造一個(gè)空棧S，為棧底分配一個(gè)指定大小的存儲空間　　(*S).base = (SElemType *)malloc(STACK_INIT_SIZE*sizeof(SElemType));　　if( !(*S).base ) exit(0);

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

48、;　　Status StackEmpty(SqStack S)　　{ // 若棧S為空棧（棧頂與棧底相同的），則返回1，否則返回0。　　if(S.top == S.base) return 1;　　else return 0;&l

49、t;p>　　}Status Push(SqStack *S, SElemType e)　　{//插入元素e為新的棧頂元素。　　if((*S).top - (*S).base >= (*S).stacksize) {// 棧滿，追加存儲空間　　(*S).base = (SElemType *)re

50、alloc((*S).base , ((*S).stacksize + STACKINCREMENT) * sizeof(SElemType));　　if( !(*S).base ) exit(0);　　(*S).top = (*S).base+(*S).stacksize;　　(*S).stacksize

51、 += STACKINCREMENT;　　}　　*((*S).top)++=e;　　return 1;　　}　　S

52、tatus Pop(SqStack *S,SElemType *e)　　{//若棧不空，則刪除S的棧頂元素，用e返回其值，并返回1；否則返回0。　　if((*S).top == (*S).base) return 0;　　*e = *--(*S).top;<

53、;b>　　return 1;　　}　　查找路徑的算法，簡單算法說明如下：　　Status MazePath(PosType start,PosType end) 　　{ // 若迷宮maze中存在從入口st

54、art到出口end的通道，則求得一條 　　// 存放在棧中(從棧底到棧頂)，并返回1；否則返回0 　　InitStack(&S); curpos=start; curstep=1;　　do　　{<

55、;/b>　　if(Pass(curpos)){// 當(dāng)前位置可以通過，即是未曾走到過的通道塊 　　FootPrint(curpos); // 留下足跡 　　e =( curstep, curpos,1);　　Push(&S,e); // 入棧當(dāng)前位置及狀態(tài)

56、　　if(curpos.x==end.x&&curpos.y==end.y) // 到達(dá)終點(diǎn)(出口) 　　return 1;　　curpos=NextPos(curpos,e.di);　　}</

57、b>　　else{// 當(dāng)前位置不能通過 　　if(!StackEmpty(S)){　　Pop(&S,&e); // 退棧到前一位置 　　curstep--; // 前一位置處于最后一個(gè)方向(北) 　　wh

58、ile(e.di==3&&!StackEmpty(S))　　{　　MarkPrint(e.seat); Pop(&S,&e); //留下不能通過的標(biāo)記(-1) , 退回一步　　}&l

59、t;p>　　if(e.di<3) { // 沒到最后一個(gè)方向(北) 　　e.di++; Push(&S,e);// 換下一個(gè)方向探索　　curpos=NextPos(e.seat,e.di); // 設(shè)定當(dāng)前位置是該新方向上的相鄰塊　　}

60、;　　}　　}　　}while(!StackEmpty(S));　　return 0;　　}<

61、;/p>　　4. 流程圖　　4.1建立迷宮構(gòu)造空棧函數(shù)并判斷，若是則建立迷宮，否則返回并構(gòu)造空棧。　　n　　y　　圖3.1建

62、立迷宮函數(shù)流程圖　　4.2設(shè)置迷宮先設(shè)置迷宮障礙和起點(diǎn)與終點(diǎn)坐標(biāo)，障礙設(shè)為0，用printf函數(shù)輸出　　圖3.2設(shè)置迷宮函數(shù)的流程圖　　4.3尋找路徑先輸入起點(diǎn)與終點(diǎn)坐標(biāo)。判斷，若能通過則留下足跡，入棧，足跡加一并繼續(xù)判斷，若不能，則換方向繼續(xù)判斷。

63、　　N　　N　　Y　　Y　　N　　圖3.3尋找路徑函數(shù)流程

64、圖　　4.4輸出結(jié)果　　圖3.4輸出結(jié)果流程圖　　5 程序編碼　　#include<stdio.h>　　#include<stdl

65、ib.h>　　#include<string.h>　　#include<malloc.h>　　// 迷宮坐標(biāo)位置類型　　typedef struct 　　{&l

66、t;/p>　　int x;// 行值 　　int y;// 列值 　　}PosType;　　#define MAXLENGTH 25 // 設(shè)迷宮的最大行列為25 　　typedef int Maz

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

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

69、;p>　　int curstep=1; // 當(dāng)前足跡,初值為1 　　#define STACK_INIT_SIZE 10// 存儲空間初始分配量 　　#define STACKINCREMENT 2// 存儲空間分配增量 　　// 棧的順序存儲表示 　　typ

70、edef struct SqStack　　{　　SElemType *base;// 在棧構(gòu)造之前和銷毀之后，base的值為NULL 　　SElemType *top;// 棧頂指針 　　int stacksize;// 當(dāng)

71、前已分配的存儲空間，以元素為單位 　　}SqStack;// 順序棧　　//構(gòu)造一個(gè)空棧S　　int InitStack(SqStack *S)　　{　　// 為棧底分配一個(gè)指定大小的存儲

72、空間　　(*S).base = (SElemType *)malloc(STACK_INIT_SIZE*sizeof(SElemType));　　if( !(*S).base )　　exit(0);　　(*S).top = (*S).

73、base;// 棧底與棧頂相同表示一個(gè)空棧　　(*S).stacksize = STACK_INIT_SIZE;　　return 1;　　}　　// 若棧S為空棧（棧頂與棧底相同的），則返回1，

74、否則返回0。　　int StackEmpty(SqStack S)　　{　　if(S.top == S.base)　　return 1;

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

76、;p>　　{　　if((*S).top - (*S).base >= (*S).stacksize)// 棧滿，追加存儲空間　　{　　(*S).base = (SElemType *)realloc((*S).base ,

77、　　((*S).stacksize + STACKINCREMENT) * sizeof(SElemType));　　if( !(*S).base )　　exit(0);　　(*S).top = (*S).base+(*S).stac

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

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

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

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

82、　　if(m[b.x][b.y]==1)　　return 1;　　else　　return 0;

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

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

85、 {行增量,列增量} 　　// 移動方向,依次為東南西北 　　c.x+=direc[di].x;　　c.y+=direc[di].y;　　return c;　　}</b

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

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

88、b>　　SqStack S;　　PosType curpos;　　SElemType e;　　InitStack(&S);　　curpos=start;

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

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

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

92、;b>　　}　　else　　{// 當(dāng)前位置不能通過 　　if(!StackEmpty(S))　　{　　Pop(&S,&

93、amp;e); // 退棧到前一位置 　　curstep--;　　while(e.di==3&&!StackEmpty(S)) // 前一位置處于最后一個(gè)方向(北)　　{　　MarkPrint(e.seat); //

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

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

96、　　}　　}　　}while(!StackEmpty(S));　　return 0;　　}<

97、/b>　　// 輸出迷宮的結(jié)構(gòu) 　　void Print(int x,int y)　　{ 　　int i,j;　　for(i=0;i<x;i+

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

99、}　　}　　void main()　　{　　PosType begin,end;　　int i,j,x,y,x1,y1,n,k;<

100、;/p>　　do{　　system("cls"); //清屏函數(shù)　　printf(" <<<<&l

101、t;<<<<<<<<<<<welcome>>>>>>>>>>>>>>>> \n\n\n");　　printf(" 1請輸入迷宮的行數(shù),列數(shù)(包括外墻)\

102、n");　　printf(" 2請輸入迷宮內(nèi)墻單元數(shù)\n");　　printf(" 3迷宮結(jié)構(gòu)如下\n");　　printf("

103、 4輸入迷宮的起點(diǎn)和終點(diǎn)\n");　　printf(" 5輸出結(jié)果\n");　　printf(" 0退出\n");　　printf

104、("\n\n請選擇 ");　　scanf("%d",&n);　　switch(n)　　{　　case 1:{

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

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

107、t;　　{　　m[j][0]=0;// 迷宮左邊列的周邊即左邊墻 　　m[j][y-1]=0;// 迷宮右邊列的周邊即右邊墻 　　}　　for(i=1;i<x-1;i++)</p&g

108、t;　　for(j=1;j<y-1;j++)　　m[i][j]=1; // 定義通道初值為1 　　}break; 　　case 2:　　{printf("請

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

110、t;/b>　　scanf("%d%d",&x1,&y1);　　m[x1][y1]=0; 　　}　　}break;

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

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

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

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

115、t;　　}break;　　}　　}while(n!=0);}　　6 程序測試與運(yùn)行　　6.1 程序調(diào)試　　在調(diào)試程序是主要遇到一

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

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

118、是運(yùn)用了switch(n)語句來實(shí)現(xiàn)的，這樣增加了程序的實(shí)用性。　　6.2程序運(yùn)行過程　　出現(xiàn)界面后選擇1，：進(jìn)行迷宮大小的設(shè)計(jì)如圖5.1所示　　圖5.1 進(jìn)行迷宮大小的設(shè)計(jì)　　選擇2，開始設(shè)計(jì)迷宮的內(nèi)部：如圖5.2所示</p

119、>　　圖5.2設(shè)計(jì)迷宮的內(nèi)部　　觀察設(shè)計(jì)的是否滿足你的要求：如圖 5.3所示　　圖5.3觀察設(shè)計(jì)的是否滿足你的要求　　輸入迷宮的起點(diǎn)和終點(diǎn)：如圖5.4所示(見下頁)　　圖5.4輸入起點(diǎn)和終點(diǎn)　　選擇5，

120、查看結(jié)果（路徑由1.2.3.4.5表示出來）：如圖5.5所示　　圖5.5查看結(jié)果　　無通路情況。如圖5.6、5.7所示（見下頁）　　圖5.6無通路情況　　圖5.7無通路情況<

121、;/b>　　有多條通路的情況，如圖5.8 5.9 5.10所示（見下頁）　　圖5.8多條通路的情況　　圖5.9多條通路的情況　　圖5.10多條通路的情況　　之所以程序選擇這條通路，是因?yàn)樗剿鞯捻樞蚴菛|-南-西-北。<

122、/p>　　7 結(jié)果分析　　通過此次課程設(shè)計(jì)，是我對于數(shù)據(jù)結(jié)構(gòu)有了更深的了解，更新的認(rèn)識。數(shù)據(jù)結(jié)構(gòu)是一門重要的課程，只有數(shù)據(jù)結(jié)構(gòu)學(xué)得扎實(shí)了，才能對于計(jì)算機(jī)有更深的應(yīng)用，所以學(xué)好數(shù)據(jù)結(jié)構(gòu)是很重要的。經(jīng)過兩周的上機(jī)設(shè)計(jì)，我實(shí)現(xiàn)了簡單的迷宮求解，能夠簡單的實(shí)現(xiàn)求解過程。但是還存在著不足之處，程序不能循環(huán)執(zhí)行、求路徑時(shí)遇見有多條路徑的情

123、況下，只能找出一條，并且不一定是最優(yōu)路徑。有待改進(jìn)。　　總結(jié)　　本次課程設(shè)計(jì)是一個(gè)關(guān)于迷宮求解的問題，雖然剛聽到有一些迷茫但是通過老師和同學(xué)的幫助最后還是有了結(jié)果，同時(shí)有了很多的體會和經(jīng)驗(yàn)。　　課程設(shè)計(jì)涉及很多的范圍，這就需要我重新的溫習(xí)以前學(xué)過的C語言的知識和數(shù)據(jù)結(jié)構(gòu)的算法

124、，別且通過這個(gè)過程我又發(fā)現(xiàn)了我自身的不足，同時(shí)也鞏固了我的C語言和數(shù)據(jù)結(jié)構(gòu)。這對我以后的學(xué)習(xí)是非常有幫助的。　　但在運(yùn)行測試的時(shí)候，我發(fā)現(xiàn)程序不能循環(huán)輸入，多通路下只能選擇一條通路。在進(jìn)行最優(yōu)路徑搜索時(shí)，我查閱了資料，知道要運(yùn)用圖與隊(duì)列的相關(guān)知識，但試了很多次沒有試出來。這都需要以后進(jìn)行不斷的學(xué)習(xí)來改進(jìn)。　　參考文獻(xiàn)

125、　　嚴(yán)蔚敏. 數(shù)據(jù)結(jié)構(gòu)（C語言版）[M]. 北京：清華大學(xué)出版社,1997.　　譚浩強(qiáng). C程序設(shè)計(jì)（第三版）[M]. 北京：清華大學(xué)出版社，2005.1. 　　二霍紅衛(wèi)算法設(shè)計(jì)與分析〔」西安西安電子科技大學(xué)出版社，2005.113-127.　　陳杰.計(jì)算機(jī)專業(yè)課程設(shè)計(jì)中

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

溫馨提示

1. 本站所有資源如無特殊說明，都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
2. 本站的文檔不包含任何第三方提供的附件圖紙等，如果需要附件，請聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
3. 本站RAR壓縮包中若帶圖紙，網(wǎng)頁內(nèi)容里面會有圖紙預(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ì)

文檔簡介

溫馨提示

最新文檔

評論

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

文檔簡介

溫馨提示

最新文檔

評論

免費(fèi)下載