Week 7 Tutorial — Memory Management, Linked Lists

  1. Consider the following function. 

    /* Makes an array of 10 integers and returns a pointer to it */

int *makeArrayOfInts(void) {
    int arr[10];
    int i;
    for (i=0; i<10; i++) {
        arr[i] = i;
    }
    return arr;
}

    Explain what is wrong with this function. Rewrite the function so that it correctly achieves the intended result using malloc().

  2. Consider the following code. What is the output? 

    # include <stdio.h>
# include <stdlib.h>

void fun(int *);

int main(int argc, char *argv[]) {
    int *p;
    fun(p);
    *p = 6;
    printf("%d\n",*p);
    return(0);
}

void fun(int *a) {
    a = (int*)malloc(sizeof(int));
}

  3. The following program 

     1  // lljoin.c: create 4 nodes and join them together
 2  #include <stdio.h>
 3  #include <stdlib.h>
 4
 5  typedef struct node {
 6     int data;
 7     struct node *next;
 8  } NodeT;
 9
10  NodeT *makeNode(int);
11  void printList(NodeT *);
12  void freeList(NodeT *);
13
14  int main(int argc, char *argv[]) {
15     NodeT *a, *b, *c, *d;
16
17     a = makeNode(10);
18     b = makeNode(20);
19     c = makeNode(30);
20     d = makeNode(40);
21
22     a->next = b; // this joins a to b
23     b->next = c; // this joins b to c
24     c->next = d; // this joins c to d
25
26     printList(a);
27     freeList(a);
28     return EXIT_SUCCESS;
29  }

    The functions makeNode(), printList() and freeList() have been given in the lecture (list.c)

    Note:

    1. At conclusion of the main function, why don't I need to free nodes 'b', 'c' and 'd'?

    2. Consider the function with prototype: 
      NodeT *joinList(NodeT *head1, NodeT *head2);
      which takes two arbitrary lists head1 and head2 and produces a single list. This function should not make any nodes: it should just 'relink' the lists.

      1. How would you implement this function?

      2. How robust should this function be? In other words, what do you know about head1 and head2?
        • What would happen when head1 and head2 are the same?
          • if 'same' means different lists with same data?
          • if 'same' means the addresses are the same?

      3. If you had such a function, how would you use it to replace the 'out-of-place' statements in lines 22, 23 and 24?

  4. Given the struct: 
    typedef struct _node {
   int data;
   struct _node *next;
} NodeT;

    write a function to test whether a given linked list is empty. The function should have prototype: 
    int isEmptyList(NodeT *);  // 1 if true, 0 if false

    If you have a linked list head, how would you call this function to test whether head is not empty?