Algorithms

 

Double Ended Queue

Aim: To write a C program to implement operations on a double ended queue using linked list.

Algorithm:

Function Main():

Step 1: Start

Step 2: Declare the variables needed in the program.

Step 3: Use a while loop and display the options.

Step 4: Read the choice using switch statement and call the appropriate function,

            Case 1: Create()

            Case 2: Insert()

            Case 3: Delete()

            Case 4: Display()

            Case 5: Exit()

Step 5: Stop

Function Create():

Step 1: Allocate memory for a new node using malloc function,

            temp=(struct node*)malloc(sizeof(struct node))

Step 2: Get the data value to be inserted in new node.

Step 3: Assign it link to be null.

Step 4: Check If(start==NULL), then assign start = temp.

Step 5: Otherwise, execute For loop, from ptr=start to ptr->next!=NULL and assign ptr->next = temp.

Function Insert():

Step 1: Print the options - 1.Front and 2.End.

Step 2: Read the option using switch statement and call the appropriate function,

            Case 1: finsert()

            Case 2: einsert()

            Function Finsert():

            Step 1: Allocate a new node using malloc function.

            Step 2: Get the data to be inserted into the node.

            Step 3: Assign address of new node to start and vice versa.

            Function Einsert():

            Step 1: Allocate a new node using malloc function.

            Step 2: Get the data to be inserted into the node.

            Step 3: Using For loop, traverse to the last node.

            Step 4: Assign address of new node to the last node.

Function Delete():

Step 1: Print the options - 1.Front and 2.End.

Step 2: Read the option using switch statement and call the appropriate function,

            Case 1: fdelete()

            Case 2: edelete()

            Function Fdelete():

            Step 1: Traverse the pointer to the header node.

            Step 2: Assign the node to be NULL

            Step 3: Traverse the pointer to next node.

            Function Edelete():

            Step 1: Using For loop, traverse pointer to the last node.

            Step 2: Assign the node to be null.

            Step 3: Again using For loop traverse the node, next-> NULL.

            Step 4: Remove the address of pointer from that node.

Function Display():

Step 1: Using For loop, traverse from header to last node.

Step 2: Print every element in the linked list.

 

Sparse Matirx and Transpose

Aim: To write a C program to implement a Sparse matrix and to transpose it.
Algorithm:
Function Main():
Step 1: Start
Step 2: Declare the necessary vriables and function used in the program.
Step 3: Get the no. of rows and columns - row and col.
Step 4: Using For loop, kand l get the values for the elements in the sparse matrix.
Step 5: Call the function - Implement() and Transpose().
Step 6: Stop

Function Implement():
Step 1: Initialize no. of non-zero values in the matrix, nz to be zero.
Step 2: Execute For loops, k aand l for no. of rows and columns.
Step 3: Check for each element, if(a[k][pl]!=0) is true, then increment nz.
Step 4: End loops k and l respectively.
Step 5: In another matrix-B, assign b[0][0]=row, b[0][1]=col and b[0][2]=nz.
Step 6: Execute For loops, k and l for no. of rows and columns.
Step 7: Assign every elements of Matix A to Matrix B.

Function Transpose():
Step 1: Execute a For loop, from i=0 to i<=b[0][2].
Step 2: In another matrix C, assign c[i][0]=b[i][1],c[i][1]=b[i][0] and c[i][2]=b[i][2] .
Step 3: End loop i.
Step 4: Execute For loops, i=0 to i<=b[0][2] and j=i+1 to j<=b[0][2].
Step 5: Check if(c[i][0]>c[j][0]) is true, then execute a for loop k=0 to k<3.
Step 6: Assign temp = c[i][k], c[i][k]=c[j][k] and c[j][k]= temp.
Step 7: End If and k loop respectively.
Step 8: End loop i and j respectively.
Step 9: Again using for loop i and j, print the elements in the matrix.

 

Dijkstra's Algorithm

Aim: To write a C program to find shortest path using Dijkstra's Algorithm.
Algorithm:
Define IN to be 99 and N to be 6
Function Declaration: Dijkstra()
Function Main():
Step 1: Start
Step 2: Using For loop, i and j from i,j= 1 to N, assign cost[i][j]=IN.
Step 3: Execute For loop, x= 1 to N and y= x+1 to N.
Step 4: Get the weight between two paths.
Step 5: Assign, cost[x][y]=cost [y][x]=w.
Step 6: End loop x and y.
Step 7: Get the source and target for finding shortest path.
Step 8: Call function - Dijkstra()
Step 9: Stop

Function Dijkstra():
Step 1: Using For loop, i= 1 to N, assign dist[i] = IN and prev[i] = -1.
Step 2: Assign start = source, selected[start]=1 and dist[start]=0.
Step 3: Execute While loop, for selected[target]==0.
Step 4: Assign min=IN and m=0.
Step 5: Execute For loop, for i=1 to N, assign d= dist[start] + cost[start][i].
Step 6: Check if(d<dist[i]&&selected[i]==0) is true, then assign dist[i]=d and prev[i]=start.
Step 7: Check if(min>dist[i]&&selected[i]==0) is true, then assign min = dist[i] and m=i.
Step 8: End loop i.
Step 9: Assign start = m and selected[start]=1.
Step 10: End While Loop.
Step 11: Assign start=target and j=0.
Step 12: Using While loop, for start!= -1, assign path[j++]=start+65 and start=prev[start].
Step 13: Assign path[j]=NULL and String reverse (path).
Step 14 Return dist[target].

Selection Sort

Algorithm:

Function Main():

Step 1: Start

Step 2: Declare an array variable and other variables needed.

Step 3: Get the needed size of the array.

Step 4: Read the elements for the array using for loop.

Step 5: Select the first element of the array and compare with all other elements in the array.

Step 6: If first element is greater than any element, then these two elements are interchanged.

Step 7: Repeat Step 5 and Step 6 till every element is sorted.

Step 8: Finally, using for loop, print the sorted elements in the array.

Step 9: Stop

EVALUATION OF ARITHMETIC EXPRESSIONS

AIM:

To develop a program to implement stack application such as conversion of infix to postfix expression.

ALGORITHM:

1. A string INFIX containing the infix expression

2. A stack opstk, which may contain:

                  - All arithmetic operators

                  - Parenthesis " (“ and “) "

                  - Null character " \O "

3. A string POSTFIXES containing the final postfix expression.

4. Push ' \o ' out OPSTACK as its first entry

5. Read the next character CH from the INFIX string

6.Test CH and:

-          If CH is an operand, append it to the POSTFIX string

-          If CH is a left parenthesis, then push CH onto the stack

- If CH is a right parenthesis. then pop entries from stack and append them to POSTFIX until a left parenthesis is  popped. Discard both left and right parentheses.

- If CH is ' \o ', pop all entries that remain on the stack and append them to the POSTFIX string

- Otherwise, pop from the stack and append to the POSTFIX  string ,  whose STACK - PRIORITY is greater than or equal to the INFIX - PRIORITY of CH. Then stack CH.

7. Repeat step (4) and (5) until CH becomes ' \o ‘.

Queue Using Array

Aim: To write a C program to implement the operation on Queue using array.

Algorithm:

Function Main():

Step 1: Start the process

Step 2: Declare the variables choice, front = 0 and rear = -1. Declare the array size for queue as 100.

Step 3: Use while () loop for looping conditions.

Step 4: Read the choice.

Step 5: Use switch statement to perform the following operations:

            Case 1: Enqueue

            Case 2: Dequeue

            Case 3: Display

            Case 4: Exit

Step 6: Stop the process

Function Enqueue()

Step 1: Start

Step 2: Check the condition, if(rear>=size-1)

Step 3: If the condition is true, then print “Queue is Full”

Step 4: Otherwise, Read the element to be inserted in the queue.

Step 5: Stop

Function Dequeue():

Step 1:Start

Step 2: Check the condition, if((rear==front)&&(q[rear]==0))

Step 3: If the condition is true, then print “Queue is Empty”

Step 4: Otherwise remove one element at he front poition of the queue.

Step 5: Increment the front pointer by 1.

Step 6: Stop

Function Display():

Step 1:Start

Step 2: Check the condition , if((rear==front)&&(q[rear]==0))

Step 3: If the condition is true “Queue is empty”

Step 4: Print the element in the queue using the for loop, for(i=front;i<=rear;i++)

Step 5: Stop

PRIORITY Queue

Aim: To write a C program to implement the operation on Priority Queue.
Algorithm:
Function Main():
Step 1: Start the process
Step 2: Declare the variables choice, front = 0 and rear = -1. Declare the array size for queue as 100.
Step 3: Use while () loop for looping conditions.
Step 4: Read the choice.
Step 5: Use switch statement to perform the following operations:
            Case 1: Enqueue
            Case 2: Dequeue
            Case 3: Display
            Case 4: Exit
Step 6: Stop the process


Function Enqueue()
Step 1: Start
Step 2: Check the condition, if(rear>=size-1)
Step 3: If the condition is true, then print “Queue is Full”
Step 4: Otherwise, Read the element to be inserted in the queue.
Step 5: Stop


Function Dequeue():
Step 1:Start
Step 2: Check the condition, if((rear==front)&&(q[rear]==0))
Step 3: If the condition is true, then print “Queue is Empty”
Step 4: Otherwise remove one element at he front poition of the queue.
Step 5: Increment the front pointer by 1.
Step 6: Stop


Function Display():
Step 1:Start
Step 2: Check the condition , if((rear==front)&&(q[rear]==0))
Step 3: If the condition is true “Queue is empty”
Step 4: Print the element in the queue using the for loop, for(i=front;i<=rear;i++)
Step 5: Stop

Function Priority():

Step 1: Start

Step 2: Using for loop, loop the condition from i=front to I <=rear.

Step 3: Again using for loop, loop the condition from j=front to j<rear.

Step 4: Check if(queue[j]>queue[j+1]) is true, then interchange the elements.

Step 5: End loop j.

Step 6: End loop i.

Step 7: End

Circular Queue

Aim: To write a C program to implement the operations of a circular queue.

Algorithm:

Function Main():

Step 1: Start

Step 2: Declare a array of size 50 and declare the variables f=-1,r=0 and s as global variables.

Step 3: Read the size of circular queue.

Step 4: Read the value of choice using switch case statements,

Case 1: Enqueue

            Case 2: Dequeue

            Case 3: Display

            Case 4: Exit

Step 5: Perform the particular function chosen in switch statement.

Step 6: Stop

Function Enqueue():

Step 1: If front is present next to rear, then print “Queue is full”.

Step 2: Read the element to be inserted.

Step 4: If f=-1, then f=r=0.

Step 5: Increment rear pointer and insert the element at q[r].

Funciton Dequeue():

Step 1: Check, if(f==-1) is true, then print “Queue is full”

Step 2: If false, then delete one element at front.

Step 3: If front is equal to rear, then q[f]=0.

Step 4: If front is not equal to rear, then increment front pointer by one.

Function Display():

Step 1: Assign i=f.

Step 2: Check if(i==-1) is true, then print “Queue is Empty”.

Step 3: If false, print the elements in the array.

 Implementation of Doubly Linked List

Aim: To write a C program o implement the doubly linked list using structure.

Algorithm:

Function Main():

Step 1: Start the process

Step 2: Create a structure in node to handle the linked list globally.

Step 3: Declare the pointer variable *next,*prev and create the objects for the structure.

Step 4: Using while() loop display the options to perform particular function,

            Case 1: Create()

            Case 2: Insert()

            Case 3: Delete()

            Case 4: Display()

            Case 5: Exit()

Step 5: Read the value of choice using switch statement and call particular function.

Step 6: Stop the process.

Function Create():

Step 1: Using malloc function create the link list having left and right address field.

Step 2: The datas are entered to the list

Step 3: The address of the first node created is stored in the header part.

Step 4: Check if(Start == NULL) is true, then create the list using the above operation.

Step 5: If false, then the list is created and the address is stored to the link field.

Function Insertion():

Step 1: Insertion of data into the list takes place in three ways.

Step 2: To perform insertion, select any one of the following, 1.Front, 2. Middle and3. End.

Step 3: Read the option using switch statement, and call the particular function.

            Function Front Insert():

            Step 1: Get the data value for the new node.

Step 2: Assign start address to left link of the new node and address of new node to start.

Step 3: Assign address stored in start to right link of the new node.

           

            Function Middle insert():

            Step 1: Get the data value for the new node.

            Step 2: Get the key node, after which the new node has to be inserted.

            Step 3: Search the key node using for loop, and insert the new node after it.

           

            Function End insert():

            Step 1: Get the data value for the new node.

            Step 2: Assign right link of the new node to be NULL

Step 3: Traverse to the last node using for loop, and assign the address to new node.

Function Deletion():

Step 1: Deletion of data from the list takes place in three ways.

Step 2: To perform deletion, select any one of the following, 1.Front, 2. Middle and3. End.

Step 3: Read the option using switch statement, and call the particular function.

            Function Front delete():

            Step 1: Using pointer traverse to first node.

Step 2: Assign the address stored right link of the first node to start.

Step 3: Remove the address of first node from start and second node.

           

            Function Middle delete():

            Step 1: Get the key node, which is to be deleted.

Step 3: Search the key node using for loop, and remove the address of that node stored in previous and next node.

           

            Function End delete():

            Step 1: Using for loop traverse to the node before end node.

            Step 2: Assign the right link of that node to be NULL.

Function Display():

Step 1: Check if(start==NULL) is true, print “Linked list is empty”

Step 2: If false, using for loop, for(ptr=start;ptr->next!=NULL;ptr=ptr->next)

Step 3: Print the linked list elements.

CIRCULAR Linked List

Aim: To write a C program to implement the circular linked list using structure.
Algorithm:
Function Main():
Step 1: Start the process
Step 2: Create a structure in node to handle the linked list globally.
Step 3: Declare the pointer variable *next,*prev,*temp,*ptr and create the objects for the structure.
Step 4: Using while() loop display the options to perform particular function,
            Case 1: Insertion()
            Case 2: Deletion()
            Case 3: Display()
            Case 4: Exit()
Step 5: Read the value of choice using switch statement and call particular function.
Step 6: Stop the process.


Function Insert():
Step 1: Using malloc function create the link list having an address field.
Step 2: The data is entered to the data field.
Step 3: The address of the first node created is stored in the header part.
Step 4: Check if(Start == NULL) is true, then create the list using the above operation.
Step 5: If false, then the list is created and the address is stored to the link field.


Function Deletion():
Step 1: Check if(start==NULL) is true, print “Circular Linked list is empty”
Step 2: Get the data - e of the node to be deleted.
Step 3: If(start->data== e), then move the pointer to next node and assign to start.
Step 4: Otherwise, using for loop traverse the node containing the data.
Step 5: Remove the address of that node from previous node and assign address of next node.


Function Display():
Step 1: Check if(start==NULL) is true, print “Circular Linked list is empty”
Step 2: If false, using for loop, for(ptr=start;ptr->next!=NULL;ptr=ptr->next)
Step 3: Print the linked list elements.

Binary Tree Traversal

Algorithm:

Function Main():

Step 1: Start

Step 2: Declare the variables need and structure for node.

Step 3: Get the number of nodes - n in the tree and the items are inserted for n times using the function insert().

Step 4: Call the functions preorder(), postorder() and inorder() to perform the respective operations.

Step 5: Stop

Function Insert():

Step 1: Check if((*temp) == NULL) is true, then print “Leaf node is created”

Step 2: Assign left and right as NULL and num value for data.

Step 3: If false, check if(num ==(*temp->data)) is true, then value are same.

Step 4: For next insertion, check if(num<=(*temp->data)) is true, then link data to left otherwise to right.

Function Inorder():

Step1: Check if(temp!=NULL) is true, then perform the following actions.

Step 2: Traverse the left sub-tree in Inorder

Step 3: Visit the root node.

Step 4: Traverse the right sub-tree in Inorder.

Step 5: Otherwise return.

Function Preorder():

Step 1: Check if(Temp!=NULL) is true, then perform the following actions,

Step 2: Visit the root node.

Step 3: Traverse the left sub-tree in pre-order.

Step 4: Traverse the right sub-tree in pre-order.

Step 5: Otherwise return.

Function Postorder():

Step 1: Check if (temp!=NULL) is true, then perform the ollowing actions,

Step 2: Traverse the left sub tree.

Step 3: Traverse the rigth sub tree

Step 4: Visit the root node.

Step 5: Otherwise return.

BREADTH FIRST SEARCH

Algorithm:
Function Main();
Step 1: Start
Step 2: Declare the variables globally used in the program.
Step 3: Get the no. of nodes to be inserted – n.
Step 4: Using for loop from i=0 to i<=n, assign v[i]=0.
Step 5: Again using for loop, from j=0 to j<=n, assign a[i][j]=0.
Step 6: End loop j and i respectively.
Step 7: Using Do loop, perform,

1)      Get the links between two nodes.

2)      Get the option – c, to continue.

3)      Flushall()

While(c==’y’)

Step 8: Using For loop, from i=1 to i<=n, assign v[i]=0.
Step 9: Assign r=1,f=0,q[0]=1.
Step 10: Call Function – Bfss()
Step 11: Stop


Function Bfss():
Step 1: Print – cc.
Step 2: Using While loop, check if(f!=r), then perform the following steps.
Step 3: Assign cc=q[f] and f=f+1.
Step 4: Perform For loop, from i=1 to i<=n.
Step 5:Check if((a[cc][i]==1)&&(v[i]==0))
Step 6: Print – I and assign v[i]=0 and q[r++]=i.
Step 7: End For loop.
Step 8: End While.

DEPTH FIRST SEARCH

Algorithm:
Function Main();
Step 1: Start
Step 2: Declare the variables globally used in the program.
Step 3: Get the no. of nodes to be inserted – n.
Step 4: Using for loop from i=0 to i<=n, assign v[i]=0.
Step 5: Again using for loop, from j=0 to j<=n, assign a[i][j]=0.
Step 6: End loop j and i respectively.
Step 7: Using Do loop, perform,

1)      Get the links between two nodes.

2)      Get the option – c, to continue.

3)      Flushall()

While(c==’y’)

Step 8: Call Function – Dfss()
Step 9: Stop


Function Dfss():
Step 1: Assign v[cc]=1.
Step 2: Print – cc.
Step 3: Perform For loop, from j=1 to j<=n.
Step 4: Check if ((a[cc][j]==1)&&(v[j]==0) is true, then call function Dfss().

STACK USING LINKED LIST

Algorithm:

Function Main():

Step 1: Start

Step 2: Declare the variables and functions using structure.

Step 3: Using while loop display the options,

            Case 1: Create

            Case 2: Push

            Case 3: Pop

            Case 4: Display

            Case 5: Exit

Step 4: Read the options using switch statement and call the particular function.

Function Create():

Step 1: Check if(head==NULL)

Step 2: If true, then allocate memory space for new node as,

            N=(struct list*)malloc(sizeof(struct list))

Function Push():

Step 1: Allocate memory for the node to be inserted,

            N=(struct list*)malloc(sizeof(struct list))

Step 2: Get the data value for the new node.

Step 3: Assign, n->link=NULL, n->link=head and head =n

Function Pop():

Step 1: Initialize i=1.

Step 2: If dum=head, then assign, head = head->link, then the data is deleted.

Step 3: Then display the deleted element in list using switch statement.

Function Display();

Step 1: Using while loop, for dum!=NULL.

Step 2: Display the present element.

Step 3: Check if(head == NULL), then print “NULL”

Step 4: Otherwise print – “Stack is empty”