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