Data structure and Algorithm
Stack
Algorithm: Procedure for push():
Step 1: START
Step 2: if top>=size-1 then
Write “ Stack is Overflow”
Step 3: Otherwise
3.1: read data value ‘x’
3.2: top=top+1;
3.3: stack[top]=x;
Step 4: END
Algorithm: procedure pop():
Step 1: START
Step 2: if top==-1 then
Write “Stack is Underflow”
Step 3: otherwise
3.1: print “deleted element”
3.2: top=top-1;
Step 4: END
Algorithm: procedure pop():
Step 1: START
Step 2: if top==-1 then
Write “Stack is Underflow”
Step 3: otherwise
3.1: print “Display elements are”
3.2: for top to 0
Print ‘stack[i]’
Step 4: END
Queue
Algorithm: Procedure for insertion():
Step-1:START
Step-2: if rear==max then
Write ‘Queue is full’
Step-3: otherwise
3.1: read element ‘queue[rear]’
Step-4:STOP
Algorithm: procedure for deletion():
Step-1:START
Step-2: if front==rear then
Write’ Queue is empty’
Step-3: otherwise
3.1: print deleted element
Step-4:STOP
Algorithm: procedure for deletion():
Step-1:START
Step-2: if front==rear then
Write’ Queue is empty’
Step-3: otherwise
3.1: for i=front to rear then
3.2: print ‘queue[i]’
Step-4:STOP
Circular Queue
Algorithm: procedure of insertCQ():
Step-1:START
Step-2: if count==MAX then
Write “Circular queue is full”
Step-3:otherwise
3.1: read the data element
3.2: CQ[rear]=data
3.3: rear=(rear+1)%MAX
3.4: count=count+1
Step-4:STOP
Algorithm: procedure of deleteCQ():
Step-1:START
Step-2: if count==0 then
Write “Circular queue is empty”
Step-3:otherwise
3.1: print the deleted element
3.2: front=(front+1)%MAX
3.3: count=count-1
Step-4:STOP
Algorithm: procedure of displayCQ():
Step-1:START
Step-2: if count==0 then
Write “Circular queue is empty”
Step-3:otherwise
3.1: print the list of elements
3.2: for i=front to j!=0
3.3: print CQ[i]
3.4: i=(i+1)%MAX
Step-4:STOP
Bubble sort
Bubble Sort Algorithm:
Step 1: Repeat Steps 2 and 3 for i=1 to 10
Step 2: Set j=1
Step 3: Repeat while j<=n
(A)
if a[i] < a[j] Then
interchange a[i] and a[j]
[End of if]
(B) Set j = j+1
[End of Inner Loop]
[End of Step 1 Outer Loop]
Step 4: Exit
Insertion
Insertion_sort(ARR,SIZE)
Step 1: Set i=1;
Step 2: while(i<SIZE)
Set temp=ARR[i]
J=i=1;
While(Temp<=ARR[j] and j>=0)
Set ARR[j+1]=ARR[i]
Set j=j-1
End While
SET ARR(j+1)=Temp;
Print ARR after ith pass
Set i=i+1
End while
Step 3: print no.of passes i-1
Step 4: end
Quick sort
ALGORITHM
Step 1: Select first element of array as Pivot
Step 2: Initialize i and j to Beg and End elements respectively
Step 3: Increment i until A[i]>Pivot.
Stop
Step 4: Decrement j until A[ j]>Pivot
Stop
Step 5: if i<j interchange A[i] with A[j].
Step 6: Repeat steps 3,4,5 until i>j i.e: i crossed j.
Step 7: Exchange the Pivot element with element placed at j, which is correct place for
Pivot.
Merge sort
Step 1: First divide the combined list into two sub lists as follows.
Step 2: Now Divide the left sub list into smaller sub list
Step 3: Similarly divide the sub lists till one element is left in the sub list.
Step 4: Next sort the elements in their appropriate positions and then combined the sub
lists.
Step 5: Now these two sub lists are again merged to give the following sorted sub list of size
4.
Step 6: After sorting the left half of the array, containing the same process for the right sub
list also. Then the sorted array of right half of the list is as follows.
Step 7: Finally the left and right halves of the array are merged to give the sorted array as
follows.
Insertion Sort
Step 1: Set DATA[N+1]=ITEM
Step 2: Set LOC=1
Step 3: Repeat while (DATA [LOC] != ITEM)
Set LOC=LOC+1
Step 4: if LOC=N+1 then
Set LOC= -1.
Step 5: Exit
Binary search
BINARY SEARCH[A,N,KEY]
Step 1: begin
Step 2: [Initilization]
Lb=1; ub=n;
Step 3: [Search for the ITEM]
Repeat through step 4,while Lower bound is less than Upper Bound.
Step 4: [Obtain the index of middle value]
MID=(lb+ub)/2
Step 5: [Compare to search for ITEM]
If Key<A[MID] then
Ub=MID-1
Other wise if Key >A[MID] then
Lb=MID+1
Otherwise write “Match Found”
Return Middle.
Step 6: [Unsuccessful Search]
write “Match Not Found”
Step 7: Stop.
Singly linked list
Get the new node using getnode().
newnode = getnode();
If the list is empty, assign new node as start.
start = newnode;
• If the list is not empty, follow the steps given below:
• The next field of the new node is made to point the first
node (i.e. start node) in the list by assigning the address of
the first node.
The start pointer is made to point the new node by
assigning the address of the new node.
Repeat the above steps ‘n’ times.
Insertion at beginning
Get the new node using getnode().
newnode = getnode();
If the list is empty then start = newnode.
If the list is not empty, follow the steps given below:
newnode -> next = start;
start = newnode;
The function insert_at_beg(), is used for inserting a node at the
beginning
At End
Get the new node using getnode()
newnode = getnode();
If the list is empty then start = newnode.
If the list is not empty follow the steps given below:
temp = start;
while(temp -> next != NULL)
temp = temp -> next;
temp -> next = newnode;
At intermediate
Get the new node using getnode().
newnode = getnode();
Ensure that the specified position is in between first node and
last node. If not, specified position is invalid. This is done by
countnode() function.
Store the starting addres s (which is in start pointer) in temp and
prev pointers. Then traverse the temp pointer upto the specified
position followed by prev pointer.
After reaching the specified position, follow the steps given
below:
prev -> next = newnode;
newnode -> next = temp;
Let the interme diat e position be 3.
Delete at begining
If list is empty then display ‘Empty List’ message.
If the list is not empty, follow the steps given below:
temp = start;
start = start -> next;
free(tem p);
Delete at End
If list is empty then display ‘Empty List’ message.
If the list is not empty, follow the steps given below:
temp = prev = start;
while(tem p -> next != NULL)
{
prev = temp;
temp = temp -> next;
}
prev -> next = NULL;
free(tem p);
Delete at intermediate
If list is empty then display ‘Empty List’ message
If the list is not empty, follow the steps given below.
if(pos > 1 && pos < nodectr)
{
temp = prev = start;
ctr = 1;
while(ctr < pos)
{
prev = temp;
temp = temp -> next;
ctr+ + ;
}
prev -> next = temp -> next;
free(tem p);
printf("\n node deleted..");
Double linked list
Insertion at intermediate
Get the new node using getnode().
newnode =getnod e();
If the list is empty then start = newnode.
If the list is not empty, follow the steps given below:
The left field of the new node is made to point the
previous node.
The previous nodes right field must be assigned with
address of the new node.
Insertion at beginning
Get the new node using getnode().
newnode = g e t n o d e();
If the list is empty then start = newnode.
If the list is not empty, follow the steps given below:
newnode -> right = start;
start -> left = newnode;
start = newnode;
At End
Get the new node using getnode()
newnode=getnode();
If the list is empty then start = newnode.
If the list is not empty follow the steps given below:
temp = start;
while(tem p -> right != NULL)
temp = temp -> right;
temp -> right = newnode;
newnode -> left = temp;
At intermediate
Get the new node using getnode().
newnode = g e t n o d e();
Ensure that the specified position is in between first node and
last node. If not, specified position is invalid. This is done by
countnode() function.
Store the starting addres s (which is in start pointer) in temp and
prev pointers. Then travers e the temp pointer upto the specified
position followed by prev pointer.
After reaching the specified position, follow the steps given
below:
newnode -> left = temp;
newnode -> right = temp -> right;
temp -> right -> left = newnode;
temp -> right = newnode;
Delete at begining
If list is empty then display ‘Empty List’ message.
If the list is not empty, follow the steps given below:
temp = start;
start = start -> right;
start -> left = NULL;
free(temp);
At end
If list is empty then display ‘Empty List’ message
If the list is not empty, follow the steps given below:
temp = start;
while(tem p -> right != NULL)
{
temp = temp -> right;
}
temp -> left -> right = NULL;
free(tem p);
Deletion at intermediate
If list is empty then display ‘Empty List’ message.
If the list is not empty, follow the steps given below:
Get the position of the node to delete.
Ensure that the specified position is in betwee n first node
and last node. If not, specified position is invalid.
Then perform the following steps:
if(pos > 1 && pos < nodectr)
{
temp = start;
i = 1;
while(i < pos)
{
temp = temp -> right;
i+ +;
}
temp -> right -> left = temp -> left;
temp -> left -> right = temp -> right;
free(tem p);
printf("\n node deleted..");
}
Transversal and display left to right
If list is empty then display ‘Empty List’ message.
If the list is not empty, follow the steps given below:
temp = start;
while(tem p != NULL)
{
print temp -> data;
temp = temp -> right;
}
Right to left
If list is empty then display ‘Empty List’ message.
If the list is not empty, follow the steps given below:
temp = start;
while(tem p -> right != NULL)
temp = temp -> right;
while(tem p != NULL)
{
print temp -> data;
temp = temp -> left;
}
Creating Circular linked list
Get the new node using getnode().
newnode = getnode();
If the list is empty, assign new node as start.
start = newnode;
If the list is not empty, follow the steps given below:
temp = start;
while(tem p -> next != NULL)
temp = temp -> next;
temp -> next = newnode;
Repeat the above steps ‘n’ times.
newnode -> next = start;
Insertion at beginning
Get the new node using getnode().
newnode = getnode();
If the list is empty, assign new node as start.
start = newnode;
newnode -> next = start;
If the list is not empty, follow the steps given below:
last = start;
while(last -> next != start)
last = last -> next;
newnode -> next = start;
start = newnode;
last -> next = start;
At End
Get the new node using getnode().
newnode = getnode();
• If the list is empty, assign new node as start.
start = newnode;
newnode -> next = start;
If the list is not empty follow the steps given below:
temp = start;
while(tem p -> next != start)
temp = temp -> next;
temp -> next = newnode;
newnode -> next = start;
Delete at begining
If the list is empty, display a message ‘Empty List’.
If the list is not empty, follow the steps given below:
last = temp = start;
while(last -> next != start)
last = last -> next;
start = start -> next;
last -> next = start;
After deleting the node, if the list is empty then start = NULL.
Delete at End
If the list is empty, display a message ‘Empty List’.
If the list is not empty, follow the steps given below:
temp = start;
prev = start;
while(temp -> next != start)
{
prev = temp;
temp = temp -> next;
}
prev -> next = start;
After deleting the node, if the list is empty then start = NULL.
Transversal
If list is empty then display ‘Empty List’ message.
If the list is not empty, follow the steps given below:
temp = start;
do
{
printf("%d ", temp -> data);
temp = temp -> next;
} while(temp != start);
Circular doubly Linked list
Get the new node using getnode().
newnode = getnode();
If the list is empty, then do the following
start = newnode;
newnode -> left = start;
newnode ->right = start;
If the list is not empty, follow the steps given below:
newnode -> left = start -> left;
newnode -> right = start;
start -> left- >right = newnode;
start -> left = newnode;
Repeat the above steps ‘n’ times.
Insertion at beginning
Get the new node using getnode().
newnode = g e t n o d e();
If the list is empty, then
start = newnode;
newnode -> left = start;
newnode -> right = start;
If the list is not empty, follow the steps given below:
newnode -> left = start -> left;
newnode -> right = start;
start -> left -> right = newnode;
start -> left = newnode;
start = newnode;
.
Insertion at End
Get the new node using getnode()
newnode=getnode();
If the list is empty, then
start = newnode;
newnode -> left = start;
newnode -> right = start;
If the list is not empty follow the steps given below:
newnode -> left = start -> left;
newnode -> right = start;
start -> left -> right = newnode;
start -> left = newnode;
[ ] Insertion at intermediate
Get the new node using getnode().
newnode = g e t n o d e();
Ensure that the specified position is in between first node and
last node. If not, specified position is invalid. This is done by
countnode() function.
Store the starting addres s (which is in start pointer) in temp and
prev pointers. Then travers e the temp pointer upto the specified
position followed by prev pointer.
After reaching the specified position, follow the steps given
below:
newnode -> left = temp;
newnode -> right = temp -> right;
temp -> right -> left = newnode;
temp -> right = newnode;
nodectr + + ;
Delete at beginning
If list is empty then display ‘Empty List’ message.
If the list is not empty, follow the steps given below:
temp = start;
start = start -> right;
start -> left = NULL;
free(tem p);
Delete at End
If list is empty then display ‘Empty List’ message
If the list is not empty, follow the steps given below:
temp = start;
while(temp -> right != NULL)
{
temp = temp -> right;
}
temp -> left -> right = NULL;
free(temp);
Delete at given position
If list is empty then display ‘Empty List’ message.
If the list is not empty, follow the steps given below:
Get the position of the node to delete.
Ensure that the specified position is in betwee n first node
and last node. If not, specified position is invalid.
Then perform the following steps:
if(pos > 1 && pos < nodectr)
{
temp = start;
i = 1;
while(i < pos)
{
temp = temp -> right;
i+ +;
}
temp -> right -> left = temp -> left;
temp -> left -> right = temp -> right;
free(tem p);
printf("\n node deleted..");
}
Transversal left to right
If list is empty then display ‘Empty List’ message.
If the list is not empty, follow the steps given below:
temp = start;
while(tem p != NULL)
{
print temp -> data;
temp = temp -> right;
}
Right to left
If list is empty then display ‘Empty List’ message.
If the list is not empty, follow the steps given below:
temp = start;
while(tem p -> right != NULL)
temp = temp -> right;
while(tem p != NULL){
print temp -> data;
temp = temp -> left;
}
Kruskal’s Algorithm for minimal spanning tree
Make the tree T empty.
2. Repeat the steps 3, 4 and 5 as long as T contains less than n - 1
edges and E is not empty otherwise, proceed to step 6.
3. Choose an edge (v, w) from E of lowest cost.
4. Delete (v, w) from E.
5. If (v, w) does not create a cycle in T
then Add (v, w) to T
else discard (v, w)
6. If T contains fewer than n - 1 edges then print no spanning tree.
Warshall
It begins with the adjacency matrix for the given graph, which is called
A0 , and then updates the matrix ‘n’ times, producing matrices called A1 ,
A2 , . . . . . , An and then stops.
In warshall’s algorithm the matrix Ai merely contains information about
the existence of i – paths. A 1 entry in the matrix Ai will correspond to the
existence of an i – paths and O entry will correspond to non- existence.
Thus when the algorithm stops, the final matrix, the matrix An , contains
the desired connectivity information.
A 1 entry indicates a pair of vertices, which are connected, and O entry
indicates a pair, which are not. This matrix is called a reachability matrix
or path matrix for the graph. It is also called the transitive closure of the
original adjacency matrix.
Bfs
Initialize all nodes to the ready state (STATUS = 1).
2. Put the starting node A in QUEUE and change its status to the
waiting state (STATUS = 2).
3. Repeat the following steps until QUEUE is empty:
a. Remove the front node N of QUEUE. Process N and change
the status of N to the processed state (STATUS = 3).
b. Add to the rear of QUEUE all the neighbors of N that are in
the ready state (STATUS = 1), and change their status to the
waiting state (STATUS = 2).
4. Exit.
Dfs
1. Initialize all nodes to the ready state (STATUS = 1).
2. Push the starting node A into STACK and change its status to the
waiting state (STATUS = 2).
3. Repeat the following steps until STACK is empty:
a. Pop the top node N from STACK. Process N and change the
status of N to the processe d state (STATUS = 3).
b. Push all the neighbors of N that are in the ready state
(STATUS = 1), and change their status to the waiting state
(STATUS = 2).
4. Exit.
General tree to binary tree
As a first step, we delete all the branches originating in every
node except the left most branch.
We draw edges from a node to the node on the right, if any,
which is situated at the same level.
Once this is done then for any particular node, we choose its left
and right sons in the following manner:
The left son is the node, which is immediately below the
given node, and the right son is the node to the immediate
right of the given node on the same horizontal line. Such a
binary tree will not have a right subtree
Tree
In Depth first search, we begin with root as a start state, then some
successor of the start state, then some successor of that state, then some
successor of that and so on, trying to reach a goal state. One simple way
to implement depth first search is to use a stack data structure
consisting of root node as a start state.
If depth first search reaches a state S without successors, or if all the
successors of a state S have been chosen (visited) and a goal state has
not get been found, then it “backs up” that means it goes to the
immediately previous state or predec essor formally, the state whose
successor was ‘S’ originally.
Bfs
Breadth-first search starts at root node S and “discovers" which vertices are reachable from S.
Breadth-first search discovers vertices in increasing order of distance. Breadth-first search is named
because it visits vertices across the entire breadth.
Tower of hoinoni
1.Only one disk can be moved at a time.
2.Each move consists of taking the upper disk from one of the stacks and placing it on top
of another stack i.e. a disk can only be moved if it is the uppermost disk on a stack.
3.No disk may be placed on top of a smaller disk.
Algorithm: Procedure for push():
Step 1: START
Step 2: if top>=size-1 then
Write “ Stack is Overflow”
Step 3: Otherwise
3.1: read data value ‘x’
3.2: top=top+1;
3.3: stack[top]=x;
Step 4: END
Algorithm: procedure pop():
Step 1: START
Step 2: if top==-1 then
Write “Stack is Underflow”
Step 3: otherwise
3.1: print “deleted element”
3.2: top=top-1;
Step 4: END
Algorithm: procedure pop():
Step 1: START
Step 2: if top==-1 then
Write “Stack is Underflow”
Step 3: otherwise
3.1: print “Display elements are”
3.2: for top to 0
Print ‘stack[i]’
Step 4: END
Queue
Algorithm: Procedure for insertion():
Step-1:START
Step-2: if rear==max then
Write ‘Queue is full’
Step-3: otherwise
3.1: read element ‘queue[rear]’
Step-4:STOP
Algorithm: procedure for deletion():
Step-1:START
Step-2: if front==rear then
Write’ Queue is empty’
Step-3: otherwise
3.1: print deleted element
Step-4:STOP
Algorithm: procedure for deletion():
Step-1:START
Step-2: if front==rear then
Write’ Queue is empty’
Step-3: otherwise
3.1: for i=front to rear then
3.2: print ‘queue[i]’
Step-4:STOP
Circular Queue
Algorithm: procedure of insertCQ():
Step-1:START
Step-2: if count==MAX then
Write “Circular queue is full”
Step-3:otherwise
3.1: read the data element
3.2: CQ[rear]=data
3.3: rear=(rear+1)%MAX
3.4: count=count+1
Step-4:STOP
Algorithm: procedure of deleteCQ():
Step-1:START
Step-2: if count==0 then
Write “Circular queue is empty”
Step-3:otherwise
3.1: print the deleted element
3.2: front=(front+1)%MAX
3.3: count=count-1
Step-4:STOP
Algorithm: procedure of displayCQ():
Step-1:START
Step-2: if count==0 then
Write “Circular queue is empty”
Step-3:otherwise
3.1: print the list of elements
3.2: for i=front to j!=0
3.3: print CQ[i]
3.4: i=(i+1)%MAX
Step-4:STOP
Bubble sort
Bubble Sort Algorithm:
Step 1: Repeat Steps 2 and 3 for i=1 to 10
Step 2: Set j=1
Step 3: Repeat while j<=n
(A)
if a[i] < a[j] Then
interchange a[i] and a[j]
[End of if]
(B) Set j = j+1
[End of Inner Loop]
[End of Step 1 Outer Loop]
Step 4: Exit
Insertion
Insertion_sort(ARR,SIZE)
Step 1: Set i=1;
Step 2: while(i<SIZE)
Set temp=ARR[i]
J=i=1;
While(Temp<=ARR[j] and j>=0)
Set ARR[j+1]=ARR[i]
Set j=j-1
End While
SET ARR(j+1)=Temp;
Print ARR after ith pass
Set i=i+1
End while
Step 3: print no.of passes i-1
Step 4: end
Quick sort
ALGORITHM
Step 1: Select first element of array as Pivot
Step 2: Initialize i and j to Beg and End elements respectively
Step 3: Increment i until A[i]>Pivot.
Stop
Step 4: Decrement j until A[ j]>Pivot
Stop
Step 5: if i<j interchange A[i] with A[j].
Step 6: Repeat steps 3,4,5 until i>j i.e: i crossed j.
Step 7: Exchange the Pivot element with element placed at j, which is correct place for
Pivot.
Merge sort
Step 1: First divide the combined list into two sub lists as follows.
Step 2: Now Divide the left sub list into smaller sub list
Step 3: Similarly divide the sub lists till one element is left in the sub list.
Step 4: Next sort the elements in their appropriate positions and then combined the sub
lists.
Step 5: Now these two sub lists are again merged to give the following sorted sub list of size
4.
Step 6: After sorting the left half of the array, containing the same process for the right sub
list also. Then the sorted array of right half of the list is as follows.
Step 7: Finally the left and right halves of the array are merged to give the sorted array as
follows.
Insertion Sort
Step 1: Set DATA[N+1]=ITEM
Step 2: Set LOC=1
Step 3: Repeat while (DATA [LOC] != ITEM)
Set LOC=LOC+1
Step 4: if LOC=N+1 then
Set LOC= -1.
Step 5: Exit
Binary search
BINARY SEARCH[A,N,KEY]
Step 1: begin
Step 2: [Initilization]
Lb=1; ub=n;
Step 3: [Search for the ITEM]
Repeat through step 4,while Lower bound is less than Upper Bound.
Step 4: [Obtain the index of middle value]
MID=(lb+ub)/2
Step 5: [Compare to search for ITEM]
If Key<A[MID] then
Ub=MID-1
Other wise if Key >A[MID] then
Lb=MID+1
Otherwise write “Match Found”
Return Middle.
Step 6: [Unsuccessful Search]
write “Match Not Found”
Step 7: Stop.
Singly linked list
Get the new node using getnode().
newnode = getnode();
If the list is empty, assign new node as start.
start = newnode;
• If the list is not empty, follow the steps given below:
• The next field of the new node is made to point the first
node (i.e. start node) in the list by assigning the address of
the first node.
The start pointer is made to point the new node by
assigning the address of the new node.
Repeat the above steps ‘n’ times.
Insertion at beginning
Get the new node using getnode().
newnode = getnode();
If the list is empty then start = newnode.
If the list is not empty, follow the steps given below:
newnode -> next = start;
start = newnode;
The function insert_at_beg(), is used for inserting a node at the
beginning
At End
Get the new node using getnode()
newnode = getnode();
If the list is empty then start = newnode.
If the list is not empty follow the steps given below:
temp = start;
while(temp -> next != NULL)
temp = temp -> next;
temp -> next = newnode;
At intermediate
Get the new node using getnode().
newnode = getnode();
Ensure that the specified position is in between first node and
last node. If not, specified position is invalid. This is done by
countnode() function.
Store the starting addres s (which is in start pointer) in temp and
prev pointers. Then traverse the temp pointer upto the specified
position followed by prev pointer.
After reaching the specified position, follow the steps given
below:
prev -> next = newnode;
newnode -> next = temp;
Let the interme diat e position be 3.
Delete at begining
If list is empty then display ‘Empty List’ message.
If the list is not empty, follow the steps given below:
temp = start;
start = start -> next;
free(tem p);
Delete at End
If list is empty then display ‘Empty List’ message.
If the list is not empty, follow the steps given below:
temp = prev = start;
while(tem p -> next != NULL)
{
prev = temp;
temp = temp -> next;
}
prev -> next = NULL;
free(tem p);
Delete at intermediate
If list is empty then display ‘Empty List’ message
If the list is not empty, follow the steps given below.
if(pos > 1 && pos < nodectr)
{
temp = prev = start;
ctr = 1;
while(ctr < pos)
{
prev = temp;
temp = temp -> next;
ctr+ + ;
}
prev -> next = temp -> next;
free(tem p);
printf("\n node deleted..");
Double linked list
Insertion at intermediate
Get the new node using getnode().
newnode =getnod e();
If the list is empty then start = newnode.
If the list is not empty, follow the steps given below:
The left field of the new node is made to point the
previous node.
The previous nodes right field must be assigned with
address of the new node.
Insertion at beginning
Get the new node using getnode().
newnode = g e t n o d e();
If the list is empty then start = newnode.
If the list is not empty, follow the steps given below:
newnode -> right = start;
start -> left = newnode;
start = newnode;
At End
Get the new node using getnode()
newnode=getnode();
If the list is empty then start = newnode.
If the list is not empty follow the steps given below:
temp = start;
while(tem p -> right != NULL)
temp = temp -> right;
temp -> right = newnode;
newnode -> left = temp;
At intermediate
Get the new node using getnode().
newnode = g e t n o d e();
Ensure that the specified position is in between first node and
last node. If not, specified position is invalid. This is done by
countnode() function.
Store the starting addres s (which is in start pointer) in temp and
prev pointers. Then travers e the temp pointer upto the specified
position followed by prev pointer.
After reaching the specified position, follow the steps given
below:
newnode -> left = temp;
newnode -> right = temp -> right;
temp -> right -> left = newnode;
temp -> right = newnode;
Delete at begining
If list is empty then display ‘Empty List’ message.
If the list is not empty, follow the steps given below:
temp = start;
start = start -> right;
start -> left = NULL;
free(temp);
At end
If list is empty then display ‘Empty List’ message
If the list is not empty, follow the steps given below:
temp = start;
while(tem p -> right != NULL)
{
temp = temp -> right;
}
temp -> left -> right = NULL;
free(tem p);
Deletion at intermediate
If list is empty then display ‘Empty List’ message.
If the list is not empty, follow the steps given below:
Get the position of the node to delete.
Ensure that the specified position is in betwee n first node
and last node. If not, specified position is invalid.
Then perform the following steps:
if(pos > 1 && pos < nodectr)
{
temp = start;
i = 1;
while(i < pos)
{
temp = temp -> right;
i+ +;
}
temp -> right -> left = temp -> left;
temp -> left -> right = temp -> right;
free(tem p);
printf("\n node deleted..");
}
Transversal and display left to right
If list is empty then display ‘Empty List’ message.
If the list is not empty, follow the steps given below:
temp = start;
while(tem p != NULL)
{
print temp -> data;
temp = temp -> right;
}
Right to left
If list is empty then display ‘Empty List’ message.
If the list is not empty, follow the steps given below:
temp = start;
while(tem p -> right != NULL)
temp = temp -> right;
while(tem p != NULL)
{
print temp -> data;
temp = temp -> left;
}
Creating Circular linked list
Get the new node using getnode().
newnode = getnode();
If the list is empty, assign new node as start.
start = newnode;
If the list is not empty, follow the steps given below:
temp = start;
while(tem p -> next != NULL)
temp = temp -> next;
temp -> next = newnode;
Repeat the above steps ‘n’ times.
newnode -> next = start;
Insertion at beginning
Get the new node using getnode().
newnode = getnode();
If the list is empty, assign new node as start.
start = newnode;
newnode -> next = start;
If the list is not empty, follow the steps given below:
last = start;
while(last -> next != start)
last = last -> next;
newnode -> next = start;
start = newnode;
last -> next = start;
At End
Get the new node using getnode().
newnode = getnode();
• If the list is empty, assign new node as start.
start = newnode;
newnode -> next = start;
If the list is not empty follow the steps given below:
temp = start;
while(tem p -> next != start)
temp = temp -> next;
temp -> next = newnode;
newnode -> next = start;
Delete at begining
If the list is empty, display a message ‘Empty List’.
If the list is not empty, follow the steps given below:
last = temp = start;
while(last -> next != start)
last = last -> next;
start = start -> next;
last -> next = start;
After deleting the node, if the list is empty then start = NULL.
Delete at End
If the list is empty, display a message ‘Empty List’.
If the list is not empty, follow the steps given below:
temp = start;
prev = start;
while(temp -> next != start)
{
prev = temp;
temp = temp -> next;
}
prev -> next = start;
After deleting the node, if the list is empty then start = NULL.
Transversal
If list is empty then display ‘Empty List’ message.
If the list is not empty, follow the steps given below:
temp = start;
do
{
printf("%d ", temp -> data);
temp = temp -> next;
} while(temp != start);
Circular doubly Linked list
Get the new node using getnode().
newnode = getnode();
If the list is empty, then do the following
start = newnode;
newnode -> left = start;
newnode ->right = start;
If the list is not empty, follow the steps given below:
newnode -> left = start -> left;
newnode -> right = start;
start -> left- >right = newnode;
start -> left = newnode;
Repeat the above steps ‘n’ times.
Insertion at beginning
Get the new node using getnode().
newnode = g e t n o d e();
If the list is empty, then
start = newnode;
newnode -> left = start;
newnode -> right = start;
If the list is not empty, follow the steps given below:
newnode -> left = start -> left;
newnode -> right = start;
start -> left -> right = newnode;
start -> left = newnode;
start = newnode;
.
Insertion at End
Get the new node using getnode()
newnode=getnode();
If the list is empty, then
start = newnode;
newnode -> left = start;
newnode -> right = start;
If the list is not empty follow the steps given below:
newnode -> left = start -> left;
newnode -> right = start;
start -> left -> right = newnode;
start -> left = newnode;
[ ] Insertion at intermediate
Get the new node using getnode().
newnode = g e t n o d e();
Ensure that the specified position is in between first node and
last node. If not, specified position is invalid. This is done by
countnode() function.
Store the starting addres s (which is in start pointer) in temp and
prev pointers. Then travers e the temp pointer upto the specified
position followed by prev pointer.
After reaching the specified position, follow the steps given
below:
newnode -> left = temp;
newnode -> right = temp -> right;
temp -> right -> left = newnode;
temp -> right = newnode;
nodectr + + ;
Delete at beginning
If list is empty then display ‘Empty List’ message.
If the list is not empty, follow the steps given below:
temp = start;
start = start -> right;
start -> left = NULL;
free(tem p);
Delete at End
If list is empty then display ‘Empty List’ message
If the list is not empty, follow the steps given below:
temp = start;
while(temp -> right != NULL)
{
temp = temp -> right;
}
temp -> left -> right = NULL;
free(temp);
Delete at given position
If list is empty then display ‘Empty List’ message.
If the list is not empty, follow the steps given below:
Get the position of the node to delete.
Ensure that the specified position is in betwee n first node
and last node. If not, specified position is invalid.
Then perform the following steps:
if(pos > 1 && pos < nodectr)
{
temp = start;
i = 1;
while(i < pos)
{
temp = temp -> right;
i+ +;
}
temp -> right -> left = temp -> left;
temp -> left -> right = temp -> right;
free(tem p);
printf("\n node deleted..");
}
Transversal left to right
If list is empty then display ‘Empty List’ message.
If the list is not empty, follow the steps given below:
temp = start;
while(tem p != NULL)
{
print temp -> data;
temp = temp -> right;
}
Right to left
If list is empty then display ‘Empty List’ message.
If the list is not empty, follow the steps given below:
temp = start;
while(tem p -> right != NULL)
temp = temp -> right;
while(tem p != NULL){
print temp -> data;
temp = temp -> left;
}
Kruskal’s Algorithm for minimal spanning tree
Make the tree T empty.
2. Repeat the steps 3, 4 and 5 as long as T contains less than n - 1
edges and E is not empty otherwise, proceed to step 6.
3. Choose an edge (v, w) from E of lowest cost.
4. Delete (v, w) from E.
5. If (v, w) does not create a cycle in T
then Add (v, w) to T
else discard (v, w)
6. If T contains fewer than n - 1 edges then print no spanning tree.
Warshall
It begins with the adjacency matrix for the given graph, which is called
A0 , and then updates the matrix ‘n’ times, producing matrices called A1 ,
A2 , . . . . . , An and then stops.
In warshall’s algorithm the matrix Ai merely contains information about
the existence of i – paths. A 1 entry in the matrix Ai will correspond to the
existence of an i – paths and O entry will correspond to non- existence.
Thus when the algorithm stops, the final matrix, the matrix An , contains
the desired connectivity information.
A 1 entry indicates a pair of vertices, which are connected, and O entry
indicates a pair, which are not. This matrix is called a reachability matrix
or path matrix for the graph. It is also called the transitive closure of the
original adjacency matrix.
Bfs
Initialize all nodes to the ready state (STATUS = 1).
2. Put the starting node A in QUEUE and change its status to the
waiting state (STATUS = 2).
3. Repeat the following steps until QUEUE is empty:
a. Remove the front node N of QUEUE. Process N and change
the status of N to the processed state (STATUS = 3).
b. Add to the rear of QUEUE all the neighbors of N that are in
the ready state (STATUS = 1), and change their status to the
waiting state (STATUS = 2).
4. Exit.
Dfs
1. Initialize all nodes to the ready state (STATUS = 1).
2. Push the starting node A into STACK and change its status to the
waiting state (STATUS = 2).
3. Repeat the following steps until STACK is empty:
a. Pop the top node N from STACK. Process N and change the
status of N to the processe d state (STATUS = 3).
b. Push all the neighbors of N that are in the ready state
(STATUS = 1), and change their status to the waiting state
(STATUS = 2).
4. Exit.
General tree to binary tree
As a first step, we delete all the branches originating in every
node except the left most branch.
We draw edges from a node to the node on the right, if any,
which is situated at the same level.
Once this is done then for any particular node, we choose its left
and right sons in the following manner:
The left son is the node, which is immediately below the
given node, and the right son is the node to the immediate
right of the given node on the same horizontal line. Such a
binary tree will not have a right subtree
Tree
In Depth first search, we begin with root as a start state, then some
successor of the start state, then some successor of that state, then some
successor of that and so on, trying to reach a goal state. One simple way
to implement depth first search is to use a stack data structure
consisting of root node as a start state.
If depth first search reaches a state S without successors, or if all the
successors of a state S have been chosen (visited) and a goal state has
not get been found, then it “backs up” that means it goes to the
immediately previous state or predec essor formally, the state whose
successor was ‘S’ originally.
Bfs
Breadth-first search starts at root node S and “discovers" which vertices are reachable from S.
Breadth-first search discovers vertices in increasing order of distance. Breadth-first search is named
because it visits vertices across the entire breadth.
Tower of hoinoni
1.Only one disk can be moved at a time.
2.Each move consists of taking the upper disk from one of the stacks and placing it on top
of another stack i.e. a disk can only be moved if it is the uppermost disk on a stack.
3.No disk may be placed on top of a smaller disk.
