Arrays and For Loops
COP-3223H
Table of Contents
New construct: increment (++)
i++;
means
i = i + 1;
Syntactic sugar for reassigning a variable to the value plus one.
Similarly, i-- means decrement, i = i - 1
The i++ operator is postfix, i.e., the operator appears after the variable.
Prefix variations
++i--i
Prefix vs. postfix affects when the increment/decrement happens:
- Prefix, e.g.,
++i, increment the value before using the variable's value. - Postfix, e.g.,
i++, increment the value after using the variable's value.
int i = 1;
printf("%d\n", i++); // prints 1 (increment after using)
printf("%d\n", i); // prints 2
int j = 1;
printf("%d\n", ++j); // prints 2 (increment before using)
printf("%d\n", j); // prints 2
For loops
for (INITIALIZE; CONDITION; ITERATOR) {
instructions;
}
- Run INITIALIZE
- Check CONDITION
- If it's true, run instructions
- Then run ITERATOR
- Then repeat from #2
- If it's not true, done, continue after the for loop
Example: printing digits
What is the output of this program?
for (int i = 0; i < n; i++) {
printf("%d\n", i);
}
Notice that i++ makes this slightly more concise to write, instead of
for (int i = 0; i < n; i = i + 1) {
printf("%d\n", i);
}
Demonstrating for-loop semantics, boundary conditions, etc.
#include <stdio.h>
int main() {
int n = 10;
for (int i = 0; i < n; i++) {
printf("%d\n", i);
}
printf("done\n");
for (int i = 0; i < n; i = i + 1) {
printf("%d\n", i);
}
printf("done\n");
for (int i = 0; i < n; i = i + 2) {
printf("%d\n", i);
// once i is eight
}
printf("done\n");
for (int i = 0; i < n; i = i + 2) {
printf("%d\n", i);
// once i is eight
}
printf("done\n");
for (int i = 9; i < n; i++) {
printf("%d\n", i);
}
// i = 9
// i < n => 0 < 10 true
// print 9
// i++ => 9++ => 10
// i < n => 10 < 10
// for loop is done
printf("done\n");
int i;
for (i = 10; i < n; i++) {
printf("%d\n", i);
}
// i = 10
// i < n => 10 < 10 false
// continue after the for loop
printf("done\n");
printf("%d\n", i);
}
Example: equivalent while loop
for (int i = 0; i < n; i++) {
printf("%d\n", i);
}
int i = 0;
while (i < n) {
instructions;
i++;
}
Aside on C scoping rules
#include <stdio.h>
int main() { // new "scope" for main
int i = 1;
printf("%d\n", i);
if (i > 0) { // new "scope" for a set of variables for if statement
i = 2;
printf("%d\n", i);
if (i > 0) {
i = 3;
}
printf("%d\n", i);
} // scope is thrown away along with any variable declared here
// still inside main's scope
printf("%d\n", i);
}
General while loop implementation
for (INITIALIZE; CONDITION; ITERATOR) {
instructions;
}
INITIALIZE;
while (CONDITION) {
instructions;
ITERATOR;
}
Technically, the equivalence would be
{
INITIALIZE;
while (CONDITION) {
instructions;
ITERATOR;
}
}
This ensures that any declarations in INITIALIZE are only scoped to the while loop, and do not interfere with declarations above the while loop.
Example: sum of 1..N
#include <stdio.h>
int main() {
int n;
int sum;
scanf("%d", &n);
// sum the numbers from 1 to n
// assume 1 to N is inclusive
sum = 0;
for (int i = 1; i < n + 1; i++) {
sum = sum + i;
}
// what values of i will we have (inside the loop body)?
// n large enough i = { 1, 2, 3, ..., N }
// n = 0? i = { }
// n = 1? i = { 1 }
// sum = { 1, 3, 6, ... }
printf("%d\n", sum);
}
Example: exponent
#include <stdio.h>
int main() {
int x;
int e;
int result;
scanf("%d", &x);
scanf("%d", &e);
// x^e = x * x * x * ... e times
result = 1;
for (int i = 1; i <= e; i++) {
result = result * x;
}
printf("%d\n", result);
}
Example: factorial
Example: counting down
for (int i = 9; i >= 0; i--) {
}
Example: sum of powers of two
int sum = 0;
for (int i = 0; i < N; i++) {
int pow = 1;
for (int j = 0; j < i; j++) {
pow = 2 * pow;
}
sum = sum + pow;
}
More efficient way to do this?
Arrays
- Variables store one value
- Arrays store one or more values
- Uses a single variable name
Defining a fixed-length array
int a[] = { 1, 2, 3, 4, 5 };
All values have the same datatype, e.g., int in this case.
Operations
Looks like variables, but with a "subscript" in brackets
a[0];
Base-0
- Arrays indices start at zero
int a[] = { 1, 2, 3, 4, 5 };
| Index | Value |
|---|---|
| 0 | 1 |
| 1 | 2 |
| 2 | 3 |
| 3 | 4 |
| 4 | 5 |
Note that there is no index 5. The array has five elements, but starting the count as 0 means there are only indices 0 (inclusive) through 4 (inclusive). If you take the length of the array, that is the upper bound, exclusive, i.e,.
[0, 5)
0 <= index < 5
Assigning an array at an index
a[0] = 2;
Reading an array at an index
printf("%d\n", a[0]);
Memory diagram
Diagram
- Variable names one memory box
- Array names several memory boxes
- Index starts at 0
- We can think of this as an offset from 0
Example: reading and writing a fixed array
#include <stdio.h>
int main(int argc, char **argv) {
int a[] = { 1, 2, 3, 4, 5 };
}
Uninitialized arrays
int a[5];
You don't need to initialize an array on declaration. Instead you can declare the variable, and all memory slots will be uninitialized as with scalar variables. It may be difficult to reason about which indicies have been initialized, so it is good practice to carefully initialize arrays before usage, e.g., with a for loop. Be careful about crafting the loop, as mistakes like off-by-one errors can lead to uninitialized indicies or out-of-bounds array accesses.
Initializer loop
int a[5];
for (int i = 0; i < 5; i++) {
a[i] = i + 1;
}
Make the for loop match the array, i.e., start at 0 and end at the array length (exclusive).
C gotcha: out-of-bounds array accesses
Compilers can catch simple-to-reason-about instances. In general, though, it is difficult or impossible to do so. For simplicity of implementation, most C compilers will produce machine code that performs the out of bounds memory access.
Example: what does this array contain?
int a[10];
for (int i = 0; i < 10; i++) {
a[i] = i * i;
}
Example: what does this array contain?
int a[10];
for (int i = 0; i < 10; i++) {
a[i] = 1;
}
for (int i = 1; i < 10; i++) {
a[i] = a[i - 1] * 2;
}
Example: what does this array contain?
int a[10];
a[0] = 0;
for (int i = 1; i < 3; i++) {
a[i] = 1;
}
for (int i = 3; i < 10; i++) {
a[i] = a[i - 1] + a[i - 2];
}
Notice how the for-loop boundaries "link" together when using the inclusive/exclusive pattern, i.e., the first assigment is [0, 1), and the first loop is from [1, 3), while the second loop is from [3, 10). It's easy to see that this array is completely initialized by joining [0, 1), [1, 3) and [3, 10) to be [0, 10), the complete set of array indices.