Lista jednokierunkowa w pascalu

To jest mój pierwszy artykuł jakikolwiek to mogłem coś źle zrobić albo mogą być błędy. Jak coś to piszcie to poprawię. Opisze tutaj sposób posługiwania się listą jednokierunkową w Pascalu. Na początek może napisze co powinieneś już wiedzieć żeby to zrozumieć: -procedury i funkcje -posługiwanie się rekordami -podstawy programowania w Pascalu (wiadomo, if, else, for, przypisywanie itd itd...)

Żeby nauczyć się list, najpierw trzeba wiedzieć co to jest wskaźnik i jak go używać. Wskaźnik w skrócie wskazuje na dane miejsce w pamięci które zostało mu wcześniej przypisanie. Np:

program wsk;
uses CRT;
type
  t_wsk=^integer;             // tworzymy typ wskaźnika
var
  wsk:t_wsk;                    // tutaj mamy zmienne wskaźnika i liczby 
  liczba:integer; 
begin
  liczba:=200;
  writeln(liczba);                // wyświetli 200
  wsk:=@liczba;               // przypisuje adres pamięci w której jest zmienna liczba
  wsk^:=500;  // odwołuje się do tamtego adresu pamięci poprzez ^, przypisuje nową wartość
  writeln(liczba);                // i wyświetli na końcu 500 zamiast 200 
  readkey;
end.

Prosty kod mający pokazać jak działają wskaźniki do pamięci. Teraz może przemyślmy jaka jest koncepcja list jednokierunkowych. Lista jednokierunkowa zawsze musi mieć swój początek, nazwijmy że to będzie głowa. Jest to zawsze rekord który ma zawsze wartość adresu następnego elementu listy (jeśli go nie ma to jest NIL), oraz jakieś zmienne z danymi. Przykładowy rekord:

type
  wsk=^lista;
  lista=record
    liczba:integer;
    nastepny:wsk;
  end;
var
  glowa:wsk;  
  liczba:integer;

Rekord zawiera: -liczba żebyśmy mieli jakieś dane w liście -nastepny które wskazuje na następny element Zmienna glowa która będzie głównym odnośnikiem do listy.

To mamy już początek programu w którym chcemy posługiwać się listami, teraz dalej. Należałoby stworzyć procedurę która dodaje kolejne elementy listy. Zrobimy też od razu samo sortującą się listę. Może najpierw nagłówek procedury i zarezerwowanie pamięci.

procedure dodaj(var glowa:wsk; liczba:integer);
var                                                 
  nowa, tmp,pop:wsk;
begin
new(nowa);                  // rezerwujemy miejsce w pamięci
nowa^.liczba:=liczba;
nowa^.nastepny:=NIL;  // przypisujemy liczba i następny element (NIL)

Nie wydaję się chyba trudne prawda? Teraz wyszukajmy w liście miejsce gdzie mamy to wstawić.

while ((tmp<>NIL) or (tmp^.liczba<liczba)) do
begin
  pop:=tmp;
  tmp:=tmp^.nastepny;
end;

Znaleźliśmy liczbę która jest większa od naszej. Poprzednią liczbę zapisaliśmy do pop. Teraz czas dodać naszą:

if (glowa = NIL ) then
  glowa:=nowa
else if (tmp=NIL) then
  pop^.nastepny:=nowa;
else if (tmp^.nr=nr) then
  writeln('Juz istnieje');
else
  begin
    glowa:=nowa;
    nowa^.nastepny:=tmp;
  end;
end;

Po kolei może wytłumaczę: 1. Sprawdzamy czy nasza pierwsza liczba(czyli glowa) jest NIL, jeśli tak to przypisujemy do głowy naszą liczbę(nowa); 2. Jeśli tmp jest NIL to używamy poprzednią liczbę (zapisaną w pop) i i zapisujemy w niej odnośnik (do następnego elementu) naszą liczbę. 3. Jeśli liczba ma taki sam nr to jej nie dodaje i wyświetla że nie może dodać. 4. Jeśli wszystko przejdzie, znaczy że nasza liczba jest najmniejsza i dodaje ją na początku listy, czyli do głowy przypisujemy nową liczbę, a do nowej liczby następną liczbę. Teraz może usuniemy niechcianą liczbę? ;> Najpierw może nagłówek i wyszukanie liczby którą chcemy usunąć.

procedure usun(var glowa:wsk;liczba);
var
  tmp,pop:wsk;
begin
tmp:=glowa;
while ((tmp<>NIL) OR (tmp^.liczba<>liczba)) do
begin
  pop:=tmp;
  tmp:=tmp^.nastepny;
end;

W ten sposób znajdziemy naszą liczbę w liście albo przejdziemy na koniec listy, czyli że nie ma takiej liczby. A do zmiennej pop zapisujemy poprzednią liczbę. Zapiszmy to w kodzie co ma zrobić w danych przypadkach:

if (tmp<>NIL) then
begin
  if(tmp=glowa) then
  begin
    glowa:=glowa^.nastepny;
    dispose(tmp);
  end
  else
  begin
    pop^.nast:=tmp^.nastepny;
    dispose(tmp);
  end;
end;
end;

Najpierw sprawdzamy czy to nie jest NIL czyli koniec listy, jakby był to znaczy że nie ma takiej liczby. Jak nie jest sprawdzamy czy to jest nasza pierwsza liczba w liście, jeśli tak to przypisujemy jako głowę następną liczbę, a liczbę usuwamy poprzez dispose żeby nam pamięci nie śmieciła :)

Fajnie by było wyświetlić daną liczbę jaką chcemy, albo wszystkie naraz. To będzie bardzo prosta procedura.

procedure pokaz(glowa:wsk);
var
  tmp:wsk;
begin
while (tmp^.nastepny<>NIL) do
begin
  writeln(tmp^.liczba);
  tmp:=tmp^.nastepny;
end;
end;

Na pojedynczą liczbę chyba sami sobie poradzicie. Wystarczy wyszukać przechodząc przez pętlę całą sprawdzając czy to aktualna liczba. Jak znajdzie to potem tylko wyświetlić. Proste prawda? :) Dobrze jest żeby jeszcze zanim zaczniecie używać jakiejkolwiek procedury w głównym programie na samym początku ustawić głowę jako NIL, czyli:

glowa:=NIL;

To tyle. Mam nadzieję że komuś pomogłem :)