數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)報(bào)告馬踏棋盤

1、目 錄1 課程設(shè)計(jì)的目的x2 需求分析x3 課程設(shè)計(jì)報(bào)告內(nèi)容x1、概要設(shè)計(jì)x2、詳細(xì)設(shè)計(jì)x3、調(diào)試分析x4、用戶手冊(cè)x5、測(cè)試結(jié)果x6、程序清單x4 小結(jié) x5 參考文獻(xiàn) x2011年5月23日1、 課程設(shè)計(jì)的目的（1） 熟練使用棧和隊(duì)列解決實(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ī)放在國(guó)際象棋的8X8棋盤Bo阿rd0.7,0.7的某個(gè)方格中，馬按走棋規(guī)則進(jìn)行移動(dòng)。要求每個(gè)

2、方格上只進(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ù)。3、課程設(shè)計(jì)報(bào)告內(nèi)容根據(jù)分析先建了2個(gè)結(jié)構(gòu)體struct PosType /馬的坐標(biāo)位置類型int m_row; /行值int m_col;/列值;struct DataType /棧的元素類型PosType se

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

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

5、ream>using namespace std;#include "SqStack.h"struct PosType /馬的坐標(biāo)位置類型int m_row; /行值int m_col;/列值;struct DataType /棧的元素類型PosType seat; /馬在棋盤中的“坐標(biāo)位置” 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; /留下足跡，標(biāo)注當(dāng)前位置是馬第幾次走e.seat.m_row=curpos.m_row; e.seat.m_col=curpos.m_col;e.di=0;path.Push(e); /當(dāng)前位置和方向入棧curstep+;if(curstep=65)return true;curpos=NextPos(curpos,e.di); elsecurpos=NextPos(curp

8、os,e.di+); /在棋盤之外自動(dòng)進(jìn)行下一次試探else /當(dāng)前位置已走過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) /沒到可能的最后一個(gè)位置e.di+; /換下一個(gè)位置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' /輸出對(duì)齊，水平制表cout<<endl;cout<<endl;PosType chess:NextPos(PosType a,int di)/根據(jù)當(dāng)前點(diǎn)的位置a和移動(dòng)方向di，試探下一位置PosType direct8=2,1,1,2,-1,2,-2,1,-2,-1,-1,-2,1,

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

11、CK_H_/定義順序棧類template <class ElemType>/聲明一個(gè)類模板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個(gè)結(jié)點(diǎn)的順序空間，構(gòu)造一個(gè)空的順序棧。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/求棧的長(zhǎng)度。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/入棧，若棧滿，則先擴(kuò)展空間。插入e到棧頂。template <class ElemType>void SqStack <ElemType>:Push(const ElemType &e) if(m_top >= m_size)/若棧滿，則擴(kuò)展空間。 ElemType *newbase; newbase = new ElemTypem_size +