棧和隊(duì)列試驗(yàn)報(bào)告課案

1、專業(yè)名稱班級(jí)：學(xué)生姓名西安郵電大學(xué)（計(jì)算機(jī)學(xué)院）課內(nèi)實(shí)驗(yàn)報(bào)告實(shí)驗(yàn)名稱：一棧和隊(duì)列的應(yīng)用學(xué)號(hào)（8位）：指導(dǎo)教師：實(shí)驗(yàn)時(shí)間:實(shí)驗(yàn)?zāi)康募皩?shí)驗(yàn)環(huán)境1.實(shí)驗(yàn)?zāi)康?1)熟練使用棧和隊(duì)列解決實(shí)際問(wèn)題；(2)了解并掌握數(shù)據(jù)結(jié)構(gòu)與算法的設(shè)計(jì)方法，具備初步的獨(dú)立分析和設(shè)計(jì)能力；(3)初步掌握軟件開發(fā)過(guò)程的問(wèn)題分析、系統(tǒng)設(shè)計(jì)、程序編碼、測(cè)試等基本方法和技能；(4)提高綜合運(yùn)用所學(xué)的理論知識(shí)和方法獨(dú)立分析和解決問(wèn)題的能力；2.實(shí)驗(yàn)環(huán)境Dev-C+實(shí)驗(yàn)內(nèi)容設(shè)計(jì)一個(gè)國(guó)際象棋的馬踏棋盤的演示過(guò)程?；疽螅簩ⅠR隨機(jī)放在國(guó)際象棋的8*8棋盤Board88的某個(gè)方格中，馬按走棋規(guī)則進(jìn)行移動(dòng)，要求每個(gè)方格只進(jìn)行一次，走遍整個(gè)棋盤

2、的全部64個(gè)方格。編制非遞歸程序，求出馬的行走路線，并按求出的行走路線，將數(shù)字1,2,，64依次填入一個(gè)8*8的方陣，輸出之。測(cè)試數(shù)據(jù)：可自行制定一個(gè)馬的初始位置(i,j),0=IJv=7o第1步：實(shí)現(xiàn)提示一般來(lái)說(shuō),當(dāng)馬位于位置(ij)時(shí)，可以走到下列8個(gè)位置之一：(i-2,j+1),(il,j+2)(i+l,j+2),(i+2,j+l)(i+2J-l),(i+1J-2)(i-1,j-2),(i-2zj-1)但是，如果(i,j)靠近棋盤的邊緣,上述有些位置可能要超出棋盤位置，成為不允許的位置。8個(gè)可能位置可以用一位數(shù)組HTrylO刀和HTry20刀來(lái)表示：01234567-2-11212212

3、1-1-2-1-2-2-1位于(i,j)的馬可以走到新位置是在棋盤范圍內(nèi)的(i+HTrylh,j+HTry2h),其中h=0.7o第2步：需求分析(1)輸入的形式和輸入值的范圍：輸入馬的初始行坐標(biāo)X和列坐標(biāo)丫,乂和丫的范圍都是口網(wǎng)。(2)輸出形式：以數(shù)組下表的形式輸入，i為行標(biāo)J為列標(biāo)，用空格符號(hào)隔開。以棋盤形式輸出，每一格打印馬走的步數(shù)，這種方式比較直觀(3)程序所能達(dá)到的功能：讓馬從任意起點(diǎn)出發(fā)都能夠遍歷整個(gè)8*8的棋盤。(4)測(cè)試數(shù)據(jù)，包括正確輸入及輸出結(jié)果和含有錯(cuò)誤的輸入及其輸出結(jié)果。數(shù)據(jù)可以任定，只要l=xzyv=8就可以了。正確的輸出結(jié)果為一個(gè)二維數(shù)組，每個(gè)元素的值表示馬行走的第幾

4、步，若輸并且要求用戶重新輸入數(shù)據(jù)，直至輸入正確為止。入有錯(cuò)，則程序會(huì)顯示：輸入有誤！請(qǐng)重新輸入/第3步，算法設(shè)計(jì)思想:1、輸入馬所在初始位置的坐標(biāo)值，考慮到用戶的輸入習(xí)慣，此處l=x,yv=8;2、將輸入的初始值進(jìn)棧；3、設(shè)置一個(gè)while循環(huán)，循環(huán)條件為count64;4、取出棧頂元素；5、定義flag標(biāo)志變量的值；6、按照SetRound函數(shù)逆時(shí)針順序優(yōu)先原則，找棧頂元素周圍未被占用的7、新位置。若存在該位置，則令order的值等于該新位置的坐標(biāo),并入棧;&否則彈出棧頂元素；9、再次回到第步while循環(huán)進(jìn)行判斷；10、輸出一個(gè)8*8的方陣，所示數(shù)字即為相應(yīng)步驟。四測(cè)試數(shù)據(jù)及運(yùn)行結(jié)果1 .

5、正常測(cè)試數(shù)據(jù)(3組)及運(yùn)行結(jié)果；Pleaseincutinoortoointandl=v=8.)InputK=1yInput=2withbegin2.“board:16118611451326319481535(52)3522370455百33644?2049b936&31224346354457ao27214223275411a425404369382941225263928710度迥財(cái)播入法全：2 .非正常測(cè)試數(shù)據(jù)（2組）及運(yùn)行結(jié)果Q-7五.總結(jié)1 .實(shí)驗(yàn)過(guò)程中遇到的問(wèn)題及解決辦法。(例如：記錄編譯時(shí)錯(cuò)誤信息，根據(jù)實(shí)驗(yàn)過(guò)程中出現(xiàn)的編譯錯(cuò)誤信息分析出錯(cuò)原因，并改正錯(cuò)誤。)2 .對(duì)設(shè)計(jì)及調(diào)試過(guò)

6、程的心得體會(huì)。馬踏棋盤，作為一種經(jīng)典的棧的應(yīng)用例子，從大方面將,剛看到這名字就知道用棧來(lái)實(shí)現(xiàn)，但是，當(dāng)你面對(duì)這個(gè)題目，打開編譯器之后想寫的時(shí)候，發(fā)現(xiàn)又不是那么容易，很多細(xì)節(jié)需要認(rèn)真的分析，比如結(jié)構(gòu)體的定義，棋子因?yàn)槭嵌S的，所以對(duì)于用來(lái)存儲(chǔ)棋盤的橫縱坐標(biāo)，需要用到兩個(gè)變量，定義兩整型變量x,yo剛開始只定義了這兩個(gè)變量，后來(lái)發(fā)現(xiàn)如果找到下一個(gè)位置，而下一個(gè)位置有很多個(gè)都是符合的，如何選取最優(yōu)的呢？最有的有可能是最先找到的，可找到后還得繼續(xù)找下去，萬(wàn)一沒(méi)有比他更優(yōu)的，則要退回來(lái)，如果沒(méi)有變量from來(lái)記錄前一位置最優(yōu)位置，就無(wú)法找到之前的點(diǎn)，所以要多加一個(gè)變量；其外就是程序的調(diào)試，調(diào)試確實(shí)需要很

7、大的耐心，有時(shí)候只是你的大意而輸錯(cuò)了字符或輸入輸出格式不符合就會(huì)出現(xiàn)很多看起來(lái)不可思議很難發(fā)現(xiàn)的錯(cuò)誤，這也說(shuō)明了編程的時(shí)候一定要認(rèn)真有耐心六.附錄：源代碼(請(qǐng)把源代碼按照實(shí)驗(yàn)內(nèi)容附到其后)#include#defineMAXSIZE100#defineN8/(2)、數(shù)據(jù)類型定義intboard88;/定義棋盤intHtryl8=L-L-2,22L-L-2;/*存儲(chǔ)馬各個(gè)出口位置相對(duì)當(dāng)前位置行下標(biāo)的增量數(shù)組*/intHtry28=2,-2,l,L-L-22-l;/*存儲(chǔ)馬各個(gè)出口位置相對(duì)當(dāng)前位置列下標(biāo)的增量數(shù)組*/structStack/定義棧類型inti;行坐標(biāo)intj;/列坐標(biāo)intdire

8、ctor;/存儲(chǔ)方向stackMAXSIZE;/定義一個(gè)棧數(shù)組inttop=-l;棧指針(3)、函數(shù)聲明voidInitLocation(intxijntyi);/馬兒在棋盤上的起始位置坐標(biāo)intTryPath(intijntj);/馬兒每個(gè)方向進(jìn)行嘗試，直到試完整個(gè)棋盤voidDisplay();/輸出馬兒行走的路徑int x,y;top + +;stacktop.i=xi;stacktop.j=yi;stacktop.director=-l; / boardxiyi=top +1;x=stacktop.i;y=stacktop.j;回0Display();else printf(無(wú)解)；(

9、5)、探尋路徑函數(shù)模塊int TryPath(int ijnt j)/(4)、起始坐標(biāo)函數(shù)模塊voidInitLocation(intxijntyi)(定義棋盤的橫縱坐標(biāo)變量棧指針指向第一個(gè)棧首將起始位置的橫坐標(biāo)進(jìn)棧將起始位置的縱坐標(biāo)進(jìn)棧將起始位置的嘗試方向賦初值標(biāo)記棋盤將起始位置的橫坐標(biāo)賦給棋盤的橫坐標(biāo)輸出馬兒的行走路徑intfind,director,number,min;定義幾個(gè)臨時(shí)變量intiljl,h,k,s;/定義幾個(gè)臨時(shí)變量if(TryPath(xzy)調(diào)用馬兒探尋函數(shù)，如果馬兒探尋整個(gè)棋盤返回1否則返inta8zbl8Lb28Ld8;/定義幾個(gè)臨時(shí)數(shù)組while(top-l)/

10、棧不空時(shí)循環(huán)(for(h=0;h=0&iv8&j=0&的8)如果找至!下一位置for(k=0;k=0&il=084&jl8)/$D果找到下一位置number+;/記錄條數(shù)ah=number;/將條數(shù)存入數(shù)組a8中)for(h=0;h8;h+)根據(jù)可行路徑條數(shù)小至I大按下表排序放入數(shù)組d8中(min=9;for(k=0;kak)=63)/如果走完整個(gè)棋盤返回1return(1);find=O;II表示沒(méi)有找到下一個(gè)位置for(h=director+l;h=0&i=0&8(jv8)如果找至！下一位置(find=l;/表示找到下一個(gè)位置break;)if(find=l)/如果找到下一個(gè)位置進(jìn)棧(st

11、acktop.director=director;/存儲(chǔ)棧結(jié)點(diǎn)的方向top+;棧指針前移進(jìn)棧stacktop.i=i;stacktop.j=j;stacktop.director=-l;/重新初始化下一棧結(jié)點(diǎn)的嘗試方向boardij=top+l;標(biāo)記棋盤)else/否則退棧boardstacktop.istacktopj=0;/清除棋盤的標(biāo)記top-；棧指針前移退棧)return(0);)/(6)輸出路徑函數(shù)模塊voidDisplayO(intij;for(i=0;iN;i+)for(j=0;jN;j+)printf(t%d，boardij);輸出馬兒在棋盤上走過(guò)的路徑printf(nn);)printf(n);)/(5)主程序模塊intmain()intij;intx,y;for(i=0;ivN;i+)初始化棋盤for(j=0;jvN;j+)b