Pseudo Codes 3rd Sem Ds Lab

Adhit Mukesh Shet

[email protected]

Pseudo Codes Program Number 14 Write a recursive C program for searching an element on a given list of integers using binary search method and for solving the tower of Hanoi problem Logic Binary Search Function Input Search Element Output Position of the search element if found, else inform the user that the search element was not found. Logic 1. Assign the variable 'low' to the position of the first element and also assign the variable 'high' to the position of the last element (To be done in the Main function) 2. Whenever 'low' is greater than 'high' the search fails, i.e. the search element is not found. 3. The position of the middle element is obtained by the statement below and is saved in the variable 'mid' mid=(low+high)/2 4. If the search element is found at 'mid' position return variable 'mid' 5. If the search element is less than middle element then the elements in the left part have to be compared ranging from 'low' to 'mid-1' 6. If not then the elements in the right part of the array has to be compared from 'mid +1' to 'high' Tower of Hanoi Function Input Number of discs Output Solution to the Tower of Hanoi problem Logic 1. In case the number of discs are 1 then output would be 'Move disc n form source_needle to destination_needle. 2. If not then do steps 3-5 3. Move n-1 discs recursively from source_needle to temp_needle 4. Move disc n from source_needle to destination_needle 5. Move n-1 discs from temp_needle to destination_needle

Adhit Mukesh Shet

[email protected]

WAP to construct a binary search tree of integers , to traverse the tree using all methods Insert Function Logic 1. 2. 3. 4. 5.

Dynamically create a node and save it as the variable 'temp' Update the information part of this node to the input element Update the left and right link of this node as NULL If the 'root' variable is NULL then assign 'temp' to 'root'. Assign 'root' to 'cur', use this variable to traverse the linked list till the information part of the node is not equal to input element and till the node is not equal to NULL. Do steps 6-7 (cur points to the current node) 6. Assign the 'cur' to the variable 'prev'(prev points to the previous node) 7. If the input element is less than the information part of the current node then update 'cur' to the left link of the current node else update it to the right link of the current node 8. If the input element is less than the information part of the previous node, then update the left link of the previous node as NULL else update the right link of the previous node as NULL

Inorder Traversal Logic 1. 2. 3. 4. 5.

If 'root' is NULL then return control to the calling function If not then do steps 3-5 Traverse the left subtree in inorder Print the root node Traverse the right subtree in inorder

Preorder Traversal Logic 1. If 'root' is NULL then return control to the calling function 2. If not then do steps 3-5 3. Print the root node 4. Traverse the left subtree in preorder 5. Traverse the right subtree in preorder Postorder Traversal Logic 1. If 'root' is NULL then return control to the calling function 2. If not then do steps 3-5 3. Traverse the left subtree in postorder 4. Traverse the right subtree in postorder 5. Print the root node

Adhit Mukesh Shet

[email protected]

WAP to support the following operations on a doubly linked list where each node consists of integers 1. Create a doubly linked list be adding each node at the front 2. Insert a new node to the left of the node whose key value is read as input 3. Delete the node of the given data, if it is found, other wise display appropriate message 4. Display the contents of the linked list Function to insert at the front of the linked list Logic 1. 2. 3. 4. 5. 6. 7.

Dynamically create a node On successful creation of the node do steps 3-6 else go to step 7 Assign 'first' to the right link of this node Update the left link of the first node to this node Initialize the left link of this node as NULL Take the value of the node from the user and save it in the information part of this node Return the node first to the calling function

Function to insert at the left of the specified node Logic 1. 2. 3. 4.

Dynamically create a node On successful creation of the node do steps 3-13 else go to step 14 Take the value of the specified node from the user If the first node is NULL or if the first node is the specified node then call the insert at the front of the linked list function 5. If not then assign the first node to 'trv' 6. While 'trv' is not equal to NULL and the 'trv' is not the specified node assign the value of the right link of 'trv' to trv ( Do this to traverse the linked list and find the specified node) 7. If 'trv' is not NULL then do steps 8-12 else go to step 13 8. Take the value of the new node from the user 9. Update the left link of the new node to the left link of the node 'trv' 10. Update the right link of the new node to 'trv' 11. Update trv to the left link of the new node 12. Update the right link of 'trv' to the new node. Go to step 14 13. Inform the user that the specified node was not found in the linked list 14. Return the node first to the calling function. Function to delete the specified node Logic 1. If first node is NULL then inform the user that the linked list is empty. 2. Assign first node to 'trv' 3. While 'trv' is not equal to NULL and the 'trv' is not the specified node assign the value of the right link of 'trv' to 'trv'(Do this to traverse the linked list and find the specified node) 4. If 'trv' is NULL then inform the user that the specified node was not found.

Adhit Mukesh Shet

[email protected]

5. If not then do steps 6-10 6. Assign the value of the left link of the current node 'trv' to prev and also assign the value of the right link of the current node 'trv' to next 7. Update right link of the previous node 'prev' as the next node 'next' 8. Update the left link of the next node 'next' as the previous node 'prev' 9. If the first node is the specified node then assign the current node as first. 10. Return the first node to the calling function Display Function Logic 1. 2. 3. 4.

If the first node is NULL then inform the user that the liked list is empty If not then do steps 3-4 Assign first node to 'trv' While trv is not equal to NULL print the contents of the node and also update the value of the node 'trv' to its right link

Adhit Mukesh Shet

[email protected]

WAP using dynamic variables and pointers, to construct a singly linked list consisting of the following information in each node: Student ID, Student Name and Semester. The operations to be supported are 1. The insertion operation 1. At the front of the list 2. At the back of the list 3. At any position in the list 2. Deleting a node based on ID. If the specified node is not found then display an error message 3. Searching a node based on student ID and update the information content. If the specified node is not found then display an error message 4. Displaying all nodes in the list Function to insert at the front of the list Logic 1. Dynamically create a node 2. On successful creation of the node do steps 3-5 else go to step 6 3. Assign 'first' to the link of this node 4. Take the Student ID, Student Name and Semester from the user and save it in the information part of this node 5. Assign this node as first 6. Return the node first to the calling function Function to insert at the back of the list Logic 1. Dynamically create a node 2. On successful creation of the node do steps 3-8 else go to step 9 3. Assign first node to 'trv' 4. While the link of trv is not equal to NULL update the value of the node 'trv' to its link 5. Assign the link of this node as NULL 6. Assign the link of trv as this node 7. Take the Student ID, Student Name and Semester from the user and save it in the information part of this node 8. If first is NULL then assign this node as first 9. Return the node first to the calling function Function to insert at any position in the list Logic 1. Dynamically create a node 2. On successful creation of the node do steps 3-13 else do step 13 3. Take the value of the position at which the new node has to be inserted from the user 4. If this position is 1 then call the insert at the front of the linked list function 5. If not then do steps 6-13 6. Assign first to 'trv' and also assign NULL to 'prev' 7. While trv is not NULL and the counter 'pos' is not equal to the input position assign the link of trv to trv, update the counter pos and also assign the value of trv to prev 8. If trv is NULL then inform the user that the input position is illegal and go to step 9. If not then do steps 10-12 else do step 13 10. Assign the link part of the node prev to the dynamically created node

Adhit Mukesh Shet

[email protected]

11. Assign the link part of this node as trv 12. Take the Student ID, Student Name and Semester from the user and save it in the information part of this node 13. Return the node first to the calling function Function to delete a node based on Student ID Logic 1. Take the value of the Student ID from the user 2. If the node first is NULL then inform the user that the linked list is empty and to return control to the calling function 3. If not then assign first to 'trv' and assign NULL to 'prev' 4. While 'trv' is not NULL and Student ID of the trv is not input Student ID assign the link of trv to trv and assign trv to prev 5. If the node trv is NULL then inform the user that the required node was not found in the list and return the control to the calling function 6. If not then assign the link part of prev as the link part of trv 7. Free the node trv 8. Return control to the calling function Function to Search and update a node based on Student ID Logic 1. Take the value of the Student ID from the user 2. If the node first is NULL then inform the user that the linked list is empty and to return control to the calling function 3. If not then assign first to 'trv' 4. While 'trv' is not NULL and Student ID of the trv is not input Student ID assign the link of trv to trv 5. If the node trv is NULL then inform the user that the required node was not found in the list and return the control to the calling function 6. If not then take the new Student ID, Student Name and Semester from the user and update the information part of this node 7. Return the control to the calling function Function to display the contents of the linked list Logic 1. 2. 3. 4.

If the first node is NULL then inform the user that the linked list is empty If not then do steps 3-4 Assign first node to 'trv' While trv is not equal to NULL print the contents of the node and also update the value of the node 'trv' to its link 5. Return the control to the calling function

Adhit Mukesh Shet

[email protected]

WAP to implement Queues using Linked list Q Insert Function Logic 1. 2. 3. 4. 5. 6. 7. 8. 9.

Dynamically create a node On successful creation of the node do steps 3-8 else go to step 9 Assign first node to 'trv' While the link of trv is not equal to NULL update the value of the node 'trv' to its link Assign the link of this node as NULL Assign the link of trv as this node Take the value from the user and save it in the information part of this node If first is NULL then assign this node as first Return the node first to the calling function

Q Delete Function Logic 1. 2. 3. 4. 5.

If the first node is NULL then inform the user that the linked list is empty If not then assign the value of first to dump Update first to the link of first Free dump Return the node first to the calling function

Q Display Function Logic 1. 2. 3. 4.

If the first node is NULL then inform the user that the linked list is empty If not then do steps 3-4 Assign first node to 'trv' While trv is not equal to NULL print the contents of the node and also update the value of the node 'trv' to its link 5. Return the control to the calling function

Adhit Mukesh Shet

[email protected]

WAP to implement Stacks using Linked Lists Push Function Logic 1. 2. 3. 4. 5. 6.

Dynamically create a node On successful creation of the node do steps 3-5 else go to step 6 Assign 'first' to the link of this node Take the value from the user and save it in the information part of this node Assign this node as first Return the node first to the calling function

Pop Function Logic 1. 2. 3. 4. 5. 6.

If the first node is NULL then inform the user that the linked list is empty If not then assign the value of first to dump Update first to the link of first Display the information contained in the node dump. Free dump Return the node first to the calling function

Display Function Logic 1. 2. 3. 4.

If the first node is NULL then inform the user that the linked list is empty If not then do steps 3-4 Assign first node to 'trv' While trv is not equal to NULL print the contents of the node and also update the value of the node 'trv' to its link 5. Return the control to the calling function

Adhit Mukesh Shet

[email protected]

WAP to stimulate the working of a circular queue of integers using an array. Provide the following operations I. Insert II. Delete III. Display Insert Function Logic 1. If count(the variable indicating the number of values present in the circular queue ) is maximum then inform the user that the circular queue is full. 2. If not then take the value to be inserted into the circular queue from the user 3. Update the location of the rear of the queue using modulus addition. i.e. rear = (rear+1)%MAX (where MAX indicates the maximum number of values the circular queue can hold) 4. Save the input value at the rear of the circular queue 5. Increment the variable 'count' Delete Function Logic 1. If count is 0 then inform the user that the circular queue is empty 2. If not then display the element located at the front of the queue. 3. Delete this element by updating the front of the queue using modulus addition i.e.front=(front +1)%MAX(where MAX indicates the maximum number of values the queue can hold) 4. Decrement the variable 'count' Display Function Logic 1. 2. 3. 4. 5.

If the count is 0 then inform the user that the circular queue is empty If not then assign front to trv For count number of times do steps 4-5 Display the value located at location in the circular queue pointed to at by trv Update the value of trv by modulus addition i.e. trv=(trv+1)%MAX

Adhit Mukesh Shet

[email protected]

WAP to stimulate the working of queue of integers using an array. Provide the following options on it i. Insert ii. Delete iii. Display Insert function Logic 1. If the maximum number of values the array can take is rear+1, then inform the user that the queue is full 2. If not then increment the rear by 1 3. Take the element to be entered into the queue from the user. 4. Save this element at the rear of the queue 5. If front of the queue is -1 then increment it by 1 Delete Function Logic 1. If front is -1 or if front is greater than the rear then inform the user that the queue is empty. Also assign both front and rear of the queue to -1 2. If not then display the front of the queue. This is the element to be deleted. 3. Increment the front of the queue by one. Display Function Logic 1. If front is -1 or if front is greater than the rear then inform the user that the queue is empty. Also assign both front and rear of the queue to -1 2. If not then display every array element from front of the queue to its rear

Adhit Mukesh Shet

[email protected]

WAP to evaluate a valid postfix expression using stack. Assume that the postfix expression is read as a single line consisting of non negative single digit operands and binary arithematic operators like plus, minus, multiply and divide. Input : Postfix Expression Output: Evaluated result of the postfix expression Evaluation function Logic 1. 2. 3. 4. 5. 6. 7. 8.

Read each character from the postfix expression If the characters are operands then push them into the stack If the characters are operators then do steps 4-7 Pop an operand from the stack and save it as operand2 Pop another operand from the stack and save it as operand1 Perform the required operation on operand1 and operand2 Push the result obtained into the stack Do the steps 1-7 till the end of the postfix expression i.e. until '\0' is encountered

Push function Logic 1. Increment the top variable 2. Read the character of the postfix expression to be entered into the stack 3. Save this character at the top of the stack Pop Function Logic 1. Return the character saved at the top of the stack to the calling function 2. Decrement the top of the stack

Adhit Mukesh Shet

[email protected]

WAP which accepts the IP address in decimal dot format and converts it into 32 bit long integer using strtok library function and unions Logic 1. Take the IP address in the dot format from the user 2. Use the strtok function to separate the IP address into different fields 3. Pass the variable name of the IP address when calling the strtok function for the 1st time, from then on pass NULL as the 1st argument. The field separator “.” is to passed as the 2nd argument in all cases. 4. Use the strtol function to convert each field into its 32bit long integer form. Pass the string name, the end pointer and radix as its arguments 5. Print the 32 bit long integer value of the given IP address

Adhit Mukesh Shet

[email protected]

Write a C program to construct an array of integers and to perform the following operations on it. (i) Insert (ii) Delete (iii) Search by an item (iv)Search by position (v) Display Pseudo Code Search Function Input Search element Output Notify the user if Search was successful or not. If the search was successful then do display the position of the found element Logic 1. Read the Search element 2. Search If the search element is in the given array using Linear Search 3. From the base address of the array till the last element in the array which is pointed to by the no. of elements variable, read every element and check if the array element is equal to the given search element 4. If the given search element is found ,then note the position of the element in the array and display it to the user 5. If the search is not successful then notify the user Delete Function Input To delete by position or by element, if to delete by position then the position of the element to be deleted in the array. If to be deleted by element, then search function Output If to delete by element then notify the user if the element in not found in the array Logic 1. Ask the user if we have to delete by position or by element 2. If an element has to be deleted by position then ask the user to enter the position. 3. Read the position. 4. To delete an element at the given position, read the array content at (position +1) location. Copy the contents of this location to the given position. Do so forth till the last array element is moved one location forward. 5. Decrement the count of number of array elements by one. 6. To delete by element, ask the user to enter the element. 7. Read the element 8. Call the Search function to find if the element exists in the array. In case the element does not exist then notify the user. 9. In case the element exists in the array then delete the element by transferring the contents of the next array element into its location and so forth 10. Decrement the count of number of array elements by one. Insert Function Input The position at which the element is to be inserted, the element to be inserted Output nil Logic 1. Ask the user to enter the position where the element is to be inserted. 2. Read the position

Adhit Mukesh Shet

[email protected]

3. Read the last element in the string and copy its value to its immediate next location. Now read the last but one location and copy its contents to the immediate next location. Do so forth till the required position is reached. 4. Ask the user to enter the element to be inserted and save it at the given position 5. Increment the count of number of array elements by one. Search by Position Function Input The position of the Search element Output If the position is a valid one then output the search element else notify the user that it is an invalid choice. Logic 1. Ask the user to enter the position of the search element 2. Read the position 3. If the position of the search element is greater than the number of the elements in the array, notify the user about the error 4. If not then display the element present at the given Search position Display Function Input The base address of the array, number of elements in the array Output The contents of the Array. Logic 1. Read the base address of the array 2. Read the maximum number of array elements 3. From 0th element of the array till the last element of the array, print the value of the array elements on the console.

Adhit Mukesh Shet

[email protected]

Write and demonstrate the following functions: i) newStrCpy that does the same job as strcpy ii) newStrCat that does the same job as strcat without using any library functions. Pseudo Code String copy Function Input Input string Output Copied String and the Input String Logic 1. Read the Input String. 2. Begin from the start of the string, read every character of the input string and copy it to another string till ‘\0’ is encountered 3. When ‘\0’ is encountered in the input string, come out of the loop. 4. Append ‘\0’ to the end of the Copied String String Concatenate Function Input The two input strings Output The concatenated string Logic 1. Read the 2 input Strings 2. From the 1st element of the String, Increment the counter of the 1st string till ‘\0’ is reached 3. Replace ‘\0’ with a blank space ‘ ‘ 4. Increment the counter of the 1st array once. 5. Now read every character of the 2nd string from the start and copy it to the present counter location in the 1st string 6. Do this till ‘\0’ is encountered in the 2nd String. 7. Now append ‘\0’ to the end of the 1st String. 8. The 1st String is now the concatenated String.

Adhit Mukesh Shet

[email protected]

Sequential File containing Student Records Pseudo Code Function to create records Input Number of Records, record details like Student id number, name, Marks scored in 3 subjects Output Save the record details in a file Logic 1. Read the number of records the User wants to create 2. Open a file in write mode 3. From 0 to the number of record times loop steps 4-9. 4. Read the Student id Number 5. Read the Student Name 6. Read Marks1 7. Read Marks2 8. Read Marks3 9. Write these Student Details in the file. 10. Close the file. Function to display the records Input File, number of records Output Student record details like Student id, name, Marks 1, Marks2, Marks 3 Logic 1. Open the file in read mode 2. To display the Student Records in a table like format display the Column Headers. 3. From 0 to the number of record times loop steps 4-10 4. Read the Student id from the file 5. Display it at the console 6. Read the Student Name from the file 7. Display it at the console 8. Read Marks1 from the file and display it at the console 9. Read Marks2 from the file and display it at the console 10. Read Marks3 from the file and display it at the console 11. Close the file Function to Search for a specific record based on ID Input Search element, File, Number of records Output To display the specific record if found else notify the user of the unsuccessful search Logic 1. Read the ID number whose records details have to be displayed 2. Open the file in read mode 3. From 0 to the number of record times loop steps 4-6 4. Read the Student ID from the file 5. Check if the given ID number and the ID number read from the file is the same 6. If so then display the Student record details like Student Name, Marks1, Marks2 and Marks3 7. If the given ID has no match in the file then notify the user that the search has been unsuccessful 8. Close the file

Adhit Mukesh Shet

[email protected]

Write a C program to construct a stack of integers and to perform the following operations on it: Push Pop Display The program should print appropriate messages for stack overflow, stack underflow and stack empty. Pseudo Code Push Function Input Maximum number of Stack elements, the element to be pushed into the Stack, top Output Notify the user if Stack Overflow conditions exist. Logic 1. Check if the Stack is full i.e. for Stack Overflow condition 2. If the Stack Overflow condition exists then notify the user 3. If the Stack is not full then increment the value of the top variable 4. Ask the user to enter the variable to be pushed into the stack 5. Read this element and save it at the location in the stack pointed to by the top variable Pop Function Input Maximum number of Stack elements, top Output Notify the user if Stack Underflow conditions exist, the element to be deleted. Logic 1. Check if the Stack is empty i.e. for Stack underflow conditions 2. If the Stack Underflow conditions exist then notify the user 3. If the Stack Underflow conditions do not exist then notify to the user the element to be deleted from the stack Decrement the top variable Display Function Input Top Output Notify the user if the Stack is empty, the stack elements Logic 1. Check if the Stack is empty 2. If so notify the user that the Stack is empty 3. If not, then read the contents of the stack pointed to at by the top variable decrementing it till 0. Print these values on the console.

Adhit Mukesh Shet

[email protected]

Write a C program to convert and print a given valid parenthesized infix arithmetic expression to postfix expression. The expression consists of single character operands and the binary operators + (plus), - (minus), * (multiply) and / (divide). Precedence Function Input Operator Output Precedence Value Logic 1. Read the operator from the String 2. If ‘$’ or ‘^’ is the operator then precedence value is 3 3. If ‘/’ or ‘*’ is the operator then precedence value is 2 4. If ‘+’ or ‘-‘ is the operator then precedence value is 1 5. If ‘(‘ is the input then precedence value is 0 6. For ‘#’ the precedence value is -1 Push Function Logic 1. Increment the value of the top pointer variable 2. The value to be pushed into the stack is read from the calling function 3. This variable is saved at the location in the stack pointed at by top pointer variable Pop Function Logic 1. Return the value of the stack element pointed at by the top pointer variable to the calling function 2. Decrement the value of the top pointer variable Infix to Postfix Function Logic 1. Push ‘#’ into the stack 2. Till the infix expression is ‘\0’ do steps 3-14 3. If the infix expression is ‘(‘ push it into the Stack 4. If the infix expression is ‘)’ do steps 5-7 5. Till the stack element is not ‘(‘ do steps 6-7 6. Pop the element from the stack into the postfix string 7. Increment the postfix counter 8. If $,^,*,/,+ or – operators are encountered then do steps 9-12 9. Check if the precedence value of the stack element is greater than or equal to the precedence value of the infix element then do steps 10-11 10. Pop the element into the postfix string 11. Increment the postfix counter 12. Push the infix element into the stack 13. Else pass the character into the postfix array 14. Increment the infix array counter 15. Till the stack element is not ‘#’ do steps 16-17 16. Pop an element from the stack and put it into the postfix array 17. Increment the postfix array counter 18. Save ‘\0’ in the postfix array