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

 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.