計算機學院 13級 數據結構課程設 3周

《計算機學院 13級 數據結構課程設 3周》由會員分享，可在線閱讀，更多相關《計算機學院 13級 數據結構課程設 3周（12頁珍藏版）》請在裝配圖網上搜索。

1、數據結構課程設計任務書 《數據結構》課程設計任務書 學期：14-15-1 班級：計科、網絡、軟件13級 一、設計目的 《數據結構》是一門實踐性較強的軟件基礎課程，為了學好這門課程，必須在掌握理論知識的同時，加強上機實踐。本課程設計的目的就是要達到理論與實際應用相結合，使同學們能夠根據數據對象的特性，學會數據組織的方法，能把現實世界中的實際問題在計算機內部表示出來，并培養(yǎng)基本的、良好的程序設計技能。 二、設計要求 1、通過這次設計，要求在數據結構的邏輯特性和物理表示、數據結構的選擇應用、算法的設計及其實現等方面加深對課程基本內容的理解。同時，在程序設計方法以及上機操作等基本技能

2、和科學作風方面受到比較系統和嚴格的訓練。 2、學生必須仔細研讀《數據結構》課程設計(實習)要求，以學生自學為主、指導教師指導為輔，認真、獨立地完成課程設計的任務，有問題及時主動與指導教師溝通。 3、本次課程設計按照教學要求需要在三周時間內獨立完成，學生要發(fā)揮自主學習的能力，充分利用時間，安排好課設的時間計劃，并在課設過程中不斷檢測自己的計劃完成情況，及時地向指導教師匯報。 4、編程語言任選。 三、設計選題 選題說明：本次課設共提供若干個不同難易程度的題目，其中前面5個為必做題，滿分80分（系統功能完善、人機交互界面簡單、直觀、便捷，否則逐項減分）；后面為選做題，共20分，題目難度層度

3、不等，題目*越多難度越大，根據實際選做題目的難度和數量以及實現程序的完善性可以適當加減分；同學們在選題時，要結合個人實際情況，確保及格，力爭多做。 1、 單位員工通訊錄管理系統（線性表的應用） [問題描述] 為某個單位建立一個員工通訊錄管理系統，可以方便查詢每一個員工的辦公室電話、手機號、及電子郵箱。其功能包括通訊錄鏈表的建立、員工通訊信息的查詢、修改、插入與刪除、以及整個通訊錄表的輸出。 [實現提示] 可以采用單鏈表的存儲結構，如可定義如下的存儲結構： typedef struct { /*員工通訊信息的結構類型定義*/ char num[5]; /*

4、員工編號*/ char name[10]; /*員工姓名*/ char phone[15]; /*辦公室電話號碼*/ char call[15]; /*手機號碼*/ char mail[25]; /*郵箱*/ }DataType; /*通訊錄單鏈表的結點類型*/ typedef struct node { DataType data; /*結點的數據域*/ struct node *next; /*結點的指針域*/ }ListNode,*LinkList; 2、停車場管理（棧和隊列的應用） [問題描述]

5、 設停車場是一個可以停放n輛汽車的狹長通道，且只有一個大門可供汽車進出。汽車在停車場內按車輛到達時間的先后順序，依次有北向南排列（大門在最南端，最先到達的第一車停放在車場的最北端），若車場內已停滿n輛車，那么后來的車只能在門外的便道上等候，一旦有車開走，則排在便道上的第一輛車即可開入；當停車場內某輛車要離開時，在它之后進入的車輛必須先退出車場為它讓路，待該輛車開出大門外，其他車輛再按原次序進入車場，每輛停放在車場的車在它離開停車場時必須按它停留的時間長短交納費用。試為停車場編制按上述要求進行管理的模擬程序。 [實現提示] 以棧模擬停車場，以隊列模擬車場外的便道。每一組輸入數據包括三個數據項

6、：汽車“到達”或“離去”信息、汽車牌照號碼以及到達或離去的時刻。對每一組輸入數據進行操作后的輸出信息為：若是車輛到達，則輸出汽車在停車場內或便道上的停車位置；若是車輛離去，則輸出汽車在停車場內停留的時間和應交納的費用（在便道上停車不收費）。棧以順序存儲結構實現，隊列以鏈表結構實現。 3、哈夫曼編碼/譯碼系統（樹應用） [問題描述] 利用哈夫曼編碼進行通信，可以壓縮通信的數據量，提高傳輸效率，縮短信息的傳輸時間，還有一定的保密性?，F在要求編寫一程序模擬傳輸過程，實現在發(fā)送前將要發(fā)送的字符信息進行編碼，然后進行發(fā)送，接收后將傳來的數據進行譯碼，即將信息還原成發(fā)送前的字符信息。 [實現提示]

7、 在本例中設置發(fā)送者和接受者兩個功能， 發(fā)送者的功能包括： ①輸入待傳送的字符信息； ②統計字符信息中出現的字符種類數和各字符出現的次數（頻率）； ②根據字符的種類數和各自出現的次數建立哈夫曼樹； ③利用以上哈夫曼樹求出各字符的哈夫曼編碼； ④將字符信息轉換成對應的編碼信息進行傳送。 接受者的功能包括： ①接收發(fā)送者傳送來的編碼信息； ②利用上述哈夫曼樹對編碼信息進行翻譯，即將編碼信息還原成發(fā)送前的字符信息。 從以上分析可發(fā)現，在本例中的主要算法有三個： （1）哈夫曼樹的建立； （2）哈夫曼編碼的生成； （3）對編碼信息的翻譯。 4、校園導游咨詢（圖的應用） [

8、問題描述] 設計一個校園導游程序，為來訪的客人提供各種信息查詢服務。 （1）設計學校的校園平面圖，所含景點不少于10個，以圖中頂點表示校內各景點，存放景點名稱、代號、簡介等信息；以邊表示路徑，存放路徑長度等相關信息； （2）提供基本信息的修改功能； （3）為來訪客人提供圖中任意景點相關信息的查詢； （4）為來訪客人提供景點的問路查詢，即已知一個景點，查詢到某景點之間的一條最短路徑及長度。 5、藥店的藥品銷售統計系統（排序應用） [問題描述] 設計一系統，實現醫(yī)藥公司定期對銷售各藥品的記錄進行統計，可按藥品的編號、單價、銷售量或銷售額做出排名。 [實現提示] 在本設計中，首先

9、從數據文件中讀出各藥品的信息記錄，存儲在順序表中。各藥品的信息包括：藥品編號、藥名、藥品單價、銷出數量、銷售額。藥品編號共4位，采用字母和數字混合編號，如：A125，前一位為大寫字母，后三位為數字，按藥品編號進行排序時，可采用基數排序法。對各藥品的單價、銷售量或銷售額進行排序時，可采用多種排序方法，如直接插入排序、冒泡排序、快速排序，直接選擇排序等方法。在本設計中，對單價的排序采用冒泡排序法，對銷售量的排序采用快速排序法，對銷售額的排序采用堆排序法。 藥品信息的元素類型定義： typedef struct node { char num[4]; /*藥品編號*/ char nam

10、e[10]; /*藥品名稱*/ float price; /*藥品單價*/ int count; /*銷售數量*/ float sale; /*本藥品銷售額*/ }DataType; 存儲藥品信息的順序表的定義： typedef struct { DataType r[MaxSize]; int length; }SequenList; 6、散列表的設計與實現（*） 任務：設計散列表實現電話號碼查找系統。 要求： （1) 設每個記錄有下列數據項：用戶名、電話號碼、地址； （2) 從鍵盤輸入各記錄，以用戶名（漢語拼音形式）為關鍵

11、字建立散列表； （3) 采用線性探測再散列法解決沖突； （4) 查找并顯示給定電話號碼的記錄； (5) 通訊錄信息文件保存； (6) 要求人機界面友好，使用圖形化界面； 選作內容： （1) 系統功能的完善； （2) 設計不同的散列函數，比較沖突率； （3) 在散列函數確定的前提下，嘗試各種不同類型處理沖突的方法，考察平均查找長度的變化。 7、一元稀疏多項式的計算（*） 任務：能夠按照指數降序排列建立并輸出多項式；能夠完成兩個多項式的相加、相減，并將結果輸出； 　　要求：以鏈式存儲結構實現多項式。 8、迷宮求解（*） 　　任務：以一個m*n的長方陣表示迷宮，

12、0和1分別表示迷宮中的通路和障礙。設計一個程序，對任意設定的迷宮，求出一條從入口到出口的通路，或得出沒有 通路的結論。 要求：首先實現一個棧類型，然后編寫一個求解迷宮的非遞歸程序。求得的通路以三元組(i,j,d)的形式輸出，其中(i,j)指示迷宮中的一個坐標，d表示走到下一坐標的方向。 9、排序綜合（**） 利用隨機函數產生N個隨機整數（20000以上），對這些數進行多種方法進行排序。 要求： （1）至少采用三種方法（希爾排序、快速排序、堆排序）實現上述問題求解； （2）統計每一種排序方法的性能（以上機運行程序所花費的時間為準進行對比），找出其中兩種較快的方法； （

13、3）統計每種算法所用的比較次數和交換次數，最后列表顯示； （4）如果采用4種或4種以上的方法者，可適當加分。 10、教學計劃編制問題（**） [問題描述] 大學的每個專業(yè)都要制定教學計劃。假設任何專業(yè)都有固定的學習年限，每學年含兩學期，每學期的時間長度和學分上限值均相等。每個專業(yè)開設的課程都是確定的，而且課程在開設時間的安排必須滿足先修關系。每門課程有哪些先修課程是確定的，可以有任意多門，也可以沒有。每門課恰好占一個學期。試在這樣的前提下設計一個教學計劃編制程序。 [實現提示] 1、 輸入參數應包括：學期總數，一學期的學分上限，每門課的課程號（可以是固定占3位的字母數字串）、學

14、分和直接先修課的課程號。 2、 應允許用戶指定下列兩種編排策略之一：一是使學生在各學期中的學習負擔盡量均勻；二是使課程盡可能地集中在前幾個學期中。 3、 若根據給定的條件問題無解，則報告適當的信息；否則將教學計劃輸出到用戶指定的文件中。計劃的表格格式可以自己設計。 4、 可設學期總數不超過12，課程總數不超過100。如果輸入的先修課程號不在該專業(yè)開設的課程序列中，則作為錯誤處理。 11、二叉排序樹的基本操作（**） 任務： 編寫算法實現對依次輸入的關鍵字序列建立二叉排序樹，并能實現二叉排序樹的查找、插入和刪除運算。 12、 運動會分數統計（**） 任務：參加運動會有n個學校，

15、學校編號為1……n。比賽分成m個男子項目，和w個女子項目。項目編號為男子1……m，女子m+1……m+w。不同的項目取前五名或前三名積分；取前五名的積分分別為：7、5、3、2、1，前三名的積分分別為：5、3、2；哪些項目取前五名或前三名由學生自己設定。（m<=20,n<=20） 功能要求： (1)可以輸入各個項目的前三名或前五名的成績； (2)能統計各學?？偡?， (3)可以按學校編號、男女團體總分排序輸出； (4)可以按學校編號查詢學校某個項目的情況；可以按項目編號查詢取得前三或前五名的學校。 規(guī)定：輸入數據形式和范圍：20以內的整數（如果做得更好可以輸入學校的名稱，運動項目的名

16、稱） 輸出形式：有中文提示，各學校分數為整形 界面要求：有合理的提示，每個功能可以設立菜單，根據提示，可以完成相關的功能要求。 存儲結構：學生自己根據系統功能要求自己設計，但是要求運動會的相關數據要存儲在數據文件中。（數據文件的數據讀寫方法等相關內容在c語言程序設計的書上，請自學解決）請在最后的上交資料中指明你用到的存儲結構； 相關數據結構（參考）： 項目名次及分值 ：用二位數組Score[m+w][5]; 單項獲獎情況登記表（項目編號，獲獎名次、獲獎學校，得分（自動得分）） 學校獲獎名次表（學校編號，團體總分，名次） 測試數據：要求使用1、全部合法數據；2、整體非法數據；3、

17、局部非法數據。進行程序測試，以保證程序的穩(wěn)定。測試數據及測試結果請在上交的資料中寫明； 13、宿舍管理查詢軟件（**） 任務：為宿舍管理人員編寫一個宿舍管理查詢軟件, 程序設計要求： （1）采用交互工作方式 （2）可以增加、刪除、修改信息 （3）建立數據文件 ，數據文件按關鍵字（姓名、學號、房號）進行排序(選擇、快速排序、堆排序等任選一種) (4) 查詢 : a.按姓名查詢 ;b.按學號查詢 ;c按房號查詢 (5) 打印任一查詢結果（可以連續(xù)操作） 14、最小生成樹問題（**） 【問題描述】 若要在n個城市之間建設通信網絡，只需要假設n-1條線路即可。如何以最低的

18、經濟代價建設這個通信網，是一個網的最小生成樹問題。 【系統要求】 1． 利用克魯斯卡爾算法求網的最小生成樹。 2． 利用普里姆算法求網的最小生成樹。 3． 要求輸出各條邊及它們的權值。 【測試數據】 由學生任意指定，但報告上要求寫出多批數據測試結果。 【實現提示】 通信線路一旦建成，必然是雙向的。因此，構造最小生成樹的網一定是無向網。設圖的頂點數不超過30個，并為簡單起見，網中邊的權值設成小于100的整數，可利用C語言提供的隨機函數產生。 圖的存儲結構的選取應和所作操作相適應。為了便于選擇權值最小的邊，此題的存儲結構既不選用鄰接矩陣的數組表示法，也不選用鄰接表，而是以存儲邊（

19、帶權）的數組表示圖。 【選作內容】 利用堆排序實現選擇權值最小的邊。 15、平衡二叉排序樹的實現（**） 【系統要求】 （1）用二叉鏈表作存儲結構，以回車('\n')為輸入結束標志,輸入數列L，生成一棵平衡的二叉排序樹T，并以直觀的方式顯示在終端上； （2）對二叉排序樹T作中序遍歷，輸出結果； （3）輸入元素x,查找二叉排序樹T,若存在含x的結點,則刪除該結點,并作中序遍歷(執(zhí)行操作2)；否則輸出信息“無x”，并將x插入該二叉排序樹中。 注意：插入、刪除應保證二叉排序樹的平衡性。 16、商店存貨管理系統（**） 功能：建立一商店存貨管理系統，要求每次出貨時取進

20、貨時間最早且最接近保質期中止時間的貨物。 分步實施： 1.初步完成總體設計，搭好框架，確定人機對話的界面，確定函數個數； 2.完成最低要求：建立一個文件，包括5個種類的貨物情況，能對商品信息進行擴充（追加），修改和刪除以及簡單的排序； 3.進一步要求：擴充商品數量，以及完成系統查詢功能。有興趣的同學可以自己擴充系統功能。 17、售票處的服務系統（***） 【問題描述】 航空客運訂票的業(yè)務活動包括：查詢航線、客票預訂和辦理退票等。試設計一個航空客運訂票系統，以使上述業(yè)務可以借助計算機來完成。 【系統要求】 設民航售票處的計算機系統可以為客戶提供下列各項服務： 1． 查詢航線：

21、根據旅客提出的終點站名輸出下列信息：航班號、飛機號、星期幾飛行，最近一天航班的日期和余票額； 2． 承辦訂票業(yè)務：根據客戶提出的要求（日期、航班號、訂票數額）查詢該航班票額情況，若尚有余額，則為客戶辦理訂票手續(xù)，輸出座位號；若已滿員或余票額少于訂票額，則需要重新詢問客戶要求。若需要，可預約登記排隊等候。 3．承辦退票業(yè)務：根據客戶提供的情況（日期、航班、退票數額），為客戶辦理退票手續(xù)，然后查詢該航班是否有人預約登記，首先詢問排在第一的客戶，若所退票額能滿足他的要求，則為他辦理訂票手續(xù)，否則依次詢問其他排隊預約的客戶。 【測試數據】 由學生任意指定，但報告上要求寫出多批數據測試結果。

22、【實現提示】 每條航線應包含的信息有：終點站名、航班號、飛機號、飛行日期（星期幾）、乘員定額、余票額、已訂票的客戶名單（包括姓名、訂票額、座位號）和預約登記的客戶名單（包括日期、姓名、所需票額）。這最后兩項顯然是一個線性表和一個隊列。為查找方便、已訂票客戶的線性表應按客戶姓名有序，并且，為插入和刪除方便，應以鏈表作存儲結構。由于預約人數無法預料，隊列也應以鏈表作存儲結構。整個系統需匯總各條航線的情況登錄在一張線性表上，由于航線基本不變，可采用順序存儲結構，并按航班有序或按終點站名有序。每條航線是這張表上的一個記錄，包含上述八個域，其中乘員名單域為指向乘員名單鏈表的頭指針，預約登記客戶名單域為

23、分別指向隊頭和隊尾的指針。 【選做內容】 當客戶訂票要求不能滿足時，系統可向客戶提供到達同一目的地的其它航線情況。 大家還可以充分發(fā)揮自己的想象力，增加你的系統的功能和其它服務項目。 18、 中國道路交通網絡信息查詢系統（****） 【問題描述】 出于不同的目的的旅客對交通工具有不同的要求。例如，因公出差的旅客希望在旅途中的時間盡可能短，出門旅游的游客則期望旅費盡可能省，而老年旅客則要求中轉次數最少。編制一個全國城市間的交通咨詢程序，為旅客提供兩種或三種最優(yōu)決策的交通咨詢。 【基本要求】 （1） 提供對城市信息進行編輯（如：添加或刪除）的功能。 （2） 城市之間有兩種交通

24、工具：火車和飛機。提供對列車時刻表和飛機航班進行編輯（增設或刪除）的功能。 （3） 提供兩種最優(yōu)決策：最快到達或最省錢到達。全程只考慮一種交通工具； （4） 旅途中耗費的總時間應該包括中轉站的等候時間； （5） 咨詢以用戶和計算機的對話方式進行。由用戶輸入起始站、終點站、最優(yōu)決策原則和交通工具，輸出信息：最快需要多長時間才能到達或者最少需要多少旅費才能到達，并詳細說明依次于何時乘坐哪一趟列車或哪一次班機到何地。 【測試數據】 參考《數據結構》清華版7.6節(jié)圖7.33的全國交通圖,自行設計列車時刻表和飛機航班。 【實現提示】 (1)對時刻表和飛機航班進行編輯,應提供文件輸入和鍵盤輸

25、入兩種形式。飛機航班信息包括:起始站的出發(fā)時間,終點站的到達時間和票價;列車時刻表則需 根據交通圖給出各個路段的詳細信息,如:對從北京到上海的火車,給出北京至天 津,天津至徐州及徐州至上海各段的出發(fā)時間,到達時間及票價等信息。 (2)以鄰接表作交通圖的存儲結構,表示邊的結構內除含有鄰接點的信息外,還包括交通工具,路途中耗費的時間和花費以及出發(fā)和到達時間等多種屬性。 【選做內容】 增加旅途中中轉次數最少的最優(yōu)決策。 19. 英語單詞學習助手 【問題描述】 掌握線性表、串、查找表等數據結構的物理存儲結構與基本算法，通過解決較復雜的實際問題，提高學生對數據結構知識綜合運用的技能與實踐能力

26、。設計內容：以大學英語相關英語文章為語料素材，設計有效的數據結構及其存儲結構表示英語單詞表，并建立相應的倒排索引，幫助英語學習者在遇到生詞時能方便找到生詞的相應例句，熟悉其應用語境與地道的用法；設計有效的算法對語料進行清理與分句處理，實現基于索引的快速例句搜索程序。 【基本要求】 （1）輸入某一個（或若干個）英語單詞，要求返回相應的英語例句。 （2）根據單詞與語句建立倒排索引，并且索引要求物化到外存，以文件形式保存，每次啟動程序時不必重新建立索引，只需將索引文件導入內存。 （3）采用圖形界面，便于輸入單詞，例句展現直觀，界面布局合理。 【設計提示】 按三步進行：（1）準備英語

27、語料。尋找英語文章，可下載英語新聞，托福、GRE文章，或大學英語課文等。（2）處理語料。對語料進行清理、分句、索引、生成字典。需要進行取詞干的操作，分句可以直接根據標點符號處理。（3）根據索引進行查詢。支持一個或多個查詢，基于對詞干的處理，當查go、going等時也能夠有返回。由于查詢的結果是語句，如果直接按照詞與文章的關系建立索引，這樣需要從文章中找句子，太多的串匹配操作可能導致查詢較慢，所以要設計好索引的粒度。 p 大學校區(qū)（*） 【題目描述】 當前，中原工學院共有四個校區(qū)：北校區(qū)（North）、南校區(qū)（South）、西校區(qū)（West）和東校區(qū)（信商新區(qū)）（East），每一個校

28、區(qū)都有若干個建筑物，如公園、廣場、科研院所、實驗中心、禮堂等，每個建筑物之間都有一定的距離，因此，在平時的教學和生活中，教師和學生都會經常面臨這樣的問題：在同一個校區(qū)或不同校區(qū)之間，從一個地點到另一個地點往來的需要。現在，他們需要找到從出發(fā)點S到目的地T的一條最短路徑，以便節(jié)省時間，你能幫助他們嗎？假設任兩個建筑物之間至多存在一條直接相連的道路，并且都有具體的長度。 【輸入】 輸入的第一行是一個正整數C，表示下面測試案例數目。在每一種測試例中，第一行的正整數 N(0

29、≤100），第N+1行表示教師或學生的出發(fā)地S與目的地T,你必須幫找出他們從出發(fā)地S到目的地T之間的最短路徑。每個校區(qū)分別使用North、South、West和East，每一個建筑物名稱用長度不超出100個小寫字符（a-z）串表示。 【輸出】 輸出應包括C行，每行對應一個測試例，輸出從起點到目的地的最短距離。如果兩地點間無路徑則輸出-1。系統沒有多余的內存空間可利用。 【輸入樣例】 1 2 South.litang South.lab 2 South.lab West.guangchang 100 South.lab South.litang 【輸出樣例

30、】 2 四、學生自選課題 學生原則上可以結合個人愛好自選課題，要求自選課題必須覆蓋數據結構的主要內容，有一定的深度與難度，有一定的算法復雜性，能明確體現數據抽象與組織、算法設計與性能分析以及編碼實現等過程。學生自選課題需提前報課程設計指導教師批準方可生效。 五、指導教師 苗鳳君、高艷霞、吳志剛、田繼鵬 六、時間安排 第17-19 每天上午8:30-12:00下午13:00-16：30 七、完成課程設計報告 課程設計報告書封面用學校的統一封面。 課程設計報告的內容：設計題目、需求分析、算法設計（包含算法思想、算法設計分析、流程圖等）、調試分析、測試結果、課設總結

31、（收獲及體會）、附錄（源代碼）。 八、成績考核 根據完成任務的情況(必須進行系統驗收 + 答辯)、課程設計報告書的質量和課程設計過程中的工作態(tài)度等按照50%、30%、20%加權綜合打分。上機程序檢查未通過者、無設計報告者以及嚴重抄襲他人設計者，成績?yōu)椴患案瘛? 缺席次數 最終成績 2次 中等及以下 3次及以上 不及格 其它情況根據界面設計、實現方法、功能效果、設計報告來評定。主要從以下幾個方面考察： 項目 得分 備注 程序運行情況 25分 程序的結構合理與否 15分 算法說明的清晰程度 20分 總結的深刻程度 10分 獨立

32、完成情況 20分 加分因素 10分 九、上交報告及相關源代碼 上交課程設計報告和相關光盤。其中設計報告要以打印文稿的形式上交。光盤內容包括程序源碼和課程設計報告的電子文檔。整個班級的設計均刻在一張光盤上。（上交時每人交一份，文件夾的取名規(guī)則為：“班級_學號_姓名”，如“計科131_學號_張三”。該文件夾下至少包括：“源代碼”、“課程設計報告”。由以班為單位收集刻盤按規(guī)定時間統一上交）。 數據結構課程組 2014-12-10 12 /7