Programowanie funkcyjne/Programowanie imperatywne/Ćwiczenia: Różnice pomiędzy wersjami
| Linia 1: | Linia 1: | ||
== Praca domowa == | == Praca domowa == | ||
{{cwiczenie|[BST]|| | |||
Zastosuj metodę spaceru do sprawdzenia, czy drzewo jest drzewem BST. | |||
}} | |||
{{cwiczenie|[<tt>Append</tt>]|| | |||
Zaimplementuj modyfikowalne listy i procedurę <tt>append</tt>, | |||
która modyfikuje daną listę przez dołączenie na jej końcu innej listy. | |||
Dołączana lista jest przy tym niszczona. | |||
Procedura <tt>append</tt> powinna działać w stałym czasie. | |||
(Lista powinna zawierać referencje do obu jej końców). | |||
}} | |||
{{cwiczenie|[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 == | == Ćwiczenia == | ||
Wersja z 18:22, 17 gru 2006
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.
