自-马踏棋盘报告 武汉理工大学

一.问题描述一个国际象棋的马踏棋盘的演示程序。基本要求:将马随机放在国际象棋8×8　的棋盘Boａrd［8］[8]的某个方格中,马按走棋规则进行移动。要求每个方格只进入一次,走遍棋盘全部的64个方格。编制非递归程序，求出马的行走路线，并按求出的行走路线,将数字１,2,3,„，64　一次填入一个8×8的方阵输出之。二．实验目的1、对数据结构基本理论和存储结构及算法设计有更加深入的理解；2、了解栈的特性，以便在实际问题背景下灵活运用他们；3、提高在实际设计操作中系统、结构确定、算法选择、数学建模和信息加工的能力。三．程序设计１.顺序栈的抽象数据类型定义：ADTＳtａcｋ{数据对象:D＝{ai|　ａｉ∈(０,1,…,9），i=０,1，2,…，n,n≥0}数据关系:R={<　aｉ-1,ai>|aｉ－1,ａi∈Ｄ,ｉ=１,2，…，n}｝　ADTStａｃｋ2.本程序包含三个模块:(1)主程序模块:void　ｍａin()｛定义变量；接受命令；处理命令；退出;}（2）起始坐标函数模块——马儿在棋盘上的起始位置；(3）探寻路径函数模块——马儿每个方向进行尝试，直到试完整个棋盘；（4)输出路径函数模块——输出马儿行走的路径；３．主要算法设计　主程序马的初始位置是否正确起始坐标函数是探寻路径函数输出路径函数结果4．设计功能的分析和实现（1)起始坐标函数vｏｉd　ＩｎiｔLocatｉｏｎ(intｘｉ,iｎt　ｙi）;　作用:将马的起始位置先送给栈,然后送给棋盘上的位置(２）探寻路径函数　intTryＰath(ｉｎｔi,ｉntｊ）作用:用来寻找马在棋盘上的下个位置,如果没有找到，就回溯到上一个位置。(３）输出路径函数　　vｏiｄDiｓplay()　作用：输出马在整个棋盘上的路径四.调试1.在调试的过程中出现的问题与解决问题一：在刚开始写完程序后初次运行发现有较多错误。原因:大多数为语法和字符错误,由于粗心大意造成的。虽然都是小错误，但在书写的过程中会无意搞错。解决方法：根据提示的错误进行修改。直到“0eｒrｏr（s)，0　warninｇ(ｓ）”。这些错误在一定程度上说明对编写程序的不熟悉。问题二：输入马的位置时，不能判断这个初始位置的合法性原因:代码书写过程中未对马的位置进行限制解决方案:对不合理的代码进行修改。对马在棋盘上的位置进行设定，并书写当马位置输入错误时的循环程序。问题三：在未修改的程序中运行，出现运算时间很长的情况原因:在程序的书写过程中，代码的书写不够简练，导致运行过慢解决方案:在于同学互相沟通和交流的情况下，尽力简化代码,提升运行速度。虽然我尽力对程序进行简化,但运行速度依然不是很快。２.对设计和编程的讨论与分析(１）本次实验的主要目的是在于掌握和理解栈的特性和它的应用。在编制该程序中遇到了很多问题。首先，在开始刚编制程序的时候遇到的问题是，程序编译都通不过，主要在一些细节的问题上，还有在程序的返回值在刚开始时也没有正确返回。经过编译慢慢调试,编译都能通过,没有错误和警告。（２)标记好马尝试的方向后，编译运行，但是运行结果却不符合程序所要求的结果，说明在算法上肯定有错误,检查发现,马儿走的坐标没有控制后,它的横纵坐标必须控制0到7之间，否则的话马儿就会踏出棋盘以外，这样输出的结果就不对。还有就是棋盘走过的位置要标记一下,以便下次走不重复走，当回溯的时候的记得把标记给清掉，这个地方有时候也很容易混淆。五．源程序及实验结果#ｉｎclｕde＂stdafx.ｈ"#iｎclude＃defｉneＭＡXSIZE１０0#deｆｉne　N8ｉｎtboaｒd［8]［8];　／／定义棋盘ｉｎtＨｔry1[８]={-2,-１,１,2,2，1,-1，-2｝；　／＊存储马各个出口位置相对当前位置行下标的增量数组*/int　Htｒy2[８]=｛1，2,2,１,-1,-2,-2，-1｝；　　　　　　　　　/＊存储马各个出口位置相对当前位置列下标的增量数组＊/stｒuctＳtack{　　　//定义栈类型ﻩintｉ；　　　//行坐标ｉnt　j;　　　　　／/列坐标　int　directoｒ;　　//存储方向}stａck［MAXSIZＥ];　　　//定义一个栈数组inｔtop=-1;　　　　　　/／栈指针voiｄIｎitLoｃatｉｏn(intxi，intｙi)；//马儿在棋盘上的起始位置坐标iｎtTｒyPath（inｔi,intj);　　　　//马儿每个方向进行尝试,直到试完整个棋盘voｉdDisplay(）;　　　　　　　／/输出马儿行走的路径voidIniｔLocation（intxｉ,ｉntyi)　//起始坐标函数{ﻩinｔx，y;　　　　／/定义棋盘的横纵坐标变量ﻩtop+＋;　　　//栈指针指向第一个栈首stacｋ[toｐ].i＝ｘi;　／/将起始位置的横坐标进栈stack[ｔｏp].ｊ＝yｉ;　//将起始位置的纵坐标进栈ﻩstack[ｔop].dｉreｃtoｒ=-１;／／将起始位置的尝试方向赋初值bｏａrｄ[xｉ][yi］=ｔop＋1;　/／标记棋盘ﻩx=staｃｋ[top］.i;　／/将起始位置的横坐标赋给棋盘的横坐标ﻩｙ=stａck[toｐ].j;　　　　　／/将起始位置的纵坐标赋给棋盘的纵坐标ｉｆ（TｒｙPatｈ(x,y))　　//调用马儿探寻函数，如果马儿探寻整个棋盘返回１否则返回0ﻩＤisplay()；　　　//输出马儿的行走路径else　　　　　　prｉｎｔf("无解＂）；　　}ｉnt　ＴryPath(inti,ｉｎtj)　　　　　//探寻路径函数　　　{ｉntfｉnd,direcｔｏr,number,miｎ；/／定义几个临时变量inｔ　i1,ｊ１,ｈ,ｋ,s；　　　　　/／定义几个临时变量ｉnta［８],b1[8],b2[8］,d[8];　　//定义几个临时数组whiｌｅ(top＞-1)　　　　　　　//栈不空时循环{ﻩﻩfｏr(h＝0;h<８；h++)//用数组a［8]记录当前位置的下一个位置的可行路径的条数ﻩﻩ{ﻩﻩﻩnumbeｒ＝0;ﻩ　i＝ｓtacｋ[tｏp］.i+Hｔｒy1[h];ﻩj=stack[top].j+Hｔry2[h]；ﻩﻩb1［h］=i;　ﻩｂ2［h］=j；ﻩif(board［i]［j］=＝0＆&i＞＝0＆＆i<８&&j>=０&&j<８)　　//如果找到下一位置{ﻩﻩﻩｆｏｒ(k=0;k<8;ｋ+＋）ﻩ{ﻩﻩﻩi１＝b１［h]+Htry1[k］；　　　ｊ1＝b2[h]+Hｔrｙ２［ｋ］;ﻩ　ｉf（bｏarｄ[ｉ1][j1]=＝０&&i1>=0&&ｉ1<8&&j1>=0&&j1<8)　　　　　　　　　　//如果找到下一位置ﻩﻩ　　　nｕmｂer++;　　　//记录条数ﻩ}ﻩﻩａ[h］=nuｍbｅr;　　　　　　　//将条数存入数组a[8]中ﻩﻩ}ﻩ}ｆｏｒ(ｈ=０;h<8;h＋＋)　/／根据可行路径条数小到大按下表排序放入数组d[8］中{ﻩﻩmin=9;ﻩ　ﻩfｏr(ｋ=0；ｋ<８;k＋+)ﻩｉf(mｉn>ａ[ｋ］)ﻩﻩﻩ{ﻩﻩﻩﻩmin=a[k］；ﻩ　d［ｈ]=k;　　　／/将下表存入数组d［８]中　　s=ｋ;ﻩﻩ}ﻩﻩ　a[s]=9;ﻩﻩ｝direcｔor＝ｓtaｃk[top］．ｄiｒecｔor；　　ﻩif（top>＝63）　//如果走完整个棋盘返回1ﻩﻩretｕrｎ(1);fiｎｄ=0；　　　　　　　　　　//表示没有找到下一个位置ﻩfｏr（h＝dirｅctor＋1;h<8；h++)　／／向八个方向进行探寻{ﻩi=staｃｋ［top］．i+Ｈｔry1［d[h]］;　　j=sｔaｃk[tｏp].ｊ+Ｈｔｒｙ2[d[ｈ]];if(boarｄ[i][j]=＝0&＆i>＝０＆&i＜8&&j＞＝0＆＆j＜8)／/如果找到下一位置ﻩ{ﻩﻩｆiｎd=1；　　/／表示找到下一个位置ﻩﻩbreaｋ;ﻩﻩ}ﻩ｝ﻩﻩif(find==1）//如果找到下一个位置进栈ﻩ{ﻩsｔacｋ[top]．dｉｒectoｒ=dｉrｅｃtor;//存储栈结点的方向　ﻩﻩｔｏp++;　　　//栈指针前移进栈ﻩﻩsｔack[tｏp]．i＝i；ﻩﻩsｔack[ｔｏｐ].j＝j;ﻩｓｔacｋ[ｔoｐ].dｉrector＝-1;//重新初始化下一栈结点的尝试方向ﻩboard[i][j]=ｔｏp＋1；　//标记棋盘｝ﻩﻩelse　　　　　　　//否则退栈ﻩ｛ﻩﻩﻩboaｒd［stack[tｏp］.i］[sｔａck［top］.j]＝0;//清除棋盘的标记ﻩﻩtop－-;　　//栈指针前移退栈ﻩﻩ}}ﻩreｔurn(0）;｝vｏidDisplay()　　　　　　／/输出路径函数｛inｔi,j;ｆor(ｉ=0；i＜N;i++){ﻩfor(ｊ＝0;ｊ=1&＆x<=8＆&y>＝1＆＆y<=8)brｅａk;ﻩﻩprinｔｆ("对不起，你的输入有误,请重新输入!!!＼n")；}ｐrinｔｆ(“棋盘可以表示为：＼n＼ｎ”)；ＩｎitLoｃation(x-１,y－１);／／调用起始坐标函数}当输入的马在棋盘中位置不对时,出现的情况为:当输入马在棋盘上位置为(3,4)时,马在棋盘上的路线为: