[C++] Dynamiczne struktury danych

[wolder]

Witam, mam problem z tematem odnośnie dynamicznych struktur danych. Wiem bardzo dobrze jak działają i do czego służą, ale nie rozumiem ich kodu źródłowego. Weźmy tu np. stos. Program w książce wygląda następująco:


Definicja struktury:

Kod: Zaznacz cały

struct element
{
    int wartosc;
    emelent *poprzedni;
};

Funkcja wykonująca dodawanie elementów:

Kod: Zaznacz cały

element *dodaj (int liczba, element *wierzcholek)
{
    element *wsk;
    wsk = new element;
    if (!wsk) return 0;
    wsk->wartosc = liczba;
    wsk->poprzedni = wierzcholek;
    return wsk;
}

Już na samym początku nie rozumiem definicji struktury. Wiem, że można zagnieżdżać struktury, ale tutaj deklarujemy pole struktury jako typ strukturalny tej samej struktury i to na dodatek jako wskaźnik. Nie potrafię zrozumieć tego działania.
Kolejny problem jest w funkcji dodającej elementy. Tutaj bardzo bym prosił o wytłumaczenie poszczególnych elementów, począwszy od argumentów funkcji, typu zwracanego oraz samej definicji.

[Jacek_Karwatka]

struktura zawiera dwa pola
-wartość gdzie jest przechowywana wartość konkretnej danej
- poprzedni - wskaźnik do takiej samej struktury zawierającej poprzedni element
Przedstawiona struktura to klasyczna lista jednokierunkowa.
Konstrukcją przypomina łańcuch
Dwuelementowa lista składa się z dwóch instancji omawianej struktury
el1=[wartość=w1, poprzedni=NULL]
el2=[wartość=w2, poprzedni=el1]
każda instancja struktury to jedno ogniwo łańcucha które zawiera wartości wskaźnik do kolejnego ogniwa

el2 -> el1 -> NULL

Wierzchołek listy to el2. Każdy element (z wyjątkiem ostatniego) zawiera wskaźnik do poprzedniego elementu. Przechodząc po kolei można przejżeć wszystki elementy listy.
Załóżmy ze mamy dwuelementowa listę i chcemy dodać nowy element (ogniwo łańcucha)
Najpierw tworzymy dynamicznie nowe ogniwo

element *wsk;
wsk = new element;

sprawdzamy czy przydział pamięci udał się

if (!wsk) return 0;

W nowym ogniwie przypisujemy zadaną wartość

wsk->wartosc = liczba;

W nowym ogniwie ustawiamy wskaźnik poprzedni na obecny wierzchołek listy
Teraz to nowe ogniwo jest wierzchołkiem listy która ma już 3 elementy

wsk->poprzedni = wierzcholek;

Zwracamy nowy wierzchołek listy

return wsk;

Ot i cała procedura:-)




f
f
f
f

[wolder]

Nagle wszystko stało się jasne! Nawet nie wiem jak dziękować, wszystko jasno i przejrzyście opisane. Dzięki raz jeszcze.

[Igor V]

W strukturze element, polem nie jest inna struktura tylko wskaźnik na nią. Zwłaszcza że nie jest to definicja z explicte tworzeniem obiektu tylko sama deklaracja. Mówi to tylko tyle żeby w pamięci zarezerwować miejsce na wskaźnik danego typu. W funkcji dodaj:
- w linii 1 nie wiem za bardzo co tłumaczyć. Funkcja przyjmuje wartość int i wskaźnik na strukturę typu element oraz zwraca wskaźnik na strukturę typu element
- w linii 3 masz deklarację wskaźnika na strukturę typu element
- w linii 4 zostaje utworzony obiekt struktury i zostaje zwrócony przez operator new wskaźnik do zaalokowanej pamięci, który zostaje przypisany do wskaźnika wsk
- w linii 5 powiem szczerze że nie pamiętam czy to było od początku C++ czy od któregoś standardu, ale
new w przypadku błędu standardowo nic nie zwraca tylko rzuca wyjątkiem typu bad_alloc więc u Ciebie ten if się nie wywoła nawet jak będzie błąd alokacji pamięci. Żeby się wywołał musisz zrobić tak żeby new w przypadku błędu zwracał NULL zamiast rzucać wyjątkiem (którego nawiasem mówiąc też już się nie powinno używać, a zamiast niego stosować nullptr) , a do tego służy nothrow :

Kod: Zaznacz cały

wsk = new(std::nothrow) element;

Teraz w przypadku błędu alokacji pamięci new zwraca NULL, który jest równoznaczny z 0, więc warunek logiczny to odwróci i wejdziesz w if-a.
Pomijam już fakt że ten stos mimo wszystko jakoś dziwnie wygląda.

-- 5 sie 2017, o 14:42 --

Widzę że ktoś już odpisał, w trakcie jak musiałem wyskoczyć na chwilę przy pisaniu posta, ale szkoda było mi już marnować tego co napisałem.