I. In-Class Exercises

Programming Exercises

1. Reverse Output an Array: L2031
2. Find the Average Height: L2032
3. Move Array Elements: L2033

II. Knowledge Summary

✨ What Is an Array

In previous lessons, we used variables to store data. But if you need to store the scores of 30 students in a class, defining 30 separate variables would be too cumbersome. An array solves this problem — it can store multiple values of the same type under a single name, and its size must be determined at the time of definition.

You can think of an array as a row of numbered lockers: each locker holds one piece of data, and you can quickly find any data by its number (the index).

Arrays are stored contiguously in memory. Since each int occupies 4 bytes, adjacent elements differ in address by 4. Knowing the base address and the index, you can directly compute the address of any element (base address + index × 4) — this is why arrays can access elements quickly by index.

✨ One-Dimensional Arrays vs. Multi-Dimensional Arrays

Arrays can be classified by dimension into one-dimensional arrays and multi-dimensional arrays:

• One-dimensional array: Data is arranged in a single row, and only one index is needed to locate an element — like the locker example above, arr[3] finds the 4th locker.
• Multi-dimensional array: Data is arranged in multiple rows and columns, and multiple indices are needed to locate an element — like seats in a classroom, where you need both "row number" and "column number" to identify a position.

In this lesson, we will learn about one-dimensional arrays. Multi-dimensional arrays will be covered in a later lesson.

✨ Defining a One-Dimensional Array

When defining a one-dimensional array, you need to specify the data type, array name, and array size. The naming rules for arrays are the same as for variables, and the array size is expressed using [] with a number.

int arri[10];
double arrd[1];
bool arrb[12];

Due to memory limits in competitive programming, it is recommended to define arrays outside the main function.

There are a few additional points to note about one-dimensional array sizes:

1. The array size must be known at compile time — you cannot read in a value and then use it to create an array.

int n;
cin >> n;
int arr[n]; // Do not define an array this way

2. We generally use a literal number for the array size. When we need to create multiple arrays of the same size, we can use a constant for the array size.

int N = 100000;
int arr1[N];
double arr2[N];

3. The array size must be an integer. Since char types are internally stored as integers, you can technically use a char to define the array size, but this practice should be avoided.

int arr['0']; // Creates an array of size 48

✨ Initializing a One-Dimensional Array

Brace Initialization

Use {} to initialize a one-dimensional array. This must be done at the time of definition. If values are provided inside {}, they are assigned to array elements in order, and any remaining elements are set to 0.

int arr[10] = {}; // Initialize all to 0
int arr[5] = {1, 2}; // First element is 1, second is 2, rest are 0
int arr[5] = {0}; // First element is 0, rest are 0
int arr[5] = {2, 3, 8, 1, 3}; // Entire array initialized to 2,3,8,1,3

fill_n Initialization

Requires the <algorithm> header. Can be used at any point to assign a value to all array elements. fill_n takes three arguments: the array name, the number of elements, and the initialization value (which can be any value).

1#include <iostream>
2#include <algorithm>
3using namespace std;
4
5int arr[105];
6
7int main () {
8    fill_n(arr, 105, 1);
9    return 0;
10}

memset Initialization

memset is a C-style initialization method that can be used at any point to set all array elements to a specific value.

memset takes three arguments: the array name, the initialization value, and the array size.

The initialization value is typically specified in hexadecimal. Common values are: 0, 1, -1, 0x3f, and 0x7f, where 0x3f and 0x7f both represent relatively large integers.

Note that the array size parameter is not the number of elements, but the memory size in bytes.

1#include <iostream>
2#include <algorithm>
3using namespace std;
4
5int arr[105];
6
7int main () {
8    memset(arr, 0, sizeof(arr));
9    memset(arr, 1, sizeof(arr));
10    memset(arr, -1, sizeof(arr));
11    memset(arr, 0x3f, sizeof(arr));
12    memset(arr, 0x7f, sizeof(arr));
13    return 0;
14}

Ways to Initialize an Array to All Zeros

There are 5 ways to initialize an array to all zeros:

1. arr[3] = {};
2. arr[3] = {0};
3. arr[3] = {0, 0, 0};
4. fill_n(arr, 3, 0);
5. memset(arr, 0, sizeof(arr));

✨ Accessing Elements of a One-Dimensional Array

A one-dimensional array only needs one index to locate an element. We use the format arrayName[index] to access an array, which allows us to get the value at the given index or assign a value to that position.

1#include <iostream>
2#include <algorithm>
3using namespace std;
4
5int arr[105];
6
7int main () {
8    fill_n(arr, 105, 1);
9    arr[10] = 2; // Assign a value to a specific position
10    arr[20] = 4; // Assign a value to a specific position
11    for (int i = 0; i < 105; i++) { // Use a loop to traverse all indices
12        cout << arr[i] << " "; // Get the value at a specific position
13    }
14    return 0;
15}

Important notes when accessing array elements:

1. Indices start from 0 and go up to the array size minus 1. If the array has n elements, the first element has index 0, the second has index 1, and the last has index n-1.
2. Array indices cannot be negative. When using expressions like arr[i-1], always check that i-1 is greater than or equal to 0.
3. Array indices must not go out of bounds. If the array has n elements, you cannot use an index beyond n-1. When using expressions like arr[i+1], always check that i+1 is less than n.
4. For out-of-bounds array access, the compiler will not report an error, but the program will produce incorrect results at runtime. Therefore, you must use indices carefully.

✨ Common Mistakes with One-Dimensional Arrays

1. Out-of-bounds array access: This is the most common and dangerous mistake. If the array size is n, the valid index range is 0 to n-1 — accessing arr[n] is already out of bounds. The compiler will not report an error, but the program may produce incorrect results or crash at runtime.

int arr[5] = {1, 2, 3, 4, 5};
// Error: accesses arr[5], but the maximum valid index is 4
for (int i = 0; i <= 5; i++) {
    cout << arr[i];
}

2. Defining large arrays inside functions causes stack overflow: Defining a large array inside main or other functions (e.g., int arr[1000000];) will cause a stack overflow. The solution is to define large arrays outside of functions (in the global scope).

3. Using a variable as the array size: int n; cin >> n; int arr[n]; may compile on some compilers, but it is not standard C++ and should be avoided in competitive programming. The correct approach is to pre-define an array that is large enough.

4. Forgetting to initialize the array: Global arrays are automatically initialized to 0, but local arrays are not. Uninitialized local arrays contain random garbage values.

5. Misusing memset initialization: memset fills by byte, so memset(arr, 1, sizeof(arr)) does not set each int element to 1 — it sets each byte to 1, resulting in the int value 16843009. memset is only suitable for initializing to 0, -1, or special values (0x3f, 0x7f).

III. Homework

Knowledge Quiz

• One-Dimensional Arrays - Quiz

Programming Exercises

1. Find Support Numbers: L2034
2. Xiaoyang's Piggy Bank: L2035