Linked-Lists in C

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

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

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

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

void displayList(NODE *ptr);

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

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

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

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

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

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


	displayList(nOne);

    return 0;
}

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

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

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

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

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

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

int main() {
	
	const int buffer_size = 64;

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

	viewList(nOne);

	deleteTail(&nOne);

	viewList(nOne);

	return 0;
}

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

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

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

 

Pointers to Pointers, Structures, Pointers to Structures

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

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

#define SMALL_BUFFER 256

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

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

	int numStudents = 0;
	int numTests = 0;

	int i = 0;
	int j = 0;

	char buffer[SMALL_BUFFER];

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

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


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

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

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

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

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

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

	printResults(students, grades, numStudents, numTests);

    return 0;
}

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

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

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

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

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

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

	char **myArgs = argv;

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


    return 0;
}

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

const int char_buffer_size = 128;

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

void changeName(struct employee *emp);

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

	struct employee *empPtr;

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

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

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

	changeName(&nd);

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

    return 0;
}

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

 

Searching and Sorting Arrays

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

Arrays are represented in memory using sequential mapping.

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

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

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

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

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

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

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

    addArray(arrOne, arrTwo, rSize, cSize);


    return 0;
}

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

    printArray(arrOne, row, column);

}

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

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

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

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


#define ROW_LENGTH 3
#define COL_LENGTH 3

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

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

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

    return 0;
}

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

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

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

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

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

int main()
{

    const int bounds = 10;

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

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


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

}


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

 

Introduction to Sorting and Searching in C

A lot of computation time is spent searching for values. Normally, the objects searched for are records that have a sort key chosen for the search – such as the time, a range of numeric values, name, etc. Searching thus involves comparing the given data objects to a given search key value. If the value can be matched, then a pointer to that object in memory must be returned.

The three most basic searches are linear, binary, and interpolation search. A linear search proceeds linearly through an array.

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

typedef struct {
	int iValue;
	double dValue;
} record;

record * createRecords(int numRecords);
void initializeRecords(record recordSet[], int numRecords);
void printRecords(record recordSet[], int numRecords);
void printARecord(record recordSet[], int loc);
int main()
{
	time_t tme;

	int numRecords = 100;
	srand((unsigned)(time(&tme)));
	record *recordSet = createRecords(numRecords);
	initializeRecords(recordSet, numRecords);
	printRecords(recordSet, numRecords);

    return 0;
}

void printARecord(record recordSet[], int loc) {
	printf("Record %d contains values %d and %f\n", loc + 1, recordSet[loc].iValue, recordSet[loc].dValue);
}

void printRecords(record recordSet[], int numRecords) {
	for (int i = 0; i < numRecords; i++) {
		printf("%d %f \t", recordSet[i].iValue, recordSet[i].dValue);
	}
	printf("\n");
}

void initializeRecords(record recordSet[], int numRecords) {
	for (int i = 0; i < numRecords; i++) {
		recordSet[i].iValue = rand() % 50;
		recordSet[i].dValue = (double)(i + 1) / ((rand() % 20) + 1);
	}
}

//instantiate an array of records 
record * createRecords(int numRecords) {
	record *returnRecord = (record *)malloc(sizeof(record) * numRecords);
	return returnRecord;
}

The code above sets up an array of 100 structs that each contain an integer and a floating point value. We will use this array to look at some simple search algorithms.

The most elementary search is a linear search. A linear search is so named because it goes through an array in sequence till it finds the requested value.

//Use a linear search algorithm until a matching record is found
void tryLinearSearch(record recordSet[], int numRecords) {
	int req = 0;
	int found = -1;
	
	printf("Performing linear search\n");
	while (found < 0) {
		req = rand() % 50;
		printf("Searching for value %d...\n", req);
		found = linearSearch(recordSet, numRecords, req);
	}

	printf("Value %d found!\t", req);
	printARecord(recordSet, found);

}

int linearSearch(record recordSet[], int limit, int req) {
	int rLocation = 0;
	while (rLocation++ < limit) {
		//find first match
		if (recordSet[rLocation].iValue == req) {
			break;
		}
	}
	//no record found, return neg value
	if (rLocation == limit) {
		rLocation = -1;
	}

	return rLocation;
}

A linear search not only proceeds linearly through an array, its processing time increases linearly with the number of elements in the collection.  In the worst-case scenario, when not matching element is found, the search time is O(n), where n is the length of the collection being searched.

One way to save time in a linear search is to order the records in decreasing or increasing order. The linear search can then be modified by terminating the search as soon as a record is met whose value is greater than or less than the desired value.

The most elementary sort is the maximum entry sort. In the maximum entry sort organizes elements in an array into decreasing order, where the largest number is placed in element 1, the second largest in element 2, and so on.  In such an algorithm, when the k largest numbers have been put in the first k elements of the array, a variable, let’s call it next, will point to the element of the array into which the next largest element should be placed. The next variable must be updated to next + 1, so that it will contain the value k + 1.

This algorithm would need to be called n – 1 times, where n is the size of the array. In the algorithm, we will compare each element to a variable containing the largest element found so far.


//copy array 
int copyRecordArray(record sourceRecords[], record targetRecords[], int bounds) {
	int rValue = 0;

	for (int i = 0; i < bounds; i++) {
		targetRecords[i].dValue = sourceRecords[i].dValue;
		targetRecords[i].iValue = sourceRecords[i].iValue;
	}
	return rValue;

}

//return a new, sorted array
record * maxEntrySort(record recordSet[], int bounds) {
	int next, maxLocation;

	//copy the data to new array
	record *newArray = createRecords(bounds);
	copyRecordArray(recordSet, newArray, bounds);
	//sort the records copied into the new array
	for (next = 0; next < bounds; next++) {
		//find the maximum value in the array
		maxLocation = locateMax(newArray, next, bounds);
		//interchange record at current position with record at position of max
		switchRecords(newArray, next, maxLocation);
	}
	return newArray;

}

//this function locates the max value in an array
int locateMax(record recordSet[], int next, int bounds) {
	int largest, i, maxLocation;
	maxLocation = next;
	largest = recordSet[maxLocation].iValue;
	//go forward through array looking for the largest remaining value
	for (i = next + 1; i < bounds; i++) { 		
if (recordSet[i].iValue > largest) {
			maxLocation = i;
			largest = recordSet[i].iValue;
		}
	}
	return maxLocation;
}


//switch the locations of two records in the record array
void switchRecords(record recordSet[], int recordA, int recordB) {
	record tmpRecord;
	//copy recordA's data into a temp
	tmpRecord.dValue = recordSet[recordA].dValue;
	tmpRecord.iValue = recordSet[recordA].iValue;

	//copy recordB's data into recordA
	recordSet[recordA].dValue = recordSet[recordB].dValue;
	recordSet[recordA].iValue = recordSet[recordB].iValue;

	//copy the recordA data stored in the temp variable to recordB
	recordSet[recordB].dValue = tmpRecord.dValue;
	recordSet[recordB].iValue = tmpRecord.iValue;
}

 

How much time does this algorithm take? Well, one call is made to the locateMax() function n – 1 times, and each search for locateMax() takes n – k, where n is the upper bounds of the array and k is the value of the current position in the array. The total number of comparisons sums up to n(n-1)/n. The final result is O(n^2) time.

The bubble sort gets its name from the manner in which larger entries rise up to the top of the collection while smaller entries float down. To perform a bubble sort, we traverse the array, comparing the two adjacent elements, starting with the first two and ending with the last two. If the second element is larger than the first, we switch them. Each traversal of the array is considered one pass. After the first pass the smallest entry will be at the bottom of the array.

In general, after the kth pass, the k smallest entries will be in order in the bottom k elements in the array. The array will be sorted after at most n – 1 passes, though it may actually be sorted before then.

record * bubbleSort(record recordSet[], int bounds) {
	bool notDone = true;
	int i; 
	record * rArray = createRecords(bounds);
	copyRecordArray(recordSet, rArray, bounds);
	int numPasses = 0;
	while (notDone) {
		notDone = false;
		for (i = 0; i < bounds; i++) { 			if (rArray[i + 1].iValue > rArray[i].iValue) {
				switchRecords(rArray, i, i+1);
				notDone = true;
			}
		}
		numPasses++;
	}
	printf("%d passes made\n", numPasses);
	return rArray;
}

The worst cast scenario is O(n^2) for bubble sort, the same as for a linear sort. However, the best case scenario is O(n), with the more sorted the initial data, the shorter the time.

With the elements sorted, we are free to perform a binary search. In a binary search, every time a test is made in the search, there are two choices, to search either half of the remaining elements for the desired element.

With a binary search, at most n key comparisons are needed when searching among 2^n elements, as long as each comparison is able to split the remaining collection of elements into two parts that differ in size by at most one.

//be sure to use sorted array
void tryBinarySearch(record recordSet[], int numRecords) {
	int req = 0; 
	int found = -1;

	printf("Perfoming binary search\n");
	while (found < 0) {
		req = rand() % 50;
		printf("Searching for value %d...\n", req);
		found = binarySearch(recordSet, numRecords, req);
	}
	printf("Value %d found\t", req);
	printARecord(recordSet, found);
}

int binarySearch(record recordSet[], int bounds, int key) {
	int rValue = -1;
	int top, mid, bottom;
	bool found = false;
	top = 0; 
	bottom = bounds;
	while ((top <= bottom) && found == false) {
		mid = (top + bottom) / 2;
		if (recordSet[mid].iValue == key) {
			found = true;
			rValue = mid;
		}
		//if the value is less than the searched for value
		else if (recordSet[mid].iValue < key) {
			bottom = mid - 1;
		}
		else {
			top = mid + 1;
		}
	}
	return rValue;
}

Each pass through the loop in a binary search involves at most half the elements that were under consideration in the preceding pass; starting with n elements, after one pass through the loop at most 1/2n elements are left, after two passes, 1/2(1/2n)n elements, after three passes 1/2(1/2)(1/2) elements are left, and after k passes at most [1/2(1/2)^(k-1)]n elements are left, or (1/2^k)n. Therefore in the worst case the search time is O(lg n).

 

More Recursion in C

Recursion is a repetitive process where a function calls itself directly or indirectly. A function is directly recursive when it calls itself from within its scope, and it is indirectly recursive when it calls other functions that eventually calls it back.

In general, we use two approaches to writing repetitive algorithms. The first approach is the iterative approach using loops, the other uses recursion.  For example, let’s consider a factorial:

factorial (n) = 1 if n = 0
                n * (n -1) * (n -2) ... 1 if n > 0

A repetitive function is iterative when the definition of the function involves only the parameters and not the function itself. A repetitive function is defined recursively whenever the function appears within the definition itself. To look at factorials again, we would define them as:

factorial(n) = 1 if n = 0
               n * factorial(n - 1) if n > 0

 

We will write two functions, one two solve the factorial problem in an iterative manner, and the other to solve the factorial problem in a recursive manner.

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

long itFactorial(int n){
    int i;
    long rValue = 1;
    for(i = 1; i <= n; i++){
        rValue = rValue * i;
    }
    return rValue;
}

long recFactorial(int n){
    if(n==0) { return 1;}

    return n * recFactorial(n-1);

}

int main()
{

    printf("%li\n", itFactorial(7));

    printf("%li\n", recFactorial(7));

    return 0;
}

Recursive functions have two elements, solving one part of the problem, and/or reducing the size of the problem. The call that delivers a definitive solution is known as the base case. Every recursive function must have a base case.

When implementing a recursive function, we should bear in mind how the function’s arguments are put on the stack. The stack frame grows by push operations caused by function calls, and it shrinks by pop operations by function returns. Each call gets a fresh copy of automatic variables that are totally independent of the previous set of values.

A popular example of a recurrence relation is the Fibonacci sequence, in which a number is the sum of the previous two numbers. The first few numbers of the Fibonacci sequence are 0, 1, 1, 2, 3, 5, 8, 13, 21, 34. To start the sequence, we define the first two numbers as 0 and 1, so that the third number is also 1 (0 + 1), and the fourth number in the sequence is 2 (1 + 1).

We will see two examples of the recursive Fibonnaci function.

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

int fibA(int iParam){
    int rValue;

    //base case for 0 and 1 in the sequence
    if(iParam == 0 || iParam == 1) { return iParam; }

    //calls itself twice
    rValue = fibA(iParam - 1) + fibA(iParam - 2);

    printf("Returning %d\t", rValue);

    return rValue;
}

int fibB(int iNum, int iPrevOne, int iPrevTwo){
    int rValue;

    if(iNum == 0){
        printf("iNum == 0, returning %d\n", iPrevTwo);
        return iPrevTwo;
    } else if (iNum == 1){
        //when count reaches 1, returning back the final number
        //reached by adding iPrevOne and iPrevTwo
        printf("iNum == 1, returning %d\n", iPrevOne);
        return iPrevOne;
    } else {
        printf("%d, %d, %d\n", iNum-1, iPrevOne + iPrevTwo, iPrevOne);
        rValue = fibB(iNum-1, iPrevOne + iPrevTwo, iPrevOne);
        return rValue;
    }
}


int main()
{

    int i = 0;

    printf("\nfibA(5) = %d\n", fibA(5));
    printf("\nfibA(8) = %d\n", fibA(8));

    printf("\nfibB(7) = %d\n\n", fibB(7, 1, 0));
    printf("\nfibB(9) = %d\n", fibB(9, 1, 0));

    return 0;
}

We can also use a recursive function to find the greatest common denominator. The function will return the second parameter if the first parameter modulo the second parameter is 0, meaning that they divide evenly. Otherwise, the function will call itself, with the second parameter as the first argument, and the remainder of the modulo operation as the second argument.

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

int findGCD(int a, int b){
    int remainder;
    if((remainder = a % b) == 0){
        return b;
    }
    return findGCD(b, remainder);
}


int main()
{
    printf("The GCD of 100 and 8 is %d\n", findGCD(100, 8));
    printf("The GCD of 150 and 5 is %d\n", findGCD(150, 5));

    return 0;
}

One of the most famous examples of a recursive s0lution is the Towers of Hanoi problem, but we will look at that at another time.

 

 

 

 

Very Short Look at the Big O and Nested For Loops

Big O notation is used to indicate the runtime of an algorithm as it processes large amounts of data, in which case the determining factor of the execution time is the term with the largest exponent, ignoring all other terms and even the coefficient as the data set to be processed grows extremely large. Big O notation therefore drops the constants, which can be confusing.

#include <time.h>
#include <stdlib.h>

void populateArray(int array[], int size, int num_max);
void printArray(int arrayParam[], int size);
void minMaxA(int iArray[], int size, int num_max);
void minMaxB(int iArray[], int size, int num_max);

int main() {
	
	const int array_size = 2056;
	const int num_max = 7800;

	int iArray[array_size];
	int iMax = 0;

	populateArray(iArray, array_size, num_max);
	printArray(iArray, array_size);

	minMaxA(iArray, array_size, num_max);
	minMaxB(iArray, array_size, num_max);

	return 0;

}

void printArray(int arrayParam[], int size) {
	int *iArray = arrayParam;
	for (int i = 0; i < size; i++) {
		printf("%d ", *iArray++);
	}
}

//populate the array with random numbers
void populateArray(int array[], int size, int num_max) {
	srand(time(NULL));
	for (int i = 0, x = 0; i < size; i++) {
		x = rand() % num_max;
		array[i] = x;
	}
}

//one loop 
void minMaxA(int iArray[], int size, int num_max) {
	int iMin = num_max;
	int iMax = 0;
	for (int i = 0; i < size; i++) {
		//check for minimum 
		if (iArray[i] < iMin) { iMin = iArray[i]; } 		       //check for maximum 		
                if (iArray[i] > iMax) { iMax = iArray[i]; }
	}

	printf("\nThe maximum value is %d\n\n", iMax);
	printf("\nThe minimum value is %d\n\n", iMin);
}

//two loops
void minMaxB(int iArray[], int size, int num_max) {
	//start search from highest value
	int iMin = num_max;
	//start search from lowest value
	int iMax = 0;
	//loop one
	for (int i = 0; i < size; i++) {
		if (iArray[i] < iMin) { iMin = iArray[i]; }
	}
	//loop two
	for (int i = 0; i < size; i++) { 		
                if (iArray[i] > iMax) { iMax = iArray[i]; }
	}

	printf("\nThe maximum value is %d\n\n", iMax);
	printf("\nThe minimum value is %d\n\n", iMin);
}


Note that the minMaxA() and minMaxB() functions have the same time complexity, since we drop the coefficient. Likewise, we drop all other other non-dominant terms, meaning that the term or terms with the largest exponents are the only ones that we need to concern ourselves with.

void printSumProducts(int iArray[], int length);

int main() {
	
	int iArray[7] = {73, 4, 8, 15, 16, 23, 42 };
	printSumProducts(iArray, 7);

	return 0;

}


//this function takes O(2) time
//the fact that it loops twice is irrelevant 
void printSumProducts(int iArray[], int length) {
	long long int sum = 0;
	//initialize product to 1, not 0
	long long int product = 1;

	for (int i = 0; i < length; i++) {
		sum += iArray[i];
	}

	for (int i = 0; i < length; i++) {
		product *= iArray[i];
	}

	printf("Sum of the array: %lld\n", sum);
	printf("Product of the array: %lld\n", product);

}

Runtimes tend to increase as loops are called within loops. For example, a nested loop that iterates through the entire list once for each loop as O(n^2) time.

void printPairs(int iArray[], int arraySize);
void printUnorderedPairs(int iArray[], int arraySize);

int main() {
	
	const int array_size = 10;

	int iArray[array_size] = { 1138, 151, 191, 47, 353, 383, 16, 32, 64, 128 };

	printPairs(iArray, array_size);

	printf("\n\n");

	printUnorderedPairs(iArray, array_size);

	return 0;

}

//both of these functions take O(n^2) time
void printPairs(int iArray[], int arraySize) {
	int iNumPairs = 0;
	for (int i = 0; i < arraySize; i++) { 		
           for (int j = arraySize - 1; j >= 0; j--) {
			printf("(%d, %d) \t", iArray[i], iArray[j]);
			iNumPairs++;
		}
		printf("\n");
	}
	printf("Printed %d pairs total.\n", iNumPairs);
}

//inner loop starts at i + 1
//stil takes O(n^2) time
void printUnorderedPairs(int iArray[], int arraySize) {
	int iNumPairs = 0;
	for (int i = 0; i < arraySize; i++) {
		for (int j = i + 1; j < arraySize; j++) {
			printf("(%d, %d) \t", iArray[i], iArray[j]);
			iNumPairs++;
		}
		printf("\n");
	}
	printf("Printed %d pairs total.\n", iNumPairs);
}

Even though the second function performs roughly half as many operations as the first, it still has the same time complexity.

Another illustration of this is given with the following code, which contains a function that reverses an array.

void reverseArray(int array[], int lengthParam);
void printArray(int array[], int length);

int main() {
	
	const int array_length = 11;

	int iArray[array_length] = { 10538, 1, 451, 47, 1865, 73, 6174, 1701, 2001, 8675309, 8086 };

	printArray(iArray, array_length);
	reverseArray(iArray, array_length);
	printArray(iArray, array_length);

	return 0;

}


void reverseArray(int array[], int lengthParam) {
	int halfLength = lengthParam / 2;
	int temp;
	for (int i = 0, j = lengthParam - 1; i < halfLength; i++) {
		temp = array[i];
		array[i] = array[j - i];
		array[j - i] = temp;
	}
}

void printArray(int array[], int length) {
	for (int i = 0; i < length; i++) {
		printf("%d ", array[i]);
	}
	printf("\n\n");
}

Even though our reverseArray() function only goes through half of the array, or less, the big O time is still considered to be O(n).

 

 

Pointer pointers

Pointer pointers are pointers that point to pointers. We’re really down the rabbit hole, folks.

A pointer pointer is a memory location that holds the address of a pointer. We use pointer pointers when attempting to manipulate another pointer by reference, essentially. We mostly encounter pointer pointers in the wild when dealing with dynamically allocated data structures that need to be passed ‘by value’ to a function.

A pointer pointer will hold the address of a pointer, which in turn holds the address of the block of data we want to work with. Pointer pointers are can also be called double indirection.

Pointer pointers aren’t as difficult as they sound, but they’re as far out as I personally am willing to get.

int main() {

	int iNum = 42;
	int *iNumPtr = NULL;
	int **iNumPtrPtr = NULL;

	printf("The address of the actual data is %p and it holds %d\n", &iNum, iNum);
	
	//assign address of iNum to iNumPtr
	iNumPtr = &iNum;

	printf("The address of the pointer to the data is %p and it holds %p\n", &iNumPtr, iNumPtr);

	//assign address of iNumPtr to iNumPtrPtr
	iNumPtrPtr = &iNumPtr;

	printf("The adress of the pointer to the pointer to the data is %p and it holds %p\n", &iNumPtrPtr, iNumPtrPtr);


	printf("We can access the original data via the pointer pointer. It's %d!!!\n", **iNumPtrPtr);

	return 0;

}

One of the virtues of pointer pointers is that they enable us to perform the dynamic initialization of arrays and strings from within a function. We note here that the C language copies all function parameters onto the stack, thus creating a unique variable that we then use as a local variable in the function. To pass by value, we pass the function the address of the data we wish to use locally in the function, which is then copied onto the stack. So within the function, the pointer itself is a unique copy, even if the data it points to has scope outside the function.

void workingWithParameters(char *string, char **szPtr);

int main() {

	char *string = "Nice boat!";

	printf("The address of the string is %p\n", &string);
	printf("And its value is %s\n", string);

	workingWithParameters(string, &string);

	printf("Back in main() the value is now %s\n", string);

	return 0;

}


void workingWithParameters(char *string, char **szPtr) {
	printf("The address of the string on the stack is %p\n", &string);
	printf("But back in main() the string is located really at %p\n", *szPtr);
	printf("And its value is %s\n", *szPtr);
	*szPtr = "For great justice!";
}

 

Pointer pointers are typically used as function parameters. It’s important to remember that all function parameters are local to the function, even ones that are passed by reference via the pointer mechanism.