Homework #10 Solution

Hand in: A student with number 20180000001 should hand in a file named 20180000001.c for this homework and compress it into a .zip file.




This assignment consist of four sub-parts. For each part, you need to make performance comparisons in terms of execution time and print them with the following format (Execution times should be represented with milliseconds). Remember that, if you are asked to implement your solution by using a data structure, then, you can only use the data structures which you have already learned in the class. Please note that, you are not allowed to use dynamic arrays in your data structure implementations. The main function is also given at the end of the document.




The Performance result reports should be seem as following:




Structures Stack Queue BST




Exec. Time
1.24
0.89
0.06











Part 1. [20pts] Write a function that takes three data structure as parameters and a data array to fill them with the values of the data array. The data structures should be queue, stack and binary search tree. Tract the execution time of filling time for each data structure and report the total execution time of filling the structures separately. The function prototype is:




void fill_structures(stack * stack_, queue * queue_, bst * bst_, int data[20])




Part 2. [30pts] Write a function that takes the data structures parameters and print them in descending order. Report the total of structure separately. The function prototype is:




which were filled on part one as ordering and printing time for each



void ordered_print(stack * stack_, queue * queue_, bst * bst_)




Part 3. [20pts] Write a function that takes the data structures which were filled on part one as parameters and also an integer parameter to search in the structures. The function prints all the founded items and also number of steps to find the result, the function should report if there is no result. In example; let the queue be (tail)1→3→5→2→11→18](head) and we want to search 3, then the result of the search should be; “1 result founded on 5. step.” for queue structure and so on. Report the total of search time for each structure separately. The function prototype is:




void search(stack * stack_, queue * queue_, bst * bst_, int val_to_search)



Part 4. [30pts] Write a function that takes the data structures which were parameters and print them in a specific traversal method. The traversal method




filled on part one as follows the basic rule:





Start with the max value of the structure and go on with the min value and after that, again the max value and the min value, so on and so forth.




In example; let the stack be 3, 5, 6, 2, 1, 7 (top), then the function should print ; 7, 1, 6, 2, 5, 3. Report the total of traverse time for each structure separately. The function prototype is:




void special_traverse(stack * stack_, queue * queue_, bst * bst_)







Note that, you are not allowed to change; function names, parameters or structures, structure names and the code inside the main function (in short, any given thing on the homework sheet), unless it said to you to do so. Otherwise, you will get zero from the changed part.




The main function:




int main()




{




int data[20]={5, 2, 7, 8, 11, 3, 21, 7, 6, 15, 19, 35, 24, 1, 8, 12, 17, 8, 23, 4};




bst * bst_;




queue * queue_;




stack * stack_;




fill_structures(stack_, queue_, bst, data);




ordered_print(stack_, queue_, bst);




search(stack_, queue_, bst, 5);




special_traverse(stack_, queue_, bst, 5);




return 0;




}




General Rules:




 
Obey and don’t broke the function prototypes that are shown on each part, otherwise, you will get zero from the related part.




 
The program must be developed on Linux based OS and must be compiled with gcc compiler, any problem which rises due to using another OS or compiler won’t be tolerated.




 
Note that if any part of your program is not working as expected, then you can get zero from the related part, even it’s working in some way.




 
Upload your .zip file on to Moodle to deliver your homework. The zip file must consist of one .c file that contains your solutions. Name format can be found on the top of this homework sheet.




 
You can ask any question about the homework on forum that is stated on the Moodle page of the course.