数据结构学习之集合

        只要受过教育的人相信对集合的概念并不陌生，集合是标记着具有某些相关联或相互依赖的一系列离散数据。集合有两个重要的特点：

        第一，集合中的数据成员是无序的，如果{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 inte易做图ce */  

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,

补充：软件开发 , C++ ,