CSC 228 Data Structures and Algorithms, Fall 2017 Instructor: Dr. Natarajan Megh
ID: 3584980 • Letter: C
Question
CSC 228 Data Structures and Algorithms, Fall 2017 Instructor: Dr. Natarajan Meghanathan Exam 1 (Take Home) Due: Oct. 2, 2017: 1 PM (submission through Canvas) Q1 -25 pts) The deleteElement(int deleteData) member function in the code for the Singly Linked List based implementation of a List ADT deletes the first occurrence of deleteData in the List. Modify this member function in such a way that all occurrences of deleteData in the List are deleted with a single call to the deleteElement function from main. After you modify the deleteElement function, run the main function (as given in the startup code for this question) by creating a List of at least 10 elements with certain elements repeating. Now ask for a value (deleteData) to delete from the user and call the deleteElement deleteData) function to delete all occurrences of deleteData in the List. Capture the output of your program displaying the contents of the List before and after the call to the deleteElement function. A sample of the expected screenshot of the program is shown below. As noticed in the screenshot, all occurrences of deleteData'15' in the List are removed after a call to the deleteElement function. Enter the nunber of elenents you want to insert: 10 Enter elenent # 0 : 12 Enter elenent # 1 14 Enter elenent # 2 : 14 Enter elenent # 3 : 15 Enter elenent # 4 : 15 Enter eierent # 5 18 Enter elenent # 6 : 17 Enter elenent # 7 15 Enter eienent # 8 : 19 Enter elenent # 9 14 Contents of the List: 12 14 14 15 15 18 1? 15 19 14 Enter the data to delete: 15 Contents of the List after de lete); 12 14 14 18 17 19 14 Q2 - 25 pts) The Fibonacci sequence is generated using the following recursion: F(n) F(n-2) F(n-1), for n > 1.1(0) = 0 and F(1)-1 In this question, you will generate the Fibonacci sequence as a "Singly Linked List" of integers 0, 1, 1, 2, 3, 5, 8, 13, 21, 34,..., N where N is the largest integer in the sequence that is less than the integer J comprising the last three digits of your For example, if your J# is J00543244, then J is 244, In that case, the Fibonacci sequence that is generated should be 0, 1,1,2, 3,5, 8,13,21, 34, 55, 89, 144, 233 If the last three digits of your J# form an integer that is less than 100, add 100 to the last three digits of your J# and use the resulting value as J. For example, if your J# is J00543034, then J is 34 + 100 = 134 and the Fibonacci sequence generated would be: 0, 1, 1, 2, 3, 5, 8, 13,21, 34, 55, 89 You are given the code for the Singly Linked List-based implementation of the List ADT. Add a member function constructSequence(int) to the List class that takes an integer argument (upperBound: J for the Fibonacci sequence) The main function given to you already inserts the first two nodes (with data 0 and 1 respectively) to a List called Fibonaccilist. Your task will be to implement the constructSequence function that will insert a sequence of nodes (one node per iteration) to the FibonacciList whose last element will be the largest element in the sequence that is less than the upperBound Q3 -20 pts) You are given the code (including the main function) for evaluating an expression in post-fix format using Stack. Your task is to modify the code in the main function to input an expression in pre-fixExplanation / Answer
Q3) The desired program for converting the prefix expression to postfix is given below:
#include <string.h>
#include <ctype.h>
char opds[50][80],oprs[50];
int sTop=-1,dTop=-1;
dPush(char *op)
{
strcpy(opds[++dTop],op);
}
char *dPop()
{
return(opds[dTop--]);
}
rPush(char op)
{
oprs[++sTop]=op;
}
char rPop()
{
return(oprs[sTop--]);
}
int isEmpty(int a)
{
if( a == 0) return(1);
return(0);
}
main()
{
char prefixExp[50],ch,stringExp[50],op1[50],op2[50],opr[2];
int i=0,k=0,opndcnt=0;
gets(prefixExp);
printf(" The Prefix is: %s ",prefixExp);
while( (ch=prefixExp[i++]) != '')
{
if(isalnum(ch))
{
stringExp[0]=ch; stringExp[1]='';
dPush(stringExp); opndcnt++;
if(opndcnt >= 2)
{
strcpy(op2,dPop());
strcpy(op1,dPop());
strcpy(stringExp,op1);
strcat(stringExp,op2);
ch=rPop();
opr[0]=ch;opr[1]='';
strcat(stringExp,opr);
dPush(stringExp);
opndcnt-=1;
}
}
else
{
rPush(ch);
if(opndcnt==1)opndcnt=0;
}
}
if(!isEmpty(dTop))
{
strcpy(op2,dPop());
strcpy(op1,dPop());
strcpy(stringExp,op1);
strcat(stringExp,op2);
ch=rPop();
opr[0]=ch;opr[1]='';
strcat(stringExp,opr);
dPush(stringExp);
}
printf(" The Postfix is: ");
puts(opds[dTop]);
}