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