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

Przeszukiwanie liniowe z wartownikiem dla listy dwukierunkowej

SPIS TREŚCI
Tematy pomocnicze
Podrozdziały

Problem

Należy szybko wyszukać na liście dwukierunkowej element zawierający daną o wartości v.

Rozwiązanie

Wyszukiwanie z wartownikiem skraca czas poszukiwań eliminując sprawdzanie 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.

Zmienne pomocnicze:

p  –  wskaźnik elementów listy

Lista kroków:

K01: l_push_back(L, v) na końcu listy umieszczamy wartownika
K02: pL.head w p ustawiamy adres pierwszego elementu listy
K03: Dopóki (pdata) ≠ v, wykonuj p ← (pnext) przeszukujemy listę, aż natrafimy na element zawierający v
K04: Jeśli p = L.tail, to p ← nil jeśli odszukaliśmy wartownika, 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 : dlistVar; v : char) : PdlistEl;
var
  p : PdlistEl;
begin
  l_push_back(L, v); // wstawiamy wartownika na koniec listy
  p := L.head;
  while p^.data <> v do p := p^.next;
  if p = L.tail then p := nil;
  l_pop_back(L);    // usuwamy wartownika
  l_find_first := p;
end;
C++
dlistEl * l_find_first(dlistVar & L, char v)
{
  dlistEl * p;
  l_push_back(L, v);  // wstawiamy wartownika na koniec listy
  p = L.head;
  while(p->data != v) p = p->next;
  if(p == L.tail) p = NULL;
  l_pop_back(L);     // usuwamy wartownika
  return p;  
}
Basic
Function l_find_first(ByRef L As dlistVar, v As String) As dlistEl Ptr
  Dim p As dlistEl Ptr
  l_push_back(L, v)    ' wstawiamy wartownika na koniec listy
  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

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ę find_first oraz zmodyfikowaliśmy nieco metodę printl. 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)2019 mgr Jerzy Wałaszek
//--------------------------------------

program dlist_lssearch;

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

type

  PdlistEl = ^dlistEl;  // wskaźnik do elementów listy

  // Element listy
  //--------------
  dlistEl = record
    next : PdlistEl;   // następnik
    prev : PdlistEl;   // poprzednik
    data : char;
  end;


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

      constructor init;
      destructor  destroy;
      procedure   printl;
      procedure   push_front(v : char);
      procedure   push_back(v : char);
      procedure   insert_before(e : PdlistEl; v : char);
      procedure   insert_after(e : PdlistEl; v : char);
      procedure   remove(e : PdlistEl);
      procedure   pop_front;
      procedure   pop_back;
      function    find_first(v : char) : PdlistEl;
  end;

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

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

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

// Procedura wyświetla zawartość elementów listy
//----------------------------------------------
procedure dlist.printl;
var
  p : PdlistEl;
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 dlist.push_front(v : char);
var
  p : PdlistEl;
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 dlist.push_back(v : char);
var
  p : PdlistEl;
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 dlist.insert_before(e : PdlistEl; v : char);
var
  p : PdlistEl;
begin
  if e = head then 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 dlist.insert_after(e : PdlistEl; v : char);
var
  p : PdlistEl;
begin
  if e = tail then 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 dlist.remove(e : PdlistEl);
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 dlist.pop_front;
begin
  if count > 0 then remove(head);
end;

// Procedura usuwa element z końca listy
//--------------------------------------
procedure dlist.pop_back;
begin
  if count > 0 then remove(tail);
end;

// Wyszukuje pierwsze wystąpienie elementu v
//------------------------------------------
function dlist.find_first(v : char) : PdlistEl;
var
  p : PdlistEl;
begin
  push_back(v);
  p := head;
  while p^.data <> v do p := p^.next;
  if p = tail then p := nil;
  pop_back;
  find_first := p;
end;

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

var

  L : dlist;
  p : PdlistEl;
  i : integer;

begin
  Randomize;
  L.init;
  for i := 1 to 40 do L.push_back(char(65 + random(8)));
  L.printl;
  repeat
    p := L.find_first('A');
    if p <> nil then
    begin
      p^.data := '.';
      L.insert_before(p, '(');
      L.insert_after(p, ')');
      L.printl;
    end;
  until p = nil;
  L.destroy;
end.
C++
// Przeszukiwanie liniowe z wartownikiem
// Data: 17.02.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
  char data;
};

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

    dlist();         // konstruktor
    ~dlist();        // destruktor
    void printl();
    void push_front(char v);
    void push_back(char v);
    void insert_before(dlistEl * e, char v);
    void insert_after(dlistEl * e, char v);
    void remove(dlistEl * e);
    void pop_front();
    void pop_back();
    dlistEl * find_first(char v);
};

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

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

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

// Wyświetla zawartość elementów listy
//----------------------------------------------
void dlist::printl()
{
  dlistEl * 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 dlist::push_front(char v)
{
  dlistEl * p;

  p = new dlistEl;
  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 dlist::push_back(char v)
{
  dlistEl * p;

  p = new dlistEl;
  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 dlist::insert_before(dlistEl * e, char v)
{
  dlistEl * p;

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

// Dodaje nowy element za wybranym
//--------------------------------
void dlist::insert_after(dlistEl * e, char v)
{
  dlistEl * p;

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

// Usuwa wybrany element z listy
//------------------------------
void dlist::remove(dlistEl * 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 dlist::pop_front()
{
  if(count) remove(head);
}

// Usuwa element z końca listy
//----------------------------
void dlist::pop_back()
{
  if(count) remove(tail);
}

// Wyszukuje pierwsze wystąpienie elementu v
//------------------------------------------
dlistEl * dlist::find_first(char v)
{
  dlistEl * p;
  push_back(v);   // wstawiamy wartownika na koniec listy
  p = head;
  while(p->data != v) p = p->next;
  if(p == tail) p = NULL;
  pop_back();     // usuwamy wartownika
  return p;
}

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

int main()
{
  dlist L;
  dlistEl * p;
  int i;

  srand(time(NULL));
  for(i = 0; i < 40; i++) L.push_back(65 + rand() % 8);
  L.printl();
  do
  {
    p = L.find_first('A');
    if(p)
    {
      p->data = '.';
      L.insert_before(p, '(');
      L.insert_after(p, ')');
      L.printl();
    }
  } while(p);

  return 0;
}
Basic
' Przeszukiwanie liniowe z wartownikiem
' Data: 17.02.2012
' (C)2019 mgr Jerzy Wałaszek
'--------------------------------------

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

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

  Declare Constructor()
  Declare Destructor()
  Declare Sub printl()
  Declare Sub push_front(v As String)
  Declare Sub push_back(v As String)
  Declare Sub insert_before(e As dlistEl Ptr, v As String)
  Declare Sub insert_after(e As dlistEl Ptr, v As String)
  Declare Sub remove(e As dlistEl Ptr)
  Declare Sub pop_front()
  Declare Sub pop_back()
  Declare Function find_first(v As String) As dlistEl Ptr
End Type

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

Dim L As dlist
Dim p As dlistEl Ptr
Dim i As Integer

Randomize
For i = 1 To 40: L.push_back(Chr(65 + Int(Rnd() * 8))): Next
L.printl()
Do
  p = L.find_first("A")
  If p Then
    p->data = "."
    L.insert_before(p, "(")
    L.insert_after(p, ")")
    L.printl()
  End If
Loop Until p = 0
End

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

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

' Procedura wyświetla zawartość elementów listy
'----------------------------------------------
Sub dlist.printl()
  Dim p As dlistEl 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 dlist.push_front(v As String)
  Dim p As dlistEl Ptr

  p = New dlistEl
  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 dlist.push_back(v As String)
  Dim p As dlistEl Ptr

  p = New dlistEl
  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 dlist.insert_before(e As dlistEl Ptr, v As String)

  Dim p As dlistEl Ptr

  If e = head Then
    push_front(v)
  Else
    p = New dlistEl
    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 dlist.insert_after(e As dlistEl Ptr, v As String)

  Dim p As dlistEl Ptr

  If e = tail Then
    push_back(v)
  Else
    p = New dlistEl
    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 dlist.remove(e As dlistEl 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 dlist.pop_front()
  If count > 0 Then remove(head)
End Sub

' Procedura usuwa element z końca listy
'--------------------------------------
Sub dlist.pop_back()
  If count > 0 Then remove(tail)
End Sub

' Wyszukuje pierwsze wystąpienie elementu v
'------------------------------------------
Function dlist.find_first(v As String) As dlistEl Ptr
  Dim p As dlistEl Ptr
  push_back(v)    ' wstawiamy wartownika na koniec listy
  p = head
  While p->data <> v
    p = p->next
  Wend
  If p = tail Then p = 0
  pop_back()
  find_first = p
End Function
Wynik:
 40 : CCHFAHBGAAADDEHAGBBHBHABDHDCBADDGHFEBHCB
 42 : CCHF(.)HBGAAADDEHAGBBHBHABDHDCBADDGHFEBHCB
 44 : CCHF(.)HBG(.)AADDEHAGBBHBHABDHDCBADDGHFEBHCB
 46 : CCHF(.)HBG(.)(.)ADDEHAGBBHBHABDHDCBADDGHFEBHCB
 48 : CCHF(.)HBG(.)(.)(.)DDEHAGBBHBHABDHDCBADDGHFEBHCB
 50 : CCHF(.)HBG(.)(.)(.)DDEH(.)GBBHBHABDHDCBADDGHFEBHCB
 52 : CCHF(.)HBG(.)(.)(.)DDEH(.)GBBHBH(.)BDHDCBADDGHFEBHCB
 54 : CCHF(.)HBG(.)(.)(.)DDEH(.)GBBHBH(.)BDHDCB(.)DDGHFEBHCB
Na początek:  podrozdziału   strony 

Zadanie

Zaproponuj algorytm wyszukujący ostatni element z daną v.

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.