Fun with Mathematical Sets in C

I thought I would review some discrete math for fun by writing some quick programs for handling discrete math problems.

Let’s start with a structure to contain a set. It will have three parts – the name of the set as a string, an array of integers that is the actual set itself, and an integer value indicating the cardinality of the set, which is how many discrete elements are in the set. Defining a type definition for a pointer to a set structure will help keep our code readable.

struct set{
    char *setname;
    int *set;
    int cardinality;
};

typedef struct set * SET;

Let’s then set up a number of utility functions for working with the sets.

I’m going to go ahead and use scanf() since this is just coding for fun. I want to create two functions for prompting and returning an integer value and a string value. For the string, I am going to define a named literal called SMALL_STRING_LENGTH that will be used to construct a 256 byte buffer for accepting string input.

I will also create two functions, one for allocating and then filling a dynamic array of integers, and the second for printing the dynamic array of integers. The function for printing the integer array adds comma delimiters between the numbers being printed.

//--utility functions ----------
int promptForInt(char *thePrompt){
    int returnValue = 0;
    printf("%s ", thePrompt);
    scanf("%d", &returnValue);
    return returnValue;
}

char *promptForString(char *thePrompt){
    char strBuffer[SMALL_STRING_LENGTH];
    char *rString;
    int strLength;
    printf("%s ", thePrompt);
    scanf("%s", strBuffer);
    
    //strlen returns offset of string terminating 
    //character
    strLength = strlen(strBuffer) + 1;
    
    rString = (char *)malloc(sizeof(char) * strLength);
    strcpy(rString, strBuffer);
    
    return rString;
    
}

int *fillDynamicIntArray(int length){
    int i = 0;
    
    int *returnArray = (int *)malloc(sizeof(int) * length);
    
    for(i = 0; i < length; i++){         
        printf("Element %d, ", i);         
        *(returnArray + i) = promptForInt("please enter the value: "); 
        printf("%d elements left\n", length - i - 1);     
     }         
       
     return returnArray; 
} 

void printIntArray(int *theArray, int length){     
       int i;     
       if(length > 0){
        printf("%d", *theArray);
    }
    for(i = 1; i < length; i++){
        printf(", %d", *(theArray + i));
    }
}

//--end utility functions------

The the last set of functions is for dealing with the sets themselves.

The printSet() function prints the set, including its name and the contents of the set. It calls the printIntArray() utility function defined above.

//displays the set, including the set name
void printSet(SET theSet){
    printf("Set %s ", theSet->setname);
    printf("{ ");
    printIntArray(theSet->set, theSet->cardinality);
    printf(" } ");
}

SET getSet(){
   char stringBuffer[SMALL_STRING_LENGTH];    
   SET returnSet = (SET)malloc(sizeof(SET));    
    
   returnSet->setname = promptForString("What is the name of the set?"); 
   returnSet->cardinality = promptForInt("How many elements are in the set?");
   returnSet->set = fillDynamicIntArray(returnSet->cardinality);
   
   //remove duplicate elements
   dedupeSet(&returnSet);
   
   return returnSet;
}

The final function is the most complex. It searches through the set’s integer array and removes any deduplicated elements. It then copies this array to another array, and frees the original array.

While sets can have duplicates, the duplicates aren’t really duplicates, they’re just the same element mentioned twice (or more). Each element in a set has to be distinct from the other.

void dedupeSet(SET *theSet){
     SET ourSet = *theSet;
     int *potentialSet;
     int potentialCardinality = 1;
     
     int *setStart = ourSet->set;
     int *setEnd = ourSet->set + ourSet->cardinality - 1;
     int *current;
     
     while(setStart <= setEnd){
         current = setStart + 1;
         while(current <= setEnd){              
         if(*current == *setStart){                  
           *current = *setEnd;                 
            setEnd--;             
         } else {
                  current++;              
         }        
         }          
         setStart++;
         potentialCardinality++;
      } 
     //allocate new int array if duplicate elements have been found     
     if((potentialCardinality)!=ourSet->cardinality){
        //change the cardinality to account for duplicate items
         ourSet->cardinality = potentialCardinality;
         //allocate new int array with the correct size
         potentialSet = (int *)malloc(sizeof(int) * (potentialCardinality));
         //set pointer to start of original set and to start of the new set
         //continue copying until the pointer to the start of the set reaches the end
         //increment pointers to both sets
         for(setStart = ourSet->set, current = potentialSet; setStart <= setEnd; setStart++, current++){
              //copy from old set to new set              
              *current = *setStart;          
          }          
         //clean up the memory from the old set         
         free(ourSet->set);
        //assign new set to the set structure
        ourSet->set = potentialSet;
     }
     
}

The final, final function we will define here is a function to free up the memory allocated for the set, and then finally free the set itself

void deleteSet(SET theSet){
    free(theSet->setname);
    free(theSet->set);
    free(theSet);
    theSet = NULL;
}

Now let’s use the functions in our program

int main(){
    
    char buffer[256];
    
    int counter = 0;
    
    SET setA, setB;
    
    printf("Please fill out the first set\n");
    setA = getSet();
    printSet(setA);
    
    printf("Please fill out the second set\n");
    setB = getSet();
    printSet(setB);
    
    deleteSet(setA);
    deleteSet(setB);

    return 0;   
    
}
Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s