Data Structures Tutorial

Data Structures Tutorial Asymptotic Notation Structure and Union Array Data Structure Linked list Data Structure Type of Linked list Advantages and Disadvantages of linked list Queue Data Structure Implementation of Queue Stack Data Structure Implementation of Stack Sorting Insertion sort Quick sort Selection sort Heap sort Merge sort Bucket sort Count sort Radix sort Shell sort Tree Traversal of the binary tree Binary search tree Graph Spanning tree Linear Search Binary Search Hashing Collision Resolution Techniques

Misc Topic:

Priority Queue in Data Structure Deque in Data Structure Difference Between Linear And Non Linear Data Structures Queue Operations In Data Structure About Data Structures Data Structures Algorithms Types of Data Structures Big O Notations Introduction to Arrays Introduction to 1D-Arrays Operations on 1D-Arrays Introduction to 2D-Arrays Operations on 2D-Arrays Strings in Data Structures String Operations Application of 2D array Bubble Sort Insertion Sort Sorting Algorithms What is DFS Algorithm What Is Graph Data Structure What is the difference between Tree and Graph What is the difference between DFS and BFS Bucket Sort Dijkstra’s vs Bellman-Ford Algorithm Linear Queue Data Structure in C Stack Using Array Stack Using Linked List Recursion in Fibonacci Stack vs Array What is Skewed Binary Tree Primitive Data Structure in C Dynamic memory allocation of structure in C Application of Stack in Data Structures Binary Tree in Data Structures Heap Data Structure Recursion - Factorial and Fibonacci What is B tree what is B+ tree Huffman tree in Data Structures Insertion Sort vs Bubble Sort Adding one to the number represented an array of digits Bitwise Operators and their Important Tricks Blowfish algorithm Bubble Sort vs Selection Sort Hashing and its Applications Heap Sort vs Merge Sort Insertion Sort vs Selection Sort Merge Conflicts and ways to handle them Difference between Stack and Queue AVL tree in data structure c++ Bubble sort algorithm using Javascript Buffer overflow attack with examples Find out the area between two concentric circles Lowest common ancestor in a binary search tree Number of visible boxes putting one inside another Program to calculate the area of the circumcircle of an equilateral triangle Red-black Tree in Data Structures Strictly binary tree in Data Structures 2-3 Trees and Basic Operations on them Asynchronous advantage actor-critic (A3C) Algorithm Bubble Sort vs Heap Sort Digital Search Tree in Data Structures Minimum Spanning Tree Permutation Sort or Bogo Sort Quick Sort vs Merge Sort

Primitive Data Structure in C

The data structure is a logical or mathematical model for organizing and structuring the main memory or elements.

We can classify the data structures in two ways one is primitive, and the other is non primitive.

Primitive

They are primitive to the language we are using for developing the program. They can be manipulated directly by the machine's instructions.

In C, we have int, float, char, pointer, etc.

Non-primitive data structures

They cannot be manipulated by machine code. They are entirely developer made.

Examples: Arrays, Stacks, Queues, linked lists, trees, etc.

In C, every variable has a specific data type. The data type indicates the size, range, and type of values stored in the variable. There are about seven primitive data types in C. These are short, int, long, char, Float, double, and some variants.

Primitive data types fall into Integer data types such as short, int, and long.

Floating-point data types such as Float and double.

In character data type the number of bytes used to store the data type depends on the compiler (depending on the compiler bit size and operating system). However, regardless of the compiler and operating system bit size, it follows the following rules:

  • Short
    C provides a variant of the integer data type called short. Short Integer is designed to provide integer values with a narrower range than the int data type.

    In C, the number of bytes used to store a data type depends on the compiler (depending on the compiler bit size and operating system). Still, the size of temporary variables is at least 16 or 2 bytes, which is larger. It is not from the size of int. Therefore, for a 2-byte short variable, the minimum value stored in short is -215 or -32768, and the maximum value is 215-1 or +32767. Therefore, the range is -32768 to 0 to 32767.
  • Unsigned Short
    If you already know that you want to store only positive short integers, you can use a variant of the short data type called unsigned short. The unsigned short data type stores only positive short integer values.
  • Int
    Internal In C, the number of bytes used to store the data type depends on the compiler. Depending on the bit size of the compiler and operating system, the size of the int variable should be at least 16 bits or 2 bytes and should not exceed the length. For example- The 16-bit Turbo-C / Turbo-C ++ compiler requires at least 2 bytes to store an int. The minimum value stored in an int is -215 or -32768, and the maximum value is 215-1 or 32767.
  • Unsigned Int
    If you already know that you want to store a positive integer value, you can use a variant of the int data type called unsigned int. The unsigned int data type is used to store only positive integer values.

    Stores a positive integer value twice the int data type because the most significant bit normally used to store the sign of an integer value is freed and not used to store the sign of an integer.

    For a 4-byte unsigned int variable, depending on the compiler and operating system bit size, the minimum value that can be stored is 0, and the maximum value that can be stored is 232 or 4,294,967,295. Therefore, the range is 0 to 4,294,967,295.
  • Long
    The size of a C long variable is at least 32 bits or 4 bytes, depending on the bit size of the compiler and operating system. The minimum value stored in long is -231, and the maximum range is 231-1.
  • Unsigned long
    If you already know that you want to store a positive long integer, you can use a variant of the long data type called unsigned long. The unsigned long data type stores only positive long integer values. Stores a positive integer value twice the long data type because the most significant bit, normally used to store the sign of an integer value, is freed and not used to store the sign of an integer. For a 4-byte unsigned int variable, the minimum value can be stored as 0, and the maximum value is 232-1 or 4,294,967,295. Therefore, the range is 0 to 4,294,967,295. Hover The float data type can also hold numbers in the fractional part. Therefore, use this data type if you need very accurate calculations.
  • Float
    The size of the float variable is at least 32 bits = 4 bytes. You don't have to remember the minimum and maximum floating data types, but for those who want to know, the minimum range is 3.4e-038, and the maximum range is 3.4e + 038.
  • Double
    The size of the double variable is at least 64 bits = 8 bytes. Double data type variables can store data with a minimum value of 1.7e-038 to a maximum value of 1.7e + 038.

    Double data type can store numbers with double precision compared to Float.
  • Char
    C provides the char data type used to store the character value. The char data type can be signed or unsigned. You do not need to specify the signed keyword when declaring a signed char variable, but you must specify the unsigned keyword to declare an unsigned char variable. Now, if you store a character value in the char data type, the character is not stored, but the binary value corresponding to the ASCII value of the character is stored.

    Let us have a look on non-primitive data types to.

Tree

The tree is a Non-Linear data structure. Here data is arranged on multiple levels means, like a hierarchy. To explain hierarchal data clearly, imagine your college where at the top we have a director of the college, then in the next level, we will have HOD, and in the third level, we will have faculty members. Here if there is an issue in your college, the first student will inform the faculty, then the faculty will inform HODs, then HOD will inform the director. But students will not go to the director directly if any issues occur.

In tree data, elements have a hierarchal relationship among them. The tree is used to represent this type of element. We can go from top to bottom in a tree but not down to up. Nodes store information such as integers, strings, etc., this information contained in nodes is of primitive data structure. The node contains information as well as a link to the successor. So basically, tree is a collection of nodes linked together in a hierarchy.

Terminologies used in C

Root: The top most element, it won't have any top most element

Node: It stores information and link.

Parent Node: The principal element of the child node. It is an immediate predecessor of the node.

Child Node: The immediate successor of the node.

Leaf: Node without any immediate successor.

Binary Tree:

This is a Hierarchical data structure where the top element is called the root of the binary tree. Here each node can have up to two children in the binary tree .We can randomly access the element using the index

 Example: File system hierarchy, Data Base Management

 Here we have three main methods

  • preorder (root): print-left-right
  • post order (root): Left and right printing
  • in order (root): Left-Print-Right.

Advantage

  • Can represent relevant data 
  • Inserting and searching is very efficient

Disadvantages

  • Difficult to sort
  • Not very flexible

Application

  • File system hierarchy
  • Some variations of binary trees have different uses.

Program to implement Preorder, In order and Post order In C


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


struct bst
 {
 	int data;
 	struct bst *left;
 	struct bst *right;
 };
 
 struct bst * insert(struct bst *,int);
 void inorder(struct bst *);
 void preorder(struct bst *);
 void postorder(struct bst *);
 
 int main ()
  {
  	struct bst *r=NULL;
  	  r=insert(r,7);
  	  r=insert(r,17);
  	  r=insert(r,27);
  	  r=insert(r,37);
  	  r=insert(r,57);
  	  r=insert(r,67);
  	  r=insert(r,77);
  	  r=insert(r,87);
  	  printf("\n Inorder");
  	  inorder(r);
  	  printf("\nPre Order");
  	  preorder(r);
  	  printf("\nPost Order");
  	  postorder(r);
  	 return 1;
  	 
   } 
   
   struct bst * insert(struct bst *q,int val)
    {
      struct bst *tmp;
      tmp=(struct bst *)malloc(sizeof(struct bst));
      
    	if(q==NULL)
    	 { 
    	 	 tmp->data=val;
    	 	 tmp->left=tmp->right=NULL;
    	 	 return tmp;
		 }
		 else
		  {
		  	 if(val<(tmp->data))
		  	   {
		  	   	  q->left=insert(q->left,val);
			   }
		  	 else
		  	  {
		  	  	 q->right=insert(q->right,val);
		      }
		  }
		 return q; 
	}
	
	
	 void inorder(struct bst *q)
	 {
	  	
	 	if(q==NULL)
	 	 {
	 	 	return;
	     }
	      
	 	   inorder(q->left);
	 	   printf(" %d ",q->data);
		   inorder(q->right);	
	 }
	void preorder(struct bst *q)
	 {
	  	
	 	if(q!=NULL)
	 	 {
		  printf(" %d ",q->data);
		  preorder(q->left);
		  preorder(q->right);
	     }
	     
	 }
	 
	 void postorder(struct bst *q)
	 {
	  	
	 	if(q!=NULL)
	 	 {
	 	   postorder(q->left);
		   postorder(q->right);	
		   printf(" %d ",q->data);
		  
		  
	     }
	     
	 }

Output 

Primitive Data Structure In C

Binary search tree

 Binary tree with additional constraints

 limit:

  • The child on the left should always be smaller than the root node
  • The right child must always be larger than the root node
  • Inserting, deleting and searching are much more efficient than binary trees

 Advantage

  • Organize elements in efficient way
  • You can easily find the smallest and largest nodes in the tree
  • When traversing an order, you will find the sorted items

 Disadvantages

  • Cannot be accessed directly
  • The order adds complexity

 Application

  •  Suitable for sorted hierarchical data

Program In C


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


struct bst
 {
 	int data;
 	struct bst *left;
 	struct bst *right;
 };
 
 struct bst * insert(struct bst *,int);
 void inorder(struct bst *);
 void preorder(struct bst *);
 void postorder(struct bst *);
 
 int main ()
  {
  	struct bst *r=NULL;
  	  r=insert(r,7);
  	  r=insert(r,17);
  	  r=insert(r,27);
  	  r=insert(r,37);
  	  r=insert(r,57);
  	  r=insert(r,67);
  	  r=insert(r,77);
  	  r=insert(r,87);
  	  printf("\n Inorder");
  	  inorder(r);
  	  printf("\nPre Order");
  	  preorder(r);
  	  printf("\nPost Order");
  	  postorder(r);
  	 return 1;
  	 
   } 
   
   struct bst * insert(struct bst *q,int val)
    {
      struct bst *tmp;
      tmp=(struct bst *)malloc(sizeof(struct bst));
      
    	if(q==NULL)
    	 { 
    	 	 tmp->data=val;
    	 	 tmp->left=tmp->right=NULL;
    	 	 return tmp;
		 }
		 else
		  {
		  	 if(val<(tmp->data))
		  	   {
		  	   	  q->left=insert(q->left,val);
			   }
		  	 else
		  	  {
		  	  	 q->right=insert(q->right,val);
		      }
		  }
		 return q; 
	}
	
	
	 void inorder(struct bst *q)
	 {
	  	
	 	if(q==NULL)
	 	 {
	 	 	return;
	     }
	      
	 	   inorder(q->left);
	 	   printf(" %d ",q->data);
		   inorder(q->right);	
	 }
	void preorder(struct bst *q)
	 {
	  	
	 	if(q!=NULL)
	 	 {
		  printf(" %d ",q->data);
		  preorder(q->left);
		  preorder(q->right);
	     }
	     
	 }
	 
	 void postorder(struct bst *q)
	 {
	  	
	 	if(q!=NULL)
	 	 {
	 	   postorder(q->left);
		   postorder(q->right);	
		   printf(" %d ",q->data);
		  
		  
	     }
	     
	 }


Output:

Primitive Data Structure In C

Heap

The binary heap can be visualized as an array as a complete binary tree

 Arr [0] element is treated as root

 length (A)-the size of the array

 heapSize (A)-Heap size 

 Commonly used when dealing with minimum and maximum elements

 For the i-th node

There are two types, minimum heap and maximum heap.

 The minimum heap holds the minimum and elements, and the top and maximum hold the maximum.

 O (1) for processing the minimum or maximum element.

Array

Arrays are a collection of elements of similar data types that continuously allocate memory for randomly accessible arrays. You may be wondering how to access items randomly. Arrays allow you to access elements using only addresses. Now let's actually understand the concept of arrays. The main application is linear storage of information. Works efficiently in frequently searched applications.

Let's start by understanding how to use a one-dimensional array.

One-dimensional array

 The 1D array here looks like a simple line, with the elements stored one at a time.  Declaring an array is similar to simply declaring a variable in C. You must specify the data type, then the array name, and then the maximum size. Check the following syntax to get an idea.  

Array initialization

There are two options for initialization. One is compile-time initialization and the other is run-time initialization. First, every element in the array is assigned some garbage values and needs to be initialized to explicitly store them.

Initialization at compile time

Example program in C language

#include<stdio.h>
int main()
{
int numbers[20]={11,22,33,44,55,66,77,88,99};
printf(" We are initializing variables in compile time\n");
printf("%d \n",numbers[0]);
printf("%d \n",numbers[1]);
printf("%d \n",numbers[2]);
printf("%d \n",numbers[3]);
printf("%d \n",numbers[4]);
printf("%d \n",numbers[6]);
printf("%d \n",numbers[7]);
printf("%d \n",numbers[8]);
}

Output

Primitive Data Structure In C

Compile-time initialization initializes the value of the code itself, so memory is allocated at compile-time. C language sample program.

Runtime initialization

This is also known as dynamic initialization. Here, the elements are initialized at run time and memory is allocated at run time after the program compiles successfully. Use the scanner function to successfully initialize the value at run time. To better understand array access, check out the following examples. The elements of a one-dimensional array are accessed by specifying the exact array name and index value. Note that the index always starts with the value 0. You can access it like this. C language sample program.

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

Primitive Data Structure In C

 There are special rules for declaring a one-dimensional array. It is as follows.

 1. You must declare the variable before you can access it.

 2. Array indexes always start at 0 and end at size -1.

 3. When declaring an array, you need to specify the data type and variable name.

 Two-dimensional array

 A two-dimensional array looks like a mathematical matrix with columns and rows. Also called an array of arrays. 

Like a one-dimensional array, you can declare a two-dimensional array as the arrayname [rowsize] [columnsize] data type.

 Example:

int twodarray [4] [4]; 

Initialization

 The basic and first type of initialization is to specify the value directly when it is declared.

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

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

Primitive Data Structure In C

Access

You can access the element by specifying the correct position as the row and column. Just type arrayname [row] [column].

The main point that should be conveyed is primitive data structures are basic building blocks in non-primitive data structures.



ADVERTISEMENT
ADVERTISEMENT