Czym jest wskaźnik?
Każda zmienna w programie ma dwie rzeczy: wartość i adres w pamięci, pod którym ta wartość jest fizycznie zapisana. Wskaźnik to po prostu zmienna, której wartością jest właśnie taki adres — wskaźnik „wskazuje” na miejsce w pamięci, w którym leży inna zmienna.
Do pracy ze wskaźnikami potrzebujesz dwóch operatorów, które na pierwszy rzut oka wyglądają
tak samo (* i &), ale robią coś zupełnie innego w zależności od kontekstu:
- & (adres-of) — postawiony przed zmienną zwraca jej adres w pamięci, np.
&x. - * w deklaracji — mówi „ta zmienna jest wskaźnikiem”, np.
int* pdeklaruje wskaźnik na inta. - * w wyrażeniu (dereferencja) — wchodzi pod adres i daje dostęp do wartości tam zapisanej, np.
*p.
int x = 10; // zwykła zmienna typu int
int* p = &x; // p to wskaźnik na inta — przechowuje ADRES zmiennej x
cout << x; // 10 -> wartość x
cout << &x; // np. 0x61fe1c -> adres x w pamięci
cout << p; // np. 0x61fe1c -> to samo co &x, bo p PRZECHOWUJE ten adres
cout << *p; // 10 -> dereferencja: wartość pod adresem, na który wskazuje p
*p = 99; // zmieniamy wartość POD adresem, czyli zmieniamy x!
cout << x; // 99
| Zmienna | Typ | Przykładowy adres | Wartość |
|---|---|---|---|
x | int | 0x61fe1c | 10 → 99 |
p | int* | 0x61fe10 | 0x61fe1c (adres x) |
int* pCzytaj ją jako: „p jest wskaźnikiem, który wskazuje na int-a”.
Gwiazdka jest tu częścią typu zmiennej p (typ to int*), nie częścią jej nazwy.
nullptr — wskaźnik, który „donikąd” nie wskazuje
Niezainicjalizowany wskaźnik wskazuje na losowy, przypadkowy adres w pamięci — to bardzo
niebezpieczne. Dlatego wskaźnik, który chwilowo nie ma na co wskazywać, ustawiamy jawnie na
nullptr:
int* p = nullptr; // bezpieczny, "pusty" stan początkowy
if (p != nullptr) { // ZAWSZE sprawdzaj przed dereferencją
cout << *p;
}
Wskaźnik zawsze ma stały rozmiar — na typowym systemie 64-bitowym to 8 bajtów,
niezależnie od tego, czy wskazuje na int, double czy ogromny obiekt klasy.
Przechowuje przecież tylko adres, nigdy samą wartość.
Operacje na wskaźnikach
Przypisanie wskaźnika do wskaźnika kopiuje adres, a nie wartość, na którą ten adres wskazuje. Oba wskaźniki zaczynają wtedy wskazywać na to samo miejsce w pamięci:
int a = 5, b = 99;
int* p1 = &a;
int* p2 = p1; // p2 wskazuje na to samo co p1, czyli na "a"
*p2 = 50; // zmieniamy wartość POD adresem -> zmienia się "a"!
cout << a; // 50
p1 = &b; // teraz p1 wskazuje na "b" -> to NIE zmienia ani a, ani p2
cout << *p1; // 99
cout << *p2; // 50 (p2 wciąż wskazuje na "a")
Kluczowe rozróżnienie: *p = wartość zmienia to, na co wskaźnik wskazuje, natomiast
p = &cosInnego zmienia samego wskaźnika, żeby wskazywał gdzie indziej.
Wskaźniki i tablice
Nazwa tablicy w C++ w większości kontekstów „rozpada się” (ang. array decay) do
wskaźnika na jej pierwszy element. Dzięki temu arytmetyka wskaźników działa jak poruszanie się
po tablicy — przy czym p + 1 oznacza „następny element danego typu”, a nie
„następny bajt”:
int tab[5] = {10, 20, 30, 40, 50};
int* p = tab; // p wskazuje na tab[0]
cout << *p; // 10
cout << *(p + 1); // 20 -> p przesuwa się o sizeof(int), nie o 1 bajt
cout << p[2]; // 30 -> p[i] to dokładnie *(p + i)
p++; // teraz p wskazuje na tab[1]
cout << *p; // 20
int* p = tab;
Przekazywanie wskaźników do funkcji
To jest właściwy powód, dla którego wskaźniki są tak ważne. W C++ argumenty domyślnie przekazywane są przez wartość — funkcja dostaje kopię i jakiekolwiek zmiany wewnątrz niej nie wychodzą na zewnątrz:
void zmienPrzezWartosc(int x) {
x = 100; // zmienia tylko lokalną kopię
}
int a = 5;
zmienPrzezWartosc(a);
cout << a; // wciąż 5
Żeby funkcja mogła faktycznie zmienić zmienną z zewnątrz, trzeba dać jej adres tej zmiennej — wtedy funkcja, mając ten adres, może dereferencją dotrzeć do oryginału:
void zmienPrzezWskaznik(int* x) {
*x = 100; // dereferencja -> wchodzimy pod adres i zmieniamy oryginał
}
int a = 5;
zmienPrzezWskaznik(&a); // przekazujemy ADRES a, nie samo a
cout << a; // 100
C++ ma też referencje (int&) — to składniowo wygodniejszy
wariant tego samego mechanizmu: pod spodem nadal przekazywany jest adres, ale nie trzeba pisać
& przy wywołaniu ani * przy każdym użyciu wewnątrz funkcji:
void zmienPrzezReferencje(int& x) {
x = 100; // wygląda jak zwykłe przypisanie, ale modyfikuje oryginał
}
int a = 5;
zmienPrzezReferencje(a); // bez & przy wywołaniu!
cout << a; // 100
| Sposób | Co dostaje funkcja | Składnia wywołania | Może być „pusty”? |
|---|---|---|---|
| przez wartość | kopię danych | f(a) | nie dotyczy |
| przez wskaźnik | adres (kopię adresu) | f(&a) | tak, nullptr |
| przez referencję | alias do oryginału | f(a) | nie, zawsze coś wskazuje |
Tablice w funkcjach i niebezpieczeństwo zwracania wskaźnika
Tablica przekazana do funkcji zawsze „rozpada się” do wskaźnika na pierwszy element — dlatego
w środku funkcji modyfikujesz oryginalną tablicę, a nie jej kopię, mimo że nie widać tam jawnego
&:
void wyzeruj(int tab[], int n) { // tak naprawdę: int* tab
for (int i = 0; i < n; i++) tab[i] = 0;
}
// po wywołaniu wyzeruj(tablica, 5) -> oryginalna tablica jest faktycznie wyzerowana
Zmienna lokalna funkcji żyje tylko do momentu jej zakończenia. Jeśli zwrócisz jej adres, otrzymasz wskaźnik wiszący (dangling pointer) — adres, pod którym formalnie nic już nie istnieje.
int* zly() { int x = 5; return &x; } — to błąd,
nawet jeśli się skompiluje.
Wskaźniki a klasy
Obiekt klasy można mieć na dwa sposoby: jako zwykłą zmienną na stosie, albo jako wskaźnik na obiekt utworzony na stercie. To rozróżnienie zmienia zarówno składnię dostępu do pól, jak i czas życia obiektu.
class Punkt {
public:
int x, y;
Punkt(int x, int y) : x(x), y(y) {}
void pokaz() { cout << x << "," << y; }
};
Punkt p1(1, 2); // obiekt NA STOSIE
p1.pokaz(); // dostęp przez kropkę
Punkt* wp = &p1; // wskaźnik na ISTNIEJĄCY obiekt p1
wp->pokaz(); // dostęp przez strzałkę
(*wp).pokaz(); // dokładnie to samo co wyżej, tylko mniej wygodne w zapisie
wp->pole to skrót na (*wp).poleNajpierw dereferencja (*wp daje obiekt), potem dostęp do pola kropką.
Operator -> łączy te dwa kroki w jeden, bo robi się to bardzo często.
Wskaźnik this
Każda niestatyczna metoda klasy w tle dostaje ukryty parametr this —
wskaźnik na obiekt, na którym tę metodę wywołano. Dzięki temu metoda „wie”, czyje pola modyfikuje:
class Licznik {
int wartosc = 0;
public:
Licznik& dodaj(int x) {
this->wartosc += x; // "this->" jest tu opcjonalne, ale jasno pokazuje pole obiektu
return *this; // zwracamy referencję do samego siebie
}
int get() { return wartosc; }
};
Licznik l;
l.dodaj(1).dodaj(2).dodaj(3); // łańcuchowanie wywołań dzięki "return *this"
cout << l.get(); // 6
Dynamiczne tworzenie obiektów: new i delete
Obiekt utworzony na stosie znika automatycznie, gdy kończy się jego zasięg (np. funkcja, w
której go zadeklarowano). Obiekt utworzony przez new trafia na stertę
i żyje tak długo, aż go ręcznie zwolnisz przez delete — dlatego sterta jest niezbędna
wszędzie tam, gdzie obiekt musi „przeżyć” funkcję, w której powstał (np. węzły drzewa czy listy).
Punkt* dynPunkt = new Punkt(3, 4); // obiekt na stercie
dynPunkt->pokaz();
delete dynPunkt; // KONIECZNE -> inaczej wyciek pamięci
dynPunkt = nullptr; // dobra praktyka po delete
Gdy pole klasy jest wskaźnikiem
Pole klasy może samo być wskaźnikiem — także na obiekt tego samego typu. To dokładnie ten mechanizm stoi za listami jednokierunkowymi, drzewami i każdą inną strukturą, która „wskazuje sama na siebie”:
struct Node {
int val;
Node* next; // pole klasy będące wskaźnikiem na kolejny węzeł
Node(int v) : val(v), next(nullptr) {}
};
Node* head = new Node(1);
head->next = new Node(2);
head->next->next = new Node(3);
// head -> [1] -> [2] -> [3] -> nullptr
cout << head->next->val; // 2
To samo dzieje się w strukturze drzewa binarnego — każdy węzeł ma pola left i
right będące wskaźnikami na poddrzewa, a brak dziecka oznaczany jest przez
nullptr. Wracamy do tego dokładnie w sekcji 7.
Co właściwie znaczy „klasa jest wskaźnikiem”?
Sama klasa nigdy nie „jest” wskaźnikiem — to zmienna danego typu może być
albo zwykłym obiektem (Klasa obj), albo wskaźnikiem na obiekt (Klasa* obj).
To rozróżnienie ma realne konsekwencje:
| Cecha | Klasa obj | Klasa* obj |
|---|---|---|
| dostęp do pól | obj.pole | obj->pole |
| kopiowanie | tworzy nowy, niezależny obiekt | kopiuje tylko adres — oba wskaźniki dalej widzą ten sam obiekt |
porównanie == | (jeśli zdefiniowane) porównuje zawartość | porównuje adresy — „czy to ten sam obiekt?” |
| czas życia | kończy się wraz z zasięgiem | żyje na stercie, aż wywołasz delete |
| może być „pusty” | nie | tak, nullptr |
Node* b = a; nie tworzy nowego węzła — a i b to
teraz dwie nazwy wskazujące na ten sam obiekt. Zmiana przez jedną z nich (np. b->val = 5)
jest widoczna również przez drugą.
Wskaźnik na wskaźnik (krótko)
Czasem funkcja musi zmienić sam wskaźnik znajdujący się poza nią (np. przestawić head
listy na nowy pierwszy element) — wtedy przekazuje się Node**, czyli adres wskaźnika:
void wstawNaPoczatek(Node** head, int val) {
Node* nowy = new Node(val);
nowy->next = *head; // nowy węzeł wskazuje na dotychczasowy początek
*head = nowy; // zmieniamy SAM wskaźnik head w main, nie tylko to, na co wskazywał
}
Node* head = nullptr;
wstawNaPoczatek(&head, 5); // przekazujemy adres wskaźnika head
Nowoczesny C++ oferuje std::unique_ptr i std::shared_ptr —
„inteligentne” wskaźniki, które same wywołują delete w odpowiednim momencie,
eliminując wycieki pamięci. Na olimpiadach i w zadaniach typu LeetCode rzadko są potrzebne
(czas życia obiektów jest krótki, kod startowy zwykle używa surowych wskaźników), ale warto
wiedzieć, że istnieją jako bezpieczniejsza alternatywa dla new/delete
w większych projektach.
Najczęstsze błędy
Większość błędów ze wskaźnikami nie daje błędu kompilacji — program się skompiluje i czasem nawet zadziała „przez przypadek”, a zawiedzie dopiero przy innych danych wejściowych. Warto umieć je rozpoznać:
Niezainicjalizowany wskaźnik wskazuje na losowy adres. int* p; *p = 5; —
kompiluje się, ale jest niezdefiniowanym zachowaniem. Zawsze inicjalizuj wskaźnik, jeśli
nie masz na co go od razu ustawić — użyj nullptr.
Wskaźnik wskazuje na pamięć, która już nie istnieje — najczęściej po delete
albo po zwróceniu adresu zmiennej lokalnej z funkcji (zobacz sekcję 3).
new bez odpowiadającego delete. Każdy obiekt utworzony na
stercie trzeba prędzej czy później zwolnić — inaczej program będzie zużywał coraz więcej
pamięci.
delete p; delete p; — wywołanie delete dwa razy na ten sam
wskaźnik to niezdefiniowane zachowanie. Po pierwszym delete ustaw wskaźnik na
nullptr — wywołanie delete nullptr jest bezpieczne i nic nie robi.
Node* p = nullptr; p->val; — to klasyczny segmentation fault.
Zawsze sprawdzaj if (p != nullptr) (albo po prostu if (p)) przed
dostępem do pól.
Range Sum of BST (LeetCode 938)
Treść zadania: dany jest korzeń drzewa BST (binary search tree) oraz
dwie liczby low i high. Trzeba zwrócić sumę wartości wszystkich węzłów,
których wartość mieści się w przedziale domkniętym [low, high].
Dlaczego to jest zadanie o wskaźnikach
Kod startowy definiuje strukturę dokładnie taką, jak w sekcji 5 — węzeł drzewa przechowujący dwa wskaźniki na poddrzewa:
struct TreeNode {
int val;
TreeNode *left;
TreeNode *right;
TreeNode() : val(0), left(nullptr), right(nullptr) {}
TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};
root to TreeNode* — wskaźnik na korzeń drzewa, a nie sam obiekt.
root->left i root->right to wskaźniki na poddrzewa, które mogą
być nullptr, jeśli dziecko nie istnieje. Wywołując funkcję rekurencyjnie z argumentem
root->left, nie kopiujemy całego poddrzewa — kopiujemy tylko 8-bajtowy adres, więc
rekurencja jest tania niezależnie od tego, jak duże jest poddrzewo. To dokładnie mechanizm z
sekcji 3 („przekazywanie wskaźnika do funkcji”).
Pomysł na rozwiązanie
Najprostsze podejście to przejście całego drzewa (DFS) i sprawdzenie każdego węzła. Ale własność BST — lewe poddrzewo zawiera tylko wartości mniejsze od rodzica, prawe tylko większe — pozwala obciąć (ang. prune) całe gałęzie, w których nie ma sensu szukać:
- jeśli
root == nullptr, poddrzewo jest puste — wynik to0(przypadek bazowy); - jeśli
root->valmieści się w[low, high], dodajemy go do sumy; - jeśli
root->val > low, w lewym poddrzewie mogą jeszcze istnieć wartości≥ low— wchodzimy w lewo; - jeśli
root->val < high, w prawym poddrzewie mogą jeszcze istnieć wartości≤ high— wchodzimy w prawo.
Gdy root->val ≤ low, cała lewa strona poddrzewa jest jeszcze mniejsza — z definicji
BST nie może tam być nic w przedziale, więc w ogóle nie odwiedzamy tej gałęzi (analogicznie po
prawej stronie dla high).
Rozwiązanie
class Solution {
public:
int rangeSumBST(TreeNode* root, int low, int high) {
if (root == nullptr) return 0; // puste poddrzewo -> nic nie dodajemy
int suma = 0;
if (root->val >= low && root->val <= high) // wartość w przedziale
suma += root->val;
if (root->val > low) // w lewym poddrzewie mogą być wartości >= low
suma += rangeSumBST(root->left, low, high);
if (root->val < high) // w prawym poddrzewie mogą być wartości <= high
suma += rangeSumBST(root->right, low, high);
return suma;
}
};
root == nullptr jako pierwszeGdybyśmy najpierw spróbowali odczytać root->val bez tego sprawdzenia,
a root okazał się nullptr, dostalibyśmy dereferencję nullptra —
dokładnie błąd opisany w sekcji 6.
Krok po kroku na przykładzie
Dla drzewa [10,5,15,3,7,null,18] z low = 7, high = 15
(Przykład 1 z treści zadania), wywołania wyglądają tak:
| Krok | Węzeł | W [7,15]? | Rekursja w lewo? | Rekursja w prawo? | Suma |
|---|---|---|---|---|---|
| 1 | 10 | tak, +10 | tak (10 > 7) | tak (10 < 15) | 10 |
| 2 | 5 | nie | nie — poddrzewo z 3 obcięte | tak (5 < 15) | 10 |
| 3 | 7 | tak, +7 | nie (7 > 7 to fałsz) | tak → ale dziecko nullptr | 17 |
| 4 | 15 | tak, +15 | tak → ale dziecko nullptr | nie — poddrzewo z 18 obcięte | 32 |
Wynik: 10 + 7 + 15 = 32 — zgadza się z oczekiwanym wyjściem z treści zadania.
Węzły 3 i 18 nigdy nie zostały odwiedzone — to właśnie dzięki własności
BST nie musieliśmy sprawdzać całego drzewa.
Złożoność
W najgorszym przypadku (przedział obejmuje cały zakres wartości albo drzewo jest mocno
niezbalansowane) odwiedzamy wszystkie węzły: O(N). Dla zbalansowanego drzewa i
wąskiego przedziału, dzięki obcinaniu gałęzi, czas zbliża się do O(log N + k), gdzie
k to liczba węzłów w przedziale. Pamięć dodatkowa to O(H) na stos
wywołań rekurencyjnych, gdzie H to wysokość drzewa.
Bonus: wersja iteracyjna
To samo da się zapisać bez rekurencji, trzymając wskaźniki do węzłów „do odwiedzenia” w
jawnym stosie — co dodatkowo pokazuje, że wskaźniki świetnie nadają się do przechowywania
w kontenerach, bo kopiowanie elementu vector<TreeNode*> to wciąż tylko
kopiowanie 8-bajtowego adresu, a nie całego węzła:
int rangeSumBST(TreeNode* root, int low, int high) {
int suma = 0;
vector<TreeNode*> stos; // przechowujemy WSKAŹNIKI do węzłów
stos.push_back(root);
while (!stos.empty()) {
TreeNode* w = stos.back();
stos.pop_back();
if (w == nullptr) continue;
if (w->val >= low && w->val <= high) suma += w->val;
if (w->val > low) stos.push_back(w->left);
if (w->val < high) stos.push_back(w->right);
}
return suma;
}