【正文】 activemaxlen，應(yīng)將插入點之前的活區(qū)部分中第一行輸出到輸出文件中；若插入點為第一行之前，則只得將新插入的這一行輸出。x的值可以自定，例如20。（2）初始化過程包括：請用戶提供輸入文件名（空串表示無輸入文件）和輸出文件名，兩者不能相同。此外，還應(yīng)記住活區(qū)起始行號。一行文字可能占多個行塊。可以以標準行塊為單位為各行分配存儲，每個標準行塊含81個字符。[實現(xiàn)提示]（1）設(shè)活區(qū)的大小用行數(shù)activemaxlen（可設(shè)為100）來描述。[測試數(shù)據(jù)]由學(xué)生依據(jù)軟件工程的測試技術(shù)自己確定。印出的每一行要前置以行號和一個空格符，行號固定占4位，增量為1。（4）活區(qū)顯示。兩種格式的例子是：“d10↙”和“d10□14↙”（3）活區(qū)切換。格式：i將插入活區(qū)中第行之后（2）行刪除。設(shè)文件每行不超過320個字符，很少超過80字符。任何時刻只把待編輯文件的一段放在內(nèi)存，稱為活區(qū)。被編輯的文本文件可能很大，全部讀入編輯程序的數(shù)據(jù)空間（內(nèi)存）的做法既不經(jīng)濟，也不總能實現(xiàn)。[問題描述]文本編輯程序是利用計算機進行文字加工的基本軟件工具，實現(xiàn)對文本文件的插入、刪除等修改操作。（3）汽車可以直接從便道上開走，此時排在它前面的汽車要先開走讓路，然后再依次排到隊尾。棧中每個元素表示一輛汽車，包含兩個數(shù)據(jù)項：汽車的牌照號碼和進入停車場的時刻。[實現(xiàn)提示]需另設(shè)一個棧，臨時停放為給要離去的汽車讓路而從停車場退出來的汽車，也用順序存儲結(jié)構(gòu)實現(xiàn)。每一組輸入數(shù)據(jù)包括三個數(shù)據(jù)項：汽車“到達”或“離去”信息、汽車牌照號碼及到達或離去的時刻，對每一組輸入數(shù)據(jù)進行操作后的輸出數(shù)據(jù)為：若是車輛到達，則輸出汽車在停車場內(nèi)或便道上的停車位置；若是車離去；則輸出汽車在停車場內(nèi)停留的時間和應(yīng)交納的費用（在便道上停留的時間不收費）。每一組輸入數(shù)據(jù)包括三個數(shù)據(jù)項：汽車“到達”或“離去”信息、汽車牌照號碼及到達或離去的時刻，其中，‘A’表示到達；‘D’表示離去，‘E’表示輸入結(jié)束。試為停車場編制按上述要求進行管理的模擬程序。[問題描述]設(shè)停車場內(nèi)只有一個可停放n輛汽車的狹長通道，且只有一個大門可供汽車進出。在初始和結(jié)束時，棧應(yīng)該是空的?？梢娺@個處理過程正好和棧的特點相吻合。檢驗括號是否匹配的方法可用“期待的緊迫程度”這個概念來描述。在上交資料中請寫明：存儲結(jié)構(gòu)、基本算法（可以使用程序流程圖）、源程序、算法的時間復(fù)雜度、另外可以提出算法的改進方法；[實現(xiàn)提示]可以用一個二維數(shù)組存儲迷宮圖，值為1或者0分別表示通路和不通； 搜索路徑可以參考樹的深度優(yōu)先和廣度優(yōu)先算法。利用單詞匹配特點另寫一個高效的統(tǒng)計程序，與KMP算法統(tǒng)計程序進行效率比較。（2）整個統(tǒng)計過程中只對小說文字掃描一遍以提高效率。如果讀者希望達到選作部分（1）和（2）所提出的要求，則首先應(yīng)把KMP算法改寫成如下的等價形式，再將它推廣到多個模式的情形。出現(xiàn)位置所在行的行號可以用鏈表存儲。[實現(xiàn)提示]設(shè)小說中的詞匯一律不跨行。程序的輸出結(jié)果是每個詞的出現(xiàn)次數(shù)和出現(xiàn)位置所在行的行號，格式自行設(shè)計。[基本要求]英文小說存于一個文本文件中。文學(xué)研究助手[問題描述]文學(xué)研究人員需要統(tǒng)計某篇英文小說中某些形容詞的出現(xiàn)次數(shù)和位置。引入變量操作數(shù)。（2）顯示輸入序列和棧的變化過程。編程利用“算符優(yōu)先法”求算術(shù)表達式的值。假設(shè)操作數(shù)是正整數(shù)，運算符只含加減乘除等四種運算符，界限符有左右括號和表達式起始、結(jié)束符“”，如：（7+15）*（2328/4）。（3）實現(xiàn)導(dǎo)游圖的仿真界面。[選作內(nèi)容]（1）求多個景點的最佳（最短）游覽路徑。（3）查詢圖中任意兩個景點間的所有路徑。要求能夠回答有關(guān)景點介紹、游覽路徑等問題。為保證質(zhì)量，需要每個學(xué)生將每天的上機調(diào)試程序的時間記錄下來，作為評判成績的標準之一。三．設(shè)計要求學(xué)生要發(fā)揮自主學(xué)習(xí)的能力，充分利用時間，安排好課設(shè)的時間計劃，并在課設(shè)過程中不斷檢測自己的計劃完成情況，及時的向教師匯報。盡量避免出現(xiàn)操作錯誤時出現(xiàn)死循環(huán)。要結(jié)構(gòu)清晰，重點函數(shù)的重點變量，重點功能部分要加上清晰的程序注釋。如果程序不能正常運行，寫出實現(xiàn)此算法中遇到的問題，和改進方法。給出實現(xiàn)功能的一組或多組測試數(shù)據(jù)，程序調(diào)試后，將按照此測試數(shù)據(jù)進行測試的結(jié)果列出來。二、設(shè)計要點1．設(shè)計和調(diào)試過程要規(guī)范化。學(xué)好數(shù)據(jù)結(jié)構(gòu)對掌握實際編程能力是很有幫助的。六、本課程與其它課程的聯(lián)系與分工先修課包括：集合論，圖論，高級語言（結(jié)構(gòu)或記錄，指針）；后續(xù)課包括：數(shù)據(jù)庫，編譯原理，操作系統(tǒng)等。總成績由平時成績和考試成績組成。在課程后半程，安排3~4個上機實驗，讓學(xué)生應(yīng)用數(shù)據(jù)結(jié)構(gòu)的理論、方法，分組設(shè)計幾個較大的軟件，使理論與實際相結(jié)合。條件允許可采用CAI、電子教案、幻燈片、參觀等進行輔助教學(xué)。（二）實驗過程 編程實現(xiàn)實驗內(nèi)容（三）實驗教學(xué)基本要求 掌握索引技術(shù)的使用。待填入哈希表的人名共有30個，取平均查找長度的上限為2。（四）實驗設(shè)備和材料 計算機。（二）實驗過程 編程實現(xiàn)實驗內(nèi)容（三）實驗教學(xué)基本要求通過實例，使學(xué)生熟悉圖的各種存儲結(jié)構(gòu)的特性，掌握如何應(yīng)用圖結(jié)構(gòu)解決具體問題。（五）實驗學(xué)時 2學(xué)時實驗三最小生成樹問題（一）實驗內(nèi)容利用克魯斯卡爾算法求最小生成樹。實驗后學(xué)生提交實驗報告。（二）實驗過程編程實現(xiàn)實驗內(nèi)容。每門課恰好占一個學(xué)期。每個專業(yè)開設(shè)的課程都是確定的，而且課程在開設(shè)時間的安排必須滿足先修關(guān)系。（四）實驗設(shè)備和材料 計算機。（三）實驗教學(xué)基本要求通過實例，使學(xué)生掌握棧和隊列兩種特殊的線性結(jié)構(gòu)，掌握棧和隊列的特點。棧以順序結(jié)構(gòu)實現(xiàn)，隊列以鏈表結(jié)構(gòu)實現(xiàn)。實踐教學(xué)部分：上機實驗分4個專題，每個專題可提供2~4個難度不等的題目供選。（二）教學(xué)內(nèi)容 本章知識點：(理解)；(掌握)；(掌握)；(掌握)；(掌握)；（熟悉）；，外存讀/寫次數(shù)的計算方法(掌握)。難點：各種排序算法的時間復(fù)雜度分析。（二）教學(xué)內(nèi)容 本章知識點：(掌握)； (掌握)；(掌握)。（三）重點與難點重點：二叉排序樹的構(gòu)造方法、二叉平衡樹的建立方法；哈希表的構(gòu)造、應(yīng)用；難點：二叉排序樹的構(gòu)造及應(yīng)用；哈希表的構(gòu)造方法；查找的平均長度。（三）重點與難點重點：圖的存儲結(jié)構(gòu)；圖的遍歷 難點：圖遍歷的算法；第八章動態(tài)存儲管理（一）目的要求了解邊界標識法和伙伴系統(tǒng)；無用單元收集和緊縮；（二）教學(xué)內(nèi)容 本章知識點：（了解）；（了解）。第七章 圖（一）目的要求理解圖的基本概念；圖的存儲結(jié)構(gòu)；掌握圖的遍歷及應(yīng)用{最小生成樹，最短路徑等}；拓撲排序和關(guān)鍵路徑。（三）重點與難點 重點：二叉樹的概念、性質(zhì)；二叉樹的遍歷方式；構(gòu)造二叉排序樹。難點：稀疏矩陣的三元組表示；廣義表的存儲定義、操作。（二）教學(xué)內(nèi)容 本章知識點：(掌握)； (掌握)；，領(lǐng)會以三元組表示稀疏矩陣時進行運算采用的處理方法(掌握)；，學(xué)會廣義表的表頭，表尾分析方法(掌握)； (掌握)。（二）教學(xué)內(nèi)容 本章知識點：（了解）；(掌握)； (掌握)；，熟悉NEXT函數(shù)和改進NEXT函數(shù)的定義和計算(掌握)； (理解)。難點：遞歸的編程實現(xiàn)；循環(huán)隊列和鏈隊列的基本運算。（二）教學(xué)內(nèi)容 本章知識點： (掌握)；(掌握)； (熟練掌握)； (掌握)。難點：鏈式存儲結(jié)構(gòu)及其常用算法；雙向循環(huán)鏈表。第二章線性表（一）目的要求掌握線性表的邏輯結(jié)構(gòu)；線性表的存儲結(jié)構(gòu)及操作的實現(xiàn)；理解一元多項式的表示；（二）教學(xué)內(nèi)容 本章知識點：(掌握)；(掌握)；(掌握)；(掌握)。（三）重點與難點重點：數(shù)據(jù)結(jié)構(gòu)的定義；算法的描述方法。理解數(shù)據(jù)結(jié)構(gòu)的基本概念；算法設(shè)計；掌握算法的時間和空間復(fù)雜度。三、主要內(nèi)容、重點及深度本門課程共60學(xué)時，其中理論教學(xué)48學(xué)時，實驗教學(xué)12學(xué)時。包括深度優(yōu)先搜索和廣度優(yōu)先搜索算法、求連通分量的方法(不要求算法)理解：求解關(guān)節(jié)點及構(gòu)造重連通圖的方法(不要求算法)掌握：構(gòu)造最小生成樹的Prim算法和Kruskal算法，要求理解算法理解：如何用Dijkstra方法求解單源最短路徑問題(不要求算法)熟練掌握：活動網(wǎng)絡(luò)的拓撲排序算法掌握：求解關(guān)鍵路徑的方法九、排序 7學(xué)時教學(xué)內(nèi)容：概述插入排序：直接插入排序；折半插入排序；鏈表插入排序；希爾排序交換排序：起泡排序；快速排序選擇排序：直接選擇排序；錦標賽排序；堆排序歸并排序：歸并；迭代的歸并排序算法；遞歸的鏈表歸并排序基數(shù)排序：多關(guān)鍵碼排序；鏈式基數(shù)排序外排序：外排序的基本過程；k路平衡歸并；初始歸并段的生成；最佳歸并樹教學(xué)要求：掌握：排序的基本概念和性能分析方法掌握：插入排序、交換排序、選擇排序、歸并排序等內(nèi)排序的方法及其性能分析方法了解：基數(shù)排序方法及其性能分析方法掌握：多路平衡歸并等外排序方法及敗者樹構(gòu)造方法掌握：生成初始歸并段及敗者樹構(gòu)造方法掌握：最佳歸并樹的建立方法十、索引與散列結(jié)構(gòu) 5學(xué)時教學(xué)內(nèi)容：靜態(tài)索引結(jié)構(gòu)：線性索引；倒排索引；m路靜態(tài)查找樹動態(tài)索引結(jié)構(gòu)：動態(tài)的m路查找樹；B樹的定義；B樹的插入；B樹的刪除；B+樹散列：散列表與散列方法；散列函數(shù)；處理溢出的閉散列方法；處理溢出的開散列方法；散列表分析教學(xué)要求：熟練掌握：靜態(tài)索引結(jié)構(gòu)，包括線性索引、倒排索引、靜態(tài)索引樹的搜索和構(gòu)造方法熟練掌握：動態(tài)索引結(jié)構(gòu)，包括B樹、B+樹的搜索和構(gòu)造方法熟練掌握：散列法，包括散列函數(shù)的構(gòu)造、解決沖突的方法第三篇：數(shù)據(jù)結(jié)構(gòu)課程教學(xué)大綱數(shù)據(jù)結(jié)構(gòu)課程教學(xué)大綱一、課程基本概況課程名稱：數(shù)據(jù)結(jié)構(gòu)課程名稱（英文）： Data Structures課程編號：B09042課程總學(xué)時：60（其中，講課48，實驗12）課程學(xué)分：3課程分類：專業(yè)選修課開設(shè)學(xué)期：4適用專業(yè)：計算機網(wǎng)絡(luò)工程本科先修課程：集合論，圖論，高級語言（結(jié)構(gòu)或記錄，指針）后續(xù)課程：數(shù)據(jù)庫，編譯原理，操作系統(tǒng)等二、課程的性質(zhì)、目的和任務(wù)數(shù)據(jù)結(jié)構(gòu)是計算機專業(yè)的一門核心專業(yè)課程，是軟件課程中非常重要的一門課程，在整個專業(yè)教學(xué)中占有十分重要的地位，是一門理論性非常強的課程。包括樹的定義、樹的術(shù)語、樹的抽象數(shù)據(jù)類型掌握：二叉樹的概念、性質(zhì)及二叉樹的表示熟練掌握：二叉樹的遍歷方法掌握：線索化二叉樹的特性及尋找某結(jié)點的前驅(qū)和后繼的方法熟練掌握：堆的定義，堆的建立、堆的插入與刪除、堆的向上和向下調(diào)整等算法以及用來實現(xiàn)優(yōu)先級隊列的方法掌握：樹與森林的實現(xiàn)，重點在用二叉樹實現(xiàn)掌握：森林與二叉樹的轉(zhuǎn)換；樹的遍歷算法掌握：二叉樹的計數(shù)方法及從二叉樹遍歷結(jié)果得到二叉樹的方法掌握：霍夫曼樹的實現(xiàn)方法、構(gòu)造霍夫曼編碼的方法及帶權(quán)路徑長度的計算七、集合與搜索 5學(xué)時教學(xué)內(nèi)容：集合及其表示：集合基本概念；以集合為基礎(chǔ)的抽象數(shù)據(jù)類型；用位向量實現(xiàn)集合抽象據(jù)類型；用有序鏈表實現(xiàn)集合的抽象數(shù)據(jù)類型并查集：并查集的定義；并查集的實現(xiàn)簡單的搜索結(jié)構(gòu)：搜索的概念；靜態(tài)搜索結(jié)構(gòu)；順序搜索；基于有序順序表的順序搜索和折半搜索二叉搜索樹：二叉搜索樹的定義；二叉搜索樹上的搜索；二叉搜索樹的插入；二叉搜索樹的刪除AVL樹：AVL樹定義；平衡化旋轉(zhuǎn)；AVL樹的插入和刪除；AVL樹高度教學(xué)要求：掌握：集合的基本概念及其表示方法，包括位數(shù)組及有序鏈表的表示及其相關(guān)操作的實現(xiàn)算法掌握：利用并查集實現(xiàn)集合的方法熟練掌握：靜態(tài)搜索表的順序搜索和折半搜索算法及其性能分析方法熟練掌握：二叉搜索樹的表示、搜索、插入、刪除算法及其性能分析方法掌握：AVL樹的平衡化旋轉(zhuǎn)、構(gòu)造、插入、刪除時的調(diào)整方法及其性能分析八、圖 7學(xué)時教學(xué)內(nèi)容：圖的基本概念：圖的基本概念；圖的抽象數(shù)據(jù)類型圖的存儲表示：鄰接矩陣；鄰接表；鄰接多重表圖的遍歷與連通性：深度優(yōu)先搜索；廣度優(yōu)先搜索；連通分量；關(guān)節(jié)點與重連通分量