C Tutorial

C Tutorial C Language Environment Setup Execution flow of C program C printf and Scanf C Data type C Token Variable in C Operators in C Comments in C Escape Sequence in C C – Storage Classes C Decision control statement Loop Statement in C Break, continue and goto statement in C Type Casting in C Function in C Recursion in C String in C C Array Pointer in C Dynamic memory allocation C –Structure Nested Structure in C Union in C File Handling in C C pre-processor Static Function In C Sizeof In C Selection Sort In C Scope Of Variables In C Runtime Vs Compile Time In C Random Access Lseek In C Queue Implementation In C Pseudo Code In C Prototype In C Pointer To Pointer In C Pointer Arithmetic In C Passing Array To Function In C Null Character In C Merge Sort In C Macros In C Library Functions In C Memory Leak In C Int In C Goto And Labels In C Fibonacci Series In C Fflush In C Derived Data Types In C Data Types In C Const Vs Volatile In C Character Set In C Character Class Tests In C Calloc In C C Pointers Arrays In C Include In C Clrscr In C C Vs Java String Literals In C Types Of Pointers In C Variables In C Volatile In C Why C Is A Middle Level Language Infix To Postfix Program In C Ceil function in C LCM of two numbers in C Quick sort in C Static in C function pointer as argument in C Top Array Keywords in C Add two numbers using the function in C Armstrong program in C using function Array, Declaring Arrays and Array Initialization Limitations of Inline Function in C Merge and Merge sort with example in C Do-While Loop in C For Loop in C While-Loop in C Difference between while and do-while loop in C Array Of Structures in C Data Structures And Algorithms in C Types Of Structures In C How to Avoid Structure Padding in C Use of Structure in C Do WHILE LOOP in C Programming Examples For Loop in C Programming Examples Entry Control Loop in C Exit control loop in C Infinite loop in C Nested loop in C pow() function in C String Handling functions in C Prime Number code in C Factorial Program in C using For Loop Factorial Program in C Using While Loop Fibonacci Series in C Using For Loop Fibonacci series in C using while loop Prime Number Program in C using for Loop While Loop in C programming examples Built-in functions in C Assert() Function C vs Java Strings Call Back Function in Embedded C Else If Ladder fgets() function Ftell() Function getc() function getch() function gets() function Heap Sort Nested if-else statement Pi() Function Positioning of file Write() function abs() function in C Attributes in C C program to find factorial of a number using Recursion Ferror() in c fopen() function in C Fibonacci series program in C using Recursion Formatted Input and output function in C Snake Game in C User Defined Functions in C Beep() function in C Cbrt() function in C Hook() function in C Isalnum() function in C C Program to find the Roots of a Quadratic Equation C Switch Statements Difference between rand() and srand() function in C Difference between while and for loop in C Doubly Linked list in C Example of Iteration in C How to use atoi() function in C How to use floor() function in C How to use sine() function in C How to use Typedef Struct in C Integer Promotions in C C Program Swap Numbers in cyclic order Using Call by Reference C Program to Find Largest Number Using Dynamic Memory Allocation C Program to Find the Largest Number using Ternary Operator C/C++ Program to Find the Size of int, float, double and char Find the Largest Three Distinct Elements in an Array using C/C++ Loop Questions in C Modulus on Negative Numbers in C Multiplication table program in C using For loop Nested Loops in C Programming Examples C Program for Mean and Median of an Unsorted Array Results of Comparison Operations in C and C++ Reverse a Stack using Recursion in C Simple hash() function in C strcat() Function in C Sum of N numbers in C using For loop Use of free() function in C Write a program that produces different results in C and C++ C Function Argument and Return Values Keywords in C Bank management system in C Calendar application in C Floor() Function in C Free() Function in C How to delete a file in C How to move a text in C Remove an element from an array in C Unformatted input() and output() function in C What are linker and loader in C fork() in C GCD program in C Branching Statements in C Comma Operator in C Control statement in C Double Specifier in C How to create a binary file in C Long int in C Palindrome Number in C Pure Virtual Function in C Run Time Polymorphism in C Types of Array in C Types of Function in C What is a buffer in C What is required in each C Program Associativity of Operators in C Bit Stuffing Program in C Actual and Formal Parameters Addition of two Numbers in C Advantages of function in C

Data Structures And Algorithms in C

C language is one of the most flexible and simple languages. So, it is always better to learn any concept in C language compared to other languages. Let us look into the data structures and algorithms in C. Before moving ahead, and we need to know the data structure.

Data structures

Data structures are made up of two words one is data, and the other one is structure. We all know that data is a piece of normal information stored in a device. Data can be in any format, numbers, characters, etc. And structure means arranging the data, so entirely Data Structure means it is an efficient way of arranging data in a system. If we think why Data Structure is necessary, the one good answer is using data structures, we can save a huge amount of memory and CPU utilization. We have two different types of data structures: a linear data structure and the second is a nonlinear data structure.

Data Structures And Algorithms In C

Let's have a look at the linear data structure.

Linear Data Structure

Linear data structure arranges the data sequentially in a specific order, simply one after another. Here every element has two neighbors. One is the left neighbor, and another one is the right neighbor. Some good examples of linear data structures are a linked list stack and queue. Linear data structures are widely used in software development.

Nonlinear Data Structure

In the nonlinear data structure, all the elements are attached hierarchically. For Example, in trees and graphs and nonlinear data structures, there are multiple levels compared to Linear data structures, and nonlinear data structures use the memory very efficiently. Nonlinear data structures are highly used in artificial intelligence and also best fit for the image processing. We can have a clear idea of all the data structures before that let us know the algorithms' basics.

Algorithm

An algorithm is a step-by-step process of solving a particular problem or finishing a particular task. A very big advantage of an algorithm is any nontechnical people can also understand an algorithm. There is a possibility of having many algorithms for the same problem.

Now let's step into the very basic Linear Data Structure named array.

Array

The Array is a collection of elements of similar data types, and it continuously allocates memory in an array we can access randomly. We may get doubt how we can access elements randomly. An array allows us to access elements just with the help of their addresses. Now let us understand the array concept practically. Major applications are to store information in a linear fashion. It works efficiently in applications where frequent searching takes place.

Data Structures And Algorithms In C

Let us start by understanding using the one-dimensional array.

One-Dimensional Array

The 1D array looks like a simple row here, and elements are stored one after another.

Declaration

Declaring an array is similar to declaring a variable in C language simply. We need to specify the data type, then the array name, and next, you need to tell the maximum size.

Check the below Syntax to get an idea:

int array_name[4];

Array Initialization

 We have two ways of initializing one is compile-time initialization, and the second one is run-time initialization. Initially, all the elements in an array will be assigned with some garbage values, so we need to initialize them to store them explicitly.

Data Structures And Algorithms In C

Compile-Time-Initialization

In compile-time initialization, we initialize the value within the code itself, so the memory will be allocated in the compile time.

Example program in C language

#include<stdio.h>
int main()
{
int numbers[2]={9,99};
printf(" We are initializing variables in compile time\n");
printf("%d \n",numbers[0]);
printf("%d \n",numbers[1]);
}

Output:

Data Structures And Algorithms In C

Run time Initialization

 This is also called dynamic initialization. Here elements are initialized at the run-time, and after successfully compiling the program, the memory is allocated in the run-time. We use the scanner function to initialize values in the run-time successfully. Check the below Example for a better understanding of Array Accessing. In a one-dimensional array, elements are accessed by specifying the exact array name and index value. Please make a note that our index always starts with Value 0. We can access it like this.

Example program in C language

#include<stdio.h>
int main()
{
int numbers[4];
printf("We are initializing in run time\n");
printf("Enter elements one by one\n");
for(int i=0;i<4;i++)
{
scanf("%d",&numbers[i]);
}
printf("The array elements are \n");
for(int i=0;i<4;i++)
{
printf("%d\n",numbers[i]);
}
return 0;
}

Output:

Data Structures And Algorithms In C

We have specific rules for declaring a one-dimensional array. They are as follows.

1. Before accessing, we need to declare the variable.

2. An array index always starts with zero and ends it size -1.

3. It is necessary to include data type and variable name while declaring an array.

Two-Dimensional Array

A two-dimensional array looks like a matrix in maths with columns and rows. It is also called an array of arrays.

Declaration

Similar to a one-dimensional array, we can declare the two-dimensional array as:

datatype arrayname[row-size][column-size]

Example:

int twodarray[4][4];

Initializing

The basic and first way of initializing is directly giving values when declaring themselves.

int twodarray[2][2] = {{1,2}, {1,2}};

Accessing

We can access elements by giving their correct location as rows and columns. Simply enter arrayname[row][column]

C program to initialize elements in runtime for two-dimensional array.

#include<stdio.h>
int main(){
int twodarray[2][2];
int i,j;
for(i=0;i<2;i++){
for(j=0;j<2;j++)
{
printf("Enter value for twodarray[%d][%d]\t",i,j);
scanf("%d",&twodarray[i][j]);
}
}
printf("The elements of Two Dimensional Array are\n");
for(i=0;i<2;i++)
{
for(j=0;j<2;j++)
{
printf("%d \n",twodarray[i][j]);
}
}
return 0;
}

Output

Data Structures And Algorithms In C

In this program, we took a two-dimensional array named twodarray and assigned maximum row size and column size. Then we started taking values from the user and then displayed them in order.

Multi-Dimensional Array

The two-dimensional array also comes under the multi-dimensional array.

The structure will be like this

datatype arrayname[size 1][size 2][size 3].....[size n]

Linked List

It is a Linear Data Structure, and here elements can be stored as per the memory availability. Generally, if we have 4 bytes of memory in the array, we can store 4 bytes at maximum. And sometimes, there is a case where we declare an array of size 20 bytes and use only 4 bytes means the other 16 bytes of memory are going to be wasted. In a linked list, we can save a lot of memory by using junks of memory in our system, which is ignored in the array case. We can access elements only in a linear fashion means we cannot randomly access them we need to travel in a linear model. Similar to arrays, the linked lists also store similar data type elements. Linked List is dynamic in size means there is no need to specify the maximum size. We can increase the size dynamically. Insertion and deletion are easy on Linked List. The starting element of the Linked List is called a head.

Applications

1. This is best suitable for systems where memory is limited

2. Very suitable for software programs where frequent insertion and deletion occur.

3. Works well where time complexity is important while inserting and deleting.

Types of Linked List

1. Singly Linked List

2. Doubly Linked List

3. Circular Linked List

Singly Linked List

Here we have a head that points to the first element of the Linked List to make it clear head is a pointer that always points to the first element. The most important thing is we never manipulate. If we manipulate, then we will get undesired results. Every block is called a node, and it contains two parts: Data and the second one is a link. The link part links to the next element. You will get a good better idea after watching the below image.

Data Structures And Algorithms In C

Doubly Linked List

In the Doubly Linked List, we have two pointers, the previous node address, and the next node address, and here also head will point to the first node whose previous address is NULL as there are no previous elements to it. From next, every node will have both the previous and next link address, and finally, the last node won't have any next link address.

Data Structures And Algorithms In C

The structure of a double-Linked List will be like this.

Uses

1. Used in navigation systems that require forward and backward navigation.

 2. The browser implements navigation before and after the web page, you visit. You can use it both as a back button and a forward button.

 3. It is also used to represent the classic deck of cards.

 4. Also used in various applications to implement undo and redo functionality.

Disadvantages

1. It uses additional memory compared to arrays and single-linked lists.

2. Therefore, the elements are randomly stored in memory, so the elements are accessed in sequence, and direct access is not allowed.

Circular Linked List

A circular linked list is a variant of a linked list where the first element points to the last element and the last element points to the first element.

Data Structures And Algorithms In C

See the below diagram to understand it in a good way.

You can convert both single and double-linked lists to circular linked lists.

Advantages

1. Helps implement queues.

 2. Each node can be the starting point.

 3. Circular lists help your application repeat the List repeatedly.

 4. Circular double-linked lists implement advanced data structures like the Fibonacci heap.

In a circular linked list, the first node's previous pointer and the last node's next pointer will not be null, so it efficiently links and uses pointer space.

Now let us move to the programming part step by step in C.

Declaration and Initialization

Here initially, we need to learn how to declare the node. As we know, that node has two parts, one is the head, and the other is the next, which is a pointer, so we use structure here in the example, we used the structure of the name "node."

Basic code for creation of node in C

struct node
{
int data;
struct node * next;
}*tmp;
tmp=(struct node*)malloc(sizeof(struct node));
tmp->data=1;
tmp->next=NULL

With variables, one is data of int data type and the next pointer, which is a self-referencing structure variable. To allocate memory, we are using the malloc method. Once we allocate memory to tmp by declaring the size of operator "struct node " and then type casting into type node, we get some address that will be stored in tmp.

Till here, we will be getting this

Check this picture to get a better idea.

Data Structures And Algorithms In C

Let us think the address is 1000, allocated using the malloc function and stored in temp variables. In the next line, we said "tmp->data=1" which means the data is going to be one till here, and then "tmp->next=NULL" which means the NULL value is going to be stored in the next part of the node.

Next, we defined a tmp through which we can access data members of the structure. If we think about why it is a self-referencing variable, the pointer points to the next element, also a type node.

Head is a variable that needs to store the value of the first node address. The first node stores the second node's address, and so on. Finally, when we are at the end of the List, it stores the NULL value.

Implementation of insertion of an element in Linked List at beginning

We have a function named insertbeg, and now we are passing the argument, which is the element value to be inserted into Linked List.

CODE

Example program in C language

void insertbeg()
{
tmp=(struct node*)malloc(sizeof(structnode));
tmp->data=ele;
if(p==NULL)
{
tmp->next=NULL;
}
else
{
tmp->next=p;
}
p=tmp;


Note that the root node that is the first node is created in the main function itself means it is created globally, so there is no need to declare all other functions in the program. There will be two cases. The first case is the entire Linked List is empty. At this time, the root is null means p=null as we said, "tmp->next=p" for the second case where at least two elements exist. In the Linked List for both cases, we need to have the address of the first node, so we create a new node named "p". This will act as the head node. First, we allocate memory to tmp and initialize the data part with the element. And then, by using the if-else block, we are checking whether Linked List is empty or not in the empty case "tmp->next=NULL" in the else case, the tmp node, which is the new node, will get its next pointer value as p that is first element value and finally, we are updating the p address value to the current temp value.

Implementation of Inserting At END

Generally, we cannot manipulate the head value. To link at the end, the last node should point to null, and this won't change even if many nodes get added. Here in the code, we initially assigned p to the temp value to store our data, and we know that p points to the first element. Here also, we have two cases: Linked List is empty, and the second one is at least two nodes exist on Linked List. Here we declared a function named insertend().

Example program in C language

void insertend(int ele)
{
tmp=p;
tmp1=(struct node*)malloc(sizeof(struct node));
tmp1->data=ele;
tmp1->next=NULL;
if(p==NULL)
p=tmp1;
else
{
while(tmp->next!=NULL)
      tmp=tmp->next;
tmp->next=tmp1;
}
}


Here in the code, we are giving the next address in the temp variable as null as the last element address should always be null. Now we start checking the condition if Linked List is empty, then the p stores tmp1 address that is "NULL”.

In the else condition, we need to start the loop as we need to traverse around the linked List, so we used while (condition), and after that, the tmp value traverses’ step by step ahead "temp=temp->next;" and after loop, the temp value address gets updated to tmp1, so we are making the next element address is null.

C program to do Insertion at end and beginning in Single Linked List:

#include <stdio.h>
struct node
{
int data;
struct node *link;
}*head=NULL,*temp;;
int main()
{
void insertbeg(int);
void insetend(int);
void display();
struct node *temp;
int x,ch;
do{
printf("\n1.insert at beg ");
printf("2.insert at end ");
printf("3.display ");
printf("4.exit \n");
printf("enter ur choice: ");
scanf("%d",&ch);
switch(ch)
{
case 1:printf("enter the element to insert ");
scanf("%d",&x);
insertbeg(x);
break;
case 2:printf("enter the element to insert ");
scanf("%d",&x);
insertend(x);
break;
case 3:display();
break;
case 4:exit(0);
break;
default: printf("You entered other character make sure to enter number in between 1 to 4 ");
break;
}
}while(ch!=6);
}
void create(int x)
{
// struct node *temp;
temp=(struct node *)malloc(sizeof(struct node));
temp->data=x;
temp->link=NULL;
}
void insertbeg(int x)
{
//struct node *temp;
create(x);
if(head==NULL)
head=temp;
else
{
temp->link=head;
head=temp;
}
printf("element inserted at the beg is %d \n",head->data);
}
void insertend(int x)
{
struct node *ptr;
create(x);
if(head==NULL)
head=temp;
else
{
ptr=head;
while(ptr->link!=NULL)
ptr=ptr->link;
ptr->link=temp;
}
printf("element inserted at end is %d \n",x);
}


void display()
{
struct node *ptr;
if(head==NULL)
printf("list is empty \n");
else
{
printf("the elements are ");
for(ptr=head;ptr!=NULL;ptr=ptr->link)
printf("%d ",ptr->data);
}
}




Output:

Data Structures And Algorithms In C

CODE EXPLAINATION

Here we created a node Initially, and then by using a do-while loop, we are showing MENU where the user can select an option 1 for insertion at the beginning, 2 for insertion at the ending, 3 for display, and finally, 4 for exiting from the loop. According to the selection, the functions get executed. We used "next" in the above implementation and "link" in this program.

Stack

Stack follows the Last In First Out(LIFO) principle. It means the last element entered will be removed first. A stack of books is a good real-time example where we remove the last book inserted first.

Queue

Queue follows the First In First Out FIFO. The queue is open at both ends. Here we insert an element at the rear end, and deletion is done at the tail end. A simple Queue at the ticket counter is an example of a "Queue."

Tree

Data Structures And Algorithms In C

The tree is a simple data structure with levels and elements stored in nodes. Non-linear data structures such as trees are popular. The tree represents a hierarchical structure unlike other data structures such as an array, stack, queue, and linked list, which are linear. It is not important to know the order of trees. A tree contains nodes and two pointers. The two pointers represent the left and right children of the parent node, respectively. It is helpful to understand the terms of a tree in more detail.

Searching

Data Structures And Algorithms In C

1. Linear Search:

It helps us search elements in linear data structure example array.

Linear Search checks all the elements one after another. It is a simple straight brute-forced algorithm.

Linear Search Algorithm

linearSearch(arr,item)
for each element in the array
if item==element
return its index
return -1.

This algorithm uses the "for each" loop to search for the key elements in the given array. Inside the loop, we iterate through each element and check whether it matches the key and if the matched algorithm returns the index. There is a scenario where the element won't exist in the array. In that case, our algorithm returns "-1."

2. Binary Search

This algorithm can only be used for the sorted array. The Binary Search technique follows the divide and conquers methodology. Binary Search is more efficient than Linear Search.

Binary Search-Iterative Algorithm

binarySearch(arr,size)
loop until beg is not qual to end 
midindex=(beg+end)/2
if(item==arr[midindex])
return midindex
else if(item>arr[midindex])
beg=midindex+1
else
end=midindex-1

We iterate until the beginning is less than the ending. Have a look at the below image to get an idea.

To iterate, the begging should always be less than the end. We create a new middle index, the beginning and ending index average. With the help of conditional statements, we check first whether the item matches the central index element. If so, we return the mid index, the element we are searching for. Next, we check whether an item is greater than the central element.



ADVERTISEMENT
ADVERTISEMENT