Algorytmy i Struktury Danych - Liniowe przeszukiwanie listy

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: p ← head ; ustawiamy wskaźnik na pierwszy element listy
K02: Dopóki p ≠ nil  p→data ≠ v, ; przeszukujemy listę
     wykonuj p ← p→next ; aż do znalezienia v lub napotkania
     ; końca listy
K03: Zakończ z wynikiem p

Pascal

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

C++

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

Basic

Function l_find_first(head As SLel Ptr, _
                      v As String)_
                      As SLel Ptr
  Dim p As SLel Ptr = head
  while(p <> 0) AndAlso (p->data <> v)
    p = p->next
  Wend
  l_find_first = p
End Function

Python (dodatek)

# klasa elementu listy jednokierunkowej
class SLel:


    def __init__(self, data):
        self.next = None
        self.data = data

# klasa listy jednokierunkowej
class SLvar:


    def __init__(self):
        self.head = None

    # pierwsze wystąpienie
    def l_find_first(self, v):
        p = self.head
        while p and (p.data != v):
            p = p.next
        return p

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 60 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
  PSLel = ^SLel;

  SLel =  record
    next  : PSLel;
    data  : char;
  end;

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

  SLvar = object
    public
      head : PSLel;  // początek listy

      constructor init;
      destructor  destroy;
      procedure   l_print;
      procedure   l_push_front(v : char);
      procedure   l_pop_front;
      function    l_find_first(v : char) : PSLel;
  end;

//------------------------
// Metody obiektu SLvar
//------------------------

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

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

// Procedura wyświetla zawartość elementów listy
//----------------------------------------------
procedure SLvar.l_print;
var
  p : PSLel;
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 SLvar.l_push_front(v : char);
var
  p : PSLel;
begin
  new(p);
  p^.next := head;
  p^.data := v;
  head    := p;
end;

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

// Wyszukuje pierwszy element listy o wartości v
//----------------------------------------------
function SLvar.l_find_first(v : char) : PSLel;
var
  p : PSLel;
begin
  p := head;
  while(p <> nil) and (p^.data <> v) do
    p := p^.next;
  l_find_first := p;
end;

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

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

begin
  randomize;
  L.init; // inicjujemy obiekt listy

  // Tworzymy listę o 60 elementach. Każdy element
  // przechowuje przypadkową literę od A do G
  for i := 1 to 60 do
    L.l_push_front(char(65+random(7)));
  L.l_print;

  // Na liście wyszukujemy literki A
  // i zastępujemy je znakiem .
  repeat
    p := L.l_find_first('A');
    if p <> nil then
    begin
      p^.data := '.';
      L.l_print;
    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 SLel
{
  SLel * next;
  char data;
};

// Definicja typu obiektowego SLvar
//------------------------------------
class SLvar
{
  public:
    SLel * head;

    SLvar();  // konstruktor
    ~SLvar(); // destruktor
    void l_print();
    void l_push_front(char v);
    void l_pop_front();
    SLel * l_find_first(char v);
};

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

// Destruktor listy
//-----------------
SLvar::~SLvar()
{
  while(head) l_pop_front();
}

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

// Procedura dołączania na początek listy
//---------------------------------------
void SLvar::l_push_front(char v)
{
  SLel * p;

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

// Procedura usuwa pierwszy element
//---------------------------------
void SLvar::l_pop_front()
{
  SLel * 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
//----------------------------------------------------
SLel * SLvar::l_find_first(char v)
{
  SLel * p = head;
  while(p && p->data != v) p = p->next;
  return p;
}

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

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

  srand(time(NULL));

  // Tworzymy listę o 60 elementach.
  // Każdy element przechowuje
  // przypadkową literę od A do G
  for(i = 0; i < 60; i++)
    L.l_push_front(65+rand()%7);
  L.l_print();

  // Na liście wyszukujemy literki A
  // i zastępujemy je znakiem .
  do
  {
    p = L.l_find_first('A');
    if(p)
    {
      p->data = '.';
      L.l_print();
    }
  } while(p);

  return 0;
}

Basic

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

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

' Typ obiektowy SLvar
'-----------------------
Type SLvar
  head As SLel Ptr
 
  Declare Constructor()
  Declare Destructor()
  Declare Sub l_print()
  Declare Sub l_push_front(v As String)
  Declare Sub l_pop_front()
  Declare Function l_find_first(v As String) _
                                As SLel Ptr
End Type

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

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

Randomize

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

For i = 1 To 60
  L.l_push_front(Chr(65+Int(Rnd*7)))
Next
L.l_print()

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

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

End

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

' Destruktor listy
'-----------------
Destructor SLvar()
  While head
    l_pop_front()
  Wend
End Destructor

' Procedura wyświetla zawartość listy
'------------------------------------
Sub SLvar.l_print()
  Dim p As SLel Ptr = head
  While p
    Print p->Data;
    p = p->next
  Wend
  Print
End Sub

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

' Procedura usuwa pierwszy element
'---------------------------------
Sub SLvar.l_pop_front()
  Dim p As SLel 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 SLvar.l_find_first(v As String)_
                               As SLel Ptr
  Dim p As SLel Ptr = head
  while(p <> 0) AndAlso (p->data <> v)
    p = p->next
  Wend
  l_find_first = p
End Function

Python (dodatek)

# sliniowe przeszukiwanie listy
# Data: 13.05.2024
# (C)2024 mgr Jerzy Wałaszek
#-----------------------------

import random


# klasa elementu listy jednokierunkowej
class SLel:


    def __init__(self, data):
        self.next = None
        self.data = data


# klasa listy jednokierunkowej
class SLvar:


    # Konstruktor
    def __init__(self):
        self.head = None

    # destruktor
    def __del__(self):
        while self.head:
            self.l_pop_front()
        print("slista usunięta z pamięci")

    # wyświetlenie listy
    def l_print(self):
        p = self.head
        while p:
            print(p.data, end="")
            p = p.next
        print()

    # wstawianie na początek
    def l_push_front(self, v):
        p = SLel(v)
        p.next = self.head
        self.head = p

    # pierwsze wystąpienie
    def l_find_first(self, v):
        p = self.head
        while p and (p.data != v):
            p = p.next
        return p

    # usuwa pierwszy element
    def l_pop_front(self):
        if self.head:
            # nowy początek
            self.head = self.head.next


#---------------
# Program główny
#---------------

# obiekt listy jednokierunkowej
sl = SLvar()
# Tworzymy listę o 60 elementach.
# Każdy element przechowuje
# przypadkową literę od A do G
for i in range(0, 60):
    sl.l_push_front(chr(65+random.randrange(0, 7)))
sl.l_print()
# Na liście wyszukujemy literki A
# i zastępujemy je znakiem .
while True:
    p = sl.l_find_first("A")
    if p:
        p.data = "."
        sl.l_print()
    if not p: break

Wynik:

GEDCEAEDABEEDGDAEBEAEEEBBABGCFDGCGEACDDCGBAEECBAAEBFGDBDEFAC
GEDCE.EDABEEDGDAEBEAEEEBBABGCFDGCGEACDDCGBAEECBAAEBFGDBDEFAC
GEDCE.ED.BEEDGDAEBEAEEEBBABGCFDGCGEACDDCGBAEECBAAEBFGDBDEFAC
GEDCE.ED.BEEDGD.EBEAEEEBBABGCFDGCGEACDDCGBAEECBAAEBFGDBDEFAC
GEDCE.ED.BEEDGD.EBE.EEEBBABGCFDGCGEACDDCGBAEECBAAEBFGDBDEFAC
GEDCE.ED.BEEDGD.EBE.EEEBB.BGCFDGCGEACDDCGBAEECBAAEBFGDBDEFAC
GEDCE.ED.BEEDGD.EBE.EEEBB.BGCFDGCGE.CDDCGBAEECBAAEBFGDBDEFAC
GEDCE.ED.BEEDGD.EBE.EEEBB.BGCFDGCGE.CDDCGB.EECBAAEBFGDBDEFAC
GEDCE.ED.BEEDGD.EBE.EEEBB.BGCFDGCGE.CDDCGB.EECB.AEBFGDBDEFAC
GEDCE.ED.BEEDGD.EBE.EEEBB.BGCFDGCGE.CDDCGB.EECB..EBFGDBDEFAC
GEDCE.ED.BEEDGD.EBE.EEEBB.BGCFDGCGE.CDDCGB.EECB..EBFGDBDEF.C
slista usunięta z pamięci

Na początek: podrozdziału strony

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.

Liniowe przeszukiwanie listy

Problem

Rozwiązanie dla listy niecyklicznej

Algorytm wyszukiwania liniowego na liście niecyklicznej

Wejście:

Wyjście:

Elementy pomocnicze:

Lista kroków:

Przykładowe programy

Rozwiązanie dla listy cyklicznej

Algorytm wyszukiwania liniowego na liście cyklicznej

Wejście:

Wyjście:

Elementy pomocnicze:

Lista kroków:

Zadania dla ambitnych