COEN12 HW3

Written in C programming language: you will implement a set abstract data type, first for strings and then for generic pointer types. Your interface and implementation must be kept separate.

The interface to your abstract data type must provide the following operations: SET *createSet(int maxElts); return a pointer to a new set with amaximumcapacity of maxElts void destroySet(SET *sp); deallocate memory associated with the set pointed to by sp int numElements(SET *sp); return the number of elements in the set pointed to by sp void addElement(SET *sp, char *elt); add elt to the set pointed to by sp void removeElement(SET *sp, char *elt); remove elt from the set pointed to by sp char *findElement(SET *sp, char *elt); if elt is present in the set pointed to by sp then return the matching element, otherwise return NULL char **getElements(SET *sp); allocate and return an array of elements in the set pointed to by sp

For your reference,

Implement a set using a hash table of length m> 0 and linear probing to resolve collisions. Create an auxiliary function search that contains all of the search logic as you did for the previous assignment, and use search to Implement the functions in your interface. The following hash function should be used: unsigned strhash (char *s) { unsigned hash-8; while (es !- '10') hash - 31 hash + S ++; return hash; As in the previous assignment, your implementation should allocate memory and copy the string when adding and therefore also deallocate memory when removing. 3 An ADT for Generic Pointer Types So far, we have only developed ADTs for strings. If we wanted to store another type of data, we would need to copy our implementation and change char. "to the new type, which is both tedious and error-prone. Fortunately, C provides a generic pointer type: a pointer to void can be assigned to or from any other pointer type. For example, the function malloc returns a pointer to void so its result can be assigned to any pointer type. Similarly, the function free takes a pointer to void as a parameter so it can be passed any pointer type. By changing "char." to "void ." In our Implementation, we can write an ADT that works on generic pointer types, allowing us to store strings, pointers to structures, or whatever we like. The test program counts uses a generic set ADT to store structures rather than just strings in order to count the number of times each word occurs in a file. Unfortunately, we need to do a little more than just replace "char." with "void ." in our implementation. Our Implementation needs to be told how to compare two elements as well as compute the hash value for an element. After all, strcmp and strhash only work on strings. Therefore, our createSet function must take extra parameters that are now pointers to these two functions: SET .createSet(int maxElts, int (.compare)(), unsigned (=hash)()); These two functions must be stored internally as part of the set structure. Rather than calling strcmp and strhash in the function search, you will need to call the client provided functions instead. Assuming that the pointer to the set is sp and the comparison function is stored as a member called compare: (sp->compare)(...); Our new generic set ADT also does not know how to allocate or deallocate the elements It stores, so rather than calling strdup and free, it simply coples the pointers themselves. The client is responsible for managing memory Such is the price we pay for using a generic ADT. Implement a set using a hash table of length m> 0 and linear probing to resolve collisions. Create an auxiliary function search that contains all of the search logic as you did for the previous assignment, and use search to Implement the functions in your interface. The following hash function should be used: unsigned strhash (char *s) { unsigned hash-8; while (es !- '10') hash - 31 hash + S ++; return hash; As in the previous assignment, your implementation should allocate memory and copy the string when adding and therefore also deallocate memory when removing. 3 An ADT for Generic Pointer Types So far, we have only developed ADTs for strings. If we wanted to store another type of data, we would need to copy our implementation and change char. "to the new type, which is both tedious and error-prone. Fortunately, C provides a generic pointer type: a pointer to void can be assigned to or from any other pointer type. For example, the function malloc returns a pointer to void so its result can be assigned to any pointer type. Similarly, the function free takes a pointer to void as a parameter so it can be passed any pointer type. By changing "char." to "void ." In our Implementation, we can write an ADT that works on generic pointer types, allowing us to store strings, pointers to structures, or whatever we like. The test program counts uses a generic set ADT to store structures rather than just strings in order to count the number of times each word occurs in a file. Unfortunately, we need to do a little more than just replace "char." with "void ." in our implementation. Our Implementation needs to be told how to compare two elements as well as compute the hash value for an element. After all, strcmp and strhash only work on strings. Therefore, our createSet function must take extra parameters that are now pointers to these two functions: SET .createSet(int maxElts, int (.compare)(), unsigned (=hash)()); These two functions must be stored internally as part of the set structure. Rather than calling strcmp and strhash in the function search, you will need to call the client provided functions instead. Assuming that the pointer to the set is sp and the comparison function is stored as a member called compare: (sp->compare)(...); Our new generic set ADT also does not know how to allocate or deallocate the elements It stores, so rather than calling strdup and free, it simply coples the pointers themselves. The client is responsible for managing memory Such is the price we pay for using a generic ADT