Data
Structure
The
data structure name indicates itself that organizing the data in memory.
Types of
Data Structures
There are two types of data structures:
- Primitive data structure
- Non-primitive data structure
Primitive Data structure
The primitive data structures are primitive
data types. The int, char, float, double, and pointer are the primitive data
structures that can hold a single value.
Non-Primitive Data structure
The non-primitive data structure is divided
into two types:
- Linear data structure
- Non-linear data structure
Data structures can also be classified as:
- Static data structure: It is a type of
data structure where the size is allocated at the compile time. Therefore,
the maximum size is fixed.
- Dynamic data structure: It is a type of data
structure where the size is allocated at the run time. Therefore, the
maximum size is flexible.
Advantages
of Data structures
·
Efficiency
·
Reusability
· Abstraction
Stack
A Stack is a linear
data structure that follows the LIFO
(Last-In-First-Out) principle
- push(): When we insert an element in a stack then
the operation is known as a push. If the stack is full then the overflow
condition occurs.
- pop(): When we delete an element from the stack,
the operation is known as a pop. If the stack is empty means that no
element exists in the stack, this state is known as an underflow state.
- show()
- exit
#include <stdio.h>
#include<conio.h>
int stack[100],i,j,choice=0,n,top=-1;
void push();
void pop();
void show();
main ()
{
printf("Enter the number of elements in the stack ");
scanf("%d",&n);
printf("*********Stack operations using array*********");
printf("\n----------------------------------------------\n");
while(choice != 4)
{
printf("Chose one from the below options...\n");
printf("\n1.Push\n2.Pop\n3.Show\n4.Exit");
printf("\n Enter your choice \n");
scanf("%d",&choice);
switch(choice)
{
case 1:
{
push();
break;
}
case 2:
{
pop();
break;
}
case 3:
{
show();
break;
}
case 4:
{
printf("Exiting....");
break;
}
default:
{
printf("Please Enter valid choice ");
}
};
}
}
void push ()
{
int val;
if (top == n )
printf("\n Overflow");
else
{
printf("Enter the value?");
scanf("%d",&val);
top = top +1;
stack[top] = val;
}
}
void pop ()
{
if(top == -1)
printf("Underflow");
else
top = top -1;
}
void show()
{
for (i=top;i>=0;i--)
{
printf("%d\n",stack[i]);
}
if(top == -1)
{
printf("Stack is empty");
}
}
Queue
·
A queue can be defined as an ordered list which enables insert operations
to be performed at one end called REAR and delete operations to be performed at another end called FRONT.
·
Queue is referred to be as First In First Out list.
Array representation of Queue
#include<stdio.h>
#include<stdlib.h>
#define maxsize 5
void insert();
void delete();
void display();
int front = -1, rear = -1;
int queue[maxsize];
main ()
{
int choice;
while(choice != 4)
{
printf("\n*************************Main Menu*****************************\n");
printf("\n=================================================================\n");
printf("\n1.insert an element\n2.Delete an element\n3.Display the queue\n4.Exit\n");
printf("\nEnter your choice ?");
scanf("%d",&choice);
switch(choice)
{
case 1:
insert();
break;
case 2:
delete();
break;
case 3:
display();
break;
case 4:
exit(0);
break;
default:
printf("\nEnter valid choice??\n");
}
}
getch();
}
void insert()
{
int item;
printf("\nEnter the element\n");
scanf("\n%d",&item);
if(rear == maxsize-1)
{
printf("\nOVERFLOW\n");
return;
}
if(front == -1 && rear == -1)
{
front = 0;
rear = 0;
}
else
{
rear = rear+1;
}
queue[rear] = item;
printf("\nValue inserted ");
}
void delete()
{
int item;
if (front == -1 || front > rear)
{
printf("\nUNDERFLOW\n");
return;
}
else
{
item = queue[front];
if(front == rear)
{
front = -1;
rear = -1 ;
}
else
{
front = front + 1;
}
printf("\nvalue deleted ");
}
}
void display()
{
int i;
if(rear == -1)
{
printf("\nEmpty queue\n");
}
else
{ printf("\nprinting values .....\n");
for(i=front;i<=rear;i++)
{
printf("\n%d\n",queue[i]);
}
}
}
Output:
*************Main
Menu**************
==============================================
1.insert
an element
2.Delete
an element
3.Display
the queue
4.Exit
Enter
your choice ?1
Enter
the element
123
Value
inserted
*************Main
Menu**************
==============================================
1.insert
an element
2.Delete
an element
3.Display
the queue
4.Exit
Enter
your choice ?1
Enter
the element
90
Value
inserted
*************Main
Menu**************
===================================
1.insert
an element
2.Delete
an element
3.Display
the queue
4.Exit
Enter
your choice ?2
value
deleted
*************Main
Menu**************
==============================================
1.insert
an element
2.Delete
an element
3.Display
the queue
4.Exit
Enter
your choice ?3
printing
values .....
90
*************Main
Menu**************
==============================================
1.insert
an element
2.Delete
an element
3.Display
the queue
4.Exit
Enter
your choice ?4
Linked list
Linked list is a linear data structure that includes a series of connected nodes. Linked list can be defined as the nodes that are randomly stored in the memory.
Advantages of Linked list
·
Dynamic data structure
·
Memory
efficient
Types
of Linked list
·
Singly-linked list
·
Doubly linked list
·
Circularly linked list
* Circularly Singly linked list
*
Circularly Doubly linked list
Singly
Linked list
·
A data item
·
An address of another
node
We wrap both the data
item and the next node reference in a struct as:
struct node
{
int
data;
struct node
*next;
};
#include<stdio.h>
#include<stdlib.h>
struct node
{
int
data;
struct node
*next;
};
struct node *head;
void beginsert ();
void lastinsert ();
void begin_delete();
void last_delete();
void display();
void search();
void main ()
{
int choice
=0;
clrscr();
while(choice
!= 7)
{
printf("\n\n*********Main
Menu*********\n");
printf("\nChoose
one option from the following list ...\n");
printf("\n===============================================\n");
printf("\n1.Insert
in begining\n2.Insert at last\n3.Delete from Beginning\n4.Delete from
last\n5.Search for an element\n6.Show\n7.Exit\n");
printf("\nEnter
your choice?\n");
scanf("\n%d",&choice);
switch(choice)
{
case 1:
beginsert();
break;
case 2:
lastinsert();
break;
case 3:
begin_delete();
break;
case 4:
last_delete();
break;
case 5:
search();
break;
case 6:
display();
break;
case 7:
exit(0);
break;
default:
printf("Please enter valid
choice..");
}
}
getch();
}
void beginsert()
{
struct node
*ptr;
int item;
ptr = (struct
node *) malloc(sizeof(struct
node *));
if(ptr ==
NULL)
{
printf("\nOVERFLOW");
}
else
{
printf("\nEnter
value\n");
scanf("%d",&item);
ptr->data = item;
ptr->next = head;
head = ptr;
printf("\nNode
inserted");
}
}
void lastinsert()
{
struct node
*ptr,*temp;
int item;
ptr = (struct
node*)malloc(sizeof(struct
node));
if(ptr ==
NULL)
{
printf("\nOVERFLOW");
}
else
{
printf("\nEnter
value?\n");
scanf("%d",&item);
ptr->data = item;
if(head ==
NULL)
{
ptr
-> next = NULL;
head = ptr;
printf("\nNode inserted");
}
else
{
temp = head;
while (temp -> next != NULL)
{
temp = temp -> next;
}
temp->next = ptr;
ptr->next = NULL;
printf("\nNode inserted");
}
}
}
void begin_delete()
{
struct node
*ptr;
if(head ==
NULL)
{
printf("\nList
is empty\n");
}
else
{
ptr = head;
head = ptr->next;
free(ptr);
printf("\nNode
deleted from the begining ...\n");
}
}
void last_delete()
{
struct node
*ptr,*ptr1;
if(head ==
NULL)
{
printf("\nlist
is empty");
}
else if(head -> next == NULL)
{
head = NULL;
free(head);
printf("\nOnly
node of the list deleted ...\n");
}
else
{
ptr = head;
while(ptr->next
!= NULL)
{
ptr1 = ptr;
ptr
= ptr ->next;
}
ptr1->next = NULL;
free(ptr);
printf("\nDeleted
Node from the last ...\n");
}
}
void search()
{
struct node
*ptr;
int
item,i=0,flag;
ptr = head;
if(ptr ==
NULL)
{
printf("\nEmpty
List\n");
}
else
{
printf("\nEnter
item which you want to search?\n");
scanf("%d",&item);
while
(ptr!=NULL)
{
if(ptr->data == item)
{
printf("item
found at location %d ",i+1);
flag=0;
}
else
{
flag=1;
}
i++;
ptr
= ptr -> next;
}
if(flag==1)
{
printf("Item not found\n");
}
}
}
void display()
{
struct node
*ptr;
ptr = head;
if(ptr ==
NULL)
{
printf("Nothing
to print");
}
else
{
printf("\nprinting
values . . . . .\n");
while
(ptr!=NULL)
{
printf("\n%d",ptr->data);
ptr = ptr -> next;
}
}
}
Output
Doubly linked list
struct node
{
struct node *prev;
int data;
struct node *next;
}
#include<stdio.h>
#include<conio.h>
#include<stdlib.h>
struct node
{
struct node
*prev;
struct node
*next;
int
data;
};
struct node *head;
void insertion_beginning();
void insertion_last();
void deletion_beginning();
void deletion_last();
void display();
void search();
main
()
{
int choice =0;
clrscr();
while(choice
!= 7)
{
printf("\n*********Main
Menu*********\n");
printf("\nChoose
one option from the following list ...\n");
printf("\n===============================================\n");
printf("\n1.Insert
in begining\n2.Insert at last\n3.Delete from Beginning\n4.Delete from
last\n5.Search\n6.Show\n7.Exit\n");
printf("\nEnter
your choice?\n");
scanf("\n%d",&choice);
switch(choice)
{
case
1:
insertion_beginning();
break;
case
2:
insertion_last();
break;
case
3:
deletion_beginning();
break;
case
4:
deletion_last();
break;
case
5:
search();
break;
case
6:
display();
break;
case
7:
exit(0);
break;
default:
printf("Please
enter valid choice..");
}
}
getch();
}
void insertion_beginning()
{
struct node
*ptr;
int
item;
ptr = (struct
node *)malloc(sizeof(struct
node));
if(ptr ==
NULL)
{
printf("\nOVERFLOW");
}
else
{
printf("\nEnter
Item value");
scanf("%d",&item);
if(head==NULL)
{
ptr->next = NULL;
ptr->prev=NULL;
ptr->data=item;
head=ptr;
}
else
{
ptr->data=item;
ptr->prev=NULL;
ptr->next = head;
head->prev=ptr;
head=ptr;
}
printf("\nNode
inserted\n");
}
}
void insertion_last()
{
struct node
*ptr,*temp;
int
item;
ptr = (struct
node *) malloc(sizeof(struct
node));
if(ptr ==
NULL)
{
printf("\nOVERFLOW");
}
else
{
printf("\nEnter
value");
scanf("%d",&item);
ptr->data=item;
if(head
== NULL)
{
ptr->next = NULL;
ptr->prev = NULL;
head = ptr;
}
else
{
temp = head;
while(temp->next!=NULL)
{
temp = temp->next;
}
temp->next = ptr;
ptr ->prev=temp;
ptr->next = NULL;
}
}
printf("\nnode
inserted\n");
}
void deletion_beginning()
{
struct node
*ptr;
if(head ==
NULL)
{
printf("\n
UNDERFLOW");
}
else if(head->next == NULL)
{
head = NULL;
free(head);
printf("\nnode
deleted\n");
}
else
{
ptr = head;
head = head -> next;
head -> prev = NULL;
free(ptr);
printf("\nnode
deleted\n");
}
}
void deletion_last()
{
struct node
*ptr;
if(head ==
NULL)
{
printf("\n
UNDERFLOW");
}
else if(head->next == NULL)
{
head = NULL;
free(head);
printf("\nnode
deleted\n");
}
else
{
ptr = head;
if(ptr->next
!= NULL)
{
ptr = ptr -> next;
}
ptr -> prev -> next = NULL;
free(ptr);
printf("\nnode
deleted\n");
}
}
void display()
{
struct node
*ptr;
printf("\n
printing values...\n");
ptr = head;
while(ptr
!= NULL)
{
printf("%d\n",ptr->data);
ptr=ptr->next;
}
}
void search()
{
struct node
*ptr;
int
item,i=0,flag;
ptr = head;
if(ptr ==
NULL)
{
printf("\nEmpty
List\n");
}
else
{
printf("\nEnter
item which you want to search?\n");
scanf("%d",&item);
while
(ptr!=NULL)
{
if(ptr->data
== item)
{
printf("\nitem
found at location %d ",i+1);
flag=0;
break;
}
else
{
flag=1;
}
i++;
ptr = ptr -> next;
}
if(flag==1)
{
printf("\nItem
not found\n");
}
}
}
Circular Singly Linked List
#include<stdio.h>
#include<stdlib.h>
struct node
{
int
data;
struct node
*next;
};
struct node *head;
void beginsert ();
void lastinsert ();
void begin_delete();
void last_delete();
void display();
void search();
void main ()
{
int choice
=0;
clrscr();
while(choice
!= 7)
{
printf("\n*********Main
Menu*********\n");
printf("\nChoose
one option from the following list ...\n");
printf("\n===============================================\n");
printf("\n1.Insert
in begining\n2.Insert at last\n3.Delete from Beginning\n4.Delete from
last\n5.Search for an element\n6.Show\n7.Exit\n");
printf("\nEnter
your choice?\n");
scanf("\n%d",&choice);
switch(choice)
{
case
1:
beginsert();
break;
case
2:
lastinsert();
break;
case
3:
begin_delete();
break;
case
4:
last_delete();
break;
case
5:
search();
break;
case
6:
display();
break;
case
7:
exit(0);
break;
default:
printf("Please
enter valid choice..");
}
}
getch();
}
void beginsert()
{
struct node
*ptr,*temp;
int
item;
ptr = (struct
node *)malloc(sizeof(struct
node));
if(ptr ==
NULL)
{
printf("\nOVERFLOW");
}
else
{
printf("\nEnter
the node data?");
scanf("%d",&item);
ptr -> data = item;
if(head
== NULL)
{
head = ptr;
ptr -> next = head;
}
else
{
temp = head;
while(temp->next
!= head)
temp = temp->next;
ptr->next = head;
temp -> next = ptr;
head = ptr;
}
printf("\nnode
inserted\n");
}
}
void lastinsert()
{
struct node
*ptr,*temp;
int
item;
ptr = (struct
node *)malloc(sizeof(struct
node));
if(ptr ==
NULL)
{
printf("\nOVERFLOW\n");
}
else
{
printf("\nEnter
Data?");
scanf("%d",&item);
ptr->data = item;
if(head
== NULL)
{
head = ptr;
ptr -> next = head;
}
else
{
temp = head;
while(temp
-> next != head)
{
temp = temp -> next;
}
temp -> next = ptr;
ptr -> next = head;
}
printf("\nnode
inserted\n");
}
}
void begin_delete()
{
struct node
*ptr;
if(head ==
NULL)
{
printf("\nUNDERFLOW");
}
else if(head->next == head)
{
head = NULL;
free(head);
printf("\nnode
deleted\n");
}
else
{
ptr = head;
while(ptr
-> next != head)
ptr = ptr -> next;
ptr->next = head->next;
free(head);
head = ptr->next;
printf("\nnode
deleted\n");
}
}
void last_delete()
{
struct node
*ptr, *preptr;
if(head==NULL)
{
printf("\nUNDERFLOW");
}
else if (head ->next == head)
{
head = NULL;
free(head);
printf("\nnode
deleted\n");
}
else
{
ptr = head;
while(ptr
->next != head)
{
preptr=ptr;
ptr = ptr->next;
}
preptr->next = ptr -> next;
free(ptr);
printf("\nnode
deleted\n");
}
}
void search()
{
struct node
*ptr;
int
item,i=0,flag=1;
ptr = head;
if(ptr ==
NULL)
{
printf("\nEmpty
List\n");
}
else
{
printf("\nEnter
item which you want to search?\n");
scanf("%d",&item);
if(head
->data == item)
{
printf("item
found at location %d",i+1);
flag=0;
}
else
{
while
(ptr->next != head)
{
if(ptr->data
== item)
{
printf("item
found at location %d ",i+1);
flag=0;
break;
}
else
{
flag=1;
}
i++;
ptr = ptr -> next;
}
}
if(flag
!= 0)
{
printf("Item
not found\n");
}
}
}
void display()
{
struct node
*ptr;
ptr=head;
if(head ==
NULL)
{
printf("\nnothing
to print");
}
else
{
printf("\n
printing values ... \n");
while(ptr
-> next != head)
{
printf("%d\n",
ptr -> data);
ptr = ptr -> next;
}
printf("%d\n",
ptr -> data);
}
Output
Circular Doubly Linked List
#include<stdio.h>
#include<conio.h>
#include<stdlib.h>
struct node
{
struct node
*prev;
struct node
*next;
int
data;
};
struct node *head;
void insertion_beginning();
void insertion_last();
void deletion_beginning();
void deletion_last();
void display();
void search();
void main ()
{
int choice =0;
clrscr();
while(choice
!= 7)
{
printf("\n*********Main
Menu*********\n");
printf("\nChoose
one option from the following list ...\n");
printf("\n===============================================\n");
printf("\n1.Insert
in Beginning\n2.Insert at last\n3.Delete from Beginning\n4.Delete from
last\n5.Search\n6.Show\n7.Exit\n");
printf("\nEnter
your choice?\n");
scanf("\n%d",&choice);
switch(choice)
{
case
1:
insertion_beginning();
break;
case
2:
insertion_last();
break;
case
3:
deletion_beginning();
break;
case
4:
deletion_last();
break;
case
5:
search();
break;
case
6:
display();
break;
case
7:
exit(0);
break;
default:
printf("Please
enter valid choice..");
}
}
getch();
}
void insertion_beginning()
{
struct node
*ptr,*temp;
int
item;
ptr = (struct
node *)malloc(sizeof(struct
node));
if(ptr ==
NULL)
{
printf("\nOVERFLOW");
}
else
{
printf("\nEnter
Item value");
scanf("%d",&item);
ptr->data=item;
if(head==NULL)
{
head = ptr;
ptr -> next = head;
ptr -> prev = head;
}
else
{
temp = head;
while(temp
-> next != head)
{
temp = temp -> next;
}
temp -> next = ptr;
ptr -> prev = temp;
head -> prev = ptr;
ptr -> next = head;
head = ptr;
}
printf("\nNode
inserted\n");
}
}
void insertion_last()
{
struct node
*ptr,*temp;
int
item;
ptr = (struct
node *) malloc(sizeof(struct
node));
if(ptr ==
NULL)
{
printf("\nOVERFLOW");
}
else
{
printf("\nEnter
value");
scanf("%d",&item);
ptr->data=item;
if(head
== NULL)
{
head = ptr;
ptr -> next = head;
ptr -> prev = head;
}
else
{
temp = head;
while(temp->next
!=head)
{
temp = temp->next;
}
temp->next = ptr;
ptr ->prev=temp;
head -> prev = ptr;
ptr -> next = head;
}
}
printf("\nnode
inserted\n");
}
void deletion_beginning()
{
struct node
*temp;
if(head ==
NULL)
{
printf("\n
UNDERFLOW");
}
else if(head->next == head)
{
head = NULL;
free(head);
printf("\nnode
deleted\n");
}
else
{
temp = head;
while(temp
-> next != head)
{
temp = temp -> next;
}
temp -> next = head -> next;
head -> next -> prev = temp;
free(head);
head = temp -> next;
}
}
void deletion_last()
{
struct node
*ptr;
if(head ==
NULL)
{
printf("\n
UNDERFLOW");
}
else if(head->next == head)
{
head = NULL;
free(head);
printf("\nnode
deleted\n");
}
else
{
ptr = head;
if(ptr->next
!= head)
{
ptr = ptr -> next;
}
ptr -> prev -> next = head;
head -> prev = ptr -> prev;
free(ptr);
printf("\nnode
deleted\n");
}
}
void display()
{
struct node
*ptr;
ptr=head;
if(head ==
NULL)
{
printf("\nnothing
to print");
}
else
{
printf("\n
printing values ... \n");
while(ptr
-> next != head)
{
printf("%d\n",
ptr -> data);
ptr = ptr -> next;
}
printf("%d\n",
ptr -> data);
}
}
void search()
{
struct node
*ptr;
int
item,i=0,flag=1;
ptr = head;
if(ptr ==
NULL)
{
printf("\nEmpty
List\n");
}
else
{
printf("\nEnter
item which you want to search?\n");
scanf("%d",&item);
if(head
->data == item)
{
printf("item
found at location %d",i+1);
flag=0;
}
else
{
while
(ptr->next != head)
{
if(ptr->data
== item)
{
printf("item
found at location %d ",i+1);
flag=0;
break;
}
else
{
flag=1;
}
i++;
ptr = ptr -> next;
}
}
if(flag
!= 0)
{
printf("Item
not found\n");
}
}
Output
} Tree
Collections of nodes & edges form of
hierarchical data structure
Complete Binary Tree
Perfect Binary Tree
- Inorder traversal
- Preorder traversal
- Postorder traversal
Inorder Traversal
left ->root->right
Preorder Traversal
root->left->right
Postorder Traversal
left->right->root
EXAMPLE:1
#include<stdio.h>
#include<stdlib.h>
#include<conio.h>
struct
node{
int item;
struct
node* left;
struct
node* right;
};
void
inordertraversal(struct node* root){
if(root==NULL)
return;
inordertraversal(root
-> left);
printf("%d->",root->item);
inordertraversal(root->right);
}
void
preordertraversal(struct node* root){
if(root==NULL)
return;
printf("%d->",root->item);
preordertraversal(root
-> left);
preordertraversal(root
-> right);
}
void
postordertraversal(struct node* root){
if(root==NULL)
return;
postordertraversal(root
-> left);
postordertraversal(root
-> right);
printf("%d->",root->item);
}
struct
node* createnode(value){
struct
node* newnode= malloc(sizeof(struct node));
newnode->item=value;
newnode->left=NULL;
newnode->right=NULL;
return
newnode;
}
struct
node* insertleft(struct node*root, int value){
root->left=createnode(value);
return
root->left;
}
struct
node* insertright(struct node*root, int value){
root->right=createnode(value);
return
root->right;
}
int
main(){
struct
node* root=createnode(1);
clrscr();
insertleft(root,2);
insertright(root,3);
insertleft(root->left,4);
printf("inorder
traversal");
inordertraversal(root);
printf("\n
preorder traversal");
preordertraversal(root);
printf("\n
postorder traversal");
postordertraversal(root);
getch();
}
output
inorder traversal order
4->2->1->3
preorder traversal order
1->2->4->3
postorder traversal order
4->2->3->1
0 comments:
Post a Comment