Tydzień 11: kolekcje

Ćwiczenia

1. Dany jest graf. Podzielić jego wierzchołki na możliwie najwięcej niepustych zbiorów, tak by podział miał tę własność, że każda para wierzchołków należących do różnych zbiorów jest połączona krawędzią. Dane:
   
   • pierwszy wiersz: liczba wierzchołków, liczba krawędzi
   • kolejne: opisy poszczególnych krawędzi (jako dwie liczby, nr pierwszego i nr drugiego wierzchołka).
   Np.:
        3 3
        1 2
        2 3
        3 1
     (graf trójkąt)
   
   Wynik: Posortowane niemalejąco liczby elementów poszczególnych zbiorów wierzchołków.
   
   W zadaniu należy zaprojektować struktury danych przechowujące graf (chcemy korzystać z kolekcji w Javie) oraz zaimplementować odpowiedni algorytm.
2. (Merge uporządkowanych iteratorów) Dane są dwa iteratory na liczbach całkowitych, o których wiemy, że zwracają liczby w porządku rosnącym. Utworzyć uporządkowaną rosnąco listę zawierającą te same elementy, co w danych iteratorach.
   

Laboratorium

1. Anagramy to słowa, które składają się z tych samych liter, ale w różnej kolejności. Napisz program, który dla danej listy słów wypisze wszystkie grupy anagramów pojawiające się na tej liście.
2. Napisz własną implementację listy wraz z iteratorem. Twoja lista powinna mieć nastepujące operacje:
   
   • dodawanie nowego elementu,
   • rozmiar,
   • test niepustości,
   • iterowanie przy pomocy pętli foreach.
   Wskazówki:
   • Pętlą foreach można iterować po obiektach implementujących interfejs Iterable.
   • Do implementacji iteratora trzeba użyć klas wewnętrznych (ang. inner classes). Klasa wewnętrzna ma dostęp do prywatnych składowych otaczającego obiektu.
   • Warto przeczytać rozdział o klasach wewnętrznych z tutorialu na stronie Oracle.
   • Ściągawkę, jak napisać własny iterator można znaleźć w klasie java.util.AbstractList. W Eclipse trzeba mieć podpięte źródła Javy.