數(shù)據(jù)結構課程設計實施方案任務書(軟件)

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

2、 地訓 練.p1EanqFDPw2、學生必須仔細研讀數(shù)據(jù)結構課程設計要求 ，以學生自學為主、指導教 師指導為輔，認真、獨立地完成課程設計地任務，有問題及時主動與指導教師溝 通.DXDiTa9E3d3、 本次課程設計按照教學要求需要在三周時間內獨立完成，學生要發(fā)揮自主 學習地能力，充分利用時間，安排好課設地時間計劃，并在課設過程中不斷檢測自 己地計劃完成情況，及時地向指導教師匯報.RTCrpUDGiT4、編程語言任選.三、設計選題選題說明：一個*地題代表15分,兩個*地代表30分,三個*地題 代表60分，四個*地題代表90分.根據(jù)實際選做題目地分值和數(shù)量以 及實現(xiàn)程序地完善性可以適當加減分；同學

3、們在選題時,要結合個人實際情況，保障及格,力爭多做.5PCzVD7HxA1、迷宮求解（*）任務：可以輸入一個任意大小地迷宮數(shù)據(jù)，用非遞歸地方法求出一條走出迷宮地 路徑,并將路徑輸出；要求：在上交資料中請寫明：存儲結構、基本算法（可以使用程序流程圖）、 源程序、測試數(shù)據(jù)和結果、算法地時間復雜度、另外可以提出算法地改進方法；jLBHrnAlLg2、文章編輯（* ）任務：輸入一頁文字，程序可以統(tǒng)計出文字、數(shù)字、空格地個數(shù) 靜態(tài)存儲一頁文章，每行最多不超過80個字符,共N行；要求：（1 ）分別統(tǒng)計出其中英文字母數(shù)和空格數(shù)及整篇文章總字數(shù)；（2）統(tǒng)計某一字符串在文章中出現(xiàn)地次數(shù)，并輸出該次數(shù)；（3）刪除

4、某一子串，并將后面地字符前移 存儲結構使用線性表，分別用幾個子函數(shù)實現(xiàn)相應地功能；輸入數(shù)據(jù)地形式和范圍：可以輸入大寫、小寫地英文字母、任何數(shù)字及標點符 號.XHAQX74J0X輸出形式：（1）分行輸出用戶輸入地各行字符；（2）分4行輸出"全部字母數(shù)"、"數(shù)字個數(shù)"、"空格個數(shù)"、"文章總字數(shù)"（3）輸出刪除某一字符串后地文章；3、單位員工通訊錄管理系統(tǒng)（*）任務：為某個單位建立一個員工通訊錄管理系統(tǒng)，可以方便查詢每一個員工 地辦公室電話、手機號、及電子郵箱.要求：其功能包括通訊錄鏈表地建立、員工通訊信息地查詢、修改

5、、插入與 刪除、以及整個通訊錄表地輸出.4、停車場管理（*）問題描述設停車場是一個可以停放n輛汽車地狹長通道，且只有一個大門可供汽車進 出.汽車在停車場內按車輛到達時間地先后順序，依次有北向南排列（大門在最南 端,最先到達地第一車停放在車場地最北端），若車場內已停滿n輛車,那么后來 地車只能在門外地便道上等候，一旦有車開走，則排在便道上地第一輛車即可開 入；當停車場內某輛車要離開時，在它之后進入地車輛必須先退出車場為它讓路， 待該輛車開出大門外，其他車輛再按原次序進入車場，每輛停放在車場地車在它 離開停車場時必須按它停留地時間長短交納費用.試為停車場編制按上述要求進 行管理地模擬程序.LDAY

6、tRyKfE實現(xiàn)提示以棧模擬停車場，以隊列模擬車場外地便道每一組輸入數(shù)據(jù)包括三個數(shù)據(jù) 項：汽車“到達”或“離去”信息、汽車牌照號碼以及到達或離去地時刻.對每一組輸入數(shù)據(jù)進行操作后地輸出信息為：若是車輛到達，則輸出汽車在停車場內 或便道上地停車位置；若是車輛離去，則輸出汽車在停車場內停留地時間和應交 納地費用（在便道上停車不收費）棧以順序存儲結構實現(xiàn)，隊列以鏈表結構實 現(xiàn).Zzz6ZB2Ltk5、排序綜合（*）任務：利用隨機函數(shù)產生N個隨機整數(shù)（20000以上），對這些數(shù)進行多種方法進 行排序要求：（1）至少采用三種方法實現(xiàn)上述問題求解（提示,可采用地方法有插入排序、希爾排序、起泡排序、快速排序

7、、選擇排序、堆排序、歸并排序）并把排序后地結果保存在不同地文件中；dvzfvkwMIl（2）統(tǒng)計每一種排序方法地性能（以上機運行程序所花費地時間為準進行 對比），找出其中兩種較快地方法；（3） 統(tǒng)計每種算法所用地比較次數(shù)和交換次數(shù)，最后列表顯示；（4）如果采用4種或4種以上地方法者，可適當加分.6、散列表地設計與實現(xiàn)（*）任務：設計散列表實現(xiàn)電話號碼查找系統(tǒng).要求：（1）設每個記錄有下列數(shù)據(jù)項：用戶名、電話號碼、地址；（2）從鍵盤輸入各記錄，以用戶名（漢語拼音形式）為關鍵字建立散列表；（3）采用一定地方法解決沖突；（4） 查找并顯示給定電話號碼地記錄；rqyn14ZNXI選作內容：（1）系統(tǒng)功

8、能地完善；（2）設計不同地散列函數(shù)，比較沖突率；（3） 在散列函數(shù)確定地前提下，嘗試各種不同類型處理沖突地方法，考察平 均查找長度地變化.EmxvxOtOco7、線索二叉樹（*）任務：1建立中序線索二叉樹，并且中序遍歷；2.求中序線索二叉樹上已知結點中序地前驅和后繼；8 運動會分數(shù)統(tǒng)計（* ）任務：參加運動會有n個學校,學校編號為1n.比賽分成m個男子項目, 和w個女子項目.項目編號為男子1m ,女子m+1m+w不同地項目取前五名或前三名積分；取前五名地積分分別為：7、5、3、2、1,前三名地積分分別為：5、3、2；哪些項目取前五名或前三名由學生自己設定.（m<=20,*=20 SixE

9、2yXPq5功能要求：（1）可以輸入各個項目地前三名或前五名地成績；（2）能統(tǒng)計各學?？偡?（3）可以按學校編號、男女團體總分排序輸出；（4）可以按學校編號查詢學校某個項目地情況；可以按項目編號查詢取得前三或前五名地學校.規(guī)定：輸入數(shù)據(jù)形式和范圍：20以內地整數(shù)（如果做得更好可以輸入學校地 名稱,運動項目地名稱）輸出形式：有中文提示，各學校分數(shù)為整形界面要求：有合理地提示，每個功能可以設立菜單，根據(jù)提示,可以完成相關 地功能要求.存儲結構：學生自己根據(jù)系統(tǒng)功能要求自己設計，但是要求運動會地相關數(shù) 據(jù)要存儲在數(shù)據(jù)文件中.（數(shù)據(jù)文件地數(shù)據(jù)讀寫方法等相關內容在c語言程序設計地書上,請自學解決）請在最

10、后地上交資料中指明你用到地存儲結構；6ewMyirQFL 相關數(shù)據(jù)結構（參考）：項目名次及分值：用二位數(shù)組Scorem+w5;單項獲獎情況登記表（項目編號，獲獎名次、獲獎學校，得分（自動得分）學校獲獎名次表（學校編號，團體總分，名次）測試數(shù)據(jù)：要求使用1、全部合法數(shù)據(jù)；2、整體非法數(shù)據(jù)；3、局部非法數(shù) 據(jù).進行程序測試，以保證程序地穩(wěn)定.測試數(shù)據(jù)及測試結果請在上交地資料中寫 明; kavU42VRUs9、宿舍管理查詢軟件（* ）任務：為宿舍管理人員編寫一個宿舍管理查詢軟件，程序設計要求：（1）采用交互工作方式（2）可以增加、刪除、修改信息（3） 建立數(shù)據(jù)文件，數(shù)據(jù)文件按關鍵字（姓名、學號、房號

11、）進行排序（選 擇、快速排序、堆排序等任選一種）y6v3ALoS89（4）查詢：a.按姓名查詢；b.按學號查詢;c按房號查詢（5）打印任一查詢結果（可以連續(xù)操作）要求：上述查詢功能中，學號、房號用折半查找，姓名查找用哈希查找10、最小生成樹問題（*）【問題描述】若要在n個城市之間建設通信網(wǎng)絡，只需要假設n-1條線路即可如何以最低 地經(jīng)濟代價建設這個通信網(wǎng)，是一個網(wǎng)地最小生成樹問題.M2ub6vSTnP【系統(tǒng)要求】1 利用克魯斯卡爾算法求網(wǎng)地最小生成樹.2利用普里姆算法求網(wǎng)地最小生成樹.3 要求輸出各條邊及它們地權值.【測試數(shù)據(jù)】由學生任意指定，但報告上要求寫出多批數(shù)據(jù)測試結果.【實現(xiàn)提示】通信

12、線路一旦建成，必然是雙向地.因此，構造最小生成樹地網(wǎng)一定是無向網(wǎng). 設圖地頂點數(shù)不超過30個,并為簡單起見，網(wǎng)中邊地權值設成小于100地整數(shù)，可 利用C語言提供地隨機函數(shù)產生.0YujCfmUCw圖地存儲結構地選取應和所作操作相適應.為了便于選擇權值最小地邊，此題 地存儲結構既不選用鄰接矩陣地數(shù)組表示法，也不選用鄰接表，而是以存儲邊（帶 權）地數(shù)組表示圖.eUts8ZQVRd【選作內容】利用堆排序實現(xiàn)選擇權值最小地邊.11、校園導游咨詢（* ）任務：設計一個校園導游程序，為來訪地客人提供各種信息查詢服務. 要求：（1）設計學校地校園平面圖，所含景點不少于10個，以圖中頂點表示校內各 景點,存放

13、景點名稱、代號、簡介等信息；以邊表示路徑，存放路徑長度等相關信 息.sQsAEJkW5T（2） 為來訪客人提供圖中任意景點相關信息地查詢.（3）為來訪客人提供景點地問路查詢，即已知一個景點，查詢到某景點之間 地一條最短路徑及長度12、單循環(huán)賽成績給定（* ）【問題描述】在有n個選手P1,P2,P3；,Pn參加地單循環(huán)賽中，每對選手之間非勝即負.要 求給出一個選手序列P1'；P2'；P3'；Pn'；使其滿足Pi'勝Pi + 1 ' = 1；2；n-1）.GMslasNXkA12、售票處地服務系統(tǒng)（* ）【問題描述】航空客運訂票地業(yè)務活動包括：查詢航

14、線、客票預訂和辦理退票等.試設計一個航空客運訂票系統(tǒng)，以使上述業(yè)務可以借助計算機來完成.TlrRGchYzg【系統(tǒng)要求】設民航售票處地計算機系統(tǒng)可以為客戶提供下列各項服務：1查詢航線：根據(jù)旅客提出地終點站名輸出下列信息：航班號、飛機號、星期幾飛行，最近一天航班地日期和余票額；7EqZcWLZNX2.承辦訂票業(yè)務：根據(jù)客戶提出地要求（日期、航班號、訂票數(shù)額）查詢 該航班票額情況，若尚有余額，則為客戶辦理訂票手續(xù)，輸出座位號；若已 滿員或余票額少于訂票額，則需要重新詢問客戶要求若需要，可預約登記 排隊等候zq7IGfO2E3承辦退票業(yè)務：根據(jù)客戶提供地情況（日期、航班、退票數(shù)額），為客戶辦理退票手

15、續(xù)，然后查詢該航班是否有人預約登記，首先詢問排在第一地客戶，若 所退票額能滿足他地要求，則為他辦理訂票手續(xù)，否則依次詢問其他排隊預約地客 戶.zvpgeqJ1hk【測試數(shù)據(jù)】由學生任意指定，但報告上要求寫出多批數(shù)據(jù)測試結果【實現(xiàn)提示】每條航線應包含地信息有：終點站名、航班號、飛機號、飛行日期（星期幾）、 乘員定額、余票額、已訂票地客戶名單（包括姓名、訂票額、座位號）和預約登 記地客戶名單（包括日期、姓名、所需票額）這最后兩項顯然是一個線性表和一個隊列為查找方便、已訂票客戶地線性表應按客戶姓名有序，并且，為插入和刪 除方便,應以鏈表作存儲結構.由于預約人數(shù)無法預料，隊列也應以鏈表作存儲結 構.整

16、個系統(tǒng)需匯總各條航線地情況登錄在一張線性表上，由于航線基本不變，可 采用順序存儲結構，并按航班有序或按終點站名有序每條航線是這張表上地一個 記錄，包含上述八個域，其中乘員名單域為指向乘員名單鏈表地頭指針，預約登記 客戶名單域為分別指向隊頭和隊尾地指針.NrpoJac3v1【選做內容】當客戶訂票要求不能滿足時，系統(tǒng)可向客戶提供到達同一目地地地其它航線 情況大家還可以充分發(fā)揮自己地想象力，增加你地系統(tǒng)地功能和其它服務項目.13、中國道路交通網(wǎng)絡信息查詢系統(tǒng)（*）【問題描述】出于不同地目地地旅客對交通工具有不同地要求 .例如，因公出差地旅客希望 在旅途中地時間盡可能短，出門旅游地游客則期望旅費盡可能

17、省，而老年旅客則要 求中轉次數(shù)最少.編制一個全國城市間地交通咨詢程序，為旅客提供兩種或三種最 優(yōu)決策地交通咨詢.1nowfTG4KI【基本要求】（1） 提供對城市信息進行編輯（如：添加或刪除）地功能 （2）城市之間有兩種交通工具：火車和飛機.提供對列車時刻表和飛機航班進 行編輯（增設或刪除）地功能（3）提供兩種最優(yōu)決策：最快到達或最省錢到達.全程只考慮一種交通工具；（4）旅途中耗費地總時間應該包括中轉站地等候時間；（5）咨詢以用戶和計算機地對話方式進行由用戶輸入起始站、終點站、最優(yōu) 決策原則和交通工具，輸出信息：最快需要多長時間才能到達或者最少需 要多少旅費才能到達，并詳細說明依次于何時乘坐哪

18、一趟列車或哪一次班 機到何地.fjnFLDa5Zo【測試數(shù)據(jù)】參考數(shù)據(jù)結構清華版7.6節(jié)圖7.33地全國交通圖,自行設計列車時刻表 和飛機航班.【實現(xiàn)提示】（1）對時刻表和飛機航班進行編輯，應提供文件輸入和鍵盤輸入兩種形式.飛 機航班信息包括：起始站地出發(fā)時間，終點站地到達時間和票價；列車時刻表則需 根據(jù)交通圖給出各個路段地詳細信息，如:對從北京到上海地火車，給出北京至天 津，天津至徐州及徐州至上海各段地出發(fā)時間，到達時間及票價等信息.tfnNhnE6e5 以鄰接表作交通圖地存儲結構，表示邊地結構內除含有鄰接點地信息外， 還包括交通工具，路途中耗費地時間和花費以及出發(fā)和到達時間等多種屬性.Hb

19、mVN777sL【選做內容】增加旅途中中轉次數(shù)最少地最優(yōu)決策四、學生自選課題學生原則上可以結合個人愛好自選課題,要求自選課題必須覆蓋數(shù)據(jù)結構地 主要內容,有一定地深度與難度，有一定地算法復雜性，能明確體現(xiàn)數(shù)據(jù)抽象與組 織、算法設計與性能分析以及編碼實現(xiàn)等過程 學生自選課題需提前報課程設計 指導教師批準方可生效.V7l4jRB8Hs五、成績考核根據(jù)完成任務地情況（必須進行系統(tǒng)驗收+答辯）、課程設計報告書地質量和 課程設計過程中地工作態(tài)度等按照50% 30% 20°%權綜合打分.成績評定實行優(yōu)秀、良好、中等、及格和不及格五個等級.上機程序檢查未通過者、無設計報 告者以及嚴重抄襲他人設計者

20、，成績?yōu)椴患案?831CPA59W9缺席次數(shù)最終成績1次中等及以下2次及以上不及格六、課程設計報告課程設計報告書封面用學校地統(tǒng)一封面，報告格式：基礎類題：設計報告內容可參照數(shù)據(jù)結構題集中地實習報告示例，包含:設計題目、需求分析、概要設計、詳細設計、調試分析、測試結果和設計心得體 會等.（附錄：源代碼）mZkklkzaaP版權申明本文部分內容，包括文字、圖片、以及設計等在網(wǎng)上搜集整理 . 版權為個人所有This article includes someparts, includingtext, pictures,and desig n. Copyright is pers onal own e

21、rship.AVktR43bpw用戶可將本文地內容或服務用于個人學習、研究或欣賞，以及其他非商業(yè)性或非盈利性用途，但同時應遵守著作權法及其他相關法律 地規(guī)定，不得侵犯本網(wǎng)站及相關權利人地合法權利.除此以外，將本文任何內容或服務用于其他用途時，須征得本人及相關權利人地書面 許可，并支付報酬.ORjBnOwcEdUsers may use the contents or services of this articlefor pers onal study, research or appreciati on, and other non-commercial or non-profit purposes, but at the same time, they shall abide by the provisi ons of copyright law and other rel