【正文】 進(jìn)方法；[實(shí)現(xiàn)提示]可以用一個(gè)二維數(shù)組存儲(chǔ)迷宮圖，值為1或者0分別表示通路和不通； 搜索路徑可以參考樹的深度優(yōu)先和廣度優(yōu)先算法。（2）整個(gè)統(tǒng)計(jì)過程中只對(duì)小說文字掃描一遍以提高效率。出現(xiàn)位置所在行的行號(hào)可以用鏈表存儲(chǔ)。程序的輸出結(jié)果是每個(gè)詞的出現(xiàn)次數(shù)和出現(xiàn)位置所在行的行號(hào)，格式自行設(shè)計(jì)。文學(xué)研究助手[問題描述]文學(xué)研究人員需要統(tǒng)計(jì)某篇英文小說中某些形容詞的出現(xiàn)次數(shù)和位置。（2）顯示輸入序列和棧的變化過程。假設(shè)操作數(shù)是正整數(shù)，運(yùn)算符只含加減乘除等四種運(yùn)算符，界限符有左右括號(hào)和表達(dá)式起始、結(jié)束符“”，如：（7+15）*（2328/4）。[選作內(nèi)容]（1）求多個(gè)景點(diǎn)的最佳（最短）游覽路徑。要求能夠回答有關(guān)景點(diǎn)介紹、游覽路徑等問題。三．設(shè)計(jì)要求學(xué)生要發(fā)揮自主學(xué)習(xí)的能力，充分利用時(shí)間，安排好課設(shè)的時(shí)間計(jì)劃，并在課設(shè)過程中不斷檢測(cè)自己的計(jì)劃完成情況，及時(shí)的向教師匯報(bào)。要結(jié)構(gòu)清晰，重點(diǎn)函數(shù)的重點(diǎn)變量，重點(diǎn)功能部分要加上清晰的程序注釋。給出實(shí)現(xiàn)功能的一組或多組測(cè)試數(shù)據(jù)，程序調(diào)試后，將按照此測(cè)試數(shù)據(jù)進(jìn)行測(cè)試的結(jié)果列出來。學(xué)好數(shù)據(jù)結(jié)構(gòu)對(duì)掌握實(shí)際編程能力是很有幫助的?？偝煽?jī)由平時(shí)成績(jī)和考試成績(jī)組成。條件允許可采用CAI、電子教案、幻燈片、參觀等進(jìn)行輔助教學(xué)。待填入哈希表的人名共有30個(gè)，取平均查找長(zhǎng)度的上限為2。（二）實(shí)驗(yàn)過程 編程實(shí)現(xiàn)實(shí)驗(yàn)內(nèi)容（三）實(shí)驗(yàn)教學(xué)基本要求通過實(shí)例，使學(xué)生熟悉圖的各種存儲(chǔ)結(jié)構(gòu)的特性，掌握如何應(yīng)用圖結(jié)構(gòu)解決具體問題。實(shí)驗(yàn)后學(xué)生提交實(shí)驗(yàn)報(bào)告。每門課恰好占一個(gè)學(xué)期。（四）實(shí)驗(yàn)設(shè)備和材料 計(jì)算機(jī)。棧以順序結(jié)構(gòu)實(shí)現(xiàn)，隊(duì)列以鏈表結(jié)構(gòu)實(shí)現(xiàn)。（二）教學(xué)內(nèi)容 本章知識(shí)點(diǎn)：(理解)；(掌握)；(掌握)；(掌握)；(掌握)；（熟悉）；，外存讀/寫次數(shù)的計(jì)算方法(掌握)。（二）教學(xué)內(nèi)容 本章知識(shí)點(diǎn)：(掌握)； (掌握)；(掌握)。（三）重點(diǎn)與難點(diǎn)重點(diǎn)：圖的存儲(chǔ)結(jié)構(gòu)；圖的遍歷 難點(diǎn)：圖遍歷的算法；第八章動(dòng)態(tài)存儲(chǔ)管理（一）目的要求了解邊界標(biāo)識(shí)法和伙伴系統(tǒng)；無用單元收集和緊縮；（二）教學(xué)內(nèi)容 本章知識(shí)點(diǎn)：（了解）；（了解）。（三）重點(diǎn)與難點(diǎn) 重點(diǎn)：二叉樹的概念、性質(zhì)；二叉樹的遍歷方式；構(gòu)造二叉排序樹。（二）教學(xué)內(nèi)容 本章知識(shí)點(diǎn)：(掌握)； (掌握)；，領(lǐng)會(huì)以三元組表示稀疏矩陣時(shí)進(jìn)行運(yùn)算采用的處理方法(掌握)；，學(xué)會(huì)廣義表的表頭，表尾分析方法(掌握)； (掌握)。難點(diǎn)：遞歸的編程實(shí)現(xiàn)；循環(huán)隊(duì)列和鏈隊(duì)列的基本運(yùn)算。難點(diǎn)：鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)及其常用算法；雙向循環(huán)鏈表。（三）重點(diǎn)與難點(diǎn)重點(diǎn)：數(shù)據(jù)結(jié)構(gòu)的定義；算法的描述方法。三、主要內(nèi)容、重點(diǎn)及深度本門課程共60學(xué)時(shí)，其中理論教學(xué)48學(xué)時(shí)，實(shí)驗(yàn)教學(xué)12學(xué)時(shí)。包括樹的定義、樹的術(shù)語、樹的抽象數(shù)據(jù)類型掌握：二叉樹的概念、性質(zhì)及二叉樹的表示熟練掌握：二叉樹的遍歷方法掌握：線索化二叉樹的特性及尋找某結(jié)點(diǎn)的前驅(qū)和后繼的方法熟練掌握：堆的定義，堆的建立、堆的插入與刪除、堆的向上和向下調(diào)整等算法以及用來實(shí)現(xiàn)優(yōu)先級(jí)隊(duì)列的方法掌握：樹與森林的實(shí)現(xiàn)，重點(diǎn)在用二叉樹實(shí)現(xiàn)掌握：森林與二叉樹的轉(zhuǎn)換；樹的遍歷算法掌握：二叉樹的計(jì)數(shù)方法及從二叉樹遍歷結(jié)果得到二叉樹的方法掌握：霍夫曼樹的實(shí)現(xiàn)方法、構(gòu)造霍夫曼編碼的方法及帶權(quán)路徑長(zhǎng)度的計(jì)算七、集合與搜索 5學(xué)時(shí)教學(xué)內(nèi)容：集合及其表示：集合基本概念；以集合為基礎(chǔ)的抽象數(shù)據(jù)類型；用位向量實(shí)現(xiàn)集合抽象據(jù)類型；用有序鏈表實(shí)現(xiàn)集合的抽象數(shù)據(jù)類型并查集：并查集的定義；并查集的實(shí)現(xiàn)簡(jiǎn)單的搜索結(jié)構(gòu)：搜索的概念；靜態(tài)搜索結(jié)構(gòu)；順序搜索；基于有序順序表的順序搜索和折半搜索二叉搜索樹：二叉搜索樹的定義；二叉搜索樹上的搜索；二叉搜索樹的插入；二叉搜索樹的刪除AVL樹：AVL樹定義；平衡化旋轉(zhuǎn)；AVL樹的插入和刪除；AVL樹高度教學(xué)要求：掌握：集合的基本概念及其表示方法，包括位數(shù)組及有序鏈表的表示及其相關(guān)操作的實(shí)現(xiàn)算法掌握：利用并查集實(shí)現(xiàn)集合的方法熟練掌握：靜態(tài)搜索表的順序搜索和折半搜索算法及其性能分析方法熟練掌握：二叉搜索樹的表示、搜索、插入、刪除算法及其性能分析方法掌握：AVL樹的平衡化旋轉(zhuǎn)、構(gòu)造、插入、刪除時(shí)的調(diào)整方法及其性能分析八、圖 7學(xué)時(shí)教學(xué)內(nèi)容：圖的基本概念：圖的基本概念；圖的抽象數(shù)據(jù)類型圖的存儲(chǔ)表示：鄰接矩陣；鄰接表；鄰接多重表圖的遍歷與連通性：深度優(yōu)先搜索；廣度優(yōu)先搜索；連通分量；關(guān)節(jié)點(diǎn)與重連通分量最小生成樹：kruskul算法；prim算法單源最短路徑問題：dijkstra算法活動(dòng)網(wǎng)絡(luò)：AOV網(wǎng)絡(luò)與拓?fù)渑判?；AOE網(wǎng)絡(luò)與關(guān)鍵路徑教學(xué)要求：理解：圖的基本概念和圖的抽象數(shù)據(jù)類型掌握：圖的3種存儲(chǔ)表示：鄰接矩陣、鄰接表和鄰接多重表。四、棧和隊(duì)列 3學(xué)時(shí)教學(xué)內(nèi)容：棧：棧的抽象數(shù)據(jù)類型；棧的順序存儲(chǔ)表示；棧的鏈接存儲(chǔ)表示表達(dá)式求值：中綴表達(dá)式求值；中綴表示到后綴表示的轉(zhuǎn)換隊(duì)列 ：隊(duì)列的抽象數(shù)據(jù)類型；隊(duì)列的順序存儲(chǔ)表示；隊(duì)列的鏈接存儲(chǔ)表示；隊(duì)列的應(yīng)用舉例優(yōu)先級(jí)隊(duì)列：優(yōu)先級(jí)隊(duì)列的定義；優(yōu)先級(jí)隊(duì)列的存儲(chǔ)表示教學(xué)要求：熟練掌握：棧的定義、特性和棧的抽象數(shù)據(jù)類型，棧的順序表示、鏈表表示以及相應(yīng)操作的實(shí)現(xiàn)。課程考試具體規(guī)定請(qǐng)參看該課程考核說明。考試考試是對(duì)學(xué)生掌握知識(shí)水平的檢驗(yàn)。要求學(xué)生珍惜實(shí)驗(yàn)機(jī)時(shí)，真正做到學(xué)有所獲。教師講課只是起到拋磚引玉的作用，關(guān)鍵還在于學(xué)生的自學(xué)。各地方電大應(yīng)聘請(qǐng)有經(jīng)驗(yàn)、認(rèn)真負(fù)責(zé)的教師任教，以習(xí)題課、專題討論或答疑的方式，對(duì)課程中的重要概念和典型問題的解決方法進(jìn)行總結(jié)和深入討論，鞏固和加深課堂內(nèi)學(xué)到的知識(shí)。第二部分 多種媒體教材一體化總體設(shè)計(jì)初步方案一、學(xué)時(shí)分配課程教學(xué)總學(xué)時(shí)數(shù)為 72學(xué)時(shí)，4學(xué)分，其中講授學(xué)時(shí)48，實(shí)驗(yàn)24教 學(xué) 內(nèi) 容講授學(xué)時(shí)實(shí)驗(yàn)學(xué)時(shí)一、數(shù)據(jù)結(jié)構(gòu)基本概念及算法分析3學(xué)時(shí)2學(xué)時(shí)二、數(shù)組3學(xué)時(shí)2學(xué)時(shí)三、鏈表3學(xué)時(shí)3學(xué)時(shí)四、棧和隊(duì)列3學(xué)時(shí)2學(xué)時(shí)五、遞歸3學(xué)時(shí)2學(xué)時(shí)六、樹與森林9學(xué)時(shí)4學(xué)時(shí)七、集合與搜索5學(xué)時(shí)2學(xué)時(shí)八、圖7學(xué)時(shí)4學(xué)時(shí)九、排序7學(xué)時(shí)3學(xué)時(shí)十、索引與散列結(jié)構(gòu)5學(xué)時(shí)二、教學(xué)環(huán)節(jié)電視教學(xué)本課程是計(jì)算機(jī)專業(yè)基礎(chǔ)課，內(nèi)容多且?guī)в幸欢ǖ某橄笮裕瑢W(xué)習(xí)起來有一定難度。五、課程教學(xué)要求的層次熟練掌握：要求學(xué)生能夠全面、深入理解和熟練掌握所學(xué)內(nèi)容，并能夠用其知識(shí)分析、設(shè)計(jì)和解答相關(guān)的應(yīng)用問題。為后續(xù)計(jì)算機(jī)專業(yè)課程的學(xué)習(xí)打下堅(jiān)實(shí)的基礎(chǔ)。第二篇：數(shù)據(jù)結(jié)構(gòu)教學(xué)大綱中央廣播電視大學(xué)“開放教育試點(diǎn)”計(jì)算機(jī)科學(xué)與技術(shù)專業(yè)（本科）《數(shù)據(jù)結(jié)構(gòu)》課程教學(xué)大綱第一部分 大綱說明一、課程的性質(zhì)和任務(wù)《數(shù)據(jù)結(jié)構(gòu)》是計(jì)算機(jī)科學(xué)與技術(shù)專業(yè)本科生的一門必修課程。重點(diǎn)：外部排序算法 難點(diǎn)：多路平衡歸并的實(shí)現(xiàn) 第11章 算法設(shè)計(jì)的一般方法（2學(xué)時(shí)）1．重點(diǎn)（1）有效算法的概念，問題固有難度的概念；（2）遞歸法；分治法；平衡原則；貪心法；動(dòng)態(tài)規(guī)劃的基本原理；（3）．難點(diǎn)（1）問題固有難度的概念；（2）遞歸分治法的效率分析（寫出時(shí)間耗費(fèi)的遞推式，并求解）；（3）動(dòng)態(tài)規(guī)劃法中的狀態(tài)轉(zhuǎn)移方程的確定。重點(diǎn)：各種算法的基本思想及實(shí)現(xiàn)。難點(diǎn)：圖的遍歷算法，最短路徑算法。難點(diǎn)：哈夫曼樹構(gòu)造的方法和算法第7章 圖（11學(xué)時(shí)） 圖的定義和術(shù)語 圖的存儲(chǔ)結(jié)構(gòu)（數(shù)組表示法，鄰接表，十字鏈表，鄰接多重表） 圖的遍歷（深度優(yōu)先搜索，廣度優(yōu)先搜索） 圖的連通性問題（無向圖的連通分量和生成樹，有向圖的強(qiáng)連通分量，最小生成樹，關(guān)節(jié)點(diǎn)和重連通分量） 有向無環(huán)圖及其應(yīng)用（拓?fù)渑判?，關(guān)鍵路徑） 最短路徑（從某個(gè)源點(diǎn)到其余各項(xiàng)點(diǎn)的最短路徑，每一對(duì)頂點(diǎn)之間的最短路徑）基本要求：了解：圖的基本概念和相關(guān)術(shù)語。第6章 樹與二叉樹（15學(xué)時(shí)） 樹的定義和基本術(shù)語 二叉樹（二叉樹的定義，二叉樹的性質(zhì)，二叉樹的存儲(chǔ)結(jié)構(gòu)） 遍歷二叉樹和線索二叉樹（遍歷二叉樹，線索二叉樹） 樹和森林（樹的存儲(chǔ)結(jié)構(gòu)，森林與二叉樹的轉(zhuǎn)換，樹和森林的遍歷） 樹與等價(jià)問題 赫夫曼樹及其應(yīng)用（最優(yōu)二叉樹（赫夫曼樹），赫夫曼編碼） 回溯法與樹的遍歷 樹的計(jì)數(shù)基本要求：了解：理解樹與森林的定義與術(shù)語。也可以采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。重點(diǎn)：主要操作和運(yùn)算。重點(diǎn)： 棧和隊(duì)列的算法實(shí)現(xiàn)。第3章 棧與隊(duì)列（4學(xué)時(shí)） 棧（定義，棧的表示和實(shí)現(xiàn)） 棧的應(yīng)用舉例（數(shù)制轉(zhuǎn)換，括號(hào)匹配的檢驗(yàn)，行編輯程序，迷宮求解，表達(dá)式求值） 棧與遞歸的實(shí)現(xiàn) 隊(duì)列及其實(shí)現(xiàn)（定義，鏈隊(duì)列，循環(huán)隊(duì)列） *離散事件模擬教學(xué)要求：熟練掌握棧和隊(duì)列的特性和在不同存儲(chǔ)結(jié)構(gòu)前提下的算法實(shí)現(xiàn)。掌握：要求熟練掌握處理線性表的各種算法。本課程以提高學(xué)生的計(jì)算機(jī)應(yīng)用能力和綜合素質(zhì)為目標(biāo)，通過課程教學(xué)，為學(xué)生構(gòu)建數(shù)據(jù)結(jié)構(gòu)與算法方面的知識(shí)體系，使學(xué)生一方面能夠根據(jù)問題選擇合適的數(shù)據(jù)結(jié)構(gòu)，設(shè)計(jì)高效的算法，提高程序設(shè)計(jì)能力，另一方面，在工程應(yīng)用中，具有甄別好算法的能力，也就是要從建模、解模和綜合等三個(gè)方面，提高學(xué)生的程序設(shè)計(jì)能力。通過本課程的教學(xué)，使學(xué)生知道求解非數(shù)值類問題的基本模型（表、樹、圖），模型的特點(diǎn)和適用場(chǎng)合，能夠根據(jù)問題設(shè)計(jì)和選擇好的算法，為學(xué)習(xí)后續(xù)的操作系統(tǒng)、編譯原理和軟件工程等專業(yè)課程，設(shè)計(jì)應(yīng)用程序打下基礎(chǔ)。第2章 線性表（8學(xué)時(shí)） 線性表的類型定義 線性表的順序表示和實(shí)現(xiàn) 線性表的鏈?zhǔn)奖硎竞蛯?shí)現(xiàn)（線性鏈表，循環(huán)鏈表，雙向鏈表） 一元多項(xiàng)式的表示及相加基本要求：了解：兩種存儲(chǔ)結(jié)構(gòu)（順序存儲(chǔ)結(jié)構(gòu)和鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)）及一元多項(xiàng)式的表示及相加。難點(diǎn)：鏈表的理解。掌握： 熟練掌握棧和隊(duì)列的特性和在不同存儲(chǔ)結(jié)構(gòu)前提下的算法實(shí)現(xiàn)。掌握：掌握串的基本概念和運(yùn)算。認(rèn)識(shí)到數(shù)組可以作為順序存儲(chǔ)結(jié)構(gòu)用于順序表、字符串和稀疏矩陣的實(shí)現(xiàn)。難點(diǎn)：廣義表的遞歸算法。重點(diǎn)： 樹的存儲(chǔ)結(jié)構(gòu)和遍歷算法。重點(diǎn)：圖的兩種主要存儲(chǔ)結(jié)構(gòu)及遍歷算法。掌握哈希表查找算法。掌握：基本掌握外排算法的基本思想，不同排序方法的比較。由于本課程內(nèi)容較多，在實(shí)際教學(xué)中可根據(jù)大綱內(nèi)容，進(jìn)行適當(dāng)調(diào)整。課程采用面向?qū)ο蟮挠^點(diǎn)討論數(shù)據(jù)結(jié)構(gòu)技術(shù)，并以兼有面向過程和面向?qū)ο箅p重特色的C++語言作為算法的描述工具，強(qiáng)化數(shù)據(jù)結(jié)構(gòu)基本知識(shí)和面向?qū)ο蟪绦蛟O(shè)計(jì)基本能力的雙基訓(xùn)練。四、教學(xué)方法和教學(xué)形式建議電視授課為主，結(jié)合面授輔導(dǎo)、面授或電子郵件答疑，進(jìn)行必要的上機(jī)實(shí)驗(yàn)。六、課程實(shí)驗(yàn)實(shí)驗(yàn)內(nèi)容和要求由省級(jí)電大作出具體規(guī)定，從2004年春開始按該課程實(shí)驗(yàn)教材規(guī)定進(jìn)行。面授輔導(dǎo)或答疑本課程教學(xué)過程中，面授輔導(dǎo)和答疑是必不可少的教學(xué)環(huán)節(jié)。自學(xué)與練習(xí)自學(xué)是獲取知識(shí)的重要手段。為此，安排一定的實(shí)驗(yàn)上機(jī)學(xué)時(shí)。除學(xué)校提供的時(shí)間外，要求課外學(xué)生利用自己可能擁有的計(jì)算機(jī)條件，完成更多的練習(xí)，不通過大量的實(shí)踐，能力和知識(shí)水平得不到有效得提高。因此，不要出難題、怪題，但也不要過于簡(jiǎn)單，適當(dāng)有一些編程題。有動(dòng)態(tài)鏈表和靜態(tài)鏈表之分了解：鏈表有單鏈表、循環(huán)單鏈表、雙向鏈表之分了解：?jiǎn)捂湵淼慕Y(jié)構(gòu)、特點(diǎn)掌握：?jiǎn)捂湵淼念惗x、構(gòu)造函數(shù)、單鏈表的插入與刪除算法了解：帶表頭結(jié)點(diǎn)的單鏈表的優(yōu)點(diǎn)和類定義及相應(yīng)操作的實(shí)現(xiàn)熟練掌握：用模板定義的單鏈表類了解：循環(huán)鏈表的特點(diǎn)，循環(huán)鏈表的類定義，以及用循環(huán)鏈表解決問題的方法掌握：雙向鏈表的特點(diǎn)，雙向鏈表的類定義及相關(guān)操作的實(shí)現(xiàn)，用雙向鏈表解決問題的方法。包括什么是遞歸，有那些種類的遞歸，遞歸問題的遞歸求解方法掌握：遞歸過程的機(jī)制與利用遞歸工作棧實(shí)現(xiàn)遞歸的方法了解：迷宮問題的遞歸求解思路及如何利用棧實(shí)現(xiàn)迷宮問題的非遞歸解法掌握：利用遞歸解決問題的分治法和回溯法掌握：廣義表的定義及其實(shí)現(xiàn)方法掌握：廣義表的遞歸算法六、樹與森林 9學(xué)時(shí)教學(xué)內(nèi)容：樹和森林的概念：樹的定義；樹的術(shù)語；樹的抽象數(shù)據(jù)類型二叉樹：二叉樹的定義；二叉樹的性質(zhì)；二叉樹的抽象數(shù)據(jù)類