Listy

Słyszałem, że nikt nie rozumie tego co jest tutaj napisane:PP
Dlatego jakby ktoś chciał coś tu napisać to nad moją wersją. Albo służę pomocą w szkole.

Lista to jest nic innego jak struktura danych, która ma pewne własności.
Najpierw napiszę co można "łatwo", a czego nie można "łatwo" na nich robić:

1. Wady i zalety

+(po co to się używa)

  • Szybki dostęp do skrajnych elementów: O(1)
  • Możliwość wstawiania w wybranym miejscu nowego elementu: O(1)(jeżeli mamy podany adres- o tym za chwilę)
  • Możliwość usuwania konkretnego elementu: O(1)(jeśli mamy adres w pamięci)
  • Dodatkowo możemy szybko połączyć dwie listy w jedną: także O(1)

-(dlaczego to nie jest takie fajne)

  • Wyszukiwanie może zająć O(n) operacji(tak jak w zwykłej tablicy)
  • Sprawdzenie wartości k-tego elementu(1<k<n): O(n), w tablicy możemy w czasie O(1)

2. Zmienne dynamiczne, adresowanie

definiując zmienną w C++ najprościej napisać po prostu:
typ_zmiennej nazwa_zmiennej;

Oznacza to stworzenie zmiennej, zajęcie dla niej pamieci. Ale uwaga! System operacyjny od razu przydziela pamięć już na początku programu. W praktyce, miejsce w pamięci jest cały czas zajęte, mimo że używamy jej dopiero po deklaracji.

Co jeżeli będziemy operować na bardzo dużych zmiennych, które w sumie przekroczą dostępną pamięć(oczywiście wszystkie naraz nie mogą być potrzebne, bo wtedy z algorytmicznego punktu widzenia jesteśmy w zupie).

Trzeba definiować zmienne dynamicznie. Co to znaczy?
Przydzielamy pamięć jeśli zmienna jest potrzebna, a jak nie to zwalniamy.

W praktyce wygląda to tak:

int *zmienna; //definicja zmiennej dynamicznej: od tego jest znak *
(…)
zmienna=new int; //przydzielenie pamieci do tej zmiennej
(…)
delete zmienna; //zwalniamy pamięć

Po zwolnieniu pamięci możemy przydzielić ją jeszcze raz.
Oczywiście po zwolnieniu pamięci(i przed przydzieleniem) nie wolno się do tej zmiennej odwoływać(grozi sygnałem SIGSEGV).
Odwołujemy się do niej jak do zwykłej(czyli statycznej)zmiennej.

2.a. Tablice
Zmienne tablicowe też mogą być zmiennymi dynamicznymi, od razu mówię że to jest temat dodatkowy, nie dotyczny list.

Wygląda to tak:

  • zmienną tablicową definiujemy jakby nie była tablicą, zrobimy to przy przydzielaniu pamięci, inaczej wygląda też zwolnienie. Pokażę na przykładzie:

int *tablica; //definiujemy tablicę(tak samo jak dla zmiennej dynamicznej nietablicowej)
(…)
tablica=new int[77]; //przydzielamy 77 elementów
(…)
delete []tablica; //[] musi być, tylko do tablic

oczywiście nie wolno się odwołać do elementu dla którego nie przydzieliliśmy pamięci, w tym przykładzie dla 77, 78 itd.

2b. Struktury
Definiujemy strukturę tak jak zwykle, np.:

struct struktura
{
int x,y;
};

Następnie definiujemy zmienną dynamiczną:

struktura *my_object;

przydzielanie pamięci oraz zwalnianie wygląda tak jak w zmiennej dynamicznej nietablicowej
odwołanie wygląda tak samo, z tym że zamiast kropki używamy ->

np.
my_object->x=7;
albo: printf("%d",my_object->y);

3. Czym jest zmienna dynamiczna?

Jest liczbą, przydzielaną przez system operacyjny. Jaką? - to nas nie obchodzi.
W każdym razie podaje ona jednoznacznie adres pamięci, gdzie się znajduje wartość.
Coś takiego się nazywa wskaźnik. Jeśli ta liczba=0, przyjmujemy że nie wskazuje nigdzie.
W praktyce zamiast 0, piszemy NULL.

4. Właściwa implementacja

Będę po kolei pisał po polsku(kto chce kod w c++, proszę zerżnąć od kogoś-ze wszelkimi konsekwencjami)
Chociażby dlatego że inaczej mi się nie chcę.

A więc definiujemy strukturę pojedynczego elementu:

struct element
{
typ wartość; //właściwa wartość
element *nastepny; //wskaźnik na następny element
};

Wskaźnik na następny element to wskazanie do miejsca w pamięci, gdzie znajduje się następnik tego, który właśnie analizujemy.
Dalej musimy zdefiniować gdzie w pamięci jest pierwszy element i ostatni(żeby wiedzieć kiedy skończyć przeszukiwanie).

element *pocz,*kon;
pocz=kon=NULL; //od razu zerujemy, na początku lista ma 0 elementów.

Dodawanie nowego elementu na koniec listy:

void dodaj(element nowy)
{
1. tworzymy nową tymczasową zmienną dynamiczną typu element, zajmujemy dla niej miejsce.
będzie to nowy element, który zaraz doczepimy do listy, od razu wypełniamy go zawartością(wpisujemy do środka wartość), a
następcę ustawiamy na NULL(ponieważ jeszcze nie ma następcy).
2a. Mamy zdefiniowaną listę, oraz ten nowy element:
a)Dla ostatniego elementu ustawiamy następcę na wskaźnik na tą tymczasową zmienną, w ten sposób dołączamy element.
b)Musimy poprawić zmienną kon, ustawić ją na ten nowo stworzony element.
2b. W przypadku kiedy lista jest pusta, nie można do niej nic dopisywać(bo wskaźniki są NULL).
ustawiamy pocz taki jak kon(pierwszy element jest jednocześnie ostatnim), jako wskaźniki na tymczasową zmienną
}
Określenie tymczasowa zmienna: chodzi o tą stworzoną w pkt. 1.
W zależności czy lista jest pusta, czy ma chociaż 1 element wykonujemy 2b albo 2a.

Znajdowanie elementu:

? znajdz(element szukany)
{
ustawiamy tymczasowy wskaźnik na start. Będziemy po kolei "wędrować" po liście, nazwiemy go tmp.
dopóki(istnieje obecny element istnieje)
{
jeżeli(tmp->wartosc==szukany)znaleźliśmy element
tmp=tmp->nast;
ustawiamy tmp na jego następce, czyli przechodzimy do kolejnego elementu
}
}
Specjalnie nie oznaczyłem typu wartości zwracanej przez funkcję
Pozostaje pytanie, kiedy się zatrzymamy?
-Na końcu listy:W pewnym momencie następca będzie NULL(czyli go nie będzie), tmp będzie wskazywać do nikąd.
Jak to sprawdzić?
- if(tmp!=NULL)…

Usuwanie elementu:

Załóżmy że usuwamy następcę obecnego elementu

void usun(element *tmp)
{
1. ustaw następcę tmp, na następcę jego następcy(proponuję na kartce sobie narysować).
zwolnij pamięć dla elementu, który właśnie odłączyliśmy(będzie potrzebna dodatkowa zmienna).
}
To jest tyle, tylko trzeba uwzględnić 2 przypadki:
1)usuwany element jest na początku: trzeba inaczej wywołać funkcję usun. Jak? -chociażby podstawiając NULL za tmp.
(trzeba poprawić wskaźnik na początek kolejki)
2)nie ma następcy usuwanego elementu(czyli usuwamy ostatni): trzeba poprawić wskaźnik na koniec kolejki oraz uważać żeby nie sprawdzać następcy ostatniego elementu.

Zadania:
1. Zaimplementuj listę jednokierunkową(napisz te 3 główne polecenia).
2. Napisz funkcję dodaj, która dodaje element na początek kolejki
3. Napisz funkcję wypisującą wszystkie elementy

Proszę o poprawę ewentualnych błędów, usunięcie niepotrzebnych dodatków jeśli są, ewentualnie napisanie tego czego nie ma(łączenie list, wypisywanie elementów, bądź ilustracji list), zdaję sobie sprawę, że to nie jest doskonałe.

Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-ShareAlike 3.0 License