Mastering Algorithms with C

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 --------------------------------- * * * *****************************************************************************/ ...