TI/Algorytmy i struktury danych/Dynamiczne struktury danych
Spis treści
szkic
- co to jest tablica i jakie ma wady, jak to jest w pythonie, a jak to jest gdzie indziej i czemu to, że będizemy te struktury implementować w pythonie jest trochę oszukane
- wskaźnik w miejsce pamięci – czysto teoretycznie, kilka ćwiczeń na „odwołania do pamięci”, co jest wskaźnikiem, a co wartością miejsca w pamięci
- prosta lista jenokierunkowa, przejście i wypisanie elementów -- implementacja w C
- przykład programu w C ze wskaźnikami, przykład błędu jakiegoś złego odwołania do pamięci, żeby zobaczyli, jak takie coś wygląda, wyjaśnienie na czym to polega, wszystko na zasadzie oswajania że kiedyś może ich to spotkać?
- nie tylko teoria, również implementacja w C
zadania
odwracanie listy
procedure odwrocListe(l : lista);
var
p, q : lista;
begin
if l != nil then
begin
p := l^.nast;
q := nil;
while p != nil do
begin
l^.nast := q;
q := l;
l := p;
p := p^.nast;
end;
l^.nast := q;
end;
end;
koniecznie zadanie ze sprawdzaniem czy lista ma cykl przez parę ścigających się wskaźników :-)
function czyListaMaCykl(l : lista) : boolean; var p : lista; begin if l = nil then begin p := l^.nast; while (p != nil) and (p != l) do begin l := l^.nast; p := p^.nast; if p != nil then p := p^.nast; end; czyListaMaCykl := p != nil; end else czyListaMaCykl := false; end;
scalanie dwóch posortowanych list
procedure scal(var l1 : lista; l2 : lista); var p, q, s : lista; begin new(p); p^.nast := nil; q := l1; l1 := p; while (q != nil) and (l2 != nil) do begin if q^.value < l2^.value then begin p^.nast := q; q := q^.nast; p^.nast^.nast := nil; end else if p^.value > l2^.value then begin p^.nast := l2; l2 := 2l^.nast; p^.nast^.nast := nil; end else begin p^.nast := q; q := q^.nast; s := l2; l2 := l2^.nast; dispose(s); p^.nast^.nast := nil; end; end; if q != nil then p^.nast := q; if l1 != nil then p^.nast := l1; end;
mamy listy posortowane l1 i l2, z l2 usunąć wszystkie elementy występujące na liście l1 - zastosowanie atrapy
procedure usun(var l1 : lista; l2 : lista); var p, q : lista; begin new(p); p^.nast := l1; q := l1; l1 := p; while (q != nil) and (l2 != nil) do begin if q^.value = l2^.value then begin p^.nast := q^.nast; q := q ^.nast; delete(p^.nast); end else if q^.value < l2^.value then q := q^.nast; else l2 := l2^.nast; end; p := l1; l1 := l1^.nast; dispose(p); end;
dana jest lista nieposortowana, uzyskać listę w której najpierw będą elementy ujemne, później zera i na końcu dodatnie
procedure tasuj(var l : lista); var a, b, c, d : lista; begin new(a); new(b); new(c); a^.nast := nil; b^.nast := nil; c^.nast := nil; d := l; while d != nil do begin if d^.value = 0 then begin p := b^.nast; b^.nast := d; d^.nast := p; end else if d^.value < 0 then begin p := a^.nast; a^.nast := d; d^.nast := p; end else begin p := c^.nast; c^.nast := d; d^.nast := p; end; d := d^.nast; end; l := a^.nast; dispose(a); if l = nil then begin l := b^.nast; dispose(b); if l = nil then begin l := c^.nast; dispose(c); end else begin a := l; while a^.nast != nil do a := a^.nast; a := c^.nast; dispose(c); end; end else begin a := l; while a^.nast != nil do a := a^.nast; a^.nast := b^.nast; dispose(b); if a^.nast = nil then begin a^.nast := c^.nast; dispose(c); end else begin while a^.nast != nil do a := a^.nast; a^.nast := c^.nast; dispose(c); end; end; end;
Tablica a lista
tablica ma ustaloną długość, aby przechowywać więcej elementów musimy zaalokować nową tablicę o większej pojemności i przepisać wszystkie elementy (patrz opis tablicy dynamicznej w podrozdziale koszt amortyzowany), podobny problem występuje gdy chcemy wstawić do tablicy wartość między dwie już istniejące - wszystkie późniejsze elementy muszą zostać przeniesione - są to niewątpliwie wady tablic, ta struktura danych ma jednak dużą zaletę mianowicie szybki dostęp do elementu o danym indeksie
konkurencją dla tablic są listy, element listy jednokierunkowej przechowuje wartość pewnego typu i wskaźnik na następny element, ostatni element wskazuje na nil (null, 0), zaletą tablic jest bardzo tanie i wygodne wstawianie elementu między dwa już istniejące, wadą jest to, że aby dostać się do jakiegoś elementu musimy przejść wszystkie go poprzedzające
lista w C:
struct elementListy{ int wartosc; elementListy * nast; };
typedef *ElementListy lista;
wypisanie listy w C:
lista * l; ... while(l != 0){ printf("%d\n", l->wartosc); l = l->nast; }
element listy dwukierunkowej trzyma także wskaźnik na poprzednik
Tablice vs listy, podejście abstrakcyjne
Złożoność list vs tablic
Różne przykłady, z którymi nie wiadomo co teraz zrobić
Wróćmy do przykładu sortowania przez liczanie, z wykładu o złożoności. Poprzednio nie umieliśmy tworzyc list, więc alokowaliśmy dodatkowo całe tablice dla każdej liczby N. Zatem złożoność pamięciowa wynosiła O(M * N). Tym razem mamy już do dyspozycji listy -- możemy zamiast tablic, w każdej komórce naszej tablicy pom tworzyć listę naszych obiektów do posortowania. Złożność pamięciowa nie pogorszy się już tak bardzo.