Lab Exercises Week 1

Objectives

To practise programming linked lists
To practise programming doubly linked lists
To practise using tools such as gdb and valgrind

Assessment

Deadline: 11:59pm Tue 8 December 2015

Total Marks: 3

You must get your tutor in your lab to mark the exercises during the 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 this testing code, too. Good style requires good tests!

Exercise 1 - Linked Lists (0.5 mark)

Copy the files lists.h , lists.c and testLists.c into your working directory. The file lists.c contains a printList function and stubs for other functions you need to implement to complete the lab. You can use testLists.c to write your tests, but do not edit lists.h

Implement the function

int sumListItems (link ls);

which adds all the items in a list and returns the resulting integer value, and and tests to testLists.c. Test it for lists with zero, one, and some more elements.

Compile your program with the command

	 gcc -Wall -Werror -gdwarf-2 -o  testLists testLists.c lists.c

The -gdwarf-2 option makes sure that debug information is generated.

Execute your program in gdb or ddd and show your tutor that you can:

set a breakpoint at the beginning of a function and at a given line in the program
know how to inspect the elements of a list using the print command
inspect the call stack.

Exercise 2 - Linked Lists (0.5 mark)

Type in the command

valgrind ./testLists

The output should show you that you have some memory leaks - assuming you have written some code in testLists that actually adds some nodes to your linked list.

Implement the function

void freeList(link list);

that frees all the memory for each node in your list. Once you have written the function, test it in your testLists code. Run valgrind again and check that all the memory leaks have gone. You must be able to show this to your tutor.

Exercise 3 - Linked Lists (1 mark)

Implement the function

link fromTo (int start, int end);

which creates a list with the elements start to end. If start is greater than end, return the empty list. Examples:

fromTo (2,6)      2 ->3 ->4 ->5 ->6 ->X
fromTo (3,3)      3 ->X
fromTo (4,3)      ->X

Exercise 4 - Doubly Linked Lists (1 mark)

Write a function

dlink doublify (link ls)

which, given a linked list, creates a new doubly linked list with the same items as elements. You might want to write a printDList function to test it.

You must also write a function

void freeDList(dlink list);

and make sure you can demonstrate that you have freed the memory correctly to your tutor.

Submitting your lab

You must get the lab marked by your tutor in your lab. You should also submit your solution using give on a CSE machine. To do this, run:

1927 classrun 16x1 give lab01 lists.c