數(shù)據(jù)結(jié)構(gòu)chapter樹和二叉樹等價(jià)問題(參考版)
2025-06-24 08:45本頁面
【正文】 。 路徑壓縮不改變結(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)。 //找到結(jié)點(diǎn) j的根 if (rooti!=rootj) { F[rootj].parent=rooti。 rooti=Find(F,i)。 return i。 F[i].parent=1。in。/*存儲(chǔ)森林結(jié)點(diǎn)的數(shù)組 */ 【 并查集初始化算法 】 void Initiate(UFSTreeNode F[ ],int n) /*初始化并查集，并查集 (森林 )中最初有 n個(gè)集合 (樹 )，每個(gè)集合只有一個(gè)元素 */ { int i。//雙親結(jié)點(diǎn)在數(shù)組的下標(biāo)，根的 parent為 1 } UFSTreeNode。 B C D E F G H I 序號(hào) 0 1 2 3 4 5 6 7 B 1 E 0 F 0 C 1 D 1 G 4 H 5 I 5 data parent 采用 雙親表示法 實(shí)現(xiàn)森林 例： 10個(gè)結(jié)點(diǎn) A、 B、 C、 D、 E、 F、 G、 H、 J、 K和它們的等價(jià)關(guān)系（ A,B）、 (C,K) 、 (F,J) 、(E, H) 、 (D,G) 、 (A, K) 、 (G, E) 、 (H,J) 初始狀態(tài)： 森林表示法示例 對(duì)（ A,B）、 (C,K) 、 (F, J) 、 (E,H) 、 (D,G)這 5個(gè)等價(jià)對(duì)的處理結(jié)果 森林表示法示例 對(duì)兩個(gè)等價(jià)對(duì)（ A, K）和（ G, E ）的處理結(jié)果： 森林表示法示例 并查集類型定義 define MaxTreeNode 20
教學(xué)教案相關(guān)推薦
鄂ICP備17016276號(hào)-1