課程設(shè)計(jì)報(bào)告-馬踏棋盤(pán)2

1、合肥老浣必靠機(jī)科學(xué)與技術(shù)系課程設(shè)計(jì)報(bào)告20122013 學(xué)年第二學(xué)期2013一、課程設(shè)計(jì)目的“數(shù)據(jù)結(jié)構(gòu)與算法課程設(shè)計(jì)”是計(jì)算機(jī)科學(xué)與技術(shù)專(zhuān)業(yè)學(xué)生的集中實(shí)踐性環(huán)節(jié)之一，是 學(xué)習(xí)“數(shù)據(jù)結(jié)構(gòu)與算法”理論和實(shí)驗(yàn)課程后進(jìn)行的一次全面的綜合練習(xí)。其目的是要到達(dá)理 論與實(shí)際應(yīng)用相結(jié)合，提高學(xué)生組織數(shù)據(jù)及編寫(xiě)程序的能力，使學(xué)生能夠根據(jù)問(wèn)題要求和數(shù) 據(jù)對(duì)象的特性，學(xué)會(huì)數(shù)據(jù)組織的方法，把現(xiàn)實(shí)世界中的實(shí)際問(wèn)題在計(jì)算機(jī)內(nèi)部表示出來(lái)并用 軟件解決問(wèn)題，培養(yǎng)良好的程序設(shè)計(jì)技能。二、課程設(shè)計(jì)名稱(chēng)及內(nèi)容名稱(chēng)：馬踏棋盤(pán)內(nèi)容：將馬隨機(jī)放在國(guó)際象棋的8義8棋盤(pán)的某個(gè)方格中，馬按照走棋的規(guī)那么進(jìn)行移動(dòng)。 每個(gè)方格只進(jìn)入一次，走遍棋盤(pán)

2、的全部64個(gè)方格。編寫(xiě)算法，求出馬的行走路線，并按求 出的行走路線，將1,2,64依次填入一個(gè)8X8的方陣，并輸出。三、數(shù)據(jù)結(jié)構(gòu)的選擇和概要設(shè)計(jì)根據(jù)需求分析可知，我們所設(shè)計(jì)的程序要到達(dá)讓馬從任意一起點(diǎn)出發(fā)都不重復(fù)地遍歷所 有的8X8棋格的功能。按照需求，并考慮到程序的可讀性，我們按順序共設(shè)計(jì)了以下六大 模塊：(1)定義頭文件和宏定義模塊：這是C程序必不可少的一個(gè)局部，通過(guò)頭文件來(lái)調(diào)用 程序所需庫(kù)函數(shù)，而通過(guò)宏定義進(jìn)行宏替換。(2)數(shù)據(jù)類(lèi)型定義模塊：該模塊定義了全局?jǐn)?shù)據(jù)結(jié)構(gòu)，它們的作用域?yàn)閺亩x開(kāi)始到 根源文件結(jié)束，以便于讓后面很多函數(shù)都可以用到它們，而不必再重新定義。(3)探尋路徑函數(shù)模塊：按

3、照馬的行走規(guī)那么對(duì)棋盤(pán)進(jìn)行遍歷，尋找馬的行走路徑，每 次僅訪問(wèn)一個(gè)棋格，保證每個(gè)棋格都訪問(wèn)到且每個(gè)棋格僅訪問(wèn)一次。(4)輸出路徑函數(shù)模塊：對(duì)探尋路徑函數(shù)模塊中保存下來(lái)的順序進(jìn)行輸出，輸出格式 按照棋盤(pán)8X8的方陣格式。(5)起始坐標(biāo)函數(shù)模塊：將馬的起始位置坐標(biāo)與棋盤(pán)坐標(biāo)聯(lián)系起來(lái)，通過(guò)調(diào)用探尋路 徑函數(shù)和輸出路徑函數(shù)到達(dá)預(yù)期效果。(6)主程序模塊：主要是完成棋盤(pán)初始化，輸入，調(diào)用等任務(wù)進(jìn)而來(lái)完成馬踏棋盤(pán)問(wèn) 題。另外，一般來(lái)說(shuō)，當(dāng)馬位于(i,j)時(shí)，可以走以下8個(gè)位置之一：(i-2, j+1) (i-1, j+2) (i+1, j+2) (i+2, j+1)1、(i+2, j-1) (i+1, j

4、-2) (i-1, j-2)(i-2, j-1)這 8 個(gè)可能的位置可以用兩個(gè)一維數(shù)組存放，利用一維數(shù)組表示馬在棋盤(pán)內(nèi)新位置。但是，如果(x,y)靠近棋盤(pán) 的邊緣，上述位置可能超出棋盤(pán)范圍，成為不允許的位置。四、詳細(xì)設(shè)計(jì)方案及流程圖(1)定義頭文件和宏定義#includettdefine MAXSIZE 100ttdefine N 8(2)數(shù)據(jù)類(lèi)型定義int board8 8;定義棋盤(pán)；int Htryl 8 = 1, -1, -2, 2, 2, 1, -1, -2；int Htry28 = 2, -2, 1, 1,-1,-2, 2,-l;Htryl8和 H宜y28分別表示馬各個(gè)出 口位置相對(duì)

5、當(dāng)前位置的橫坐標(biāo)和縱坐標(biāo)的增量數(shù)組；struct Stack(int i;int j;int director;stackMAXSIZE;int top=-l;這里是定義棧類(lèi)型，其中i是橫坐標(biāo)，j是縱坐標(biāo)，director是 存儲(chǔ)方向，stackMAXSIZE表示定義一個(gè)棧數(shù)組，top=-l表示棧指針，可以存儲(chǔ)棋盤(pán)上的 信息以及棧中元素移動(dòng)情況。(3)主函數(shù)在mainO函數(shù)中，我們通過(guò)一個(gè)雙重for循環(huán)控制棋盤(pán)的橫縱坐標(biāo)完成了對(duì)棋盤(pán)的初始 化，在通過(guò)一個(gè)三個(gè)表達(dá)式都為空的for循環(huán)來(lái)控制輸入正確的橫縱坐標(biāo)，直到輸入正確才 跳出循環(huán)在執(zhí)行下面的語(yǔ)句，最后通過(guò)調(diào)用InitLocation(int

6、xi, int yi)函數(shù)完整了整個(gè) 馬踏棋盤(pán)問(wèn)題。(4)探尋路徑函數(shù)定義一個(gè)TryPath(int i, int j)函數(shù)來(lái)探尋馬的行走路徑，此函數(shù)通過(guò)while (top-l) 語(yǔ)句將程序控制在棧不為空的情況下進(jìn)行循環(huán)，在while循環(huán)中，首先通過(guò)一個(gè)雙重for 循環(huán)記錄下當(dāng)前位置的下一個(gè)位置的可行路徑條數(shù),在通過(guò)一個(gè)雙重for循環(huán)將前面可行路 徑條數(shù)從小到大排序存儲(chǔ)在數(shù)組中，最后通過(guò)一個(gè)for循環(huán)來(lái)向8個(gè)方向進(jìn)行探尋。(5)輸出路徑函數(shù)定義一個(gè)Display。函數(shù)來(lái)按照棋盤(pán)格式輸出馬的探尋路徑，此函數(shù)通過(guò)一個(gè)雙重for 循環(huán)來(lái)實(shí)現(xiàn)的，外循環(huán)控制橫坐標(biāo)的增加，內(nèi)循環(huán)控制縱坐標(biāo)的增加。(6)

7、起始坐標(biāo)函數(shù)定義一個(gè)InitLocation(int xi, int yi)函數(shù)將馬的行走路徑與棋盤(pán)坐標(biāo)聯(lián)系起來(lái)到達(dá) 預(yù)期效果，此函數(shù)是通過(guò)棧將馬的起始位置與棋盤(pán)坐標(biāo)聯(lián)系起來(lái)的，并且調(diào)用了 TryPath(int i, int j)函數(shù)和 Display ()函數(shù)。時(shí)間復(fù)雜度分析：在main。函數(shù)中，棋盤(pán)初始化的時(shí)間復(fù)雜度為0 (M2),接著經(jīng)過(guò)一 個(gè)for循環(huán)，其時(shí)間復(fù)雜度為0 (1),再往下調(diào)用InitLocation(xT,y-l)函數(shù)時(shí)，要經(jīng)過(guò) 一個(gè)while(topT),在while循環(huán)中還有雙重for循環(huán)，因此時(shí)間復(fù)雜度比擬大，故總的 時(shí)間復(fù)雜度也比擬大。（7）流程圖開(kāi)始v錄入橫坐

8、標(biāo)x= 1 &x= 1 &y=8探索路徑lllll5、測(cè)試結(jié)果及其分析:KM XX X X X X X X X X 馬踏xxxxxxxxxxxxxxPlease input importpoint1 =x =8 and l=y請(qǐng)輸入起始位置的橫坐標(biāo)x = 3輸入起始位置的縱坐標(biāo)y = 1begin viith 17board：37239184944120321736340195051383348355221421631625344476516312453461544322301564554625607115613289582326142910572427859Press any key to

9、continue圖2首先就輸入正確的初始位置橫縱坐標(biāo)的運(yùn)行結(jié)果結(jié)果2：* 馬 區(qū)沓xy w.xxPlease input importpoint1 =x =8 and l=y請(qǐng)輸入起始位置的橫坐標(biāo)x = 3輸入起始位置的縱坐標(biāo)y = 9Vour input is worng? ? ?Please input inportpo int1 =x =8 and l=y請(qǐng)輸入起始位置的橫坐標(biāo)x = 3輸入起始位置的縱坐標(biāo)y = 4begin with 20 board：245316132235181115223541?1221365225141345710193326350552037582651303364495693144562294059384627643486184154447287423960Press any key to continue圖3首先就輸入錯(cuò)誤的初始位置橫縱坐標(biāo)的運(yùn)行結(jié)果6、用戶使用說(shuō)明運(yùn)行環(huán)境：(1) WINDOWS/XP系統(tǒng)