Jarekz: Utworzono nową stronę " = 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 je..."

2015-05-23T14:10:38Z

Utworzono nową stronę " = 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 je..."

Nowa strona

= 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.

TI/Algorytmy i struktury danych/Dynamiczne struktury danych - Historia wersji

Jarekz: Utworzono nową stronę " = 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 je..."