2023年實驗報告馬踏棋盤

2.4題馬踏棋盤題目：設(shè)計一個國際象棋的馬踏棋盤的演示程序班級:。姓名：。學(xué)號：完畢口期：—.需求分析(1)輸入的形式和輸入值的范圍：輸入馬的初始行坐標(biāo)X和列坐標(biāo)Y,X和Y的范圍都是［1,8］。(2)輸出形式:以數(shù)組下表的形式輸入，i為行標(biāo),j為列標(biāo)，用空格符號隔開。以棋盤形式輸出,每一格打印馬走的步數(shù)，這種方式比較直觀(3)程序所能達(dá)成的功能：讓馬從任意起點出發(fā)都可以遍歷整個8*8的棋盤。(4)測試數(shù)據(jù)，涉及對的輸入及輸出結(jié)果和具有錯誤的輸入及其輸出結(jié)果。數(shù)據(jù)可以任定，只要l<=x,y<=8就可以了。對的的輸出結(jié)果為一個二維數(shù)組,每個元素的值表達(dá)馬行走的第幾步，若輸入有錯,則程序會顯示：“輸入有誤！請重新輸入……”并且規(guī)定用戶重新輸入數(shù)據(jù),直至輸入對的為止。二.概要設(shè)計(1)、位置的存儲表達(dá)方式(2)typedefstruct{

P:俄的文若\C-Free\Temp除命名3.exe"■aPleaseinputInputx■2Inputy=3beginwith11inpoi?tpoint<l<=x<=8andboard：l<=y<=8>i▲23141924291417520130151825283235623582716132163346554059263453225744471239764455437604148523562950433811638513661104942請按任意鍵繼續(xù)...,xl五.原程序代碼#inc1ude<stdio.h>#defineMAXSIZE100#defineN8intboard[8][8];〃定義棋盤intHtryl[8]={1,-1,—2,2,2,1,?1,-2};/*存儲馬各個出口位置相對當(dāng)前位置行下標(biāo)的*/intHtry2[8]={2,-2,1,1,-1,-2,2,-l};/*存儲馬各個出口位置相對當(dāng)前位置列下標(biāo)的增量數(shù)組*/structStack{〃定義棧類型inti;inti;inti;//行坐標(biāo)intj;inti;//行坐標(biāo)intdirector;//存儲方向}stack[MAXSIZE]；〃定義一個棧數(shù)組inttop=-l;//棧指針voidInitLocation(intxijntyi);〃馬兒在棋盤上的起始位置坐標(biāo)intTryPathfintiJntj);〃馬兒每個方向進(jìn)行嘗試，直到試完整個棋盤voidDisplay()；//輸出馬兒行走的途徑voidInitLocation(intxi,intyi)(intx,y;〃定義棋盤的橫縱坐標(biāo)變量top++;〃棧指針指向第一個棧首stack[top],i=xi；//將起始位置的橫坐標(biāo)進(jìn)棧stack[top].j=yi；//將起始位置的縱坐標(biāo)進(jìn)棧stack[top].director=-l；//將起始位置的嘗試方向賦初值board[xi][yi]=top+l；〃標(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否則返回0Disp1ay();//輸出馬兒的行走途徑elseprintf("無解”);)intTryPath(inti,intj){intfind,director,number,min;//定義幾個臨時變量int//定義幾個臨時變量inta[8],bl[8],b2[8],d[8]；//定義幾個臨時數(shù)組whiIe(top>—1)//棧不空時循環(huán){for(h=0；h<8;h++)〃用數(shù)組a[8]記錄當(dāng)前位置的下一個位置的可行途徑的條數(shù)(number=0;i=stack[top].i+Htryl[h];j=stack[top].j+Htry2[h]；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];jl=b2[h]+Htry2[k];if(board[il][jl]==0&&il>=0&&il<8&&jl>=0&&jl<8)〃假如找到下一位置number++；〃記錄條數(shù))a[h]=number;〃將條數(shù)存入數(shù)組a[8]中)}for(h=0；h<8;h++)〃根據(jù)可行途徑條數(shù)小到大按下表排序放入數(shù)組d[8]中{min=9;for(k=0;kV8;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;〃表達(dá)沒有找到下一個位置for(h=director+l;h<8；h++)〃向八個方向進(jìn)行探尋(i=stack[top].i+Htry1[d[h]];j=stack[top].j+Htry2[d[h]]；if(board[i][j]==0&&i>=0&&i<8&&j>=0&&jV8)〃假如找到下一位置find=l;〃表達(dá)找到下一個位置))if(find==l)〃假如找到下一個位置進(jìn)棧(stack[top].director=director;〃存儲棧結(jié)點的方向top++；//棧指針前移進(jìn)棧stack[top].i=i；stack[top].j=j;。stack[top].director=-l;//重新初始化下一，棧結(jié)點的嘗試方向board[i][j]=top+1;〃標(biāo)記棋盤)e1se//否則退棧(。board[stack[top].i][stack[top].j]=0;〃清除棋盤的標(biāo)記。top-;//棧指針前移退棧)return(0);voidDisplay()inti,j;for(i=0;i<N；i++){for(j=0；j<N;j++)printf("\t%d'\boardti][j]);〃輸出馬兒在棋盤上走過的途徑oprintf("\n\n")；)printf("\n");)intmain()(inti,j;intx,y;。for(i=0;i<N；i++)//初始化棋盤for(j=0;j<N；j++)。printf("Pleaseinputimportpoint(l<=x<=8andl<=y<=8)\n")；printf("Inputx=")；scanf("%d",&x)；//輸入起始位置的橫坐標(biāo)printf("Inputy=");scanf（"％d"，&y）;〃輸入起始位置的縱坐標(biāo)if(x>=l&&x<=8&&y>=l&&y<=8)break;printf("Yourinputisworng!!!\n")：printf("beginwith%dboard:\n\n",8*(x-l)+y);InitLocation(x-l,y—1）;〃調(diào)用起始坐標(biāo)函數(shù)inty；intfrom;}Point；(2)、棧的存儲方式#defineSTACKSIZE70#defineSTACKINCREASE10typedefstructStack{Point*top;Point*base;intstacksize;}；(1)、設(shè)定棧的抽象數(shù)據(jù)類型定義：ADTStack-數(shù)據(jù)對象:D={ai|aiWEIemSet,i=l,2””n,n20}數(shù)據(jù)關(guān)系:R1={<ai-l,ai>|ai-l,aiED,i=2,,,,n}約定an端為棧頂，ai端為棧頂?；静僮鳎褐糏nitStack(&s)操作結(jié)果:構(gòu)造一個空棧s,DestroyStack(&s)初始條件：棧s己存在。操作結(jié)果：棧S被銷毀。ClearStack(&s)初始條件：棧s已存在。操作結(jié)果:棧s清為空棧。StackEmpty(&s)初始條件：棧s已存在。操作結(jié)果:若棧s為空棧，則返回TRUE,否則返回FALSE。StackLength(s);初始條件：棧s存在。操作結(jié)果:返回s的元素個數(shù),即棧的長度。GetTop(s,&e);初始條件:棧s己存在且非空。操作結(jié)果：用e返回s的棧頂元素。Push(&s,e)初始條件:棧s已存在。操作結(jié)果:插入元素e為新的棧頂元素。Pop(&s,&e)初始條件：棧s存在且非空。

操作結(jié)果：刪除棧頂元素，并用e返回。stackTraverse(s,visit())初始條件:棧s存在且非空。操作結(jié)果：從棧底到棧頂依次對s的每個元素調(diào)用Visit()o一旦Visit()失敗，則操作失敗。}ADTStack本程序包含模塊：1、主程序模塊：voidmain(){定義變量;接受命令;解決命令;退出；}2、起始坐標(biāo)函數(shù)模塊一一馬兒在棋盤上的起始位置；3、探尋途徑函數(shù)模塊一一馬兒每個方向進(jìn)行嘗試,直到試完整個棋盤；4、輸出途徑函數(shù)模塊一一輸出馬兒行走的途徑；三.具體設(shè)計1.函數(shù)聲明VoidInitLocation(intxi,intyi)；//馬兒在棋盤上的起始位置標(biāo)intTryPath(inti,intj)；//馬兒每個方向進(jìn)行嘗試，直到試完整個棋盤voidDisplayf);//輸出馬兒行走的途徑2.起始坐標(biāo)函數(shù)模塊voidInitLocation(intxijntyi){intx.y;〃定義棋盤的橫縱坐標(biāo)變量top++top++；top++；//棧指針指向第一個棧首stack[top].i=xi;top++；//棧指針指向第一個棧首stack[top].j=yi;〃將起始位置的縱坐標(biāo)進(jìn)棧stack[top].director=-1;//將起始位置的嘗試方向賦初值board[xi][yi]=top+1;〃標(biāo)記棋盤x=stack[top].i;//將起始位置的橫坐標(biāo)賦給棋盤的橫標(biāo)y=stack[top].j;〃將起始位置的縱坐標(biāo)賦給棋盤的縱坐標(biāo)iffTryPathtx,y))〃調(diào)用馬兒探尋函數(shù)，假如馬兒探尋整個棋盤返回1否則0Display();//輸出馬兒的行走途徑elseprint「(”無解");)3.探尋途徑函數(shù)模塊intTryPath(intijntj){intfind,director,number,min；//定義幾個臨時變量inti1,jl,h,k,s;〃定義幾個臨時變量inta[8Lbl[8Lb2[8Ld[8];//定義幾個臨時數(shù)組whi1e(top>-1)〃棧不空時循環(huán)(for(h=0;h<8;h++)//用數(shù)組a[8]記錄當(dāng)前位置的下一個位置的可行途徑的條數(shù)

number=O；i=stack[top].i+Htryl[h];j=stack[top].j4-Htry2[h];bl[h]=i;b2[h]=j;if(board[i][j]==0&&i>=0&&i<8&&j>=0&&j<8)〃假如找到下一位置{for(k=0;k<8;k++)(il=bl[h]+Htryl[k];jl=b2[h]+Htry2[k];if(board[il][jl]==0&&i1>=0&&il<8&&j1>=0&&jl<8)0。。。3。//假如找到下一位置number++;number++;number++;〃記錄條數(shù)a[h]=number;number++;〃記錄條數(shù)a[h]=number;a[h]=number;〃將條數(shù)存入數(shù)組a[h]=number;〃將條數(shù)存入數(shù)組a[8]中for(h=0;h<8;h++)//根據(jù)可行途徑條數(shù)小到大按下表排序放d[8]中{min=9;for(k=0;k<8;k++)if(min>a[k]){min=a[k]；od[h]=k;//將下表存入數(shù)組d[8]中s=k;}a[s]=9;)director=stack[top],director；if(top>=63)〃假如走完整個棋盤返回1return(1);find=0;〃表達(dá)沒有找到下一個位置for(h=director+l;h<8;h++)〃向八個方向進(jìn)行探尋{i=stack[top].i+Htryl[d[h]];j=stack