迷宮問題課程設(shè)計報告

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

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

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

文檔簡介

1、　　題目：迷宮問題 　　課程設(shè)計目的　　1, 深入了解棧的特征及數(shù)據(jù)結(jié)構(gòu)。　　2, 了解迷宮問題的提出背景以及試探法的求解思路。

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

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

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

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

6、迷宮，并保存在文件中，然后尋找通路并保存。　　5，利用菜單選擇自己創(chuàng)建迷宮的方式。　　五、詳細設(shè)計及運行結(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("請輸入您想進的入口. \n");　　scanf("%d",&t.i);　　t.j = 1;　　t.d = -1;

12、 //初始方向為-1　　if(S==NULL)　　{　　printf("error!");　　return;&l

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

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

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

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

17、　　PushStack(S, t); //可以走的坐標入棧　　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,運行結(jié)果 　　(1)，文本文件中提前存儲好迷宮，然后選擇通

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

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

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

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

30、為之后的相關(guān)科目打好基礎(chǔ)?？傊?，此次實習(xí)，我收獲頗多，以后會更加努力的。　　七、參考文獻　　數(shù)據(jù)結(jié)構(gòu)-C語言描述 C語言程序設(shè)計　　八、附錄：源代碼　　#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]的兩個域，0,1，2,3分別表示東西南北　　{ 　　int i; //i表示行位移

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

34、 //當前的行坐標　　int j; //當前的列坐標　　int 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; 　　}　　//電腦自動創(chuàng)建迷宮&l

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

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

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

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

49、gt;　　while(!feof(fp)) //用來測試fp所指向的文件當前狀態(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("請輸入您想進的入口. \n");　　scanf("%d",&t.i);<b

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

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

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

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

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

65、;　　t.d = d;　　PushStack(S, t); //可以走的坐標入棧　　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"); //為輸出打開一個文本文件,只寫　　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、. 電腦自動生成迷宮 \n");　　printf("\t ☆2. 用戶手動創(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è)計

溫馨提示

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)方式做保護處理，對用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯，并不能對任何下載內(nèi)容負責。
6. 下載文件中如有侵權(quán)或不適當內(nèi)容，請與我們聯(lián)系，我們立即糾正。
7. 本站不保證下載資源的準確性、安全性和完整性, 同時也不承擔用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。

迷宮問題課程設(shè)計報告

文檔簡介

溫馨提示

最新文檔

評論

迷宮問題課程設(shè)計報告

文檔簡介

溫馨提示

最新文檔

評論

免費下載