數(shù)據(jù)結(jié)構(gòu)chapter樹和二叉樹等價(jià)問題-在線瀏覽
2024-08-01 08:45本頁面
【正文】 稱 是 x的等價(jià)類 。 簡言之 ， 等價(jià)類是集合中相互等價(jià)的元素的最大子集合 。在這類問題中主要涉及的是對集合的合并和查找，因此將這種集合稱為 并查集 。他可能是你的曾祖父的外公的女婿的外甥女的表姐的孫子。在這種情況下，最好的幫手是計(jì)算機(jī)。請寫一個(gè)程序，對于我們的關(guān)于親戚關(guān)系的提問，以最快的速度給出答案。其中 ai∈ {0,1,2,……,n} 結(jié)構(gòu)： 邏輯操作：設(shè) S為 UnionFindSet型 ? Initiate(S,n)：建立 n個(gè)新集合，每個(gè)集合有唯一元素。每一次 union操作使得集合的個(gè)數(shù)減少 1 )( jise tse t ji ?? ??算法性能參數(shù) ? n ? Find操作的次數(shù) m ? Union操作的次數(shù)（至多 n1） 并查集實(shí)現(xiàn)方法 1： 數(shù)組表示法 建立一大小為 n的數(shù)組，其中每個(gè)元素是等價(jià)類名 0 1 2 3 4 5 6 7 8 9 10 11 下標(biāo) 0 1 2 3 4 5 6 7 8 9 10 11 等價(jià)類名 , union(x,y):把所有的 Find(x)改為 Find(y) 4 1 2 3 4 5 6 7 8 9 10 11 Union(0,4)： 把所有的 0改為 4 4 1 2 1 4 5 6 7 8 9 10 11 Union(3,1)： 把所有的 3改為 1 4 1 2 1 4 5 10 7 8 9 10 11 Union(6,10)： 把所有的 6改為 10 4 1 2 1 4 5 10 7 9 9 10 11 Union(8,9)： 把所有的 8改為 9 4 1 2 1 4 5 10 4 9 9 10 11 Union(7,4)： 把所有的 7改為 4 4 1 2 1 4 5 9 4 9 9 9 11 Union(6,8)： 把所有的 10改為 9 4 5 2 5 4 5 9 4 9 9 9 11 Union(3,5)： 把所有的 1改為 5 4 5 11 5 4 5 9 4 9 9 9 11 Union(2,11)： 把所有的 2改為 11 4 5 4 5 4 5 9 4 9 9 9 4 Union(11,0)： 把所有的 11改為 4 數(shù)組法算法分析 操作 時(shí)間效率 操作執(zhí)行次數(shù) Find O(1) m Union O(n) n1 將所有元素合并到一個(gè)集合： O(m+n2) 并查集實(shí)現(xiàn)方法 2： 鏈表表示法 每個(gè)等價(jià)類用一個(gè)鏈表表示， 第一個(gè)結(jié)點(diǎn)作其代表，初始 n個(gè)鏈表 (a) 兩個(gè)集合的鏈表表示，其中一個(gè)集合c{b,c,e,h}，另一個(gè)集合 f{d
教學(xué)教案相關(guān)推薦
鄂ICP備17016276號-1