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

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

已閱讀1頁，還剩13頁未讀，繼續(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ì)　　題目：迷宮求解 　　班級： 　　學(xué) 號： 　　作者姓名： 　　指

2、導(dǎo)教師： 　　2012年12月11日　　目錄　　1．需求分析…………………………………………….…….…..……1　　2．概要設(shè)計(jì)…………………………………………….….……..……1</p

3、>　　2.1．?dāng)?shù)據(jù)結(jié)構(gòu)………………………………………….……..……1　　2.1.1．邏輯結(jié)構(gòu)…………………………..………..…..…….1　　2.1.1．存儲結(jié)構(gòu)…………………………………..…....….…2　　2.2.基本操作…………………………………………..…...…….…

4、3　　2.2.1.迷宮中棧的基本操作………………………….…....….3　　2.2.2.迷宮的抽象數(shù)據(jù)類型…………………………..………3　　2.2.3.本程序包含三個模塊…………………….......….….….4　　3．詳細(xì)設(shè)計(jì)……………………………………………..

5、…… ….……5　　4．調(diào)試與分析………………………………………..… …….………9　　5．用戶手冊……………………………………………………………9　　6. 測試結(jié)果…………………………………………………………….10　　7. 附錄…………………………………………………

6、……………….12　　8. 參考文獻(xiàn)…………………………………………………………….12　　9、心得體會……………………………………………………………12　　10、小組成員工作分配………………………………………………..13　　需求分析

7、;　　以二維數(shù)組maze[n+2][m+2]表示迷宮，其中：maze[0][j]和maze[n+1][j](0<=j<=m+1)及maze[i][0]和maze[i][m+1](0<=i<=j+1)為添加的一圈障礙。數(shù)組中以元素值為0的表示通路，1表示障礙，限定迷宮的大小，m，n<=0。　　迷宮的入口位置和出口位置可由用戶自

8、行設(shè)定。　　如設(shè)定的迷宮處在通路，則值輸出迷宮中的通路，即0，現(xiàn)實(shí)的0連起來就是一個迷宮通路路徑；如設(shè)定的迷宮中不出在通路，則輸出“該迷宮找不到通路!”；　　測試樣例：輸入迷宮的長寬為5和6，輸入迷宮為：　　1 0 0 1 1 1　　0 0 1 1 1 1</p&g

9、t;　　1 0 0 0 1 1　　0 1 0 1 1 1　　1 1 0 0 0 0　　當(dāng)入口位置為（1,2），出口位置為（5,6）時，則輸出數(shù)據(jù)為：　　# # # # # # # #　　# 0

10、 #　　# 0 #　　# 0 0 #　　# 0 #　　# 0 0 0 0 #　　# # # # # # # #<b

11、>　　程序執(zhí)行的命令為：　　輸入迷宮的尺寸；2、創(chuàng)建迷宮；3、輸入迷宮的的出入口位置；　　4、求解迷宮；輸出迷宮的解。　　概要設(shè)計(jì)　　2.1.數(shù)據(jù)結(jié)構(gòu)

12、　　2.1.1、邏輯結(jié)構(gòu)　　1）棧的定義：限定僅在表尾進(jìn)行插入或刪除操作的線性表；　　2）操作特性：后進(jìn)先出;　　3) ADT定義：　　ADT Stack{　　數(shù)據(jù)對象：

13、D={ai|ai∈CharSet,i=1,2,…,n,n>=0}　　數(shù)據(jù)關(guān)系：R1={<ai-1,ai>|ai-1,ai∈D,i=2,…,n}　　基本操作：　　InitStack(&S)　　操作結(jié)果：構(gòu)造一個

14、空棧S。　　DestroyStack（&S）　　初始條件：棧S 已存在。　　操作結(jié)果：銷毀棧S。　　ClearStack(&S)　　初始條件：棧S 已存在。　　操作結(jié)果：將

15、 S 清為空棧。　　StackLength(&S)　　初始條件：棧S 已存在。　　操作結(jié)果：返回棧 S 的長度。　　StackEmpty(&S)　　初始條件：棧S 已存在。

16、　　操作結(jié)果：若 S 為空棧，則返回TRUE，否則返回FALSE。　　GetTop(S,&e)　　初始條件：棧S 已存在。　　操作結(jié)果：若棧 S 不空，則以e 返回棧頂元素。　　Push(&S,e)　　初始條件：棧

17、S 已存在。　　操作結(jié)果：在棧 S 的棧頂插入新的棧頂元素e。　　Pop(&S,&e)　　初始條件：棧S 已存在。　　操作結(jié)果：刪除 S 的棧頂元素，并以e 返回其值。　　StackTraverse(S,visit

18、())　　初始條件：棧S 已存在。　　操作結(jié)果：從棧底到棧頂依次對 S 中的每個元素調(diào)用函數(shù)visit( )。　　}ADT Stack　　2.1.2、存儲結(jié)構(gòu)　　1）順序存儲結(jié)構(gòu)：</p

19、>　　順序棧：是利用一塊地址連續(xù)的存儲單元來存放棧中的元素，同時要利用一個指針top 來指示棧頂元素的位置。　　注：在本迷宮求解程序設(shè)計(jì)中用到的就是棧的順序存儲結(jié)構(gòu)。　　//----- 棧的順序存儲表示 -----　　#define STACK_INIT_SIZE 100; </

20、p>　　#define STACKINCREMENT 10; 　　typedef struct{ 　　SElemType *base; 　　SElemType *top;　　int stacksize;<p

21、>　　}SqStack;　　2）鏈?zhǔn)酱鎯Y(jié)構(gòu)　　鏈?zhǔn)綏＃烘湕Ｊ侵覆捎面準(zhǔn)酱鎯Y(jié)構(gòu)存儲的棧。　　鏈棧是一種特殊的單鏈表，即限定僅在表頭進(jìn)行插入和刪除操作的單鏈表，因此鏈棧的結(jié)點(diǎn)結(jié)構(gòu)與單鏈表的結(jié)點(diǎn)結(jié)構(gòu)相同。<

22、;p>　　2.2、基本操作　　2.2.1、迷宮中棧的基本操作：　　基本操作：　　InitStack(&S)　　操作結(jié)果：構(gòu)造一個空棧S。

23、StackEmpty(&S)　　初始條件：棧S 已存在。　　操作結(jié)果：若 S 為空棧，則返回TRUE，否則返回FALSE。　　GetTop(S,&e)　　初始條件：棧S 已存在。　　操作結(jié)果：若棧 S 不空，則以e

24、返回棧頂元素。　　Push(&S,e)　　初始條件：棧S 已存在。　　操作結(jié)果：在棧 S 的棧頂插入新的棧頂元素e。　　Pop(&S,&e)　　初始條件：棧S 已存在。<p&

25、gt;　　操作結(jié)果：刪除 S 的棧頂元素，并以e 返回其值。　　2.2.2、迷宮的抽象數(shù)據(jù)類型　　ADT MazeType{　　數(shù)據(jù)對象 : D={ai,j|ai,j∈{‘ ’,‘#’、‘@’、‘*’}，0<=i<=n+1, 0<=j<=m+1,m,n<=20}

26、　　數(shù)據(jù)關(guān)系 :R={ROW,LINE}　　ROW={<ai-1,j,ai,j>|ai-1,j,ai,j∈D,i=1,…,m+1,j=0,…,n+1}　　LINE={<ai-1,j,ai,j>|ai-1,j,ai,j∈D,i=1,…,m+1,j=0,…,n+1}<

27、;b>　　基本操作 :　　Status Pass(MazeType &maze,PosType curpos)　　初始條件: maze 存在迷宮, curpos 保存了當(dāng)前位置的坐標(biāo)　　操作結(jié)果: 如果可通,返回真,否則為假　　void

28、FootPrint(MazeType &maze,PosType curpos)　　初始條件: maze 存在迷宮, curpos 保存了當(dāng)前位置的坐標(biāo)　　操作結(jié)果: 將當(dāng)前坐標(biāo)curpos處的maze[][]值記為足跡　　PosType NextPos(PosType CurPos,int di)&l

29、t;/p>　　初始條件: 各參數(shù)值已經(jīng)定義　　操作結(jié)果: 求得以當(dāng)前位置為棧頂?shù)南乱粋€方向的元素的坐標(biāo)　　Status MazePath(SqStack &S, PosType start, PosType end) 初始條件: maze 存在迷宮地圖　　操作結(jié)果:

30、為建立的迷宮找到一條路徑　　}ADT maze;　　2.2.3、本程序包含三個模塊　　1）主函數(shù)模塊：　　int main（）　　{

31、　　初始化迷宮；　　求解迷宮；　　輸出迷宮的解；　　return 0；　　}<

32、;/b>　　2）棧實(shí)現(xiàn)模塊—實(shí)現(xiàn)棧的抽象殊絕類型　　3）迷宮實(shí)現(xiàn)模塊—實(shí)現(xiàn)迷宮的抽象數(shù)據(jù)類型　　各模塊的調(diào)用關(guān)系如下：　　主函數(shù)模塊——>迷宮模塊——>棧模塊　　4）求解迷宮中一條通路的偽碼算法：</p&g

33、t;　　設(shè)定當(dāng)前位置的初值為入口位置；　　do{　　若當(dāng)前位置可通，　　則{　　將當(dāng)前位置插入棧頂； //納入路徑

34、　　若該位置是出口位置，則結(jié)束； //求得路徑存放在棧中　　否則切換當(dāng)前位置的東鄰方塊為新的當(dāng)前位置；　　}　　否則{　　若棧不空且棧位置尚有其他方向未被探索，</p&g

35、t;　　則設(shè)定新的當(dāng)前位置為沿順時針方向旋轉(zhuǎn)找到的棧頂位置的下一相鄰塊；　　若棧不空但棧頂位置的四周均不可通，　　則{刪去棧頂位置； //后退一步，從路徑中刪去該通道塊；　　若棧不空，則重新測試新的棧頂位置；　　直到找到一個可通的相鄰塊或出棧至?？眨?/p>

36、　　}　　}　　}while(棧不空)；　　{?？照f明沒有路徑存在}　　詳細(xì)設(shè)計(jì)<p&

37、gt;　　坐標(biāo)位置類型　　typedef struct　　{　　int row;　　int line;

38、;　　}PosType;　　迷宮類型　　Status Pass(PosType CurPos)　　//判定當(dāng)前位置是否可以通過，即是未曾走到過的通道塊　　void FootP

39、rint(PosType CurPos)　　//給當(dāng)前可通過的位置標(biāo)記　　PosType NextPos(PosType CurPos,int di)　　//探尋下一個位置，并標(biāo)記方向　　Status MazePath(SqStack &S, PosType st

40、art, PosType end)　　//求解迷宮maze中，從入口start到出口end的一條路徑，　　//如存在，返回OK，否則返回ERROR　　棧類型　　typedef struct&l

41、t;b>　　{　　int ord; //通道塊在路徑上的“序號”　　int di; //通道塊在迷宮中的“坐標(biāo)位置”　　PosType seat;//從此通道塊走向下一通道塊的“方向”　　}SElemType; //

42、棧的元素類型　　typedef struct　　{　　SElemType *base;//在構(gòu)造棧之前和銷毀之后，base的值為NULL　　SElemType *top; //棧頂指針　　in

43、t stacksize; //當(dāng)前已分配的存儲空間，以元素為單位　　}SqStack;//棧定義　　棧的基本操作如下：　　void InitStack(SqStack &S)　　//初始化棧，設(shè)棧S為空棧（S.top=NUL

44、L）　　void Push(SqStack &S,SElemType e)　　//若分配空間成功，則在S 的棧頂插入新的棧頂元素e　　//否則增加棧棧的存儲空間，再插入新的元素　　int GetTop(SqStack &S,SElemType e)<

45、/p>　　//若棧S不空，則以e帶回棧頂元素并返回TRUE，否則返回FALSE　　int Pop(SqStack &S,SElemType &e)　　//若棧不空，則刪除S 的棧頂元素并以e 帶回其值，且返回TRUE　　//否則返回FALSE&l

46、t;p>　　int StackEmpty(SqStack S)　　//若S為空棧（S.top==NULL），則返回TRUE；否則返回FALSE　　具體部分操作的算法如下：　　void InitStack(SqStack &S)　　{<

47、/b>　　//初始化棧S為空棧（S.top=NULL）　　S.base=(SElemType *)malloc(STACK_INIT_SIZE *sizeof(SElemType));　　if(!S.base) exit(OVERFLOW);　　S.top=S.ba

48、se;　　S.stacksize=STACK_INIT_SIZE;　　}//Initstack　　void Push(SqStack &S,SElemType e)　　{　　//若分配

49、空間成功，則在S 的棧頂插入新的棧頂元素e　　//否則增加棧棧的存儲空間，再插入新的元素　　if(S.top-S.base>=S.stacksize)　　{　　S.base=(SElemType *)realloc(S.base

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

51、lt;b>　　}　　*S.top++=e;　　}//Push　　求解迷宮的偽碼算法：　　Status MazePath(SqStack &S, PosType start, PosType end)

52、　　{ 　　//若迷宮maze中存在從入口start到出口end的通道，則　　//一條存放在棧中(從棧底到棧頂為從入口到出口的路徑)，并返　　//回OK，否則返回ERROR　　PosType

53、curpos;　　int curstep;　　SElemType e;　　InitStack(S);　　curpos = start;//設(shè)定“當(dāng)前位置”為“初始位置” 　　curste

54、p = 1; //探索第一步 　　do {　　if (Pass(curpos)) 　　{ 　　//當(dāng)前位置可以通過，即是未曾

55、走到過的的通道塊//留下足跡　　FootPrint(curpos); 　　e.di =1;　　e.ord = curstep;　　e.seat= curpos;　　Push(S,

56、e); //加入路徑 　　if (curpos.row==end.row && curpos.line==end.line) return OK; //到達(dá)出口位置 　　curpos = NextPos(curpos, 1); <

57、;p>　　curstep++;//探索下一步　　} 　　else //當(dāng)前位置不能通過 　　{　　if (!StackEmpty(S)

58、) 　　{　　Pop(S,e);　　while (e.di==4 && !StackEmpty(S)) 　　{<

59、p>　　FootPrint(e.seat); 　　Pop(S,e); 　　curstep--； 　　} 　　if (e.di<4) 　　{

60、　　e.di++; 　　Push(S, e); 　　curpos = NextPos(e.seat, e.di); 　　} //if

61、;　　} //if　　} 　　} while (!StackEmpty(S));　　return ERROR;　　}//MazePath　　主函數(shù)和其它函數(shù)的偽碼算法<

62、;/p>　　void printpath(SqStack S,int n,int m)　　{//打印路徑　　printf("\n\n通路路徑為:\n");　　//PosType start,end;<

63、;p>　　SElemType * p=S.base;//定義一個指針p指向棧中的元素，設(shè)//定初值為p=S.base　　while(p!=S.top)　　{　　maze[p->seat.row][p->seat.line]=2;<

64、;p>　　p++;//將有效路徑的通道塊全部標(biāo)記為2或其他不為1或0的//值　　}　　int i,flag=0;//打印出路徑，周圍用“#”圍成一圈作圍墻　　for(i=0;i<m+2;i++)printf("%c ",'#')

65、;printf("\n");　　for(i=1;i<n+1;i++)　　{ 　　printf("%c ",'#');　　for(int j=1;j<m+1;j++)&

66、lt;/p>　　{　　if(maze[i][j]==2) printf("%c ",'0');　　else printf(" ");　　}<

67、/b>　　printf("%c",'#');　　printf("\n");　　}　　for(i=0;i<m+2;i++)printf("%c ",

68、'#');printf("\n\n");　　}//printpath　　int main()　　{//主函數(shù)　　SqStack S;　　i

69、nt r,l;　　while(true)　　{　　printf("創(chuàng)建一個迷宮，請輸入迷宮長和寬(不得大于20):\n");　　scanf("%d%d",&r,&am

70、p;l);if(r<1 || r>20||l<1||l>20){printf("輸入錯誤!");}　　int i;　　printf("按行輸入%d*%d數(shù)據(jù)(0代表可通,1代表不可通):\n",r,l);　　fo

71、r(i=0;i<l+2;i++)maze[0][i]=1;　　for(i=1;i<r+1;i++)　　{　　maze[i][0]=1;　　for(int j=1;j<l+1;j++)<p

72、>　　scanf("%d",&maze[i][j]);　　maze[i][l+1]=1;　　}　　for(i=0;i<l+2;i++)maze[r+1][i]=1;　　PosType start

73、,end;　　printf("輸入入口行坐標(biāo)和列坐標(biāo):");scanf("%d",&start.row);scanf("%d",&start.line);　　printf("輸入出口行坐標(biāo)和列坐標(biāo):");scanf("%d",&en

74、d.row);scanf("%d",&end.line);　　if(MazePath(S,start,end)) 　　printpath(S,r,l);　　else printf("該迷宮找不到通路!\n\n");<b

75、>　　}　　return 0;　　}//main　　調(diào)試分析　　1、在本次的程序設(shè)計(jì)中，最核心的算法就是MazePath()函數(shù)，其

76、他的算法并沒有出現(xiàn)什么問題。不過在最后輸出的時候本來想輸出路徑的先后順序，即maze[1][2]----->maze[2][2]----->maze[3][2]----->maze[3][3]----->maze[4][3]----->　　maze[5][3]----->maze[5][4]----->maze[5][5]----->maze[5]

77、[6]，但是最后發(fā)現(xiàn)這樣只有在入口在左上角，出口在右下角時，才可以正確輸出。但是入口和出口是隨機(jī)的，若是入口在右下角，出口在左上角，則也同樣輸出maze[1][2]----->maze[2][2]----->maze[3][2]----->maze[3][3]----->maze[4][3]----->　　maze[5][3]----->maze[5][4]-

78、---->maze[5][5]----->maze[5][6]，雖然這兩個路徑是一樣的，但是有先后順序，故最后沒有輸出這種形式，將這段代碼注釋了（源程序中有注釋的代碼）；　　2、本來是想設(shè)計(jì)成既可以手動輸入迷宮又可以自動生成迷宮，但是感覺沒有太大的用處，所以最后省略了，只保留了手動輸入。　　3、在整個編寫的過程中，出現(xiàn)過很多錯誤，包括一些標(biāo)點(diǎn)

79、符號的小錯誤，但是借助DEBUG調(diào)試器和數(shù)據(jù)觀察窗口，很快找出來問題的所在。　　用戶手冊　　本程序的運(yùn)行環(huán)境為 DOS 操作系統(tǒng), 執(zhí)行文件為：迷宮求解.exe.　　進(jìn)入演示程序后 , 即顯示文本方式的用戶界面:　　根據(jù)提示輸入迷宮大

80、小及迷宮后,輸入迷宮的行和列,回車后即可得到所輸入迷宮的解或者是顯示“該迷宮找不到通路!”字樣。　　測試結(jié)果　　輸入長寬為5，6，入口為（1,2），出口為（5,6）的迷宮　　1 0 0 1 1 1　　0 0 1

81、1 1 1　　1 0 0 0 1 1　　0 1 0 1 1 1　　1 1 0 0 0 0　　求解結(jié)果：　　輸入長寬為4，5，入口為（1,1），出口為（4,5）的迷宮&l

82、t;p>　　0 1 0 1 1　　0 0 1 1 0　　1 0 1 1 1　　1 0 0 0 0

83、　　輸出結(jié)果為：　　輸入長寬為4，5，入口為（1,1），出口為（4,5）的迷宮　　1 1 0 1 1 1　　0 1 0 1 0 1　　1 0 0 0 1 1　　0 1 0 1 1 1&l

84、t;p>　　1 1 0 0 0 0　　輸出結(jié)果為：　　附錄　　源程序文件名清單：　　主函數(shù).cpp</p&g

85、t;　　迷宮的實(shí)現(xiàn).h　　棧的實(shí)現(xiàn).h　　參考文獻(xiàn)　　1、嚴(yán)蔚敏，吳偉民.數(shù)據(jù)結(jié)構(gòu)(C語言版)[M].北京：清華大學(xué)出版社，2012.

86、　2、嚴(yán)蔚敏，吳偉民，米寧.數(shù)據(jù)結(jié)構(gòu)題集(C語言版)[M].北京：清華大學(xué)出版社，2012.　　3、蘇仕華，魏韋巍，王敬生，劉燕君.數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)[M].北京：機(jī)械工業(yè)出版社，2010.　　心得體會　　做了這次程序設(shè)計(jì)，我們發(fā)現(xiàn)利用數(shù)據(jù)結(jié)構(gòu)進(jìn)行程序設(shè)計(jì)并不像想像中的那么高深

87、，像我們現(xiàn)在所做的，只是一些最基本的程序。經(jīng)過一個學(xué)期的學(xué)習(xí)，對數(shù)據(jù)結(jié)構(gòu)有了一個初步的認(rèn)識，但沒有進(jìn)行實(shí)際應(yīng)用。這次程序設(shè)計(jì)，就相當(dāng)于對一個學(xué)期的所學(xué)做一個總結(jié)，再進(jìn)行一次綜合運(yùn)用，更是學(xué)到了很多新的東西，無意中也提升了自己的程序設(shè)計(jì)水平；在程序設(shè)計(jì)過程中碰到了很多問題，通過上網(wǎng)查資料等各種手段，我們的解決實(shí)際問題的能力也得到了提高。這次的程序設(shè)計(jì)，讓我們對程序設(shè)計(jì)有了一個更全面的認(rèn)識，如果我們以后能在編程領(lǐng)域深入發(fā)展，這一次也算是我們

眾賞文庫> 全部分類> 畢業(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)確性、安全性和完整性, 同時也不承擔(dān)用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。

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

文檔簡介

溫馨提示

最新文檔

評論

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

文檔簡介

溫馨提示

最新文檔

評論

免費(fèi)下載