数据结构学习之集合(三)
}
}
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
#include
#include
#include "list.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 no