數(shù)據(jù)結(jié)構(gòu)課設(shè)報告-絕對原版大家珍惜啊.doc

數(shù)據(jù)結(jié)構(gòu)課程設(shè)計報告姓名：班級：學(xué)號：指導(dǎo)教師成績：一 各個課設(shè)概述1 算術(shù)表達(dá)式求值 (必做)A 算法思想及數(shù)據(jù)結(jié)構(gòu)及時間復(fù)雜度(括號內(nèi)容)：算式（棧）：計算部分(n)：建立運算符優(yōu)先規(guī)則，存在一個二維數(shù)組中。運用數(shù)字棧和運算符棧，逐個字符讀入算式，若字符為數(shù)字則放入數(shù)字棧；若字符為運算符則讓它和元素符棧的棧頂元素比較優(yōu)先級，若優(yōu)先級低則進(jìn)運算符棧，若優(yōu)先級高，則取數(shù)字棧中元素進(jìn)行運算。直至讀到#。糾錯部分(n)：首先對每個讀入的字符進(jìn)行判斷，如果非法則終止程序。對于運算符匹配，則在計算完后查看字符棧和數(shù)字棧，進(jìn)而判斷。B 程序測試 正確表達(dá)式測試：#7+8+(9+6*5)+4#結(jié)果：OPTR: OPND: OPTR: #OPND: OPTR: #OPND: 7OPTR: + #OPND: 7OPTR: + #OPND: 8 7OPTR: #OPND: ?OPTR: + #OPND: ?OPTR: ( + #OPND: ?OPTR: ( + #OPND: 9 ?OPTR: + ( + #OPND: 9 ?OPTR: + ( + #OPND: 6 9 ?OPTR: * + ( + #OPND: 6 9 ?OPTR: * + ( + #OPND: 5 6 9 ?OPTR: + ( + #OPND: N 9 ?OPTR: ( + #OPND: W ?OPTR: + #OPND: W ?OPTR: #OPND: fOPTR: + #OPND: fOPTR: + #OPND: 4 fOPTR: #OPND: jresult: 58錯誤表達(dá)式測試#(7*5)(3+4)#輸出結(jié)果：OPTR: OPND: OPTR: #OPND: OPTR: ( #OPND: OPTR: ( #OPND: 7OPTR: * ( #OPND: 7OPTR: * ( #OPND: 5 7OPTR: ( #OPND: SOPTR: #OPND: SOPTR: ( #OPND: SOPTR: ( #OPND: 3 SOPTR: + ( #OPND: 3 SOPTR: + ( #OPND: 4 3 SOPTR: ( #OPND: 7 SOPTR: #OPND: 7 S算式操作符搭配有問題，請重新輸入。2 二叉樹的應(yīng)用 (必做)A 算法思想及數(shù)據(jù)結(jié)構(gòu)及時間復(fù)雜度：二叉樹（二叉樹）：建樹：采用課本上先序建樹方法。層序遍歷：增加一個數(shù)字棧，從樹的祖先開始訪問，訪問后就把該節(jié)點的左右子樹放進(jìn)棧里，然后訪問棧頂元素，依次遞歸下去，直至棧為空。深度：在樹節(jié)點的結(jié)構(gòu)體內(nèi)增加一個level變量用來記錄該節(jié)點的層數(shù)。采用層序遍歷，令頭結(jié)點的level為1，訪問到時在把其左右子樹放進(jìn)棧的同時，付其level為2，依次遞歸下去。繁茂度：在求深度程序的基礎(chǔ)上，加開一個一維數(shù)組，記錄各個節(jié)點的level，訪問完后再掃描一下數(shù)組，分別記錄各個層的節(jié)點數(shù)，找出最大值再乘以深度。葉子節(jié)點個數(shù)：加開count變量。任意遍歷方法，若訪問節(jié)點左右子樹均為空則count+；遍歷完后，count即為葉子節(jié)點個數(shù)。判斷完全二叉樹：采用層序遍歷的方法，并把訪問多的節(jié)點記錄在數(shù)組里，如果在數(shù)組中間出現(xiàn)了NULL，則樹不是完全二叉樹。B 測試主界面當(dāng)輸入相應(yīng)的代號就能輸出相應(yīng)的結(jié)果。3 Huffman編碼與解碼 (必做)A 算法思想及數(shù)據(jù)結(jié)構(gòu)及時間復(fù)雜度：哈弗曼（哈弗曼樹）：編碼：先讀一遍文章，統(tǒng)計各個字符出現(xiàn)的個數(shù)，賦給各個字符以weight；然后建立哈弗曼樹(n2)，生成哈弗曼編碼。然后再讀一遍文章，把其轉(zhuǎn)換為哈弗曼編碼。解碼(ne)：讓編碼在輸出哈弗曼編碼的同時，并把各個節(jié)點的父節(jié)點以及左右孩子節(jié)點輸出，利用這些數(shù)據(jù)重新還原哈弗曼數(shù)，然后讀入哈弗曼編碼，如果是1則從樹頭往右走，如果讀入0則往左走。B 使用說明編碼：直接運行編碼的程序，就能把默認(rèn)final.in里的文章轉(zhuǎn)換成哈弗曼編碼，并記錄在final.out中，如果顯示每個字符的編碼，只需把主函數(shù)中的“輸出各個字母所對應(yīng)的哈弗曼編碼”部分取消注釋即可。在執(zhí)行解碼時，請先運行編碼，并把“輸出各個字母所對應(yīng)的哈弗曼編碼”注釋掉，解碼部分將從final.out讀入數(shù)據(jù)，把解碼結(jié)果存放在finalout.out中。4 校園局域網(wǎng)布線和游歷問題 (必做) A 算法思想及數(shù)據(jù)結(jié)構(gòu)及時間復(fù)雜度：校園游歷（圖論，）：遍歷圖：利用深搜(n+e)和寬搜(n+e)建立校園網(wǎng)(n2)：利用prim算法求最小生成樹。從宿舍到其他各點的路徑(n2)：利用迪杰斯特拉算法求某點到其他各點的最短路徑。查詢?nèi)我鈨牲c間的路徑長度(n2)：利用弗洛伊的算法求兩點間的最短距離。B 測試主界面當(dāng)輸入相應(yīng)的代號，就能執(zhí)行相應(yīng)的操作，當(dāng)鍵入c后則顯示：5 Hash表應(yīng)用 （必做）A 算法思想及數(shù)據(jù)結(jié)構(gòu)及時間復(fù)雜度：哈希（哈希算法）：手機(jī)號碼哈希(n)：經(jīng)分析，對于一個手機(jī)號碼可取代表性的幾位第三、六以及后四位，根據(jù)其出現(xiàn)的頻率不同并附其不同的權(quán)值，鑒于此程序?qū)ο笫?00個數(shù)據(jù)，可用公式 第三位*3+第六位*9+后四位之和*27，并采用二次探測再散列。另外開一個大的指向人員信息的指針數(shù)組，首先置其所有變量為空。當(dāng)讀到一個手機(jī)號碼，利用上述公式計算出一個整數(shù)，然后就讓該整數(shù)對應(yīng)的指針指向這個人，如果這個指針已經(jīng)指向別人，就用二次探測再散列解決沖突，當(dāng)超出指針數(shù)組大小時，就用recalloc增大數(shù)組容量并使增添的指針置空。姓名哈希(n)：方法同手機(jī)號碼哈希。利用手機(jī)號碼查找，利用姓名查找：首先根據(jù)號碼或姓名算出一個數(shù)n，如果指針n指向人的號碼或手機(jī)與要查找人的相同，則輸出這個人的信息，否則利用二次探測再散列繼續(xù)查找。利用手機(jī)號刪除：首先根據(jù)號碼或姓名算出一個數(shù)n，如果指針n指向人的號碼與要刪除人的相同，則令該指針置空，如果不相同，則利用二次探測再散列繼續(xù)查找直至相同，并置其為空，令mark=0（在現(xiàn)實所有人信息時，如果mark=1則顯示，如果為0則不顯示）。6、排序算法比較 （必做）A 算法思想及數(shù)據(jù)結(jié)構(gòu)及時間復(fù)雜度：排序：簡單排序(n2)；快排（nlogn）；堆排（nlogn）；歸并（nlogn）；基數(shù)（d(n+rd)）。B 功能測試當(dāng)運行程序后，就會依次排序500、1500、2000、2500、30000個數(shù)，并顯示所需時間。7 家譜管理系統(tǒng) （4）A 算法思想及數(shù)據(jù)結(jié)構(gòu)及時間復(fù)雜度：家譜管理 （二叉樹）：建樹采用左母親右孩子的方式，數(shù)據(jù)存儲時采用先序遍歷的方式把家譜成員寫入，用二叉樹中的先序方法建立原始家譜，原始家譜成員的信息中要有他的代數(shù)，以后添加時就不用在寫了。顯示第n代人的信息(n)：利用先序遍歷，當(dāng)訪問節(jié)點的level與n相等時則輸出他的信息圖形顯示(n)：自定義遞歸方法，使其俺家譜輩分輸出，利用成員的代數(shù)，在其前打空格。按出生年月查詢：利用先序遍歷的方式，如果訪問到的成員的出生日期與要查詢?nèi)说囊恢聞t輸出此人的信息。按姓名查詢(n)：利用先序遍歷，若訪問節(jié)點有做孩子，則查看其左孩子的有孩子們有沒有要查找的人，如果有則輸出訪問節(jié)點信息及其左孩子的信息（即是要查詢?nèi)烁改傅男畔ⅲ绻L問績點沒有左孩子或有左孩子而左孩子沒有右孩子則讓其指向其右孩子；若其左孩子有右孩子則指向其右孩子，依次遞歸。添加、刪除節(jié)點(n)：利用先序遍歷，當(dāng)找到節(jié)點時若要刪除這個節(jié)點及孩子，則令其左右孩子為NULL，并釋放其所有孩子的空間。如果要添加孩子，則先判斷該節(jié)點是否符合添加孩子要求，如何就執(zhí)行添加操作，并對孩子的level賦值。確定兩個人的關(guān)系(2n)：利用先序遍歷分別找到兩個人的信息，比較他們對應(yīng)的level即可。按出生時間排序家譜成員(n)：另外加開一個鏈表，其成員為指向家譜成員的指針，利用線序排序，不斷開鏈表并插入到鏈表中，是鏈表中的指針按順序的指向家譜中的成員。B 功能測試主界面鍵入不同的號碼將會執(zhí)行相應(yīng)的操作，如鍵入11，將有以下界面8 公交線路提示 （4）A 算法思想及數(shù)據(jù)結(jié)構(gòu)及時間復(fù)雜度：公交線路（圖論）：最少?？奎c(n2)：令一條線路中相鄰站點之間的權(quán)值為1，再用弗洛伊的算法求最短路徑即可。最少換乘(n2)：令一條線路中任意兩個站點之間的權(quán)值為1，再利用弗洛伊的算法求最短路徑即可，而且易知，經(jīng)過的站點就為換乘站點。B 測試主界面當(dāng)鍵入1后則有一下界面9 關(guān)鍵路徑問題 （3）A 算法思想及數(shù)據(jù)結(jié)構(gòu)及時間復(fù)雜度：關(guān)鍵路徑（圖論）(n+e)：先用拓?fù)渑判?，把訪問過的節(jié)點一次放到一個棧中，與此同時，計算出各個點的最早開始時間，并記錄下來；遍歷完后，再把棧中元素一次取出，計算出個點的最遲結(jié)束時間，并記錄下來。若最早開始時間和相等，則這個點就是關(guān)鍵路徑上的點。B 使用說明當(dāng)執(zhí)行完程序后，將把9.in中存的圖的工序的關(guān)鍵路徑和圖的臨界表存放在9.out中。10 電梯模擬 （5）A 算法思想及數(shù)據(jù)結(jié)構(gòu)及時間復(fù)雜度：電梯模擬（棧和隊列）(1)：在電梯內(nèi)部設(shè)置兩個棧：上升棧和下降棧，再往電梯里放元素的時候是可以插隊的，對于要上升的人，就把他插入到上升棧中，并且，從棧頂?shù)綏Ｎ苍匾来卧龃?，為的是方便下電梯時的處理。對于要下樓的人，就把他插入到下降棧中，并且，從棧頂?shù)綏Ｎ苍厥且来螠p小的，也是為了下電梯時處理的方便。在電梯外，每層設(shè)置了兩個對列，如果隨機(jī)產(chǎn)生的人要上樓，就把它放到上升隊列中，反之，放在下降隊列中。當(dāng)電梯到達(dá)相應(yīng)樓層是，只需把相應(yīng)隊列中的元素全部放進(jìn)去就行了。另外，電梯內(nèi)添加了一個callHeight數(shù)組，用來存放電梯要在哪層停，電梯外有一個upordownHeight2的二維數(shù)組，用來存放電梯外的需求，當(dāng)隨機(jī)產(chǎn)生了人后，就對其對應(yīng)的upordownmn賦值，若其要上升則令upordownm1=1;反之令upordownm0=1；表示該層有上升或下降的需求。當(dāng)人進(jìn)入電梯后，就在對電梯內(nèi)callm賦值1表示要在m層停。利用for循環(huán)執(zhí)行電梯，每一次循環(huán)處理一次電梯處于上升、下降或靜止的情況。B 測試主界面當(dāng)輸入任意時間后，則運行電梯，其表現(xiàn)形式如下圖圖中為五層樓即橫線中間的部分。掐腰的人表示電梯里面，招手的人表示外面，數(shù)組時人的代號。掐腰人后面的數(shù)字表示電梯內(nèi)現(xiàn)在的人，招手的人后面的數(shù)字表示電梯外現(xiàn)在的人。二 結(jié)束語終于寫到結(jié)束語這最后一個環(huán)節(jié)了，數(shù)據(jù)結(jié)構(gòu)課設(shè)也算是告一段落了?；叵肫饋?，在寫課設(shè)的這段日子里真實很充實啊，尤其是停課之后的這段時間，每天爬起來的第一件事就是打開電腦，洗漱之后就是寫程序，一直到吃午飯。然后，那道自習(xí)室去寫，知道關(guān)門。有時忘記吃飯；有時望著窗外，天已經(jīng)有黑轉(zhuǎn)白。但最終，這一切還是挺過去了?？粗@是個活靈活現(xiàn)的程序，心中不禁沾沾自喜。但細(xì)想起來，心中也難免有些遺憾，一方面是程序確實還存在這一些小問題，另一方面程序還有很多可以完善的地方，還有就是所有的程序都沒有用到可視化界面。在問題上我總結(jié)了一下，主要有以下幾點。（1）算式表達(dá)式求值：由于只用了一個字符棧，所以只能計算輸入為單個位的數(shù)字，計算結(jié)果及中間數(shù)不能超過阿斯科馬范圍。由于時間原因，也沒有進(jìn)一步改進(jìn)。（2）排序算法比較中的基數(shù)排序，調(diào)試了很久也通過不了，考慮到后面還有很多課設(shè)要做，就沒繼續(xù)調(diào)試下去。在完善這方面，主要有：（1）算術(shù)表達(dá)式求值，我完全可以在加一個數(shù)字棧，改幾個變量就行了。（2）公交管理系統(tǒng)中，我只實現(xiàn)了顯示最小換乘的中間站點以及最少?？空军c時經(jīng)過的站點，而沒有顯示所乘坐車的路線名。對于最小換乘，我可以用一個數(shù)組記錄各個站點，然后查看經(jīng)過的相鄰兩個站點同時在哪些公交路線中出現(xiàn)即使其乘坐車的路線。同樣的思路也可以應(yīng)用到最少?？空军c上（3）在哈希中，程序比較散亂，沒有與用戶寫交互界面，只是一些功能的直接展示。我計劃這些需要完善的程序?qū)⑹俏揖毷諱FC的首個堡壘。而在可視化方面，只是后悔當(dāng)初沒有學(xué)習(xí)MFC啊