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

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

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), ; przeszukujemy listę
     wykonuj p ← (pnext) ; aż do znalezienia v lub napotkania
                          ; końca listy
K03: Zakończ z wynikiem p

Pascal
function l_find_first(head : PslistEl;
                      v : char)
                      : PslistEl;
var
  p : PslistEl;
begin
  p := head;
  while(p <> nil) and (p^.data <> v) do
    p := p^.next;
  l_find_first := p;
end;
C++
slistEl * l_find_first(slistEl * head;
                       char v)
{
  slistEl * p = head;
  while(p && p->data != v)
    p = p->next;
  return p;
}
Basic
Function l_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
  l_find_first = p
End Function
Python (dodatek)
# klasa elementu listy jednokierunkowej
class slistEl:
    def __init__(self,data):
        self.next = None
        self.data = data

# klasa listy jednokierunkowej
class slistVar:
    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
  PslistEl = ^slistEl;

  slistEl =  record
    next  : PslistEl;
    data  : char;
  end;

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

  slistVar = object
    public
      head : PslistEl;  // 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) : PslistEl;
  end;

//------------------------
// Metody obiektu slistVar
//------------------------

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

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

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

// Procedura usuwa pierwszy element
//---------------------------------
procedure slistVar.l_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 wartości v
//----------------------------------------------
function slistVar.l_find_first(v : char) : PslistEl;
var
  p : PslistEl;
begin
  p := head;
  while(p <> nil) and (p^.data <> v) do
    p := p^.next;
  l_find_first := p;
end;

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

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

begin
  randomize; // inicjujemy generator pseudolosowy
  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 slistEl
{
  slistEl * next;
  char data;
};

// Definicja typu obiektowego slistVar
//------------------------------------

class slistVar
{
  public:
    slistEl * head;

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

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

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

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

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

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

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

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

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

  srand(time(NULL)); // inicjujemy generator pseudolosowy

  // 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 slistEl
  next As slistEl Ptr
  data As String * 1
End Type

' Typ obiektowy slistVar
'-----------------------
Type slistVar
  head As slistEl 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 slistEl Ptr
End Type

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

Dim L As slistVar    ' 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. 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 slistVar()
  head = 0
End Constructor

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

' Procedura wyświetla zawartość elementów listy
'----------------------------------------------
Sub slistVar.l_print()
  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 slistVar.l_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 slistVar.l_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 slistVar.l_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
  l_find_first = p
End Function
Python (dodatek)
# Liniowe przeszukiwanie listy
# Data: 13.05.2024
# (C)2024 mgr Jerzy Wałaszek
#-----------------------------

import random

# klasa elementu listy jednokierunkowej
class slistEl:
    def __init__(self,data):
        self.next = None
        self.data = data

# klasa listy jednokierunkowej
class slistVar:

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

    # destruktor
    def __del__(self):
        while self.head:
            self.l_pop_front()
        print("Lista 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 = slistEl(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

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

L = slistVar() # obiekt listy jednokierunkowej

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

for i in range(0,60):
    L.l_push_front(chr(65+random.randrange(0,7)))
L.l_print()

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

while True:
    p = L.l_find_first("A")
    if p:
        p.data = "."
        L.l_print()
    if not p: break
Wynik:
DBGGAECBFBFGCEABFGAAAGEFCDFBDDEEDDAGEADDGDAGFGDGCAGADGBEECAB
DBGG.ECBFBFGCEABFGAAAGEFCDFBDDEEDDAGEADDGDAGFGDGCAGADGBEECAB
DBGG.ECBFBFGCE.BFGAAAGEFCDFBDDEEDDAGEADDGDAGFGDGCAGADGBEECAB
DBGG.ECBFBFGCE.BFG.AAGEFCDFBDDEEDDAGEADDGDAGFGDGCAGADGBEECAB
DBGG.ECBFBFGCE.BFG..AGEFCDFBDDEEDDAGEADDGDAGFGDGCAGADGBEECAB
DBGG.ECBFBFGCE.BFG...GEFCDFBDDEEDDAGEADDGDAGFGDGCAGADGBEECAB
DBGG.ECBFBFGCE.BFG...GEFCDFBDDEEDD.GEADDGDAGFGDGCAGADGBEECAB
DBGG.ECBFBFGCE.BFG...GEFCDFBDDEEDD.GE.DDGDAGFGDGCAGADGBEECAB
DBGG.ECBFBFGCE.BFG...GEFCDFBDDEEDD.GE.DDGD.GFGDGCAGADGBEECAB
DBGG.ECBFBFGCE.BFG...GEFCDFBDDEEDD.GE.DDGD.GFGDGC.GADGBEECAB
DBGG.ECBFBFGCE.BFG...GEFCDFBDDEEDD.GE.DDGD.GFGDGC.G.DGBEECAB
DBGG.ECBFBFGCE.BFG...GEFCDFBDDEEDD.GE.DDGD.GFGDGC.G.DGBEEC.B

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.

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), ; przeszukujemy listę
     wykonuj kroki K03…K04
K03:   p ← (pnext) ; 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 : 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;
  l_find_first := p;
end;
C++
slistEl * l_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 l_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
  l_find_first = p
End Function
Python (dodatek)
# klasa elementu listy jednokierunkowej
class cslistEl:
    def __init__(self,data):
        self.next = None
        self.data = data

# klasa listy jednokierunkowej
class cslistVar:

    # 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

Na początek:  podrozdziału   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.

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