數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)-- 騎士游歷

1、<p>　　存檔資料 成績(jī)： 　 </p><p>　　課 程 設(shè) 計(jì) 報(bào) 告 書</p><p>　　所屬課程名稱 數(shù)據(jù)結(jié)構(gòu) </p><p>　　題 目 　 騎士游歷　　　　　 </p><p>　　分 院

2、 電信分院 　　 </p><p>　　專業(yè)班級(jí) </p><p>　　學(xué)　　號(hào) 　 　　 　　 　 </p><p>　　學(xué)生姓名 　 　　　　 　　　 &

3、lt;/p><p>　　指導(dǎo)教師 　 </p><p>　　2013 年 7月 5 日 </p><p><b>　　目　錄</b></p><p>　　第一章 課程設(shè)計(jì)內(nèi)容及要求2</p><p>　　第二章 課程設(shè)計(jì)的設(shè)計(jì)分析

4、與功能模塊1</p><p>　　2.1 設(shè)計(jì)分析1</p><p><b>　　(1)設(shè)計(jì)目的1</b></p><p><b>　　(2)任務(wù)分析1</b></p><p><b>　　1. 要求1</b></p><p><b&g

5、t;　　2. 輸入1</b></p><p>　　2.2 程序功能模塊圖1</p><p>　　第三章 流程圖設(shè)計(jì)的具體實(shí)現(xiàn)3</p><p>　　3.1 馬踏遍棋盤流程圖3</p><p>　　3.2 系統(tǒng)測(cè)試與調(diào)試5</p><p>　　第四章 源代碼程序設(shè)計(jì)9</p&g

6、t;<p>　　4.1 詳細(xì)設(shè)計(jì)9</p><p><b>　　創(chuàng)建9</b></p><p><b>　　操作9</b></p><p><b>　　顯示9</b></p><p>　　4.2 源代碼10</p><p>　

7、　第五章 課程設(shè)計(jì)心得13</p><p>　　第六章 參考文獻(xiàn)14</p><p>　　第七章 致謝15</p><p>　　第一章 課程設(shè)計(jì)內(nèi)容及要求</p><p>　　騎士游歷問題是一個(gè)古老而著名的問題,問題的描述是:在8×8格的國際象棋棋盤上,象棋馬能否從某個(gè)格子出發(fā)按照“馬跳

8、日”的規(guī)則跳遍所有64個(gè)格子最后 再回到出發(fā)的那個(gè)格子。國際象棋中的馬,英語為knight,恰好又意指中世紀(jì)西方世界的“騎士”,因此,這個(gè)問題又被稱為“騎士游歷。</p><p>　　在一個(gè)棋盤上（8行8列）放一個(gè)“馬”，按“馬走日字”的規(guī)則，馬要走到棋盤上每一個(gè)格子，且每個(gè)格子只走一次。</p><p>　　用回溯法深度優(yōu)先搜索，若尋找到滿足要求的解，則輸出；否則推回上一層往下一個(gè)方向搜

9、索。</p><p>　　對(duì)于當(dāng)前所在位置（x，y），依次枚舉8個(gè)方向搜索，直到找到一組可行解為止。使用剪枝有2處：</p><p>　　第一、使用Warnsdorff's rule，枚舉當(dāng)前解得時(shí)候優(yōu)先選擇下一步可行步數(shù)最少的方向；</p><p>　　第二、若第一點(diǎn)中的方向存在不止一個(gè)，則優(yōu)先選擇離中心位置較遠(yuǎn)的方向；每次都從中心點(diǎn)開始出發(fā)，求出一條合法

10、路徑后再平移映射回待求路徑。</p><p>　　第二章 課程設(shè)計(jì)的設(shè)計(jì)分析與功能模塊</p><p><b>　　2.1 設(shè)計(jì)分析</b></p><p><b>　　(1)設(shè)計(jì)目的</b></p><p>　　1.熟練使用C語言編寫程序，強(qiáng)化模塊設(shè)計(jì)理念。</p><

11、p>　　2.設(shè)計(jì)一個(gè)國際象棋馬踏棋盤的演示程序。</p><p>　　3.理解棧的特性“后進(jìn)先出” 和隊(duì)列的特性“先進(jìn)先出”。</p><p>　　4.初步掌握軟件開發(fā)過程的問題分析、系統(tǒng)設(shè)計(jì)、程序編 碼、測(cè)試等基本方法和技能。</p><p><b>　　(2)任務(wù)分析</b></p><p><b>

12、　　1. 要求</b></p><p>　　在國際象棋8×8棋盤上面，按照國際象棋規(guī)則中馬的行進(jìn)規(guī)則，實(shí)現(xiàn)從任意初始位置，每個(gè)方格只進(jìn)入一次，走遍棋盤上全部64個(gè)方格。編制程序，求出馬的行走路線，并按求出的行走路線，將數(shù)字1，2，…，64依次填入一個(gè)8×8的方陣，并輸出它的行走路線。</p><p><b>　　2. 輸入</b><

13、;/p><p>　　任意一個(gè)起始位置；輸出：無重復(fù)踏遍棋盤的結(jié)果，以數(shù)字1-64表示行走路線。</p><p>　　2.2 程序功能模塊圖</p><p>　　各模塊之間的調(diào)用關(guān)系，如圖所示：</p><p>　　第三章 流程圖設(shè)計(jì)的具體實(shí)現(xiàn)</p><p>　　3.1 馬踏遍棋盤流程圖</p><

14、;p>　　3.2 系統(tǒng)測(cè)試與調(diào)試</p><p>　　1.程序代碼的輸入和運(yùn)行</p><p>　　新建C文件并輸入代碼到工作界面當(dāng)中，仔細(xì)檢查，運(yùn)行代碼，如下圖所示，圖3.2-1表示程序的輸入和運(yùn)行，</p><p><b>　　圖3.2—1</b></p><p><b>　　圖3.2—2</b

15、></p><p><b>　　2.程序代碼的調(diào)試</b></p><p>　　經(jīng)過請(qǐng)教老師和同學(xué)們的幫助，還有自己的多次調(diào)試，終于修改好了程序代碼，運(yùn)行后準(zhǔn)確無誤，如圖3.2-3所示：</p><p><b>　　圖3.2-3</b></p><p><b>　　3 程序的顯示結(jié)果

16、</b></p><p>　　在命令窗口中輸入了棋子的不同起點(diǎn)，運(yùn)行都成功了。如下圖所示：</p><p>　　圖3.2-4 以（1，1）為起點(diǎn)</p><p>　　圖3.2-5 以（0，5）為起點(diǎn)</p><p>　　圖3.2-6 以（2，0）為起點(diǎn)</p><p>　　圖3.2-6 以（4，0）為起點(diǎn)&

17、lt;/p><p>　　圖3.2-6 以（0，3）為起點(diǎn)</p><p>　　第四章 源代碼程序設(shè)計(jì)</p><p><b>　　4.1 詳細(xì)設(shè)計(jì)</b></p><p><b>　　創(chuàng)建</b></p><p>　　創(chuàng)建一個(gè)8行8列的棋盤：</p>&l

18、t;p>　　#include <stdio.h></p><p>　　int board[8][8] = {0};</p><p>　　int main(void) {</p><p>　　for(i = 0; i < 8; i++) {</p><p>　　for(j = 0; j < 8; j++) {<

19、;/p><p>　　printf("%2d ", board[i][j]);</p><p><b>　　}</b></p><p>　　putchar('\n');</p><p><b>　　}</b></p><p><b>　

20、　return 0;</b></p><p><b>　　}</b></p><p><b>　　操作</b></p><p>　　輸入騎士的初始位置，進(jìn)行騎士游歷操作：</p><p><b>　　int i, j;</b></p><p>

21、;　　printf("輸入起始點(diǎn)：");</p><p>　　int travel(int x, int y) {</p><p>　　int ktmove1[8] = {-2, -1, 1, 2, 2, 1, -1, -2};</p><p>　　int ktmove2[8] = {1, 2, 2, 1, -1, -2, -2, -1};<

22、;/p><p><b>　　顯示</b></p><p><b>　　顯示出游歷結(jié)果：</b></p><p>　　int startx, starty;</p><p><b>　　int i, j;</b></p><p>　　printf("

23、輸入起始點(diǎn)：");</p><p>　　scanf("%d %d", &startx, &starty);</p><p>　　if(travel(startx, starty)) {</p><p>　　printf("游歷完成！\n");</p><p><b>

24、　　}</b></p><p><b>　　else {</b></p><p>　　printf("游歷失?。n");</p><p><b>　　}</b></p><p><b>　　4.2 源代碼</b></p><

25、;p>　　#include <stdio.h> </p><p>　　#define N 5</p><p>　　#define NSQUARE N*N </p><p>　　int HorseTry(int i, int x, int y, int h[N+1][N+1]); </p><p>　　static int a

26、[9] = {0, 2, 1, -1, -2, -2, -1, 1, 2};</p><p>　　static int b[9] = {0, 1, 2, 2, 1, -1, -2, -2, -1}; </p><p><b>　　main()</b></p><p><b>　　{</b></p><p

27、>　　int i, j, flag, x, y;</p><p>　　static int h[N+1][N+1] ={0}; </p><p>　　printf("Input the initial position x,y:");</p><p>　　scanf("%d,%d", &x, &y);&l

28、t;/p><p>　　h[x][y] = 1;</p><p>　　flag = HorseTry(2, x, y, h);</p><p><b>　　if (flag)</b></p><p><b>　　{</b></p><p>　　printf("Output

29、:\n");</p><p>　　for (i=1; i<=N; i++)</p><p><b>　　{</b></p><p>　　for (j=1; j<=N; j++)</p><p><b>　　{</b></p><p>　　printf(&

30、quot;%5d", h[i][j]);</p><p><b>　　}</b></p><p>　　printf("\n");</p><p><b>　　}</b></p><p><b>　　}</b></p><p>

31、;<b>　　else</b></p><p><b>　　{</b></p><p>　　printf("No solution!\n");</p><p><b>　　}</b></p><p><b>　　} </b></p

32、><p>　　int HorseTry(int i, int x, int y, int h[N+1][N+1])</p><p><b>　　{</b></p><p>　　int u, v, flag, count = 0;</p><p><b>　　do{</b></p><

33、p><b>　　count++;</b></p><p><b>　　flag = 0;</b></p><p>　　u = x + a[count];</p><p>　　v = y + b[count];</p><p>　　if ((u>=1&&u<=N) &

34、amp;& (v>=1&&v<=N) && h[u][v]==0)</p><p><b>　　{</b></p><p>　　h[u][v] = i;</p><p>　　if (i < NSQUARE)</p><p><b>　　{</b&g

35、t;</p><p>　　flag = HorseTry(i+1, u, v, h);</p><p>　　if (!flag) h[u][v] = 0;</p><p><b>　　}</b></p><p><b>　　else</b></p><p><b>

36、　　{</b></p><p><b>　　flag = 1;</b></p><p><b>　　}</b></p><p><b>　　}</b></p><p>　　}while (!flag && count<8);</p>

37、<p>　　return flag;</p><p><b>　　}</b></p><p>　　第五章 課程設(shè)計(jì)心得</p><p>　　通過兩個(gè)星期對(duì)騎士游歷這個(gè)程序的分析，我對(duì)C語言這門課程有了進(jìn)一步的鞏固，對(duì)我們現(xiàn)在學(xué)的《數(shù)據(jù)結(jié)構(gòu)（C語言版）》的知識(shí)有了一個(gè)很好的回顧和掌握，我的在這個(gè)過程中我也知道自己能力的不足

38、，在面對(duì)問題的時(shí)候更應(yīng)該要請(qǐng)教老師和同學(xué)，自己也可以動(dòng)手查閱資料。我們不單是要提高自己的理論能力，還要多去實(shí)踐，這樣我們就能夠更好的提高自己。</p><p>　　課程設(shè)計(jì)是我們專業(yè)課程知識(shí)綜合應(yīng)用的實(shí)踐訓(xùn)練，是我們邁向社會(huì)，從事職業(yè)工作前一個(gè)必不少的過程．”千里之行始于足下”，通過這次課程設(shè)計(jì)，我深深體會(huì)到這句千古名言的真正含義．我今天認(rèn)真的進(jìn)行課程設(shè)計(jì)，學(xué)會(huì)腳踏實(shí)地邁開這一步，就是為明天能穩(wěn)健地在社會(huì)大潮中奔

39、跑打下堅(jiān)實(shí)的基礎(chǔ)．</p><p>　　在這次設(shè)計(jì)過程中，體現(xiàn)出自己?jiǎn)为?dú)設(shè)計(jì)的能力以及綜合運(yùn)用知識(shí)的能力，體會(huì)了學(xué)以致用、突出自己勞動(dòng)成果的喜悅心情，從中發(fā)現(xiàn)自己平時(shí)學(xué)習(xí)的不足和薄弱環(huán)節(jié)，從而加以彌補(bǔ)。</p><p>　　第六章 參考文獻(xiàn)</p><p>　　[1] 謝希仁. 計(jì)算機(jī)網(wǎng)絡(luò)（第五版）[M]. 北京：電子工業(yè)出版社，2008年2月&l

40、t;/p><p>　　[2] 胡小強(qiáng) 計(jì)算機(jī)網(wǎng)絡(luò)[M] 北京：北京郵電大學(xué)出版社2005 年1月</p><p>　　[3] 嚴(yán)蔚敏 李冬梅 吳偉民 數(shù)據(jù)結(jié)構(gòu)（C語言版）[M] 人民郵電出版社，2011年2月</p><p>　　[4] 李麗娟 C語言程序設(shè)計(jì)教程（第二版）[M] 北京：人民郵電出版社2009年3月</p><p>　　

41、［5］ 朱戰(zhàn)立.《數(shù)據(jù)結(jié)構(gòu)(C++語言描述)》(第二版本).高等教育出版社。</p><p>　　[6] 陸蓓. C語言程序設(shè)計(jì)（第二版）[M]. 北京：科學(xué)出版社，2009</p><p>　　[7] 嚴(yán)蔚敏. 數(shù)據(jù)結(jié)構(gòu)：C語言版[M]. 北京：清華大學(xué)出版社，2007.</p><p>　　第七章 致謝 </p>&l

42、t;p>　　感謝學(xué)院領(lǐng)導(dǎo)與分院領(lǐng)導(dǎo)的大力支持，感謝指導(dǎo)老師的</p><p>　　辛勤指導(dǎo)，感謝同學(xué)們的熱心幫助，感謝室友的無私幫助。</p><p>　　在此感謝我們的指導(dǎo)老師，老師嚴(yán)謹(jǐn)細(xì)致、一絲不茍的作風(fēng)一直是我工作、學(xué)習(xí)中的榜樣；老師循循善誘的教導(dǎo)和不拘一格的思路給予我無盡的啟迪；這次課程設(shè)計(jì)的每個(gè)細(xì)節(jié)和每個(gè)數(shù)據(jù)，都離不開老師您的細(xì)心指導(dǎo)。而您開朗的個(gè)性和寬容的態(tài)度，幫助我能夠