Algorytmy i Struktury Danych - Odwracanie listy jednokierunkowej

Problem

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.

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

Wejście

head

–

adres pierwszego elementu listy

Wyjście:

lista, na której każda wartość danych jest reprezentowana tylko jeden raz

Elementy pomocnicze:

p	–	wskaźniki elementu listy
pc	–	wskaźnik elementu bieżącego

Lista kroków:

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

Lazarus

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;

Code::Blocks

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

Free 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

Program

Ważne:

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.

Lazarus

// Odwracanie zawartości listy jednokierunkowej
// Data: 20.02.2012
// (C)2012 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.

Code::Blocks

// Odwracanie zawartości listy jednokierunkowej
// Data: 20.02.2012
// (C)2012 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;
}

Free Basic

' Odwracanie zawartości listy jednokierunkowej
' Data: 20.02.2012
' (C)2012 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

Wyniki

ABCDEFGHIJKLMNOPQRSTUVWXYZ
ZYXWVUTSRQPONMLKJIHGFEDCBA