GESPRG: Uitwerking huiswerk les 10.

© Harry Broeders.

Deze pagina is bestemd voor studenten van de Haagse Hogeschool - Academie voor Technology, Innovation & Society Delft.

Huiswerk les 10:

Uitwerking:

14. De opgave is: schrijf een functie die een string als argument pakt en die de waarde 1 aflevert als de string een palindroom is, en de waarde 0 aflevert als dit niet zo is. Een palindroom is een string die achterstevoren gelezen weer zichzelf produceert. Bijvoorbeeld: "ABBA", "maandnaam", enz. Zie eventueel: http://nl.wikipedia.org/wiki/Palindroom.

Als eerste bepaal ik het prototype van de functie (de functie declaratie). De returnwaarde is de waarde 1 of de waarde 0, dat zijn gehele getallen dus het returntype is een int. De parameter is een string. In C wordt een string opgeslagen in een character array en afgesloten met een speciaal karakter, het karakter '\0'. Zie eventueel paragraaf 6.9. Het parametertype is dus char[] en het is niet nodig om het aantal karakters van de string als aparte parameter door te geven omdat het karakter '\0' het einde van de string markeerd. Het prototype van de functie is dus: 

int isPalindroom(char string[]);

Voordat ik de functie ga ontwerpen (bedenken) en implementeren (coderen) schrijven ik eerst een testprogramma 6_18_14a.c : 

#include <stdio.h>

int isPalindroom(char string[]) {
    // dummy implementatie
    return -1;
}

int main(void) {
    int errors = 0, i;
    char* testStrings[] = { "ABBA", "ABA", "maandnaam", "", "ABB", "ABBB", "ABAA"};
    int expectedResults[] = {    1,     1,           1,  1,     0,      0,      0};
    for (i = 0; i < sizeof testStrings / sizeof testStrings[0]; i = i + 1) {
        if (isPalindroom(testStrings[i]) != expectedResults[i]) {
            printf("Test isPalindroom(\"%s\") FAALT\n", testStrings[i]);
            errors = errors + 1;
        }
    }
    printf("%d tests GEFAALD!\n", errors);
    getchar();
    return 0;
}

De uitvoer van dit programma is:

Test isPalindroom("ABBA") FAALT
Test isPalindroom("ABA") FAALT
Test isPalindroom("maandnaam") FAALT
Test isPalindroom("") FAALT
Test isPalindroom("ABB") FAALT
Test isPalindroom("ABBB") FAALT
Test isPalindroom("ABAA") FAALT
7 tests GEFAALD!

Ik kan deze opgave op verschillende manieren aanpakken.

Als eerste aanpak ga ik zoveel mogelijk gebruik maken van dingen die ik al eerder heb gemaakt. Ik bedenkt het volgende. Ik kan een string eenvoudig omkeren met (een beetje aangepaste versie van) de functie reverse en ik kan als ik de omgekeerde string heb eenvoudig kijken of de orginele en de omgekeerde string gelijk zijn met behulp van de standaard libary functie strcmp. Ik moet dan alleen wel een kopietje maken, met de standaard library functie strcpy wat ik kan omdraaien omdat ik anders het orgineel kwijt ben. Zie 6_18_14b.c : 

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

/* functies wissel en reverse zoals besproken in de les maar dan aangepast om te werken met char i.p.v. int */

void wissel(char *p, char *q) {
    char hulpje = *p;
    *p = *q;
    *q = hulpje;
}

void reverse(char a[]) {
    int first = 0, last = strlen(a) - 1;
    while (first < last) {
        wissel(&a[first], &a[last]);
        first = first + 1;
        last = last - 1;
    }
}

/* onderstaande implementatie van isPalindroom werkt alleen in C99 (en dus niet in Microsoft Visual C 2010) */

int isPalindroom(char string[]) {
    char kopie[strlen(string) + 1];
    strcpy(kopie, string);
    reverse(kopie);
    return strcmp(string, kopie) == 0;
}

int main(void) {
    /* idem als hierboven */
}

Toelichting:

Er is echter een probleem met deze oplossing: de regel char kopie[strlen(string) + 1]; is niet toegestaan in C89. De Microsoft Visual compiler geeft de volgende foutmelding: "expected constant expression". De grootte van een array moet in C89 namelijk tijdens compile-time bekend zijn. We kunnen dit probleem vermijden door deze regel te vervangen door char kopie[100]; maar dit zal tot run-time fouten leiden als we de functie isPalindroom aanroepen met een string die 100 of meer karakters bevat. In C99 is het wel toegestaan om een array aan te maken waarvan de grootte tijdens het compileren nog niet bekend is. Dit wordt een VLA (variabele-length array) genoemd. Zie eventueel: http://en.wikipedia.org/wiki/Variable-length_array.

Als ik dit programma compileer met gcc (onder Linux) voor C99 dan blijkt het inderdaad te werken:

$ gcc -std=c99 -Wall 6_18_14b.c
$ a.exe
0 tests GEFAALD!

Er is dus (in C98) een andere aanpak gewenst. Ik bedenk dat het helemaal niet nodig is om de string te verwisselen. Ik kan de karakters die ik zou gaan verwisselen meteen met elkaar vergelijken. Zodra ik twee karakters vind (die ik zou gaan verwisselen) die niet gelijk zijn aan elkaar dan weet ik dat de string geen palindroom is. Als ik geen twee karakters tegenkom (die ik zou gaan verwisselen) die ongelijk zijn aan elkaar dan is de string dus een palindroom. Zie 6_18_14c.c : 

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

int isPalindroom(char a[]) {
    int first = 0, last = strlen(a) - 1;
    while (first < last) {
        if (a[first] != a[last]) {
            return 0;
        }
        first = first + 1;
        last = last - 1;
    }
    return 1;
}

int main(void) {
    /* idem als hierboven */
}

De uitvoer van dit programma is:

0 tests GEFAALD!