馬踏棋盤 數(shù)據(jù)結構實踐報告

馬踏棋盤問題摘要：馬踏棋盤就是在國際象棋8X8棋盤上面，按照國際象棋規(guī)則中馬的行進規(guī)則，實現(xiàn)從任意初始位置，每個方格只進入一次，走遍棋盤上全部64個方格。理解棧的 “后進先出”的特性以及學會使用回溯。關鍵字：馬踏棋盤、遞歸、棧、回溯1引言馬踏棋盤就是在國際象棋8X8棋盤上面，按照國際象棋規(guī)則中馬的行進規(guī)則，實現(xiàn)從任意初始位置，每個方格只進入一次，走遍棋盤上全部64個方格。編制程序，求出馬的行走路線，并按求出的行走路線，將數(shù)字1，2.64依次填入一個8X8的方陣，并輸出它的行走路線。輸入：任意一個起始位置；輸出：無重復踏遍棋盤的結果，以數(shù)字1-64表示行走路線。2需求分析（1）需要輸出一個8X8的棋盤，可以采用二維數(shù)組的方法實現(xiàn)。（2）輸入馬的起始位置，必須保證輸入的數(shù)字在規(guī)定范圍內，即0<=X<=7,0<=Y<=7。（3）保證馬能走遍整個棋盤，并且不重復。（4）在棋盤上輸出馬的行走路線,標記好數(shù)字1、2、3直到64。3數(shù)據(jù)結構設計采用棧數(shù)組為存儲結構。#define maxsize 100struct int i; int j;int director;stackmaxsize;4算法設計4.1 馬的起始坐標void location(int x,int y) /馬的位置坐標的初始化top+;stacktop.i=x; /起始位置的橫坐標進棧stacktop.j=y; /起始位置的豎坐標進棧stacktop.director=-1;axy=top+1; /標記棋盤Try(x,y); /探尋的馬的行走路線4.2 路徑探尋函數(shù)void Try(int i,int j) int count,find,min,director; int i1,j1,h,k,s; int b8=-2,-2,-1,1,2,2,1,-1,c8=1,-1,-2,-2,-1,1,2,2; /存儲馬各個出口相對當前位置行、列坐標的增量數(shù)組 int b28,b18; for(h=0;h<=7;h+) /用數(shù)組b18記錄當前位置的下一個位置的可行路徑的條數(shù) count=0; i=stacktop.i+ch; j=stacktop.j+bh; if(i>=0&&i<=7&&j>=0&&j<=7&&aij=0) /如果找到下一個位置 for(k=0;k<=7;k+) i1=i+ck; j1=j+bk;if(i1>=0&&i1<=7&&j1>=0&&j1<=7&&ai1j1=0) /如果找到下一個位置 count+; /記錄條數(shù)b1h=count; /將條數(shù)存入b18中 for(h=0;h<=7;h+) /根據(jù)可行路徑條數(shù)的大小，從小到大排序，并放入數(shù)組b28中 min=9; for(k=0;k<=7;k+) if(min>b1k) min=b1k; b2h=k; s=k; b1s=9; find=0; director=stacktop.director; for(h=director+1;h<=7;h+)/向8個方向進行尋找i=stacktop.i+cb2h;j=stacktop.j+bb2h;if(i>=0&&i<=7&&j>=0&&j<=7&&aij=0)stacktop.director=h; /存儲棧的尋找方向top+; /進棧stacktop.i=i;stacktop.j=j;stacktop.director=-1;/重新初始化下一棧的方向 aij=top+1; find=1; /找到下一位置 break; if(find!=1)astacktop.istacktop.j=0; /清除棋盤的標記 top-; /退棧 if(top<63)Try(i,j); /遞歸4.3輸出函數(shù)void display()int i,j;for(i=0;i<=7;i+) for(j=0;j<=7;j+) printf("t%d ",aij); /輸出馬的行走路線 printf("nn");printf("n");5.程序實現(xiàn)5.1 主函數(shù)void main()int i,j,x,y;for(i=0;i<=7;i+) /棋盤的初始化for(j=0;j<=7;j+)aij=0;printf("輸入X Y (0=<X<=7,0=<Y<=7)n");scanf("%d%d",&x,&y);if(x>=0&&x<=7&&y>=0&&y<=7) /判斷輸入的起始位子是否正確location(x,y); display();else printf("錯誤n");5.2運行結果（1）當輸入不符合要求時 （2）正確輸入時5.3 算法分析（1）馬的起始坐標 一開始先建立一個棧數(shù)組，里面包括橫坐標和豎坐標還有方向。輸入馬的起始位置，進入坐標起始化函數(shù)，讓輸入的橫坐標和豎坐標進棧，并初始化方向，并且標記棋盤，指示此位置已走過，此時的位置是棧的第一個元素，進入路徑探尋函數(shù)。（2）路徑探尋函數(shù) 路徑探尋函數(shù)中有兩個分別存儲馬各個出口相對當前位置行、列坐標的增量數(shù)組。要使馬走遍所有的棋盤，必須要有一定的行走規(guī)律。我使用的是記錄當前位置的下一個位置的可行路徑的條數(shù)，并對它們進行排序，按從小到大的順序存儲在一個一維數(shù)組中。開始進行探尋，分別向8個方向探尋，如果找到一個方向可行，則存儲棧的尋找方向，再進棧，重新初始化棧的尋找方向，并用二維數(shù)組標記此位置，再使用遞歸進入下一次新的探尋。如果在某一次探尋中，沒能找到方向，則清除該位置的標記，并退棧，再次遞歸，回到上次的尋找方向（之前已經(jīng)存儲過棧的尋找方向），跳過已經(jīng)尋找過的方向，再進行探尋，直到全部棋盤都被走遍。（3）輸出函數(shù) 當馬走遍所有的棋盤時，輸出馬的行走路線，因為之前已經(jīng)把馬的行走路線記錄在二維數(shù)組中了，所以此時只需把二維數(shù)組中的標記輸出即可。6.設計體會 本次課程設計讓我學會了很多東西，使得我對于棧的理解更深入了，使用更加熟練。是此之前，我對于回溯并不是特別了解，但是這次設計讓我學會了回溯的基本概念以及基礎的用法。當一件事情有很多種方法進行時，我們要將所有的方法集合起來形成一個集合，再用一定的規(guī)律去調用這個集合內的方法。剛開始的時候，我并不能讓馬走遍所有的棋盤，但當我知道了回溯的思想之后，我修正了我的算法，最終使馬走遍所有的棋盤。我還考慮了遞歸與非遞歸的問題，在試驗了兩種方法之后，發(fā)現(xiàn)兩種都可以，在時間的復雜度上也沒有太大的差別（顯示棋盤的時間上），但我還是使用的是遞歸的方法來完成本次設計。參考文獻：1 嚴蔚敏、吳偉民編著數(shù)據(jù)結構（C語言版）北京：清華大學出版社，2 譚浩強主編C程序設計（第三版）北京：清華大學出版，20053 張蕊、呂濤主編C程序設計教程. 華中科技大學出版，2012