馬踏棋盤(pán)報(bào)告

本文格式為Word版，下載可任意編輯——馬踏棋盤(pán)報(bào)告馬踏棋盤(pán)試驗(yàn)報(bào)告

張冰22920232203923

一、試驗(yàn)?zāi)康?/p>

（1）、理解棧的特性“后進(jìn)先出〞。（2）、僅僅認(rèn)識(shí)到棧和隊(duì)列是兩種特別的線性表是遠(yuǎn)遠(yuǎn)不夠的，本次試驗(yàn)的目的在于更深入的了解棧和隊(duì)列的特性，以便在實(shí)際問(wèn)題背景下靈活運(yùn)用他們。

（3）、在了解他特性的基礎(chǔ)上，還將穩(wěn)定對(duì)這種結(jié)構(gòu)的構(gòu)造方法的理解。

二、試驗(yàn)內(nèi)容

（1）、要求：在國(guó)際象棋8×8棋盤(pán)上面，依照國(guó)際象棋規(guī)則中馬的行進(jìn)規(guī)則，實(shí)現(xiàn)從任意初始位置，每個(gè)方格只進(jìn)入一次，走遍棋盤(pán)上全部64個(gè)方格。編制程序，求出馬的行走路線，并按求出的行走路線，將數(shù)字1，2，?，64依次填入一個(gè)8×8的方陣，并輸出它的行走路線（棋盤(pán)如下圖）。

（2）、輸入：任意一個(gè)起始位置；

輸出：無(wú)重復(fù)踏遍棋盤(pán)的結(jié)果，以數(shù)字1-64表示行走路線。

01234567

（3）、數(shù)據(jù)結(jié)構(gòu)要求：采用順序棧實(shí)現(xiàn)。

01762853H41452367三、試驗(yàn)步驟

為了實(shí)現(xiàn)上述程序功能，可以采用順序棧或者鏈棧來(lái)存儲(chǔ)它的數(shù)據(jù)，本試驗(yàn)所需要的存儲(chǔ)空間不是很大，不需動(dòng)態(tài)的開(kāi)拓好多空間，所以采用相對(duì)簡(jiǎn)單的順序棧來(lái)存儲(chǔ)數(shù)據(jù)，既便利有簡(jiǎn)單。

（一）、概要設(shè)計(jì)

（1）、順序棧的抽象數(shù)據(jù)類型定義：ADTStack{

數(shù)據(jù)對(duì)象：D={ai|ai∈（0，1，?，9），i=0,1，2，?，n，n≥0}數(shù)據(jù)關(guān)系：R={|ai-1,ai∈D,i=1,2，?，n}}ADTStack

（2）本程序包含三個(gè)模塊：

1、主程序模塊：voidmain(){

定義變量；接受命令；處理命令；退出；}

2、起始坐標(biāo)函數(shù)模塊——馬兒在棋盤(pán)上的起始位置；

3、探尋路徑函數(shù)模塊——馬兒每個(gè)方向進(jìn)行嘗試，直到試完整個(gè)棋盤(pán)；4、輸出路徑函數(shù)模塊——輸出馬兒行走的路徑；

（二）、詳細(xì)設(shè)計(jì)

（1）、定義頭文件和預(yù)定義#include#defineMAXSIZE100#defineN8（2）、數(shù)據(jù)類型定義

intboard[8][8];//定義棋盤(pán)intHtry1[8]={1,-1,-2,2,2,1,-1,-2};

/*存儲(chǔ)馬各個(gè)出口位置相對(duì)當(dāng)前位置行下標(biāo)的增量數(shù)組*/

intHtry2[8]={2,-2,1,1,-1,-2,2,-1};

/*存儲(chǔ)馬各個(gè)出口位置相對(duì)當(dāng)前位置列下標(biāo)的增量數(shù)組*/

structStack{//定義棧類型inti;//行坐標(biāo)intj;//列坐標(biāo)intdirector;//存儲(chǔ)方向

}stack[MAXSIZE];//定義一個(gè)棧數(shù)組inttop=-1;//棧指針

（3）、函數(shù)聲明

voidInitLocation(intxi,intyi);//馬兒在棋盤(pán)上的起始位置坐標(biāo)

intTryPath(inti,intj);//馬兒每個(gè)方向進(jìn)行嘗試，直到試完整個(gè)棋盤(pán)

voidDisplay();//輸出馬兒行走的路徑

（4）、起始坐標(biāo)函數(shù)模塊

voidInitLocation(intxi,intyi){

intx,y;//定義棋盤(pán)的橫縱坐標(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]=top+1;//標(biāo)記棋盤(pán)

x=stack[top].i;//將起始位置的橫坐標(biāo)賦給棋盤(pán)的橫坐標(biāo)y=stack[top].j;//將起始位置的縱坐標(biāo)賦給棋盤(pán)的縱坐標(biāo)

if(TryPath(x,y))//調(diào)用馬兒探尋函數(shù)，假使馬兒探尋整個(gè)棋盤(pán)返回1否則返回0

Display();//輸出馬兒的行走路徑else

printf(\無(wú)解\}

（5）、探尋路徑函數(shù)模塊intTryPath(inti,intj){

intfind,director,number,min;//定義幾個(gè)臨時(shí)變量inti1,j1,h,k,s;//定義幾個(gè)臨時(shí)變量inta[8],b1[8],b2[8],d[8];//定義幾個(gè)臨時(shí)數(shù)組while(top>-1)//棧不空時(shí)循環(huán){

for(h=0;ha[k]){

min=a[k];

d[h]=k;//將下表存入數(shù)組d[8]中s=k;}

a[s]=9;}

director=stack[top].director;

if(top>=63)//假使走完整個(gè)棋盤(pán)返回1return(1);

find=0;//表示沒(méi)有找到下一個(gè)位置for(h=director+1;h=1printf(\}

printf(\InitLocation(x-1,y-1);//調(diào)用起始坐標(biāo)函數(shù)}

四、調(diào)試分析

（1）、本次試驗(yàn)的主要目的是在于把握和理解棧的特性和它的應(yīng)用。在編制該程序中遇到了好多問(wèn)題。首先，在開(kāi)始剛編制程序的時(shí)候遇到的問(wèn)題是，程序編譯都通不過(guò)，主要在一些細(xì)節(jié)的問(wèn)題上，還有在程序的返回值在剛開(kāi)始時(shí)也沒(méi)有正確返回。經(jīng)過(guò)編譯漸漸調(diào)試，

編譯都能通過(guò)，沒(méi)有錯(cuò)誤和警告。

（2）、雖然編譯都能通過(guò)，但是運(yùn)行時(shí)卻出錯(cuò)，程序不能終止，只有通過(guò)人工方式終止程序，可能是在某些地方出現(xiàn)了無(wú)限死循環(huán)了，然后在細(xì)心檢查代碼，發(fā)現(xiàn)沒(méi)有標(biāo)記馬兒嘗試的方向director，這樣的話，馬兒回溯的時(shí)候，下一次又有可能走那個(gè)方向，這樣就出現(xiàn)了死循環(huán)。

（3）、標(biāo)記好馬兒嘗試的方向后，編譯運(yùn)行，但是運(yùn)行結(jié)果卻不符合程序所要求的結(jié)果，說(shuō)明在算法上確定有錯(cuò)誤，檢查發(fā)現(xiàn)，馬兒走的坐標(biāo)沒(méi)有控制后，它的橫縱坐標(biāo)必需控制0到7之間，否則的話?cǎi)R兒就會(huì)踏出棋盤(pán)以外，這樣輸出的結(jié)果就不對(duì)。還有就是棋盤(pán)走過(guò)的位置要標(biāo)記一下，以便下次走不重復(fù)走，當(dāng)回溯的時(shí)候的記得把標(biāo)記給清掉，這個(gè)地方有時(shí)候也很簡(jiǎn)單混淆。

五、運(yùn)行結(jié)果

六、試驗(yàn)體會(huì)

通過(guò)本次試驗(yàn)的編寫(xiě)，能夠把握棧的性質(zhì)以及它的應(yīng)用。這次試驗(yàn)花了好多時(shí)間才完成，其實(shí)本應(yīng)當(dāng)早完成的，在檢查的過(guò)程中有多多少少修改完美了一下，不過(guò)算法思想?yún)s沒(méi)有改變。這個(gè)程序也讓我頭疼了幾次，就是運(yùn)行速度很慢，要等很久才能輸出結(jié)果，這樣的話很占內(nèi)存資源，而且CPU的使用記錄也很高，主要是它需要的運(yùn)算太多，所以CPU使用記錄也是很高的。雖然我也參考了一些優(yōu)化的算法，可以找到最優(yōu)路進(jìn)走，但是這些最優(yōu)算法都和棧的應(yīng)用失去了聯(lián)系，本次的試驗(yàn)主要目的就是要了解棧，