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 |
ProblemNależy odwrócić kolejność elementów na liście jednokierunkowej. |
Zadanie wykonujemy następująco. Jeśli lista jest pusta, kończymy. W przeciwnym razie zapamiętujemy adres pierwszego elementu listy. Następnie dopóki istnieje następnik zapamiętanego elementu, wyjmujemy go z listy i dodajemy na jej początek. W efekcie elementy na liście zmienią swoją kolejność, a element pierwszy stanie się ostatnim. Algorytm posiada liniową klasę złożoności czasowej O(n).
Dla list dwukierunkowych nie ma zwykle potrzeby odwracania kolejności elementów, ponieważ listę można czytać wspak, od ostatniego do pierwszego elementu.
K01: Jeśli head = nil, ; jeśli lista jest pusta, kończymy. to zakończ K02: pc ← head ; zapamiętujemy adres pierwszego elementu K03: Dopóki pc→next ≠ nil, ; dopóki istnieje następnik wykonuj kroki K04…K07 ; zapamiętanego elementu K04: p ← pc→next ; zapamiętujemy adres następnika K05: pc→next ← p→next ; wyjmujemy następnik z listy K06: p→next ← head ; i wstawiamy go na jej początek K07: head ← p K08: Zakończ
Pascalprocedure l_reverse(var head : PSLel); var p, pc : PSLel; begin if head <> nil then begin pc := head; while pc^.next <> nil do begin p := pc^.next; pc^.next := p^.next; p^.next := head; head := p; end; end; end; |
void l_reverse(SLel * & head) { SLel * p, * pc; if(head) { pc = head; while(pc->next) { p = pc->next; pc->next = p->next; p->next = head; head = p; } } } |
BasicSub l_reverse (ByRef head As SLel Ptr) Dim As SLel Ptr p, pc If head Then pc = head While pc->next p = pc->next pc->next = p->next p->next = head head = p Wend End If End Sub |
Python (dodatek) |
# 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 # Odwraca listę def l_reverse(self): if self.head: pc = self.head while pc.next: p = pc.next pc.next = p.next p.next = self.head self.head = p |
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. |
Program tworzy listę zawierającą kolejne znaki alfabetu od A do Z, a następnie odwraca ją wspak. Program wykorzystuje obiekt listy jednokierunkowej. |
Pascal// Odwracanie zawartości listy jednokierunkowej // Data: 20.02.2012 // (C)2020 mgr Jerzy Wałaszek //--------------------------------------------- program slist_reverse; // Typ elementów listy //-------------------- type PSLel = ^SLel; SLel = record next : PSLel; data : char; end; // Definicja typu obiektowego slist //--------------------------------- SLvar = object public head : PSLel; // początek listy constructor init; destructor destroy; procedure l_print; procedure l_push_front(v : char); procedure l_pop_front; procedure l_reverse; end; //--------------------- // Metody obiektu slist //--------------------- // 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; // Procedura wyświetla zawartość elementów listy //---------------------------------------------- procedure SLvar.l_print; var p : PSLel; begin p := head; while p <> nil do begin write(p^.data); 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 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; // Odwraca kolejność elementów listy //---------------------------------- procedure SLvar.l_reverse(); var p, pc : PSLel; begin if head <> nil then begin pc := head; while pc^.next <> nil do begin p := pc^.next; pc^.next := p^.next; p^.next := head; head := p; end; end; end; //--------------- // Program główny //--------------- var L : SLvar; // obiekt listy jednokierunkowej i : integer; begin L.init; // inicjujemy obiekt for i := 25 downto 0 do L.l_push_front(char(65+i)); L.l_print; L.l_reverse; L.l_print; L.destroy; end. |
// Odwracanie zawartości listy jednokierunkowej // Data: 20.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 slist //--------------------------------- class SLvar { public: SLel * head; SLvar(); // konstruktor ~SLvar(); // destruktor void l_print(); void l_push_front(char v); void l_pop_front(); void l_reverse(); }; // Konstruktor listy //------------------ SLvar::SLvar() { head = NULL; } // Destruktor listy //----------------- SLvar::~SLvar() { while(head) l_pop_front(); } // Procedura wyświetla zawartość listy //------------------------------------ void SLvar::l_print() { SLel * p; for(p = head; p; p = p->next) cout << p->data; 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 usuwa pierwszy element //--------------------------------- void SLvar::l_pop_front() { SLel * p = head; // zapamiętujemy początek if(p) { head = p->next; // nowy początek delete p; // usuń element z pamięci } } // Odwraca elementy na liście //--------------------------- void SLvar::l_reverse() { SLel * p, * pc; if(head) { pc = head; while(pc->next) { p = pc->next; pc->next = p->next; p->next = head; head = p; } } } //--------------- // Program główny //--------------- int main() { SLvar L; int i; for(i = 25; i >= 0; i--) L.l_push_front(65+i); L.l_print(); L.l_reverse(); L.l_print(); return 0; } |
Basic' Odwracanie zawartości listy jednokierunkowej ' Data: 20.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 slist '------------------------------ Type SLvar head As SLel Ptr Declare Constructor() Declare Destructor() Declare Sub l_print() Declare Sub l_push_front(v As String) Declare Sub l_pop_front() Declare Sub l_reverse() End Type '--------------- ' Program główny '--------------- Dim L As SLvar Dim i As Integer For i = 25 To 0 Step -1 L.l_push_front(Chr(65+i)) Next L.l_print() L.l_reverse() 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 p As SLel Ptr = head While p Print p->Data; p = p->next Wend Print End Sub ' 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 usuwa pierwszy element '--------------------------------- Sub SLvar.l_pop_front() 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 ' Odwraca kolejność elementów listy '---------------------------------- Sub SLvar.l_reverse() Dim As SLel Ptr p, pc If head Then pc = head While pc->next p = pc->next pc->next = p->next p->next = head head = p Wend End If End Sub |
Python (dodatek) |
# Odwracanie zawartości # listy jednokierunkowej # Data: 21.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 # Destruktor def __del__(self): while self.head: self.l_pop_front() # Wyświetla zawartość listy def l_print(self): p = self.head while p: print(p.data, end="") p = p.next print() # Dodaje nowy element na początek def l_push_front(self, v): p = SLel(v) p.next = self.head self.head = p # Usuwa element z początku def l_pop_front(self): p = self.head if p: self.head = p.next p = None # Odwraca elementy na liście def l_reverse(self): if self.head: pc = self.head while pc.next: p = pc.next pc.next = p.next p.next = self.head self.head = p # --------------- # Program główny # --------------- sl = SLvar() # obiekt listy for i in reversed(range(26)): sl.l_push_front(chr(65 + i)) sl.l_print() sl.l_reverse() sl.l_print() |
Wynik: |
ABCDEFGHIJKLMNOPQRSTUVWXYZ ZYXWVUTSRQPONMLKJIHGFEDCBA |
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.