java數(shù)據(jù)結(jié)構(gòu)第9章-綜合應(yīng)用設(shè)計

《數(shù)據(jù)結(jié)構(gòu)〔Java版〕》葉核亞《數(shù)據(jù)結(jié)構(gòu)〔Java版〕》第1章緒論 第2章線性表第3章排序第4章棧與隊列第5章數(shù)組和廣義表第6章樹和二叉樹第7章查找第8章圖第9章綜合應(yīng)用設(shè)計第9章綜合應(yīng)用設(shè)計9.1用“預(yù)見算法”解騎士游歷問題9.2綜合應(yīng)用實習(xí)9.1用“預(yù)見算法”解騎士游歷問題題意在國際象棋的棋盤〔8行×8列〕上放置一個馬，按照“馬走日字”的規(guī)那么，馬要遍歷棋盤，即到達棋盤上的每一格，并且每格只到達一次。假設(shè)給定起始位置〔x0,y0〕，編程探索出一條路徑，沿著這條路徑馬能遍歷棋盤上的所有單元格，這就是“騎士游歷”問題。圖9.1馬下一步可走的8個方向2．棋盤的存儲結(jié)構(gòu)設(shè)二維數(shù)組mat表示棋盤，每個元素表示棋盤的一格，其值定義為：圖9.2從〔1,1〕開始的一次成功的遍歷3．常規(guī)的“回溯算法”〔1〕設(shè)計思想〔2〕輔助結(jié)構(gòu)——?！?〕性能評價圖9.3“回溯算法”流程圖4．“預(yù)見算法”〔1〕設(shè)計思想如果在每步選擇方向時，不是任意選擇一個方向，而是經(jīng)過一定的測試和計算，“預(yù)見”每條路的“寬窄”，再選擇一條最“窄”的路先走，成功的可能性較大?！?〕實現(xiàn)手段表9.1〔5,4〕位置的可通路數(shù)情況方向下一位置可通路數(shù)1(3,5)72(4,6)73(6,6)74(7,5)55(7,3)56(6,2)57(4,2)58(3,3)7算法描述圖9.4play()方法實現(xiàn)游歷的算法流程例9.1用“預(yù)見算法”解騎士游歷問題5．進一步研究方向程序運行時，隨意設(shè)置棋盤的大小，最小為5×5。設(shè)置棧，在無路可通時，選擇另一條路徑。設(shè)置隊列，對于同一個初始位置，求得多條路徑。用圖形描繪馬在棋盤上的移動情況。使用?；蜿犃袝r，跟蹤程序運行，觀察并描繪?；蜿犃械膭討B(tài)變化情況。9.2綜合應(yīng)用實習(xí)1．求解騎士游歷、迷宮等問題的多種算法2．計算表達式值的多種算法3．利用線程比較多種查找、排序算法的運行時間4．管理信息系統(tǒng)中的算法設(shè)計5．經(jīng)典問題求解6．?dāng)?shù)據(jù)結(jié)構(gòu)的算法設(shè)計與動態(tài)描述1．求解騎士游歷、迷宮等問題的多種算法〔1〕實習(xí)目的掌握棧、隊列的根本概念，熟練運用。掌握遞歸算法的設(shè)計思想?！?〕題意騎士游歷、迷宮的題意參見第4章實習(xí)4。漢諾塔問題和八皇后問題圖9.5漢諾塔問題的解答圖9.6八皇后問題2．計算表達式值的多種算法〔1〕實習(xí)目的掌握棧、遞歸算法、二叉樹的設(shè)計技術(shù)。〔2〕題意計算表達式的值?！?〕實習(xí)要求同時使用兩個棧求值。遞歸算法。采用二叉樹結(jié)構(gòu)。圖9.7表達式二叉樹3．利用線程比較多種查找、排序算法的運行時間〔1〕實習(xí)目的利用線程技術(shù)，比較不同查找、排序算法的性能?！?〕題意將順序、折半查找算法設(shè)計成線程，啟動二個不同線程同時運行，并計算不同查找算法的運行時間。將冒泡、快速等多個排序算法設(shè)計成線程，啟動二個以上不同線程同時運行，并計算不同排序算法的運行時間。4．管理信息系統(tǒng)中的算法設(shè)計〔1〕實習(xí)目的以Java中的流技術(shù)，練習(xí)管理信息系統(tǒng)中常用的算法設(shè)計?！?〕題意以學(xué)生管理信息系統(tǒng)為例：設(shè)計Student類的增加、刪除、修改、查詢、統(tǒng)計、自動編號等功能。設(shè)計系統(tǒng)管理員、班主任、任課教師、學(xué)生、普通用戶等多級用戶管理權(quán)限。設(shè)計系別、專業(yè)、班級等字典庫，并進行維護。5．經(jīng)典問題求解〔1〕實習(xí)目的綜合運用所學(xué)知識，設(shè)計新算法并實現(xiàn)?！?〕題意對于以下的經(jīng)典問題，設(shè)計相應(yīng)的算法：電梯調(diào)度算法。自動排課算法。號碼簿的設(shè)計與查找算法。數(shù)據(jù)字典的設(shè)計與查找算法。城市道路交通網(wǎng)絡(luò)的構(gòu)架設(shè)計。6．?dāng)?shù)據(jù)結(jié)構(gòu)的算法設(shè)計與動態(tài)描述〔1〕實習(xí)目的對常用數(shù)據(jù)結(jié)構(gòu)和經(jīng)典算法進行動態(tài)描述。將數(shù)據(jù)結(jié)構(gòu)用圖形方式顯示在屏幕上，并對插入、刪除等操作的每一步狀態(tài)〔當(dāng)前結(jié)點等〕進行動態(tài)演示?！?〕題意線性表：單向鏈表、雙向鏈表的插入與刪除操作，約瑟夫環(huán)問題，多項式相加。排序：單向鏈表的簡單項選擇擇排序〔不新建鏈表〕、歸并排序，順序表的希爾排序、快速排序、堆排序、歸并排序的排序過程動態(tài)演示，九宮排序的排序過程動態(tài)演示，各種排序算法的比較演示。棧與隊列：計算表達式值時的棧、解素數(shù)環(huán)問題時的隊列的動態(tài)演示。稀疏矩陣與廣義表：稀疏矩陣三元組的順序存儲結(jié)構(gòu)、鏈?zhǔn)酱鎯Y(jié)構(gòu)。廣義表的存儲結(jié)構(gòu)。樹和二叉樹：二叉樹的建立與3種遍歷算法〔先根、中根、后根〕，表達式二叉樹的建立與計算，廣義表描述的二叉樹的建立與遍歷，線索二叉樹的建立與遍歷。二叉樹中求兩個結(jié)點最近的共同祖先。樹與二叉樹的轉(zhuǎn)換。查找：順序表的鏈表的順序查找算法，有序順序表的折半查