Lista jednokierunkowa C++

0

Witam wszystkich. Na wstępie chciałbym zaznaczyć, że jestem zupełnie początkujący jeżeli chodzi o C++ i w ogóle programowanie. Mój problem dotyczy zrozumienia poniższego kodu, który przedstawia dodawanie elementów do listy jednokierunkowej. Konkretniej nie rozumiem dlaczego funkcja dodaj jako argument pobiera (lista *& start) oraz co w ogóle znaczy *& oraz co to daje? dlaczego w argumencie tej funkcji zapisanej w funkcji main jest tylko sam start? Z góry dziękuję za odpowiedź :)

 
#include <iostream>

using namespace std;

struct lista
{
    int numer;
    lista *wsk;
};

void dodaj(lista *&start);



int main()
{
 lista *start;
 start = NULL;

dodaj(start);



}


void dodaj(lista *&start)
{

        lista *wskaznik;
        wskaznik = start;
        for(int i = 0; i<10; i++)
        {
        wskaznik = new lista;


        cout << "podaj liczbe: ";
        cin >> wskaznik->numer;

        wskaznik->wsk = start;
        start=wskaznik;
        }

}
0

Wskaźnik przez referencję

dlaczego w argumencie tej funkcji zapisanej w funkcji main jest tylko sam start?

Przeglądanie listy jednokierunkowej odbywa się tylko w jedną stronę, od początku do końca,
więc potrzebny jest tylko wskaźnik na pierwszy elementy listy (głowa listy).
Fatalne nazewnictwo.

tutaj jest nieźle wytłumaczony kod listy jednokierunkowej

2

*& to jest referencja na wskaźnik, jest to bardzo podobne do ** czyli wskaźnik na wskaźnik. Po co? Aby można było modyfikować adres na który wskazuje przekazywany wskaźnik. Pewnie nie zrozumiesz, ja też bym nie zrozumiał, więc przykład:

Mamy kod, dla uproszczenia kod jest na jakimś banalnym 8bitowym procesorze z 8bitową przestrzenią adresową bez mapowania. Dla czystości przekazu pomijam odkładanie na stos adresu powrotu do funkcji i innych pierdół.

void modifyp(char *pa)
{
    a = 0xfe;
}

void modifypp(char **ppa)
{
    *a = 0xfe;
}

int main(void)
{
char *a = (char *a)0xff;
*a = 5;
modifyp(a);
*a = 6;
modifyp(&a);
*a = 7;
return 0;
}

Teraz co się dzieje? Gdy program się zaczyna, na stos (czyli adres 0x00) odkładana jest zmienna a z wartością 0xff, a w następnej linijce pod adres 0xff zapisujemy wartość 5, pamięć wygląda teraz tak:

+------+------+
| adr  | val  |
+------+------+
| 0xff | 0x05 | (*a)
| .... | .... |
| 0x00 | 0xff | (a)
+------+------+

Teraz wchodzimy do funkcji modifyp(char *), co się dzieje, na stos ląduje nowa zmienna pa i kopiujemy wartość z a czyli 0xff

+------+------+
| adr  | val  |
+------+------+
| 0xff | 0x05 | (*a)
| .... | .... |
| 0x01 | 0xff | (pa)
| 0x00 | 0xff | (a)
+------+------+

Potem w funkcji modyfikujemy wartość LOKALNEJ zmiennej pod adresem 0x01.

+------+------+
| adr  | val  |
+------+------+
| 0xff | 0x05 | (*a)
| .... | .... |
| 0x01 | 0xfe | (pa)
| 0x00 | 0xff | (a)
+------+------+

Zauważ, że nasze a w ogóle się nie zmieniło!

Po wyjściu z funkcji kompilator zwinie stos i zdejmie z niego nasze lokalne pa (wartości w pamięci zostaną nienaruszone)

+------+------+
| adr  | val  |
+------+------+
| 0xff | 0x05 | (*a)
| .... | .... |
| 0x01 | 0xfe | (null)
| 0x00 | 0xff | (a)
+------+------+

Jak widać zmienna a nie zmieniła się w ogóle, i zapis pod nią dalej będzie zapisywał adres 0xff, więc zapis *a = 6 zrobi w pamięci to:

+------+------+
| adr  | val  |
+------+------+
| 0xff | 0x06 | (*a)
| .... | .... |
| 0x01 | 0xfe | (null)
| 0x00 | 0xff | (a)
+------+------+

Nie to co chcieliśmy, teraz wchodzimy do funkcji modifypp. I znowu kompilator odkłada na stos ppa i kopiuje tam wartość 0xff? Błąd, skopiuje tam adres zmiennej (wskaźnika) a, czyli wartość 0x00

+------+------+
| adr  | val  |
+------+------+
| 0xff | 0x06 | (*a)
| .... | .... |
| 0x01 | 0x00 | (ppa)
| 0x00 | 0xff | (a)
+------+------+

Teraz instrukcja *paa = 0xfe. Jakbyśmy zrobili jak w poprzedniej funkcji paa = 0xfe to sytuacja byłaby dokładnie taka sama i wskaźnik a byłby niezmieniony, zmienilibyśmy tylko lokalną kopię paa na stosie. Bo paa to po prostu zwykła zmienna, ale jako że z gwiazdką to kompilator traktuje ją trochę inaczej. I tak, *paa = 0xfe każe wziąć wartość z paa czyli 0x00 a następnie pod ten właśnie adres (to dzieje się przez *) zapisać wartość 0xfe, więc pamięć wyglądać będzie tak:

+------+------+
| adr  | val  |
+------+------+
| 0xff | 0x06 | (*a)
| .... | .... |
| 0x01 | 0x00 | (ppa)
| 0x00 | 0xfe | (a)
+------+------+

Po wyjściu z funkcji mamy tak:

+------+------+
| adr  | val  |
+------+------+
| 0xff | 0x06 | (-> na to już nic w programie nie wskazuje)
| 0xfe | 0x00 | (*a)
| .... | .... |
| 0x01 | 0x00 | (null)
| 0x00 | 0xfe | (a)
+------+------+

Teraz zauważ, że a ma zapisane w sobie nie 0xff tylko 0xfe i wskazuje już na wartość 0x00, zapis pod *a spowoduje zapisanie do pamięci o adresie 0xfe wartość 7

+------+------+
| adr  | val  |
+------+------+
| 0xff | 0x06 | (-> na to już nic w programie nie wskazuje)
| 0xfe | 0x07 | (*a)
| .... | .... |
| 0x01 | 0x00 | (null)
| 0x00 | 0xfe | (a)
+------+------+

Trochę to może wydawać się ciężkie, wskaźnik na wskaźnik może wydawać się trudny do ogarnięcia i tak jest dopóki nie rozrysujemy sobie tego wszystkiego co się w pamięci dzieje.

Z referencją na wskaźnik jest podobnie, z tym, że mniej gwiazdek się w funkcji używa i troszkę inaczej może pamięć i kod asemblera wyglądać, niestety nie znam referencji od kuchni, to tłumaczyłem na wskaźnikach:)

0

Rzuć okiem na ten link, może się coś rozjaśni: http://eduinf.waw.pl/inf/alg/001_search/0086.php :)

1 użytkowników online, w tym zalogowanych: 0, gości: 1