Wstęp do programowania / Ćwiczenia 8

To są zadania na wskaźniki.

Oglądaj wskazówki i rozwiązania __SHOWALL__
Ukryj wskazówki i rozwiązania __HIDEALL__

Zadanie 1 (Tablica wskaźników do tablic)

Zaimplementuj strukturę danych reprezentującą ciąg liczb z operacjami:

1. wstaw liczbę na koniec ciągu,
2. pobierz (usuwając) pierwszą liczbę ciągu.

Użyj w tym celu tablicy wskaźników do tablic, gdzie tablice składowe są przydzielane i zwalniane w miarę potrzeby (zaletą tej implementacji jest to, że dość elastycznie dostosowuje się do aktualnego rozmiaru ciągu, nie wymagając tylu wskaźników co zwykła lista).

Wskazówka 1

{{{3}}}

Rozwiązanie 1

{{{3}}}

Zadanie 2 (Haszowanie)

Zaimplementuj strukturę danych z operacjami:

1. Wstaw(klucz: integer; var d: Dane); (var zwiększa efektywność)
2. Daj(var klucz: integer; var d: Dane);

Wstaw wstawia do struktury danych parę (klucz, napis) lub (klucz, liczba), gdzie napis jest typu string, zaś liczba typu integer. Podaj stosowną deklarację dla typu Dane. Do przechowywania informacji użyj tablicy [0..N] elementów odpowiedniego typu. Wstawianie ma polegać na obliczeniu klucz mod (N+1); jeśli pod tym indeksem jest wolne miejsce (-1), to wstawiamy, w przeciwnym przypadku szukamy liniowo (cyklicznie) pierwszego wolnego miejsca. Wyszukiwanie analogicznie. Zakładamy, że nigdy nie będzie wkładane więcej niż N elementów (to m.in. upraszcza wyszukiwanie indeksu dla danego klucza, zawsze jest co najmniej jedno wolne miejsce).

Wskazówka 1

{{{3}}}

Rozwiązanie 1

{{{3}}}

Zadanie 3 (New i dispose dla typu T)

Zaimplementuj własne operacje new i delete dla elementów typu T. Użyj w tym celu tablicy [1..N] zawierającej rekordy z dwoma wariantami:

1. pole typu T
2. pole(-a) z pewnymi dodatkowymi informacjami (jakimi?)

Wskazówka 1

{{{3}}}

Rozwiązanie 1

{{{3}}}

Zadanie 4 (Sortowanie tablicy wskaźników do napisów)

Dana jest tablica A typu array[1..N] of ^string. Posortuj tę tablicę, używając porządku leksykograficznego (słownikowego) na słowach. Załóż, że dana jest funkcja compare(s,t:string):boolean, która ma wartość true wtedy i tylko wtedy, gdy słowo s jest leksykograficznie mniejsze od słowa t.

Wskazówka 1

{{{3}}}

Rozwiązanie 1

{{{3}}}