數(shù)據(jù)結(jié)構(gòu)java實(shí)驗(yàn)三

1、數(shù)據(jù)結(jié)構(gòu)（JAVA）綜合性、設(shè)計(jì)性實(shí)驗(yàn)成績單開設(shè)時(shí)間： 班級學(xué)號姓名實(shí)驗(yàn)題目實(shí)驗(yàn)三 棧和隊(duì)列及遞歸算法成績教師簽名數(shù)據(jù)結(jié)構(gòu)（JAVA）實(shí) 驗(yàn) 報(bào) 告實(shí)驗(yàn)題目： 棧和隊(duì)列及遞歸算法 指導(dǎo)教師： 實(shí)驗(yàn)組長（姓名+學(xué)號）： 組員（姓名+學(xué)號）： 實(shí)驗(yàn)時(shí)間： 組長簽名： 一、實(shí)驗(yàn)報(bào)告撰寫提綱1、實(shí)驗(yàn)?zāi)康? 理解棧和隊(duì)列抽象數(shù)據(jù)類型，掌握棧和隊(duì)列的存儲結(jié)構(gòu)和操作實(shí)現(xiàn)，理解棧和隊(duì)列在實(shí)際應(yīng)用問題的作用。2、實(shí)驗(yàn)內(nèi)容（1） 使用一個(gè)棧，將十進(jìn)制轉(zhuǎn)換成二進(jìn)制。（2） 分別用循環(huán)單鏈表、循環(huán)雙鏈表結(jié)構(gòu)設(shè)計(jì)隊(duì)列，并討論他們之間的差別。（3） 使用3個(gè)隊(duì)列分別保留手機(jī)最近10個(gè)“未接來電”、“已接來電”、“以撥電話

2、”。（4） 走迷宮。一個(gè)迷宮如圖所示，他有一個(gè)入口和一個(gè)出口，其中白色單元表示通路，黑色單元表示不通路。試尋找一條從入口到出口的路徑，每一部只能從一個(gè)白色單元走到相鄰的白色單元，直至出口。分別用站和隊(duì)列求解問題。入口出口（5）騎士游歷騎士游歷問題是指，在國際象棋的棋盤（8行*8列）上，一個(gè)馬要遍歷棋盤，即走到棋盤上的每一格，并且每隔只到達(dá)一次。設(shè)碼在棋盤的某一位置（x,y）上，按照“走馬日”的規(guī)則，下一步有8個(gè)方向走，如圖所示。若給定起始位置（x0,y0）,使用站和隊(duì)列探索出一條馬遍歷棋盤的路勁。 12345 6 7 8 8172馬63543、實(shí)驗(yàn)步驟與結(jié)果(1)審題：使用一個(gè)棧，將十進(jìn)制轉(zhuǎn)換

3、成二進(jìn)制。編程：本代碼使用了一個(gè)順序棧SeqStack，編寫一個(gè)循環(huán)讓十進(jìn)制數(shù)除2的余數(shù)入站，然后讓全部余數(shù)出棧，輸出二進(jìn)制數(shù)。驗(yàn)證結(jié)果：圖 1（2）審題：分別用循環(huán)單鏈表、循環(huán)雙鏈表結(jié)構(gòu)設(shè)計(jì)隊(duì)列，并討論他們之間的差別。編程：首先先編寫一個(gè)隊(duì)列抽象數(shù)據(jù)類型QQueue，然后編寫循環(huán)單鏈表SlinkedQueue和 雙鏈表DlinkedQueue逐一實(shí)現(xiàn)Qqueue中的三個(gè)方法，即判斷是否隊(duì)列為空、入隊(duì)和出隊(duì)。循環(huán)雙鏈表所占的時(shí)間復(fù)雜度和空間復(fù)雜度比單鏈表多。驗(yàn)證結(jié)果：兩個(gè)均可被調(diào)用。（3）審題：使用3個(gè)隊(duì)列分別保留手機(jī)最近10個(gè)“未接來電”、“已接來電”、“以撥電話”。編程：110代表未接來電

4、，1120代表已接來電，2130代表以撥電話，編寫三個(gè)順序棧stack1，stack2，stack3，運(yùn)用條件語句存儲10個(gè)號碼，然后輸出。驗(yàn)證結(jié)果：圖 2（4）審題：一個(gè)迷宮，他有一個(gè)入口和一個(gè)出口，其中白色單元表示通路，黑色單元表示不通路。試尋找一條從入口到出口的路徑，每一部只能從一個(gè)白色單元走到相鄰的白色單元，直至出口。分別用站和隊(duì)列求解問題。編程：暫時(shí)做不出驗(yàn)證結(jié)果：（5）審題：騎士游歷問題是指，在國際象棋的棋盤（8行*8列）上，一個(gè)馬要遍歷棋盤，即走到棋盤上的每一格，并且每隔只到達(dá)一次。設(shè)碼在棋盤的某一位置（x,y）上，按照“走馬日”的規(guī)則，下一步有8個(gè)方向走，如圖所示。若給定起始位

5、置（x0,y0）,使用站和隊(duì)列探索出一條馬遍歷棋盤的路勁。編程：利用預(yù)見算法解這類問題，以二維數(shù)組chessboard表示棋盤并保存問題的一個(gè)解；將棋盤上一格的位置（x，y）聲明為一個(gè)內(nèi)部類Position；start（x，y）方法從（x，y）格開始游歷，初始位置p=new Position（x，y）；判斷是否滿n*n，不滿的話選擇一個(gè)方向direction=select（p）；判斷是否有方向可選，有的話步數(shù)加1，向所選方向前進(jìn)一步p=goaStep（p，direction），遞歸執(zhí)行上述算法；如果無方向可選，則無路可通；當(dāng)慢n*n步時(shí)，成功輸出。驗(yàn)證結(jié)果：圖 34、源碼見附錄：附錄中的源代碼在同一個(gè)包中。5.結(jié)論與討論通過本次試驗(yàn)，我們剛開始時(shí)遇到了很多問題，比如說做騎士游歷這道題，剛看到他們的時(shí)候根本就是無法下手，但經(jīng)過我們小組的討論，我們最后解決 了這道題。但對于走迷宮這道題，有本小組知識