Classroom practice: Strings, Dynamic Strings

The two solution approaches lead to very different solutions. The one where the output is directed to a separate array mostly consists of copy operations, such that the input array is traversed backwards, while the output array is built forwards. The inplace reverse algorithm is a bit more tricky. In each step, two characters have to be swapped (first - last, second - before the last, etc.). Take care to stop swapping in the middle, otherwise the already reversed array is reversed back again.

In both cases the end of the output string must be handled with care, we have to make sure that the terminating zero value is at the end of the resulting string before the function returns. Note that the functions do not receive the length of the strings, since it is unnecessary because of the zero marks the end of the string.

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

void reverse_to_array(char *in, char *out) {
    /* find the position of the last valid character */
    int i = strlen(in) - 1;

    /* goes backwards and puts all the characters to the output array */
    int j = 0;
    while (i >= 0) {
        out[j] = in[i];
        ++j;
        --i;
    }

    /* closing the output string with a terminating zero value */
    out[j] = '\0';
}

void reverse_inplace(char *str) {
    /* determine the length of the string */
    int len = strlen(str);

    /* going till the middle */
    for (int i = 0; i != len/2; ++i) {
        /* str[i] <-> str[len-1-i] */
        char temp = str[i];
        str[i] = str[len-1-i];
        str[len-1-i] = temp;
    }

    /* the terminating zero value remains where it was originally */
}

int main(void) {
    char first[] = "hello world!";

    char second[20];
    reverse_to_array(first, second);
    printf("[%s] [%s]\n", first, second);

    printf("[%s]\n", second);
    reverse_inplace(second);
    printf("[%s]\n", second);

    return 0;
}

Some considerations:

• Is the capacity of the original string enough to fit the result? Yes, since the resulting string can only be shorter.
• Do we need an auxiliary array? No, since the string can only be shorter during the space removal.
• Write down a string with spaces, and the same string with the spaces removed below each other, algined to characters. The solution should now be straight forward: two variables are needed, one marks the current position in the original string (we copy the next character from this position), and an other variable that marks the target position for the next caracter.

#include <stdio.h>

void removespaces(char *t) {
    /* go through all of the characters */
    /* "from" increases in every iteration, "to" increases only if needed */
    int to = 0;
    for (int from = 0; t[from] != '\0'; ++from) {
        /* if not a space, copy it */
        if (t[from] != ' ') {
            t[to] = t[from];
            to++;
        }
    }
    t[to] = '\0';  /* terminating zero */
}

int main(void) {
    char hello[] = "H e l l o, world!";

    removespaces(hello);
    printf("Without spaces: [%s]\n", hello);

    return 0;
}

Dynamic memory management will be useful for this exercise for two reasons. First, it enables us to allocate an array in the function which it can actually return. (Remember that arrays declared as local variables can not be returned since they are removed from the memory after the function finishes. However, arrays allocated dynamically survive the death of the function). Second, we can set the size of the resulting string at run-time as needed, without wasting memory.

The input string is traversed twice: first the number of non-space characters are counted, then, in the second phase, the non-space characters are copied to the target array allocated for this purpose.

The space-removing function can return a NULL in case of any error, just like the malloc() function.

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

char *removespaces(char *inp) {
    int nonspace = 0;
    for (int i = 0; inp[i] != '\0'; ++i)
        if (inp[i] != ' ')
            nonspace += 1;
    
    char *str = (char*) malloc(sizeof(char) * (nonspace+1));
    if (str == NULL)
        return NULL;    /* :( */
    
    int j = 0;
    for (int i = 0; inp[i] != '\0'; ++i)
        if (inp[i] != ' ')
            str[j++] = inp[i];
    str[j] = '\0';
    
    return str;
}

int main(void) {
    char *nospaces = removespaces("hello word apple tree");
    if (nospaces == NULL) {
        printf("there was an error, no space-free string is available");
    } else {
        printf("%s", nospaces);
        free(nospaces);
    }
    
    return 0;
}