Programowanie funkcyjne/Programowanie imperatywne/Ćwiczenia
Praca domowa
Ćwiczenie [BST]
Zastosuj metodę spaceru do sprawdzenia, czy drzewo jest drzewem BST.
Ćwiczenie [Append]
Zaimplementuj modyfikowalne listy i procedurę append, która modyfikuje daną listę przez dołączenie na jej końcu innej listy. Dołączana lista jest przy tym niszczona. Procedura append powinna działać w stałym czasie. (Lista powinna zawierać referencje do obu jej końców).
Ćwiczenie [Odwracanie listy]
Napisz procedurę, która odwraca zadaną listę modyfikowalną. Dwukrotne odwrócenie powinno dawać listę tożsamą z początkową. Należy to zrobić w stałej pamięci dodatkowej i liniowym czasie.
Ćwiczenia
Ćwiczenie [Listy cykliczne]
Zaimplementuj cykliczne listy modyfikowalne.
Ćwiczenie [Wykrywanie cykli]
Napisz procedurę sprawdzającą, czy dana lista zawiera cykl. Można to zrobić w stałej pamięci i liniowym czasie (i to na kilka sposobów!).
Laboratorium
Ćwiczenie [FIFO]
Zaimplementuj imperatywną kolejkę FIFO.
Ćwiczenie [Kolejki dwustronne]
Zaimplementuj imperatywne kolejki dwustronne z dodatkowymi operacjami odwracania i sklejania kolejek. Wszystkie operacje powinny działać w czasie stałym.
Ćwiczenie [Find-union]
Zaimplementuj drzewa find-union.
Rozwiązanie