09級數(shù)據(jù)結(jié)構(gòu)課程設(shè)計任務(wù)書

1、一課程設(shè)計的任務(wù)本次設(shè)計是為加強學(xué)生的軟件編程能力而進行的專門訓(xùn)練。選題考慮到學(xué)生在數(shù)據(jù)結(jié)構(gòu)中學(xué)過的各種算法、數(shù)據(jù)組織方式進行選題，考慮數(shù)據(jù)結(jié)構(gòu)算法所涉及的操作系統(tǒng)、網(wǎng)絡(luò)、編譯方法等中的實例，進行設(shè)計。下面是課程設(shè)計待選題目共43題。按學(xué)號相應(yīng)選題，如：學(xué)號為01，則選擇第1題。分析題目，完成相應(yīng)題目的程序設(shè)計。1、商品管理問題描述：以鏈表結(jié)構(gòu)的有序表表示某商場家電部的庫存模型，當有提貨或進貨時需要對該鏈表及時進行維護，每個工作日結(jié)束以后，將該鏈表中的數(shù)據(jù)以文件形式保存，每日開始營業(yè)之前，須將文件形式保存的數(shù)據(jù)恢復(fù)成鏈表結(jié)構(gòu)的有序表。實現(xiàn)要求：鏈表結(jié)構(gòu)的數(shù)據(jù)域 包括家電名稱、品牌、單價和數(shù)量，

2、以單價的升序體現(xiàn)鏈表的有序性。程序功能包括：初始化、創(chuàng)建表、插入、刪除、更新數(shù)據(jù)、查詢及鏈表數(shù)據(jù)與文件之間的轉(zhuǎn)換等。2、編程整理表達式鍵盤輸入一個含有括號的四則運算表達式，可能含有多余的括號，編程整理該表達式，去掉所有多余的括號，原表達式中所有變量和運算符相對位置保持不變，并保持與原表達式等價。3、個人帳簿管理問題描述：個人帳簿管理系統(tǒng)記錄某人每月的全部收入及各項開支情況，包括食品消費，房租，子女教育費用，水電費，醫(yī)療費，儲蓄等。進入系統(tǒng)后可以輸入和修改某月的收支情況，可以對每月的開支從小到大進行排序，可以根據(jù)輸入的月份查詢每月的收支情況。實現(xiàn)要求：1 初步完成總體設(shè)計，搭好框架，確定人機對話

3、的界面，確定函數(shù)個數(shù)；2 完成最低要求：建立一個文件，包括某人5個月的收支情況，能對文件中的信息進行擴充（追加），修改和刪除；3 進一步要求：完成對每月的開支排序，以及完成系統(tǒng)查詢功能。有興趣的同學(xué)可以自己擴充系統(tǒng)功能。4、實現(xiàn)：連通無向圖的非遞歸遍歷。5、招聘模擬。 問題描述：某集團公司為發(fā)展生產(chǎn)向社會公開招聘m個工種的工作人員，每個工種各有不同的編號(o，1，3，m一1)和計劃招聘人數(shù)，參加應(yīng)聘的人數(shù)有n個(編號為o，1，2，n一1)。每位應(yīng)聘者可以申報兩個工種，并參加公司組織的考試。公司將按應(yīng)聘者的成績，從高到低的順序排隊錄取。公司的錄取原則是：從高分到低分依次對每位應(yīng)聘者先按其第一志愿

4、錄??；當不能按第一志愿錄取時，便將他的成績扣去5分后，重新排隊并按其第二志愿考慮錄取。 實現(xiàn)要求：要求程序輸出每個工種錄用者的信息(編號、成績，以及落選者的信息(編號、成績)。 程序設(shè)計思路：程序中按應(yīng)聘者的成績從高到低的順序排隊錄取。如果在第一志愿隊列中落選，便將他的成績扣去5分后重新排隊，并按其第二志愿考慮錄取。程序為每個工種保留一個錄取者的有序隊列。錄取處理循環(huán)直至招聘額滿或已對全部應(yīng)聘者都做了錄用處理。6、求矩陣的所有馬鞍點。矩陣A中的元素若滿足：Ai,j是第i行中值最小的元素，且又是第j列中值最大的元素，則稱元素Ai,j為該矩陣的一個馬鞍點。求出m×n矩陣的所有馬鞍點。7、

5、最少換車次數(shù)問題。問題描述: 設(shè)某城市有n個車站，并有m條公交線路連接這些車站。設(shè)這些公交車都是單向的，這n個車站被順序編號為0-n-1。編號程序，輸入該城市的公交線路數(shù)，車站個數(shù)，以及各公交線路上的各站編號。 實現(xiàn)要求：求得從站0出發(fā)乘公交車至站n一1的最少換車次數(shù)。 程序設(shè)計思路：利用輸入信息構(gòu)建一張有向圖G(用鄰接短陣g表示)，有向圖的頂點是車站，若有某條公交線路經(jīng)i站能到達j站，就在頂點i到頂點j之間設(shè)置一條權(quán)為1的有向邊i,j)。這樣，從站x至站y的最少上車次數(shù)便對應(yīng)于圖G中從點x至點y的最短路徑長度。而程序要求的換車次數(shù)就是上車次數(shù)減1。8、實現(xiàn)： 拓撲排序9、圖的算法實現(xiàn)問題描述

6、：圖的存儲結(jié)構(gòu)的建立、Prim、Kruskal、Dijkstra和拓撲排序算法。實現(xiàn)要求：（1）將圖的信息建立文件；（2）從文件讀入圖的信息，建立鄰接矩陣和鄰接表；（3）實現(xiàn)Prim、Kruskal、Dijkstra和拓撲排序算法。10、實現(xiàn)二叉樹的葉子結(jié)點按從左到右的順序連成一個單鏈表請設(shè)計一個算法，把二叉樹的葉子結(jié)點按從左到右的順序連成一個單鏈表。二叉樹用二叉鏈存儲，鏈接時用葉子結(jié)點的rchild 域存放指針。11、模擬實現(xiàn)五子棋在圍棋比賽中，某一方（假設(shè)為黑方）在棋盤的某個位置（i，j）下子后，有可能提取對方（白方的一串子）。以W1919表示一個棋盤，若Wij=0表示在位置(i,j)上沒

7、有子，Wij=1表示該位置上的是黑子，Wij=-1表示該位置上是白子。模擬實現(xiàn)五子棋 過程。12、實現(xiàn)：判別給定的二叉樹是否為二叉排序樹。13、文章編輯問題描述：輸入一頁文字，程序可以統(tǒng)計出文字、數(shù)字、空格的個數(shù)。靜態(tài)存儲一頁文章，每行最多不超過80個字符，共N行；實現(xiàn)要求：（1）分別統(tǒng)計出其中英文字母數(shù)和空格數(shù)及整篇文章總字數(shù)；（2）統(tǒng)計某一字符串在文章中出現(xiàn)的次數(shù)，并輸出該次數(shù)；（3）刪除某一子串，并將后面的字符前移。存儲結(jié)構(gòu)使用線性表，分別用幾個子函數(shù)實現(xiàn)相應(yīng)的功能；輸入數(shù)據(jù)的形式和范圍：可以輸入大寫、小寫的英文字母、任何數(shù)字及標點符號。輸出形式：（1）分行輸出用戶輸入的各行字符；（2）

8、分4行輸出"全部字母數(shù)"、"數(shù)字個數(shù)"、"空格個數(shù)"、"文章總字數(shù)"（3）輸出刪除某一字符串后的文章14、實現(xiàn)：對一個存儲為鄰接表的圖，給出求其所有連通分量。15、管道鋪設(shè)設(shè)計問題描述：N(N>10)個居民區(qū)之間需要鋪設(shè)煤氣管道。假設(shè)任意兩個居民區(qū)之間都可以 鋪設(shè)煤氣管道，但代價不同。實現(xiàn)要求：事先任意兩居民區(qū)之間鋪設(shè)煤氣管道的代價存入磁盤文件中。設(shè)計一個最佳方案使得這N個居民區(qū)之間鋪設(shè)煤氣管道所需代價最小，并將結(jié)果以圖形方式在屏幕上輸出。16、排序算法的實現(xiàn)與比較問題描述：編程實現(xiàn)希爾、快速排序算法，并利用

9、程序統(tǒng)計每種算法的執(zhí)行時間。實現(xiàn)要求：隨機產(chǎn)生10000、50000、 100000、 200000個待排數(shù)據(jù)存入磁盤文件，從磁盤文件讀入待排數(shù)據(jù)進行排序，并將排序結(jié)果寫入另一個文件中。17、實現(xiàn)排序：設(shè)一單向鏈表的頭指針為head,鏈表的記錄中包含著整數(shù)類型的key域,試設(shè)計算法,將此鏈表的記錄按照key遞增的次序進行就地排序.（不允許使用數(shù)組做輔助存儲）18、統(tǒng)計C程序單詞的個數(shù)問題描述：掃描c源程序，利用hash技術(shù)和二分查找技術(shù)統(tǒng)計該源程序中的關(guān)鍵字出現(xiàn)的頻度，并比較各自查找的次數(shù)。實現(xiàn)要求：（1）、先用Hash表存儲c語言中32個關(guān)鍵字，再掃描c源程序取出每個單詞，利用Hash查找技

10、術(shù)統(tǒng)計該程序中的關(guān)鍵字出現(xiàn)的頻度。發(fā)生Hash沖突用線性探測法解決。設(shè)Hash函數(shù)為：Hash（key）=(key的第一個字母序號)*100+(key的最后一個字母序號) MOD 41。（2）、用順序表存儲c語言中的關(guān)鍵字，把c源程序取出每個單詞利用二分查找技術(shù)統(tǒng)計該程序中的關(guān)鍵字的出現(xiàn)頻度。19、擦數(shù)游戲在黑板上從1開始寫出一組連續(xù)的自然數(shù)，然后擦去其中的一個數(shù)k，其余的數(shù)的平均值為a/b(a,b為整數(shù))。試編寫程序求出被擦去的數(shù)k。20、醫(yī)院選址問題描述：有n個村莊，現(xiàn)要從這n個村莊中選擇一個村莊新建一所醫(yī)院，使其余的村莊到這所醫(yī)院的距離總體來說較短，設(shè)計較合理。實現(xiàn)要求：可以將問題抽象為

11、有n個接點，在這n個接點之間建立一個無向圖，邊上的權(quán)值w(i,j)表示村莊i到j(luò)之間道路的長度， 在無向圖中n個頂點之間，最多可能設(shè)置n(n-1)/2條線路，如何在這些線路中選擇n-1條線路，以使總的線路最短？對于n個頂點的連通網(wǎng)可以建立許多不同的無向圖，每一個無向圖都可以表示一個道路網(wǎng)，其中要選擇一個最優(yōu)圖，使圖上各邊之小。21、求二叉樹根結(jié)點到指定結(jié)點的路徑。22、保齡球記分系統(tǒng) 問題描述：保齡球一局分10輪，每輪可按球一次或多次，以擊倒的球數(shù)為依據(jù)得分。一局得分為10輪得分之和，而每輪的得分不僅與本輪滾球情況有關(guān)，還可能與后續(xù)一兩輪的滾球情況有關(guān)。即某輪某次滾球擊例的球數(shù)不僅要記入本輪得

12、分，還可能記入前一兩輪得分。具體的滾球規(guī)則和記分規(guī)則如下。 (1)若一輪的第一次該球就擊倒10個球，則本輪不再滾球(若是第10輪則還需另加兩次滾球)，該輪的得分為本次擊倒球數(shù)10與以后兩次滾球所擊倒的球數(shù)之和。 (2)若某一輪的第一次滾球未擊倒10個球，則可對剩下的球再擊一次。如果兩次擊倒10個球，則本輪不再滾球(若是第10輪則還需另加一次滾球)，該輪的得分為本次擊倒球數(shù)10與下一次滾球所擊倒的球數(shù)之和。 (3)若某一輪的兩次滾球未擊倒10個球，則本輪不再滾球。該輪的得分為本輪擊倒的球數(shù)。 實現(xiàn)要求：程序要求輸出10輪中各輪的第一次得分和第二次得分，以及各輪得分和總分。 程序設(shè)計思想 程序交互

13、地逐輪輸入一次滾球擊倒的球數(shù)ball1和ball2，計算該輪得分score和累計得分total。為記錄因一輪擊倒10個球，還暫時不能計算該輪的得分和累計總分的情況，程序引入變量frame，用來記錄當前已完成完整計算的輪次，程序每輸入一次滾球擊倒球數(shù)，就檢查還未完成完整計算的輪次，并計算之。23、修改起泡排序試修改起泡排序，以交替的正、反兩個方向進行掃描。即第一趟把排序碼最大的記錄放到最末尾，第二趟把排序碼最小的記錄放到最頭上。如此反復(fù)進行。24、運動會分數(shù)統(tǒng)計：問題描述：參加運動會有n個學(xué)校，學(xué)校編號為1n。比賽分成m個男子項目，和w個女子項目。項目編號為男子1m，女子m+1m+w。不同的項目

14、取前五名或前三名積分；取前五名的積分分別為：7、5、3、2、1，前三名的積分分別為：5、3、2；哪些取前五名或前三名由學(xué)生自己設(shè)定。（m<=20,n<=20）實現(xiàn)要求：1). 可以輸入各個項目的前三名或前五名的成績；2)能統(tǒng)計各學(xué)?？偡郑?)可以按學(xué)校編號、學(xué)校總分、男女團體總分排序輸出；4).可以按學(xué)校編號查詢學(xué)校某個項目的情況；可以按項目編號查詢?nèi)〉们叭蚯拔迕膶W(xué)校。規(guī)定：輸入數(shù)據(jù)形式和范圍：20以內(nèi)的整數(shù)（如果做得更好可以輸入學(xué)校的名稱，運動項目的名稱）25、堆排序的實現(xiàn)：在順序結(jié)構(gòu)上完成,先建堆然后重建堆,最后實現(xiàn)全部排序26、公園的導(dǎo)游圖問題描述：給出一張某公園的導(dǎo)游圖

15、，游客通過終端詢問可知：從某一景點到另一景點的最短路徑。游客從公園大門進入，選一條最佳路線，使游客可以不重復(fù)地游覽各景點，最后回到出口（出口就在入口旁邊）。實現(xiàn)要求：1 初步完成總體設(shè)計，搭好框架，確定人機對話的界面，確定函數(shù)個數(shù)；2 完成最低要求：建立一個文件，包括5個景點情況，能完成遍歷功能；3 進一步要求：進一步擴充景點數(shù)目，畫出景點圖，有興趣的同學(xué)可以自己擴充系統(tǒng)功能。27、萬年歷：通過給定的年，求該年的日歷，閏年算法：Y%4 &&!Y%100|Y%4000 28、歸并排序算法：用兩路歸并算法，實現(xiàn)N個無素的排序29、學(xué)籍管理 對學(xué)生、課程、成績分別建立三個數(shù)據(jù)文件（學(xué)

16、生、課程、成績屬性自定）。查詢某個學(xué)生的選課情況成績不及格的學(xué)生情況對課程名按不及格學(xué)生人數(shù)進行排序建立模擬索引。30、最短路徑：求圖中任意兩點間的最短路徑 31、旅游交通查詢系統(tǒng)：實現(xiàn)功能：火車信息查詢、最短路徑查詢、火車信息編輯、讀入修改信息、查看火車信息、查看城市信息。每個功能中又有一些小功能，如火車信息查詢中有：按車次查詢、按出發(fā)地與目的地查詢（其中又有最快、最省錢、全部選擇）中轉(zhuǎn)站查詢、查看火車信息，火車信息編輯又包括：添加火車信息、刪除火車信息、查看火車信息、保存火車信息功能。32、房產(chǎn)信息管理 自己建立數(shù)據(jù)文件的方式對房產(chǎn)信息進行如下管理：查詢修改排序33、供貨信息管理自己建立數(shù)

17、據(jù)文件的方式對供貨信息進行如下管理：查詢修改排序。商店貨架以棧的形式擺放商品，生產(chǎn)日期越近的越靠近棧底,出棧是從棧頂取貨，一天營業(yè)結(jié)束，如果貨架不滿,則需上貨，如果直接將商品擺放到貨架上，則會使生產(chǎn)日期越近的越靠近棧頂.這就需要倒貨架，仍使生產(chǎn)日期越近的越靠近棧底。寫出貨物進棧、出棧算法。34、銀行業(yè)務(wù)模擬問題描述： 客戶業(yè)務(wù)分為兩種。第一種是申請從銀行得到一筆資金，即取款或借款。第二種是向銀行投入一筆資金，即存款或還款。銀行有兩個服務(wù)窗口，相應(yīng)的有兩個隊列?？蛻舻竭_銀行后先排第一個隊。處理每個客戶業(yè)務(wù)時，如果屬于第一種，且申請額超出銀行現(xiàn)存資金總額而得不到滿足，則立即排入第二隊等候，直至滿足

18、時才離開銀行，否則業(yè)務(wù)處理完后立即離開銀行。每接待完一個第二種業(yè)務(wù)的客戶，則順序檢查和處理（如果可能）第二個隊列的客戶，對能滿足的申請者予以滿足，不能滿足者重新排到第二個隊列的隊尾。注意，在此檢查過程中，一旦銀行資金總額少于或等于剛才第一個隊列中最后一個客戶（第二種業(yè)務(wù)）被接待之前的數(shù)額，或者本次已將第二個隊列檢查或處理了一遍，就停止檢查（因為此時已不可能還有能滿足者）轉(zhuǎn)而繼續(xù)接待第一個隊列的客戶。任何時刻都只開一個窗口。假設(shè)檢查不需要時間。營業(yè)時間結(jié)束時所有客戶立即離開銀行。寫一個上述銀行業(yè)務(wù)的事件驅(qū)動模擬系統(tǒng)，通過模擬方法求出客戶在銀行內(nèi)逗留的平均時間。 35、航空訂票系統(tǒng)：通過此系統(tǒng)可以

19、實現(xiàn)如下功能： 1、錄入航線信息每條航線信息包括航班號、飛機號、目的地、訂票數(shù)、余票數(shù)共5項。假設(shè)現(xiàn)在有3條航線, 目的地分別是北京, 上海, 廣州, 飛機上可乘坐100人( 即初始訂票數(shù)為0, 余票數(shù)為100) , 將這3條航線信息存入文件中。 2、訂票業(yè)務(wù)客戶信息包括姓名, 航班號, 座位號(初始為0), 假設(shè)已有3個客戶信息存入文件中。3、退票業(yè)務(wù)根據(jù)客戶提出的航班號, 辦理退票, 并刪除該客戶的信息, 并修改相應(yīng)航線的訂票數(shù)和余票數(shù)。4、修改航班信息：當航班信息改變可以修改航班數(shù)據(jù)文件。5、輸出全部航線信息和全部客戶信息。6、退出系統(tǒng)。 36、24點游戲：基本要求及步驟： 1、 隨機產(chǎn)

20、生四個1-13的數(shù)，分別代表13張牌。 2、 提示玩家輸入算式。 3、 判斷玩家輸入的表達式是否合法，其中算式中的四個數(shù)字只能是程序所給的四個數(shù)字，非法則回到1）。 4、 如果玩家認為這四張牌算不出24點（如：1，1，1，1），可只輸入？，程序?qū)⑴袛噙@四張牌是否能得出24點，如果能，則程序?qū)⒔o出算式，如果不能，說明不能，并回到1）。 5、 當用戶正確輸入算式后，用“堆棧來求表達式的值”的原理 求出結(jié)果并判斷是否為24，得出用戶是輸是贏的結(jié)果。 6、 詢問用戶是否繼續(xù)，是則回到1），否則結(jié)束程序。37、工資管理 自己建立數(shù)據(jù)文件（提示可建立：職工、工資級別、職工工資）完成：查詢職工的平均工資查詢

21、某一級別人員的平均工資普調(diào)工資將職工姓名按工資額度進行排序38、 一元多項式計算任務(wù)：能夠按照指數(shù)降序排列建立并輸出多項式；能夠完成兩個多項式的相加、相減，并將結(jié)果輸入；39、 猴子選大王任務(wù)：一堆猴子都有編號，編號是1，2，3 .m ,這群猴子（m個）按照1-m的順序圍坐一圈，從第1開始數(shù)，每數(shù)到第N個，該猴子就要離開此圈，這樣依次下來，直到圈中只剩下最后一只猴子，則該猴子為大王。要求：輸入數(shù)據(jù)：輸入m,n m,n 為整數(shù)，n<m輸出形式：中文提示按照m個猴子，數(shù)n 個數(shù)的方法，輸出為大王的猴子是幾號 ，建立一個函數(shù)來實現(xiàn)此功能40、 joseph環(huán) 任務(wù)：編號是1，2，,n的n個人按

22、照順時針方向圍坐一圈，每個人只有一個密碼（正整數(shù)）。一開始任選一個正整數(shù)作為報數(shù)上限值m,從第一個人開始順時針方向自1開始順序報數(shù)，報到m時停止報數(shù)。報m的人出列，將他的密碼作為新的m值，從他在順時針方向的下一個人開始重新從1報數(shù)，如此下去，直到所有人全部出列為止。設(shè)計一個程序來求出出列順序。要求：利用單向循環(huán)鏈表存儲結(jié)構(gòu)模擬此過程，按照出列的順序輸出各個人的編號。41、 紙牌游戲任務(wù)：編號為1-52張牌，正面向上，從第2張開始，以2為基數(shù)，是2的倍數(shù)的牌翻一次，直到最后一張牌；然后，從第3張開始，以3為基數(shù)，是3的倍數(shù)的牌翻一次，直到最后一張牌；然后從第4張開始，以4為基數(shù)，是4的倍數(shù)的牌翻

23、一次， 直到最后一張牌；.再依次5的倍數(shù)的牌翻一次，6的，7的 直到 以52為基數(shù)的 翻過，輸出：這時正面向上的牌有哪些？42、迷宮求解在迷宮中求一條路徑的算法，基本思想：若當前、位置可通過，則壓入棧中，否則探索下一位置，若走不通，則回溯，迷宮大小：M*N。迷宮設(shè)置自定義。43、內(nèi)存分配算法：利用靜態(tài)鏈表，模擬實現(xiàn)內(nèi)存分配 二. 要求：1、 對相應(yīng)的題目進行算法設(shè)計2、 編寫源代碼3、 上機調(diào)試4、 顯示調(diào)試結(jié)果5、寫出實驗總結(jié)三課程設(shè)計進度安排設(shè)計總學(xué)時為2周課程設(shè)計大體分五個階段:1、選題與搜集資料:每人選擇相應(yīng)題目,進行課程設(shè)計課題的資料搜集.2、分析與概要設(shè)計:根據(jù)搜集的資料,進行程序功能與數(shù)據(jù)結(jié)構(gòu)分析,并選擇合適的數(shù)據(jù)結(jié)構(gòu),并在此基礎(chǔ)上進行實現(xiàn)程序功能的算法設(shè)計.3、程序設(shè)計:運用掌握C語言編寫程序,實現(xiàn)所程序的各個模塊功能.4、調(diào)試與測試:自行調(diào)試程序,成員交叉測試程序,并記錄測試情況.5、實習(xí)報告:編寫實習(xí)報告6、驗收與評分:指導(dǎo)教師對每個小組的開發(fā)的