Mastering Algorithms With C - Kyle Loudon [57]
int set_difference(Set *setd, const Set *set1, const Set *set2);
int set_is_member(const Set *set, const void *data);
int set_is_subset(const Set *set1, const Set *set2);
int set_is_equal(const Set *set1, const Set *set2);
#define set_size(set) ((set)->size)
#endif
set_init
The set_init operation initializes a set so that it can be used in other operations (see Example 7.2). Since a set is a linked list, list_init is called to initialize it. The match member is set to match by hand because this member is not used by linked lists and is therefore not set by list_init.
The runtime complexity of set_init is the same as list_init, or O (1).
set_destroy
The set_destroy operation destroys a set (see Example 7.1). Since a set is a linked list and requires being destroyed in the same manner, set_destroy is defined to list_destroy.
The runtime complexity of set_destroy is the same as list_destroy, or O (n), where n is the number of members in the set.
set_insert
The set_insert operation inserts a member into a set (see Example 7.2). Since a member must not occur more than once in a set, set_is_member is called to make sure that the set does not already contain the new member. As long as the member does not already exist in the set, list_ins_next is called to insert the member.
The runtime complexity of set_insert is O (n) because set_is_member runs in O (n) time, and list_ins_next runs in O (1).
set_remove
The set_remove operation removes a member from a set by traversing it using list_next until match determines that the member to be removed has been found (see Example 7.2). The pointer prev points just before the member to be removed since this is required by list_rem_next. The list_rem_next operation sets data to point to the data from the member removed.
The runtime complexity of set_remove is O (n), where n is the number of elements in the set. This is because, in the worst case, the entire set must be traversed in order to find the member to be removed. This results in n times O (1), the cost of the statements within the loop, for a running time of O (n) overall. Once the member is found, list_rem_next removes it in O (1) time.
set_union
The set_union operation builds a set, setu, which is the union of the sets set1 and set2 (see Example 7.2). First, setu is initialized by calling set_init. Next, the members of set1 are inserted into setu by calling list_ins_next repeatedly for each member of set1. Finally, the members of set2 are inserted into setu in a similar manner except that set_is_member is called before each insertion to ensure that no members are duplicated in setu.
The runtime complexity of set_union is O (mn), where m is the size of set1 and n is the size of set2. In the first loop, each member of set1 is traversed and inserted into setu, which results in a running time of O (m). In the second loop, each element of set2 is traversed, which results in n times the cost of the statements within this loop. This loop contains the O (m) operation set_is_member. Therefore, the overall complexity of the loop is O (mn). Since the two loops are executed one after another, the complexity of set_union is the more expensive of the two, or O (mn).
set_intersection
The set_intersection operation builds a set, seti, which is the intersection of the sets set1 and set2 (see Example 7.2). First, seti is initialized by calling set_init. Next, for each member of set1, set_is_member is called to determine whether the member is in set2. If so, the member is inserted into seti.
The runtime complexity of set_intersection is O (mn), where m is the size of set1 and n is the size of set2. This is because for each member in set1, the O (n) operation set_is_member is called to determine whether the member is in set2.
set_difference
The set_difference operation builds a set, setd, which is the difference of the sets set1 and set2 (see Example 7.2). First, setd is initialized by calling set_init. Next, for each member of set1, set_is_member