Ćwiczenie 8 - struktury, operacje na napisach, listy jednokierunkowe

Polecane strony manuala:

1. strcpy(3)
2. strcmp(3)

Przykłady pomocnicze:

1. structure1.c - przykładowa prosta struktura.
2. string.c - operacje na ciągach znaków - kopiowanie i porównywanie.
3. structure2.c - struktura, oraz przykład użycia wskaźnika do struktury.
4. types.c - kilka przykładowych definicji typów.
5. list.c - przykład prostej listy jednokierunkowej.
6. list2.c - powyższy przykład, przerobiony tak, by działał w sposób bardziej ogólny, tzn. dla dowolnej długości listy.

Operacje na napisach

W języku C napisy reprezentowane są przez tablice znaków (tablice typu char), każdy napis jest zakończony przez znak '\0':

Gdy kopiujemy lub konstruujemy napis - ważne jest by zwrócić uwagę na to czy nie przekraczamy zadeklarowanej długości napisu (i powodujemy przez to nadpisanie innego obszaru pamięci), oraz czy funkcje których używamy - terminują go znakiem '\0'. Napis nie posiadający takiego terminatora - może być również źródłem kłopotów - gdyż standardowe funkcje operujące na napisach przeszukują je aż do wystąpienia '\0' ...
Więcej informacji na temat napisów:

• przykład string.c
• lista funkcji z biblioteki standardowej zadeklarowanych w <string.h> wraz z opisem.
• String and Array Utilities - rozdział na temat napisów i tablic pochodzący z opracowania pt: "GNU C Library".
• zajęcia laboratoryjne

Listy jednokierunkowe

Lista jednokierunkowa to ciąg struktur (czyli obszarów pamięci reprezentowanych w języku C przez zmienne typu struct) takich, że każda struktura zawiera oprócz odpowiednich danych wskaźnik do następnej struktury. Struktura kończąca listę - zawiera wskaźnik do NULL. Strukturę na samym początku takiej listy nazywamy korzeniem. Listę taką, można schematycznie przedstawić, jak na poniższym rysunku:

Zaletą takiej listy jest dogodność z jaką możemy wstawić w jej środek dodatkowy element:

Więcej na temat list:

• przykłady: structure1.c, structure2.c, list.c list2.c;
• Linked List Basics (fragment "Stanford CS Education Library")
• zajęcia laboratoryjne

Zadanie:

Proszę dokładnie przejrzeć, skompilować i uruchomić podane przykłady pomocnicze. Następnie proszę napisać program, który tworzy skorowidz na podstawie pliku tekstowego podanego jako argument wywołania, przy użyciu listy jednokierunkowej. Skorowidz powinien zawierać alfabetyczną listę wystąpień wszystkich słów w danym tekście, wraz z liczbą wystąpień danego słowa (przez słowo rozumiemy każdy ciąg znaków niezawierający znaków "białych" tzn. spacji, tabulatora, znaku nowej linii itd. czyli tak jak wczytuje je funkcja scanf ). Zatem dla tekstu:

program powinien wyświetlić:

Struktura w zadaniu powinna zawierać trzy pola:

• tablicę do przechowywania jednego słowa,
• licznik wczytanych słów,
• wskaźnik do następnej struktury.

Listę w naszym przykładzie najlepiej tworzyć - od razu ją sortując, tzn. każde nowo wczytane słowo (element struktury) jest porównywane z kolejnymi z listy (przy użyciu funkcji strcmp), a następnie cała struktura umieszczana jest w odpowiednim miejscu w liście. Jeśli w liście wystąpiło już takie słowo (wystąpiło już wcześniej we wczytanym tekście), wówczas tylko zwiększamy licznik w odpowiadającej mu strukturze o 1.

W celu ułatwienia zadania, można posłużyć się przygotowanym "szablonem": index.c. Zawiera on już drobne, pomocnicze fragmenty programu.
Program proszę przetestować na pliku: example.txt i porównać wynik z rozwiązaniem: solution.txt.

* Zadanie dodatkowe (nieobowiązkowe):
Proszę tak zmodyfikować powyższy program, aby:

• jako słowa traktował tylko ciągi znaków alfanumerycznych (czyli np. dla ciągu "red, green8, blue" jako osobne słowa policzy "red", "green8" oraz "blue", ignorując przecinki. Patrz strona manuala isalpha(3) - isdigit(3);
• sortował z uwzględnieniem ustawień locale (czyli np. potrafił sortować poprawnie z użyciem polskich znaków). Patrz strony manuala: locale(7), setlocale(3), strcoll(3) ;
• posiadał opcję wywołania powodującą, iż traktuje tak samo duże i małe litery w tekście (konwertując duże do małych) - patrz manual tolower(3);
• zapisywał dodatkowo (do oddzielnego pliku) skorowidz posortowany względem częstości wystąpień poszczególnych słów.