Strona używa cookies (ciasteczek). Dowiedz się więcej o celu ich używania i zmianach ustawień. Korzystając ze strony wyrażasz zgodę na używanie cookies, zgodnie z aktualnymi ustawieniami przeglądarki.    X

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 :) Jeśli ktoś chce gdzieś to udostępnić proszę mnie zawiadomić mailowo chociaż (michal.switalik@gmail.com). 

programowanie

Komentarze

0 nowych
aeroflyluby   15 #1 22.02.2013 10:12

witaj na politechnice slaskiej

  #2 22.02.2013 21:44

Stanowczo odradzam naukę tego języka (podobnie jak VisualBasic). Nie wiem co do za chory pomysł, aby w 2013 roku odkopywać język, który umarł jakieś 15 lat temu.

Nauczenie się go wymusza na nas pewien sposób myślenia, zapamiętanie nietypowej składni i przesiadka z tego języka na C/C++/PHP/Java czy cokolwiek w ten deseń do litania przekleństw.
Podobnie VB, tylko on jest jeszcze bardziej prosty i wyrabia niezdrowe nawyki.

Dla czepialskich:
Nie potrafię podać teraz przykładów (bo było to bardzo dawno temu), ale uczyłem się kolejno: Pascala, C, VB, Delphi, PHP i przy każdym z nich byłem w szoku, jak mogą być różne i jak różne problemy stwarza pamiętanie składni poprzedniego.

tfl   8 #3 22.02.2013 22:20

@autor

skoro "Jak coś to piszcie to poprawię. " to musze zauwazyc, ze wiekszosc poprawnie postawionych przecinkow znajduje sie miedzy tagami [code]

lincoln2491   4 #4 23.02.2013 02:17

Z ciekawości, czemu pascal?

MrGh0st   2 #5 23.02.2013 07:12

Bo aktualnie akurat go przerabiałem.

Faja   3 #6 23.02.2013 08:12

Haha, rozwalają mnie komentarze w stylu "czemu pascal", "to jakaś archeologia". A na jakim innym języku wytłumaczyć idee list? Sorry ale inżynier informatyki powinien sam umieć napisać listy w dowolnie wybranym języku który nie ma w standardowej bibliotece takiego typu.

Druedain   14 #7 23.02.2013 10:47

@Faja
Jako czysto akademickie zajęcie, czy ciekawostka, może i tak. Ale wymyślanie koła na nowo w środowisku produkcyjnym w przypadku rzeczy wrażliwych tak jak struktury danych na wskaźnikach, jest absurdem. Życzę szczęścia, wydajności i stabilności, jeśli wszystko ma być ręcznie pisanie.

lincoln2491   4 #8 23.02.2013 15:18

@Faja
Można na c++/javie/innym języku. Po prostu zastanawia mnie po co ktoś się uczy Pascala, skoro i tak jest to język praktycznie nigdzie nie używany. U nas na uczelni (P. Poznańska) wykładowcą z podstaw programowania jest chyba najsłynniejszy programista pascala/delphi, pan A.M. No i uczylismy sie tego języka niepotrzebnie, skoro na następnym semie, na algorytmach i strukturach danych, prawie wszyscy używali już c++ (wybór języka był dowolny). Lepiej było ten czas na uczenie sie delphi, wykorzystac na uczenie się c++.

emig   5 #9 23.02.2013 23:12

Z wypowiedzi wnioskuję, że raczej większość zabierających tutaj głos karierę zawodową ma jeszcze przed sobą. Cóż, nie chcę wylewać "kubła zimnej wody" na "zapalone głowy" ale wasz przyszły pracodawca będzie miał zupełnie inne zdanie na temat "Który to język programowania najlepszy ?". Bo odpowiedzią będzie "A ten, w którym nasze oprogramowanie napisanym jest".

  #10 24.02.2013 12:45

@emig:
Nasze oprogramowanie jest w PHP i Smarty (nad tym drugim strasznie ubolewam).

Kto pisze teraz w Pascalu? Nawet "głupie" pralki mają soft w ASM/C pisany. Wprawdzie nie jestem w temacie sterowników urządzeń RTV/AGD czy typowych przemysłówek (np CNC), ale szczerze wątpię, aby którekolwiek z nich używały Pascala. Jeśli się mylę, to proszę o przykład.

emig   5 #11 25.02.2013 10:06

@RaveStar & @Ullisses

1) Ja jeszcze piszę kod w Pascalu (Delphi , Object Pascal (OpenVMS)) ! ;-)
2) Nie dlatego że "kocham Pascala" ale dlatego, że firmie w której pracuję starsze wersje wyspecjalizowany softu na nim stoją. Dopóki klienci ich używają (najbliższe 5-10 lat ;-)) Pascal będzie w firmie ciągle żywy... :/.
3) Wygooglałem "job search Python Developer" / "job search Ruby Developer" / "job search Delphi Developer" itd. To może pokazywać "zapotrzebowanie rynkowe" na programistów języka X. Dla porównania (C 32.8mln , Java 32mln, PHP 22,6 mln Python 12.9mln , C++ 10.8mln . Ruby 2.6mln , Delphi 1,2mln ,Pascal 1.2mln, Ada 1,2mln, Lisp 0.6mln, Fortran 0.6mln) Prawdopodobieństwo trafienia na "Pascala" wcale nie jest takie znikome, ba Ada czy Fortran też się mogą trafić. :D

  #12 25.02.2013 23:59

@emig - Tak u nas sie szuka ludzi piszacych w Fortranie - po co? Zeby przepisac to co bylo napisane w tym jezyku do czegos nowoczesniejszego...