Słownik

Napisz program generujący słownik wyrazów zawartych w dowolnym pliku tekstowym. Dla podanego pliku (lub po wczytaniu tekstu ze strumienia wejściowego) program wyświetla posortowaną alfabetycznie listę występujących w tekście wyrazów oraz liczbę wytapiań danego wyrazu w tekście.

Przykładowe wyjście programu:

ala      5
kota     2
ma       1

Duże i małe znaki są nierozróżnialne - słownik wypisuje wyłącznie słowa pisane małymi literami

Zakładamy, że: pojedyncze słowo to dowolny ciąg znaków alfabetycznych (wyłącznie litery [a-zA-Z]). Wszystkie pozostałe znaki są separatorami wyrazów.

Dla ułatwienia można zaimplementować funkcję getword, która pobiera kolejne słowo ze strumienia (wejściowego, z pliku). Funkcja wczytuje do tablicy pierwsze napotkane w strumieniu słowo (po pominięciu wszystkich początkowych znaków które nie są literami) i zwraca wartość sygnalizującą czy słowo zostało wczytane (np. może zwracać długość słowa gdzie wartość 0 zwracana jest w przypadku dotarcia do końca strumienia w którym nie wystąpiło już żadne słowo).

Słownik generowany jest w oparciu o drzewo binarne.

Utwórz projekt w środowisku VisualStudio, dodaj do niego plik nagłówkowy slownik.h zawierający deklarację funkcji obsługi drzewa oraz plik źródłowy słownik.c z definicjami tych funkcji.
Przykładowa zawartość pliku slownik.h:

struct tree
{
    char *word;
    int count;
    struct tree *left, *right; 
};
 
struct tree* add(struct tree *d,char *word);
void print(struct tree *d);

Funkcja add(struct tree *d,char *word) dodaje nowe słowo do słownika (drzewa). Wartością zwracaną jest wskaźnik do bieżącego węzła w drzewie. Słowo umieszczane jest w drzewie zależnie od kolejności słownikowej (alfabetycznej).
Algorytm dodawania słowa
Dane: węzeł d i napis s

1. jeżeli d jest pusty utwórz nowy węzeł zawierający słowo s, ustaw licznik na 1 i idź do kroku 5
2. jeżeli słowo zawarte w węźle d jest takie samo jak s to zwiększ licznik i idź do kroku 5
3. jeżeli słowo zawarte w węźle d powinno stać dalej w słowniku niż s to dodaj słowo w lewej podgałęzi i idź do kroku 5
4. dodaj słowo s do prawej podgałęzi
5. zwróć d

Funkcja print(struct tree *d) wypisuje zawartość słownika, czyli posortowaną listę słów wraz z liczbą wystąpień danego słowa w pliku.

• Dopisz definicje funkcji add i print w pliku źródłowym slownik.c
• Program niech pobiera plik wejściowy jako argument wywołania aplikacji, jeżeli argumentu brakuje wówczas czytany jest tekst ze standardowego wejścia

 slownik.exe plik_tekstowy

Przydatne funkcje:

• string.h : strcpy, strcmp, strlen, strdup
• ctype.h : isalpha, tolower

Różnice miedzy C i C++

• Zamień rozszerzenia nazw plików *.c → *.cpp
• Zamień wywołania funkcji malloc() i free() na wywołania operatorów new i delete
• Spróbuj użyć strumieni <iostream> do wczytywania i wyświetlania słów z terminala lub pliku (cout, cin)
• Spróbuj wykorzystać obiekty typu <string> zamiast tablic char* do zapamiętywania słów w węzłach drzewa
• Jeżeli wykorzystujesz nadal którąkolwiek funkcję z biblioteki standardowej C zastąp ją odpowiednikiem ze standardowej biblioteki C++
  • C standard library
  • C++ Standard_Library
• Struktura w C++ jest klasą, usuń zbędne słowo kluczowe struct przy deklaracjach zmiennych typu drzewo lub uczyń węzeł drzewa klasą.
• Użyj referencji zamiast wskaźników tam gdzie uznasz to za stosowane
• Utwórz klasę „slownik”, korzeń drzewa uczyń polem prywatnym zaś funkcje dodaj() i wyswietl() przepisz jako metody publiczne tej klasy (Zobacz zadanie Słownik obiektowo)