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

 

Advertisements

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