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

1、數(shù)據(jù)結(jié)構(gòu)課程設計報告課程設計題目：馬踏棋盤姓 名：張程浩院 系：通信工程專 業(yè)：信息安全年 級：2011學 號：指導教師：任雪萍2012年 11 月 26 日(任雪萍編寫)目 錄一、課程設計目的3二、任務分析3三、分析設計3四、調(diào)試分析5五、測試結(jié)果5六、小結(jié)6七、用戶手冊6八、附錄6九、參考文獻8一、課程設計目的(1) 熟練使用C語言編寫程序，強化模塊設計理念；(2) 設計一個國際象棋馬踏棋盤的演示程序。(3) 理解棧的特性“后進先出” 和隊列的特性“先進先出”。(4) 初步掌握軟件開發(fā)過程的問題分析、系統(tǒng)設計、程序編碼、測試等基本方法和技能；二、任務分析（1）要求：在國際象棋8×

2、8棋盤上面，按照國際象棋規(guī)則中馬的行進規(guī)則，實現(xiàn)從任意初始位置，每個方格只進入一次，走遍棋盤上全部64個方格。編制程序，求出馬的行走路線，并按求出的行走路線，將數(shù)字1，2，64依次填入一個8×8的方陣，并輸出它的行走路線。（2）輸入：任意一個起始位置；輸出：無重復踏遍棋盤的結(jié)果，以數(shù)字1-64表示行走路線。三、分析設計l 需要處理的數(shù)據(jù)的邏輯結(jié)構(gòu)：線性結(jié)構(gòu)l 合適的存儲結(jié)構(gòu)：順序儲存l 設計好的數(shù)據(jù)類型：#define BS8/棋盤大小typedef int Status; int step; int board88=0; /定義棋盤 int mayway9;/儲存可能的路徑 int

3、 Htry18=-2,-1,1,2,2,1,-1,-2,Htry28=1,2,2,1,-1,-2,-2,-1;/*存儲馬各個出口位置相對當前位置列下標的增量數(shù)組*/typedef struct /位置存儲表達方式 int i;/行坐標int j;/列坐標int from; /存儲下一步所選方向SElemType;typedef struct SElemType*base;/在棧構(gòu)造之前和銷毀之后，base的值為NULLSElemType*top;/棧頂指針intstacksize;/當前已經(jīng)分配的儲存空間，以元素為單位Stack;Stack Path;l 本程序包含模塊：1、主程序模塊：voi

4、d main()定義變量；接受命令；處理命令；退出；輸入的初始位置是否正確主程序模塊起始坐標函數(shù)模塊探尋路徑函數(shù)模塊 結(jié)束輸出路徑函數(shù)模塊塊 是否2、起始坐標函數(shù)模塊馬兒在棋盤上的起始位置；3、探尋路徑函數(shù)模塊馬兒每個方向進行嘗試，直到試完整個棋盤；4、輸出路徑函數(shù)模塊輸出馬兒行走的路徑； 各模塊之間的調(diào)用關系： l 與功能對應的模塊劃分定義：/構(gòu)造一個空棧SStatus InitStack(Stack &s);/若棧不空，則用e返回s的棧頂元素，返回OK；否則返回ERRORStatus GetTop(Stack s,SElemType &e);/插入元素e為新的棧頂元素Sta

5、tus Push(Stack &s,SElemType e);/若棧不空，則刪除s的棧頂元素，并用e返回其值，并返回OK；否則返回ERRORStatus Pop(Stack &s,SElemType &e);/從棧底到棧頂依次對棧中每個元素輸出。Status StackTraverse(Stack s);/若當前坐標在有效棋盤內(nèi)返回OK；否則返回ERRORStatus InBoard(int i,int j);/貪心法判斷下一步的可能選位置，并把可選的最佳位置依次存入mayway，并返回OK；/若找不到位置返回ERRORStatus TryPath(SElemType

6、s, int mayway);Status NextPath(SElemType &cur,int mayway);l 函數(shù)調(diào)用關系： 四、調(diào)試分析1、調(diào)試中的問題（1）調(diào)試問題：本程序設計過程中采用多文件組件工程的方式進行。在頭文件中定義了全局變量，解決方案：將全局變量 定義為staic型變量?；蛘咴诼暶髦惺褂胑xtern關鍵字（2）調(diào)試問題：雖然編譯都能通過，但是運行時卻出錯，程序不能終止，只有通過人工方式結(jié)束程序，可能是在某些地方出現(xiàn)了無限死循環(huán)了，馬兒回溯的時候，下一次又有可能走那個方向，這樣就出現(xiàn)了死循環(huán)。解決方案：標記馬兒選擇的方向director。在結(jié)點結(jié)構(gòu)設計上加入di

7、rector（3）調(diào)試問題：在調(diào)試過程中，對變量的監(jiān)視發(fā)現(xiàn)棧頂元素中director無法更新，我原本的程序代碼設計是cur. director= k解決方案：(Path.top-1)->from=k;/保存下一步 所選最佳路徑 下標（4）調(diào)試問題：當走到邊界時，有可走的路，但是程序卻回溯了。解決方案：for (int k = 1+direction; k < 9, k <= mayway0 ; k+)/向所得的方向進行探尋五、測試結(jié)果六、小結(jié)通過本次實驗的編寫，能夠掌握棧的性質(zhì)以及它的應用。這個程序也讓我頭疼了幾次，就是運行速度很慢，要等很久才能輸出結(jié)果，這樣的話很占內(nèi)存資源

8、，而且CPU的使用記錄也很高，主要是它需要的運算太多，所以CPU 使用記錄也是很高的。通過網(wǎng)上查詢一些算法了解到了貪心法，并運用到本程序的設計中，大大提升了算法的效率。在該程序的編制過程中留下了一些思考的問題，就是馬兒從一個起點位置開始探尋，最后馬兒探尋成功的路徑會不會是不只一條路徑，可能還有多條路徑，由于時間和精力的限制沒有去深究，但是這應該值的思考的。在用順序棧來實現(xiàn)該程序之前，也嘗試過用鏈棧來做，但是發(fā)現(xiàn)如果用鏈棧來做的話，在存儲調(diào)用的時候不是很方便，或許用鏈棧來做應該是對自己的一種挑戰(zhàn)。盡管沒有用鏈棧做不過，用順尋棧來做在編制該程序中也收獲不小。 七、用戶手冊本程序在DOS環(huán)境下運行，

9、輸入馬的起始位置即可。八、附錄程序清單如下：8 / 8文檔可自由編輯打印Status InitStack(Stack &s)/構(gòu)造一個空棧Ss.base = (SElemType*)malloc(STACK_INIT_SIZE*sizeof(SElemType);if(!s.base)exit(OVERFLOW);/儲存分配失敗s.top=s.base;s.stacksize=STACK_INIT_SIZE;return OK;Status GetTop(Stack s,SElemType &e)/若棧不空，則用e返回s的棧頂元素，返回OK；否則返回ERRORif (s.top

10、 = s.base) return ERROR;e= *(s.top - 1);return OK;Status Push(Stack &s,SElemType e)/插入元素e為新的棧頂元素if(s.top - s.base >= s.stacksize)s.base = (SElemType*)realloc(s.base, (s.stacksize+ STACKINCREMENT) *sizeof(SElemType) );if (!s.base)exit(OVERFLOW);s.top= s.base+ s.stacksize;s.stacksize += STACKIN

11、CREMENT;*s.top+= e;return OK;Status Pop(Stack &s,SElemType &e)/若棧不空，則刪除s的棧頂元素，并用e返回其值，并返回OK；否則返回ERRORif(s.top = s.base)return ERROR;e = * -s.top;return OK;Status StackTraverse(Stack s)/從棧底到棧頂依次對棧中每個元素輸出。int x,y;cout<<"開始"<<endl;while(s.top>s.base)x=s.base->i;y=s.b

12、ase->j; cout<<"->("<<x<<","<<y<<")"s.base+;cout<<"結(jié)束"<<endl;return OK;Status InBoard(int i,int j)/若當前坐標在有效棋盤內(nèi)返回OK；否則返回ERRORif(i >=0 && i<=7 && j>=0 && j<=7 )return OK;elseretur

13、n ERROR;Status TryPath(SElemType s, int mayway)/貪心法判斷下一步的可能選位置，并把可選的最佳位置依次存入mayway，并返回OK；/若找不到位置返回ERRORint choices,count=0;int stepchoices9=10,10,10,10,10,10,10,10,10;/儲存第二步后的可能路徑數(shù),初始化為9int ni=s.i;int nj=s.j;int i,t;for ( i = 1; i <= 8; i+)maywayi=i-1;for (int k=0; k<8; k+) int find=0;if( InBo

14、ard( (ni+Htry1k),(nj+Htry2k) ) &&( board ni+Htry1k nj+Htry2k =0) ) /第一步成功choices=9;for (int h=0; h<8; h+) if( InBoard( (ni+Htry1k+Htry1h),(nj+Htry2k+Htry2h) ) &&( board ni+Htry1k+Htry1h nj+Htry2k+Htry2h =0) )/第二步仍滿足if (choices=9)/第一步成功后，第一次 第二步仍成功choices=0;find=1;choices+;/累積第二步的路

15、徑數(shù)if (BS*BS-1 = step)/若為最后一步，無貪心法第二步stepchoicesk+1=0;count+;elsestepchoicesk+1=choices;/第二步后的可走路徑數(shù)存入stepchoices8if (find)count+;mayway0=count;/*貪心法全部計算后，對路徑數(shù)進行排序*/for( i=1;i<=9;i+)/冒泡排序 /根據(jù)可走路徑數(shù)由小到大排序?qū)?走法存入數(shù)組mayway8for(int m=1;m<=8-i;m+)if(stepchoicesm>stepchoicesm+1)t=stepchoicesm;/可走路徑數(shù)進行

16、排序stepchoicesm=stepchoicesm+1;stepchoicesm+1=t;t=maywaym;/可走路徑進行排序maywaym=maywaym+1;maywaym+1=t;return OK;Status NextPath(SElemType &cur,int mayway)/貪心法尋找可行路徑int direction=cur.from;/初始位置嘗試的位置方向設為-1SElemType p;for (int k = 1+direction; k < 9, k <= mayway0 ; k+)/向所得的方向進行探尋int xt=cur.i+Htry1

17、maywayk ;int yt=cur.j+Htry2 maywayk ;if( InBoard( xt,yt ) && (boardxtyt=0) )/如果找到下一個位置boardxtyt= +step;(Path.top-1)->from=k;/保存下一步 所選最佳路徑 下標/Path.top-1cur.from= k p.i=xt;p.j=yt;p.from=0;Push(Path,p); return OK;return ERROR;void main()SElemType origin,pope,cur;/起點元素int curx,cury;/初始位置 x行坐標

18、，y列坐標/int mayway9;/儲存可能的路徑step=0;InitStack(Path);H1:cout<<"請輸入馬的起始位置坐標（x,y）0x7 0y7，中間用空格隔開，例如（2，3）請輸入： 2 3"<<endl;cin>>curx>>cury;if (curx<1|curx>8|cury<1| cury>8)cout<<"輸入錯誤，請重新輸入！"<<endl;goto H1;origin.i=curx;origin.j=cury;origin.from=0;/初始位置嘗試的位置方向設為0boardcurxcury=+step;Push(Path,origin);while (step<64)GetTop(Path,cur);TryPath(cur,mayway);/貪心法尋找可行路徑if (!NextPath(cur,mayway)