2023年实验报告马踏棋盘VIP

2.4题马踏棋盘题目：设计一个国际象棋的马踏棋盘的演示程序班级:。姓名：。学号：完毕口期：—.需求分析(1)输入的形式和输入值的范围：输入马的初始行坐标X和列坐标Y,X和Y的范围都是［1,8］。(2)输出形式:以数组下表的形式输入，i为行标,j为列标，用空格符号隔开。以棋盘形式输出,每一格打印马走的步数，这种方式比较直观(3)程序所能达成的功能：让马从任意起点出发都可以遍历整个8*8的棋盘。(4)测试数据，涉及对的输入及输出结果和具有错误的输入及其输出结果。数据可以任定，只要l<=x,y<=8就可以了。对的的输出结果为一个二维数组,每个元素的值表达马行走的第几步，若输入有错,则程序会显示：“输入有误！请重新输入……”并且规定用户重新输入数据,直至输入对的为止。二.概要设计(1)、位置的存储表达方式(2)typedefstruct{

P:俄的文若\C-Free\Temp除命名3.exe"■aPleaseinputInputx■2Inputy=3beginwith11inpoi»tpoint<l<=x<=8andboard：l<=y<=8>i▲23141924291417520130151825283235623582716132163346554059263453225744471239764455437604148523562950433811638513661104942请按任意键继续...,xl五.原程序代码#inc1ude<stdio.h>#defineMAXSIZE100#defineN8intboard[8][8];〃定义棋盘intHtryl[8]={1,-1,—2,2,2,1,・1,-2};/*存储马各个出口位置相对当前位置行下标的*/intHtry2[8]={2,-2,1,1,-1,-2,2,-l};/*存储马各个出口位置相对当前位置列下标的增量数组*/structStack{〃定义栈类型inti;inti;inti;//行坐标intj;inti;//行坐标intdirector;//存储方向}stack[MAXSIZE]；〃定义一个栈数组inttop=-l;//栈指针voidInitLocation(intxijntyi);〃马儿在棋盘上的起始位置坐标intTryPathfintiJntj);〃马儿每个方向进行尝试，直到试完整个棋盘voidDisplay()；//输出马儿行走的途径voidInitLocation(intxi,intyi)(intx,y;〃定义棋盘的横纵坐标变量top++;〃栈指针指向第一个栈首stack[top],i=xi；//将起始位置的横坐标进栈stack[top].j=yi；//将起始位置的纵坐标进栈stack[top].director=-l；//将起始位置的尝试方向赋初值board[xi][yi]=top+l；〃标记棋盘x=stack[top],i;//将起始位置的横坐标赋给棋盘的横坐标y=stack[top].j;〃将起始位置的纵坐标赋给棋盘的纵坐标if(TryPath(x,y))//调用马儿探寻函数，假如马儿探寻整个棋盘返回1否则返回0Disp1ay();//输出马儿的行走途径elseprintf("无解”);)intTryPath(inti,intj){intfind,director,number,min;//定义几个临时变量int//定义几个临时变量inta[8],bl[8],b2[8],d[8]；//定义几个临时数组whiIe(top>—1)//栈不空时循环{for(h=0；h<8;h++)〃用数组a[8]记录当前位置的下一个位置的可行途径的条数(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++；〃记录条数)a[h]=number;〃将条数存入数组a[8]中)}for(h=0；h<8;h++)〃根据可行途径条数小到大按下表排序放入数组d[8]中{min=9;for(k=0;kV8;k++)If(min>a[k])min=a[k]；d[h]=k;//将下表存入数组d[8]中s=k；)a[s]=9；)director=stack[top],director;if(top>=63)〃假如走完整个棋盘返回1return(1);find=0;〃表达没有找到下一个位置for(h=director+l;h<8；h++)〃向八个方向进行探寻(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;〃表达找到下一个位置))if(find==l)〃假如找到下一个位置进栈(stack[top].director=director;〃存储栈结点的方向top++；//栈指针前移进栈stack[top].i=i；stack[top].j=j;。stack[top].director=-l;//重新初始化下一，栈结点的尝试方向board[i][j]=top+1;〃标记棋盘)e1se//否则退栈(。board[stack[top].i][stack[top].j]=0;〃清除棋盘的标记。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)；//输入起始位置的横坐标printf("Inputy=");scanf（"％d"，&y）;〃输入起始位置的纵坐标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）;〃调用起始坐标函数inty；intfrom;}Point；(2)、栈的存储方式#defineSTACKSIZE70#defineSTACKINCREASE10typedefstructStack{Point*top;Point*base;intstacksize;}；(1)、设定栈的抽象数据类型定义：ADTStack-数据对象:D={ai|aiWEIemSet,i=l,2””n,n20}数据关系:R1={<ai-l,ai>|ai-l,aiED,i=2,,,,n}约定an端为栈顶，ai端为栈顶。基本操作：旨InitStack(&s)操作结果:构造一个空栈s,DestroyStack(&s)初始条件：栈s己存在。操作结果：栈S被销毁。ClearStack(&s)初始条件：栈s已存在。操作结果:栈s清为空栈。StackEmpty(&s)初始条件：栈s已存在。操作结果:若栈s为空栈，则返回TRUE,否则返回FALSE。StackLength(s);初始条件：栈s存在。操作结果:返回s的元素个数,即栈的长度。GetTop(s,&e);初始条件:栈s己存在且非空。操作结果：用e返回s的栈顶元素。Push(&s,e)初始条件:栈s已存在。操作结果:插入元素e为新的栈顶元素。Pop(&s,&e)初始条件：栈s存在且非空。

操作结果：删除栈顶元素，并用e返回。stackTraverse(s,visit())初始条件:栈s存在且非空。操作结果：从栈底到栈顶依次对s的每个元素调用Visit()o一旦Visit()失败，则操作失败。}ADTStack本程序包含模块：1、主程序模块：voidmain(){定义变量;接受命令;解决命令;退出；}2、起始坐标函数模块一一马儿在棋盘上的起始位置；3、探寻途径函数模块一一马儿每个方向进行尝试,直到试完整个棋盘；4、输出途径函数模块一一输出马儿行走的途径；三.具体设计1.函数声明VoidInitLocation(intxi,intyi)；//马儿在棋盘上的起始位置标intTryPath(inti,intj)；//马儿每个方向进行尝试，直到试完整个棋盘voidDisplayf);//输出马儿行走的途径2.起始坐标函数模块voidInitLocation(intxijntyi){intx.y;〃定义棋盘的横纵坐标变量top++top++；top++；//栈指针指向第一个栈首stack[top].i=xi;top++；//栈指针指向第一个栈首stack[top].j=yi;〃将起始位置的纵坐标进栈stack[top].director=-1;//将起始位置的尝试方向赋初值board[xi][yi]=top+1;〃标记棋盘x=stack[top].i;//将起始位置的横坐标赋给棋盘的横标y=stack[top].j;〃将起始位置的纵坐标赋给棋盘的纵坐标iffTryPathtx,y))〃调用马儿探寻函数，假如马儿探寻整个棋盘返回1否则0Display();//输出马儿的行走途径elseprint「(”无解");)3.探寻途径函数模块intTryPath(intijntj){intfind,director,number,min；//定义几个临时变量inti1,jl,h,k,s;〃定义几个临时变量inta[8Lbl[8Lb2[8Ld[8];//定义几个临时数组whi1e(top>-1)〃栈不空时循环(for(h=0;h<8;h++)//用数组a[8]记录当前位置的下一个位置的可行途径的条数

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++;〃记录条数a[h]=number;number++;〃记录条数a[h]=number;a[h]=number;〃将条数存入数组a[h]=number;〃将条数存入数组a[8]中for(h=0;h<8;h++)//根据可行途径条数小到大按下表排序放d[8]中{min=9;for(k=0;k<8;k++)if(min>a[k]){min=a[k]；od[h]=k;//将下表存入数组d[8]中s=k;}a[s]=9;)director=stack[top],director；if(top>=63)〃假如走完整个棋盘返回1return(1);find=0;〃表达没有找到下一个位置for(h=director+l;h<8;h++)〃向八个方向进行探寻{i=stack[top].i+Htryl[d[h]];j=stack