Tekst źródłowy strony TI/Algorytmy i struktury danych/Dynamiczne struktury danych


= 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
<source lang="pascal">
 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;
</source>
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.