版權(quán)說明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請(qǐng)進(jìn)行舉報(bào)或認(rèn)領(lǐng)
文檔簡(jiǎn)介
1、4.6.3 集合及運(yùn)算11.集合的表示 集合運(yùn)算:交、并、補(bǔ)、差,判定一個(gè)元素是否屬于某一集合 并查集:集合并、查某元素屬于什么集合 并查集問題中集合存儲(chǔ)如何實(shí)現(xiàn)? 可以用樹結(jié)構(gòu)表示集合,樹的每個(gè)結(jié)點(diǎn)代表一個(gè)集合元素例如,有三個(gè)整數(shù)集合S1=1,2,4,7S2=3,5,8S3=6,9,10集合名 指針雙親表示法:孩子指向雙親。S1S2S32467538910 采用數(shù)組存儲(chǔ)形式下標(biāo)01234Data12345Parent-10-102數(shù)組中每個(gè)元素的類型描述為:typedef struct ElementType Data;int Parent; SetType;56-1136670788925
2、247589109105負(fù)數(shù)表示根結(jié)點(diǎn);非負(fù)數(shù)表示雙親結(jié)點(diǎn)的下標(biāo)。2.集合運(yùn)算(1)查找某個(gè)元素所在的集合(用根結(jié)點(diǎn)表示)查找某個(gè)元素所在的集合(用根結(jié)點(diǎn)表示)int Find( SetType S , ElementType X )/* 在數(shù)組S中查找值為X的元素所屬的集合 */* MaxSize是全局變量,為數(shù)組S的最大長(zhǎng)度 */int i;for ( i=0; i = MaxSize ) return -1; /* 未找到X,返回-1 */for( ; Si.Parent = 0; i = Si.Parent ) ;return i; /* 找到X所屬集合,返回樹根結(jié)點(diǎn)在數(shù)組S中的下標(biāo)
3、*/(2) 集合的并運(yùn)算 分別找到X1和X2兩個(gè)元素所在集合樹的根結(jié)點(diǎn) 如果它們不同根,則將其中一個(gè)根結(jié)點(diǎn)的父結(jié)點(diǎn)指針設(shè)置成另一個(gè)根結(jié)點(diǎn)的數(shù)組下標(biāo)。void Union( SetType S , ElementType X1, ElementType X2 )int Root1, Root2;當(dāng)x1和x2不屬于同一子集時(shí),才需要合并Root1 = Find(S, X1);Root2 = Find(S, X2);if( Root1 != Root2 )SRoot2.Parent = Root1;改成-7。表示集下標(biāo)dataParent合有7個(gè)元素0112-10162302473910340455
4、62-1586789789100255改成-3。表示集合有3個(gè)元素為了改善合并以后的查找性能,可以采用小的集合合并到相對(duì)大的集合中。(修改Union函數(shù))作業(yè):1.課本154頁題目4.6.2.課本154頁題目4.7.3. 一棵深度為h的滿k叉樹有如下性質(zhì): 第h層上的結(jié)點(diǎn)都是葉子結(jié)點(diǎn),其余各層上每個(gè)結(jié)點(diǎn)都有k棵非空子樹。 如果按層次順序(同層自左至右)從1開始對(duì)全部結(jié)點(diǎn)編號(hào),問: 各層的結(jié)點(diǎn)數(shù)是多少? 編號(hào)為i的結(jié)點(diǎn)的雙親結(jié)點(diǎn)(若存在)的編號(hào)是多少? 編號(hào)為i的結(jié)點(diǎn)的第j個(gè)孩子結(jié)點(diǎn)(若存在)的編號(hào)是多少? 編號(hào)為i的結(jié)點(diǎn)的有右兄弟的條件是什么? 其右兄弟的編號(hào)是多少? 4.在最大堆 97,76,65,50,49,13,27中插入83后,該最大堆為:.A.97,76,65,83,49,13,27,50B.97,83,6
溫馨提示
- 1. 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請(qǐng)下載最新的WinRAR軟件解壓。
- 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請(qǐng)聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
- 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁內(nèi)容里面會(huì)有圖紙預(yù)覽,若沒有圖紙預(yù)覽就沒有圖紙。
- 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
- 5. 人人文庫網(wǎng)僅提供信息存儲(chǔ)空間,僅對(duì)用戶上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理,對(duì)用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對(duì)任何下載內(nèi)容負(fù)責(zé)。
- 6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請(qǐng)與我們聯(lián)系,我們立即糾正。
- 7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時(shí)也不承擔(dān)用戶因使用這些下載資源對(duì)自己和他人造成任何形式的傷害或損失。
最新文檔
- 產(chǎn)品生命周期管理與維護(hù)
- 學(xué)生管理系統(tǒng) jsp課程設(shè)計(jì)
- 中班冬天美食課程設(shè)計(jì)
- 青島工學(xué)院《行政法(下)》2023-2024學(xué)年第一學(xué)期期末試卷
- 儀態(tài)訓(xùn)練課程設(shè)計(jì)
- 護(hù)理心理學(xué)課程設(shè)計(jì)
- 工程材料采購的招標(biāo)與投標(biāo)技巧
- 個(gè)人健康管理與生活方式的改變
- 大健康產(chǎn)業(yè)發(fā)展與未來趨勢(shì)
- 幼兒園魔方拼圖課程設(shè)計(jì)
- 全國養(yǎng)老護(hù)理職業(yè)技能大賽養(yǎng)老護(hù)理員賽項(xiàng)考試題庫-下(判斷題)
- 數(shù)智時(shí)代的商業(yè)變革智慧樹知到期末考試答案章節(jié)答案2024年山東大學(xué)(威海)
- 2024年貴州省中國貴州茅臺(tái)酒廠(集團(tuán))限責(zé)任公司公開招聘人員1120名公開引進(jìn)高層次人才和急需緊缺人才筆試參考題庫(共500題)答案詳解版
- 飼料合作進(jìn)口訂購合同范本
- 胸痛中心關(guān)鍵質(zhì)控指標(biāo)及質(zhì)量改進(jìn)計(jì)劃
- DGTJ 08-010-2018 輕型鋼結(jié)構(gòu)制作及安裝驗(yàn)收標(biāo)準(zhǔn)
- 幼兒園科學(xué)活動(dòng)觀察
- 質(zhì)量成熟度評(píng)價(jià)標(biāo)準(zhǔn)樣本
- 小學(xué)科學(xué)期末測(cè)評(píng)方案設(shè)計(jì)
- 2024年中考作文十二大高頻熱點(diǎn)主題4-青春夢(mèng)想(素材)
- 河北省藥品流通非現(xiàn)場(chǎng)監(jiān)管藥品流通追溯系統(tǒng)操作手冊(cè)
評(píng)論
0/150
提交評(píng)論