數(shù)據(jù)結(jié)構(gòu)實習(xí)報告-國際象棋中馬及遍歷.doc

《數(shù)據(jù)結(jié)構(gòu)實習(xí)報告-國際象棋中馬及遍歷.doc》由會員分享，可在線閱讀，更多相關(guān)《數(shù)據(jù)結(jié)構(gòu)實習(xí)報告-國際象棋中馬及遍歷.doc（12頁珍藏版）》請在裝配圖網(wǎng)上搜索。

數(shù)據(jù)結(jié)構(gòu)與VC編程實習(xí) 實習(xí)報告 學(xué)生姓名： 學(xué) 號： 專業(yè)班級： 指導(dǎo)教師： 2012年7月14日 實習(xí)題目 在國際象棋棋盤上實現(xiàn)馬的遍歷 一、任務(wù)描述及要求 國際象棋的棋盤有88＝64個格子，給它們規(guī)定坐標(biāo)（1，1）到（8，8）。馬在這64個格子的某一個格子上，它的跳動規(guī)則是：如果它現(xiàn)在在（x，y）位置，它下一步可以跳到（x1，y2）或（x2，y1）（所有的“”之間沒有相關(guān)性）。一般來說它下一步可以有八種跳法，但是它不能跳出這64個格子。 設(shè)計算法使它不管從哪出發(fā)都可以跳遍所有的格子（每個格子只能路過一次）最后回到起點。 1.基本要求： 合理設(shè)計界面，自行設(shè)計國際象棋棋盤，用鼠標(biāo)選擇馬的起始位置，起始位置選定后，按“開始”按鈕演示馬的每一步行走路線。棋盤和馬的顯示盡量美觀逼真。功能菜單或按鈕自行設(shè)計，以合理為目的。 2.擴(kuò)展要求： 對算法進(jìn)行優(yōu)化，根據(jù)j.c.Warnsdorff規(guī)則設(shè)計算法，該規(guī)則是在所有可跳的方格中,馬只可能走這樣一個方格:從該方格出發(fā),馬能跳的方格數(shù)為最少；如果可跳的方格數(shù)相等,則從當(dāng)前位置看,方格序號小的優(yōu)先。 二、概要設(shè)計 1．抽象數(shù)據(jù)類型 本次實習(xí)中，我主要采用圖的深度遍歷知識和貪心算法來解決在國際象棋棋盤上實現(xiàn)馬的遍歷問題。棋盤上將64個格子視為64個點，將馬從一個格子跳到另一個格子視為一條邊，則共有168條邊，那么可以將棋盤視為一個無向圖，馬在棋盤上按c.Warnsdorff規(guī)則跳動可視為圖的深度遍歷過程中的一步。 為了實現(xiàn)圖的存儲，需要建立頂點順序表和鄰接表，這個過程是在圖的構(gòu)造函數(shù)里實現(xiàn)的。圖的操作主要包括：給出頂點vertex在表中的位置，給出頂點位置為 v 的第一個鄰接頂點的位置，給出頂點v的鄰接頂點w的下一個鄰接頂點的位置，給出頂點位置為 v 的最優(yōu)鄰接頂點的位置。圖的遍歷算法是在視圖類里面實現(xiàn)的。 圖的抽象數(shù)據(jù)類型為： ADT Graph{ 數(shù)據(jù)：頂點順序表 關(guān)系: 鄰接表表示了頂點之間的鄰接關(guān)系 操作：① 給出頂點vertex在表中的位置 ② 給出頂點位置為 v 的第一個鄰接頂點的位置 ③ 給出頂點v的鄰接頂點w的下一個鄰接頂點的位置 ④ 給出頂點位置為 v 的最優(yōu)鄰接頂點的位置 } 由于貪心算法有時不能得到整體最優(yōu)解，所以我設(shè)計了另一種遍歷算法。由于要求遍歷完所有點后要回到起點，則這是一條哈密頓回路，故可以事先找出這樣的一種遍歷序列并將其用點數(shù)組記錄下來，以后在每次遍歷時不論從哪個點出發(fā)都走這條路線，則一定能回到起點。此種遍歷易于理解，下面不再詳細(xì)介紹。 2．整個程序包含功能模塊及模塊間的調(diào)用關(guān)系 ⑴ 整個程序包含的主要功能模塊：更換棋盤顏色，遍歷起點的定位（鼠標(biāo)定位、坐標(biāo)定位和默認(rèn)起點），在窗口的狀態(tài)欄右邊可以顯示鼠標(biāo)當(dāng)前所處的坐標(biāo)值以協(xié)助頂點的定位，棋盤上遍歷過程的動態(tài)顯示（圖片（可更換）或路線），遍歷頂點序列的打印，兩種遍歷方式（規(guī)則遍歷（基于c.Warnsdorff規(guī)則的圖的深度遍歷）和固定遍歷（按固定的路線遍歷）），重新遍歷。 ⑵ 模塊間的調(diào)用關(guān)系：每次開始遍歷之前可以更換棋盤的顏色、選擇遍歷過程的動態(tài)顯示方式和遍歷起點，然后選擇規(guī)則遍歷或固定遍歷。開始遍歷之后可以動態(tài)顯示遍歷過程，并打印遍歷的頂點序列。在下一次遍歷之前要選擇重新遍歷，并重新選擇起點和遍歷方式。實際上整個遍歷是在開始動態(tài)顯示遍歷過程之前完成的，在遍歷時將遍歷序列用一維數(shù)組記錄下來，遍歷完之后利用此數(shù)組記錄的序列來控制遍歷過程的動態(tài)顯示和遍歷頂點序列的打印。 三、詳細(xì)設(shè)計 1．虛擬實現(xiàn)（即數(shù)據(jù)結(jié)構(gòu)的C++語言描述） ⑴ 規(guī)則遍歷中圖的抽象數(shù)據(jù)類型的C++類定義為： class Edge { //邊結(jié)點的定義 public: int dest; //邊的另一頂點位置，即下標(biāo) Edge *link; //下一條邊結(jié)點的指針 public: Edge (int num=-1,Edge *ptr=NULL): dest (num),link (ptr) { } //構(gòu)造函數(shù) }; struct Vertex { //頂點的定義 E data; //頂點的名字 int numEdge; //此頂點當(dāng)前關(guān)聯(lián)的可走邊數(shù) bool ver; //標(biāo)記此頂點是否被訪問過 Edge *adj; //邊鏈表的頭指針 }; class Graph { //圖的類定義 public: Vertex *NodeTable; //頂點順序表 (各邊鏈表的頭結(jié)點) int numVertices; //頂點個數(shù) public: Graph (); //構(gòu)造函數(shù) ~Graph(); //析構(gòu)函數(shù) int getVertexPos (const E vertx);//給出頂點vertex在表中的位置 int getFirstNeighbor (int v); //給出頂點位置為 v 的第一個鄰接頂點的位置 int getNextNeighbor (int v, int w);//給出頂點v的鄰接頂點w的下一個鄰接//頂點的位置 int GetPriNeighbor(int v); //給出頂點位置為 v 的最優(yōu)鄰接頂點的位置 }; ⑵ 固定遍歷中存儲點的數(shù)組的定義： CPoint arr[64]; //存儲馬的固定行走回路路徑，共64步 2．抽象數(shù)據(jù)類型中定義的操作算法實現(xiàn)（用偽代碼描述） 此處只介紹求頂點位置為 v 的最優(yōu)鄰接頂點的位置的函數(shù)和圖的深度遍歷算法的偽代碼： ⑴ int GetPriNeighbor(int v)的偽代碼： ① 若v存在則執(zhí)行以下操作,否則返回-1； ② 令min=9,w2=-1，w2記錄最優(yōu)鄰接點； ③ 令w1為v的第一個鄰接頂點的位置； ④ 當(dāng)鄰接頂點w1存在時執(zhí)行以下操作: ⑤ 若 w1未被訪問，則轉(zhuǎn)到⑥，否則轉(zhuǎn)到⑦； ⑥ 若min大于w1當(dāng)前關(guān)聯(lián)的可走邊數(shù)numEdge則令min= numEdge，令w2=w1；若min等于w1當(dāng)前關(guān)聯(lián)的可走邊數(shù)numEdge，如果w2>w1則令w2=w1； ⑦ 令w1為v的鄰接頂點w1的下一個鄰接頂點的位置，轉(zhuǎn)到④； ⑧ 返回w2； 具體實現(xiàn)代碼如下： int Graph::GetPriNeighbor(int v) {//給出頂點位置為 v 的最優(yōu)鄰接頂點的位置, 如果找不到, 則函數(shù)返回-1 if (v != -1) //頂點v存在 { int min=9,w2=-1; //w2記錄最優(yōu)鄰接點 int w1 = getFirstNeighbor (v); //獲取第一個鄰接頂點的位置 while (w1 != -1) //若鄰接頂點w存在 { if ( !NodeTable[w1].ver ) //w1未被訪問 { if(min>NodeTable[w1].numEdge) { min=NodeTable[w1].numEdge;//記錄v的最優(yōu)鄰接頂點的當(dāng)前關(guān)聯(lián)的邊數(shù) w2=w1; //從該方格出發(fā),馬能跳的方格數(shù)為最少 } else if(min==NodeTable[w1].numEdge) { if(w2>w1) w2=w1; } //如果可跳的方格數(shù)相等,則從當(dāng)前位置看,方格序號小的優(yōu)先 else {} } w1 = getNextNeighbor (v, w1); //獲取下一個鄰接頂點 } return w2; } return -1; } ⑵ void DFS(Graph & G,E & v)的偽代碼： ① 若開始遍歷且起點在棋盤內(nèi)則令常變量m為起始點v的下標(biāo)，令loc=m,v=loc； ② 令v的訪問標(biāo)記ver為true； ③ 若k>=0且k<=64，令h[65]=v，k=k+1；(k、h[65]為全局變量，初始值都為0) ④ v當(dāng)前關(guān)聯(lián)的可走邊數(shù)numEdge=numEdge-1； ⑤ 當(dāng)k=64時令m的訪問標(biāo)記ver=false； ⑥ 令w為v的第一個鄰接頂點的位置； ⑦ 當(dāng)w存在時執(zhí)行以下操作： ⑧ w當(dāng)前關(guān)聯(lián)的可走邊數(shù)numEdge=numEdge-1； ⑨ 令w為v的鄰接頂點w的下一個鄰接頂點的位置，轉(zhuǎn)到⑦； ⑩ 令pw為v 的最優(yōu)鄰接頂點的位置； ? 若pw不為-1則令v=pw,轉(zhuǎn)到②； 具體實現(xiàn)代碼如下: void CChessView::DFS(Graph & G, E &v)//從頂點v出發(fā)對圖G進(jìn)行深度優(yōu)先遍歷 { if(flag==1 && v>=1 && v<=64) { const int m = G.getVertexPos(v); //獲取起始點的下標(biāo) int loc=m; //記錄起始點的下標(biāo) dfs (G,loc,m); //從頂點v開始深度優(yōu)先搜索 } } void CChessView::dfs(Graph & G,int v,const int m) { if(flag==1) //判斷當(dāng)前是否處在遍歷的狀態(tài) { G.NodeTable[v].ver=true; //作頂點的訪問標(biāo)記 if(k>=0 && k<=64) h[k++]=v; //標(biāo)記序號,存儲下標(biāo) G.NodeTable[v].numEdge--; //起始點被訪問過則將其邊數(shù)減1 if(k==64) G.NodeTable[m].ver=false; //k=64時將起始點標(biāo)記為未被遍歷,以便回到起始點 int w = G.getFirstNeighbor (v); //獲取第一個鄰接頂點的位置 while (w != -1) //若鄰接頂點w存在 { // if ( !G.NodeTable[w].ver ) //w未被訪問 G.NodeTable[w].numEdge--; //頂點各鄰接點的邊數(shù)都應(yīng)減1 w = G.getNextNeighbor (v, w); //獲取下一個鄰接頂點 } int pw=G.GetPriNeighbor(v); //給出頂點位置為 v 的最優(yōu)鄰接頂點的位置, 如果找不到, 則函數(shù)返回-1 if(pw!=-1) dfs(G,pw,m); //若最優(yōu)鄰接頂點存在, 遞歸訪問頂點pw } } 3．函數(shù)之間的調(diào)用關(guān)系 ⑴ 運(yùn)行程序后調(diào)用視圖類的OnDraw()函數(shù)在窗口中繪制棋盤。 ⑵ 在菜單欄的“操作”中點擊“黃綠相間” 、“黑白相間” 、“恢復(fù)默認(rèn)”菜單后分別調(diào)用視圖類的OnMenuitemby()、OnMenuitembw()、OnSyschMenuitem()函數(shù)，在此函數(shù)中調(diào)用了Invalidate()函數(shù)，它自動調(diào)用OnDraw函數(shù)重新繪制窗口。 ⑶ 點擊“圖片” 、“路線”菜單后分別調(diào)用視圖類的OnMaMenuitem()、OnRouteMenuitem()函數(shù)。 ⑷ 點擊“更換圖片”菜單調(diào)用視圖類的OnDialog3()函數(shù)以彈出對話框，在對話框上點擊單選按鈕選擇圖片后，若點擊“確定”按鈕調(diào)用Dialog3類的OnOk3Button()函數(shù)，若點擊“缺省設(shè)置”按鈕則調(diào)用Dialog3類的OnPicsysButton()函數(shù)。 ⑸ 點擊“鼠標(biāo)定位”、“坐標(biāo)定位”菜單后分別調(diào)用視圖類的OnMouselocation()、OnMenuitemsys()函數(shù)，點擊“坐標(biāo)定位” 后彈出OnDialog2()對話框，設(shè)置起點后，若點擊對話框上的“確定”“按鈕后調(diào)用OnDialog2()類的OnOk2Button() 函數(shù)，在此函數(shù)中調(diào)用了 UpdateData(TRUE)函數(shù)以刷新控件的值到對應(yīng)的變量，若點擊“缺省值”按鈕則調(diào)用OnDialog2()類的OnSysButton()函數(shù) 關(guān)閉對話框后調(diào)用視圖類的OnDialog2()函數(shù)。 ⑹ 點擊“規(guī)則遍歷”菜單或工具欄中的“J”圖標(biāo)后調(diào)用視圖類的OnMenuitemstart()函數(shù)，此函數(shù)中調(diào)用了Graph類的構(gòu)造函數(shù)Graph ()來建立圖，也調(diào)用了視圖類的圖的深度遍歷函數(shù)DFS()和顯示圖片或路線和遍歷序列l(wèi)istnumber()函數(shù)。在DFS()中調(diào)用了Graph類的getVertexPos()和視圖類的dfs ()函數(shù)，在dfs ()中又調(diào)用了Graph類的getFirstNeighbor()、getNextNeighbor ()、GetPriNeighbor()函數(shù)，也調(diào)用了它本身來形成深度遍歷，也用到了遍歷序列存儲數(shù)組h[65]。在listnumber()中調(diào)用了視圖類的picture()和route()函數(shù)和延時函數(shù)Sleep()，用以動態(tài)顯示遍歷過程，之后打印頂點的遍歷序列并提示遍歷成功與否。 ⑺ 點擊“固定遍歷”菜單或工具欄中的“S”圖標(biāo)后調(diào)用視圖類的OnSolidMenuitem()和listnumber()函數(shù), 也用到了存儲固定路徑的點數(shù)組arr[64]和遍歷序列存儲數(shù)組h[65]。 ⑻ 點擊“重新遍歷”菜單或工具欄中的“T”圖標(biāo)后視圖類的OnStopMenuitem()函數(shù)，在此函數(shù)中對遍歷序列存儲數(shù)組h[65]和全局變量進(jìn)行了初始化，也調(diào)用了Invalidate()函數(shù)，它自動調(diào)用OnDraw函數(shù)重新繪制窗口。 四、調(diào)試分析 1．程序在調(diào)試過程中出現(xiàn)的問題及解決方法 我個人認(rèn)為我在寫程序之前時考慮得比較仔細(xì)，所以需要調(diào)試的地方比較少。以下是我在調(diào)試過程中出現(xiàn)的問題及解決方法： ⑴ 實習(xí)期間的前幾天我一直認(rèn)為利用c.Warnsdorff規(guī)則設(shè)計出的圖的深度遍歷算法自己設(shè)計出算法后，通過窗口右側(cè)顯示的遍歷序列發(fā)現(xiàn)算法不正確。為了解決這個問題，我先仔細(xì)得把程序讀了幾遍，覺得算法設(shè)計得不縝密，尤其是對當(dāng)前遍歷點和其鄰接點的邊數(shù)減少問題的考慮和對獲取最優(yōu)鄰接點的函數(shù)的設(shè)計。經(jīng)過改進(jìn)后，還是不能得到理想的結(jié)果。于是我認(rèn)為還是算法設(shè)計得有問題，所以我對程序進(jìn)行了調(diào)試。經(jīng)過反復(fù)地調(diào)試和改進(jìn)，我覺得算法沒有問題了，可是對于某些起始點遍歷結(jié)果還是不正確。于是我開始懷疑利用c.Warnsdorff規(guī)則設(shè)計出的算法是不是一定能遍歷到所有點并回到起點。在網(wǎng)上查詢資料并與老師交流后發(fā)現(xiàn)自己前期的想法是錯誤的，實際上利用c.Warnsdorff規(guī)則在大多數(shù)情況下能夠?qū)崿F(xiàn)遍歷，但并不能確保成功。經(jīng)過再次深究自己設(shè)計的算法，我認(rèn)為算法是正確的。 ⑵ 與老師探討自己設(shè)計的算法后，老師要求我重新設(shè)計一種算法使得從任何一個點出發(fā)都可以遍歷到所有點并回到起點，即利用事先已知的固定路線來遍歷。在這個算法的設(shè)計過程中，也出現(xiàn)了遍歷序列不正確的問題，序列的前一部分正確，后一部分錯誤。經(jīng)過調(diào)試，發(fā)現(xiàn)在存儲遍歷序列的過程中用來控制點數(shù)組元素從arr[63]轉(zhuǎn)到arr[0]的變量出了問題，修改之后，問題順利解決。 2．算法的時間復(fù)雜度分析 ⑴ 圖的深度遍歷算法的時間復(fù)雜度分析： 設(shè)第i（1<=i<=64）個點的鄰接點個數(shù)為Di,圖的邊數(shù)為e。則遍歷算法第i個點的各鄰接點的邊數(shù)都減1的循環(huán)的時間代價是Di，獲取最優(yōu)鄰接頂點的函數(shù)的時間代價也是Di，故深度遍歷算法的總時間代價為2(D1+D2+…+D63+D64+Dj)=2 O(e)+2Dj，其中Dj是起點的鄰接點個數(shù)。 ⑵ 固定路線遍歷算法的時間復(fù)雜度分析： 設(shè)數(shù)組元素個數(shù)為n,則遍歷算法中for循環(huán)、while循環(huán)和listnumber()函數(shù)的時間復(fù)雜度都為O(n),故固定路線遍歷算法的時間復(fù)雜度為O(n)。 五、測試結(jié)果 根據(jù)一組提供的測試數(shù)據(jù)得到什么樣的結(jié)果？ ⑴ 圖的深度遍歷算法的測試數(shù)據(jù)為：坐標(biāo)值（7，8） 遍歷序列：63，48，31，16，6，12，2，17，11，1，18，3，9，26，41，58，52，62，56，46，40，55，61，51，57，42，25，10，4，14，8，23，13，7，24，39，29，19，34，49，59，44，27，33，50，35，20，5，15，21，36，30，45，60，54，64，47，32，22，37，43，28，38，53，63 遍歷結(jié)果正確！ ⑵ 固定路線遍歷算法的測試數(shù)據(jù)為：坐標(biāo)值（1，4） 遍歷序列：25，10，4，14，8，23，6，16，31，48，63，53，59，49，34，17，2，12，29，19，9，3，13，7，24，39，56，62，47，64，54，60，50，33，18，1，11，5，15，32，22，28，38，21，27，44，61，55，40，46，52，37，43，58，41，26，20，35，45，30，36，51，57，42，25 遍歷結(jié)果正確！ 六、心得體會 為期九天的數(shù)據(jù)結(jié)構(gòu)實習(xí)，感覺比平常的一個月都要漫長。這不僅僅是因為在考完試后的這九天中我依然早起晚睡，每天的工作量不亞于考前復(fù)習(xí)每天的工作量，每天對著電腦思考一些復(fù)雜的問題，更重要的是因為這九天我堅持下來了，學(xué)到了很多知識，錘煉了自己多方面的能力，增強(qiáng)了自己的毅力和信心，為以后的學(xué)習(xí)和工作奠定了很好的基礎(chǔ)。 實習(xí)前我并沒有做充分的準(zhǔn)備，實習(xí)開始時老師只說了相關(guān)事項，并沒有說怎么去做。所以，一切工作都得靠自己，自己利用網(wǎng)絡(luò)和書籍去解決編程中遇到的問題，請教老師和同學(xué)也是很好的一種解決問題的方式，此時我才體會到了“書到用時方恨少”的含義。實習(xí)前期主要是對題目加以分析，設(shè)計實習(xí)作品的預(yù)期效果，查找資料并學(xué)習(xí)相關(guān)知識。由于缺乏獨立解決問題的經(jīng)驗，以前接觸的很少，所以這個階段感覺比較費(fèi)力。由于時間有限，所以實習(xí)中期知識基本上都是現(xiàn)學(xué)現(xiàn)用，而且還得自己設(shè)計算法解決相關(guān)問題。然而自己設(shè)計的算法并不一定正確，需要反復(fù)改進(jìn)并反復(fù)測試，經(jīng)過多次修改后結(jié)果還不正確時，自己會感到很失望，并且會動搖自己的信心，甚至想放棄。更令人頭疼的是編程過程中會遇到很多錯誤，有時需要查閱相關(guān)資料，有時需要調(diào)試程序，所以這個階段感覺相當(dāng)費(fèi)力，當(dāng)然這個階段多與老師和同學(xué)溝通是非常有必要的，在溝通中常常會有意想不到的收獲。但當(dāng)每一個問題得到解決時，都會令自己信心大增，都會展現(xiàn)出最燦爛的笑容，吃飯都覺得胃口好，睡覺也睡得安穩(wěn)，于是更加堅定地接著做下去。實習(xí)后期主要是對程序進(jìn)行優(yōu)化，添加一些功能，驗收程序并撰寫實習(xí)報告。 實習(xí)期間一次次的失望對自己是一個很大的考驗，但一次次的看到希望對自己則是莫大的肯定。當(dāng)自己獨立完成整個作品時，再回首整個實習(xí)期間遇到的問題和經(jīng)受的苦難，感覺那也不算什么，并且覺得自己的付出是非常值得的，因為這是大學(xué)期間乃至整個人生中的一筆寶貴的財富。 指導(dǎo)教師評語及成績 姓名 學(xué)號 評價項目 評 價 內(nèi) 容 得 分 （百分制） 平時表現(xiàn) (30%) 學(xué)習(xí)、工作態(tài)度(30%) 紀(jì)律性(30%) 綜合運(yùn)用知識能力(40%) 實習(xí)成果 (70%) 開題報告書寫水平(15%) 實習(xí)總結(jié)報告書寫水平(15%) 成果(70%) 總分 評語： 指導(dǎo)教師（簽名）： 年 月 日