集合我們高中都學過吧？

最重要的幾個特點：元素不能重復、各個元素之間沒有關系、沒有順序

集合內的元素可以是單元素或者是集合。

對集合的操作：交集并集差集等，還有對自身的加減等。

需要頻繁的加減元素，所以順序存儲效率較低，但是我們還是說一下是怎么實現的：

? ? 用01向量表示集合，因為現實中任何一個有窮集合都能對應到一個0、1、2.....n這么一個序列中。所以可以對應過來，每位的01代表這個元素存在與否即可。

鏈接存儲表示使用有序鏈表來實現，雖然集合是無序的，但是我們的鏈表可以是有序的。可以按升序排列。而鏈表理論上可以無限增加，所以鏈表可以表示無限集。

下面我們來實現一下：

我們定義一個節點：

typedef int ElemType;
typedef struct SetNode{//節點定義ElemType data;//數據struct SetNode * link;
}*LinkedSet//集合定義

然后要實現那些操作了，首先想插入吧：我們對于一個新元素，查找集合中是否存在，存在就不插入，不存在就插入到查找失敗位置。

刪除也簡單，查找存在就刪除。

?

我們說兩個集合的操作：

求兩個集合的并：

兩個鏈表，都是升序。把他們去重合并即可。

其實和鏈表歸并的merge過程是一樣的，只是相等的時候插入一個，兩個指針都向后走就行了。

我就再寫一遍吧。

void UnionSet(LinkedSet & A,LinkedSet & B,LinkedSet & C)
{SetNode *pa=A->link,*pb=B->link,*pc=C;while(pa && pb)//都不為空{if(pa->data==pb->data)//相等，插一次，兩邊向后{pc->link=new SetNode;pc->data=pa->data;pa=pa->link;pb=pb->link;}else if(pa->data<pb->data)//插小的，小的向后{pc->link=new SetNode;pc->data=pa->data;pa=pa->link;}else{pc->link=new SetNode;pc->data=pb->data;pb=pb->link;}pc=pc->link;//注意指針}if(pa)p=pa;//剩下的接上else p=pb;//只執行一個while(p)//依次復制{pc->link=new SetNode;pc->data=p->data;pc=pc->link;p=p->link;}pc->link=NULL;
}

求兩個集合的交，更簡單，還是這三種情況，誰小誰向后，相等才插入。

void UnionSet(LinkedSet & A,LinkedSet & B,LinkedSet & C)
{SetNode *pa=A->link,*pb=B->link,*pc=C;while(pa && pb)//都不為空{if(pa->data==pb->data)//相等，插一次，兩邊向后{pc->link=new SetNode;pc->data=pa->data;pa=pa->link;pb=pb->link;pc=pc->link;//注意指針,就不是每次都向后了，只有插入才向后}else if(pa->data<pb->data)//小的向后{pa=pa->link;}else{pb=pb->link;}}pc->link=NULL;
}

求兩個集合的差：高中可能沒學這個概念，其實就是A-B，就是B中的元素，A都不能有了。

運算你可以把B元素全過一遍，A中有就去掉，但是這樣時間復雜度太高了，我們需要O(A+B)而不是O(A*B)

因為有序，很好操作，還是兩個指針，

如果AB相同，都向后移。

或者，B小，B就向后移。

如果A小，說明B中不含這個元素，我們把它復制到結果鏈表里。

?

思想還行，實在懶得寫了，有時間再說吧。