Podstawy programowania- wykład

Podstawy Programowania   semestr drugiWyk ał d trzeci1. Jednokierunkowa lista liniowa
Jednokierunkowa lista liniowa jest abstrakcyjną strukturą danych przechowującą elementy w okre l
ś onym liniowym porządku. Elementy można
dodawać i usuwać z listy  w dowolnym  jej  miejscu. Czas wykonania tych  operacji  jest  stały  i  niezależny  od  ilo c
ś i  elementów  w li c
ś ie1,
natomiast czas wyszukania elementu jest proporcjonalny do ilo c
ś i elementów umieszczonych na li c
ś ie. 
2. Implementacja listy jednokierunkowej jako dynamicznej struktury danych 
Lista jednokierunkowa zostanie opisana na przykładzie programu, który wstawia do listy kolejne elementy, tak aby znajdowały się w porządku
niemalejącym. Można również użyć listy w inny sposób. Definicja typu pojedynczego elementu listy jest taka sama jak w przypadku stosu i
kolejki   (nazwy   pól   nie   mają   większego   znaczenia).   W   przypadku   list   stosuje   się   zazwyczaj   jeden   wskaźnik,   wskazujący   na   element
początkowy listy. Podstawowymi operacjami dotyczącymi listy są operacje wstawiania i usuwania elementu, i usuwanie listy. Można również
zdefiniować operację wyszukiwania elementu na li c
ś ie spełniającego ustalone kryterium. Oto kod wspomnianego wyżej programu:   
 
Operacja wstawiania elementu na listę została „rozbita” na
      1 program single_linked_list;
dwie procedury: zadaniem procedury „crate” sprawdza, czy
      2 uses crt;
istnieje pierwszy element na tej li c
ś ie. Je l
ś i nie to tworzy go
(wiersze   69     74)  i   ko c
ń zy   swoje   działanie.   Je l
ś i   takowy
      3 type
element  istnieje wywoływana jest procedura „insert_node”.
Zadaniem   tej   procedury   jest   utworzenie   nowego   elementu
      4   wskaznik=^element;
listy i umieszczenie go w odpowiednim miejscu na tej li c
ś ie.
Procedura   ta   pobiera   dwa   parametry.   Pierwszym   jest
      5   element=record
wska n
ź ik   na   pierwszy   element   listy,   a   poprzez   drugi
      6            dana:integer;
przekazywana   jest   wartoś ,
ć   która   zostanie   umieszczona   w
elemencie.   Posiada   ona   również   trzy   lokalne   zmienne
      7            next:wskaznik;
wska n
ź ikowe. Zmienna „p” b d
ę zie służyła do poruszania się
po   li c
ś ie.   Zmienna   „prev”   będzie   wskazywała   na   element
      8           end;
poprzedzający   ten,   który   wskazuje   „p”.   Zmienna   „nowy”

(…)

…(first);
116 writeln('Dostępna pamięć: ',MemAvail);
117 readln;
118 end.
3.
Uwagi końcowe
Listy jednokierunkowe można również implementować jako listy z wartownikami. W takim wypadku tworzy się na początku działania
programu jeden lub dwa elementy, które tworzą atrapy. Dzięki nim nie trzeba w procedurach usuwania i wstawiania elementów sprawdzać
dodatkowych warunków. Możliwa jest również implementacja…
... zobacz całą notatkę