Laboratory
Objectives
- To practise programming linked lists
- To practise programming doubly linked lists
- To practise using
gdb
,valgrind
, and3c
Assessment
- Deadline
- 2 December 2018, 23:59:59
- Marks
- 3
- Submission
give cs2521 lab01
This lab should be done individually.
You must get your tutor in your lab to mark the exercises during allocated lab time, or the following week if you submitted your lab on time using Give. Try to get them to mark each exercise as you complete it in your lab time, if possible.
In addition to the code that the exercise calls for, you will of course have to write some additional code to test the correctness of your implementation. Your tutor may want to see your testing code, too; good style requires good tests!
Code submitted by the deadline for a lab may be marked the following week at the beginning of the lab with no penalty. Late submissions will receive a 1 mark penalty. Once solutions are available, labs will be given 0.
Setting up
Create a directory for this lab, change into it,
and retrieve the files with the fetch
command:
2521 fetch lab01 `./lists.h' -> `.../lists.h' ./ Makefile lists.c test_lists.c
This will have provided you with several files (as you may have guessed by its output):
lists.h
- contains linked-list definitions and function prototypes. Do not change this file.
Makefile
- contains build rules.
lists.c
- contains a
list_print
function, and stubs for functions you need to implement to complete this lab. test_lists.c
- contains a
main
function to test your list implementation. You will need to add your own tests to this file.
The provided code contains tags marking unused variables. You should remove these tags as you implement those functions.
Exercise 1: Linked Lists (0.5 marks)
Using the code given in the tutorial, or otherwise,
implement the functions in lists.c
:
link node_new (Item it);
void list_insert_next (link list, link node);
Modify the test_lists.c
code
to use these functions
to create a list with 3 nodes,
and use the list_print
function to print them out.
Compile your program –
make 2521 3c -c -o test_lists.o test_lists.c 2521 3c -c -o lists.o lists.c 2521 3c test_lists.o lists.o -o test_lists
Execute your program in gdb
,
and show your tutor that you can:
- set a breakpoint at the beginning of a function, and at a given line in the program;
- inspect the elements of a list
using the
print
command; and - inspect the call stack.
Now implement the function list_sum_items
,
which adds all the items in a list
and returns the resulting integer value.
Add some tests to test_lists.c
,
for cases with zero, one, and more elements.
Use gdb
to help debug your code, if needed.
Exercise 2: Six Bytes In A Leaky Boat (0.5 marks)
Our compiler, 3c
, supports memory leak checking.
You’ll have to invoke it by hand, though,
adding +leak
as the first argument –
2521 3c +leak test_lists.c lists.c -o test_lists ./test_lists
The output should show you that you have some memory leaks,
assuming you have written some code in test_lists.c
that actually adds some nodes to your linked list.
Implement a function list_drop
that frees all the memory for each node in your list.
Once you have written the function,
test it in your test_lists.c
code.
Run 3c +leak
again,
and check that all the memory leaks have gone.
You must be able to show this to your tutor.
Exercise 3: Ouraboros! (1 mark)
Implement the functions
link clist_new (int n_nodes);
void clist_print (link clist);
The first function creates a circular linked list with the specified number of nodes. The second function prints the data in each node, starting with the node specified.
Test it in your test_lists.c
code
for lists with zero, one, and more elements.
What happens if you try to run list_sum_items
on your circular linked list?
You must be able to explain this to your tutor,
but you do not need to fix it.
What happens if you try to run list_drop
on your circular list?
Modify list_drop
so it works for
both regular linked lists
and circular linked lists.
You should be able to show your tutor
using 3c +leak
or Valgrind
that no memory leaks exist.
Exercise 4: Double, Double, Linked-List Trouble (1 mark)
Write a function dlist_new_from_list
which,
given a singly-linked list,
creates a new doubly-linked list,
with the same items as elements.
You might want to write
a dlist_print
function to test it.
You must also write a function dlist_drop
,
and make sure you can demonstrate that
you have freed the memory correctly
to your tutor.
Submitting
You must get the lab marked by your tutor in your lab.
Submit your work with the give command, like so:
give cs2521 lab01 lists.c
Or, if you are working from home, upload the relevant file(s) to the lab01 activity on WebCMS3 or on Give Online.