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 6 December 2016

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:

1. set a breakpoint at the beginning of a function and at a given line in the program
2. know how to inspect the elements of a list using the print command
3. 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 – Circular Linked List (1 mark)

Implement the functions

 
link create_circular_list (int num_nodes);
void print_nodes(link list);

The first function creates a circular linked list with the specified number of nodes. The second function prints the data in each node in a circular fashion starting with the node specified. Test it for lists with zero, one, and some more elements.

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 17x1 give lab01 lists.c testLists.c