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