馬踏棋盤分析文檔

《馬踏棋盤分析文檔》由會員上傳分享，免費在線閱讀，更多相關(guān)內(nèi)容在工程資料-天天文庫。

1、數(shù)據(jù)結(jié)構(gòu)課程設(shè)計題目：馬踏棋盤院系：班級：學號：姓名：2014-2015年度第1學期馬踏棋盤一.題目：馬踏棋盤3二.設(shè)計目標3三?問題描述3四.需求分析4五.概要設(shè)計4第?步：定義四個常量和?個數(shù)據(jù)類型4第二步：構(gòu)造函數(shù)4六.詳細設(shè)計（給出算法的偽碼描述和流程圖）5流程圖設(shè)計5代碼分析9第一步：定義常量與變量9第二步：構(gòu)造函數(shù)9?定義一個結(jié)構(gòu)體類型9?倉U建一個初始化函數(shù)10?創(chuàng)建提示輸入函數(shù)10?創(chuàng)建產(chǎn)生新節(jié)點函數(shù)11?創(chuàng)建計算路徑函數(shù)12?創(chuàng)建入棧函數(shù)13?創(chuàng)建出棧函數(shù)13?創(chuàng)建輸出函數(shù)13第二步：在主函數(shù)屮調(diào)用其它函數(shù)15七測試分析16八.使用說明16九?測試數(shù)據(jù)16十.課程設(shè)計總結(jié)

2、17一.題目：馬踏棋盤二.設(shè)計目標幫助學生熟練掌握順序棧的基本操作，讓學生深入了解棧的使用，使得更深層次的靈活運用棧。三.問題描述（?謂的馬踏棋盤是：將馬隨機放在國際象棋的8X8棋盤的某個方格中，馬按走棋規(guī)則（馬走日字）進行移動。要求每個方格只進入一次，走遍棋盤上全部64個方格。由用戶自行指定一個馬的初始位置，求出馬的行走路線，并按照求出的行走路線的順序，將數(shù)字1、2、…、64依次填入一個8X8的方陣并輸出。從用戶給出的初始位置開始判斷，按照順時針順序，每次產(chǎn)生一個新的路點，并驗證此路點的可用性，需要考慮的是當前路點是否超出棋盤范圍和此路點是否已經(jīng)走過。如果新路點可用，則入棧，并執(zhí)行下一步

3、，重復進行如上步驟，每次按照已走路點的位置生成新路點。如果一個路點的可擴展路數(shù)為0,進行回溯，直到找到一個馬能踏遍棋盤的行走路線并輸出。1-需求分析1.讓用戶輸入馬的初始位置；2.按照馬的行走路線，判斷馬是否能夠走遍整個棋盤；3.輸出結(jié)果（若能走遍，則輸出馬的行走路線，若不能，提示用戶“此時不能踏遍棋盤上所有點！”）五.概要設(shè)計為了實現(xiàn)上述程序功能，程序包含以下幾大模塊:第一步：定義四個常量和一個數(shù)據(jù)類型:MAXNUM、INVALIDDIR、MAXLEN、MAXDIR、HorsePoint第二步：構(gòu)造函數(shù)：voidInitial0//初始化函數(shù)；voidPushStack(HorsePoi

4、ntpositon)//入才戔函數(shù)；HorsePointGetlnitPointO//請求用戶輸入函數(shù)；HorsePointGetNewPoint但orscPoint^parent)//產(chǎn)生新節(jié)點函數(shù)；voidCalcPoint(HorsePointhh)//計算路徑的函數(shù);voidPrintChessO//輸出函數(shù)；intmain(intarge,char*argv[])//主函數(shù)五.詳細設(shè)計（給出算法的偽碼描述和流程圖）總體操作步驟如下：流程圖設(shè)計：o&jsta【e三=K1O蘇莊sOTre三三輸出“此時不能踏遍棋盤上所有.nf風代碼分析:第一步：定義常量與變量:常量：/*橫縱格數(shù)的最大

5、值*/MAXNUM8——INVAIJDDIR-1/*無路可走的情況*/MAXLKN64/*棋盤總個數(shù)*/MAXDIR8/*下一步可走的方向*/變量：HorscPointChcssPath[MAXLKN]/*模擬路徑棧*/Intcount/*入棧節(jié)點個數(shù)*/intChcssBoard[MAXNUM][MAXNUM]/*標志棋盤數(shù)組*/第二步：構(gòu)造函數(shù)：?為了明確馬將要走的路線，我們必須定義一個結(jié)構(gòu)體類型：typedefstruct{intx;/*表示橫坐標*/inty;/*表示縱坐標*/intdirection;/*表示移動方向*/}HorsePoint;?創(chuàng)建一個初始化函數(shù):voidIni

6、tialQintij;for(i=O;i

7、f(Hn);}while(positon.x>=MAXNUM

8、

9、positon.y>=MAXNUM

10、

11、positon.x<0

12、

13、positon.y<0);/*不超過各個邊緣時*//*是初值，沒走過positon.direction=INVALIDDIR;*/returnpositon;}?創(chuàng)建產(chǎn)生新節(jié)點函數(shù)：HorsePointGetNewPoint(HorsePoint^parent)inti;HorsePoi