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

©2020 mgr Jerzy Wałaszek
I LO w Tarnowie

Zliczanie elementów listy

SPIS TREŚCI
Tematy pomocnicze
Podrozdziały

Problem

Należy określić liczbę elementów listy, które zawierają daną o wartości v.

Rozwiązanie

Zadanie jest bardzo proste. Tworzymy licznik, zerujemy go. Następnie przechodzimy przez wszystkie elementy listy. Jeśli bieżący element ma w polu data wartość v, to licznik zwiększamy o 1. Po przejściu listy w liczniku znajdzie się liczba wystąpień wartości v  na liście.

Algorytm zliczania wystąpień danej wartości na liście

Wejście:

head  –  adres pierwszego elementu listy
v  – zliczana wartość

Wyjście:

liczba elementów listy, które w polu danych zawierają v

Zmienne pomocnicze:

p  – wskaźnik elementu listy
c  –  licznik, c  ∈ N

Lista kroków:

K01: c  ← 0 zerujemy licznik
K02: p  ← head ustawiamy p na pierwszy element listy
K03: Dopóki p  ≠ nil,
wykonuj kroki K04...K05
przeglądamy kolejne elementy listy
K04:     Jeśli ( pdata  ) = v,
    to c  ← c  + 1
jeśli natrafimy na element przechowujący v, zwiększamy licznik
K05:     p  ← ( pnext  ) przechodzimy do następnego elementu listy
K06: Zakończ z wynikiem c  

W poniżej znajdują się przykładowe funkcje zliczania wystąpień elementów na liście. Po lewej stronie dla listy jednokierunkowej, po prawej stronie dla listy dwukierunkowej.

Pascal
function l_countv ( head : PslistEl, v : char ) : cardinal;
var
  p : PslistEl;
  c : cardinal;
begin
  c := 0;
  p := head;
  while p <> nil do
  begin
    if p^.data = v then inc ( c );
    p := p^.next;
  end;
  l_countv := c;  
end;
  
function l_countv ( var L : dlistVar; v : char ) : cardinal;
var
  p : PdlistEl;
  c : cardinal;
begin
  c := 0;
  p := L.head;
  while p <> nil do
  begin
    if p^.data = v then inc ( c );
    p := p^.next;
  end;
  l_countv := c;  
end;
C++
unsigned l_countv ( slistEl * head, char v )
{
  slistEl * p = head;
  unsigned c = 0;  
  while( p )
  {
    if( p->data == v ) c++;
    p = p->next;
  }
  return c;
}
 
unsigned l_countv ( dlistVar & L, char v )
{
  dlistEl * p = L.head;
  unsigned c = 0;  
  while( p )
  {
    if( p->data == v ) c++;
    p = p->next;
  }
  return c;
}
Basic
Function l_countv ( head As slistEl Ptr, v As String ) As UInteger
  Dim As slistEl Ptr p = head
  Dim As UInteger c = 0
  While p
    If p->data = v Then c += 1
    p = p->next
  Wend
  l_countv = c
End Function
 
Function l_countv ( ByRef L As dlistVar, v As String ) As UInteger
  Dim As dlistEl Ptr p = L.head
  Dim As UInteger c = 0
  While p
    If p->data = v Then c += 1
    p = p->next
  Wend
  l_countv = c
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ę o długości 400 elementów, które zawierają losowo litery od A do Z. Następnie wylicza ilość wystąpień na liście każdej litery. Program wykorzystuje obiekt listy jednokierunkowej, w którym pozostawiliśmy tylko niezbędne metody.
Pascal
// Zliczanie elementów listy
// Data: 19.02.2012
// (C)2020 mgr Jerzy Wałaszek
//---------------------------

program slist_count;

// 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    countv ( v : char ) : cardinal;
  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;

// Oblicza liczbę elementów zawierających v
//-----------------------------------------
function slist.countv ( v : char ) : cardinal;
var
  p : PslistEl;
  c : cardinal;
begin
  c := 0;
  p := head;
  while p <> nil do
  begin
    if p^.data = v then inc ( c );
    p := p^.next;
  end;
  countv := c;
end;

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

var
  L : slist;    // obiekt listy jednokierunkowej
  i : integer;

begin
  Randomize;

  L.init;  // inicjujemy obiekt

  for i := 1 to 400 do L.push_front ( char ( 65+random ( 26 ) ) );
  L.printl;

  for i := ord ( 'A' ) to ord ( 'Z' ) do writeln ( char ( i ), ' : ', L.countv ( char ( i ) ):3 );

  L.destroy;
end.
C++
// Zliczanie elementów listy
// Data: 19.02.2012
// (C)2020 mgr Jerzy Wałaszek
//---------------------------

#include <iostream>
#include <iomanip>
#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( );
    unsigned countv ( 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( )
{
  slistEl * p;
  for( 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
  }
}

// Oblicza liczbę elementów zawierających v
//-----------------------------------------
unsigned slist::countv ( char v )
{
  slistEl * p = head;
  unsigned c = 0;
  while( p )
  {
    if( p->data == v ) c++;
    p = p->next;
  }
  return c;
}

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

int main( )
{
  slist L;     // zawiera adres początku listy
  int i;

  srand ( time ( NULL ) );

  for( i = 0; i < 400; i++ ) L.push_front ( 65 + rand( ) % 26 );
  L.printl( );

  for( i = 'A'; i <= 'Z'; i++ ) cout << char ( i ) << ": " << setw ( 3 ) << L.countv ( i ) << endl;
  return 0;
}
Basic
' Zliczanie elementów listy
' Data: 19.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 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 countv ( v As String ) As UInteger
End Type

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

Dim L As slist       ' zawiera adres początku listy  
Dim i As Integer

Randomize

For i = 1 To 400
  L.push_front ( Chr ( 65 + Int ( Rnd *26 ) ) )
Next
L.printl( )

For i = Asc ( "A" ) To Asc ( "Z" )
  Print Using "&: ###";Chr ( i ), L.countv ( Chr ( i ) )
Next

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

  p = 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

  p = head      ' zapamiętujemy początek
  If p Then
    head = p->next  ' nowy początek
    Delete p     ' usuń element z pamięci
  End If
End Sub

' Oblicza liczbę elementów zawierających v
'-----------------------------------------
Function slist.countv ( v As String ) As UInteger
  Dim As slistEl Ptr p = head
  Dim As UInteger c = 0
  While p
    If p->data = v Then c += 1
    p = p->next
  Wend
  countv = c
End Function
Wynik:
XJIOTMLPBNMHIVLUKPIVXZUJXGMABVQIEQSDHCMFKTSGXDCOVGIQURDUXFDIQUIXCVCARPMEHTGUVZVY
BHAVRACLBEXODIXPTPYUNCVPXVDCYWDSLVBYSMKDCYJZTDUQABUQMKROGSMDDOIZVVSYQNUIQOMPGQLY
PCUDSHXLFRCRKAPUXNXQFPSCPAFEDMIYYSKEWINKVUATZPUQFOREPQPVPDBRAWBPJTDLXUCKQURTXOTD
MRGMDDJAWOLMWDYHRQCBHEHERZLNHFGYRSLJHESOMWFCRAEKIWUDBQELBCEMJPUAXNYEOEVWDHQVZQKJ
GZYLUGOFVGLZKIVMBLLINCEKGBKOKOCRPHJTOPXGIZAFTRNKGMHAAFSRUMJPBGSGPTARUCLGIPDBTBLB

A :  16
B :  17
C :  18
D :  22
E :  15
F :  11
G :  17
H :  13
I :  17
J :  10
K :  15
L :  17
M :  18
N :   9
O :  15
P :  22
Q :  17
R :  18
S :  13
T :  13
U :  21
V :  19
W :   8
X :  16
Y :  13
Z :  10
Na początek:  podrozdziału   strony 

Zadanie

Zaproponuj podobny algorytm dla listy 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
©2020 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.