W5,6

Spis treści:

 - pojęcie typu tablicowego,
 - definicja składni deklaracji typu tablicowego,
 - przykłady deklarowania i używania zmiennych tablicowych,
 - dalsze uwagi,
 - uwagi o zagrożeniach zwiazanych z używaniem tablic,
 - dalsze przykłady,
 - kompletny przykład programu używającego tablic.

-----------------------------------------------------------------------

Notatki

Ad pojęcie typu tablicowego:
  - t.t. jest typem strukturalnym,
  - wszystkie elementy tablicy są tego samego typu,
  - wszystkie elementy są równie łatwo i szybko dostępne (struktura o dostępie
    swobodnym),
  - rozmiar tablicy jest określany statycznei (tj podczas kompilacji),
  - do elementów tablicy dostajemy się za pomocą indeksów,
  - indeksy są wyliczane dynamicznie (tj podczas działania programu),
  - tablice pozwalają nam operować na wielkich ilościach danych,

  Ad definicja składni typu tablicowego
  - array [ <typ porządkowy> ] of <typ>
  - omówienie czemu tylko typ porządkowy może być indeksem, 
  - podanie przykładów zastosowań tablic z indeksami z poszczególnych typów
     porządkowych:
       boolean - gra z tablicą opisującą kolejno się poruszających graczy i zmienna logiczna CzyPierwszyGracz,
       char - program szyfrujący plik tekstowy z tablicą zawierającą kodowanie,
       wyliczeniowy - program grający w karty i pamiętający w tablciy indeksowanej kolorami kart jakie
              karty danego koloru wskazany gracz ma na ręku,
       okrojony - praktycznei wszystkie przykłady będą właśnie z typem okrojonym,
       integer - składniowo poprawny, w praktyce raczej nie występuje zwn wielkość (dla 16-bitowych
            liczb całowitych tablica musiałaby mieć 65 536 (64K) elementów, dla 32-bitowych zaś 
	    4 294 967 296 (4G) elementów,

 - przykłady deklarowania i używania zmiennych tablicowych,
    - różne deklaracje
      - A_zle: array[1..10] of integer;
      - zakładam deklarację:
          const 
	     N =   ;  {Na wykładzie  nigdy nie będziemy pisać wartości stałych}
      - A: array[1..N] of integer;
      - B: array[-5..5] of real; {tablica 11-tu liczb rzeczywistych},
      - C: array['a'..'z'] of integer;
      - D_zle: array[(czerwony, niebieski, bialy)] of integer; 
               Deklaracja poprawna składniowo, ale nie da się teraz zadeklarować zmiennej
	       do indeksowania tej tablicy!
      - type 
             TKolory = (piki, kiery, kara, trefle);
         var
	     D: array[ TKolory ] of integer;

    - proste przykłady użycia:
      - zakładam deklarację 
         var
	   i: integer;   
      - A[3] := 1;
      - A[i] := 13;
      - A[k*j+7*i-2] := 0;
      - A[i] := A[i] + 1;
      - readln(A[i]);
      - write(B[4]);

 - Ad. dalsze uwagi:
      - nie można wczytywać/zapisywać operacjami read(ln)/write(ln) całych tablic, 
      - zmienne tablicowe (tak jak wszystkie w Pascalu) nie są inicjalizowane,

 - Ad. dalsze przykłady:

    - przykłady implementacji pewnych operacji na całych tablicach:
       - zakładam deklaracje:
          const
	    N =  ;
          var
	    i: integer;
	    tab: array[1..N] of integer;

       - wypełnienie elementów wartościami indeksów:
             for i := 1 to N do
	       tab[i] := i;

       - wczytanie od użytkownika:
             for i := 1 to N do
                begin
		   write('Podaj element nr ', i, '/', N, ' : ');
		   readln(tab[i]);
                end;

       - wypisanie tablicy:
              for i:=1 to N do
	        writeln('tab[', i, ']=', tab[i]);

       - znalezienie elementu maksymalnego
             max := tab[1];
	     for i:=2 to N do
	        if tab[i] > max
		then
		   max := tab[i];
          

 - uwagi o zagrożeniach zwiazanych z używaniem tablic,
      - każde silne narzędzie niesie z sobą zagrożenia,
      - w przypadku tablic największym problemem jest odwoływanie się poza tablice,
      - konsekwencje pisania poza tablicą są dowolnie poważne, szczególnie jeśli w systemie
         operacyjnym (np. DOS) nie ma ochrony pamięci. Czytanie spoza tablicy _też_
	 jest poważnym błędem (np. może spowodować przerwanei wykonywania programu),
      - [FreePascal, TP/BP, Delphi: częściowe zabezpieczenie {$R+}]
      - uwaga na wyrażenia logiczne, w których sensowność jednego członu zależy od 
        prawdziwości innego - są _niepoprawne_ w Pascalu. Rozważmy jako przykład
	fragmnet programu pomijający początkowe zera w tablicy (zakładamy deklarację
	i oraz tab taką jak wcześniej):

	i:=1;
	while (i<=N) and (tab[i]=0) do
          i := i + 1;

       Powyższy program jest niepoprawny w Pascalu (zwn przypadek, gdy cała tablica
       jest wypełniona zerami).

       Zawsze można zupełnie mechanicznie poprawić taki program, by był poprawny 
       przepychając liczenie powodującego kłopoty wyrazenia do środka pętli (zakładam
       następującą dekarację dodatkowej zmiennej var SameZera: boolean):

       SameZera := true;
       i :=1;
       while (i<=N) and SameZera do
         if tab[i] = 0
	 then
	   i := i + 1
        else
	   SameZera := false;

      [FreePascal, TP/BP, Delphi: tu można opcją {$B-} wymusić krótkie wyliczanie wyrazeń logicznych.]

 - kompletny przykład programu używającego tablic.

program SortowaniePrzezSelekcje;

const
  N = ;   {Tu trzeba uzupełnic wartość stałej}

var
  a : array [1..N] of integer;
  i, i_max, max, j : integer;
begin
  { Wczytanie danych. }

  writeln('Podaj ', N, ' liczb calkowitych.');
  for i := 1 to  N do
   begin
     write('Podaj element nr ', i);
     readln(a[i]);   {Pomija liczby (poza pierwszą) zapisane w jednym wierszu}
   end;

  writeln('Ciag do posortowania:');
  for i := 1 to N do
     write(a[i],', ');  {Wypisuje zbędny przecinek po ostatniej liczbie}
  writeln;

  { Wlasciwe sortowanie. }
  for  j := N downto 2 do
   begin
  { Nzm.: a[1],...,a[j]<=a[j+1]<=...<=a[N] }
    max := a[1];
    i_max := 1;
    for i := 2 to j do
    { Nzm.: a[i_max]=max=MAX(a[1],...,a[i]) }
      if a[i] > max then
      begin
        max := a[i];
        i_max := i
      end
    a[i_max] := a[j];
    a[j] := max;
  end;

  { Wypisanie wyników. }
  writeln('Ciąg posortowany:');
  for i := 1 to N do
    write(a[i],' , ');
  writeln
end.