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

©2026 mgr Jerzy Wałaszek

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.

Elementy 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, ; 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

do podrozdziału  do 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.

Elementy 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, ; przeszukujemy listę
     wykonuj kroki K03…K04
K03:   p ← p→next ; przechodzimy do następnika
K04:   Jeśli p = head, ; jeśli obiegliśmy całą listę, to zerujemy p, 
       to p ← nil ; co spowoduje wyjście z pętli
K05: 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
  begin
    p := p^.next;
    if p = head then
      p := nil;
  end;
  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;
    if(p == head)
      p = NULL;
  }
  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
    If p = head Then _
      p = 0
  Wend
  l_find_first = p
End Function
Python (dodatek) 
# klasa elementu listy jednokierunkowej
class CSLel:


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

# klasa listy jednokierunkowej
class CSLvar:


    # Konstruktor
    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
            if p is self.head:
                p = None
        return p

do podrozdziału  do strony 

Zadania dla ambitnych

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

do podrozdziału  do strony 
Zespół Przedmiotowy
Chemii-Fizyki-Informatyki
w I Liceum Ogólnokształcącym
im. Kazimierza Brodzińskiego
w Tarnowie
ul. Piłsudskiego 4
©2026 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.