數(shù)據(jù)結(jié)構(gòu)實習(xí)報告——國際象棋中馬及遍歷(已修改)
2025-04-04 08:47 本頁面
【正文】 數(shù)據(jù)結(jié)構(gòu)與VC編程實習(xí)實習(xí)報告 學(xué)生姓名：學(xué) 號：專業(yè)班級：指導(dǎo)教師：2012年7月14日實習(xí)題目在國際象棋棋盤上實現(xiàn)馬的遍歷一、任務(wù)描述及要求國際象棋的棋盤有88＝64個格子，給它們規(guī)定坐標（1，1）到（8，8）。馬在這64個格子的某一個格子上，它的跳動規(guī)則是：如果它現(xiàn)在在（x，y）位置，它下一步可以跳到（x177。1，y177。2）或（x177。2，y177。1）（所有的“177?！敝g沒有相關(guān)性）。一般來說它下一步可以有八種跳法，但是它不能跳出這64個格子。設(shè)計算法使它不管從哪出發(fā)都可以跳遍所有的格子（每個格子只能路過一次）最后回到起點。： 合理設(shè)計界面，自行設(shè)計國際象棋棋盤，用鼠標選擇馬的起始位置，起始位置選定后，按“開始”按鈕演示馬的每一步行走路線。棋盤和馬的顯示盡量美觀逼真。功能菜單或按鈕自行設(shè)計，以合理為目的。： 對算法進行優(yōu)化，該規(guī)則是在所有可跳的方格中,馬只可能走這樣一個方格:從該方格出發(fā),馬能跳的方格數(shù)為最少；如果可跳的方格數(shù)相等,則從當前位置看,方格序號小的優(yōu)先。二、概要設(shè)計1．抽象數(shù)據(jù)類型本次實習(xí)中，我主要采用圖的深度遍歷知識和貪心算法來解決在國際象棋棋盤上實現(xiàn)馬的遍歷問題。棋盤上將64個格子視為64個點，將馬從一個格子跳到另一個格子視為一條邊，則共有168條邊，那么可以將棋盤視為一個無向圖。 為了實現(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ā)都走這條路線，則一定能回到起點。此種遍歷易于理解，下面不再詳細介紹。2．整個程序包含功能模塊及模塊間的調(diào)用關(guān)系⑴ 整個程序包含的主要功能模塊：更換棋盤顏色，遍歷起點的定位（鼠標定位、坐標定位和默認起點），在窗口的狀態(tài)欄右邊可以顯示鼠標當前所處的坐標值以協(xié)助頂點的定位，棋盤上遍歷過程的動態(tài)顯示（圖片（可更換）或路線），遍歷頂點序列的打印，兩種遍歷方式（規(guī)則遍歷（）和固定遍歷（按固定的路線遍歷）），重新遍歷。 ⑵ 模塊間的調(diào)用關(guān)系：每次開始遍歷之前可以更換棋盤的顏色、選擇遍歷過程的動態(tài)顯示方式和遍歷起點，然后選擇規(guī)則遍歷或固定遍歷。開始遍歷之后可以動態(tài)顯示遍歷過程，并打印遍歷的頂點序列。在下一次遍歷之前要選擇重新遍歷，并重新選擇起點和遍歷方式。實際上整個遍歷是在開始動態(tài)顯示遍歷過程之前完成的，在遍歷時將遍歷序列用一維數(shù)組記錄下來，遍歷完之后利用此數(shù)組記錄的序列來控制遍歷過程的動態(tài)顯示和遍歷頂點序列的打印。三、詳細設(shè)計1．虛擬實現(xiàn)（即數(shù)據(jù)結(jié)構(gòu)的C++語言描述）⑴ 規(guī)則遍歷中圖的抽象數(shù)據(jù)類型的C++類定義為：class Edge { //邊結(jié)點的定義public: int dest。 //邊的另一頂點位置，即下標 Edge *link。 //下一條邊結(jié)點
環(huán)評公示相關(guān)推薦
鄂ICP備17016276號-1