【文章內(nèi)容簡(jiǎn)介】 器分配策略和算法、無(wú)用單元收集時(shí)的標(biāo)志算法第九章查找（一）目的要求了解靜態(tài)查找表(順序表，有序表，索引順序表)；動(dòng)態(tài)查找表(二叉排序樹(shù)，平衡二叉樹(shù)，B樹(shù)和B+樹(shù))的建立和查找；掌握哈希表的建立，查找及分析；（二）教學(xué)內(nèi)容 本章知識(shí)點(diǎn)：、折半查找和索引查找的方法、應(yīng)用(掌握)；(掌握)；(掌握)；，B+樹(shù)和鍵樹(shù)的特點(diǎn)以及它們的建立過(guò)程（理解）；(掌握)；；(掌握)。（三）重點(diǎn)與難點(diǎn)重點(diǎn)：二叉排序樹(shù)的構(gòu)造方法、二叉平衡樹(shù)的建立方法；哈希表的構(gòu)造、應(yīng)用；難點(diǎn)：二叉排序樹(shù)的構(gòu)造及應(yīng)用；哈希表的構(gòu)造方法；查找的平均長(zhǎng)度。第十章內(nèi)部排序（一）目的要求掌握插入排序、交換排序(起泡排序，快速排序)、選擇排序(簡(jiǎn)單選擇，樹(shù)形選擇，堆)、歸并排序、基數(shù)排序等算法。（二）教學(xué)內(nèi)容 本章知識(shí)點(diǎn)：(掌握)； (掌握)；(掌握)。（三）重點(diǎn)與難點(diǎn)重點(diǎn)：各種排序方法的特點(diǎn)及其應(yīng)用；實(shí)現(xiàn)排序的各種算法。難點(diǎn)：各種排序算法的時(shí)間復(fù)雜度分析。十一章外部排序（一）目的要求理解外部排序的基本方法；掌握敗者樹(shù)和多路平衡歸并的實(shí)現(xiàn)；置換選擇排序；最佳歸并樹(shù)。（二）教學(xué)內(nèi)容 本章知識(shí)點(diǎn)：(理解)；(掌握)；(掌握)；(掌握)；(掌握)；（熟悉）；，外存讀/寫(xiě)次數(shù)的計(jì)算方法(掌握)。（三）重點(diǎn)與難點(diǎn)重點(diǎn)：外部排序過(guò)程和實(shí)現(xiàn)方法；多路并歸算法及其實(shí)現(xiàn)； 難點(diǎn)：最佳并歸樹(shù)的構(gòu)造方法及其應(yīng)用。實(shí)踐教學(xué)部分：上機(jī)實(shí)驗(yàn)分4個(gè)專題，每個(gè)專題可提供2~4個(gè)難度不等的題目供選。實(shí)驗(yàn)一停車場(chǎng)管理系統(tǒng)（一）實(shí)驗(yàn)內(nèi)容 以棧模擬車場(chǎng)，以隊(duì)列模擬車場(chǎng)外的便道，按照從終端讀入的輸入數(shù)據(jù)序列進(jìn)行模擬管理。棧以順序結(jié)構(gòu)實(shí)現(xiàn)，隊(duì)列以鏈表結(jié)構(gòu)實(shí)現(xiàn)。（二）實(shí)驗(yàn)過(guò)程 編程實(shí)現(xiàn)實(shí)驗(yàn)內(nèi)容。（三）實(shí)驗(yàn)教學(xué)基本要求通過(guò)實(shí)例，使學(xué)生掌握棧和隊(duì)列兩種特殊的線性結(jié)構(gòu)，掌握棧和隊(duì)列的特點(diǎn)。實(shí)驗(yàn)后學(xué)生提交實(shí)驗(yàn)報(bào)告。（四）實(shí)驗(yàn)設(shè)備和材料 計(jì)算機(jī)。（五）實(shí)驗(yàn)學(xué)時(shí) 4學(xué)時(shí)實(shí)驗(yàn)二教學(xué)計(jì)劃編制問(wèn)題（一）實(shí)驗(yàn)內(nèi)容假設(shè)任何專業(yè)都有固定的學(xué)習(xí)年限，每學(xué)年含兩學(xué)期，每學(xué)期的時(shí)間長(zhǎng)度和學(xué)分上限值均相等。每個(gè)專業(yè)開(kāi)設(shè)的課程都是確定的，而且課程在開(kāi)設(shè)時(shí)間的安排必須滿足先修關(guān)系。每門(mén)課程有哪些先修課程是確定的，可以有任意多門(mén)，也可以沒(méi)有。每門(mén)課恰好占一個(gè)學(xué)期。編制一個(gè)教學(xué)計(jì)劃程序。（二）實(shí)驗(yàn)過(guò)程編程實(shí)現(xiàn)實(shí)驗(yàn)內(nèi)容。（三）實(shí)驗(yàn)教學(xué)基本要求通過(guò)實(shí)例，使學(xué)生熟悉圖的各種存儲(chǔ)結(jié)構(gòu)的特性，掌握如何應(yīng)用圖結(jié)構(gòu)解決具體問(wèn)題。實(shí)驗(yàn)后學(xué)生提交實(shí)驗(yàn)報(bào)告。（四）實(shí)驗(yàn)設(shè)備和材料 計(jì)算機(jī)。（五）實(shí)驗(yàn)學(xué)時(shí) 2學(xué)時(shí)實(shí)驗(yàn)三最小生成樹(shù)問(wèn)題（一）實(shí)驗(yàn)內(nèi)容利用克魯斯卡爾算法求最小生成樹(shù)。以文本形式輸出樹(shù)中各條邊以及他們的權(quán)值。（二）實(shí)驗(yàn)過(guò)程 編程實(shí)現(xiàn)實(shí)驗(yàn)內(nèi)容（三）實(shí)驗(yàn)教學(xué)基本要求通過(guò)實(shí)例，使學(xué)生熟悉圖的各種存儲(chǔ)結(jié)構(gòu)的特性，掌握如何應(yīng)用圖結(jié)構(gòu)解決具體問(wèn)題。實(shí)驗(yàn)后學(xué)生提交實(shí)驗(yàn)報(bào)告。（四）實(shí)驗(yàn)設(shè)備和材料 計(jì)算機(jī)。（五）實(shí)驗(yàn)學(xué)時(shí) 2學(xué)時(shí)實(shí)驗(yàn)四哈希表設(shè)計(jì)（一）實(shí)驗(yàn)內(nèi)容假設(shè)人名為中國(guó)人的漢語(yǔ)拼音形式。待填入哈希表的人名共有30個(gè)，取平均查找長(zhǎng)度的上限為2。哈希函數(shù)用除留余數(shù)法構(gòu)造，用偽隨機(jī)探測(cè)再散列法處理沖突。（二）實(shí)驗(yàn)過(guò)程 編程實(shí)現(xiàn)實(shí)驗(yàn)內(nèi)容（三）實(shí)驗(yàn)教學(xué)基本要求 掌握索引技術(shù)的使用。（四）實(shí)驗(yàn)設(shè)備和材料 計(jì)算機(jī)（五）實(shí)驗(yàn)學(xué)時(shí) 4學(xué)時(shí)五、課程教學(xué)的基本要求和主要環(huán)節(jié)本課程可采用課堂講授、課堂討論、習(xí)題課等進(jìn)行課堂教學(xué)。條件允許可采用CAI、電子教案、幻燈片、參觀等進(jìn)行輔助教學(xué)。每章布置3~6道習(xí)題以鞏固教學(xué)。在課程后半程，安排3~4個(gè)上機(jī)實(shí)驗(yàn)，讓學(xué)生應(yīng)用數(shù)據(jù)結(jié)構(gòu)的理論、方法，分組設(shè)計(jì)幾個(gè)較大的軟件，使理論與實(shí)際相結(jié)合?？荚嚥捎瞄]卷方式?？偝煽?jī)由平時(shí)成績(jī)和考試成績(jī)組成。平時(shí)成績(jī)占30%，考試成績(jī)占70%。六、本課程與其它課程的聯(lián)系與分工先修課包括：集合論，圖論，高級(jí)語(yǔ)言（結(jié)構(gòu)或記錄，指針）；后續(xù)課包括：數(shù)據(jù)庫(kù)，編譯原理，操作系統(tǒng)等。七、建議教材與參考教材《數(shù)據(jù)結(jié)構(gòu)》（C語(yǔ)言版）嚴(yán)蔚敏等清華大學(xué)出版社1997 《數(shù)據(jù)結(jié)構(gòu)題集》嚴(yán)蔚敏等清華大學(xué)出版社1999《數(shù)據(jù)結(jié)構(gòu)習(xí)題與解析》李春葆清華大學(xué)出版社2004八、負(fù)責(zé)人撰稿人：劉景匯、李玉香審稿人：系（院）領(lǐng)導(dǎo)：第四篇：數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)教學(xué)大綱《數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)》教學(xué)大綱Data Structure Course Design一、課程的性質(zhì)、教學(xué)目的和要求《數(shù)據(jù)結(jié)構(gòu)》是計(jì)算機(jī)軟件的一門(mén)基礎(chǔ)課程，計(jì)算機(jī)科學(xué)各領(lǐng)域及有關(guān)的應(yīng)用軟件都要用到各種類型的數(shù)據(jù)結(jié)構(gòu)。學(xué)好數(shù)據(jù)結(jié)構(gòu)對(duì)掌握實(shí)際編程能力是很有幫助的。為了學(xué)好《數(shù)據(jù)結(jié)構(gòu)》，必須編寫(xiě)一些在特定數(shù)據(jù)結(jié)構(gòu)上的算法，通過(guò)上機(jī)調(diào)試，才能更好地掌握各種數(shù)據(jù)結(jié)構(gòu)及其特點(diǎn)，同時(shí)提高解決計(jì)算機(jī)應(yīng)用實(shí)際問(wèn)題的能力。二、設(shè)計(jì)要點(diǎn)1．設(shè)計(jì)和調(diào)試過(guò)程要規(guī)范化。① 需求分析將題目中要求的功能進(jìn)行敘述分析，并且設(shè)計(jì)解決此問(wèn)題的數(shù)據(jù)存儲(chǔ)結(jié)構(gòu)，（有些題目已經(jīng)指定了數(shù)據(jù)存儲(chǔ)的，按照指定的設(shè)計(jì)），設(shè)計(jì)或敘述解決此問(wèn)題的算法，描述算法建議使用流程圖，進(jìn)行算法分析指明關(guān)鍵語(yǔ)句的時(shí)間復(fù)雜度。給出實(shí)現(xiàn)功能的一組或多組測(cè)試數(shù)據(jù)，程序調(diào)試后，將按照此測(cè)試數(shù)據(jù)進(jìn)行測(cè)試的結(jié)果列出來(lái)。對(duì)有些題目提出算法改進(jìn)方案，比較不同算法的優(yōu)缺點(diǎn)。如果程序不能正常運(yùn)行，寫(xiě)出實(shí)現(xiàn)此算法中遇到的問(wèn)題，和改進(jìn)方法。②源程序（可以是一組源程序，即詳細(xì)設(shè)計(jì)部分）源程序要按照寫(xiě)程序的規(guī)則來(lái)編寫(xiě)。要結(jié)構(gòu)清晰，重點(diǎn)函數(shù)的重點(diǎn)變量，重點(diǎn)功能部分要加上清晰的程序注釋。程序能夠運(yùn)行，要有基本的容錯(cuò)功能。盡量避免出現(xiàn)操作錯(cuò)誤時(shí)出現(xiàn)死循環(huán)。2．課程設(shè)計(jì)實(shí)習(xí)報(bào)告的書(shū)寫(xiě)格式① 設(shè)計(jì)題目（任選其一）②運(yùn)行環(huán)境（軟、硬件環(huán)境）③算法設(shè)計(jì)的思想 ④算法的流程圖 ⑤算法設(shè)計(jì)分析 ⑥源代碼 ⑦運(yùn)行結(jié)果分析 ⑧收獲及體會(huì) 3．實(shí)施方式可設(shè)23人一題，安排在《數(shù)據(jù)結(jié)構(gòu)》課程開(kāi)課學(xué)期布置題目，然后在期末前兩周完成。三．設(shè)計(jì)要求學(xué)生要發(fā)揮自主學(xué)習(xí)的能力，充分利用時(shí)間，安排好課設(shè)的時(shí)間計(jì)劃，并在課設(shè)過(guò)程中不斷檢測(cè)自己的計(jì)劃完成情況，及時(shí)的向教師匯報(bào)。課程設(shè)計(jì)按照教學(xué)要求需要1周時(shí)間完成，1周中每天至少要上68小時(shí)的機(jī)來(lái)調(diào)試C語(yǔ)言設(shè)計(jì)的程序，總共至少要上機(jī)調(diào)試程序30小時(shí)。為保證質(zhì)量，需要每個(gè)學(xué)生將每天的上機(jī)調(diào)試程序的時(shí)間記錄下來(lái)，作為評(píng)判成績(jī)的標(biāo)準(zhǔn)之一。四．設(shè)計(jì)題目校園導(dǎo)游程序[問(wèn)題描述]用無(wú)向網(wǎng)表示你所在學(xué)校的校園景點(diǎn)平面圖，圖中頂點(diǎn)表示主要景點(diǎn)，存放景點(diǎn)的編號(hào)、名稱、簡(jiǎn)介等信息，圖中的邊表示景點(diǎn)間的道路，存放路徑長(zhǎng)度等信息。要求能夠回答有關(guān)景點(diǎn)介紹、游覽路徑等問(wèn)題。[基本要求]（1）查詢各景點(diǎn)的相關(guān)信息；（2）查詢圖中任意兩個(gè)景點(diǎn)間的最短路徑。（3）查詢圖中任意兩個(gè)景點(diǎn)間的所有路徑。（4）增加、刪除、更新有關(guān)景點(diǎn)和道路的信息。[選作內(nèi)容]（1）求多個(gè)景點(diǎn)的最佳（最短）游覽路徑。（2）區(qū)分機(jī)動(dòng)車道和人行道。（3）實(shí)現(xiàn)導(dǎo)游圖的仿真界面。算術(shù)表達(dá)式求值[問(wèn)題描述]一個(gè)算術(shù)表達(dá)式是由操作數(shù)(operand)、運(yùn)算符(operator)和界限符(delimiter)組成的。假設(shè)操作數(shù)是正整數(shù)，運(yùn)算符只含加減乘除等四種運(yùn)算符，界限符有左右括號(hào)和表達(dá)式起始、結(jié)束符“”，如：（7+15）*（2328/4）。引入表達(dá)式起始、結(jié)束符是為了方便。編程利用“算符優(yōu)先法”求算術(shù)表達(dá)式的值。[基本要求]（1）從鍵盤(pán)讀入一個(gè)合法的算術(shù)表達(dá)式，輸出正確的結(jié)果。（2）顯示輸入序列和棧的變化過(guò)程。[選作內(nèi)容]擴(kuò)充運(yùn)算符集合。引入變量操作數(shù)。操作數(shù)類型擴(kuò)充到實(shí)數(shù)。文學(xué)研究助手[問(wèn)題描述]文學(xué)研究人員需要統(tǒng)計(jì)某篇英文小說(shuō)中某些形容詞的出現(xiàn)次數(shù)和位置。試寫(xiě)一個(gè)實(shí)現(xiàn)這一目標(biāo)的文字統(tǒng)計(jì)系統(tǒng)，稱為“文學(xué)研究助手”。[基本要求]英文小說(shuō)存于一個(gè)文本文件中。待統(tǒng)計(jì)的詞匯集合要一次輸入完畢，即統(tǒng)計(jì)工作必須在程序的一次運(yùn)行之后就全部完成。程序的輸出結(jié)果是每個(gè)詞的出現(xiàn)次數(shù)和出現(xiàn)位置所在行的行號(hào)，格式自行設(shè)計(jì)。[測(cè)試數(shù)據(jù)]以你的源程序模擬英文小說(shuō)，程序語(yǔ)言保留字集作為待統(tǒng)計(jì)的詞匯集。[實(shí)現(xiàn)提示]設(shè)小說(shuō)中的詞匯一律不跨行。這樣，每讀入一行，就統(tǒng)計(jì)每個(gè)詞在這行中的出現(xiàn)次數(shù)。出現(xiàn)位置所在行的行號(hào)可以用鏈表存儲(chǔ)。若某行中出現(xiàn)了不止一次，不必存多個(gè)相同的行號(hào)。如果讀者希望達(dá)到選作部分（1）和（2）所提出的要求，則首先應(yīng)把KMP算法改寫(xiě)成如下的等價(jià)形式，再將它推廣到多個(gè)模式的情形。[選作內(nèi)容]（1）模式匹配要基于KMP算法。（2）整個(gè)統(tǒng)計(jì)過(guò)程中只對(duì)小說(shuō)文字掃描一遍以提高效率。（3）假設(shè)小說(shuō)中的每個(gè)單詞或者從行首開(kāi)始，或者前置以一個(gè)空格符。利用單詞匹配特點(diǎn)另寫(xiě)一個(gè)高效的統(tǒng)計(jì)程序，與KMP算法統(tǒng)計(jì)程序進(jìn)行效率比較。（4）推廣到更一般的模式集匹配問(wèn)題，并設(shè)待查模式串可以跨行（提示：定義操作getachar）[問(wèn)題描述]可以輸入一個(gè)任意大小的迷宮數(shù)據(jù)，用非遞歸的方法求出一條走出迷宮的路徑，并將路徑輸出；[基本要求]含有兩個(gè)以上的迷宮圖，由用戶選擇哪一張迷宮圖； 實(shí)現(xiàn)深度優(yōu)先、廣度優(yōu)先兩種回溯法。在上交資料中請(qǐng)寫(xiě)明：存儲(chǔ)結(jié)構(gòu)、基本算法（可以使用程序流程圖）、源程序、算法的時(shí)間復(fù)雜度、另外可以提出算法的改進(jìn)方法；[實(shí)現(xiàn)提示]可以用一個(gè)二維數(shù)組存儲(chǔ)迷宮圖，值為1或者0分別表示通路和不通； 搜索路徑可以參考樹(shù)的深度優(yōu)先和廣度優(yōu)先算法。[問(wèn)題描述]假設(shè)表達(dá)式中允許有兩種括號(hào)：圓括號(hào)和方括號(hào)，其嵌套的順序隨意，即CC或[（[ ] [ ]）]等為正確格式，[（]）或（（（]均為不正確的格式。檢驗(yàn)括號(hào)是否匹配的方法可用“期待的緊迫程度”這個(gè)概念來(lái)描述。例如：考慮下列的括號(hào)序列：[([ ] [ ])]8當(dāng)計(jì)算機(jī)接受了第1個(gè)括號(hào)以后，他期待著與其匹配的第8個(gè)括號(hào)的出現(xiàn)，然而等來(lái)的卻是第2個(gè)括號(hào)，此時(shí)第1個(gè)括號(hào)“[”只能暫時(shí)靠邊，而迫切等待與第2個(gè)括號(hào)相匹配的 第7個(gè)括號(hào)“）”的出現(xiàn)，類似的，因只等來(lái)了第3個(gè)括號(hào)“[”，此時(shí)，其期待的緊迫程度較第2個(gè)括號(hào)更緊迫，則第2個(gè)括號(hào)只能靠邊，讓位于第3個(gè)括號(hào)，顯然第3個(gè)括號(hào)的期待緊迫程度高于第2個(gè)括號(hào)，而第2個(gè)括號(hào)的期待緊迫程度高于第1個(gè)括號(hào)；在接受了第4個(gè)括號(hào)之后，第3個(gè)括號(hào)的期待得到了滿足，消解之后，第2個(gè)括號(hào)的期待匹配就成了最急迫的任務(wù)了，??，依次類推?？梢?jiàn)這個(gè)處理過(guò)程正好和棧的特點(diǎn)相吻合。[基本要求]設(shè)置一個(gè)棧，每讀入一個(gè)括號(hào)，若是左括號(hào)，則作為一個(gè)新的更急迫的期待壓入棧中，若是右括號(hào)，則或者是和當(dāng)前棧頂?shù)睦ㄌ?hào)相匹配，或者是不合法的情況，輸出“此串括號(hào)匹配不合法”。在初始和結(jié)束時(shí)，棧應(yīng)該是空的。[測(cè)試數(shù)據(jù)]輸入 （[ ]（）），結(jié)果“匹配”輸入 [（）]，結(jié)果“此串括號(hào)匹配不合法”為起始和結(jié)束標(biāo)志。[問(wèn)題描述]設(shè)停車場(chǎng)內(nèi)只有一個(gè)可停放n輛汽車的狹長(zhǎng)通道，且只有一個(gè)大門(mén)可供汽車進(jìn)出。汽車在停車場(chǎng)內(nèi)按車輛到達(dá)時(shí)間的先后順序，依次由北向南排列（大門(mén)在最南端，最先到達(dá)的第一輛車停放在車場(chǎng)的最北端），若車場(chǎng)內(nèi)已停滿n輛汽車，則后來(lái)的汽車只能在門(mén)外的便道上等候，一旦有車開(kāi)走，則排在便道上的第一輛車即可開(kāi)入；當(dāng)停車場(chǎng)內(nèi)某輛車要離開(kāi)時(shí)，在它之后開(kāi)入的車輛必須先退出車場(chǎng)為它讓路，待該輛車開(kāi)出大門(mén)外，其它車輛再按原次序進(jìn)入車場(chǎng)，每輛停放在車場(chǎng)的車在它離開(kāi)停車場(chǎng)時(shí)必須按它停留的時(shí)間長(zhǎng)短交納費(fèi)用。試為停車場(chǎng)編制按上述要求進(jìn)行管理的模擬程序。[測(cè)試數(shù)據(jù)]設(shè)n=2,輸入數(shù)據(jù)為：（‘A’，1，5），（‘A’，2，10），（‘D’，1，15），（‘A’，3，20），（‘A’，4，25），（‘A’，5，30），（‘D’，2，35），（‘D’，4，40），（‘E’，0，0）。每一組輸入數(shù)據(jù)包括三個(gè)數(shù)據(jù)項(xiàng)：汽車“到達(dá)”或“離去”信息、汽車牌照號(hào)碼及到達(dá)或離去的時(shí)刻，其中，‘A’表示到達(dá)；‘D’表示離去，‘E’表示輸入結(jié)束