課程設(shè)計(論文)任務(wù)書軟件 學(xué)院軟件工程+電子商務(wù)2009專業(yè)2班一、 課程設(shè)計(論文)題目迷宮問題二、課程設(shè)計(論文)工作自2010 年12月27日起至2011年1月_2_日止三、課程設(shè)計(論文)地點(diǎn):創(chuàng)新大樓實(shí)訓(xùn)中心四、課程設(shè)計(論文)內(nèi)容要求：1本課程設(shè)計的目的(1)鞏固和加深對數(shù)據(jù)結(jié)構(gòu)基本知識的理解，提高綜合運(yùn)用課程知識的能力。(2) 使學(xué)生掌握軟件設(shè)計的基本內(nèi)容和設(shè)計方法，并培養(yǎng)學(xué)生進(jìn)行規(guī)范化軟 件設(shè)計的能力。(3) 使學(xué)生掌握使用各種計算機(jī)資料和有關(guān)參考資料，提高學(xué)生進(jìn)行程序設(shè) 計的基本能力。2 課程設(shè)計的任務(wù)及要求1) 基本要求:(1) 對系統(tǒng)進(jìn)行功能模塊分析、控制模塊分析；(2)系統(tǒng)設(shè)計要能完成題目所要求的功能;(3) 編程簡練，可用，盡可能的使系統(tǒng)的功能更加完善和全面；(4) 說明書、流程圖要清楚；(5) 提高學(xué)生的論文寫作能力； (6)特別要求自己獨(dú)立完成;2) 創(chuàng)新要求：在基本要求達(dá)到后，可進(jìn)行創(chuàng)新設(shè)計，如改善算法性能、友好的人機(jī)界面。3) 課程設(shè)計論文編寫要求(1) 要按照書稿的規(guī)格打印與寫課程設(shè)計論文(2) 論文包括目錄、正文、小結(jié)、參考文獻(xiàn)、附錄等"""(3)課程設(shè)計論文裝訂按學(xué)校的統(tǒng)一要求完成4）課程設(shè)計進(jìn)度安排內(nèi)容天數(shù)地點(diǎn)構(gòu)思及收集資料1圖書館編碼與調(diào)試3實(shí)驗室撰寫論文1圖書館、實(shí)驗室學(xué)生簽名：20011年1 月3日課程設(shè)計（論文）評審意見（1）基本算法（20 分）：優(yōu)（）、良（）、中（）、一般（）、差（）；（2）設(shè)計分析（20 分）：優(yōu)（）、良（）、中（）、一般（）、差（）；（3）調(diào)試分析（20 分）：優(yōu)（）、良（）、中（）、一般（）、差（）；（4）論文內(nèi)容（20 分）：優(yōu)（）、良（）、中（）、一般（）、差（）；（5）答辯分析（20 分）：優(yōu)（）、良（）、中（）、一般（）、差（）；（6）格式規(guī)范性及考勤是否降等級：是（）、否（）目錄一、需求分析1二、概要設(shè)計2三、詳細(xì)設(shè)計5四、調(diào)試分析及測試15五、個人工作及創(chuàng)新18六、小結(jié)19參考文獻(xiàn)20、需求分析1. 選題理由本次課設(shè)我選擇了迷宮問題，迷宮求解是數(shù)據(jù)結(jié)構(gòu)課程的一個經(jīng)典問題, 迷宮問題要求尋找一條從入口到出口的路徑。通常用的是“窮舉求解” 的方法。為了保證在任何位置上都能原路退回，顯然需要用一個后進(jìn)先出的 結(jié)構(gòu)來保存從入口到當(dāng)前位置的路徑。因此，在求解迷宮通路的算法中要應(yīng) 用“棧”的思想。對于棧的內(nèi)容在整個學(xué)期的學(xué)習(xí)中我也有了一定的了解， 所以選擇了迷宮這一經(jīng)典問題作為本次課設(shè)的內(nèi)容。2. 基本原理分析迷宮問題通常是用“窮舉求解”方法解決，即從入口出發(fā)，順著某一個 方向進(jìn)行探索，若能走通，則繼續(xù)往前走；否則沿著原路退回，換一個方向 繼續(xù)探索，直至出口位置，求得一條通路。假如所有可能的通路都探索到而 未能到達(dá)出口，則所設(shè)定的迷宮沒有通路。棧是一個后進(jìn)先出的結(jié)構(gòu)，可以 用來保存從入口到當(dāng)前位置的路徑。以二維數(shù)組存儲迷宮數(shù)據(jù)，通常設(shè)定入口點(diǎn)的下標(biāo)為（1，1），出口點(diǎn)的 下標(biāo)為（n,n）。為處理方便起見，在迷宮的四周加一圈障礙。對于迷宮任何 一個位置，均約定東、南、西、北四個方向可通。3. 功能要求（1）以一個二維數(shù)組Mazem+2n+2表示迷宮，其中：MazeOj和 Mazem+1j（0<=j<=n+1）及 MazeiO和 Mazein+1 （0<=i<=m+1）為做 外層的一圈障礙。數(shù)組中以0表示通路，1表示障礙，限定迷宮的大小為： m,n<=10。（2）用戶需用文件的形式輸入迷宮的數(shù)據(jù)：文件中第一行的數(shù)據(jù)為迷宮 的行數(shù)m和列數(shù)n；從第2行至第m+1行（每行n個數(shù)）為迷宮值，用0, 1 輸入，同行中的兩個數(shù)字之間用空白字符相隔。（3）迷宮的入口位置和出口位置可由用戶隨時設(shè)定。（4）若設(shè)定的迷宮存在通路，則以長方陣形式將迷宮及其通路輸出到標(biāo) 準(zhǔn)輸出文件上，其中字符“# ”表示障礙，“* ”表示路徑，“ ”表示曾途經(jīng)該 位置但不能到達(dá)出口，其余位置用空格符表示。若設(shè)定迷宮不存在通路則報 告相應(yīng)信息（5）本程序只求出一條成功的通路。（6）程序執(zhí)行的命令為：1，創(chuàng)建迷宮；2,求解迷宮；3,輸出迷宮的解。二、概要設(shè)計1、數(shù)據(jù)結(jié)構(gòu)及其抽象數(shù)據(jù)類型的定義。(1)棧的抽象數(shù)據(jù)類型ADT Stack 數(shù)據(jù)對象：D=ai| aiUCharSet,i=1,2n,n>=0 數(shù)據(jù)關(guān)系：R1=<ai-1, ai >| aiT, ai WD,i=2, n 基本操作：InitStack(&S)操作結(jié)果：構(gòu)造一個空棧SoDestroyStack(&S) 初始條件：棧S已存在。 操作結(jié)果：銷毀棧S。ClearStack(&S) 初始條件：棧S已存在。操作結(jié)果：將S清為空棧。StackLength(S) 初始條件：棧S已存在。 操作結(jié)果：返回棧S的長度。StackEmpty(S)初始條件：棧S已存在。操作結(jié)果：若S為空棧，則返回TRUE,否則返回FALSE。GetTop(S, &e) 初始條件：棧S已存在。 操作結(jié)果：若棧S不空，則以e返回棧頂元素。Push(&S, e) 初始條件：棧S已存在。 操作結(jié)果：在棧S的棧頂插入新的棧頂元素e。Pop(&S, &e) 初始條件：棧S已存在。 操作結(jié)果：刪除S的棧頂元素，并以e返回其值。StackTraverse (S, visit () 初始條件：棧S已存在。操作結(jié)果：從棧底到棧頂依次對S中的每個元素調(diào)用函數(shù)visit ()。 ADT Stack(2)迷宮的抽象數(shù)據(jù)類型ADT maze數(shù)據(jù)對象：D=ai,j| ai,j e ' *',0二i二m+1,0二j二n+l,m,n<=10數(shù)據(jù)關(guān)系：R=ROW,COL基本操作：InitM aze( &M ,a,row,col)初始條件：二維數(shù)組arow+2col+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 maze2、整體框架 本程序包含三個模塊(1) 棧模塊一一實(shí)現(xiàn)棧抽象數(shù)據(jù)類型(2) 迷宮模塊一一實(shí)現(xiàn)迷宮抽象數(shù)據(jù)類型(3) 主程序模塊： void mian()初始化； Do 接受命令； 處理命令； while(命令!= “退出”)； 各模塊之間的調(diào)用關(guān)系如圖一:主程序模塊挫宮權(quán)塊棧模塊圖一：調(diào)用關(guān)系圖主稈序InitMaze MazePath PrintMaze函數(shù)的調(diào)用關(guān)系圖反映了程序的層次結(jié)構(gòu)如圖二:InitializationRcadCcmma ti dlnitStack Push Pop StnckEmpty StackTraverseFootPrint MarkPrint Pass NextPos Same圖二-:函數(shù)的調(diào)用關(guān)系圖三、詳細(xì)設(shè)計源程序：#include <stdio.h>#include <stdlib.h>#include <st ring.h>#define MAXLEN 10/迷宮包括外墻最大行列數(shù)目#define TRUE 1#define FALSE 0#define OK 1#define ERROR 0typedef int Status;/坐標(biāo)位置類型typedef structint r,c; PosType;/迷宮中r行c列的位置/迷宮類型typedef struct int r;int c;char arrMAXLENMAXLEN;/可取''，' MazeType;typedef struct/int st ep; /當(dāng)前位置在路徑上的“序號”PosType sea t; /當(dāng)前的坐標(biāo)位置 int di; /往下一坐標(biāo)位置的方向 SElemType;/結(jié)點(diǎn)類型typedef struct NodeTypeSElemType data;NodeType *next;NodeType ,*LinkType;/棧類型typedef struet LinkType top; int staeksize;SqStack;PosType start;PosType end;MazeType maze;bool found;/創(chuàng)建棧Status InitStack(SqStack &S)S.to p=(LinkType)malloc(sizeof(NodeType);S.to p->nex t二N ULL;S.s tacksize=O; return OK;/進(jìn)棧Status Push(SqS tack & S,SElemType &e)LinkType p; p=(NodeType*)malloc(sizeof(NodeType); p->data二e;p->nex t二S.top;S.to p=p;S.s tacksize+; return OK;/判斷是否為?？誗tatus StackEmpty(SqStack S)if(S .top->next二二NULL) return OK; return ERROR;/出棧Status Pop(SqStack &S,SElemType &e)LinkType p;if(StackEmpty(S) return ERROR; p=S .top;e=p->data;S.to p=S .to p->nex t;S.stacksize-; free(p);return OK;/銷毀棧Status DestroyStack(SqStack &S)LinkType p;while(S. top!二NULL)p=S .top;S.to p=S .to p->nex t; free(p);/一個一個刪除if(S.top二二NULL) return OK; else return ERROR;/曾走過但不是通路標(biāo)記并返回OKStatus MarkPrint(MazeType &maze,PosType curpos)maze.arrcurpos.rcurpos.c=''/" "表示曾走過但不通 return OK; /曾走過而且是通路標(biāo)記并返回OKStatus FootPrint(MazeType &maze,PosType curpos) maze.arrcurpos.rcurpos.c二'*' ;/"*"表示可通 return OK;/選擇下一步的方向PosType NextPos(PosType &curpos,int i)PosType cpos;epos二curpos;分別表示東，南,西,北方向case 1 : cpos.c+=1;break;case 2 : cpos.r+=1; break;case 3 : cpos.c=l; break;case 4 : cpos.r=1; break;return cpos;/判斷當(dāng)前位置是否可通Status Pass(MazeType &maze, PosType curpos) if(maze.arrcurpos.rcurpos.c二二'')return TRUE;else return FALSE;/創(chuàng)建迷宮/按照用戶輸入的二維數(shù)組(0或1),設(shè)置迷宮maze的初值，包括加上 邊緣一圈的值void InitMaze(MazeType &maze, char aMAXLENMAXLEN, int row, int col)maze.r二row;maze.c二col;for(int i=0;i二col+l;i+) a0i='1' arow+1i='1' for(i=0;i<=row+1;i+)ai0='1' aicol+1='1' for(i=0;i<=maze.r+2;i+) for(i nt j=0;j<maze.c+2;j+)if(aij='1') maze.arrij二'#' else maze.arrij二'' /求迷宮路徑的偽碼算法：Status MazePath(MazeType &maze,PosType start ,PosType end) /求解迷宮maze中，從入口 start到出口 end的一條路徑，若存在，返 回TRUE,否則返回FALSEPosType curpos;SqStack S;SElemType e;InitSt ack(S);curpos二s tart; /設(shè)定“當(dāng)前位置"為“入口位置"/curs tep=l; /探索第一步found二false;doif(Pass(maze,curpos)/當(dāng)前位置可以通過，即是未曾走到過的通道塊留下足跡 Foo tPrin t( maze,curpos);/做可以通過的標(biāo)識/e.s tep二curs tep;e.sea t二 curpos;e.di=l;/為棧頂元素賦值Push(S,e); /加入路徑if(curpos.r二二end.r && curpos.c二二end.c) found 二t rue;/如果到達(dá) 終點(diǎn)返回trueelsecurpos二Nex tPos(curpos,l);/下一位置是當(dāng)前位置的東鄰 else/當(dāng)前位置不能通過if(!S tackEmp ty (S)Pop(S,e);while(e.di=4 && !St ackEmp ty (S)MarkPrin t(maze,e.sea t);/留下不能通過的標(biāo)記Pop(S,e);if(e.di<4)e.di+;/換下個方向Push(S,e);/curpos二Nex tPos(e.sea t,e.di);/進(jìn)行探索 while(!S tackEmp ty(S)&&!fo und);Des troyS tack(S);return found;/將標(biāo)記路徑信息的迷宮(字符型方陣)輸出到終端(包括外墻)void PrintMaze(MazeType &maze)for(i nt i=0;i二maze.r+2;i+)for(i nt j=O;j二maze.c+2;j+)prin tf(“c",maze.arrij);/輸出迷宮printf ("n");/系統(tǒng)初始化void Initi aliza tion()sys tem("cls");printf(“welcome to the game!");printf ("n*") printf("n*創(chuàng)建迷宮一c執(zhí)行迷宮一m輸出迷宮一p退出一q*"); printf ("n*") pri ntf ("nn操作:-")；/讀入操作命令符，顯示提示信息void ReadCommand(char &cmd)doif(cmd='c')printf ("n*") prin tf("n *選擇操作：執(zhí)行迷宮一m*");printf("n* 退出一:q*)；printf (n*) pri ntf (nn 操作:-)；else if(cmd='m')printf (n*)prin tf(n *選擇操作：輸出迷宮一p*");printf("n* 退出一:q*)；printf (n*) printf (nn 操作:-)；else if(cmd='p')printf (n*)； prin tf(n *選擇操作：執(zhí)行迷宮一c*");printf("n *退出一:q*)；printf (n*) pri ntf (nn操作:-)；cmd=ge tchar();while(!(cmd二二，c，|cmd二二,m，|cmd二二,p，|cmd二二，q，);/解釋cmd-具體執(zhí)行void Interpre(char cmd)swit ch(cmd)case c :int rnum, cnum, i=0,m=l,n=l;char a2MAXLENMAXLEN;char inputl;char data1000;printf(n請輸入迷宮數(shù)據(jù)文件名！ n)； scanf(s，inp ut);FILE *fp; fp=fopen(input, r)； if(!fp)printf(n不能打開文件n"); break;while(!feof(fp) fscanf(fp,s，&dat ai); if(i=0)rnum=( int )da tai-(int)，0，;if(i=1)cnum=( int )da tai (int)，0，;if(i>=2)if(n>cnum)m+;n=l;a2mn=da tai;n+;i+;fclose(fp);InitM aze(maze, a2, rnum, cnum);printf("n迷宮建立完成！ n");break;case m :printf(n請輸入迷宮入口的坐標(biāo)，以空格為間隔:一); scanf("%d %d，&start.r,&start .c);printf(n請輸入迷宮出口的坐標(biāo)，以空格為間隔:一); scanf("%d %d"，& end.r，& end.c);MazePa th(maze, start, end);break;case p :if(found)printf(n求解迷宮的結(jié)果如下-n");Pri ntM aze(maze);else printf(n 找不到路徑！ n");void main()char cmd;Initi aliza tion();doReadCommand(cmd);Int erpre(cmd); while(cmd!二'q'); /讀入一個操作符命令/解釋執(zhí)行命令操作符調(diào)試分析及測試1、調(diào)試分析：(1) 本程序有一個核心算法，即求迷宮的路徑，在調(diào)試的時候，出現(xiàn)了 兩個問題：沒有想到要用記號，導(dǎo)致迷宮走不出來；沒有設(shè)置'found',不知何時跳出。(2) 原本棧的元素e中除了 di往下一坐標(biāo)位置的方向和seat當(dāng)前 的坐標(biāo)位置，還有一個step當(dāng)前位置在路徑上的序號，后來發(fā)現(xiàn)step沒什 么用，就刪掉了。(3) 函數(shù)ReadCommand中，cmd=getchar();的位置找不準(zhǔn)，最后是試出 來的。(4) 調(diào)試的時候多次出現(xiàn)，沒有錯誤，但是dos環(huán)境下就是執(zhí)行不起來, 所以采用了一些輸出變量，判斷到底是哪里出了問題。(5) 本程序中三個主要的算法：InitMaze, MazePath和MarkPrint的時 間復(fù)雜度均為O (m*n),本程序的空間復(fù)雜度也為O (m*n)(棧所占最大空 間)(1)2、使用說明和運(yùn)行結(jié)果:亠11】11宀11】亠11】111± 1ILO ,u. iI 1±首先以文件形式輸入迷宮數(shù)據(jù)，如圖三:rll.txt -記事本1 =回 ld文徉(E 鋸® 梧式回 w(v)幫助(to圖三(2) 進(jìn)入演示程序后，會出現(xiàn)以下界面如圖四: g'Users'toshiba'Desktop'已經(jīng)完成的作業(yè)遨曇制切設(shè)Debtigl.exe' = I 回圖四(3) 進(jìn)入“創(chuàng)建迷宮”的命令后，即提示輸入迷宮數(shù)據(jù)的文件名，結(jié)束 符為“回車符"，該命令執(zhí)行之后輸出“迷宮建立完成"，且輸出下面可執(zhí) 行的操作。如圖五：圖五(4) 進(jìn)入“執(zhí)行迷宮”的命令后，即提示輸入迷宮入口，出口的坐標(biāo)， 結(jié)束符為“回車符”，該命令執(zhí)行之后表示迷宮路徑已尋找完成或未找到路 徑。請注意：若迷宮中存在路徑，執(zhí)行此命令后，迷宮狀態(tài)已經(jīng)改變，若要 重復(fù)執(zhí)行此命令，需重新輸入迷宮數(shù)據(jù)。如圖六：圖六(5) 進(jìn)入“輸出迷宮”的命令后，即輸出迷宮求出路徑之后的狀態(tài)。#' 表示障礙，表示曾走過但不通，*'表示路徑。如圖七：圖七(6) 進(jìn)入“退出”的命令后，按任意鍵結(jié)束。如圖八:圖八3、缺點(diǎn)與改進(jìn)：(1) 在定義函數(shù)Mazepa th的時候，開始的循環(huán)語句的結(jié)束條件不對， 沒有出路時，導(dǎo)致一直出現(xiàn)了不正確的結(jié)果，最后沒有新位置入棧，則返回 上一個位置，否則沒有路徑。(2) 只是以文件形式輸入迷宮，如果迷宮數(shù)據(jù)量大時，要先建好文件 還是很浪費(fèi)時間，如果以隨機(jī)產(chǎn)生函數(shù)自動產(chǎn)生迷宮會更好。五、個人工作及創(chuàng)新為了準(zhǔn)備這次課程設(shè)計我查找了很多的資料，對于迷宮問題的求解中迷 宮的產(chǎn)生方式有很多的不同，有的是直接輸入迷宮，有的是用文件輸入，有 的是隨機(jī)函數(shù)產(chǎn)生，我的課設(shè)是參考了用文件輸入的方法，這樣做相比直接 輸入迷宮操作要更簡單。當(dāng)然用隨機(jī)函數(shù)產(chǎn)生迷宮比如用：for (i = 0; i < MAX_R0W; i+)for(j = 0; j < MAX_COL; j+) mazeij = (int) (rand() % 2);mazel0 = 1; /* start poi nt */mazeMAX_ROW - 1MAX_COL - 2 = 1; /* end point */ 這樣產(chǎn)生迷宮要更加的方便。結(jié)果也有不確定性，可能可以有通路也可能沒 有。對于迷宮的求解都是采用的“窮舉求解”的方法，用到了一些棧的知識。 把以前學(xué)過的棧的基本操作實(shí)際應(yīng)用了一番也使有了更加清楚的認(rèn)識。在求解迷宮的算法中，先設(shè)定當(dāng)前位置的初值為入口位置，然后Do若當(dāng)前位置可通，則將當(dāng)前位置插入棧頂；若該位置是出口位置，則結(jié)束；否則切換當(dāng)前位置的東鄰方塊為新的當(dāng)前位置；否則若棧不為空且棧頂位置尚有其它方向未被探索，則設(shè)定新的當(dāng)前位置為延順時針方向旋轉(zhuǎn)找到的棧頂位置的下 一相鄰塊；若棧不空但棧頂位置四周均不通，則刪去棧頂位置；若棧不為空，則重新測試新的棧頂位置，直至找到一個可通的相鄰塊或出棧至?？眨磺蠼饷詫m的算法大概就是這么個思路。六、小結(jié)要能很好的掌握編程，僅僅通過幾個簡單的程序的編寫是無法達(dá)成的， 更需要的是大量的積累和深入研究才可能。在程序的編寫中也不能一味的向 已有的程序進(jìn)行模仿，而要自己去探索，去尋找最好的解決方法，只有帶著 問題去反復(fù)實(shí)踐，才能更熟練的掌握和運(yùn)用，當(dāng)然，對現(xiàn)有的程序也要多去 接觸，因為有些程序是我們在短時間內(nèi)無法想出來的，我們也應(yīng)該去參考別 人的作品，這樣可以節(jié)約時間獲得更多的知識。最重要的是持之以恒，要經(jīng) 常性的復(fù)習(xí)原來接觸到的程序，這樣才能保證我們有足夠的經(jīng)驗去面對程序 問題。參考文獻(xiàn)1 .嚴(yán)蔚敏，吳偉民數(shù)據(jù)結(jié)構(gòu)（C語言版）清華大學(xué)出版社.20072 .嚴(yán)蔚敏，數(shù)據(jù)結(jié)構(gòu)題集（C語言版）清華大學(xué)出版社.20073 .譚浩強(qiáng)，C程序設(shè)計（第四版）清華大學(xué)出版社.2007