C語(yǔ)言與數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)報(bào)告

1、C語(yǔ)言與數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)報(bào)告學(xué) 號(hào) 2011013759 姓 名 俞杰 課程設(shè)計(jì)題目 迷宮求解 小組成員 俞杰 安飛 洪飛 2012 年 12 月目 錄1 需求分析 1.1 功能與數(shù)據(jù)需求 1.1.1 題目要求的功能 1.1.2 擴(kuò)展功能 1.2 界面需求 1.3 開(kāi)發(fā)環(huán)境與運(yùn)行需求 2 概要設(shè)計(jì) 2.1主要數(shù)據(jù)結(jié)構(gòu)2.2程序總體結(jié)構(gòu)2.3各模塊函數(shù)說(shuō)明3 詳細(xì)設(shè)計(jì)3.1算法分析與設(shè)計(jì)3.2主要程序段設(shè)計(jì)4 測(cè)試5 使用說(shuō)明5.1應(yīng)用程序功能的詳細(xì)說(shuō)明5.2應(yīng)用程序運(yùn)行環(huán)境要求5.5輸入數(shù)據(jù)類(lèi)型、格式和內(nèi)容限制6 總結(jié)提高6.1課程設(shè)計(jì)總結(jié)6.2開(kāi)發(fā)中遇到的問(wèn)題和解決方法6.3 對(duì)自己完成課設(shè)

2、完成情況的評(píng)價(jià)6.4C語(yǔ)言與數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)課程的意見(jiàn)與建議附錄：程序源代碼1 需求分析 1.1 功能與數(shù)據(jù)需求 1.1.1 題目要求的功能 以一個(gè)mn的長(zhǎng)方形表示迷宮，0和1分別表示迷宮中的通路和障礙。設(shè)計(jì)一個(gè)程序，對(duì)任意設(shè)定的迷宮，求出一條從入口到出口的通路，或得出沒(méi)有通路的結(jié)論。 測(cè)試數(shù)據(jù)：迷宮的測(cè)試數(shù)據(jù)如下：左上角（1,1）為入口，右下角（9,8）為出口。 001000100010001000001101011100100001000001000101011110011100010111000000 1 2 3 4 5 6 7 8 1.1.2 擴(kuò)展功能 （1）編寫(xiě)遞歸形式的算法，求得迷

3、宮中所有可能的通路； （2）以方陣形式輸出迷宮及其通路。1.2 界面需求 輸入行數(shù)和列數(shù) 輸入每一行中的通路（0，0）和障礙（1,1）. 輸入入口坐標(biāo)（1,1）和出口坐標(biāo)（m,n）.1.3 開(kāi)發(fā)環(huán)境與運(yùn)行需求 開(kāi)發(fā)環(huán)境 Microsoft Visual C+ 6.0 最低運(yùn)行需求 windows xp ;32位系統(tǒng)2 概要設(shè)計(jì) 2.1主要數(shù)據(jù)結(jié)構(gòu)： typedef struct /*用于存放迷宮的位置和該點(diǎn)信息*/ int x,y,d;Datatype;typedef struct /*該棧用于存儲(chǔ)走過(guò)的結(jié)點(diǎn)*/ Datatype dataMAXSIZE; int top;Sqstack,*P

4、Sqstack;typedef struct /*用于存放當(dāng)前結(jié)點(diǎn)可走的四個(gè)方向*/ int x,y;item;2.2程序總體結(jié)構(gòu) 輸入起始位置，終點(diǎn)位置 判斷首節(jié)點(diǎn)是否為通路判斷路徑能否走通對(duì)坐標(biāo)標(biāo)記 是否到達(dá)迷宮出口處南邊是否存在通路東邊是否存在通路北邊是否存在通路存儲(chǔ)路徑，將路徑入棧 有解迷宮 無(wú)解迷宮 YNYNY輸出迷宮 選擇路徑 西邊是否存在通路 打印所走的路徑2.3各模塊函數(shù)說(shuō)明 PSqstack Init_Sqstack() /*初始化空棧*/int Push_Sqstack(PSqstack s,Datatype x) /*入棧*/int Pop_Sqstack(PSqstac

5、k s,Datatype *x) /*出棧*/void Destroy_Sqstack(PSqstack *s) /*銷(xiāo)毀棧*/int Mazepath(int mazen+2,int x0,int y0) /*求迷宮路徑函數(shù)，入口參數(shù)： 指向迷宮數(shù)組的指針，開(kāi)始點(diǎn)（x0,y0）*/Pop_ Sqstack(s,&temp);Push_Sqstack(t,temp); /*棧t是棧s的逆，因?yàn)閟保存 的途徑是反的，加t 使輸出的途徑變?yōu)檎?/3 詳細(xì)設(shè)計(jì)3.1算法分析與設(shè)計(jì) 思路：計(jì)算機(jī)解迷宮通常用的是“窮舉求解”方法，即從入口出發(fā)，順著某一個(gè)方向進(jìn)行探索，若能走通，則繼續(xù)往前進(jìn)；否則沿著原路

6、退回，換一個(gè)方向繼續(xù)探索，直至出口位置，求得一條通路。假如所有可能的通路都探索到而未能到達(dá)出口，則所設(shè)定的迷宮沒(méi)有通路。實(shí)現(xiàn)：假設(shè)“當(dāng)前位置”指的是“在收索過(guò)程中某一時(shí)刻所在圖中某個(gè)方 塊位置”，則求迷宮中的一條路徑的算法的基本思想是：若當(dāng)前位置“可通”， 則納入“當(dāng)前路徑”，并繼續(xù)朝“下一位置”探索，即切換“下一位置”為“當(dāng)前位置”，如此重復(fù)直至到達(dá)出口；若當(dāng)前位置“不可通”則應(yīng)該順著“來(lái)向”退回到“前一通道塊”，然后朝著除“來(lái)向”之外的其他方向繼續(xù)探索；若該通道塊的四周4個(gè)方塊均“不可通”，則應(yīng)從“當(dāng)前路徑”上刪除該通道塊。所謂“下一位置”指的是“當(dāng)前位置”四周4個(gè)方向（東南西北）上相鄰的

7、方塊。假設(shè)以棧S記錄“當(dāng)前路徑”，則棧頂中存放的是“從當(dāng)前路徑上最后一個(gè)通道塊”。由此，“納入路徑”的操作即為“當(dāng)前位置入?！?；“從當(dāng)前路徑上刪除前一通道塊”的操作即為“入?！?。3.2主要程序段設(shè)計(jì)void main() int i,j; int mazem+2n+2; printf(請(qǐng)輸入迷宮矩陣:9*8n); for(i=0,j=0;im+2;i+) /*將迷宮四周賦值為1，即不可走*/ mazeij=1; for(i=0,j=0;jn+2;j+) mazeij=1; for(i=0,j=n+1;im+2;i+) mazeij=1; for(i=m+1,j=0;jn+2;j+) maze

8、ij=1; for(i=1;im+1;i+) /*給迷宮賦值*/ for(j=1;jn+1;j+) scanf(%d,&mazeij); for(i=0;im+2;i+) /*打印迷宮*/ for(j=0;jtop!=-1)Pop_Seqstack(s,&temp);x=temp.x;y=temp.y;d=0; /*將方向重新定位為右方，即move0*/while(dtop!=-1)Pop_Seqstack(s,&temp);Push_Seqstack(t,temp); /*棧t是棧s的逆，因?yàn)閟保存的途徑是反的，加t使輸出的途徑變?yōu)檎?/Destroy_Seqstack(&s); /*銷(xiāo)毀棧

9、*/while(t-top!=-1) /*打印走過(guò)的途徑*/Pop_Seqstack(t,&temp); printf(,temp.x,temp.y,temp.d);printf(,m,n);Destroy_Seqstack(&t); /*銷(xiāo)毀棧*/return OK;elsed=0; /*將方向定位為右方*/elsed+; /*嘗試其 他方向是否可走*/printf(該迷宮無(wú)法走出n);Destroy_Seqstack(&s);return ERROR;Mazepath函數(shù)if（迷宮入口或迷宮是否有通路）Printf（“輸入迷宮數(shù)據(jù)錯(cuò)誤“）；else對(duì)move定義為向四個(gè)方向探索的數(shù)組初始化

10、棧s，t；迷宮入口點(diǎn)入棧While（判斷s是否為空） 入口參數(shù)：指向迷宮數(shù)組的指針，開(kāi)始點(diǎn)（x0,y0）while（d4）初始位置If（該路口走）將可走的路入棧將走過(guò)的點(diǎn)標(biāo)記為-1If（ 判斷走到終點(diǎn)）棧t是棧s的逆，因?yàn)閟保存的途徑是反的加t使輸出的途徑變?yōu)檎?；銷(xiāo)毀棧s；打印走過(guò)的途徑；銷(xiāo)毀棧t；Else將方向定位為右方*/Else嘗試其他方向是否可走*/4 測(cè)試 迷宮路徑測(cè)試迷宮方向測(cè)試無(wú)法走出迷宮的測(cè)試完整的迷宮測(cè)試5 使用說(shuō)明5.1應(yīng)用程序功能的詳細(xì)說(shuō)明 使用者自己設(shè)計(jì)一個(gè)（9，8）迷宮，迷宮為9行8列的矩陣，1表示該 位置為路障，0表示該位置為通路， 每一行中兩位置之間用空格隔開(kāi)。進(jìn)

11、 入下一行設(shè)計(jì)按enter鍵。設(shè)計(jì)特別要求，矩陣位置（1,1）,（9,8）為0， 否則程序不能運(yùn)行。 按enter鍵運(yùn)行程.5.2應(yīng)用程序運(yùn)行環(huán)境要求 Microsoft Visual C+6.05.5輸入數(shù)據(jù)類(lèi)型、格式和內(nèi)容限制 輸入的數(shù)據(jù)都是整型（int），輸入迷宮的數(shù)據(jù)間要用空格或回車(chē)隔開(kāi)6 總結(jié)提高6.1課程設(shè)計(jì)總結(jié)這次的實(shí)驗(yàn)，我們發(fā)現(xiàn)書(shū)本上理論性的東西與在實(shí)際運(yùn)用中的還是有一定的出入的，所以有些問(wèn)題不但要深入地理解，而且要不斷地更正以前的錯(cuò)誤思維，才能完成實(shí)驗(yàn)設(shè)計(jì)。通過(guò)這次的課程設(shè)計(jì)我們也更加理解和掌握了棧和數(shù)組的正確使用方法，更為重要的是了解了通過(guò)數(shù)組和結(jié)構(gòu)體結(jié)合來(lái)生成的數(shù)據(jù)結(jié)構(gòu)的

12、特點(diǎn)及應(yīng)用，這是在這之前未接觸過(guò)的。總之，通過(guò)這次的課程設(shè)計(jì)，讓我對(duì)計(jì)算機(jī)編程在實(shí)際問(wèn)題中的應(yīng)用有了極大的了解，同時(shí)也讓我知道了棧的強(qiáng)大，很多問(wèn)題都可以用棧來(lái)解決。6.2開(kāi)發(fā)中遇到的問(wèn)題和解決方法1.（安飛）問(wèn)題：對(duì)循環(huán)結(jié)構(gòu)與數(shù)組結(jié)合對(duì)迷宮外墻的的設(shè)計(jì)不知道該怎么應(yīng)用。 解決方法：上網(wǎng)查找?guī)讉€(gè)迷宮的設(shè)計(jì)，以后結(jié)合自己的理解，小組討論后，建了一個(gè)二維數(shù)組，定義2個(gè)變量，控制變量法，讓迷宮四周為1。2. (洪飛) 問(wèn)題：對(duì)于點(diǎn)向四個(gè)方向的走向不清楚，不知道如何判斷該路是否可走，最后如何判斷到達(dá)終點(diǎn)以及出棧。解決方法：首先將迷宮口的點(diǎn)入棧，然后將點(diǎn)的坐標(biāo)賦值給x,y，將方向重新定位為右方。用whil

13、e循環(huán)來(lái)判斷四個(gè)方向是否可走，用if語(yǔ)句來(lái)來(lái)判斷該路是否可走，最后將走過(guò)的路徑入棧，將走過(guò)的點(diǎn)標(biāo)記為-1，同樣用if語(yǔ)句來(lái)判斷到達(dá)終點(diǎn)，最后出棧。3.（俞杰）問(wèn)題：剛開(kāi)始的時(shí)候我們只定義了一個(gè)棧s=Init_Sqstack()；但是在輸出結(jié)果時(shí)發(fā)現(xiàn)無(wú)法把所有走過(guò)的坐標(biāo)輸出來(lái)！最后通過(guò)討論，知道原來(lái)?xiàng)Ｊ呛筮M(jìn)先出，所以只能輸出最后一個(gè)坐標(biāo)。 解決方法：引入另一個(gè)棧t=Init_Sqstack();它的作用是：棧t是棧s的逆，因?yàn)閟保存的途徑是反的，加t 使輸出的途徑變?yōu)檎@樣就可以把所有的坐標(biāo)輸出來(lái)。6.3 對(duì)自己完成課設(shè)完成情況的評(píng)價(jià) 在這次的課程設(shè)計(jì)中，我們小組通過(guò)對(duì)棧和數(shù)組的運(yùn)用，終于完成

14、了迷宮求解的編程,在我們剛拿到題目的時(shí)候，我們就知道這一次的任務(wù)必須要棧來(lái)實(shí)現(xiàn)，所以我們把棧的內(nèi)容復(fù)習(xí)了一下才開(kāi)始編的，不過(guò)當(dāng)我們把棧的部分編好的時(shí)候，才知道后面的似乎更難。在方向的可走上我提出使用類(lèi)似于二維坐標(biāo)的方式來(lái)實(shí)現(xiàn)，也就是數(shù)組move .x或move .y來(lái)實(shí)現(xiàn)的。我覺(jué)得這種思想好在把數(shù)學(xué)的知識(shí)融合在程序里，使的整個(gè)程序更容易理解。最后，在我們?nèi)齻€(gè)人共同討論、上網(wǎng)查找相關(guān)知識(shí)和向其他同學(xué)請(qǐng)教最終解決了遇到的問(wèn)題，完成了整個(gè)設(shè)計(jì)。6.4C語(yǔ)言與數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)課程的意見(jiàn)與建議 C語(yǔ)言是數(shù)據(jù)結(jié)構(gòu)這門(mén)課的核心，沒(méi)有良好的c語(yǔ)言基礎(chǔ)，學(xué)習(xí)這門(mén)課程是很難的。首先，我們?cè)陂喿x數(shù)據(jù)結(jié)構(gòu)的時(shí)候，都是

15、用c語(yǔ)言編寫(xiě)的，這就需要我們把程序看懂；其次，當(dāng)你完成某部分的數(shù)據(jù)結(jié)構(gòu)的知識(shí)時(shí)，必須要把它完整了，才能在VC+ 6.0上運(yùn)行，我發(fā)現(xiàn)我們?cè)谕瓿删幊毯?，main函數(shù)部分是我們最容易錯(cuò)的部分，這和我們c語(yǔ)言的基礎(chǔ)有關(guān)吧。所以我的建議是：1. 希望老師在上課的時(shí)候能夠簡(jiǎn)單幫我們復(fù)習(xí)回顧一下c語(yǔ)言知識(shí)。2. 希望老師能夠在舉例的時(shí)候能夠多用幾個(gè)完整的程序，這樣可以運(yùn)行給我們看看，更能夠加深我們對(duì)知識(shí)的理解。附錄：程序源代碼#include#include#define MAXSIZE 100#define ERROR 0#define OK 1#define m 9#define n 8typedef

16、 struct /*用于存放迷宮的位置和該點(diǎn)信息*/int x,y,d;Datatype;typedef struct /*該棧用于存儲(chǔ)走過(guò)的結(jié)點(diǎn)*/Datatype dataMAXSIZE;int top;Sqstack,*PSqstack;typedef struct /*用于存放當(dāng)前結(jié)點(diǎn)可走的四個(gè)方向*/int x,y;item;PSqstack Init_Sqstack() /*初始化空棧*/PSqstack s;s=(PSqstack)malloc(sizeof(Sqstack);if(s)s-top=-1;return s;int Push_Sqstack(PSqstack s,D

17、atatype x) /*入棧*/if(s-top=MAXSIZE-1)return ERROR; /*棧滿不能入棧*/elses-top+;s-datas-top=x;return OK;int Pop_Sqstack(PSqstack s,Datatype *x) /*出棧*/if(!s)return ERROR; /*棧控不能出棧*/else*x=s-datas-top;s-top-;return OK;void Destroy_Sqstack(PSqstack *s) /*銷(xiāo)毀棧*/if(*s)free(*s);*s=NULL;return;int Mazepath(int mazen

18、+2,int x0,int y0) /*求迷宮路徑函數(shù)，入口參數(shù)：指向迷宮數(shù)組的指針，開(kāi)始點(diǎn)（x0,y0）*/PSqstack s,t;Datatype temp;int x,y,d,i,j;item move4;if(maze11=1|mazemn=1)printf(輸入迷宮數(shù)據(jù)錯(cuò)誤，起點(diǎn)和終點(diǎn)應(yīng)為:0n);elsemove0.x=0;move0.y=1;move1.x=1;move1.y=0;move2.x=0;move2.y=-1;move3.x=-1;move3.y=0; /*對(duì)move定義為向四個(gè)方向探索的數(shù)組*/s=Init_Sqstack(); /*初始化棧s*/t=Init_Sqstack(); /*初始化棧t*/if(!s)printf(棧初始化失敗n);return (0);temp.x=x0;temp.y=y0;temp.d=0;Push_Sqstack(s,temp); /*迷宮入口點(diǎn)入棧*/while(s-top!=-1)Pop_Sqstack(s,&temp);x=temp.x;y=temp.y;d=0; /*將方向重新定位為右方，即move0*/while(dtop!=-1)Pop_Sqstack(s,&temp);Push_Sqstack(t,temp); /*棧t是棧s的逆，因?yàn)閟保存的途徑是反的，加t使輸出的途徑變