Lab 7 - Data Arrays | Computer Programming

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

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 form	Effect
`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].

Expression	Meaning	Example for `int v[4]`
`sizeof(v)`	the array's total size	16 bytes
`sizeof(v[0])`	the size of one element	4 bytes
`sizeof(v)/sizeof(v[0])`	the number of elements	4
`v`	the 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.

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`)	Role	Caution
`strlen(s)`	the length, without the terminator	scans the whole string every time
`strcpy(d, s)`	copies s into d	does not check d's size
`strncpy(d, s, n)`	copies at most n characters	may not add the terminator
`strcat(d, s)`	appends s to the end of d	d must have enough space
`strcmp(a, b)`	compares lexicographically	returns 0 for equality, not 1

Comparing stringsif (s1 == s2) compares addresses, not content. For content, use if (strcmp(s1, s2) == 0).

7Common algorithms

Algorithm	Requirement	Complexity
Sequential search	none	O(n)
Binary search	the array must be sorted	O(log n)
Bubble sort	none	O(n²)
Selection sort	none	O(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>

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

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: "); printArray(v, 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:  "); printArray(v, 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) = %zu\n", strlen(text));
    printf("Space occupied  = %zu bytes\n", 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.

10Work 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.

11Extended 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>.

Data Arrays

1Lab objectives

2Declaring arrays

3Memory layout

4Indexing simulator

5Two-dimensional arrays

6Character strings

7Common algorithms

8Source code

9Code workshop

10Work tasks

11Extended application

12Review questions

13Resources