數據結構課程設計教學大綱(編輯修改稿)

　

【文章內容簡介】 類和確定書號后登記到圖書帳目中去。如果這種書在帳目中已有，則只將總庫存量增加。②清除庫存：某種書已無保留價值，將它從圖書帳目中注銷。③某種書的現存量大于零，則借出一本，登記借閱者的圖書證號和歸還期限。④歸還：注銷對借閱者的登記，改變該書的現存量。⑤顯示：以凹入表的形式顯示B樹。這個操作是為了調試和維護的目的而設置的。下列B樹的打印格式如下所示：50，52 70，728第三篇：數據結構課程設計教學大綱《數據結構課程設計》教學大綱Data Structure Course Design一、課程的性質、教學目的和要求《數據結構》是計算機軟件的一門基礎課程，計算機科學各領域及有關的應用軟件都要用到各種類型的數據結構。學好數據結構對掌握實際編程能力是很有幫助的。為了學好《數據結構》，必須編寫一些在特定數據結構上的算法，通過上機調試，才能更好地掌握各種數據結構及其特點，同時提高解決計算機應用實際問題的能力。二、設計要點1．設計和調試過程要規范化。① 需求分析將題目中要求的功能進行敘述分析，并且設計解決此問題的數據存儲結構，（有些題目已經指定了數據存儲的，按照指定的設計），設計或敘述解決此問題的算法，描述算法建議使用流程圖，進行算法分析指明關鍵語句的時間復雜度。給出實現功能的一組或多組測試數據，程序調試后，將按照此測試數據進行測試的結果列出來。對有些題目提出算法改進方案，比較不同算法的優缺點。如果程序不能正常運行，寫出實現此算法中遇到的問題，和改進方法。②源程序（可以是一組源程序，即詳細設計部分）源程序要按照寫程序的規則來編寫。要結構清晰，重點函數的重點變量，重點功能部分要加上清晰的程序注釋。程序能夠運行，要有基本的容錯功能。盡量避免出現操作錯誤時出現死循環。2．課程設計實習報告的書寫格式① 設計題目（任選其一）②運行環境（軟、硬件環境）③算法設計的思想 ④算法的流程圖 ⑤算法設計分析 ⑥源代碼 ⑦運行結果分析 ⑧收獲及體會 3．實施方式可設23人一題，安排在《數據結構》課程開課學期布置題目，然后在期末前兩周完成。三．設計要求學生要發揮自主學習的能力，充分利用時間，安排好課設的時間計劃，并在課設過程中不斷檢測自己的計劃完成情況，及時的向教師匯報。課程設計按照教學要求需要1周時間完成，1周中每天至少要上68小時的機來調試C語言設計的程序，總共至少要上機調試程序30小時。為保證質量，需要每個學生將每天的上機調試程序的時間記錄下來，作為評判成績的標準之一。四．設計題目校園導游程序[問題描述]用無向網表示你所在學校的校園景點平面圖，圖中頂點表示主要景點，存放景點的編號、名稱、簡介等信息，圖中的邊表示景點間的道路，存放路徑長度等信息。要求能夠回答有關景點介紹、游覽路徑等問題。[基本要求]（1）查詢各景點的相關信息；（2）查詢圖中任意兩個景點間的最短路徑。（3）查詢圖中任意兩個景點間的所有路徑。（4）增加、刪除、更新有關景點和道路的信息。[選作內容]（1）求多個景點的最佳（最短）游覽路徑。（2）區分機動車道和人行道。（3）實現導游圖的仿真界面。算術表達式求值[問題描述]一個算術表達式是由操作數(operand)、運算符(operator)和界限符(delimiter)組成的。假設操作數是正整數，運算符只含加減乘除等四種運算符，界限符有左右括號和表達式起始、結束符“”，如：（7+15）*（2328/4）。引入表達式起始、結束符是為了方便。編程利用“算符優先法”求算術表達式的值。[基本要求]（1）從鍵盤讀入一個合法的算術表達式，輸出正確的結果。（2）顯示輸入序列和棧的變化過程。[選作內容]擴充運算符集合。引入變量操作數。操作數類型擴充到實數。文學研究助手[問題描述]文學研究人員需要統計某篇英文小說中某些形容詞的出現次數和位置。試寫一個實現這一目標的文字統計系統，稱為“文學研究助手”。[基本要求]英文小說存于一個文本文件中。待統計的詞匯集合要一次輸入完畢，即統計工作必須在程序的一次運行之后就全部完成。程序的輸出結果是每個詞的出現次數和出現位置所在行的行號，格式自行設計。[測試數據]以你的源程序模擬英文小說，程序語言保留字集作為待統計的詞匯集。[實現提示]設小說中的詞匯一律不跨行。這樣，每讀入一行，就統計每個詞在這行中的出現次數。出現位置所在行的行號可以用鏈表存儲。若某行中出現了不止一次，不必存多個相同的行號。如果讀者希望達到選作部分（1）和（2）所提出的要求，則首先應把KMP算法改寫成如下的等價形式，再將它推廣到多個模式的情形。[選作內容]（1）模式匹配要基于KMP算法。（2）整個統計過程中只對小說文字掃描一遍以提高效率。（3）假設小說中的每個單詞或者從行首開始，或者前置以一個空格符。利用單詞匹配特點另寫一個高效的統計程序，與KMP算法統計程序進行效率比較。（4）推廣到更一般的模式集匹配問題，并設待查模式串可以跨行（提示：定義操作getachar）[問題描述]可以輸入一個任意大小的迷宮數據，用非遞歸的方法求出一條走出迷宮的路徑，并將路徑輸出；[基本要求]含有兩個以上的迷宮圖，由用戶選擇哪一張迷宮圖； 實現深度優先、廣度優先兩種回溯法。在上交資料中請寫明：存儲結構、基本算法（可以使用程序流程圖）、源程序、算法的時間復雜度、另外可以提出算法的改進方法；[實現提示]可以用一個二維數組存儲迷宮圖，值為1或者0分別表示通路和不通； 搜索路徑可以參考樹的深度優先和廣度優先算法。[問題描述]假設表達式中允許有兩種括號：圓括號和方括號，其嵌套的順序隨意，即CC或[（[ ] [ ]）]等為正確格式，[（]）或（（（]均為不正確的格式。檢驗括號是否匹配的方法可用“期待的緊迫程度”這個概念來描述。例如：考慮下列的括號序列：[([ ] [ ])]8當計算機接受了第1個括號以后，他期待著與其匹配的第8個括號的出現，然而等來的卻是第2個括號，此時第1個括號“[”只能暫時靠邊，而迫切等待與第2個括號相匹配的 第7個括號“）”的出現，類似的，因只等來了第3個括號“[”，此時，其期待的緊迫程度較第2個括號更緊迫，則第2個括號只能靠邊，讓位于第3個括號，顯然第3個括號的期待緊迫程度高于第2個括號，而第2個括號的期待緊迫程度高于第1個括號；在接受了第4個括號之后，第3個括號的期待得到了滿足，消解之后，第2個括號的期待匹配就成了最急迫的任務了，??，依次類推。可見這個處理過程正好和棧的特點相吻合。[基本要求]設置一個棧，每讀入一個括號，若是左括號，則作為一個新的更急迫的期待壓入棧中，若是右括號，則或者是和當前棧頂的括號相匹配，或者是不合法的情況，輸出“此串括號匹配不合法”。在初始和結束時，棧應該是空的。[測試數據]輸入 （[ ]（）），結果“匹配”輸入 [（）]，結果“此串括號匹配不合法”為起始和結束標志。[問題描述]設停車場內只有一個可停放n輛汽車的狹長通道，且只有一個大門可供汽車進出。汽車在停車場內按車輛到達時間的先后順序，依次由北向南排列（大門在最南端，最先到達的第一輛車停放在車場的最北端），若車場內已停滿n輛汽車，則后來的汽車只能在門外的便道上等候，一旦有車開走，則排在便道上的第一輛車即可開入；當停車場內某輛車要離開時，在它之后開入的車輛必須先退出車場為它讓路，待該輛車開出大門外，其它車輛再按原次序進入車場，每輛停放在車場的車在它離開停車場時必須按它停留的時間長短交納費用。試為停車場編制按上述要求進行管理的模擬程序。[測試數據]設n=2,輸入數據為：（‘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）。每一組輸入數據包括三個數據項：汽車“到達”或“離去”信息、汽車牌照號碼及到達或離去的時刻，其中，‘A’表示到達；‘D’表示離去，‘E’表示輸入結束。[基本要求]以棧模擬停車場，以隊列模擬車場外的便道，按照從終端讀入的輸入數據序列進行模擬管理。每一組輸入數據包括三個數據項：汽車“到達”或“離去”信息、汽車牌照號碼及到達或離去的時刻，對每一組輸入數據進行操作后的輸出數據為：若是車輛到達，則輸出汽車在停車場內或便道上的停車位置；若是車離去；則輸出汽車在停車場內停留的時間和應交納的費用（在便道上停留的時間不收費）。棧以順序結構實現，隊列以鏈表實現。[實現提示]需另設一個棧，臨時停放為給要離去的汽車讓路而從停車場退出來的汽車，也用順序存儲結構實現。輸入數據按到達或離去的時刻有序。棧中每個元素表示一輛汽車，包含兩個數據項：汽車的牌照號碼和進入停車場的時刻。[選作內容]（1）兩個棧共享空間，思考應開辟數組的空間是多少？（2）汽車可有不同種類，則它們的占地面積不同，收費標準也不同，1輛十輪卡車占地面積相當于3輛小汽車的占地面積。（3）汽車可以直接從便道上開走，此時排在它前面的汽車要先開走讓路，然后再依次排到隊尾。（4）停放在便道上的汽車也收費，收費標準比停放在停車場的車低，請思考如何修改結構以滿足這種要求。[問題描述]文本編輯程序是利用計算機進行文字加工的基本軟件工具，實現對文本文件的插入、刪除等修改操作。限制這些操作以行為單位進行的編輯程序稱為行編輯程序。被編輯的文本文件可能很大，全部讀入編輯程序的數據空間（內存）的做法既不經濟，也不總能實現。一種解決方法是逐段地編輯。任何時刻只把待編輯文件的一段放在內存，稱為活區。試按照這種方法實現一個簡單的行編輯程序。設文件每行不超過320個字符，很少超過80字符。[基本要求]實現以下4條基本編輯命令：（1）行插入。格式：i將插入活區中第行之后（2）行刪除。格式：d[□]刪除活區中第行（到第行）。兩種格式的例子是：“d10↙”和“d10□14↙”（3）活區切換。格式：n將活區寫入輸出文件，并從輸入文件中讀入下一段，作為新的活區。（4）活區顯示。格式：p逐頁地（每頁20行）顯示活區內容，每顯示一頁之后請用戶決定是否繼續顯示以后各頁（如果存在）。印出的每一行要前置以行號和一個空格符，行號固定占4位，增量為1。各條命令中的行號均須在活區中各行行號范圍之內，只有插入命令的行號可以等于活區第一行行號減1，表示插入當前屏幕中第一行之前，否則命令參數非法。[測試數據]由學生依據軟件工程的測試技術自己確定。注意測試邊界數據，如首行、尾行。[實現提示]（1）設活區的大小用行數activemaxlen（可設為100）來描述。考慮到文本文件行長通常為正態分布，且峰值在60到70之間，用320activemaxlen大小的字符數組實現存儲將造成大量浪費。可以以標準行塊為單位為各行分配存儲，每個標準行塊含81個字符。這些行塊可以組成一個數組，也可以利用動態 8 鏈表連接起來。一行文字可能占多個行塊。行尾可用一個特殊的ASCII字符（如(012)8）標識。此外，還應記住活區起始行號。行插入將引起隨后各行行號的順序下推。（2）初始化過程包括：請用戶提供輸入文件名（空串表示無輸入文件）和輸出文件名，兩者不能相同。然后盡可能多地從輸入文件中讀入各行，但不超過activemaxlenx。x的值可以自定，例如20。（3）在執行行插入命令的過程中，每接收到一行時到要檢查活區大小是否已達activemaxlen。如果是，則為了在插入這一行之后仍保持活區大小不超過activemaxlen，應將插入點之前的活區部分中第一行輸出到輸出