《數據結構》課程設計教學大綱-預覽頁

　

【正文】 確定其拓撲有序后求關鍵路徑。1B樹問題描述：完成B樹的創建、查找、插入和刪除。四、指導方式集體輔導與個別輔導相結合。學好數據結構對掌握實際編程能力是很有幫助的。給出實現功能的一組或多組測試數據，程序調試后，將按照此測試數據進行測試的結果列出來。要結構清晰，重點函數的重點變量，重點功能部分要加上清晰的程序注釋。三．設計要求學生要發揮自主學習的能力，充分利用時間，安排好課設的時間計劃，并在課設過程中不斷檢測自己的計劃完成情況，及時的向教師匯報。比賽分成m個男子項目，和w個女子項目。規定：輸入數據形式和范圍：20以內的整數（如果做得更好可以輸入學校的名稱，運動項目的名稱）輸出形式：有中文提示，各學校分數為整形界面要求：有合理的提示，每個功能可以設立菜單，根據提示，可以完成相關的功能要求。測試數據及測試結果請在上交的資料中寫明；一元多項式計算*問題描述：能夠按照指數降序排列建立并輸出多項式； 能夠完成兩個多項式的相加、相減，并將結果輸入；在上交資料中請寫明：存儲結構、多項式相加的基本過程的算法（可以使用程序流程圖）、源程序、測試數據和結果、算法的時間復雜度、另外可以提出算法的改進方法；訂票系統*問題描述：通過此系統可以實現如下功能： 1）錄入：可以錄入航班情況（數據可以存儲在一個數據文件中，數據結構、具體數據自定）2）查詢：可以查詢某個航線的情況（如，輸入航班號，查詢起降時間，起飛抵達城市，航班票價，票價折扣，確定航班是否滿倉）； 可以輸入起飛抵達城市，查詢飛機航班情況；3）訂票：（訂票情況可以存在一個數據文件中，結構自己設定）可以訂票，如果該航班已經無票，可以提供相關可選擇航班； 4）退票： 可退票，退票后修改相關數據文件；客戶資料有姓名，證件號，訂票數量及航班情況，訂單要有編號。*存儲結構使用線性表，分別用幾個子函數實現相應的功能；*輸入數據的形式和范圍：可以輸入大寫、小寫的英文字母、任何數字及標點符號。設計一個程序來求出出列順序。*輸入數據：輸入m,n m,n 為整數，n建立二叉樹，層序、先序遍歷（用遞歸或非遞歸的方法都可以）*問題描述：要求能夠輸入樹的各個結點，并能夠輸出用不同方法遍歷的遍歷序列；分別建立建立二叉樹存儲結構的的輸入函數、輸出層序遍歷序列的函數、輸出先序遍歷序列的函數；赫夫曼樹的建立*問題描述：建立建立最優二叉樹函數*要求：可以建立函數輸入二叉樹，并輸出其赫夫曼樹在上交資料中請寫明：存儲結構、基本算法（可以使用程序流程圖）、輸入輸出、源程序、測試數據和結果、算法的時間復雜度、另外可以提出算法的改進方法；紙牌游戲*問題描述：編號為152張牌，正面向上，從第2張開始，以2為基數，是2的倍數的牌翻一次，直到最后一張牌；然后，從第3張開始，以3為基數，是3的倍數的牌翻一次，直到最后一張牌；然后…從第4張開始，以4為基數，是4的倍數的牌翻一次，直到最后一張牌；...再依次5的倍數的牌翻一次，6的，7的 直到 以52為基數的 翻過。*輸入的數據形式為任何一個正整數，大小不限。*基本要求：利用雙向循環鏈表實現長整數的存儲，每個結點含一個整形變量。（2）2345,6789；7654,3211；應輸出“1,0000,0000”。（7）1,0000,9999,9999；1；應輸出“1,0001,0000,0000”。相加過程中不要破壞兩個操作數鏈表。要求每個方格上只進入一次，走遍棋盤上全部64個方格。1校園導游咨詢 *問題描述：（1）設計你的學校的校園平面圖，所含景點不少于10個。*測試數據：由讀者根據實際情況指定。*問題描述：1）輸入一個任意大小的迷宮，任設起點、終點、障礙，用棧求出一條走出迷宮的路徑，并顯示在屏幕上。4）本程序只求出一條成功的通路，但若對求解函數MazePath稍加更改即可求得全部路徑。21．算術表達式求值演示*問題描述：表達式求值是實現程序設計語言的基本問題之一，也是棧的應用的一個典型例子。*實現提示：（1）設置運算棧和運算數棧輔助分析算符優先關系。22．稀疏矩陣運算器*問題描述：稀疏矩陣是指那些多數元素為0的矩陣。稀疏矩陣的輸入形式采用三元組表示，而運算結構的矩陣則以通常的陣列形式列出。注意研究教科書中的算法，以便提高計算效率。*基本要求：（1）每種書的登記內容至少包括書號、書名、作者、現存量和總庫存量等五4。如果這種書在帳目中已有，則只將總庫存量增加。⑤顯示：以凹入表的形式顯示B樹。為了學好《數據結構》，必須編寫一些在特定數據結構上的算法，通過上機調試，才能更好地掌握各種數據結構及其特點，同時提高解決計算機應用實際問題的能力。對有些題目提出算法改進方案，比較不同算法的優缺點。程序能夠運行，要有基本的容錯功能。課程設計按照教學要求需要1周時間完成，1周中每天至少要上68小時的機來調試C語言設計的程序，總共至少要上機調試程序30小時。[基本要求]（1）查詢各景點的相關信息；（2）查詢圖中任意兩個景點間的最短路徑。（2）區分機動車道和人行道。引入表達式起始、結束符是為了方便。[選作內容]擴充運算符集合。試寫一個實現這一目標的文字統計系統，稱為“文學研究助手”。[測試數據]以你的源程序模擬英文小說，程序語言保留字集作為待統計的詞匯集。若某行中出現了不止一次，不必存多個相同的行號。（3）假設小說中的每個單詞或者從行首開始，或者前置以一個空格符。[問題描述]假設表達式中允許有兩種括號：圓括號和方括號，其嵌套的順序隨意，即CC或[（[ ] [ ]）]等為正確格式，[（]）或（（（]均為不正確的格式。[基本要求]設置一個棧，每讀入一個括號，若是左括號，則作為一個新的更急迫的期待壓入棧中，若是右括號，則或者是和當前棧頂的括號相匹配，或者是不合法的情況，輸出“此串括號匹配不合法”。汽車在停車場內按車輛到達時間的先后順序，依次由北向南排列（大門在最南端，最先到達的第一輛車停放在車場的最北端），若車場內已停滿n輛汽車，則后來的汽車只能在門外的便道上等候，一旦有車開走，則排在便道上的第一輛車即可開入；當停車場內某輛車要離開時，在它之后開入的車輛必須先退出車場為它讓路，待該輛車開出大門外，其它車輛再按原次序進入車場，每輛停放在車場的車在它離開停車場時必須按它停留的時間長短交納費用。[基本要求]以棧模擬停車場，以隊列模擬車場外的便道，按照從終端讀入的輸入數據序列進行模擬管理。輸入數據按到達或離去的時刻有序。（4）停放在便道上的汽車也收費，收費標準比停放在停車場的車低，請思考如何修改結構以滿足這種要求。一種解決方法是逐段地編輯。[基本要求]實現以下4條基本編輯命令：（1）行插入。格式：n將活區寫入輸出文件，并從輸入文件中讀入下一段，作為新的活區。各條命令中的行號均須在活區中各行行號范圍之內，只有插入命令的行號可以等于活區第一行行號減1，表示插入當前屏幕中第一行之前，否則命令參數非法?？紤]到文本文件行長通常為正態分布，且峰值在60到70之間，用320activemaxlen大小的字符數組實現存儲將造成大量浪費。行尾可用一個特殊的ASCII字符（如(012)8）標識。然后盡可能多地從輸入文件中讀入各行，但不超過activemaxlenx。（4）若輸入文件尚未讀完，活區切換命令可將原活區中最后幾行留在活區頂部，以保持閱讀連續性；否則，它意味著結束編輯或開始編輯另一個文件。[問題描述]很多涉及圖上操作的算法都是以圖的遍歷操作為基礎的。[測試數據]由學生依據軟件工程的測試技術自己確定。注意，生成樹的邊是有向邊，端點順序不能顛倒。1各種排序*問題描述：對30000個隨機整數，利用插入排序、希爾排序、起泡排序、快速排序、選擇排序、堆排序、歸并排序等排序方法進行排序，并統計每一種排序上機所花費的時間。1編制一個求解迷宮通路的圖形界面演示程序。3）橙色的實心小圓圈表示起點，綠色實心圓圈表示終點，空心圓圈表示足跡，紅色方塊表示墻。*實現提示：用帶頭結點的單鏈表存儲多項式，多項式的項數存在頭結點。利用教材中給出的算符優先關系，實現對算術四則混合運算表達式的求值，并仿照教材例31演示在求值中運算符棧、運算數棧、輸入字符和主要操作的變化過程。*選作內容：（1）擴充運算符集，如增加乘方、單目減、賦值等運算；（2）運算量可以是變量；（3）運算量可以是實數類型；（4）計數器的功能和仿鎮界面。*基本要求：以“帶行邏輯鏈接信息”的三元組順序表示稀疏矩陣，實現兩個矩陣相加、相減和相乘的運算。（2）程序可以對三元組的輸入順序加以限制，例如，按行優先。試設計一個圖書管理系統，將上述業務活動借助于計算機系統完成。（3）系統應實現的操作及功能定義如下：①采編入庫：新購入一種書，經分類和確定書號后登記到圖書帳目中去。④歸還：注銷對借閱者的登記，改變該書的現存量。靜態存儲一頁文章，每行最多不超過80個字符，共N行。 序列2’模式的字符序列。b+a’是屬該模式的字符序列，而‘１+３amp。學好數據結構對掌握實際編程能力是很有幫助的。對有些題目提出算法改進方案，比較不同算法的優缺點。程序能夠運行，要有基本的容錯功能。例如：當T=10，各件物品的體積{1，8，4，3，5，2}時，可找到下列4組解：（1，4，3，2），（1，4，5），（8，2），（3，5，2）。由于回溯求解的規則規則是“后進先出”因此自然要用到棧。一開始任選一個正整數作為報數上限值m,從第一個仍開始順時針方向自1開始順序報數，報到m時停止報數。（3）測試數據：m的初值為20，n=7 ,7個人的密碼依次為3，1，7，2，4，7，4，首先m=6,則正確的輸出是什么？（4）輸入數據：建立輸入處理輸入數據，輸入m的初值，n，輸入每個人的密碼，建立單循環鏈表。（2）要求：輸入的數據形式為任何一個正整數，大小不限。*基本要求：利用雙向循環鏈表實現長整數的存儲，每個結點含一個整形變量。（2）2345,6789；7654,3211；應輸出“1,0000,0000”。（7）1,0000,9999,9999；1；應輸出“1,0001,0000,0000”。相加過程中不要破壞兩個操作數鏈表。設計一個程序，演示用算符優先法對算術表達式求值的過程。利用“稀疏”特點進行存儲和計算可以大大節省存儲空間，提高計算效率。*實現提示：（1）首先應輸入矩陣的行數和列數，并判別給出的兩個矩陣的行、列數對于所要求作的運算是否匹配。（3）在用三元組表示稀疏矩陣時，相加或相減所得結果矩陣應該另生成，乘積矩陣也可以用二維數組存放。六、成績考核與評定學生課程設計結束后寫出總結報告，對設計的內容和效果進行總結，按照學生在設計期間的表現，指導老師對每位學生寫出評語和鑒定，系課程設計領導小組組織答辯，最后確定每位學生課程設計成績，課程設計成績分為優、良、中、及格和不及格五個等級。撰寫了高質量的總結報告。答辯較準確流利?；驘o實習報告，沒有通過答辯。說明書中除了在封面中應有題目、班級、姓名、學號和課程設計日期以外，其正文一般有如下幾個方面的內容： 三、課程設計教學基本要求四、課程設計選題根據教材《數據結構題集（C語言版）》（嚴蔚敏、吳偉民主編）選擇課程設計題目，或選擇下列與實際應用緊密結合的較綜合性的題目，要求通過設計，在數據結構的邏輯特性和物理表示、數據結構的選擇應用、算法的設計及其實現等方面加深對課程基本內容的理解和綜合運用。課程設計結束時，要求學生寫出課程設計報告，可運行的軟件系統（包括源程序）。優秀者人數一般不得超過總人數的20%