Algorytmy i Struktury Danych - Odwracanie listy 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.

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:

p : 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: 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

Pascal

procedure 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;

C++

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;
    }
  }
}

Basic

Sub 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

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

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

do podrozdziału do strony

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.

Odwracanie listy jednokierunkowej