Laboratorium 7

Wskaźniki, rekurencja

Wskaźniki

Deklaracja wskaźnika, alokacja pamięci

Wskaźnik jest to adres pod którym przechowywana jest zmienna określonego typu. Deklaracja ma postać: 
  typ *nazwa;
np. int *wsk;. Aby można było z tym wskaźnikiem zrobić coś sensownego można przypisać mu adres istniejącej zmiennej. Wykorzystuje się do tego operator pobrania adresu &. Aby otrzymać lub zmienić wartość na którą wskazuje dany wskaźnik należy użyć operatora *. Przykładowo: 
  int z;
  int *wsk=&z;

  *wsk=1; // zmienna z będzie miała wartość 1

Jeśli wsk jest wskaźnikiem danego typu, to można na nim wykonywać operacje arytmetyczne. I tak wsk+1 będzie wskazywał na kolejną zmienną danego typu w pamięci itd.

W języku C++ jak i w C istnieje ścisła zależność pomiędzy tablicami a wskaźnikami. Można powiedzieć, że tablica jest wskaźnikiem stałym (nie prawidłowa jest na przykład instrukcja T++, gdzie T jest tablicą). Przykładowo: 

  int T[3]={1,2,3};
  int *wsk=T;
  *wsk=3;   // równoważnie T[0]=3
  wsk++;
  *wsk=2;   // T[1]=2
  wsk++;
  *wsk=1; // T[2]=1

Wskaźnikowi można także dynamicznie (tzn. w trakcie działania programu) przydzielić pamięć. Wykorzystujemy w tym celu operator new: 

  int *wsk=new int;  // alokacja nowej zmiennej typu int
  double *wd=new double[10];  // alokacja tablicy
Aby zwolnić wcześniej przydzieloną pamięć wykorzystujemy operator delete: 
  delete wsk;
  delete []wd;

Tablica wskaźników a wskaźnik na tablice

  int T1[10][10];
  int (*W1)[10];
  int **W2;
  int *T2[10];

Po takich deklaracjach T1 jest tablicą dwuwymiarową 10x10, W1 wskaźnikiem na tablicę 10-elementową, W2 wskaźnikiem na wskaźnik, zaś T2 tablicą 10 wskaźników. Możliwe są więc przypisania: 

  W2=T2;  // T2 jest tablicą wskaźników, a więc wskaźnikiem na wskaźnik
  W1=T1;  // T1 jest tablicą tablic, a więc wskaźnikiem na tablicę
Ale nie możliwe są przypisania W2=T1 lub W1=T2.

Porównaj dwa programy:

Rekurencja

Symbol Newtona

Newton2.

Zastanów się, który z programów (ten czy z trzeciego laboratorium) jest bardziej efektywny?

Generowanie permutacji

Permutacje

Sortowanie Merge Sort

Algorytm sortowania MergeSort zadanego wektora n-elementowego:
  1. Jeśli n=1, to wektor jest posortowany, koniec;
  2. Dla n>1 podziel wektor na dwa "mniej więcej" równe wektory w1 i w2;
  3. Posortuj wektory w1 i w2 algorytmem MergeSort;
  4. Scal wektory w1 i w2 do wektora posortowanego, wykorzystując, że są one posortowane.

Program sortujący wektor liczb całkowitych: MergeSort.

Krzywa Kocha

Definiujemy rekurencyjnie następujący sposób ciąg krzywych K(k):

  1. Jeśli k=0, to K(0) jest odcinkiem;
  2. Dla k>0 K(k) powstaje przez odpowiednie połączenie czterech kopii krzywych K(k-1) (patrz ilustracja - poszczególne kopie krzywych stopnia o jeden mniejszego wyróżniono różnymi kolorami).

Krzywa Kocha

Program generujący rekurencyjnie krzywą Kocha zadanego stopnia: Koch.cpp Uruchom ten program rysując kolejno krzywe stopnia 0, 1, 2, itd.

Trójkąt Sierpińskiego

Definiujemy rekurencyjnie ciąg podzbiorów płaszczyzny TS(k):
  1. TS(0) to wypełniony trójkąt;
  2. Dla k>0 zbiór TS(k) powstaje poprzez sklejenie 3 mniejszych kopii TS(k-1) (patrz rysunek).

Krzywa Kocha

Program generujący trójkąt Sierpińskiego zadanego stopnia: sierp.cpp Uruchom ten program rysując kolejno trójkąt stopnia 0, 1, 2, itd.