棧和隊列試驗報告課案

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

2、的全部64個方格。編制非遞歸程序，求出馬的行走路線，并按求出的行走路線，將數(shù)字1,2,，64依次填入一個8*8的方陣，輸出之。測試數(shù)據(jù)：可自行制定一個馬的初始位置(i,j),0=IJv=7o第1步：實現(xiàn)提示一般來說,當馬位于位置(ij)時，可以走到下列8個位置之一：(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個可能位置可以用一位數(shù)組HTrylO刀和HTry20刀來表示：01234567-2-11212212

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

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

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

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

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

8、ctor;/存儲方向stackMAXSIZE;/定義一個棧數(shù)組inttop=-l;棧指針(3)、函數(shù)聲明voidInitLocation(intxijntyi);/馬兒在棋盤上的起始位置坐標intTryPath(intijntj);/馬兒每個方向進行嘗試，直到試完整個棋盤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(無解)；(

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

10、棧不空時循環(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)/如果走完整個棋盤返回1return(1);find=O;II表示沒有找到下一個位置for(h=director+l;h=0&i=0&8(jv8)如果找至！下一位置(find=l;/表示找到下一個位置break;)if(find=l)/如果找到下一個位置進棧(st

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