學期:13-14-1 班級:軟體12
一、設計目的
《資料結構》是一門實踐性較強的專業基礎課程,為了學好這門課程,必須在掌握理論知識的同時,加強上機實踐。本課程設計的目的就是要達到理論與實際應用相結合,使同學們能夠根據資料物件的特性,學會資料組織的方法,能把現實世界中的實際問題在計算機內部表示出來,並培養基本的、良好的程式設計技能。
二、設計要求
1、通過這次設計,要求在資料結構的邏輯特性和物理表示、資料結構的選擇應用、演算法的設計及其實現等方面加深對課程基本內容的理解。同時,在程式設計方法以及上機操作等基本技能和科學作風方面受到比較系統和嚴格的訓練。
2、學生必須仔細研讀《資料結構》課程設計要求,以學生自學為主、指導教師指導為輔,認真、獨立地完成課程設計的任務,有問題及時主動與指導教師溝通。
3、本次課程設計按照教學要求需要在三周時間內獨立完成,學生要發揮自主學習的能力,充分利用時間,安排好課設的時間計畫,並在課設過程中不斷檢測自己的計畫完成情況,及時地向指導教師匯報。
4、程式語言任選。
三、設計選題
選題說明:乙個*的題代表15分,兩個*的代表30分,三個*的題代表60分,四個*的題代表90分。根據實際選做題目的分值和數量以及實現程式的完善性可以適當加減分;同學們在選題時,要結合個人實際情況,保障及格,力爭多做。
1、迷宮求解(*)
任務:可以輸入乙個任意大小的迷宮資料,用非遞迴的方法求出一條走出迷宮的路徑,並將路徑輸出;
要求:在上交資料中請寫明:儲存結構、基本演算法(可以使用程式流程圖)、源程式、測試資料和結果、演算法的時間複雜度、另外可以提出演算法的改進方法;
2、 文章編輯(*)
任務:輸入一頁文字,程式可以統計出文字、數字、空格的個數。
靜態儲存一頁文章,每行最多不超過80個字元,共n行;
要求:(1)分別統計出其中英文本母數和空格數及整篇文章總字數;
(2)統計某一字串在文章**現的次數,並輸出該次數;
(3)刪除某一子串,並將後面的字元前移。
儲存結構使用線性表,分別用幾個子函式實現相應的功能;
輸入資料的形式和範圍:可以輸入大寫、小寫的英文本母、任何數字及標點符號。
輸出形式:
(1)分行輸出使用者輸入的各行字元;
(2)分4行輸出"全部字母數"、"數字個數"、"空格個數"、"文章總字數"
(3)輸出刪除某一字串後的文章;
3、 單位員工通訊錄管理系統(*)
任務:為某個單位建立乙個員工通訊錄管理系統,可以方便查詢每乙個員工的辦公室**、手機號、及電子郵箱。
要求:其功能包括通訊錄鍊錶的建立、員工通訊資訊的查詢、修改、插入與刪除、以及整個通訊錄表的輸出。
4、停車場管理(*)
[問題描述]
設停車場是乙個可以停放n輛汽車的狹長通道,且只有乙個大門可供汽車進出。汽車在停車場內按車輛到達時間的先後順序,依次有北向南排列(大門在最南端,最先到達的第一車停放在車場的最北端),若車場內已停滿n輛車,那麼後來的車只能在門外的便道上等候,一旦有車開走,則排在便道上的第一輛車即可開入;當停車場內某輛車要離開時,在它之後進入的車輛必須先退出車場為它讓路,待該輛車開出大門外,其他車輛再按原次序進入車場,每輛停放在車場的車在它離開停車場時必須按它停留的時間長短交納費用。試為停車場編制按上述要求進行管理的模擬程式。
[實現提示]
以棧模擬停車場,以佇列模擬車場外的便道。每一組輸入資料報括三個資料項:汽車「到達」或「離去」資訊、汽車牌照號碼以及到達或離去的時刻。
對每一組輸入資料進行操作後的輸出資訊為:若是車輛到達,則輸出汽車在停車場內或便道上的停車位置;若是車輛離去,則輸出汽車在停車場內停留的時間和應交納的費用(在便道上停車不收費)。棧以順序儲存結構實現,佇列以鍊錶結構實現。
5、 排序綜合(**)
任務:利用隨機函式產生n個隨機整數(20000以上),對這些數進行多種方法進行排序。
要求:(1)至少採用三種方法實現上述問題求解(提示,可採用的方法有插入排序、希爾排序、起泡排序、快速排序、選擇排序、堆排序、歸併排序)。並把排序後的結果儲存在不同的檔案中;
(2)統計每一種排序方法的效能(以上機執行程式所花費的時間為準進行對比),找出其中兩種較快的方法;
(3)統計每種演算法所用的比較次數和交換次數,最後列表顯示;
(4)如果採用4種或4種以上的方法者,可適當加分。
6、雜湊表的設計與實現(**)
任務:設計雜湊表實現**號碼查詢系統。
要求:(1) 設每個記錄有下列資料項:使用者名稱、**號碼、位址;
(2) 從鍵盤輸入各記錄,以使用者名稱(漢語拼音形式)為關鍵字建立雜湊表;
(3) 採用一定的方法解決衝突;
(4) 查詢並顯示給定**號碼的記錄;
選作內容:
(1) 系統功能的完善;
(2) 設計不同的雜湊函式,比較衝突率;
(3) 在雜湊函式確定的前提下,嘗試各種不同型別處理衝突的方法,考察平均查詢長度的變化。
7、線索二叉樹(**)
任務:1.建立中序線索二叉樹,並且中序遍歷;
2. 求中序線索二叉樹上已知結點中序的前驅和後繼;
8、 運動會分數統計(**)
任務:參加運動會有n個學校,學校編號為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)可以按學校編號查詢學校某個專案的情況;可以按專案編號查詢取得前三或前五名的學校。
規定:輸入資料形式和範圍:20以內的整數(如果做得更好可以輸入學校的名稱,運動專案的名稱)
輸出形式:有中文提示,各學校分數為整形
介面要求:有合理的提示,每個功能可以設立選單,根據提示,可以完成相關的功能要求。
儲存結構:學生自己根據系統功能要求自己設計,但是要求運動會的相關資料要儲存在資料檔案中。(資料檔案的資料讀寫方法等相關內容在c語言程式設計的書上,請自學解決)請在最後的上交資料中指明你用到的儲存結構;
相關資料結構(參考):
專案名次及分值 :用二位陣列score[m+w][5];
單項獲獎情況登記表(專案編號,獲獎名次、獲獎學校,得分(自動得分))
學校獲獎名次表(學校編號,團體總分,名次)
測試資料:要求使用1、全部合法資料;2、整體非法資料;3、區域性非法資料。進行程式測試,以保證程式的穩定。測試資料及測試結果請在上交的資料中寫明;
9、宿舍管理查詢軟體(**)
任務:為宿舍管理人員編寫乙個宿舍管理查詢軟體, 程式設計要求:
(1)採用互動工作方式
(2)可以增加、刪除、修改資訊
(3)建立資料檔案 ,資料檔案按關鍵字(姓名、學號、房號)進行排序(選擇、快速排序、堆排序等任選一種)
(4) 查詢 : a.按姓名查詢 ;b.按學號查詢 ;c按房號查詢
(5) 列印任一查詢結果(可以連續操作)
要求:上述查詢功能中,學號、房號用折半查詢,姓名查詢用雜湊查詢。
10、最小生成樹問題(***)
【問題描述】
若要在n個城市之間建設通訊網路,只需要假設n-1條線路即可。如何以最低的經濟代價建設這個通訊網,是乙個網的最小生成樹問題。
【系統要求】
1. 利用克魯斯卡爾演算法求網的最小生成樹。
2. 利用普里姆演算法求網的最小生成樹。
3. 要求輸出各條邊及它們的權值。
【測試資料】
由學生任意指定,但報告上要求寫出多批資料測試結果。
【實現提示】
通訊線路一旦建成,必然是雙向的。因此,構造最小生成樹的網一定是無向網。設圖的頂點數不超過30個,並為簡單起見,網中邊的權值設成小於100的整數,可利用c語言提供的隨機函式產生。
圖的儲存結構的選取應和所作操作相適應。為了便於選擇權值最小的邊,此題的儲存結構既不選用鄰接矩陣的陣列表示法,也不選用鄰接表,而是以儲存邊(帶權)的陣列表示圖。
【選作內容】
利用堆排序實現選擇權值最小的邊。
11、校園導遊諮詢(***)
任務:設計乙個校園導遊程式,為來訪的客人提供各種資訊查詢服務。
要求:(1)設計學校的校園平面圖,所含景點不少於10個,以圖中頂點表示校內各景點,存放景點名稱、代號、簡介等資訊;以邊表示路徑,存放路徑長度等相關資訊。
(2)為來訪客人提供圖中任意景點相關資訊的查詢。
(3)為來訪客人提供景點的問路查詢,即已知乙個景點,查詢到某景點之間的一條最短路徑及長度。
12、單迴圈賽成績給定(***)
【問題描述】
在有n個選手p1,p2,p3,…,pn參加的單迴圈賽中,每對選手之間非勝即負。要求給出乙個選手序列p1』,p2』,p3』,…,pn』,使其滿足pi』勝pi+1』(i=1,2,…,n-1)。
12、售票處的服務系統(***)
【問題描述】
航空客運訂票的業務活動包括:查詢航線、客票預訂和辦理退票等。試設計乙個航空客運訂票系統,以使上述業務可以借助計算機來完成。
【系統要求】
設民航售票處的計算機系統可以為客戶提供下列各項服務:
1. 查詢航線:根據旅客提出的終點站名輸出下列資訊:航班號、飛機號、星期幾飛行,最近一天航班的日期和餘票額;
2. 承辦訂票業務:根據客戶提出的要求(日期、航班號、訂票數額)查詢該航班票額情況,若尚有餘額,則為客戶辦理訂票手續,輸出座位號;若已滿員或余票額少於訂票額,則需要重新詢問客戶要求。若需要,可預約登記排隊等候。
3.承辦退票業務:根據客戶提供的情況(日期、航班、退票數額),為客戶辦理退票手續,然後查詢該航班是否有人預約登記,首先詢問排在第一的客戶,若所退票額能滿足他的要求,則為他辦理訂票手續,否則依次詢問其他排隊預約的客戶。
【測試資料】
由學生任意指定,但報告上要求寫出多批資料測試結果。
【實現提示】
每條航線應包含的資訊有:終點站名、航班號、飛機號、飛行日期(星期幾)、乘員定額、餘票額、已訂票的客戶名單(包括姓名、訂票額、座位號)和預約登記的客戶名單(包括日期、姓名、所需票額)。這最後兩項顯然是乙個線性表和乙個佇列。
為查詢方便、已訂票客戶的線性表應按客戶姓名有序,並且,為插入和刪除方便,應以鍊錶作儲存結構。由於預約人數無法預料,佇列也應以鍊錶作儲存結構。整個系統需彙總各條航線的情況登入在一張線性表上,由於航線基本不變,可採用順序儲存結構,並按航班有序或按終點站名有序。
每條航線是這張表上的乙個記錄,包含上述八個域,其中乘員名單域為指向乘員名單鍊錶的頭指標,預約登記客戶名單域為分別指向隊頭和隊尾的指標。
資料結構課程設計任務書
一 設計的目的 資料結構與演算法課程設計是在學完資料結構與演算法課程之後的實踐教學環節。該實踐教學是軟體設計的綜合訓練,包括問題分析 總體結構設計 使用者介面設計 程式設計基本技能和技巧。要求學生在設計中逐步提高程式設計能力,培養科學的軟體工作方法。學生通過資料結構課程設計在下述各方面得到鍛鍊 1 ...
資料結構課程設計任務書
專業年級班 一 設計題目 學生成績管理系統的設計 二 主要內容 外存用檔案的形式,記憶體採用不同的資料結構完成對學生 班級 課程 成績進行管理。三 具體要求 在記憶體中完成對學生資訊按姓名形成乙個排序二叉樹並進行維護在記憶體中對班級 課程表形成乙個鍊錶,並進行維護在記憶體中用陣列的形式完成成績表的維...
《資料結構》課程設計任務書
學生姓名專業班級 軟體080 班 指導教師 夏紅霞工作單位 電腦科學與技術學院 題目 學生成績管理程式的設計與實現 課程設計要求 1 熟練掌握基本的資料結構 2 熟練掌握各種演算法 3 運用高階語言編寫質量高 風格好的應用程式。課程設計任務 1 系統應具備的功能 1 對學生的姓名 各科成績進行輸入和...