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

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

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

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

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

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

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

8、ctor;/存儲方向stackMAXSIZE;/定義一個棧數組inttop=-l;棧指針(3)、函數聲明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)、探尋路徑函數模塊int TryPath(int ijnt j)/(4)、起始坐標函數模塊voidInitLocation(intxijntyi)(定義棋盤的橫縱坐標變量棧指針指向第一個棧首將起始位置的橫坐標進棧將起始位置的縱坐標進棧將起始位置的嘗試方向賦初值標記棋盤將起始位置的橫坐標賦給棋盤的橫坐標輸出馬兒的行走路徑intfind,director,number,min;定義幾個臨時變量intiljl,h,k,s;/定義幾個臨時變量if(TryPath(xzy)調用馬兒探尋函數，如果馬兒探尋整個棋盤返回1否則返inta8zbl8Lb28Ld8;/定義幾個臨時數組while(top-l)/

10、棧不空時循環(for(h=0;h=0&iv8&j=0&的8)如果找至!下一位置for(k=0;k=0&il=084&jl8)/$D果找到下一位置number+;/記錄條數ah=number;/將條數存入數組a8中)for(h=0;h8;h+)根據可行路徑條數小至I大按下表排序放入數組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;/存儲棧結點的方向top+;棧指針前移進棧stacktop.i=i;stacktop.j=j;stacktop.director=-l;/重新初始化下一棧結點的嘗試方向boardij=top+l;標記棋盤)else/否則退棧boardstacktop.istacktopj=0;/清除棋盤的標記top-；棧指針前移退棧)return(0);)/(6)輸出路徑函數模塊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