LABORATORY 07

Data Arrays

Duration: 2 hours Language: C / C++ Previous: Laboratory 6 PDF handout RO versiunea română

An array is a collection of data of the same type, placed in a contiguous region of memory. Using a single name and an index, you can store and process any number of values - the only limit is the available memory.

1Lab objectives

int v[5]; each element takes 4 bytesv[0]0x1000v[1]0x1004v[2]0x1008v[3]0x100Cv[4]0x1010v (the address of the first element)&v[i] = v + i * sizeof(int)the index is not checked: v[5] reads memory outside the array
Fig. - How an array is laid out in memory. The elements are contiguous, and the array's name is the address of the first element - hence the address formula and the lack of any bounds checking.
  • Declaring arrays with one or more dimensions
  • Computing the address of an element and the total size occupied
  • Understanding the consequences of out-of-bounds access
  • Using character strings and the null terminator
  • Implementing search and sort algorithms

2Declaring arrays

syntax
element_type array_name [dim_1][dim_2]...[dim_N];

float vect1[5];          // 5 float elements -> 5 * sizeof(float) bytes
int   sizes[4][12];      // 4 * 12 = 48 int elements

The dimensions must be integer constants known at compile time. The reserved memory area contains dim_1 × dim_2 × ... × dim_N elements of the specified type.

Initialization formEffect
int v[5] = {1, 2, 3, 4, 5};every element gets an explicit value
int v[5] = {1, 2};the first two get values, the rest become 0
int v[5] = {0};the whole array is set to zero
int v[] = {1, 2, 3};the size is deduced automatically: 3
int v[5];undefined values - contains "garbage" from memory
Indices start at zeroAn array declared with int v[5] has the elements v[0], v[1], v[2], v[3], v[4]. The element v[5] does not exist, even though the compiler accepts writing it.

3Memory layout

The elements are placed at successive addresses. The address of an element is computed as follows:

The addressing formula
&v[i] = base_address + i · sizeof(element_type)
The array's name, used on its own, is precisely the address of the first element: v is equivalent to &v[0].
ExpressionMeaningExample for int v[4]
sizeof(v)the array's total size16 bytes
sizeof(v[0])the size of one element4 bytes
sizeof(v)/sizeof(v[0])the number of elements4
vthe address of the first element&v[0]

4Indexing simulator

Change the index and watch which element is accessed and at what address it sits. Try negative indices or ones larger than the size, to see what going out of bounds means.

Accessing the elements of an integer array
Out-of-bounds access is not checkedIn C/C++ there is no automatic check on indices, neither at compile time nor at run time. Writing to v[10] for an array of 6 elements overwrites the memory of other variables, producing errors that often show up much later, in a completely different part of the program. This is the most common cause of serious security flaws.

5Two-dimensional arrays

A matrix is declared with two dimensions and is stored row by row (row-major): all the elements of the first row, then those of the second, and so on.

the layout of a 3x4 matrix in memory
int m[3][4];

row 0: m[0][0]  m[0][1]  m[0][2]  m[0][3]
row 1: m[1][0]  m[1][1]  m[1][2]  m[1][3]
row 2: m[2][0]  m[2][1]  m[2][2]  m[2][3]

in memory, consecutively:
[0][0] [0][1] [0][2] [0][3] [1][0] [1][1] ... [2][3]

address: &m[i][j] = base + (i * 4 + j) * sizeof(int)
The traversal order matters for speedTraversing by rows (for i { for j }) accesses consecutive addresses and uses the cache efficiently. Traversing by columns jumps 4 elements at a time and can be noticeably slower for large matrices.

6Character strings

C has no dedicated string type: strings are arrays of char, which must end with the null character '\0'.

the representation of the string "abc"
char s[] = "abc";

index:    0    1    2    3
value:   'a'  'b'  'c'  '\0'
         ^                ^
         first character  terminator added automatically

sizeof(s)  = 4   (includes the terminator)
strlen(s)  = 3   (counts up to the terminator)
Function (string.h)RoleCaution
strlen(s)the length, without the terminatorscans the whole string every time
strcpy(d, s)copies s into ddoes not check d's size
strncpy(d, s, n)copies at most n charactersmay not add the terminator
strcat(d, s)appends s to the end of dd must have enough space
strcmp(a, b)compares lexicographicallyreturns 0 for equality, not 1
Comparing stringsif (s1 == s2) compares addresses, not content. For content, use if (strcmp(s1, s2) == 0).

7Common algorithms

AlgorithmRequirementComplexity
Sequential searchnoneO(n)
Binary searchthe array must be sortedO(log n)
Bubble sortnoneO(n²)
Selection sortnoneO(n²)
Why complexity mattersFor 1000 elements, sequential search makes 500 comparisons on average, while binary search makes only 10. The difference becomes decisive for large volumes of data.

8Source code

statistics.c - processing a vector
#include <stdio.h>

#define MAX_SIZE 100

int main(void)
{
    int v[MAX_SIZE], n;
    int sum = 0, minimum, maximum;

    printf("Number of elements (max %d): ", MAX_SIZE);
    scanf("%d", &n);

    if (n <= 0 || n > MAX_SIZE) {
        printf("Invalid size\n");
        return 1;
    }

    for (int i = 0; i < n; i++) {
        printf("v[%d] = ", i);
        scanf("%d", &v[i]);
    }

    minimum = maximum = v[0];          // start from the first element

    for (int i = 0; i < n; i++) {
        sum += v[i];
        if (v[i] < minimum) minimum = v[i];
        if (v[i] > maximum) maximum = v[i];
    }

    printf("\nSum     = %d\n", sum);
    printf("Mean    = %.3f\n", (double)sum / n);
    printf("Minimum = %d\n", minimum);
    printf("Maximum = %d\n", maximum);

    return 0;
}
sort.c - bubble sort with an optimization
#include <stdio.h>

int main(void)
{
    int v[] = {29, 10, 14, 37, 13, 5};
    int n = sizeof(v) / sizeof(v[0]);   // the number of elements, computed automatically

    printf("Initial: ");
    for (int i = 0; i < n; i++) printf("%d ", v[i]);
    printf("\n");

    for (int i = 0; i < n - 1; i++) {
        int swapped = 0;               // optimization: detects an already-sorted array

        for (int j = 0; j < n - 1 - i; j++) {
            if (v[j] > v[j + 1]) {
                int tmp  = v[j];
                v[j]     = v[j + 1];
                v[j + 1] = tmp;
                swapped  = 1;
            }
        }
        if (!swapped) break;           // no swaps -> done
    }

    printf("Sorted:  ");
    for (int i = 0; i < n; i++) printf("%d ", v[i]);
    printf("\n");
    return 0;
}
matrix.c - matrix operations
#include <stdio.h>

#define N 3

int main(void)
{
    int m[N][N] = {
        {1, 2, 3},
        {4, 5, 6},
        {7, 8, 9}
    };
    int diagSum = 0;

    printf("The matrix:\n");
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++)
            printf("%4d", m[i][j]);
        printf("\n");
    }

    // sum of the main diagonal: elements with i == j
    for (int i = 0; i < N; i++)
        diagSum += m[i][i];
    printf("\nMain diagonal sum = %d\n", diagSum);

    // transpose: rows and columns are swapped
    printf("\nTranspose:\n");
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++)
            printf("%4d", m[j][i]);
        printf("\n");
    }
    return 0;
}
strings.c - processing strings
#include <stdio.h>
#include <string.h>

int main(void)
{
    char text[100];

    printf("Enter a word: ");
    fgets(text, sizeof(text), stdin);
    text[strcspn(text, "\n")] = '\0';        // remove the newline

    printf("Length (strlen) = %d\n", (int)strlen(text));
    printf("Space occupied  = %d bytes\n", (int)sizeof(text));

    // reverse the string in place
    int n = strlen(text);
    for (int i = 0; i < n / 2; i++) {
        char tmp        = text[i];
        text[i]         = text[n - 1 - i];
        text[n - 1 - i] = tmp;
    }
    printf("Reversed        = %s\n", text);

    // palindrome check
    int palindrome = 1;
    for (int i = 0; i < n / 2; i++)
        if (text[i] != text[n - 1 - i]) { palindrome = 0; break; }
    printf("Is palindrome?  %s\n", palindrome ? "YES" : "NO");

    return 0;
}

9Code workshop

An array is a contiguous region of memory. In Step by step mode, the panel on the right shows the entire contents of the array after every statement - including when you write outside it.

Statistics on a vector
#include <stdio.h>

int main(void)
{
    int v[8] = {23, 7, 41, 15, 8, 39, 12, 30};
    int n = 8, i;
    int minimum = v[0], maximum = v[0], sum = 0;

    for (i = 0; i < n; i++) {
        sum += v[i];
        if (v[i] < minimum) minimum = v[i];
        if (v[i] > maximum) maximum = v[i];
    }

    printf("Elements : ");
    for (i = 0; i < n; i++) printf("%d ", v[i]);

    printf("\nSum      : %d\n", sum);
    printf("Mean     : %.2f\n", (double)sum / n);
    printf("Minimum  : %d\n", minimum);
    printf("Maximum  : %d\n", maximum);
    return 0;
}
Try thisTry changing i < n to i <= n and run it: the engine warns you that you went outside the array. An ordinary compiler would say nothing, and the program would use a random value from memory.
Exercise - reversing a vector
#include <stdio.h>

int main(void)
{
    int v[6] = {1, 2, 3, 4, 5, 6};
    int n = 6, i, temp;

    /* Reverse the vector in place, without an auxiliary vector:
       swap v[0] with v[n-1], v[1] with v[n-2], and so on.
       How many swaps are needed? */

    for (i = 0; i < n; i++) printf("%d ", v[i]);
    printf("\n");
    return 0;
}

10Exercises with automatic checking

This is where you write the code. The ✓ Check button runs your program on several data sets and shows you right away where the result differs. At the end you submit the track you chose, and the instructor grades it automatically.

Every exercise has the program already started, and the comments tell you what is left to add. Write the code, press ✓ Check and read what each failed test says. If you get stuck, open the hints one at a time. You may also print messages for the user (such as Enter n:); the test looks at what you print at the end.

P1

Sum and maximum

The first line holds n (1 ≤ n ≤ 100), then n integers. Print their sum and the largest of them.

input5 3 9 -2 7 1
output18 9
#include <stdio.h>

int main(void)
{
    int v[100], n, i;
    scanf("%d", &n);
    for (i = 0; i < n; i++)
        scanf("%d", &v[i]);

    /* The array v has already been read. Go through it once more:
         - add every v[i] to a variable sum (starting at 0);
         - for the maximum, start from max = v[0] and update it.
       Print: printf("%d %d\n", sum, max); */

    return 0;
}
P2

In reverse order

Read n and then n integers. Print them in reverse order, on one line.

input4 1 2 3 4
output4 3 2 1
#include <stdio.h>

int main(void)
{
    int v[100], n, i;
    scanf("%d", &n);
    for (i = 0; i < n; i++)
        scanf("%d", &v[i]);

    /* Go through the array from the last element (index n - 1)
       down to the first (index 0): for (i = n - 1; i >= 0; i--) */

    return 0;
}
P3

How many numbers are even

Read n and then n integers. Print how many of them are even.

input5 1 2 3 4 6
output3
#include <stdio.h>

int main(void)
{
    int v[100], n, i;
    scanf("%d", &n);
    for (i = 0; i < n; i++)
        scanf("%d", &v[i]);

    /* Use a counter starting at 0 and increase it for every element
       with v[i] % 2 == 0. */

    return 0;
}
P4

Searching for a value

Read n, then n integers, then a value x. Print the position (index, from 0) of the first occurrence of x, or -1 if x does not occur.

input5 4 8 15 16 23 15
output2
#include <stdio.h>

int main(void)
{
    int v[100], n, i, x, pos = -1;
    scanf("%d", &n);
    for (i = 0; i < n; i++)
        scanf("%d", &v[i]);
    scanf("%d", &x);

    /* Go through the array; at the first match v[i] == x
       store pos = i and stop searching with break. */

    printf("%d\n", pos);
    return 0;
}
P5

Palindrome

Read a word (no spaces, at most 100 lower-case letters). Print yes if it reads the same left to right and right to left, otherwise no.

inputcojoc
outputyes
#include <stdio.h>
#include <string.h>

int main(void)
{
    char s[101];
    int i, n, ok = 1;
    scanf("%100s", s);
    n = strlen(s);

    /* Compare s[i] with s[n - 1 - i] for i from 0 up to the middle.
       At the first difference, ok = 0. At the end print "yes" or "no". */

    return 0;
}

Problems start from an empty main. The output format must be followed exactly (spaces and newlines do not matter unless the statement says otherwise), so do not print prompts. The visible tests cover only the simple cases; grading also runs hidden tests chosen to catch the edge cases.

A1

Sorting an array

Read n (1 ≤ n ≤ 1000) and n integers. Print them in ascending order, on one line. Implement the sort yourself (no qsort).

input5 5 3 9 1 3
output1 3 3 5 9
#include <stdio.h>

int main(void)
{
    /* write your solution here */

    return 0;
}
A2

Removing duplicates

Read n (1 ≤ n ≤ 1000) and n integers. Print the distinct values in order of first appearance, then, on the next line, how many distinct values there are.

input7 3 1 3 2 1 5 3
output3 1 2 5 4
#include <stdio.h>

int main(void)
{
    /* write your solution here */

    return 0;
}
A3

Diagonals and the transpose

Read n (1 ≤ n ≤ 20) and an n × n square matrix of integers. On the first line print the sum of the main diagonal and the sum of the secondary diagonal, then the transposed matrix, one row per line.

input2 1 2 3 4
output5 5 1 3 2 4
#include <stdio.h>

int main(void)
{
    /* write your solution here */

    return 0;
}
A4

Letter frequency

Read a line of text. Ignoring the difference between upper and lower case, print every letter that appears, in alphabetical order, together with its number of occurrences, one pair per line (print the letters in lower case). All other characters are ignored.

inputAna are mere
outputa 3 e 3 m 1 n 1 r 2
#include <stdio.h>

int main(void)
{
    /* write your solution here */

    return 0;
}

11Work tasks

  • Read N values into a vector and determine the sum, mean, minimum, and maximum.
  • Print the address of each element and check that the difference between addresses is sizeof(type).
  • Compute the number of elements with sizeof(v)/sizeof(v[0]) and check the result.
  • Implement bubble sort, with the early-exit optimization.
  • Write binary search on a sorted vector and compare the number of steps with the sequential version.
  • Build the transpose of a square matrix and compute the sum of both diagonals.
  • Check whether an entered word is a palindrome.
  • Intentionally write outside the bounds of a small array and observe what happens to neighboring variables.

12Extended application

ExtensionImplement the "Sieve of Eratosthenes" for finding the prime numbers up to N: use an array of flags, mark the multiples of each prime found, and at the end print only the positions left unmarked. Compare the running time with the method of checking each number through successive divisions, for N = 100,000, using the clock() function from <time.h>.

13Review questions

14Resources