(Tu podajemy temat zadania w formie, jaka została podana przez prowadzącego)

początek

(Ten rozdział zawiera sprawozdanie z czynności wykonanych przed przystąpieniem do pisania kodu. Jest to ważny etap, którego nie należy opuszczać, ani zaniedbywać nawet w prostych zadaniach laboratoryjnych. W rozdziale tym należy tu zastanowić się, wybrać i uzasadnić odpowiedni wybór:
- struktury danych:
dane można przechowywać w strukturze statycznej, o ograniczonym z góry rozmiarze, jak łatwa w użyciu tablica czy rekord, albo w strukturze dynamicznej (lista, drzewo, graf),
- algorytmu:
 algorytmy różnią się złożonością czasową i pamięciową, czasem wymagają pewnej postaci danych czy wiedzy o nich, które to warunki w konkretnym zadaniu wykluczają pewne algorytmy, a faworyzują inne.

Jeśli do rozwiązania problemu niezbędne było wykorzystanie podstaw teoretycznych opartych na pewnej dziedzinie wiedzy, jak matematyka lub fizyka (np.: obliczanie całki oznaczonej metodą trapezów lub wykreślanie wykresu funkcji; wykreślanie trajektorii ruchu kuli armatniej, bądź symulacja odbijania bil na stole bilardowym), należy te podstawy (wzory, stałe, twierdzenia, modele) przytoczyć i krótko przybliżyć, na poziomie popularnonaukowym, wystarczającym do zrozumienia działania programu. W tym rozdziale mogą pojawic się odnośniki do popzycji literaturowych.
Wszystkie kolejne rozdziały dokumentacji dotyczyć już będą gotowego produktu i powinny jednoznacznie opisywać to, co zostało zrobione.)

2.1. Załadowanie danych

Zakładamy, że plik tekstowy z wyrazami do posortowania jest zbudowany tak, ze w każdej linii tekstu znajduje się jeden wyraz. Użytkownik, który będzie chciał sobie posortowac wyrazy, bedzie musiał sobie taki plik przygotować. Program nie będzie sprawdzał poprawności pliku z danymi, ponieważ jego format jest bardzo prosty i ryzyko popełnienia błędu przez użytkownika podczas tworzenia pliku jest stosunkowo niewielkie.
Ponieważ liczba wyrazów, które mogą wystąpic w pliku wejściowym nie jest określona, dlatego należy je przechować w dynamicznie rezerwowanym obszarze pamięci operacyjnej. Wybierzmy sposób organizacji pamięci określany nazwa listy jednokierunkowej [1]. Każdy element listy będzie wskazywał na jeden wyraz (dzięki zastosowaniu wskaźnika na łańcuch znakowy unikamy ograniczenia długości sortowaych wyrazów do określonej ilości liter) oraz na element następny. Schematycznie strukturę taką można przedstawić tak jak na rys.1.

Rys.1. Przykład dynamicznej struktury listowej

Zakładamy, że wszystkie wszystkie wyrazy z pliku zmieszczą się razem w pamięci operacyjnej przy użyciu struktury z rys.1.

2.2. Sortowanie

Wczytane wyrazy będą podlegać sortowaniu leksykograficznemu (wg porządku alfabetycznego) oraz wg ilości liter. Temat zadania precyzuje, ze sortowanie należy wykonać metodą bąbelkową [2]. Metoda ta opiera sę na na zasadzie porównywania i ewentualnej zamiany dwóch elementów leżących obok siebie. Przeanalizujemy ja na przykładzie sortowania kilku przykładowych wyrazów narastająco wg porządku leksykograficznego. Kolejno porównujemy z sobą pary sąsiadujących wyrazów, a następnie zamieniamy miejscami jeśli trzeba. Podkreśleniem zaznaczono porównywane słowa, a kolorem zaznaczono słowa zamienione miejscami:

mama, tata, dziadek, babcia -> bez zamiany
mama, tata, dziadek, babcia -> zamiana
mama, dziadek, tata, babcia -> zamiana
mama, dziadek, babcia, tata

Przystępujemy do kolejnego przebiegu sortowania:
mama, dziadek, babcia, tata -> zamiana
dziadek, mama, babcia, tata -> zamiana
dziadek, babcia, mama, tata -> bez zamiany
dziadek, babcia, mama, tata

I ostatni, trzeci przebieg porównywania:
dziadek,babcia, mama, tata -> zamiana
babcia,dziadek,mama, tata -> bez zamiany
babcia,dziadek, mama, tata-> bez zamiany
babcia,dziadek, mama, tata

Podany przykład pokazuje, że w drugim przebiegu niepotrzebne jest porównywanie dwóch ostatnich słów, ponieważ sa one już uszeregowane we właściwej kolejności. Podobnie w trzecim przebiegu - nie ma potrzeby wykonywania dwóch ostatnich porównań.

Powyżej przeanalizowano w jak sortować, nalezy jeszcze zastanowić się jak to realizowac w praktyce. Zauważmy, ze elementy listy nie zawieraja zamienianych słów, lecz tylko wskaźniki do nich. Dlatego tez aby dokonac zamiany wyrazów, nie trzeba zamieniać miejscami elementów listy, lecz zamienić tylko wartości odpowiednich wskaźników (korzystając ze wskaźnika pomocniczego), tak jak pokazano na ry.2.

2.3. Zapis wyników

Ostania częścią programu jest zapis posortowanych wyrazów do pliku tekstowego. Nazwa tego pliku zostanie podana przez użytkownika, bądź zostanie uzta nazwa domyślna. Plik ten będzie miał taki sam format jak plik wejściowy, tzn. każdy wyraz zostanie umieszczony w oddzielnej linii. Po tej operacji zwolnione zostaną obszary zarezerwowane w pamięci operacyjnej na wyrazy, oraz elementy listy.
 

Literatura
[1] A.Drozdek, D.L.Simon: Struktury danych w języku C. WNT, Warszawa 1996, str. 79-86.
[2] N.Wirth: Algorytmy + struktury danych = programy. WNT, Warszawa 1989, str. 77-80.

początek

(Rozdział ten jest inaczej instrukcją użytkownika i – mówiąc najogólniej – powinno się tu znaleźć wszystko to, co przeciętny użytkownik powinien się dowiedzieć o programie w celu jego prawidłowego użytkowania. Specyfikacja zewnętrzna dotyczy interfejsu użytkownika, sposobu obsługi programu, formatu danych wejściowych (zadawanych) i wyjściowych (otrzymywanych).
Jeżeli użytkownik jest świadomy istnienia pliku z danymi, bo ma możliwość pobierania danych lub zapisywania wyników w pliku o podanej nazwie, należy tu opisać format danych w tym pliku i jego przeznaczenie.
W ramach opisu obsługi lub osobno należy wymienić wszystkie komunikaty produkowane przez program, wraz z ich wyjaśnieniami i, w przypadku komunikatów o błędach, zalecanymi reakcjami na te sytuacje.)

3.1. Sposób uruchomienia programu
Program pracuje w środowisku Dos/Windows. Aby go poprawnie uruchomić należy w linii poleceń systemu operacyjnego podać nazwę pliku z kodem wykonywalnym oraz nazwę pliku z wyrazami do posortowania, oraz nazwę pliku, w którym ma się znaleźć posortowany ciąg tych wyrazów. Podanie nazwy pliku wyjściowego nie jest konieczne. W przypadku jej braku, wyniki zostaną zapisane do pliku o nazwie "wynik.txt".

sort <nazwa_pliku_wejściowego> [nazwa_pliku_wyjściowego]

Przykładowe uruchomienie programu to n.p.:

sort slownik.dat nowy.dat
lub
sort dane.dat

gdzie slownik.dat i dane.dat to pliki tekstowy zapisane w ściśle określonym formacie.

Prawidłowe uruchomienie programu:
sort <nazwa_pliku_wejściowego> [nazwa_pliku_wyjściowego]
gdzie:
nazwa_pliku_wejściowego - nazwa pliku z wyrazami do posortowania
nazwa_pliku_wyjściowego - nazwa pliku zawierającego odpowiednio posortowany ciag wyrazów

3.2. Format danych wejściowych

Plik z danymi wejściowymi powinien być plikiem tekstowym zapisanym w formacie ASCII, czyli jeden znak powinien zajmować jeden bajt. Danymi do sortowania są wyrazy wykorzystujące 10 znaków cyfr oraz 24 znaki  liter, co oznacza że wyrazy nie mogą zawierać "polskich" znaków. Wyrazy powinny być umieszczone w pliku tak, aby każdy znajdował się w oddzielnej linii, np.:

mama
tata
dzadek
babcia

3.3. Obsługa programu

Po poprawnym uruchomieniu programu w górnej części ekranu pokazuje się proste menu:

Po naciśnięciu jednego z klawiszy oznaczonych cyframi: 1, 2, 3, 4 i potwierdzeniu klawiszem "enter" następuje uruchomienie odpowiedniej operacji sortowania. Następnie program zapisuje posortowane wyrazy w pliku tekstowym i wypisuje komunikat:

Posortowane wyrazy zapisano w pliku "yyy"

gdzie yyy oznacza nazwę podaną jako drugi parametr w linii wywołania programu, bądź oznacza napis wynik.txt. Następnie program kończy działanie zwracając do systemu wartość 0.

Program może równiez pokazać następujące komunikaty w przypadku nieprawidłowego działania:

Nie znaleziono pliku z danymi: "yyy"
Oznacza on, że plik z danymi do posortowania nie istnieje, bądź istnieje lecz nie ma go w bieżącym katalogu.

Zapis do pliku "yyy" nie powiódł się!
Oznacza on, że nie można było utworzyć pliku z posortowanymi wyrazami. Przyczyna może tkwić w braku miejsca na bieżącym dysku, bądź w braku uprawnień użytkownika do zapisu na bieżącym dysku.

3.4. Format danych wyjściowych

Dane wyjściowe zostają zapisane w pliku tekstowym w formacie ASCII. Posortowane wyrazy zostają umieszczone w pliku tak, aby każdy znajdował się w oddzielnej linii, np.:

babcia
dzadek
mama
tata

początek

4. Przykład działania

(W tej części należy umieścić opis działania programu dla przykładowych danych wejściowych. Należy przedstawić sposób uruchomienia programu i przedstawic dane wejściowe. Następnie należy przedstawić przebieg pracy programu opisując interakcje użytkownika oraz komunikaty programu. Na końcu należy przedstawić efekt działania programu. W rozdziale tym można umieścić np. zawartość konsoli, zrzut ekranu lub wydruk zawartości pliku wynikowego.

Sortuj.exe dane.txt

gdzie dane.txt oznacza plik tekstowy znajdujący się w bieżącym katalogu o zawartości:

mama
tata
dziadzio
babcia
ciocia
wujek

Po uruchomieniu programu otrzymano na ekranie proste menu i możliwość wyboru metody sortowania. wybrano metodę "leksykograficzną malejąco" naciskając klawisz '2' i potwierdzając "enterem".
Na ekranie pojawił się komunikat:

Posortowane wyrazy zapisano w pliku "wynik.txt"

W biezącym katalogu został utworzony plik o nazwie "wynik.txt" o zawartości:

wujek
tata
mama
dziadzio
ciocia
babcia

początek

5. Specyfikacja wewnętrzna

(Specyfikacja wewnętrzna jest dokumentacją techniczną biblioteki użytkowej. Jej zasadnicza część omówienie klas wraz atrybutami i metodami,omówienie funkcji oraz zmiennych globalnych powinna być wzorowana na jakiejś istniejącej już dokumentacji. Rozdział ten przeznaczony jest dla programisty, który zna język, a jego ewentualnym zadaniem byłoby zmodyfikować nasz program lub użyć części funkcji we własnym programie, więc opisujemy tu precyzyjnie językiem technicznym własne zmienne i funkcje. Nie opisujemy konstrukcji samego języka programowania ani użytych bibliotek standardowych (czyli nie przepisujemy dostępnego Helpa).
Specyfikację wewnętrzną należy wykonać dla wszystkich plików z tekstem źródłowym tak, aby uwzględnione zostały wszystkie zmienne globalne, zmienne lokalne funkcji main() oraz wszystkie zdefiniowane przez autora funkcje.
Specyfikacja wewnętrzna może zostać wygenerowana automatycznie za pomocą jednego z istniejących generatorów dokumentacji).

Struktury, stałe i zmienne zdefiniowane globalnie

W programie zdefiniowano strukturę opisującą element listy jednokierunkowej:

struct wyraz
{
  char *slowo;           /* wskaźnik na początek łańcucha znakowego        */
  struct wyraz *nast;    /* wskaźnik na kolejny element listy              */
}
 

Zdefiniowano też stałą wartość N określająca maksymalną długość wyrazu w pliku na 100.
 

Funkcje

int dodaj( struct wyraz **_pocz, char *_slowo )
void usun( struct wyraz *_pom )
int czytaj( struct wyraz **_pocz, char *_nazwaPliku )
int zapisz( struct wyraz *_pocz, char *_nazwaPliku )
int dlugoscListy( struct wyraz *_pocz )
void sortuj( struct wyraz *_pocz, int _method )
int main(int ilePar, char *tabPar[])

int dodaj( struct wyraz **_pocz, char *_slowo )

Funkcja dodająca na początek listy jednokierunkowej nowy element i umieszczająca w nim określony wyraz  Parametry: _pocz - wskaźnik na wskaźnik na pierwszy element listy _slowo - wskaźnik na łańcuch znakowy zawierajacy wyraz z pliku Zwracane wartości: 1 - gdy rezerwacja pamięci dla nowego elementu zakończyła sie powodzeniem  0 - gdy system nie przydzielił pamięci operacyjnej na kolejny element listy

void usun( struct wyraz *_pom )

Rekurencyjna funkcja usuwająca z pamięci operacyjnej strukturę listową Parametry: _pom - wskaźnik na element do usunięcia Zwracane wartości: brak

int czytaj( struct wyraz **_pocz, char *_nazwaPliku )

Funkcja odczytująca z pliku tekstowego łańcuchy znakowe i umieszczająca je na liście jednokierunkowej Parametry: _pocz - wskaźnik na wskaźnik na pierwszy element listy _nazwaPliku - wskaźnik na łańcuch znakowy zawierający nazwę pliku Zwracane wartości: Ilość odczytanych słów z pliku

int zapisz( struct wyraz *_pocz, char *_nazwaPliku )

Parametry: _pocz - wskaźnik na pierwszy element listy; _nazwaPliku - wskaźnik na łańcuch znakowy zawierający nazwę pliku Zwracane wartości: 1 - gdy plik został zapisany na dysku; 0 - gdy nie udało się utworzyć pliku.

int dlugoscListy( struct wyraz *_pocz )

Funkcja obliczająca ilość elementów na liscie jednokierunkowej Parametry: _pocz - wskaźnik na pierwszy element listy Zwracane wartości: Funkcja zwraca ilość elementów listy

void sortuj( struct wyraz *_pocz, int _method )

Funkcja sortująca wyrazy zgodnie z wybraną metodą  Parametry: _pocz - wskaźnik na pierwszy element listy; _method - numer metody sortowania: 1 - leksykalnie narastająco, 2 - leksykalnie malejąco, 3 - wg długosci rosnaco, 4 - wg długości malejąco. Zwracane wartości: brak

int menu(void)

Funkcja odczytująca z pliku tekstowego łańcuchy znakowe i umieszczająca je na liście jednokierunkowej Parametry: brak Zwracane wartości: Funkcja zwraca ilość odczytanych słów z pliku

int main(int ilePar, char *tabPar[])

Główna funkcja programu. Parametry: ilePar - ilość łańcuchów znakowych w linii poleceń tabPar - tablica wskaźników na łańcuchy znakowe z linii wywołania Zwracane wartości: 0 - gdy program zakończył się prawidłowo, 1 - gdy podano niewłaściwą liczbę parametrów wywołania programu, 2 - gdy nie znaleziono pliku z danymi wejściowymi, 3 - gdy nie można było zapisać na dysku pliku wynikowego.

początek

6. Treść źródłowa programu

(Gotowy program oddany do oceny lub eksploatacji powinien przede wszystkim być poprawny i przetestowany, jednak jego forma tekstowa, styl zapisu i postać wydruku również powinna spełniać pewne wymagania. Dokładniej takimi wymaganiami zajmuje się inżynieria programowania – tu tylko przypomnimy i zasygnalizujemy pewne sprawy.
- wcięcia:
powinny podnosić czytelność wydruku i podkreślać strukturę składniową programu; powinny być wzorowane na przykładach zaczerpniętych z powszechnie szanowanej literatury, np. B.W. Kernighan, D.M. Ritchie: "Język ANSI C".
- komentarze:
powinny znajdować się przy deklaracji każdej zmiennej nad deklaracją każdej funkcji (podobna treść powinna się znaleźć w specyfikacji wewnętrznej); przy ważniejszych pętlach, skomplikowanych miejscach w algorytmach i we wszystkich innych fragmentach, które prawdopodobnie wymagałyby wyjaśnienia w czasie analizy tekstu programu.
Komentarze powinny być wyróżnione innym kolorem. Ewentualnie innym kolorem można również wyróżnić: instrukcje języka C, stałe liczbowe, znakowe i napisowe)

początek

7. Uwagi i wnioski z testowania i uruchamiania

(Rozdział ten może być sprawozdaniem z procesu systematycznego testowania programu. Powinien zawierać omówienie odpowiednio przygotowanych danych testowych wraz z formalnym uzasadnieniem ich doboru i ilości.
W niniejszym rozdziale można umieścić komentarze na temat pracy nad programem i inne spostrzeżenia. Można tu ustosunkować się do założeń umieszczonych w analizie zadania i stwierdzić, czy oczekiwania były trafne (np. że przewidywany algorytm okazał się odpowiedni do takiego charakteru/ takiej ilości danych lub że przyjęte rozwiązanie zbyt ograniczyło możliwości programu i że poszczególne moduły należałoby rozwijać. Powinno się również określić na jakiej platformie sprzętowo-systemowej uruchamiano i testowano program. )

1. Przetestowano program pod kątem ilości parametrów umieszczanych w linii wywołania programów.
2. Program sprawdza, czy plik z danymi wejściowymi o nazwie podanej w linii poleceń istnieje, jednakże nie sprawdza poprawności jego formatu.
3. Nie przewidziano reakcji na sytuację gdy stworzenie i zapisanie pliku wynikowego będzie niemożliwe n.p. ze względu na brak praw dostępu do zapisu w danym katalogu.
4. W programie nie kontroluje się wartości zwracanej przez funkcję malloc(), a więc zakłada się, że tworzona w czasie pracy programu struktura dynamiczna nie przekroczy rozmiaru dostępnej pamięci operacyjnej.