數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)--隨機(jī)漫步

1、<p><b>　　數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)三</b></p><p>　　題目：數(shù)據(jù)結(jié)構(gòu)教材第62頁(yè)，第二章附加題第9題：“隨機(jī)漫步”問題，即使用計(jì)算機(jī)“模擬”蟑螂漫步。要解決的問題是（1）打印蟑螂進(jìn)行的合法移動(dòng)總次數(shù)。（2）打印實(shí)驗(yàn)中每一塊瓷磚被經(jīng)歷的次數(shù)。</p><p><b>　　需求分析</b></p><p&g

2、t;　　1、數(shù)據(jù)存儲(chǔ)結(jié)構(gòu)分析：</p><p>　　對(duì)于此“蟑螂漫步”問題的模擬，最主要的是數(shù)據(jù)存儲(chǔ)結(jié)構(gòu)的設(shè)計(jì)。對(duì)此，首先想到了兩種結(jié)構(gòu)：鏈表和數(shù)組。</p><p>　　首先分析鏈表形式的存儲(chǔ)結(jié)構(gòu)。我們看到，“蟑螂漫步”問題中，蟑螂的移動(dòng)是隨機(jī)的。從一個(gè)地方出發(fā)可以隨機(jī)向周圍8個(gè)方位移動(dòng)。如果使用鏈表的存儲(chǔ)形式，固然可以記錄蟑螂對(duì)每一塊瓷磚的訪問次數(shù)，但是，要實(shí)現(xiàn)“隨機(jī)”二字確實(shí)非常不可

3、取。通常鏈表是一個(gè)數(shù)據(jù)域一個(gè)鏈域，要實(shí)現(xiàn)從一個(gè)結(jié)點(diǎn)向周圍8個(gè)結(jié)點(diǎn)都能移動(dòng)，那么要增加7個(gè)鏈域。這是很不安全的，且增加之后也不再是鏈表，而是一個(gè)“網(wǎng)” 。</p><p>　　結(jié)合問題初始提到的把房間劃分成N*M個(gè)方格的思維，我認(rèn)為選擇二維數(shù)組作為數(shù)據(jù)存儲(chǔ)結(jié)構(gòu)是最好不過(guò)的。一來(lái)，不會(huì)造成指針的混亂；二來(lái)，能非常方便的解決蟑螂的隨機(jī)移動(dòng)問題。</p><p>　　把整個(gè)可移動(dòng)的房間放入一個(gè)坐標(biāo)

4、中。我們可以用一組坐標(biāo)（ibut,jbug）來(lái)表示蟑螂的起始坐標(biāo)。坐標(biāo)原點(diǎn)規(guī)定為二維數(shù)組的第一個(gè)元素，即“數(shù)組名[0][0]” 。對(duì)于蟑螂的隨機(jī)移動(dòng)的表示，我們引入兩個(gè)輔助數(shù)組imove[k]和jmove[k]。且imove[]={-1,0,1,1,1,0,-1,-1} jmove[]={1,1,1,0,-1,-1,-1,0}其中K為隨機(jī)數(shù)。而兩個(gè)輔助數(shù)組中的每一個(gè)值代表蟑螂的移動(dòng)方位，因此移動(dòng)后的坐標(biāo)可以這樣表示：（ibug+imov

5、e[k],jbug+jmoge[k]）。</p><p>　　通過(guò)隨機(jī)數(shù)K的變化就巧妙的表示了蟑螂的隨機(jī)移動(dòng)。</p><p>　　2、該試驗(yàn)結(jié)束條件是每一個(gè)方格都被至少進(jìn)入一次，也許出現(xiàn)一直不終止的情況，即有方格一直沒有被進(jìn)入，所以程序中應(yīng)該設(shè)置實(shí)驗(yàn)過(guò)程中進(jìn)入方塊的最大次數(shù)，保證程序能夠終止。</p><p><b>　　3、程序執(zhí)行命令：</b&

6、gt;</p><p>　　（1）提示用戶輸入進(jìn)行模擬矩陣的行列數(shù)；</p><p>　　（2）提示用戶輸入蟑螂初始時(shí)在矩陣中的位置；</p><p>　　（3）輸入過(guò)程中能自動(dòng)檢驗(yàn)輸入字符是否合法，如果不合法，給出相應(yīng)的提示。</p><p><b>　　4、測(cè)試數(shù)據(jù)</b></p><p>　

7、　（1）輸入矩陣行與列分別為：15 15 起始位置為：（10，10）（結(jié)果見后面測(cè)試結(jié)果部分）；</p><p>　　（2）輸入矩陣行與列分別為：39 19 起始位置為：（1，1）（結(jié)果見后面測(cè)試結(jié)果部分）。</p><p><b>　　概要設(shè)計(jì)</b></p><p>　　1、解決問題的各種操作：</p><p>　　

8、（1）漫步函數(shù)：void manbu(int n,int m,int ibug,int jbug)；</p><p>　　（2）方格計(jì)數(shù)器初始化函數(shù)：void chuzhi(int n,int m)；</p><p>　?。?）判斷每個(gè)方格是否都至少進(jìn)入了一次函數(shù)：bool panduan(int n,int m)；</p><p>　?。?）漫步的密度函數(shù)：voi

9、d midu(int n,int m)；</p><p>　?。?）計(jì)算移動(dòng)總次數(shù)函數(shù)：void cishu(int n,int m)；</p><p><b>　　2、主程序</b></p><p>　　Void main()</p><p><b>　　{</b></p><

10、p>　　接受命令（輸入模擬矩陣的行列數(shù)）；</p><p>　　接受命令（輸入蟑螂初始所在位置）；</p><p><b>　　處理命令；</b></p><p><b>　　輸入結(jié)果；</b></p><p><b>　　}</b></p><p&g

11、t;　　3、函數(shù)之間的調(diào)用關(guān)系：</p><p><b>　　詳細(xì)設(shè)計(jì)</b></p><p>　?。ㄒ唬┑谝环N設(shè)計(jì)程序分析</p><p>　　1、主函數(shù)需要的全程量</p><p>　　#include<iostream></p><p>　　#include <stdio.

12、h> </p><p>　　#include <stdlib.h> </p><p>　　#include <time.h></p><p>　　using namespace std;</p><p>　　int imove[]={-1,0,1,1,1,0,-1,-1};</p><p>

13、;　　int jmove[]={1,1,1,0,-1,-1,-1,0};</p><p>　　int h=0,z=0,k,a=0;</p><p>　　int wu[40][20];</p><p><b>　　char ch;</b></p><p><b>　　2、漫步函數(shù)：</b></p

14、><p>　　void manbu(int n,int m,int ibug,int jbug)//漫步函數(shù)</p><p><b>　　{</b></p><p>　　chuzhi(n,m);</p><p>　　wu[ibug][jbug]=1;</p><p>　　srand((unsigned

15、)time(NULL));</p><p>　　for(int j=1;j<=50000;j++)</p><p><b>　　{</b></p><p>　　k=rand()%8;</p><p>　　if(ibug+imove[k]>=n||ibug+imove[k]<0||jbug+jmove[k

16、]>=m||jbug+jmove[k]<0)</p><p>　　continue; //如果越界，則跳到下一次循環(huán)</p><p>　　ibug=ibug+imove[k];</p><p>　　jbug=jbug+jmove[k];//監(jiān)視橫坐標(biāo)和縱坐標(biāo)</p><p>　　wu[ibug][jbug]++;</p

17、><p><b>　　if(j>m*n)</b></p><p><b>　　{</b></p><p>　　if(panduan(n,m))</p><p><b>　　break;</b></p><p><b>　　}</b>

18、;</p><p><b>　　}</b></p><p><b>　　}</b></p><p>　　3、方格計(jì)數(shù)器初始化函數(shù)：</p><p>　　void chuzhi(int n,int m)//方格計(jì)數(shù)器初始化為0</p><p><b>　　{</

19、b></p><p>　　for(int i=0;i<n;i++)</p><p><b>　　{</b></p><p>　　for(int j=0;j<m;j++)</p><p>　　wu[i][j]=0;</p><p><b>　　}</b><

20、;/p><p><b>　　}</b></p><p>　　4、判斷每個(gè)方格是否都至少進(jìn)入了一次函數(shù)：</p><p>　　bool panduan(int n,int m)//判斷每個(gè)方格是否都至少進(jìn)入了一次，如果都進(jìn)入了一次則為真反之為假</p><p><b>　　{</b></p>

21、<p>　　for(int i=0;i<n;i++)</p><p><b>　　{</b></p><p>　　for(int j=0;j<m;j++)</p><p><b>　　{</b></p><p>　　if(wu[i][j]==0)</p><

22、;p>　　return false;</p><p><b>　　}</b></p><p><b>　　}</b></p><p><b>　　}</b></p><p>　　5、漫步的密度函數(shù)：</p><p>　　void midu(int

23、n,int m)//漫步的密度</p><p><b>　　{</b></p><p>　　for(int i=0;i<n;i++)</p><p><b>　　{</b></p><p>　　for(int j=0;j<m;j++)</p><p><b

24、>　　{</b></p><p>　　printf("%4d",wu[i][j]);</p><p><b>　　}</b></p><p>　　printf("\n");</p><p><b>　　}</b></p><

25、;p><b>　　}</b></p><p>　　6、計(jì)算移動(dòng)總次數(shù)函數(shù)：</p><p>　　void cishu(int n,int m)//合法移動(dòng)總次數(shù)</p><p><b>　　{</b></p><p>　　for(int i=0;i<m;i++)</p>&

26、lt;p><b>　　{</b></p><p>　　for(int j=0;j<n;j++)</p><p><b>　　{</b></p><p>　　a+=wu[i][j];</p><p><b>　　}</b></p><p>&l

27、t;b>　　}</b></p><p>　　printf("%d",a);</p><p><b>　　a=0;</b></p><p><b>　　}</b></p><p><b>　　7、主函數(shù)：</b></p><

28、;p>　　void main()</p><p><b>　　{</b></p><p>　　int q,r,s,e;</p><p><b>　　for(;;)</b></p><p><b>　　{</b></p><p>　　printf(&

29、quot;請(qǐng)輸入行數(shù):");</p><p><b>　　cin>>q;</b></p><p>　　printf("請(qǐng)輸入列數(shù):");</p><p><b>　　cin>>r;</b></p><p>　　printf("請(qǐng)輸入起始

30、坐標(biāo):\n");</p><p>　　cin>>s>>e;</p><p>　　if(q>40||q<=2||r>40||r<2)</p><p>　　printf("你的輸入超出范圍，請(qǐng)檢查并重新輸入");</p><p>　　manbu(q,r,s,e);<

31、;/p><p>　　printf("漫步總次數(shù):");</p><p>　　cishu(q,r);</p><p>　　printf("\n");</p><p>　　printf("漫步密度:\n");</p><p>　　midu(q,r);</p>

32、;<p>　　printf("\n");</p><p>　　printf("是否繼續(xù)?(y/n):");</p><p><b>　　cin>>ch;</b></p><p>　　if(ch=='y')</p><p><b>

33、　　continue;</b></p><p><b>　　else</b></p><p><b>　　break;</b></p><p><b>　　}</b></p><p><b>　　}</b></p><p&g

34、t;<b>　　8、函數(shù)調(diào)用關(guān)系圖</b></p><p>　?。ǘ┑诙N設(shè)計(jì)程序：</p><p>　　#include <iostream></p><p>　　#include <cstdlib></p><p>　　#include <iomanip></p>

35、<p>　　#include <time.h></p><p>　　using namespace std;</p><p>　　void main()</p><p><b>　　{</b></p><p>　　int seed = (unsigned)time(NULL);

36、//利用系統(tǒng)時(shí)間獲取一個(gè)產(chǎn)生隨機(jī)數(shù)的種子</p><p>　　int m, n; //地板的瓷磚行列數(shù)</p><p>　　int count; //輔助變量，計(jì)數(shù)蟑螂到過(guò)的瓷磚的塊數(shù)</p><p>　　int random;

37、 //隨機(jī)數(shù)</p><p>　　int ibug, jbug; //蟑螂的位置</p><p>　　int imove[8] = {-1,0,1,1,1,0,-1,-1}; //蟑螂移動(dòng)數(shù)組</p><p>　　int jmove[8] = {1,

38、1,1,0,-1,-1,-1,0};</p><p>　　int **matrix; //計(jì)數(shù)蟑螂到過(guò)每一塊瓷磚的數(shù)目矩陣</p><p>　　cout <<"輸入地板瓷磚的行數(shù)\n"; //輸入地板瓷磚的行列數(shù)</p><p><b>　　c

39、in >> m;</b></p><p>　　cout <<"輸入地板瓷磚的列數(shù)\n";</p><p><b>　　cin >> n;</b></p><p>　　matrix = new int*[m]; //動(dòng)態(tài)創(chuàng)建matrix數(shù)

40、組</p><p>　　for (int i=0; i<m; i++)</p><p><b>　　{</b></p><p>　　matrix[i] = new int[n];</p><p><b>　　}</b></p><p>　　for (i=0; i<

41、m; i++)</p><p><b>　　{</b></p><p>　　for (int j=0; j<n; j++)</p><p><b>　　{</b></p><p>　　matrix[i][j] = 0;</p><p><b>　　}</

42、b></p><p><b>　　}</b></p><p>　　cout <<"請(qǐng)給出蟑螂的初始位置\n"; //輸入蟑螂的初始位置</p><p>　　cin >> ibug >> jbug;</p><p>　　count = 1;&l

43、t;/p><p>　　if (ibug>=m || ibug<0 || jbug>=n || jbug<0) //驗(yàn)證蟑螂初始位置</p><p><b>　　{</b></p><p>　　cout <<"錯(cuò)誤的初始位置\n";</p><p><b>　　

44、return;</b></p><p><b>　　}</b></p><p>　　matrix[ibug][jbug] = 1; //蟑螂初始位置坐標(biāo)置1</p><p>　　srand(seed);</p><p>　　for (i=1; i<=50000; i+

45、+) //蟑螂在地板上移動(dòng)</p><p><b>　　{</b></p><p>　　random = rand()%8;</p><p>　　if (ibug+imove[random]>=m || ibug+imove[random]<0 || </p><p>　　j

46、bug+jmove[random]>=n || jbug+jmove[random]<0)//當(dāng)蟑螂移動(dòng)到墻壁時(shí)，進(jìn)入下一輪循環(huán)</p><p><b>　　continue;</b></p><p>　　ibug += imove[random]; //改變蟑螂位置</p><p>　　jbug +=

47、 jmove[random];</p><p>　　matrix[ibug][jbug] += 1; //蟑螂到過(guò)的位置加1</p><p>　　if (i>=m*n) //檢測(cè)蟑螂是否已經(jīng)到過(guò)所有的瓷磚</p><p><b>　　{</b></p>

48、;<p>　　for (int j=0; j<m; j++)</p><p><b>　　{</b></p><p>　　for (int k=0; k<n; k++)</p><p><b>　　{</b></p><p>　　if (matrix[j][k] != 0)

49、</p><p><b>　　count++;</b></p><p><b>　　}</b></p><p><b>　　}</b></p><p><b>　　}</b></p><p>　　if (count==m*n)

50、 //若蟑螂到到過(guò)所有的瓷磚</p><p>　　break; //退出循環(huán)</p><p>　　count = 0;</p><p><b>　　}</b></p><p>　　cout << "蟑螂總共移動(dòng)的

51、次數(shù)為:" <<i-1<<endl;</p><p>　　cout << "蟑螂所經(jīng)過(guò)每一塊瓷磚的次數(shù)為:\n";</p><p>　　for (i=0; i<m; i++) //輸出蟑螂到過(guò)每一塊瓷磚的次數(shù)</p><p><b>　　{&

52、lt;/b></p><p>　　for (int j=0; j<n; j++)</p><p><b>　　{</b></p><p>　　cout << setw(4)<<matrix[i][j];</p><p><b>　　}</b></p>

53、<p>　　cout << endl;</p><p><b>　　}</b></p><p>　　for (i=0; i<m; i++) //數(shù)組matrix</p><p>　　delete[] matrix[i];</p><p><b

54、>　　}</b></p><p><b>　　調(diào)試分析</b></p><p>　　1、“隨機(jī)漫步”問題長(zhǎng)久以來(lái)一直吸引著數(shù)學(xué)界的興趣，但即便是最簡(jiǎn)單的隨機(jī)漫步問題，解決起來(lái)是極其困難，本課程設(shè)計(jì)只是一個(gè)模擬的隨機(jī)問題，所以技術(shù)含量并不高。</p><p>　　2、一開始設(shè)計(jì)了一個(gè)使用隨機(jī)數(shù)的程序，運(yùn)行起來(lái)相當(dāng)?shù)穆?，要?jì)算一個(gè)

55、15行15列矩陣的“隨機(jī)問題”需要運(yùn)行差不多二個(gè)小時(shí)，后來(lái)經(jīng)過(guò)改進(jìn)，才形成第一種程序，運(yùn)行速度非常的快。</p><p>　　3、該程序設(shè)置進(jìn)行得比較順利，初始運(yùn)行時(shí)只有幾處小的錯(cuò)誤，改正后就能正常運(yùn)行了。</p><p><b>　　用戶手冊(cè)</b></p><p>　　本程序的運(yùn)行環(huán)境為DOS操作環(huán)境，文件名為walk.exe;</p

56、><p>　　2、本例演示程序簡(jiǎn)單明了，按提示輸入即可。</p><p>　　時(shí)間復(fù)雜度和空間復(fù)雜度分析</p><p><b>　　時(shí)間復(fù)雜度分析：</b></p><p>　　對(duì)于程序的第一種設(shè)計(jì)，是用函數(shù)劃分功能模塊的方式，將漫步問題的每個(gè)步驟劃分為一個(gè)個(gè)功能函數(shù)，然后調(diào)用這些函數(shù)來(lái)實(shí)現(xiàn)漫步過(guò)程?？梢钥吹狡渲?cish

57、u()函數(shù) midu()函數(shù) panduan()函數(shù) chuzhi()函數(shù)都有兩個(gè)for循環(huán)，每一個(gè)函數(shù)的時(shí)間復(fù)雜度為O（M）*O（N）。在 manbu()函數(shù)中有一個(gè)for循環(huán)，要循環(huán)50000次。最壞情況下其時(shí)間復(fù)雜度為：O（50000）。所以程序總的時(shí)間復(fù)雜度為：O（M）*O（N）*3＋O（50000）*O（M）*O（N）。</p><p>　　對(duì)于程序的第二種設(shè)計(jì)，是在主函數(shù)中一并實(shí)現(xiàn)所有過(guò)程。沒有使用函

58、數(shù)來(lái)封裝功能。它總共包含了九個(gè)for語(yǔ)句。第一個(gè)for語(yǔ)句的時(shí)間復(fù)雜度為O（M）。進(jìn)入第二個(gè)for之后為O（M）*O（N）。進(jìn)入第四個(gè)for語(yǔ)句之后的時(shí)間復(fù)雜度為：O（M*N）+O（50000-M*N）*O（M）*O（N）。進(jìn)入第七個(gè)for的時(shí)間復(fù)雜度為：O（M）*O（N）。最后一個(gè)for：O（M）。因此，第二種程序總時(shí)間復(fù)雜度為：O（M）＋O（M）*O（N）+ O（M*N）+O（50000-M*N）*O（M）*O（N）+ O（M）*O

59、（N）+ O（M）。</p><p><b>　　空間復(fù)雜度分析：</b></p><p>　　很明顯可以看出：第一種程序設(shè)計(jì)用的是一個(gè)固定大小的數(shù)組，而第二種程序設(shè)計(jì)用的是動(dòng)態(tài)分配數(shù)組。其他方面均相差不大，對(duì)于空間復(fù)雜度的問題，最主要的就在于一個(gè)動(dòng)態(tài)數(shù)組一個(gè)固定數(shù)組。</p><p>　　動(dòng)態(tài)數(shù)組能按照實(shí)時(shí)需要來(lái)分配合適的內(nèi)存空間，而固定的數(shù)