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

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

 

Memory Management and Strings in C

C has an extremely flexible – some would say, dangerous – ability to allocate, use, and deallocate memory. Memory can be allocated statically, dynamically, or automatically in C. Static memory allocation occurs when variables are declared with the static keyword, and have scope set to the file; static memory also occurs when variables are declared outside the scope of any function, these variables may be used globally via the extern keyword. Dynamic memory allocation is the result of calling malloc() or another related function to get memory from the heap, and persists until free() is called. Automatic memory allocation occurs when a variable is declared within a function.

One of that nice things about static variables is that we can declare them within a function, and yet they persist beyond the lifetime of a function.

int useStaticVar(int iNum = 1);

int main()
{

	int i = 1;
	int iSum = 0;
	while (i++ < 10) {
		useStaticVar(i);
	}
	
	printf("Value is %d\n", useStaticVar());

    return 0;
}


int useStaticVar(int iNum) {
	static int iProduct = 1;
	iProduct *= iNum;
	return iProduct;
}

Remember, automatic variables are allocated on the stack. They are allocated and deallocated for us when the program enters and leaves their scopes.

Both automatic and static variables share the same problem – their size must be declared, and therefore known, at compile time. Dynamic memory allocation allows memory to be allocated by the program while it is running as needed. The malloc() function enables us to allocate variable amounts of memory that can be utilized via a pointer that is returned by the function.

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

char * allocateString(int iLength);

int main()
{
	char * ourString = allocateString(256);
	strcpy_s(ourString, 256, "With sufficient thrust, pigs fly just fine.");

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

    return 0;
}

char * allocateString(int iLength) {
	char *str = NULL;
	if (iLength > 0) {
		str = (char*)malloc(iLength);
	}
	return str;
}

Note that to modify a pointer that is a parameter in a function, we must pass it as a pointer to a pointer, using **.

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

#define STRING_LENGTH 256

void appendString(char ** szTarget, int iTotalLength, char *szSource);

int main()
{
	char *szString = (char *)malloc(STRING_LENGTH);
	strcpy_s(szString, STRING_LENGTH, "A strange game.The only winning move is not to play.");
	appendString(&szString, STRING_LENGTH, " All your base are belong to us.");

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

    return 0;
}

void appendString(char ** szTarget, int iTotalLength, char *szSource) {
	int i = 0;
	int j = 0;
	//with single indirection, the pointer arithmetic would be
	//*(szTarget+i)
	//with double indirection, we have to deallocate once
	//just to get to where we would be with single indirection
	while (*(*szTarget+i) != '\0') { i++; }

	iTotalLength--;
	while ((i < iTotalLength) && (*(szSource + j) != '\0')) {
		*(*szTarget + i) = *(szSource + j);
		i++;
		j++;
	}

	*(*szTarget + i) = '\0';
}

Converting an integer to a string is fun, but there are three things to bear in mind. First, the characters that make up strings themselves have an integer value, which is set by the ASCII standard. To get the ASCII equivalent of an integer between 0-9, we need to add the integer value of the character 0 to the integer. Second, while strings in English are read left to right, numbers are read right to left. This means that the easiest thing to do for us will be to write the string equivalent of the integer backwards.

Finally, we should keep in mind that the value of any digit in a number is the digit itself multiplied by 10 for each place it is left of the starting position.  So, for example, the ‘9’ in 90210 itself is 9 * 10 * 10 * 10 * 10, or 90,000. The ‘2’, therefore, is 2 * 10 * 10, or 200.

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

#define STRING_LENGTH 256

char * intToString(int iNum);

int main()
{
	char *s = intToString(8675309);

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

    return 0;
}

char * intToString(int iNum) {

	int iNumCopy = iNum;
	int iLength = 0;
	
	//numbers are read right from left, not left to right 
	//as words are
	do {
		iLength++;
		printf("iNumCopy = %d\n", iNumCopy);
		iNumCopy /= 10;
	} while (iNumCopy != 0);

	printf("Number has %d places\n", iLength);

	//one extra char needed 
	char *rString = (char *)malloc(iLength + 1);

	//terminate string
	*(rString + iLength) = '\0';

	while (--iLength >= 0) {
		printf("%d\n", iNum % 10);
		*(rString + iLength) = (iNum % 10) + '0';
		iNum /= 10;
	}

	return rString;

}

Please note that the example above does not, for reasons of simplicity, handle negative numbers. However, it would be easy enough to add that capability.

Incidentally, reversing a number is even easier. We just have to remember that multiplication and division are the opposites of each other.

#include <stdlib.h>

int reverseNumber(int iNum);

int main()
{
	int i = 73;
	int j = reverseNumber(i);

	int x = 501;
	int y = reverseNumber(x);

	printf("%d \t %d\n", i, j);
	printf("%d \t %d\n", x, y);

    return 0;
}

int reverseNumber(int iNum) {
	int iReturnNum = 0;
	while (iNum != 0) {
		//shift iReturnNum left one position
		//except when at the first position
		//as 0 * 10 = 0
		iReturnNum *= 10;
		iReturnNum += iNum % 10;
		//dividing by 10
		//removes the rightmost digit 
		//from an integer
		iNum /= 10;
	}

	return iReturnNum;
}

Pointers and Dynamic Linked Lists in C

One of the more awe-inspiring features of C is its use of pointers.

Pointers enable us to create complex and dynamic data structures like linked lists and binary trees. A dynamic data structure is one that can grow or shrink as needed.

Structures can contain pointers, even a pointer to another instance of the same structure.

The malloc() function allocates storage for a variable and then returns a pointer to that storage. Data objects created by malloc() can only be referenced, never named; this means we have to deal with malloc-ed memory via pointers.

#include "stdafx.h"
#include <stdlib.h>

struct dataStruct {
 int iData;
 double dData;
 struct dataStruct *structPtrNext;
};

//use the typedef to create an alias for
//a pointer to the dataStruct structure
typedef struct dataStruct* node;

int main()
{
 node currentNode;
 node startNode = (node)malloc(sizeof(dataStruct));

 startNode->iData = 73;
 startNode->dData = 3.14;
 
 startNode->structPtrNext = (node)malloc(sizeof(dataStruct));
 currentNode = startNode->structPtrNext;

 currentNode->iData = 42;
 currentNode->dData = 19.99;

 currentNode->structPtrNext = (node)malloc(sizeof(dataStruct));

 currentNode = currentNode->structPtrNext;
 currentNode->iData = 404;
 currentNode->dData = .5772;
 currentNode->structPtrNext = NULL;


 currentNode = startNode;
 while (currentNode != NULL) {
  printf("%d \t %f\n", currentNode->iData, currentNode->dData);
  currentNode = currentNode->structPtrNext;
 }


 return 0;
}

The malloc() function takes a single argument, the number of bytes to allocate. If malloc() cannot allocate the requested memory, it returns a null pointer. We can use malloc() to allocate space on an as-needed business. We use the sizeof() operator to determine the size of the structure in bytes; this is easier and less error-prone than using a hard number to allocate the bytes.

The malloc() function gets memory from the heap. To free that memory after we are finished utilizing it, we should call the clearly named free() function. The free() function takes a single argument, the pointer to the block of memory to be freed.

struct structTypeA{
 char chA;
 int iB;
};

struct structTypeB {
 double dA;
 double dB;
};

int main()
{
 printf("Sizeof structTypeA %d\n", sizeof(structTypeA));
 printf("Sizeof structTypeB %d\n", sizeof(structTypeB));

 struct structTypeA *aPtr = NULL;
 struct structTypeB *bPtr = NULL;

 //lets malloc the memory
 aPtr = (structTypeA *)malloc(sizeof(structTypeA));
 if (aPtr != NULL) {
  printf("Memory for the type A structure allocated!\n");
 }

 bPtr = (structTypeB *)malloc(sizeof(structTypeB));

 if (bPtr != NULL) {
  printf("Memory for the type B structure allocated!\n");
 }

 //lets free the memory, return it to the heap
 free(aPtr);
 aPtr = NULL;
 free(bPtr);
 bPtr = NULL;

 return 0;
}

While we do not have to set the pointer to NULL after calling free(), it is generally considered a best practice, as doing so prevents us from trying to use free memory.

Note that the structure pointer operator, ->, provides a shorthand way to access the data field of a structure being pointed to by a pointer.

A linked list is a chain of nodes in which each node points to the next one in the chain. A linked-list data structure is like an array we can grow as needed.

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

const int string_length = 256;

struct linkedList {
 char string[string_length];
 struct linkedList *nextPtr;
};

typedef struct linkedList *list;


int main()
{
 list firstNode = (list)malloc(sizeof(linkedList));
 list nextNode = NULL;

 //set firstNode to point to NULL
 firstNode->nextPtr = NULL;
 strcpy_s(firstNode->string, string_length, "Do you have stairs in your house?");
 

 //create new node for the list
 nextNode = (list)malloc(sizeof(linkedList));

 strcpy_s(nextNode->string, string_length, "Nice boat!");
 //have the new node point to the first node
 nextNode->nextPtr = firstNode;
 //set the first or "top" node to be the new node
 firstNode = nextNode;
 //assign the new node new memory
 nextNode = (list)malloc(sizeof(linkedList));

 strcpy_s(nextNode->string, string_length, "Shaka, when the walls fell.");
 //set the new node to point to the top node
 nextNode->nextPtr = firstNode;
 //set the first node to the node
 firstNode = nextNode;

 //let's do it one more time 

 nextNode = (list)malloc(sizeof(linkedList));

 strcpy_s(nextNode->string, string_length, "For relaxing times, make it Suntory time.");
 nextNode->nextPtr = firstNode;

 firstNode = nextNode;

 while (firstNode != NULL) {
  printf("%s\n", firstNode->string);
  firstNode = firstNode->nextPtr;
 }

 return 0;
}

Of course, it’s easier if we offload some of this into some functions. One of the blessings (some say it is a curse) of dynamically allocated memory is that we are free from worrying about scope.

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


const int string_length = 256;

struct linkNode {
 //unicode strings? why not!
 wchar_t string[string_length];
 struct linkNode *nxtPtr;
};

struct linkNode * initializeList(void) {
 struct linkNode *firstNode = (struct linkNode *)malloc(sizeof(linkNode));
 firstNode->nxtPtr = NULL;
 return firstNode;
}

//need to have a pointer to the pointer
//now we see the point of typedefs!
//we have to have a pointer to a pointer
//in order for the changes to persist
void addNode(struct linkNode **lPtrFirst) {
 struct linkNode *newNode = (struct linkNode *)malloc(sizeof(linkNode));
 if (newNode == NULL) {
 printf("Error allocating memory.\n");
 exit(EXIT_FAILURE);
 }
 newNode->nxtPtr = *lPtrFirst;
 *lPtrFirst = newNode;
}

int main()
{
 wchar_t answer[2];

 struct linkNode *lPtrFirst = initializeList();

 while (true) {
 printf("Please enter the text to store:\t");
 fgetws(lPtrFirst->string, string_length, stdin);

 printf("Would you like to enter another string? (y/n) \t");
 wscanf_s(L"%s", answer, 2);
 //clear buffer
 while (getwchar() != L'\n') {}
   if (answer[0] == L'n' || answer[0] == L'N') {
   break;
 }
  addNode(&lPtrFirst);
 }

 while (lPtrFirst != NULL) {
   wprintf(L"%s", lPtrFirst->string);
   lPtrFirst = lPtrFirst->nxtPtr;
 }

 return 0;
}

Binary Trees in C

A binary tree is a data structure that visually looks cool, but more importantly allows for rapid searching by the way it is structured. The hierarchical structure is analogous to the family tree model, with parents and children the branch off from parents, and one single common ancestor, the root. Ideally, if we organize the tree well, the search time for any one element or “node” in the tree should take a time of log2n.

However, in order to get this to work, the tree must be balanced with the height of the left subtrees equaling the height of the right subtrees.

A binary tree can be set up as a multiply linked list in which each node consists of a link pointing to its left child, another link pointing to its right child, and its node data.

In our free-and-easy implementation, a node with NULL pointer values for the left child and right child is a leaf node.

To dynamically create and use a node, we will first allocate memory space via the malloc() system call. Therefore, the entire binary tree can dynamically grow or shrink during the execution of the program.

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

typedef struct structNode {
 struct structNode *lChildPtr;
 struct structNode *rChildPtr;
 int iNodeData;
} sNode;

//create a new node with an int i
//data value
sNode * createNode(int i) {

 sNode *nPtr = (sNode*)malloc(sizeof(sNode));
 if (nPtr != NULL) {
 nPtr->lChildPtr = NULL;
 nPtr->rChildPtr = NULL;
 nPtr->iNodeData = i;
 return nPtr;
 }
 else {
 printf("Failed to allocated another node.\n");
 exit(EXIT_FAILURE);
 }
}

//release the memory space after it is used
void disposeNode(sNode * nPtr) {
 free(nPtr);
 nPtr = NULL;
}

int populateSubTree(int num, sNode *theNode) {
 theNode->lChildPtr = createNode(++num);
 theNode->rChildPtr = createNode(++num);
 return num;
}

//visit each node of the tree in order
//starts printing from the leftmost leaf node
//ends at the rightmost leaf node
void traverseInOrder(sNode *root) {
 if (root != NULL) {
 traverseInOrder(root->lChildPtr);
 //print root
 printf("%d\n", root->iNodeData);
 traverseInOrder(root->rChildPtr);
 }
}

//visit each node in tree
//starting from leftmost leaf node
//ending at the root of the trea
void traversePostOrder(sNode *root) {
 if (root != NULL) {
 traversePostOrder(root->lChildPtr);
 traversePostOrder(root->rChildPtr);
 //finally print root
 printf("%d\n", root->iNodeData);
 }
}



int main()
{
 int i = 1;
 sNode * rootNode = createNode(i);
 sNode * currentNode;

 i = populateSubTree(i, rootNode);
 i = populateSubTree(i, rootNode->lChildPtr);
 i = populateSubTree(i, rootNode->rChildPtr);

 
 currentNode = rootNode->lChildPtr;
 i = populateSubTree(i, currentNode->lChildPtr);
 i = populateSubTree(i, currentNode->rChildPtr);

 currentNode = rootNode->rChildPtr;
 i = populateSubTree(i, currentNode->lChildPtr);
 i = populateSubTree(i, currentNode->rChildPtr);

 printf("Traversing the tree, in order\n");
 traverseInOrder(rootNode);

 printf("\nTraversing the tree, post order\n");
 traversePostOrder(rootNode);

 return 0;
}

That’s enough for today. If you want, take a look at my book on Amazon.com http://www.amazon.com/Big-Als-C-Standard-ebook/dp/B00A4JGE0M

Dynamic Storage Allocation

The malloc() function provides dynamically-allocated storage.

The malloc() function sets aside a contiguous chunk of bytes of memory and returns the address of this chunk to be stored in a pointer.

The calloc() function sets aside a block of memory in the same fashion as malloc(), but it also zero-initializes the memory, meaning that the allocated memory is filled with 0-bits. The calloc() function also takes two arguments, whereas malloc() takes only one. The calloc() function allocates the number of bytes produced by the product of the two arguments it receives.

#include "stdafx.h"
#include <stdlib.h>

int main()
{
 //allocate 1 int's worth of memory
 int *i = (int *)malloc(sizeof(int));
 //allocate 5 double variable's worth of memory
 double *dArray = (double *)malloc(sizeof(double) * 5);

 //let's use calloc()
 char *szText = (char *)calloc(64, sizeof(char));
 int *i2 = (int *)calloc(1, sizeof(int));

 //will display 'garbage' value
 printf("Allocated with malloc(), *i = %d\n", *i);
 //will display 0
 printf("Allocated with calloc(), *i2 = %d\n", *i2);

 return 0;
}

Allocated memory storage is on the heap. Traditionally, the heap started at the low address of the process and grew upwards, whereas the stack started at a high address and grew downwards. Occasionally, a stack-heap collision would occur, where the stack or the heap grew overwrote one or the other.  As memory on modern OSes is pageable virtual memory, this is no longer a concern. At this point, even the idea of the stack growing downward and the head growing upward is conceptual rather than literal.

If the allocated memory function asks for more bytes than are available on the heap, the malloc() or calloc() function returns a NULL pointer. So, by checking the pointer with NULL, we can ensure that the memory was allocated.

#include "stdafx.h"
#include <stdlib.h>

int main()
{
 int *iPtrArray = (int*)malloc(10 * sizeof(int));

 if (iPtrArray != NULL) {
 printf("Memory allocated.\n");
 }

 return 0;
}

When allocated memory has been used and is no longer needed, we can return it to the heap with the free() function. Memory that has been allocated dynamically should be free, otherwise we will end up with memory leaks.

Now, when a process ends, all of the memory is reclaimed by the system . Therefore, it is not necessarily a big deal if we do not call free() in the small programs we have been writing. However, it’s best to maintain the ironclad habit of free-ing all memory that has been dynamically allocated.

 #include "stdafx.h"
#include <stdlib.h>

int main()
{
 double *dPtrArray = (double *)malloc(sizeof(double) * 5);

 if (dPtrArray != NULL) {
 printf("Memory allocated!\n");
 }

 //free the memory
 free(dPtrArray);
 dPtrArray = NULL;

 return 0;
}

After calling free on a pointer, we should consider the pointer to have an undefined value. Setting the value of the pointer to NULL explicitly is a good practice. A dangling pointer can result if we try to access deallocated memory via a pointer.