CS580U - asgn-5-Munjal511 - Solved

 ADT Sequence Structures



Driver Code and Test Input Files
●         Provided Files
○         program5.c //This is the Driver Code, to be linked with your functions.



To make our code more portable, we are going to wrap our data in a Data struct, and build all our operations around this data type. In a header file, data.h, create a struct, Data, which contains the following:

●        a single integer called, ‘value’
Since we are going to be passing by value, we will not need a constructor or destructor.

 

Part A: Vectors

●        You must break up your code into vector.h and vector.c according to the conventions we discussed in class.
●        Create a dynamic array data structure, Vector. You must create your struct and internal array on the heap (using malloc). Your dynamic array should have, at minimum, the following:
■        data: A pointer to a Data struct array

■        current_size: an unsigned integer containing the current size

■        max_size: an unsigned integer containing the maximum capacity

■        void (*insert)(Vector * array, int index, Data value): a function pointer to an insert function

■        Data * (*read)(Vector * array, int index): a function pointer to an read function

■        void (*remove)(Vector * array, int index): a function pointer to an delete function

■        void (*delete)(Vector * array): a function pointer to a destructor

○        You may add additional attributes if you need them

●        You must create the following functions for your Vector 

○        Constructor - initializes the vector struct attributes and returns a pointer to a Vector struct created on the heap

■        Vector * newVector()

NOTE: The remaining function names are suggestions since the driver code calls them all via function pointers

○        Insert - inserts an element at the specified index. Use the 2n+1 geometric expansion formula to increase the size of your list if the index is out of the current bounds.

■        void insertVector(Vector * array, int index, Data value);

○        Remove - deletes an element from the list at the specified index.

■        void removeVector(Vector * array, int index);

●        You must implement true deletion, which will reduce the size of the vector by 1

○     Read - return the pointer to the data struct from the specified index, return NULL if the index is out of bounds, and a data struct with the value set to -1 if the index has not been initialized

■        Data * readVector(Vector * array, int index);

○        Destructor - upon exiting, be sure all memory has been freed by calling 

■        void * deleteVector which free’s all struct memory

●        You should return a NULL pointer from any delete procedure. This is just a convention. 

 

Part B: Linked Lists

●     You must break up your code into list.h and list.c according to the conventions we discussed in class. 
Your node struct must have the following:

○        next/prev: A pointer to the next and previous nodes

○        data: A data object (note: not a pointer)

Your list struct must have the following:

○        head/tail: A pointer to nodes at the head and tail

○        void (*insert)(List *, int, Data): a function pointer to an insert function

○        Data * (*read)(List *, int): a function pointer to a read function

○        void (*remove)(List *, int): a function pointer to an delete function

○        void (*delete)(List *): a function pointer to a destructor

●        Create a doubly linked list using a list and node structs. You must create your linked list on the heap (using malloc). Your linked list should have the following operations:

○        Constructor - initializes the linked list struct:

■        List * newList()

●        A pointer to a head and tail node, both initialized to NULL

●        set function pointers to the appropriate functions

●        returns a pointer to a List struct created on the heap

○        Insert - inserts an element at a specified index in the list. 

■        void insertList(List * list, int index, Data value);

●        Adds the Data to the specified index 

●        If the index is out of bounds, adds the data to the end of your list. 

○        Delete - deletes an element from a specified index in the list. 

■        void removeData(List * list, int index);

●        If the index is out of bounds, you should just return without doing anything.

○        Read - returns a pointer to the data element stored in the list

■        Data * readData(List * list, int index);

●        If the index is out of bounds, return a NULL pointer




Part C: Profiling Your Code

●        Create another file called profile.c/.h. Inside this file you should implement 3 functions that profile your vector and list data structures. You must ensure that only the relevant code is being profiled. Example profiling code is provided:
○    #include <time.h>
#include <sys/time.h>/* timeval, gettimeofday() */
...
struct timeval start, stop;
gettimeofday(&start, NULL);

//code to be profiled…
gettimeofday(&stop, NULL);
time_t start_time = (start.tv_sec* 1000000) + start.tv_usec;
time_t stop_time = (stop.tv_sec* 1000000) + stop.tv_usec;
float profile_time = stop_time - start_time;

●        Print the results to stdout. The description of each function is below.
○        void profileInsert(Vector *, List *)

■        Insert 1000 data objects. The data objects should contain integers in increasing value, i.e. 1,2,3, etc. 

■        Profile the insertion of the data objects for both the vector and the list separately, then print the results.

○        void profileRead(Vector *, List *)

■        Search for 100 random data objects in your sequences. Try to use as similar search algorithms as possible for your search. Your search algorithm can assume unordered data. 

■        Profile the read time of the data objects for both the vector and the list separately, then print the results.

○        void profileRemove(Vector *, List *)

■        Remove for 100 random data objects in your sequences.

■        Profile the read time of the data objects for both the vector and the list separately, then print the results.