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

©2019 mgr Jerzy Wałaszek
I LO w Tarnowie

Samoorganizujące się listy

SPIS TREŚCI
Tematy pomocnicze
Podrozdziały

Problem

Należy zaprojektować listę, w której dostęp do elementów wyszukiwanych najczęściej jest najkrótszy.

Tego typu lista nosi nazwę listy samoorganizującej się (ang. self organizing list). Samoorganizujące się listy posiadają wiele praktycznych zastosowań. Ich zaletą jest fakt, że czas dostępu do elementów często używanych jest niższy niż dla pozostałych elementów. Dzięki takie cesze listy samoorganizujące się mogą być bardziej efektywne dla niektórych algorytmów, np. dla baz danych. Przykładem jest lista odwiedzanych stron w przeglądarce. Gdy ją rozwiniemy, to na samym początku znajdą się najczęściej odwiedzane strony. W ten sposób szybko możemy przejść do ulubionej strony WWW. Podobnie działa lista skrótów do ostatnio używanych programów w menu Start w systemie Windows – na samej górze listy system umieszcza skróty do najczęściej uruchamianych aplikacji.

Z badań wynika, że 80% odczytów z listy dotyczy jedynie 20% jej elementów. Pozostałe są wykorzystywane rzadko. Istnieje kilka strategii rozwiązania tego problemu. Polegają one na takim uporządkowaniu listy, aby elementy wyszukiwane najczęściej znalazły się na jej początku. Dzięki temu algorytm przeszukujący listę natrafi na nie szybciej.

Metoda przesuwania na początek listy (ang. move-to-front method)

W metodzie tej każdy znaleziony element jest umieszczany na początku listy. Można ją w prosty sposób zaimplementować na listach jedno i dwukierunkowych. Nie wymaga dodatkowej pamięci. Szybko przebudowuje listę w miarę wyszukiwania w niej elementów, jednakże niektóre elementy mogą zostać ocenione zbyt wysoko przez tę metodę, tzn. element rzadko wykorzystywany może być przeniesiony do początku listy.

Algorytm wyszukiwania z przesuwaniem na początek listy

Wejście:

L  –  zmienna obsługująca listę
v  – poszukiwana wartość

Wyjście:

adres znalezionego elementu lub nil, jeśli elementu nie ma na liście. Znaleziony element jest umieszczany na początku listy.

Zmienne pomocnicze:

p  –  wskaźnik elementów listy

Lista kroków:

K01: p L.head rozpoczynamy wyszukiwanie od pierwszego elementu listy
K02: Jeśli p = nil, to idź do K09 jeśli koniec listy, to kończymy
K03: Jeśli (pdata) ≠ v, to idź do K07 sprawdzamy, czy natrafiliśmy na poszukiwany element
K04: Odłącz element p od listy jeśli tak, to wyłączamy go z listy
K05: Wstaw element p na początek listy i umieszczamy go na początku listy
K06: Idź do K09 wychodzimy z pętli
K07: p ← (pnext) przechodzimy do następnego elementu na liście
K08: Idź do K02 i kontynuujemy pętlę
K09: Zakończ z wynikiem 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 uporządkowaną listę dwukierunkową 10 liczb całkowitych od 0 do 9. Następnie dokonuje 20 wyszukiwań liczb losowych od 0 do 9. Po każdym wyszukaniu prezentuje zawartość listy – element wyszukiwany zawsze znajduje się na jej początku. W programie wykorzystujemy zmodyfikowany obiekt listy dwukierunkowej.
Pascal
// Samoorganizujące się listy
// Przesuwanie na początek listy
// Data: 04.08.2012
// (C)2019 mgr Jerzy Wałaszek
//------------------------------

program move_to_front;

// Typ elementów listy
//--------------------
type
  PdlistEl = ^dlistEl;

  dlistEl =  record
    next  : PdlistEl;
    prev  : PdlistEl;
    data  : integer;
  end;

// Definicja typu obiektowego dlist
//---------------------------------

  dlist = object
    public

      head : PdlistEl;  // początek listy
      tail : PdlistEl;  // koniec listy

      constructor init;
      destructor  destroy;
      procedure   printl;
      procedure   push_front(v : integer);
      procedure   pop_front;
      function    find(v : integer) : PdlistEl;
  end;

//---------------------
// Metody obiektu dlist
//---------------------

// Konstruktor - inicjuje pole head
//---------------------------------
constructor dlist.init;
begin
  head := nil;
  tail := nil;
end;

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


// Procedura wyświetla zawartość elementów listy
//----------------------------------------------
procedure dlist.printl;
var
  p : PdlistEl;
begin
  p := head;
  while p <> nil do
  begin
    if p = head then
      write('(', p^.data, ')')
    else
      write(' ', p^.data, ' ');
    p := p^.next;
  end;
  writeln;
end;

// Procedura dołączania na początek listy
//---------------------------------------
procedure dlist.push_front(v : integer);
var
  p : PdlistEl;
begin
  new(p);   // tworzymy nowy element
  p^.data := v;
  p^.prev := nil;
  p^.next := head;
  head  := p;
  if p^.next <> nil then p^.next^.prev := p
  else tail := p;
end;


// Procedura usuwa pierwszy element
//---------------------------------
procedure dlist.pop_front;
var
  p : PdlistEl;
begin
  p := head;
  if p <> nil then
  begin
    head := p^.next;
    if head = nil then tail := nil
    else head^.prev := nil;
    dispose(p);
  end;
end;

// Funkcja wyszukuje element, a jeśli go znajdzie, 
// to umieszcza go na początku listy. Zwraca
// adres znalezionego elementu lub nil
//------------------------------------------------

function dlist.find(v : integer) : PdlistEl;
var
  p : PdlistEl;
begin
  p := head;                   // rozpoczynamy od początku listy

  while p <> nil do            // w pętli przeszukujemy listę
  begin

    if p^.data = v then        // element znaleziony?
    begin
                               // odłączamy element od listy

      if p^.prev <> nil then p^.prev^.next := p^.next
      else head := p^.next;
      if p^.next <> nil then p^.next^.prev := p^.prev
      else tail := p^.prev;

                               // umieszczamy go na początku listy
      p^.next := head;
      p^.prev := nil;
      head := p;
      if p^.next <> nil then p^.next^.prev := p
      else tail := p;

      break;                   // opuszczamy pętlę

    end;

    p := p^.next;              // przechodzimy do następnego elementu
  end;                         // kontynuujemy pętlę

  find := p;                   // zwracamy wynik p
end;

//---------------
// Program główny
//---------------

var
  L   : dlist;    // obiekt listy
  i, v : integer;

begin
  randomize;                              // inicjujemy liczby pseudolosowe

  L.init;                                 // inicjujemy obiekt

  for i := 9 downto 0 do L.push_front(i); // tworzymy listę

  for i := 1 to 20 do                     // przeszukujemy listę
  begin
    v := random(10);                      // losujemy element
    write(v, ':  ');                       // wyświetlamy go
    L.find(v);                            // szukamy elementu
    L.printl;                             // wyświetlamy zawartość listy
  end;

  L.destroy;
end.
C++
// Samoorganizujące się listy
// Przesuwanie na początek listy
// Data: 04.08.2012
// (C)2019 mgr Jerzy Wałaszek
//------------------------------

#include <iostream>
#include <cstdlib>
#include <ctime>

using namespace std;

// Element listy
//--------------
struct dlistEl
{
  dlistEl * next;   // następnik
  dlistEl * prev;   // poprzednik
  int data;
};

// Definicja obiektu listy dwukierunkowej
//---------------------------------------
class dlist
{
  public:
    dlistEl * head;  // początek listy
    dlistEl * tail;  // koniec listy

    dlist();         // konstruktor
    ~dlist();        // destruktor
    void printl();
    void push_front(int v);
    void pop_front();
    dlistEl * find(int v);
};

//------------------------------------
// Metody obiektu listy dwukierunkowej
//------------------------------------

// Inicjuje pola zmiennej listy
//-----------------------------
dlist::dlist()
{
  head  = tail  = NULL;
}

// Usuwa listę z pamięci
//----------------------
dlist::~dlist()
{
  while(head) pop_front();
}

// Procedura wyświetla zawartość elementów listy
//----------------------------------------------
void dlist::printl()
{
  for(dlistEl * p = head; p; p = p->next)
    if(p == head) cout << "(" << p->data << ")";
    else          cout << " " << p->data << " ";
  cout << endl;
}

// Procedura dołączania na początek listy
//---------------------------------------
void dlist::push_front(int v)
{
  dlistEl * p = new dlistEl;   // tworzymy nowy element
  p->data = v;
  p->prev = NULL;
  p->next = head;
  head = p;
  if(p->next) p->next->prev = p; else tail = p;
}

// Procedura usuwa pierwszy element
//---------------------------------
void dlist::pop_front()
{
  if(dlistEl * p = head)
  {
    if(!(head = p->next)) tail = NULL; else head->prev = NULL;
    delete p;
  }
}

// Funkcja wyszukuje element, a jeśli go znajdzie, 
// to umieszcza go na początku listy. Zwraca
// adres znalezionego elementu lub nil
//------------------------------------------------

dlistEl * dlist::find(int v)
{
  dlistEl * p;

  for(p = head; p; p = p->next) // w pętli przeszukujemy listę

    if(p->data == v)            // element znaleziony?
    {
      // odłączamy element od listy

      if(p->prev) p->prev->next = p->next; else head = p->next;
      if(p->next) p->next->prev = p->prev; else tail = p->prev;

      // umieszczamy go na początku listy

      p->next = head;
      p->prev = NULL;
      head = p;
      if(p->next) p->next->prev = p; else tail = p;

      break;                   // opuszczamy pętlę

    }

  return p;                    // zwracamy wynik p
}

//---------------
// Program główny
//---------------

int main()
{
  dlist L;    // obiekt listy
  int i, v;

  srand(time(NULL));                       // inicjujemy liczby pseudolosowe

  for(i = 9; i >= 0; i--) L.push_front(i); // tworzymy listę

  for(i = 0; i < 20; i++)                  // przeszukujemy listę
  {
    v = rand() % 10;                       // losujemy element
    cout << v << ":  ";                    // wyświetlamy go
    L.find(v);                             // szukamy elementu
    L.printl();                            // wyświetlamy zawartość listy
  }
  return 0;
}
Basic
' Samoorganizujące się listy
' Przesuwanie na początek listy
' Data: 04.08.2012
' (C)2019 mgr Jerzy Wałaszek
'------------------------------

' Element listy
'--------------
Type dlistEl
  next As dlistEl Ptr   ' następnik
  prev As dlistEl Ptr   ' poprzednik
  data As Integer
End Type

' Definicja obiektu listy dwukierunkowej
'---------------------------------------
Type dlist

  head As dlistEl Ptr  ' początek listy
  tail As dlistEl Ptr  ' koniec listy

  Declare Constructor()
  Declare Destructor()
  Declare Sub printl()
  Declare Sub push_front(v As Integer)
  Declare Sub pop_front()
  Declare Function find(v As Integer) As dlistEl Ptr
End Type

'---------------
' Program główny
'---------------

Dim L As dlist
Dim As Integer i, v

Randomize                                  ' inicjujemy liczby pseudolosowe

For i = 9 To 0 Step -1
  L.push_front(i)                          ' tworzymy listę
Next

For i = 1 To 20                            ' przeszukujemy listę
  v = Int(Rnd()* 10)                       ' losujemy element
  Print Using "#:  ";v;                    ' wyświetlamy go
  L.find(v)                                ' szukamy elementu
  L.printl()                               ' wyświetlamy zawartość listy
Next
End

'------------------------------------
' Metody obiektu listy dwukierunkowej
'------------------------------------

' Konstruktor listy
'------------------
Constructor dlist()
  head  = 0
  tail  = 0
End Constructor

' Usuwa listę z pamięci
Destructor dlist()
  While head
  	 pop_front()
  Wend
End Destructor

' Procedura wyświetla zawartość elementów listy
'----------------------------------------------
Sub dlist.printl()

  Dim p As dlistEl Ptr
  p = head
  While p
    If p = head Then
    	Print Using "(#)";p->data;
    Else
      Print Using " # ";p->data;
    End If
    p = p->Next
  Wend
  Print
End Sub

' Procedura dołączania na początek listy
'---------------------------------------
Sub dlist.push_front(v As Integer)
  Dim p As dlistEl Ptr
  p = new dlistEl
  p->data = v
  p->prev = 0
  p->next = head
  head = p
  If p->Next Then
  	 p->next->prev = p
  Else
  	 tail = p
  End If
End Sub

' Procedura usuwa pierwszy element
'---------------------------------
Sub dlist.pop_front()
  Dim p As dlistEl Ptr
  p = head
  If p Then
  	 head = p->Next
    If head = 0 Then
    	tail = 0
    Else
    	head->prev = 0
    End If
    Delete p
  End If
End Sub

' Funkcja wyszukuje element, a jeśli go znajdzie, 
' to umieszcza go na początku listy. Zwraca
' adres znalezionego elementu lub nil
'------------------------------------------------

Function dlist.find(v As integer) As dlistEl Ptr

  Dim p As dlistEl Ptr
  p = head
  While p                          ' w pętli przeszukujemy listę

    If p->data = v Then            ' element znaleziony?
    
      ' odłączamy element od listy

      If p->prev Then
        p->prev->next = p->next
      Else
        head = p->Next
      End If
      
      If p->next Then
        p->next->prev = p->prev
      Else
        tail = p->prev
      End If

      ' umieszczamy go na początku listy

      p->next = head
      p->prev = 0
      head = p
      if p->Next Then
        p->next->prev = p
      Else
        tail = p
      End If

      Exit While               ' opuszczamy pętlę

    End If
    
    p = p->Next                ' idziemy do następnego elementu
   
  Wend

  find = p                     ' zwracamy wynik p
End function
Wynik:
4:  (4) 0  1  2  3  5  6  7  8  9
6:  (6) 4  0  1  2  3  5  7  8  9
7:  (7) 6  4  0  1  2  3  5  8  9
5:  (5) 7  6  4  0  1  2  3  8  9
0:  (0) 5  7  6  4  1  2  3  8  9
6:  (6) 0  5  7  4  1  2  3  8  9
7:  (7) 6  0  5  4  1  2  3  8  9
7:  (7) 6  0  5  4  1  2  3  8  9
2:  (2) 7  6  0  5  4  1  3  8  9
0:  (0) 2  7  6  5  4  1  3  8  9
4:  (4) 0  2  7  6  5  1  3  8  9
5:  (5) 4  0  2  7  6  1  3  8  9
5:  (5) 4  0  2  7  6  1  3  8  9
6:  (6) 5  4  0  2  7  1  3  8  9
4:  (4) 6  5  0  2  7  1  3  8  9
5:  (5) 4  6  0  2  7  1  3  8  9
0:  (0) 5  4  6  2  7  1  3  8  9
6:  (6) 0  5  4  2  7  1  3  8  9
8:  (8) 6  0  5  4  2  7  1  3  9
8:  (8) 6  0  5  4  2  7  1  3  9
Na początek:  podrozdziału   strony 

Metoda zliczania (ang. count method)

W tej metodzie każdy element listy posiada dodatkowe pole licznika. Po znalezieniu elementu jego licznik zostaje zwiększony, a następnie lista zostaje uporządkowana względem malejącej wartości liczników. W ten sposób elementy wykorzystywane najczęściej zajmują początkowe pozycje listy. Ta metoda jest lepsza od poprzedniej, ponieważ rozkład elementów lepiej odpowiada częstości ich wykorzystywania. Wadą jest zwiększone zapotrzebowanie na pamięć, ponieważ musimy z każdym elementem dodatkowo przechowywać jego licznik. Musimy również pamiętać, że liczniki posiadają górny zakres, np. 4 miliardów. Jeśli program przekroczy tę wartość, to liczniki się przewiną i element najczęściej używany trafi na koniec listy (w takim przypadku można zastosować różne strategie normalizacyjne – np. umawiamy się, że jeśli wartość licznika przekroczy, powiedzmy, 4 miliardy, to wszystkie liczniki zmniejszamy o 2 miliardy, a te, które po zmniejszeniu mają stan ujemny, zerujemy – pozwoli to zachować względną kolejność elementów na liście).

Metoda wymaga nowego typu elementów:

Pascal
type
  PdlistEl = ^dlistEl;
  dlistEl =  record
    next  : PdlistEl;
    prev  : PdlistEl;
    count : Cardinal
    data  : typ_danych;
  end;
   C++
struct dlistEl
{
  dlistEl * next, * prev;
  unsigned int count;
  typ_danych data;
};
   Basic
Type dlistEl
  next As dlistEl Ptr
  prev As dlistEl Ptr
  count As UInteger
  data As typ_danych
End Type

Algorytm wyszukiwania ze zliczaniem znalezionych elementów i sortowaniem listy

Wejście:

L  –  zmienna obsługująca listę
v  – poszukiwana wartość

Wyjście:

adres znalezionego elementu lub nil, jeśli elementu nie ma na liście. Lista zostaje posortowana wg częstości wykorzystywania jej elementów.

Zmienne pomocnicze:

p, r  –  wskaźniki elementów listy

Lista kroków:

K01: p L.head rozpoczynamy wyszukiwanie od pierwszego elementu listy
K02: Jeśli p = nil, to idź do K14 jeśli koniec listy, to kończymy
K03: Jeśli (pdata) ≠ v, to idź do K09 element znaleziony?
K04: (pcount) ← (pcount) + 1 zwiększamy licznik użycia
K05: r ← (pprev) zapamiętaj poprzedni element w r
K06: Odłącz element p od listy  
K07: Jeśli r = nil, idź do K11 jeśli brak poprzednika, to p jest pierwszym elementem
K08: Jeśli (rcount) > (pcount), to idź do K13 szukamy bardziej częstego elementu poprzedzającego
K09: r ← (rprev) cofamy się wstecz o jeden element
K10: Idź do K07 i kontynuujemy wyszukiwanie
K11: Wstaw p na początek listy  
K12 Idź do K14  
K13: Wstaw p za r  
K14: Zakończ z wynikiem 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 uporządkowaną listę dwukierunkową 10 liczb całkowitych od 0 do 9. Następnie dokonuje 1000 wyszukiwań liczb losowych od 0 do 9. Na końcu wypisuje zawartość listy wraz ze stanem licznika każdego elementu. W programie wykorzystujemy zmodyfikowany obiekt listy dwukierunkowej.
Pascal
// Samoorganizujące się listy
// Zliczanie z sortowaniem
// Data: 04.08.2012
// (C)2019 mgr Jerzy Wałaszek
//------------------------------

program count_use;

// Typ elementów listy
//--------------------
type
  PdlistEl = ^dlistEl;

  dlistEl =  record
    next  : PdlistEl;
    prev  : PdlistEl;
    count : Cardinal;
    data  : integer;
  end;

// Definicja typu obiektowego dlist
//---------------------------------

  dlist = object
    public

      head : PdlistEl;  // początek listy
      tail : PdlistEl;  // koniec listy

      constructor init;
      destructor destroy;
      procedure printl;
      procedure push_front(v : integer);
      procedure pop_front;
      function  find(v : integer) : PdlistEl;
  end;

//---------------------
// Metody obiektu dlist
//---------------------

// Konstruktor - inicjuje pole head
//---------------------------------
constructor dlist.init;
begin
  head := nil;
  tail := nil;
end;

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


// Procedura wyświetla zawartość elementów listy
//----------------------------------------------
procedure dlist.printl;
var
  p : PdlistEl;
begin
  p := head;
  while p <> nil do
  begin
    writeln(p^.data, ' : ', p^.count:4);
    p := p^.next;
  end;
end;

// Procedura dołączania na początek listy
//---------------------------------------
procedure dlist.push_front(v : integer);
var
  p : PdlistEl;
begin
  new(p);   // tworzymy nowy element
  p^.data  := v;
  p^.count := 0;
  p^.prev  := nil;
  p^.next  := head;
  head     := p;
  if p^.next <> nil then p^.next^.prev := p
  else tail := p;
end;


// Procedura usuwa pierwszy element
//---------------------------------
procedure dlist.pop_front;
var
  p : PdlistEl;
begin
  p := head;
  if p <> nil then
  begin
    head := p^.next;
    if head = nil then tail := nil
    else head^.prev := nil;
    dispose(p);
  end;
end;

// Funkcja wyszukuje element, zwiększa jego licznik
// i umieszcza na takim miejscu listy, że poprzednik
// posiada licznik większy
//------------------------------------------------

function dlist.find(v : integer) : PdlistEl;
var
  p, r : PdlistEl;
begin
  p := head;                  // rozpoczynamy od początku listy

  while p <> nil do           // w pętli przeszukujemy listę
  begin

    if p^.data = v then       // element znaleziony?
    begin

      inc(p^.count);          // zwiększamy licznik użycia

      r := p^.prev;           // w r zapamiętujemy poprzedni element

                              // odłączamy element od listy

      if r <> nil then r^.next := p^.next
      else head := p^.next;

      if p^.next <> nil then p^.next^.prev := p^.prev
      else tail := p^.prev;

      while true do
      begin

        if r = nil then
        begin                 // umieszczamy go na początku listy
          p^.next := head;
          p^.prev := nil;
          head := p;
          if p^.next <> nil then p^.next^.prev := p
          else tail := p;

          Exit(p);            // wychodzimy z funkcji
        end;

        if r^.count > p^.count then
        begin                 // umieszczamy go za r
          p^.next := r^.next;
          r^.next := p;
          p^.prev := r;
          if p^.next <> nil then p^.next^.prev := p
          else tail := p;

          Exit(p);            // wychodzimy z funkcji
        end;

        r := r^.prev;         // idziemy do poprzedniego elementu

      end;

    end;

    p := p^.next;             // przechodzimy do następnego elementu
  end;                        // kontynuujemy pętlę

  find := p;                  // zwracamy wynik p
end;

//---------------
// Program główny
//---------------

var
  L : dlist;    // obiekt listy
  i : integer;

begin
  randomize;                              // inicjujemy liczby pseudolosowe

  L.init;                                 // inicjujemy obiekt

  for i := 9 downto 0 do L.push_front(i); // tworzymy listę

  for i := 1 to 1000 do                   // przeszukujemy listę 1000 razy
    L.find(random(10));                   // szukamy elementów od 0 do 9

  L.printl;                               // wyświetlamy wyniki
  L.destroy;
end.
C++
// Samoorganizujące się listy
// Zliczanie z sortowaniem
// Data: 04.08.2012
// (C)2019 mgr Jerzy Wałaszek
//------------------------------

#include <iostream>
#include <iomanip>
#include <cstdlib>
#include <ctime>

using namespace std;

// Element listy
//--------------
struct dlistEl
{
  dlistEl * next;     // następnik
  dlistEl * prev;     // poprzednik
  unsigned int count; // licznik
  int data;
};

// Definicja obiektu listy dwukierunkowej
//---------------------------------------
class dlist
{
  public:
    dlistEl * head;  // początek listy
    dlistEl * tail;  // koniec listy

    dlist();         // konstruktor
    ~dlist();        // destruktor
    void printl();
    void push_front(int v);
    void pop_front();
    dlistEl * find(int v);
};

//------------------------------------
// Metody obiektu listy dwukierunkowej
//------------------------------------

// Inicjuje pola zmiennej listy
//-----------------------------
dlist::dlist()
{
  head  = tail  = NULL;
}

// Usuwa listę z pamięci
//----------------------
dlist::~dlist()
{
  while(head) pop_front();
}

// Procedura wyświetla zawartość elementów listy
//----------------------------------------------
void dlist::printl()
{
  for(dlistEl * p = head; p; p = p->next)
    cout << p->data << ":  " << setw(4) << p->count << endl;
}

// Procedura dołączania na początek listy
//---------------------------------------
void dlist::push_front(int v)
{
  dlistEl * p = new dlistEl;   // tworzymy nowy element
  p->data = v;
  p->count = 0;
  p->prev = NULL;
  p->next = head;
  head = p;
  if(p->next) p->next->prev = p; else tail = p;
}

// Procedura usuwa pierwszy element
//---------------------------------
void dlist::pop_front()
{
  if(dlistEl * p = head)
  {
    if(!(head = p->next)) tail = NULL; else head->prev = NULL;
    delete p;
  }
}

// Funkcja wyszukuje element, zwiększa jego licznik
// i umieszcza na takim miejscu listy, że poprzednik
// posiada licznik większy
//------------------------------------------------

dlistEl * dlist::find(int v)
{
  dlistEl *p, *r;

  for(p = head; p; p = p->next)  // w pętli przeszukujemy listę

    if(p->data == v)             // element znaleziony?
    {
      p->count++;                // zwiększamy licznik użycia

      r = p->prev;               // w r zapamiętujemy poprzedni element

      // odłączamy element od listy

      if(r)       r->next = p->next;       else head = p->next;
      if(p->next) p->next->prev = p->prev; else tail = p->prev;

      while(true)
      {
        if(!r)
        { // umieszczamy go na początku listy
          p->next = head;
          p->prev = NULL;
          head = p;
          if(p->next) p->next->prev = p; else tail = p;

          return p;            // wychodzimy z funkcji
        }

        if(r->count > p->count)
        { // umieszczamy go za r
          p->next = r->next;
          r->next = p;
          p->prev = r;
          if(p->next) p->next->prev = p; else tail = p;

          return p;            // wychodzimy z funkcji
        }

        r = r->prev;         // idziemy do poprzedniego elementu
      }
    }

  return p;                  // zwracamy wynik p
}

//---------------
// Program główny
//---------------

int main()
{
  dlist L;    // obiekt listy
  int i;

  srand(time(NULL));                       // inicjujemy liczby pseudolosowe

  for(i = 9; i >= 0; i--) L.push_front(i); // tworzymy listę

  for(i = 0; i < 1000; i++)                // przeszukujemy listę 1000 razy
    L.find(rand() % 10);

  L.printl();                              // wyświetlamy zawartość listy

  return 0;
}
Basic
' Samoorganizujące się listy
' Zliczanie z sortowaniem
' Data: 04.08.2012
' (C)2019 mgr Jerzy Wałaszek
'------------------------------

' Element listy
'--------------
Type dlistEl
  next As dlistEl Ptr   ' następnik
  prev As dlistEl Ptr   ' poprzednik
  count As UInteger     ' licznik
  data As Integer
End Type

' Definicja obiektu listy dwukierunkowej
'---------------------------------------
Type dlist

  head As dlistEl Ptr  ' początek listy
  tail As dlistEl Ptr  ' koniec listy

  Declare Constructor()
  Declare Destructor()
  Declare Sub printl()
  Declare Sub push_front(v As Integer)
  Declare Sub pop_front()
  Declare Function find(v As Integer) As dlistEl Ptr
End Type

'---------------
' Program główny
'---------------

Dim L As dlist
Dim As Integer i

Randomize                                  ' inicjujemy liczby pseudolosowe

For i = 9 To 0 Step -1
  L.push_front(i)                          ' tworzymy listę
Next

For i = 1 To 1000                          ' przeszukujemy listę 1000
  L.find(Int(Rnd()* 10))                   ' szukamy elementów od 0 do 9
Next

L.printl()                                 ' wyświetlamy zawartość listy

End

'------------------------------------
' Metody obiektu listy dwukierunkowej
'------------------------------------

' Konstruktor listy
'------------------
Constructor dlist()
  head  = 0
  tail  = 0
End Constructor

' Usuwa listę z pamięci
Destructor dlist()
  While head
  	 pop_front()
  Wend
End Destructor

' Procedura wyświetla zawartość elementów listy
'----------------------------------------------
Sub dlist.printl()

  Dim p As dlistEl Ptr
  p = head
  While p
    Print Using "#: ####";p->Data, p->count
    p = p->Next
  Wend
  Print
End Sub

' Procedura dołączania na początek listy
'---------------------------------------
Sub dlist.push_front(v As Integer)
  Dim p As dlistEl Ptr
  p = new dlistEl
  p->data = v
  p->count = 0
  p->prev = 0
  p->next = head
  head = p
  If p->Next Then
  	 p->next->prev = p
  Else
  	 tail = p
  End If
End Sub

' Procedura usuwa pierwszy element
'---------------------------------
Sub dlist.pop_front()
  Dim p As dlistEl Ptr
  p = head
  If p Then
  	 head = p->Next
    If head = 0 Then
    	tail = 0
    Else
    	head->prev = 0
    End If
    Delete p
  End If
End Sub

' Funkcja wyszukuje element, zwiększa jego licznik
' i umieszcza na takim miejscu listy, że poprzednik
' posiada licznik większy
'------------------------------------------------
Function dlist.find(v As integer) As dlistEl Ptr

  Dim As dlistEl Ptr p, r
  
  p = head
  
  While p                        ' w pętli przeszukujemy listę

    if p->data = v Then          ' element znaleziony?
    
      p->count += 1              ' zwiększamy licznik użycia

      r = p->prev                ' w r zapamiętujemy poprzedni element

      ' odłączamy element od listy

      if r then
        r->next = p->next
      else
        head = p->Next
      End If
      
      if p->Next Then
        p->next->prev = p->prev
      else
        tail = p->prev
      End If

      While 1
        if r = 0 Then
          ' umieszczamy go na początku listy
          p->next = head
          p->prev = 0
          head = p
          If p->Next Then
            p->next->prev = p
          else
            tail = p
          End If

          return p             ' wychodzimy z funkcji
        End If

        if r->count > p->count Then
          ' umieszczamy go za r
          p->next = r->Next
          r->next = p
          p->prev = r
          if p->next Then
            p->next->prev = p
          else
            tail = p
          End If

          return p             ' wychodzimy z funkcji
        
        End If

        r = r->prev            ' idziemy do poprzedniego elementu
      
      Wend
    
    End If
    
    p = p->Next
    
  Wend

  return p                      ' zwracamy wynik p

End function
Wynik:
8 :  113
5 :  111
7 :  105
9 :  103
0 :  102
3 :   99
2 :   98
4 :   96
6 :   91
1 :   82
Na początek:  podrozdziału   strony 

Metoda przemieszczania (ang. transpose method)

W metodzie przemieszczania znaleziony element zostaje wymieniony z elementem go poprzedzającym. W efekcie elementy często używane ciągle są przemieszczane w kierunku początku listy. Zaletą tej metody jest brak konieczności utrzymywania liczników, z drugiej strony elementy znajdujące się początkowo daleko na liście będą wymagały wielu operacji przemieszczenia, zanim znajdą się na początku listy.

Algorytm wyszukiwania z przemieszczaniem elementów

Wejście:

L  –  zmienna obsługująca listę
v  – poszukiwana wartość

Wyjście:

adres znalezionego elementu lub nil, jeśli elementu nie ma na liście. Znaleziony element zostaje przemieszczony na liście o jedną pozycję w kierunku jej początku.

Zmienne pomocnicze:

p  –  wskaźnik elementów listy

Lista kroków:

K01: pL.head przeszukiwanie rozpoczynamy od pierwszego elementu na liście
K02: Jeśli p = nil, to idź do K09  
K03: Jeśli (pdata) ≠ v, to idź do K07 sprawdzamy, czy p wskazuje poszukiwany element
K04: Odłącz p od listy jeśli tak, to zamieniamy go z poprzedzającym
K05: Wstaw p przed jego poprzednik  
K06: Idź do K09  
K07: p ← (pnext) przechodzimy do następnego elementu
K08: Idź do K02 i kontynuujemy pętlę
K09: Zakończ z wynikiem 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 uporządkowaną listę dwukierunkową 10 liczb całkowitych od 0 do 9. Następnie dokonuje 40 wyszukiwań liczb losowych od 0 do 9, wypisując za każdym razem stan listy. W programie wykorzystujemy zmodyfikowany obiekt listy dwukierunkowej.
 
Pascal
// Samoorganizujące się listy
// Wyszukiwanie z przemieszczaniem
// Data: 04.08.2012
// (C)2019 mgr Jerzy Wałaszek
//------------------------------

program transpose;

// Typ elementów listy
//--------------------
type
  PdlistEl = ^dlistEl;

  dlistEl =  record
    next  : PdlistEl;
    prev  : PdlistEl;
    data  : integer;
  end;

// Definicja typu obiektowego dlist
//---------------------------------

  dlist = object
    public

      head : PdlistEl;  // początek listy
      tail : PdlistEl;  // koniec listy

      constructor init;
      destructor  destroy;
      procedure   printl(v : integer);
      procedure   push_front(v : integer);
      procedure   pop_front;
      function    find(v : integer) : PdlistEl;
  end;

//---------------------
// Metody obiektu dlist
//---------------------

// Konstruktor - inicjuje pole head
//---------------------------------
constructor dlist.init;
begin
  head := nil;
  tail := nil;
end;

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

// Procedura wyświetla zawartość elementów listy
//----------------------------------------------
procedure dlist.printl(v : integer);
var
  p : PdlistEl;
begin
  p := head;
  while p <> nil do
  begin
    if p^.data = v then write('(', p^.data, ')') else write(' ', p^.data, ' ');
    p := p^.next;
  end;
  writeln;
end;

// Procedura dołączania na początek listy
//---------------------------------------
procedure dlist.push_front(v : integer);
var
  p : PdlistEl;
begin
  new(p);   // tworzymy nowy element
  p^.data  := v;
  p^.prev  := nil;
  p^.next  := head;
  head     := p;
  if p^.next <> nil then p^.next^.prev := p
  else tail := p;
end;

// Procedura usuwa pierwszy element
//---------------------------------
procedure dlist.pop_front;
var
  p : PdlistEl;
begin
  p := head;
  if p <> nil then
  begin
    head := p^.next;
    if head = nil then tail := nil
    else head^.prev := nil;
    dispose(p);
  end;
end;

// Funkcja wyszukuje element i zamienia go z poprzednikiem
//--------------------------------------------------------

function dlist.find(v : integer) : PdlistEl;
var
  p : PdlistEl;
begin
  p := head;                   // rozpoczynamy od początku listy

  while p <> nil do            // w pętli przeszukujemy listę
  begin

    if p^.data = v then        // element znaleziony?
    begin
                               // odłączamy element od listy

      if p^.prev <> nil then p^.prev^.next := p^.next
      else break;

      if p^.next <> nil then p^.next^.prev := p^.prev
      else tail := p^.prev;

                               // umieszczamy go przed poprzednikiem
      p^.next := p^.prev;
      p^.prev := p^.next^.prev;
      p^.next^.prev := p;
      if p^.prev <> nil then p^.prev^.next := p
      else head := p;

      break;

    end;

    p := p^.next;              // przechodzimy do następnego elementu
  end;                         // kontynuujemy pętlę

  find := p;                   // zwracamy wynik p
end;

//---------------
// Program główny
//---------------

var
  L : dlist;    // obiekt listy
  i, v : integer;

begin
  Randomize;                              // inicjujemy liczby pseudolosowe

  L.init;                                 // inicjujemy obiekt

  for i := 9 downto 0 do L.push_front(i); // tworzymy listę


  write('    '); L.printl(10);            // lista początkowa

  for i := 1 to 40 do                     // 40 razy wyszukujemy element
  begin
    v := random(10);                      // losujemy elemeny 0...9
    write(v, ':  ');                       // wyświetlamy wylosowany element
    L.find(v);                            // wyszukujemy element
    L.printl(v);                          // wyświetlamy listę
  end;

  L.destroy;
end.
C++
// Samoorganizujące się listy
// Wyszukiwanie z przemieszczaniem
// Data: 04.08.2012
// (C)2019 mgr Jerzy Wałaszek
//------------------------------

#include <iostream>
#include <cstdlib>
#include <ctime>

using namespace std;

// Element listy
//--------------
struct dlistEl
{
  dlistEl * next;     // następnik
  dlistEl * prev;     // poprzednik
  int data;
};

// Definicja obiektu listy dwukierunkowej
//---------------------------------------
class dlist
{
  public:
    dlistEl * head;  // początek listy
    dlistEl * tail;  // koniec listy

    dlist();         // konstruktor
    ~dlist();        // destruktor
    void printl(int v);
    void push_front(int v);
    void pop_front();
    dlistEl * find(int v);
};

//------------------------------------
// Metody obiektu listy dwukierunkowej
//------------------------------------

// Inicjuje pola zmiennej listy
//-----------------------------
dlist::dlist()
{
  head  = tail  = NULL;
}

// Usuwa listę z pamięci
//----------------------
dlist::~dlist()
{
  while(head) pop_front();
}

// Procedura wyświetla zawartość elementów listy
//----------------------------------------------
void dlist::printl(int v)
{
  for(dlistEl * p = head; p; p = p->next)
    if(p->data == v) cout << "(" << p->data << ")";
    else             cout << " " << p->data << " ";
  cout << endl;
}

// Procedura dołączania na początek listy
//---------------------------------------
void dlist::push_front(int v)
{
  dlistEl * p = new dlistEl;   // tworzymy nowy element
  p->data = v;
  p->prev = NULL;
  p->next = head;
  head = p;
  if(p->next) p->next->prev = p; else tail = p;
}

// Procedura usuwa pierwszy element
//---------------------------------
void dlist::pop_front()
{
  if(dlistEl * p = head)
  {
    if(!(head = p->next)) tail = NULL; else head->prev = NULL;
    delete p;
  }
}

// Funkcja wyszukuje element i zamienia go z poprzednikiem
//--------------------------------------------------------

dlistEl * dlist::find(int v)
{
  dlistEl *p;

  for(p = head; p; p = p->next)  // w pętli przeszukujemy listę

    if(p->data == v)             // element znaleziony?
    {

      // odłączamy element od listy

      if(p->prev) p->prev->next = p->next;
      else break;

      if(p->next) p->next->prev = p->prev;
      else tail = p->prev;

                               // umieszczamy go przed poprzednikiem
      p->next = p->prev;
      p->prev = p->next->prev;
      p->next->prev = p;
      if(p->prev) p->prev->next = p;
      else head = p;

      break;
    }

  return p;                    // zwracamy wynik p
}

//---------------
// Program główny
//---------------

int main()
{
  dlist L;    // obiekt listy
  int i, v;

  srand(time(NULL));                       // inicjujemy liczby pseudolosowe

  for(i = 9; i >= 0; i--) L.push_front(i); // tworzymy listę

  cout << "    "; L.printl(10);            // lista początkowa

  for(i = 0; i < 40; i++)                  // 40 razy wyszukujemy element
  {
    v = rand() % 10;                       // losujemy elemeny 0...9
    cout << v << ":  ";                    // wyświetlamy wylosowany element
    L.find(v);                             // wyszukujemy element
    L.printl(v);                           // wyświetlamy listę
  }

  return 0;
}
Basic
' Samoorganizujące się listy
' Wyszukiwanie z przemieszczaniem
' Data: 04.08.2012
' (C)2019 mgr Jerzy Wałaszek
'------------------------------

' Element listy
'--------------
Type dlistEl
  next As dlistEl Ptr   ' następnik
  prev As dlistEl Ptr   ' poprzednik
  data As Integer
End Type

' Definicja obiektu listy dwukierunkowej
'---------------------------------------
Type dlist

  head As dlistEl Ptr  ' początek listy
  tail As dlistEl Ptr  ' koniec listy

  Declare Constructor()
  Declare Destructor()
  Declare Sub printl(v As Integer)
  Declare Sub push_front(v As Integer)
  Declare Sub pop_front()
  Declare Function find(v As Integer) As dlistEl Ptr
End Type

'---------------
' Program główny
'---------------

Dim L As dlist
Dim As Integer i, v

Randomize                                  ' inicjujemy liczby pseudolosowe

For i = 9 To 0 Step -1
  L.push_front(i)                          ' tworzymy listę
Next

Print "    ";: L.printl(10)                ' lista początkowa

For i = 1 to 40                            ' 40 razy wyszukujemy element
  v = Int(Rnd() * 10)                      ' losujemy elemeny 0...9
  Print Using "#:  ";v;                    ' wyświetlamy wylosowany element
  L.find(v)                                ' wyszukujemy element
  L.printl(v)                              ' wyświetlamy listę
Next
End

'------------------------------------
' Metody obiektu listy dwukierunkowej
'------------------------------------

' Konstruktor listy
'------------------
Constructor dlist()
  head  = 0
  tail  = 0
End Constructor

' Usuwa listę z pamięci
Destructor dlist()
  While head
  	 pop_front()
  Wend
End Destructor

' Procedura wyświetla zawartość elementów listy
'----------------------------------------------
Sub dlist.printl(v As Integer)

  Dim p As dlistEl Ptr
  p = head
  While p
    if p->data = v Then
    	Print Using "(#)";p->data;
    Else
    	Print Using " # ";p->data;
    End If
    p = p->Next
  Wend
  Print
End Sub

' Procedura dołączania na początek listy
'---------------------------------------
Sub dlist.push_front(v As Integer)
  Dim p As dlistEl Ptr
  p = new dlistEl
  p->data = v
  p->prev = 0
  p->next = head
  head = p
  If p->Next Then
  	 p->next->prev = p
  Else
  	 tail = p
  End If
End Sub

' Procedura usuwa pierwszy element
'---------------------------------
Sub dlist.pop_front()
  Dim p As dlistEl Ptr
  p = head
  If p Then
  	 head = p->Next
    If head = 0 Then
    	tail = 0
    Else
    	head->prev = 0
    End If
    Delete p
  End If
End Sub

' Funkcja wyszukuje element i zamienia go z poprzednikiem
'--------------------------------------------------------
Function dlist.find(v As integer) As dlistEl Ptr

  Dim As dlistEl Ptr p
  
  p = head
  
  While p                        ' w pętli przeszukujemy listę

    if p->data = v Then          ' element znaleziony?

      ' odłączamy element od listy
      
      if p->prev Then
        p->prev->next = p->Next
      Else
        Exit While
      End If

      if p->next then
        p->next->prev = p->prev
      Else
        tail = p->prev
      End If

      ' umieszczamy go przed poprzednikiem
      
      p->next = p->prev
      p->prev = p->next->prev
      p->next->prev = p
      if p->prev then
        p->prev->Next = p
      Else
      	head = p
      End If
      
      Exit While
    
    End If
    
    p = p->Next
    
  Wend

  return p                   ' zwracamy wynik p

End function
Wynik:
     0  1  2  3  4  5  6  7  8  9
3:   0  1 (3) 2  4  5  6  7  8  9
5:   0  1  3  2 (5) 4  6  7  8  9
5:   0  1  3 (5) 2  4  6  7  8  9
8:   0  1  3  5  2  4  6 (8) 7  9
0:  (0) 1  3  5  2  4  6  8  7  9
4:   0  1  3  5 (4) 2  6  8  7  9
4:   0  1  3 (4) 5  2  6  8  7  9
0:  (0) 1  3  4  5  2  6  8  7  9
8:   0  1  3  4  5  2 (8) 6  7  9
3:   0 (3) 1  4  5  2  8  6  7  9
8:   0  3  1  4  5 (8) 2  6  7  9
4:   0  3 (4) 1  5  8  2  6  7  9
5:   0  3  4 (5) 1  8  2  6  7  9
5:   0  3 (5) 4  1  8  2  6  7  9
3:  (3) 0  5  4  1  8  2  6  7  9
6:   3  0  5  4  1  8 (6) 2  7  9
3:  (3) 0  5  4  1  8  6  2  7  9
2:   3  0  5  4  1  8 (2) 6  7  9
5:   3 (5) 0  4  1  8  2  6  7  9
2:   3  5  0  4  1 (2) 8  6  7  9
1:   3  5  0 (1) 4  2  8  6  7  9
6:   3  5  0  1  4  2 (6) 8  7  9
4:   3  5  0 (4) 1  2  6  8  7  9
2:   3  5  0  4 (2) 1  6  8  7  9
2:   3  5  0 (2) 4  1  6  8  7  9
1:   3  5  0  2 (1) 4  6  8  7  9
1:   3  5  0 (1) 2  4  6  8  7  9
6:   3  5  0  1  2 (6) 4  8  7  9
2:   3  5  0 (2) 1  6  4  8  7  9
9:   3  5  0  2  1  6  4  8 (9) 7
4:   3  5  0  2  1 (4) 6  8  9  7
9:   3  5  0  2  1  4  6 (9) 8  7
5:  (5) 3  0  2  1  4  6  9  8  7
2:   5  3 (2) 0  1  4  6  9  8  7
1:   5  3  2 (1) 0  4  6  9  8  7
0:   5  3  2 (0) 1  4  6  9  8  7
9:   5  3  2  0  1  4 (9) 6  8  7
3:  (3) 5  2  0  1  4  9  6  8  7
1:   3  5  2 (1) 0  4  9  6  8  7
9:   3  5  2  1  0 (9) 4  6  8  7
Na początek:  podrozdziału   strony 

Zadanie

Zaproponuj podobne algorytmy dla list jednokierunkowych

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