Read numbers without knowing how many there will be.
What to build
The same growing array that sits inside many languages' list types.
Requirements
- Read numbers until a 0 appears. The 0 is not stored.
- Start with a capacity of 2, and double it with
reallocwhenever the array is full. - Print
count C capacity K. - Print the numbers in reverse order on one line, or
empty. - Free the memory.
Input
Whole numbers separated by spaces, ending with a 0.
Output
Two lines.
Constraints
There are at most 100000 numbers before the 0.
Example
Input:
1 2 3 0
Output:
count 3 capacity 4
3 2 1
Why it works
Doubling means that most additions need no copying at all. Over the whole run, the cost is small for each number.
Examples
Example 1 · Input
1 2 3 0
Expected output
count 3 capacity 4 3 2 1
Example 2 · Input
0
Expected output
count 0 capacity 2 empty
Hints
Hint 1
Start with room for 2 numbers.
Hint 2
When the count reaches the capacity, double the capacity and call realloc.
Hint 3
Keep the result of realloc in the pointer.
Solution
Show one correct solution (try it yourself first)
#include <stdio.h>
#include <stdlib.h>
int main(void) {
int capacity = 2, count = 0;
int *a = malloc(capacity * sizeof(int));
if (a == NULL) return 1;
int x;
scanf("%d", &x);
while (x != 0) {
if (count == capacity) {
capacity *= 2;
int *bigger = realloc(a, capacity * sizeof(int));
if (bigger == NULL) {
free(a);
return 1;
}
a = bigger;
}
a[count] = x;
count++;
scanf("%d", &x);
}
printf("count %d capacity %d\n", count, capacity);
if (count == 0) {
printf("empty\n");
}
for (int i = count - 1; i >= 0; i--) {
printf(i == 0 ? "%d\n" : "%d ", a[i]);
}
free(a);
return 0;
}