Mastering Algorithms With C - Kyle Loudon [56]
Return Value
0if computing the difference is successful, or -1 otherwise.
Description
Builds a set that is the difference of set1 and set2. Upon return, setd contains the difference. Because setd points to data in set1, the data in set1 must remain valid until setd is destroyed with set_destroy.
Complexity
O (mn), where m and n are the number of members in set1 and set2, respectively.
Name
set_is_member
Synopsis
int set_is_member(const Set *set, const void *data);
Return Value
1 if the member is found, or otherwise.
Description
Determines whether the data specified by data matches that of a member in the set specified by set.
Complexity
O (n), where n is the number of members in the set.
Name
set_is_subset
Synopsis
int set_is_subset(const Set *set1, const Set *set2);
Return Value
1 if the set is a subset, or otherwise.
Description
Determines whether the set specified by set1 is a subset of the set specified by set2.
Complexity
O (mn), where m and n are the number of members in set1 and set2, respectively.
Name
set_is_equal
Synopsis
int set_is_equal(const Set *set1, const Set *set2);
Return Value
1 if the two sets are equal, or otherwise.
Description
Determines whether the set specified by set1 is equal to the set specified by set2.
Complexity
O (mn), where m and n are the number of members in set1 and set2, respectively.
Name
set_size
Synopsis
int set_size(const Set *set);
Return Value
Number of members in the set.
Description
Macro that evaluates to the number of members in the set specified by set.
Complexity
O (1)
Implementation and Analysis of Sets
The structure Set is the set data structure. A good way to implement a set is as a linked list. A simple way to do this is to typedef Set to List (see Example 7.1). In addition to simplicity, using a typedef has the benefit of making the set somewhat polymorphic, just as was described for stacks and queues (see Chapter 6). Thus, because the set is a linked list, we can use linked list operations on it when we want it to act like one. The biggest benefit of this with sets is that we can use list_next to traverse a set, and list_rem_next to remove members without having to identify them by the data they store. Recall that set_remove only removes members keyed by their data, which can be a problem when we do not know the members a set contains.
In general, the set operations presented here are somewhat costly, primarily because many of them search for members of one set in another by traversing each member. However, we can improve the running times of these operations by using a more efficient searching technique, such as hashing (see Chapter 8). Nevertheless, the implementation provided here is a general-purpose approach whose performance is adequate for small to medium-sized sets of data.
Example 7.1. Header for the Set Abstract Datatype
/*****************************************************************************
* *
* -------------------------------- set.h --------------------------------- *
* *
*****************************************************************************/
#ifndef SET_H
#define SET_H
#include #include "list.h" /***************************************************************************** * * * Implement sets as linked lists. * * * *****************************************************************************/ typedef List Set; /***************************************************************************** * * * --------------------------- 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); int set_intersection(Set