《大數(shù)據(jù)結(jié)構(gòu)馬踏棋盤》由會(huì)員分享，可在線閱讀，更多相關(guān)《大數(shù)據(jù)結(jié)構(gòu)馬踏棋盤（8頁(yè)珍藏版）》請(qǐng)?jiān)谘b配圖網(wǎng)上搜索。

1、word 實(shí)現(xiàn)順序?；蜓h(huán)隊(duì)列的存儲(chǔ) 一 需求分析 理解棧的特性“后進(jìn)先出〞 和隊(duì)列的特性“先進(jìn)先出〞。僅僅認(rèn)識(shí)到棧和隊(duì)列是兩種特殊的線性表是遠(yuǎn)遠(yuǎn)不夠的，本次實(shí)驗(yàn)的目的在于更深入的了解棧和隊(duì)列的特性，以便在實(shí)際問題背景下靈活運(yùn)用他們。在了解他特性的根底上，還將鞏固對(duì)這種結(jié)構(gòu)的構(gòu)造方法的理解。 要求：在國(guó)際象棋8×8棋盤上面，按照國(guó)際象棋規(guī)如此中馬的行進(jìn)規(guī)如此，實(shí)現(xiàn)從任意初始位置，每個(gè)方格只進(jìn)入一次，走遍棋盤上全部64個(gè)方格。編制程序，求出馬的行走路線，并按求出的行走路線，將數(shù)字1，2，…，64依次填入一個(gè)8×8的方陣，并輸出它的行走路線〔棋盤如下列圖〕。 輸入：任意一個(gè)起始

2、位置； 輸出：無(wú)重復(fù)踏遍棋盤的結(jié)果，以數(shù)字1-64表示行走路線。 ? 0 1 2 3 4 5 6 7 0 ? ? 8 ? 1 ? ? ? 1 ? 7 ? ? ? 2 ? ? 2 ? ? ? H ? ? ? ? 3 ? 6 ? ? ? 3 ? ? 4 ? ? 5 ? 4 ? ? ? 5 ? ? ? ? ? ? ? ? 6 ? ? ? ? ? ? ? ? 7 ? ? ? ? ? ? ? ? 二 概要設(shè)計(jì) 為了實(shí)現(xiàn)上述程

3、序功能，可以采用順序棧或者鏈棧來(lái)存儲(chǔ)它的數(shù)據(jù)，本實(shí)驗(yàn)所需要的存儲(chǔ)空間不是很大，不需動(dòng)態(tài)的開辟很多空間，所以采用相對(duì)簡(jiǎn)單的順序棧來(lái)存儲(chǔ)數(shù)據(jù)，既方便有簡(jiǎn)單，而用鏈棧在實(shí)現(xiàn)上相比照順序棧復(fù)雜的一點(diǎn)。 2.1順序棧的抽象數(shù)據(jù)類型定義： ADT Stack{ 數(shù)據(jù)對(duì)象：D={ai| ai∈〔0，1，…，9〕，i=0,1，2，…，n，n≥0} 數(shù)據(jù)關(guān)系：R={< ai-1, ai >| ai-1, ai∈D,i=1,2，…，n} } ADT Stack 2.2本程序包含三個(gè)模塊： 1、主程序模塊： void main(){ 定義變量； 承受命令； 處理命令； 退出；

4、 } 2、起始坐標(biāo)函數(shù)模塊——馬兒在棋盤上的起始位置； 3、探尋路徑函數(shù)模塊——馬兒每個(gè)方向進(jìn)展嘗試，直到試完整個(gè)棋盤； 4、輸出路徑函數(shù)模塊——輸出馬兒行走的路徑； 2.3各模塊之間的調(diào)用關(guān)系：主程序模塊 輸入的初始位置是否正確 否 起始坐標(biāo)函數(shù)模塊 是 探尋路徑函數(shù)模塊 輸出路徑函數(shù)模塊塊

5、 完畢 三 詳細(xì)設(shè)計(jì) #include #define MAXSIZE 100 #define N 8 int board[8][8]; //定義棋盤 int Htry1[8]={1,-1,-2,2,2,1,-1,-2}; /*存儲(chǔ)馬各個(gè)出口位置相對(duì)當(dāng)前位置行下標(biāo)的增量數(shù)組*/ int Htry2[8]={2,-2,1,1,-1,-2,2,-1}; /*存儲(chǔ)馬各個(gè)出口位置相對(duì)當(dāng)前位置列下標(biāo)的增量數(shù)組*/ struct Stack{

6、 //定義棧類型 int i; //行坐標(biāo) int j; //列坐標(biāo) int director; //存儲(chǔ)方向 }stack[MAXSIZE]; //定義一個(gè)棧數(shù)組 int top=-1; //棧指針 void InitLocation(int xi,int yi); //馬兒在棋盤上的起始位置坐標(biāo) int TryPath(int i,int j); //馬兒每個(gè)方向進(jìn)展嘗試，直到試完整個(gè)棋盤 void D

7、isplay(); //輸出馬兒行走的路徑 void InitLocation(int xi,int yi) { int x,y; //定義棋盤的橫縱坐標(biāo)變量 top++; //棧指針指向第一個(gè)棧首 stack[top].i=xi; //將起始位置的橫坐標(biāo)進(jìn)棧 stack[top].j=yi; //將起始位置的縱坐標(biāo)進(jìn)棧 stack[top].director=-1; //將起始位置的嘗試方向賦初值 board[xi][yi]=t

8、op+1; //標(biāo)記棋盤 x=stack[top].i; //將起始位置的橫坐標(biāo)賦給棋盤的橫坐標(biāo) y=stack[top].j; //將起始位置的縱坐標(biāo)賦給棋盤的縱坐標(biāo) if(TryPath(x,y)) //調(diào)用馬兒探尋函數(shù)，如果馬兒探尋整個(gè)棋盤返回1否如此返回0 Display(); //輸出馬兒的行走路徑 else printf("無(wú)解"); } int TryPath(int i,int j) { int find,director

9、,number,min;//定義幾個(gè)臨時(shí)變量 int i1,j1,h,k,s; //定義幾個(gè)臨時(shí)變量 int a[8],b1[8],b2[8],d[8];//定義幾個(gè)臨時(shí)數(shù)組 while(top>-1) //棧不空時(shí)循環(huán) { for(h=0;h<8;h++) //用數(shù)組a[8]記錄當(dāng)前位置的下一個(gè)位置的可行路徑的條數(shù) { number=0; i=stack[top].i+Htry1[h]; j=stack[top].j+Htry2[h]; b1[h]=i;

10、 b2[h]=j; if(board[i][j]==0&&i>=0&&i<8&&j>=0&&j<8) //如果找到下一位置 { for(k=0;k<8;k++) { i1=b1[h]+Htry1[k]; j1=b2[h]+Htry2[k]; if(board[i1][j1]==0&&i1>=0&&i1<8&&j1>=0&&j1<8) //如果找到下一位置

11、 number++; //記錄條數(shù) } a[h]=number; //將條數(shù)存入數(shù)組a[8]中 } } for(h=0;h<8;h++) //根據(jù)可行路徑條數(shù)小到大按下表排序放入數(shù)組d[8]中 { min=9; for(k=0;k<8;k++) if(min>a[k]) { min=a[k]; d[h]=k; //將下表存入數(shù)組d[8]中 s=k

12、; } a[s]=9; } director=stack[top].director; if(top>=63) //如果走完整個(gè)棋盤返回1 return (1); find=0; //表示沒有找到下一個(gè)位置 for(h=director+1;h<8;h++) //向八個(gè)方向進(jìn)展探尋 { i=stack[top].i+Htry1[d[h]]; j=stack[top].j+Htry2[d[h]]; if(board[i][

13、j]==0&&i>=0&&i<8&&j>=0&&j<8) //如果找到下一位置 { find=1; //表示找到下一個(gè)位置 break; } } if(find==1) //如果找到下一個(gè)位置進(jìn)棧 { stack[top].director=director; //存儲(chǔ)棧結(jié)點(diǎn)的方向 top++; //棧指針前移進(jìn)棧 stack[top].i=i; stack[top].j=j; stack[top].director=-1;

14、 //重新初始化下一棧結(jié)點(diǎn)的嘗試方向 board[i][j]=top+1; //標(biāo)記棋盤 } else //否如此退棧 { board[stack[top].i][stack[top].j]=0; //去除棋盤的標(biāo)記 top--; //棧指針前移退棧 } } return (0); } void Display() { int i,j; for(i=0;i

15、0;j

16、<=y<=8)\n"); printf("Input x = "); scanf("%d",&x); //輸入起始位置的橫坐標(biāo) printf("Input y = "); scanf("%d",&y); //輸入起始位置的縱坐標(biāo) if(x>=1&&x<=8&&y>=1&&y<=8)break; printf("Your input is worng!!!\n"); } printf("begin with %d board:\n\n", 8*(x-1)+y); InitLocation(x-1,y-1);

17、 //調(diào)用起始坐標(biāo)函數(shù) } 四 調(diào)試分析 〔1〕本次實(shí)驗(yàn)的主要目的是在于掌握和理解棧的特性和它的應(yīng)用。在編制該程序中遇到了很多問題。首先，在開始剛編制程序的時(shí)候遇到的問題是，程序編譯都通不過，主要在一些細(xì)節(jié)的問題上，還有在程序的返回值在剛開始時(shí)也沒有正確返回。經(jīng)過編譯慢慢調(diào)試，編譯都能通過，沒有錯(cuò)誤和警告。 〔2〕雖然編譯都能通過，但是運(yùn)行時(shí)卻出錯(cuò)，程序不能終止，只有通過人工方式完畢程序，可能是在某些地方出現(xiàn)了無(wú)限死循環(huán)了，然后在仔細(xì)檢查代碼，發(fā)現(xiàn)沒有標(biāo)記馬兒嘗試的方向director，這樣的話，馬兒回溯的時(shí)候，下一次又有可能走那個(gè)方向，這樣就出現(xiàn)了死循環(huán)。 〔3〕標(biāo)記

18、好馬兒嘗試的方向后，編譯運(yùn)行，但是運(yùn)行結(jié)果卻不符合程序所要求的結(jié)果，說(shuō)明在算法上肯定有錯(cuò)誤，檢查發(fā)現(xiàn)，馬兒走的坐標(biāo)沒有控制后，它的橫縱坐標(biāo)必須控制0到7之間，否如此的話?cǎi)R兒就會(huì)踏出棋盤以外，這樣輸出的結(jié)果就不對(duì)。還有就是棋盤走過的位置要標(biāo)記一下，以便下次走不重復(fù)走，當(dāng)回溯的時(shí)候的記得把標(biāo)記給清掉，這個(gè)地方有時(shí)候也很容易混淆。 〔4〕還有一點(diǎn)就是，該程序運(yùn)算量大，算法復(fù)雜度高，所以運(yùn)行的時(shí)候很慢，特別占內(nèi)存，CPU的使用也很高，幾乎都在70%到90%之間，配置低了可能還運(yùn)行不了。 五 測(cè)試結(jié)果 結(jié)果1： 結(jié)果2： 六 實(shí)驗(yàn)體會(huì) 通過本次實(shí)驗(yàn)的編寫，能夠掌握

19、棧的性質(zhì)以與它的應(yīng)用。這次實(shí)驗(yàn)花了很多時(shí)間才完成，其實(shí)本應(yīng)該早完成的，在檢查的過程中有多多少少修改完美了一下，不過算法思想?yún)s沒有改變。這個(gè)程序也讓我頭疼了幾次，就是運(yùn)行速度很慢，要等很久才能輸出結(jié)果，這樣的話很占內(nèi)存資源，而且CPU的使用記錄也很高，主要是它需要的運(yùn)算太多，所以CPU 使用記錄也是很高的。雖然我也參考了一些優(yōu)化的算法，可以找到最優(yōu)路進(jìn)走，但是這些最優(yōu)算法都和棧的應(yīng)用失去了聯(lián)系，本次的實(shí)驗(yàn)主要目的就是要了解棧，所以不用棧來(lái)寫該程序就失去了該實(shí)驗(yàn)的意義。 在該程序的編制過程中留下了一些思考的問題，就是馬兒從一個(gè)起點(diǎn)位置開始探尋，最后馬兒探尋成功的路徑會(huì)不會(huì)是不只一條路徑，可能還有多條路徑，由于時(shí)間和精力的限制沒有去深究，但是這應(yīng)該值的思考的。 在用順序棧來(lái)實(shí)現(xiàn)該程序之前，也嘗試過用鏈棧來(lái)做，但是發(fā)現(xiàn)如果用鏈棧來(lái)做的話，在存儲(chǔ)調(diào)用的時(shí)候不是很方便，或許用鏈棧來(lái)做應(yīng)該是對(duì)自己的一種挑戰(zhàn)。盡管沒有用鏈棧做不過，用順尋棧來(lái)做在編制該程序中也收獲不小。 8 / 8