Implement a resizable array.
In this lab, you will implement a resizable array. Unlike arrays provided in the C language, a resizable array can be increased in size to accommodate more data when necessary. However, unlike in a linked list the elements are still kept in an array. The array however is not statically allocated since its size may change at runtime. The array is allocated on heap and moved from one heap location to another if there isn't sufficient room in heap at the current location to increase its size.
The array list you will implement in this lab will contain pointers of type void *.
We provide details of the functions you need to write below. The prototypes for these functions can be found in al.h
HERE. Please do not modify this header and make sure that your implementation conforms to the prototypes provided.
Put all your code in a file named al.c. Submit only al.c. This file should NOT contain any other function
definitions than those declared in al.h.
An array list has the following structure type.
struct al;
Observe that we do not provide a definition of this structure in al.h. It only provides the above declaration.
This hides the internal details of your array list implementation from code that uses the array list. You may define the structure
al in al.c to suite your requirements.
The functions below return -1 (or NULL) on error and 0 (or valid pointer) on success depending on their return type.
| struct al *al_create(int size); | Creates an array list of given size. The function returns NULL if size is 0 or negative. |
| void al_free(struct al *l); | Deletes the given array list. Note that this function deletes only the array list object and not any objects in the array list. |
| int al_resize(struct al *l, int size); | Resizes the array list to the specified size. If the size is less than the number of elements in the array list at the time, it returns -1 and size of array list is not modified. |
| int al_add(struct al *l, void *e); | Adds the given pointer to the end of the array list resizing the array list if necessary. When the list is resized the function doubles the size of the list. |
| int al_insertat(struct al *l, int i, void *e); | Inserts the given pointer at the specified index. If the index is not less than the number of elements in the array list or is negative the function returns -1. |
| int al_clear(struct al *l); | Discards all elements in the array list. |
| int al_removeat(struct al *l, int i); | Removes the element at given index. If index is negative or is not less than the number of elements in the array list the function returns -1. |
| int al_remove(struct al *l, void *e); | Removes the given pointer from the array list. If the pointer is not found in the list the function returns -1. |
| void *al_get(struct al *l, int i); | Returns the pointer at the given index in the array list. |
Begin your work by creating a folder named lab05 and downloading the provided header file.
The sample main function below shows how to test your implementation. al_dump function
prints out the contents of the list and new_int function creates an integer with the given value
on heap and returns a pointer to it. Note that al_dump function in code below is not part of
what you are required to implement for this lab. You may however find such a function useful for testing
your code.
main()
{
struct al *l;
int *u;
l = al_create(5);
al_add(l, new_int(1));
al_add(l, new_int(2));
al_add(l, new_int(3));
printf("%d\n", al_resize(l, 3));
al_dump(l);
al_insertat(l, 0, new_int(4));
al_dump(l);
printf("%d\n", al_insertat(l, 6, NULL));
printf("%d\n", al_insertat(l, 3, new_int(5)));
al_dump(l);
printf("%d\n", al_removeat(l, 5));
printf("%d\n", al_removeat(l, 4));
printf("%d\n", al_insertat(l, 2, u = new_int(6)));
al_dump(l);
printf("%d\n", al_remove(l, u));
al_dump(l);
free(l);
return 0;
}
Before you submit make sure that your submission directory lab05 contains only al.c file.
Furthermore, make sure to test your implementation on LORE using GCC compiler.
To use GCC use the command gcc to compile or
set CC=gcc in your Makefile.
We must be able to find al.c and to compile it in order for you
to get points for this lab.
Type cd .. in lab05 and change working directory to the parent directory of lab05.
In the parent directory of lab05, type turnin -v -c cs240=XXX -p lab05 lab05 to turnin your work. Replace XXX with your section number.
| 9:30 am - 11:20 am F | F930 |
| 11:30 am - 1:20 pm F | F1130 |
| 1:30 pm - 3:20 pm F | F130 |
| 3:30 pm - 5:20 pm F | F330 |
| 9:30 am - 11:20 am R | R930 |
| 11:30 am - 1:20 pm R | R1130 |
| 3:30 pm - 5:20 pm R | R330 |
| 11:30 am - 1:20 pm T | T1130 |
Now, you may use the command, turnin -c cs240=XXX -p lab05 -v to verify your submission.
This lab is due on Mon March 7 11:59PM.