Liniowe przeszukiwanie listy


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

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:
p  –  wskazanie elementu listy
Lista kroków:
K01: phead ; ustawiamy wskaźnik na pierwszy element listy
K02: Dopóki (p ≠ nil) obrazek ((pdata) ≠ v), wykonuj p ← (pnext) ; 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:
p  –  wskazanie elementu listy
Lista kroków:
K01: phead ; ustawiamy wskaźnik na pierwszy element listy
K02: Dopóki (p ≠ nil) obrazek ((pdata) ≠ v), wykonuj K03... ; przeszukujemy listę
K03:     p ← (pnext) ; 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

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

 


   I Liceum Ogólnokształcące   
im. Kazimierza Brodzińskiego
w Tarnowie

©2019 mgr Jerzy Wałaszek

Dokument ten rozpowszechniany jest zgodnie z zasadami licencji
GNU Free Documentation License.

Pytania proszę przesyłać na adres email: i-lo@eduinf.waw.pl

W artykułach serwisu są używane cookies. Jeśli nie chcesz ich otrzymywać,
zablokuj je w swojej przeglądarce.
Informacje dodatkowe