課程設計任務.doc

附件3：課 程 設 計 任 務 書題 目 還原二叉樹 院 (部) 交通與物流工程學院 專 業(yè) 物聯(lián)網(wǎng)工程 班 級 物聯(lián)141-2 學生姓名 學 號 月 日至 月 日 共 1 周指導教師(簽字) 陳穎 負責人(簽字) 張良智 年 月 日一、設計內(nèi)容及要求目的：熟練掌握二叉樹存儲結(jié)構；熟練掌握二叉樹的遍歷及應用。要求：給定一顆二叉樹的先序遍歷序列和中序遍歷序列，要求計算該二叉樹的高度。(1) 輸入說明：輸入第1行給出正整數(shù)N(N<=50)，為樹中結(jié)點總數(shù)。隨后2行先后給出先序和中序遍歷序列，均是長度為N的不包含重復英文字母（區(qū)別大小寫）的字符串。(2) 輸出說明：輸出為一個整數(shù)，即該二叉樹的高度。(3) 測試用例序列輸入輸出說明19ABDFGHIECFDHGIBEAC5一般情況測試215cdefghijklmnxyzcdefghijklmnxyz15完全右斜37AbcdefggfedcbA7完全左斜41aa1邊界測試55050個隨機數(shù)略二、設計原始資料本題需要解決兩個子問題：(1) 通過輸入給定的先序遍歷和中序遍歷兩個序列構建對應二叉樹。由于我們知道先序遍歷的第1個結(jié)點必然是根節(jié)點，可以在終須遍歷序列中找到這個根結(jié)點的位置，于是就知道在中序遍歷中，根節(jié)點左邊的所有結(jié)點一定屬于左子樹，右邊的所有結(jié)點一定屬于右子樹。根據(jù)這個判斷，可以從中序遍歷序列中知道左、右子樹分別有L,R個結(jié)點，它們必然對應存儲在先序遍歷序列遍歷中第2-（L-1）個結(jié)點以及最后的R個結(jié)點。于是可以對左右子樹遞歸地解決這個問題，直到生成整個二叉樹。(2) 求二叉樹的高度。如果已經(jīng)知道左右子樹的高度，那么樹的高度就是左右子樹中比較高的那個 加1.這是一個可以用二叉樹后序遍歷解決的問題，在遍歷過程中，我們將“訪問節(jié)點”定義為“求左右子樹高度的較大值加1。實現(xiàn)要點：樹形結(jié)構用一般教材中介紹的鏈表結(jié)構存儲，結(jié)點結(jié)構體存儲該節(jié)點的字符以及左右子樹的指針。在構建二叉樹和求二叉樹高度的過程中，需注意遞歸終止的條件。typedef struct TreeNode *BinTree;struct TreeNode char Data; BinTree Left; BinTree Right;三、設計完成后提交的文件和圖表1算法設計部分 可以選擇隊列進行算法設計。必須包含實驗分析，需求分析，程序流程設計，函數(shù)名稱及實現(xiàn)功能說明。2程序部分：針對自己的數(shù)據(jù)結(jié)構算法設計，按照流程圖進行C語言源程序設計。設計要求：（1）運行無錯誤(2) 運行在有限時間內(nèi)，不能是無限循環(huán)(3) 運行測例進行測試無錯誤。四、進程安排課程設計前完成資料收集課程設計第3天完成五、主要參考資料 數(shù)據(jù)結(jié)構 嚴蔚敏 清華大學出版社其它網(wǎng)絡開源資料附件3：課 程 設 計 任 務 書題 目 六度空間 院 (部) 交通與物流工程學院 專 業(yè) 物聯(lián)網(wǎng)工程 班 級 物聯(lián)141-2 學生姓名 學 號 月 日至 月 日 共 1 周指導教師(簽字) 陳穎 負責人(簽字) 張良智 年 月 日一、設計內(nèi)容及要求“六度空間”理論又稱作“六度分隔理論”。這個理論可以通俗地闡述為：“你和任何一個陌生人之間所間隔的人不會超過六個，也就是說，最多通過五個人你就能認識任何一個陌生人”六度空間理論雖然得到廣泛的認同，并且正在得到越來越多的應用。但是數(shù)十年來，試圖驗證這個力量始終是許多社會學家努力追求的目標。然而由于歷史的原因，這樣的研究具有太大的局限性和困難。隨著當代人依賴于電話、短信、微信以及因特網(wǎng)上即時通信等工具，能夠體現(xiàn)社交網(wǎng)絡關系的一手數(shù)據(jù)已經(jīng)逐漸使得六度空間理論的驗證成為可能。假如給你一個社交網(wǎng)絡圖，請你對每個節(jié)點計算符合六度空間理論的結(jié)點總數(shù)的百分比。(1) 輸入：輸入第1行給出兩個正整數(shù)，分別表示社交網(wǎng)絡圖的結(jié)點數(shù)N(1<N<104,表示人數(shù))、邊數(shù)M(<=33*N，表示社交關系數(shù))。隨后的M行對應M條邊，每行給出一對正整數(shù)，分別是該條邊直接連通的兩個結(jié)點的編號（節(jié)點從1到N編號）。(2) 輸出格式：對每個結(jié)點輸出與該節(jié)點距離不超過6的結(jié)點數(shù)占結(jié)點總數(shù)的百分比，精確到小數(shù)點后2位。每個結(jié)節(jié)點輸出一行，格式為“結(jié)點編號：（空格）百分比%”二、設計原始資料（1）問題分析：把驗證六度空間理論改成計算“到某個結(jié)點的距離不超過6的結(jié)點總數(shù)占所有節(jié)點數(shù)的百分比”是一個比較現(xiàn)實的做法?！懊總€社會人”的這個百分比如果都能夠達到98%（或者99%），是不是也可以認為六度空間理論基本成立？(2)實現(xiàn)要點：圖的存儲有鄰接矩陣和鄰接表兩種。由于本題給出邊數(shù)的上屆不超過結(jié)點數(shù)的33倍，且結(jié)點數(shù)最多可達1000，即相對于人數(shù)而言，龐大的社交網(wǎng)絡的關系遠遠達不到稠密圖，所以選擇鄰接表來做圖的存儲比較合理。（這個地方參考教材鄰接表的類型，還要考慮題目要求，增加記錄最后得到百分比的變量，浮點型）。這里對鄰接表中每個節(jié)點對應的所有鄰接點編號順序沒有要求。所以在建立鄰接表時，每條邊只需簡單依次插入到鄰接表的頭部。三、設計完成后提交的文件和圖表1算法設計部分 可以選擇隊列進行算法設計。必須包含實驗分析，需求分析，程序流程設計，函數(shù)名稱及實現(xiàn)功能說明。2程序部分：針對自己的數(shù)據(jù)結(jié)構算法設計，按照流程圖進行C語言源程序設計。設計要求：（1）運行無錯誤(2) 運行在有限時間內(nèi)，不能是無限循環(huán)(3) 運行測例進行測試無錯誤。四、進程安排課程設計前完成資料收集課程設計第4天完成五、主要參考資料 數(shù)據(jù)結(jié)構 嚴蔚敏 清華大學出版社其它網(wǎng)絡開源資料