《數據結構》課程設計計劃書班級：2012信計專業授課教師：馬阿曼一、課程設計目的《數據結構》課程是計算機科學與技術專業的核心專業基礎課。本課程設計的目的是將數據結構理論和實踐結合起來，鍛練學生編寫程序過程中的數據結構使用和分析、解決實際問題的能力。1、使學生進一步理解和掌握課堂上所學各種基本抽象數據類型的邏輯結構、存儲結構和操作實現算法，以及它們在程序中的使用方法。2、使學生掌握軟件設計的基本內容和設計方法，并培養學生進行規范化軟件設計的能力。3、使學生掌握使用各種計算機資料和有關參考資料，提高學生進行程序設計的基本能力。二、課程設計內容

《數據結構》課程設計包含以下主要內容：

1、查閱相關資料確定課題；

2、課題所設計的數據結構設計、算法設計；

3、編寫代碼并調試；

4、完成課程設計報告；5、進行課設答辯。三、設計地點及時間安排地點：瑞樟6-402時間：2014年6月3、4、5、6、7、8號時間安排課程設計計劃3號布置課題和要求：課題內容介紹，課程設計安排、課程設計紀律，注意事項學生選題，做好課題的前期準備工作4號需求分析：根據所選課題進行總體設計，確定數據結構，確定主要功能模塊（函數）和采用的算法等。選擇和準備原始數據確定輸入和輸出方式5號—8號編碼實現：主要功能模塊的功能實現輸入和輸出數據方式的整合調試和測試程序的功能檢驗程序是否完整，結果是否符合要求，對程序進行驗收進行課程設計答辯撰寫課程設計報告并打印，整理源代碼一并上交四、課程設計報告的書寫格式1、問題描述：描述要求編程解決的問題。2、基本要求：給出程序要達到的具體的要求。3、測試數據：設計測試數據，或具體給出測試數據。要求測試數據能全面地測試所設計程序的功能。4、算法思想：描述解決相應問題算法的設計思想。5、模塊劃分：描述所設計程序的各個模塊（即函數）功能。6、數據結構：給出所使用的基本抽象數據類型,所定義的具體問題的數據類型,以及新定義的抽象數據類型。7、算法設計分析：給出算法的設計分析和算法流程圖。8、源程序：給出所有源程序清單，要求程序有充分的注釋語句，至少要注釋每個函數參數的含義和函數返回值的含義。9、測試情況：給出程序的測試情況，并分析運行結果。10、收獲及體會：寫出此次課程設計過程中的收獲及體會。五、評分標準程序運行結果（30%）設計報告（30%）設計考勤，平時上機成績，教師不定期檢查（10%）學生根據自己設計報告對教師的提問可以熟練的解釋（10%）設計課題的難易程度（20%）六、參考設計題目課程設計題一：學生成績管理系統

設計目的：掌握線性鏈表的建立。掌握線性鏈表的基本操作。掌握查找的基本算法。設計內容：

利用線性鏈表實現學生成績管理系統，具體功能：輸入、輸出、插入、刪除、查找、追加、讀入、顯示、保存、拷貝、排序、索引、分類合計、退出，并能在屏幕上輸出操作前后的結果。

設計要求：寫出系統需求分析,并建模。編程實現,界面友好。輸出操作前后的結果。

課程設計題二：停車場管理系統

設計目的：掌握棧和隊列的建立。掌握棧和隊列的基本操作。3、深入了解棧和隊列的特性,以便在解決實際問題中靈活運用它們。4、加深對棧和隊列的理解和認識。設計內容：

設有一個可以停放n輛汽車的狹長停車場,它只有一個大門可以供車輛進出。車輛按到達停車場時間的早晚依次從停車場最里面向大門口處停放(最先到達的第一輛車放在停車場的最里面)。如果停車場已放滿n輛車,則后來的車輛只能在停車場大門外的便道上等待,一旦停車場內有車開走,則排在便道上的第一輛車就進入停車場。停車場內如有某輛車要開走,在他之后進入停車場的車都必須先退出停車場為它讓路,待其開出停車場后,這些車輛在依原來的次序進場。每輛車在離開停車場時,都應依據它在停車場內停留的時間長短交費。如果停留在便道上的車未進停車場就要離去,允許其離去,不收停車費,并且仍然保持在便道上等待的車輛的次序。編制一程序模擬該停車場的管理。

設計要求：以棧模擬停車場,以隊列模擬車場外的便道,按照從終端讀入的輸入數據序列進行模擬管理。每一組輸入數據包括三個數據項：汽車“到達”或“離去”信息、汽車牌照號碼以及到達或離去的時刻。對每一組輸入數據進行操作后的輸出信息為：若是車輛到達,則輸出汽車在停車場或便道上的停車位置；若是車輛離去,則輸出汽車在停車場內停留的時間和應交納的費用(在便道上停留的時間不收費，功能可自己添加)。

課程設計題三：約瑟夫(Joseph)環

設計目的：掌握單向循環鏈表的建立。掌握單向循環鏈表的操作。設計內容：

編號是1,2,……,n的n個人按照順時針方向圍坐一圈,每個人只有一個密碼(正整數)。一開始任選一個正整數作為報數上限值m,從第一個仍開始順時針方向自1開始順序報數,報到m時停止報數。報m的人出列,將他的密碼作為新的m值,從他在順時針方向的下一個人開始重新從1報數,如此下去,直到所有人全部出列為止。請設計一個程序求出出列順序。

設計要求：利用單向循環鏈表存儲結構模擬此過程,按照出列的順序輸出各個人的編號。測試數據：m的初值為20,n=7,7個人的密碼依次為3,1,7,2,4,7,4,首先m=6,則正確的輸出是什么？輸入數據：建立輸入函數處理輸入的數據,輸入m的初值n,輸入每個人的密碼,建立單向循環鏈表。輸出形式：建立一個輸出函數,將正確的出列順序輸出。

課程設計題四：文學研究助手的實現

設計目的：熟悉串類型的實現方法和文本匹配方法。熟悉一般文字處理軟件的設計方法。設計內容：

文學研究人員需要統計某篇英文小說中某些形容詞的出現次數和位置。試寫一個實現這一目標的文字統計系統,稱為“文學研究助手”。

設計要求：英文小說存于一個文本文件中。待統計的詞匯集合要一次輸入完畢。3、程序的輸出結果是每個詞的出現次數和出現位置所在行的行號,格式自行設計。

課程設計題五：一元稀疏多項式計算器

設計目的：掌握稀疏矩陣的相關運算。掌握廣義表的操作。設計內容：

設計一個一元稀疏多項式簡單計算器。

設計要求：

一元稀疏多項式簡單計算器的基本功能是：輸入并建立多項式；輸出多項式,輸出形式為整數序列：n,c1,e1,,c2,e2……cn,en,其中n是多項式的項數,ci和ei分別是第i項的系數和指數,序列按指數降序排列。多項式a和b相加,建立多項式a+b多項式a和b相減,建立多項式a-b

課程設計題六：哈夫曼樹及其應用

設計目的：熟悉樹的各種存儲結構及其特點。掌握建立哈夫曼樹和哈夫曼編碼的方法及帶權路徑長度的計算。設計內容：

欲發一封內容為AABBCAB……(共長100字符,其中:A、B、C、D、E、F分別有7、9、12、22、23、27個)的電報報文,實現哈夫曼編碼。

設計要求：分析系統需求。建立哈夫曼樹。進行哈夫曼編碼,并求出平均編碼長度。編程實現2、3步驟。

課程設計題七：哈夫曼編/譯碼器

設計目的：掌握建立哈夫曼樹和哈夫曼編碼的方法。掌握哈夫曼編碼的實際應用方法。設計內容：

利用哈夫曼編碼進行通信可以大大提高信道利用率,縮短信息傳輸時間,降低傳輸成本。但是,這要求在發送端通過一個編碼系統對待傳數據預先編碼,在接收端將傳來的數據進行譯碼。對于雙工信道(即可以雙向傳輸信息的信道),每端都需要一個完成的編\譯碼系統。試為這樣的信息收發站寫一個哈夫曼的編\譯碼系統。

設計要求：初始化。從終端讀入字符集大小n,以及n個字符和n個權值,建立哈夫曼樹。編碼。利用已建好的哈夫曼樹,對正文進行編碼。譯碼。對編碼好的內容進行譯碼。打印編碼。打印哈夫曼樹。

課程設計題八：圖的遍歷演示

設計目的：理解圖的基本概念,熟悉圖的各種存儲結構及其構造算法。掌握圖的遍歷方法。設計內容：

實現圖的深度優先、廣度優先遍歷算法,并輸出原圖結構及遍歷結果。

設計要求：兩種遍歷方法必須都要實現,寫出畫圖的思路。界面友好,函數功能要劃分合理。總體設計應畫一流程圖。程序要加必要的注釋。5、提供程序測試方案。

課程設計題九：交通咨詢系統設計

設計目的：熟練掌握迪杰斯特拉算法和費洛伊德算法,能夠利用它們解決最短路徑問題。能夠解決工程項目實施過程中的關鍵路徑問題。設計內容：

設計一個交通咨詢系統,能讓旅客咨詢從任一個城市定點到另一個城市定點之間的最短路徑或最低花費或最少時間等問題。對于不同的咨詢要求、可輸入城市間的路程或所需時間或所需花費。

設計要求：1、建立交通網絡網的存儲結構。2、總體設計要畫流程圖。提供程序測試方案。界面友好。

課程設計題十：航班信息的查詢與檢索

設計目的：深刻理解排序的定義和各種排序方法的特點,并能靈活的應用；掌握描述查找過程的判定樹的構造方法。設計內容：

設計民航售票處的計算機系統可以為客戶提供下列各項服務：1.

查詢航線：根據旅客提出的終點站名輸出下列信息：航班號、飛機號、星期幾飛行、最近一天航班的日期和余票額；