Data Structure And Algorithms Using C Language Tutorial For Beginners
All PostsC_languageData Structure And AlgorithmsProgramming

Data Structure And Algorithms Using C Language Tutorial For Beginners

Posted on by Chetan Shidling

Hello guys, welcome back to my blog. In this article, I will discuss each and every aspect of the data structure and algorithms using c language. I will try to explain everything in a simple way with many examples. Read this article till the end if you want to become a master in the data structure.

Ask questions if you have any electrical,  electronics, or computer science doubts. You can also catch me on Instagram – CS Electrical & Electronics

Also, read:

  1. Top 10 In-Demand Programming Languages To Learn In 2021.
  2. Exception Handling | Try, Throw, Catch Keyword, Syntax, Code

Nowadays, the data structure and algorithms using c language are very important for students who are willing to get a job in IT companies. Well, don’t worry guys you will get a good job in an IT company and you will become perfect in the data structure and algorithms using c language by reading this article completely.

Data Structure And Algorithms Using C Language

Topics which I cover in this article are:

  1. Arrays
  2. Functions
  3. Pointers
  4. Memory Allocation
  5. Files
  6. Strings
  7. Structures and Unions
  8. Stacks
  9. Searching
  10. Sorting
  11. Queues
  12. Linked List
  13. Trees
  14. Graph’s

Let’s begin.

What is a data structure?

Remember one thing data structure and algorithms using c language is not a language, a data structure is a concept set of algorithms used to structure the data, it is not a programming language such as like C, C++, Java, so there are just a set of algorithms, we are executing these algorithms using any programming language.

The data structure means it is the collection of some data or elements and all possible operations which are required for those set of elements. For example: consider an array, where the set of elements is required to store in an array. Various operations such as inserting and deleting can be performed.

The need for a data structure’s

The computers are electronic data processing machines. In order to solve a particular problem we need to know: How to represent data in a computer, how to access them, and what are steps to be performed to get the needed output. These tasks can be achieved with the knowledge of data structures and algorithms.

01. Arrays

An array is a group of similar data items. The elements of an array are of the identical type and each element can be accessed using the same name, but with different index values. The elements of the array are collected in consecutive memory places and are referenced by an index (also recognized as the subscript). A subscript is an ordinal number which is used to recognize an element of the array.

Example: Array for character

char name[25];
strcpy(name,"Chetan");

array
| C | h | e | t | a | n |………….|
Total memory occupied is 1 byte * 25 = 25 byte.

We have previously seen that all variable must be declared before it is used. The same idea is true for array variables. An array need be declared before being used. Declaring an array means defining the following:

  1. Data type—the kind of values it can store, for example, int, char, float, double.
  2. Name—to identify the array.
  3. Size—the maximum number of values that the array can hold.

Arrays are declared using the following syntax:

type name[size];

The type can be int, float, double, char, or any other valid data type. The number in brackets shows the size of the array, i.e., the maximum number of elements that can be collected in the array. For example, if we write, int marks[10]; then the statement declares marks to be an array holding 10 elements. In C, the array index begins from zero. The first element will be saved in marks[0], the second element in marks[1], and so on. Therefore, the last element, which is the 10th element, will be saved in marks[9].

Operations Performed In Array

  1. Traversing an array
  2. Inserting an element in an array
  3. Searching an element in an array
  4. Deleting an element from an array
  5. Merging two arrays
  6. Sorting an array in ascending or descending sequence

a. Traversing an Array

Traversing an array means accessing each and all elements of the array for a particular purpose. Traversing the data elements of an array can include print every element, calculating the total number of elements, or conducting any process on these elements.

Program to read and display numbers:

#include <stdio.h>
int main()
{
int i, n, arr[20];
clrscr();
printf("\n Enter the number of elements to store in the array : ");
scanf("%d", &n);
for(i=0;i<n;i++)
{
printf("\n arr[%d] = ", i);
scanf("%d",&arr[i]);
}
printf("\n The array elements are ");
for(i=0;i<n;i++)
printf("\t %d", arr[i]);
return 0;
}

Output:

Enter the number of elements in the array : 5
arr[0] = 1
arr[1] = 2
arr[2] = 3
arr[3] = 4
arr[4] = 5
The array elements are 1 2 3 4 5

b. Inserting an element in an array

If an element has to be inserted at the end of an existing array, then the task of insertion is quite simple. We just have to add 1 to the upper_bound and assign the value. Algorithm to insert an element in the middle of an array.

Step 1: [INITIALIZATION] SETI=N
Step 2: Repeat Steps 3 and 4 whileI>= POS
Step 3: SET A[I + 1] = A[I]
Step 4: SETI=I–1
[END OF LOOP]
Step 5: SETN=N+1
Step 6: SET A[POS] = VAL
Step 7: EXIT

Program to insert element in between of the array

#include <conio.h>
int main()
{
int i, n, num, pos, arr[10];
clrscr();
printf("\n Enter the number of elements in the array : ");
scanf("%d", &n);
for(i=0;i<n;i++)
{
printf("\n arr[%d] = ", i);
scanf("%d", &arr[i]);
}
printf("\n Enter the number to be inserted : ");
scanf("%d", &num);
printf("\n Enter the position at which the number has to be added :");
scanf("%d", &pos);
for(i=n–1;i>=pos;i––)
arr[i+1] = arr[i];
arr[pos] = num;
n = n+1;
printf("\n The array after insertion of %d is : ", num);
for(i=0;i<n;i++)
printf("\n arr[%d] = %d", i, arr[i]);
getch();
return 0;
}

Output:

Enter the number of elements in the array : 5
arr[0] = 1
arr[1] = 2
arr[2] = 3
arr[3] = 4
arr[4] = 5
Enter the number to be inserted : 0
Enter the position at which the number has to be added : 3
The array after insertion of 0 is :
arr[0] = 1
arr[1] = 2
arr[2] = 3
arr[3] = 0
arr[4] = 4
arr[5] = 5

c. Deleting an element from an array

Deleting an element from an array means removing a data element from an already existing array.

#include <stdio.h>
#include <conio.h>
int main()
{
int i, n, pos, arr[10];
clrscr();
printf("\n Enter the number of elements in the array : ");
scanf("%d", &n);
for(i=0;i<n;i++)
{
printf("\n arr[%d] = ", i);
scanf("%d", &arr[i]);
}
printf("\nEnter the position from which the number has to be deleted : ");
scanf("%d", &pos);
for(i=pos; i<n–1;i++)
arr[i] = arr[i+1];
n––;
printf("\n The array after deletion is : ");
for(i=0;i<n;i++)
printf("\n arr[%d] = %d", i, arr[i]);
getch();
return 0;
}

Output:

Enter the number of elements in the array : 5
arr[0] = 1
arr[1] = 2
arr[2] = 3
arr[3] = 4
arr[4] = 5
Enter the position from which the number has to be deleted : 3
The array after deletion is :
arr[0] = 1
arr[1] = 2
arr[2] = 3
arr[3] = 5

d. Merging two arrays

Merging two arrays in a third array means first copying the elements of the first array into the third array and then copying the elements of the second array in the third array. Therefore, the merged array contains the elements of the first array followed by the elements of the second array.

#include <stdio.h>
#include <conio.h>
int main()
{
int arr1[10], arr2[10], arr3[20];
int i, n1, n2, m, index=0;
clrscr();
printf("\n Enter the number of elements in array1 : ");
scanf("%d", &n1);
printf("\n\n Enter the elements of the first array");
for(i=0;i<n1;i++)
{
printf("\n arr1[%d] = ", i);
scanf("%d", &arr1[i]);
}
printf("\n Enter the number of elements in array2 : ");
scanf("%d", &n2);
printf("\n\n Enter the elements of the second array");
for(i=0;i<n2;i++)
{
printf("\n arr2[%d] = ", i);
scanf("%d", &arr2[i]);
}
m = n1+n2;
for(i=0;i<n1;i++)
{
arr3[index] = arr1[i];
index++;
}
for(i=0;i<n2;i++)
{
arr3[index] = arr2[i];
index++;
}
printf("\n\n The merged array is");
for(i=0;i<m;i++)
printf("\n arr[%d] = %d", i, arr3[i]);
getch();
return 0;
}

Output:

Enter the number of elements in array1 : 3
Enter the elements of the first array
arr1[0] = 1
arr1[1] = 2
arr1[2] = 3
Enter the number of elements in array2 : 3
Enter the elements of the second array
arr2[0] = 4
arr2[1] = 5
arr2[2] = 6
The merged array is
arr[0] = 1
arr[1] = 2
arr[2] = 3
arr[3] = 4
arr[4] = 5
arr[5] = 6

Types of arrays

01. One dimensional array    ex: int a[10]

02. Two-dimensional array     ex: int a[10][10]

03. Multi-dimensional array     ex: int a[10][10][10]

02. Functions

The function can be described as a subprogram that includes a combination of statements to do a particular task. The programming method in which the given big and complex problem will be split into many subprograms to do a particular task and are called by main() is called Modular Programming Approach.

The functions can be classified into two categories:

01. Library functions

02. User-defined functions

01. Library functions – They are built-in functions that perform a predefined task.
Example: pow(x,y), sqrt(x), printf(), scanf().

02. User-defined functions – A function written by the programmer to do a specific task is called User-defined function. The advantage of user-defined function is the program maintenance, testing, and debugging will become easier.
Example: main()

#include<stdio.h>
void addition(int x, int y);  #function declaration
void main()
{
   int n1, n2;
   printf("Enter 2 no\n");
   scanf("%d %d",&n1, &n2);
   addition(n1, n2);   #function call
   getch();
}

void addition(int x, int y)     #function definition
{
    int sum;
    sum= x+y;
    printf("sum = %d\n",sum);
}

Output:

Enter 2 no
4
3

sum = 7

Elements of User-defined functions

01. Function declaration or prototype

02. Function call

03. Function definition

01. Function declaration – The function must be declared in the global declaration part of C program, i.e., before main().
Syntax of the function declaration

return_type function_name(arguments_list);

where,

return_type – The function return type like int, double, float, char, etc.function_name – valid identifierarguments_list – No of parameters

example: float area(float x)
float is return_type, the area is function_name, float x is argument_list.

02. Function call – The user-defined function is called by the main() by simply using function name followed by a list of actual parameters/arguments enclosed in parentheses.

Example:

void main()
{
   -----
   addition(n1,n2)   #function call
   -----
}

03. Function Definition – This is the subprogram, which can be written before or after main(). It consists of a body of a function.

Syntax of a function definition

return_type function_name(arguments_list)
{
    local variable declaration;
    Statement 1;
    Statement n;
    return statement;
}

C program of addition using functions

#include<stdio.h>
void addition(int x, int y);  #function declaration
void main()
{
   int n1, n2;
   printf("Enter 2 no\n");
   scanf("%d %d",&n1, &n2);
   addition(n1, n2);   #function call
   getch();
}

void addition(int x, int y)     #function definition
{
    int sum;
    sum= x+y;
    printf("sum = %d\n",sum);
}

Output:

Enter 2 no
4
3

sum = 7

C program of movie details using functions

#include<stdio.h>
#include<stdlib.h>
struct movie
{

 char name[15];
 char producer[15]; 
 char director[15];
 int year;
 char phouse[15];
 
};
typedef struct movie D;
D read(D m);
void display(D m);
void sort(D m[], int n);
void sreach(D m[], int n);

int main()

{
 int n,i;
 printf("Enter the number of movies\n");
 scanf("%d",&n);
 D m[n],temp;
 for(i=0;i<n;i++)
  m[i]=read(m[i]);
 printf("movie details");
 printf("\n MOVIE\t PRODUCER\t DIRECTOR\t YEAR\t HOUSE\t");
 for(i=0;i<n;i++)
  display(m[i]);
 sort(m,n);
 sreach(m,n);
 return 0;
}


D read(D m)

 {
  printf("Enter the name of movie : ");
  scanf("%s", m.name);
  printf("Enter the name of producer : ");
  scanf("%s", m.producer);
  printf("Enter the name of director : ");
  scanf("%s", m.director);
  printf("Enter the year : ");
  scanf("%d",&m.year);
  printf("Enter the Pro House : ");
  scanf("%s", m.phouse);
  return m;    
 }



void display(D m)
{
printf("\n %s\t %s\t %s\t %d\t %s\t",m.name,m.producer,m.director,m.year,m.phouse);
}

void sort(D m[20], int n)
{
D temp;
int i,j;
for(i=0;i<n;i++)
{
 for(j=0;j<n-1;j++)
 {
 if(m[j].year<m[j+1].year)
   {
    temp=m[j];
    m[j]=m[j+1];
    m[j+1]=temp;
   }
 }    

printf("\n Movie details after sorting");
printf("\n MOVIE\t PRODUCER\t DIRECTOR\t YEAR\t HOUSE\t");
 for(i=0;i<n;i++)
  display(m[i]);
}
}

void sreach(D m[20], int n)
{
char di[20];
int i;
printf("Enter the director name to sreach");
scanf("%s",di);
printf("movie details of director %s\n", di);
printf("\n MOVIE\t PRODUCER\t DIRECTOR\t YEAR\t HOUSE\n");
for(i=0;i<n;i++)
{
 if(strcmp(m[i].director,di)==0)
 display(m[i]);

}
}

Output:

Enter the number of movies
2

Enter the name of the movie: Boss
Enter the name of producer: Chetan
Enter the name of director: Akshay
Enter the year: 1999
Enter the Pro House: CS

Enter the name of the movie: Khiladi
Enter the name of producer: Shidling
Enter the name of director: Kumar
Enter the year: 2000
Enter the Pro House: SE

movie details

 MOVIE     PRODUCER     DIRECTOR     YEAR     HOUSE 
 Boss       Chetan       Akshay      1999      CS 
 Khiladi   Shidling      Kumar       2000      SE 

 Movie details after sorting

 MOVIE  PRODUCER  DIRECTOR  YEAR  HOUSE 

 Khiladi  Shidling          Kumar          2000  SE   
 Boss     Chetan            Akshay         1999  CS 

Enter the directer name to search: Kumar

movie details of director Kumar

MOVIE  PRODUCER  DIRECTOR  YEAR  HOUSE

Khiladi  Shidling  Kumar   2000   SE

03. Pointers

 A pointer is a variable that holds the address of a different or another variable. The pointers are listed in the declaration part of the main() using * operator.

Syntax of the pointers

data_type *ptr_variable;

where,

data_types are int, float, double, char.* – deference operatorptr_variable – valid identifier

Example:

int n=7;    #integer variable

int *ptr;   #integer pointer

int = &n;    #address of n will be stored in ptr

C Program to print the address and contents using pointers

#include<stdio.h>
int main()
{
int j=7;
int *ptr;
*ptr = &j;

#Using pointers

printf("Address of j = %d\n",ptr);
printf("Contents of j = %d\n", *ptr);

#Without using pointers

printf("Address of j without using pointer = %d", &n);
printf("Contents of j without using pointer = %d", n);

}

Output:

Address of n = 0x8000
Contents of n = 7

Address of n without using pointer = 0x8000
Contents of n with using pointer = 7

C program to perform addition using pointers and show the address of the memory

#include<stdio.h>

void main()
{
 int i;
 int sum=0;
 int num[5];
 int *pnum,*psum;
 pnum=#
 psum=∑
 
 printf("enter the 5 numbers : \n");
 for(i=0;i<5;i++)
 scanf("%d",pnum+i);
 for(i=0;i<5;i++)
 *psum=(*psum)+ *(pnum+i);
 printf("Number\t Adress\n");
 for(i=0;i<5;i++)
 { 
 printf("%d\t %p\n", pnum[i],&pnum[i]);
 
 }
 printf("the sum is %d\n",*psum);
}

Output:

enter the 5 numbers : 
2
3
4
3
2
Number  Adress
2          0xbfa4fbdc
3          0xbfa4fbe0
4          0xbfa4fbe4
3          0xbfa4fbe8
2          0xbfa4fbec

the sum is 14

04. Memory Allocation

What is dynamic memory allocation?

The process of allocating memory to the variables during the execution of the program or at run time is known as dynamic memory allocation. C language has four library routines that allow this function. Allocation can be done by the following functions.

  1. malloc( ) – Allocates memory and returns a pointer to the first byte of allocated space.
  2. callock( ) – Allocates space for an array of elements, initializes them to zero and returns a pointer to the memory
  3. reallock( ) – Frees previously allocated memory.
  4. free( ) – Alters the size of previously allocated memory.

05. Files

If you want to work with any file, you need to create file pointer.

Syntax: FILE*<identify> ;

Example:

FILE* ptr;

ptr: The variable which points to any type of file and it holds the address of the file.

Now let’s see how to open the file? To open a file we have one function i.e fopen( ) = This function is used to open a file in different modes like reading mode, write mode, append mode, etc in various modes you can open your file. The prototype of fopen( ) function is, FILE* fopen(“path”, “mode”) On success this function opens a file and returns the address of the file. On failure, this returns a null pointer. The return type of fopen( ) function is FILE*. The fopen( ) function takes 2 arguments. One is the path of the file and another one is a mode of the file. Let’s see how to open a file programmatically.

#include<stdio.h>
main()
{
 FILE* fp;
 fp=fopen(“g:/examples/test.txt”, “r");
 if (fp == NULL)
 print(“file is not present\n");
 else
 print(“file is opened\n")
}

So this is about how to open a file programmatically. Now let’s see how to read the information from that opened file. We can read information in integer by integer or character by character or string by string, or different types of data we can read at a time. So let’s see how to read data on a character by character.

int fgetc(FILE* stream)
FILE* fp=fopen(“g:/text.txt", “r");
int ch;
while ((ch=fgetc(fp)!=EOF))
{
 Print(“/c", ch);
}

On success it returns ASCII of character. On failure it returns EOF (-1).

06. Strings

In C, a string is known as a null-terminated character array. That implies that after the last character, a null character (‘\0’) is saved to signify the end of the character array. For instance, if we write char str[] = “HELLO”; when we are declaring an array that has five characters, specifically, H, E, L, L, and O. Aside from these characters, a null character (‘\0′) is saved at the end of the string. So, the internal design of the string becomes HELLO’\0’. To save a string of length 5, we require 5 + 1 places (1 extra for the null character). The title of the character array (or the string) is a pointer to the beginning of the string. The figure explains the string storage. If we had declared str as char str[5] = “HELLO”;

Program to find length of the string

#include <stdio.h>
#include <conio.h>
int main()
{
char str[100], i = 0, length;
clrscr();
printf("\n Enter the word or string : ");
gets(str)
while(str[i] != '\0')
 i++;
length = i;
printf("\n The length of the word or string is : %d", length);
getch()
return 0;
}

Output:

Enter the word or string : HELLO
The length of the word or string is : 5

07. Structures and Unions

Structures

The structure is defined as the collection of data of the same or different data types. All data items grouped are logically related and can be accessed using variables. The keyword used for structure is a struct.

a. struct

struct tag_name
{
      type1 number1;
      type2 number2;
      .................
      type3 numbern;
};

Note: Semi-colon is a must at the end.

Example:

struct student
{
     char name[10];
     int roll_number;
     float marks;
};

The total memory allocated is 10 bytes + 4 bytes + 8 bytes = 22 bytes.

To allocate the memory for the structure, we have to declare the variable as shown below.

struct student chetan;

where,

struct is a keyword.
student is a structure name.
chetan is a structure variable.

Once the structure variables are declared, the compiler allocates memory for the structure variables. There are two ways to declare variables.

01. One method

struct student
{
.....
......
....
};
struct student chetan;

02. Another method

struct student
{
......
.....
.....
}chetan;

b. Type-defined Structure

The structure associated with the keyword typedef is called a type-defined structure. This is the most powerful way of defining the structure. There are two methods.

01. One method

Syntax:

typedef struct
{
      type1 member1;
      type2 member2;
}structure name;

Example:

typedef struct
{
      char name[10];
      int roll_no;
      float average;
}student;

02. Another method

Syntax:

struct structure_name
{
      type1 member1;
      type2 member 2;
};

typedef struct structure_name typedef_name; //To allocate the memory for the structure, we have to declare the variable as shown below.//

Example:

struct student
{
        char name[10];
        int roll_no;
        float average;
};
typedef struct student Chetan;

Chetan eee;

c. Structure Initialization – The structure initialization means assigning values to the structure variables.

Method 1:

struct student
{
       char name[10];
       int roll_no;
       float average;
}chetan = {"shidling","135","20"};

Method 2:

struct student
{
        char name[10];
        int roll_no;
        float average;
};
struct student chetan={"Shidling","135","20"};

Accessing structure members

01. We perform structure initialization.
02. To access the members of the structure, we specify the variable followed by the dot operator, then followed by the name of the member.

Example:

printf("%s\n", chetan.name);
printf("%s\n", chetan.roll_no);
printf("%s\n", chetan.average);

03. To read the values from the user during the execution of a program, we use format specifiers and access the members of structures.

Example:

gets(chetan.name);
scanf("%d",& chetan.roll_no);
scanf("%f",& chetan.average);

C program for a date using a structure

#include<stdio.h>
struct Date
{
 int day;
 int month;
 int year;
};

void main()
{
 struct Date d;

 printf("Enter Date in following format(01-07-2019)\n");
 printf("Enter day: ");
 scanf("%d",&d.day);
 printf("Enter Month: ");
 scanf("%d",& d.month);
 printf("Enter year: ");
 scanf("%d",&d.year);
 printf("\n %d - %d - %d\n",d.day,d.month,d.year);
}

Output:

Enter Date in the following format(01-07-2019)
Enter day: 21
Enter Month: 06
Enter year: 1999

21 - 6 - 1999

C program to enter details of students using arrays

#include<stdio.h>
#include<stdlib.h>
struct bio
{

 char name[15];
 int day, month, year;
 char srn[15];
 char sub[7][15];
 int marks[7];
 float sgpa;
 float cgpa;
};
void main()

{
int i=0,j=0,s=0,k;
 printf("Enter the number of students",i);
 scanf("%d",&i);
 struct bio st[i];
 for(j=0;j<i;j++)
 {
  printf("Enter the name of Student");
  scanf("%s", st[j].name);
  printf("Enter the day");
  scanf("%d",& st[j].day);
  printf("Enter the month");
  scanf("%d",& st[j].month);
  printf("Enter the year");
  scanf("%d",& st[j].year);
  printf("Enter the srn");
  scanf("%s", st[j].srn);
  printf("Enter the all subjects");
  for(k=0;k<7;k++)
   scanf("%s",& st[j].sub[k]);
  
  printf("Enter the marks of all sub");
  for(k=0;k<7;k++)
   scanf("%d",& st[j].marks[k]);

  printf("Enter the sgpa");
  scanf("%f",& st[j].sgpa);
  printf("Enter the cgpa");
  scanf("%f",& st[j].cgpa);
 }

printf("Name\t DOB\t SRN\t SUB1\t M1\t SUB2\t M2\t SUB3\t M3\t SUB4\t M4\t SUB5\t M5\t SUB6\t M6\t SUB7\t M7\t MARKS\t SGPA\t CGPA");

 for(j=0;j<i;j++)
 {
printf("%s\t %d-%d-%d\t %s\t %s\t %d\t %s\t %d\t %s\t %d\t %s\t %d\t %s\t %d\t %s\t %d\t %s\t %d\t %f\t %d\t", st[j].name, st[j].day, st[j].month, st[j].year, st[j].srn, st[j].sub[0], st[j].marks[0], st[j].sub[1], st[j].marks[1], 
st[j].sub[2], st[j].marks[2], st[j].sub[3], st[j].marks[3], st[j].sub[4], st[j].marks[4], st[j].sub[5], st[j].marks[5], st[j].sub[6], st[j].marks[6], st[j].sgpa, st[j].cgpa);
 }
}

Output:

Enter the number of students: 1
Enter the name of Student: Chetan
Enter the day: 17
Enter the month: 06
Enter the year: 1999
Enter the srn: 01FE18BEE420
Enter all subjects: Maths
Network
Machines
Digital
Power
EPGTDU
Drives

Enter the marks of all sub: 78
87
87
67
98
78
77
Enter the sgpa: 7.8
Enter the cgpa: 8.7

Name  DOB  SRN  SUB1  M1  SUB2  M2  SUB3  M3  SUB4  M4  SUB5  M5  SUB6  M6  SUB7  M7  MARKS  SGPA  CGPA

Chetan  17-6-1999  01FE18BEE420  Maths  78  Network  87  Machines  87  Digital  67  Power  98  EPGTDU  78  Drives  77  7.800000  8.800000

Unions

Related to structures, a union is a set of variables of different data types. The exclusive difference between a structure and a union is that in state of unions, you can only store data in one field at any one time. To completely understand a union, imagine it as a chunk of memory that is used to store variables of different types. When a new value is allocated to a field, the current data is replaced with the new data.

Therefore, unions are used to save memory. They are beneficial for applications that require multiple members, wherever values need not be allotted to all the members at one time.

Declaring a Union

The syntax for representing a union is identical to that of declaring a structure. The only difference is that rather of using the keyword struct, the keyword union would be used. The syntax for union declaration can be presented as:

Syntax

union union–name
{
 data_type variable–name;
 data_type variable–name;
 ..................
};

Repeat the typedef keyword that can be done to simplify the declaration of union variables. The most significant thing to learn about a union is that the size of a union is the size of its highest field. This is because enough number of bytes must be kept to store the largest-sized field.

A member of a union can be obtained using the corresponding syntax as that of a structure. To reach the fields of a union, use the dot operator (.), i.e., the union variable name served by the dot operator followed by the member name.

The difference within a structure and a union are that in case of a union, the fields share the same memory location, therefore new data replaces any current data. See the following code and recognize the difference between a structure and union when their fields are to be initialized.

#include <stdio.h>
typedef struct CASH1
{
int a, b;
};
typedef union CASH2
{
int a;
int b;
};
int main()
{
	 CASH1 CS1 = {4,3};
	 // CASH2 CS2 ={1,5}; Illegal in case of unions
	 CASH2 CS2;
	 CS2.a = 1;
	 CS2.b = 5;
	 printf("\n The coordinates of CS1 are %d and %d", CS1.a, CS1.b);
	 printf("\n The coordinates of CS2 are %d and %d", CS2.a, CS2.b);
	 return 0;
}

The coordinates of P1 are 2 and 3
The coordinates of P2 are 5 and 5

In the code, CASH1 is a structure name and CASH2 is a union name. But, both the declarations are roughly the same (except the keywords—struct and union). In main(), we can recognize the difference between structures and unions while initializing values. The fields of a union cannot be initialized at once.

Output:

#include <stdio.h>
typedef struct CASH1
{
int a, b;
};
typedef union CASH2
{
int a;
int b;
};
int main()
{
	 CASH1 CS1 = {1,7};
	 CASH2 CS2;
	 printf("\n The coordinates of CS1 are %d and %d", CS1.a, CS1.b);
	 CS2. a = 2;
	 printf("\n The a coordinate of CS2 is %d", CS2.a);
	 CS2.b = 3;
	 printf("\n The b coordinate of CS2 is %d", CS2.b);
	 return 0;
}

Output:

See the output nicely. For the structure variable, the output is as required but for the union variable, the result does not appear to be correct. To get the concept of union, execute the next code. The code given here simply re-arranges the printf statements. You will be surprised to see the result.

The coordinates of P1 are 1 and 7
The x coordinate of P2 is 2
The y coordinate of P2 is 3

Here although the output is correct, the data is still overwritten in memory.

Like structures, we can too have an array of union variables. But, because of the problem of new data overwriting existing data in the different fields, the program may not display correct results.

08. Stacks

The stack is an essential data structure that stores its components in an arranged manner. A stack is a linear data structure that uses the principle, i.e., the components in a stack are added and removed only from one end. Therefore, a stack is called a LIFO (Last-In-First-Out) data structure, as the data or element that was inserted last is the first one to be brought out.

The stack is used during function calls, let’s discuss the above image. If W calls X, W is pushed on top of the system stack. When the execution of X is finished, the system control will remove W from the stack and proceed with its execution. If X calls Y, X is pushed on top of the system stack. When the execution of Y is finished, the system control will remove X from the stack and proceed with its execution and so on.

When Z has executed, Y will be removed for execution. When Y has executed, X will be removed for execution. When X has executed, W will be removed for execution.

A stack holds three basic services: push, pop, and peek. The push method adds a component to the top of the stack and the pop process removes the component from the top of the stack. The peek method returns the value of the topmost component of the stack.

Program to perform push, pop and peek operation.

#include <stdio.h>
#include <stdlib.h>
#include <conio.h>
#define MAX 3 // The size of stack created changes by alternating this value.
int st[MAX], top=-1;
void push(int st[], int val);
int pop(int st[]);
int peek(int st[]);
void display(int st[]);
int main(int argc, char *argv[]) {
int val, option;
do
{
printf("\n *****MAIN MENU*****");
printf("\n 1. PUSH");
printf("\n 2. POP");
printf("\n 3. PEEK");
printf("\n 4. DISPLAY");
printf("\n 5. EXIT");
printf("\n Enter your option: ");
scanf("%d", &option);
switch(option)
{
case 1:
    printf("\n Enter the number to be pushed on stack: ");
    scanf("%d", &val);
    push(st, val);
    break;
case 2:
    val = pop(st);
    if(val != -1)
    printf("\n The value deleted from stack is: %d", val);
    break;
case 3:
    val = peek(st);
    if(val != -1)
    printf("\n The value stored at top of stack is: %d", val);
    break;
case 4:
    display(st);
    break;
 }
}while(option != 5);
return 0;
}
void push(int st[], int val)
{
    if(top == MAX-1)
    {
    printf("\n STACK OVERFLOW");
    }
    else
    {
    top++;
    st[top] = val;
    }
}
int pop(int st[])
{
    int val;
    if(top == -1)
    {
    printf("\n STACK UNDERFLOW");
    return -1;
    }
    else
    {
    val = st[top];
    top--;
    return val;
    }
}
void display(int st[])
{
    int i;
    if(top == -1)
    printf("\n STACK IS EMPTY");
    else
    {
    for(i=top;i>=0;i--)
    printf("\n %d",st[i]);
    printf("\n"); // Added for formatting purposes
    }
}
int peek(int st[])
{
    if(top == -1)
    {
    printf("\n STACK IS EMPTY");
    return -1;
    }
    else
    return (st[top]);
}

Output:

1. PUSH
2. POP
3. PEEK
4. DISPLAY
5. EXIT
Enter your option : 1
Enter the number to be pushed on stack : 420

09. Searching

Searching means to determine whether a special value is now in an array or not. If the value is now in the array, then searching is assumed to be successful and the searching method gives the place of that value in the array. But, if the content is not being in the array, the searching method displays a relevant message and in this case, searching is assumed to be unsuccessful.

The different methods of searching are:

  1. Linear search
  2. Binary search
  3. Interpolation search
  4. Jump search

01. Linear search

Linear search, too pronounced as sequential search, is a really simple process used for searching an array for an appropriate value. It operates by comparing the value to be searched with each component of the array one by one in a series until a match is found. Linear search is often utilized to search an unordered arrangement of elements.

02. Binary search

A binary search is a searching algorithm that operates efficiently by a sorted list. Binary search breaks the list in two equal halves. When we are searching for a special word meaning in a directory, we initial open the directory from the middle and later decide whether to look for the name in the front part of the directory or in the other part of the directory. Again, we open any pages in the middle and the whole method is repeated until we finally find the right name.

03. Interpolation search

Interpolation search, also recognized as an extrapolation search, is a searching method that obtains a particularized value in a sorted array. The idea of interpolation search is related to how we search for word meaning in a dictionary book by which a work’s entries are ordered. Suppose you are searching word meaning in dictionary example Chetan, you start the search from a word which starts from c in order ways.

04. Jump search

If we have a previously sorted list, then the additional suitable algorithm to search for value is jump search or also called a block search. In the jump search, it is not required to scan all the elements in the list to obtain the desired value. We only check an element and if it is shorter than the desired value, then any of the elements following it are skipped by jumping forward. After going a little forward again, the element is checked.

I will share only linear search program. and remaining methods codes if you want comment below.

#include <stdio.h>
#include <stdlib.h>
#include <conio.h>
#define size 20 // 
int main(int argc, char *argv[]) {
int arr[size], num, i, n, found = 0, pos = -1;
printf("\n Enter the number of elements in the array : ");
scanf("%d", &n);
printf("\n Enter the elements: ");
for(i=0;i<n;i++)
{
scanf("%d", &arr[i]);
}
printf("\n Enter the number that has to be searched : ");
scanf("%d", &num);
for(i=0;i<n;i++)
{
if(arr[i] == num)
{
found =1;
pos=i;
printf("\n %d is found in the array at position= %d", num,i+1);
/* +1 added in line 23 so that it would display the number in
 the first place in the array as in position 1 instead of 0 */
break;
 }
}
if (found == 0)
printf("\n %d does not exist in the array", num);
return 0;
}

10. Sorting

Sorting involves managing the elements of an array so that all are placed in some proper order which may be both ascending or descending. A sorting algorithm is specified as an algorithm that sets the elements of a list in a particular order, which can occur either numerical order, lexicographical order, or a user-defined order.

There are two kinds of sorting:

  1. Internal sorting means sorting the data collected in the computer’s memory
  2. External sorting means sorting the data collected in files. External sorting is used when there is abundant data that cannot be stored in the memory.

The various algorithms used for sorting are:

  1. Bubble sort
  2. Insertion sort
  3. Selection sort
  4. Merge sort
  5. Quick sort
  6. Radix sort
  7. Heap sort
  8. Shell sort
  9. Tree sort

Program on sorting

#include <stdio.h>
#include <conio.h>
int main()
{
int i, n, temp, j, arr[10];
clrscr();
printf("\n Enter the number of component in the array : ");
scanf("%d", &n);
printf("\n Enter the elements: ");
for(i=0;i<n;i++)
{
scanf("%d", &arr [i]);
}
for(i=0;i<n;i++)
{
for(j=0;j<n–i–1;j++)
 {
if(arr[j] > arr[j+1])
 {
temp = arr[j];
arr[j] = arr[j+1];
arr[j+1] = temp;
}
}
}
printf("\n The sorted in ascending order is :\n");
for(i=0;i<n;i++)
printf("%d\t", arr[i]);
getch();
return 0;
}

Output:

Enter the number of elements in the array : 10
Enter the elements : 8  9  6  7  5  4  2  3  1  10
The sorted in ascending order is :
1 2  3  4  5  6  7  8  9  10

11. Queues

Queues can be simply realized using linear arrays, the queue has front and rear variables that point to the location of where deletions and insertions can be made, sequentially.

Assume we require to add another element by value 5, then REAR would be incremented by 1 and that value would be saved at the position pointed by REAR. The queue after addition would be as shown in block 02. Here, FRONT = 0 and REAR = 8. Each time a different element has to be added, we replicate the same procedure. If we need to delete a component from the queue, later the value of FRONT will be incremented. Deletions are made from just this end of the queue. The queue after deletion will be as shown in block 03.

Program for linear queue

##include <stdio.h>
#include <conio.h>
#define MAX 10 // Changing this number will change length of array
int queue[MAX];
int front = -1, rear = -1;
void insert(void);
int delete_element(void);
int peek(void);
void display(void);
int main()
{
int option, val;
do
{
printf(“\n\n ***** MAIN MENU *****”);
printf(“\n 1. Insert an element”);
printf(“\n 2. Delete an element”);
printf(“\n 3. Peek”);
printf(“\n 4. Display the queue”);
printf(“\n 5. EXIT”);
printf(“\n Enter your option : “);
scanf(“%d”, &option);
switch(option)
 {
case 1:
 insert();
break;
case 2:
val = delete_element();
if (val != -1)
printf(“\n The number deleted is : %d”, val);
break;
case 3:
val = peek();
if (val != -1)
printf(“\n The first value in queue is : %d”, val);
break;
case 4:
display();
break;
 }
}while(option != 5);
getch();
return 0;
}
void insert()
{
int num;
printf(“\n Enter the element to be inserted in the queue : “);
scanf(“%d”, &num);
if(rear == MAX-1)
printf(“\n OVERFLOW”);
else if(front == -1 && rear == -1)
front = rear = 0;
else
rear++;
queue[rear] = num;
}
int delete_element()
{
int val;
if(front == -1 || front>rear)
{
printf(“\n UNDERFLOW”);
return -1;
}
else
{
val = queue[front];
front++;
if(front > rear)
front = rear = -1;
return val;
}
}
int peek()
{
if(front==-1 || front>rear)
{
printf(“\n QUEUE IS EMPTY”);
return -1;
}
else
{
return queue[front];
}
}
void display()
{
int i;
printf(“\n”);
if(front == -1 || front > rear)
printf(“\n QUEUE IS EMPTY”);
else
{
for(i = front;i <= rear;i++)
printf(“\t %d”, queue[i]);
}
}

Output:

***** MAIN MENU *****"
1. Insert an element
2. Delete an element
3. Peek
4. Display the queue
5. EXIT
Enter your option : 1
Enter the number to be inserted in the queue : 50

Types of queues

  1. Circular Queue
  2. Deque
  3. Priority Queue
  4. Multiple Queue

12. Linked Lists

A linked list, in simple words, is a linear arrangement of data elements. Those data elements are described nodes. A linked list is a data structure which in turn can be employed to perform other data structures. Therefore, it serves as a building block to perform data structures so as to stacks, queues, and variations. A linked list can be seen as a train or a sequence of nodes in which each node includes one or more data fields and a pointer to the following node.

we can observe a linked list in which each node holds two parts, a data location and a pointer to the next node. The left portion of the node which holds data may include a simple data type, an array, or a structure. The right portion of the node contains a pointer to the next node (or address of the next node in order).

In C, we can create a linked list using the following code:

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

Types Of Linked Lists

01. Singly linked lists

A singly linked list is the easiest variety of linked list in which each node includes some data and a pointer to the next node of the corresponding data type. By assuming that the node contains a pointer to the next node, we determine that the node stores the address of the next node in the series. A singly linked list provides traversal of data just in one way.

02. Circular linked list

In a circular linked list, that last node holds a pointer to the first node of the list. While traversing a circular linked list, we can start at any node and traverse the list in either direction, forward or backward, till we reach the same node where we began. Therefore, a circular linked list has no beginning and no end.

03. Doubly linked list

A doubly linked list or a two-way linked list is a higher complex variety of linked list which includes a pointer to the next as well as the earlier node in the series. Hence, it consists of three parts—data, a pointer to the next node, and a pointer to the past node.

04. Circular doubly linked list

A circular doubly linked list or a circular two-way linked list is a more complex type of linked list which contains a pointer to the next as well as the previous node in the order. The difference within a doubly linked and a circular doubly linked list is identical as that exists between a singly linked list and a circular linked list.

05. Header linked list

A header linked list is a specific type of linked list which includes a header node at the start of the list. Hence, in a header linked list, START will not point to the first node of the list but START will include the address of the header node. The following are the two kinds of a header-linked list:

Grounded header linked list which saves NULL in the next field of the last node and circular header linked list which saves the address of the header node in the next field of the last node.

Program to create a linked list and perform insertions and deletions of all cases.

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

// Create a node
struct Node {
  int item;
  struct Node* next;
};

void insertAtBeginning(struct Node** ref, int data) {
  // Allocate memory to a node
  struct Node* new_node = (struct Node*)malloc(sizeof(struct Node));

  // insert the item
  new_node->item = data;
  new_node->next = (*ref);

  // Move head to new node
  (*ref) = new_node;
}

// Insert a node after a node
void insertAfter(struct Node* node, int data) {
  if (node == NULL) {
    printf("the given previous node cannot be NULL");
    return;
  }

  struct Node* new_node = (struct Node*)malloc(sizeof(struct Node));
  new_node->item = data;
  new_node->next = node->next;
  node->next = new_node;
}

void insertAtEnd(struct Node** ref, int data) {
  struct Node* new_node = (struct Node*)malloc(sizeof(struct Node));
  struct Node* last = *ref;

  new_node->item = data;
  new_node->next = NULL;

  if (*ref == NULL) {
    *ref = new_node;
    return;
  }

  while (last->next != NULL)
    last = last->next;

  last->next = new_node;
  return;
}

void deleteNode(struct Node** ref, int key) {
  struct Node *temp = *ref, *prev;

  if (temp != NULL && temp->item == key) {
    *ref = temp->next;
    free(temp);
    return;
  }
  // Find the key to be deleted
  while (temp != NULL && temp->item != key) {
    prev = temp;
    temp = temp->next;
  }

  // If the key is not present
  if (temp == NULL) return;

  // Remove the node
  prev->next = temp->next;

  free(temp);
}

// Print the linked list
void printList(struct Node* node) {
  while (node != NULL) {
    printf(" %d ", node->item);
    node = node->next;
  }
}

// Driver program
int main() {
  struct Node* head = NULL;

  insertAtEnd(&head, 1);
  insertAtBeginning(&head, 2);
  insertAtBeginning(&head, 3);
  insertAtEnd(&head, 4);
  insertAfter(head->next, 5);

  printf("Linked list: ");
  printList(head);

  printf("\nAfter deleting an element: ");
  deleteNode(&head, 3);
  printList(head);
}

13. Trees

One tree is represented as a set of one or more nodes where one node is designated as the root of the tree and all the surviving nodes can be partitioned into non-empty sets any of which is a sub-tree of the root. Image shows a tree where node A is the root node and nodes B, C, and D remain children of the root node and set sub-trees of the tree rooted at node A.

  1. Root node: The root node A is the topmost node in the tree. If A = NULL, then it indicates the tree is empty. Sub-trees If the root node A is non NULL, then the trees T1, T2, and T3 are described as the sub-trees of A.
  2. Leaf node: A node that has no children is designated the leaf node or the terminal node. Path A series of continuous edges is called a path. For example, in an image, the path of the root node A to node I is given as A, D, and I.
  3. Ancestor node: An ancestor of a node is any antecedent node on the path from the root to that node. The root node does not have any ancestors. In the tree given in the image, but the nodes A, C, and G are the ancestors of node K.

Types of trees

  1. General trees
  2. Forests
  3. Binary trees
  4. Binary search trees
  5. Expression trees
  6. Tournament trees

If you want one more article on types of trees with programs, then comment below.

14. Graphs

One graph is an ideal data structure that is utilized to perform the mathematical theory of graphs. It is primarily a set of vertices (also called nodes) and edges that join these vertices. A graph is usually viewed as a generalization of the tree building, where instead of becoming a purely parent-to-child the connection between tree nodes, any variety of complex relationships can exist. Graphs are generally used to model any situation where things are related to each other in pairs.

If you want one more article on graphs then comment below, because data structure and algorithms using c language is a huge topic and we can’t cover everything in one article, so comment below if you need programs on data structure and algorithms using c language.

I hope this article “Data Structure and Algorithms Using C Language” may help you all a lot. Thank you for reading the data structure and algorithms using c language.

About The Author

Chetan Shidling

Automotive | Technical Blogger | Engineer | Content Creator

See author's posts

Share Now