數(shù)據(jù)結(jié)構課程設計--隨機漫步

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

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

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

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

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

6、gt;</p><p>　?。?）提示用戶輸入進行模擬矩陣的行列數(shù)；</p><p>　?。?）提示用戶輸入蟑螂初始時在矩陣中的位置；</p><p>　?。?）輸入過程中能自動檢驗輸入字符是否合法，如果不合法，給出相應的提示。</p><p><b>　　4、測試數(shù)據(jù)</b></p><p>　

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

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

9、d midu(int n,int m)；</p><p>　　（5）計算移動總次數(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)用關系：</p><p><b>　　詳細設計</b></p><p>　?。ㄒ唬┑谝环N設計程序分析</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)視橫坐標和縱坐標</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、方格計數(shù)器初始化函數(shù)：</p><p>　　void chuzhi(int n,int m)//方格計數(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、判斷每個方格是否都至少進入了一次函數(shù)：</p><p>　　bool panduan(int n,int m)//判斷每個方格是否都至少進入了一次，如果都進入了一次則為真反之為假</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、計算移動總次數(shù)函數(shù)：</p><p>　　void cishu(int n,int m)//合法移動總次數(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;請輸入行數(shù):");</p><p><b>　　cin>>q;</b></p><p>　　printf("請輸入列數(shù):");</p><p><b>　　cin>>r;</b></p><p>　　printf("請輸入起始

30、坐標:\n");</p><p>　　cin>>s>>e;</p><p>　　if(q>40||q<=2||r>40||r<2)</p><p>　　printf("你的輸入超出范圍，請檢查并重新輸入");</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)用關系圖</b></p><p>　?。ǘ┑诙N設計程序：</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)時間獲取一個產(chǎn)生隨機數(shù)的種子</p><p>　　int m, n; //地板的瓷磚行列數(shù)</p><p>　　int count; //輔助變量，計數(shù)蟑螂到過的瓷磚的塊數(shù)</p><p>　　int random;

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

38、1,1,0,-1,-1,-1,0};</p><p>　　int **matrix; //計數(shù)蟑螂到過每一塊瓷磚的數(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]; //動態(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 <<"請給出蟑螂的初始位置\n"; //輸入蟑螂的初始位置</p><p>　　cin >> ibug >> jbug;</p><p>　　count = 1;&l

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

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

45、+) //蟑螂在地板上移動</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)//當蟑螂移動到墻壁時，進入下一輪循環(huán)</p><p><b>　　continue;</b></p><p>　　ibug += imove[random]; //改變蟑螂位置</p><p>　　jbug +=

47、 jmove[random];</p><p>　　matrix[ibug][jbug] += 1; //蟑螂到過的位置加1</p><p>　　if (i>=m*n) //檢測蟑螂是否已經(jīng)到過所有的瓷磚</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、 //若蟑螂到到過所有的瓷磚</p><p>　　break; //退出循環(huán)</p><p>　　count = 0;</p><p><b>　　}</b></p><p>　　cout << "蟑螂總共移動的

51、次數(shù)為:" <<i-1<<endl;</p><p>　　cout << "蟑螂所經(jīng)過每一塊瓷磚的次數(shù)為:\n";</p><p>　　for (i=0; i<m; i++) //輸出蟑螂到過每一塊瓷磚的次數(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、“隨機漫步”問題長久以來一直吸引著數(shù)學界的興趣，但即便是最簡單的隨機漫步問題，解決起來是極其困難，本課程設計只是一個模擬的隨機問題，所以技術含量并不高。</p><p>　　2、一開始設計了一個使用隨機數(shù)的程序，運行起來相當?shù)穆嬎阋粋€

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

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

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

58、數(shù)來封裝功能。它總共包含了九個for語句。第一個for語句的時間復雜度為O（M）。進入第二個for之后為O（M）*O（N）。進入第四個for語句之后的時間復雜度為：O（M*N）+O（50000-M*N）*O（M）*O（N）。進入第七個for的時間復雜度為：O（M）*O（N）。最后一個for：O（M）。因此，第二種程序總時間復雜度為：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>　　空間復雜度分析：</b></p><p>　　很明顯可以看出：第一種程序設計用的是一個固定大小的數(shù)組，而第二種程序設計用的是動態(tài)分配數(shù)組。其他方面均相差不大，對于空間復雜度的問題，最主要的就在于一個動態(tài)數(shù)組一個固定數(shù)組。</p><p>　　動態(tài)數(shù)組能按照實時需要來分配合適的內(nèi)存空間，而固定的數(shù)