Algorytmy i Struktury Danych - Przeszukiwanie liniowe z wartownikiem dla listy dwukierunkowej

Wyszukiwanie z wartownikiem skraca czas poszukiwań eliminując sprawdzanie przy każdym elemencie warunku osiągnięcia końca listy. Jeśli lista jest bardzo długa, to postępujemy następująco. Na koniec listy dodajemy chwilowo element z poszukiwaną daną v. Dzięki temu zapewniamy, że na liście na pewno jest poszukiwany element – nasz wartownik. Teraz upraszczamy przejście przez poszczególne elementy listy, sprawdzając jedynie, czy spełniają one kryterium poszukiwań. Gdy znajdziemy odpowiedni element, to sprawdzamy, czy jest wartownikiem – jeśli tak, poszukiwanego elementu nie było na liście. Jeśli nie, to znaleźliśmy nasz element. Po tej operacji wartownika należy usunąć z listy.

Algorytm przeszukiwania liniowego z wartownikiem dla listy dwukierunkowej

Wejście:

L : zmienna obsługująca listę.
v : poszukiwana dana.

Wyjście:

Adres elementu listy, który zawiera v lub adres zerowy w przypadku, gdy takiego elementu nie ma na liście.

Elementy pomocnicze:

p : wskaźnik elementów listy.
l_push_back(L, v) : umieszcza element na końcu listy.
l_pop_back(L) : usuwa ostatni element listy.

Lista kroków:

K01: l_push_back(L, v) ; na końcu listy umieszczamy wartownika
K02: p ← L.head ; w p ustawiamy adres pierwszego elementu listy
K03: Dopóki p→data ≠ v, ; przeszukujemy listę, aż natrafimy
     wykonuj p ← p→next ; na element zawierający v
K04: Jeśli p = L.tail, ; jeśli odszukaliśmy wartownika, 
     to p ← nil        ; to poszukiwanego elementu na liście nie ma
K05: l_pop_back(L) ; usuwamy wartownika z listy
K06: Zakończ z wynikiem p

Pascal

function l_find_first(var L : DLvar;
                          v : char)
                          : PDLel;
var
  p : PDLel;
begin
  l_push_back(L, v);
  p := L.head;
  while p^.data <> v do
    p := p^.next;
  if p = L.tail then
    p := nil;
  l_pop_back(L);
  l_find_first := p;
end;

C++

DLel * l_find_first(DLvar & L, 
                       char v)
{
  DLel * p;
  l_push_back(L, v);
  p = L.head;
  while(p->data != v)
    p = p->next;
  if(p == L.tail)
    p = NULL;
  l_pop_back(L);
  return p; 
}

Basic

Function l_find_first(ByRef L As DLvar, _
                            v As String) _
                            As DLel Ptr
  Dim p As DLel Ptr
  l_push_back(L, v)
  p = L.head
  While p->data <> v
    p = p->next
  Wend
  If p = L.tail Then _
    p = 0
  l_pop_back(L)
  l_find_first = p
End Function

Python (dodatek)

# 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
        self.count = 0


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


    # Dodaje nowy element na koniec
    def l_push_back(self, v):
        p = DLel(v)
        p.prev = self.tail
        self.tail = p
        self.count += 1
        if p.prev:
            p.prev.next = p
        else:
            self.head = p


    # Usuwa wybrany element
    def l_remove(self, e):
        self.count -= 1
        if e.prev:
            e.prev.next = e.next
        else:
            self.head = e.next
        if e.next:
            e.next.prev = e.prev
        else:
            self.tail = e.prev
        e = None


    # Usuwa element z końca
    def l_pop_back(self):
        if self.count:
            self.l_remove(self.tail)


    # Wyszukuje v
    def l_find_first(self, v):
        self.l_push_back(v)
        p = self.head
        while p.data != v:
            p = p.next
        if p is self.tail:
            p = None
        self.l_pop_back()
        return 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 wykorzystuje obiekt listy dwukierunkowej, w którym dodaliśmy metodę l_find_first( ) oraz zmodyfikowaliśmy nieco metodę l_print( ). Tworzona jest lista 40 przypadkowych znaków od A do G. Następnie na liście wyszukiwane są elementy zawierające znak A. Znak ten zostaje zastąpiony znakiem kropki. Następnie z lewej strony wstawiany jest znak (, a z prawej znak ). Po każdej modyfikacji zawartość listy jest wyświetlana.

Pascal

// Przeszukiwanie liniowe z wartownikiem
// Data: 17.02.2012
// (C)2020 mgr Jerzy Wałaszek
//--------------------------------------

program dlist_lssearch;

// Definicje typów
//----------------

type

  PDLel = ^DLel; // wskaźnik do elementów listy

  // Element listy
  //--------------
  DLel = record
    next : PDLel; // następnik
    prev : PDLel; // poprzednik
    Data: char;
  end;

// Definicja obiektu listy dwukierunkowej
//---------------------------------------
  DLvar = object
    public
      head  : PDLel; // początek listy
      tail  : PDLel; // koniec listy
      count : cardinal; // licznik elementów

      constructor init;
      destructor  destroy;
      procedure   l_print;
      procedure   l_push_front(v : char);
      procedure   l_push_back(v : char);
      procedure   l_insert_before(e : PDLel; v : char);
      procedure   l_insert_after(e : PDLel; v : char);
      procedure   l_remove(e : PDLel);
      procedure   l_pop_front;
      procedure   l_pop_back;
      function    l_find_first(v : char) : PDLel;
  end;

//---------------------------------------------
// Definicje metod obiektu listy dwukierunkowej
//---------------------------------------------

// Inicjuje pola zmiennej listy
//-----------------------------
constructor DLvar.init;
begin
  head  := nil;
  tail  := nil;
  count := 0;
end;

// Usuwa elementy listy
//---------------------
destructor DLvar.destroy;
begin
  while count > 0 do
    l_pop_front;
end;

// Procedura wyświetla zawartość elementów listy
//----------------------------------------------
procedure DLvar.l_print;
var
  p : PDLel;
begin
  write(count:3, ' : ');
  p := head;
  while p <> NIL do
  begin
    write(p^.data);
    p := p^.next;
  end;
  writeln;
end;

// Procedura dodaje nowy element na początek listy
//------------------------------------------------
procedure DLvar.l_push_front(v : char);
var
  p : PDLel;
begin
  new (p); // tworzymy nowy element
  p^.Data:= v;
  p^.prev := nil;
  p^.next := head;
  head  := p;
  inc(count);
  if p^.next <> nil then
    p^.next^.prev := p
  else tail := p;
end;

// Procedura dodaje nowy element na koniec listy
//----------------------------------------------
procedure DLvar.l_push_back(v : char);
var
  p : PDLel;
begin
  new(p); // tworzymy nowy element
  p^.Data:= v;
  p^.next := nil;
  p^.prev := tail;
  tail    := p;
  inc(count);
  if p^.prev <> nil then
    p^.prev^.next := p
  else head := p;
end;

// Procedura dodaje nowy element przed wybranym
//---------------------------------------------
procedure DLvar.l_insert_before(e : PDLel;
                                   v : char);
var
  p : PDLel;
begin
  if e = head then
    l_push_front(v)
  else
  begin
    new(p);
    p^.Data:= v;
    p^.next := e;
    p^.prev := e^.prev;
    inc(count);
    e^.prev^.next := p;
    e^.prev := p;
  end;
end;

// Procedura dodaje nowy element za wybranym
//------------------------------------------
procedure DLvar.l_insert_after(e : PDLel;
                                  v : char);
var
  p : PDLel;
begin
  if e = tail then
    l_push_back(v)
  else
  begin
    new(p);
    p^.Data:= v;
    p^.next := e^.next;
    p^.prev := e;
    inc(count);
    e^.next^.prev := p;
    e^.next := p;
  end;
end;

// Procedura usuwa wybrany element z listy
//----------------------------------------
procedure DLvar.l_remove(e : PDLel);
begin
  dec(count);
  if e^.prev <> nil then
    e^.prev^.next := e^.next
  else
    head := e^.next;
  if e^.next <> nil then
    e^.next^.prev := e^.prev
  else
    tail := e^.prev;
  dispose(e);
end;

// Procedura usuwa element z początku listy
//-----------------------------------------
procedure DLvar.l_pop_front;
begin
  if count > 0 then
    l_remove(head);
end;

// Procedura usuwa element z końca listy
//--------------------------------------
procedure DLvar.l_pop_back;
begin
  if count > 0 then
    l_remove(tail);
end;

// Wyszukuje pierwsze wystąpienie elementu v
//------------------------------------------
function DLvar.l_find_first(v : char) : PDLel;
var
  p : PDLel;
begin
  l_push_back(v);
  p := head;
  while p^.data <> v do
    p := p^.next;
  if p = tail then
    p := nil;
  l_pop_back;
  l_find_first := p;
end;

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

var

  L : DLvar;
  p : PDLel;
  i : integer;

begin
  Randomize;
  L.init;
  for i := 1 to 40 do
    L.l_push_back(char(65+random(8)));
  L.l_print;
  repeat
    p := L.l_find_first('A');
    if p <> nil then
    begin
      p^.Data:= '.';
      L.l_insert_before(p, '(');
      L.l_insert_after(p, ')');
      L.l_print;
    end;
  until p = nil;
  L.destroy;
end.

C++

// Wyszukiwanie liniowe z wartownikiem
// Data: 17.02.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
  char data;
};

// Definicja obiektu listy dwukierunkowej
//---------------------------------------
class DLvar
{
  public:
    DLel * head; // początek listy
    DLel * tail; // koniec listy
    unsigned count; // licznik elementów

    DLvar();  // konstruktor
    ~DLvar(); // destruktor
    void l_print();
    void l_push_front(char v);
    void l_push_back(char v);
    void l_insert_before(DLel * e, char v);
    void l_insert_after(DLel * e, char v);
    void l_remove(DLel * e);
    void l_pop_front();
    void l_pop_back();
    DLel * l_find_first (char v);
};

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

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

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

// Wyświetla zawartość elementów listy
//------------------------------------
void DLvar::l_print()
{
  DLel * p;

  cout << setw(3) << count << ": ";
  p = head;
  while(p)
  {
    cout << p->data;
    p = p->next;
  }
  cout << endl;
}

// Dodaje nowy element na początek listy
//--------------------------------------
void DLvar::l_push_front(char v)
{
  DLel * p;

  p = new DLel;
  p->data = v;
  p->prev = NULL;
  p->next = head;
  head  = p;
  count++;
  if(p->next)
    p->next->prev = p;
  else
    tail = p;
}

// Dodaje nowy element na koniec listy
//------------------------------------
void DLvar::l_push_back(char v)
{
  DLel * p;

  p = new DLel;
  p->data = v;
  p->next = NULL;
  p->prev = tail;
  tail  = p;
  count++;
  if(p->prev)
    p->prev->next = p;
  else
    head = p;
}

// Dodaje nowy element przed wybranym
//-----------------------------------
void DLvar::l_insert_before(DLel * e, 
                               char v)
{
  DLel * p;

  if(e == head)
    l_push_front(v);
  else
  {
    p = new DLel;
    p->data = v;
    p->next = e;
    p->prev = e->prev;
    count++;
    e->prev->next = p;
    e->prev = p;
  }
}

// Dodaje nowy element za wybranym
//--------------------------------
void DLvar::l_insert_after(DLel * e, 
                           char v)
{
  DLel * p;

  if(e == tail)
    l_push_back(v);
  else
  {
    p = new DLel;
    p->data = v;
    p->next = e->next;
    p->prev = e;
    count++;
    e->next->prev = p;
    e->next = p;
  }
}

// Usuwa wybrany element z listy
//------------------------------
void DLvar::l_remove(DLel * e)
{
  count--;
  if(e->prev)
    e->prev->next = e->next;
  else
    head = e->next;
  if(e->next)
    e->next->prev = e->prev;
  else
    tail = e->prev;
  delete e;
}

// Usuwa element z początku listy
//-------------------------------
void DLvar::l_pop_front()
{
  if(count)
    l_remove(head);
}

// Usuwa element z końca listy
//----------------------------
void DLvar::l_pop_back()
{
  if(count)
    l_remove(tail);
}

// Wyszukuje pierwsze wystąpienie
// elementu v
//-------------------------------
DLel * DLvar::l_find_first(char v)
{
  DLel * p;
  l_push_back(v); // wstawiamy wartownika
  p = head;
  while(p->data != v)
    p = p->next;
  if(p == tail)
    p = NULL;
  l_pop_back(); // usuwamy wartownika
  return p;
}

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

int main()
{
  DLvar L;
  DLel * p;
  int i;

  srand(time(NULL));
  for(i = 0; i < 40; i++)
    L.l_push_back(65+rand()%8);
  L.l_print();
  do
  {
    p = L.l_find_first('A');
    if(p)
    {
      p->data = '.';
      L.l_insert_before(p, '(');
      L.l_insert_after(p, ')');
      L.l_print();
    }
  } while(p);

  return 0;
}

Basic

' Przeszukiwanie liniowe z wartownikiem
' Data: 17.02.2012
' (C)2020 mgr Jerzy Wałaszek
'--------------------------------------

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

' Typ obiektowy listy dwukierunkowej
'-----------------------------------
Type DLvar
  head As DLel Ptr ' początek listy
  tail As DLel Ptr ' koniec listy
  count As UInteger   ' licznik elementów

  Declare Constructor()
  Declare Destructor()
  Declare Sub l_print()
  Declare Sub l_push_front(v As String)
  Declare Sub l_push_back(v As String)
  Declare Sub l_insert_before(e As DLel Ptr, v As String)
  Declare Sub l_insert_after(e As DLel Ptr, v As String)
  Declare Sub l_remove(e As DLel Ptr)
  Declare Sub l_pop_front()
  Declare Sub l_pop_back()
  Declare Function l_find_first(v As String) As DLel Ptr
End Type

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

Dim L As DLvar
Dim p As DLel Ptr
Dim i As Integer

Randomize
For i = 1 To 40
  L.l_push_back(Chr(65+Int(Rnd()*8)))
Next
L.l_print()
Do
  p = L.l_find_first("A")
  If p Then
    p->data = "."
    L.l_insert_before(p, "(")
    L.l_insert_after(p, ")")
    L.l_print()
  End If
Loop Until p = 0
End

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

' Usuwa listę z pamięci
Destructor DLvar()
  While count > 0
    l_pop_front()
  Wend
End Destructor

' Procedura wyświetla zawartość elementów listy
'----------------------------------------------
Sub DLvar.l_print()
  Dim p As DLel Ptr

  Print Using "### : ";count;
  p = head
  while p
    Print p->Data;
    p = p->next
  Wend
  Print
End Sub

' Procedura dodaje nowy element na początek listy
'------------------------------------------------
Sub DLvar.l_push_front(v As String)
  Dim p As DLel Ptr

  p = New DLel
  p->data = v
  p->prev = 0
  p->next = head
  head  = p
  count += 1
  If p->next Then
    p->next->prev = p
  Else
    tail = p
  End If
End Sub

' Procedura dodaje nowy element na koniec listy
'----------------------------------------------
Sub DLvar.l_push_back(v As String)
  Dim p As DLel Ptr

  p = New DLel
  p->data = v
  p->next = 0
  p->prev = tail
  tail  = p
  count += 1
  If p->prev Then
    p->prev->next = p
  Else
    head = p
  End If
End Sub

' Procedura dodaje nowy element przed wybranym
'---------------------------------------------
Sub DLvar.l_insert_before(e As DLel Ptr, _
                             v As String)
  Dim p As DLel Ptr

  If e = head Then
    l_push_front(v)
  Else
    p = New DLel
    p->data = v
    p->next = e
    p->prev = e->prev
    count += 1
    e->prev->next = p
    e->prev = p
  End If
End Sub

' Procedura dodaje nowy element za wybranym
'------------------------------------------
Sub DLvar.l_insert_after(e As DLel Ptr, _
                            v As String)
  Dim p As DLel Ptr

  If e = tail Then
    l_push_back(v)
  Else
    p = New DLel
    p->data = v
    p->next = e->next
    p->prev = e
    count += 1
    e->next->prev = p
    e->next = p
  End If
End Sub

' Procedura usuwa wybrany element z listy
'----------------------------------------
Sub DLvar.l_remove(e As DLel Ptr)
  count -= 1
  If e->prev Then
    e->prev->next = e->next
  Else
    head = e->next
  End If
  If e->next Then
    e->next->prev = e->prev
  Else
    tail = e->prev
  End If
  Delete e
End Sub

' Procedura usuwa element z początku listy
'-----------------------------------------
Sub DLvar.l_pop_front()
  If count > 0 Then _
    l_remove(head)
End Sub

' Procedura usuwa element z końca listy
'--------------------------------------
Sub DLvar.l_pop_back()
  If count > 0 Then _
    l_remove(tail)
End Sub

' Wyszukuje pierwsze wystąpienie elementu v
'------------------------------------------
Function DLvar.l_find_first(v As String)_
                               As DLel Ptr
  Dim p As DLel Ptr
  l_push_back(v) ' wstawiamy wartownika
  p = head
  While p->data <> v
    p = p->next
  Wend
  If p = tail Then _
    p = 0
  l_pop_back() ' usuwamy wartownika
  l_find_first = p
End Function

Python (dodatek)

# Wyszukiwanie liniowe z wartownikiem
# Data: 14.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
        self.count = 0


    # Destruktor
    def __del__(self):
        while self.count:
            self.l_pop_front()


    # Wyświetla zawartość listy
    def l_print(self):
        print("%3d: " % self.count, end="")
        p = self.head
        while p:
            print(p.data, end="")
            p = p.next
        print()


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


    # Dodaje nowy element na koniec
    def l_push_back(self, v):
        p = DLel(v)
        p.prev = self.tail
        self.tail = p
        self.count += 1
        if p.prev:
            p.prev.next = p
        else:
            self.head = p


    # Dodaje nowy element przed
    def l_insert_before(self, e, v):
        if e is self.head:
            self.l_push_front(v)
        else:
            p = DLel(v)
            p.next = e
            p.prev = e.prev
            self.count += 1
            e.prev.next = p
            e.prev = p


    # Dodaje nowy element za
    def l_insert_after(self, e, v):
        if e is self.tail:
            self.l_push_back(v)
        else:
            p = DLel(v)
            p.next = e.next
            p.prev = e
            self.count += 1
            e.next.prev = p
            e.next = p


    # Usuwa wybrany element
    def l_remove(self, e):
        self.count -= 1
        if e.prev:
            e.prev.next = e.next
        else:
            self.head = e.next
        if e.next:
            e.next.prev = e.prev
        else:
            self.tail = e.prev
        e = None


    # Usuwa element z początku
    def l_pop_front(self):
        if self.count:
            self.l_remove(self.head)


    # Usuwa element z końca
    def l_pop_back(self):
        if self.count:
            self.l_remove(self.tail)


    # Wyszukuje pierwsze wystąpienie
    def l_find_first(self, v):
        self.l_push_back(v) # wartownik
        p = self.head
        while p.data != v:
            p = p.next
        if p is self.tail:
            p = None
        self.l_pop_back() # wartownik
        return p


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

dl = DLvar()
for i in range(40):
    dl.l_push_back(chr(random.randrange(65, 73)))
dl.l_print()
while True:
    p = dl.l_find_first('A')
    if p:
        p.data = '.'
        dl.l_insert_before(p, '(')
        dl.l_insert_after(p, ')')
        dl.l_print()
    else:
        break

Wynik:

 40 : FBGEECAFAFDFAGFADEHBFEGACDECHGFAAHBEFBGH
 42 : FBGEEC(.)FAFDFAGFADEHBFEGACDECHGFAAHBEFBGH
 44 : FBGEEC(.)F(.)FDFAGFADEHBFEGACDECHGFAAHBEFBGH
 46 : FBGEEC(.)F(.)FDF(.)GFADEHBFEGACDECHGFAAHBEFBGH
 48 : FBGEEC(.)F(.)FDF(.)GF(.)DEHBFEGACDECHGFAAHBEFBGH
 50 : FBGEEC(.)F(.)FDF(.)GF(.)DEHBFEG(.)CDECHGFAAHBEFBGH
 52 : FBGEEC(.)F(.)FDF(.)GF(.)DEHBFEG(.)CDECHGF(.)AHBEFBGH
 54 : FBGEEC(.)F(.)FDF(.)GF(.)DEHBFEG(.)CDECHGF(.)(.)HBEFBGH

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.

Przeszukiwanie liniowe z wartownikiem dla listy dwukierunkowej

Problem