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;   
    
}

Linked Lists in C

Linked lists are ordered collections of data where each elements stores the location of the next element. Each element therefore contains two parts, the data and the link. The link is used to chain the elements together.

A list must at least have one separate pointer to the first element in the list; the name of this pointer is synonymous with the name of the list. This pointer is known as the head pointer, as it points to the head of the list.

Linked lists are made up of nodes. A node in a linked list is a structure that should have at least two fields, one for the data and one for the link. Nodes are self-referential structures in that each instance of the node structure should have a pointer to another instance of the same type.

typedef struct aNode {
	int data;
	struct aNode *link;
} LIST_NODE;

We can define an empty linked list as a single pointer that has the value NULL.

Let’s create a function that allocates memory for the node, assigns the data, and sets the link field to NULL.

LIST_NODE *createNode(int data) {
	LIST_NODE *newNode = (LIST_NODE *)malloc(sizeof(LIST_NODE));
	newNode->data = data;
	newNode->link = NULL;
	return newNode;
}

As there is no physical relationship between the nodes in a linked list in terms of where they are placed in memory, it is vital to ensure that each node links correctly to the next. Functions that insert or delete a node should return the head of the list; if the head has not been changed, then they simply return the original head address.

We will create three functions for adding and inserting nodes. The first function will simply append one node after another. The second function will set a node as the head of the list. The third function will insert a node at a specific location in the list.

//returns location of new node added to the list
LIST_NODE *appendNode(LIST_NODE *pre, LIST_NODE *theNode) {
	if (pre != NULL) {
                //if pre is at the end of the list
                //pre->link is NULL
                theNode->link = pre->link;
		pre->link = theNode;
	}
	return theNode;
}

LIST_NODE *setHead(LIST_NODE *head, LIST_NODE *theNode) {
	if (head != NULL) {
		theNode->link = head;
	}
	return theNode;
}

LIST_NODE *insertNode(LIST_NODE *head, LIST_NODE *pre, LIST_NODE *theNode) {
	LIST_NODE *returnHead = NULL;

	//if the head is not null, set it as the default return value
	//otherwise set it to pre
	if (head != NULL) {
		returnHead = head;
	}
	else {
		returnHead = pre;
	}
	
	//if the preceding node is the start of the list
	//or both pre and head are NULL
	if (head == pre) {
		//set new node as the head of the list
		returnHead = setHead(pre, theNode);
	} else {
		//inserting at middle or end
		//leave head as it was set initially
		appendNode(pre, theNode);
	}

	return returnHead;
}

Since every new node created has its link set automatically to null by the function that creates the node, we can be sure that any node we add to the end of the list will automatically end the list.

Since the first node of the list is stored in the head pointer, it is easy to append a new node to the beginning of the list, and make it the new head pointer.

To delete a node, we must remove it from the linked list by altering the pointers and then physically removing the node from heap memory. To delete  a node, we must have its location, given by its predecessor. We can then alter the links and return the memory to the heap using free().

LIST_NODE *deleteHead(LIST_NODE *head) {
	return deleteNode(head, NULL);
}

LIST_NODE * deleteNode(LIST_NODE *head, LIST_NODE *pre) {
	LIST_NODE *target;
	//deleting first node
	if (pre == NULL) {
		target = head;
		head = head->link;
	} //deleting other nodes
	else { 
		target = pre->link;
		pre->link = target->link;
	}

	free(target);
	return head;
}

To delete or insert a node, we must first find the node that precedes it. To do so, we must find the logical predecessor of the target node. We can design a search function to find a node based on an offset number from the head of the list, or we can design a search function find the last node in the list, or we can search the list to find a node with a particular value.

//returns a pointer to the node at the 0-index offset from the head
LIST_NODE *findByIndex(LIST_NODE *head, int offset) {
	int i = 0;
	LIST_NODE *prev = head;
	LIST_NODE *current = head->link;
	while (i++ < offset && current != NULL) { 		
               prev = current; 		
               current = current->link;
	}
	//previous node always holds value at the index 
	//if it exists
	return prev;
}

//finds and returns first match for the data value
LIST_NODE *findByDataValue(LIST_NODE *head, int dValue) {
	LIST_NODE *current = head;
	bool found = false;
	do {
		if (current->data == dValue) {
			found = true;
		}
		else {
			current = current->link;
		}
	} while (current != NULL && found == false);

	return current;
}

//find predecessor
LIST_NODE *findPredecessor(LIST_NODE *head, LIST_NODE *target) {
	LIST_NODE *predecessor = head;
	while (predecessor->link != target) {
		predecessor = predecessor->link;
	}
	return predecessor;
}

Any application that must process the entire list will use list traversal logic. To traverse the list, we will need to start at the beginning and work with each node in succession. A simple function for printing the entire list would involve starting at the head, printing the data stored in the head, checking to see if the next node is null, and if not, setting the current node to the next node, and repeating this process until the next node is null.

//print list
void printList(LIST_NODE *head) {
	LIST_NODE *current = head;
	while (current != NULL) {
		printf("%d\t", current->data);
		current = current->link;
	}
	printf("\n\n");
}

Let’s tie it all together in the main() function.

int main()
{
	LIST_NODE *head = createNode(1138);
	LIST_NODE *current = createNode(73);
	LIST_NODE * newNode = createNode(1701);
	LIST_NODE * deleteNodePred = NULL;

	appendNode(head, current);
	appendNode(current, newNode);

	current = createNode(1999);
	appendNode(newNode, current);

	newNode = createNode(73);
	current = appendNode(current, newNode);

	current = appendNode(current, createNode(3435));

	printList(head);

	newNode = createNode(389);

	appendNode(current, newNode);

	insertNode(head, newNode, createNode(404));

	insertNode(head, current, createNode(65537));

	printList(head);

	newNode = createNode(443);

	head = setHead(head, newNode);

	head = setHead(head, createNode(118));

	printList(head);

	deleteNodePred = findByIndex(head, 2);
	head = deleteNode(head, deleteNodePred);

	printList(head);

    return 0;
}

Representing Stacks in C

A stack is an ordered collection of objects in memory. C already has a data type that is an ordered collection – the array. We can therefore use the array to represent a stack; however, a drawback to this approach is that the number of items in an array is fixed at declaration. A stack, on the other hand, is a dynamically sized collection that grows and shrinks as items are pushed onto the stack and popped off of the stack.

There is more than one way to represent a stack in C. We can use the array to store a stack, as long as we declare the array to be large enough to store the maximum number of items we think will be placed on the stack. The start of the array functions as the bottom of the stack, and the last element in the array that holds data will be the top the stack that shifts as data is popped off the stack and pushed on the stack.

We can therefore declare a stack to be a structure containing an array as well an integer value indicating the top of the stack. If we declare the array as itself being of the struct type, we can declare a stack that contains different value types.

const int stack_array_size = 100;

enum StackArrayNodeType {integer, floatingpoint, character};

struct StackArrayNode {
	enum StackArrayNodeType;

	union {
		int iValue;
		double dValue;
		char cValue;
	};
};

struct StackArray {
	int top;
	struct StackArrayNode items[stack_array_size];
}; 

The top field in the StackArray structure is declared as an int, since it always represents an index or offset. We represent an empty stack by setting the top field to -1 or some other negative value. We can even set up a simply function to check if the stack is empty or not.

We need to declare a set of auxiliary functions for handling the nodes that make up item in the stack; remember here that each node is itself a stack consisting of an enumerated type identifier as well as a union allowing for different types of actual data stored.

//copy node after it has been popped off the stack
struct StackArrayNode *CopyNode(struct StackArrayNode source) {
	struct StackArrayNode *ReturnNode = (StackArrayNode*)malloc(sizeof(StackArrayNode));
	ReturnNode->type = source.type;
	switch (source.type) {
	case integer:
		ReturnNode->iValue = source.iValue;
		break;
	case floatingpoint:
		ReturnNode->dValue = source.dValue;
		break;
	case character:
		ReturnNode->cValue = source.cValue;
		break;
	}
	return ReturnNode;
}

//returns true only if able to identify type and print value to the screen
bool StackArrayNodePrint(const struct StackArrayNode *theNode) {
	bool returnValue = false;
	//check for NULL node
	if (theNode != NULL) {
		//print node according to its type
		switch (theNode->type) {
		case integer:
			printf("Type: Int \t Value: %d\n", theNode->iValue);
			returnValue = true;
			break;
		case floatingpoint:
			printf("Type: Double \t Value: %f\n", theNode->dValue);
			returnValue = true;
			break;
		case character:
			printf("Type: Char \t Value: %c\n", theNode->cValue);
			returnValue = true;
			break;
		}
	}
	return returnValue;
}

bool StackArrayNodeSetInt(struct StackArrayNode *theNode, int value) {
	bool returnValue = false;
	if (theNode->type == integer) {
		theNode->iValue = value;
		returnValue = true;
	}
	return returnValue;
}

bool StackArrayNodeSetChar(struct StackArrayNode *theNode, char value) {
	bool returnValue = false;
	if (theNode->type == character) {
		theNode->cValue = value;
		returnValue = true;
	}
	return returnValue;
}

bool StackArrayNodeSetFloatingPoint(struct StackArrayNode *theNode, double value) {
	bool returnValue = false;
	if (theNode->type == floatingpoint) {
		theNode->dValue = value;
		returnValue = true;
	}
	return returnValue;
}

We have three functions, each for setting a different value type for the node. We also have a function that prints the node depending on its type. This is necessary since the printf() function requires different conversion characters in the string literal.

bool StackArrayIsEmpty(const struct StackArray theStack) {
	if (theStack->top < 0) {
		return true;
	}
	else {
		return false;
	}
}

Using simple functions like this may impose a minuscule performance penalty as function stacks are added, but it adds immeasurably to the readability of programs. Let’s also add a function to clear the stack. We do this by simply setting the stack’s top value to -1.

void ClearStack(struct StackArray *theStack) {
	theStack->top = -1;
}

Next, let’s implement the pop function. The possibility of underflow should be addressed when implementing the pop functionality for a stack. In this context, we should make sure that the stack is not empty before popping off a value. This function will return a pointer to a dynamically allocated stack object that stores the copied data from the original item on the stack.

struct StackArrayNode *StackArrayPop(struct StackArray *theStack) {

	struct StackArrayNode *returnValue = NULL;

	if (StackArrayIsEmpty(theStack) == false) {
		//note that the decremement of the top index should occur after popping the value
		//because after push operation the index is set to the last element added
		returnValue = CopyNode(theStack->items[theStack->top--]);
	}

	return returnValue;
}

For implementing the push() operation, let’s first add a helper function to check if the stack is already full.

bool StackArrayIsFull(const struct StackArray *theStack) {
	if (theStack->top >= stack_array_size) {
		return true;
	}
	else {
		return false;
	}
}

The push() operation must increment the top of the stack by one. In our case, the stack will increment the top of the stack before actually adding the value, using the prefix increment operator. We do this since whenever the the stack is cleared or initialized, the top value is set to -1, indicating an empty stack. Since we cannot have an array with a negative index value, we must increment it first so that the value to be used as the index is at least 0.

Since we have three different value types, we will have three different push() functions – one for the int type, one for the double type, and one for the char type.

bool StackArrayPushInt(struct StackArray *theStack, int value) {
	//check if stack is full
	bool returnValue = StackArrayIsFull(theStack);
	//if stack isn't full, push value onto stack
	if (returnValue == false) {
		//guard against a negative value other than -1
		if (theStack->top < -1) { 			
                     theStack->top = -1;
		}
		//increment top index before adding value 
		++theStack->top;
		theStack->items[theStack->top].type = integer;
		returnValue = StackArrayNodeSetInt(&theStack->items[theStack->top], value);
	}
	return returnValue;
}

bool StackArrayPushDouble(struct StackArray *theStack, double value) {
	//check if stack is full
	bool returnValue = StackArrayIsFull(theStack);
	//if stack isn't full, push value onto stack
	if (returnValue == false) {
		//guard against a negative value other than -1
		if (theStack->top < -1) { 			
                    theStack->top = -1;
		}
		++theStack->top;
		theStack->items[theStack->top].type = floatingpoint;
		returnValue = StackArrayNodeSetFloatingPoint(&theStack->items[theStack->top], value);
	}
	return returnValue;
}

bool StackArrayPushChar(struct StackArray *theStack, char value) {
	//check if stack is full
	bool returnValue = StackArrayIsFull(theStack);
	//if stack isn't full, push value onto stack
	if (returnValue == false) {
		//guard against a negative value other than -1
		if (theStack->top < -1) { 			
                      theStack->top = -1;
		}
		//increment top index before adding value 
		++theStack->top;
		theStack->items[theStack->top].type = character;
		returnValue = StackArrayNodeSetChar(&theStack->items[theStack->top], value);
	}
	return returnValue;
}

Finally, we can bring it all together in the main() function, were we utilize everything we have written.

int main()
{
	struct StackArray theStack; 
	struct StackArrayNode *tempNode = NULL;

	ClearStack(&theStack);

	StackArrayPushInt(&theStack, 42);
	StackArrayPushChar(&theStack, 'X');
	StackArrayPushDouble(&theStack, 1.61803);
	StackArrayPushInt(&theStack, 8088);
	StackArrayPushChar(&theStack, 'H');
	StackArrayPushDouble(&theStack, 3.14159);
	StackArrayPushInt(&theStack, 1138);
	StackArrayPushChar(&theStack, 'T');
	StackArrayPushInt(&theStack, 6174);

	do {
		tempNode = StackArrayPop(&theStack);
		StackArrayNodePrint(tempNode);
		free(tempNode);
	} while (tempNode != NULL);

    return 0;
}

 

Linked List Structures in C

A linked list is a collection in which each element is a node that contains the location of the next node. Thus, each element in the collection contains two parts, the data and then the link to the next element. These links can be used to chain the nodes together; this chain is the collection, proper. We mark the collection with a pointer to the first element in the list; the name of the list is interchangeable with the name of the pointer to the start of the list.

As mentioned, the elements of a list are nodes. A node in a linked list is a structure that has at least two fields. One of the two fields is a data field; the other is a pointer that contains the address of the next node in the sequence. The nodes in a linked list are called self-referential structures. Each instance of the structure will contain a link to another instance of the same type.

typedef struct {
	int key;
	int iData;
	double dData;
} DATA;

typedef struct listNode {
	DATA data;
	struct listNode *link;
};

We will create two utility functions to make the process of creating nodes a little faster. The first function will create the data structure that holds the information. The second structure will actually create the node that contains the data structure as well as the node structure itself, which is the data plus a pointer to the next node. Since we will not know what the next node is, if there even will be one, we will set this link to NULL.

//create and return a pointer to the data structure
DATA *createData(int iData, double dData) {
	static int keyValue = 1;
	DATA * rData = (DATA *)malloc(sizeof(DATA));
	if (rData != NULL) {
		rData->key = keyValue++;
		rData->iData = iData;
		rData->dData = dData;
	}
	return rData;
}

//create and return a pointer to the node structure
listNode *createNode(int iData, double dData) {
	listNode *rNode = (listNode *)malloc(sizeof(listNode));
	if (rNode != NULL) {
		rNode->data = createData(iData, dData);
		//set the link to NULL
		rNode->link = NULL;
	}
	return rNode;
}

Finally, let’s create one more utility function to quickly show the data contents on the screen.

void displayNode(listNode *node) {
	DATA *temp = node->data;
	printf("Node #%d: %d %f\n", temp->key, temp->iData, temp->dData);
}

One of the features of a linked list is that there is no need for the nodes to be physically adjacent to each other, as they are dynamically allocated in memory. The beginning of the list is identified with a pointer to the start or head of the list. This pointer is known as the head pointer, because it points to the list’s head. A linked list must always have a head pointer.

We can use the head node as a jumping off point for listing all the members in the list. Our function for displaying all of the nodes will call the function for displaying a single node from within a loop that checks for the end of the list by looking to see if the node’s link is set to null.

void displayAllNodes(listNode *head) {
	listNode *temp = head;
	if (temp != NULL) {
		do {
			displayNode(temp);
			temp = temp->link;
		} while (temp->link != NULL);
	}
}

Next, let’s create a function to insert a node anywhere in the list. To do so, we need to determine an insertion point. We will determine this point using the node’s unique identifier number that was assigned at the time of its creation. Once we have found the right node, we will insert the new node after it. We find out what node the preceding node is pointing to, and we have the new node point to it. Then, we have the preceding node change so that it is pointing to the new node. Thus, the new node is inserted into the chain of nodes.

//finds the node by the indexed key number stored
//in the data section of the node
listNode * findNode(listNode *theHead, int index) {
	listNode *temp = theHead;
	listNode *returnNode = NULL;
	while (temp != NULL) {
		if (temp->data->key == index) {
			return temp;
		}
		temp = temp->link;
	}
	//returns NULL if index isn't found
	return temp;
}


listNode *insertNode(listNode *theNode, listNode *theHead, int index) {
	listNode *prevNode = findNode(theHead, index);
	listNode *temp = NULL;
	if (prevNode != NULL) {
		temp = prevNode->link;
		prevNode->link = theNode;
		theNode->link = temp;
	}
	return theNode;
}

Alright, so let’s bring it all together in one program.

#include <stdlib.h>

typedef struct {
	int key;
	int iData;
	double dData;
} DATA;

typedef struct listNode {
	DATA *data;
	struct listNode *link;
};

DATA *createData(int iData, double dData);
listNode *createNode(int iData, double dData);

listNode * findNode(listNode *theHead, int index);
listNode *insertNode(listNode *theNode, listNode *theHead, int index);

void displayNode(listNode *node); 
void displayAllNodes(listNode *head);

int main()
{
	listNode *listHead = createNode(42, 1.618);
	listNode *current = createNode(73, 192.168);
	
	listHead->link = current;

	current->link = createNode(1999, 25.806975);

	current = current->link;

	current->link = createNode(404, 1.5122);

	displayAllNodes(listHead);

	//insert a node
	current = createNode(8088, 802.11);
	insertNode(current, listHead, 3);

	current = createNode(47, 15.3465);
	insertNode(current, listHead, 1);

	printf("\n\nAfter inserting nodes\n");
	displayAllNodes(listHead);

    return 0;
}

//create and return a pointer to the data structure
DATA *createData(int iData, double dData) {
	static int keyValue = 1;
	DATA * rData = (DATA *)malloc(sizeof(DATA));
	if (rData != NULL) {
		rData->key = keyValue++;
		rData->iData = iData;
		rData->dData = dData;
	}
	return rData;
}

//create and return a pointer to the node structure
listNode *createNode(int iData, double dData) {
	listNode *rNode = (listNode *)malloc(sizeof(listNode));
	if (rNode != NULL) {
		rNode->data = createData(iData, dData);
		//set the link to NULL
		rNode->link = NULL;
	}
	return rNode;
}


void displayNode(listNode *node) {
	DATA *temp = node->data;
	printf("Node #%d: %d %f\n", temp->key, temp->iData, temp->dData);
}

void displayAllNodes(listNode *head) {
	listNode *temp = head;
	if (temp != NULL) {
		do {
			displayNode(temp);
			temp = temp->link;
		} while (temp != NULL);
	}
}

//finds the node by the indexed key number stored
//in the data section of the node
listNode * findNode(listNode *theHead, int index) {
	listNode *temp = theHead;
	listNode *returnNode = NULL;
	while (temp != NULL) {
		if (temp->data->key == index) {
			returnNode = temp;
                        break;
		}
		temp = temp->link;
	}
	//returns NULL if index isn't found
	return temp;
}


listNode *insertNode(listNode *theNode, listNode *theHead, int index) {
	listNode *prevNode = findNode(theHead, index);
	listNode *temp = NULL;
	if (prevNode != NULL) {
		temp = prevNode->link;
		prevNode->link = theNode;
		theNode->link = temp;
	}
	return theNode;
}

To delete a node, we must remove the node from the linked list by altering the pointers in the nodes, and then physically remove the node to be deleted from the heap.

To delete a node, we first must find its preceding node, then alter it to link to the node that comes after the node we wish to delete. The we use the free() function to delete the node from memory.

Let’s create a function that will find the node previous to the node we are looking for.

//returns the head of the list
listNode * deleteNode(listNode *theHead, int index) {
	listNode *temp = theHead;
	listNode *toDelete = NULL;
	//check to see if head is the value to be deleted
	if (temp->data->key == index) {
		toDelete = temp;
		theHead = temp->link;
	}
	else {
		//try to find the requested record to delete
		temp = findPrevNode(theHead, index);
		if (temp != NULL) {
			toDelete = temp->link;
			temp->link = toDelete->link;
		}
	}

	if (toDelete != NULL) {
		free(toDelete);
	}
	return theHead;

}

Finally, let’s test the delete node function in main().

int main()
{
	listNode *listHead = createNode(42, 1.618);
	listNode *current = createNode(73, 192.168);
	
	listHead->link = current;

	current->link = createNode(1999, 25.806975);

	current = current->link;

	current->link = createNode(404, 1.5122);

	displayAllNodes(listHead);

	//insert a node
	current = createNode(8088, 802.11);
	insertNode(current, listHead, 3);

	current = createNode(47, 15.3465);
	insertNode(current, listHead, 1);

	printf("\n\nAfter inserting nodes\n");
	displayAllNodes(listHead);

	listHead = deleteNode(listHead, 1);
	listHead = deleteNode(listHead, 3);

	printf("\n\nAfter deleting nodes\n");
	displayAllNodes(listHead);

    return 0;
}

Circular Linked Lists

The problem with a linear linked list is that given a point p to a node we cannot reach any of the nodes that precede it. Also, when we traverse the list, an external pointer to the list must be preserved in order to be able to reference the list again.

If we make a small change to the last node in the list we can have a circular list. For the last node, we make the pointer point to the first node rather than to a null pointer. From any point in a circular list it is possible to reach any other point.

#include <stdio.h>
#include <stdlib.h>

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

struct node *createCircularList(int data);
struct node *createNode(int data);
struct node *insertNodeAfter(struct node *p, node *newNode);
struct node *appendNode(struct node *pHeader, node *newNode);

void printOutList(char *message, struct node *location);
void printList(struct node*location);

int main()
{
	struct node *head = createCircularList(42);
	struct node *current = head;

	struct node *newNode = createNode(73);
	current = appendNode(head, newNode);

	newNode = createNode(404);
	current = insertNodeAfter(current, newNode);

	newNode = createNode(1138);
	current = insertNodeAfter(head, newNode);

	newNode = createNode(2600);
	current = appendNode(head, newNode);

	printOutList("First Time", head);

	newNode = createNode(3435);
	current = insertNodeAfter(head, newNode);

	newNode = createNode(7749);
	current = insertNodeAfter(current, newNode);

	printOutList("Second Time", head);

    return 0;
}

void printOutList(char *message, struct node *location) {
	printf("\n%s\n", message);
	printList(location);
	printf("\n");
}

void printList(struct node*location) {
	struct node *temp = location;
	do {
		printf("%d\t", temp->data);
		temp = temp->link;
	} while (temp != location);
}

struct node *createCircularList(int data = 0) {
	return createNode(data);
}

struct node *appendNode(struct node *pHeader, node *newNode) {
	struct node *tempNode = pHeader->link;
	while (tempNode->link != pHeader) {
		tempNode = tempNode->link;
	}
	return insertNodeAfter(tempNode, newNode);
}

struct node *insertNodeAfter(struct node *p, node *newNode) {
		//set new node linked to whatever old node is linked to
		newNode->link = p->link;
		//set old node linked to new node
		p->link = newNode;
		return newNode;
}

struct node *createNode(int dataParam) {
	struct node *retNode = (struct node *)malloc(sizeof(struct node));

	retNode->data = dataParam;
	retNode->link = retNode; 

	return retNode;
}

Let’s take a look at the Josephus problem using a circular list. The Josephus problem relates to a real event that occurred in the life of Flavius Josephus, a Jewish Roman historian. According to Josephus, he and his fellow soldiers decided to kill each other rather than surrender to the Roman army. The typical version involves the soldiers standing in a circle and clockwise around themselves, and killing every nth.

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define NAME_MAX 256
#define LIST_MAX 10

struct node {
	char name[NAME_MAX];
	node *link;
};

struct node* createNode(const char *name);
struct node* createCircularList(const char *names[], int numNames);
void printCircularList(struct node* head, int nums);
void deleteNodeAfter(struct node *theNode);
void printNode(struct node *theNode);

int main()
{
	//typically this is set to three
	//every third is killed
	int n = 3;
	
	const char *soldiers[LIST_MAX];
	struct node* listHead;
	struct node* position;

	soldiers[0] = "Aaron";
	soldiers[1] = "Benjamin";
	soldiers[2] = "Samuel";
	soldiers[3] = "Caleb";
	soldiers[4] = "Daniel";
	soldiers[5] = "Jacob";
	soldiers[6] = "Elliot";
	soldiers[7] = "Gabriel";
	soldiers[8] = "John";
	soldiers[9] = "Michael";

	//create the list
	listHead = createCircularList(soldiers, LIST_MAX);
	//test to make sure list works
	printCircularList(listHead, LIST_MAX + 4);

	//eliminate every third soldier
	position = listHead;
	do {
		for (int i = 0; i < n-1; i++) { 			
                    position = position->link;
		}
		printf("We will kill ");
		printNode(position->link);
		printf("\n");
		deleteNodeAfter(position);
	} while (position->link != position);

	printNode(position);
	printf(" is left...\n");
	return 0;
}

void deleteNodeAfter(struct node *theNode) {
	struct node*temp = theNode->link;
	theNode->link = temp->link;
	free(temp);
}

void printNode(struct node *theNode) {
	printf("%s", theNode->name);
}

struct node* createCircularList(const char *names[], int numNames) {
	int i = 0;
	node *head, *temp, *tail;
	head = createNode(names[i++]);
	tail = head;
	for (i; i < numNames; i++) { 		
                 temp = createNode(names[i]); 		
                //make the current tail link to the new node 		
                 tail->link = temp;
		//make the new node link back to the head
		temp->link = head;
		//make the new node the tail
		tail = temp;
	}

	return head;

}

void printCircularList(struct node* head, int nums) {
	struct node*temp = head;
	for (int i = 0; i < nums; i++) { 		
                printf("Name: \t%s\n", temp->name);
		temp = temp->link;
	}
}

struct node* createNode(const char *name) {
	node * newNode = (node*)malloc(sizeof(node));
	//copy name to new node
	if (strlen(name) < NAME_MAX) { 		
           strcpy_s(newNode->name, NAME_MAX, name);
	}
	//initialize link to point to itself
	newNode->link = newNode;
	return newNode;
}

Function Pointers

A function is the address of the entry point to a group of instructions bundled together into the function construct. A function pointer stores the entry-point address of a function. If we dereference a function pointer, it is the same as calling the function.

When declaring a function pointer we need to separate the pointer declaration from the type of the return value. To separate the two we wrap the pointer declaration in a set of parentheses.

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

long addNums(int a, int b);
long subNums(int a, int b);
long multNums(int a, int b);

char *reverseStr(char *str);

int main()
{
    char *strOrig = "Greetings, Professor Falken";
    char *str = NULL;

    int i = 0;
    long answer = 0;
    int iVarOne = 42;
    int iVarTwo = 73;

    long (*mathFunction)(int a, int b);

    long (*mathArray[3])(int a, int b);

    char *(*stringFunction)(char *str);

    stringFunction = reverseStr;

    printf("Address of string reverse function is %p\n", reverseStr);
    str = (*stringFunction)(strOrig);

    printf("%s backwards is %s\n", strOrig, str);

    mathArray[0] = addNums;
    mathArray[1] = subNums;
    mathArray[2] = multNums;

    for(i = 0; i < 3; i++){
        answer = (*mathArray[i])(iVarOne, iVarTwo);
        printf("%ld\n", answer);
    }

    return 0;
}

long addNums(int a, int b){
    return a + b;
}

long subNums(int a, int b){
    return a - b;
}

long multNums(int a, int b){
    return a * b;
}

char *reverseStr(char *str){
    int i, j, strLength;

    char *returnString = NULL;

    if(str != NULL){
        strLength = strlen(str);
        returnString = (char *)malloc(sizeof(char) * (strLength  + 1));
        if(returnString != NULL){
            for(i = 0, j = strLength - 1; i < strLength; i++, j--){
                returnString[i] = str[j];
            }
            returnString[strLength] = '\0';
        }
    }
    return returnString;
}

The function names act as address tags in the same way that array names act as address tags.

Pointers and Dynamic Memory

The malloc() function in <stdlib.h> allocates the requested number of bytes from the heap for the application to use.  malloc() returns a void pointer that should be cast to the data type of the pointer. Casting the memory is important because in order for pointer arithmetic to work, the compiler must know the size of the object to which the pointer is pointing. We also use sizeof() to ensure the portability of the code. sizeof() returns the size in bytes of the variable type we wish to allocate memory for.

The free() function returns a previously allocated block of memory to the heap.

#include <stdlib.h>
#include <string.h>

char *strCpy(const char * str) {
	char *rStr = NULL;
	
	if (str == NULL) {
		return NULL;
	}

	int strLength = strlen(str);

	//add one for the terminating character
	rStr = (char *)malloc(sizeof(char) * strLength + 1);

	if (rStr == NULL) {
		printf("Error allocating memory.\n");
		return NULL;
	}

	//add terminating character for string
	*(rStr + strLength) = '\0';

	while (strLength-- > 0) {
		*(rStr + strLength) = *(str + strLength);
	}

	return rStr;
}

//substring of a larger substring copied onto head and returned
char *substr(const char *theString, int start, int length) {
	char *rStr;
	int count = 0;
	int strLen = strlen(theString);

	//check for bad start position
	if (start < 1) {
		printf("String positions start from 1.\n");
		return NULL;
	}

	if (length < 1) {
		printf("Length must be at least one character long.\n");
	}

	rStr = (char *)malloc(sizeof(char) * (length + 1));

	if (rStr == NULL) {
		printf("Could not allocate the memory.\n");
		return NULL;
	}

	//c strings start at 0
	//so subtract one
	start--;
	
	*(rStr + length) = '\0';

	while (count < length) {
		*(rStr + count) = *(theString + start + count);
		count++;
	}

	return rStr;

}

int main(void) {

	char *newString = strCpy("Nilbog is Goblin Spelled Backwards!");

	printf("%s\n", newString);

	char *newSubStr = substr(newString, 1, 6);

	printf("%s\n", newSubStr);

	//free up the memory when done
	free(newString);
	newString = NULL;

	return 0;
}

It is considered good practice to initialize pointers to NULL and after calling free(). It is also important to verify that the value returned from malloc() is a valid pointer.

const int buffer_max = 256;

double getInput(char *inputBuffer, int bufferSize) {

	int i = 0;

	fgets(inputBuffer, bufferSize, stdin);

	//check for alpha characters
	for (; *(inputBuffer + i) != '\0'; i++) {
		if (iswalpha(*(inputBuffer + i))) {
			return -1;
		}
	}

	return atof(inputBuffer);

}

double * resizeDArray(double **array, int newMax) {
	return (double *)realloc(*array, sizeof(double) * newMax);
}

void printScores(const double *array, int count) {
	for (int i = 0; i < count; i++) {
		printf("%f\t", *(array + i));
		if (count % 5 == 0) {
			printf("\n");
		}
	}
}

double getHighScore(const double *array, int count) {
	double highScore = 0;
	for (int i = 0; i < count; i++) { 		if (*(array + i) > highScore) {
			highScore = *(array + i);
		}
	}
	return highScore;
}

double getLowScore(const double*array, int count) {
	double lowScore = 125;
	for (int i = 0; i < count; i++) {
		if (*(array + y) < lowScore) { 			
                    lowScore = *(array + i); 		
                   } 	
        }   
	
    return lowScore; 

} 

int main() { 	
   char inputBuffer[buffer_max]; 	
   int count = 0; 	
   int max = 5; 	
   double *ptrScores = NULL; 	
   double entry = 0; 	
   double high = 0; 	
   double low = 100; ] 	
   int i = 0, j = 0; 	
   //allocate space for 10 scores 	
   ptrScores = (double *)malloc(sizeof(double) * max); 	
   if (ptrScores == NULL) { 		
       printf("Could not allocate memory.\n"); 		
       exit(0); 	
   } 	
   printf("Please enter the test scores. Once the scores are entered, the program will sort the scores "); 	printf("and calculate the high and low scores.\n\n"); 	while (entry >= 0) {
		
   printf("Enter a score greater than or equal to 0, or a negative number to stop: ");
		
   entry = getInput(inputBuffer, buffer_max);
		
          if (entry >= 0) {
			if (count == (max - 1)) {
				//reallocate memory if there is not enough 
				//increase max size
				max += 5;
				ptrScores = resizeDArray(&ptrScores, max);
			}
			*(ptrScores + count) = entry;
			count++;
		}
	}

	printf("Scores entered: \n");
	printScores(ptrScores, count);

	high = getHighScore(ptrScores, count);
	low = getLowScore(ptrScores, count);

	printf("The high score is %f\n", high);
	printf("The low score is %f\n", low);

	free(ptrScores);

	return 0;
}

The realloc() function takes a previously malloc-ed, realloc-ed, etc. pointer that we want to modify the space it points to in memory. The realloc() function will increase or decrease the size of that space. If realloc() returns NULL, then it failed to allocate the space for some reason; thankfully, the previously allocated space is still there.

 

 

Linked-Lists in C

Linked-lists utilize nodes of data. A node consists of two parts: a data part and a link part. The data part contains the data actually stored by the node. The link part consists of one or more pointers to other nodes. These pointers contain the addresses in memory of other nodes.

A linked list consists of a node that is the head or first node, that links to another node, that in turn links to another node, until finally the last node has a link set to NULL.

typedef struct node {
	char data; 
	struct node *link;
} NODE;

Nodes are created dynamically as needed during run time. In C, we do this using the malloc() function contained in the <stdlib.h> library. Linked-list nodes are created by dynamically allocating chunks of memory large enough to store the node. The nodes must be set to either point to another node, or else by NULL if it is at the end of the list.

void displayList(NODE *ptr);

int main()
{
	NODE *nOne, *nTwo, *nThree, *nFour;

	nOne = (NODE *)malloc(sizeof(NODE));
	nTwo = (NODE *)malloc(sizeof(NODE));
	nThree = (NODE *)malloc(sizeof(NODE));
	nFour = (NODE *)malloc(sizeof(NODE));

	nOne->data = 't';
	nOne->link = nTwo;

	nTwo->data = 'r';
	nTwo->link = nThree;

	nThree->data = 'e';
	nThree->link = nFour;

	nFour->data = 'e';
	nFour->link = NULL;


	displayList(nOne);

    return 0;
}

void displayList(NODE *ptr) {
	while (ptr != NULL) {
		printf("%c\t", ptr->data);
		ptr = ptr->link;
	}
	printf("\n\n");
}

As linked-lists are created dynamically, just adding a node isn’t just adding a node. Whenever we add a node, we have to consider several possible cases according to where in the list the node is being added and whether or not the list is empty.

The addNode() function uses a while loop to find the last node in the list before  allocating a new node and attaching it to the last node.

Adding a new node to the beginning of the list is simpler.

typedef struct node {
	int data;
	struct node *link;
} NODE;

void showList(NODE *ptr);
void addNode(NODE **ptr, int data);
void prependNode(NODE **ptr, int data);

int main() {
	
	const int buffer_size = 64;

	char buffer[buffer_size];
	NODE *n = NULL;
	int i = 0;
	int data;
	
	while (i++ < 5) { 		printf("Please enter a number: "); 		fgets(buffer, buffer_size, stdin); 		addNode(&n, atoi(buffer)); 	} 	 	printf("The link list is: \n"); 	showList(n); 	 	return 0; } void showList(NODE *ptr) { 	while (ptr != NULL) { 		printf("%d\t", ptr->data);
		ptr = ptr->link;
	}
}

void prependNode(NODE **ptr, int data) {
	NODE *nOne = (NODE *)malloc(sizeof(NODE));
	if (nOne != NULL) {
		nOne->data = data;
		nOne->link = *ptr;
		*ptr = nOne;
	}
}

void addNode(NODE **ptr, int data) {
	NODE *pOne, *pTwo;

	pOne = *ptr;
	if (pOne == NULL) {
		//empty list
		pOne = (NODE *)malloc(sizeof(NODE));
		if (pOne != NULL) {
			pOne->data = data;
			pOne->link = NULL;
			*ptr = pOne;
		}
	}
	else {
		while (pOne->link != NULL) {
			pOne = pOne->link;
		}
		pTwo = (NODE *)malloc(sizeof(NODE));
		if (pTwo != NULL) {
			pTwo->data = data;
			pTwo->link = NULL;
			pOne->link = pTwo;
		}
	}
}

Sometimes we may need to delete a node from a linked list. We can delete a node from the beginning of the linked list, from the end of the list, or from somewhere in the middle. We use the free() function to return the memory back to the heap.

void deleteFromHead(NODE **ptr) {
	NODE *head;
	head = *ptr;
	if (head != NULL) {
		head = head->link;
		free(*ptr);
	}
	*ptr = head;
}

To delete the node from the tail of a linked list we search to find the last node in the list.

typedef struct node {
	double data;
	struct node *link;
} NODE;

void viewList(NODE *ptr);
void deleteTail(NODE **ptr);

int main() {
	
	NODE *nOne, *nTwo, *nThree, *nFour;

	nOne = (NODE *)malloc(sizeof(NODE));
	nTwo = (NODE *)malloc(sizeof(NODE));
	nThree = (NODE *)malloc(sizeof(NODE));
	nFour = (NODE *)malloc(sizeof(NODE));

	nOne->data = 2.718;
	nOne->link = nTwo;

	nTwo->data = 1.491625;
	nTwo->link = nThree;

	nThree->data = 169.254;
	nThree->link = nFour;

	nFour->data = 0.57721;
	nFour->link = NULL;

	viewList(nOne);

	deleteTail(&nOne);

	viewList(nOne);

	return 0;
}

void viewList(NODE *ptr) {
	printf("\n");
	while (ptr != NULL) {
		printf("%f\t", ptr->data);
		ptr = ptr->link;
	}
	printf("\n");
}

void deleteTail(NODE **ptr) {
	NODE *nOne, *nTwo;

	nOne = *ptr;
	if (nOne != NULL)
	{
		if (nOne->link == NULL) {
			free(*ptr);
			*ptr = NULL;
		}
		else {
			nTwo = nOne;
			while (nOne->link != NULL) {
				nTwo = nOne;
				nOne = nOne->link;
			}
			nTwo->link = NULL;
			free(nOne);
		}
	}
}

 

Pointers to Pointers, Structures, Pointers to Structures

Pointers to pointers can be used to effectively create and manipulate dynamic two dimensional arrays. Arrays of pointers are extremely useful tools for rapid manipulation of large amounts of data.

#include <stdlib.h>
#include <stdio.h>
#include <string.h>
#include <ctype.h>

#define SMALL_BUFFER 256

int readInt(char *buffer, int bounds);
int readPositiveInt(char *buffer, int bounds);
char *readString(char *buffer, int bounds);
void printResults(char **students, int **tests, int numStudents, int numTests);

int main()
{
	int **grades = NULL;
	char **students = NULL;

	int numStudents = 0;
	int numTests = 0;

	int i = 0;
	int j = 0;

	char buffer[SMALL_BUFFER];

	printf("Please enter the number of students ");
	numStudents = readPositiveInt(buffer, SMALL_BUFFER);

	printf("There are %d students.\n", numStudents);


	printf("Please enter the number of tests ");
	numTests = readPositiveInt(buffer, SMALL_BUFFER);

	printf("There were %d tests.\n", numTests);

	//malloc the space for the student names
	students = (char **)malloc(sizeof(char *) * numStudents);

	//malloc the space for the student grades
	grades = (int **)malloc(sizeof(int *) * numTests);

	for (i = 0; i < numStudents; i++) {
		//flush the output buffer of stdin
		fflush(stdin);
		printf("Please enter student #%d's name ", i+1);
		students[i] = readString(buffer, SMALL_BUFFER);

		printf("Please enter the test scores for student %s \n", students[i]);
		//malloc space for the int array
		grades[i] = (int *)malloc(sizeof(int) * numTests);
		for (j = 0; j < numTests; j++) {
			printf("Enter %s's grade for the %d test", students[i], j + 1);
			grades[i][j] = readPositiveInt(buffer, SMALL_BUFFER);
		}
	}

	printResults(students, grades, numStudents, numTests);

    return 0;
}

void printResults(char **students, int **tests, int numStudents, int numTests) {
	for (int i = 0; i < numTests; i++) {
		printf("\nResults for Test %d: \n", i + 1);
		for (int j = 0; j < numStudents; j++) {
			//*(tests + j) gets the column
			printf("%s scored %d\n", *(students + j), *(*(tests + j) + i));
		}
	}
}

int readInt(char *buffer, int bounds) {
	fgets(buffer, bounds, stdin);
	return atoi(buffer);
}

//ensure a positive number is given
int readPositiveInt(char *buffer, int bounds) {
	int rValue;
	while ((rValue = readInt(buffer, bounds)) < 1) { 		
                 printf("Value must be a positive number. Please enter again: "); 
	} 	
return rValue; 
} 

//read a string from standard input 
char *readString(char *buffer, int bounds) { 	
            fflush(stdin); 	
            fgets(buffer, bounds, stdin); 	
            int strLength = strlen(buffer) - 1; 	
            //allocate a string of the exact length needed 	
           char *rValue = (char *)malloc(sizeof(char) * strLength); 	
            //copy the string over backwards from the buffer 	
            *(rValue + strLength) = '\0'; 	
          while (--strLength >= 0) {
		*(rValue + strLength) = *(buffer + strLength);
	  }
	return rValue;
}

Interesting enough, the argv portion of the command line arguments is a pointer pointer as well.

int main(int argc, char *argv[])
{
	
	int i, j;

	char **myArgs = argv;

	//print out arguments as strings
	for (i = 0; i < argc; i++) {
		printf("argument %d = %s\n", i + 1, *(myArgs + i));
	}


    return 0;
}

Structures are aggregate data types, which means that they can store different data types in the same unit. These units, or records, can hold multiple different data types grouped together and accessed via the structure’s name. We can access these different data elements using the dot operator.

const int char_buffer_size = 128;

struct employee {
	int id;
	char name[char_buffer_size];
	int age;
};

void changeName(struct employee *emp);

int main(int argc, char *argv[])
{
	
	struct employee nd = { 411, "Nick Danger", 32 };

	struct employee *empPtr;

	printf("The starting memory address of nd is %p\n", &nd);
	empPtr = &nd;

	printf("empPtr holds %p\n", empPtr);

	printf("His name is %s, third eye.\n", nd.name);
	printf("His name is %s, third eye.\n", empPtr->name);

	changeName(&nd);

	printf("His name is now %s\n", nd.name);
	printf("His name is now %s\n", empPtr->name);

    return 0;
}

void changeName(struct employee *emp) {
	strcpy_s(emp->name, char_buffer_size, "Ivo Shandor");
}

 

Searching and Sorting Arrays

An array is a fixed-size, homogeneous data structure with random-access, where all elements can be selected at random and are equally accessible. An element of the array can be selected by giving its subscript, which is an integer indicating the position of the element in the array.

Arrays are represented in memory using sequential mapping.

A two dimensional array can be viewed as a one-dimensional array who elements are in turn one-dimensional arrays. We can view a two dimensional array as a single column of rows; this is called row-major representation.

An array can be viewed as a matrix. To add two matrices, we simply add the matching rows and columns to each other.

int * getArray(int row, int column);
void printArray(int *array, int row, int column);
void populateArray(int *array, int row, int column, char *name);
void addArray(int *arrOne, int *arrTwo, int row, int column);

int main()
{
    const int rSize = 3;
    const int cSize = 3;

    int *arrOne = getArray(rSize, cSize);
    int *arrTwo = getArray(rSize, cSize);

    populateArray(arrOne, rSize, cSize, "first");
    populateArray(arrTwo, rSize, cSize, "second");

    printArray(arrOne, rSize, cSize);
    printArray(arrTwo, rSize, cSize);

    addArray(arrOne, arrTwo, rSize, cSize);


    return 0;
}

void addArray(int *arrOne, int *arrTwo, int row, int column){
    int i = 0;
    int j = 0;
    int a, b;
    while(i < row){
        while(j < column){
            a = *(arrOne + (i*column) + j);
            b = *(arrTwo + (i*column) + j);
            printf("\n%d + %d = ", a, b);
            *(arrOne + (i*column) + j) += b;
            printf("%d\n", *(arrOne + (i * column) + j));
            j++;
        }
        j = 0;
        i++;
    }

    printArray(arrOne, row, column);

}

void populateArray(int *array, int row, int column, char *name){
    int i = 0;
    int j = 0;
    int val;
    printf("Please populate the %s array:\n", name);
    while(i < row){
        while(j < column){
            printf("Value for row %d, column %d\t", i, j);
            scanf("%d", &val);
            *(array + (i * column)+j) = val;
            j++;
        }
        j = 0;
        i++;
    }
}

void printArray(int *array, int row, int column){
    int i = 0;
    int j = 0;
    printf("\n");
    while(i < row){
        while(j < column){
            //use pointer arithmetic to get the array elements
            printf("%d\t", *(array + (i*column)+j));
            j++;
        }
        j = 0;
        i++;
        printf("\n");
    }
}

int * getArray(int row, int column){
    int *rArray = (int *)malloc(row * column * sizeof(int));
    return rArray;
}

The transpose of a matrix is a new matrix whose rows are the columns of the original, and whose columns are the rows of the original .

#define ROW_LENGTH 3
#define COL_LENGTH 3

void readArray(int *array, int rowLength, int colLength);
void displayArray(int *array, int rowLength, int colLength);
void transpose(int *matrix, int rowLength, int colLength);

int main()
{
    int iMatrix[ROW_LENGTH][COL_LENGTH];

    readArray(iMatrix, ROW_LENGTH, COL_LENGTH);
    displayArray(iMatrix, ROW_LENGTH, COL_LENGTH);
    transpose(iMatrix, ROW_LENGTH, COL_LENGTH);
    displayArray(iMatrix, ROW_LENGTH, COL_LENGTH);

    return 0;
}

void readArray(int *array, int rowLength, int colLength){
    int i, j;
    for(i = 0; i < rowLength; i++){
        for(j = 0; j < colLength; j++){
            printf("Enter value for element [%d, %d]: ", i, j);
            scanf("%d", (array + (i * colLength) + j));
        }
    }
}

void displayArray(int *array, int rowLength, int colLength){
    int i, j;
    for(i = 0; i < rowLength; i++){
        for(j = 0; j < colLength; j++){
            printf("%5d\t", *(array + (i * colLength) + j));
        }
        printf("\n");
    }
}

void transpose(int *matrix, int rowLength, int colLength){
    int i, j, temp;
    for(i = 0; i < rowLength; i++){
            for(j = i+1; j < colLength; j++){
                temp =  *(matrix + (i * colLength) + j);
                 *(matrix + (i * colLength) + j) = *(matrix + (j * colLength) + i);
                *(matrix + (j * colLength) + i) = temp;
            }
    }
}

A bubble sort is a simple sort in which we arrange the elements of the set by forming pairs of adjacent elements, where the pair is of the ith and (i+1)th element. If the order is ascending, we interchange the elements of the pair if the first element of the pair is greater than the second element.

void swap(int *x, int *y);
void bSort(int *list, int bounds);

int main()
{

    const int bounds = 10;

    int iArray[] = {1701, 73, 6174, 2048, 52, 203, 42, 3389, 1138, 1999};
    printArray(iArray, bounds);
    bSort(iArray, bounds);
     printArray(iArray, bounds);
    return 0;
}

void printArray(int *list, int bounds){
    int i = 0;
    for(; i < bounds; i++){
        printf("%d\t", *(list+i));
    }
    printf("\n");
}


void bSort(int *list, int bounds){
    int inner, outer;
    //go backwards through the array;
    for(inner = bounds - 1; inner > 0; inner--){
            for(outer = 0; outer < inner; outer++){                 
            if(*(list + outer) > *(list + outer + 1)){
                    swap((list + outer), (list + outer + 1));
                }
            }
    }

}


void swap(int *x, int *y){
    printf("swaping %d and %d\n", *x, *y);
    int tmp = *x;
    *x = *y;
    *y = tmp;
}