Class 13 — Tuesday, October 6
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:
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.