迷宮問題課程設(shè)計(jì)報(bào)告

上傳人：奔*** IP屬地：河北更新時(shí)間：2024-03-01 格式：doc 頁數(shù)：14 大?。?25.50KB 人氣指數(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ì)目的　　1, 深入了解棧的特征及數(shù)據(jù)結(jié)構(gòu)。　　2, 了解迷宮問題的提出背景以及試探法的求解思路。

2、　　3, 設(shè)計(jì)實(shí)現(xiàn)一個(gè)完整的迷宮求解程序。　　課程設(shè)計(jì)內(nèi)容　　迷宮是實(shí)驗(yàn)心理學(xué)中一個(gè)古典問題。用計(jì)算機(jī)解迷宮路徑的程序，就是仿照人走迷宮。計(jì)算機(jī)解迷宮時(shí)，通常用的是"窮舉求解"的方法，即從入口出發(fā)，順某一方向向前探索，若能走通，則繼續(xù)往前走；否則沿原路退回，換一個(gè)方向再繼續(xù)探索，直至所有可能的通路

3、都探索到為止。　　三、需求分析　　電腦自動(dòng)存儲迷宮，先將m*n迷宮先輸入在文件中，通過輸入文件名（*.txt），將該迷宮在屏幕上顯示出來，選擇通路。　　由用戶自己手動(dòng)創(chuàng)建迷宮，將創(chuàng)建好的m*n迷宮保存在文件（*.txt）中，選擇通路。

4、　　用“回溯法”來尋找通路，借用一個(gè)move[4]數(shù)組來存儲四個(gè)方向，數(shù)組的i,j兩個(gè)域分別表示行列位移的增量,在通過棧的相關(guān)操作來求解通路。　　最終的解要求在屏幕上顯示并存入文件(*.txt)中。　　四、概要設(shè)計(jì)　　1．系統(tǒng)結(jié)構(gòu)圖<

5、;/p>　　2．功能模塊說明　　1，定義相關(guān)的結(jié)構(gòu)體。　　2，關(guān)于棧的操作，入棧，出棧，判空棧，銷毀棧。　　3，先在文本文件中創(chuàng)建好一個(gè)迷宮，然后顯示在屏幕上，尋找通路并保存。　　4，用戶自己手動(dòng)創(chuàng)建好一個(gè)

6、迷宮，并保存在文件中，然后尋找通路并保存。　　5，利用菜單選擇自己創(chuàng)建迷宮的方式。　　五、詳細(xì)設(shè)計(jì)及運(yùn)行結(jié)果　　1，主要的流程圖　　2，重要的程序，Seekpath的主要算法　　//尋找迷宮路

7、徑并保存　　void Seekpath(char maze[Max][Max])　　{　　int i, j, d, x, y, m, n;　　Seqstack *S;　　F

8、ILE *fp;　　Item move[4]; 　　Elemtype t;　　fp=fopen("路徑.txt","wt");　　S = (struct stack *)malloc(sizeof

9、(struct stack));　　InitStack(S);　　move[0].i = 0; move[0].j = 1; //move[4]數(shù)組的初始化　　move[1].i = 1; move[1].j = 0;　　move[2].i = 0; mov

10、e[2].j = -1;　　move[3].i = -1;move[3].j = 0; 　　d = 0;　　printf("請輸入您想出的出口.\n");　　scanf("%d %d",&am

11、p;m,&n);　　printf("請輸入您想進(jìn)的入口. \n");　　scanf("%d",&t.i);　　t.j = 1;　　t.d = -1;

12、 //初始方向?yàn)?1　　if(S==NULL)　　{　　printf("error!");　　return;&l

13、t;b>　　}　　PushStack(S, t); //棧里的第一個(gè)元素就是入口點(diǎn)　　while(!EmptyStack(S))　　{　　PopStack(S, &

14、;t); //第一個(gè)元素出棧　　i = t.i;　　j = t.j;　　d = t.d +1; //下一個(gè)方向　　while(

15、d<4) //開始試探東南西北四個(gè)方向　　{　　x = i+move[d].i;　　y = j+move[d].j; //試探后的新坐標(biāo)　　if(maze[x][y

16、] == '0')　　{　　t.i = i;　　t.j = j;　　t.d = d;

17、　　PushStack(S, t); //可以走的坐標(biāo)入棧　　i=x; j=y;　　maze[i][j] = -1; //已走過的路置為-1　　if(m==i && n==j) //判斷是否到了

18、出口　　{　　printf("通路為:\n"); //將走通的路徑打印出來　　printf("(%2d,%2d) <==",m, n);　　fprintf(fp,"

19、;%2d,%2d",m,n); //將m,n的值按%2d和%2d的格式輸出到fp指向的文件上　　while(!EmptyStack(S) && S->top!=0) 　　{　　PopStack(S, &t);</p&

20、gt;　　printf("(%2d,%2d) <== ",t.i,t.j);　　fputs("<==",fp);　　fprintf(fp,"%2d,%2d",t.i,t.j);　　}

21、　　if(S->top==0)　　PopStack(S, &t);　　printf("(%2d,%2d) ",t.i,t.j);　　printf("\n路徑已保存!\n");

22、　　fputs("<==",fp);　　fprintf(fp,"%2d,%2d",t.i,t.j);　　DestoryStack(&S); //所有的元素出棧之后銷毀棧　　return;<

23、;p>　　}　　else　　d=0;　　}　　else

24、　　d++;　　}　　}　　DestoryStack(&S);　　printf("該迷宮不能走通!\n");&

25、lt;/p>　　fclose(fp);　　return ;　　}　　3,運(yùn)行結(jié)果 　　(1)，文本文件中提前存儲好迷宮，然后選擇通

26、路。　　文件可以打開的情況　　文件不能打開的情況　?。?），用戶手動(dòng)創(chuàng)建迷宮　　有通路的情況　　沒

27、有通路的情況　　六、調(diào)試情況，設(shè)計(jì)技巧及體會　　1，調(diào)試情況　　在調(diào)試的時(shí)候，程序出現(xiàn)了好多問題，有邏輯上的錯(cuò)誤，還有語法上的錯(cuò)誤，特別是文件的讀寫方式那經(jīng)常搞錯(cuò)，還有一個(gè)關(guān)于緩沖區(qū)的問題，經(jīng)常忘記用　　Flush

28、all()，導(dǎo)致調(diào)試時(shí)出現(xiàn)問題。不過最后經(jīng)過仔細(xì)的分析解決了這個(gè)問題，最終的程序也沒有太大的問題。　　2，程序的優(yōu)缺點(diǎn)　　我認(rèn)為本次程序中較好的一點(diǎn)是，我可以用兩種方法來創(chuàng)建迷宮并顯示在屏幕上，然后查找通路并保存。不足之處是沒有找到最短路徑，界面也不夠美觀好看，最終展示出的迷宮路徑不太直觀，如果用動(dòng)態(tài)的會更好。<

29、;/p>　　3，心得體會　　通過一周的學(xué)習(xí)與上機(jī)編程，大大提高了我的編程能力，讓我把棧的相關(guān)知識和數(shù)據(jù)結(jié)構(gòu)有了更好的理解。同時(shí)也使我面對一個(gè)程序時(shí)，能更好地深刻的去理解它，分析它，找出最有效的解決方法。在面對不懂的問題時(shí)，請教老師或同學(xué)，幫助我解決問題，這樣也有助于我能力的提高。但在以后還需要多多上機(jī)編程，真正學(xué)通數(shù)據(jù)結(jié)構(gòu)這門課，

30、為之后的相關(guān)科目打好基礎(chǔ)?？傊?，此次實(shí)習(xí)，我收獲頗多，以后會更加努力的。　　七、參考文獻(xiàn)　　數(shù)據(jù)結(jié)構(gòu)-C語言描述 C語言程序設(shè)計(jì)　　八、附錄：源代碼　　#include<stdio.h

31、>　　#include<malloc.h>　　#include<string.h>　　#include<stdlib.h>　　#define stacksize 20　　#define M

32、ax 20 //maze[][]數(shù)組行列的最大范圍　　typedef struct //move[4]的兩個(gè)域，0,1，2,3分別表示東西南北　　{ 　　int i; //i表示行位移

33、　　int j; //j表示列位移　　}Item;　　typedef struct //棧中每一個(gè)節(jié)點(diǎn)的三個(gè)元素　　{ 　　int i;

34、 //當(dāng)前的行坐標(biāo)　　int j; //當(dāng)前的列坐標(biāo)　　int d; //下一步要到達(dá)的方向　　}Elemtype;　　//有關(guān)順序棧的相關(guān)操作　　typedef struc

35、t stack　　{　　Elemtype data[stacksize];　　int top;　　}Seqstack;　　//初始化棧&

36、lt;/b>　　void InitStack(Seqstack *S)　　{　　S->top = -1;　　}　　//入棧&

37、lt;/b>　　int PushStack(Seqstack *S,Elemtype x)　　{　　if(S->top == stacksize-1 )　　return 0;</

38、p>　　S->top++;　　S->data[S->top]=x;　　return 1;　　}

39、　　//出棧　　int PopStack(Seqstack *S,Elemtype *x)　　{　　if(S->top == -1)　　return 0;</p&g

40、t;　　else　　{　　*x = S->data[S->top];　　S->top--;　　ret

41、urn 1;　　}　　}　　//判空棧　　int EmptyStack(Seqstack *S)

42、　　{　　if(S->top == -1)　　return 1;　　else 　　return 0;</p&

43、gt;　　}　　//銷毀棧　　void DestoryStack(Seqstack **S)　　{　　if(*S)&l

44、t;/b>　　free(*S);　　*S = NULL;　　return; 　　}　　//電腦自動(dòng)創(chuàng)建迷宮&l

45、t;/p>　　int dcreatmaze(char maze[][Max],int M,int N) //M N為電腦自動(dòng)創(chuàng)建時(shí)的行和列　　{　　int i, j; //創(chuàng)建迷宮時(shí)的下標(biāo)，i表示行，j表示列

46、;　　FILE *fp; 　　char n;　　char filename[20];　　printf("請輸入要打開文件的完整路徑及文件名: ");

47、　　flushall();　　gets(filename);　　fp = fopen(filename, "r"); //只讀，為輸入打開一個(gè)文本文件　　if( fp == NULL)

48、{　　printf("文件打開失敗，文件名可能不存在 !\n");　　return 0;　　}　　flushall();<p&

49、gt;　　while(!feof(fp)) //用來測試fp所指向的文件當(dāng)前狀態(tài)是否"文件結(jié)束"　　{　　for(i=0; i<M; i++)　　{<p&

50、gt;　　for(j=0;j<N;j++)　　{　　fscanf(fp,"%c",&maze[i][j]); //將磁盤文件中的數(shù)據(jù)送給maze[][]數(shù)組　　}<p&g

51、t;　　fscanf(fp,"%c",&n); //將磁盤文件中的換行給n　　}　　}　　fclose(fp);　　printf("\n

52、親，您現(xiàn)在可以走迷宮了~~~\n");　　for(i=0; i<=M; i++) //輸出迷宮　　{　　for(j=0; j<=N; j++)　　{&

53、lt;/b>　　if (maze[i][j] == '1')　　printf("◆");　　else if(maze[i][j] == '0')　　printf("◇");

54、　　}　　printf("\n");　　}　　printf("\n");　　return 1;&l

55、t;/p>　　}　　//尋找迷宮路徑并保存　　void Seekpath(char maze[Max][Max])　　{　　int i, j, d, x, y, m,

56、 n;　　Seqstack *S;　　FILE *fp;　　Item move[4]; 　　Elemtype t;　　fp=fopen("路徑.txt",&

57、quot;wt");　　S = (struct stack *)malloc(sizeof(struct stack));　　InitStack(S);　　move[0].i = 0; move[0].j = 1; //move[4]數(shù)組的初始化

58、　move[1].i = 1; move[1].j = 0;　　move[2].i = 0; move[2].j = -1;　　move[3].i = -1;move[3].j = 0; 　　d = 0;　　printf("

59、;請輸入您想出的出口.\n");　　scanf("%d %d",&m,&n);　　printf("請輸入您想進(jìn)的入口. \n");　　scanf("%d",&t.i);<b

60、>　　t.j = 1;　　t.d = -1; //初始方向?yàn)?1　　if(S==NULL)　　{　　printf("error!");&

61、lt;/p>　　return;　　}　　PushStack(S, t); //棧里的第一個(gè)元素就是入口點(diǎn)　　while(!EmptyStack(S))

62、　　{　　PopStack(S, &t); //第一個(gè)元素出棧　　i = t.i;　　j = t.j;

63、;　　d = t.d +1; //下一個(gè)方向　　while(d<4) //開始試探東南西北四個(gè)方向　　{　　x = i+move[d].i;　　y

64、 = j+move[d].j; //試探后的新坐標(biāo)　　if(maze[x][y] == '0')　　{　　t.i = i;　　t.j = j

65、;　　t.d = d;　　PushStack(S, t); //可以走的坐標(biāo)入棧　　i=x; j=y;　　maze[i][j] = -1; //已走

66、過的路置為-1　　if(m==i && n==j) //判斷是否到了出口　　{　　printf("通路為:\n"); //將走通的路徑打印出來　　printf(&qu

67、ot;(%2d,%2d) <==",m, n);　　fprintf(fp,"%2d,%2d",m,n); //將m,n的值按%2d和%2d的格式輸出到fp指向的文件上　　while(!EmptyStack(S) && S->top!=0) &

68、lt;b>　　{　　PopStack(S, &t);　　printf("(%2d,%2d) <== ",t.i,t.j);　　fputs("<==",fp);　　fprintf(fp,&

69、quot;%2d,%2d",t.i,t.j);　　}　　if(S->top==0)　　PopStack(S, &t);　　printf("(%2d,%2d) ",t.i,t.j);<

70、/p>　　printf("\n路徑已保存!\n");　　fputs("<==",fp);　　fprintf(fp,"%2d,%2d",t.i,t.j);　　DestoryStack(&S); //所有的元素

71、出棧之后銷毀棧　　return;　　}　　else　　d=0;

72、;　　}　　else　　d++;　　}　　}　　Desto

73、ryStack(&S);　　printf("該迷宮不能走通!\n");　　fclose(fp);　　return ;　　}

74、void zcreatmaze(char maze[Max][Max]) 　　{　　int i,j,m,n;　　FILE *fp;　　char ch;<

75、/p>　　fp=fopen("migong.txt","wt"); //為輸出打開一個(gè)文本文件,只寫　　printf("請輸入迷宮的行數(shù)和列數(shù)(包括外圍的墻壁):");　　scanf("%d%d",&m,&n);</p&g

76、t;　　flushall();　　printf("\n請輸入迷宮\n");　　for(i=0;i<m;i++)　　{//創(chuàng)建迷宮　　for(j=0;j<n;j++)

77、　　scanf("%c",&maze[i][j]);　　flushall();　　}　　printf("\n");　　printf("您創(chuàng)建的迷宮為:\n\n");&

78、lt;/p>　　for(i=0; i<m; i++) //輸出迷宮 　　{　　for(j=0; j<n; j++)　　{　　if(maze[i][j]

79、 == '1')　　printf("◆");　　else if(maze[i][j] == '0')　　printf("◇");　　fprintf(fp,"%c ",maze[i

80、][j]);　　} 　　fprintf(fp,"\n");　　printf("\n");　　}　　fclose(f

81、p);　　printf("\n");　　printf("該迷宮已保存!\n");　　Seekpath(maze);　　printf("\n");　　}&

82、lt;/b>　　void menu()　　{　　printf("\t ※※※※※※※※※※※※※※※\n\n");　　printf("\t ☆1

83、. 電腦自動(dòng)生成迷宮 \n");　　printf("\t ☆2. 用戶手動(dòng)創(chuàng)建迷宮 \n");　　printf("\t ☆0. 退出系統(tǒng) \n\n");　　print

84、f("\t ※※※※※※※※※※※※※※※ \n");　　printf("\t 輸入數(shù)字編號(0-2):");　　}　　void main()<

85、b>　　{　　char maze[Max][Max];　　int choice;　　while(choice)　　{　　flushall();

86、　　system("cls");　　menu();　　scanf("%d",&choice);　　switch(choice)　　{ </b&

87、gt;　　case 1: 　　system("cls");　　dcreatmaze(maze,8,8);　　Seekpath(maze);　　printf("\n

88、");　　system("pause");　　break;　　case 2:　　system("cls");<p&g

89、t;　　zcreatmaze(maze);　　system("pause");　　break;　　case 0:　　break;</

眾賞文庫> 全部分類> 畢業(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ì)報(bào)告

文檔簡介

溫馨提示

最新文檔

評論

迷宮問題課程設(shè)計(jì)報(bào)告

文檔簡介

溫馨提示

最新文檔

評論

免費(fèi)下載