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

©2019 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 obrazek N

Lista kroków:

K01: c ← 0 zerujemy licznik
K02: phead ustawiamy p na pierwszy element listy
K03: Dopóki p ≠ nil, wykonuj K04...K05 przeglądamy kolejne elementy listy
K04:     Jeśli (pdata) = v, to cc + 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)2019 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)2019 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)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 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
©2019 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.