COMP 1917 Computing 1
Session 2, 2015

Tutorial - Week 9

Presentation Topic for Week 9

What is the difference between black box and white box testing? Demonstrate how both work by writing corresponding tests for the point.c program we developed in the Week 8 tutorial.

In this tutorial you will practice implementing linked lists and writing functions to perform various operations on the data structure. Create a file List.c and use the following struct definition for your implementation: 
    typedef struct node* Lnode;

    struct node{
      int val;
      Lnode next;  
    };
  1. Write a function Lnode newNode(int value) to dynamically allocate new node and initialise it.

  2. Write a function Lnode prepend(Lnode head, Lnode new) that prepends new node to an existing list.

  3. Write a function Lnode append(Lnode head, Lnode new) that appends new node to an existing list.

  4. Write a function void printList(Lnode head) that prints existing list.

  5. Write a function Lnode deleteNode(Lnode head, int val) that removes the first occurence of val in a list.

  6. Create a separate file called testList.c and test the above functions.

  7. An alternative implementation of linked lists requires a separate struct to keep tack of the head and additional features. 
        typedef struct node* Lnode;

    struct node{
      int val;
      Lnode next;  
    };

    typedef struct list* List;

    struct list{
        Lnode head;
        int numNodes;
    };
    How would implementation of the above functions and tests change if you use this representation.

  8. Write a function 
    Lnode  concat( Lnode L, Lnode M )
    which concatenates two linked lists L and M into a single list containing all the nodes of L (in their original order) followed by all the nodes of M (in their original order) and returns a pointer to the head of the new list.

  9. If time allows: using the Lnode structure write a function 
    Lnode reverse( Lnode head )
    which reverses the nodes of a linked list, so that the ordering of the nodes becomes exactly the opposite of what it was before. The function should return a pointer to the head of the new list.

Presentation Topic for Week 11

There are tools available that can help you debug your programs. Two of such tools are valgrind and gdb. Show how you would use these tools to check for memory leaks and debug segmentation faults. (For gdb show at least commands like where, info locals, print and how to set a breakpoint).

PS: Usually, to include debug symbols you will compile your program with -g flag, however on cse machine you will need to use -gdwarf-2 flag to produce debugging symbols.