Programowanie w języku Delphi » Artykuły

Wskaźniki. Listy jedno i dwukierunkowe

  • 2015-04-10 18:22
  • 15 komentarzy
  • 5886 odsłon
  • Oceń ten tekst jako pierwszy
<center> Wskaźniki
Listy jedno i dwukierunkowe

</center><center> Spis treści</center><center> Wstęp do wskaźników</center>
Otóż co to są wskaźniki? To jest poprostu liczba będąca adresem komórki pamięci. Tak więc, jeśli jakaś zmienna jest wskaźnikiem, to (o ile nie zawiera wartości nil) możemy być pewni, że na coś wskazuje (stąd nazwa, proste co nie?). Typ danych, na który wskazuje nam ów pointer może być dowolny, a na dodatek, wskaźnik, podaje nam tylko adres pierwszej komórki pamięci. Jeśli za wskaźnikiem kryje się np. typ Cardinal, to za tym co podaje nam wskaźnik kryją się jeszcze 3 bajty informacji (jak wiemy Cardinal zajmuje 4 bajty). Dlatego też niezbędne jest posiadanie wiedzy o rozmiarze, a najlepiej typie struktury, do której mamy adres. Ponadto za pomocą pointerów możemy wykorzystać wyższą pamięć komputera, a nie tylko tą, która jest przydzielona dla programu. Dla przypomnienia dodam, iż granica ta w Turbo Pascalu wynosiła 64kB. Tak, tylko tyle było miejsca na wszystkie zmienne programu, niezbyt wiele.

rys1.1.gif
Rys 1.1 Organizacja pamięci

Dereferencją nazywamy odwołanie się do elementu wskazywanego. Dla przykładu podam prosty kod, może będzie to łatwiej zrozumieć.

type
 PCardinal = ^Cardinal; // deklarujemy typ wskaźnikowy
var
 Wskaznik: PCardinal; // używamy typu wskaźnikowego
 Liczba: Cardinal;
begin
 Liczba := 1000; // przypisujemy jakąś wartość początkową
 Wskaznik := @Liczba; // Wskaznik wskazuje teraz na zmienna Liczba
 Wskaznik^ := 2000; // używamy dereferencji
 ShowMessage(IntToStr(Liczba)); // wyskakuje 2000, a nie 1000.
end;
  Listing 1.1 Przykładowa dereferencja

Podsumuwując, co dają nam wskaźniki? Możliwość wykorzystania większych obszarów pamięci, a także ciekawy sposób organizacji danych. Jednem z nich są właśnie listy, których rozwinięciem są drzewka.
Jest to taki łopatologiczny opis wskaźników i może nie do końca konkretny, dający jednak z grubsza pojęcie o temacie. W przyszłości rozwinę ten temat.
<center> Wstęp do list</center>
Do głowy przychodzi zapewne niektórym pytanie co to są listy? Nie, nie, to nie jest nic związanego z TListBox, ani innymi takimi wynalazkami. Otóż wyobraźcie sobie sznurek z supełkami, który trzymacie za pierwszy supełek. Żeby nie było za łatwo, to do tej scenerii dodajcie kompletne ciemności. Mając poczatek takiego sznurka, możemy bez problemu przejść na kolejny supełek, z tego na następny, z którego z koleji możemy przejść na kolejny itp, aż znajdziemy koniec sznurka. Lista jest własnie takim sznurkiem, a supełki - elementami listy.

rys2.1.gif
Rys 2.1 Uproszczony wygląd listy

Po liście można się poruszać tak długo, dopóki nie trafi się na jej koniec, w przypadku programowym koniec listy to nic innego jak wartość nil w polu Next elementu.
<center> Lista jednokierunkowa</center>
Skoro wiadomo już jak wygląda lista, czas coś takiego zaprogramować. Na początek kilka deklaracji.

type
 PElement = ^TElement;
 TElement = record
   Next: PElement; // wskaźnik na element następny listy
   Dane: Integer; // tu możemy użyć dowolnego typu danych
 end;
 
public 
 Root: PElement; // potrzebujemy początku listy
 Last: PElement; // koniec listy także się przyda
 procedure GenerateList(Count: Integer);
 procedure DestroyList;
  Listing 3.1 Deklaracje

Zmienna Root będzie nam zawsze wskazywała na pierwszy element w liście, natomiast Last na ostatni. Można by się obejść bez tej drugiej zmiennej, jednak za każdym dodaniem do listy, trzeba by przejść przez nią całą, aby odnaleźć ostatni jej element i nowy dopisać na koniec. Lepiej poświęcić te 4 bajty na wskaźnik niż tracić czas procesora, tym bardziej, że gdy lista robi się dłuższa... no sami wiecie. Teraz czas na procedurę tworzącą nam daną ilość losowych elementów i dopisującą te elementy do listy.

 procedure TForm1.GenerateList(Count: Integer);
 var
  n: Integer;
  NewOne: PElement;
 begin
  Randomize;
  Root := nil;
  Last := nil;
  for n := 1 to Count do
   begin
    New(NewOne);
    NewOne^.Next := nil;
    NewOne^.Dane := Random(10000);
    if Root = nil then
     begin
      Root := NewOne;
      Last := Root;
     end else begin
      Last^.Next := NewOne;
      Last := NewOne;
     end;
   end;
 end; 
  Listing 3.2 Procedura generująca listę

Analizując powyższy kod, można zauważyć, że najpierw zmienne Root oraz Last są ustawiane na nil, następnie Count ilość razy przypisywana jest pamięć dla obiektu TElement, jego wartość Next jest ustawiana na nil (z tej samej przyczyny dla której poprzednie dwie zmienne też zostały ustawione na nil, otóż póki nie przypisze się żadanej przez nas wartości to wskaźnik wskazuje na coś, ale te coś jest wybrane poprostu losowo, np. w pamięci siedziała bitmapa, a następnie funkcja New pzydzieliła pamięć należący niegdyś do tej bitmapy, struktura TElement wypełni się wtedy fragmentem tej bitmapy, my tego nie chcemy więc musimy ustawić wartości po swojemu). Następnie jeśli nie mamy jeszcze pierwszego elementu to należy go stworzyć, w przeciwnym wypadku dopisujemy nowy element do końca listy.
Skoro wiemy jak tworzyć listę, przydałoby się wiedzieć jak ją usunąć z pamięci. Przecież zażądaliśmy nowych obszarów pamięci używając New i w dobrym guście byłoby po sobie posprzątać, samo się to nie zrobi.

procedure TForm1.DestroyList;
var
 ToDelete: PElement;
begin
 while Root <> nil do
  begin
   ToDelete := Root;
   Root := Root^.Next;
   Dispose(ToDelete);
  end;
end;
  Listing 3.3 Procedura usuwająca listę

W powżyszym kodzie, przesuwamy się po liście od początku powodując, że każdy kolejny element staje się początkiem, a pierwotnie pierwszy element jest zwalniany. Pętla trwa póki nie dojdziemy do końca listy. Nie jest to chyba specjalnie skomplikowane?Teraz umiemy stworzyć listę, a takżę ją usunąć. Jednak przydałoby się móc obejrzeć jak ta lista wygląda, jakoś ją wyświetlić. Otóż nic prostszego. Z pomocą przyjdzie nam mocno oklepane TMemo.

procedure TForm1.Button1Click(Sender: TObject);
var
 AtList: PElement;
begin
 Memo1.Lines.BeginUpdate;
 Memo1.Lines.Text := 'START';
 AtList := Root;
 while AtList <> nil do
  begin
   Memo1.Lines.Text := Memo1.Lines.Text + ' -> ' + IntToStr(AtList^.Dane);
   AtList := AtList^.Next;
  end;
 Memo1.Lines.EndUpdate;  
end;
  Listing 3.4 Procedura wyświetlająca listę

Pamiętajmy jednak, że zanim ją wyświetlimy, to należałoby ową listę stworzyć, a po jej wyświetleniu, lub gdy nei będzie już potrzebna - usunąć ją.
<center> Lista jednokierunkowa samoorganizująca się</center>
Wyrażenie samoorganizująca się może brzmieć jak koszmar, ale nic bardziej mylnego. Taka lista to poprostu lista, która sama się sortuje przy jej tworzeniu. Łatwo jest zauważyć, iż aby posortować listę z poprzedniego rodziału trzeba by ją całą przebudować. Zamiast przebudowywać listę, przebudujemy procedurę ją tworzącą.

procedure TForm1.GenerateList(Count: Integer);
var
 n: Integer;
 AtList, NewOne: PElement;
begin
 Randomize;
 Root := nil;
 for n := 1 to Count do
  begin
   New(NewOne);
   NewOne^.Next := nil;
   NewOne^.Dane := Random(10000);
   if Root = nil then
    begin
     Root := NewOne;
    end else begin
     if Root^.Dane > NewOne^.Dane then
      begin
       NewOne^.Next := Root;
       Root := NewOne;
      end else begin
       AtList := Root; // zaczynamy od początku
       while (AtList^.Next <> nil) and (AtList^.Next^.Dane < NewOne^.Dane) do
        begin
         AtList := AtList^.Next; // przechodzimy element wprzód
        end;
       if AtList^.Next = nil then
        begin
         AtList^.Next := NewOne;
        end else begin
         NewOne^.Next := AtList^.Next;
         AtList^.Next := NewOne;
        end;
      end;
    end;
  end;
end;
  Listing 4.1 Procedura tworząca samoorganizującą się listę

Procedura trochę już urosła. Zmienna Last nie jest już tutaj potrzebnam gdyż za każdym dodaniem nowego elementu, lista jest przeszukiwana w poszukiwaniu odpowiedniego miejsca do wstawienia elementu, a nie jest on już dodawany na koniec listy. Zanim zacznę tłumaczyć sposób działania to przedstawię kilka rysunków.

rys4.1.gif
Rys 4.1 Lista i nowy element

Otóż mamy już jakąś listę, z posortowanymi elementami. Dodajemy do niej nowy element. Teraz trzeba znaleźć mu miejsce. Warunek Root.Dane > NewOne.Dane sprawdza czy wartość pierwszego elementu jest większa od wartości nowego. Jeśli tak to należy wstawić nowy element przed pierwszy.

rys4.2.gif
Rys 4.2 Lista i jej nowy pierwszy element (stare połączenie pomalowane na szaro)

Ważna jest tutaj kolejność operacji. Jesli odrazu przypieszemy zmiennej Root adres do nowego elementu utracimy mozliwość wpisania czegokolwiek sensownego do wartości Next nowego elementu. Jeśli powyższy warunek okaże się fałszem wtedy nie ma innego wyjścia jak przejść przez całą listę i znaleźć element, którego następca ma wartość mniejszą od wartości nowego elementu. Stąd warunek (AtList.Next < nil) and (AtList.Next.Dane < NewOne.Dane). Pierwsza część pozwala nam bezpiecznie przemieszczać się po liście aż do końca, druga część przerywa pętlę jeśli zostanie znaleziony odpowiedni element. Po zakończeniu pętli są dwa wyjścia. Pierwsze z nich to trafienie na koniec pętli (warunek AtList^.Next = nil). Wtedy poprostu wstawiamy nowy element na koniec listy.

rys4.3.gif
Rys 4.3 Lista i jej nowy, ostatni element (stare połączenie pomalowane na szaro)

Jeśli jednak pętla została przerwana warunkiem mniejszości, oznacza to, że "stoimy" na liście, na elemencie, którego następca ma wartość większą od wartości nowego elementu. Prościej mówiąc, zmienna AtList wskazuje na element, po którym należy wstawić nowy klocek. Tutaj także kolejność operacji przepisywania połączeń jest bardzo ważna i nie wolno się pomylić, ponieważ zniszczy to delikatną ciagłość listy.

rys4.4.gif
Rys 4.4 Lista i jej nowy, nie pierwszy i nie ostatni, element (stare połączenie pomalowane na szaro)

<center> Lista dwukierunkowa</center>
Lista dwukierunkowa to nic innego jak modyfikacja listy jednokierunkowej. Zaletą takiej listy jest możliwość przejścia nie tylko do następnego elementu, ale i także do poprzedniego elementu. Schematycznie taką listę można przedstawić tak jak na poniższym szkicu.

rys5.1.gif
Rys 5.1 Lista dwukierunkowa

Natomiast deklaracja typu zmienia się tylko poprzez dodanie wartości Prev

type
 PElement = ^TElement;
 TElement = record
   Next: PElement; // wskaźnik na element następny listy
   Prev: PElement; // wskaźnik na element poprzedni listy
   Dane: Integer; // tu możemy użyć dowolnego typu danych
 end;
  Listing 5.1 Deklaracje

Napiszmy teraz procedurę tworzącą listę dwukierunkową. Wykorzystamy do tego procedurę z poprzedniego rozdziału, dodać nalezy tylko instrukcje tworzące połączenia wsteczne. Ponieważ w takiej liscie mamy możliwość przejścia przez nią od tyłu, warto dodać globalną zmieną Last

  public
    Last: PElement;
 
[...]
 
procedure TForm1.GenerateList(Count: Integer);
var
 n: Integer;
 AtList, NewOne: PElement;
begin
 Randomize;
 Root := nil;
 for n := 1 to Count do
  begin
   New(NewOne);
   NewOne^.Next := nil;
   NewOne^.Prev := nil;
   NewOne^.Dane := Random(10000);
   if Root = nil then
    begin
     Root := NewOne;
     Last := Root;
    end else begin
     if Root^.Dane > NewOne^.Dane then
      begin
       NewOne^.Next := Root;
       Root^.Prev := NewOne;
       Root := NewOne;
      end else begin
       AtList := Root;
       while (AtList^.Next <> nil) and (AtList^.Next^.Dane < NewOne^.Dane) do
        begin
         AtList := AtList^.Next;
        end;
       if AtList^.Next = nil then
        begin
         AtList^.Next := NewOne;
         NewOne^.Prev := AtList;
         Last := NewOne;
        end else begin
         NewOne^.Next := AtList^.Next;
         NewOne^.Prev := AtList;
         AtList^.Next^.Prev := NewOne;
         AtList^.Next := NewOne;
        end;
      end;
    end;
  end;
end;
  Listing 5.2 Procedura generująca listę dwukierunkową

Teraz możecie spytać jak przejść tą listę od końca? Wystarczy zmodyfikować poprzednią procedurę służącą do wyświetlenia listy.

procedure TForm1.Button2Click(Sender: TObject);
var
 AtList: PElement;
begin
 Memo1.Lines.BeginUpdate;
 Memo1.Lines.Text := 'END';
 AtList := Last;
 while AtList <> nil do
  begin
   Memo1.Lines.Text := Memo1.Lines.Text + ' -> ' + IntToStr(AtList^.Dane);
   AtList := AtList^.Prev;
  end;
 Memo1.Lines.EndUpdate;
end;
  Listing 5.3 Wyświetlanie listy dwukierunkowej od końca

<center> 19 lipiec 2004</center>

15 komentarzy

abrakadaber 2014-04-25 09:25

@{Adam Boduch}  zjadło obrazki. W kodzie mamy coś takiego <img src="{{SITE URL}}bin/rys2.1.gif" /> i teraz czy tag {{SITE URL}} działa i po prostu zjadło rysunek czy jest to wymysł autora?

RedSand 2006-05-06 14:34

I mam problem. Co robię źle bo wyskakuje mi ptzy jednokierunkowej:
[Error] Unit1.pas(80): Illegal character in input file: '&' ($26)
O co chodzi, co zepsułem??

RedSand 2006-04-17 20:58

No rysunków to się nie doczekamy, co??

Sheitar 2005-05-02 12:59

Rysunki to hmm pewnie jakiś błąd w Coyote.

Thomashek 2005-04-12 18:16

A co z rysuneczkami? Wcięło?

wotek 2005-03-17 20:23

Świetny art!

brodny 2005-02-25 00:19

Ano dlatego, że najpierw (jak dodajesz nowy element) to w ostatnim zapisujesz do niego adres (żeby było wiadomo, że po tym, który jest teraz ostatni, coś będzie) a potem zapisujesz wskaźnik do ostatniego elementu listy. Jeśli zrobiłyś odwrotnie to w ostatnim elemencie listy (przynajmniej w teorii, chodzi o element wskazywany przez Last) jako następny element wskazany byłby... ten sam element. W przypadku przetwarzania element po elemencie i dostania się do tego \"ostatniego\" mamy martwy punkt (no, może nie taki martwy, to bodajże nieskończona pętla będzie :) ).

AdamK 2005-01-15 13:34

A ja mam kilka pytan:
Dlaczego te dwie linijki sa potrzebne:
      Last^.Next := NewOne;
      Last := NewOne;
I akurat w takiej kolejnosci? Jak kombinowalem wywalalem jedna albo zmienialem kolejnosc to nie dzialalo (dodawal sie i wyswietlal tylko 1 element listy).
Drugie pytanie jak zrobic zgrabne usuwanie elementow z listy, napisalem cos u siebie ale wyszedl mi niezly kolos :(

Iwan 2004-11-18 17:02

Fajny artykuł, ale i tak nic z tego ni jarzę :)

RafalS 2004-08-10 10:54

Fajny art. Dopracowane formatowanie.

brodny 2004-07-30 22:10

Nie ma nawet co skomentować :). Wreszcie ktoś mi porządnie wytłumaczył listy :)

Kszol 2004-07-22 10:34

Świetny artykuł...
Nic dodać nic ująć.

lofix 2004-07-20 09:45

no cycu. art pierwyj sort, i jakie ladne formatowanie...

Sheitar 2004-07-23 21:30

Rysunki to zasługa Worda 2003 :)
Zastosowanie list... są to swego rodzaju "tablice" a jak wiemy to dość pożyteczny obiekt. Elementów listy może być tyle ile daje nam wynik działania "Wolna_Pamięć div SizeOf(TElement)". Co do zastosowania... głównie proste bazy danych (w bardziej złożonych to drzewka binarne). O ile dostanie się do n-tego elementu listy wymaga trochę szperania, o tyle operacje typu usunięcie 1 czy 100 pozycji ze środka to będzie jedno i to samo, poprostu przepisuje się wiązanie między elementem x, a x+1, na x i x+100. Używając tablic trzeba by przenieść wszystkie dane powyżej x+100 o 100 pozycji w dół, a to już trochę zajmuje.

Deti 2004-07-22 16:27

Art z całą pewnością dopracowany w 100% [ rysuneczki mniam ;) ] .. - połowe z tego znałem wcześniej - jednak nauczyłem się czegoś nowego :) .. Jednak brakuje mi tu kilku przykładów praktycznego zastosowania list... - jeśli masz takowe fajnie by było je tu zamieścic...