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