【正文】 樹函數(shù) *要求：可以建立函數(shù)輸入二叉樹，并輸出其赫夫曼樹。報m的人出列，將他的密碼作為新的m值，從他在順時針方向的下一個人開始重新從1報數(shù)，如此下去，直到所有人全部出列為止。通過指導教師命題或學生自擬題目的方式，學生要發(fā)揮自主學習的能力，充分利用時間，安排好課設的時間計劃，并在課設過程中不斷檢測自己的計劃完成情況，及時的向教師匯報。2）課程設計報告的書寫格式 ①設計題目（任選其一）②運行環(huán)境（軟、硬件環(huán)境）③算法設計的思想 ④算法的流程圖 ⑤算法設計分析⑥源代碼 ⑦運行結果分析 ⑧收獲及體會 3）實施方式可設一人一題，安排在《數(shù)據(jù)結構》課程開課學期布置題目，然后在期末4周時間內(nèi)完成。②源程序（可以是一組源程序，即詳細設計部分）源程序要按照寫程序的規(guī)則來編寫。①需求分析將題目中要求的功能進行敘述分析，并且設計解決此問題的數(shù)據(jù)存儲結構，（有些題目已經(jīng)指定了數(shù)據(jù)存儲的，按照指定的設計），設計或敘述解決此問題的算法，描述算法建議使用流程圖，進行算法分析指明關鍵語句的時間復雜度?！稊?shù)據(jù)結構課程設計》是計算機科學專業(yè)本科學生必修的實踐課程，本課程設計旨在培養(yǎng)學生的將理論應用于實踐的能力。第一篇：數(shù)據(jù)結構課程設計教學大綱計科《數(shù)據(jù)結構課程設計》教學大綱哈爾濱師范大學計算機學與信息工程學院《數(shù)據(jù)結構課程設計》一、課程設置的有關說明 本課程屬于集中實踐教學環(huán)節(jié)，是在學習了C語言、面向對象程序設計（C++）和數(shù)據(jù)結構后開設的?？倢W分1學分，在第5學期4周集中進行，主要訓練學生綜合運用C語言、C++、面向對象程序設計、數(shù)據(jù)結構知識解決實際問題，使學生能熟練的設計算法并有效的實現(xiàn)。給出實現(xiàn)功能的一組或多組測試數(shù)據(jù)，程序調試后，將按照此測試數(shù)據(jù)進行測試的結果列出來。要結構清晰，重點函數(shù)的重點變量，重點功能部分要加上清晰的程序注釋。（或在下學期開學4周時間內(nèi)完成）。最終按要求上交一份3000字左右數(shù)據(jù)結構課程設計報告（附源程序）。設計一個程序來求出出列順序。在上交資料中請寫明：存儲結構、基本算法（可以使用程序流程圖）、輸入輸出、源程序、測試數(shù)據(jù)和結果、算法的時間復雜度、另外可以提出算法的改進方法；圖的建立及輸出 *問題描述：建立圖的存儲結構（圖的類型可以是有向圖、無向圖、有向網(wǎng)、無向網(wǎng)，學生可以任選兩種類型），能夠輸入圖的頂點和邊的信息，并存儲到相應存儲結構中，而后輸出圖的鄰接矩陣拓撲排序 *問題描述：編寫函數(shù)實現(xiàn)圖的拓撲排序。（二）主要先修課程和后續(xù)課程 ：《C語言程序設計》 ：《計算機組成原理》、《操作系統(tǒng)》、《數(shù)據(jù)庫系統(tǒng)原理》二、課程設計目的及基本要求《數(shù)據(jù)結構》是一門實踐性強的課程，其中對算法設計和程序編寫的掌握尤為重要。三、課程設計內(nèi)容及安排矩陣的轉置、加減和相乘問題描述：采用十字鏈表存儲的稀疏矩陣，完成矩陣轉置、加減和相乘功能。根據(jù)哈夫曼樹的原理求n個自然數(shù)相加減后結果最?。ㄖ虚g結果、最后結果不能負）。要求：1）先生成一個網(wǎng)圖，該網(wǎng)圖既能是無向網(wǎng)圖，有能是有向網(wǎng)圖； 2）要求分別采用鄰接矩陣和鏈接表存儲來完成； 3）最后打印輸出最小生成樹；4）每一個函數(shù)要有必要的注釋，在課程設計論文中有流程圖。要求：1）先生成一個帶權的有向圖，并打印輸出； 2）用函數(shù)形式完成狄杰斯特算法；3）打印輸出最后的該頂點到其它頂點的路徑，并打印最短路徑。4）每一個函數(shù)要有必要的注釋，在課程設計論文中有流程圖。要求：1）建立一個AOE圖，并輸出結果確保創(chuàng)建成功；2）判斷AOE圖是一個拓撲有序序列，如果不是拓撲有序則報錯； 3）編寫函數(shù)求AOE圖的關鍵路徑； 4）打印輸出關鍵路徑；5）每一個函數(shù)要有必要的注釋，在課程設計論文中有流程圖。要求：1）創(chuàng)建一顆B樹，并打印輸出；2）分別編寫函數(shù)完成B的查找、插入和刪除；3）測試B樹的查找、插入和刪除，分別打印測試結果； 4）每一個函數(shù)要有必要的注釋，在課程設計論文中有流程圖。五、課程設計考核方法及成績評定程序清單：代碼應具有詳細注釋，用來說明程序的功能、結構；設計報告：報告中應包含上機時遇到的問題及解決辦法，觀察到的現(xiàn)象及其分析，對程序設計技巧的總結及分析等；程序的輸出結果及對結果的分析；實驗的心得體會，以及其它信息；提交時，須向指導教師說明：程序的使用方法，調用方法、操作步驟等；要求輸入信息的類型及格式；出錯信息的含義及程序的適用范圍等。為了學好《數(shù)據(jù)結構》，必須編寫一些在特定數(shù)據(jù)結構上的算法，通過上機調試，才能更好地掌握各種數(shù)據(jù)結構及其特點，同時提高解決計算機應用實際問題的能力。對有些題目提出算法改進方案，比較不同算法的優(yōu)缺點。程序能夠運行，要有基本的容錯功能。課程設計按照教學要求需要兩周時間完成，兩周中每天至少要上34小時的機來調試C語言設計的成成，總共至少要上機調試程序30小時。項目編號為男子1……m，女子m+1……m+w。*存儲結構：學生自己根據(jù)系統(tǒng)功能要求自己設計，但是要求運動會的相關數(shù)據(jù)要存儲在數(shù)據(jù)文件中。5）修改航班信息：當航班信息改變可以修改航班數(shù)據(jù)文件 *要求：根據(jù)以上功能說明，設計航班信息，訂票信息的存儲結構，設計程序完成功能；迷宮求解*問題描述：可以輸入一個任意大小的迷宮數(shù)據(jù)，用非遞歸的方法求出一條走出迷宮的路徑，并將路徑輸出； *要求：在上交資料中請寫明：存儲結構、基本算法（可以使用程序流程圖）、源程序、測試數(shù)據(jù)和結果、算法的時間復雜度、另外可以提出算法的改進方法；文章編輯*問題描述：輸入一頁文字，程序可以統(tǒng)計出文字、數(shù)字、空格的個數(shù)。*輸出形式：（1）分行輸出用戶輸入的各行字符；（2）分4行輸出“全部字母數(shù)”、“數(shù)字個數(shù)”、“空格個數(shù)”、“文章總字數(shù)”（3）輸出刪除某一字符串后的文章；joseph環(huán)*問題描述：編號是1，2，……,n的n個人按照順時針方向圍坐一圈，每個人只有一個密碼（正整數(shù)）。*要求：利用單向循環(huán)鏈表存儲結構模擬此過程，按照出列的順序輸出各個人的編號。輸出：這時正面向上的牌有哪些？1圖的建立及輸出*問題描述：建立圖的存儲結構（圖的類型可以是有向圖、無向圖、有向網(wǎng)、無向網(wǎng)，學生可以任選兩種類型），能夠輸入圖的頂點和邊的信息，并存儲到相應存儲結構中，而后輸出圖的鄰接矩陣。*輸出的形式：數(shù)字大小逐個遞增的數(shù)列?1圖的遍歷*問題描述：對任意給定的圖（頂點數(shù)和邊數(shù)自定），建立它的鄰接表并輸出，然后利用隊列的五種基本運算（置空隊列、進隊、出隊、取隊頭元素、判隊空）實現(xiàn)圖的廣度優(yōu)先搜索周游。任何整形變量的范圍是(2^151)。（3）9999,9999；1,0000,0000,0000；應輸出“999（4）1,0001,0001；1,0001,0001；應輸出“0”。*實現(xiàn)提示：（1）每個結點中可以存放的最大整數(shù)為32767，才能保證兩數(shù)相加不會溢出，但若這樣存放，即相當于按32768進制存放，在十進制與32768 5 進制數(shù)之間的轉換十分不方便，故可以在每個結點中僅存十進制的4位，即不超過9999的非負整數(shù)，整個鏈表表示為萬進制。兩操作數(shù)的頭指針存于指針數(shù)組中是簡化程序結構的一種方法。編制非遞歸程序，求出馬的行走路線，并按求出的行走路線，將數(shù)字1，2，?，64依次填入個8 8的方陣，輸出之。以圖中頂點表示學校各景點，存放景點名稱、代號、簡介等信息；以邊表示路徑，存放路徑長度等相關信息。*實現(xiàn)提示：一般情況下，校園的道路是雙向通行的，可設校園平面圖是一個無向網(wǎng)。2）根據(jù)用戶界面提示，用鍵盤輸入。此外，因受圖形界面限制，不能保存或載入測試文件（此功能可在Maze_text中實現(xiàn)）。設計一個程序，演示用算符優(yōu)先法對算術表達式求值的過程。（2）在輸入表達式的字符序列的同時，完成運算符和運算數(shù)（整數(shù)）的識別處理，以及相應的運算。利用“稀疏”特點進行存儲和計算可以大大節(jié)省存儲空間，提高計算效率。*實現(xiàn)提示：（1）首先應輸入矩陣的行數(shù)和列數(shù)，并判別給出的兩個矩陣的行、列數(shù)對于所要求作的運算是否匹配。（3）在用三元組表示稀疏矩陣時，相加或相減所得結果矩陣應該另生成，乘積矩陣也可以用二維數(shù)組存放。（2）作為演示系統(tǒng)，不必使用文件，全部數(shù)據(jù)可以都在內(nèi)存存放。②清除庫存：某種書已無保留價值，將它從圖書帳目中注銷。這個操作是為了調試和維護的目的而設置的。二、設計要點1．設計和調試過程要規(guī)范化。如果程序不能正常運行，寫出實現(xiàn)此算法中遇到的問題，和改進方法。盡量避免出現(xiàn)操作錯誤時出現(xiàn)死循環(huán)。為保證質量，需要每個學生將每天的上機調試程序的時間記錄下來，作為評判成績的標準之一。（3）查詢圖中任意兩個景點間的所有路徑。（3）實現(xiàn)導游圖的仿真界面。編程利用“算符優(yōu)先法”求算術表達式的值。引入變量操作數(shù)。[基本要求]英文小說存于一個文本文件中。[實現(xiàn)提示]設小說中的詞匯一律不跨行。如果讀者希望達到選作部分（1）和（2）所提出的要求，則首先應把KMP算法改寫成如下的等價形式，再將它推廣到多個模式的情形。利用單詞匹配特點另寫一個高效的統(tǒng)計程序，與KMP算法統(tǒng)計程序進行效率比較。檢驗括號是否匹配的方法可用“期待的緊迫程度”這個概念來描述。在初始和結束時，棧應該是空的。試為停車場編制按上述要求進行管理的模擬程序。每一組輸入數(shù)據(jù)包括三個數(shù)據(jù)項：汽車“到達”或“離去”信息、汽車牌照號碼及到達或離去的時刻，對每一組輸入數(shù)據(jù)進行操作后的輸出數(shù)據(jù)為：若是車輛到達，則輸出汽車在停車場內(nèi)或便道上的停車位置；若是車離去；則輸出汽車在停車場內(nèi)停留的時間和應交納的費用（在便道上停留的時間不收費）。棧中每個元素表示一輛汽車，包含兩個數(shù)據(jù)項：汽車的牌照號碼和進入停車場的時刻。[問題描述]文本編輯程序是利用計算機進行文字加工的基本軟件工具，實現(xiàn)對文本文件的插入、刪除等修改操作。任何時刻只把待編輯文件的一段放在內(nèi)存，稱為活區(qū)。格式：i將插入活區(qū)中第行之后（2）行刪除。（4）活區(qū)顯示。[測試數(shù)據(jù)]由學生依據(jù)軟件工程的測試技術自己確定。可以以標準行塊為單位為各行分配存儲，每個標準行塊含81個字符。此外，還應記住活區(qū)起始行號。x的值可以自定，例如20。（5）可令前三條命令執(zhí)行后自動調用活區(qū)顯示。試寫一個程序，演示無向圖的遍歷操作。注意測試邊界數(shù)據(jù)，如單個結點。[選作內(nèi)容]（1）借助于棧類型（自己定義和實現(xiàn)）將深度優(yōu)先遍歷用非遞歸算法實現(xiàn)。*輸入的數(shù)據(jù)形式為任何一個正整數(shù)，大小不限。*問題描述：1）輸入一個任意大小的迷宮，任設起點、終點、障礙，用棧求出一條走出迷宮的路徑，并顯示在屏幕上。4）本程序只求出一條成功的通路，但若對求解函數(shù)MazePath稍加更改即可求得全部路徑。16．算術表達式求值演示*問題描述：表達式求值是實現(xiàn)程序設計語言的基本問題之一，也是棧的應用的一個典型例子。*實現(xiàn)提示：（1）設置運算棧和運算數(shù)棧輔助分析算符優(yōu)先關系。17．稀疏矩陣運算器*問題描述：稀疏矩陣是指那些多數(shù)元素為0的矩陣。稀疏矩陣的輸入形式采用三元組表示，而運算結構的矩陣則以通常的陣列形式列出。注意研究教科書中的算法，以便提高計算效率。*基本要求：（1）每種書的登記內(nèi)容至少包括書號、書名、作者、現(xiàn)存量和總庫存量等五4。如果這種書在帳目中已有，則只將總庫存量增加。⑤顯示：以凹入表的形式顯示B樹。*要求（1）分別統(tǒng)計出其中英文字母數(shù)和空格數(shù)及整篇文章總字數(shù)；（2）統(tǒng)計某一字符串在文章中出現(xiàn)的次數(shù)，并輸出該次數(shù)；（3）刪除某一子串，并將后面的字符前移。其中序列1和序列2 中都不含字符‘a(chǎn)mp。３－１’則不是。為了學好《數(shù)據(jù)結構》，必須編寫一些在特定數(shù)據(jù)結構上的算法，通過上機調試，才能更好地掌握各種數(shù)據(jù)結構及其特點，同時提高解決計算機應用實際問題的能力。如果程序不能正常運行，寫出實現(xiàn)此算法中遇到的問題，和改進方法。盡量避免出現(xiàn)操作錯誤時出現(xiàn)死循環(huán)。提示：可利用回溯法的設計思想來解決背包問題。訂票系統(tǒng)（1）問題描述通過此系統(tǒng)可以實現(xiàn)如下功能： 1）錄入：可以錄入航班情況（數(shù)據(jù)可以存儲在一個數(shù)據(jù)文件中，數(shù)據(jù)結構、具體數(shù)據(jù)自定）2）查詢： 可以查詢某個航線的情況（如，輸入航班號，查詢起降時間，起飛抵達城市，航班票價，票價折扣，確定航班是否滿倉）；可以輸入起飛抵達城市，查詢飛機航班情況；3）訂票：（訂票情況可以存在一個數(shù)據(jù)文件中，結