只要受過教育的人相信對集合的概念並不陌生，集合是標記著具有某些相關聯或相互依賴的一系列離散數據。集合有兩個重要的特點：
第一，集合中的數據成員是無序的，如果{1,3},{3,1}都表示同一集合;
第二，每個數據成員在集合中不能重復，僅且只出現一次，如{1,3,1}則不能稱之為集合。
雖然我們都了解集合，也知道集合的一些基本概念及數學運算，但是在計算學科中，對集合的數據結構表示還是比較困難的，特別是C語言，因為C語言本身沒有集合的這種特性，但是某些其它高級語言應該是有集合特性的，如python，perl等。本文的主要目的就是用C語言來實現“集合”這種數據結構，然後完成集合的一些操作。在進入主題之前，先復習一下集合的一些基本操作：
1 並操作:
2 交操作:
3 差操作：
注：德摩根定律：
s1-(s2並s3) = (s1-s2)交(s1-s3)
s1-(s2交s3) = (s1-s2)並(s1-s3)
有了這些基本概念之後，就不難理解集合的操作方式了。前面說道，集合是一種數據結構，也是一種組織數據的方式，把一些相關聯的數據組織在一起，從這個意義上來說，集合結構的數據存儲方式也可以是鏈表，可以用一個鏈表來表示某一個集合，這麼理解來看，集合也是在鏈表的基礎上進行了概念的延伸與擴展。並且，用鏈表的方式來表示集合這種數據結構也並有多態的特性，因為除了集合本身的一些基本操作外，有某些情況下，我們也可以使用鏈表的一些基本操作，比如當需要對集合中的數據進行遍歷的時候，就可以用鏈表的方式進行遍歷操作了。
一、集合的數據結構及接口定義(set.h)
集合的數據結構的定義也建立在鏈表的基礎上，實際上就是鏈表的數據結構定義，只不過用typedef語句重新命名而已。如下：
[cpp]
/*
* filename: set.h
* author: zhm
* date: 2013-01-06
*/
#ifndef SET_H
#define SET_H
#include <stdlib.h>
#include "list.h"
typedef List Set; //將鏈表經typedef重命名為Set集合類型
下面是集合的相關操作接口，如下：
[cpp]
/* public interface */
void set_init(Set *set, int (*match)(const void *key1, const void *key2),
void (*destroy)(void *data)); //集合初始化操作
#define set_destroy list_destroy //集合銷毀,重命名鏈表的銷毀操作
int set_insert(Set *set, const void *data); //將某一數據插入至集合中
int set_remove(Set *set, void **data); //從集合中移除某一數據
int set_union(Set *setu, const Set *set1, const Set *set2); //集合的並操作，即setu = set1 並 set2
int set_difference(Set *setd, const Set *set1, const Set *set2); //集合的差操作, 即setd = set1-set2
int set_intersection(Set *seti, const Set *set1, const Set *set2); //集合的交操作：即seti = set1 交 set2
int set_is_member(const Set *set, const void *data); //判斷某一數據是否在集合中
int set_is_subset(const Set *set1, const Set *set2); //集合set1是否為set2的子集，是則返1,否則0
int set_is_equal(const Set *set1, const Set *set2); //set1是否等於set2，是否返1，否則0
#define set_size(set) ((set)->size) //返回集合中元數據大小
#endif
上述接口聲明後面的注釋已經非常清楚，所以不再累述，但是需要注意set_init()中的第二個參數，即函數指針match, 此函數由用戶自己定義，用於匹配兩個元素是否相同，如果key1 = key2,則返回1,如果key1 != key2,則返回0, 如果錯誤則返回-1。
二、集合的接口實現細節(set.c)
(1) set_init
此函數在鏈表的初始化基礎上，對match域進行初始化。代碼如下所示：
[cpp]
/*
* filename: set.c
* author: zhm
* date: 2013-01-06
*/
#include <stdlib.h>
#include <string.h>
#include "list.h"
#include "set.h"
/* set_init */
void set_init(Set *set, int (*match)(const void *key1, const void *key2),
void (*destroy)(void *data))
{
/* init the list */
list_init(set, destroy);
set->match = match;
return;
}
(2) set_destroy
集合的銷毀操作同鏈表操作，只不過換了個馬甲。。。
(3) set_insert
集合的插入操作，在插入到集合之前，需要判斷被插入的數據是否在集合中已經存在，根據集合的特性，集合中的元素是不能重復的。
[cpp]
/* set_insert */
int set_insert(Set *set, const void *data)
{
/* Do not allow the insertion of duplicates. */
if( set_is_member(set, data) )
return 1;
return list_ins_next(set, list_tail(set), data); //調用鏈表的插入元素操作
}
(4) set_remove
從集合中刪除某一元素操作接口，邏輯思路也很簡單，在執行刪除操作之前需要判斷元素為集合中的成員，如果是則刪除，不是則返回相應錯誤信息。
[cpp]
/* set_remove */
int set_remove(Set *set, void **data)
{
ListElmt *member, *prev; //注意prev，用於記錄被刪除元素前面的那一元素位置，為後續刪除作好准備
/* Find the member to remove */
prev = NULL;
for( member = list_head(set); member != NULL; member = list_next(member) )
{
if( set->match(list_data(member), *data) )
{
break;
}
prev = member;
}
/* Return if the member was not found */
if( member == NULL )
return -1;
/* remove the member */
return list_rem_next(set, prev, data);
}
(5) set_union
集合的並操作，它實現的思想是，首先先將集合set1的元素全部拷貝至集合setu中，按照集合特性，以及並操作的特點，集合set2中的元素也應存至setu中，但是需要注意元素的重復性問題，所以在拷貝set2中的元素之前需要做個判斷，即判斷set2中的元素是否已經存在於set1中，如果存在則不添加，否則需要添加，具體過程參見如下代碼：
[cpp]
/* set_union */
int set_union(Set *setu, const Set *set1, const Set *set2)
{
void *data;
ListElmt *member;
/* initialize the set for the union */
set_init( setu, set1->match, NULL );
/* Insert the members of the first set */
for( member = list_head(set1); member != NULL; member = list_next(member) )
{
data = list_data(member);
if( list_ins_next(setu, list_tail(setu), data) != 0 )
{
set_destroy(setu);
return -1;
}
}
/* Insert the members of the second set. */
for( member = list_head(set2); member != NULL; member = list_next(member) )
{
if( set_is_member(set1, list_data(member)) )
{
continue;
}
else
{
data = list_data(member);
if( list_ins_next(setu, list_tail(setu), data) != 0 )
{
set_destroy(setu);
return -1;
}
}
}
return 0;
}
(6) set_difference
集合的差操作，它實現的思路是，集合setd保存的是差操作的結果，即set1-set2，所以根據差的定義，setd中要保存的是集合set1中的元素，並且set1中的這些元素必須是非集合set2的成員。具體代碼如下：
[cpp]
/* set_difference */
int set_difference(Set *setd, const Set *set1, const Set *set2)
{
ListElmt *member;
void *data;
/* Initialize the set for the difference */
set_init(setd, set1->match, NULL);
/* Insert the members from set1 not in set2 */
for( member = list_head(set1); member != NULL; member = list_next(member) )
{
if( !set_is_member(set2, list_data(member)) )
{
data = list_data(member);
if( list_ins_next(setd, list_tail(setd), data) != 0 )
{
set_destroy(setd);
return -1;
}
}
}
return 0;
}
(7) set_intersection
集合的交操作，它實現的思路是，遍歷set1中的每個成員，然後判斷set1中的每個成員是否也屬於集合set2,如果是則滿足條件，在集合seti中記錄，下面為具體的實現代碼：
[cpp]
/* set_intersection */
int set_intersection(Set *seti, const Set *set1, const Set *set2)
{
ListElmt *member;
void *data;
/* initialize the set for the intersection */
set_init(seti, set1->match, NULL);
/* Insert the members present in both sets */
for( member = list_head(set1); member != NULL; member = list_next(member) )
{
if( set_is_member(set2, list_data(member)) )
{
data = list_data(member);
if( list_ins_next(seti, list_tail(seti), data) != 0 )
{
set_destroy(seti);
return -1;
}
}
}
return 0;
}
(8) set_is_member
此接口用於判斷某個數據是否是集合中的成員，具體的判斷方法是根據用戶自己定義的match函數實現的。如果是集合中的成員返1，否則返0
[cpp]
/* set_is_member */
int set_is_member(const Set *set, const void *data)
{
ListElmt *member;
for(member = list_head(set); member != NULL; member = list_next(member))
{
if( set->match(list_data(member), data) )
{
return 1;
}
}
return 0;
}
(9) set_is_subset
此接口用於判斷集合set1是否是集合set2的子集，首先先判斷元素大小，如果集合set1元素個數 大於 set2，則set1不可能是set2的子集。這是子集條件的前提。然後再遍歷set1中的每個成員，只要set1中的某個成員不在set2中，則說明set1就不是set2的子集，如果set1中的每個成員也都存在於set2中，則表明set1是set2的子集。代碼如下:
[cpp]
/* set_is_subset */
int set_is_subset(const Set *set1, const Set *set2)
{
ListElmt *member;
if( set_size(set1) > set_size(set2) )
return 0;
for(member = list_head(set1); member != NULL; member = list_next(member))
{
if( !set_is_member(set2, list_data(member)) )
{
return 0;
}
}
return 1;
}
(10) set_is_equal
此接口用於判斷兩集合是否相等，條件有兩個。條件一：元數個數大小相等；條件二：其中一個集合是另一集合的子集，只要滿足這兩條件，則表示集合相等。
[cpp]
/* set_is_equal */
int set_is_equal( const Set *set1, const Set *set2 )
{
if( set_size(set1) != set_size(set2) )
return 0;
return set_is_subset(set1, set2);
}
三、集合操作的應用舉例(main.c)
先看代碼，如下：
[cpp]
/*
* filename: main.c
* author:zhm
* date: 2012-12-06
*/
#include <string.h>
#include <stdlib.h>
#include <stdio.h>
#include "list.h"
#include "set.h"
/* destroy */
void destroy(void *data)
{
printf("in destroy\n");
free(data);
return;
}
/* compare */
int compare(const void *key1, const void *key2)
{
if( *(int *)key1 == *(int *)key2 )
{
return 1;
}
return 0;
}
/* main */
int main(int argc, char **argv)
{
int ret, i;
int *int_ptr = NULL;
ListElmt *member = NULL;
/* set1 = {1,2,3,4,5}
* set2 = {1,2,3,4,5,8,9}
*/
Set set1, set2;
Set setu, setd, seti; //union, difference, intersection
/* initialize sets:set1,set2 */
set_init(&set1, compare, destroy);
set_init(&set2, compare, destroy);
/* insert the data:1-5 into set1 and set2*/
for( i = 1; i <= 5; i++ )
{
int_ptr = NULL;
int_ptr = (int *)malloc(sizeof(int));
if( int_ptr == NULL )
return -1;
*int_ptr = i;
set_insert(&set1, (void *)int_ptr);
set_insert(&set2, (void *)int_ptr);
}
/* insert the data: 8,9 into set2 */
for( i = 1; i <= 2; i++ )
{
int_ptr = NULL;
int_ptr = (int *)malloc(sizeof(int));
if( int_ptr == NULL )
return -1;
*int_ptr = 7+i;
set_insert(&set2, (void *)int_ptr);
}
/* display the size for the sets :set1, set2 */
printf("size of set1 = %d\n", set_size(&set1));
printf("size of set2 = %d\n\n", set_size(&set2));
ret = set_is_subset(&set1, &set2);
if( ret == 1 )
{
printf("set1 belong to set2\n");
}
ret = set_is_equal(&set1, &set2);
if( ret != 0 )
{
printf("set1 not equal set2\n");
}
ret = set_union(&setu, &set1, &set2);
if( ret != 0 )
return -1;
printf("setu = {");
for( member = list_head(&setu); member != NULL; member = list_next(member) )
{
printf("%d ,", *(int*)list_data(member));
}
printf("}\n");
ret = set_intersection(&seti, &set1, &set2);
if( ret != 0 )
return -1;
printf("seti = {");
for( member = list_head(&seti); member != NULL; member = list_next(member) )
{
printf("%d ,", *(int*)list_data(member));
}
printf("}\n");
ret = set_difference(&setd, &set1, &set2);
if( ret != 0 )
return -1;
printf("setd = {");
for( member = list_head(&setd); member != NULL; member = list_next(member) )
{
printf("%d ,", *(int*)list_data(member));
}
printf("}\n");
set_destroy(&setu);
set_destroy(&seti);
set_destroy(&setd);
set_destroy(&set1);
set_destroy(&set2);
return 0;
}
上面的一個應用主要完成這麼幾件事：
1 通過集合的插入元素操作，生成兩個集合,set1 和 set2,它們的值分別為：set1 = {1,2,3,4,5},set2={1,2,3,4,5,8,9}
2 判斷set1是否是set2的子集
3 判斷set1是否等於set2
4 set1及set2的交，並，差操作
5 最後是集合的銷毀。
上述的compare函數是用戶自定義的比較函數，需要將此函數作為指針傳遞給集合初始化接口set_init()中。
上述代碼經過編譯、運行的結果如下：
