Algorytmy i Struktury Danych - Samoorganizujące się listy

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.

Elementy 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,  ; jeśli koniec listy, 
       to idź do kroku K09 ; to kończymy
K03:   Jeśli p→data ≠ v, ; sprawdzamy, czy natrafiliśmy
       to idź do kroku K07 ; na poszukiwany element
K04:   Odłącz element p od listy
K05:   Wstaw element p na początek listy
K06:   Idź do kroku K09 ; wychodzimy z pętli
K07:   p ← p→next ; następny element na liście
K08:   Idź do kroku 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)2020 mgr Jerzy Wałaszek
//------------------------------

program move_to_front;

// Typ elementów listy
//--------------------
type
  PDLel = ^DLel;

  DLel =  record
    next  : PDLel;
    prev  : PDLel;
    Data: integer;
  end;

// Definicja typu obiektowego DLvar
//------------------------------------

  DLvar = object
    public

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

      constructor init;
      destructor  destroy;
      procedure   l_print;
      procedure   l_push_front(v : integer);
      procedure   l_pop_front;
      function    l_find(v : integer)
                         : PDLel;
  end;

//------------------------
// Metody obiektu DLvar
//------------------------

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

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


// Procedura wyświetla zawartość listy
//------------------------------------
procedure DLvar.l_print;
var
  p : PDLel;
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 DLvar.l_push_front(v : integer);
var
  p : PDLel;
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 DLvar.l_pop_front;
var
  p : PDLel;
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 DLvar.l_find(v : integer)
                         : PDLel;
var
  p : PDLel;
begin
  p := head; // rozpoczynamy od początku
  while p <> nil do // 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; // do następnego elementu
  end;            // kontynuujemy pętlę
  l_find := p;    // zwracamy wynik p
end;

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

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

begin
  randomize;
  L.init; // inicjujemy obiekt
  for i := 9 downto 0 do
    L.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.l_find(v);    // szukamy elementu
    L.l_print;      // wyświetlamy zawartość
  end;
  L.destroy; // usuwamy listę z pamięci
end.

C++

// Samoorganizujące się listy
// Przesuwanie na początek listy
// Data: 04.08.2012
// (C)2020 mgr Jerzy Wałaszek
//------------------------------

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

using namespace std;

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

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

    DLvar();     // konstruktor
    ~DLvar();    // destruktor
    void l_print();
    void l_push_front(int v);
    void l_pop_front();
    DLel * l_find(int v);
};

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

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

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

// Wyświetla zawartość elementów listy
//------------------------------------
void DLvar::l_print()
{
  for(DLel * p = head; p; p = p->next)
    if(p == head)
      cout << " (" << p->data << ")";
    else
      cout << " " << p->data << " ";
  cout << endl;
}

// Dołącza na początek listy
//--------------------------
void DLvar::l_push_front(int v)
{
  DLel * p = new DLel;
  p->data = v;
  p->prev = NULL;
  p->next = head;
  head = p;
  if(p->next)
    p->next->prev = p;
  else
    tail = p;
}

// Usuwa pierwszy element
//-----------------------
void DLvar::l_pop_front()
{
  if(DLel * p = head)
  {
    if(!(head = p->next))
      tail = NULL;
    else
      head->prev = NULL;
    delete p;
  }
}

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

DLel * DLvar::l_find (int v)
{
  DLel * p;

  for(p = head; p; p = p->next)
    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()
{
  DLvar L; // obiekt listy
  int i, v;

  srand(time(NULL));

  for(i = 9; i >= 0; i--)
    L.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.l_find(v); // szukamy elementu
    L.l_print(); // wyświetlamy zawartość listy
  }
  return 0;
}

Basic

' Samoorganizujące się listy
' Przesuwanie na początek listy
' Data: 04.08.2012
' (C)2020 mgr Jerzy Wałaszek
'------------------------------

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

' Definicja obiektu listy dwukierunkowej
'---------------------------------------
Type DLvar

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

  Declare Constructor()
  Declare Destructor()
  Declare Sub l_print()
  Declare Sub l_push_front(v As Integer)
  Declare Sub l_pop_front()
  Declare Function l_find(v As Integer)_
                          As DLel Ptr
End Type

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

Dim L As DLvar
Dim As Integer i, v

Randomize ' inicjujemy liczby pseudolosowe

For i = 9 To 0 Step -1
  L.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.l_find(v) ' szukamy elementu
  L.l_print() ' wyświetlamy zawartość listy
Next
End

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

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

' Usuwa listę z pamięci
Destructor DLvar()
  While head
    l_pop_front()
  Wend
End Destructor

' Wyświetla zawartość elementów listy
'------------------------------------
Sub DLvar.l_print()
  Dim p As DLel 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

' Dołącza na początek listy
'--------------------------
Sub DLvar.l_push_front(v As Integer)
  Dim p As DLel Ptr
  p = new DLel
  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

' Usuwa pierwszy element
'-----------------------
Sub DLvar.l_pop_front()
  Dim p As DLel 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

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

Function DLvar.l_find(v As integer)_
                         As DLel Ptr
  Dim p As DLel 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
  l_find = p ' zwracamy wynik p
End function

Python (dodatek)

# Samoorganizujące się listy
# Przesuwanie na początek listy
# Data: 31.05.2024
# (C)2024 mgr Jerzy Wałaszek
# ------------------------------

import random


# klasa elementu listy
# ---------------------
class DLel:


    def __init__(self, data):
        self.next = None
        self.prev = None
        self.data = data


# klasa listy dwukierunkowej
# ---------------------------
class DLvar:


    # Konstruktor
    def __init__(self):
        self.head = None
        self.tail = None


    # Destructor
    def __del__(self):
        while self.head:
            self.l_pop_front()


    # Wyświetla zawartość elementów listy
    def l_print(self):
        p = self.head
        while p:
            if p is self.head:
                print("(", p.data, ")",
                      sep="", end="")
            else:
                print(" ", p.data, " ",
                      sep="", end="")
            p = p.next
        print()


    # Dodaje nowy element na początek
    def l_push_front(self, v):
        p = DLel(v)
        p.next = self.head
        self.head = p
        if p.next:
            p.next.prev = p
        else:
            self.tail = p


    # Usuwa pierwszy element
    def l_pop_front(self):
        p = self.head
        if p:
            self.head = p.next
            if not self.head:
                self.tail = None
            else:
                self.head.prev = None


    # Wyszukuje element, a jeśli go znajdzie,
    # to umieszcza go na początku listy. Zwraca
    # adres znalezionego elementu lub nil
    # -----------------------------------------
    def l_find(self, v):
        p = self.head
        while p:
            if p.data == v:  # element znaleziony?
                # odłączamy element od listy
                if p.prev:
                    p.prev.next = p.next
                else:
                    self.head = p.next
                if p.next:
                    p.next.prev = p.prev
                else:
                    self.tail = p.prev
                # umieszczamy go na początku listy
                p.next = self.head
                p.prev = None
                self.head = p
                if p.next:
                    p.next.prev = p
                else:
                    self.tail = p
                break  # opuszczamy pętlę
            p = p.next
        return p  # zwracamy wynik p


# ---------------
# Program główny
# ---------------

dl = DLvar()  # obiekt listy
for i in reversed(range(10)):
    # tworzymy listę
    dl.l_push_front(i)
for i in range(20):  # przeszukujemy listę
    # losujemy element
    v = random.randrange(10)
    # wyświetlamy go
    print(v, ": ", sep="", end="")
    # szukamy elementu
    dl.l_find(v)
    # wyświetlamy zawartość listy
    dl.l_print()

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

do podrozdziału do strony

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
  PDLel = ^DLel;
  DLel =  record
    next  : PDLel;
    prev  : PDLel;
    count : Cardinal
    Data: typ_danych;
  end;

C++

struct DLel
{
  DLel * next, * prev;
  unsigned int count;
  typ_danych data;
};

Basic

Type DLel
  next As DLel Ptr
  prev As DLel Ptr
  count As UInteger
  data As typ_danych
End Type

Python (dodatek)

# klasa elementu listy
#---------------------
class DLel:


    def __init__(self, data):
        self.next  = None
        self.prev  = None
        self.count = 0
        self.data  = data

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.

Elementy pomocnicze:

p, r : wskaźniki elementów listy.

Lista kroków:

K01: p ← L.head ; rozpoczynamy od pierwszego elementu
K02: Jeśli p = nil, ; jeśli koniec listy, to kończymy
     to idź do kroku K14
K03: Jeśli p→data ≠ v, ; element znaleziony?
     to idź do kroku K09
K04: p→count ← p→count+1 ; zwiększamy licznik użycia
K05: r ← p→prev ; zapamiętaj poprzedni element w r
K06: Odłącz element p od listy
K07: Jeśli r = nil, ; jeśli brak poprzednika, to p
     idź do kroku K11 ; jest pierwszym elementem
K08: Jeśli r→count > p→count, ; szukamy częstszego
     to idź do kroku K13 ; elementu poprzedzającego
K09: r ← r→prev ; cofamy się wstecz o jeden element
K10: Idź do kroku K07 ; i kontynuujemy wyszukiwanie
K11: Wstaw p na początek listy
K12: Idź do kroku 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)2020 mgr Jerzy Wałaszek
//------------------------------

program count_use;

// Typ elementów listy
//--------------------
type
  PDLel = ^DLel;

  DLel =  record
    next  : PDLel;
    prev  : PDLel;
    count : Cardinal;
    Data: integer;
  end;

// Definicja typu obiektowego DLvar
//------------------------------------

  DLvar = object
    public

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

      constructor init;
      destructor destroy;
      procedure l_print;
      procedure l_push_front(v : integer);
      procedure l_pop_front;
      function  l_find(v : integer) : PDLel;
  end;

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

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

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


// Procedura wyświetla zawartość elementów listy
//----------------------------------------------
procedure DLvar.l_print;
var
  p : PDLel;
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 DLvar.l_push_front(v : integer);
var
  p : PDLel;
begin
  new(p);
  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 DLvar.l_pop_front;
var
  p : PDLel;
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 DLvar.l_find(v : integer) : PDLel;
var
  p, r : PDLel;
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ę
  l_find := p;    // zwracamy wynik p
end;

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

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

begin
  randomize;
  L.init;                 // inicjujemy obiekt listy
  for i := 9 downto 0 do
    L.l_push_front(i);    // tworzymy listę
  for i := 1 to 1000 do   // przeszukujemy listę 1000 razy
    L.l_find(random(10)); // szukamy elementów od 0 do 9
  L.l_print;              // wyświetlamy wyniki
  L.destroy;
end.

C++

// Samoorganizujące się listy
// Zliczanie z sortowaniem
// Data: 04.08.2012
// (C)2020 mgr Jerzy Wałaszek
//------------------------------

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

using namespace std;

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

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

    DLvar();     // konstruktor
    ~DLvar();    // destruktor
    void l_print();
    void l_push_front(int v);
    void l_pop_front();
    DLel * l_find(int v);
};

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

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

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

// Procedura wyświetla zawartość listy
//------------------------------------
void DLvar::l_print()
{
  for(DLel * p = head; p; p = p->next)
    cout << p->data << ":  "
         << setw(4) << p->count << endl;
}

// Procedura dołączania na początek listy
//---------------------------------------
void DLvar::l_push_front(int v)
{
  DLel * p = new DLel;
  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 DLvar::l_pop_front()
{
  if(DLel * 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, iż poprzednik
// posiada licznik o stanie większym
//------------------------------------------------
DLel * DLvar::l_find(int v)
{
  DLel *p, *r;

  for(p = head; p; p = p->next)

    if(p->data == v) // element znaleziony?
    {
      p->count++;    // zwiększamy licznik użycia
      r = p->prev;   // w r poprzedni element
                     // i 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()
{
  DLvar L; // obiekt listy
  int i;

  srand(time(NULL));

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

  for(i = 0; i < 1000; i++) // przeszukujemy listę 1000 razy, 
    L.l_find(rand() % 10);  // porządkując jej elementy

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

  return 0;
}

Basic

' Samoorganizujące się listy
' Zliczanie z sortowaniem
' Data: 04.08.2012
' (C)2020 mgr Jerzy Wałaszek
'---------------------------

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

' Definicja obiektu listy dwukierunkowej
'---------------------------------------
Type DLvar

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

  Declare Constructor()
  Declare Destructor()
  Declare Sub l_print()
  Declare Sub l_push_front(v As Integer)
  Declare Sub l_pop_front()
  Declare Function l_find(v As Integer) As DLel Ptr
End Type

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

Dim L As DLvar
Dim As Integer i

Randomize

For i = 9 To 0 Step -1
  L.l_push_front(i)       ' tworzymy listę
Next
For i = 1 To 1000         ' przeszukujemy listę 1000
  L.l_find(Int(Rnd()*10)) ' szukamy elementów od 0 do 9
Next
L.l_print() ' wyświetlamy zawartość listy
End

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

' Konstruktor listy
Constructor DLvar()
  head  = 0
  tail  = 0
End Constructor

' Usuwa listę z pamięci
Destructor DLvar()
  While head
    l_pop_front()
  Wend
End Destructor

' Procedura wyświetla zawartość listy
Sub DLvar.l_print()
  Dim p As DLel 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 DLvar.l_push_front(v As Integer)
  Dim p As DLel Ptr
  p = new DLel
  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 DLvar.l_pop_front()
  Dim p As DLel 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, iż poprzednik
' posiada licznik o większej wartości
'--------------------------------------------------
Function DLvar.l_find(v As integer) As DLel Ptr

  Dim As DLel 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

Python (dodatek)

# Samoorganizujące się listy
# Zliczanie z sortowaniem
# Data: 02.06.2024
# (C)2024 mgr Jerzy Wałaszek
# ---------------------------

import random


# klasa elementu listy
# ---------------------
class DLel:


    def __init__(self, data):
        self.next = None
        self.prev = None
        self.count = 0
        self.data = data


# klasa listy dwukierunkowej
# ---------------------------
class DLvar:


    # Konstruktor
    def __init__(self):
        self.head = None
        self.tail = None


    # Destructor
    def __del__(self):
        while self.head:
            self.l_pop_front()


    # Wyświetla zawartość elementów listy
    def l_print(self):
        p = self.head
        while p:
            print(p.data, ":  ",
                  "%4d" % p.count,
                  sep="")
            p = p.next


    # Dodaje nowy element na początek
    def l_push_front(self, v):
        p = DLel(v)
        p.next = self.head
        self.head = p
        if p.next:
            p.next.prev = p
        else:
            self.tail = p


    # Usuwa pierwszy element
    def l_pop_front(self):
        p = self.head
        if p:
            self.head = p.next
            if not self.head:
                self.tail = None
            else:
                self.head.prev = None


    # Wyszukuje element, zwiększa jego licznik
    # i umieszcza na takim miejscu listy, iż
    # poprzednik posiada licznik o stanie większym
    def l_find(self, v):
        p = self.head
        while p:
            # element znaleziony?
            if p.data == v:
                # zwiększamy licznik użycia
                p.count += 1
                # w r poprzedni element
                r = p.prev
                # odłączamy element od listy
                if r:
                    r.next = p.next
                else:
                    self.head = p.next
                if p.next:
                    p.next.prev = p.prev
                else:
                    self.tail = p.prev
                while True:
                    if not r:
                        # umieszczamy go
                        # na początku listy
                        p.next = self.head
                        p.prev = None
                        self.head = p
                        if p.next:
                            p.next.prev = p
                        else:
                            self.tail = p
                        # wychodzimy z funkcji
                        return p
                    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:
                            self.tail = p
                        # wychodzimy z funkcji
                        return p
                    # idziemy do poprzedniego elementu
                    r = r.prev
            p = p.next
        return p  # zwracamy wynik p


# ---------------
# Program główny
# ---------------

dl = DLvar()  # obiekt listy
for i in reversed(range(10)):
    # tworzymy listę
    dl.l_push_front(i)
# przeszukujemy listę 1000 razy,
# porządkując jej elementy
for i in range(1000):
    dl.l_find(random.randrange(10))
# wyświetlamy zawartość listy
dl.l_print()

Wynik:

do podrozdziału do strony

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.

Elementy pomocnicze:

p : wskaźnik elementów listy.

Lista kroków:

K01: p ← L.head ; przeszukiwanie rozpoczynamy
     ; od pierwszego elementu na liście
K02: Jeśli p = nil, 
     to idź do kroku K09
K03: Jeśli p→data ≠ v, ; sprawdzamy, czy p
     to idź do kroku K07 ; 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 kroku K09
K07: p ← p→next ; przechodzimy do następnego elementu
K08: Idź do kroku 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)2020 mgr Jerzy Wałaszek
//--------------------------------

program transpose;

// Typ elementów listy
//--------------------
type
  PDLel = ^DLel;

  DLel =  record
    next  : PDLel;
    prev  : PDLel;
    Data: integer;
  end;

// Definicja typu obiektowego DLvar
//------------------------------------

  DLvar = object
    public
      head : PDLel;  // początek listy
      tail : PDLel;  // koniec listy

      constructor init;
      destructor  destroy;
      procedure   l_print(v : integer);
      procedure   l_push_front(v : integer);
      procedure   l_pop_front;
      function    l_find(v : integer) : PDLel;
  end;

//------------------------
// Metody obiektu DLvar
//------------------------

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

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

// Procedura wyświetla zawartość elementów listy
//----------------------------------------------
procedure DLvar.l_print(v : integer);
var
  p : PDLel;
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 DLvar.l_push_front(v : integer);
var
  p : PDLel;
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 DLvar.l_pop_front;
var
  p : PDLel;
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 DLvar.l_find(v : integer) : PDLel;
var
  p : PDLel;
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ę
  l_find := p; // zwracamy wynik p
end;

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

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

begin
  Randomize; // inicjujemy liczby pseudolosowe
  L.init;    // inicjujemy obiekt
  for i := 9 downto 0 do
    L.l_push_front(i); // tworzymy listę
  write('    ');
  L.l_print(10); // lista początkowa
  for i := 1 to 40 do // 40 razy wyszukujemy element
  begin
    v := random(10); // losujemy elementy 0…9
    write(v, ':  ');  // wyświetlamy wylosowany element
    L.l_find(v);     // wyszukujemy element
    L.l_print(v);    // wyświetlamy listę
  end;
  L.destroy;
end.

C++

// Samoorganizujące się listy
// Wyszukiwanie z przemieszczaniem
// Data: 04.08.2012
// (C)2020 mgr Jerzy Wałaszek
//--------------------------------

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

using namespace std;

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

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

    DLvar();     // konstruktor
    ~DLvar();    // destruktor
    void l_print(int v);
    void l_push_front(int v);
    void l_pop_front();
    DLel * l_find(int v);
};

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

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

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

// Procedura wyświetla zawartość listy
//------------------------------------
void DLvar::l_print(int v)
{
  for(DLel * 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 DLvar::l_push_front(int v)
{
  DLel * p = new DLel; // 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 DLvar::l_pop_front()
{
  if(DLel * p = head)
  {
    if(!(head = p->next))
      tail = NULL;
    else
      head->prev = NULL;
    delete p;
  }
}

// Funkcja wyszukuje element
// i zamienia go z poprzednikiem
//------------------------------
DLel * DLvar::l_find(int v)
{
  DLel *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()
{
  DLvar L; // obiekt listy
  int i, v;

  srand (time(NULL)); // inicjujemy liczby pseudolosowe
  for(i = 9; i >= 0; i--)
    L.l_push_front(i); // tworzymy listę
  cout << "    ";
  L.l_print(10);  // lista początkowa
  for(i = 0; i < 40; i++) // 40 razy wyszukujemy element
  {
    v = rand()%10; // losujemy elementy 0…9
    cout << v << ":  "; // wyświetlamy wylosowany element
    L.l_find(v); // wyszukujemy element
    L.l_print(v); // wyświetlamy listę
  }
  return 0;
}

Basic

' Samoorganizujące się listy
' Wyszukiwanie z przemieszczaniem
' Data: 04.08.2012
' (C)2020 mgr Jerzy Wałaszek
'--------------------------------

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

' Definicja obiektu listy dwukierunkowej
'---------------------------------------
Type DLvar

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

  Declare Constructor()
  Declare Destructor()
  Declare Sub l_print(v As Integer)
  Declare Sub l_push_front(v As Integer)
  Declare Sub l_pop_front()
  Declare Function l_find(v As Integer)_
                          As DLel Ptr
End Type

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

Dim L As DLvar
Dim As Integer i, v

Randomize

For i = 9 To 0 Step -1
  L.l_push_front(i) ' tworzymy listę
Next
Print "    ";
L.l_print(10) ' lista początkowa

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

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

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

' Usuwa listę z pamięci
Destructor DLvar()
  While head
  	 l_pop_front()
  Wend
End Destructor

' Procedura wyświetla zawartość listy
'------------------------------------
Sub DLvar.l_print(v As Integer)
  Dim p As DLel 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 DLvar.l_push_front(v As Integer)
  Dim p As DLel Ptr
  p = new DLel
  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 DLvar.l_pop_front()
  Dim p As DLel 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 DLvar.l_find(v As integer)_
                         As DLel Ptr
  Dim As DLel 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

Python (dodatek)

# Samoorganizujące się listy
# Wyszukiwanie z przemieszczaniem
# Data: 02.06.2024
# (C)2024 mgr Jerzy Wałaszek
# --------------------------------

import random


# klasa elementu listy
# ---------------------
class DLel:


    def __init__(self, data):
        self.next = None
        self.prev = None
        self.data = data


# klasa listy dwukierunkowej
# ---------------------------
class DLvar:


    # Konstruktor
    def __init__(self):
        self.head = None
        self.tail = None


    # Destructor
    def __del__(self):
        while self.head:
            self.l_pop_front()


    # Wyświetla zawartość elementów listy
    def l_print(self, v):
        p = self.head
        while p:
            if p.data == v:
                print("(%1d)" % p.data, end="")
            else:
                print(" %1d " % p.data, end="")
            p = p.next
        print()


    # Dodaje nowy element na początek
    def l_push_front(self, v):
        p = DLel(v)
        p.next = self.head
        self.head = p
        if p.next:
            p.next.prev = p
        else:
            self.tail = p


    # Usuwa pierwszy element
    def l_pop_front(self):
        p = self.head
        if p:
            self.head = p.next
            if not self.head:
                self.tail = None
            else:
                self.head.prev = None
            p = None


    # Funkcja wyszukuje element
    # i zamienia go z poprzednikiem
    # ------------------------------
    def l_find(self, v):
        p = self.head
        while p:  # 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:
                    self.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:
                    self.head = p
                break
            p = p.next


# ---------------
# Program główny
# ---------------

dl = DLvar()
for i in reversed(range(10)):
    # tworzymy listę
    dl.l_push_front(i)
print("    ", end="")
# lista początkowa
dl.l_print(10)
# 40 razy wyszukujemy element
for i in range(40):
    # losujemy elementy 0…9
    v = random.randrange(10)
    # wyświetlamy wylosowany element
    print("%1d:  " % v, end="")
    # wyszukujemy element
    dl.l_find(v)
    # wyświetlamy listę
    dl.l_print(v)

Wynik:

     0  1  2  3  4  5  6  7  8  9
5:   0  1  2  3 (5) 4  6  7  8  9
8:   0  1  2  3  5  4  6 (8) 7  9
6:   0  1  2  3  5 (6) 4  8  7  9
6:   0  1  2  3 (6) 5  4  8  7  9
2:   0 (2) 1  3  6  5  4  8  7  9
6:   0  2  1 (6) 3  5  4  8  7  9
2:  (2) 0  1  6  3  5  4  8  7  9
6:   2  0 (6) 1  3  5  4  8  7  9
5:   2  0  6  1 (5) 3  4  8  7  9
4:   2  0  6  1  5 (4) 3  8  7  9
9:   2  0  6  1  5  4  3  8 (9) 7
8:   2  0  6  1  5  4 (8) 3  9  7
0:  (0) 2  6  1  5  4  8  3  9  7
0:  (0) 2  6  1  5  4  8  3  9  7
8:   0  2  6  1  5 (8) 4  3  9  7
5:   0  2  6 (5) 1  8  4  3  9  7
8:   0  2  6  5 (8) 1  4  3  9  7
9:   0  2  6  5  8  1  4 (9) 3  7
4:   0  2  6  5  8 (4) 1  9  3  7
4:   0  2  6  5 (4) 8  1  9  3  7
5:   0  2 (5) 6  4  8  1  9  3  7
2:  (2) 0  5  6  4  8  1  9  3  7
0:  (0) 2  5  6  4  8  1  9  3  7
2:  (2) 0  5  6  4  8  1  9  3  7
3:   2  0  5  6  4  8  1 (3) 9  7
7:   2  0  5  6  4  8  1  3 (7) 9
8:   2  0  5  6 (8) 4  1  3  7  9
4:   2  0  5  6 (4) 8  1  3  7  9
3:   2  0  5  6  4  8 (3) 1  7  9
5:   2 (5) 0  6  4  8  3  1  7  9
7:   2  5  0  6  4  8  3 (7) 1  9
7:   2  5  0  6  4  8 (7) 3  1  9
1:   2  5  0  6  4  8  7 (1) 3  9
6:   2  5 (6) 0  4  8  7  1  3  9
4:   2  5  6 (4) 0  8  7  1  3  9
8:   2  5  6  4 (8) 0  7  1  3  9
9:   2  5  6  4  8  0  7  1 (9) 3
3:   2  5  6  4  8  0  7  1 (3) 9
8:   2  5  6 (8) 4  0  7  1  3  9
0:   2  5  6  8 (0) 4  7  1  3  9

do podrozdziału do strony

Zaproponuj podobne algorytmy dla list jednokierunkowych.

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.

Samoorganizujące się listy

Problem

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

Algorytm wyszukiwania z przesuwaniem na początek listy

Wejście:

Wyjście:

Elementy pomocnicze:

Lista kroków:

Przykładowe programy

Metoda zliczania (ang. count method)

Algorytm wyszukiwania ze zliczaniem znalezionych elementów i sortowaniem listy

Wejście:

Wyjście:

Elementy pomocnicze:

Lista kroków:

Przykładowe programy

Metoda przemieszczania (ang. transpose method)

Algorytm wyszukiwania z przemieszczaniem elementów

Wejście:

Wyjście:

Elementy pomocnicze:

Lista kroków:

Przykładowe programy

Zadanie