數(shù)據(jù)結(jié)構(gòu)專業(yè)課程設(shè)計(jì)題目

數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)一、教學(xué)目標(biāo)和要求為了配合《數(shù)據(jù)結(jié)構(gòu)》課程教學(xué)，使學(xué)生能更深刻地領(lǐng)會(huì)《數(shù)據(jù)結(jié)構(gòu)》這門課程關(guān)鍵性，特開設(shè)此課程設(shè)計(jì)；編寫部分在特定數(shù)據(jù)結(jié)構(gòu)上算法，經(jīng)過(guò)上機(jī)調(diào)試，愈加好掌握多種數(shù)據(jù)結(jié)構(gòu)及其特點(diǎn)，同時(shí)提升處理計(jì)算機(jī)應(yīng)用實(shí)際問(wèn)題能力。二、課程設(shè)計(jì)要求1、選好題目：每題一人，每班每個(gè)題目最多許可三人選做，必需確保每題有兩人選做，學(xué)習(xí)委員將選題情況先統(tǒng)計(jì)上交。2、獨(dú)立思索，獨(dú)立完成：課程設(shè)計(jì)中各任務(wù)設(shè)計(jì)和調(diào)試要求獨(dú)立完成，碰到問(wèn)題能夠討論，但不能夠拷貝。相同題目標(biāo)同學(xué)，算法思緒能夠相同，不過(guò)程序和課設(shè)匯報(bào)不能相同。3、做好上機(jī)準(zhǔn)備：每次上機(jī)前，要事先編制好準(zhǔn)備調(diào)試程序，認(rèn)真想好調(diào)試步驟和相關(guān)環(huán)境設(shè)置方法，準(zhǔn)備好相關(guān)文件。4、設(shè)計(jì)關(guān)鍵點(diǎn)：⑴需求分析：在該部分中敘述總共多個(gè)模塊，每個(gè)模塊功效要求。⑵系統(tǒng)設(shè)計(jì)總體設(shè)計(jì)：定義某個(gè)數(shù)據(jù)結(jié)構(gòu)抽象數(shù)據(jù)類型及其它算法功效說(shuō)明。具體設(shè)計(jì)：在此定義存放結(jié)構(gòu)，每個(gè)部分算法設(shè)計(jì)說(shuō)明（提議描述算法采取步驟圖）。⑶編碼實(shí)現(xiàn)各個(gè)算法實(shí)現(xiàn)源程序，對(duì)每個(gè)題目要有對(duì)應(yīng)源程序（每個(gè)功效模塊采取不一樣函數(shù)實(shí)現(xiàn)）。源程序要根據(jù)程序規(guī)則來(lái)編寫，要結(jié)構(gòu)清楚，關(guān)鍵函數(shù)關(guān)鍵變量，關(guān)鍵功效部分要加上清楚程序注釋。程序能夠運(yùn)行，要有基礎(chǔ)容錯(cuò)功效，盡可能避免出現(xiàn)操作失誤時(shí)出現(xiàn)死循環(huán)。⑷調(diào)試分析給出實(shí)現(xiàn)功效一組或多組測(cè)試數(shù)據(jù)，程序調(diào)試后，將根據(jù)此測(cè)試數(shù)據(jù)進(jìn)行測(cè)試結(jié)果列出來(lái)。時(shí)間復(fù)雜度分析，每個(gè)模塊設(shè)計(jì)和調(diào)試時(shí)存在問(wèn)題思索（問(wèn)題是哪些？問(wèn)題怎樣處理？），算法改善設(shè)想。⑸課設(shè)總結(jié)：課程設(shè)計(jì)過(guò)程收獲、碰到問(wèn)題、碰到問(wèn)題處理問(wèn)題過(guò)程思索、程序調(diào)試能力思索、對(duì)數(shù)據(jù)結(jié)構(gòu)這門課程思索、在課程設(shè)計(jì)過(guò)程中對(duì)《數(shù)據(jù)結(jié)構(gòu)》課程認(rèn)識(shí)等內(nèi)容。5、實(shí)現(xiàn)結(jié)果必需進(jìn)行檢驗(yàn)和演示；程序源代碼和程序說(shuō)明文件必需上交，作為考評(píng)內(nèi)容一部分；（上交時(shí)文件夾取名規(guī)則為：“課設(shè)題目（***設(shè)計(jì)完成）”，如“資源管理系統(tǒng)設(shè)計(jì)和實(shí)現(xiàn)（張三設(shè)計(jì)完成）”。該文件夾下包含三個(gè)目錄：“源代碼”、“可實(shí)施文件”、“張三_課程設(shè)計(jì)匯報(bào)”。由學(xué)習(xí)委員按要求時(shí)間統(tǒng)一上交）。6、匯報(bào)提交時(shí)間:待定。形式:紙介質(zhì)(要求B5紙張打印，加封皮)和電子文檔。三、考評(píng)方法和內(nèi)容依據(jù)課程設(shè)計(jì)過(guò)程中學(xué)生學(xué)生態(tài)度、題目完成情況、課程設(shè)計(jì)匯報(bào)書質(zhì)量和回復(fù)問(wèn)題情況等根據(jù)10%、40%、30%、20%加權(quán)綜合打分。成績(jī)?cè)u(píng)定實(shí)施優(yōu)異、良好、中等、及格和不及格五個(gè)等級(jí)。評(píng)分標(biāo)準(zhǔn)：優(yōu)異：答辯+匯報(bào)優(yōu)異良好：答辯+匯報(bào)通?；騾R報(bào)優(yōu)異+沒(méi)答辯中等：答辯+匯報(bào)稍差或匯報(bào)通常+沒(méi)答辯及格：匯報(bào)稍差+沒(méi)答辯或答辯但被發(fā)覺不是自己編寫實(shí)現(xiàn)不及格：匯報(bào)幾乎全部是代碼或類同部分達(dá)成70%課設(shè)匯報(bào)裝訂次序以下：封面-----任務(wù)書-----目錄-----設(shè)計(jì)任務(wù)-----需求分析-----系統(tǒng)設(shè)計(jì)-----編碼實(shí)現(xiàn)-----調(diào)試分析-----課設(shè)總結(jié)-----謝辭-----參考文件-----附錄（可選）等；匯報(bào)總頁(yè)數(shù)控制在10±2頁(yè)內(nèi)，匯報(bào)中不能全是代碼，匯報(bào)中代碼控制在150行內(nèi)。四、課程設(shè)計(jì)題目1、運(yùn)動(dòng)會(huì)分?jǐn)?shù)統(tǒng)計(jì)2、集合并、交和差運(yùn)算程序3、長(zhǎng)整數(shù)加法運(yùn)算4、一元多項(xiàng)式計(jì)算器5、車廂調(diào)度問(wèn)題6、文章編輯7、識(shí)別廣義表頭或尾演示8、哈夫曼樹及其編碼9、校園導(dǎo)游咨詢10、地圖著色問(wèn)題11、內(nèi)部排序算法比較12、哈希表設(shè)計(jì)和實(shí)現(xiàn)13、火車售票系統(tǒng)14、圖書管理系統(tǒng)15、用戶消費(fèi)積分管理系統(tǒng)16、產(chǎn)品進(jìn)銷存管理系統(tǒng)五、數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)具體內(nèi)容要求：全部采取數(shù)據(jù)結(jié)構(gòu)課程中線性結(jié)構(gòu)、樹型結(jié)構(gòu)、圖型結(jié)構(gòu)、集合結(jié)構(gòu)中一個(gè)，不能用數(shù)據(jù)庫(kù)。1、運(yùn)動(dòng)會(huì)分?jǐn)?shù)統(tǒng)計(jì)問(wèn)題描述：參與運(yùn)動(dòng)會(huì)n個(gè)學(xué)校編號(hào)為1～n。比賽分成m個(gè)男子項(xiàng)目和w個(gè)女子項(xiàng)目，項(xiàng)目編號(hào)分別為1～m和m+1～m＋w。因?yàn)楦黜?xiàng)目參與人數(shù)差異較大，有些項(xiàng)目取前五名，得分次序?yàn)?，5，3，2，1；還有些項(xiàng)目只取前三名，得分次序?yàn)?，3，2。寫一個(gè)統(tǒng)計(jì)程序產(chǎn)生多種成績(jī)單和得分報(bào)表?；A(chǔ)要求：⑴每個(gè)項(xiàng)目結(jié)束時(shí)，輸入前三名或前五名項(xiàng)目編號(hào)、運(yùn)動(dòng)員姓名、校名和名次（成績(jī)）；⑵產(chǎn)生各學(xué)校成績(jī)單，內(nèi)容包含各學(xué)校所取得每項(xiàng)成績(jī)項(xiàng)目號(hào)、名次（成績(jī)）、姓名和得分，并統(tǒng)計(jì)各學(xué)?？偡郑虎钱a(chǎn)生團(tuán)體總分報(bào)表，內(nèi)容包含校號(hào)、男子團(tuán)體總分、女子團(tuán)體總分和團(tuán)體總分。2、集合并、交和差運(yùn)算程序問(wèn)題描述：編制一個(gè)能演示實(shí)施集合并、交和差運(yùn)算程序?；A(chǔ)要求：⑴集合元素限定為小寫字母符[′a′….′z′]，集合大小n<27。⑵集合輸入形式為一個(gè)以"回車符"為結(jié)束標(biāo)志字符串，串中字符次序不限，且許可出現(xiàn)反復(fù)字符或非法字符，程序應(yīng)能自動(dòng)濾去。⑶輸出運(yùn)算結(jié)果字符串中將不含反復(fù)字符或非法字符。⑷演示程序以用戶和計(jì)算機(jī)對(duì)話方法實(shí)施。3、長(zhǎng)整數(shù)加法運(yùn)算問(wèn)題描述：設(shè)計(jì)一個(gè)實(shí)現(xiàn)任意長(zhǎng)整數(shù)進(jìn)行加法運(yùn)算演示程序?；A(chǔ)要求：1利用鏈表實(shí)現(xiàn)長(zhǎng)整數(shù)存放，每個(gè)結(jié)點(diǎn)含一個(gè)整型變量。2任何整型變量范圍是-(2^15-1)~(2^15-1)。3輸入和輸出形式根據(jù)中國(guó)對(duì)于長(zhǎng)整數(shù)表示習(xí)慣，每四位一組,組間用逗號(hào)隔開。如：-2345，6789，3211；4、一元多項(xiàng)式計(jì)算器問(wèn)題描述：設(shè)有一元多項(xiàng)式Am(x)和Bn(x).Am(x)=A0+A1x1+A2x2+A3x3+…+AmxmBn(x)=B0+B1x1+B2x2+B3x3+…+Bnxn試求M(x)=Am(x)+Bn(x)、M(x)=Am(x)-Bn(x)和M(x)=Am(x)×Bn(x)?；A(chǔ)要求：⑴首先判定多項(xiàng)式是否稀疏；⑵分別采取次序和鏈?zhǔn)浇Y(jié)構(gòu)實(shí)現(xiàn)；⑶結(jié)果M(x)中無(wú)反復(fù)階項(xiàng)和無(wú)零系數(shù)項(xiàng)；⑷要求輸出結(jié)果升冪和降冪兩種排列情況。5、車廂調(diào)度問(wèn)題問(wèn)題描述：假設(shè)停在鐵路調(diào)度站(如教科書中圖3.1(b)所表示)入口處車廂系列編號(hào)依次為1，2，3，…n。設(shè)計(jì)一個(gè)程序,求出全部可能由此輸出長(zhǎng)度為n車廂系列?；A(chǔ)要求：⑴設(shè)計(jì)一個(gè)程序，求出由一個(gè)編號(hào)依次為1，2，、、、，n車廂序列可能產(chǎn)生全部出棧系列。⑵利用雙向棧存放結(jié)構(gòu)實(shí)現(xiàn)調(diào)度站和輸出序列這兩個(gè)?？臻g共享。⑶對(duì)于每個(gè)輸出序列演示出全部操作序列改變過(guò)程。6、文章編輯問(wèn)題描述：輸入一頁(yè)文字，能夠統(tǒng)計(jì)出文字、數(shù)字、空格個(gè)數(shù)?；A(chǔ)要求：⑴靜態(tài)存放一頁(yè)文章，每行最多不超出80個(gè)字符，共N行。⑵分別統(tǒng)計(jì)出其中英文字母和空格數(shù)及整篇文章總字?jǐn)?shù)。⑶統(tǒng)計(jì)某一字符串在文章中出現(xiàn)次數(shù)，并輸出該次數(shù)。⑶刪除某一子串，并將后面字符前移。⑷存放結(jié)構(gòu)使用線性表，分別用多個(gè)子函數(shù)實(shí)現(xiàn)對(duì)應(yīng)功效。7、識(shí)別廣義表頭或尾演示問(wèn)題描述：寫一個(gè)程序，建立廣義表存放結(jié)構(gòu)，演示在此存放結(jié)構(gòu)上定義廣義表求頭、求尾操作序列結(jié)果?；A(chǔ)要求：⑴組成廣義表正當(dāng)字符：小寫或大寫字母、空白字符、圓括號(hào)和逗號(hào)，且設(shè)廣義表原子為單個(gè)字母。⑵以用戶和計(jì)算機(jī)對(duì)話方法實(shí)施，廣義表建立方法為邊輸入邊建立；分解操作進(jìn)行方法為，輸入整個(gè)命令串，然后分步顯示每一個(gè)操作結(jié)果。⑶輸入過(guò)程中自動(dòng)濾去正當(dāng)字符以外其它字符，并能在輸入步當(dāng)初輸入對(duì)應(yīng)提醒信息。8、哈夫曼樹及其編碼問(wèn)題描述：設(shè)計(jì)一個(gè)利用哈夫曼算法編碼系統(tǒng)，反復(fù)地顯示并處理以下項(xiàng)目，直到選擇退出為止?；A(chǔ)要求：⑴初始化：鍵盤輸入字符集大小n、n個(gè)字符和n個(gè)權(quán)值，建立哈夫曼樹；⑵編碼：利用建好哈夫曼樹生成哈夫曼編碼；⑶輸出其哈夫曼樹及哈夫曼編碼；⑷設(shè)字符集及頻度以下表：字符空格ABCDEFGHIJKLM頻度1866413223210321154757153220字符NOPQRSTUVWXYZ頻度57631514851802381811619、校園導(dǎo)游咨詢問(wèn)題描述：設(shè)計(jì)一個(gè)校園導(dǎo)游程序，為來(lái)訪客人提供多種信息查詢服務(wù)?；A(chǔ)要求：⑴設(shè)計(jì)華東交通大學(xué)校園平面圖，所含景點(diǎn)不少于10個(gè)。以圖中頂點(diǎn)表示校內(nèi)各景點(diǎn)，⑵存放景點(diǎn)名稱、代號(hào)、介紹等信息；以邊表示路徑，存放路徑長(zhǎng)度等相關(guān)信息。⑶為來(lái)訪客人提供圖中任意景點(diǎn)相關(guān)信息查詢。⑷為來(lái)訪客人提供圖中任意景點(diǎn)問(wèn)路查詢，即查詢?nèi)我鈨蓚€(gè)景點(diǎn)之間一條最短簡(jiǎn)單路徑。10、地圖著色問(wèn)題問(wèn)題描述：已知江西地圖，請(qǐng)?jiān)O(shè)計(jì)地圖著色軟件，對(duì)11個(gè)地級(jí)市進(jìn)行著色，要求相鄰地級(jí)市所使用顏色不一樣，并確保使用顏色最少。基礎(chǔ)要求：⑴地圖采取圖型數(shù)據(jù)結(jié)構(gòu)，每個(gè)地級(jí)市為一個(gè)節(jié)點(diǎn)，邊表示對(duì)應(yīng)兩個(gè)地級(jí)市相鄰。⑵設(shè)計(jì)著色算法，確保鄰接點(diǎn)不是同一個(gè)顏色。⑶演示程序以用戶和計(jì)算機(jī)對(duì)話方法進(jìn)行。11、內(nèi)部排序算法比較問(wèn)題描述：試經(jīng)過(guò)隨機(jī)數(shù)據(jù)比較各算法關(guān)鍵字比較次數(shù)和關(guān)鍵字移動(dòng)次數(shù)，以取得直觀感受。基礎(chǔ)要求：⑴最少采取三種方法實(shí)現(xiàn)上述問(wèn)題求解（提醒，可采取方法有插入排序、希爾排序、起泡排序、快速排序、選擇排序、堆排序、歸并排序）。⑵待排序表表長(zhǎng)大于100，其中數(shù)據(jù)要用偽隨機(jī)數(shù)產(chǎn)生程序產(chǎn)生；最少要用5組不一樣輸入數(shù)據(jù)作比較；比較指標(biāo)為相關(guān)鍵字參與比較次數(shù)和關(guān)鍵字移動(dòng)次數(shù)（關(guān)鍵字交換計(jì)為3次移動(dòng)）。⑶最終對(duì)結(jié)果作出簡(jiǎn)單分析，包含對(duì)各組數(shù)據(jù)得出結(jié)果波動(dòng)大小解釋。12、哈希表設(shè)計(jì)和實(shí)現(xiàn)問(wèn)題描述：設(shè)計(jì)哈希表實(shí)現(xiàn)電話號(hào)碼查找系統(tǒng)?；A(chǔ)要求：⑴設(shè)每個(gè)統(tǒng)計(jì)有下列數(shù)據(jù)項(xiàng)：電話號(hào)碼、用戶名、地址；⑵從鍵盤輸入各統(tǒng)計(jì)，分別以電話號(hào)碼和用戶名為關(guān)鍵字建立哈希表；⑶采取一定方法處理沖突；⑷查找并顯示給定電話號(hào)碼統(tǒng)計(jì)；⑸查找并顯示給定用戶名統(tǒng)計(jì)。13、火車售票系統(tǒng)問(wèn)題描述：經(jīng)過(guò)此系統(tǒng)能夠?qū)崿F(xiàn)售票、退票、車票剩下情況查詢等功效。每張車票包含車次、座位信息?；A(chǔ)要求：⑴在售票、退票、查詢剩下票等步驟中，全部必需顯示出車票信息，即車次、座位情況。⑵為簡(jiǎn)單起見，在此假設(shè)全部出售車票均為同一車次車票。⑶退票時(shí)，必需是車站售出車票才能退，不然視為無(wú)效票，不能退票。14、圖書管理系統(tǒng)問(wèn)題描述：設(shè)計(jì)一個(gè)計(jì)算機(jī)管理系統(tǒng)完成圖書管理基礎(chǔ)業(yè)務(wù)?；A(chǔ)要求：⑴每種書登記內(nèi)容包含書號(hào)、書名、著作者、現(xiàn)存量和庫(kù)存量；⑵對(duì)書號(hào)建立索引表（線性表）以提升查找效率；⑶系統(tǒng)關(guān)鍵功效以下：①采編入庫(kù)：新購(gòu)一個(gè)書，確定書號(hào)后，登記到圖書帳目表中，假如表中已經(jīng)有，則只將庫(kù)存量增加；②借閱：假如一個(gè)書現(xiàn)存量大于0，則借出一本，登記借閱者書證號(hào)和歸還期限，改變現(xiàn)存量；③歸還：注銷對(duì)借閱者登記，改變?cè)摃F(xiàn)存量。15、用戶消費(fèi)積分管理系統(tǒng)問(wèn)題描述：針對(duì)用戶消費(fèi)情況，進(jìn)