數(shù)據(jù)結(jié)構(gòu)數(shù)組的表示及其應(yīng)用

1、數(shù)組的表示及其應(yīng)用【實(shí)驗(yàn)題目】：數(shù)組的表示及其應(yīng)用【問題描述】以一個(gè)m x n的長方陣表示迷宮，1和0分別表示迷宮中的通路和障礙。 設(shè)計(jì)一個(gè)程序，對(duì)任意設(shè)定的迷宮，求出一條從入口到出口的通路，或得出沒有通路 的結(jié)論。【基本要求】首先實(shí)現(xiàn)一個(gè)以鏈表作存儲(chǔ)結(jié)構(gòu)的棧類型，然后編寫一個(gè)求解迷宮的非遞歸程序。 求得的通路以三元組(i, j, d)的形式輸出，其中：(i, j)指示迷宮中的一個(gè)坐標(biāo)，d表 示走到下一坐標(biāo)的方向。如；對(duì)于下列數(shù)據(jù)的迷宮，輸出的一條通路為：(l, 1, 1), (1, 2, 2), (2, 2, 2), (3, 2, 3), (3, 1, 2),.?！緦?shí)現(xiàn)提示】計(jì)算機(jī)解迷宮通常

2、用的是“窮舉求解”方法，即從人口出發(fā)，順著某一個(gè)方向進(jìn)行 探索，若能走通，則繼續(xù)往前進(jìn)；否則沿著原路退回，換一個(gè)方向繼續(xù)探索，直至出口 位置，求得一條通路。假如所有可能的通路都探索到而未能到達(dá)出口，則所設(shè)定的迷宮 沒有通路。可以二維數(shù)組存儲(chǔ)迷宮數(shù)據(jù)，通常設(shè)定人口點(diǎn)的下標(biāo)為(1, 1),出口點(diǎn)的下 標(biāo)為(n, n)。為處理方便起見，可在迷宮的四周加一圈障礙。對(duì)于迷宮中任一位置，均 可約定有東、南、西、北四個(gè)方向可通。一、【實(shí)驗(yàn)構(gòu)思(Conceive) (10%)整個(gè)實(shí)驗(yàn)將實(shí)現(xiàn)迷宮路徑的查找，并圖形化輸出其中最短的路徑。本實(shí)驗(yàn)?zāi)_步的存 放使用雙向鏈表實(shí)現(xiàn)，迷宮使用二維數(shù)組存放。機(jī)器通過窮舉法解出迷

3、宮的最短路 徑，儲(chǔ)存在雙向鏈表中，最后輸出。整個(gè)實(shí)驗(yàn)分為以下幾個(gè)模塊：創(chuàng)建模塊。本實(shí)驗(yàn)的創(chuàng)建包含兩方面，迷宮的定義和腳步的初始化。迷宮的 定義通過修改二維數(shù)組實(shí)現(xiàn)，最終創(chuàng)建一個(gè)確定的迷宮。腳步的初始化由程序自 行完成，最終建立一個(gè)雙向鏈表的附加頭結(jié)點(diǎn)。路徑查找模塊。路徑查找核心分為兩個(gè)部分：路徑查找、更優(yōu)解替換。路徑查找包括可通性檢查、腳步前進(jìn)、腳步后退三個(gè)模塊?？赏ㄐ詸z查會(huì)檢查當(dāng)前腳 步的四個(gè)方向是否有通路。腳步前進(jìn)可以在有通路的情況下抵達(dá)下一個(gè)點(diǎn)，并記 錄在腳步雙向鏈表中。腳步后退使在當(dāng)前腳步無路的情況下后退一步，并轉(zhuǎn)向其 他方向，同時(shí)刪除鏈表中最后一個(gè)腳步。當(dāng)求出的路徑比上一次求出的路徑

4、更短 時(shí)，更優(yōu)解替換將更優(yōu)解替換進(jìn)路線存儲(chǔ)鏈表。輸出模塊。實(shí)現(xiàn)迷宮解的圖形化顯示和路徑的坐標(biāo)輸出。其他模塊。格式化模塊，用于迷宮求解后的處理。迷宮數(shù)組改寫模塊，按照求 解的結(jié)果改寫迷宮二維數(shù)組，以滿足最終輸出需要。二、【實(shí)驗(yàn)設(shè)計(jì)(Design)】(15%)主函數(shù)main():程序啟動(dòng)時(shí)，執(zhí)彳亍main ()函數(shù)輸出菜單。用戶根據(jù)菜單的提示 輸入要執(zhí)行的功能，程序會(huì)根據(jù)用戶的選擇執(zhí)行不同的功能。自動(dòng)演示：命令1,由程序自動(dòng)生成一個(gè)迷宮，并進(jìn)行路徑求解的演示。手動(dòng)迷宮：命令2,由用戶自行創(chuàng)建一個(gè)迷宮，定義迷宮的大小、形狀等，程 序?qū)?duì)用戶指定的迷宮進(jìn)行求解。程序幫助：命令3，顯示程序幫助和必要信息

5、。退出：命令4，退出程序。創(chuàng)建模塊在自動(dòng)演示中，機(jī)器會(huì)調(diào)用autocreat ()函數(shù)自動(dòng)創(chuàng)建一個(gè)10*10的迷宮。在di+;if(direction=1)if(maze(nowstep-x)-1nowstep-y=1) return 1;else return 0;else if(direction=2)if(mazenowstep-x(nowstep-y)+1=1) return 1;else return 0;else if(direction=3)if(maze(nowstep-x)+1nowstep-y=1) return 1;else return 0;else if(direct

6、ion=4)if(mazenowstep-x(nowstep-y)-i=i) return 1;else return 0;void move(int direction)/如果chk函數(shù)判斷下一點(diǎn)可通，則使用此函數(shù)實(shí)現(xiàn)走動(dòng)。laststep=nowstep;/ 將laststep 指向 nowstep，再建立新的 nowstep，實(shí)現(xiàn)nowstep 的前進(jìn)。nowstep=(node *)malloc( sizeof(node); nowstep-di=0; nowstep-next=NULL;nowstep-pre=laststep; nowstep-stepsum=laststep-st

7、epsum+1; nowstep-x=laststep- x;nowstep-y=laststep-y; laststep-next=nowstep;mazelaststep-xlaststep-y=-1;/用-1 將maze 數(shù)組中的值標(biāo)記，表示已經(jīng)走過switch (direction)case 1:nowstep-x-; break;case 2:nowstep-y+; break;case 3: nowstep- x+;break;case 4: nowstep-y-; 函數(shù)功能描述autocreat()用以自動(dòng)生成一個(gè)10*10的迷宮。creat()通過用戶輸入的數(shù)據(jù)，創(chuàng)建一個(gè)指定大

8、小為m*n，具有特定形狀的迷宮。seek()程序?yàn)槊詫m查找的核心函數(shù)，通過調(diào)用chk()、move()、back ()以及自身的 優(yōu)解替換功能，最終求解出一個(gè)迷宮的最短路徑，存儲(chǔ)在雙向鏈表之中。此外，seek() 函數(shù)還具有判斷處理特殊迷宮的功能。seek ()函數(shù)不同返回值的含義，返回-1無解， 1正常解出，2入口和出口重合。chk(int direction)用來判斷指定方向的可通性，返回1表示可通，0表示不可通。move(int direction)函數(shù)可以實(shí)現(xiàn)腳步向指定方向移動(dòng)。即把新的腳步納入腳步 雙向鏈表中，并將maze數(shù)組中相應(yīng)的元素記錄為-1表示已走。back()當(dāng)腳步的四個(gè)方

9、向均已不能通過時(shí)，調(diào)用back()函數(shù)刪除雙向鏈表的最后一 個(gè)腳步，并將maze數(shù)組中相應(yīng)元素標(biāo)記為1，實(shí)現(xiàn)腳步的回退。revise()使用指針p,根據(jù)已求的的腳步，改寫maze數(shù)組，使之滿足輸出需要。設(shè) 有指針p,則根據(jù)p-pre，p， p-next三點(diǎn)所記錄的坐標(biāo)，可以求出p的腳步形狀， 并標(biāo)記在 mazep-xp-y中。8.outlin()輸出迷宮求解的結(jié)果。help()函數(shù)用以輸出程序必要的幫助信息。formatmaze()初始化存儲(chǔ)迷宮的二維數(shù)組、各變量值，銷毀上次求解時(shí)產(chǎn)生的雙 向鏈表，釋放內(nèi)存空間。時(shí)間復(fù)雜度分析迷宮求解的時(shí)間復(fù)雜度與迷宮大小m*n、迷宮形狀、第一次成功求解時(shí)產(chǎn)生

10、的雙向鏈 表長度等均有關(guān)系。兩個(gè)典型的極端情況：當(dāng)?shù)谝淮吻蠼饧囱刂嫌疫吔绯晒η蟪龅谝粋€(gè)路徑。此時(shí)已是最短路徑，在判斷此 為理論最短路徑后，結(jié)束其他可能路徑的求解，并輸出此路徑。時(shí)間復(fù)雜度為o(m+n)。建立一個(gè)n*n的迷宮，迷宮內(nèi)無任何阻擋，程序開始求解。此時(shí)會(huì)尋遍n*n個(gè)點(diǎn)， 第一次求出的路徑為理論上最長的路徑。此后程序不斷back()，重復(fù)直至求出最短路 徑，此時(shí)經(jīng)歷了 n!次運(yùn)算，時(shí)間復(fù)雜度為o(n!)主函數(shù)main()執(zhí)行流程圖四、【測(cè)試結(jié)果(Testing) (20%)程序菜單3：W2 手動(dòng)迷宮4-退由程岸同選擇1-4：1論序?qū)?duì)此迷宮進(jìn)行求解，入口出口口艮1。)012345678

11、 91011列數(shù) 最大36游36。1為通路，數(shù)字間用空梧間隔。.系統(tǒng)將自動(dòng)添加圍墻。1110 0110 101110 010 0 1111111 偵IIS仃 555 5 5 為共共共共共 0 居居居居居 一.+,-.+.-. -. 一.+,-據(jù)數(shù)數(shù)# 數(shù)個(gè)個(gè)個(gè)個(gè)個(gè) 言 5 5 5 S 5 _!=匚勺勺勺勺勺 *-、-1- - 1- - 1 - - 1 - - 1- 法偵1III1I仃 . 12 3 4 5已成功建立迷宮x，示示 標(biāo)宮式式 坐迷藕富： 數(shù)列蓋 口75坐坐 入命口口 出立入出 定建定入己成功查找出最短路徑，輸出如下： 0 12 3 4 5 6 。 1BA 2 TOC o 1-5 h

12、 z 34| 5B 出.&此路徑的步進(jìn)順序?yàn)椋捍寺窂揭咽亲疃搪窂剑?步。五、【實(shí)驗(yàn)總結(jié)】(10%)最初的腳步可通性檢查中，僅僅使用chk ()判斷了下一個(gè)點(diǎn)是否有障礙，沒有考 慮到下一個(gè)點(diǎn)是否已經(jīng)存在于腳步鏈表中，結(jié)果導(dǎo)致經(jīng)典的迷宮死循環(huán)。通過不斷 的畫圖計(jì)算，參閱資料，最終明確了此問題并對(duì)判斷條件進(jìn)行了更正，消除了錯(cuò)誤， 提高了程序的穩(wěn)定性。下圖所示一個(gè)典型的問題迷宮，機(jī)器窮舉法求解時(shí)判斷條件 不嚴(yán)密會(huì)造成死循環(huán)。當(dāng)結(jié)束一次迷宮求解，進(jìn)行第二次迷宮求解時(shí)，建立的迷宮在輸出時(shí)會(huì)出現(xiàn)“亂 碼”現(xiàn)象。分析其原因，上次求解完畢后迷宮數(shù)組并沒有初始化。類似的，考慮到 其他變量也可能出現(xiàn)此問題，上次求

13、解的路徑雙向鏈表空間沒有被釋放，導(dǎo)致內(nèi)存 泄露，遂編寫了 formatmaze ()函數(shù)。此函數(shù)在必要時(shí)運(yùn)行，可以初始化各值并銷毀 殘余的雙向鏈表。本次課程設(shè)計(jì)使我有很大收獲。通過迷宮的實(shí)現(xiàn)，使我對(duì)隊(duì)列、棧、雙向鏈表等結(jié) 構(gòu)有了更深的認(rèn)識(shí)。在起草程序過程中，我明白了明確的思路、獨(dú)立的思考和好的 流程圖對(duì)編寫程序的極端重要性。在程序的調(diào)試過程中，我學(xué)到了很多程序調(diào)試的 技巧，領(lǐng)悟到合理地設(shè)置斷點(diǎn)和中間變量輸出，對(duì)各模塊的調(diào)試大有裨益。在幾天 的程序編寫和調(diào)試過程中，我的細(xì)心和耐心程度得以提高，領(lǐng)悟到一絲不茍是工作 和學(xué)習(xí)必備的品質(zhì)?？傊@次課程設(shè)計(jì)使我在知識(shí)水平和性格培養(yǎng)兩個(gè)方面，都有豐富的收

14、獲。五、【項(xiàng)目運(yùn)作描述(Operate)】 (10%)本次試驗(yàn)基本實(shí)現(xiàn)了給定條件并生成迷宮，并且求解出路，以及求解最短路徑，功能 比較齊全，并且通過釋放棧的空間，更改運(yùn)算模式，在時(shí)間和空間上都比較簡(jiǎn)化，只 是本試驗(yàn)沒有成熟的界面設(shè)計(jì)，只能停留在dos界面。六【代碼】(10%)#include #include #include #define maxsize 36typedef struct lnodestruct lnode *next;struct lnode *pre;int x;int y;int stepsum;/表示當(dāng)前腳步為第幾步。int di;/用di代表已嘗試的腳步方向。分別

15、代表未嘗試、f、一、I、一。node,*linklist;/全局變量開始linklist L,L2,p,q,g; 三個(gè)指針pqg滿足不同函數(shù)臨時(shí)指針需要node *nowstep,*laststep;int mazemaxsize+2maxsize+2;/存儲(chǔ)迷宮的數(shù)組，+2 是為了加圍墻。int m,n;/迷宮行、列數(shù)變量int exitx,exity,entrancex,entrancey;/出入口。xy分別代表行歹列int finish=0;/走迷宮的最終全局結(jié)果。有路，-1無路，出入口重合。int existL=0;/手動(dòng)創(chuàng)建迷宮，選擇r重新創(chuàng)建迷宮，formatmaze()將格式化各

16、變量。檢測(cè)L鏈表是否存在防止程序崩 潰。int mindistance=0;/存放求出的最短路徑的步數(shù)。/創(chuàng)建迷宮void creat() int i,j;char cord= a;system(cls);do if(cord= r)void formatmaze();printf(n請(qǐng)輸入迷宮行、列數(shù)(最大d*%d)。n行:,maxsize,maxsize);scanf(%d”,&m);printf(列:，scanf(%d,&n);while(mmaxsize|nmaxsize|mi|ni)printf(輸入有誤。只支持%d*%d以內(nèi)的迷宮，請(qǐng)重新輸入行列數(shù)。n行:,maxsize,maxs

17、ize); scanf(%d,&m);printf( 列:);scanf(%d,&n);printf(n輸入迷宮數(shù)據(jù)，為磚頭，為通路，數(shù)字間用空格間隔。系統(tǒng)將自動(dòng)添加圍墻。n”);for(i=i;i=m;i+)printf(第d行的d個(gè)數(shù)據(jù)(共d彳亍):,i,n,m);for(j=i;jm|entranceyn |mazeentrancexentrancey=0)printf(-輸入有誤，請(qǐng)檢查。坐標(biāo)應(yīng)在(1,1)至(d,%d)之間。n請(qǐng)重新輸入入口坐標(biāo)，格式示例1,1:”,m,n);scanf(%d,%d”,&entrancex,&entrancey);printf(輸入出口坐標(biāo)，格式示例%

18、d,%d : ,m,n);scanf(%d,%d”,&exitx,&exity);while(exitxm+1|exityn+1|mazeexitxexity=0)printf(輸入有誤，請(qǐng)檢查。坐標(biāo)應(yīng)在(1,1) 至(d,%d)之間n請(qǐng)重新輸入出口坐標(biāo)，格式示例%d,%d : ”,m,n,m,n);scanf(%d,%d”,&exitx,&exity);system(cls);printf(n你設(shè)定的迷宮如下：n);mazeentrancexentrancey= -1;mazeexitxexity= -2;void outlin();mazeentrancexentrancey=1;maze

19、exitxexity=1;printf(入口和出口分別為(%d,%d)(%d,%d)?？阪I入)將開始求解，鍵站重新設(shè)定：”,entrancey,entrancex,exity,exitx);scanf(%c%c”,&cord,&cord);while(cord!= y &cord!=r)printf(輸入有誤，請(qǐng)重新輸入:)；scanf(%c%c”,&cord,&cord);system(cls);while(cord!= y);/格式化迷宮。再創(chuàng)建新迷宮時(shí)用。void formatmaze()int i,j;for(i=0;im+2;i+)for(j=0;jnext)L=L-next; fr

20、ee(L-pre);free (L);if(existL=2)while(L2-next)L2=L2-next; free(L2-pre);free (L2);existL=0； finish=0； mindistance=0；/迷宮求解。int chk(int direction) /判斷下一個(gè)方向是否有障礙的函數(shù)。nowstep-di+;if(direction=1)if(maze(nowstep-x)-1nowstep-y=1) return 1;else return 0;else if(direction=2)if(mazenowstep-x(nowstep-y)+1=1) retu

21、rn 1;else return 0;else if(direction=3)if(maze(nowstep-x)+1nowstep-y=1) return 1;else return 0;else if(direction=4)if(mazenowstep-x(nowstep-y)-1=1) return 1;else return 0;void move(int direction)/如果chk函數(shù)判斷下一點(diǎn)可通，則使用此函數(shù)實(shí)現(xiàn)走動(dòng)。laststep=nowstep;/ 將laststep 指向 nowstep nowstep=(node *)malloc( sizeof(node);n

22、owstep-next=NULL;nowstep-stepsum=laststep- stepsm+1;nowstep-y=laststep-y;再建立新的nowstep，實(shí)現(xiàn)nowstep的前進(jìn)。 nowstep-di=0;nowstep-pre=laststep;nowstep-x=laststep- x;laststep-next=nowstep;mazelaststep-xlaststep- y=-1;/用-1 將maze 數(shù)組中的值標(biāo)記，表示已經(jīng)走過switch (direction) case 1:nowstep-x-; break;case 2:nowstep-y+; break

23、;case 3: nowstep- x+;break;case 4: nowstep-y-;void back()nowstep=laststep;free(nowstep- next);mazenowstep-xnowstep-y=1;/將maze數(shù)組中標(biāo)記的-1改為，以便其他路徑嘗試時(shí)可以通過。 laststep=laststep-pre;nowstep-next=NULL;void revise。/ I 一廠r六個(gè)符號(hào)在maze數(shù)組里分別由3 4 5 6 7表示. int dx,dy;p=L2-next- next;while(p-next&p-pre) dx=(p-next-x)-(p

24、-pre- x);dy=(p-next- y)-(p-pre- y);if(dy=0)mazep-xp-y=2;else if(dx=0)mazep-xp-y=3;else if(dx=1&dy=1) if(p-x=p-pre-x)mazep-xp-y=5;elsemazep-xp-y=6;mazep-xp-y=7；mazep-xp-y=4；mazep-xp-y=4;mazep-xp-y=7;mazep-xp-y=6;mazep-xp-y=5;else if(dx=-i&dy=i) if(p-x=p-pre-x) elseelse if(dx=i&dy=-i) if(p-x=p-pre-x)

25、elseelse if(dx=-i&dy=-i) if(p-x=p-pre-x) else p=p-next;mazeexitxexity= -2; mazeentrancexentrancey= -1;int seek() int allfinished=0;if(entrancex=exitx&entrancey=exity)/入口和出口重合的特殊情況。return 2;L=(linklist)malloc( sizeof(node);/ 建立存儲(chǔ)腳步的鏈表.L-next=NULL;L-pre=NULL; L-stepsum=0;existL=i;/初始化nowstep，令其在入口處。no

26、wstep=(node *)malloc( sizeof(node);nowstep-x=entrancex; nowstep-y=entrancey; nowstep-pre=L; nowstep-next=NULL;nowstep-di=0;nowstep-stepsum=i;L-next=nowstep;/開始查找第一條可通路徑。while(nowstep-x!=exitx|nowstep-y!=exity) /用代表 1 四個(gè)方向。if(nowstep-di=0&chk(i)=i)/可通必須滿足兩個(gè)條件，下一個(gè)點(diǎn)無障礙、下一個(gè)點(diǎn)未出現(xiàn)在已構(gòu)建的路徑中。move(i);else if(n

27、owstep-di=i&chk(2)=i)move(2);else if(nowstep-di=2&chk(3)=i)move(3);else if(nowstep-di=3&chk(4)=i)move(4);else if(nowstep-x=entrancex&nowstep-y=entrancey)/如果腳步停留在了入口，說明迷宮無解， 不再查找。return-1;elseback();/本步無路了，回退。mindistance=laststep-stepsum;/OK,查找出了第一條路徑L，說明迷宮有解。建立L2比較路徑，嘗試尋找比1更短的路徑。if (laststep-stepsum

28、=abs(entrancex-exitx)+abs(entrancey-exity) /若第一條路徑與理論最小路徑相等，則 不需要再次比較，直接返回。L2=L; revise(); return i;existL=2;while(allfinished=0) L2=(linklist)malloc( sizeof(node); L2-next=NULL; L2-pre=NULL; L2-stepsum=0;/將最后一個(gè)最小路徑備份到L2,繼續(xù)求解。p=L2; g=L-next;while(g)q=(node *)malloc( sizeof(node);q-di=g-di; q-stepsum

29、=g-stepsum; q-x=g-x; q-y=g- y;q-pre=p; p-next=q; g=g-next; p=q;q-next=NULL;/開始查找第二條可通路徑。back();while(nowstep-x!=exitx|nowstep-y!=exity) if(nowstep-di=0&chk(i)=i)move(i);else if(nowstep-di=1&chk(2)=1)move(2);else if(nowstep-di=2&chk(3)=1)move(3);else if(nowstep-di=3&chk(4)=1)move(4);else if(nowstep-s

30、tepsum=1&nowstep-di=4) /第一步的四個(gè)方向也都嘗試過了，說明迷宮所 有可能路徑都已嘗試完畢。 allfinished=1; break; back(); if (nowstep-stepsum=mindistance) /新路徑大于舊路徑，就不要再往下嘗試?yán)速M(fèi)時(shí)間了。換其 他路徑。back();if(allfinished=0)/每次找到更短路徑，都要存入L2，并銷毀原L2釋放空間。 mindistance=laststep-stepsum;while(L2-next) L2=L2-next; free(L2-pre); free (L2);revise();/改寫maz

31、e數(shù)組里存儲(chǔ)的內(nèi)容，把每一步的方向信息寫進(jìn)去，以便輸出圖形路徑。return 1;/輸出迷宮的函數(shù)int outlin() int i,j;if(finish=-1) printf(nn 沒找到路!你的迷宮有問題.n);return 1; else if(finish=2) printf(nn。入口和出口重合了!n); return 1; else if(finish=1) printf(nn已成功查找出最短路徑，輸出如下：n);printf(- );/開始輸出圖形。for(j=0;jn+2;j+) printf(%2d”,j);printf(n);for(i=0;im+2;i+) printf(%2d”,i);for(j=0;jnext;printf(此路徑的步進(jìn)順序?yàn)椋簄);while(q-next