Serwis Edukacyjny w I-LO w Tarnowie Materiały dla uczniów liceum |
Wyjście Spis treści Wstecz Dalej Autor artykułu: mgr Jerzy Wałaszek |
©2024 mgr Jerzy Wałaszek |
Podane tutaj procedury obsługi list nie uwzględniają sytuacji błędnych – np. braku pamięci dla tworzonych elementów czy nieprawidłowych danych. Można je zatem stosować tylko wtedy, gdy jesteśmy w 100% pewni, że nie dojdzie do żadnych błędów. W przeciwnym razie należałoby zaimplementować obsługę wyjątków, a to jest temat na osobny artykuł.
Pascal |
type PSLel = ^SLel; SLel = record next : PSLel; data : typ_danych; end; |
|
struct SLel { SLel * next; typ_danych data; }; |
Basic |
Type SLel next As SLel Ptr data As typ_danych End Type |
Python (dodatek) |
# klasa elementu listy jednokierunkowej class SLel: def __init__(self, data): self.next = None self.data = data |
# klasa listy jednokierunkowej class SLvar: def __init__(self): self.head = None |
Przechodzenie listy – ma na celu przejście kolejno przez wszystkie elementy listy, począwszy od pierwszego, a skończywszy na ostatnim. Operacja ta jest częścią składową wielu innych operacji, gdzie algorytm musi coś wyszukać na liście. W przypadku listy jednokierunkowej możemy się po niej poruszać tylko w jednym kierunku: od początku do końca. Z uwagi na sposób powiązania ze sobą elementów listy, do jej przechodzenia potrzebna jest zmienna typu wskaźnik, która będzie wskazywała na kolejne elementy. Na początku algorytmu zmienna ta powinna wskazywać pierwszy element na liście. W pętli przetwarzamy element wskazywany przez tą zmienną, po czym za nową wartość zmiennej przyjmuje się adres następnego elementu listy. Adres ten jest przechowywany w polu next elementu bieżącego. Listę przechodzimy do momentu, aż zmienna wskazująca przyjmie wartość 0. Stanie się tak po wyjściu z ostatniego elementu listy, w którego polu next przechowywany jest adres 0.
K01: Dopóki p ≠ nil, ; w pętli przechodzimy przez wykonuj kroki K02…K03 ; kolejne elementy listy K02: Przetwarzaj element wskazywany przez p K03: p ← p→next ; w p umieść zawartość pola next ; elementu wskazywanego przez p K04: Zakończ
Pascalwhile p <> nil do begin … p := p^.next; end; |
while(p) { … p = p->next; } |
BasicWhile p … p = p->next Wend |
Python
(dodatek)while p: … p = p.next |
Problem liczby elementów listy rozwiązujemy za pomocą algorytmu przejścia przez listę. Tworzymy licznik, któremu na początku nadajemy wartość 0. Następnie przechodzimy kolejno przez wszystkie elementy na liście. Przy każdym mijanym elemencie zwiększamy licznik o 1. Po przejściu całej listy w liczniku będzie liczba elementów.
K01: c ← 0 ; zeruj licznik K02: Dopóki p ≠ nil, ; w pętli przechodzimy przez wykonuj kroki K03…K04 ; kolejne elementy listy K03: c ← c+1 ; zwiększ licznik K04: p ← p→next ; w p umieść zawartość pola next ; elementu wskazywanego przez p K05: Zakończ z wynikiem c ; koniec, wynik w c
Pascalfunction l_len(p : PSLel) : cardinal; var c : cardinal; begin c := 0; // zerujemy licznik while p <> nil do begin inc(c); // zwiększamy licznik o 1 p := p^.next; // następny element end; l_len := c; end; |
unsigned l_len(SLel * p) { unsigned c = 0; // zerujemy licznik while(p) { c |
BasicFunction l_len(p As SLel Ptr) _ As UInteger Dim c As UInteger c = 0 ' zerujemy licznik While p c += 1 ' zwiększamy licznik o 1 p = p->next ' następny element Wend l_len = c End Function |
Python
(dodatek)# klasa elementu listy jednokierunkowej class SLel: def __init__(self, data): self.next = None self.data = data # klasa listy jednokierunkowej class SLvar: def __init__(self): self.head = None def l_len(self): c = 0 p = self.head while p: c += 1 p = p.next return c |
K01: p ← nowy element ; tworzymy nowy element listy ; i jego adres umieszczany w p K02: p→data ← v ; umieszczamy dane w elemencie K03: p→next ← head ; następnikiem będzie bieżący ; pierwszy element listy K04: head ← p ; ustawiamy początek listy ; na nowy element K05: Zakończ
Uwaga:
Elementy są umieszczone na liście w kierunku odwrotnym do kolejności ich wstawiania – ostatnio wstawiony element jest pierwszym elementem listy. Taka struktura pozwala prosto realizować stos. |
Pascalprocedure l_push_front(var head : PSLel; v : char); var p : PSLel; begin new(p); // tworzymy nowy element p^.data := v; // inicjujemy element p^.next := head; head := p; end; |
void l_push_front(SLel * & head, char v) { SLel * p = new SLel; p->data = v; // inicjujemy element p->next = head; head = p; } |
BasicSub l_push_front(ByRef head As SLel Ptr, _ v As String) Dim p As SLel Ptr p = new SLel ' tworzymy nowy element p->data = v ' inicjujemy element p->next = head head = p End Sub |
Python
(dodatek)class SLel: def __init__(self, data): self.next = None self.data = data class SLvar: def __init__(self): self.head = None def l_push_front(self, v): p = SLel(v) p.next = self.head self.head = p |
K01: p ← head ; zapamiętaj pierwszy element K02: Jeśli p = nil, ; zakończ, jeśli lista jest pusta to zakończ K03: head ← p→next ; początkiem listy będzie ; element następny K04: Usuń z pamięci element wskazany przez p K05: Zakończ
Pascalprocedure l_pop_front(var head : PSLel); var p : PSLel; begin p := head; // zapamiętujemy początek if p <> nil then begin head := p^.next; // nowy początek dispose(p); // usuń element z pamięci end; end; |
void l_pop_front(SLel * & head) { SLel * p; p = head; // zapamiętujemy początek if(p) { head = p->next; // nowy początek delete p; // usuń element z pamięci } } |
BasicSub l_pop_front(ByRef head As SLel Ptr) Dim p As SLel Ptr p = head ' zapamiętujemy początek If p Then head = p->next ' nowy początek Delete p ' usuń element z pamięci End If End Sub |
Python
(dodatek)class SLel: def __init__(self, data): self.next = None self.data = data class SLvar: def __init__(self): self.head = None def l_pop_front(self): p = self.head if p: self.head = p.next p = None |
Dla prostych zastosowań podane powyżej operacje dla list jednokierunkowych zwykle wystarczają. W dalszej części artykułu rozszerzamy tę listę o kolejne operacje.
Uwaga: Zanim uruchomisz program, przeczytaj wstęp do tego artykułu, w którym wyjaśniamy funkcje tych programów oraz sposób korzystania z nich. |
Poniższy program implementuje listę jednokierunkową. Elementy tej listy będą przechowywały znaki. Najpierw umieszczamy na liście kolejno litery A, B i C, następnie usuwamy z początku listy dwa elementy. Za każdym razem zawartość listy jest wyświetlana. |
Pascal// Program testowy dla list jednokierunkowych // Data: 11.02.2012 // (C)2020 mgr Jerzy Wałaszek //------------------------------------------- program slist_test1; // Typ elementów listy //-------------------- type PSLel = ^SLel; SLel = record next : PSLel; data : char; end; // Funkcja oblicza liczbę elementów listy //--------------------------------------- function l_len(p : PSLel) : cardinal; var c : cardinal; begin c := 0; while p <> nil do begin inc(c); p := p^.next; end; l_len := c; end; // Procedura wyświetla zawartość elementów listy //---------------------------------------------- procedure l_print(p : PSLel); var i : cardinal; begin writeln('Number of elements : ', l_len(p)); i := 1; while p <> nil do begin writeln('Element #', i, ' data = ', p^.data); inc(i); p := p^.next; end; writeln; end; // Procedura dołączania na początek listy //--------------------------------------- procedure l_push_front(var head : PSLel; v : char); var p : PSLel; begin new(p); p^.data := v; p^.next := head; head := p; end; // Procedura usuwa pierwszy element //--------------------------------- procedure l_pop_front(var head : PSLel); var p : PSLel; begin p := head; if p <> nil then begin head := p^.next; dispose(p); end; end; //--------------- // Program główny //--------------- var L : PSLel; // adres początku listy begin L := nil; l_push_front(L, 'A'); l_push_front(L, 'B'); l_push_front(L, 'C'); l_print(L); l_pop_front(L); l_pop_front(L); l_print(L); end. |
// Program testowy dla list jednokierunkowych // Data: 11.02.2012 // (C)2020 mgr Jerzy Wałaszek //------------------------------------------- #include <iostream> using namespace std; // Typ elementów listy //-------------------- struct SLel { SLel * next; char data; }; // Funkcja oblicza liczbę elementów listy //--------------------------------------- unsigned l_len(SLel * p) { unsigned c = 0; while(p) { c++; p = p->next; } return c; } // Procedura wyświetla zawartość elementów //---------------------------------------- void l_print(SLel * p) { unsigned i; cout << "Number of elements : " << l_len(p) << endl; for(i = 1; p; p = p->next) cout << "Element #" << i++ << " data = " << p->data << endl; cout << endl; } // Procedura dołączania na początek listy //--------------------------------------- void l_push_front(SLel * & head, char v) { SLel * p; p = new SLel; p->data = v; p->next = head; head = p; } // Procedura usuwa pierwszy element //--------------------------------- void l_pop_front(SLel * & head) { SLel * p = head; if(p) { head = p->next; delete p; } } //--------------- // Program główny //--------------- int main() { SLel * L = NULL; l_push_front(L, 'A'); l_push_front(L, 'B'); l_push_front(L, 'C'); l_print(L); l_pop_front(L); l_pop_front(L); l_print(L); return 0; } |
Basic' Program testowy dla list jednokierunkowych ' Data: 11.02.2012 ' (C)2020 mgr Jerzy Wałaszek '------------------------------------------- ' Typ elementów listy '-------------------- Type SLel next As SLel Ptr data As String * 1 End Type ' Funkcja oblicza liczbę elementów listy '--------------------------------------- Function l_len(p As SLel Ptr) As UInteger Dim c As UInteger c = 0 While p c += 1 p = p->next Wend l_len = c End Function ' Procedura wyświetla zawartość listy '----------------------------------- Sub l_print(p As SLel Ptr) Dim i As UInteger Print "Number of elements : ";l_len (p) i = 1 While p Print "Element #";i;" data = ";p->data i += 1 p = p->next Wend Print End Sub ' Procedura dołączania na początek listy '--------------------------------------- Sub l_push_front(ByRef head As SLel Ptr, _ v As String) Dim p As SLel Ptr p = new SLel p->data = v p->next = head Head = p End Sub ' Procedura usuwa pierwszy element '--------------------------------- Sub l_pop_front(ByRef head As SLel Ptr) Dim p As SLel Ptr p = head If p Then head = p->next Delete p End If End Sub '--------------- ' Program główny '--------------- Dim L As SLel Ptr L = 0 l_push_front(L, "A") l_push_front(L, "B") l_push_front(L, "C") l_print(L) l_pop_front(L) l_pop_front(L) l_print(L) End |
Wynik: |
Number of elements : 3 Element #1 data = C Element #2 data = B Element #3 data = A Number of elements : 1 Element #1 data = A |
Python
(dodatek)# Program testowy dla list jednokierunkowych # Data: 1.05.2024 # (C)2024 mgr Jerzy Wałaszek # ------------------------------------------- # klasa elementu listy # --------------------- class SLel: def __init__(self, data): self.next = None self.data = data # klasa listy jednokierunkowej # ----------------------------- class SLvar: # Konstruktor def __init__(self): self.head = None # liczba elementów def l_len(self): c = 0 p = self.head while p: c += 1 p = p.next return c # wstawianie na początek def l_push_front(self, v): p = SLel(v) p.next = self.head self.head = p # usuwanie z początku def l_pop_front(self): p = self.head if p: self.head = p.next # wyświetlenie listy def l_print(self): print("Liczba elementów :", self.l_len()) i = 1 p = self.head while p: print("Element nr", i, "dane =", p.data) i += 1 p = p.next print() # destruktor def __del__(self): while self.head: self.l_pop_front() print("Lista usunięta z pamięci") # --------------- # Program główny # --------------- sl = SLvar() # lista jednokierunkowa sl.l_push_front('A') sl.l_push_front('B') sl.l_push_front('C') sl.l_print() sl.l_pop_front() sl.l_pop_front() sl.l_print() sl = None |
Wynik: |
Liczba elementów : 3 Element nr 1 dane = C Element nr 2 dane = B Element nr 3 dane = A Liczba elementów : 1 Element nr 1 dane = A Lista usunięta z pamięci |
K01: p ← nowy element ; tworzymy nowy element listy ; i jego adres umieszczany w p K02: e→next ← nil ; inicjujemy pola nowego elementu K03: e→data ← v K04: p ← head ; w p ustawiamy początek listy K06: Jeśli p ≠ nil, ; czy lista jest pusta? to idź do kroku K09 K06: head ← e ; jeśli tak, to nowy element będzie ; pierwszym elementem listy K07: Zakończ K08: Dopóki p→next ≠ nil, ; inaczej przechodzimy wykonuj p ← p→next ; do ostatniego elementu listy K09: p→next ← e ; dołączamy nowy element ; za ostatnim na liście K10: Zakończ
Pascalprocedure l_push_back(var head : PSLel; v : char); var p, e : PSLel; begin new(e); // tworzymy nowy element e^.next := nil; // inicjujemy element e^.data := v; p := head; if p = nil then head := e else begin while p^.next <> nil do p := p^.next; p^.next := e; end; end; |
void l_push_back(SLel * & head, char v) { SLel * p, * e; e = new SLel; // tworzymy nowy element e->next = NULL; // inicjujemy element e->data = v; p = head; if(p) { while(p->next) p = p->next; p->next = e; } else head = e; } |
BasicSub l_push_back(ByRef head As SLel Ptr, _ v As String) Dim As SLel Ptr p, e e = New SLel ' tworzymy nowy element e->next = 0 ' inicjujemy element e->data = v p = head If p = 0 Then head = e Else While p->next p = p->next Wend p->next = e End If End Sub |
Python
(dodatek)class SLel: def __init__(self, data): self.next = None self.data = data class SLvar: def __init__(self): self.head = None def l_push_back(self, v): e = SLel(v) p = self.head if p: while p.next: p = p.next p.next = e else: self.head = e |
K01: p ← head ; pobieramy do p adres początku listy K02: Jeśli p = nil, ; jeśli lista jest pusta, kończymy to zakończ K03: Jeśli p→next ≠ nil, ; sprawdzamy, czy lista to idź do kroku K07 ; jest jednoelementowa K04: Usuń z pamięci element wskazywany przez p K05; head ← nil ; lista jednoelementowa staje się ; listą pustą K06: Zakończ K07: Dopóki p→next→next ≠ nil, ; idziemy do wykonuj p ← p→next ; przedostatniego elementu K08: Usuń z pamięci element ; usuwamy następny element, wskazywany przez p→next ; czyli ostatni K09: p→next ← nil ; przedostatni element nie ma ; już następnika K10: Zakończ
Pascalprocedure l_pop_back(var head : PSLel); var p : PSLel; begin p := head; if p <> nil then begin if p^.next <> nil then begin while p^.next^.next <> nil do p := p^.next; dispose(p^.next); p^.next := nil; end else begin dispose(p); // lista jednoelementowa head := nil; // staje się listą pustą end end; end; |
void l_pop_back(SLel * & head) { SLel * p = head; if(p) { if(p->next) { while(p->next->next) p = p->next; delete p->next; p->next = NULL; } else { delete p; // lista jednoelementowa head = NULL; // staje się listą pustą } } } |
BasicSub l_pop_back(ByRef head As SLel Ptr) Dim p As SLel Ptr p = head If p Then If p->next Then While p->next->next p = p->next Wend Delete p->next p->next = 0 Else Delete p head = 0 End If End If End Sub |
Python
(dodatek)class SLel: def __init__(self, data): self.next = None self.data = data class SLvar: def __init__(self): self.head = None def l_pop_back(self): p = self.head if p: if p.next: while p.next.next: p = p.next p.next = None p.next = None else: p = None # lista jednoelementowa staje się self.head = None # listą pustą |
K01: p ← head ; pobieramy do p adres początku listy K02: Jeśli p ≠ e, ;sprawdzamy, czy e nie jest to idź do kroku K05 ; pierwszym elementem listy K03: l_push_front(head, v) ; nowy element umieść ; na początku listy K04: Zakończ K05: Dopóki p→next ≠ e, ; przechodzimy do elementu wykonuj p ← p→next ; poprzedzającego e K06: p→next ← nowy element ; tworzymy nowy element listy ; i jego adres umieszczany w następniku p K07: p→next→next ← e ; inicjujemy pola nowego elementu K08: p→next→data ← v K10: Zakończ
Pascalprocedure l_insert_before(var head : PSLel; e : PSLel; v : char); var p : PSLel; begin p := head; if p = e then l_push_front(head, v) else begin while p^.next <> e do p := p^.next; new(p^.next); p^.next^.next := e; p^.next^.data := v; end; end; |
void l_insert_before(SLel * & head, SLel * e, char v) { SLel * p = head; if(p == e) l_push_front(head, v); else { while(p->next != e) p = p->next; p->next = new SLel; p->next->next = e; p->next->data = v; } } |
BasicSub l_insert_before(ByRef head As SLel Ptr, _ e As SLel Ptr, _ v As String) Dim p As SLel Ptr p = head If p = e Then l_push_front(head, v) Else While p->next <> e p = p->next Wend p->next = New SLel p->next->next = e p->next->data = v End If End Sub |
Python
(dodatek)class SLel: def __init__(self, data): self.next = None self.data = data class SLvar: def __init__(self): self.head = None def l_push_front(self, v): p = SLel(v) p.next = self.head self.head = p def l_insert_before(self, e, v): p = self.head if p is e: self.l_push_front(v) else: while(p.next is not e): p = p.next p.next = SLel(v) p.next.next = e |
K01: p ← e→next ; adres elementu następnego K02: e→next ← Nowy element ; jako następny za wybranym ; będzie nowy element K03: e→next→next ← p ; następnik nowego elementu K04: e→next→data ← v K06: Zakończ
Pascalprocedure l_insert_after(e : PSLel; v : char); var p : PSLel; begin p := e^.next; new(e^.next); (e^.next)^.next := p; (e^.next)^.data := v; end; |
void l_insert_after(SLel * e, char v) { SLel * p = e->next; e->next = new SLel; e->next->next = p; e->next->data = v; } |
BasicSub l_insert_after(e As SLel Ptr, _ v As String) Dim p As SLel Ptr p = e->next e->next = new SLel e->next->next = p e->next->data = v End Sub |
Python
(dodatek)class SLel: def __init__(self, data): self.next = None self.data = data class SLvar: def __init__(self): self.head = None def l_insert_after(self, e, v): p = e.next e.next = SLel(v) e.next.next = p; |
K01: Jeśli head ≠ e, ; sprawdzamy, czy usuwany element to idź do kroku K04 ; jest pierwszym na liście K02: l_pop_front(head) ; jeśli tak, usuwamy go z listy K03: Zakończ K04: p ← head ; w p ustawiamy początek listy K05: Dopóki p→next ≠ e, ; w p ustawiamy adres elementu wykonuj p ← p→next ; poprzedzającego e K06: p→next ← e→next ; odłączamy e od listy K07: Usuń z pamięci element wskazywany przez e K08: Zakończ
Pascalprocedure l_remove(var head : PSLel; e : PSLel); var p : PSLel; begin if head = e then l_pop_front(head) else begin p := head; while p^.next <> e do p := p^.next; p^.next := e^.next; dispose(e); end; end; |
void l_remove(SLel * & head, SLel * e) { SLel * p; if(head == e) l_pop_front(head); else { p = head; while(p->next != e) p = p->next; p->next = e->next; delete e; } } |
BasicSub l_remove(ByRef head As SLel Ptr, _ e As SLel Ptr) Dim p As SLel Ptr If head = e Then l_pop_front(head) Else p = head While p->next <> e p = p->next Wend p->next = e->next Delete e End If End Sub |
Python
(dodatek)class SLel: def __init__(self, data): self.next = None self.data = data class SLvar: def __init__(self): self.head = None def l_pop_front(self): p = self.head if p: self.head = p.next p = None def l_remove(self, e): if self.head is e: self.l_pop_front() else: p = self.head while p.next is not e: p = p.next p.next = e.next e = None |
Uwaga: Zanim uruchomisz program, przeczytaj wstęp do tego artykułu, w którym wyjaśniamy funkcje tych programów oraz sposób korzystania z nich. |
Poniższy program demonstruje opisane operacje na liście jednokierunkowej. Tworzy on listę kolejnych liter od A do G (7 elementów). Następnie wybiera element z literą D i wstawia przed nim + a za nim *. Na zakończenie z listy jest usuwany element D, pierwszy i ostatni. Po każdej operacji zawartość listy zostaje wyświetlona. |
Pascal// Program testowy dla list jednokierunkowych // Data: 7.02.2012 // (C)2020 mgr Jerzy Wałaszek //------------------------------------------- program slist_test2; // Typ elementów listy //-------------------- type PSLel = ^SLel; SLel = record next : PSLel; data : char; end; // Funkcja oblicza liczbę elementów listy //--------------------------------------- function l_len(p : PSLel) : cardinal; var c : cardinal; begin c := 0; // zerujemy licznik while p <> nil do begin inc(c); // zwiększamy licznik o 1 p := p^.next; end; l_len := c; end; // Procedura wyświetla zawartość // elementów listy //------------------------------ procedure l_print(p : PSLel); var i : cardinal; begin writeln('Number of elements : ', l_len(p)); i := 1; while p <> nil do begin writeln('Element #', i, ' data = ', p^.data); inc(i); p := p^.next; end; writeln; end; // Procedura dołączania na początek listy //--------------------------------------- procedure l_push_front(var head : PSLel; v : char); var p : PSLel; begin new(p); // tworzymy nowy element p^.data := v; // inicjujemy element p^.next := head; head := p; end; // Procedura dołączania na koniec listy //------------------------------------- procedure l_push_back(var head : PSLel; v : char); var p, e : PSLel; begin new(e); // tworzymy nowy element e^.next := nil; // inicjujemy element e^.data := v; p := head; if p = nil then head := e else begin while p^.next <> nil do p := p^.next; p^.next := e; end; end; // Procedura dołączania przed elementem e //--------------------------------------- procedure l_insert_before(var head : PSLel; e : PSLel; v : char); var p : PSLel; begin p := head; if p = e then l_push_front(head, v) else begin while p^.next <> e do p := p^.next; new(p^.next); p^.next^.next := e; p^.next^.data := v; end; end; // Procedura dołączania za elementem e //------------------------------------ procedure l_insert_after(e : PSLel; v : char); var p : PSLel; begin p := e^.next; new(e^.next); (e^.next)^.next := p; (e^.next)^.data := v; end; // Procedura usuwa pierwszy element //--------------------------------- procedure l_pop_front(var head : PSLel); var p : PSLel; begin p := head; // zapamiętujemy początek if p <> nil then begin head := p^.next; // nowy początek dispose(p); // usuń element z pamięci end; end; // Procedura usuwa ostatni element //--------------------------------- procedure l_pop_back(var head : PSLel); var p : PSLel; begin p := head; if p <> nil then begin if p^.next <> nil then begin while p^.next^.next <> nil do p := p^.next; dispose(p^.next); p^.next := nil; end else begin dispose(p); // lista jednoelementowa head := nil; // staje się listą pustą end end; end; // Procedura usuwa wybrany element //-------------------------------- procedure l_remove(var head : PSLel; e : PSLel); var p : PSLel; begin if head = e then l_pop_front(head) else begin p := head; while p^.next <> e do p := p^.next; p^.next := e^.next; dispose(e); end; end; //--------------- // Program główny //--------------- var L : PSLel; // adres początku listy e : PSLel; // wskazywanie elementów i : char; begin L := nil; for i := 'A' to 'G' do l_push_back(L, i); l_print(L); // Przechodzimy do elementu o wartości D e := L; for i := 'A' to 'C' do e := e^.next; // Przed elementem D umieszczamy + l_insert_before(L, e, '+'); // Za elementem D umieszczamy * l_insert_after(e, '*'); l_print(L); // Usuwamy element D oraz // element pierwszy i ostatni l_remove(L, e); l_pop_front(L); l_pop_back(L); l_print(L); end. |
// Program testowy dla list jednokierunkowych // Data: 11.02.2012 // (C)2020 mgr Jerzy Wałaszek //------------------------------------------- #include <iostream> using namespace std; // Typ elementów listy //-------------------- struct SLel { SLel * next; char data; }; // Funkcja oblicza liczbę elementów listy //--------------------------------------- unsigned l_len(SLel * p) { unsigned c = 0; // zerujemy licznik while(p) { c++; // zwiększamy licznik o 1 p = p->next; } return c; } // Procedura wyświetla zawartość elementów listy //---------------------------------------------- void l_print(SLel * p) { unsigned i; cout << "Number of elements : " << l_len(p) << endl; for(i = 1; p; p = p->next) cout << "Element #" << i++ << " data = " << p->data << endl; cout << endl; } // Procedura dołączania na początek listy //--------------------------------------- void l_push_front(SLel * & head, char v) { SLel * p; p = new SLel; // tworzymy nowy element p->data = v; // inicjujemy element p->next = head; head = p; } // Procedura dołączania na koniec listy //--------------------------------------- void l_push_back(SLel * & head, char v) { SLel * p, * e; e = new SLel; // tworzymy nowy element e->next = NULL; // inicjujemy element e->data = v; p = head; if(p) { while(p->next) p = p->next; p->next = e; } else head = e; } // Procedura dołączania przed elementem e //--------------------------------------- void l_insert_before(SLel * & head, SLel * e, char v) { SLel * p = head; if(p == e) l_push_front(head, v); else { while(p->next != e) p = p->next; p->next = new SLel; p->next->next = e; p->next->data = v; } } // Procedura dołączania za elementem e //------------------------------------ void l_insert_after(SLel * e, char v) { SLel * p = e->next; e->next = new SLel; e->next->next = p; e->next->data = v; } // Procedura usuwa pierwszy element //--------------------------------- void l_pop_front(SLel * & head) { SLel * p = head; // zapamiętujemy początek if(p) { head = p->next; // nowy początek delete p; // usuń element z pamięci } } // Procedura usuwa ostatni element //--------------------------------- void l_pop_back(SLel * & head) { SLel * p = head; if(p) { if(p->next) { while(p->next->next) p = p->next; delete p->next; p->next = NULL; } else { delete p; // lista jednoelementowa head = NULL; // staje się listą pustą } } } // Procedura usuwa wybrany element //-------------------------------- void l_remove(SLel * & head, SLel * e) { SLel * p; if(head == e) l_pop_front(head); else { p = head; while(p->next != e) p = p->next; p->next = e->next; delete e; } } //--------------- // Program główny //--------------- int main() { SLel * L = NULL; // adres początku listy SLel * e; // do wskazywania elementów listy char i; for(i = 'A'; i <= 'G'; i++) l_push_back(L, i); l_print(L); // Przechodzimy do elementu o wartości D e = L; for(i = 'A'; i <= 'C'; i++) e = e->next; // Przed elementem D umieszczamy + l_insert_before(L, e, '+'); // Za elementem D umieszczamy * l_insert_after(e, '*'); l_print(L); // Usuwamy element D oraz element pierwszy i ostatni l_remove(L, e); l_pop_front(L); l_pop_back(L); l_print(L); return 0; } |
Basic' Program testowy dla list jednokierunkowych ' Data: 11.02.2012 ' (C)2020 mgr Jerzy Wałaszek '------------------------------------------- ' Typ elementów listy '-------------------- Type SLel next As SLel Ptr data As String * 1 End Type ' Funkcja oblicza liczbę elementów listy '--------------------------------------- Function l_len(p As SLel Ptr) _ As UInteger Dim c As UInteger c = 0 ' zerujemy licznik While p c += 1 ' zwiększamy licznik o 1 p = p->next Wend l_len = c End Function ' Procedura wyświetla zawartość elementów listy '---------------------------------------------- Sub l_print (p As SLel Ptr) Dim i As UInteger Print "Number of elements : ";l_len(p) i = 1 While p Print "Element #";i;" data = ";p->data i += 1 p = p->next Wend Print End Sub ' Procedura dołączania na początek listy '--------------------------------------- Sub l_push_front(ByRef head As SLel Ptr, _ v As String) Dim p As SLel Ptr p = new SLel ' tworzymy nowy element p->data = v ' inicjujemy element p->next = head head = p End Sub ' Procedura dołączania na koniec listy '------------------------------------- Sub l_push_back(ByRef head As SLel Ptr, _ v As String) Dim As SLel Ptr p, e e = New SLel e->next = 0 e->data = v p = head If p = 0 Then head = e Else While p->next p = p->next Wend p->next = e End If End Sub ' Procedura dołączania przed elementem e '--------------------------------------- Sub l_insert_before(ByRef head As SLel Ptr, _ e As SLel Ptr, _ v As String) Dim p As SLel Ptr p = head If p = e Then l_push_front(head, v) Else While p->next <> e p = p->next Wend p->next = New SLel p->next->next = e p->next->data = v End If End Sub ' Procedura dołączania za elementem e '------------------------------------ Sub l_insert_after(e As SLel Ptr, _ v As String) Dim p As SLel Ptr p = e->next e->next = new SLel e->next->next = p e->next->data = v End Sub ' Procedura usuwa pierwszy element '--------------------------------- Sub l_pop_front(ByRef head As SLel Ptr) Dim p As SLel Ptr p = head If p Then head = p->next Delete p End If End Sub ' Procedura usuwa ostatni element '-------------------------------- Sub l_pop_back(ByRef head As SLel Ptr) Dim p As SLel Ptr p = head If p Then If p->next Then While p->next->next p = p->next Wend Delete p->next p->next = 0 Else Delete p head = 0 End If End If End Sub ' Procedura usuwa wybrany element '-------------------------------- Sub l_remove(ByRef head As SLel Ptr, _ e As SLel Ptr) Dim p As SLel Ptr If head = e Then l_pop_front(head) Else p = head While p->next <> e p = p->next Wend p->next = e->next Delete e End If End Sub '--------------- ' Program główny '--------------- Dim L As SLel Ptr Dim e As SLel Ptr Dim i As Integer L = 0 For i = Asc("A") To Asc("G") l_push_back(L, Chr(i)) Next l_print(L) ' Przechodzimy do elementu o wartości D e = L For i = 1 To 3 e = e->next Next ' Przed elementem D umieszczamy + l_insert_before(L, e, "+") ' Za elementem D umieszczamy * l_insert_after(e, "*") l_print(L) ' Usuwamy element D oraz element pierwszy i ostatni l_remove(L, e) l_pop_front(L) l_pop_back(L) l_print(L) End |
Wynik: |
Number of elements : 7 Element #1 data = A Element #2 data = B Element #3 data = C Element #4 data = D Element #5 data = E Element #6 data = F Element #7 data = G Number of elements : 9 Element #1 data = A Element #2 data = B Element #3 data = C Element #4 data = + Element #5 data = D Element #6 data = * Element #7 data = E Element #8 data = F Element #9 data = G Number of elements : 6 Element #1 data = B Element #2 data = C Element #3 data = + Element #4 data = * Element #5 data = E Element #6 data = F |
Python (dodatek) |
# Program testowy dla list jednokierunkowych # Data: 4.05.2024 # (C)2024 mgr Jerzy Wałaszek #------------------------------------------- # klasa elementu listy jednokierunkowej class SLel: # Konstruktor def __init__(self, data): self.next = None self.data = data # klasa listy jednokierunkowej class SLvar: # Konstruktor def __init__(self): self.head = None # destruktor def __del__(self): while self.head: self.l_pop_front() print("Lista usunięta z pamięci") # długość listy def l_len(self): c = 0 p = self.head while p: c += 1 p = p.next return c # wyświetlenie listy def l_print(self): print("Liczba elementów :", self.l_len()) i = 1 p = self.head while p: print("Element nr", i, "dane =", p.data) i += 1 p = p.next print() # wstawianie na początek def l_push_front(self, v): p = SLel(v) p.next = self.head self.head = p # wstawianie na koniec def l_push_back(self, v): e = SLel(v) p = self.head if p: while p.next: p = p.next p.next = e else: self.head = e #wstawianie przed e def l_insert_before(self, e, v): p = self.head if p is e: self.l_push_front(v) else: while p.next is not e: p = p.next p.next = SLel(v) p.next.next = e # usuwanie z przodu def l_pop_front(self): p = self.head if p: self.head = p.next # usuwanie z tyłu def l_pop_back(self): p = self.head if p: if p.next: while p.next.next: p = p.next p.next = None else: self.head = None # usuwanie e def l_remove(self, e): if self.head is e: self.l_pop_front() else: p = self.head while p.next is not e: p = p.next p.next = e.next # wstawianie za e def l_insert_after(e, v): p = e.next e.next = SLel(v) e.next.next = p #--------------- # Program główny #--------------- sl = SLvar() for i in range(ord('A'), ord('G')+1): sl.l_push_back(chr(i)) sl.l_print() # Przechodzimy do elementu D e = sl.head for i in range(ord('A'), ord('C')+1): e = e.next # Przed elementem D umieszczamy + sl.l_insert_before(e, '+') # Za elementem D umieszczamy * l_insert_after(e, '*') sl.l_print() # Usuwamy element D oraz # element pierwszy i ostatni sl.l_remove(e) sl.l_pop_front() sl.l_pop_back() sl.l_print() sl = None |
Wynik: |
Liczba elementów : 7 Element nr 1 dane = A Element nr 2 dane = B Element nr 3 dane = C Element nr 4 dane = D Element nr 5 dane = E Element nr 6 dane = F Element nr 7 dane = G Liczba elementów : 9 Element nr 1 dane = A Element nr 2 dane = B Element nr 3 dane = C Element nr 4 dane = + Element nr 5 dane = D Element nr 6 dane = * Element nr 7 dane = E Element nr 8 dane = F Element nr 9 dane = G Liczba elementów : 6 Element nr 1 dane = B Element nr 2 dane = C Element nr 3 dane = + Element nr 4 dane = * Element nr 5 dane = E Element nr 6 dane = F Lista usunięta z pamięci |
Pascal// Obiekt listy jednokierunkowej // Data: 12.02.2012 // (C)2020 mgr Jerzy Wałaszek //------------------------------ program slist_object; // Typ elementów listy //-------------------- type PSLel = ^SLel; SLel = record next : PSLel; data : char; end; // Definicja typu obiektowego SLvar //------------------------------------ SLvar = object public head : PSLel; // początek listy constructor init; destructor destroy; function l_len : cardinal; procedure l_print; procedure l_push_front(v : char); procedure l_push_back(v : char); procedure l_insert_before(e : PSLel; v : char); procedure l_insert_after(e : PSLel; v : char); procedure l_pop_front; procedure l_pop_back; procedure l_remove(e : PSLel); end; //------------------------ // Metody obiektu SLvar //------------------------ // Konstruktor-inicjuje pole head //--------------------------------- constructor SLvar.init; begin head := nil; end; // Destruktor-usuwa listę z pamięci //----------------------------------- destructor SLvar.destroy; begin while head <> nil do l_pop_front; end; // Funkcja oblicza liczbę elementów listy //--------------------------------------- function SLvar.l_len : cardinal; var c : cardinal; p : PSLel; begin c := 0; p := head; while p <> nil do begin inc(c); p := p^.next; end; l_len := c; end; // Procedura wyświetla zawartość // elementów listy //------------------------------ procedure SLvar.l_print; var i : integer; p : PSLel; begin writeln('Number of elements : ', l_len); p := head; i := 1; while p <> nil do begin writeln('Element #', i, ' data = ', p^.data); inc(i); p := p^.next; end; writeln; end; // Procedura dołączania na początek listy //--------------------------------------- procedure SLvar.l_push_front(v : char); var p : PSLel; begin new(p); p^.next := head; p^.data := v; head := p; end; // Procedura dołączania na koniec listy //------------------------------------- procedure SLvar.l_push_back(v : char); var p, e : PSLel; begin new(e); e^.next := nil; e^.data := v; p := head; if p = nil then head := e else begin while p^.next <> nil do p := p^.next; p^.next := e; end; end; // Procedura dołączania przed elementem e //--------------------------------------- procedure SLvar.l_insert_before(e : PSLel; v : char); var p : PSLel; begin p := head; if p = e then l_push_front(v) else begin while p^.next <> e do p := p^.next; new(p^.next); p^.next^.next := e; p^.next^.data := v; end; end; // Procedura dołączania za elementem e //------------------------------------ procedure SLvar.l_insert_after(e : PSLel; v : char); var p : PSLel; begin new(p); p^.next := e^.next; p^.data := v; e^.next := p; end; // Procedura usuwa pierwszy element //--------------------------------- procedure SLvar.l_pop_front; var p : PSLel; begin p := head; if p <> nil then begin head := p^.next; dispose(p); end; end; // Procedura usuwa ostatni element //--------------------------------- procedure SLvar.l_pop_back; var p : PSLel; begin p := head; if p <> nil then begin if p^.next <> nil then begin while p^.next^.next <> nil do p := p^.next; dispose(p^.next); p^.next := nil; end else begin dispose(p); head := nil; end end; end; // Procedura usuwa wybrany element //-------------------------------- procedure SLvar.l_remove (e : PSLel); var p : PSLel; begin if head = e then l_pop_front else begin p := head; while p^.next <> e do p := p^.next; p^.next := e^.next; dispose(e); end; end; //--------------- // Program główny //--------------- var L : SLvar; // lista jednokierunkowa e : PSLel; // wskazywanie elementów listy i : char; begin L.init; // inicjujemy obiekt for i := 'A' to 'G' do L.l_push_back(i); L.l_print; // Przechodzimy do elementu o wartości D e := L.head; for i := 'A' to 'C' do e := e^.next; // Przed elementem D umieszczamy + L.l_insert_before(e, '+'); // Za elementem D umieszczamy * L.l_insert_after(e, '*'); L.l_print; // Usuwamy element D oraz // element pierwszy i ostatni L.l_remove(e); L.l_pop_front; L.l_pop_back; L.l_print; L.destroy; end. |
// Obiekt listy jednokierunkowej // Data: 12.02.2012 // (C)2020 mgr Jerzy Wałaszek //------------------------------ #include <iostream> using namespace std; // Typ elementów listy //-------------------- struct SLel { SLel * next; char data; }; // Definicja typu obiektowego SLvar //------------------------------------ class SLvar { public: SLel * head; SLvar(); // konstruktor ~SLvar(); // destruktor unsigned l_len(); void l_print(); void l_push_front(char v); void l_push_back(char v); void l_insert_before(SLel * e, char v); void l_insert_after(SLel * e, char v); void l_pop_front(); void l_pop_back(); void l_remove(SLel * e); }; // Konstruktor listy //------------------ SLvar::SLvar() { head = NULL; } // Destruktor listy //----------------- SLvar::~SLvar() { while(head) l_pop_front(); } // Funkcja oblicza liczbę // elementów listy //----------------------- unsigned SLvar::l_len() { unsigned c = 0; SLel * p = head; while(p) { c++; p = p->next; } return c; } // Procedura wyświetla zawartość // elementów listy //------------------------------ void SLvar::l_print() { unsigned i; SLel * p = head; cout << "Number of elements : " << l_len() << endl; for(i = 1; p; p = p->next) cout << "Element #" << i++ << " data = " << p->data << endl; cout << endl; } // Procedura dołączania na początek listy //--------------------------------------- void SLvar::l_push_front(char v) { SLel * p; p = new SLel; p->next = head; p->data = v; head = p; } // Procedura dołączania na koniec listy //--------------------------------------- void SLvar::l_push_back(char v) { SLel * p, * e; e = new SLel; // tworzymy nowy element e->next = NULL; // inicjujemy element e->data = v; p = head; if(p) { while(p->next) p = p->next; p->next = e; } else head = e; } // Procedura dołączania przed elementem e //--------------------------------------- void SLvar::l_insert_before(SLel * e, char v) { SLel * p = head; if(p == e) l_push_front(v); else { while(p->next != e) p = p->next; p->next = new SLel; p->next->next = e; p->next->data = v; } } // Procedura dołączania za elementem e //------------------------------------ void SLvar::l_insert_after(SLel * e, char v) { SLel * p = new SLel; p->next = e->next; p->data = v; e->next = p; } // Procedura usuwa pierwszy element //--------------------------------- void SLvar::l_pop_front() { SLel * p = head; // początek if(p) { head = p->next; // nowy początek delete p; // usuń element } } // Procedura usuwa ostatni element //--------------------------------- void SLvar::l_pop_back() { SLel * p = head; // początek if(p) { if(p->next) { while(p->next->next) p = p->next; delete p->next; p->next = NULL; } else { delete p; head = NULL; } } } // Procedura usuwa wybrany element //-------------------------------- void SLvar::l_remove(SLel * e) { SLel * p; if(head == e) l_pop_front(); else { p = head; while(p->next != e) p = p->next; p->next = e->next; delete e; } } //--------------- // Program główny //--------------- int main() { SLvar L; // zawiera adres początku listy SLel * e; // do wskazywania elementów listy char i; for(i = 'A'; i <= 'G'; i++) L.l_push_back(i); L.l_print(); // Przechodzimy do elementu o wartości D e = L.head; for(i = 'A'; i <= 'C'; i++) e = e->next; // Przed elementem D umieszczamy + L.l_insert_before(e, '+'); // Za elementem D umieszczamy * L.l_insert_after(e, '*'); L.l_print(); // Usuwamy element D oraz element pierwszy i ostatni L.l_remove(e); L.l_pop_front(); L.l_pop_back(); L.l_print(); return 0; } |
Basic' Program testowy dla list jednokierunkowych ' Data: 11.02.2012 ' (C)2020 mgr Jerzy Wałaszek '------------------------------------------- ' Typ elementów listy '-------------------- Type SLel next As SLel Ptr data As String * 1 End Type ' Typ obiektowy SLvar '----------------------- Type SLvar head As SLel Ptr Declare Constructor() Declare Destructor() Declare Sub l_print() Declare Function l_len() As UInteger Declare Sub l_push_front(v As String) Declare Sub l_push_back(v As String) Declare Sub l_insert_before(e As SLel Ptr, _ v As String) Declare Sub l_insert_after(e As SLel Ptr, _ v As String) Declare Sub l_pop_front() Declare Sub l_pop_back() Declare Sub l_remove(e As SLel Ptr) End Type '--------------- ' Program główny '--------------- Dim L As SLvar ' adres początku listy Dim e As SLel Ptr ' elementy listy Dim i As Integer For i = Asc ("A") To Asc ("G") L.l_push_back(Chr(i)) Next L.l_print() ' Przechodzimy do elementu o wartości D e = L.head For i = 1 To 3 e = e->next Next ' Przed elementem D umieszczamy + L.l_insert_before(e, "+") ' Za elementem D umieszczamy * L.l_insert_after(e, "*") L.l_print() ' Usuwamy element D oraz ' elementy pierwszy i ostatni L.l_remove(e) L.l_pop_front() L.l_pop_back() L.l_print() End ' Konstruktor listy '------------------- Constructor SLvar() head = 0 End Constructor ' Destruktor listy '----------------- Destructor SLvar() While head l_pop_front() Wend End Destructor ' Procedura wyświetla zawartość ' elementów listy '------------------------------ Sub SLvar.l_print() Dim i As UInteger Dim p As SLel Ptr = head Print "Number of elements : ";l_len() i = 1 While p Print "Element #";i;" data = ";p->data i += 1 p = p->next Wend Print End Sub ' Funkcja oblicza liczbę ' elementów listy '----------------------- Function SLvar.l_len As UInteger Dim c As UInteger Dim p As SLel Ptr = head c = 0 While p c += 1 p = p->next Wend l_len = c End Function ' Procedura dołączania ' na początek listy '--------------------- Sub SLvar.l_push_front(v As String) Dim p As SLel Ptr p = new SLel p->next = head p->data = v head = p End Sub ' Procedura dołączania ' na koniec listy '--------------------- Sub SLvar.l_push_back(v As String) Dim As SLel Ptr p, e e = New SLel e->next = 0 e->data = v p = head If p = 0 Then head = e Else While p->next p = p->next Wend p->next = e End If End Sub ' Procedura dołączania ' przed elementem e '--------------------- Sub SLvar.l_insert_before(e As SLel Ptr, _ v As String) Dim p As SLel Ptr p = head If p = e Then l_push_front(v) Else While p->next <> e p = p->next Wend p->next = New SLel p->next->next = e p->next->data = v End If End Sub ' Procedura dołączania ' za elementem e '--------------------- Sub SLvar.l_insert_after(e As SLel Ptr, _ v As String) Dim p As SLel Ptr p = new SLel p->next = e->next p->data = v e->next = p End Sub ' Procedura usuwa pierwszy element '--------------------------------- Sub SLvar.l_pop_front() Dim p As SLel Ptr p = head ' początek If p Then head = p->next ' nowy początek Delete p ' usuń element End If End Sub ' Procedura usuwa ostatni element '-------------------------------- Sub SLvar.l_pop_back() Dim p As SLel Ptr p = head If p Then If p->next Then While p->next->next p = p->next Wend Delete p->next p->next = 0 Else Delete p head = 0 End If End If End Sub ' Procedura usuwa wybrany element '-------------------------------- Sub SLvar.l_remove(e As SLel Ptr) Dim p As SLel Ptr If head = e Then l_pop_front() Else p = head While p->next <> e p = p->next Wend p->next = e->next Delete e End If End Sub |
Zespół Przedmiotowy Chemii-Fizyki-Informatyki w I Liceum Ogólnokształcącym im. Kazimierza Brodzińskiego w Tarnowie ul. Piłsudskiego 4 ©2024 mgr Jerzy Wałaszek |
Materiały tylko do użytku dydaktycznego. Ich kopiowanie i powielanie jest dozwolone pod warunkiem podania źródła oraz niepobierania za to pieniędzy.
Pytania proszę przesyłać na adres email:
Serwis wykorzystuje pliki cookies. Jeśli nie chcesz ich otrzymywać, zablokuj je w swojej przeglądarce.
Informacje dodatkowe.