Wstęp do programowania / Ćwiczenia 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

Ze względu na cykliczne przesuwanie się ciągu w obrębie tablic wygodnie je wszystkie indeksować od zera.

Rozwiązanie 1

const M = 100;
      D = 100;
type Tab = array[0..D-1] of ^array[0..M-1];
      Str = record of
        T:Tab;
        poczD,konD, poczM, konM:integer;
      end; 

Teraz dwie funkcje:

function Wstaw(var S:Str; liczba: integer):boolean;
//wstawiamy liczbę do struktury S (S.T[S.poczD]^[S.poczM] to pierwsza liczba w ciągu, 
//S.T[S.konD]^[S.konM] to pierwsze wolne miejsce w S
//Wstaw staje się false wtedy i tylko wtedy gdy struktura S jest pełna 
begin
if (S.konD=S.poczD and S.konM+1=S.poczM) or ((S.konD+1) mod D = S.poczD and S.konM=M-1 and S.poczM=0) then
  Wstaw:=false
else begin
  Wstaw:=true;
  if S.konM = 0 and S.poczD <>S.konD then New(S.T[S.konD]);
  S.T[S.konD]^[S.konM]:=liczba;
  S.komM:=(S.komM+1) mod M;
  if S.konM=0 then S.konD:=(S.konD+1) mod D;
end;
end;

Koszt czasowy: stały

Koszt pamięciowy: M

function Pobierz(var S:Str; var liczba: integer):boolean;
//pobieramy liczbę ze struktury S (S.T[S.poczD]^[S.poczM] to pierwsza liczba w ciągu, 
//S.T[S.konD]^[S.konM] to pierwsze wolne miejsce w S
//Pobierz staje się false wtedy i tylko wtedy gdy struktura S jest pusta 
begin
if (S.konD=S.poczD and S.konM=S.poczM) then
  Pobierz:=false
else begin
  Pobierz:=true;
  liczba:=S.T[S.poczD]^[S.poczM];  
  S.poczM:=(S.poczM+1) mod M;
  if S.poczM=0 then begin
    if S.konD <> S.pocz then Dispose(S.T[poczD]);
    S.poczD:=(S.poczD+1) mod D;
  end;
end;
end;

Koszt czasowy: stały

Koszt pamięciowy: stały

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 w tablicy 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, zawsze jest co najmniej jedno wolne miejsce).

Wskazówka 1

Typ Dane to rekord z wariantami (string i integer). Oczywiście Dane nie nadaje się na typ eltów tablicy, tam trzeba rekordu z wariantami (wskażnik do napisu i liczba). Można by tak zdefiniować też Dane, ale nie widać ku temu powodów.

Rozwiązanie 1