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
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:
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
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
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
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.