數(shù)據(jù)結(jié)構(gòu)chapter樹和二叉樹等價問題-wenkub
2023-07-06 08:45:27 本頁面
【正文】 (1) m Union O(n) n1 將所有元素合并到一個集合： O(m+n2) 并查集實現(xiàn)方法 2： 鏈表表示法 每個等價類用一個鏈表表示， 第一個結(jié)點作其代表，初始 n個鏈表 (a) 兩個集合的鏈表表示，其中一個集合c{b,c,e,h}，另一個集合 f{d,f,g}。請寫一個程序，對于我們的關(guān)于親戚關(guān)系的提問，以最快的速度給出答案。他可能是你的曾祖父的外公的女婿的外甥女的表姐的孫子。 簡言之 ， 等價類是集合中相互等價的元素的最大子集合 。上堂課要點回顧 森林與二叉樹的轉(zhuǎn)換 ? 樹轉(zhuǎn)換為二叉樹 ? 二叉樹轉(zhuǎn)換為樹 ? 森林轉(zhuǎn)換為二叉樹 ? 二叉樹轉(zhuǎn)換為森林 森林的遍歷 ? 先根深度優(yōu)先遍歷 ? 后根深度優(yōu)先遍歷 二叉樹的應用 ? 哈夫曼樹與哈夫曼編碼 第 十二 次 課 閱讀： 朱戰(zhàn)立， 第 200204頁 習題： 作業(yè) 11 數(shù)據(jù)結(jié)構(gòu)課程內(nèi)容 二叉樹 數(shù)據(jù)結(jié)構(gòu)的應用 等價問題 （ 并查集 ） 基本概念 ? 等價關(guān)系 (equivalence relation)：假定有一具有 n個元素的非空集合 S={1， 2， … ， n}，另有一個具有 r個關(guān)系的集合 R={(i1,j1),(i2,j2),…,( ir,jr)}，若 R滿足： ? 對所有的 i∈ S，有 (i,i)∈ R時，即關(guān)系是自反的 ? 對所有的 i， j∈ S，當且僅當 (i,j)∈ R時 (j,i)∈ R，即關(guān)系是對稱的 ? 對所有的 i， j∈ S，若 (i,j)∈ R且 (j,k)∈ R，則有(i,j)∈ R，即關(guān)系是傳遞的 則稱關(guān)系 R是定義在 S上的一個 等價關(guān)系 ，其中， i1等價于 j1， i2等價于 j2， …… ， ir等價于 jr。 }|{][, x R ySyyxSx R ?????Rx][在一些應用問題中，給出各個元素之間的聯(lián)系，要求將這些元素分成幾個集合，每個集合中的元素直接或間接有聯(lián)系。如果能得到完整的家譜，判斷兩個人是否是親戚應該是可行的，但如果兩個人的最近公共祖先與他們相隔好幾代，使得家譜十分龐大，那么檢驗親戚關(guān)系實非人力所能及。 設初始有一集合 S={0,1,2,3,4,5,6,7,8,9,10,11}，依次讀若干事先定義的等價對0?4,3?1,6?10,8?9,7?4,6?8,3?5,2?11,11?0. 每次讀入一個等價對后，把等價集合 union起來，則每讀入一個等價對后集合的狀態(tài)是 : 初始 {0},{1},{2},{3},{4},{5},{6},
教學教案相關(guān)推薦
鄂ICP備17016276號-1