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

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: phead ; ustawiamy p na pierwszy element listy
K03: Dopóki p ≠ nil, ; przeglądamy kolejne elementy listy
     wykonuj kroki K04…K05
K04: Jeśli (pdata) = v, ; jeśli natrafimy na element
     to cc+1 ; 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.

Pascal
// dla listy jednokierunkowej
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;
// dla listy dwukierunkowej
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++
// dla listy jednokierunkowej
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;
}
// dla listy dwukierunkowej
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
' dla listy jednokierunkowej
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
' dla listy dwukierunkowej
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
Python (dodatek)
# dla listy jednokierunkowej

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

# klasa listy jednokierunkowej
#---------------------------
class slistVar:

    # 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 dlistEl:
    def __init__(self,data):
        self.next = None
        self.prev = None
        self.data = data

# klasa listy dwukierunkowej
#---------------------------
class dlistVar:

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

// Oblicza liczbę elementów zawierających v
//-----------------------------------------
function slistVar.l_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;
  l_countv := c;
end;

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

var
  L : slistVar; // 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 slistEl
{
  slistEl * next;
  char data;
};

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

class slistVar
{
  public:
    slistEl * head;

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

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

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

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

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

// Oblicza liczbę elementów zawierających v
//-----------------------------------------
unsigned slistVar::l_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()
{
  slistVar 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 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_countv(v As String)_
                            As UInteger
End Type

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

Dim L As slistVar
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 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
    Delete p
  End If
End Sub

' Oblicza liczbę elementów zawierających v
'-----------------------------------------
Function slistVar.l_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
  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 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()

    # 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 = slistEl(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
            del p

    # 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
#---------------

L = slistVar()
for i in range(400):
    L.l_push_front(chr(65+random.randrange(26)))
L.l_print()
for i in range(ord('A'),ord('Z')+1):
    print("%s: %3d" %(chr(i),L.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 

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