數(shù)據(jù)結(jié)構(gòu)實驗報告馬踏棋盤

1、目 錄1 課程設計的目的x2 需求分析x3 課程設計報告內(nèi)容x1、概要設計x2、詳細設計x3、調(diào)試分析x4、用戶手冊x5、測試結(jié)果x6、程序清單x4 小結(jié) x5 參考文獻 x2011年5月23日1、 課程設計的目的（1） 熟練使用棧和隊列解決實際問題；（2） 了解并掌握數(shù)據(jù)結(jié)構(gòu)與算法的設計方法，具備初步的獨立分析和設計能力；（3） 初步掌握軟件開發(fā)過程的問題分析、系統(tǒng)設計、程序編碼、測試等基本方法和技能；（4） 提高綜合運用所學的理論知識和方法獨立分析和解決問題的能力；2、 需求分析*問題描述：將馬隨機放在國際象棋的8X8棋盤Bo阿rd0.7,0.7的某個方格中，馬按走棋規(guī)則進行移動。要求每個

2、方格上只進入一次，走遍棋盤上全部64個方格。編制非遞歸程序，求出馬的行走路線 ，并按求出的行走路線，將數(shù)字1，2，64依次填入8X8的方陣輸出之。*測試數(shù)據(jù)：由讀者指定,可自行指定一個馬的初始位置。*實現(xiàn)提示：每次在多個可走位置中選擇一個進行試探，其余未曾試探過的可走位置必須用適當結(jié)構(gòu)妥善管理，以備試探失敗時的“回溯”(悔棋)使用。并探討每次選擇位置的“最佳策略”，以減少回溯的次數(shù)。3、課程設計報告內(nèi)容根據(jù)分析先建了2個結(jié)構(gòu)體struct PosType /馬的坐標位置類型int m_row; /行值int m_col;/列值;struct DataType /棧的元素類型PosType se

3、at; /馬在棋盤中的“坐標位置” int di;/換方向的次數(shù);chess:chess()bool chess:chessPath(PosType start) /在棋盤中進行試探尋找下一步位置并同時記錄位置，以及涉及到的入棧出棧void chess:Print() /打印馬走的路徑PosType chess:NextPos(PosType a,int di)/根據(jù)當前點的位置a和移動方向di，試探下一位置4、總結(jié)一、這次課程設計的心得體會通過實踐我的收獲如下：1、鞏固和加深了對數(shù)據(jù)結(jié)構(gòu)的理解，提高綜合運用本課程所學知識的能力。2、培養(yǎng)了我選用參考書，查閱手冊及文獻資料的能力。培養(yǎng)獨立思考，

4、深入研究，分析問題、解決問題的能力。二、根據(jù)我在實習中遇到得問題，我將在以后的學習過程中注意以下幾點： 1、認真上好專業(yè)實驗課，多在實踐中鍛煉自己。2、寫程序的過程中盡量在正確的基礎上追求簡潔。3、在做設計的時候要有信心，有耐心，切勿浮躁。4、認真的學習課本知識，掌握課本中的知識點，并在此基礎上學會靈活運用，不過也不能完全依賴課本。5、在課余時間里多寫程序，熟練掌握在調(diào)試程序的過程中所遇到的常見錯誤，以便能節(jié)省調(diào)試程序的時間。 6、參考文獻（1）萬健主編，數(shù)據(jù)結(jié)構(gòu)實用教程（C+版），電子工業(yè)出版社，2011（2）網(wǎng)上搜索相關(guān)程序作為參考7、程序運行結(jié)果：附件：#include <iost

5、ream>using namespace std;#include "SqStack.h"struct PosType /馬的坐標位置類型int m_row; /行值int m_col;/列值;struct DataType /棧的元素類型PosType seat; /馬在棋盤中的“坐標位置” int di;/換方向的次數(shù);class chesspublic:chess();bool chessPath(PosType);void Print();private:PosType NextPos(PosType c , int d );int m_chess88; /

6、棋盤數(shù)組;chess:chess()int i,j;for(i=0;i<=7;i+)for(j=0;j<=7;j+)m_chessij=0;bool chess:chessPath(PosType start)SqStack<DataType> path(64); /創(chuàng)建棧PosType curpos;DataType e;curpos=start ;int curstep=1; /第幾次走的位置doif(curpos.m_row<=7 && curpos.m_row>=0 && curpos.m_col>=0 &

7、;& curpos.m_col<=7)/走在棋盤之內(nèi)if(m_chesscurpos.m_rowcurpos.m_col=0)m_chesscurpos.m_rowcurpos.m_col=curstep; /留下足跡，標注當前位置是馬第幾次走e.seat.m_row=curpos.m_row; e.seat.m_col=curpos.m_col;e.di=0;path.Push(e); /當前位置和方向入棧curstep+;if(curstep=65)return true;curpos=NextPos(curpos,e.di); elsecurpos=NextPos(curp

8、os,e.di+); /在棋盤之外自動進行下一次試探else /當前位置已走過if(!path.Empty()e=path.Top();path.Pop();curstep-;while(e.di=7 && !path.Empty() /該位置已無路可走m_chesse.seat.m_rowe.seat.m_col=0; e=path.Top();/退回一步path.Pop();curstep-;if(e.di<7) /沒到可能的最后一個位置e.di+; /換下一個位置path.Push(e);curstep+;curpos=NextPos(e.seat,e.di);wh

9、ile(curstep<=64); /馬已經(jīng)走的步數(shù)return false;void chess:Print()int i,j;for(i=0;i<8;i+)for(j=0;j<8;j+)cout<<m_chessij<<'t' /輸出對齊，水平制表cout<<endl;cout<<endl;PosType chess:NextPos(PosType a,int di)/根據(jù)當前點的位置a和移動方向di，試探下一位置PosType direct8=2,1,1,2,-1,2,-2,1,-2,-1,-1,-2,1,

10、-2,2,-1;/按照順時針試探的8個位置a.m_row+=directdi.m_row;a.m_col+=directdi.m_col;return a;void main()PosType first;chess chess;cout<<"請輸入馬的初始位置（第幾行第幾列):"cin>>first.m_row>>first.m_col;chess.chessPath(first);cout<<"馬走過的一條路徑如下："<<endl; chess.Print(); #define _SQSTA

11、CK_H_/定義順序棧類template <class ElemType>/聲明一個類模板class SqStackpublic: /順序棧類的各成員函數(shù)SqStack(int m = 100); SqStack(); void Clear();bool Empty() const; int Length() const; ElemType & Top() const; void Push(const ElemType &e); void Pop();private: /順序棧類的數(shù)據(jù)成員 ElemType *m_base; /基地址指針 int m_top; /棧

12、頂指針int m_size; /向量空間大小;/構(gòu)造函數(shù)，分配m個結(jié)點的順序空間，構(gòu)造一個空的順序棧。template <class ElemType>SqStack <ElemType>:SqStack(int m)m_top = 0;m_base = new ElemTypem;m_size = m;/SqStack/析構(gòu)函數(shù)，將棧結(jié)構(gòu)銷毀。template <class ElemType>SqStack <ElemType>:SqStack()if (m_base != NULL) delete m_base;/SqStack/清空棧。te

13、mplate <class ElemType>void SqStack <ElemType>:Clear()m_top = 0;/Clear/判棧是否為空，若為空，則返回true，否則返回false。template <class ElemType>bool SqStack <ElemType>:Empty() constreturn m_top = 0;/Empty/求棧的長度。template <class ElemType>int SqStack <ElemType>:Length() constreturn m_t

14、op;/Length/取棧頂元素的值。先決條件是棧不空。template <class ElemType>ElemType & SqStack <ElemType>:Top() constreturn m_basem_top - 1;/Top/入棧，若棧滿，則先擴展空間。插入e到棧頂。template <class ElemType>void SqStack <ElemType>:Push(const ElemType &e) if(m_top >= m_size)/若棧滿，則擴展空間。 ElemType *newbase; newbase = new ElemTypem_size +