Lab Exercises Week 02

Objectives

• To practice implementing and testing ADTs

Assessment

Deadline: 11:59pm Tue 15 December 2015

Total Marks: 3

This lab should be done in pairs

Related Chapters of textbook

Chapter 4

Setting up

Change into your lab02 directory and run the following command:

cp /home/cs1927/public_html/16x1/labs/lab02/files/* .

Note the "." at the end of the command, meaning "into the current directory".

If you've done the above correctly, you should find the following files now in the directory:

To compile all the code you just need to type

make

./testStack
./testArrayQueue
./testListQueue

These programs are incomplete and you will modify the .c files as outlined in the instructions below. Evey time you modify the .c files you can recompile simply by typing the command

make

Task 1: Stack ADT Array Implementation with Bounds Checking - 1 mark

The array based stack ADT implementation we developed in lectures, had some serious shortcomings.

Pushing an item onto the stack when the maximum number of items has been reached, or popping from the stack when the stack is empty, leads to out of bounds array access. This can cause other program variables to be unintentionally overwritten and/or may result in apparently random crashes. It is good programming practice to make ADT implementations robust against out-of-bounds errors and similar problems.

The provided file, stackArray.c has the same problems. You need to modify the implementation in stackArray.c to provide the following behaviour:

• When an attempt is made to push an item onto a stack that is already full, the array is resized to accomodate the extra element. Make sure the stack is only resized when it is full and make the resized array be 2 times bigger.

• It prints the message "stack underflow" when an attempt is made to pop from an empty stack and calls the function abort to terminate the program. Also when the size of the stack drops below 1/4 of the size of the array, the array size should be resized to half of its size. However the array size should never dop below its original starting size.

Hint: Look at the C function realloc. (Note: this should ONLY be used to resize memory that has been malloced. Thus if you had declared you array like: int array[100]; You could NOT use realloc to resize it).

While you are developing you implementation, add some tests to the whiteBoxTests function in arrayStack.c. This should contain unit tests that have access to the internal structure of the ADT. These tests should be able to make sure the array is resized appropriately, as well as testing the rest of the stack functionality.

Add test cases to the testStack.c program, that would have triggered the out of bounds conditions to test that your code works properly. Be brutal with your tests! Also check that popping an empty stack generates the appropriate error messages. Note that the tests you create in testStack.c should be black box tests and can only only use the typedefs and functions that are declared in the .h interface.

If you look inside the Makefile you can see we have

CFLAGS=-Wall -Werror -O

If you want to use valgrind or gdb, you can modify the Makefile and replace the -O flag with a -g or -gdwarf-2.

Exercise 2a: Creating black box tests for a Queue - 0.5 marks

In the provided file called testQueue.c write a comprehensive set of black box tests for the Queue.h interface.

When you have finished writing your tests, use the provided Makefile to compile testQueue.c. The Makefile compiles the arrayQueue.c and the testQueue.c files and links them together to create a program called testArrayQueue. The Makefile also compiles the listQueue.c and the testQueue.c files and links them together to create a program called testListQueue.

run the testArrayQueue program

Does the provided arrayQueue.c pass your tests? It should, provided that you do not insert more than 10 items. The code contains an abort statement that will kill the program in this situation.

run the testListQueue program

Does the provided listQueue.c pass your tests? It should not. It should contain errors that you will need to fix.

Exercise 2b: Debugging a linked list Queue - 0.5 marks

In the provided file called listQueue.c write some whitebox tests and try to find and fix any errors in the listQueue.c implementation. Make sure the implementation passes all blackbox and whitebox tests.

Exercise 3: Changing the arrayQueue implementation - 1 mark

The implementation of the array based queue provided in arrayQueue.c is not very efficient. When an item is removed, all the remaining items are shifted down one place in the array. This makes the getQueue function O(n). Modify the queue implementation so that both putQueue and getQueue are O(1) operations.

Hint: Store the index of the start of the queue and the end of the queue. This way when you get an element you do not have to shift all the elements over one place, you can just update the index of the start of the queue.

You should also still make sure your implementation checks that the queue never exceeds its maximum and that it never trys to get an element from an empty queue. In this case you should print out an error message and call the function abort. (Unlike the first part of the lab, you do not have to resize the array when it becomes full).

Write some white box unit tests to confirm that your new implementation works and recompile and run against your original black box tests. If your implementation is correct they should still work.

Submission

1927 classrun 16x1 give lab02 arrayStack.c testStack.c arrayQueue.c testQueue.c listQueue.c