Algorytmy i Struktury Danych - Liniowe przeszukiwanie listy

Problem

Znaleźć element listy, który zawiera określone dane.

Zadanie rozwiązujemy algorytmem wyszukiwania liniowego (ang. linear search algorithm). Przeglądamy kolejne elementy listy, aż napotkamy poszukiwany element lub koniec listy (w przypadku listy cyklicznej – aż wrócimy z powrotem do punktu wejścia). Zwracamy adres znalezionego elementu lub zero w przypadku nie odnalezienia poszukiwanego elementu.

Algorytm wyszukiwania liniowego na liście niecyklicznej

Wejście

head	–	zawiera adres pierwszego elementu listy
v	–	poszukiwana wartość

Wyjście:

adres elementu listy, który zawiera v lub adres zerowy, jeśli lista takiego elementu nie posiada

Elementy pomocnicze:

–

wskazanie elementu listy

Lista kroków:

K01:	p ← head	; ustawiamy wskaźnik na pierwszy element listy
K02:	Dopóki (p ≠ nil) ((p→data) ≠ v), wykonuj p ← (p→next)	; przeszukujemy listę aż do znalezienia v lub napotkania końca listy
K03:	Zakończ z wynikiem p

Lazarus

function find_first(head : PslistEl; v : char) : PslistEl;
var
  p : PslistEl;
begin
  p := head;
  while (p <> nil) and (p^.data <> v) do p := p^.next;
  find_first := p;
end;

Code::Blocks

slistEl * find_first(slistEl * head; char v)
{
  slistEl * p = head;
  while(p && p->data != v) p = p->next;
  return p;
}

Free Basic

Function find_first(head As slistEl Ptr, v As String) As slistEl Ptr
  Dim p As slistEl Ptr = head
  While (p <> 0) AndAlso (p->data <> v)
    p = p->next
  Wend
  find_first = p
End Function

Program

Ważne:

Zanim uruchomisz program, przeczytaj wstęp do tego artykułu, w którym wyjaśniamy funkcje tych programów oraz sposób korzystania z nich.

Program tworzy listę jednokierunkową o długości 40 elementów. Na liście umieszcza przypadkowe znaki od A do G. Następnie kolejno wyszukuje wszystkie elementy zawierające A i zastępuje te dane znakiem kropki. Aby skrócić program, w obiekcie listy pozostawiliśmy tylko niezbędne metody.

Lazarus

// Liniowe przeszukiwanie listy
// Data: 12.02.2012
// (C)2012 mgr Jerzy Wałaszek
//-------------------------------------------

program linear_search;

// Typ elementów listy
//--------------------
type
  PslistEl = ^slistEl;

  slistEl =  record
    next  : PslistEl;
    data  : char;
  end;

// Definicja typu obiektowego slist
//---------------------------------

  slist = object
    public
      head : PslistEl;  // początek listy

      constructor init;
      destructor  destroy;
      procedure   printl;
      procedure   push_front(v : char);
      procedure   pop_front;
      function    find_first(v : char) : PslistEl;
  end;

//---------------------
// Metody obiektu slist
//---------------------

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

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

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

// Procedura dołączania na początek listy
//---------------------------------------
procedure slist.push_front(v : char);
var
  p : PslistEl;
begin
  new(p);
  p^.next := head;
  p^.data := v;
  head    := p;
end;

// Procedura usuwa pierwszy element
//---------------------------------
procedure slist.pop_front;
var
  p : PslistEl;
begin
  p := head;
  if p <> nil then
  begin
    head := p^.next;
    dispose(p);
  end;
end;

// Wyszukuje pierwszy element listy o danej zawartości
//----------------------------------------------------
function slist.find_first(v : char) : PslistEl;
var
  p : PslistEl;
begin
  p := head;
  while (p <> nil) and (p^.data <> v) do p := p^.next;
  find_first := p;
end;

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

var
  L : slist;    // obiekt listy jednokierunkowej
  p : PslistEl; // do wskazywania elementów listy
  i : integer;

begin
  randomize; // inicjujemy generator liczb pseudolosowych
  L.init;    // inicjujemy obiekt

  // Tworzymy listę o 40 elementach. Kazdy element przechowuje
  // przypadkową literę od A do G

  for i := 1 to 40 do L.push_front(char(65+random(7)));
  L.printl;

  // Na liście wyszukujemy literki A i zastępujemy je znakiem #

  repeat
    p := L.find_first('A');
    if p <> nil then
    begin
      p^.data := '.';
      L.printl;
    end;
  until p = nil;

  L.destroy;
end.

Code::Blocks

// Liniowe przeszukiwanie listy
// Data: 12.02.2012
// (C)2012 mgr Jerzy Wałaszek
//-------------------------------------------

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

using namespace std;

// Typ elementów listy
//--------------------
struct slistEl
{
  slistEl * next;
  char data;
};

// Definicja typu obiektowego slist
//---------------------------------

class slist
{
  public:
    slistEl * head;

    slist();  // konstruktor
    ~slist(); // destruktor
    void printl();
    void push_front(char v);
    void pop_front();
    slistEl * find_first(char v);
};

// Konstruktor listy
//------------------
slist::slist()
{
  head = NULL;
}

// Destruktor listy
//-----------------
slist::~slist()
{
  while(head) pop_front();
}

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

// Procedura dołączania na początek listy
//---------------------------------------
void slist::push_front(char v)
{
  slistEl * p;

  p = new slistEl;
  p->next = head;
  p->data = v;
  head = p;
}

// Procedura usuwa pierwszy element
//---------------------------------
void slist::pop_front()
{
  slistEl * p = head; // zapamiętujemy początek

  if(p)
  {
    head = p->next;   // nowy początek
    delete p;         // usuń element z pamięci
  }
}

// Wyszukuje pierwszy element listy o danej zawartości
//----------------------------------------------------
slistEl * slist::find_first(char v)
{
  slistEl * p = head;
  while(p && p->data != v) p = p->next;
  return p;
}

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

int main()
{
  slist L;     // obiekt listy jednokierunkowej
  slistEl * p; // do wskazywania elementów listy
  int i;

  srand(time(NULL)); // inicjujemy generator liczb pseudolosowych

  // Tworzymy listę o 40 elementach. Kazdy element przechowuje
  // przypadkową literę od A do G

  for(i = 0; i < 40; i++) L.push_front(65 + rand() % 7);
  L.printl();

  // Na liście wyszukujemy literki A i zastępujemy je znakiem #

  do
  {
    p = L.find_first('A');
    if(p)
    {
      p->data = '.';
      L.printl();
    }
  } while(p);

  return 0;
}

Free Basic

' Liniowe przeszukiwanie listy
' Data: 12.02.2012
' (C)2012 mgr Jerzy Wałaszek
'-------------------------------------------

' Typ elementów listy
'--------------------
Type slistEl
  next As slistEl Ptr
  data As String * 1
End Type

' Typ obiektowy slist
'------------------------------
Type slist
  head As slistEl Ptr
  
  Declare Constructor()
  Declare Destructor()
  Declare Sub printl()
  Declare Sub push_front(v As String)
  Declare Sub pop_front()
  Declare Function find_first(v As String) As slistEl Ptr
End Type

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

Dim L As slist       ' zawiera adres początku listy
Dim p As slistEl Ptr ' do wskazywania elementów listy  
Dim i As Integer

Randomize    ' inicjujemy generator liczb pseudolosowych

' Tworzymy listę o 40 elementach. Kazdy element przechowuje
' przypadkową literę od A do G

For i = 1 To 40
  L.push_front(Chr(65 + Int(Rnd * 7)))
Next
L.printl()

' Na liście wyszukujemy literki A i zastępujemy je znakiem #

Do
  p = L.find_first("A")
  If p Then
    p->data = "."
    L.printl()
  End If
Loop Until p = 0
End

' Konstruktor listy
'-------------------
Constructor slist()
  head = 0
End Constructor

' Destruktor listy
'-----------------
Destructor slist()
  While head
    pop_front()
  Wend
End Destructor

' Procedura wyświetla zawartość elementów listy
'----------------------------------------------
Sub slist.printl()
  Dim p As slistEl Ptr = head
  While p
    Print p->Data;" ";
    p = p->next
  Wend
  Print
End Sub

' Procedura dołączania na początek listy
'---------------------------------------
Sub slist.push_front(v As String)
  Dim p As slistEl Ptr = new slistEl
  p->next = head
  p->data = v
  head = p
End Sub

' Procedura usuwa pierwszy element
'---------------------------------
Sub slist.pop_front()
  Dim p As slistEl Ptr = head
  If p Then
    head = p->next  ' nowy początek
    Delete p        ' usuń element z pamięci
  End If
End Sub

' Wyszukuje pierwszy element listy o danej zawartości
'----------------------------------------------------
Function slist.find_first(v As String) As slistEl Ptr
  Dim p As slistEl Ptr = head
  While (p <> 0) AndAlso (p->data <> v)
    p = p->next
  Wend
  find_first = p
End Function

Wynik

D B G F B E F G A F F A G D A B B D G G C D D G B F C D C F F B C F D A F B B G

D B G F B E F G . F F A G D A B B D G G C D D G B F C D C F F B C F D A F B B G

D B G F B E F G . F F . G D A B B D G G C D D G B F C D C F F B C F D A F B B G

D B G F B E F G . F F . G D . B B D G G C D D G B F C D C F F B C F D A F B B G

D B G F B E F G . F F . G D . B B D G G C D D G B F C D C F F B C F D . F B B G

Algorytm wyszukiwania liniowego na liście cyklicznej

Wejście

head	–	zawiera adres punktu wejścia
v	–	poszukiwana wartość

Wyjście:

adres elementu listy, który zawiera v lub adres zerowy, jeśli lista takiego elementu nie posiada

Elementy pomocnicze:

–

wskazanie elementu listy

Lista kroków:

K01:	p ← head	; ustawiamy wskaźnik na pierwszy element listy
K02:	Dopóki (p ≠ nil) ((p→data) ≠ v), wykonuj K03...	; przeszukujemy listę
K03:	p ← (p→next)	; przechodzimy do następnika
K04:	Jeśli p = head, to p ← nil	; jeśli obiegliśmy całą listę, to zerujemy p, co spowoduje wyjście z pętli
K05:	Zakończ z wynikiem p

Lazarus

function find_first(head : PslistEl; v : char) : PslistEl;
var
  p : PslistEl;
begin
  p := head;
  while (p <> nil) and (p^.data <> v) do
  begin
    p := p^.next;
    if p = head then p := nil;
  end;
  find_first := p;
end;

Code::Blocks

slistEl * find_first(slistEl * head; char v)
{
  slistEl * p = head;
  while(p && p->data != v)
  {
    p = p->next;
    if(p == head) p = NULL;
  }
  return p;
}

Free Basic

Function find_first(head As slistEl Ptr, v As String) As slistEl Ptr
  Dim p As slistEl Ptr = head
  While (p <> 0) AndAlso (p->data <> v)
    p = p->next
    If p = head Then p = 0
  Wend
  find_first = p
End Function

Zadania

Zaproponuj algorytm znajdowania następnego wystąpienia danej v na liście.
Zaproponuj algorytm wyszukiwania ostatniego wystąpienia danej v na liście niecyklicznej.
Zaproponuj algorytm wyszukiwania ostatniego wystąpienia danej v na liście cyklicznej jednokierunkowej.

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