DATA STRUCTURE
Introduction:-
 |
| Add caption |
(Q)What
is Data Structure? How Array is differ form Data Structure?
Ans:-
Data structure is a collection of number
of elements or nodes joined by a common logical structure. Data Structure is
used to maintain or keep our data in structural formate.
Array is also a structure as it has a no
of elements joined by a common logical structure but is lacks certain main
feature of data structure.
Difference:-
*
The array can contain data of only one type. For ex:- When we declare an array
int[10] , then array can have only one int type of data ,but DS has any type of
data.
*The
length of an array becomes fixed at the time of declaration itself which can’t
be change after wards, but the length of data structure can be changed any
moment at our will.
*Insertion
and deletion is very tough process in te array, Which is very easy process in
DS.
Ans:-
STEP (1)
Start
(2)Store a value in new node and
also store its next part in NULL
(3) If the list is empty or a new element comes then new/fresh node is known as header/first node.
(4) If user want to insert node at first position then:-
(a)
Insert new node as header node and its next part in store address of first node.
(b) Set new node as header node.
(5) If user wants to insert node at last position then:-
(a) Insert new
node at the last position as:-
Last node
->next part = new node.
(6) Else If user wants to insert
node at any location then:-
(a) visit on location node and its next
part in insert new node address as:-
Location node->next part= new
node.
(b)insert new node next part in address of (location->next
node).
(7) End.
(i) insert node at begin
(ii)Insert node at end
(iii) Insert node at any location according to user choice
(iv) Display all node from link list.
(v)Del node at begin.
(vi) Del node at end
(vii) Del node at loc
#include<stdio.h> #include<conio.h> #include<stdlib.h> struct lll { int roll; struct lll *next;//self referncial structure }; struct lll *head,*fresh,*tmp,*ptr; int tn=0; void ins_at_beg(void);//prototyping of fun void display(void);//prototyping of function void ins_at_end(void);// prototyping of fun void ins_at_loc(void); void del_at_beg(void); void del_at_end(void); void del_at_loc(void); void length (void); main() { int ch ; do { printf("\n press 1 for insert at beg"); printf("\n 2 for insert at end"); printf("\n 3 for insert at location"); printf("\n 4 for display"); printf("\n 5 for del at beg"); printf("\n 6 for del at end"); printf("\n 7 for del at loc"); printf("\n 8 for find length of link list"); printf("\n 9 fornexit"); printf("\n enter ur choice"); scanf("%d",&ch); switch(ch) { case 1: ins_at_beg(); break;//calling of function case 2: ins_at_end();break; case 3: ins_at_loc();break; case 4: display();break; case 5: del_at_beg();break; case 6: del_at_end();break; case 7: del_at_loc();break; case 8: length(); break; default: printf("\n invalid entry re enter ur choice"); } }while(ch!=8); getch(); } void ins_at_beg() { fresh=(struct lll*)malloc (sizeof(struct lll));// dynamically memory allocate printf("\n enter roll no"); scanf("%d",& fresh->roll); fresh->next=NULL; if(head==NULL) { head=fresh; } else { fresh->next=head; head=fresh; } tn++; } void display(void)//definition of fun { if(head==NULL) { printf("\n link list is empty"); getch(); exit(0); } else { ptr=head; while(ptr!=NULL) { printf("\t %d",ptr->roll); ptr= ptr->next; } } getch(); } void ins_at_end() { fresh=(struct lll*)malloc (sizeof(struct lll));// dynamically memory allocate printf("\n enter roll no"); scanf("%d",& fresh->roll); fresh->next=NULL; if(head==NULL) { head=fresh; } else { ptr=head; while(ptr->next!=NULL) { ptr=ptr->next; } ptr->next=fresh; } tn++; } void del_at_end() { if(head==NULL) { printf("\n link list is empty del not possible"); getch(); exit; } else if(head->next==NULL)// only for a single node in link list. { ptr=head; head=NULL; free(ptr); } else { ptr=head; while(ptr->next!=NULL) { tmp=ptr; ptr=ptr->next; } tmp->next=NULL; free(ptr); } tn--; } void ins_at_loc() { int i=1,loc; printf("\n entr location , at which u want to insert"); scanf("%d",& loc); if(loc==1) { ins_at_beg(); } else { fresh=(struct lll*)malloc (sizeof(struct lll));// dynamically memory allocate printf("\n enter roll no"); scanf("%d",& fresh->roll); fresh->next=NULL; ptr=head; while(i<loc&&ptr->next!=NULL) { i++; tmp=ptr; ptr=ptr->next; } tmp->next=fresh; fresh->next=ptr; } tn++; } void del_at_beg() { if(head==NULL) { printf("\n link list is empty del not possible"); getch(); exit; } else { ptr=head; head=head->next; ptr->next=NULL;//ptr ka link head s khatm ho gya. free(ptr); } tn--; } void del_at_loc() { int i=1,loc; printf("\n enter location for deletion"); scanf("%d",&loc); if(loc==1) { del_at_beg(); } else if(loc==tn) { del_at_end(); } else if(loc<tn) { ptr=head; while(i<loc) {i++; tmp=ptr; ptr=ptr->next; } tmp->next=ptr->next; ptr->next=NULL; free(ptr); } } void length (void) { int len=0; if(head==NULL) { printf("\n linked list is emply,so length of lll is zero"); getch(); } else { for (ptr=head;ptr!=NULL;ptr=ptr->next); { len++; } printf("\n total no of node=%d",len); getch(); } }
(i) insert node at begin
(ii)Insert node at end
(iii) Insert node at any location according to user choice
(iv) Display all node from link list.
(v)Del node at begin.
(vi) Del node at end
(vii) Del node at loc
struct dll
{
struct dll *prev;
int roll;
struct dll *next;
};
struct dll *head,*tail,*fresh,*tmp,*ptr;
int tn=0;
void ins_at_beg(void);
void ins_at_end(void);//prototyping of fun
void ins_at_loc(void);
void del_at_beg(void);
void del_at_end(void);
void del_at_loc(void);
void display(void);
void display_rev(void);
main()
{
int ch ;
do
{
printf("\n press 1 for insert at beg");
printf("\n press 2 for insert at end");
printf("\n press 3 for insert at loc");
printf("\n press 4 for del at begin");
printf("\n press 5 for del at end");
printf("\n press 6 for del at loc");
printf("\n press 7 for display");
printf("\n press 8 for display reverse order");
printf("\n 9 for next");
printf("\n enter ur choice");
scanf("%d",&ch);
switch(ch)
{
case 1: ins_at_beg(); break;//calling of function
case 2: ins_at_end();break;
case 3: ins_at_loc();break;
case 4: del_at_beg();break;
case 5: del_at_end();break;
case 6: del_at_loc();break;
case 7:display();break;
case 8:display_rev();break;
default:
printf("\n invalid entry re enter ur choice");
}
}while(ch!=9);
getch();
}
void ins_at_beg()
{
fresh=(struct dll*)malloc (sizeof(struct dll));// dynamically memory allocate // ye line fresh me new memory allocate krega.
printf("\n enter roll no");
scanf("%d",& fresh->roll);// y line fresh me roll/value input krega.
fresh->next=NULL;// fresh ka next part me NULL value assign krega.
fresh->prev=NULL;// ye line fresh ke previous part me NULL vlaue assign krega.
if(head==NULL)
{
head=fresh; // agar link list me koi v value nhi hoga to fresh vala value head node bn jayga
tail=fresh; // dry run
} // fresh head tail ptr tmp 22 11
else // 11 11 11
{ // 22 22
// 33 33
fresh->next=head;
head->prev=fresh;
head=fresh;
}
tn++;
}
void display(void)//definition of fun
{
if(head==NULL)
{
printf("\n link list is empty");
getch();
exit(0);
}
else
{
ptr=head;
while(ptr!=NULL)
{
printf("\t %d",ptr->roll);
ptr= ptr->next;
}
}
getch();
}
void display_rev(void)//definition of fun // 33 22 11
{
if(head==NULL) //head ptr tmp tail
{ //33 33 11
printf("\n link list is empty"); // 22
getch(); // 11
exit(0); // NULL
}
else
{
ptr=tail;
while(ptr!=NULL)
{
printf("\t %d",ptr->roll);
ptr= ptr->prev;
}
}
getch();
}
void ins_at_end()
{
fresh=(struct dll*)malloc (sizeof(struct dll));// dynamically memory allocate // ye line fresh me new memory allocate krega.
printf("\n enter roll no");
scanf("%d",& fresh->roll);// y line fresh me roll/value input krega.
fresh->next=NULL;// fresh ka next part me NULL value assign krega.
fresh->prev=NULL;// ye line fresh ke previous part me NULL vlaue assign krega.
if(head==NULL)
{
head=fresh; // agar link list me koi v value nhi hoga to fresh vala value head node bn jayga
tail=fresh; // dry run
} // fresh head tail ptr tmp 22 11
else // 11 11 11
{ // 22 22
ptr=head;
while(ptr->next!=NULL)
{ // fresh tail fresh
ptr=ptr->next; // 10 20 300 40 50
}
tail->next=fresh;
fresh->prev=tail;
tail=fresh;
}
tn++;
}
(Q) What is Stack? Explain
briefly. What are the various types of operations performed on it?
Stack is a linear data structure , which works on the concept of First in last out or Last In First out. The insertion and deletion take position only at one end we can say that Top. Stack can be maintained using array and linklist.
In the case of Static array, When Stack is fully empty mean to say there are no any there are no any element in stack, its top position is below of first index i.e. -1. The value of -1 is also known as Sentinel value of Stack.
Operation on Stack:-
A Stack is a linear data structure in which items may be inserted or removed only at one end called the top of the stack.
A Stack may be seen in our daily life for ex:-
The no. of plates in a cafeteria, where every new plates added to the top of stack. Similarly every new plate takes off the stack is also from the top of the stack.
*Advantage of Stack:-
* Help in Information Hiding:-
In stack data stored in hidden form , so if some one had already written the functions for handling the stack , then we could use them without need to know the details of how stacks are kept in memory or how the stack operation are performed.
Stack is also called a “Push down list”.
Operations on Stack:-
Push:- When an item is added to a stack , the operation is called push.
POP:- when an item is removed from the stack then we say that we POP it from stack.
*IN stack Operations will be performed after checking its Status:-
(1) Stack Empty:- When the Stack exists and it has been initialized , then this return TRUE if stack is empty, and FALSE otherwise.
(2) Stack FULL:- When the stack exists and it has been initialized, then this return true if the stack is full, and false otherwise.
·
Stack relate terms:-
The method of writing all operators either before their operands, or after them , is called polish notation.
· When operators are written before there there operands, it is called the prefix form.
· When operators are written after there operands , it is called the postfix form/Reverse polish form/ suffix form.
For ex:-
The expression a*b becomes *ab in prefix form and ab* in postfix form.
(Q)Write an algorithms to create a BST Tree.
Ans:-
1.
START
2.
Select first node as a root node in given Question.
3.
Select another new
node and compare with Root node. If selected node is greater than from
Root/subroot then arrange it Right side from Root node.
4.
Else arrange its left
side From root/subroot.
5.
Repeat step 3 to 4 until
all nodes are not selected from Queue. Else
6.
END.
//Queue by using linkl list
#include<stdio.h>
#include<conio.h>
#include<stdlib.h>
struct que
{
int data;
struct que *next;
};
struct que *fresh,*front,*rear,*ptr;
//Prototyping of fun.
void enq(void);
void deq(void);
void display(void);
main()
{
int ch;
front=NULL;
rear=NULL;
do
{
// clrscr();
printf ("\n 1. Insertion");
printf("\n 2 for deletion");
printf("\n 3 for display");
printf("\n 8 for exit");
printf("\n enter ur choice");
scanf("%d",&ch);
switch(ch)
{
case 1: enq();break;
case 2: deq();break;
case 3: display();break;
case 8: exit;
default:
printf("\n invalid entry, Re_enter ur choice");
getch();
}
}while(ch!=8);
}
void enq(void)
{
fresh=(struct que*)malloc(sizeof(struct que));
printf("\n enter a no");
scanf("%d",&fresh->data);
fresh->next=NULL;
if(front==NULL)
{
front=fresh;
rear=fresh;
//front=rear=fresh;
}
else
{
rear->next=fresh;
rear=fresh;
}
}
void display()
{
if (front==NULL)
{
printf("\n Queue is empty");
getch();
exit;
}
else
{
ptr=front;
while(ptr!=NULL)
{
printf("\t %d",ptr->data);
ptr=ptr->next;
}
getch();
}
}
void deq(void)
{
if (front==NULL)
{
printf("\n queue is empty, deletion not possible");
getch();
exit;
}
else
{
ptr=front;
front=front->next;
ptr->next=NULL;
free(ptr);
}
}
Strictly Binary Tree:- A Strictly binary tree is a binary tree in which each node either contain no child or both children.
Complete Binary Tree:- A Complete binary tree is a binary tree in which all leaf nodes are placed at the same level . It is also known as full binary tree. ‘OR’ A strictly binary tree is called a complete binary tree if all leaf node are placed at same level .
Note:- A complete binary tree can be also an almost complete binary tree.
(*) Almost complete Binary Tree:-
An almost complete binary tree is a binary tree that holds following condition/criteria.
· All the leaf node are placed at bottom level or bottom(bottom-1) level.
· All the leafs are in left most possible position.
A heap tree
is a complete binary tree or almost complete binary tree in which each node has either greater value
to its child node or less value to its child node.
There are basically two types of heap tree.
(i)
Max
heap (Descending heap)
(ii)
Min
heap
(i)Max heap:- Max heap is a heap tree in which each node has
greater value to its child node it is also called descending heap.
(II)Min Heap:-
Min
heap is a hap tree in which each node has less value to its child node .It is also called ascending heap.
(Q)Construct a heap tree by using following elements.
25,35,18,9,46,70,48
HEAP Sort:-
This sorting technique is implemented on heap tree technique .It organize the element of heap tree in particular order. In heap sort last element is exchanged / Interchange element with root node and the element (Which is known as root element) is adjusted at proper position by comparing to its children.
(@)Construction of Binary tree with given preorder
and In-order :-
Preorder :- A B D E F C G H J L K.
Inorder:- D B F E A G C L J H K.
To construct
a binary on the basis of given Preorder and In-order , Follow following steps:-
(1) Pick 1st node from
preorder as root node.
(2) Check inorder in A where it substitute.
Arrange node as leaf node which are from Left side of Root(A) and rest
arrange in Right side.
(@)Construction of Binary tree with given postorder
and In-order :-
Postorder :- A B D E F C G H J L K.
Inorder:- D B F E A G C L J H K.
To construct
a binary on the basis of given Preorder and In-order , Follow following steps:-
(1) Pick last node from postorder as root
node.
(2) Check inorder in A where it substitute.
(3) Arrange node as leaf node which are from Left side of Root(A) and rest arrange in Right side.
(1) Binary tree:-
A binary tree is a tree that has at most two children. It is special type of tree in which each node can contain no child, one child or both children / two children.
*Representation of Binary Tree
· Array representation.
· Link list represention
Array representation:-
In this representation there single dimension array are used, first array holds the element of nodes of binary tree. The 2nd arrary holds the index number of left child of each node and third array holds the index no of right child of each node.
(*) Extended Binary Tree:-
An extended binary tree is generated/ divided from a binary tree by adding some additional nodes to binary tree is represented as square while original nodes of binary tree is represented as circle.
The original nodes are called internal nodes and now added nodes are called external nodes the extended binary tree is also known as 2-Tree.
NOTE:-
(i)New node sit ached as a child of leaf node or as a child of internal node / Non leaf node that contains one child.
(ii) Extended Binary tree having N nodes has N+1 external node..
There are different kinds of graph.
(i) Directed graph:- A directed graph is a graph in which edge be in unidirectional form . In directed graph ways are defined and it move from one vertices to another vertices .Here direction is defined.
(II)Undirected graph:- In undirected graph there are no any specific path direction is defined with the edge. Here edges be in bidirectional form.
(iii)Weighted
Graph:-A graph is said to be weighted , if every edge in the graph is assigned
a data or weight . weight are must be positive and should be greater than zero.
(III) Unweighted Graph:- A graph which has no any weight. This type of graph is known as unweighted graph. Weight are must be positive and should be greater than zero.
(Iv) Unweighted Graph:- A graph which has no any weight. This type of graph is known as unweighted graph. Weight are must be positive and should be greater than zero.
Traversal scheme:-
In a graph it is a problem how to traverse means say how to visit each vertex, exactly once in a graph. There are two ways to traversal a graph.
BFS:-
(1)This is a way to traverse a graph. In this graph traversing technique we use QUEUE for all the node of the graph.First we take any node as a starting node then we take all the adjacent node of that starting node . Similarly approach we take for all other adjacent nodes which are adjacent to the starting node and so on. we have to maintain the visiting status of node in array/queue so that any node can’t traverse again . BFS can be used for directed graph and undirected graph. We shall describe it in relation to undirected graph also. To perform the BFS we should follow the following steps.
Step 1. Select any vertex V in graph and make is the source vertex and make it visited.
step 2: Visit all unvisited vertices which adjacent/concatenate to visited vertex V
step 3: Now visit one of the adjacent unvisited vertexes.
step 4: Repeat step 1 to 3 until all vertices of the graph become visited.
SPANNING Tree:-
A Spanning tree of a graph is an undirected tree consisting of only those edge which are necessary to connect the all vertices(nodes) in the original graph.
A spanning tree has a properties that for any pair of vertices there exist only one edge or path between them, insertion of any edge in a spanning tree from an unique cycle.
A Tree T is said to be a spanning tree of a connected graph G . If T is a sub graph of G and T contains all vertices of G.
EX:-
Spanning tree of fig. is given below.
v6 E7 E8 v3
E4
E2 v5 v4
E3
Spanning Tree of upper Fig.
In this example spanning tree is created .An edge of a graph G i.e. not in a given in spanning tree T is called CHORED . In the above example branch are E2, E3, E4, E7 , E8 and CHORED are :- E1 , E6 , E5.
Minimum Spanning Tree:-
Minimum Spanning tree of a weighted graph ,such that the sum of weight of an edge should be minimum spanning tree with the smallest weight in a weighted graph is called a sorted spanning tree or sorted distance spanning tree or Minimal spanning tree. The minimum spanning tree result in a tree that contain only branches from the edge in the original graph. The edge for the minimum spanning tree are choose in such a way that:-
(1) Every node in a graph must be included in the spanning tree.
(2) The overall edge weight of spanning tree is the minimum.
There are several way to find the minimum spanning tree . Some of these are:-
(i) Kruskal’s Algorithem
(ii) Prim’s Algorithem
(1) Kruskal’s Algorithem:-
Suppose that G is a connected weighted graph of N vertices , we can construct an optimal tree in G by selecting the edge’s for a Tree as follows:-
Step 1. Arrange the edge of G in increasing order of there weight.
Step 2. Then from each successive step select (from all remaining edges of G) another smallest edge that make no cycle with previously selected edge.
Step 3. Stop when n-1 edges have been selected otherwise go to step 2.
v6
v7 v v3
v4
step 4 . select minimum weighted edge from remain graph. so after select vertex v2 to v3 with weight 16.after select this as:-
Traversal scheme:-
In a graph it is a problem how to traverse means say how to visit each vertex, exactly once in a graph. There are two ways to traversal a graph.
BFS:-
(1)This is a way to traverse a graph. In this graph traversing technique we use QUEUE for all the node of the graph.First we take any node as a starting node then we take all the adjacent node of that starting node . Similarly approach we take for all other adjacent nodes which are adjacent to the starting node and so on. we have to maintain the visiting status of node in array/queue so that any node can’t traverse again . BFS can be used for directed graph and undirected graph. We shall describe it in relation to undirected graph also. To perform the BFS we should follow the following steps.
Step 1. Select any vertex V in graph and make is the source vertex and make it visited.
step 2: Visit all unvisited vertices which adjacent/concatenate to visited vertex V
step 3: Now visit one of the adjacent unvisited vertexes.
step 4: Repeat step 1 to 3 until all vertices of the graph become visited.
Now in Queue after delete node 1 , node 2 be a fornt node.Now in Queue front node is 2 so we explore node 2 . Its adjacent nodes are node 4 and 5 so these nodes(node 4 and node 5) are inserted at Rear position of Queue as:-
Now node 2 is deleted from queue so after delete node 3 be a front node as:-
Now node 3 is deleted from queue because it’s a front node, so its adjacent nodes are node 6 and node 7 so after explore node 3 node 6 and 7 is inserted at rear end and node 3 (front node) is deleted from queue so node 4 be a front node as:-
Now node 4 is front node and its adjacent nodes 2 are already visited/maintained in queue, so we only delete node 4 from Front end and after delete node 4 node 5 be a front node. as:-
Now node 5 be a front node and its adjacent node is 2 which are already visited in queue so we only delete node 5 form front end and after delete node 5 node 6 be a front node. as:-
Now node 6 be a fornt node and its adjacent node is 3 which are already visited in queue so we only delete node 6 from front end after delete node 6 node 7 be a fornt node as:-
Now node 7 be a front node and its adjacent node is 3 which are already visited in queue so we only delete node 7 from front end after delete node nothing remain in queue as:-
Now all nodes are deleted from queue . Here Front/Rear located at 8th position which are not declared in queue
so Stop.
Thanks sir
ReplyDeleteGreat job
ReplyDelete
ReplyDeleteNice
Thanks
ReplyDeleteNice
ReplyDeleteWah
ReplyDeleteWelcome
ReplyDelete