杭電數(shù)據(jù)結(jié)構(gòu)馬踏棋盤

1、數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)報(bào)告課程名稱：數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)課程設(shè)計(jì)題目：馬塔棋盤姓 名:院系：計(jì)算機(jī)學(xué)院專業(yè)：計(jì)算機(jī)科學(xué)與技術(shù)年級(jí)：大二學(xué) 號(hào):指導(dǎo)教師：王立波2012年5月17日1 課程設(shè)計(jì)的目的 ,x2 需求分析x3 課程設(shè)計(jì)報(bào)告內(nèi)容 ,x1、概要設(shè)計(jì),x2 、詳細(xì)設(shè)計(jì),x3、測(cè)試結(jié)果,x4、程序清單,xi / j i 口 i4 小結(jié) ,x7 -口八5 參考文獻(xiàn) ,x1、課程設(shè)計(jì)的目的（1）熟練使用c+語(yǔ)言編寫程序，解決實(shí)際問題；（ 2） 了解并掌握數(shù)據(jù)結(jié)構(gòu)與算法的設(shè)計(jì)方法，具備初步的獨(dú)立分析和設(shè)計(jì)能力；（ 3） 初步掌握軟件開發(fā)過程的問題分析、 系統(tǒng)設(shè)計(jì)、 程序編碼、 測(cè)試等基本方法和技能；（ 4）

2、 提高綜合運(yùn)用所學(xué)的理論知識(shí)和方法獨(dú)立分析和解決問題的能力；2、需求分析1 、任務(wù)：（一）：設(shè)置一個(gè)含有 x,y,di 變量的結(jié)構(gòu)體。定義馬向八個(gè)方向走的所在位置坐標(biāo)的變化int htrxlenx=-2,-1,1,2,2,1,-1,-2; htryleny=1,2,2,1,-1,-2,-2,-1;（二）：初始化數(shù)組 mata88 ，全部賦為 0。（三）：判斷該位置是否能走（是否已走過，或超出 8x8 的矩陣）（四）：對(duì)馬走的下一個(gè)可能方向按一定順序進(jìn)行處理。將馬可能走的下一個(gè)方向按照下下 個(gè)方向能走的度進(jìn)行從大到小的順序壓入棧中（不能通過的標(biāo)記為-1）(五) ：處理棋盤。馬的行走路線 ，并按求

3、出的行走路線，將數(shù)字 1，2，,， 64 依次填入 8x8 的方陣輸出之。定義 curstep=1， mataxy=1;(x,y) 為用戶輸入的初始數(shù)據(jù) ) 判斷 path 是否為空，若不為空，判斷 path 的棧頂元素的 di 是否小于 0若 di 小于 0，退棧。否則若 mataxy >0(x,y) 為棧頂元素的坐標(biāo) ) mataxy=0( 清除走 過痕跡 )curstep- ；步伐值減一， 出棧 否則 mataxy=+curstep; 對(duì)馬走過的位置進(jìn)行標(biāo)記 根據(jù)此位置，重新對(duì)馬走的下一個(gè)可能方向進(jìn)行排序。 若已走完 64 個(gè)位置輸出“馬在此位置能走遍全部的格子” 則打印 mata

4、88 數(shù)組 若 path 為空，則輸出“馬在此位置不能走遍全部的格子”2、測(cè)試數(shù)據(jù)在 8*8 的矩陣中輸出 164 的數(shù)，且沒有重復(fù)3、課程設(shè)計(jì)報(bào)告內(nèi)容概要設(shè)計(jì) (1)在分析題目要求的基礎(chǔ)上，我首先設(shè)計(jì)了一個(gè)結(jié)構(gòu)體，定義如下 struct postint x;int y;int di;/ 該位置能走的方向 ;存儲(chǔ)坐標(biāo)信息。測(cè)試結(jié)果： :-'二:d c : .- ,：3. :請(qǐng)輸入開始位置的坐標(biāo)；0 0馬走遍所有格子的路徑1142?5211161964303712152863101713251385318592036314049關(guān)2762935啊35543?602126324148452

5、4578614744334556252242334654423s67請(qǐng)按任意鍵繼續(xù)請(qǐng)輸入開始位置的坐標(biāo)1 1馬走遍所有格子的路徑371453123924631054138255«11402315361352416296425542592657224s351633565144£183235043602746211734b30194872s43118496292047請(qǐng)按任意鍵繼續(xù)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ú)立思考，深入研究，分析

6、問 題、解決問題的能力。3、通過實(shí)際編譯系統(tǒng)的分析設(shè)計(jì)、編程調(diào)試，掌握應(yīng)用軟件的分析方法和工程設(shè)計(jì)方法。二、根據(jù)我在實(shí)習(xí)中遇到得問題，我將在以后的學(xué)習(xí)過程中注意以下幾點(diǎn)：1認(rèn)真上好專業(yè)實(shí)驗(yàn)課，多在實(shí)踐中鍛煉自己。2、寫程序的過程中要考慮周到，嚴(yá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í)間。5、程序清單：#in clude<iostream> using namespace std;#include<stac

7、k>#define lenx 8#define leny 8struct postint x;int y;int di;/ 該位置能走的方向;class mata public:mata();mata();bool pass(post );/該位置是否能走void sort(post);/ 對(duì) newseat 根據(jù) di 的大小進(jìn)行排序void deal(post );/ 處理棋盤void print();/ 輸出結(jié)果private:int *mata; / 馬踏棋盤數(shù)組 stack<post> path;/構(gòu)造函數(shù) ,棋盤大小 8*8mata:mata()mata=new

8、int*leny;for(int i=0;i<lenx;i+) matai=new intleny;for(int j=0;j<leny;j+) mataij=0;/ 表賦空mata:mata()for (int i = 0; i < lenx; i+)if (matai != null) delete matai;if (mata != null) delete mata;/當(dāng)前位置可走 ,且沒有走過 ,返回 truebool mata:pass(post c)return (c.x>=0 && c.x<lenx && c.y&g

9、t;=0 && c.y<leny && matac.xc.y=0); void mata:sort(post c)post newseat8,temp;int htrxlenx=-2,-1,1,2,2,1,-1,-2;int htryleny=1,2,2,1,-1,-2,-2,-1;for(int i=0;i<lenx;i+)/ 得到下一個(gè)可能的位置 newseati.x=c.x+htrxi; newseati.y=c.y+htryi; if(!pass(newseati)newseati.di=-1;/ 不能通過 di 為 -1 continue;

10、newseati.di=0;for(int j=0;j<leny;j+)/newseati 這個(gè)位置上可走的方向 di temp.x=newseati.x+htrxj;temp.y=newseati.y+htryj; if(pass(temp)newseati.di+;for(int i=0;i<lenx;i+)for(int j=i;j<leny;j+)if(newseati.di<newseatj.di)/ 從大到小排列temp=newseati; newseati=newseatj;newseatj=temp;for(int i=0;i<lenx;i+)/

11、將所有可能的位置按順序圧棧 path.push(newseati);void mata:deal(post start)/ 處理棋盤post e;int curstep=1; matastart.xstart.y=curstep;sort(start);while(!path.empty()e=path.top();if (e.di<0)path.pop();else if(matae.xe.y>0)matae.xe.y = 0;path.pop();-curstep;elsematae.xe.y = + curstep; sort(e);if(curstep=lenx*leny)

12、print();break;if(path.empty()cout<<" 馬不能走遍全部 64 個(gè)格子 "<<endl; void mata:print()cout<<" 馬走遍所有格子的路徑 "<<endl;for(int i=0;i<lenx;i+)for(int j=0;j<leny;j+)if(mataij>=0 && mataij<10) cout<<" "<<mataij;elsecout<<" "<<mataij;cout<<endl;int main()mata m_mata