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

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