Lista 9 (20 grudnia 2005): 15 punktów.

Przeczytaj z książki B.W.Kernighana i D.M.Ritchiego Język ANSI C rozdział 6: Struktury. Zapoznaj się z funkcjami przydzielającymi pamięć na stercie (malloc() i calloc()) i funkcją zwalniającą wcześniej przydzieloną pamięć (free()). Potem przeczytaj jeszcze raz podrozdział poświęcony strukturom dynamicznym i zastanów się nad tworzeniem takich struktur właśnie na stercie.

1. (7 punktów) W pliku nagłówkowym zdefiniuj strukturę reprezentującą element listy jednokierunkowej struct ElementLiczbowy , w której będą pola nast wskazujące na element tego samego typu oraz wartosc przechowujące liczbę rzeczywistą:
   struct ElementLiczbowy
   {
       ElementLiczbowy *nast;
       double wartosc;
   };
   Oprócz struktury zadeklaruj również funkcje wstawNaPocz() (wstawienie nowego elementu na początek listy), wstawNaKon() (wstawienie nowego elementu na koniec listy), policz() (policzenie ile jest elementów na liście) oraz wypisz() (wypisanie kolejno wszystkich wartości zapamiętanych w liście). Jednym z parametrów tych funkcji powinien być wskaźnik na pierwszy element listy. Dalej, w oddzielnym pliku źródłowym zdefiniuj wymienione funkcje (zaimplementuj je iteracyjnie). W oddzielnym pliku źródłowym napisz program testujący działanie zdefiniowanej przez Ciebie struktury danych. Testowanie ma się odbywać w sposób interakcyjny, a więc program ma realizować wydawane na konsoli polecenia. Powinniśmy mieć możliwość wydawania następujących rozkazów:
   • sprawdzenie liczby elementów na liście:
     > rozmiar
     2
     >
     
   • dopisanie elementu na początku listy:
     > poczatek 17
     >
     
   • dopisanie elementu na końcu listy:
     > koniec 43
     >
     
   • wypisanie wszystkich elementów listy:
     > wypisz
     17, 23, 37, 43
     >
     
   • wyjście z programu:
     > stop
     
   Uwaga: Program ma być odporny na błędy użytkownika.
2. (5 punktów, kontynuacja poprzedniego zadania) Do poprzedniego zadania dopisz funkcje wstaw() (wstawienie nowego elementu na i-tą pozycję w liście: i-ta pozycja oznacza, że i elementów poprzedza dany element) i usun() (usunięcie elementu z i-tej pozycjji w liście). Tak jak poprzednio, delaracje obu funkcji mają być umieszczone w pliku nagłówkowym, a definicje w pliku źródłowym (zaimplementuj je iteracyjnie). W programie testującym dopisz dwa rozkazy: wstaw i usun.
3. (3 punkty, kontynuacja poprzedniego zadania) Do poprzedniego zadania dopisz funkcję odwroc() (odwrócenie kolejności elementów na liście). Tak jak poprzednio, delaracja funkcji ma być umieszczona w pliku nagłówkowym, a definicja w pliku źródłowym (zaimplementuj ją iteracyjnie). W programie testującym dopisz rozkaz: odwroc.


4. (5 punktów) W pliku nagłówkowym zdefiniuj strukturę reprezentującą element drzewa binarnych poszukiwań struct ElementBST , w której będą pola lewy wskazujące na lewego syna (element tego samego typu), prawy wskazujące na prawego syna (element tego samego typu) oraz wartosc przechowujące liczbę rzeczywistą:
   struct ElementBST
   {
       ElementBST *lewy, *prawy;
       double wartosc;
   };
   Oprócz struktury zadeklaruj również funkcje wstaw() (wstawienie nowego elementu do drzewa), policz() (policzenie ile jest elementów w drzewie) oraz wypisz() (wypisanie wszystkich wartości zapamiętanych w drzewie w sposób uporządkowany: metoda in-order). Jednym z parametrów tych funkcji powinien być wskaźnik na korzeń drzewa. Dalej, w oddzielnym pliku źródłowym zdefiniuj wymienione funkcje (zaimplementuj je rekurencyjnie). W oddzielnym pliku źródłowym napisz program testujący działanie zdefiniowanej przez Ciebie struktury danych. Testowanie ma się odbywać w sposób interakcyjny, a więc program ma realizować wydawane na konsoli polecenia. Powinniśmy mieć możliwość wydawania następujących rozkazów:
   • sprawdzenie liczby elementów w drzewie:
     > rozmiar
     8
     >
     
   • dopisanie elementu do drzewa:
     > wstaw 23
     >
     
   • wypisanie wszystkich elementów drzewa w sposób uporządkowany:
     > wypisz
     17, 23, 37, 43
     >
     
   • wyjście z programu:
     > stop
     
   Uwaga: Program ma być odporny na błędy użytkownika.
5. (5 punktów, kontynuacja poprzedniego zadania) Do poprzedniego zadania dopisz funkcje szukaj() (sprawdzenie czy element z podaną wartością jest w drzewie) i usun() (usunięcie elementu podaną wartością z drzewa). Tak jak poprzednio, delaracje obu funkcji mają być umieszczone w pliku nagłówkowym, a definicje w pliku źródłowym (zaimplementuj je rekurencyjnie). W programie testującym dopisz dwa rozkazy: szukaj i usun.
6. (5 punktów, kontynuacja poprzedniego zadania) Do poprzedniego zadania dopisz funkcję drukuj() (wyświetlenie struktury drzewa wraz z wartościami w węzłach). Przykładowe wywołanie tej funkcji w programie testującym może wygenerować następujący wynik:
   > drukuj
      +--*11
      |  +--*13
   +--*17
   |  +--*23
   *37
   +--*43
      |  +--*47
      +--*53
         +--*57
   >
   Tak jak poprzednio, delaracja funkcji ma być umieszczona w pliku nagłówkowym, a definicja w pliku źródłowym (zaimplementuj ją rekurencyjnie). W programie testującym dopisz rozkaz: drukuj.