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

©2020 mgr Jerzy Wałaszek
I LO w Tarnowie

Liniowe przeszukiwanie listy

SPIS TREŚCI
Tematy pomocnicze
Podrozdziały

Problem

Należy znaleźć element listy, który zawiera określone dane.

Rozwiązanie dla listy niecyklicznej

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

Zmienne pomocnicze:

p  –  wskazanie elementu listy

Lista kroków:

K01: p  ← head ustawiamy wskaźnik na pierwszy element listy
K02: Dopóki ( p  ≠ nil ) obrazek ( ( p→data  ) ≠ v  ),
wykonuj p  ← ( p→next  )		 przeszukujemy listę aż do znalezienia v lub napotkania końca listy
K03: Zakończ z wynikiem p  
Pascal
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;
C++
slistEl * find_first ( slistEl * head; char v )
{
  slistEl * p = head;
  while( p && p->data != v ) p = p->next;
  return p;
}
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

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 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.
Pascal
// Liniowe przeszukiwanie listy
// Data: 12.02.2012
// (C)2020 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.
C++
// Liniowe przeszukiwanie listy
// Data: 12.02.2012
// (C)2020 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;
}
Basic
' Liniowe przeszukiwanie listy
' Data: 12.02.2012
' (C)2020 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
Na początek:  podrozdziału   strony 

Rozwiązanie dla listy cyklicznej

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 daną o wartości v  lub adres zerowy, jeśli lista takiego elementu nie posiada

Zmienne pomocnicze:

p  –  wskazanie elementu listy

Lista kroków:

K01: p  ← head ustawiamy wskaźnik na pierwszy element listy
K02: Dopóki ( p  ≠ nil ) obrazek ( ( p→data  ) ≠ v  ),
wykonuj kroki K03...K04		 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  
Pascal
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;
C++
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;
}
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
Na początek:  podrozdziału   strony 

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.
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
©2020 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.