Revision Questions - Pointers and Malloc (Solutions)

Revision Questions - Pointers and Malloc

1. Consider the following program:

int main(void) {
    int a = 1;
    int b = 2;
    swap(a, b);
    assert(a == 2);
    assert(b == 1);
}

void swap(int a, int b) {
    int tmp = a;
    a = b;
    b = tmp;
}

(a) What does assert do?

assert takes an expression (a scalar expression, to be precise) and terminates the program if the expression evaluates to false/zero.

(b) What is the intention of the program?

The program tries to swap the values of two integers using a function.

(c) Why doesn't the program work?

Most values are passed by copy into functions. The swap function receives a copy of the integers and changing these integers does not change the integers in the main function.

(d) How could the program be modified so that it works as intended?

Modify the swap function so it receives pointers to the integers rather than the integers themselves. The modified program looks like this:

int main(void) {
    int a = 1;
    int b = 1;
    swap(&a, &b);
    assert(a == 2);
    assert(b == 1);
}

void swap(int *a, int *b) {
    int tmp = *a;
    *a = *b;
    *b = tmp;
}

2. Consider the following program:

int main(void) {
    int a[] = {1, 2};
    swap(a);
    assert(a[0] == 2);
    assert(a[1] == 1);
}

void swap(int arr[]) {
    int tmp = arr[0];
    arr[0] = arr[1];
    arr[1] = tmp;
}

(a) What is a in the main function?

a is an int array of size 2.

(b) Why does this program work, whereas the program in Question 1 did not?

When an array is passed into a function it "decays" to a pointer, which means the function receives a pointer to the first element of the array. Thus the function is actually modifying the array declared in the main function.

(c) What is arr in the swap function?

arr is a pointer to an int.

3. Consider the following program:

int main(void) {
    int a = 0;
    printf("%ld\n", sizeof(a));
    char *s = "hello";
    printf("%ld\n", sizeof(s));
    printf("%ld\n", sizeof("hello"));
}

(a) What does sizeof do?

sizeof is an operator that gives the size of the given type (or the type of the given expression). It is not actually a function, so the parentheses can be omitted.

(b) What would the program print?

On CSE machines, the program prints

4
8
6

That is because the type of a is int , the type of s is char * , and the type of "hello" is char[6] (char array of size 6).

4. Consider the following code:

typedef int Integer;

typedef struct point {
    int x;
    int y;
} Point;

(a) What does the typedef keyword do?

The typedef keyword is used to assign an alternate name to a type.

(b) Explain the meaning of each of the typedefs.

The first typedef allows Integer to be used in place of int . The second typedef allows Point to be used in place of struct point . For example, the following pairs of declarations are equivalent:

int a = 0;
Integer a = 0;
 
struct point p = {1, 2};
Point p = {1, 2};

5. Consider the following linked list node definition:

struct node {
    int value;
    struct node *next;
};

Which of the following calls to malloc correctly allocates memory for a linked list node?

(A) struct node n = malloc(sizeof(n));

(B) struct node n = malloc(sizeof(*n));

(C) struct node n = malloc(sizeof(struct node));

(D) struct node n = malloc(sizeof(struct node *));

(E) struct node *n = malloc(sizeof(n));

(F) struct node *n = malloc(sizeof(*n));

(G) struct node *n = malloc(sizeof(struct node));

(H) struct node *n = malloc(sizeof(struct node *));

F and G correctly allocate memory for a linked list node.

A, B, C and D are incorrect as malloc always returns a pointer, and struct node is not a pointer type.

E is incorrect as the type of n is struct node * , which means sizeof(n) gives the size of a pointer, which is NOT the same as the size of a node. Thus malloc does not allocate the correct amount of memory. H is also incorrect for a similar reason.

6. Now add the following typedef to the code in the previous question:

typedef struct node Node;

(a) What does the typedef do?

The typedef allows Node to be used in place of struct node .

(b) Now which of the following calls to malloc correctly allocates memory for a linked list node?

(A) Node n = malloc(sizeof(n));

(B) Node n = malloc(sizeof(*n));

(C) Node n = malloc(sizeof(Node));

(D) Node n = malloc(sizeof(Node *));

(E) Node n = malloc(sizeof(struct node));

(F) Node n = malloc(sizeof(struct node *));

(G) Node *n = malloc(sizeof(n));

(H) Node *n = malloc(sizeof(*n));

(I) Node *n = malloc(sizeof(Node));

(J) Node *n = malloc(sizeof(Node *));

(K) Node *n = malloc(sizeof(struct node));

(L) Node *n = malloc(sizeof(struct node *));

H, I and K correctly allocate memory for a linked list node.

(c) What if the typedef was written like this instead?

typedef struct node *Node;

B and E correctly allocate memory for a linked list node.

H and K allocate the correct amount of memory, but the type of n is incorrect.

7. How can you allocate an array of n integers using malloc? How about an array of n characters?

The arrays can be allocated like this:

int *arr = malloc(n * sizeof(int));

char *arr = malloc(n * sizeof(char));

8. Consider the following program:

int main(void) {
    char *s1 = "keen";
    char *s2 = cloneString(s1);
    s2[0] = 'b';
    printf("%s %s\n", s1, s2);
}

char *cloneString(char *s) {
    char *t = s;
    return t;
}

(a) What is s1 ?

s1 is a pointer to the first character of "keen". We informally consider s1 to be a string.

(b) What is the intention of the program?

The program tries to create a copy of "keen", change the 'k' to a 'b' and print "keen been".

(c) Why doesn't the program work?

The program doesn't work for two reasons:

1. cloneString doesn't actually create a copy of the string - it just returns the same pointer that was passed in. Thus s2[0] = 'b'; would modify the original string pointed to by s1 .

2. s1 points to the string "keen", but this string is stored in read-only memory. Thus s2[0] = 'b'; would produce an error because modifying the string is not allowed.

(d) How could the program be modified so that it works as intended?

Modify cloneString so it actually creates a copy of the given string. This string would need to be freed at the end of the main function.

9. Consider the following function that appends a node to a linked list:

struct node *append(struct node *list, int value) {
    struct node *n = malloc(sizeof(struct node));
    n->value = value;
    n->next = NULL;

    if (list == NULL) {
        return n;
    }

    struct node *curr = list; // <-- A
    while (curr->next != NULL) {
        curr = curr->next;
    }
    curr->next = n;
    return list;
}

Why doesn't curr require a malloc? That is, instead of the line marked with A , why don't we need a malloc like so?

    ...
    struct node *curr = malloc(sizeof(struct node));
    curr = list;
    ...

malloc was used at the beginning of the function to create a linked list node that persists outside of the function. It doesn't have anything to do with the fact that n is a pointer. malloc is not needed for curr because we don't need to allocate anything.

10. We can easily create 2D arrays local to a function like so:

int arr[3][3] = {
    {1, 2, 3},
    {4, 5, 6},
    {7, 8, 9},
};

Unfortunately we can't create the array like this if we want the array to persist outside of the function. How can we allocate a 2D array using malloc?

Allocating a 2D array is not as simple as allocating a 1D array. We need to allocate an array of pointers, each of which point to an allocated array of the desired type.

The code for allocating the array looks like this (error checking omitted):

int **arr = malloc(height * sizeof(int *));
for (int i = 0; i < height; i++) {
    arr[i] = malloc(width * sizeof(int));
}