課程設(shè)計報告-馬踏棋盤2

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

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

3、照馬的行走規(guī)那么對棋盤進行遍歷，尋找馬的行走路徑，每 次僅訪問一個棋格，保證每個棋格都訪問到且每個棋格僅訪問一次。(4)輸出路徑函數(shù)模塊：對探尋路徑函數(shù)模塊中保存下來的順序進行輸出，輸出格式 按照棋盤8X8的方陣格式。(5)起始坐標函數(shù)模塊：將馬的起始位置坐標與棋盤坐標聯(lián)系起來，通過調(diào)用探尋路 徑函數(shù)和輸出路徑函數(shù)到達預(yù)期效果。(6)主程序模塊：主要是完成棋盤初始化，輸入，調(diào)用等任務(wù)進而來完成馬踏棋盤問 題。另外，一般來說，當馬位于(i,j)時，可以走以下8個位置之一：(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 個可能的位置可以用兩個一維數(shù)組存放，利用一維數(shù)組表示馬在棋盤內(nèi)新位置。但是，如果(x,y)靠近棋盤 的邊緣，上述位置可能超出棋盤范圍，成為不允許的位置。四、詳細設(shè)計方案及流程圖(1)定義頭文件和宏定義#includettdefine MAXSIZE 100ttdefine N 8(2)數(shù)據(jù)類型定義int board8 8;定義棋盤；int Htryl 8 = 1, -1, -2, 2, 2, 1, -1, -2；int Htry28 = 2, -2, 1, 1,-1,-2, 2,-l;Htryl8和 H宜y28分別表示馬各個出 口位置相對

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

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

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

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

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