Class 13 — Tuesday, October 6

Quiz 5, an array’s name as an address, walking an array with a pointer, and pointers in pairs.

Quiz 5 first, on Brightspace: one attempt now. The second comes near the end of class, when it is announced.

1 An array’s name is an address

&n is the address of the variable n — where n lives. It is not the address of a value: there is no value in n until scanf puts one there.

Arrays have addresses too. Predict first, run second.

#include <stdio.h>
#define SIZE 3

int main() {
    int a[SIZE] = {10, 20, 30};
    printf("a     is %p\n", a);
    printf("&a[0] is %p\n", &a[0]);
    printf("&a[1] is %p\n", &a[1]);
    printf("a + 1 is %p\n", a + 1);
}

Predict: are the first two lines the same? How far apart are &a[0] and &a[1]? And is a + 1 one byte past a, or the same as &a[1]? The addresses are in hexadecimal, and the last two digits are enough.

So a function given an array is given that address. That is why A4’s modify.c could change its caller’s array, while A3’s swap.c could not change two ints: an array arrives as an address, and an int as a copy. In a parameter, int a[] and int * a mean the same thing.

2 Without brackets

a + 1 is not one byte past a: it is one element past, and an int is four bytes here. So a + i is the address of a[i], and *(a + i) is a[i] itself. The brackets are shorthand for exactly that.

That gives a second way to walk an array: a pointer that starts at a and moves on one element at a time with p++, until it reaches a + n:

for (int * p = a; p < a + n; p++) {
    printf("%d\n", *p);
}

a + n is the address just past the last element. Comparing with it is fine, but *(a + n) reads past the end of the array, which is undefined behavior: C reads whatever is there.

3 Pointers, in pairs

In pairs; swap who types at every Done when. Every function walks its array with a pointer, with no [ or ] inside it. Every function gets the design recipe’s one-line comment, and every test at least one assert of your own.

3.1 fill

Write void fill(int * a, int n, int value), which sets every one of the n elements to value:

#define SIZE 5

int main() {
    int a[SIZE];
    fill(a, SIZE, 7);
    for (int i = 0; i < SIZE; i++) {
        assert(a[i] == 7);
    }
}

Done when the asserts pass.

3.2 flip

Write void flip(int * a, int n), which reverses the array in place. Start one pointer at the first element and one at the last, swap what they point to with Thursday’s swap, and move them towards each other while the first is still before the second.

#define SIZE 5

int main() {
    int a[SIZE] = {1, 2, 3, 4, 5};
    flip(a, SIZE);
    assert(a[0] == 5);
    assert(a[2] == 3);
    assert(a[4] == 1);
}

Done when the asserts pass. Then change SIZE to 4 — one edit — fix the values and the asserts, and check again: an even length has no middle element.

3.3 find

From here on, for pairs who are done with 3.1 and 3.2.

Write int * find(int * a, int n, int target), which returns the address of the first element equal to target, or NULL when there is none:

#define SIZE 5

int main() {
    int a[SIZE] = {4, 8, 15, 16, 23};
    int * p = find(a, SIZE, 15);
    assert(p != NULL);
    *p = 150;
    assert(a[2] == 150);
    assert(find(a, SIZE, 99) == NULL);
}

Done when the asserts pass.

3.4 rotate

Write void rotate(int * a, int n), which moves every element one place to the right, and the last one round to the front. Walk a pointer backwards, from the last element down, with p--:

#define SIZE 5

int main() {
    int a[SIZE] = {1, 2, 3, 4, 5};
    rotate(a, SIZE);
    assert(a[0] == 5);
    assert(a[1] == 1);
    assert(a[4] == 4);
}

Done when the asserts pass, and so does your own check that SIZE rotations bring the array back to where it started.

3.5 largest

Write int * largest(int * a, int n), which returns the address of the largest element. Then this line sets the largest element to zero, wherever it is:

#define SIZE 5

int main() {
    int a[SIZE] = {4, 23, 8, 16, 15};
    *largest(a, SIZE) = 0;
    assert(a[1] == 0);
}

Done when it passes, and still does when the largest element is the first, and when it is the last.

4 Before you leave

  • Quiz 5, attempt 2, when it is announced.
  • The Closing Journal: its prompt is in the announcements on Brightspace.
  • A5 is due Wednesday, October 7.