Question

Write the C module intSet to implement an unordered set of integers according to the specification given below. File intSet.h:

#ifndef INTSET_H

#define INTSET_H

typedef struct intsetType *intSet;

intSet createSet(); // returns an intSet created at runtime using malloc void

destroySet(intSet); // frees up the memory associated with its argument

void clear(intSet); // clears set to empty (freeing any memory if necessary)

int card(const intSet); // returns the cardinality of the set

bool equals(const intSet,const intSet); // returns true if 2 sets are equal, false

// otherwise; two sets are equal if they contain

// all of the same values

bool contains(const intSet,int); // retuns true if argument is in set, false otherwise

int largest(const intSet); // returns the largest item in the set; print error message // and exit if set is empty

int smallest(const intSet); // returns the smallest item in the set print error message // and exit if set is empty

void add(intSet s,int item); // adds item to s or does nothing if it is in set

void remove_(intSet s,int item); // removes item from s or does nothing if it is not in set

intSet union_(const intSet, const intSet); // set union

intSet intersect(const intSet, const intSet); // set intersection

intSet diff(const intSet s1, const intSet s2); // set difference, i.e. s1 - s2

bool isEmpty(const intSet); // returns true if the set is empty, false otherwise int

*toArray(const intSet); // returns an array representation of the set char

*toString(const intSet); // returns a string representation of the set;

// e.g. an empty set returns "{}", and a non-empty set containing

// the values 9,-52,17 would return the string "{-52,9,17}"

#endif

You may not modify file intSet.h in any way. Note that you must define intsetType in your C implementation file as a structure. Two of the routines (remove_, union_) contain an underscore (_) in the name because they conflict with a keyword in C (union) and a function in the standard libraries (remove). Start by defining your data structure(s) and createSet. Note that how you define your data structure(s) will strongly influence how you will need to write some of your functions. You should probably implement at least a first version of add next so you can begin to build a set, followed closely by either toArray or toString so you have the capability to actually inspect any intSet you create. Test and implement any new function you write completely before moving on to additional routines. Always remember that any routine defined in your module can be used in any of the other routines.

C coding help needed ASAP! Thank you.

Answer 1

Here is the code of intSet.h  

#ifndef INTSET_H
#define INTSET_H

typedef struct intsetType * intSet;
intSet createSet(); // returns an intSet created at runtime using malloc void
void destroySet(intSet); // frees up the memory associated with its argument
void clear(intSet); // clears set to empty (freeing any memory if necessary)
int card(const intSet); // returns the cardinality of the set
bool equals(const intSet, const intSet); // returns true if 2 sets are equal, false
// otherwise; two sets are equal if they contain
// all of the same values

bool contains(const intSet, int); // retuns true if argument is in set, false otherwise
int largest(const intSet); // returns the largest item in the set; print error message // and exit if set is empty
int smallest(const intSet); // returns the smallest item in the set print error message // and exit if set is empty
void add(intSet s, int item); // adds item to s or does nothing if it is in set
void remove_(intSet s, int item); // removes item from s or does nothing if it is not in set
intSet union_(const intSet, const intSet); // set union
intSet intersect(const intSet, const intSet); // set intersection
intSet diff(const intSet s1, const intSet s2); // set difference, i.e. s1 - s2
bool isEmpty(const intSet); // returns true if the set is empty, false otherwise int
int * toArray(const intSet); // returns an array representation of the set char
char * toString(const intSet); // returns a string representation of the set;
// e.g. an empty set returns "{}", and a non-empty set containing
// the values 9,-52,17 would return the string "{-52,9,17}"
#endif

Code of intSet.c as below

#include <stdlib.h>
#include <stdio.h>
#include <string.h>
#include <stdbool.h>
#include "intSet.h"

//Define node structure to hold data
struct node
{
int data;
struct node* next;
};

struct intsetType
{
struct node *set;
};

intSet createSet() // returns an intSet created at runtime using malloc
{
intSet iset = (intSet) malloc(sizeof(intSet));
iset->set = NULL;
return iset;
}

void destroySet(intSet iset) // frees up the memory associated with its argument
{
clear(iset);
free(iset);
}

void clear(intSet iset) // clears set to empty (freeing any memory if necessary)
{
struct node * n = iset->set;
while(n != NULL)
{
struct node * tmp = n;
n = n->next;
free(tmp);
}
iset->set = NULL;
}

int card(const intSet iset) // returns the cardinality of the set
{
int count = 0;
struct node * n = iset->set;
while(n != NULL)
{
n = n->next;
count ++;
}
return count;
}

bool equals(const intSet is1, const intSet is2) // returns true if 2 sets are equal, false
// otherwise; two sets are equal if they contain // all of the same values
{

struct node *n;
// check that every item from set 1 is also in set 2
for(n = is1->set; n != NULL; n = n->next)
{
if(! contains(is2, n->data))
return false;
}
//check that every item from set 2 is also in set 1
for(n = is2->set; n != NULL; n = n->next)
{
if(! contains(is1, n->data))
return false;
}
return true;

}

bool contains(const intSet iset,int item) // retuns true if argument is in set, false otherwise
{
struct node * n = iset->set;
while(n != NULL)
{
if(n->data == item)
return true;
n = n->next;
}
return false;
}

int largest(const intSet iset) // returns the largest item in the set; print error message
// and exit if set is empty
{
if(isEmpty(iset))
exit(1);
struct node * n = iset->set;
while(n->next != NULL) // go to last element
n = n->next;
return n->data;
}

int smallest(const intSet iset) // returns the smallest item in the set print error message
// and exit if set is empty
{
if(isEmpty(iset))
exit(1);
return iset->set->data;
}

void add(intSet s,int item) // adds item to s or does nothing if it is in set
{
// case 1: empty
if(isEmpty(s))
{
s->set = (struct node*) malloc(sizeof(struct node));
s->set->next = NULL;
s->set->data = item;
return;
}

struct node * p = NULL;
struct node * n = s->set;

// iterate and insert to keep sorted order intact
while(n != NULL)
{
if(n->data == item) // already exists
return; // do nothing
if(n->data > item) // insert before n
{
struct node *tmp = (struct node*) malloc(sizeof(struct node));
tmp->data = item;
tmp->next = n;

if(p) // not at beginning of list
{
p->next = tmp; // insert between p and n
}
else
{
s->set = tmp;
}
return;
}

//update for next iteration
p = n;
n = n->next;
}
// flow comes here implies addition at end of list
p->next = (struct node*)malloc(sizeof(struct node));
p->next->data = item;
p->next->next = NULL;
}

void remove_(intSet s,int item) // removes item from s or does nothing if it is not in set
{
struct node * p = NULL;
struct node * n = s->set;

while(n != NULL)
{
if(n->data == item) // found
{
if(p) // not first item
{
p->next = n->next;
}
else // first item
{
s->set = s->set->next;
}
free(n);
return;
}

//update for next iteration
p = n;
n = n->next;
}
}

intSet union_(const intSet s1, const intSet s2) // set union
{
struct node *n;
intSet iset = createSet();
//Add all from both sets
for(n = s1->set; n != NULL; n = n->next)
add(iset, n->data);
for(n = s2->set; n != NULL; n = n->next)
add(iset, n->data);
return iset;
}

intSet intersect(const intSet s1, const intSet s2) // set intersection
{
struct node *n;
intSet iset = createSet();
//Iterate over s1
for(n = s1->set; n != NULL; n = n->next)
{
if(contains(s2, n->data)) // add only if it exist in s2 as well
add(iset, n->data);
}
return iset;
}

intSet diff(const intSet s1, const intSet s2) // set difference, i.e. s1 - s2
{
struct node *n;
intSet iset = createSet();
//Iterate over s1
for(n = s1->set; n != NULL; n = n->next)
{
if(! contains(s2, n->data)) // add only if it does not exist in s2
add(iset, n->data);
}
return iset;
}

bool isEmpty(const intSet iset) // returns true if the set is empty, false otherwise
{
return iset->set == NULL;
}

int *toArray(const intSet iset) // returns an array representation of the set
{
int *arr = NULL;
int n, i = 0;
struct node *tmp;
n = card(iset);
if(n > 0)
{
arr = (int*)malloc(n * sizeof(int));
for(tmp = iset->set; tmp != NULL; tmp = tmp->next)
{
arr[i++] = tmp->data;
}
}
return arr;
}

char *toString(const intSet iset) // returns a string representation of the set;
// e.g. an empty set returns "{}", and a non-empty set containing
// the values 9,-52,17 would return the string "{-52,9,17}"
{
char * str = NULL;
struct node *tmp;
int first = 1;
int n = card(iset);
if(n == 0)
{
str = (char*)malloc(3 * sizeof(char));
strcpy(str, "{}");
return str;
}
// allocating space assuming maximum of 5 digit numbers plus a - sign and a comma separator
str = (char*)malloc((n * 7 + 2) * sizeof(char));
sprintf(str, "%s", "{");
for(tmp = iset->set; tmp != NULL; tmp = tmp->next)
{
if(first == 1)
{
first = 0;
sprintf(str, "%s%d", str, tmp->data);
}
else
sprintf(str, "%s,%d", str, tmp->data);
}
sprintf(str, "%s}", str);
return str;
}

Code of main.c file as below

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>
#include "intSet.h"

struct node {
int data;
struct node * next;
};

struct intsetType {
struct node * set;
};

int main() {
intSet s1, s2, s3;
char * s;
int small, large;
//Create two sets
s1 = createSet();
s2 = createSet();
//add member to set s1
add(s1, 3);
add(s1, 6);
add(s1, 9);
add(s1, 12);
//add member to set s2
add(s2, 2);
add(s2, 4);
add(s2, 6);
add(s2, 8);
remove_(s2, 8);

s = toString(s1);
printf("Set s1: %s\n", s);
free(s);

s = toString(s2);
printf("Set s2: %s\n", s);
free(s);

small = smallest(s1);
large = largest(s1);
printf("Smallest of (s1): %d\nLargest of (s1): %d\n", small, large);

s3 = union_(s1, s2);
s = toString(s3);
printf("Union of s1, s2: %s\n", s);
free(s);
destroySet(s3);

s3 = intersect(s1, s2);
s = toString(s3);
printf("Intersection of s1, s2: %s\n", s);
free(s);
destroySet(s3);

s3 = diff(s1, s2);
s = toString(s3);
printf("s1 - s2: %s\n", s);
free(s);
destroySet(s3);
return 0;
}

Below is the image of output of the program: