資源描述：
《馬踏棋盤程序設計.doc》由會員上傳分享，免費在線閱讀，更多相關(guān)內(nèi)容在應用文檔-天天文庫。
1、問題描述設計一個國際象棋的馬踏棋盤的演示程序。基本要求將馬隨機放在國際象棋8*8的棋盤Board[8][8]的某個方格中，馬按走棋規(guī)則進行移動。要求每個方格只進入一次，走遍棋盤全部的64個方格。編制非遞歸程序，求出馬的行走路線，并按求出的行走路線，將數(shù)字1，2，3…….64一次填入一個8*8的方陣輸出之測試數(shù)據(jù)可自行指定一個馬的初始位置（i,j）,0<=i,j<=7.。實現(xiàn)提示一般說來，當馬位于位置（i,j）時，可以走到下列8個位置之一（i-2,j+1）,(i-1,j+2),(i+1,j+2),
2、(i+2,j+1),(i+2,j-1),(i+1,j-2),(i-1,j-2),(i-2,j-1)但是，如果（i，j）靠近棋盤的邊緣，上述有些位置可能超出棋盤范圍，成為不允許的位置。8個可能位置可以用一維數(shù)組Htry1[0…7]和HTry2[0..7]來表示：Htry101234567-2-11221-1-2Htry2012345671221-1-2-2-1位于（i,j）的馬可以走到新位置是在棋盤范圍內(nèi)的（i+Htry1[h],j+Htry2[h]）,其中h=0,1,….7.一．需求分析1．輸入
3、的形式和輸入值的范圍；分開輸入馬的初始行坐標X和列坐標Y，X和Y的范圍都是［0,7］。2．輸出的形式；一共提供了2種輸出方式：（1）以數(shù)組下標形式輸入，代表起始位置，i表示行標，j表示列標。（2）以棋盤形式輸出，每一格打印馬走的步數(shù)，這種方式比較直觀。3．程序所能達到的功能；讓馬從任一起點出發(fā)都能夠歷遍整個8×8的棋盤。二．概要設計1．設定棧的抽象數(shù)據(jù)類型定義：ADTStack{數(shù)據(jù)對象：D={ai
4、ai∈CharSet,i=1,2..,n}數(shù)據(jù)關(guān)系:R1={
5、ai-1,ai∈
6、D,i=2,...,n}基本操作:(這里僅列舉本題中使用的操作)InitStack(&S)操作結(jié)果:構(gòu)建一個空棧。Push(&S,e)操作結(jié)果:在棧頂插入新的元素。Pop（&S,&e）操作結(jié)果：將棧頂元素彈出。SetTop(S,&e)操作結(jié)果：將e設為棧頂元素。GetTop(S,&e)操作結(jié)果：將棧頂元素取出。StackEmpty(S)判斷棧是否為空}ADTStack2．本程序包含2個模塊(1).主程序模塊:Voidmain(){初始化棋盤；while(1){接受命令；處理命令；}執(zhí)行Path(
7、x,y);}(2).棧模塊－實現(xiàn)棧抽象數(shù)據(jù)類型3．探討每次選擇位置的“最佳策略”思路1）先求出每個坐標點的權(quán)值，即是該坐標下一步有幾個方向可以走2）權(quán)值越小,則被上一點選中的可能性就越大，下一個方向八個值的選擇順序保存MAP[X][Y][K]數(shù)組中，0<=K<=7，例如MAP[X][Y][0]保存的是下一步優(yōu)先選擇走的方向，MAP[X][Y][7]就是最后才走的。邊界的點最先走，然后再走中間。4．踏遍棋盤偽碼算法：While（）{若已經(jīng)走了64步,則{打印輸出結(jié)果；}否則{若該點所有方向已走完{
8、出棧}若該點所有方向未走完{若該點未走過且在棋盤內(nèi){入棧，已走步數(shù)加1}否則{*下一步方向加1}}}}三．詳細設計1．棧類型structSElemType{inta;intb;intdi;//方向編號intflag[8];//訪問過的方向數(shù)};棧的順序存儲表示typedefstructSqStack{SElemType*base;SElemType*top;intstacksize;};棧基本操作：StatusInitStack(SqStack*S){/*構(gòu)造一個空棧S*/(*S).base=(
9、SElemType*)malloc(STACK_INIT_SIZE*sizeof(SElemType));if(!(*S).base)exit(OVERFLOW);/*存儲分配失敗*/(*S).top=(*S).base;(*S).stacksize=STACK_INIT_SIZE;returnOK;}StatusStackEmpty(SqStackS){/*若棧S為空棧，則返回TRUE，否則返回FALSE*/if(S.top==S.base)returnTRUE;elsereturnFALSE
10、;}StatusGetTop(SqStackS,SElemType*e){/*若棧不空，則用e返回S的棧頂元素，并返回OK；否則返回ERROR/if(S.top>S.base){*e=*(S.top-1);returnOK;}elsereturnERROR;}StatusSetTop(SqStackS,SElemType*e){if(S.top>S.base){*(S.top-1)=*e;returnOK;}elsereturnERROR;}StatusPush(SqStack*S,SElemT
