Programowanie funkcyjne/Programowanie imperatywne/Ćwiczenia

Praca domowa

• Zastosuj metodę spaceru do sprawdzenia, czy drzewo jest drzewem BST.
• 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).
• 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

• Zaimplementuj imperatywną kolejkę FIFO.
• Zaimplementuj imperatywne kolejki dwustronne z dodatkowymi operacjami odwracania i sklejania kolejek. Wszystkie operacje powinny działać w czasie stałym.
• Zaimplementuj drzewa find-union.