Laboratorium 12: Anagramy

Zadanie

Program czyta dwa napisy, sprawdzający czy są anagramami (to znaczy występują w nich dokładnie te same litery) i wyświetla o tym informację.

Algorytm

Jak zwykle można problem rozwiązać na wiele sposobów.

Policzyć wystąpienia wszystkich liter w jednym napisie i porównać z wystąpieniami w drugim. (Jeżeli w pierwszym napisie litera a wystąpi dwa razy i litera b trzy razy, a w drugim a trzy razy a b dwa razy — napisy nie mogą być anagramami!).
Przeglądać kolejne litery w napisie pierwszym i „odznaczać" w drugim. Jeżeli jakaś litera jest w napisie pierwszym, a nie ma w drugim — wyrazy nie są anagramami. Jeżeli po przejrzeniu całego pierwszego napisu zostaną jakieś nieodznaczone litery w drugim — napisy nie są anagramami.
Napisy o różnej długości nie mogą być anagramami.
…

Długość napisu

Funkcja strlen podaje długość napisu:

#include <string.h>
...
size_t strlen(const char *s);

(Uwaga, typ size_t to (najprawdopodobniej) unsigned long int.)

Użycie:

printf ( "Dlugosc napisu \"Ala ma kota\", to %d\n", (int) strlen("Ala ma kota") );
char * tekst[100];
scanf("%s", tekst);
printf( "Dlugosc wczytanego tekstu to: %d\n", (int) strlen(tekst) );

(Ten (int) przed wywołaniem funkcji strlen jest po to, aby móc wydrukować wartość size_t używając specyfikacji %d.)

Wielkie/małe litery

Funkcje tolower i toupper dokonują konwersji z wielkich do małych (i odwrotnie). Jeżeli litera jest już „mała" („wielka") nie ulega zmianie.

#include <ctype.h>
...
int toupper(int c);
int tolower(int c);
...
char a = tolower('A');

Konwersja dokonywana jest na pojedynczej literze!

Funkcje islower i isupper odpowiadają na pytanie czy litera jest mała/wielka. Gdy prawda — zwracają wartość różną od zera.

#include <ctype.h>
...
int islower(int c);
int isupper(int c);

Funkcje testują pojedynczy znak!

Założenia

Po pierwsze należy rozstrzygnąć czy program będzie case sensitive (czyli czy będzie rozróżniał wielkie i małe litery).
Po drugie należy podjąć decyzję, czy program będzie uwzględniał odstępy czy nie. Można rozważyć funkcję, której jednym z parametrów będzie informacja, czy ma uwzględniać odstępy.
Zakładamy, że oba napisy będą dostarczane przez użytkownika.
Funkcja scanf() nie pozwala (łatwo) wczytać napisu z odstępami.
Rozstrzygnąć trzeba czy program wprowadza ograniczenia na długość sprawdzanego tekstu.
Ani funkcja scanf() ani ~~gets()~~¹ nie zwracają uwagi na długość dostarczonego z klawiatury tekstu; nie sprawdzają czy nie przekracza on długości tablicy, do której tekst ma być wczytany. Funkcja scanf() standardowo czyta do pierwszego odstępu co (ale tylko nieco) zmniejsza prawdopodobieństwo przepełnienia bufora.
Funkcja fgets() pozwala ograniczyć liczbę czytanych znaków².

Użycie funkcji `fgets`

Prototyp funkcji fgets() wygląda następująco:

char *fgets(char *s, int size, FILE *stream);

pierwszy argument funkcji to adres bufora (tablicy znakowj) do którego wpisany zostanie przeczytany z tablicy tekst,
drugi argument to długość bufora (w znakach),
trzeci argument to opis (adres struktury danych opisujących) strumienia wejściowego, z którego czytamy; w przypadku standardowego strumienia wejściowego — stdin.

Funkcja fgets czyta tekst ze strumienia. Znak nowej linii zastępowany jest znakiem o kodzie ASCII 0 (koniec tekstu); jeżeli znaków jest więcej niż „długość bufora" czytanych jest tylko tyle znaków, żeby nie przepełnić bufora, a na końcu dodawany jest znak o kodzie ASCII 0.

Algorytm odczytu napisu

Przedstawiam poniżej alternatywny sposób czytania tekstów z terminala. Może on również być wykorzystany (po drobnych modyfikacjach) do czytania danych innego typu o nieznanej długości.

Najpierw przydzielana jest początkowa pamięć do bufora danych (linia 20).
Algorytm czyta kolejne znaki ze standardowego wejścia używając funkcji getchar() (linia 38). Funkcja ta zwraca kod ASCII przeczytanego znaku lub specjalny kod EOF gdy wystąpi błąd lub system powie, że strumień wejściowy jest już zamknięty³.
Każdy odczytany znak wstawiany jest do bufora (linia 38).
Gdy bufor się wypełni (linia 46) — jego wielkość powiększana jest o kolejny kwant (linia 48).
Gdy odczytany znak ma kod '\n' (znak przejścia do nowej linii) lub EOF (koniec danych) (linia 39) w buforze zastępowany jest znakiem o kodzie ASCII 0 (koniec tekstu), a nadmiarowa pamięć jest zwalniana (linia 42).

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
/*
 * napis.c
 * Copyright 2016 wojciech myszka <wojciech.myszka@pwr.edu.pl>
 */
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
char * czytaj(void)
{
/*
 * dN zawiera informacje o ilości dodawanych bajtów do bufora.
 * Założymy, że będzie to 10.
 */
#define dN 10
    int N = dN; // początkowy przydział
    int i;
/*
 * Przydzielamy funkcją malloc pamięć na 10 znaków
 */
    char * bufor, * bufor1;
    bufor = (char *) malloc(N);
/*
 * Gdy funkcja malloc zwróci wartość NULL
 * oznacza to, że nie udało się przydzielić
 * pamięci. Nawet jak taka sytuacja jest mało
 * prawdopodobna, trzeba ją uwzględnić.
 * W takim przypadku nie będziemy już czytali
 * żadnych danych, a funkcja zwróci wartość NULL
 */
    if ( bufor == NULL )
        return bufor;
/*
 * Teraz rozpoczniemy odczyt znaków
 */
    i = 0; // Liczba przeczytanych znaków
    while ( 1 )
    {
        bufor[i] = getchar();
        if ( bufor[i] == EOF || bufor[i] == '\n' )
        {
            bufor[i] = 0; // koniec tekstu
            bufor = realloc(bufor, i + 1); // zwalniamy nadmiarową pamięć
            return bufor;
        }
        i++;
        if ( i >= N ) // Czy skończyła się przydzielona pamięć?
        {
            bufor1 = realloc(bufor, i + dN);
            if (bufor1 == NULL)
            {
//              System odmówił zwiększenia pamięci
                bufor[N - 1] = 0; // kończymy tekst
                return bufor;     // i konczymy pracę
            }
            bufor = bufor1;
            /*
             * Zwiększamy informację o długości przydzielonego
             * bufora
             */
            N += dN;
            printf("%p %d\n", bufor, N);
        }
    }
}

int main(int argc, char **argv)
{
    char * tekst;
    char bufor[10];
    tekst = czytaj();
    if ( tekst != NULL ) // Sprawdzamy czy coś przeczytane
        printf("przeczytalem: %d znakow\n \"%s\"\n",
               (int) strlen(tekst), tekst);
    free(tekst); // Zwalniamy przydzieloną pamięć
    tekst = fgets(bufor, 10, stdin);
    printf("%p , %p\n", tekst, bufor);
    printf( "|%s| %d \n", bufor, (int) strlen(bufor) );
    return 0;
}

Funkcja zwraca adres początku bufora.

Z tej nigdy nie korzystamy! ↩︎
Jest to jedyny poprawny sposób wczytywania tekstów. ↩︎
Inaczej mówiąc wystąpi sytuacja podjęcia próby czytania poza końcem pliku. ↩︎