數(shù)據(jù)結(jié)構(gòu)chapter樹和二叉樹等價(jià)問題(文件)
【正文】 {7},{8},{9},{10},{11} 0 ? 4 {0,4},{1},{2},{3},{5},{6},{7},{8},{9},{10},{11} 3 ? 1 {0,4}, {1,3},{2},{5},{6},{7},{8},{9},{10},{11} 6 ? 10 {0,4},{1,3},{2},{5},{6,10},{7},{8},{9},{11} 8 ? 9 {0,4},{1,3},{2},{5},{6,10},{7},{8,9},{11} 7 ? 4 {0,4,7},{1,3},{2},{5},{6,10},{8,9},{11} 6 ? 8 {0,4,7},{1,3},{2},{5},{6,8,9,10},{11} 3 ? 5 {0,4,7},{1,3,5},{2},{6,8,9,10},{11} 2 ? 11 {0,4,7},{1,3,5},{2,11},{6,8,9,10} 11 ? 0 {0,2,4,7,11},{1,3,5},{6,8,9,10} ADT UnionFindSet 數(shù)據(jù)元素： seti={aj}, i=0,1,…,n 1, j=0,1,…,n i1 (n≥0, ni≥0)。鏈表中每個(gè)結(jié)點(diǎn)包含一個(gè)集合成員、一個(gè)指向下一個(gè)集合元素結(jié)點(diǎn)的指針以及一個(gè)指向表中第一個(gè)結(jié)點(diǎn)的指針。鏈表中每個(gè)結(jié)點(diǎn)包含 一個(gè)集合成員、 一個(gè)指向雙親結(jié)點(diǎn)的指針。//雙親結(jié)點(diǎn)在數(shù)組的下標(biāo)，根的 parent為 1 } UFSTreeNode。in。 return i。 //找到結(jié)點(diǎn) j的根 if (rooti!=rootj) { F[rootj].parent=rooti。 。 路徑壓縮不改變結(jié)點(diǎn)的秩 使用路徑壓縮策略處理等價(jià)對(duì)（ H,E）的結(jié)果： 森林法改進(jìn) 2示例 森林法改進(jìn) 2的算法分析 操作 時(shí)間效率 操作執(zhí)行次數(shù) Find O(log2+m/nn) m Union O(1) n1 將所有元素合并到一個(gè)集合： O(n+mlog2+m/nn) 森林法改進(jìn) 1+改進(jìn) 2的算法分析 操作 時(shí)間效率 操作執(zhí)行次數(shù) Find O(l) m Union O(1) n1 將所有元素合并到一個(gè)集合： O(m+n) 作業(yè) 11 算法設(shè)計(jì)題 ? 實(shí)現(xiàn) FindPathCompress（）函數(shù)功能，該函數(shù)在查找的同時(shí)實(shí)現(xiàn)路徑壓縮，將深層結(jié)點(diǎn)移近根結(jié)點(diǎn)。 rooti=Find(F,i)。 F[i].parent=1。/*存儲(chǔ)森林結(jié)點(diǎn)的數(shù)組 */ 【 并查集初始化算法 】 void Initiate(UFSTreeNode F[ ],int n) /*初始化
教學(xué)教案相關(guān)推薦
鄂ICP備17016276號(hào)-1