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

1、數(shù)據(jù)結(jié)構(gòu)（C+版）第1章 緒論第2章 線性表第3章 排序第4章 串第5章 棧與隊(duì)列第6章 數(shù)組和廣義表第7章 樹(shù)和二叉樹(shù)第8章 查找第9章 圖第10章 綜合應(yīng)用設(shè)計(jì)第10章 綜合應(yīng)用設(shè)計(jì)10.1 用“預(yù)見(jiàn)算法”解騎士游歷問(wèn)題10.2 綜合應(yīng)用實(shí)習(xí)數(shù)據(jù)結(jié)構(gòu)（C+版）葉核亞10.1 用“預(yù)見(jiàn)算法”解騎士游歷問(wèn)題題意在國(guó)際象棋的棋盤(pán)（8行8列）上放置一個(gè)馬，按照“馬走日字”的規(guī)則，馬要遍歷棋盤(pán)，即到達(dá)棋盤(pán)上的每一格，并且每格只到達(dá)一次。若給定起始位置（x0, y0），編程探索出一條路徑，沿著這條路徑馬能遍歷棋盤(pán)上的所有單元格，這就是“騎士游歷”問(wèn)題。圖10-1 馬下一步可走的8個(gè)方向數(shù)據(jù)結(jié)構(gòu)（C+版

2、）葉核亞2棋盤(pán)的存儲(chǔ)結(jié)構(gòu)設(shè)二維數(shù)組mat表示棋盤(pán)，每個(gè)元素表示棋盤(pán)的一格，其值定義為：圖10-2 從（1, 1）開(kāi)始的一次成功的遍歷數(shù)據(jù)結(jié)構(gòu)（C+版）葉核亞3常規(guī)的“回溯算法”（1）設(shè)計(jì)思想（2）輔助結(jié)構(gòu)棧（3）性能評(píng)價(jià)圖10-3 “回溯算法”流程圖數(shù)據(jù)結(jié)構(gòu)（C+版）葉核亞4“預(yù)見(jiàn)算法”（1）設(shè)計(jì)思想如果在每步選擇方向時(shí)，不是任意選擇一個(gè)方向，而是經(jīng)過(guò)一定的測(cè)試和計(jì)算，“預(yù)見(jiàn)”每條路的“寬窄”，再選擇一條最“窄”的路先走，成功的可能性較大。數(shù)據(jù)結(jié)構(gòu)（C+版）葉核亞（2）實(shí)現(xiàn)手段表10-1 （5, 4）位置的可通路數(shù)情況方向下一位置可通路數(shù)1(3,5)72(4,6)73(6,6)74(7,5)5

3、5(7,3)56(6,2)57(4,2)58(3,3)7數(shù)據(jù)結(jié)構(gòu)（C+版）葉核亞例10-1 用“預(yù)見(jiàn)算法”解騎士游歷問(wèn)題 數(shù)據(jù)結(jié)構(gòu)（C+版）葉核亞算法描述圖10-4 play()方法實(shí)現(xiàn)游歷的算法流程數(shù)據(jù)結(jié)構(gòu)（C+版）葉核亞5進(jìn)一步研究方向程序運(yùn)行時(shí)，隨意設(shè)置棋盤(pán)的大小，最小為55。設(shè)置棧，在無(wú)路可通時(shí)，選擇另一條路徑。設(shè)置隊(duì)列，對(duì)于同一個(gè)初始位置，求得多條路徑。用圖形描繪馬在棋盤(pán)上的移動(dòng)情況。使用?；蜿?duì)列時(shí)，跟蹤程序運(yùn)行，觀察并描繪棧或隊(duì)列的動(dòng)態(tài)變化情況。數(shù)據(jù)結(jié)構(gòu)（C+版）葉核亞10.2 綜合應(yīng)用實(shí)習(xí)1求解騎士游歷、迷宮等問(wèn)題的多種算法2計(jì)算表達(dá)式值的多種算法3利用線程比較多種查找、排序算法

4、的運(yùn)行時(shí)間4管理信息系統(tǒng)中的算法設(shè)計(jì)5經(jīng)典問(wèn)題求解6數(shù)據(jù)結(jié)構(gòu)的算法設(shè)計(jì)與動(dòng)態(tài)描述數(shù)據(jù)結(jié)構(gòu)（C+版）葉核亞1求解騎士游歷、迷宮等問(wèn)題的多種算法（1）實(shí)習(xí)目的掌握棧、隊(duì)列的基本概念，熟練運(yùn)用。掌握遞歸算法的設(shè)計(jì)思想。（2）題意騎士游歷、迷宮的題意參見(jiàn)第5章實(shí)習(xí)5。數(shù)據(jù)結(jié)構(gòu)（C+版）葉核亞漢諾塔問(wèn)題和八皇后問(wèn)題圖10-5 漢諾塔問(wèn)題的解答圖10-6 八皇后問(wèn)題數(shù)據(jù)結(jié)構(gòu)（C+版）葉核亞2計(jì)算表達(dá)式值的多種算法（1）實(shí)習(xí)目的掌握棧、遞歸算法、二叉樹(shù)的設(shè)計(jì)技術(shù)。（2）題意計(jì)算表達(dá)式的值。（3）實(shí)習(xí)要求同時(shí)使用兩個(gè)棧求值。遞歸算法。采用二叉樹(shù)結(jié)構(gòu)。圖10-7 表達(dá)式二叉樹(shù)數(shù)據(jù)結(jié)構(gòu)（C+版）葉核亞3利用線程比

5、較多種查找、排序算法的運(yùn)行時(shí)間（1）實(shí)習(xí)目的利用線程技術(shù)，比較不同查找、排序算法的性能。（2）題意將順序、折半查找算法設(shè)計(jì)成線程，啟動(dòng)二個(gè)不同線程同時(shí)運(yùn)行，并計(jì)算不同查找算法的運(yùn)行時(shí)間。將冒泡、快速等多個(gè)排序算法設(shè)計(jì)成線程，啟動(dòng)二個(gè)以上不同線程同時(shí)運(yùn)行，并計(jì)算不同排序算法的運(yùn)行時(shí)間。數(shù)據(jù)結(jié)構(gòu)（C+版）葉核亞4管理信息系統(tǒng)中的算法設(shè)計(jì)（1）實(shí)習(xí)目的以Java中的流技術(shù)，練習(xí)管理信息系統(tǒng)中常用的算法設(shè)計(jì)。（2）題意以學(xué)生管理信息系統(tǒng)為例：設(shè)計(jì)Student類(lèi)的增加、刪除、修改、查詢(xún)、統(tǒng)計(jì)、自動(dòng)編號(hào)等功能。設(shè)計(jì)系統(tǒng)管理員、班主任、任課教師、學(xué)生、普通用戶(hù)等多級(jí)用戶(hù)管理權(quán)限。設(shè)計(jì)系別、專(zhuān)業(yè)、班級(jí)等字典庫(kù)，并進(jìn)行維護(hù)。數(shù)據(jù)結(jié)構(gòu)（C+版）葉核亞5經(jīng)典問(wèn)題求解（1）實(shí)習(xí)目的綜合運(yùn)用所學(xué)知識(shí)，設(shè)計(jì)新算法并實(shí)現(xiàn)。（2）題意對(duì)于以下的經(jīng)典問(wèn)題，設(shè)計(jì)相應(yīng)的算法：電梯調(diào)度算法。自動(dòng)排課算法。電話號(hào)碼簿的設(shè)計(jì)與查找算法。數(shù)據(jù)字典的設(shè)計(jì)與查找算法。城市道路交通網(wǎng)絡(luò)的構(gòu)架設(shè)計(jì)。數(shù)據(jù)結(jié)構(gòu)（C+版）葉核亞6數(shù)據(jù)結(jié)構(gòu)的算法設(shè)計(jì)與動(dòng)態(tài)描述（1）實(shí)習(xí)目的對(duì)常用數(shù)據(jù)結(jié)構(gòu)和經(jīng)典算法進(jìn)行動(dòng)態(tài)描述。將數(shù)據(jù)結(jié)構(gòu)用圖形方式顯示在屏幕上，并對(duì)插入、刪除等操作的每一步狀態(tài)（當(dāng)前結(jié)點(diǎn)等）進(jìn)行動(dòng)態(tài)演示。（2）題意線性表：?jiǎn)蜗蜴湵?、雙向鏈表的插入與刪除操作，約瑟夫環(huán)問(wèn)題，多項(xiàng)式相加。排序：?jiǎn)?/p>