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

?求解步驟:

思考1.何為等價類？

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

思考2.構(gòu)思數(shù)據(jù)結(jié)構(gòu)

? ? ? ? 我們考慮采用鏈?zhǔn)浇Y(jié)構(gòu)表示。對本應(yīng)用而言,結(jié)點結(jié)構(gòu)中只需一個數(shù)據(jù)域和一個鏈域。為了結(jié)合隨機訪問第 i類的優(yōu)點,用n個單元的數(shù)組 seq[n]存放各類頭結(jié)點。

? ? ? 因為在算法的輸出階段,必須有某種機制指明足否已經(jīng)打印了成員i,所以設(shè)置數(shù)組put[n],單元內(nèi)容是 TRUE(未打?。┗?FALSE(已打?。?。

思考3.算法實現(xiàn)的兩個階段

第一階段:

? ? ? 讀入等價的成員偶對 (i，j); 我們用前面給出的數(shù)據(jù)作程序的輸入。while循環(huán)結(jié)束后,每個關(guān)系 j≡i對應(yīng)兩個結(jié)點,每個seq[i]指向一個鏈表,鏈表中的結(jié)點是根據(jù)輸入得到的同屬j的等價類成員。

第二階段:

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

?分解編程

1.準(zhǔn)備部分

prepare partion

a.定義程序用到的頭文件;

b.定義宏MAX表示程序最大所能運算的種類

c.定義程序中的數(shù)據(jù)結(jié)構(gòu)

d.定義帶錯誤處理的內(nèi)存分配函數(shù)

2.初始化

function of initial

a.根據(jù)用戶輸入所需的種類數(shù)n，為每一類型定義一個初始節(jié)點，其中數(shù)據(jù)域為類型號（0，n–1），鏈域為空;

b.為每一類的打印標(biāo)記put[i]賦初始值TRUE

3.讀入偶對

function of inputpairs

a.提示用戶按具體格式輸入偶對

b.判定偶對是否符合輸入結(jié)束條件（-1，-1）

c.判定用戶輸入的偶對是否合法并做出處理

4.輸出和處理偶對

output with predeal and deal

a.調(diào)用output_predeal函數(shù)，輸出未處理前的偶對種類情況

b.依次調(diào)用output_deal函數(shù)，通過其遞歸設(shè)計，輸出最終分類結(jié)果

5.輸出

a.處理前的輸出

輸入10個偶對，并輸出未處理前的的分類結(jié)果

b.處理后的輸出

一共有3大類:0、2、6

更多內(nèi)容請關(guān)注我！