迷宮問題課程設(shè)計
目 錄
1問題描述………………………………………………………………...1
2需求分析 1
3概要設(shè)計 1
3.1抽象數(shù)據(jù)類型定義 1
3.2子程序及功能要求 1
3.3各程序模塊之間的調(diào)用關(guān)系 2
4詳細(xì)設(shè)計 2
4.1設(shè)計相應(yīng)數(shù)據(jù)結(jié)構(gòu) 2
4.2主要模塊的算法描述 3
5測試分析 9
6課程設(shè)計總結(jié) 10
參考文獻(xiàn) 10
附錄(源程序清單) 10
1 問題描述
編制程序給出一條通過迷宮的路徑或報告一個“無法通過”的信息。該迷宮是一個M行N列的0-1矩陣,其中0表示無障礙,1表示有障礙。設(shè)入口為(1,1)出口為(M,N)每次移動只能從一個無障礙的單元移到其周圍8個方向上任一無障礙的單元,
2 需求分析
該算法的基本思想是:
(1) 若當(dāng)前位置“可通”,則納入路徑,繼續(xù)前進(jìn);
(2)若當(dāng)前位置“不可通”,則后退,換方向繼續(xù)探索;
(3)若四周“均無通路”,則將當(dāng)前位置從路徑中刪除出去。
3 概要設(shè)計
3.1 抽象數(shù)據(jù)類型定義
typedef struct
{
int x, y; //坐標(biāo)
int dir; //方向
}ElemType;
typedef struct StackNode//構(gòu)造棧
{
ElemType *base;
ElemType *top;
int stacksize;
}SqStack;
3.2 子程序及功能要求
(1)void Input(char b[M][M]);
(2)void Ouput(const char b[M][M]);
(3)int FindWay(char maze[M][M]);
(4)int NextStep(int *x, int *y, int dir).
3.3 各程序模塊之間的調(diào)用關(guān)系
主函數(shù)可調(diào)用子程序void Input(char b[M][M]); void Ouput(const char b[M][M]); int FindWay(char maze[M][M]); int NextStep(int *x, int *y, int dir).
4 詳細(xì)設(shè)計
4.1 設(shè)計相應(yīng)數(shù)據(jù)結(jié)構(gòu)
(1)迷宮類型定義
typedef struct
{
int x, y; //坐標(biāo)
int dir; //方向
}ElemType;
typedef struct StackNode//構(gòu)造棧
{
ElemType *base;
ElemType *top;
int stacksize;
}SqStack;
(2)棧元素類型定義
int InitStack(SqStack *S) //初始化棧
{
S->base=(ElemType*)
malloc(STACK_INIT_SIZE*sizeof(ElemType));
if(!S->base)
{
printf("memory allocation failed,goodbye");
exit(1);
}
S->top=S->base;
S->stacksize=STACK_INIT_SIZE;
return OK;
}
4.2 主要模塊的算法描述
#include
#include
#define M 10 //自己規(guī)定為10*10的迷宮
#define OK 1
#define ERROR 0
#define OVERFLOW -1
#define STACK_INIT_SIZE 100
#define STACKINCREMENT 10
int findway(int);
int NextStep(int *, int *, int );
typedef struct
{
int x, y; //坐標(biāo)
int dir; //方向
}ElemType;
typedef struct StackNode//構(gòu)造棧
{
ElemType *base;
ElemType *top;
int stacksize;
}SqStack;
int InitStack(SqStack *S) //初始化棧
{
S->base=(ElemType*)
malloc(STACK_INIT_SIZE*sizeof(ElemType));
if(!S->base)
{
printf("memory allocation failed,goodbye");
exit(1);
}
S->top=S->base;
S->stacksize=STACK_INIT_SIZE;
return OK;
}
int Push(SqStack *S,ElemType e) //進(jìn)棧操作
{
if(S->top-S->base>=S->stacksize)
{
S->base=(ElemType*)
realloc(S->base,(S->stacksize+STACKINCREMENT)*sizeof(Eleme));
if (!S->base)
{
printf("memory allocation failed,goodbye");
exit(1);
}
S->top = S->base+S->stacksize;
S->stacksize += STACKINCREMENT;
}
*S->top++=e;
return OK;
}
int Pop(SqStack *S,ElemType *e) //出棧操作
{
if(S->top==S->base)
{
return ERROR;
}
*e=*--S->top;
printf("%d\n",e);
return OK;
}
int StackEmpty(SqStack *S) //判斷棧是否為空
{
if(S->top==S->base)
return OK;
else
return ERROR;
}
void Input(char b[M][M]) //輸入時候請注意把一圈都輸入為墻即'#'
{
int i, j;
printf("qingshuirumigongxingzhuang:\n");
for (i = 0; i < M; i++)
{
for (j = 0; j < M; j++)
{
scanf("%c",&b[i][j]);
}
getchar();//吃掉內(nèi)存中的殘留換行符號
}
}
void Ouput(const char b[M][M])
{
int i, j;
printf("migongxingzhuangwei:\n");
for (i = 0; i < M; i++)
{
for (j = 0; j < M; j++)
{
printf("%c",b[i][j]);
}
printf("\n");
}
}
int FindWay(char maze[M][M])
{
ElemType e;
int constep = 1;
int x = 1, y = 1;
SqStack S;
InitStack(&S);
do
{
if (maze[x][y] == ' ') //當(dāng)?shù)?次時 maze[x][y]!=' ' 照樣通不過
{
maze[x][y] = '1';
e.x = x;
e.y = y;
e.dir = 1;
Push(&S,e);
if (x == M-2 && y == M-2)
{
printf("cunzaichukou\n");
return 1;
}
NextStep(&x,&y,1);
constep++;
}
else
{
Pop(&S,&e);
while (e.dir == 4 && !StackEmpty(&S))
{
maze[e.x][e.y] = '0';
Pop(&S,&e);
}
{
if (e.dir < 4)
{
e.dir++;
Push(&S,e);
x = e.x;
y = e.y;
NextStep(&x, &y, e.dir);
}
else
{
printf("meiyouchukou\n");
return 0;
}
}
}
}while(S.top!=S.base);
return 0;
}
int NextStep(int *x, int *y, int dir)
{
switch(dir)
{
case 1:
(*y)++;
break;
case 2:
(*x)++;
break;
case 3:
(*y)--;
break;
case 4:
(*x)--;
break;
default:
break;
}
return 0;
}
int main(void)
{
char a[M][M];
Input(a);
Ouput(a);
FindWay(a);
Ouput(a);
system("pause");
return 0;
}
5 測試分析
6 課程設(shè)計總結(jié)
該次程序設(shè)計我作為組長,我先寫了任務(wù)書,再把模板及其要求告訴了組員,再跟他們一起編寫程序、查找資料來修改程序,再一起測試分析,最后以總結(jié)結(jié)束
通過這次課程設(shè)計,我深刻的體會到了數(shù)據(jù)結(jié)構(gòu)的重要性。學(xué)數(shù)據(jù)結(jié)構(gòu)不只是為了考試,更重要的是它對我們以后也會有很大的幫助,尤其是我們這個注專業(yè)。在整個課程設(shè)計過程中,我遇到了許多困難,不管是編程序改還是調(diào)試等都存在很多問題。一遇到問題我就查看各種資料來解決,但還是又很多不明白的地方,特別是運(yùn)行的時候我還問了同學(xué)。由此我意識到自己有許多要學(xué)的,學(xué)的也不夠認(rèn)真不夠透徹。
參考文獻(xiàn):
[1] 嚴(yán)蔚敏,吳偉民. 數(shù)據(jù)結(jié)構(gòu)(C語言版)[M]. 北京:清華大學(xué)出版社,2002 [2] 劉振鵬,張曉莉,郝杰.?dāng)?shù)據(jù)結(jié)構(gòu)[M].北京:中國鐵道出版社,2003 [3] 李春葆.?dāng)?shù)據(jù)結(jié)構(gòu)習(xí)題與解析(C語言篇)[M].北京:清華大學(xué)出版社,2000
附錄(源程序清單)
#include
#include
#define M 10 //自己規(guī)定為10*10的迷宮
#define OK 1
#define ERROR 0
#define OVERFLOW -1
#define STACK_INIT_SIZE 100
#define STACKINCREMENT 10
int findway(int);
int NextStep(int *, int *, int );
typedef struct
{
int x, y; //坐標(biāo)
int dir; //方向
}ElemType;
typedef struct StackNode//構(gòu)造棧
{
ElemType *base;
ElemType *top;
int stacksize;
}SqStack;
int InitStack(SqStack *S) //初始化棧
{
S->base=(ElemType*)
malloc(STACK_INIT_SIZE*sizeof(ElemType));
if(!S->base)
{
printf("memory allocation failed,goodbye");
exit(1);
}
S->top=S->base;
S->stacksize=STACK_INIT_SIZE;
return OK;
}
int Push(SqStack *S,ElemType e) //進(jìn)棧操作
{
if(S->top-S->base>=S->stacksize)
{
S->base=(ElemType*)
realloc(S->base,(S->stacksize+STACKINCREMENT)*sizeof(Eleme));
if (!S->base)
{
printf("memory allocation failed,goodbye");
exit(1);
}
S->top = S->base+S->stacksize;
S->stacksize += STACKINCREMENT;
}
*S->top++=e;
return OK;
}
int Pop(SqStack *S,ElemType *e) //出棧操作
{
if(S->top==S->base)
{
return ERROR;
}
*e=*--S->top;
printf("%d\n",e);
return OK;
}
int StackEmpty(SqStack *S) //判斷棧是否為空
{
if(S->top==S->base)
return OK;
else
return ERROR;
}
void Input(char b[M][M]) //輸入時候請注意把一圈都輸入為墻即'#'
{
int i, j;
printf("qingshuirumigongxingzhuang:\n");
for (i = 0; i < M; i++)
{
for (j = 0; j < M; j++)
{
scanf("%c",&b[i][j]);
}
getchar();//吃掉內(nèi)存中的殘留換行符號
}
}
void Ouput(const char b[M][M])
{
int i, j;
printf("migongxingzhuangwei:\n");
for (i = 0; i < M; i++)
{
for (j = 0; j < M; j++)
{
printf("%c",b[i][j]);
}
printf("\n");
}
}
int FindWay(char maze[M][M])
{
ElemType e;
int constep = 1;
int x = 1, y = 1;
SqStack S;
InitStack(&S);
do
{
if (maze[x][y] == ' ') //當(dāng)?shù)?次時 maze[x][y]!=' ' 照樣通不過
{
maze[x][y] = '1';
e.x = x;
e.y = y;
e.dir = 1;
Push(&S,e);
if (x == M-2 && y == M-2)
{
printf("cunzaichukou\n");
return 1;
}
NextStep(&x,&y,1);
constep++;
}
else
{
Pop(&S,&e);
while (e.dir == 4 && !StackEmpty(&S))
{
maze[e.x][e.y] = '0';
Pop(&S,&e);
}
{
if (e.dir < 4)
{
e.dir++;
Push(&S,e);
x = e.x;
y = e.y;
NextStep(&x, &y, e.dir);
}
else
{
printf("meiyouchukou\n");
return 0;
}
}
}
}while(S.top!=S.base);
return 0;
}
int NextStep(int *x, int *y, int dir)
{
switch(dir)
{
case 1:
(*y)++;
break;
case 2:
(*x)++;
break;
case 3:
(*y)--;
break;
case 4:
(*x)--;
break;
default:
break;
}
return 0;
}
int main(void)
{
char a[M][M];
Input(a);
Ouput(a);
FindWay(a);
Ouput(a);
system("pause");
return 0;
}【迷宮問題課程設(shè)計】相關(guān)文章:
課程設(shè)計報告07-20
方法、思路與問題06-01
論文答辯問題01-17
休謨問題與先驗范疇05-06
施工組織設(shè)計課程設(shè)計開題報告07-13
論文答辯問題與答案04-27
論文答辯的問題及答案04-06
答辯時要注意的問題04-14
讓學(xué)生善于質(zhì)疑問題06-11
物體平衡問題的求解方法05-13