Wstęp do programowania / Ćwiczenia 8

<<< Powrót do głównej strony wykładu

<<< Powrót do modułu 8

To są zadania na wskaźniki

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ę tablice 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

Użyj dowolnego algorytmu sortowania. Zamiast przesuwać obiekty przesuwaj wskaźniki.

Rozwiązanie 1

procedure Sort(var A:array[1..N] of ^string);
//sortujemy leksykograficznie tablicę wskażników do słów
var i,j,min: integer;
    pom: ^string;
begin
  for i:=1 to N do begin
    min:=i;
    for j:=i+1 to N do 
      if compare(A[j]^,A[i]^) then min:=j;
    pom:=A[i];
    A[i]:=A[min];
    A[min]:=pom;
  end;
end;

Koszt czasowy: kwadratowy względem N

Koszt pamięciowy: stały