東北電力大學(xué)

1、數(shù)據(jù)結(jié)構(gòu)課程設(shè)汁指導(dǎo)書孫鴻飛東北電力大學(xué)經(jīng)濟管理學(xué)院數(shù)據(jù)結(jié)構(gòu)課程設(shè)汁指導(dǎo)書一、課程設(shè)計的目的數(shù)據(jù)結(jié)構(gòu)課程是信息管理與信息系統(tǒng)專業(yè)的核心課程，是一門以實踐為主的 課程。計 算機學(xué)科各領(lǐng)域及應(yīng)用都用到各種數(shù)據(jù)結(jié)構(gòu)，特別是隨著計算機應(yīng)用領(lǐng)域 的擴大和非數(shù)值計 算的增加，數(shù)據(jù)大量增加，它們之間的結(jié)構(gòu)關(guān)系也日益復(fù)雜，無 論是操作系統(tǒng)、數(shù)據(jù)庫系 統(tǒng)、電子商務(wù)系統(tǒng)、編譯系統(tǒng)及信息系統(tǒng)等的設(shè)計和實 現(xiàn)，還是其它各種應(yīng)用軟件都涉及不 同的數(shù)據(jù)結(jié)構(gòu)。學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)與算法的最終 LI 的是解決實際的應(yīng)用問題，特別是非數(shù)值計算 類型的應(yīng) 用問題。本課程設(shè)計是在學(xué)生理解了數(shù)據(jù)結(jié)構(gòu)內(nèi)在的邏輯關(guān)系的基礎(chǔ)上， 深入討論它們在計

2、 算機中的存儲表示，結(jié)合上機進行算法及存儲表示的實現(xiàn)。這 樣，進一步提高學(xué)生軟件設(shè)計 和編程水平。課程設(shè)計要求同學(xué)獨立完成一個較為完整的應(yīng)用需求分析，在完成設(shè)計和編 程大型作 業(yè)的過程中，深化對數(shù)據(jù)結(jié)構(gòu)與算法課程中基本概念、理論和方法的理 解；訓(xùn)練綜合運用所 學(xué)知識處理實際問題的能力，強化面向?qū)ο蟮某绦蛟O(shè)計理念； 使同學(xué)的程序設(shè)計與調(diào)試水平 有一個明顯的提高。經(jīng)過查找參考資料、技術(shù)手冊和 撰寫文檔的實踐，進一步培養(yǎng)軟件工程 師的綜合素質(zhì)。課程設(shè)計所安排的題 LI, 在難度和深度方面都大于課內(nèi)的上機訓(xùn)練。二、課程設(shè)計要求學(xué)生必須仔細閱讀數(shù)據(jù)結(jié)構(gòu)課程設(shè)汁指導(dǎo)，認真主動完成課設(shè)的要求。有問題及時主動

3、通過各種方式與教師聯(lián)系溝通。學(xué)生要發(fā)揮自主學(xué)習(xí)的能力，充分利用時間，安排好課設(shè)的時間計劃，并在課設(shè)過程中不斷檢測自己的計劃完成情況，及時的向教師匯報。課程設(shè)計按照教學(xué)要求需要三周時間完成，三周中每天（按每周 5 天）至少 要上 3-4 小時的機來調(diào)試 C語言/C+語言設(shè)計的程序，總共至少要上機調(diào)試程序50小時。7月9日 9點提交課程設(shè)計所需全部資料， 7月10日、 11日進行最終答辯和 程序測 試，地點：經(jīng)濟管理學(xué)院 D304o 課程設(shè)計不安排補考，不合格者將隨下屆 同學(xué)重新進行課 程設(shè)訃。注意：在課程設(shè)計時，任選下列一題完成。要求每個同學(xué)獨立完成。三、課程設(shè)計的具體內(nèi)容1. 試設(shè)計一個航空客

4、運定票系統(tǒng)。基本要求如下：每條航線所涉及的信息有：終點站名、航班號、飛行日期（星期兒飛行）、乘員定額、余票量、訂定票的客戶名單（包括姓名、訂票量、艙位等級1, 2或 3）以及等候替補的客戶名單（包括姓名、所需數(shù)量）。系統(tǒng)能實現(xiàn)的操作和功能如下：查詢航線：根據(jù)客戶提出的終點站名輸出如下信息：航班號、飛機號、星期兒飛行，最近一天航班的日期和余票額承辦訂票業(yè)務(wù)：根據(jù)客戶提出的要求（航班號、訂票數(shù)額）查詢該航班票額 情況，若 有余票，則為客戶辦理訂票手續(xù)，輸出座位號；若已滿員或余票少于訂票 額，則需重新詢問 客戶要求。若需要，可登記排隊候補；承辦退票業(yè)務(wù)：根據(jù)客戶提出的情況（日期、航班號），為客戶辦理

5、退票手 續(xù)，然后 查詢該航班是否有人排隊候補，首先詢問排在笫一的客戶，若所退票額能 滿足他的要求，則 為他辦理訂票手續(xù)，否則依次詢問其它排隊候補的客戶。實現(xiàn)提示：兩個客戶名單可分別由線性表和隊列實現(xiàn)。為查找方便，已訂票 客戶的線 性表應(yīng)按客戶姓名有序，并且，為了插入和刪除方便，應(yīng)以鏈表作為存儲 結(jié)構(gòu)。 III 于預(yù)約 人數(shù)無法預(yù)計，隊列也應(yīng)以鏈表作為存儲結(jié)構(gòu)。2. 校園導(dǎo)游咨詢（為來訪的客人提供各種信息服務(wù)）問題描述：設(shè)計你的學(xué)校的校園平面圖，所含景點 10 個左右。以圖中頂點表 示校園 內(nèi)各景點，存放景點名稱、代號、簡介等信息；以邊表示路徑，存放路徑長 度等有關(guān)信息。為來訪客人提供圖中任意景

6、點相關(guān)信息的查詢。為來訪客人提供任意景點的問路查詢，即查詢?nèi)我鈨蓚€景點之間的一條最短 路徑。實現(xiàn)提示：一般情況下，校園的道路是雙向通行的，可設(shè)計 ?校園平面圖是一個無向網(wǎng)。頂點和邊均含有相關(guān)信息。3. 停車場管理問題問題描述：設(shè)有一個可以停放 n 輛汽車的狹長停車場，它只有一個大門可以供車輛進出。車輛按到達停車場時間的早晚依次從停車場最里面向大門口處停放 （最先到達的笫一輛 車放在停車場的最里面）。如果停車場已放滿 n 輛車，則后來的 車輛只能在停車場大門外的 便道上等待，一旦停車場內(nèi)有車開走，則排在便道上的 笫一輛車就進入停車場。停車場內(nèi)如 有某輛車要開走，在它之后進入停車場的車都 必須先退

7、出停車場為它讓路，待其開出停車場后，這些車輛再依原來的次序進場。 每輛車在離開停車場時，都應(yīng)根據(jù)它在停車場內(nèi)停留的 時間長短交費。如果停留在 便道上的車未進停車場就要離去，允許其離去，不收停車費，并 且仍然保持在便道 上等待的車輛的次序。編制一程序模擬該停車場的管理。實現(xiàn)要求：要求程序輸出每輛車到達后的停車位置 ( 停車場或便道上 )，以及 某輛車離 開停車場時應(yīng)交納的費用和它在停車場內(nèi)停留的時間。實現(xiàn)提示：汽車的模擬輸入信息格式可以是： (到達/ 離去，汽車牌照號碼， 到達/ 離 去的時刻)。例如， ('A' , 1, 5)表示1號牌照車在 5這個時刻到達，而 ('D

8、' , 5, 20)表示 5號牌 照車在 20這個時刻離去。整個程序可以在輸入信息為('E' , 0, 0)時結(jié)束。本題可用棧和隊列來實現(xiàn)。4. 迷宮問題問題描述：迷宮實驗是取自心理學(xué)的一個古典實驗。在該實驗中，把一只老 鼠從一個 無頂大盒子的門放入，在盒中設(shè)置了許多墻，對行進方向形成了多處阻 擋。盒子僅有一個岀 口處放置一塊奶酪，吸引老鼠在迷宮中尋找道路以到達出口。 對同一只老鼠重復(fù)進行上述實 驗，一直到老鼠從入口到出口，而不走錯一步。老鼠 經(jīng)多次試驗終于得到它學(xué)習(xí)走通迷宮的 路線。設(shè)計一個計算機程序?qū)θ我庠O(shè)定的迷 宮，求出一條從入口到出口的通路，或得出沒有 通路的結(jié)

9、論。實現(xiàn)要求：要求程序輸出：(D-條通路的二元組(i, j)數(shù)據(jù)序列，(i, j)表示通路上某一點的坐標。(2)用一種標志 ( 如數(shù)字 8)在二維數(shù)組中標出該條通路，并在屏幕上輸出二維數(shù)組。實現(xiàn)提示：可以利用一個二維數(shù)組mazeij表示迷宮，其中1 <=i<=m, l<=j<=n。數(shù)組元素值為 1 表示該位置是墻壁，不能通行；元素值為 0 表示該位置 是通路。假定從 mazel1出發(fā)，出口位于 mazemZ nj,移動方向可以是 8個方 向（東，東南，南，西南，西，西 北，北和東北）。5. n階魔陣問題問題描述：給定一奇數(shù) m構(gòu)造一個n階魔陣。n階魔陣是一個n階方陣，其

10、 元素由自 然數(shù)1, 2, 3,，n2組成。魔陣的每一行元素之和，每列元素之和以及主、副對角線元素之和均相等。即對于給定的奇數(shù) n以及i二1,2, 3,魔陣a滿足條件：nnnna ik =cl ki = a kk = a k 、”- Ar +斤=1女=11A=1實現(xiàn)要求：要求輸出結(jié)果的格式要具有n階方陣的形式。實現(xiàn)提示：依次將自然數(shù)填入方陣中，共填n輪，每輪填n次。第一輪的第一次，將 1填入方陣的中間一行的最后一列位置。設(shè)前一次填入的位置是dij：每輪中第2至第n次將數(shù)填入ai+1, j+1,若遇到下列兩種情況之一，則填寫位置按以下規(guī)則調(diào)整。 aij是最后一列（即 仙）位置，則將下一個數(shù)填入

11、ai+1,1; sij是最后一行（即i=n）位置，則將下一個數(shù)填入 al, j+1新一輪的第一次填入 al, j-lo6. 公交線路問題表一些區(qū)問題描述：假設(shè)以一個帶權(quán)有向圖表示某一個區(qū)域的公交線路；圖中頂點代域中的重要場所，弧代表已有的公交線路，弧上的權(quán)表示該線路上的票價 （或搭乘所需時 間）。試設(shè)計一個交通指南系統(tǒng)，指導(dǎo)前來咨詢者以最低的票價或 最少的時間從區(qū)域中的某 一場所到達列一場所。實現(xiàn)提示：該問題可歸結(jié)為一個求帶權(quán)有向圖中頂點間最短路徑的問題。分 別建立以 票價為權(quán)或以搭乘時間為權(quán)的圖的鄰接矩陣，以 Floyd 算法來求最短路徑 及其路徑長度。7. 編寫一個五子棋的游戲程序。問題描

12、述：實現(xiàn)兩人對下功能。8. 紙牌游戲問題描述：編號為 1 -52張牌，正面向上，從第 2張開始，以 2為基數(shù)，是 2 的倍數(shù)的 牌翻一次，直到最后一張牌；然后，從第 3張開始，以 3 為基數(shù)，是 3的 倍數(shù)的牌翻一次， 直到最后一張牌；然后從笫4張開始，以4為基數(shù)，是4的倍 數(shù)的牌翻一次，直到最后一張牌； . 再依次 5 的倍數(shù)的牌翻一次， 6 的， 7 的直 到以 52為基數(shù)的翻過，輸出：這時正 面向上的牌有哪些？9. 文章編輯問題描述：輸入一頁文字，程序可以統(tǒng)計 ?出文字、數(shù)字、空格的個數(shù)。靜態(tài)存儲一頁文章，每行最多不超過80個字符，共N行；要求（1）分別統(tǒng) 計出其中英文字母數(shù)和空格數(shù)及整

13、篇文章總字數(shù)；（ 2） 統(tǒng)計某一字符串在文章中 出現(xiàn)的次數(shù)，并輸出該次數(shù)；（3） 刪除某一子串，并將后面的字符前移。存儲結(jié)構(gòu)使用線性表，分別用兒個子函數(shù)實現(xiàn)相應(yīng)的功能輸入數(shù)據(jù)的形式和范圍：可以輸入大寫、小寫的英文字母、任何數(shù)字及標點 符號。輸出形式： ( 1)分行輸出用戶輸入的各行字符； (2)分 4 行輸出“全部字 母數(shù)”、“數(shù) 字個數(shù)”、“空格個數(shù)”、“文章總字數(shù)”( 3)輸岀刪除某一字符 串后的文章。10. 運動會分數(shù)統(tǒng)計問題描述：參加運動會有 n個學(xué)校，學(xué)校編號為 1 n。比賽分成m個男子 項目， 和w個女子項目。項目編號為男子1 m,女子m+1 m+wo不同的項目 取前五名或前三名積

14、分；取詢五名的積分分別為：7、5、3、2、1,前三名的積分 分別為： 5、3、2；哪些取前五名或前三名由學(xué)生自己設(shè)定。 (m<=20,n<=20)功能要求：1) .可以輸入各個項目的前三名或前五名的成績；2) .能統(tǒng)計各學(xué)校總分，3) .可以按學(xué)校編號、學(xué)?？偡帧⒛信畧F體總分排序輸出；4) .可以按學(xué)校編號查詢學(xué)校某個項U 的惜況；可以按項 U 編號查詢?nèi)〉们叭?或詢五名的學(xué)校。規(guī)定：輸入數(shù)據(jù)形式和范圍： 20以內(nèi)的整數(shù) ( 如果做得更好可以輸入學(xué)校的 名稱，運 動項目的名稱 ) ；輸出形式：有中文提示，各學(xué)校分數(shù)為整型；界面要求：有合理的提示，每個功能可以設(shè)立菜單，根據(jù)提示，可以完成相關(guān)的功能要求。存儲結(jié)構(gòu)：學(xué)生自己根據(jù)系統(tǒng)功能要求自己設(shè)計，但是要求運動會的相關(guān)數(shù)據(jù)要存儲在數(shù)據(jù)文件中。（數(shù)據(jù)文件的數(shù)據(jù)讀寫方法等相關(guān)內(nèi)容在C/C+ 語言程序 設(shè)計的書上，請自學(xué)解決）請在最后的上交資料中指明你用到的存儲結(jié)構(gòu)；測試數(shù)據(jù)：要求使用 1、全部合法數(shù)據(jù)； 2、整體非法數(shù)據(jù)； 3、局部非法數(shù) 據(jù)。進行 程序測試，以保證程序的穩(wěn)定。測試數(shù)據(jù)及測試結(jié)果請在上交的資料中寫 明。四、上交相關(guān)內(nèi)容要求上交的成果的內(nèi)容必須由以下四個部分組成，缺一不可。1. 上交源程序：學(xué)生按照課程設(shè)汁的具體要求所開發(fā)