Classroom practice: Dynamic arrays, part I.

Gábor Horváth / Zsolt Kohári · 2020.11.06.

Dynamic memory allocation. Dynamic arrays.

Preparation for the practice:

  • The lecture notes on arrays should be reviewed.
  • The lecture notes on pointers and strings should be reviewed.
  • The lecture notes on dynamic memory management should be reviewed.

1. Where is the mistake?

The code snippets contain at least one (or potentially more) errors. Find them! Explain what the problem is! What makes the codes wrong? What is the principal problem with them? How to fix them?

int *fun(void) {
    int i = 2;
    return &i;
}

Solution

The local variable i is going to be destroyed right after the function returns. We have returned its address, but the calling function can not use it, since it points to a non-existing value. Such pointers are called dangling pointer. If we are interested in the value of the variable, we need to return that: the return type of the function should be int, and return i.

int *fun(void) {
    int array[100];
    array[0] = 2;
    return array;
}

Solution

The problem is the same as before. The function returns the starting address of the array, but the array gets removed from the memory right after the function returns, its memory allocation gets released. Hence, the calling function receives a useless pointer. There are two ways to fix this issue. First, the array can be allocated in the caller, as:

void fun(int *array) {
    array[0] = 2;
}

...
int array[100];
fun(array);
...

Or, it can be solved with dynamic memory allocation:

int *fun(void) {
    int *array;
    array = (int*) malloc(sizeof(int) * 100);
    array[0] = 2;
    return array;
}
/* concatenates two strings to a dynamically allocated array */
char *concatenate(char const *a, char const *b);

printf("%s", concatenate("apple", "tree"));

Solution

Memory allocated dynamically has to be released after use. The concatenate function returns a pointer to the allocated memory, but this pointer has to be used for two different purposes: to print the string in printf(), then to call the free() to release the memory. Hence, we need to introduce a variable to store the pointer:

char *s = concatenate("apple", "tree");
printf("%s", s);
free(s);
Forgetting about releasing the memory leads to memory leak.

2. Values backwards – again

The specification is very similar to a lab task of week 8, except the number of values is not known in advance: we have to ask the user to enter real numbers, and print it at the end in a reverse order. The input sequence of values is terminated (when the user enters –1, stop and print the result). To ensure that there are no restrictions on the number of real values entered by the user, increase the size of the dynamic array by one each time a new number is entered!

Hint

The dynamic array can not be allocated at once if the number of elements is not known in advance. That is why we need to resize the dynamic array after every reading of a new entry. The steps are:

  1. Allocating a new array.
  2. Copy existing values from the old.
  3. Release the old array.
  4. Make your main pointer point to the new.
  5. Put the new value in.

Remember, a pointer can be set to point to any allocated memory segment! The main rule is to remember the address of each dynamically allocated memory segment. If we lose an address, there is no way to access the stored data, neither can the allocated memory be released.

More hint

At the very beginning, before any real value read, there is no need for an array; the pointer can be NULL. It could be malloc(0*sizeof(double)) as well (but it must be released later). malloc(0) and free(NULL) are valid calls. This way the separate treatment of the "no array" (empty) case is not necessary in several algorithms.

Solution

The steps mentioned above are marked in the code as comments.

Initialy, when there are no numbers, the array does not exist yet, in this case the pointer can be NULL. In an alternative solution we could have written malloc(0*sizeof(double)), too, since malloc(0) is a valid memory allocation, just like free(NULL) is valid, too, to make such algorithms easier to implement.

#include <stdio.h>
#include <stdlib.h>

int main(void) {
    /* reading the numbers */
    printf("Enter the numbers, terminated by -1!\n");
    int cnt = 0;
    double *numbers = NULL;
    double newnum;
    while (scanf("%lf", &newnum) == 1 && newnum != -1) {
        /* extend the array by one element */
        double *newarr = (double*) malloc(sizeof(double) * (cnt+1)); // 1
        for (int i = 0; i < cnt; ++i)
            newarr[i] = numbers[i]; // 2
        free(numbers); // 3
        numbers = newarr; // 4
        numbers[cnt] = newnum; // 5
        ++cnt;
    }

    for (int i = cnt-1; i >= 0; --i) {
        printf("%f\n", numbers[i]);
    }

    free(numbers);

    return 0;
}

3. Less than the average

Let us write a function that receives a double array and returns a new, dynamically allocated array with the elements smaller than the average! The function should return the array and its size through the parameter list, as pointers. The return value itself should be true if the operation was successful and false if not.

Write a program to demonstrate how to use the function!

Solution

The principle of the solution: we need to allocate a double array to store the less-than-average elements. But what should be the size of the array? We need to count it before allocating the array, like in the previous exercise. Hence, the steps are:

  1. calculating the average,
  2. counting how many elements are below the average,
  3. allocating the target array (we know the capacity of this array from the previous step),
  4. copy the elements to the target array.

Let us focus on the syntactical elements! The double **newarray seems horrific at the first sight, but it is actually not something new: the target array (of type double*) is returned through the parameter list, as a pointer, leading to double**.

#include <stdbool.h>
#include <stdio.h>
#include <stdlib.h>

int separate(double *source, int srclen, double **target, int *trglen) {
    /* calculating the average */
    double sum = 0;
    for (int i = 0; i < srclen; ++i)
        sum += source[i];
    double average = sum/srclen; 

    /* determining the length of the target array */
    int cnt = 0;
    for (int i = 0; i < srclen; ++i)
        if (source[i] < average)
            ++cnt;            

    double *newarr = (double *) malloc(sizeof(double)*cnt);
    if (newarr == NULL)
        return 0;

    int index = 0;
    for (int i = 0; i < srclen; ++i)
        if (source[i] < average) {
            newarr[index] = source[i];
            ++index;
        }

    *target = newarr;
    *trglen = cnt;
    return 1;
}


int main(void) {
    double numbers[5] = {3.4, 8.5, 4.6, 9.1, 1.2};

    double *narr;
    int nlen;
    separate(numbers, 5, &narr, &nlen);
    for (int i = 0; i < nlen; ++i)
        printf("%f ", narr[i]);
    free(narr);

    return 0;
}