CS2092D Assignment #6 Solution

QUESTIONS

1. A Singly linked list L is a data structure in which the objects are arranged in a linear order. Each node of a Singly linked list L is an object with an attribute key and one pointer attribute, next. Given a node x in the list, x.next points to its successor in the linked list. An attribute L.head points to the first node of the list.
Write a menu driven program to implement an unsorted Singly linked list L. Your program must contain the following functions:
(In the function prototypes, L, k, x and y denote a Singly Linked List, an integer and nodes of L respectively. All operations should be done in a single pass and all keys are distinct).
• Main() - repeatedly reads a character ‘f’, ‘t’, ‘a’, ‘b’, ‘d’, ‘i’, ‘l’, ‘s’ or ‘e’ from the terminal and calls the sub-functions appropriately until character ‘e’ is entered.
• CREATE-NODE(k) - creates a new node with key k and pointer next of node points to NULL. This procedure returns a pointer to the new node.
• LIST-INSERT-FRONT(L,x) - inserts x to the front of L.
• LIST-INSERT-TAIL(L,x) - inserts x as the last node of L.
• LIST-INSERT-AFTER(L,x,y) - inserts the node x after the node y in L.
Hint: First invoke LIST-SEARCH() function to locate the node y.
• LIST-INSERT-BEFORE(L,x,y) - inserts the node x before the node y in L.
Hint: Insertion of a node x before a node y can be done by locally storing a pointer to the current node before moving to the next node.
• LIST-DELETE(L,x) - deletes the node x from L.
Hint: First invoke LIST-SEARCH() function to locate the node x.
• LIST-DELETE-FIRST(L) - deletes the first node from L.
• LIST-DELETE-LAST(L) - deletes the last node from L.
• LIST-SEARCH(L,k) - searches for a node with key k in L by doing a simple linear search, and if found, returns a pointer to this node. If a node with key k is not present in the list, or if the list is empty, the procedure returns NIL.
Note:- For every INSERT operation, the node x is created by calling CREATE-NODE() function.
Input format:
• Each line contains a character from ‘f’, ‘t’, ‘a’, ‘b’, ‘d’, ‘i’, ‘l’, ‘s’ or ‘e’ followed by zero, one or two integers. The integers, if given, are in the range [−106,106].
• Character ‘f’ is followed by an integer separated by space. In this operation, the node with this integer as key is inserted to the front of L.
• Character ‘t’ is followed by an integer separated by space. In this operation, the node with this integer as key is inserted to the tail of L.
• Character ‘a’ is followed by two integers separated by space. In this operation, the node with the first integer as key is inserted after the node with second integer as key.
• Character ‘b’ is followed by two integers separated by space. In this operation, the node with the first integer as key is inserted before the node with second integer as key.
• Character ‘d’ is followed by an integer separated by space. In this operation, the node with this integer as key is deleted from L and the deleted node’s key is printed.
• Character ‘i’ is to delete the first node from L and print the deleted node’s key.
• Character ‘l’ is to delete the last node from L and print the deleted node’s key.
• Character ‘s’ is followed by an integer separated by space. This operation is to find the node with this integer as key in L.
• Character ‘e’ is to ‘exit’ from the program.
Output Format:
• The output (if any) of each command should be printed on a separate line.
• For options ‘d’, ‘i’ and ‘l’ , print the deleted node’s key. If a node with the input key is not present in L or L is empty, then print −1.
• For option ‘s’, if the key is present in L, then print 1. If key is not present in L or L is empty, then print −1.
Sample Input :
f 7 t 10 a 11 7 b 12 11 d 10
i l
s 12 s 6 e
Sample Output:
10
7
11
1
-1
2. A Doubly linked list L is a data structure in which the objects are arranged in a linear order. Each node of a Doubly linked list L is an object with an attribute key and two other pointer attributes: next and prev. Given a node x in the list, x.next points to its successor in the linked list, and x.prev points to its predecessor. An attribute L.head points to the first node of the list.
Write a menu driven program to implement an unsorted Doubly Linked List L. Your program must contain the following functions: (In function prototypes, L, k, x and y denote a Doubly Linked list, an integer and the nodes of L respectively. All operations should be done in a single pass and all keys are distinct).
• Main() - repeatedly reads a character ‘f’, ‘t’, ‘a’, ‘b’, ‘d’, ‘i’, ‘l’, ‘s’ or ‘e’ from terminal and calls the sub-functions appropriately until character ‘e’ is entered.
• CREATE-NODE(k)- Creates a new node with key k and the pointers next and prev of node points to NULL. This procedure returns a pointer to the new node.
• LIST-INSERT-FRONT(L,x) - inserts node x to the front of L.
• LIST-INSERT-TAIL(L,x) - inserts x as the last node of L.
• LIST-INSERT-AFTER(L,x,y) - inserts node x after node y in L.
Hint: First invoke LIST-SEARCH() function to locate the node y.
• LIST-INSERT-BEFORE(L,x,y) - inserts node x before node y in L.
Hint: Insertion of a node x before a node y can be done by locally storing a pointer to the current node before moving to the next node.
• LIST-DELETE(L,x) - deletes node x from L.
Hint: First invoke LIST-SEARCH() function to locate the node x.
• LIST-DELETE-INITIAL(L) - deletes the first node from L.
• LIST-DELETE-LAST(L) - deletes the last node from L.
• LIST-SEARCH(L,k) - searches for a node with key k in L by a simple linear search, and if found, returns a pointer to this node. If a node with key k is not present in the list, or the list is empty, then the procedure returns NIL.
Note:- For every INSERT operation, the node x is created by calling CREATE-NODE() function.
Input format:
• Each line contains a character from ‘f’, ‘t’, ‘a’, ‘b’, ‘d’, ‘i’, ‘l’, ‘s’ or ‘e’ followed by zero, one or two integers. The integers, if given, are in the range [−106,106].
• Character ‘f’ is followed by an integer separated by space. In this operation, the node with this integer as key is inserted into the front of L.
• Character ‘t’ is followed by an integer separated by space. In this operation, the node with this integer as key is inserted into the tail of L.
• Character ‘a’ is followed by two integers separated by space. In this operation, the node with the first integer as key is inserted after the node with second integer as key into L.
• Character ‘b’ is followed by two integers separated by space. In this operation, the node with the first integer as key is inserted before the node with second integer as key into L.
• Character ‘d’ is followed by an integer separated by space. In this operation, the node with this integer as key is deleted from L and the deleted node’s key is printed.
• Character ‘i’ is to delete the first node from L and print the deleted node’s key.
• Character ‘l’ is to delete the last node from L and print the deleted node’s key.
• Character ‘s’ is followed by an integer separated by space. This operation is to find the node with this integer as key in L.
• Character ‘e’ is to ‘exit’ from the program.
Output Format:
• The output (if any) of each command should be printed on a separate line.
• For options ‘d’, ‘i’ and ‘l’, print the deleted node’s key. If a node with the input key is not present in L or L is empty, then print −1.
• For option ‘s’, if the key is present in L, then print 1. If key is not present in L or L is empty, then print −1.
Sample Input f 20 t 38 a 22 20 b 35 22 d 38
i l
s 35 s 40 e
Sample Output
38
20
22
1
-1
3. Operating Systems maintain a data structure called Process Control Block(PCB) for each process. The PCB of a process contains information related to that process. For simplicity, we assume that only process id and state of a process are stored in it’s PCB and the process ids are distinct. A process can be in any one of the following states: ‘new’, ‘ready’, ‘running’, ‘waiting’, or ‘terminated’.
Write a menu driven program to maintain PCBs of different processes as a Singly linked list called PCB List L. Each PCB of a PCB List L is an object which stores the attributes of a process in the order process id and state. Your program must contain the following functions: (In function prototypes, L, k and x denote the PCB List, an integer and a node of L respectively).
• Main() - repeatedly reads a character ‘i’, ‘d’, ‘g’, ‘l’, ‘u’ or ‘e’ from terminal and calls the sub-functions appropriately until character ‘e’ is entered.
• CREATE-PCB(k)- Creates a new PCB node with key k and the pointer next of PCB node points to NULL. This procedure returns a pointer to the new PCB node.
• INSERT(L,x) - inserts x to the front of L.
• DELETE(L,x) - deletes x from L.
• GET-STATE(k,L) - returns the state of process with process id=k in L.
• LIST-WAITING-PROCESSES(L) - lists the process ids of all processes that are in the state ‘waiting’ in L.
• UPDATE-STATE(L,k,s) - change the state of a PCB with process id=k to s.
• LIST-SEARCH(L,k) - does a linear search to find the PCB with process id = k in L, and if found, returns a pointer to the located PCB. If such a PCB is not found, or if the list is empty, then the procedure returns NIL.
Note:- For INSERT operation, the PCB x is created by calling CREATE-PCB() function.
Input format:
• Each line contains a character from ‘i’, ‘d’, ‘g’, ‘l’, ‘u’, ‘e’ followed by at most one integer and/or a string. The integers, if given, are in the range [1,106] and the string is from the set {new, ready, waiting, running, terminated}.
• Character ‘i’ is followed by an integer and a string separated by space. In this operation, the PCB with the integer as process id and the string as state is inserted into the front of L.
• Character ‘d’ is followed by an integer separated by space. In this operation, the PCB with this integer as process id is deleted from L and the deleted PCB’s process id is printed (you should first invoke a LIST-SEARCH function to locate the node x with the given process id and pass the pointer to node x to DELETE function).
• Character ‘g’ is followed by an integer separated by space. In this operation, the state of PCB with this integer as process id is printed.
• Character ‘l’ is to print the process ids of all PCBs having the state as ‘waiting’.
• Character ‘u’ followed by an integer k and a string s is to update the state of a PCB with process id=k to the state s.
• Character ‘e’ is to exit from the program.
Output Format:
• The output (if any) of each command should be printed on a separate line.
• For option ‘d’, print the deleted PCB’s process id. If PCB with the given process id is not present in L or if L is empty, then print −1.
• For option ‘g’, print the state of PCB with process id=k. If PCB with the given process id is not present in L or if L is empty, then print −1.
• For option ‘l’, list the process ids of all PCBs with state = ‘waiting’ in L, separated by space.
If PCB with state = ‘waiting’ is not present in L, or if L is empty, then print −1.
Sample Input :
i 17 new i 15 new i 21 new i 32 new d 15 u 17 ready u 32 ready u 21 ready u 21 waiting u 32 waiting
l
g 17 g 76 e
Sample Output:
15 32 21 ready
-1