數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)馬踏棋盤求全部解及演示程序

1、安徽工程大學(xué) 信息10課程設(shè)計(jì)馬踏棋盤的求解及演示設(shè)計(jì)摘 要數(shù)據(jù)結(jié)構(gòu)是計(jì)算機(jī)科學(xué)與技術(shù)專業(yè)的一門核心專業(yè)基礎(chǔ)課程，是一門理論性強(qiáng)、思維抽象、難度較大的課程。我認(rèn)為學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)的最終目的是為了獲得求 解問題的能力。對于現(xiàn)實(shí)世界中的問題，我們應(yīng)該能從中抽象出一個(gè)適當(dāng)?shù)臄?shù)學(xué) 模型，該數(shù)學(xué)模型在計(jì)算機(jī)內(nèi)部用相應(yīng)的數(shù)據(jù)結(jié)構(gòu)來表示，然后設(shè)計(jì)一個(gè)解此數(shù)學(xué)模型的算法，再進(jìn)行編程調(diào)試，最后獲得問題的解答。數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)是計(jì)算機(jī)科學(xué)技術(shù)專業(yè)集中實(shí)踐性環(huán)節(jié)之一， 是學(xué)習(xí)完數(shù)據(jù)結(jié)構(gòu)課程后進(jìn)行 的一次全面的綜合練習(xí)。開設(shè)本課程設(shè)計(jì)實(shí)踐的主要目的就是要達(dá)到理論與實(shí)際 應(yīng)用相結(jié)合，提高學(xué)生的動(dòng)手能力，完成計(jì)算機(jī)應(yīng)用能力的

2、培養(yǎng)；本課程設(shè)計(jì)主 要解決馬踏棋盤的問題，找出踏遍棋盤的多種路徑，并實(shí)現(xiàn)動(dòng)態(tài)要是過程。馬踏棋盤問題，實(shí)際上是圖論中的哈密頓通路問題，是 典型的np問 題,求解的問題與算法設(shè)計(jì)有很大關(guān)系，如果采取窮舉搜索的話，很容易 陷入海量搜索的狀態(tài)，耗費(fèi)巨大的時(shí)間，使問題幾乎不可解，因此馬在棋盤上遍 歷采用算法當(dāng)中的深度優(yōu)先算法和 啟發(fā)式貪心算法，用棧來存儲遍歷過程，通過 對棧的使用實(shí)現(xiàn)對所有路徑的搜索。 在調(diào)試過程發(fā)現(xiàn)，啟發(fā)式貪心算法，針對于 馬踏棋盤問題有著極大的好處，就是無論從棋盤上哪個(gè)點(diǎn)開始，找到一條遍歷完 棋盤的通路是不需要回溯的，也就節(jié)省了大量的時(shí)間，而試探性的操作對于每個(gè) 點(diǎn)都也只有168步，

3、所以求出所有路徑在 不到一秒的時(shí)間內(nèi)完成。關(guān)鍵詞：馬踏棋盤；騎士周游；哈密頓通路；np-完全問題；貪心算法；回溯法；馬踏棋盤的求解及演示設(shè)計(jì) 目錄第一章引 言第二章需求分析2.1問題描述2.2基本要求2.3具體需求2.4開發(fā)環(huán)境第三章概要設(shè)計(jì)3.1系統(tǒng)概述3.2系統(tǒng)描述3.3邏輯設(shè)計(jì)第四章詳細(xì)設(shè)計(jì)4.1 功能模塊設(shè)計(jì)4.2 數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)4.3算法設(shè)計(jì)第五章調(diào)試與分析5.1調(diào)試分析第六章系統(tǒng)試用說明6.1系統(tǒng)試用說明第七章總結(jié)與體會錯(cuò)誤！未定義書簽 錯(cuò)誤！未定義書簽 錯(cuò)誤！未定義書簽 錯(cuò)誤！未定義書簽 錯(cuò)誤！未定義書簽 錯(cuò)誤！未定義書簽 錯(cuò)誤！未定義書簽 錯(cuò)誤！未定義書簽 錯(cuò)誤！未定義書簽 錯(cuò)誤

4、！未定義書簽 錯(cuò)誤！未定義書簽 錯(cuò)誤！未定義書簽 錯(cuò)誤！未定義書簽 錯(cuò)誤！未定義書簽 錯(cuò)誤！未定義書簽 錯(cuò)誤！未定義書簽 錯(cuò)誤！未定義書簽 錯(cuò)誤！未定義書簽 錯(cuò)誤！未定義書簽 錯(cuò)誤！未定義書簽 錯(cuò)誤！未定義書簽 錯(cuò)誤！未定義書簽參考文獻(xiàn)3第一章引 言本課程設(shè)計(jì)主要研究馬踏棋盤的問題， 即騎士周游問題，是將馬隨機(jī)放在國際象棋的8x8棋盤的某個(gè)方格中，“馬”按照走棋規(guī)則進(jìn)行移動(dòng)，要求每個(gè)方格只進(jìn)入一次,走遍棋盤上全部64個(gè)方格。許多知名的數(shù)學(xué)家，如德莫弗 (de moivre)、歐拉(euler)與范德蒙德(vandermonde)等人，在過去的200年中都研究過這個(gè)問題， 今天從數(shù)據(jù)結(jié)構(gòu)的角度，

5、解決這一問題。力求以最快的速度，即最高的效率來解決問題。已知窮舉法是幾乎不可能完成的， 而與解決迷宮問題的回溯法， 也要占用大量的時(shí)間， 這里采用貪心 算法來解決這一問題，并找出多有的遍歷路徑。4第二章需求分析2.1問題描述馬隨機(jī)放在國際象棋的8x8棋盤的某個(gè)方格中，“馬”按照走棋規(guī)則 進(jìn)行移動(dòng)，要求每個(gè)方格只進(jìn)入一次，走遍棋盤上全部64個(gè)方格。設(shè)計(jì)一個(gè)國際 象棋的馬踏遍棋盤的演示程序。2.2基本要求設(shè)計(jì)合適的數(shù)據(jù)結(jié)構(gòu)，編制遞歸以及非遞歸程序，求出馬的行走路線,并按求 出的馬的行走路線,將路線1,2, , ,64依次填入一個(gè)8x 8的方陣,輸出之，若有 多種走法，則能將全部的輸出。必須要能夠?qū)?/p>

6、踏遍棋盤的過程顯示在計(jì)算機(jī)屏幕 上。要求：(1) 描述設(shè)計(jì)所涉及的數(shù)據(jù)模型，設(shè)計(jì)高效的數(shù)據(jù)結(jié)構(gòu)完成總體設(shè)計(jì)，搭好框架，確定人機(jī)對話的界面(要求界面上能動(dòng)態(tài)體現(xiàn)出演示的過程)，實(shí)現(xiàn)功能；(2) 界面友好，函數(shù)功能要?jiǎng)澐趾?3) 要有算法設(shè)計(jì)的流程圖(4) 程序要加必要的注釋(5) 要提供程序測試方案2.3具體需求1、首先要找到馬踏棋盤棋盤的多條路徑。2 、實(shí)現(xiàn)馬踏棋盤的動(dòng)態(tài)演示過程。3 、優(yōu)化算法，提高算法效率，以遞歸與非遞歸的方式實(shí)現(xiàn)2.4開發(fā)環(huán)境開發(fā)環(huán)境：win dows 8輔助工具：visual studio 2012 ,myeclipse 10.5運(yùn)行環(huán)境：win dows xp/vis

7、ta/7/8第三章概要設(shè)計(jì)3.1系統(tǒng)概述3.12 主函數(shù)main()的執(zhí)行流程求解多條路徑子系統(tǒng)：自動(dòng)演示路徑子系統(tǒng)開始3.2系統(tǒng)描述通過vs2012完成的尋找多條路徑的子系統(tǒng)，通過java來實(shí)現(xiàn)馬踏棋盤的動(dòng)態(tài)演示子系統(tǒng)。在尋找多條路徑的子系統(tǒng)中，通過啟發(fā)式貪心算法，將某點(diǎn)的下一步最少通往其它落 腳點(diǎn)，將該點(diǎn)確定為最佳落點(diǎn)。每次只走下一步通向其他點(diǎn)最少的點(diǎn)。用棧記錄探尋的過程，將走過的點(diǎn)標(biāo)記為1，試探而沒有走的點(diǎn)標(biāo)記為 0.最后通過尋找出棧標(biāo)志為0的點(diǎn)來尋找其他路徑。在動(dòng)態(tài)顯示模塊式通過java的線程機(jī)制是先的自動(dòng)動(dòng)畫演示。3.3邏輯設(shè)計(jì)抽象數(shù)據(jù)類型棋盤上某點(diǎn)的位置坐標(biāo)結(jié)構(gòu)體posti on把

8、個(gè)方向試探的增量位置數(shù)組direct8棋盤某點(diǎn)通向其他點(diǎn)的可到達(dá)數(shù)的二位數(shù)組access88鏈棧用來記錄可到達(dá)下一位置坐標(biāo)的數(shù)組：nextpath8;用來記錄整個(gè)遍歷過程的數(shù)組：tourpos64;第四章詳細(xì)設(shè)計(jì)4.1功能模塊設(shè)計(jì)4.1.2創(chuàng)建模塊本模塊創(chuàng)建棋盤，以及棋盤上每一點(diǎn)的可到達(dá)數(shù)，一個(gè)向8個(gè)方向試探的增量數(shù)組。以及記錄整個(gè)遍歷流程的鏈棧。選擇或設(shè)計(jì)數(shù)據(jù)結(jié)構(gòu)的存儲結(jié)構(gòu)，實(shí)現(xiàn)存儲結(jié)構(gòu)的基本運(yùn)算、設(shè)計(jì)的模塊構(gòu) 成、各模塊的簡要說明、流程圖、調(diào)用關(guān)系表等。在這個(gè)過程中，要綜合考慮系 統(tǒng)功能，使得系統(tǒng)結(jié)構(gòu)清晰、合理、簡單和易于調(diào)試，抽象數(shù)據(jù)類型的實(shí)現(xiàn)盡可 能做到數(shù)據(jù)封裝，基本操作的規(guī)格說明盡可

9、能明確具體。 詳細(xì)設(shè)計(jì)的結(jié)果是對數(shù) 據(jù)結(jié)構(gòu)和基本操作作出進(jìn)一步的求精，寫出數(shù)據(jù)存儲結(jié)構(gòu)的類型定義，寫出函數(shù) 形式的算法框架。4.1.3操作模塊實(shí)現(xiàn)對棋盤的周游，并找到多條路徑4.1.4顯示模塊將找到的所有路徑顯示在屏幕上，并統(tǒng)計(jì)找到的路徑數(shù)。4.1.5自動(dòng)演示模塊通過java的applet和線程機(jī)制，實(shí)現(xiàn)對找到的路徑進(jìn)行動(dòng)態(tài)演示4.2數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)4.2.1數(shù)據(jù)設(shè)計(jì)posti on定義棋盤上某點(diǎn)的位置坐標(biāo)結(jié)構(gòu)體typedef structint x;int y; postion ;定義把個(gè)方向試探的增量位置數(shù)組jqk-00l-qiira-qg-q,-1,-2,-2,-1,-1,2,-2,1;po

10、stion direct8=1,2,2,1,2,-1,1,-2定義棋盤某點(diǎn)通向其他點(diǎn)的可到達(dá)數(shù)的二位數(shù)組int access88 = 2,3,4,4,4,4,3,2,3,4,6,6,6,6,4,3,4,6,8,8,8,8,6,4,4,6,8,8,8,8,6,4,4,6,8,8,8,8,6,4,4,6,8,8,8,8,6,4,3,4,6,6,6,6,4,3,2,3,4,4,4,4,3,2；定義一個(gè)以 某一棋盤上的點(diǎn)和標(biāo)志的類型，作為棧的存儲數(shù)據(jù)typedef struct datatype data; struct node *n ext; stacknode,* pstacknode;/typ

11、edef struct / 定義一個(gè)棧pstacknode top; linkstack ,* plinkstack ;用來記錄可到達(dá)下一位置坐標(biāo)的數(shù)組：postion nextpath8;用來記錄整個(gè)遍歷過程的數(shù)組：postion tourpos64;4.3算法設(shè)計(jì)開始尋找下一條路徑: 流程圖：略：算法描述：應(yīng)考察每一方格的可到達(dá)性。使用數(shù)組accessibility 表示可達(dá)到數(shù),并當(dāng)馬踏棋盤時(shí)，程序動(dòng)態(tài)修正剩余格子的可達(dá)到數(shù)。accessibility arraypos = 0表明 格子已經(jīng)被占據(jù)。算法：void next_path( postion p)|postion testpos

12、;for ( int i = 0 ; i < 8 ; i+ )/有八種到達(dá)的情況testpos.x =p.x + direct i .x;/ 得岀 x,y坐標(biāo)的測試位置testpos.y =p.y + direct i .y;if (checkpath(testpos)/判斷測試位置是否在棋盤內(nèi)nextpatharraypos=testpos ;/由測試位置給岀正確x,丫坐標(biāo)accessibility arraypos = access testpos.xtestpos.y;/ 利用對應(yīng)/結(jié)束for循環(huán),尋找結(jié)束countaccessibility = arraypos ;/ 統(tǒng)計(jì)可達(dá)到

13、數(shù)的x,y坐標(biāo)得岀相應(yīng)的可到達(dá)的路徑總數(shù)if(accessibility arraypos > 0 )/ accessibility arraypos = 0表明格子已經(jīng)被占據(jù)arraypos + ;/尋找空格子結(jié)束/2.使用冒泡法來查詢最小數(shù)。void sortall () |/冒泡排序法.冒泡排序的基本概念是：依次比較相鄰的兩個(gè)數(shù)，將大數(shù)放在前面，小數(shù)放在后面。/保持穩(wěn)定性int temp;postion temps;for ( int i = 0 ; i < countaccessibility - 1 ; i + )for ( int j = i + 1; j < c

14、ountaccessibility ; j + )if ( accessibility i > accessibility j )temps=n extpathi;n extpathi=nextpathj;n extpathj=temps;temp = accessibility i ;accessibility i = accessibility j ;accessibility j = temp;/end of if/ end of inner for/ end of outer for / end of sortall3./3、向下一步移動(dòng)，將當(dāng)前要走的結(jié)點(diǎn)入棧，標(biāo)記為 1其他可到

15、達(dá)但沒有走的點(diǎn)入棧，標(biāo)記為 0 如果當(dāng)前坐標(biāo)走過，那么它可以到達(dá)的其它點(diǎn)的可到達(dá)數(shù)應(yīng)該-1最后將該點(diǎn)的可到達(dá)數(shù)更新為0void domoving( postion p)for ( int i = 0 ; i < countaccessibility ; i + ) ,datatype q;q.p=n extpathi;if (i=0)push li nkstack(s,q);access n extpathi.x n extpathi.y -;/直到?jīng)]有路徑了accessp.x p.y = 0 ;/ 當(dāng)前位置置 04、打印路徑：打印8x8棋盤，在棋盤中顯示馬跳的步驟:void fprin

16、t()/輸出路徑int order88=0;ii-初始化for (int k=0;k<64;k+)ordertourposk.xtourposk.y=k;cout« "n棋盤表示n"cout<< "01234567n"coutvv"+-+-+-+-+-+-+-+-+n"for (int i=0;i<8;i+)pri ntf(" " );pri ntf("%2d",i);for (int j=0;j<8;j+)printf("| %2d "

17、; ,orderij);pri ntf("|");pri ntf("n");if (i=7)pri ntf("+");elsepri ntf("+");printf("n");pri ntf(" " );5、尋找其他路徑：算法描述:將棧中存儲的路徑岀棧，判斷標(biāo)記是否為 0,并累計(jì)標(biāo)記為1的個(gè)數(shù)count next，即走過的 步數(shù)，方便撤銷走過的步驟，根據(jù) count_next來撤銷走過的步驟，先將在 access叩 撤銷，即還原 為1,將當(dāng)前為flag為0的復(fù)制到下一步的to

18、urpos數(shù)組中，之后將tourpos后面的步驟還原為 0,再結(jié)束后，在尋找下一條路徑，若找不到，則繼續(xù)岀棧，向前回溯。void other path()/尋找其他路徑int count=0;int recount=0,coutpath=0,count next=0;datatype ps169;while (!empty_linkstack(s) int flag=0;pop_li nkstack(s,&pscou nt);if (pscount.flag!=o)cou nt_n ext+;if(pscou nt.flag=0)access tourpos63-cou nt_n ex

19、t.xtourpos63-cou nt_n ext.y=1;tourpos63-cou nt_n ext=pscou nt.p;for (int i=0;i<count_next;i+)access tourpos63-i.xtourpos63-i.y=1;tourpos63-i.x=0;tourpos63-i.y=0;access tourpos63-cou nt n ext.xtourpos63-cou nt n ext.y=o; for (int j=count_next;j>0;j-)if (! tour_next( tourpos63-j,63-j)flag=1;brea

20、k;if (flag!=1)coutpath+;fprin t();cou nt+;cout«e ndl;coutvv "周游結(jié)束共找到"vvcoutpath+1 << "條路徑"<<endl;動(dòng)態(tài)演示：根據(jù)java線程機(jī)制，每隔800毫秒動(dòng)畫演示1步。public void run() /啟動(dòng)線程后將自動(dòng)調(diào)用run ()方法，在run ()方法內(nèi)產(chǎn)生一個(gè)控制動(dòng)畫的循環(huán) int delay = 800;while (true )count = 0;for (int i=0;i<64;i+)repaint();/re

21、paint()將調(diào)用 paint()方法畫一幀圖像count +;if (recount >63) final frame from= new frame();joptionpane. showmessagedialog (from,"周游完成”); return ;try thread.sleep (delay);catch (excepti on e) 第五章調(diào)試與分析5.1調(diào)試分析經(jīng)過對程序的編制，調(diào)試和運(yùn)行，使我更好的掌握了?；拘再|(zhì)和有關(guān)馬的遍歷問題 的解決方法，熟悉了各種調(diào)用的數(shù)據(jù)類型， 在調(diào)試和運(yùn)行過程中使我更加的了解和熟悉程序 運(yùn)行的環(huán)境，提高了我對程序調(diào)試分析

22、的能力和對錯(cuò)誤的糾正能力。5.1.1、首先要檢測貪心算法的可用性，先找出一條路徑；檢測輸出的路徑是否合法5.1.2、完成一條路徑的輸出之后，進(jìn)行棧的檢查，檢查棧中存儲的元素是否正確能否滿足回溯的標(biāo)準(zhǔn)，經(jīng)過檢測棧的合法性才能對棧中元素進(jìn)行操作，最后就是，實(shí)現(xiàn)對其他路徑的尋找,并統(tǒng)計(jì)路徑的條數(shù)。第六章系統(tǒng)試用說明6.1系統(tǒng)試用說明系統(tǒng)提示用戶輸入測試坐標(biāo)， 輸入坐標(biāo)應(yīng)滿足 必須為整數(shù)，且大于等于0,小于8兩 點(diǎn)之間以空格隔開。及滿足在棋盤上點(diǎn)的的要求。測試數(shù)據(jù)：0 0 ； 1 0； 7 7，2 3第七章總結(jié)與體會通過本次課程設(shè)計(jì)掌握了關(guān)于數(shù)據(jù)結(jié)構(gòu)的很多內(nèi)容如算法的設(shè)計(jì)，棧的使用，對圖的深度優(yōu)先遍歷

23、算法有了更深入的了解， 對于馬踏棋盤這一問題，有了 獨(dú)到研究和見解，讓學(xué)習(xí)的理論與實(shí)際應(yīng)用相結(jié)合， 提高了我的動(dòng)手能力，以及 獨(dú)立解決問題的能力，如使用 java來動(dòng)態(tài)演示馬踏棋盤的步驟，本來學(xué)習(xí) java 是對于用于動(dòng)畫的線程機(jī)制就沒有深入了解， 經(jīng)過這次的課程設(shè)計(jì)，在網(wǎng)上查閱 資料，在幾天內(nèi)，我學(xué)會了如何使用 java的線程機(jī)制來實(shí)現(xiàn)動(dòng)畫演示程序，可 對以說是一個(gè)不小的受獲。對數(shù)據(jù)結(jié)構(gòu)的應(yīng)用上也得到很大的提升， 前面做實(shí)驗(yàn) 都是一些驗(yàn)證性的實(shí)驗(yàn)，只是把書上的代碼輸進(jìn)去，檢測它的正確性，和它的算 法思想，而這次是在問題的前提下，來確定數(shù)據(jù)結(jié)構(gòu)，在算法思想的前提下，來 確定算法的使用，并根據(jù)各

24、種可行的算法來確定最優(yōu)的算法，即時(shí)空效率最高。 并且在寫出解決查找多種路徑的算法后， 很有成就感，因?yàn)樵诰W(wǎng)上，這一問題只 有求出一條路徑的方法，也沒有動(dòng)態(tài)演示的，很不符合課程設(shè)計(jì)的要求，并且發(fā) 現(xiàn)，如果只找一條路徑的話，要是算法用的靈活，可以說沒學(xué)數(shù)據(jù)結(jié)構(gòu)之前也可 解決，所以在找到所有路徑的時(shí)候內(nèi)心很喜悅， 大概這就是編程的樂趣吧。本次 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)確實(shí)收益匪淺。參考文獻(xiàn)xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx參考文獻(xiàn)書寫格式應(yīng)符合gb7714-87文后參考文獻(xiàn)著錄規(guī)則。常用參考 文獻(xiàn)編寫項(xiàng)目和順序規(guī)定如下：先安排中文（按姓氏筆劃排序），后安排

25、英語（或其他語種）（按字母先后排列）;注釋置于頁腳，參考文獻(xiàn)置于文末。參考文獻(xiàn)只列出最主要的、且是公開發(fā) 表的文獻(xiàn)，非正式公開發(fā)表的資料不列。文獻(xiàn)主要類型格式如下：期刊：序號作者篇名j.17附錄/ np_compelte.cpp :定義控制臺應(yīng)用程序的入口點(diǎn)/ np_compelte.cpp :定義控制臺應(yīng)用程序的入口點(diǎn)。/#i nclude "stdafx.h" #include <iostream> using namespacestd; #defi ne max100typedef struct direct_ in creme nt direct_ in

26、 creme ntdirect_ay8=1,2,2,1,2,-1,-1,-2,-2,-1,1,-2,-1,2,-2,1;int access88 = 2,3,4,4,4,4,3,2,3,4,6,6,6,6,4,3,4,6,8,8,8,8,6,4,4,6,8,8,8,8,6,4,4,6,8,8,8,8,6,4,4,6,8,8,8,8,6,4,3,4,6,6,6,6,4,3,2,3,4,4,4,4,3,2;int accessibility;int countaccessibility;typedef structint x;int y; postion ;staticpostion nextpa

27、th8;staticpostion tourpos64;staticint arraypos=0;staticint own accessibility ;/當(dāng)前棋子的可到達(dá)數(shù)static int cou ntmov in g=-1;bool success = false ;/typedef struct postion p;int flag; datatype;typedef structnode /定義結(jié)點(diǎn)結(jié)構(gòu)datatype data; struct node *n ext; stacknode,* pstacknode;/typedef struct / 定義一個(gè)棧pstacknod

28、e top; linkstack ,*plinkstack;/plinkstack init_linkstack() / 初始化函數(shù) 一plinkstack s;s=( plinkstack ) new( linkstack );if (s)s->top->n ext=nullreturn (s);j/bool empty_linkstack( plinkstack s) 判斷?？蘸瘮?shù)return ( s>top= null;/int push_linkstack( plinkstack s, datatype x) / 入棧函數(shù) 一pstacknode p;p= new (

29、 stacknode);if (!p)return 0;p->data= x;p>n ext= s>top;int pop_linkstack( plinkstack s,datatype * x) / 岀棧函數(shù)pstacknode p;if (empty linkstack( s)p=s>top;s>top= s>top->n ext;delete (p);return 1;/int gettop_linkstack( plinkstack s, datatype *x) 取棧頂元素if (empty linkstack( s)return 0;el

30、se/void destroy_linkstack(plinkstack * ls) / 銷毀棧函數(shù)pstacknode p,q;if (* ls)p=(* ls)->top;while (p)q=p;p=p->n ext;delete (q);delete (* ls);*ls=nullreturn ;plinkstack s=init_linkstack();/bool checkpath( postion p)/判斷測試位置是否在棋盤內(nèi)if (p.x>=0&&p.x<8&&p.y>=0&&p.y<8) r

31、eturn true ;elsereturn false ;/void sortall ()/冒泡排序法.冒泡排序的基本概念是：依次比較相鄰的兩個(gè)數(shù)，將大數(shù)放在前面，小數(shù)放在后面。/保持穩(wěn)定性int temp;postion temps;for ( int i = 0 ; i < countaccessibility - 1 ; i + )for (int j = i + 1; j < countaccessibility ; j + )if(accessibility i > accessibility j )temps=n extpathi;n extpathi=next

32、pathj;n extpathj=temps;temp = accessibility i ;accessibility i = accessibility j ;accessibility j = temp; /end of if/ end of inner for/ end of outer for / end of sortall/void next_path(posti on p)postion testpos;for ( int i = 0 ; i < 8 ; i+ )/有八種到達(dá)的情況testpos.x =p.x + direct ay i .dx;/ 得岀 x,y坐標(biāo)的測試

33、位置testpos.y =p.y + direct_ay i .dy;if (checkpath(testpos)/判斷測試位置是否在棋盤內(nèi)nextpatharraypos=testpos ;/由測試位置給岀正確x,丫坐標(biāo)accessibility arraypos = access testpos.xtestpos.y;/ 利用對應(yīng)的x,y坐標(biāo)得岀相應(yīng)的可到達(dá)的路徑總數(shù)if (accessibility arraypos > 0 )/ accessibility arraypos = 0表明格子已經(jīng)被占據(jù)arraypos + ;/尋找空格子結(jié)束/結(jié)束for循環(huán),尋找結(jié)束countacc

34、essibility = arraypos ;/ 統(tǒng)計(jì)可達(dá)到數(shù)if (countaccessibility > 0 )arraypos = -1 ;/bool hasmorepath()/ arraypos + 1指向下一個(gè)可行的if ( (arraypos + 1 ) < countaccessibility)return true ;elsereturn false ; / hasmoreaccessible()方法結(jié)束/void nextaccessible()arraypos + ;/void domioving( postion p)for ( int i = 0 ; i

35、 < countaccessibility ; i + )datatype q;q.p=n extpathi;if (i=0) q.flag=1;if (countaccessibility>1)q.flag=2; elseq.flag=0;push li nkstack(s,q);access n extpathi.x n extpathi.y -; =/直到?jīng)]有路徑了accessp.x p.y = 0 ;/ 當(dāng)前位置置 0/void undomoving( postion p)/撤消移動(dòng)操作for ( int i = 0 ; i < countaccessibility

36、; i + )accessp.x p.y = own accessibility ;/void tour( postion p)cou ntmov ing + ;/如果64個(gè)格子都被走過，則返回if (countmoving = 63 ) tourpos cou ntmov ing .x=p.x ;tourpos cou ntmov ing .y =p.y ;success =true ;cou ntmov ing -;returnnext_path( p);/初試化 accessiblesquares 對象，給nextsquare分配內(nèi)存while (hasmorepath()/ 利用 ac

37、cessiblesquares() 對象調(diào)用 hasmoreaccessible() 成員函數(shù)/開始移動(dòng)domoving( p); / 調(diào)用 nextsquare.domoving()函數(shù)/把這一步記錄下來tourpos cou ntmov ing .x=p.x ;tourpos cou ntmov ing .y =p.y ;/嘗試下一步的移動(dòng)n extaccessible();tour ( n extpatharraypos);/如果64個(gè)格子都被走過，則返回if ( success ) cou ntmov ing -;return ;cou ntmov ing -;/void fprint

38、()/輸出路徑int order88=0;/-初始化for (int k=0;k<64;k+)ordertourposk.xtourposk.y=k;cout<< "n棋盤表示 n"cout«"0123 45 67n"cout«"for (int i=0;i<8;i+)printf("");pri ntf("%2d",i);for (int j=0;j<8;j+)printf("| %2d " ,orderij);pri ntf(&qu

39、ot;|");pri ntf("n");if (i=7)pri ntf(i!-+ " );elsepri ntf(i!+-+-+-+-+-+-+-+ " );pri ntf("n");printf("");/bool tour_next(postion p int j) _postion testpos;int count =0;for ( int i = 0 ; i < 8 ; i+ )/有八種到達(dá)的情況testpos.x =p.x + direct_ay i .dx;/ 得岀 x,y坐標(biāo)的測試位置testpos.y =p.y + direct ay i .dy;if (checkpath(testpos)/判斷測試位置是否在棋盤內(nèi)if ( access testpos.xtestpos.y!=o)/ 利用對應(yīng)的 x,y坐標(biāo)得岀相應(yīng)的可