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

數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)任務(wù)書一、選題選題原則是數(shù)據(jù)結(jié)構(gòu)算法實(shí)現(xiàn)及在具體問題中的應(yīng)用?？蛇x擇下列與實(shí)際應(yīng)用緊密結(jié)合的較綜合性的題目，也可自選（自選題必須通過任課教師認(rèn)可）。要求通過課程設(shè)計(jì)的實(shí)踐，在數(shù)據(jù)結(jié)構(gòu)的表示、數(shù)據(jù)結(jié)構(gòu)的選擇及應(yīng)用、算法設(shè)計(jì)與實(shí)現(xiàn)等方面加深對數(shù)據(jù)結(jié)構(gòu)課程基本內(nèi)容的理解和綜合運(yùn)用能力的提高。對下列題目每個同學(xué)的課設(shè)任務(wù)按下式確定： 按宿舍，每兩個宿舍同學(xué)組成一小組，共同完成一個任務(wù)數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)任務(wù)書1題目： 學(xué)生運(yùn)動會成績數(shù)據(jù)庫功能：學(xué)生運(yùn)動會成績數(shù)據(jù)庫系統(tǒng)記錄某校運(yùn)動會上全部運(yùn)動項(xiàng)目，各系獲得的分?jǐn)?shù)及排名的情況，包括50、100、200，400，1500米，跳高，跳遠(yuǎn)，標(biāo)槍，鉛球鐵餅等。進(jìn)入系統(tǒng)后可以輸入和修改某個項(xiàng)目的結(jié)果情況，可以按各系院編號輸出總分；按總分排序；按男團(tuán)體總分排序 ；按系院編號查詢；按項(xiàng)目編號查詢；按女團(tuán)體總分排序。分步實(shí)施：1） 初步完成總體設(shè)計(jì)，搭好框架，確定人機(jī)對話的界面，確定函數(shù)個數(shù)；2） 完成最低要求：建立一個文件，包括某個系，5個項(xiàng)目的得分情況，能對文件中的信息進(jìn)行擴(kuò)充（追加），修改和刪除；3） 進(jìn)一步要求：完成對多個系，多個項(xiàng)目的得分排序，以及完成系統(tǒng)查詢功能。有興趣的同學(xué)可以自己擴(kuò)充系統(tǒng)功能。鍵盤輸入：系院數(shù)目，男子項(xiàng)目數(shù)女子項(xiàng)目數(shù)，（每項(xiàng)目取前三名，分別為10，5，2分）要求：1）界面友好，函數(shù)功能要劃分好2）總體設(shè)計(jì)應(yīng)畫一流程圖3）程序要加必要的注釋4） 要提供程序測試方案5） 程序一定要經(jīng)得起測試，寧可功能少一些，也要能運(yùn)行起來，不能運(yùn)行的程序是沒有價值的。 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)任務(wù)書2題目： 哈夫曼樹應(yīng)用功能： 1從終端讀入字符集大小n，以及n個字符和n個權(quán)值，建立哈夫曼樹并將它存于文件hfmTree中.將已在內(nèi)存中的哈夫曼樹以直觀的方式（比如樹）顯示在終端上；2利用已經(jīng)建好的哈夫曼樹（如不在內(nèi)存，則從文件htmTree中讀入），對文件ToBeTran中的正文進(jìn)行編碼，然后將結(jié)果存入文件CodeFile中，并輸出結(jié)果，將文件CodeFile以緊湊格式先是在終端上，每行50個代碼。同時將此字符形式的編碼文件寫入文件CodePrint中。3利用已建好的哈夫曼樹將文件CodeFile中的代碼進(jìn)行譯碼，結(jié)果存入文件TextFile中，并輸出結(jié)果。分步實(shí)施：1） 初步完成總體設(shè)計(jì)，搭好框架，確定人機(jī)對話的界面，確定函數(shù)個數(shù)；2） 完成最低要求：完成功能1；3） 進(jìn)一步要求：完成功能2和3。有興趣的同學(xué)可以自己擴(kuò)充系統(tǒng)功能。要求：1）界面友好，函數(shù)功能要劃分好2）總體設(shè)計(jì)應(yīng)畫一流程圖3）程序要加必要的注釋4） 要提供程序測試方案5） 程序一定要經(jīng)得起測試，寧可功能少一些，也要能運(yùn)行起來，不能運(yùn)行的程序是沒有價值的。 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)任務(wù)書3題目：圖的遍歷功能：實(shí)現(xiàn)圖的深度優(yōu)先, 廣度優(yōu)先遍歷算法，并輸出原圖結(jié)構(gòu)及遍歷結(jié)果。分步實(shí)施：1) 初步完成總體設(shè)計(jì)，搭好框架；2) 完成最低要求：兩種必須都要實(shí)現(xiàn)，寫出畫圖的思路；3) 進(jìn)一步要求：畫出圖的結(jié)構(gòu)，有興趣的同學(xué)可以進(jìn)一步改進(jìn)圖的效果。要求：1）界面友好，函數(shù)功能要劃分好2）總體設(shè)計(jì)應(yīng)畫一流程圖3）程序要加必要的注釋4) 要提供程序測試方案5) 程序一定要經(jīng)得起測試，寧可功能少一些，也要能運(yùn)行起來，不能運(yùn)行的程序是沒有價值的。 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)任務(wù)書4題目： n維矩陣乘法：A B1功能：設(shè)計(jì)一個矩陣相乘的程序，首先從鍵盤輸入兩個矩陣a，b的內(nèi)容，并輸出兩個矩陣，輸出ab1結(jié)果。分步實(shí)施：1） 初步完成總體設(shè)計(jì)，搭好框架，確定人機(jī)對話的界面，確定函數(shù)個數(shù)；2） 完成最低要求：建立一個文件，可完成2維矩陣的情況；3） 一步要求：通過鍵盤輸入維數(shù)n。有興趣的同學(xué)可以自己擴(kuò)充系統(tǒng)功能。要求：1）界面友好，函數(shù)功能要劃分好2）總體設(shè)計(jì)應(yīng)畫一流程圖3）程序要加必要的注釋4）要提供程序測試方案5）程序一定要經(jīng)得起測試，寧可功能少一些，也要能運(yùn)行起來，不能運(yùn)行的程序是沒有價值的。 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)任務(wù)書5題目： 數(shù)組應(yīng)用功能： 按照行優(yōu)先順序?qū)⑤斎氲臄?shù)據(jù)建成4維數(shù)組，再按照列優(yōu)先順序輸出結(jié)果，給出任意處的元素值，并給出對應(yīng)的一維數(shù)組中的序號。分步實(shí)施：1初步完成總體設(shè)計(jì)，搭好框架，確定人機(jī)對話的界面，確定函數(shù)個數(shù)；2 完成最低要求：完成第一個功能；3 進(jìn)一步要求：進(jìn)一步完成后續(xù)功能。有興趣的同學(xué)可以自己擴(kuò)充系統(tǒng)功能。要求：1）界面友好，函數(shù)功能要劃分好2）總體設(shè)計(jì)應(yīng)畫一流程圖3）程序要加必要的注釋4）要提供程序測試方案5）程序一定要經(jīng)得起測試，寧可功能少一些，也要能運(yùn)行起來，不能運(yùn)行的程序是沒有價值的。 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)任務(wù)書6題目： 數(shù)組應(yīng)用2功能： 讀入數(shù)組下標(biāo)，求出數(shù)組A靠邊元素之和；求從A00開始的互不相鄰的各元素之和；當(dāng)m=n時，分別求兩條對角線上的元素之和，否則打印出m!=n的信息。分步實(shí)施：1 初步完成總體設(shè)計(jì)，搭好框架，確定人機(jī)對話的界面，確定函數(shù)個數(shù)；2 完成最低要求：求出2維數(shù)組的功能；3 進(jìn)一步要求：完成3維以上數(shù)組的功能。有興趣的同學(xué)可以自己擴(kuò)充系統(tǒng)功能。要求：1）界面友好，函數(shù)功能要劃分好2）總體設(shè)計(jì)應(yīng)畫一流程圖3）程序要加必要的注釋4）要提供程序測試方案5）程序一定要經(jīng)得起測試，寧可功能少一些，也要能運(yùn)行起來，不能運(yùn)行的程序是沒有價值的。 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)任務(wù)書7題目：n元多項(xiàng)式乘法功能： 完成兩個n元多項(xiàng)式作乘法，給出明確的等式形式。分步實(shí)施：1 初步完成總體設(shè)計(jì)，搭好框架，確定人機(jī)對話的界面，確定函數(shù)個數(shù)；2 完成最低要求：建立一個文件，實(shí)現(xiàn)兩個一元二次多項(xiàng)式作乘法。3 進(jìn)一步要求：實(shí)現(xiàn)三元二次多項(xiàng)式的乘法。有興趣的同學(xué)可以自己擴(kuò)充系統(tǒng)功能。要求：1）界面友好，函數(shù)功能要劃分好2）總體設(shè)計(jì)應(yīng)畫一流程圖3）程序要加必要的注釋4）要提供程序測試方案5）程序一定要經(jīng)得起測試，寧可功能少一些，也要能運(yùn)行起來，不能運(yùn)行的程序是沒有價值的。 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)任務(wù)書8題目： 集合運(yùn)算功能： 使用鏈表來表示集合，完成集合的合并，求交集等操作。分步實(shí)施：1 初步完成總體設(shè)計(jì)，搭好框架，確定人機(jī)對話的界面，確定函數(shù)個數(shù)；2 完成最低要求： 3 進(jìn)一步要求： 要求：1）界面友好，函數(shù)功能要劃分好2）總體設(shè)計(jì)應(yīng)畫一流程圖3）程序要加必要的注釋4）要提供程序測試方案6） 程序一定要經(jīng)得起測試，寧可功能少一些，也要能運(yùn)行起來，不能運(yùn)行的程序是沒有價值的。 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)任務(wù)書9題目： 公園的導(dǎo)游圖功能：給出一張某公園的導(dǎo)游圖，游客通過終端詢問可知：從某一景點(diǎn)到另一景點(diǎn)的最短路徑。游客從公園大門進(jìn)入，選一條最佳路線，使游客可以不重復(fù)地游覽各景點(diǎn)，最后回到出口（出口就在入口旁邊）。分步實(shí)施：1 初步完成總體設(shè)計(jì)，搭好框架，確定人機(jī)對話的界面，確定函數(shù)個數(shù)；2 完成最低要求：建立一個文件，包括5個景點(diǎn)情況，能完成遍歷功能；3 進(jìn)一步要求：進(jìn)一步擴(kuò)充景點(diǎn)數(shù)目，畫出景點(diǎn)圖，有興趣的同學(xué)可以自己擴(kuò)充系統(tǒng)功能。要求：1）界面友好，函數(shù)功能要劃分好2）總體設(shè)計(jì)應(yīng)畫一流程圖3）程序要加必要的注釋4）要提供程序測試方案5）程序一定要經(jīng)得起測試，寧可功能少一些，也要能運(yùn)行起來，不能運(yùn)行的程序是沒有價值的。 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)任務(wù)書10題目： 商店存貨管理系統(tǒng)功能：建立一商店存貨管理系統(tǒng)，要求每次出貨時取進(jìn)貨時間最早且最接近保質(zhì)期中止時間的貨物。分步實(shí)施：1 初步完成總體設(shè)計(jì)，搭好框架，確定人機(jī)對話的界面，確定函數(shù)個數(shù)；2 完成最低要求：建立一個文件，包括5個種類的貨物情況，能對商品信息進(jìn)行擴(kuò)充（追加），修改和刪除以及簡單的排序；3 進(jìn)一步要求：擴(kuò)充商品數(shù)量，以及完成系統(tǒng)查詢功能。有興趣的同學(xué)可以自己擴(kuò)充系統(tǒng)功能。要求：1）界面友好，函數(shù)功能要劃分好2）總體設(shè)計(jì)應(yīng)畫一流程圖3）程序要加必要的注釋4）要提供程序測試方案5）程序一定要經(jīng)得起測試，寧可功能少一些，也要能運(yùn)行起來，不能運(yùn)行的程序是沒有價值的。數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)任務(wù)書11題目： 漢諾威塔功能：編程序顯示n（n0)個人按順時針方向圍坐一圈，每個人持有一個正整數(shù)密碼。開始時任選一個正整數(shù)做為報數(shù)上限m，從第一個人開始順時針方向自1起順序報數(shù)，報到m是停止報數(shù)，報m的人出列，將他的密碼作為新的m值，從他的下一個人開始重新從1報數(shù)。如此下去，直到所有人全部出列為止。令n最大值取30。要求設(shè)計(jì)一個程序模擬此過程，求出出列編號序列。分步實(shí)施：4 初步完成總體設(shè)計(jì)，搭好框架，確定人機(jī)對話的界面，確定函數(shù)個數(shù)；5 完成最低要求：建立一個文件，包括某人5個人的情況。6 進(jìn)一步要求：有興趣的同學(xué)可以自己擴(kuò)充系統(tǒng)功能。要求：1）界面友好，函數(shù)功能要劃分好2）總體設(shè)計(jì)應(yīng)畫一流程圖3）程序要加必要的注釋4）要提供程序測試方案5) 程序一定要經(jīng)得起測試，寧可功能少一些，也要能運(yùn)行起來，不能運(yùn)行的程序是沒有價值的。任務(wù)書1的【測試數(shù)據(jù)】 用下表給出的字符集和頻度的實(shí)際統(tǒng)計(jì)數(shù)據(jù)建立哈夫曼樹，并實(shí)現(xiàn)以下報文的編碼和譯碼：“THIS PROGRAM IS MY FAVORITE”字符A B C D E F G H I J K L M頻度64 13 22 32 103 21 15 47 57 1 5 32 20字符N O P Q R S T U V W X Y Z頻度57 63 15 1 48 51 80 23 8 18 1 16 1二、課程設(shè)計(jì)報告要求完成設(shè)計(jì)任務(wù)后，應(yīng)按要求提交課程設(shè)計(jì)報告。課程設(shè)計(jì)報告可采用統(tǒng)一規(guī)范的稿紙書寫，也可以用16k紙單面打印，并裝訂成冊。內(nèi)容包括：1. 設(shè)計(jì)題目、專業(yè)、班級、學(xué)生姓名、學(xué)生學(xué)號、指導(dǎo)教師姓名、起止時間2. 具體任務(wù)3. 軟