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 |
©2019 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.
Dla list dwukierunkowych nie ma zwykle potrzeby odwracania kolejności elementów, ponieważ listę można czytać wspak, od ostatniego do pierwszego elementu.
head | – | adres pierwszego elementu listy |
lista, na której każda wartość danych jest reprezentowana tylko jeden raz
p | – | wskaźniki elementu listy |
pc | – | wskaźnik elementu bieżącego |
K01: | Jeśli head = nil, to zakończ | jeśli lista jest pusta, kończymy. |
K02: | pc ← head | zapamiętujemy adres pierwszego elementu |
K03: | Dopóki (pc→next) ≠ nil, wykonuj K04...K07 | dopóki istnieje następnik 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 : PslistEl); var p, pc : PslistEl; 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; |
C++void l_reverse(slistEl * & head) { slistEl * 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 slistEl Ptr) Dim As slistEl 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 |
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
|
Pascal// Odwracanie zawartości listy jednokierunkowej // Data: 20.02.2012 // (C)2019 mgr Jerzy Wałaszek //--------------------------------------------- program slist_reverse; // Typ elementów listy //-------------------- type PslistEl = ^slistEl; slistEl = record next : PslistEl; data : char; end; // Definicja typu obiektowego slist //--------------------------------- slist = object public head : PslistEl; // początek listy constructor init; destructor destroy; procedure printl; procedure push_front(v : char); procedure pop_front; procedure reverse; end; //--------------------- // Metody obiektu slist //--------------------- // Konstruktor - inicjuje pole head //--------------------------------- constructor slist.init; begin head := nil; end; // Destruktor - usuwa listę z pamięci //----------------------------------- destructor slist.destroy; begin while head <> nil do pop_front; end; // Procedura wyświetla zawartość elementów listy //---------------------------------------------- procedure slist.printl; var p : PslistEl; 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 slist.push_front(v : char); var p : PslistEl; begin new(p); p^.next := head; p^.data := v; head := p; end; // Procedura usuwa pierwszy element //--------------------------------- procedure slist.pop_front; var p : PslistEl; begin p := head; if p <> nil then begin head := p^.next; dispose(p); end; end; // Odwraca kolejność elementów listy //---------------------------------- procedure slist.reverse(); var p, pc : PslistEl; 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 : slist; // obiekt listy jednokierunkowej i : integer; begin L.init; // inicjujemy obiekt for i := 25 downto 0 do L.push_front(char(65 + i)); L.printl; L.reverse; L.printl; L.destroy; end. |
C++// Odwracanie zawartości listy jednokierunkowej // Data: 20.02.2012 // (C)2019 mgr Jerzy Wałaszek //--------------------------------------------- #include <iostream> using namespace std; // Typ elementów listy //-------------------- struct slistEl { slistEl * next; char data; }; // Definicja typu obiektowego slist //--------------------------------- class slist { public: slistEl * head; slist(); // konstruktor ~slist(); // destruktor void printl(); void push_front(char v); void pop_front(); void reverse(); }; // Konstruktor listy //------------------ slist::slist() { head = NULL; } // Destruktor listy //----------------- slist::~slist() { while(head) pop_front(); } // Procedura wyświetla zawartość elementów listy //---------------------------------------------- void slist::printl() { unsigned i; slistEl * p = head; for(i = 1; p; p = p->next) cout << p->data; cout << endl; } // Procedura dołączania na początek listy //--------------------------------------- void slist::push_front(char v) { slistEl * p; p = new slistEl; p->next = head; p->data = v; head = p; } // Procedura usuwa pierwszy element //--------------------------------- void slist::pop_front() { slistEl * 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 slist::reverse() { slistEl * 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() { slist L; int i; for(i = 25; i >= 0; i--) L.push_front(65 + i); L.printl(); L.reverse(); L.printl(); return 0; } |
Basic' Odwracanie zawartości listy jednokierunkowej ' Data: 20.02.2012 ' (C)2019 mgr Jerzy Wałaszek '--------------------------------------------- ' Typ elementów listy '-------------------- Type slistEl next As slistEl Ptr data As String * 1 End Type ' Typ obiektowy slist '------------------------------ Type slist head As slistEl Ptr Declare Constructor() Declare Destructor() Declare Sub printl() Declare Sub push_front(v As String) Declare Sub pop_front() Declare Sub reverse() End Type '--------------- ' Program główny '--------------- Dim L As slist Dim i As Integer For i = 25 To 0 Step -1 L.push_front(Chr(65 + i)) Next L.printl() L.reverse() L.printl() End ' Konstruktor listy '------------------- Constructor slist() head = 0 End Constructor ' Destruktor listy '----------------- Destructor slist() While head pop_front() Wend End Destructor ' Procedura wyświetla zawartość elementów listy '---------------------------------------------- Sub slist.printl() Dim p As slistEl Ptr = head While p Print p->Data; p = p->next Wend Print End Sub ' Procedura dołączania na początek listy '--------------------------------------- Sub slist.push_front(v As String) Dim p As slistEl Ptr p = new slistEl p->next = head p->data = v head = p End Sub ' Procedura usuwa pierwszy element '--------------------------------- Sub slist.pop_front() Dim p As slistEl 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 slist.reverse() Dim As slistEl 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 |
Wynik: |
ABCDEFGHIJKLMNOPQRSTUVWXYZ ZYXWVUTSRQPONMLKJIHGFEDCBA |
![]() |
Zespół Przedmiotowy |
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: i-lo@eduinf.waw.pl
Serwis wykorzystuje pliki cookies. Jeśli nie chcesz ich otrzymywać, zablokuj je w swojej przeglądarce.
Informacje dodatkowe.