频道栏目
首页 > 程序开发 > 软件开发 > C++ > 正文
数据结构学习之集合
2013-01-08 10:17:53      个评论      
收藏   我要投稿
       

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

        第一,集合中的数据成员是无序的,如果{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()中。

        上述代码经过编译、运行的结果如下:

 

     

 

 

 

点击复制链接 与好友分享!回本站首页
相关TAG标签 习之 数据结构
上一篇:c++实现欧拉回路问题
下一篇:sizeof操作符详解一
相关文章
图文推荐
点击排行

关于我们 | 联系我们 | 广告服务 | 投资合作 | 版权申明 | 在线帮助 | 网站地图 | 作品发布 | Vip技术培训 | 举报中心

版权所有: 红黑联盟--致力于做实用的IT技术学习网站