資源描述：
《數(shù)據(jù)結(jié)構(gòu) 馬踏棋盤》由會員上傳分享，免費在線閱讀，更多相關(guān)內(nèi)容在行業(yè)資料-天天文庫。
1、實現(xiàn)順序?；蜓h(huán)隊列的存儲一需求分析1.1理解棧的特性“后進先出”和隊列的特性“先進先出”。僅僅認(rèn)識到棧和隊列是兩種特殊的線性表是遠遠不夠的，本次實驗的目的在于更深入的了解棧和隊列的特性，以便在實際問題背景下靈活運用他們。在了解他特性的基礎(chǔ)上，還將鞏固對這種結(jié)構(gòu)的構(gòu)造方法的理解。1.2要求：在國際象棋8×8棋盤上面，按照國際象棋規(guī)則中馬的行進規(guī)則，實現(xiàn)從任意初始位置，每個方格只進入一次，走遍棋盤上全部64個方格。編制程序，求出馬的行走路線，并按求出的行走路線，將數(shù)字1，2，…，64依次填入一個8×8的方陣，并輸出它的行走路線（棋盤如圖所示）。輸入：任意一
2、個起始位置；輸出：無重復(fù)踏遍棋盤的結(jié)果，以數(shù)字1-64表示行走路線。?012345670??8?1???1?7???2??2???H????3?6???3??4??5?4???5????????6????????7????????二概要設(shè)計為了實現(xiàn)上述程序功能，可以采用順序?；蛘哝湕泶鎯λ臄?shù)據(jù)，本實驗所需要的存儲空間不是很大，不需動態(tài)的開辟很多空間，所以采用相對簡單的順序棧來存儲數(shù)據(jù)，既方便有簡單，而用鏈棧在實現(xiàn)上相對比順序棧復(fù)雜的一點。82.1順序棧的抽象數(shù)據(jù)類型定義：ADTStack{數(shù)據(jù)對象：D={ai
3、ai∈（0，1，…，9），i=0,1，2
4、，…，n，n≥0}數(shù)據(jù)關(guān)系：R={
5、ai-1,ai∈D,i=1,2，…，n}}ADTStack2.2本程序包含三個模塊：1、主程序模塊：voidmain(){定義變量；接受命令；處理命令；退出；}2、起始坐標(biāo)函數(shù)模塊——馬兒在棋盤上的起始位置；3、探尋路徑函數(shù)模塊——馬兒每個方向進行嘗試，直到試完整個棋盤；4、輸出路徑函數(shù)模塊——輸出馬兒行走的路徑；2.3各模塊之間的調(diào)用關(guān)系：主程序模塊輸入的初始位置是否正確否起始坐標(biāo)函數(shù)模塊是探尋路徑函數(shù)模塊輸出路徑函數(shù)模塊塊結(jié)束8三詳細(xì)設(shè)計3.1定義頭文件和預(yù)定義#include#
6、defineMAXSIZE100#defineN83.2數(shù)據(jù)類型定義intboard[8][8];//定義棋盤intHtry1[8]={1,-1,-2,2,2,1,-1,-2};/*存儲馬各個出口位置相對當(dāng)前位置行下標(biāo)的增量數(shù)組*/intHtry2[8]={2,-2,1,1,-1,-2,2,-1};/*存儲馬各個出口位置相對當(dāng)前位置列下標(biāo)的增量數(shù)組*/structStack{//定義棧類型inti;//行坐標(biāo)intj;//列坐標(biāo)intdirector;//存儲方向}stack[MAXSIZE];//定義一個棧數(shù)組inttop=-1;//棧指針3.3函數(shù)聲
7、明voidInitLocation(intxi,intyi);//馬兒在棋盤上的起始位置坐標(biāo)intTryPath(inti,intj);//馬兒每個方向進行嘗試，直到試完整個棋盤voidDisplay();//輸出馬兒行走的路徑3.4起始坐標(biāo)函數(shù)模塊voidInitLocation(intxi,intyi){intx,y;//定義棋盤的橫縱坐標(biāo)變量top++;//棧指針指向第一個棧首stack[top].i=xi;//將起始位置的橫坐標(biāo)進棧stack[top].j=yi;//將起始位置的縱坐標(biāo)進棧stack[top].director=-1;//將起始位
8、置的嘗試方向賦初值board[xi][yi]=top+1;//標(biāo)記棋盤x=stack[top].i;//將起始位置的橫坐標(biāo)賦給棋盤的橫坐標(biāo)y=stack[top].j;//將起始位置的縱坐標(biāo)賦給棋盤的縱坐標(biāo)if(TryPath(x,y))//調(diào)用馬兒探尋函數(shù)，如果馬兒探尋整個棋盤返回1否則返回0Display();//輸出馬兒的行走路徑elseprintf("無解");}83.5探尋路徑函數(shù)模塊intTryPath(inti,intj){intfind,director,number,min;//定義幾個臨時變量inti1,j1,h,k,s;//定義幾個
9、臨時變量inta[8],b1[8],b2[8],d[8];//定義幾個臨時數(shù)組while(top>-1)//棧不空時循環(huán){for(h=0;h<8;h++)//用數(shù)組a[8]記錄當(dāng)前位置的下一個位置的可行路徑的條數(shù){number=0;i=stack[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
10、[k];if(board[i1][j1]==0&&i1>=0&&i1<8&&j1
