Odwracanie listy jednokierunkowej


Tematy pokrewne
Listy
Podstawowe pojęcia dotyczące list
Reprezentacja list w pamięci komputera
Operacje na listach jednokierunkowych
Operacje na listach dwukierunkowych
Operacje na listach cyklicznych jednokierunkowych
Liniowe przeszukiwanie listy
Przeszukiwanie liniowe z wartownikiem listy dwukierunkowej
Wyszukiwanie największego/najmniejszego elementu listy
Zliczanie elementów listy
Usuwanie z listy duplikatów
Odwracanie listy jednokierunkowej
Podział listy jednokierunkowej na dwie listy
Scalanie dwóch list posortowanych
Sortowanie listy jednokierunkowej przez scalanie
Sortowanie przez wstawianie z wykorzystaniem listy jednokierunkowej
Sortowanie szybkie listy dwukierunkowej
Samoorganizujące się listy
Haszowanie z wykorzystaniem list jednokierunkowych
Zbiory rozłączne – implementacja listowa

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: pchead ; zapamiętujemy adres pierwszego elementu
K03: Dopóki (pcnext) ≠ nil, wykonuj K04...K07 ; dopóki istnieje następnik 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  

 

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

 

 


   I Liceum Ogólnokształcące   
im. Kazimierza Brodzińskiego
w Tarnowie

©2019 mgr Jerzy Wałaszek

Dokument ten rozpowszechniany jest zgodnie z zasadami licencji
GNU Free Documentation License.

Pytania proszę przesyłać na adres email: i-lo@eduinf.waw.pl

W artykułach serwisu są używane cookies. Jeśli nie chcesz ich otrzymywać,
zablokuj je w swojej przeglądarce.
Informacje dodatkowe