Wstęp do programowania / Ćwiczenia 8: Różnice pomiędzy wersjami

Z Studia Informatyczne
Przejdź do nawigacjiPrzejdź do wyszukiwania
m
Linia 1: Linia 1:
 
 
To są zadania na wskaźniki.
 
To są zadania na wskaźniki.
  
Linia 13: Linia 12:
 
# pobierz (usuwając) pierwszą liczbę ciągu.
 
# pobierz (usuwając) pierwszą liczbę ciągu.
 
Użyj w tym celu tablicy wskaźników do tablic, gdzie tablice składowe
 
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).
+
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).
  
 
{{wskazowka| 1||<div class="mw-collapsible mw-made=collapsible mw-collapsed"><div class="mw-collapsible-content" style="display:none">
 
{{wskazowka| 1||<div class="mw-collapsible mw-made=collapsible mw-collapsed"><div class="mw-collapsible-content" style="display:none">
Ze względu na cykliczne przesuwanie się ciągu w obrębie tablic wygodnie je wszystkie indeksować od zera.
+
Ze względu na cykliczne przesuwanie się ciągu w obrębie tablic, wygodnie jest je wszystkie indeksować od zera.
 
</div>
 
</div>
 
</div>}}
 
</div>}}
Linia 32: Linia 31:
 
  //wstawiamy liczbę do struktury S (S.T[S.poczD]^[S.poczM] to pierwsza liczba w ciągu,  
 
  //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
 
  //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  
+
  //Wstaw staje się false wtedy i tylko wtedy, gdy struktura S jest pełna  
 
  '''begin'''
 
  '''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'''
 
   '''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'''
Linia 50: Linia 49:
 
  //pobieramy liczbę ze struktury S (S.T[S.poczD]^[S.poczM] to pierwsza liczba w ciągu,  
 
  //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
 
  //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  
+
  //Pobierz staje się false wtedy i tylko wtedy, gdy struktura S jest pusta  
 
  '''begin'''
 
  '''begin'''
 
   '''if''' (S.konD=S.poczD '''and''' S.konM=S.poczM) '''then'''
 
   '''if''' (S.konD=S.poczD '''and''' S.konM=S.poczM) '''then'''
Linia 77: Linia 76:
 
liczba), gdzie napis jest typu string, zaś liczba typu integer.
 
liczba), gdzie napis jest typu string, zaś liczba typu integer.
 
Podaj stosowną deklarację dla typu Dane. Do przechowywania informacji
 
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).
+
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).
  
 
{{wskazowka| 1||<div class="mw-collapsible mw-made=collapsible mw-collapsed"><div class="mw-collapsible-content" style="display:none">
 
{{wskazowka| 1||<div class="mw-collapsible mw-made=collapsible mw-collapsed"><div class="mw-collapsible-content" style="display:none">
Linia 167: Linia 166:
 
Inicjalizacja T, funkcja NewT i procedura DisposeT:
 
Inicjalizacja T, funkcja NewT i procedura DisposeT:
 
  '''procedure''' InitT(var S:Str);
 
  '''procedure''' InitT(var S:Str);
  //wszystkie pola ustawiamy na puste, nast wskazują na następne pole lub zero; pierwszy staje sie równy 1
+
  //wszystkie pola ustawiamy na puste, nast wskazują na następne pole lub zero; pierwszy staje się równy 1
 
  '''var''' i:integer;
 
  '''var''' i:integer;
 
  '''begin'''
 
  '''begin'''
Linia 177: Linia 176:
 
''Koszt pamięciowy'': stały
 
''Koszt pamięciowy'': stały
 
  '''function''' NewT(var S:Str; var nowy:integer):boolean;
 
  '''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
+
  //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'''
 
  '''begin'''
 
   '''if''' S.pierwszy = 0 '''then'''  
 
   '''if''' S.pierwszy = 0 '''then'''  

Wersja z 08:36, 16 lis 2006

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}}}