Wskaźniki. Listy jedno i dwukierunkowe
Sheitar
<font style="font-family: Verdana; font-size: 10pt; font-weight: bold;">Wskaźniki
Listy jedno i dwukierunkowe </span> <font style="text-align: center; padding: 2px; width: 100%; background-color: #EAEAEA; font-family: Verdana; font-size: 8pt; font-weight: bold;">Spis treści</span>
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.
Dereferencją nazywamy odwołanie się do elementu wskazywanego. Dla przykładu podam prosty kod, może będzie to łatwiej zrozumieć.
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.
<font style="text-align: center; padding: 2px; width: 100%; background-color: #EAEAEA; font-family: Verdana; font-size: 8pt; font-weight: bold;">Wstęp do list</span>  |
| 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ć.
</p>
|
| 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.
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.
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.
<font style="text-align: center; padding: 2px; width: 100%; background-color: #EAEAEA; font-family: Verdana; font-size: 8pt; font-weight: bold;">Lista jednokierunkowa</span>  |
| 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.
Skoro wiadomo już jak wygląda lista, czas coś takiego zaprogramować. Na początek kilka deklaracji.
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.
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ą.
<font style="text-align: center; padding: 2px; width: 100%; background-color: #EAEAEA; font-family: Verdana; font-size: 8pt; font-weight: bold;">Lista jednokierunkowa samoorganizująca się</span>|
```delphi
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 |
| 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.
```delphi
procedure TForm1.DestroyList;
var
ToDelete: PElement;
begin
while Root < nil do
begin
ToDelete := Root;
Root := Root^.Next;
Dispose(ToDelete);
end;
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ą.
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ą.
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
<font style="text-align: right; padding: 2px; width: 100%; background-color: #EAEAEA; font-family: Verdana; font-size: 8pt; font-weight: bold;">19 lipiec 2004</span>
```delphi
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 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
|
```delphi
public
Last: PElement;
[...] procedure TForm1.GenerateList(Count: Integer); |
| Listing 5.3 Wyświetlanie listy dwukierunkowej od końca |
@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?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??
No rysunków to się nie doczekamy, co??
Rysunki to hmm pewnie jakiś błąd w Coyote.
A co z rysuneczkami? Wcięło?
Świetny art!
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 :) ).
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 :(
Fajny artykuł, ale i tak nic z tego ni jarzę :)
Fajny art. Dopracowane formatowanie.
Nie ma nawet co skomentować :). Wreszcie ktoś mi porządnie wytłumaczył listy :)
Świetny artykuł...
Nic dodać nic ująć.
no cycu. art pierwyj sort, i jakie ladne formatowanie...
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.
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...