數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)馬踏棋盤

1、數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)報(bào)告設(shè)計(jì)題目： 馬踏棋盤院 系 計(jì)算機(jī)學(xué)院 年 級(jí) 11 級(jí) 學(xué) 生 xxxxxxx 學(xué) 號(hào) xxxxxxxxx 指導(dǎo)教師 xxxxxxxxx 起止時(shí)間 9-6/9-13 2013年9月10日星期二目 錄一、 課程設(shè)計(jì)目的 -3二、 需求分析-3三、程序源代碼- 4四、調(diào)試分析-7五、問題總結(jié)-8六、參考資料-9 一、 課程設(shè)計(jì)目的(1) 熟練使用 c 語言編寫程序，解決實(shí)際問題;(2) 了解并掌握數(shù)據(jù)結(jié)構(gòu)與算法的設(shè)計(jì)方法，具備初步的獨(dú)立分析和設(shè)計(jì)能力;(3) 初步掌握軟件開發(fā)過程的問題分析、系統(tǒng)設(shè)計(jì)、程序編碼、測(cè)試等基本方法和技能;(4) 提高綜合運(yùn)用所學(xué)的理論知識(shí)和方法獨(dú)立

2、分析和解決問題的能力; 二、 需求分析問題描述:將馬隨機(jī)放在國際象棋的 8x8 棋盤中的某個(gè)方格中，馬按走棋規(guī)則進(jìn)行移動(dòng)。要求每個(gè)方格上只進(jìn)入一次，走遍棋盤上全部 64 個(gè)方格。編制遞歸程序，求出馬的行走路線 ，并按求出的行走路線，將數(shù)字 1，2，64 依次填入 8x8 的方陣輸出之。測(cè)試數(shù)據(jù):由讀者指定可自行指定一個(gè)馬的初始位置。實(shí)現(xiàn)提示:每次在多個(gè)可走位置中選擇一個(gè)進(jìn)行試探，其余未曾試探過的可走位置必須用適當(dāng)結(jié)構(gòu)妥善管理，以備試探失敗時(shí)的“回溯”悔棋使用。并探討每次選擇位置的“最佳策略”，以減少回溯的次數(shù)。背景介紹：國際象棋為許多令人著迷的娛樂提供了固定的框架，而這些框架常獨(dú)立于游戲本身。

3、其中的許多框架都基于騎士奇異的l型移動(dòng)規(guī)則。一個(gè)經(jīng)典的例子是騎士漫游問題。從十八世紀(jì)初開始，這個(gè)問題就引起了數(shù)學(xué)家和解密愛好者的注意。簡(jiǎn)單地說，這個(gè)問題要求從棋盤上任一個(gè)方格開始按規(guī)則移動(dòng)騎士，使之成功的游歷國際象棋棋盤的64個(gè)方格，且每個(gè)方格都接觸且僅接觸一次?？梢杂靡环N簡(jiǎn)便的方法表示問題的一個(gè)解，即將數(shù)字1，64按騎士到達(dá)的順序依次放入棋盤的方格中。一種非常巧妙的解決騎士漫游地方法由j.c.warnsdorff于1823年給出。他給出的規(guī)則是：騎士總是移向那些具有最少出口數(shù)且尚未到達(dá)的方格之一。其中出口數(shù)是指通向尚未到達(dá)方格的出口數(shù)量。在進(jìn)一步的閱讀之前，你可以嘗試?yán)脀arnsdorff

4、規(guī)則手工構(gòu)造出該問題的一個(gè)解。實(shí)習(xí)任務(wù)：編寫一個(gè)程序來獲得馬踏棋盤即騎士漫游問題的一個(gè)解。您的程序需要達(dá)到下面的要求：棋盤的規(guī)模是8*8；對(duì)于任意給定的初始化位置進(jìn)行試驗(yàn)，得到漫游問題的解；對(duì)每次實(shí)驗(yàn)，按照棋盤矩陣的方式，打印每個(gè)格被行徑的順序編號(hào)。技術(shù)提示：解決這類問題的關(guān)鍵是考慮數(shù)據(jù)在計(jì)算機(jī)中的存儲(chǔ)表示。可能最自然的表示方法就是把棋盤存儲(chǔ)在一個(gè)8*8的二維數(shù)組board中。以(x,y)為起點(diǎn)時(shí)騎士可能進(jìn)行的八種移動(dòng)。一般來說，位于(x,y)的騎士可能移動(dòng)到以下方格之一：(x-2,y+1)、(x-1,y+2)、(x+1,y+2)、(x+2,y+1)、(x+2,y-1)、(x+1,y-2)、(

5、x-1,y-2)、(x-2,y-1)。但請(qǐng)注意，如果(x,y)的位置離某一條邊較近，有些可能的移動(dòng)就會(huì)把騎士移到棋盤之外，而這當(dāng)然是不允許的。騎士的八種可能的移動(dòng)可以用一個(gè)數(shù)組moveoffset方便地表示出來：moveoffset0=(-2,1)moveoffset1=(-1,2)moveoffset2=(1,2)moveoffset3=(2,1)moveoffset4=(2,-1)moveoffset5=(1,-2)moveoffset6=(-1,-2)moveoffset7=(-2,-1)于是，位于(x,y)的騎士可以移動(dòng)到(x+moveoffsetk.x, y+moveoffsetk.

6、y)，其中k是0到7之間的某個(gè)整數(shù)值，并且新方格必須仍位于棋盤上。擴(kuò)展需求：可以考慮將結(jié)果圖形化。(b)考察所有初始化的情況，測(cè)試是否都能夠得到解。三、程序源代碼#include#include#define maxsize 100#define n 8int board88; /定義棋盤int htry18=1,-1,-2,2,2,1,-1,-2; /*存儲(chǔ)馬各個(gè)出口位置相對(duì)當(dāng)前位置行下標(biāo)的增量數(shù)組*/int htry28=2,-2,1,1,-1,-2,2,-1; /*存儲(chǔ)馬各個(gè)出口位置相對(duì)當(dāng)前位置列下標(biāo)的增量數(shù)組*/struct stack /定義棧類型 int i; /行坐標(biāo)int j;

7、 /列坐標(biāo) int director; /存儲(chǔ)方向stackmaxsize; /定義一個(gè)棧數(shù)組int top=-1; /棧指針void initlocation(int xi,int yi); /馬在棋盤上的起始位置坐標(biāo)int trypath(int i,int j); /在每個(gè)方向進(jìn)行嘗試，直到試完整個(gè)棋盤void display(); /輸出行走的路徑void initlocation(int xi,int yi)int x,y; /定義棋盤的橫縱坐標(biāo)變量top+; /棧指針指向第一個(gè)棧首stacktop.i=xi; /將起始位置的橫坐標(biāo)進(jìn)棧stacktop.j=yi; /將起始位置的縱坐

8、標(biāo)進(jìn)棧stacktop.director=-1; /將起始位置的嘗試方向賦初值boardxiyi=top+1; /標(biāo)記棋盤x=stacktop.i; /將起始位置的橫坐標(biāo)賦給棋盤的橫坐標(biāo)y=stacktop.j; /將起始位置的縱坐標(biāo)賦給棋盤的縱坐標(biāo)if(trypath(x,y) /調(diào)用馬探尋函數(shù)，如果馬探尋整個(gè)棋盤返回1否則返回0display(); /輸出馬的行走路徑else printf(無解); int trypath(int i,int j)int find,director,number,min; /臨時(shí)變量int i1,j1,h,k,s; /臨時(shí)變量int a8,b18,b28,

9、d8; /臨時(shí)數(shù)組while(top-1) /棧不空時(shí)循環(huán)for(h=0;h=0&i=0&j8) /如果找到下一位置for(k=0;k=0&i1=0&j18) /如果找到下一位置 number+; /記錄條數(shù) ah=number; /將條數(shù)存入數(shù)組a8中 for(h=0;h8;h+) /根據(jù)可行路徑條數(shù)小到大按下表排序放入數(shù)組d8中min=9; for(k=0;kak) min=ak; dh=k; /將下表存入數(shù)組d8中 s=k; as=9; director=stacktop.director; if(top=63) /若走完整個(gè)棋盤返回1return (1);find=0; /沒有找到下一

10、個(gè)位置for(h=director+1;h=0&i=0&j8) /如果找到下一位置find=1; /表示找到下一個(gè)位置break;if(find=1) /如果找到下一個(gè)位置進(jìn)棧stacktop.director=director; /存儲(chǔ)棧結(jié)點(diǎn)的方向 top+; /棧指針前移進(jìn)棧stacktop.i=i;stacktop.j=j;stacktop.director=-1; /重新初始化下一棧結(jié)點(diǎn)的嘗試方向boardij=top+1; /標(biāo)記棋盤else /否則退棧boardstacktop.istacktop.j=0; /清除棋盤的標(biāo)記top-; /棧指針前移退棧return (0); voi

11、d display()system(color 1e); int i,j; for(i=0;in;i+)for(j=0;jn);printf(n);printf(歡迎進(jìn)入騎士漫游小游戲! n);printf(n);int i,j;int x,y;for(i=0;in;i+) /初始化棋盤 for(j=0;j.請(qǐng)輸入初始位置坐標(biāo)(x,y) 注:(1,1)-(8,8)n);printf(input x = );scanf(%d,&x); /輸入起始位置的橫坐標(biāo)printf(input y = );scanf(%d,&y); /輸入起始位置的縱坐標(biāo)if(x=1&x=1&y=8)break;printf(n輸入有誤,請(qǐng)重新輸入!nn);printf(騎士從第%d行，第%d列開始漫游:n,x,y);initlocation(x-1,y-1); /調(diào)用起始坐標(biāo)函數(shù)四、調(diào)試分析1. 開始界面2.輸入坐標(biāo)五、問題總結(jié)此次數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)我組設(shè)計(jì)的是一個(gè)利用棧遞歸得到的馬踏遍棋盤的演示程序，剛看題目時(shí)候覺得還比較困難，根本沒一點(diǎn)思緒，但通過在網(wǎng)上查找相關(guān)資料，對(duì)這個(gè)問題才有了一定的思緒。在組員的分工合作中，我們終于把程序?qū)懗鰜砹?。在這個(gè)過程中，我收獲頗多，不僅理論知識(shí)掌握的更牢，實(shí)際動(dòng)手能力也