Data Structures And Algorithms In C Set 1

In coding, references are made to extensive datasets that require management during the development process. Our code acts as the designated space where these datasets reside, and it is essential to organize them effectively within our program. Disorderly data storage can lead to inefficiencies and should be avoided at all costs.

In this sequence of guides, we will explore all the data structures within the C programming language followed by delving into another subject - Algorithms.

Data Types and Data Structures:

These two terms may share the word "Data," but they differ in meaning. Essentially, a data type serves as a property of variables, determining the type of data or value that can be held within a specific variable. C is recognized as a statically typed language, which necessitates the explicit declaration of each variable along with its corresponding data type prior to utilization in the program.

On the flip side, a data structure refers to the assortment and structuring of data originating from various data types that enables us to manipulate and access data. It pertains to how data is organized within the memory of a computer.

integers, floating-point numbers, and so on are classified as data types, while stacks, queues, and similar structures are instances of data structures.

Various kinds of data structures are accessible in the C programming language. Familiarizing ourselves with these structures is crucial to determine the most suitable one for specific requirements.

Here is a visual representation illustrating the categorization in C programming according to the arrangement of variables:

Terminology:

✅ Linear DS: Linear: line. If the elements in a data structure are stored sequentially, it is a linear data structure.
✅ Static DS: If the memory or space in a data structure is fixed and can't be altered according to need at runtime, it is a static data structure.
✅ Dynamic DS: The space or the memory in the data structure can be altered according to the need at runtime.

Facts:

✅ A linear data structure is easy to traverse.
✅ Accessing elements of a static data structure is easy
✅ The space complexity of dynamic data structures is less, making them efficient.

Arrays:

An array is a grouping of uniform elements stored at consecutive memory addresses. Access to array elements is achieved by utilizing indices ranging from 0 to size-1. Arrays can be multidimensional and are capable of storing both primitive and complex data types, with the condition that all elements share the same data type. The primary purpose of utilizing arrays is to consolidate multiple elements of the same data type under a single identifier.

Basic syntax:

Example


data type name[size]

Notable points:

✅ There is no IndexOutOfBoundException in C ; if we try to access an element from out of indexes available in the array, the compiler won't raise any error but gives garbage values.
✅ Data type name: An array of data-typed pointers. If we declare int a, a is the name of an array that can consist of integer pointers.
✅ Pointers: The name of the array indicates the address of the first element, and when passed to functions, arrays are always passed as pointers, even if we use square braces.
✅ array[index] = *(array + index) = index[array] (commutative property)
✅ Matrices: We can use multi-dimensional arrays to represent matrices-arrayrows.

Here is a script containing fundamental array manipulations:

Example


#include<stdio.h>
int sum(int arr[]);
int *sort(int arr[]);
void main()
{
	//declaration
	int i, result;
	int a[5];
	int b[5] = {1, 2, 3, 4, 5};
	int c[5] = {};
	int *d;//array pointer(8 bytes)-stores integer pointers
	//Assigning elements to a[5]
	int j = 10;
	printf("a[5] = ");
	for(i = 0; i < 5; i++)
	{
		a[i] = j;
		j += 10;
		printf("%d ", a[i]);//Accessing elements
	}
	printf("\nOut of index a[5]: %d", a[5]);//garbage value
	//contiguous memory locations
	printf("\nArray elements are stored in contiguous locations:");
	for(i = 0; i < 5; i++)
	{
		printf("\n%p ", &a[i]);
	}
	//pointer indication
	printf("\nPointer indication:");
	printf("\n a[0] = %d", a[0]);
	printf("\n *a = %d", *a);
	printf("\nTraversing using pointer:");
	for(i = 0; i < 5; i++)
	{
		printf("\n%d ", *(a + i));
	}
	printf("\nBy commutative property a[i] = i[a] =");
	printf("\n a[2] = %d", a[2]);
	printf("\n 2[a] = %d", 2[a]);
	//Multi-dimensional arrays
	printf("\nMulti-dimensional array(4 X 4): \n");
	int multarr[4][4], k = 0;
	for(i = 0; i < 4; i++)
	{
		for(j = 0; j < 4; j++)
		{
			multarr[i][j] = k;
			k++;
			printf("%d ", multarr[i][j]);
		}
		printf("\n");
	}
	//passing array to a function
	result = sum(b);
	printf("Sum of elements of b[5] =  %d", result);
	int x[5] = {4, 1, 7, 2, 9};
	printf("\nSorting the array x: ");
	int n = sort(x);
	for(i = 0; i < 5; i++)
	{
		printf("%d ", x[i]);
	}	
} 
int sum(int arr[])
{
	int i, add = 0;
	for(i = 0; i < 5; i++)
	{
		add += arr[i];
	}
	return add;
}
int* sort(int *arr)
{
	int temp, i, j;
	for(i = 0; i < 4; i++)
	{
		for(j = 0; j < 4 - i - 1; j++)
		{
			if(arr[j] > arr[j + 1])
			{
				temp = arr[j];
				arr[j] = arr[j + 1];
				arr[j + 1] = temp;
			}
		}
	}
	return arr;
}

Output:

Output


a[5] = 10 20 30 40 50
Out of index a[5]: 0
Array elements are stored in contiguous locations:
000000000062FDF0
000000000062FDF4
000000000062FDF8
000000000062FDFC
000000000062FE00
Pointer indication:
 a[0] = 10
 *a = 10
Traversing using pointer:
10
20
30
40
50
By commutative property a[i] = i[a] =
 a[2] = 30
 2[a] = 30
Multi-dimensional array(4 X 4):
0 1 2 3
4 5 6 7
8 9 10 11
12 13 14 15
Sum of elements of b[5] =  15
Sorting the array x: 1 2 4 7 9
--------------------------------
Process exited after 0.8778 seconds with return value 2
Press any key to continue . . .

Linked Lists:

A linked list is a type of linear data structure similar to an array; however, it differs in that its elements are not stored in sequential memory locations. Each node or element in the linked list comprises two parts - one containing the data and the other holding a reference to the subsequent node's position. These references establish the linear connection between the nodes, forming the linked list. The initial node's address is typically stored in a variable known as the head.

Notable Points:

✅ A linked list is also used to implement other user-defined data structures like stack and queue .
✅ The first node in a linked list is the head, and we must start all the operations on the linked list from it.
✅ The last node of the linked list refers to Null, showing that the linked list is complete.

In the C programming language, a linked list is formed by utilizing structures, and it shares a similarity with arrays in that it maintains homogeneity, allowing it to exclusively hold data of a single data type within its nodes.

A simple linked list looks like this:

As depicted in the diagram above, the head represents the initial node, and the next (pointer) section of the final node contains None.

A double-linked list looks like this:

In a doubly linked list, each node consists of three parts. The head stores the pointer to the initial node, the "previous" part of the initial node points to None, and the next field of the final node points to None. Every node contains not just the data but also two pointers, one to its preceding node and the other to the subsequent node.

Circular Linked List:

A circular linked list can be single or double:

Circular single linked list:

It's a singly linked list, with the final node pointing back to the initial node, forming a circular structure.

Circular Double-linked List:

It functions as a doubly linked list, with the final node in the sequence pointing back to the initial node, creating a circular structure where the 'previous' pointer of the initial node points to the last node.

Here is a code snippet demonstrating fundamental actions that can be executed on a singly linked list:

Example


#include<stdio.h>
#include<stdlib.h>
//declaration of a linked list
struct Node{
	int data;
	struct Node* next;
};
//Definition of all functions
void displayLL(struct Node *ptr);
void InsertNodeAtBeg(struct Node* head, int value);
void InsertAfterNode(struct Node* head, int node_val, int value);
void InsertAtlast(struct Node* head, int value);
void DeleteBeg(struct Node* head);
void DeleteEnd(struct Node* head);
void DeleteMid(struct Node* head, int pos);
int main()
{
	//Nodes
	struct Node *head;
	struct Node *first;
	struct Node *second;
	struct Node *third;
	//Allocating dynamic memory
	first = (struct Node*)malloc(sizeof(struct Node));
	second = (struct Node*)malloc(sizeof(struct Node));
	third = (struct Node*)malloc(sizeof(struct Node));
	//Given data to the nodes and linking the nodes
	first->data = 1;
	first->next = second;
	second->data = 2;
	second->next = third;
	third->data = 3;
	third->next = NULL;
	head = first;
	//Calling the functions
	printf("The created Linked List: ");
	displayLL(head);
	printf("\n\nInsertions: ");
	InsertNodeAtBeg(head, 5);
	InsertAfterNode(head, 2, 10);
	InsertAtlast(head, 17);
	printf("\n\nDeletions:");
	DeleteBeg(head);
	DeleteEnd(head);
	DeleteMid(head, 3);
}
//displaying the linked list
void displayLL(struct Node *ptr)
{
	printf("HEAD -> ");
	while(ptr != NULL)
	{
		printf("%d -> ", ptr->data);
		ptr = ptr->next;
	}
	printf("NULL");
}
//Inserting a node at the beginning
void InsertNodeAtBeg(struct Node* head, int value)
{
	printf("\n\nAfter inserting %d at the beginning: ", value);
	struct Node* newnode;
	newnode = (struct Node*)malloc(sizeof(struct Node));
	displayLL(head);
	newnode->data = value;
	newnode->next = head;
	head = newnode;
	printf(" -----> ");
	displayLL(head);
}
//Inserting a node after the node with the given value
void InsertAfterNode(struct Node* head, int node_val, int value)
{
	printf("\n\nAfter inserting %d after %d node: ", value, node_val);
	displayLL(head);
	printf(" ----> ");
	struct Node* newnode;
	newnode = (struct Node*)malloc(sizeof(struct Node));
	newnode->data = value;
	struct Node* ptr = head;
	while(ptr != NULL)
	{
		if(ptr->data == node_val)
		{
			newnode->next = ptr->next;
			ptr->next = newnode;
			break;
		}
		ptr = ptr->next;
	}
	displayLL(head);
}
//Inserting a node at the end of the linked list
void InsertAtlast(struct Node* head, int value)
{
	printf("\n\nAfter inserting %d at the end: ", value);
	displayLL(head);
	printf(" ----> ");
	struct Node* newnode;
	struct Node* ptr = head;
	newnode = (struct Node*)malloc(sizeof(struct Node));
	newnode->data = value;
	newnode->next = NULL;
	while(ptr->next != NULL)
	{
		ptr = ptr->next;
	}
	ptr->next = newnode;
	displayLL(head);
}
//deleting the first node
void DeleteBeg(struct Node* head)
{
	printf("\n\nAfter deleting the 1st node: ");
	displayLL(head);
	printf(" ----> ");
	struct Node* temp = head->next;
	head = head->next;
	displayLL(head);
}
//Deleting the last node
void DeleteEnd(struct Node* head)
{
	printf("\n\nAfter deleting the last node: ");
	displayLL(head);
	printf(" ----> ");
	struct Node* ptr = head;
	while(ptr->next->next != NULL)
	{
		ptr = ptr->next;
	}
	ptr->next = NULL;
	displayLL(head);
}
//deleting from the middle
void DeleteMid(struct Node* head, int pos)
{
	printf("\n\nAfter deleting node from %d position: ", pos);
	displayLL(head);
	printf(" ----> ");
	int i;
	struct Node* temp = head;
	for(i=2; i< pos; i++)
	{
  		if(temp->next!=NULL)
		{
   			 temp = temp->next;
  		}
	}
temp->next = temp->next->next;
displayLL(head);
}

Output:

Output


The created Linked List: HEAD -> 1 -> 2 -> 3 -> NULL

Insertions:

After inserting 5 at the beginning: HEAD -> 1 -> 2 -> 3 -> NULL -----> HEAD -> 5 -> 1 -> 2 -> 3 -> NULL

After inserting 10 after 2 node: HEAD -> 1 -> 2 -> 3 -> NULL ----> HEAD -> 1 -> 2 -> 10 -> 3 -> NULL

After inserting 17 at the end: HEAD -> 1 -> 2 -> 10 -> 3 -> NULL ----> HEAD -> 1 -> 2 -> 10 -> 3 -> 17 -> NULL

Deletions:

After deleting the 1st node: HEAD -> 1 -> 2 -> 10 -> 3 -> 17 -> NULL ----> HEAD -> 2 -> 10 -> 3 -> 17 -> NULL

After deleting the last node: HEAD -> 1 -> 2 -> 10 -> 3 -> 17 -> NULL ----> HEAD -> 1 -> 2 -> 10 -> 3 -> NULL

After deleting node from 3 position: HEAD -> 1 -> 2 -> 10 -> 3 -> NULL ----> HEAD -> 1 -> 2 -> 3 -> NULL

Dynamic Arrays:

Once we declare an array, its size will be fixed. It is a drawback because we might run into the need for more memory at runtime. Hence, dynamic arrays are introduced.

✅ Unlike a normal array, dynamic arrays are expandable and shrinkable, providing random access to the elements.
✅ Dynamic arrays are not the same as Variable length arrays . A variable length array is an array whose size is determined at runtime mostly by taking the size as input from the user.
✅ Even in the case of variable length arrays, once the user gives the size, we can't modify it.
✅ Regular arrays and variable-length arrays are allocated on the stack, whereas dynamic arrays are allocated on the heap.
✅ C language doesn't support built-in dynamic arrays , but we can use dynamic memory allocations (DMA).

There are 4 built-in dynamic memory allocation functions available:

malloc:

✅ malloc stands for memory allocation.
✅ Syntax: (type*) malloc(size)
✅ If we call the malloc function with n bytes reserves one large block of memory with n bytes. It returns a void pointer pointing to the first byte, which we can cast into any data type we want - (type*).
✅ If the available space is insufficient, the allocation fails and returns a NULL pointer.
✅ Each block is initialized with garbage values .

calloc:

✅ calloc stands for contiguous allocation.
✅ It is similar to malloc.
✅ Syntax: (type*)calloc(count, size)
✅ count is the number of elements, and size refers to the size of each element.
✅ If we call the calloc function with m count and n bytes, it allocates m number of n-sized blocks.
✅ Each block is initialized with 0 .

In both malloc and calloc, memory is allocated consecutively in a single location, enabling the creation of dynamic arrays.

Here is a sample code snippet demonstrating the variance in memory allocations between malloc and calloc:

Example


#include<stdio.h>
#include<stdlib.h>
void main()
{
	int *ptr1, *ptr2, n1, n2, i;
	printf("Enter the number of elements in the first D-array: ");
	scanf("%d", &n1);
	printf("Enter the number of elements in the second D-array: ");
	scanf("%d", &n2);
	//initialization
	ptr1 = (int*)malloc(sizeof(int)*n1);
	ptr2 = (int*)calloc(n2, sizeof(int));
	//Initial values
	printf("\nInitial values: ");
	printf("\nBy malloc(): ");
	for(i=0;i<n1;i++)
	{
		printf("%d ", *(ptr1 + i));
	}
	printf("\nBy calloc(): ");
	for(i=0;i<n1;i++)
	{
		printf("%d ", *(ptr2 + i));
	}
	//Allocated addresses
	printf("\n\nMemory allocations: ");
	printf("\nBy malloc(): ");
	for(i=0;i<n1;i++)
	{
		printf("%d ", ptr1 + i);
	}
	printf("\nBy calloc(): ");
	for(i=0;i<n1;i++)
	{
		printf("%d ", ptr2 + i);
	}
}

Output:

Output


Enter the number of elements in the first D-array: 5
Enter the number of elements in the second D-array: 5

Initial values:
By malloc(): 11901584 0 11862352 0 1936028257
By calloc(): 0 0 0 0 0

Memory allocations:
By malloc(): 11867904 11867908 11867912 11867916 11867920
By calloc(): 11867936 11867940 11867944 11867948 11867952

free:

✅ It is used to explicitly de-allocate the memory of dynamic memory allocations. For regular variables, memory is released automatically at runtime. We need to use free in the case of DMA for all the reserved memory to be released.
✅ Syntax: free(ptr)
✅ ptr refers to the pointer previously allocated using malloc or calloc.

realloc:

✅ realloc stands for reallocation.
✅ It is used to dynamically re-allocate the allocated dynamic memory.
✅ Suppose we use malloc or calloc and reserve some memory, which is insufficient; we can reserve more memory using realloc.
✅ Syntax: realloc(ptr, newsize)
✅ ptr refers to the pointer previously allocated using malloc or calloc.

If we initialize a standard array of size n and later determine that the first element is unnecessary during runtime, we can shift all elements to the left by discarding the initial element. This action does not alter the array's size, and the vacant position remains intact.

When dealing with dynamic arrays, realloc can be employed to reduce the size of the array. Below is an illustration showcasing this behavior:

Example


#include<stdio.h>
#include<stdlib.h>
void main()
{
	int *ptr, n, arr[n], i;
	printf("Enter the size: ");
	scanf("%d", &n);
	//Creating a dynamic array
	ptr = (int*)malloc(sizeof(int)*n);
	printf("\nThe memory allocations in a regular array: ");
	for(i = 0; i < n; i++)
	{
		printf("%d ", &arr[i]);
	}
	printf("\nThe memory allocations in the dynamic array: ");
	for(i = 0; i < n; i++)
	{
		printf("%d ", &ptr[i]);
	}
	//Removing the first element
	for(i = 1; i < n; i++)
	{
		arr[i - 1] = arr[i];
		ptr[i - 1] = ptr[i];
	}
	printf("\n\nAfter removing the first element:");
	printf("\nRegular array: ");
	for(i = 0; i < n; i++)
	{
		printf("%d ", &arr[i]);
	}

	printf("\nDynamic array: ");
	//Shrinking the memory of the dynamic array
	int t = n - 1;
	ptr = realloc(ptr, (t)*sizeof(int));
	for(i = 0; i < t; i++)
	{
		printf("%d ", &ptr[i]);
	}
	free(ptr);
}

Output:

Output


Enter the size: 6

The memory allocations in a regular array: 6487264 6487268 6487272 6487276 6487280 6487284
The memory allocations in the dynamic array: 12130048 12130052 12130056 12130060 12130064 12130068

After removing the first element:
Regular array: 6487264 6487268 6487272 6487276 6487280 6487284
Dynamic array: 12130048 12130052 12130056 12130060 12130064
--------------------------------
Process exited after 2.795 seconds with return value 1
Press any key to continue . . .

✅ We can't use sizeof on a dynamic array. It only returns the size of the beginning pointer.
✅ We need to use the free function to explicitly de-allocate the memory.

Conclusion:

This marks the initial guide on Data structures and algorithms in C programming.

In this tutorial, we covered:

✅ Difference between Data type and Data structures
✅ Arrays
✅ Linked lists
✅ Dynamic arrays-DMA in C

Applications containing fundamental functions along with detailed explanations are developed to enhance comprehension. The upcoming lesson will proceed with discussions on stacks and queues.

Data Types and Data Structures:

Terminology:

Facts:

Arrays:

Notable points:

Linked Lists:

Circular Linked List:

Dynamic Arrays:

Conclusion:

Input Required