Serwis Edukacyjny
w I-LO w Tarnowie
obrazek

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
I LO w Tarnowie

Odwracanie listy jednokierunkowej

SPIS TREŚCI
Tematy pomocnicze

Problem

Należy odwrócić kolejność elementów na liście jednokierunkowej.

Rozwiązanie

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.

Algorytm odwracania kolejności elementów na liście jednokierunkowej

Wejście:

head : adres pierwszego elementu listy.

Wyjście:

Lista o odwróconej kolejności elementów.

Elementy pomocnicze:

: wskaźniki elementu listy.
pc : wskaźnik elementu bieżącego.

Lista kroków:

K01: Jeśli head = nil, ; jeśli lista jest pusta, kończymy.
     to zakończ
K02: pchead ; zapamiętujemy adres pierwszego elementu
K03: Dopóki (pcnext) ≠ nil, ; dopóki istnieje następnik
     wykonuj kroki K04…K07 ; zapamiętanego elementu
K04:   p ← (pcnext) ; zapamiętujemy adres następnika
K05:   (pcnext) ← (pnext) ; wyjmujemy następnik z listy
K06:   (pnext) ← head ; i wstawiamy go na jej początek
K07:   headp
K08: Zakończ

Pascal
procedure 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;
    }
  }
}
Basic
Sub 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
Python (dodatek)
# klasa elementu listy
#---------------------
class slistEl:
    def __init__(self,data):
        self.next = None
        self.data = data

# klasa listy jednokierunkowej
#-----------------------------
class slistVar:

    # 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

Przykładowe programy

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
  PslistEl = ^slistEl;

  slistEl =  record
    next  : PslistEl;
    data  : char;
  end;

// Definicja typu obiektowego slist
//---------------------------------

  slistVar = object
    public
      head : PslistEl;  // 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 slistVar.init;
begin
  head := nil;
end;

// Destruktor - usuwa listę z pamięci
//-----------------------------------
destructor slistVar.destroy;
begin
  while head <> nil do l_pop_front;
end;

// Procedura wyświetla zawartość elementów listy
//----------------------------------------------
procedure slistVar.l_print;
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 slistVar.l_push_front(v : char);
var
  p : PslistEl;
begin
  new(p);
  p^.next := head;
  p^.data := v;
  head    := p;
end;

// Procedura usuwa pierwszy element
//---------------------------------
procedure slistVar.l_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 slistVar.l_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 : slistVar; // 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.
C++
// 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 slistEl
{
  slistEl * next;
  char data;
};

// Definicja typu obiektowego slist
//---------------------------------

class slistVar
{
  public:
    slistEl * head;

    slistVar();  // konstruktor
    ~slistVar(); // destruktor
    void l_print();
    void l_push_front(char v);
    void l_pop_front();
    void l_reverse();
};

// Konstruktor listy
//------------------
slistVar::slistVar()
{
  head = NULL;
}

// Destruktor listy
//-----------------
slistVar::~slistVar()
{
  while(head) l_pop_front();
}


// Procedura wyświetla zawartość listy
//------------------------------------
void slistVar::l_print()
{
  slistEl * p;

  for(p = head; p; p = p->next)
    cout << p->data;
  cout << endl;
}

// Procedura dołączania na początek listy
//---------------------------------------
void slistVar::l_push_front(char v)
{
  slistEl * p;

  p = new slistEl;
  p->next = head;
  p->data = v;
  head = p;
}

// Procedura usuwa pierwszy element
//---------------------------------
void slistVar::l_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 slistVar::l_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()
{
  slistVar 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 slistEl
  next As slistEl Ptr
  data As String * 1
End Type

' Typ obiektowy slist
'------------------------------
Type slistVar
  head As slistEl 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 slistVar
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()
sleep
End

' Konstruktor listy
'-------------------
Constructor slistVar()
  head = 0
End Constructor

' Destruktor listy
'-----------------
Destructor slistVar()
  While head
    l_pop_front()
  Wend
End Destructor

' Procedura wyświetla zawartość elementów listy
'----------------------------------------------
Sub slistVar.l_print()
 
  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 slistVar.l_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 slistVar.l_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 slistVar.l_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
Python (dodatek)
# Odwracanie zawartości
# listy jednokierunkowej
# Data: 21.05.2024
# (C)2024 mgr Jerzy Wałaszek
#-------------------------------------

# klasa elementu listy
#---------------------
class slistEl:
    def __init__(self,data):
        self.next = None
        self.data = data

# klasa listy jednokierunkowej
#-----------------------------
class slistVar:

    # 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 = slistEl(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
            del p

    # 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
#---------------

L = slistVar() # obiekt listy

for i in reversed(range(26)):
    L.l_push_front(chr(65+i))
L.l_print()
L.l_reverse()
L.l_print()
Wynik:
ABCDEFGHIJKLMNOPQRSTUVWXYZ
ZYXWVUTSRQPONMLKJIHGFEDCBA

Na początek:  podrozdziału   strony 

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: i-lo@eduinf.waw.pl

Serwis wykorzystuje pliki cookies. Jeśli nie chcesz ich otrzymywać, zablokuj je w swojej przeglądarce.

Informacje dodatkowe.