Week 7 Tutorial — Sample Solutions

  1. The function is erroneous because the array arr will cease to exist after the line return arr, since arr is local to this function and gets destroyed once the function returns. So the caller will get a pointer to something that doesn't exist anymore, and you will start to see garbage, segmentation faults, and other errors.

    Arrays created with malloc() are stored in a separate place in memory, the heap, which ensures they live on indefinitely until you free them yourself.

    The correctly implemented function is as follows: 
    // Makes an array of 10 ints and returns a pointer to it

int *makeArrayOfInts() {
    int *arr = (int *) malloc(sizeof(int) * 10);
    int i;
    for (i=0; i<10; i++) {
        arr[i] = i;
    }
    return arr;
    // This is fine because the array itself will live on
}

  2. The program is not valid. Try replacing int *p; with int *p = NULL; and it will try to dereference a null pointer. This is so because fun() makes a copy of the pointer, so when malloc() is called, the result is assigned to the copied pointer rather than to p. p itself is pointing to random memory before and after the call to fun(). Hence, when you dereference it, it will crash. If you want to use a function to add memory to a pointer, then you need to pass the address of the pointer (i.e. a double pointer).

    1. The nodes a, b and c are linked to a, so freeList(a) will free them all.

      1. The function joinList(NodeT *head1, NodeT *head2) needs to:
        • traverse the list head1 until the node with NULL terminator
        • then replace the next field in this node with a pointer to head2
          • head1 is now the head of the joined list
        • return head1

      2. Robustness:
        • normally head1 and head2 are lists containing at least one node each
          • the above scheme works fine in that case
        • if both head1 and head2 are empty ...
          • then there is nothing to join, so just return head1, say
        • if just head2 is empty ...
          • then there is no point joining it to head1, so just return head1
        • if just head1 is empty ...
          • then the joined list is head2 ...
            • as head1 is empty, let head1 = head2 and return head1
        • if head1 and head2 are the same ...
          • if 'same' means different lists with the same data, everything will work
          • if 'same' means head1 == head2, then we have a problem
            • joining a list to itself will result in a linked list that loops on itself
            • there is no NULL terminator: printing the list will go on forever
            • this case must be avoided: there should be an error message saying it is not possible to do this (meaningfully)

      3. Replace the three 'join' lines 22-24 in the program by: 

        a = joinList(a,b);
a = joinList(a,c);
a = joinList(a,d);

  4. A function to test whether a list is empty: 
    int isEmptyList(NodeT *head) {
   int isEmpty = 0;
   if (head == NULL) {
      isEmpty = 1;
   }
   return isEmpty;
}

    This can be written more succinctly as: 
    int isEmptyList(NodeT *head) {
   return (head == NULL);
}

    If we want a list to be non-empty, we would call this function as follows: 
    if (!isEmptyList(head)) {
   ...
}