《C++ 數(shù)據(jù)結(jié)構(gòu) 迷宮問(wèn)題》由會(huì)員分享，可在線閱讀，更多相關(guān)《C++ 數(shù)據(jù)結(jié)構(gòu) 迷宮問(wèn)題（23頁(yè)珍藏版）》請(qǐng)?jiān)谘b配圖網(wǎng)上搜索。
1、課程設(shè)計(jì)（論文）任務(wù)書(shū)
軟件 學(xué) 院 軟件工程+電子商務(wù)2009 專(zhuān) 業(yè) 2 班
一、課程設(shè)計(jì)(論文)題目 迷宮問(wèn)題
二、課程設(shè)計(jì)(論文)工作自 2010 年 12月 27 日起至 2011 年 1月 2 日止
三、課程設(shè)計(jì)(論文) 地點(diǎn): 創(chuàng)新大樓實(shí)訓(xùn)中心
四、課程設(shè)計(jì)(論文)內(nèi)容要求：
1．本課程設(shè)計(jì)的目的
（1）鞏固和加深對(duì)數(shù)據(jù)結(jié)構(gòu)基本知識(shí)的理解，提高綜合運(yùn)
2、用課程知識(shí)的能力。
（2）使學(xué)生掌握軟件設(shè)計(jì)的基本內(nèi)容和設(shè)計(jì)方法，并培養(yǎng)學(xué)生進(jìn)行規(guī)范化軟
件設(shè)計(jì)的能力。
（3）使學(xué)生掌握使用各種計(jì)算機(jī)資料和有關(guān)參考資料，提高學(xué)生進(jìn)行程序設(shè)
計(jì)的基本能力。
2．課程設(shè)計(jì)的任務(wù)及要求
1）基本要求：
（1）對(duì)系統(tǒng)進(jìn)行功能模塊分析、控制模塊分析；
（2）系統(tǒng)設(shè)計(jì)要能完成題目所要求的功能；
（3）編程簡(jiǎn)練，可用，盡可能的使系統(tǒng)的功能更加完善和全面；
（4）說(shuō)明書(shū)、流程圖要清楚；
（5）提高學(xué)生的論文寫(xiě)作能力；
（6）特別要求自己獨(dú)立完成；
2）創(chuàng)新要求：
在基本要求達(dá)到后，可進(jìn)行創(chuàng)新設(shè)計(jì)，如改善算法性能、友好的人機(jī)界面。
3、
3）課程設(shè)計(jì)論文編寫(xiě)要求
（1）要按照書(shū)稿的規(guī)格打印與寫(xiě)課程設(shè)計(jì)論文
（2）論文包括目錄、正文、小結(jié)、參考文獻(xiàn)、附錄等
（3）課程設(shè)計(jì)論文裝訂按學(xué)校的統(tǒng)一要求完成
4）課程設(shè)計(jì)進(jìn)度安排
內(nèi)容 天數(shù) 地點(diǎn)
構(gòu)思及收集資料 1 圖書(shū)館
編碼與調(diào)試 3 實(shí)驗(yàn)室
撰寫(xiě)論文 1 圖書(shū)館、實(shí)驗(yàn)室
學(xué)生簽名：
200
4、11 年 1 月 3日
課程設(shè)計(jì)(論文)評(píng)審意見(jiàn)
（1）基本算法 （20分）：優(yōu)（?。?、良（?。⒅校ā。?、一般（?。?、差（?。?；
（2）設(shè)計(jì)分析 （20分）：優(yōu)（?。⒘迹ā。?、中（?。⒁话悖ā。?、差（?。?
（3）調(diào)試分析?。?0分）：優(yōu)（?。?、良（?。?、中（ ）、一般（ ）、差（?。?；
（4）論文內(nèi)容?。?0分）：優(yōu)（?。?、良（ ）、中（ ）、一般（?。?、差（?。?；
（5）答辯分析?。?0分）：優(yōu)（?。?、良（?。?、中（ ）、一般（ ）、差（?。?；
（6）格式規(guī)范性及考勤是否降等級(jí)：是（ ）、否（?。?
評(píng)閱人： 職稱(chēng)： 講師
5、
2011 年 1月4日
目錄
一、 需求分析 1
二、 概要設(shè)計(jì) 2
三、 詳細(xì)設(shè)計(jì) 5
四、 調(diào)試分析及測(cè)試 15
五、 個(gè)人工作及創(chuàng)新 18
六、 小結(jié) 19
參考文獻(xiàn) 20
數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)
一、 需求分析
1.選題理由
本次課設(shè)我選擇了迷宮問(wèn)題，迷宮求解是數(shù)據(jù)結(jié)構(gòu)課程的一個(gè)經(jīng)典問(wèn)題，
迷宮問(wèn)題要求尋找一條從入口到出口的路徑。通常用的是“窮舉求解”的方法。為了保證在任何位置上都能原路退回，顯然需要用一個(gè)后進(jìn)先出的結(jié)構(gòu)來(lái)保存從入口到當(dāng)前位置的路徑。因此，在求解迷宮通路的算法中要應(yīng)用“?！钡乃枷搿?duì)于棧的內(nèi)容在整個(gè)學(xué)期的學(xué)
6、習(xí)中我也有了一定的了解，所以選擇了迷宮這一經(jīng)典問(wèn)題作為本次課設(shè)的內(nèi)容。
2.基本原理分析
迷宮問(wèn)題通常是用“窮舉求解”方法解決，即從入口出發(fā)，順著某一個(gè)方向進(jìn)行探索，若能走通，則繼續(xù)往前走；否則沿著原路退回，換一個(gè)方向繼續(xù)探索，直至出口位置，求得一條通路。假如所有可能的通路都探索到而未能到達(dá)出口，則所設(shè)定的迷宮沒(méi)有通路。棧是一個(gè)后進(jìn)先出的結(jié)構(gòu)，可以用來(lái)保存從入口到當(dāng)前位置的路徑。
以二維數(shù)組存儲(chǔ)迷宮數(shù)據(jù)，通常設(shè)定入口點(diǎn)的下標(biāo)為（1，1），出口點(diǎn)的下標(biāo)為（n,n）。為處理方便起見(jiàn)，在迷宮的四周加一圈障礙。對(duì)于迷宮任何一個(gè)位置，均約定東、南、西、北四個(gè)方向可通。
7、
3.功能要求
（1）以一個(gè)二維數(shù)組Maze[m+2][n+2]表示迷宮，其中：Maze[0][j]和Maze[m+1][j](0<=j<=n+1)及Maze[i][0]和Maze[i][n+1] (0<=i<=m+1)為做外層的一圈障礙。數(shù)組中以0表示通路，1表示障礙，限定迷宮的大小為：m,n<=10。
（2）用戶(hù)需用文件的形式輸入迷宮的數(shù)據(jù)：文件中第一行的數(shù)據(jù)為迷宮的行數(shù)m和列數(shù)n；從第2行至第m+1行（每行n個(gè)數(shù)）為迷宮值，用0，1輸入，同行中的兩個(gè)數(shù)字之間用空白字符相隔。
（3）迷宮的入口位置和出口位置可由用戶(hù)隨時(shí)設(shè)定。
（4）若設(shè)定的迷宮存在通路，則以長(zhǎng)方陣形式將迷宮及
8、其通路輸出到標(biāo)準(zhǔn)輸出文件上，其中字符“#”表示障礙，“*”表示路徑，“@”表示曾途經(jīng)該位置但不能到達(dá)出口，其余位置用空格符表示。若設(shè)定迷宮不存在通路則報(bào)告相應(yīng)信息
（5）本程序只求出一條成功的通路。
（6）程序執(zhí)行的命令為：1，創(chuàng)建迷宮；2，求解迷宮；3，輸出迷宮的解。
二、 概要設(shè)計(jì)
1、 數(shù)據(jù)結(jié)構(gòu)及其抽象數(shù)據(jù)類(lèi)型的定義。
（1）棧的抽象數(shù)據(jù)類(lèi)型
ADT Stack{
數(shù)據(jù)對(duì)象：D={ai| ai∈CharSet,i=1,2…n,n>=0}
數(shù)據(jù)關(guān)系：R1={| ai-1, ai∈D,i=2,…n}
基本操作：
InitStack(&S)
操作
9、結(jié)果：構(gòu)造一個(gè)空棧S。
DestroyStack(&S)
初始條件：棧S已存在。
操作結(jié)果：銷(xiāo)毀棧S。
ClearStack(&S)
初始條件：棧S已存在。
操作結(jié)果：將S清為空棧。
StackLength(S)
初始條件：棧S已存在。
操作結(jié)果：返回棧S的長(zhǎng)度。
StackEmpty(S)
初始條件：棧S已存在。
操作結(jié)果：若S為空棧，則返回TRUE，否則返回FALSE。
GetTop(S，&e)
初始條件：棧S已存在。
操作結(jié)果：若棧S不空，則以e返回棧頂元素。
Push(&S， e)
初始條件：棧S已存在。
操作結(jié)果：在棧S的棧頂插入新的棧頂元素e。
10、
Pop(&S，&e)
初始條件：棧S已存在。
操作結(jié)果：刪除S的棧頂元素，并以e返回其值。
StackTraverse（S，visit（））
初始條件：棧S已存在。
操作結(jié)果：從棧底到棧頂依次對(duì)S中的每個(gè)元素調(diào)用函數(shù)visit（）。
} ADT Stack
?
（2）迷宮的抽象數(shù)據(jù)類(lèi)型
ADT maze{
數(shù)據(jù)對(duì)象：D={ai,j| ai,j∈{ ' ','#','@','*'},0<=i<=m+1,0<=j<=n+1,m,n<=10}
數(shù)據(jù)關(guān)系：R={ROW,COL}
基本操作：
InitMaze(&M,a,row,col)
初始條件：二維數(shù)組a[row+2][
11、col+2]已存在，其中自第1行至第row+1行，每行中自第1列至第col+1列的元素已有值，并且以值0表示通路，以值1表示障礙。
操作結(jié)果：構(gòu)成迷宮的字符型數(shù)組，以空白字符表示通路，以字符‘#’表示障礙，并在迷宮四周加上一圈障礙。
MazePath(&M)
初始條件：迷宮M已被賦值。
操作結(jié)果：若迷宮M中存在一條通路，則按以下規(guī)定改變迷宮M的狀態(tài)：以字符’*’表示路徑上的位置，字符‘@’表示“死胡同”，否則迷宮的狀態(tài)不變。
PrintMaze（M）
初始條件：迷宮M已存在。
操作結(jié)果：以字符形式輸出迷宮。
} ADT maze
?
2、整體框架
本程序包含三個(gè)模塊
12、（1）棧模塊——實(shí)現(xiàn)棧抽象數(shù)據(jù)類(lèi)型
（2）迷宮模塊——實(shí)現(xiàn)迷宮抽象數(shù)據(jù)類(lèi)型
（3）主程序模塊：
void mian()
{
?? 初始化；
? Do{
接受命令；
處理命令；
}while(命令!=“退出”)；
}
各模塊之間的調(diào)用關(guān)系如圖一：
圖一：調(diào)用關(guān)系圖
函數(shù)的調(diào)用關(guān)系圖反映了程序的層次結(jié)構(gòu)如圖二：
圖二 ：函數(shù)的調(diào)用關(guān)系圖
三、 詳細(xì)設(shè)計(jì)
源程序:
#include
13、dio.h>
#include
#include
#define MAXLEN 10//迷宮包括外墻最大行列數(shù)目
#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
?
typedef int Status;
// 坐標(biāo)位置類(lèi)型?
typedef struct{
??? int r,c;
} PosType;//迷宮中r行c列的位置
//迷宮類(lèi)型?
typedef struct {
???? int r;
???? int c;
???? ch
14、ar arr[MAXLEN][MAXLEN];//可取' ','*','@','#'
}MazeType;??
?
typedef struct{
//int step; // 當(dāng)前位置在路徑上的“序號(hào)”
?? PosType seat; //當(dāng)前的坐標(biāo)位置
?? int di; //往下一坐標(biāo)位置的方向
}SElemType;
?//結(jié)點(diǎn)類(lèi)型
typedef struct NodeType{
?? SElemType data;
?? NodeType *next;
}NodeType,*LinkType;
//棧類(lèi)型?
typedef struct {
15、
?? LinkType top;
?? int stacksize;
}SqStack;
?
PosType start;
PosType end;
MazeType maze;
bool found;
?
//創(chuàng)建棧
Status InitStack(SqStack &S)
{
?? S.top=(LinkType)malloc(sizeof(NodeType));
?? S.top->next=NULL;
?? S.stacksize=0;
?? return OK;
}
?
//進(jìn)棧
Status Push(SqStack &S,SElemT
16、ype &e)
{
?? LinkType p;
?? p=(NodeType*)malloc(sizeof(NodeType));
?? p->data=e;
?? p->next=S.top;
?? S.top=p;
?? S.stacksize++;
?? return OK;
}
?
//判斷是否為?？?
Status StackEmpty(SqStack S)
{
?? if(S.top->next==NULL) return OK;
?? return ERROR;
}
?
//出棧
Status Pop(SqStack &S,SElemTyp
17、e &e)
{
?? LinkType p;
?? if(StackEmpty(S)) return ERROR;
?? p=S.top;
?? e=p->data;
?? S.top=S.top->next;
?? S.stacksize--;
?? free(p);
?? return OK;
}
?
//銷(xiāo)毀棧
Status DestroyStack(SqStack &S)
{
?? LinkType p;
?? while(S.top!=NULL)
?? {
????? p=S.top;
????? S.top=S.top->next;
????
18、? free(p);
?? }//一個(gè)一個(gè)刪除
?? if(S.top==NULL) return OK;
?? else return ERROR;
}
?
//曾走過(guò)但不是通路標(biāo)記并返回OK
Status MarkPrint(MazeType &maze,PosType curpos)
{
?maze.arr[curpos.r][curpos.c]='@';//"@"表示曾走過(guò)但不通
?return OK;
}
?
//曾走過(guò)而且是通路標(biāo)記并返回OK
Status FootPrint(MazeType &maze,PosType curpos)
{
? ma
19、ze.arr[curpos.r][curpos.c]='*';//"*"表示可通
? return OK;
}
?
//選擇下一步的方向
PosType NextPos(PosType &curpos,int i)
{
?? PosType cpos;
?? cpos=curpos;
?? switch(i){??????? //1.2.3.4分別表示東,南,西,北方向
????? case 1 : cpos.c+=1;
??????? ? break;
????? case 2 : cpos.r+=1;
??????? ? break;
????? case
20、3 : cpos.c-=1;
??????? ? break;
????? case 4 : cpos.r-=1;
??????? ? break;
}
return cpos;
}
?
//判斷當(dāng)前位置是否可通
Status Pass(MazeType &maze, PosType curpos)
{
??? if(maze.arr[curpos.r][curpos.c]==' ') return TRUE;
????? else return FALSE;
}
?
//創(chuàng)建迷宮
//按照用戶(hù)輸入的二維數(shù)組（0或1），設(shè)置迷宮maze的初值，包括加上邊緣
21、一圈的值
void InitMaze(MazeType &maze, char a[MAXLEN][MAXLEN], int row, int col)
{
?? maze.r=row;
?? maze.c=col;
?? for(int i=0;i<=col+1;i++){
??? ?? a[0][i]='1';
??? ?? a[row+1][i]='1';
?? }
?? for(i=0;i<=row+1;i++){
??? ?? a[i][0]='1';
??? ?? a[i][col+1]='1';
?? }
?? for(i=0;i<=maze.r+2;i
22、++){
????? for(int j=0;j
23、 SqStack S;
?? SElemType e;
?? InitStack(S);
?? curpos=start;//設(shè)定“當(dāng)前位置”為“入口位置”
? //curstep=1; //探索第一步
?? found=false;
do{
?? if(Pass(maze,curpos))
?? {
??? //當(dāng)前位置可以通過(guò)，即是未曾走到過(guò)的通道塊留下足跡
?? FootPrint(maze,curpos);//做可以通過(guò)的標(biāo)識(shí)
//e.step=curstep;
?? e.seat=curpos;??
?? e.di=1;????????? //為棧頂元素賦值
24、
?
?? Push(S,e); //加入路徑
?? if(curpos.r==end.r && curpos.c==end.c) found=true;//如果到達(dá)終點(diǎn)返回true
???? else{
????????? curpos=NextPos(curpos,1);//下一位置是當(dāng)前位置的東鄰
??? ? }
?? }
? else?? //當(dāng)前位置不能通過(guò)
???? if(!StackEmpty(S)){
? ???????Pop(S,e);
???????? while(e.di==4 && !StackEmpty(S)){
??????????? Mar
25、kPrint(maze,e.seat);? //留下不能通過(guò)的標(biāo)記
??????????? Pop(S,e);
??????? ?}
??????? if(e.di<4){
????????? e.di++;?? //換下個(gè)方向
????????? Push(S,e);?????????????????????? //
????????? curpos=NextPos(e.seat,e.di);???? //進(jìn)行探索
??????? }
??? ?? }
}while(!StackEmpty(S)&&!found);
DestroyStack(S);
return fou
26、nd;
}
?
//將標(biāo)記路徑信息的迷宮（字符型方陣）輸出到終端(包括外墻)
void PrintMaze(MazeType &maze)
{
??? for(int i=0;i<=maze.r+2;i++){
????? for(int j=0;j<=maze.c+2;j++){
? printf("? %c",maze.arr[i][j]);//輸出迷宮????????
??? ? }
??? printf("\n");
??? }
}
?
//系統(tǒng)初始化
void Initialization()
{
system("cls
27、");
printf("???? welcome to the game!!!?????? ");
printf("\n************************************************");
printf("\n*創(chuàng)建迷宮--c 執(zhí)行迷宮--m?輸出迷宮--p? 退出--q*");
printf("\n************************************************");
printf("\n\n??? 操作:-");
}
?
//讀入操作命令符，顯示提示信息
28、
void ReadCommand(char &cmd)
{
?do{
?? if(cmd=='c')
?? {
??? printf("\n******************************************");
??? printf("\n*選擇操作 :執(zhí)行迷宮--m???? *");
??? printf("\n* 退出--:q?????????? *");
??? printf("\n******************************************");
??? printf("\n\n? 操作:-");
?? }
?? e
29、lse if(cmd=='m'){
??? printf("\n******************************************");
??? printf("\n*選擇操作 :輸出迷宮--p????????? *");
??? printf("\n*?退出--:q? ???? ?*");
??? printf("\n******************************************");
??? printf("\n\n 操作:-");
?? }
??? else if(cmd=='p'){
??? pri
30、ntf("\n******************************************");
??? printf("\n*選擇操作 :執(zhí)行迷宮--c?? ???????*");
??? printf("\n*????????? 退出--:q?????? *");
??? printf("\n******************************************");
??? printf("\n\n????????? 操作:-");
?? }
? cmd=getchar();
}while(!(cmd=='c'||cmd=='m'||cmd=='p'|
31、|cmd=='q'));
}
?
//解釋cmd--具體執(zhí)行
void Interpre(char cmd)
{
switch(cmd){
case 'c':{
?? int rnum, cnum, i=0,m=1,n=1;
?? char a2[MAXLEN][MAXLEN];
?? char input[1];
?? char data[1000];
?? printf("\n請(qǐng)輸入迷宮數(shù)據(jù)文件名！\n");
?? scanf("%s",input);
?? FILE *fp;
?? fp=fopen(input,"r");
?? if(!fp)
?? {
32、
??? printf("\n不能打開(kāi)文件\n");
??? break;
?? }
while(!feof(fp))
?? {
??? fscanf(fp,"%s",&data[i]);
??? if(i==0)
??? {
??????? rnum=(int)data[i]-(int)'0';
??? }
??? if(i==1)
??? {
??????? cnum=(int)data[i]-(int)'0';
??? }
??? if(i>=2)
??? {
?? ??if(n>cnum){m++;n=1;}
???? a2[m][n]=dat
33、a[i];
???? n++;
??? }
??? i++;
?? }
?? fclose(fp);
InitMaze(maze, a2, rnum, cnum);
?? printf("\n迷宮建立完成?。n");
?? break;
??? }
case 'm':{
?? printf("\n請(qǐng)輸入迷宮入口的坐標(biāo)，以空格為間隔:--");
?? scanf("%d %d",&start.r,&start.c);
?? printf("\n請(qǐng)輸入迷宮出口的坐標(biāo)，以空格為間隔:--");
?? scanf("%d %d",&end.r,&end.c);
?? M
34、azePath(maze, start, end);
?? break;
??? }
case 'p':{
?? if(found)
?? {
??? printf("\n求解迷宮的結(jié)果如下--\n");
??? PrintMaze(maze);
?? }
?? else printf("\n找不到路徑！\n");
??????? ?}
}
}
?
void main()
{
char cmd;
Initialization();
do{
?? ReadCommand(cmd);??? //讀入一個(gè)操作符命令
?? Interpre(cmd);????
35、?? //解釋執(zhí)行命令操作符
}while(cmd!='q');
}
四、 調(diào)試分析及測(cè)試
1、調(diào)試分析：
（1）本程序有一個(gè)核心算法，即求迷宮的路徑，在調(diào)試的時(shí)候，出現(xiàn)了兩個(gè)問(wèn)題：沒(méi)有想到要用‘@’記號(hào)，導(dǎo)致迷宮走不出來(lái)；沒(méi)有設(shè)置‘found’，不知何時(shí)跳出。
（2）原本棧的元素e中除了di—往下一坐標(biāo)位置的方向和seat—當(dāng)前的坐標(biāo)位置，還有一個(gè)step—當(dāng)前位置在路徑上的序號(hào)，后來(lái)發(fā)現(xiàn)step沒(méi)什么用，就刪掉了。
（3）函數(shù)ReadCommand中，cmd=get
36、char();的位置找不準(zhǔn)，最后是試出來(lái)的。
（4）調(diào)試的時(shí)候多次出現(xiàn)，沒(méi)有錯(cuò)誤，但是dos環(huán)境下就是執(zhí)行不起來(lái)，所以采用了一些輸出變量，判斷到底是哪里出了問(wèn)題。?
（5）本程序中三個(gè)主要的算法：InitMaze，MazePath和MarkPrint的時(shí)間復(fù)雜度均為O（m*n）, 本程序的空間復(fù)雜度也為O（m*n）（棧所占最大空間）
2、 使用說(shuō)明和運(yùn)行結(jié)果：
（1）首先以文件形式輸入迷宮數(shù)據(jù)，如圖三：
圖三
（2）進(jìn)入演示程序后，會(huì)出現(xiàn)以下界面如圖四：
?圖四
（3） 進(jìn)入“創(chuàng)建迷宮”的命令后，即提示輸入迷宮數(shù)據(jù)的文件名，結(jié)束符為“回車(chē)符”，該命令
37、執(zhí)行之后輸出“迷宮建立完成”，且輸出下面可執(zhí)行的操作。如圖五：
圖五
（4） 進(jìn)入“執(zhí)行迷宮”的命令后，即提示輸入迷宮入口，出口的坐標(biāo)，結(jié)束符為“回車(chē)符”，該命令執(zhí)行之后表示迷宮路徑已尋找完成或未找到路徑。請(qǐng)注意：若迷宮中存在路徑，執(zhí)行此命令后，迷宮狀態(tài)已經(jīng)改變，若要重復(fù)執(zhí)行此命令，需重新輸入迷宮數(shù)據(jù)。如圖六：
圖六
（5） 進(jìn)入“輸出迷宮”的命令后，即輸出迷宮求出路徑之后的狀態(tài)?！?’表示障礙，‘@’ 表示曾走過(guò)但不通，‘*’表示路徑。如圖七：
圖七
（6） 進(jìn)入“退出”的命令后，按任意鍵結(jié)束。如圖八：
圖八
3
38、、 缺點(diǎn)與改進(jìn)：
（1） 在定義函數(shù)Mazepath的時(shí)候，開(kāi)始的循環(huán)語(yǔ)句的結(jié)束條件不對(duì)，沒(méi)有出路時(shí)，導(dǎo)致一直出現(xiàn)了不正確的結(jié)果，最后沒(méi)有新位置入棧，則返回上一個(gè)位置，否則沒(méi)有路徑。
（2） 只是以文件形式輸入迷宮 ，如果迷宮數(shù)據(jù)量大時(shí)，要先建好文件還是很浪費(fèi)時(shí)間，如果以隨機(jī)產(chǎn)生函數(shù)自動(dòng)產(chǎn)生迷宮會(huì)更好 。
五、 個(gè)人工作及創(chuàng)新
為了準(zhǔn)備這次課程設(shè)計(jì)我查找了很多的資料，對(duì)于迷宮問(wèn)題的求解中迷宮的產(chǎn)生方式有很多的不同，有的是直接輸入迷宮，有的是用文件輸入，有的是隨機(jī)函數(shù)產(chǎn)生，我的課設(shè)是參考了用文件輸入的方法，這樣做相比直接輸入迷宮操作要更簡(jiǎn)單。當(dāng)然用隨機(jī)函數(shù)產(chǎn)生迷宮 比如用：
for
39、(i = 0; i < MAX_ROW; i++)
for(j = 0; j < MAX_COL; j++)
{
maze[i][j] = (int) (rand() % 2);
}
maze[1][0] = 1; /* start point */
maze[MAX_ROW - 1][MAX_COL - 2] = 1; /* end point */
}
這樣產(chǎn)生迷宮要更加的方便。結(jié)果也有不確定性，可能可以有通路也可能沒(méi)有。
對(duì)于迷宮的求解都是采用的“窮舉求解”的方法，用到了一些棧的知識(shí)。
把以前學(xué)過(guò)的棧的基本操作實(shí)際應(yīng)用了一番也使有了更加清楚
40、的認(rèn)識(shí)。
在求解迷宮的算法中，先設(shè)定當(dāng)前位置的初值為入口位置，然后
Do{
若當(dāng)前位置可通，
則｛將當(dāng)前位置插入棧頂；
若該位置是出口位置，則結(jié)束；
否則切換當(dāng)前位置的東鄰方塊為新的當(dāng)前位置；
｝
否則｛
若棧不為空且棧頂位置尚有其它方向未被探索，
則設(shè)定新的當(dāng)前位置為延順時(shí)針?lè)较蛐D(zhuǎn)找到的棧頂位置的下
一相鄰塊；
若棧不空但棧頂位置四周均不通，
則｛刪去棧頂位置；
若棧不為空，則重新測(cè)試新的棧頂位置，
直至找到一
41、個(gè)可通的相鄰塊或出棧至?？?；｝
｝
}
求解迷宮的算法大概就是這么個(gè)思路。
六、 小結(jié)
要能很好的掌握編程，僅僅通過(guò)幾個(gè)簡(jiǎn)單的程序的編寫(xiě)是無(wú)法達(dá)成的，更需要的是大量的積累和深入研究才可能。在程序的編寫(xiě)中也不能一味的向已有的程序進(jìn)行模仿，而要自己去探索，去尋找最好的解決方法，只有帶著問(wèn)題去反復(fù)實(shí)踐，才能更熟練的掌握和運(yùn)用，當(dāng)然，對(duì)現(xiàn)有的程序也要多去接觸，因?yàn)橛行┏绦蚴俏覀冊(cè)诙虝r(shí)間內(nèi)無(wú)法想出來(lái)的，我們也應(yīng)該去參考別人的作品，這樣可以節(jié)約時(shí)間獲得更多的知識(shí)。最重要的是持之以恒，要經(jīng)常性的復(fù)習(xí)原來(lái)接觸到的程序，這樣才能保證我們有足夠的經(jīng)驗(yàn)去面對(duì)程序問(wèn)題。
參考文獻(xiàn)
[1]. 嚴(yán)蔚敏，吳偉民數(shù)據(jù)結(jié)構(gòu)（C語(yǔ)言版）.清華大學(xué)出版社.2007
[2]. 嚴(yán)蔚敏，數(shù)據(jù)結(jié)構(gòu)題集（C語(yǔ)言版）.清華大學(xué)出版社.2007
[3]. 譚浩強(qiáng) ，C程序設(shè)計(jì)（第四版）.清華大學(xué)出版社.2007
19
C++ 數(shù)據(jù)結(jié)構(gòu) 迷宮問(wèn)題
