資源描述：
《數(shù)據(jù)結構馬踏棋盤》由會員上傳分享，免費在線閱讀，更多相關內(nèi)容在行業(yè)資料-天天文庫。
1、實驗二：棧和隊列及其應用題目：馬踏棋盤班級：姓名：學號：一、問題描述設計一個國際象棋的馬踏遍棋盤的演示程序。二、基本要求將馬隨機放在國際象棋的8*8的棋盤Board[8][8]的某個方格中，馬按走棋規(guī)則進行移動。要求每個方格只進入一次，走遍棋盤上全部64個方格。編制非遞歸程序，求出馬的行走路線，并按求出的行走路線，將數(shù)字1,2，……，64依次填入一個8*8的方陣，輸出之。三、概要設計1.定義頭文件和預定義#include#defineMAXSIZE100#defineN82.起始坐標函數(shù)：voidIn
2、itLocation(intxi,intyi);3.探尋路徑函數(shù)：intTryPath(inti,intj);4.輸出路徑函數(shù)：voidDisplay();5.主程序：voidmain();四、詳細設計1.函數(shù)聲明voidInitLocation(intxi,intyi);//馬兒在棋盤上的起始位置坐標intTryPath(inti,intj);//馬兒每個方向進行嘗試，直到試完整個棋盤voidDisplay();//輸出馬兒行走的路徑2.起始坐標函數(shù)模塊voidInitLocation(intxi,intyi){in
3、tx,y;//定義棋盤的橫縱坐標變量top++;//棧指針指向第一個棧首stack[top].i=xi;//將起始位置的橫坐標進棧stack[top].j=yi;//將起始位置的縱坐標進棧stack[top].director=-1;//將起始位置的嘗試方向賦初值board[xi][yi]=top+1;//標記棋盤x=stack[top].i;//將起始位置的橫坐標賦給棋盤的橫坐標y=stack[top].j;//將起始位置的縱坐標賦給棋盤的縱坐標if(TryPath(x,y))//調(diào)用馬兒探尋函數(shù)，如果馬兒探尋整個棋
4、盤返回1否則返回0Display();//輸出馬兒的行走路徑elseprintf("無解");}3.探尋路徑函數(shù)模塊intTryPath(inti,intj){intfind,director,number,min;//定義幾個臨時變量inti1,j1,h,k,s;//定義幾個臨時變量inta[8],b1[8],b2[8],d[8];//定義幾個臨時數(shù)組while(top>-1)//棧不空時循環(huán){for(h=0;h<8;h++)//用數(shù)組a[8]記錄當前位置的下一個位置的可行路徑的條數(shù){number=0;i=stack
5、[top].i+Htry1[h];j=stack[top].j+Htry2[h];b1[h]=i;b2[h]=j;if(board[i][j]==0&&i>=0&&i<8&&j>=0&&j<8)//如果找到下一位置{for(k=0;k<8;k++){i1=b1[h]+Htry1[k];j1=b2[h]+Htry2[k];if(board[i1][j1]==0&&i1>=0&&i1<8&&j1>=0&&j1<8)//如果找到下一位置number++;//記錄條數(shù)}a[h]=number;//將條數(shù)存入數(shù)組a[8]中}}f
6、or(h=0;h<8;h++)//根據(jù)可行路徑條數(shù)小到大按下表排序放入數(shù)組d[8]中{min=9;for(k=0;k<8;k++)if(min>a[k]){min=a[k];d[h]=k;//將下表存入數(shù)組d[8]中s=k;}a[s]=9;}director=stack[top].director;if(top>=63)//如果走完整個棋盤返回1return(1);find=0;//表示沒有找到下一個位置for(h=director+1;h<8;h++)//向八個方向進行探尋{i=stack[top].i+Htry1[
7、d[h]];j=stack[top].j+Htry2[d[h]];if(board[i][j]==0&&i>=0&&i<8&&j>=0&&j<8)//如果找到下一位置{find=1;//表示找到下一個位置break;}}if(find==1)//如果找到下一個位置進棧{stack[top].director=director;//存儲棧結點的方向top++;//棧指針前移進棧stack[top].i=i;stack[top].j=j;stack[top].director=-1;//重新初始化下一棧結點的嘗試方向boa
8、rd[i][j]=top+1;//標記棋盤}else//否則退棧{board[stack[top].i][stack[top].j]=0;//清除棋盤的標記top--;//棧指針前移退棧}}return(0);}4.輸出路徑函數(shù)模塊voidDisplay(){inti,j;for(i=0;i
