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

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)2019 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)2019 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)2019 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 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  
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
©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.