數(shù)據(jù)結構課程設計(軟件工程)

《數(shù)據(jù)結構課程設計》

指導書軟件學院軟件工程（娛樂軟件）2015年06月《數(shù)據(jù)結構課程設計》指導書一、課程設計題目與要求根據(jù)課程設計題目規(guī)模，要求每個題目可分組完成（不超過3個人）。一經(jīng)確定不得隨意調(diào)換，題目由各組選派代表抽簽確定，設計題目不得更換。運動會分數(shù)統(tǒng)計任務：參加運動會有n個學校，學校編號為1n。比賽分成m個男子項目，和w個女子項目。項目編號為男子1m，女子m+1m+w。不同的項目取前五名或前三名積分；取前五名的積分分別為：7、5、3、2、1，前三名的積分分別為：5、3、2；哪些取前五名或前三名由學生自己設定。（m<=20,n<=20）功能要求：1） 可以輸入各個項目的前三名或前五名的成績；2） 能統(tǒng)計各學?？偡?，3） 可以按學校編號或名稱、學校總分、男女團體總分排序輸出；4） 可以按學校編號查詢學校某個項目的情況；可以按項目編號查詢?nèi)〉们叭蚯拔迕膶W校。5） 數(shù)據(jù)存入文件并能隨時查詢6） 規(guī)定：輸入數(shù)據(jù)形式和范圍：可以輸入學校的名稱，運動項目的名稱輸出形式：有中文提示，各學校分數(shù)為整形界面要求：有合理的提示，每個功能可以設立菜單，根據(jù)提示，可以完成相關的功能要求。存儲結構：學生自己根據(jù)系統(tǒng)功能要求自己設計，但是要求運動會的相關數(shù)據(jù)要存儲在數(shù)據(jù)文件中。請在最后的上交資料中指明用到的存儲結構；測試數(shù)據(jù)：要求使用1、全部合法數(shù)據(jù)；2、整體非法數(shù)據(jù)；3、局部非法數(shù)據(jù)。進行程序測試，以保證程序的穩(wěn)定。測試數(shù)據(jù)及測試結果請在上交的資料中寫明；飛機訂票系統(tǒng)任務：通過此系統(tǒng)可以實現(xiàn)如下功能：錄入：可以錄入航班情況（數(shù)據(jù)可以存儲在一個數(shù)據(jù)文件中，數(shù)據(jù)結構、具體數(shù)據(jù)自定）查詢：可以查詢某個航線的情況（如，輸入航班號，查詢起降時間，起飛抵達城市，航班票價，票價折扣，確定航班是否滿倉）；可以輸入起飛抵達城市，查詢飛機航班情況；訂票：（訂票情況可以存在一個數(shù)據(jù)文件中，結構自己設定）可以訂票，如果該航班已經(jīng)無票，可以提供相關可選擇航班；退票：可退票，退票后修改相關數(shù)據(jù)文件；客戶資料有姓名，證件號，訂票數(shù)量及航班情況，訂單要有編號。修改航班信息：當航班信息改變可以修改航班數(shù)據(jù)文件要求：根據(jù)以上功能說明，設計航班信息，訂票信息的存儲結構，設計程序完成功能；宿舍管理查詢系統(tǒng)1） 任務：為宿舍管理人員編寫一個宿舍管理查詢軟件，程序設計要求：采用交互工作方式建立數(shù)據(jù)文件，數(shù)據(jù)文件按關鍵字（姓名、學號、房號）進行排序（冒泡、選擇、插入排序等任選兩種方法實現(xiàn)）2） 查詢菜單:（用二分查找實現(xiàn)以下操作）按姓名查詢按學號查詢按房號查詢打印任一查詢結果(可以連續(xù)操作)簡易銀行卡管理系統(tǒng)主要功能與要求：開戶：創(chuàng)建一個新的賬戶，接受用戶輸入的身份證號，以及賬戶密碼，判斷用戶輸入的身份證號是否唯一且賬戶密碼是否符合要求，如驗證成功則為該用戶生成一個唯一的帳號。存款：在用戶輸入正確的帳號和密碼的情況下，接受用戶輸入的存款金額，并對該帳號的存款信息進行更新。取款：在用戶輸入正確的帳號和密碼的情況下，接受用戶輸入的取款金額。取款金額不應該大于當前帳號存款金額，當取款金額不大于當前帳號存款金額時，執(zhí)行取款操作，并對該帳戶的存款信息進行更新。掛失：在用戶輸入正確的帳號和密碼的情況下，接受用戶掛失操作。當帳號掛失后，與該帳號相關的操作都將被禁止。銷戶：在用戶輸入正確的帳號和密碼的情況下，接受用戶銷戶。當用戶銷戶后，該帳號將被永久刪除。轉帳：在用戶輸入正確的帳號和密碼的情況下，接受用戶轉賬操作，轉帳金額不應該大于當前帳號存款金額，當轉帳金額不大于當前帳號存款金額時，執(zhí)行轉帳操作，并對該帳戶的存款信息及轉帳的接受賬戶的存款信息進行更新。修改賬戶密碼：在用戶輸入正確的帳號和密碼的情況下，接受用戶修改密碼操作，用戶輸入的原密碼，若用戶輸入的密碼與原密碼匹配，則接受用戶輸入的新密碼，若用戶兩個輸入的密碼相同，則修改賬戶密碼，并對數(shù)據(jù)文件進行更新操作。查看余額：在用戶輸入正確的帳號和密碼的情況下，接受用戶查看余額操作，該模塊只涉及數(shù)據(jù)查詢，并不涉及數(shù)據(jù)文件更新操作。查看用戶交易歷史：在用戶輸入正確的帳號和密碼的情況下，接受用戶查看用戶交易歷史操作，系統(tǒng)將顯示當前賬戶的最近的存、取款操作記錄，該模塊只涉及數(shù)據(jù)查詢，并不涉及數(shù)據(jù)文件更新操作。校園導航設計要求：設計你的學校的平面圖，至少包括10個以上的場所，每兩個場所間可以有不同的路，且路長也可能不同，找出從任意場所到達另一場所的最佳路徑(最短路徑)?；疽螅涸O計校園平面圖，在校園景點選10個左右景點。以圖中頂點表示校園內(nèi)各景點，存放景點名稱、代號、簡介等信息；以邊表示路徑，存放路徑長度等有關信息。為來訪客人提供圖中任意景點相關信息的查詢。為來訪客人提供任意景點的問路查詢，即查詢?nèi)我鈨蓚€景點之間的一條最短路徑。實現(xiàn)提示：一般情況下，校園的道路是雙向通行的，可設計校園平面圖是一個無向網(wǎng)。頂點和邊均含有相關信息。通訊錄管理系統(tǒng)模塊要求：第一個模塊一一主函數(shù)main()的功能是：根據(jù)選單的選項調(diào)用各函數(shù)，并完成相應的功能。第二個模塊——Menu()的功能是：顯示英文提示選單。第三個模塊——Quit()的功能是：退出選單。第四個模塊 Create()的功能是：創(chuàng)建新的通訊錄。第五個模塊——Add()的功能是：在通訊錄的末尾，寫入新的信息，并返回選單。第六個模塊——Find()的功能是：查詢某人的信息，如果找到了，則顯示該人的信息，如果未找到，則提示通訊錄中沒有此人的信息，并返回選單。第七個模塊——Alter()的功能是：修改某人的信息，如果未找到要修改的人，則提示通訊錄中沒有此人的信息，并返回選單。第八個模塊——Delete()的功能是：刪除某人的信息，如果未找到要刪除的人，則提示通訊錄中沒有此人的信息，并返回選單。第九個模塊 List()的功能是：顯示通訊錄中的所有記錄。；設計要求：每條信息至包含：姓名(NAME)、性別(GENDER)、電話(TEL)、城市(CITY)由^編(EIP)幾項。通訊錄采用文件保存。作為一個完整的系統(tǒng)，應具有友好的界面和較強的容錯能力。職工管理系統(tǒng)問題描述：對單位的職工進行管理，包括插入、刪除、查找、排序等功能。要求：職工對象包括姓名、性別、出生年月、工作年月、學歷、職務、住址、電話等信息。新增一名職工：將新增職工對象存入職工數(shù)據(jù)文件中。刪除一名職工：從職工數(shù)據(jù)文件中刪除一名職工對象。查詢：從職工數(shù)據(jù)文件中查詢符合某些條件的職工。修改：檢索某個職工對象，對其某些屬性進行修改。排序：按某種需要對職工對象文件進行排序(冒泡、選擇、插入排序等任選兩種方法實現(xiàn))。實現(xiàn)提示：職工對象數(shù)不必很多，便于一次讀入內(nèi)存，所有操作不經(jīng)過內(nèi)外存交換。由鍵盤輸入職工對象，以文件方式保存。程序執(zhí)行時先將文件讀入內(nèi)存。(2)對職工對象中的”姓名”按字典順序進行排序。(3)對排序后的職工對象進行增、刪、查詢、修改、排序等操作。選做內(nèi)容：將職工對象按散列法存儲，并設計解決沖突的方法。在此基礎上實現(xiàn)增、刪、查詢、修改、排序等操作。全國交通資訊系統(tǒng)問題描述：設計、實現(xiàn)一個全國大城市間的交通咨詢程序，為旅客提供三種最優(yōu)決策方案：時間最短費用最小中轉次數(shù)最少。需求分析：該程序所做的工作的是模擬全國交通咨詢，為旅客提供三種最優(yōu)決策的交通咨詢。在程序中輸入城市名稱時，需輸入10個字母以內(nèi)的字母串；輸入列車或飛機編號時需輸入一個整型數(shù)據(jù)；輸入列車或飛機的費用時需輸入一個實型數(shù)據(jù)；輸入列車或飛機開始時間和到達時間時均需輸入兩個整型數(shù)據(jù)(以hh：mm的形式)；在選擇功能時，應輸入與所選功能對應的一個整型數(shù)據(jù)。程序的輸出信息主要是：最快需要多少時間才能到達，或最少需要多少旅費才能到達，或最少需要多少次中轉到達，并詳細說明依次于何時乘坐哪一趟列車或哪一次班機到何地。程序的功能包括：提供對城市信息的編輯，提供列車時刻表和飛機航班表的編輯，提供三種最優(yōu)決策：最快到達、最省錢到達、最少中轉次數(shù)到達。附錄：測試數(shù)據(jù)航班時刻表

機號出發(fā)地到達地出發(fā)時間到達時間費用6320北京上海上海北京16：2018：0017：2519：05680元2104北京烏魯木齊烏魯木齊北京8：0010：459：5511：401150元201北京西安西安北京15：2512：3517：0014：15930元2323西安廣州廣州西安7：1510：159：3511：351320元173拉薩昆明昆明拉薩10：2012：3511：4514：00830元3304拉薩武漢武漢拉薩14：1516：2515：4517：55890元82烏魯木齊昆明昆明烏魯木齊9：3013：0512：1515：501480元4723武漢廣州廣州武漢7：0511：258：4513:05810元列車時刻表車次出發(fā)地到達地出發(fā)時間到達時間車費27北京鄭州13：1521：1278元鄭州西安21：2405：1382元西安鄭州05：4113：3082元鄭州北京13：4221：3978元41北京鄭州7：1115：0890元鄭州上海15：2000：13100元上海鄭州00：3509：28100元鄭州北京09：4017：3790元59上海廣州08：2003：16182元廣州上海03：3922：53134蘭州北京03：5218：56162元北京蘭州19：2410：28323廣州昆明06：1816：14102元昆明廣州16：3102：27873武漢昆明07：1321：17134元昆明武漢21：4211：46116武漢長沙9：3618：3298元長沙武漢18：5403：48373長沙廣州13：1500：15116元廣州長沙00：3511：35蘭州武漢17：4114：47210元747武漢蘭州15：1312：19371蘭州烏魯木齊烏魯木齊蘭州11：4200：3523：5411：23114元218武漢西安西安武漢18：5001：3411：5118：35178元停車場管理有一個兩層的停車場，每層有6個車位，當?shù)谝粚榆囃M后才允許使用第二層.（停車場可用一個二維數(shù)組實現(xiàn)，每個數(shù)組元素存放一個車牌號）每輛車的信息包括車牌號、層號、車位號、停車時間共4項，其中停車時間按分鐘計算。假設停車場初始狀態(tài)為第一層已經(jīng)停有 4輛車，其車位號依次為1—4，停車時間依次為20,15,10,5。即先將這四輛車的信息存入文件"car.dat"+（數(shù)組的對應元素也要進行賦值）。停車操作：當一輛車進入停車場時，先輸入其車牌號,再為它分配一個層號和一個車位號（分配前先查詢車位的使用情況,如果第一層有空則必須停在第一層）,停車時間設為5,最后將新停入的汽車的信息添加文件”car.daf中,并將在此之前的所有車的停車時間加5。收費管理（取車）：當有車離開時，輸入其車牌號，先按其停車時間計算費用，每5分鐘0.2元.（停車費用可設置一個變量進行保存）,同時從文件”car.dat”中刪除該車的信息，并將該車對應的車位設置為可使用狀態(tài)（即二維數(shù)組對應元素清零）.按用戶的選擇來判斷是否要輸出停車收費的總計。輸出停車場中全部車輛的信息。商品銷售統(tǒng)計系統(tǒng)設計商品銷售統(tǒng)計系統(tǒng)，實現(xiàn)定期對銷售各商品的記錄進行統(tǒng)計，可按商品的編號、單價、銷售量或銷售額做出排名并顯示。選擇合適的存儲結構，建立商品信息表并存放在數(shù)據(jù)文件中。各商品的信息包括：商品編號、名稱、單價、銷出數(shù)量、銷售額。對各商品的單價、銷售量或銷售額進行排序時，可采用多種排序方法，如直接插入排序、折半插入排序、冒泡排序，快速排序、選擇排序等方法。功能設計：（1） 實現(xiàn)建立商品信息表功能（2） 實現(xiàn)分別使用不同的排序方法按商品單價、銷售量、銷售額進行排序功能（3） 實現(xiàn)顯示排序結果功能圖書管理系統(tǒng)設計一個計算機管理系統(tǒng)完成圖書管理基本業(yè)務?；疽螅海?） 每種書的登記內(nèi)容包括書號、書名、著作者、現(xiàn)存量和庫存量；（2） 對書號建立索引表（線性表）以提高查找效率；（3） 系統(tǒng)主要功能如下：采編入庫：新購一種書，確定書號后，登記到圖書帳目表中，如果表中已有，則只將庫存量增加；借閱：如果一種書的現(xiàn)存量大于0,則借出一本，登記借閱者的書證號和歸還期限，改變現(xiàn)存量；歸還：注銷對借閱者的登記，改變該書的現(xiàn)存量。文章編輯系統(tǒng)功能：輸入一頁文字，程序可以統(tǒng)計出文字、數(shù)字、空格的個數(shù)。靜態(tài)存儲一頁文章，每行最多不超過80個字符，共N行。要求：（1）分別統(tǒng)計出其中英文字母數(shù)和空格數(shù)及整篇文章總字數(shù)；（2）統(tǒng)計某一字符串在文章中出現(xiàn)的次數(shù)，并輸出該次數(shù)；（3）刪除某一子串，并將后面的字符前移。存儲結構使用線性表，分別用幾個子函數(shù)實現(xiàn)相應的功能。輸入數(shù)據(jù)的形式和范圍：可以輸入大寫、小寫的英文字母、任何數(shù)字及標點符號。輸出形式：（1）分行輸出用戶輸入的各行字符；（2）分4行輸出“全部字母數(shù)”、“數(shù)字個數(shù)”、“空格個數(shù)”、“文章總字數(shù)”；（3）輸出刪除某一字符串后的文章。學生成績管理系統(tǒng)現(xiàn)有學生成績信息文件1（1.txt）,內(nèi)容如下：姓名學號語文數(shù)學英語張明明01677882李成友02789188張輝燦03688256王露04564577陳東明05673847學生成績信息文件2（2.txt）,內(nèi)容如下:姓名學號語文數(shù)學英語陳果31576882李華明32889068張明東33484256李明國34504587陳道亮35475877試編寫一個管理系統(tǒng)，要求如下：1） 要求使用鏈表或數(shù)組等實現(xiàn)上述要求2） 實現(xiàn)對兩個文件數(shù)據(jù)進行合并，生成新文件3.txt3） 可實現(xiàn)學生成績信息的輸入、修改、刪除功能4） 抽取出三科成績中有補考的學生并保存在一個新文件4.txt5） 對合并后的文件3.txt中的數(shù)據(jù)按總分降序排序（至少采用兩種排序方法實現(xiàn)）6） 輸入一個學生姓名后，能查找到此學生的信息并輸出結果（至少采用兩種查找方法實現(xiàn)）7） 統(tǒng)計輸出各門課程的平均分，最高分、最低分8） 統(tǒng)計各門課程優(yōu)秀、良好、中等、及格、不及格的人數(shù)及百分比客戶消費積分管理系統(tǒng)問題描述：針對客戶的消費情況進行客戶管理，根據(jù)客戶的消費積分對客戶實行不同程度的打折優(yōu)惠。基本要求：1） 采用一定的存儲結構進行客戶信息的存儲2） 對客戶的信息可以進行添加、修改、刪除3） 可根據(jù)消費情況進行客戶積分的計算4） 根據(jù)積分情況實行不同程度的打折優(yōu)惠舞伴問題問題描述：一班有m個女生、n個男生（m不等于n）,舉辦一場舞會.男女生分別編號坐在舞池兩邊的椅子上，每曲開始時，依次從男生和女生中各出一人配對跳舞，本曲沒成功配對者坐著等待下一曲找舞伴，設計一個程序模擬舞伴配對過程?；疽螅狠斎肽?、女學生的姓名、性別，由程序自動為男女生編號，可以順序編號，也可以隨機編號，輸出每曲配對情況（包括男、女生的姓名、性別和編號〉原始數(shù)據(jù)和結果數(shù)據(jù)要保存到文件中。16.管道鋪設施工的最佳方案問題描述:需要在某個城市的n個小區(qū)鋪設管道，則在這n個小區(qū)之間鋪設n-1條管道即可，假設任意兩個居民區(qū)之間都可以架設管道，但由于地理環(huán)境的不同，所需經(jīng)費不同，選擇最優(yōu)的施工方案使總投資盡可能的少?；疽螅狠斎氡硎拘^(qū)間關系的圖及每條管道的權值，選擇出n-1條管道，使總投資最小。圖的信息輸入一次后，保存到文件中，選擇的n-1條管道輸出到顯示器的同時，也保存于文件中。（1） 設計良好的用戶界面（2） 采用兩種存儲結構實現(xiàn)（3） 用兩種算法找到最小生成樹。（4） 輸出原始圖及選擇n-1條管道后的圖。測試用例：任意選擇一個圖，模擬小區(qū)間可能鋪設的管道及費用。二、課程設計報告內(nèi)容與要求課程設計報告主要內(nèi)容應包括：1、 需求分析：根據(jù)題目要求，充分地分析和理解問題，描述系統(tǒng)的功能要求，分析系統(tǒng)所要處理的數(shù)據(jù)有哪些類型，它們之間存在哪些關系，采用何種數(shù)據(jù)結構描述。充分地分析和理解題目，明確要做什么（而不是怎么做，即設計的系統(tǒng)將要實現(xiàn)的功能），系統(tǒng)的輸入與輸出；系統(tǒng)的測試用例。（1） 問題描述（2） 基本要求輸入的形式和輸入值的范圍輸出的形式程序所能達到的功能2、 概要設計根據(jù)需求分析，完成數(shù)據(jù)模型及相關運算的定義，給出數(shù)據(jù)結構的ADT表示；設計系統(tǒng)的原型（操作界面）。說明本系統(tǒng)中用到的所有數(shù)據(jù)類型的定義及存儲結構，主程序的流程以及各程序模塊之間的調(diào)用關系。（1） 數(shù)據(jù)結構（2） 程序模塊（3） 各模塊之間的調(diào)用關系以及算法設計3、 詳細設計實現(xiàn)概要設計中定義的所有數(shù)據(jù)類型，對主要操作寫出實現(xiàn)算法，對主程序和其他模塊寫出算法，寫出函數(shù)的調(diào)用關系。4、 編碼調(diào)試：根據(jù)詳細設計完成系統(tǒng)的編碼、測試程序，要有給定的正確數(shù)據(jù)、錯誤數(shù)據(jù)和邊界數(shù)據(jù)，要有不同的結果并進行結果分析，對于出現(xiàn)的錯誤，要進行錯誤分析，并進行改正。5、 總結（收獲與體會，不少于500漢字）：主要內(nèi)容包括：（1） 本次課程設計各階段（需求分析、概要設計、詳細設計、編碼調(diào)試等）所遇到的問題，問題的現(xiàn)象描述，產(chǎn)生的原因，解決方案（措施），解決的結果等；（2） 測試結果分析，給出所采用的測試數(shù)據(jù)并對所得到的結果進行分析，分析算法的性能（時間與空間復雜度）。（3） 探討更多解決問題的途徑，給出改進算法的建議。（4）本次課程設計收獲：存在的問題（不足之處）、感想、今后努力的方向等。參考文獻附件：程序源代碼（重點功能加上必要的注釋）三、 設計報告的格式要求一律打?。ˋ4紙張），簡易裝訂。字體大小及格式可參照如下：標題題目用小二號黑體字書寫，居中放置，并且距下文雙倍行距；第一層次（章）題序和標題用小二號黑體字，第二層次（節(jié)）題序和標題用小三號黑體字，第三層次題序和標題用四號黑體字，第四層次及以下題序和標題用小四號黑體字，正文用小四號宋體字。正文章節(jié)序號均以阿拉伯數(shù)字連續(xù)編號，最多為4級，（如：1.1.1 1.1.1.1），章條編號一律左頂格，編號后空一'個字距，再寫章條題名；之后先以括號為序（如（1）、（2）…），再以帶圈字符為序（如1、2…），左空2個字距書寫。正文正文文字內(nèi)容一律采用小四號宋體字，正文中英文用四號'TimesNewRoman”字體;各級層次標題與上下文間均為1.5倍行距。公式圖表圖表和公式要按章編號。公式應另起一行書寫，公式應盡量采用公式編輯器輸入，選擇默認格式，公式號右對齊；圖表應有相對應的名稱，圖表標題均居中，用五號宋體字書寫，且置于文章中首次提到處附近。參考文獻凡引用本人或他人已公開或未公開發(fā)表文獻中的學術思想、觀點或研究方法、設計方案等，都應編入?yún)⒖嘉墨I目錄。參考文獻的編寫格式為：圖書文獻的格式：［編號］作者.書名.出版單位，年份，版次，頁碼。技術標準：［編號］標準名稱.標準代號.標準順序號-發(fā)布年.打印要求單面打印，上2.5cm，下2cm，左2.5cm，右2.0cm，頁碼用小五號宋體字下居中標明。四、 課程設計時間及地點周次日期設計內(nèi)容具體要求設計教室指導時間段172015.6.29.(周一)安排分組，選擇設計題目，查閱相關資料熟悉課題的相關資料［龍］計算中心(14:30-16:10)2015.6.30(周二)熟悉課題的任務和要求；系統(tǒng)分析、規(guī)劃，劃分功能模塊，小組成員分配任務模塊功能劃分，任務分配［龍］計算中心(14:30-16:10)2015.7.1(周三)收集相關資料進行需求分析確定模塊的功能要求［龍］計算中心(14:30-16:10)

2015.7.2（周四）不既要設計，說明每個部分的算法設計說明（可以是描述算法的流程圖），每個程序中使用的存儲結構設計說明（如果指定存儲結構請寫出該存儲結構的定義）給出程序設計框架圖和使用的數(shù)據(jù)結構［龍］計算中心（14: