Ćwiczenia 20: wskaźniki

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

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

wstaw liczbę na koniec ciągu,
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 jest 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 
       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:

Wstaw(klucz: integer; var d: Dane); (var zwiększa efektywność)
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

Typ Dane to rekord z wariantami string i integer. Dane nie nadają się na typ elementów tablicy; tam lepiej użyć 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

const N = 100;
type rodzaj = (napis, liczba)
     Dane = record 
       case co:rodzaj of
         napis: (s:string)
         liczba: (l:liczba)
       end;
     Eltab = record
       klucz:integer; 
       case co:rodzaj of
         napis: (wsk:^string)
         liczba: (l:liczba)
       end;
var T: array[0..N] of Eltab

Teraz dwie procedury:Napisz funkcję znajdującą w zadanej tablicy A typu array[1..N] of integer, N > 0, maksymalną sumę segmentu (spójnego fragmentu tablicy). Przyjmujemy, że segment pusty ma sumę 0.

procedure Wstaw(klucz: integer; var d: Dane); 
//wstawiamy dane z d do tablicy T na pierwsze wolne miejsce, zaczynając od indeksu klucz mod (N+1)
//zakładamy, że są wolne miejsca w tablicy T 
var k:integer;
begin
  k:=klucz mod (N+1);
  while T[k].klucz <> -1 do k:=(k+1) mod (N+1);
  T[k].klucz:=klucz;
  T[k].co:=d.co;
  case d.co of
    napis: New(T[k].wsk); T[k].wsk^:=d.s;
    liczba: T[k].l:=d.l
  end; 
end;

Koszt czasowy: liniowy względem N
Koszt pamięciowy: stały

function Daj(klucz: integer; var d: Dane):boolean;
//pobieramy liczbę lub napis z tablicy T skojarzonych z kluczem klucz
//zakładamy, że są wolne miejsca w tablicy T 
var i:integer;
begin
  k:=klucz mod (N+1); 
  while T[k].klucz <> klucz and T[k].klucz <> -1 do k:=(k+1) mod (N+1);
  if T[k].klucz = -1 then
    Daj:=false
  else begin
    Daj:=true;
    d.co:=T[k].co;
    case d.co of
      napis: d.s:=T[k].wsk^;
      liczba: d.l:=T[k].l;
    end;
  end; 
end;

Koszt czasowy: liniowy względem N
Koszt pamięciowy: stały

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:

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

Wskazówka 1

W elementach tablicy albo trzymamy dane, albo indeks następnego wolnego elementu tablicy (trzeba jeszcze gdzieś pamiętać indeks pierwszego wolnego elementu).

Rozwiązanie 1

const N = 100;
type rodzaj = (pełny, pusty); 
     Eltab = record 
       case rodzaj of
         pełny: (d:T)
         pusty: (nast:integer)
       end;
     Str = record 
       T:array[1..N] of Eltab;
       pierwszy:integer;
     end;

Inicjalizacja T, funkcja NewT i procedura DisposeT:

procedure InitT(var S:Str);
//wszystkie pola ustawiamy na puste, nast wskazują na następne pole lub zero; pierwszy staje się równy 1
var i:integer;
begin
  for i:=1 to N do S.T[i].nast:=(i+1) mod (N+1);
  S.pierwszy:=1;
end;

Koszt czasowy: liniowy względem N
Koszt pamięciowy: stały

function NewT(var S:Str; var nowy:integer):boolean;
//nowy to indeks któregoś z dotychczas pustych pól w S.T; jeśli takich nie ma, to New będzie miało wartość false
begin
  if S.pierwszy = 0 then 
    New:=false
  else begin
    New:=true;
    nowy:=S.pierwszy;
    S.pierwszy:=S.T[S.pierwszy].nast;
  end;
end;

Koszt czasowy: stały
Koszt pamięciowy: stały

procedure DisposeT(var S:Str; d:integer);
//zwalniamy indeks d w tablicy S.T
begin
  S.T[d].nast:=S.pierwszy;
  S.pierwszy:=d;
end;

Koszt czasowy: stały
Koszt pamięciowy: stały

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

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

Napisz funkcję znajdującą w zadanej tablicy A typu array[1..N] of integer, N > 0, maksymalną sumę segmentu (spójnego fragmentu tablicy). Przyjmujemy, że segment pusty ma sumę 0.