Algorytmy i Struktury Danych - Zliczanie elementów listy

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.

Elementy 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, ; przeglądamy kolejne elementy listy
     wykonuj kroki K04…K05
K04: Jeśli p→data = v, ; jeśli natrafimy na element
     to c ← c+1 ; przechowujący v, zwiększamy licznik
K05: p ← p→next ; 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.

Pascal

// dla listy jednokierunkowej
function l_countv(head : PSLel, 
                  v : char)
                  : cardinal;
var
  p : PSLel;
  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;

// dla listy dwukierunkowej
function l_countv(var L : DLvar;
                      v : char)
                      : cardinal;
var
  p : PDLel;
  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++

// dla listy jednokierunkowej
unsigned l_countv(SLel * head, 
                  char v)
{
  SLel * p = head;
  unsigned c = 0; 
  while(p)
  {
    if(p->data == v)
      c++;
    p = p->next;
  }
  return c;
}

// dla listy dwukierunkowej
unsigned l_countv(DLvar & L, 
                  char v)
{
  DLel * p = L.head;
  unsigned c = 0; 
  while(p)
  {
    if(p->data == v)
      c++;
    p = p->next;
  }
  return c;
}

Basic

' dla listy jednokierunkowej
Function l_countv(head As SLel Ptr, _
                  v As String)_
                  As UInteger
  Dim As SLel 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

' dla listy dwukierunkowej
Function l_countv(ByRef L As DLvar, _
                        v As String) _
                        As UInteger
  Dim As DLel 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

Python (dodatek)

# dla listy jednokierunkowej


# klasa elementu listy
#---------------------
class SLel:


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


# klasa listy jednokierunkowej
#---------------------------
class SLvar:


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


    # Zliczanie
    def l_countv(self, v):
        p = self.head
        c = 0 
        while p:
            if p.data == v:
                c += 1
            p = p.next
        return c

# dla listy dwukierunkowej


# klasa elementu listy
#---------------------
class DLel:


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


# klasa listy dwukierunkowej
#---------------------------
class DLvar:


    # Konstruktor
    def __init__(self):
        self.head = None
        self.tail = None
        self.count = 0


    # Zliczanie
    def l_countv(self, v):
        p = self.head
        c = 0 
        while p:
            if p.data == v:
                c += 1
            p = p.next
        return c

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

// Oblicza liczbę elementów zawierających v
//-----------------------------------------
function SLvar.l_countv(v : char)
                           : cardinal;
var
  p : PSLel;
  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;

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

var
  L : SLvar; // obiekt listy
  i : integer;

begin
  Randomize;
  L.init;  // inicjujemy obiekt
  for i := 1 to 400 do
    L.l_push_front(char(65+random(26)));
  L.l_print;
  for i := ord('A') to ord('Z') do
    writeln(char(i), ' : ', L.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 SLel
{
  SLel * next;
  char data;
};

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

class SLvar
{
  public:
    SLel * head;

    SLvar();  // konstruktor
    ~SLvar(); // destruktor
    void l_print();
    void l_push_front(char v);
    void l_pop_front();
    unsigned l_countv(char v);
};

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

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

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

// Procedura dołącza na początek listy
//------------------------------------
void SLvar::l_push_front(char v)
{
  SLel * 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
  }
}

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

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

int main()
{
  SLvar L; // obiekt listy
  int i;

  srand (time(NULL));
  for(i = 0; i < 400; i++)
    L.l_push_front(65+rand()%26);
  L.l_print();
  for(i = 'A'; i <= 'Z'; i++)
    cout << char(i)
         << ": "
         << setw(3) << L.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 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_countv(v As String) _
                            As UInteger
End Type

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

Dim L As SLvar
Dim i As Integer

Randomize

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

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

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ść elementów 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
    Delete p
  End If
End Sub

' Oblicza liczbę elementów zawierających v
'-----------------------------------------
Function SLvar.l_countv(v As String)_
                           As UInteger
  Dim As SLel 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

Python (dodatek)

# Zliczanie elementów listy
# Data: 17.05.2024
# (C)2024 mgr Jerzy Wałaszek
#---------------------------

import random


# klasa elementu listy
#---------------------
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()


    # Wyświetla zawartość listy
    def l_print(self):
        p = self.head
        while p:
            print(p.data, end="")
            p = p.next
        print()


    # Dodaje nowy element na początek
    def l_push_front(self, v):
        p = SLel(v)
        p.next = self.head
        self.head = p


    # Usuwa element z początku
    def l_pop_front(self):
        p = self.head
        if p:
            self.head = p.next


    # Oblicza liczbę elementów
    # zawierających v
    def l_countv(self, v):
        p = self.head
        c = 0
        while p:
            if p.data == v:
                c += 1
            p = p.next
        return c


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

sl = SLvar()
for i in range(400):
    sl.l_push_front(chr(random.randrange(65, 91)))
sl.l_print()
for i in range(ord('A'), ord('Z')+1):
    print("%s: %3d" % (chr(i), sl.l_countv(chr(i))))

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

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.

Zliczanie elementów listy

Problem