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

 

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.

Pointers and Dynamic Memory

The malloc() function allocates a certain number of bytes of heap storage for our use. We specify the size of the memory block to allocate in bytes using a value of type size_t, which is an alias of an unsigned integer type. The function returns a pointer to the allocated memory block.

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

int main()
{
 size_t NumBytes = 256;
 void *ptrMemBlock;

 ptrMemBlock = malloc(NumBytes);

 if (ptrMemBlock == NULL) {
 printf("Failed to allocated memory.\n");
 exit(EXIT_FAILURE);
 }
 else {
 printf("Allocated memory.\n");
 }

 free(ptrMemBlock);

 return 0;
}

Note that the free() function returns a previously allocated block of memory to the free list.

To reiterate, size_t is a typedef representing the number of bytes to allocate.

The malloc() function returns a null pointer if it fails.

When allocating a block of memory of a particular type, we can use the sizeof() operator to calculate the number of bytes per unit to allocate. The use of sizeof() is important for maintaining portability.

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

int main()
{
 size_t byteSize = 512;
 //wchar_t technically isn't standard (?)
 //but we don't follow *their* rules here
 wchar_t *wszStr;

 wszStr = (wchar_t*)malloc(sizeof(wchar_t) * byteSize);

 if (wszStr == NULL) {
 printf("Failed to allocate buffer. Nuts!\n");
 exit(EXIT_FAILURE);
 }
 else {
 //copy the unicode string 
 //wcspy_s takes three params
 //the destination, the max number of wide 
 //chars to copy, and the source
 wcscpy_s(wszStr, byteSize, L"It can be said that the history of science is a history of the expansion of the human body's functionality, in other words, the history of humanity's cyberization.");
 }

 printf("%ls.\n", wszStr);

 free(wszStr);

 return 0;
}

Technically, it’s a good idea to initialize pointers to NULL at declaration and after free. With small programs such as these examples, it may seem extraneous, but its better to get in the habit of doing it always, even when unnecessary, then to forget even once when it is necessary.

Setting unused pointers to NULL is basically all-around good defensive programming, as it protects us from dangling pointer bugs, which can be difficult to track down. Always remember that in C and C++ pointers are inherently unsafe.

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

int main()
{
	int i;
	int *iPtrBlock = NULL;
	
	iPtrBlock = (int *)malloc(sizeof(int) * 4);

	if (iPtrBlock == NULL) {
		printf("Error allocating memory.\n");
		exit(EXIT_FAILURE);
	}

	*iPtrBlock = 42;
	*(iPtrBlock + 1) = 73;
	*(iPtrBlock + 2) = 1138;
	*(iPtrBlock + 3) = 404;

	for (i = 0; i < 4; i++) {
		printf("%d\n", *(iPtrBlock + i));
	}

	//verify we are not passing free()
	//a NULL pointer
	if (iPtrBlock != NULL) {
		free(iPtrBlock);
	}
	
	iPtrBlock = NULL;
	
    return 0;
}


The realloc() function will change the size of the space allocated on the heap. If realloc() returns a NULL, it was unable to allocate any more free space on the heap; however, this is an unlikely event given memory sizes and the amount of data we happen to be working with. The realloc() function returns a pointer, as it may have had to move the memory block in order to fulfill the request to increase the block’s size.

#include <stdlib.h>
#include <Windows.h>

int main()
{
 double dNum = 0;
 const size_t szBuffer_Size = 256;
 const size_t numDigits = 16;
 double *dStorage = (double*)malloc(sizeof(double));
 char szBuffer[szBuffer_Size];
 //get handle for stdin
 HANDLE hStdin = GetStdHandle(STD_INPUT_HANDLE);
 DWORD dwBytesRead;
 int iLocation = 0;
 

 while (true) {
 printf("Please enter a number: ");
 ReadFile(hStdin, szBuffer, szBuffer_Size, &dwBytesRead, NULL);
 if (dwBytesRead > numDigits) {
 szBuffer[numDigits] = '\0';
 }
 else {
 szBuffer[dwBytesRead] = '\0';
 }
 //convert string to double
 dNum = atof(szBuffer);

 printf("Entering %f into database.\n", dNum);
 *(dStorage + iLocation) = dNum;
 
 printf("Continue entering numbers? (y/n) ");
 ReadFile(hStdin, szBuffer, szBuffer_Size, &dwBytesRead, NULL);
 *(szBuffer + 1) = '\0';
 if (*szBuffer == 'n' || *szBuffer == 'N') {
 printf("Thank you.\n");
 break;
 }

 iLocation++;

 //allocate more memory
 dStorage = (double*)realloc(dStorage, sizeof(double) * (iLocation + 1));
 } //end while loop

 printf("Numbers entered: \n");
 while (iLocation >= 0) {
 printf("%f \t", *(dStorage + iLocation));
 iLocation--;
 }

 return 0;
}

Allocating and Freeing Dynamic Variables in C

We create a pointer variable to an integer with the declaration int *p; Having declared a variable p as a pointer to a specific type, it is possible to dynamically create an object of that type and assign its address to p.

We do this by calling the standard library function malloc(), which dynamically allocates a portion of memory of a specified size and returns  a pointer to it.

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

int main(void){

    int *i, *j;

    int x;

    i = (int *) malloc(sizeof(int));

    *i = 1138;

    j = i;

    printf("%d %d\n", *i, *j);

    x = 73;

    *i = x;

    printf("%d %d\n", *i, *j);

    *i = 5;

    printf("%d %d\n", *i, *j);

    return 0;

}

The sizeof operator returns the size, in bytes, of its operand.  We can use sizeof in conjunction with malloc() to get an object of the proper size.

The free() function is used to return allocated storage. Calling free() on a pointer makes the memory pointed to by the pointer available for reuse.  While most operating systems “clean up” memory after a program exits, it’s still really a good idea to explicitly clean up any dynamically allocated memory ourselves.

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

int main(void){

    int *p = (int *)malloc(sizeof(int));
    int *q = (int *)malloc(sizeof(int));
    double *d = (double *)malloc(sizeof(double));
    double *e = (double *)malloc(sizeof(double));

    *p = 404;
    *q = 711;
    free(p);    
    p = q;
    printf("%d %d\n", *p, *q);
    
    *d = 0.57721;
    *e = 1.12358;

    printf("%f %f\n", *d, *e);

    free(e);
    e = d;
    *d += 7.11;

    printf("%f %f\n", *d, *e);

    //clean up time
    free(d);
    free(q);
        
    return 0;

}

As we have seen in these past two programs, if two pointers point at the same variable, they are functionally identical. Thus, an assignment to one changes the value of the other.

Next, let’s take a look at creating a linked list using dynamic variables. A linked list consists of a set of nodes, each of which has two fields: an information field and a pointer to the next node in the list. In addition, we have an external pointer that points to the first node in the list.

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

struct node * getNode();

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

int main(void){

    struct node *begin, *temp;    
    struct node *nodePtr;

    temp = getNode();
    temp->data = 42;
    
    begin = temp;
    nodePtr = temp;
    
    nodePtr->next = getNode();
    temp = nodePtr->next;

    temp->data = 73;
    nodePtr = temp;
    nodePtr->next = getNode();

    temp = nodePtr->next;
    temp->data = 1999;
    temp->next = NULL;

    nodePtr = begin;

    while(1){
        printf("%d\n", nodePtr->data);
        if(nodePtr->next==NULL){
            break;
        } else {
            nodePtr = nodePtr->next;
        }
    }
    
    return 0;

}

struct node * getNode(){
    struct node *p;
    p = (struct node *)malloc(sizeof(struct node));
    return p;
}

When looking at the above code, we should ask ourselves how we would go about returning all of the nodes’ memory to the heap.

Note that the getnode() function could as well be implemented via a macro.

Next, let’s look at implementing a list as a queue. A queue follows the first in, first out principle – the first item to be inserted into a queue, will also be the first to be taken out. To do this, we will create a second structure, known as a queue. This structure will have two fields; the first field will be a node pointer to the first node in the list, and the second pointer will be a pointer to the last node in the list.

Our function for getting a queue will initialize both of these fields to NULL. We will then implement two functions, pop() and push(). The pop() function takes a node out out of the queue, frees it in memory, and then returns the value it was storing. The push() function creates a new node, assigns its data field a value, and then assigns it to the end of the queue.

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

struct node *getNode();
struct queue * getQueue();
int empty(struct queue *q);
void push(struct queue *q, int x);
int pop(struct queue *q);

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

struct queue{
    struct node *first;
    struct node *last;
};

int main(void){
    struct queue *q = getQueue();
    printf("queue allocated.");
    if(empty(q)){
        printf("queue is empty.\n");
    }

    push(q, 2001);
    push(q, 2600);
    push(q, 80);
    push(q, 1970);
    push(q, 1701);

    while(empty(q)==0){
        printf("%d\n", pop(q));
    }


    return 0;    
}




struct node * getNode(){
    struct node *p;
    p = (struct node *)malloc(sizeof(struct node));
    return p;
}

struct queue * getQueue(){
    struct queue *q;
    q = (struct  queue*)malloc(sizeof(struct queue));
    q->first=NULL;
    q->last=NULL;
    return q;
}    

int empty(struct queue *q){
    if(q->first==NULL){
        return 1;
    } else {
        return 0;
    }
}

void push(struct queue *q, int x){
    struct node *n = getNode();
    n->data = x;
    n->next = NULL;
    if(q->last!=NULL){
        (q->last)->next = n;    
    } else {
        q->first = n;
    }
    q->last = n;
}

int pop(struct queue *q){
    int x;
    struct node *n = q->first;
    q->first = n->next;
    if(q->first==NULL){
        q->last=NULL;
    }
    x = n->data;
    free(n);
    return x;
}

One of the nice things about working with higher level languages such as C# is that data structures such as linked lists are already implemented for us in the language.

To learn more about C, take a look at my book at http://www.amazon.com/Big-Als-C-Standard-ebook/dp/B00A4JGE0M/

 

 

 

 

 

Reviewing Dynamic Memory Allocation in C

We can find four memory management functions in the stdlib.h header file: malloc(), realloc(), calloc(), and free(). The malloc() function allocates memory from the heap. The realloc() function reallocates memory relative to a previously allocated block of memory. The calloc() function is like malloc(), but zeros out the memory that is allocated from the heap. Finally, the free() function returns a block of memory to the heap.

The malloc() function allocates a block of memory from the heap; if no memory is available, NULL is returned. Since there is no guarantee that a malloc() call will work, we should always check to see if the function returned NULL.

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

int main(void){
    
    void *memPtr = (void*)malloc(8);

    if(memPtr==NULL){
        printf("Could not allocate memory.\n");
    } else {
        printf("8 bytes allocated.\n");
    }

    free(memPtr);

    return 0;

}

The free() function accepts a pointer as an argument and returns the block of memory pointed to back to the heap.

In the next program I use bitwise operators to turn on bits in the memory block. While using bitwise operators is lots of fun, at least I think so, it isn’t the most necessary thing to know how to do. The most important thing to remember when using bitwise operators is that 0 and 1 have the same value in binary as they do in the base 10 number system. As a recap, (1 << n) will turn on the bit at position n, and the | operator basically ‘adds’ the number on the left to the  number on the right. If you’re interested in learning more, take a look at my other posts at https://aljensencprogramming.wordpress.com/tag/bitwise-operators/

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

int main(void){

    void *ptr = malloc(1);

    if(ptr!=NULL){
        //turn off all bits in the memory block
        *(char*)ptr = *(char*)ptr & 255;
        printf("%d\n", *(char*)ptr);
        
        //turn on first bit
        *(char*)ptr = *(char*)ptr | 1;
        printf("%d\n", *(char*)ptr);

        //turn on the fourth bit
        *(char*)ptr = *(char*)ptr | (1<<4);
        printf("%d\n", *(char*)ptr);
    }


    //free up the memory
    free(ptr);

    
    

    return 0;

}

Note that it isn’t necessary to explicitly cast the return value of the malloc() function; whether to cast or not to cast is a minor debate topic.

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


int main(void){


    int *ptr = malloc(4);
    int *ptr2 = (int*)malloc(4);

    *ptr = 404;
    *ptr2 = 1138;
    
    if(ptr!=NULL){
        printf("%d\n", *ptr);    
    }

    if(ptr2!=NULL){
        printf("%d\n", *ptr);
    }

    return 0;

}

When using malloc() its important to use the function to allocate the correct number of bytes. So far, we have been using magic numbers to specify the number of bytes to allocate, which is generally a bad idea. Standard procedures is to use the sizeof operator when specifying the number of bytes to allocate.

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

int main(void){

    int *iPtr = (int*)malloc(sizeof(int));

    double *dPtr = (double*)malloc(sizeof(double));


    *iPtr = 3000;
    *dPtr = 255.255;

    printf("%d \t %f\n", *iPtr, *dPtr);
    
    free(iPtr);
    free(dPtr);

    return 0;

}

Sometimes we need to increase or decrease the amount of memory allocated to a pointer, which can be done using the realloc() function. The realloc() function takes two arguments, the first argument is a pointer to the original block of memory, and the second is the new size, which can be larger or smaller than the size of the original memory block.

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

int main(void){

    int *intPtr = (int*)malloc(5*sizeof(int));
    
    *intPtr = 73;
    *(intPtr+1) = 47;
    *(intPtr+2) = 1138;
    *(intPtr+3) = 80;


    printf("%d\n", *(intPtr+1));
    printf("%d\n", *(intPtr+2));

    //resize the array
    intPtr = realloc(intPtr, 4*sizeof(int));
    
    printf("%d\n", *(intPtr+3));
    
free(intPtr);

    return 0;

}

If the size of the new memory block is smaller than the current block, the memory block remains in the same location. If the memory block is larger, either a new block in a new location will be allocated, and the contents of the old block copied over, or else if there is free consecutive memory next to the current block it will be expanded to include it.

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

int main(void){

    int *ints = (int*)malloc(10*sizeof(int));

    printf("ints is located at %p\n", ints);
    
    double *dubs = (double*)malloc(5*sizeof(double));
    
    //ints will most likely be put into a new location
    ints = realloc(ints, 20*sizeof(int));
    printf("ints is located at %p\n", ints);
    
    //memory location will remain the same
    ints = realloc(ints, 5*sizeof(int));
    printf("ints is located at %p\n", ints);

    //don't forget to free the allocated memory
    free(dubs);
    free(ints);
    
    return 0;

}

If you’re interested in learning more about C, take a look at http://www.amazon.com/Big-Als-C-Standard-ebook/dp/B00A4JGE0M/