length that you will use to keep track of the list's current size.(228 points, in addition to the 20 milestone-completion points discussed above) Stubs for all of the functions have been provided for you in main.c. The file also contains specifications of each function in comments.
We've provided all of the test code in the functions
main()
and
runTests(). We've included
return
statements before each test so that you can get one set of tests working before moving on to the next.
The file
expected.txt
in the project gives the expected output for parts a through g. You can use it to check your work. Note that some of the values printed are uninitialized, and so will be different on your computer and between runs.
You are to complete the definitions of all of the functions below. The tests are written expecting that you will complete them in the order listed. For each part, you'll need to comment out a
return
statement to allow the tests for that part to run.
makeIntArray(),
printArray(), and
freeIntArray(). We will begin these together in class.
makeZeroedIntArray().
set()
and
get()
functions for mutating and accessing
IntArrays. For this part, you do not
need to check to see that the indexes are in bounds (i.e., non-negative and not larger than the array size). Your functions should initially return
FALSE.
set()
and
get(). Your functions should print an error and return
TRUE
if an out-of-bounds index is passed to the function, and return
FALSE
otherwise.
pascalsTriangle().
(10 points)
Stress tests.
Comment out the
return 0;
statement in the
main()
function. This will allow a memory stress test to run. The stress test calls your
pascalsTriangle()
function with larger and larger values, doubling in size each time. If your program has a memory leak, this stress test will detect it.
You will probably want to comment out the body of
printArray()
for this test also, otherwise your program will spend lots of time printing and it will take much longer to reach large memory sizes.
In our tests, when we failed to free memory correctly in
pascalsTriangle(), the program "died" at a stress test size of 40960, with the error message
unable to allocate enough memory for array of size 22563. Without the memory leak, our program made it to a stress test size of over 2.6 million before we stopped it.
Add a comment near the end of
main()
indicating how large a stress test size your program reached.
IntArray
struct so we could create initially empty IntArrays and
append
to them. Don't change your code, but add a comment near the end of
main()
describing what you might do.
return
line before the stress test, to keep the stress test from running. Also uncomment the body of
printArray()
so the grader can check the functionality of your functions. Commit your final version to your SVN repository.IntArray
struct to add an additional field, capacity. For our updated
IntArray, the
length
field
represents the size (number of items actually in the list). The
capacity
represents how many items the list could hold before we have to make it bigger.
makeIntArray()
and
makeZeroedIntArray()
so that they set both the
length
and the
capacity
to the given
size.
resizeIntArray(),should print a bunch of empty arrays.
The other tests should be unchanged. resizeIntArray()
It should change the
capacity
of the IntArray, but not its size.
void resizeIntArray(IntArray *a, int newsize)If
newsize is smaller than the current length (not capacity) of *a, this function should do nothing.IntArray makeEmptyIntArray()that takes no arguments and returns an empty (
size is 0) IntArray with an initial capacity of 5.
(15 points) Write a function
void append(IntArray* a, int newElement)to add the given element to the end of the given array. You will need to adjust the size. If the array has reached its capacity, use your
resizeInArray()
function to double the array's capacity.
Doubling gives us room for future growth. If we just grew by one, we would have to keep growing with every additional append, which is really inefficient.
int* getMemoryLocation(IntArray* a)that returns the address of the internal array.
int getCapacity(IntArray* a)
int getSize(IntArray* a)
that do what their names suggest.boolean insert(IntArray* aPtr, int index, int value)that works like Python's insert method. That is, the given value should be inserted into the given array and all subsequent values in the array should be moved to the next higher index. For full credit, your program must resize the array to make room for the additional element when that is necessary. The return value signifies whether there was an index out-of-bounds error. For full credit, your program must check for out-of-bounds indexes and return
TRUE if (and only if)
so, refusing to do the insertion. Add code to main() to test your new function.
(25 points) Create a driver function that will read a bunch of integers from the console and store them in an IntArray
created using
makeEmptyIntArray()
and extending using
append().
After each integer is read, you should print the memory address of the internal array, its current size, its current capacity, and the integer contents of the array (on a single line).
For example, a run might look like:
stored at 003D3D80, with size = 1 and capacity = 5, contents = [3] stored at 003D3D80, with size = 2 and capacity = 5, contents = [3,7] stored at 003D3D80, with size = 3 and capacity = 5, contents = [3,7,8] stored at 003D3D80, with size = 4 and capacity = 5, contents = [3,7,8,2] stored at 003D3D80, with size = 5 and capacity = 5, contents = [3,7,8,2,4] stored at 003D5DF0, with size = 6 and capacity = 10, contents = [3,7,8,2,4,0] stored at 003D5DF0, with size = 7 and capacity = 10, contents = [3,7,8,2,4,0,12] stored at 003D5DF0, with size = 8 and capacity = 10, contents = [3,7,8,2,4,0,12,4] stored at 003D5DF0, with size = 9 and capacity = 10, contents = [3,7,8,2,4,0,12,4,4] stored at 003D5DF0, with size = 10 and capacity = 10, contents = [3,7,8,2,4,0,12,4,4,7] stored at 003D5E20, with size = 11 and capacity = 20, contents = [3,7,8,2,4,0,12,4,4,7,9]
printIntArray(), but instead of printing, returns
what would be printed as a string. Your function's signature should be
char* toString(IntArray* ar)Add code that uses your function to demonstrate that it works. Pay attention to the memory allocation issues that we have discussed and that you have worked with during this assignment.