等價類演算法之鏈表法

?問題描述:通過自定義輸入n對偶對(偶對中的兩個元素同屬於一類），通過等價類演算法編程，求出共有哪幾種類並分別列印它們。

?求解步驟:

思考1.何為等價類？

定義在集合S上的關係 ≡"稱為 集合S上的等價關係，當且僅當它在 S上是自反的reflexive(x=x)、對稱的symmetric(x=y?y=x)、傳遞的transitive(x=y&&y=z?z=x)。

思考2.構思數據結構

我們考慮採用鏈式結構表示。對本應用而言,結點結構中只需一個數據域和一個鏈域。為了結合隨機訪問第 i類的優點,用n個單元的數組 seq[n]存放各類頭結點。

因為在演算法的輸出階段,必須有某種機制指明足否已經列印了成員i,所以設置數組put[n],單元內容是 TRUE(未列印）或 FALSE(已列印）。

思考3.演算法實現的兩個階段

第一階段:

讀入等價的成員偶對 (i，j);? 我們用前面給出的數據作程序的輸入。while循環結束後,每個關係 j≡i對應兩個結點,每個seq[i]指向一個鏈表,鏈表中的結點是根據輸入得到的同屬j的等價類成員。

第二階段:

從0開始找出所有形式為 (0，j )的 偶對,其中0，j同屬一個等價類。根據傳遞性,通過偶對 （j，k）可以確定 k與 0也 同屬一個等價類。這個過程持續下去,直到找出、標記、列印包括 0的所有等價類成員。然後同理再確定其它等價類。

?分解編程

1.準備部分

prepare partion

喜歡這篇文章嗎？立刻分享出去讓更多人知道吧！