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

Słownik na liście

SPIS TREŚCI
Tematy pomocnicze
Podrozdziały

Implementacja

Słownik można utworzyć przy pomocy list. Zaletą list w stosunku do tablic jest to, iż listy posiadają z natury dynamiczną naturę. Czas wstawiania nowego elementu jest klasy O(n). Listy nie muszą, jak tablice, zajmować spójnego bloku pamięci dlatego listy lepiej wykorzystują dostępną pamięć. Przykładowy słownik zrealizujemy przy pomocy listy jednokierunkowej o następującej strukturze

 Każdy element listy będzie zawierał trzy pola:

next : wskazuje następny element listy. Ostatni element zawiera tu wskazanie puste.
klucz : unikalny klucz, z którym powiązane jest następne pole wartości. Klucz jest daną prostego typu: liczba, tekst...
wartość : powiązana z kluczem. Wartość jest daną dowolnego typu i może się powtarzać w słowniku.

Program będzie pamiętał adres pierwszego elementu listy w zmiennej td. Jeśli adres ten jest pusty (nil), to lista nie zawiera żadnego elementu i słownik jest pusty.

Definicje elementu listy słownika są następujące:

Pascal
type
  PDict = ^TDict;
  TDict =  record
    next  : PDict;
    key   : typ_klucza;
    value : typ_wartości;
  end;
...
var
  td : PDict;
C++
struct TDict
{
  TDict * next;
  typ_klucza key;
  typ_wartości value;
};
...
TDict * td;
Basic
Type TDict
  next  As TDict Ptr
  key   As typ_klucza
  value As typ_wartości
End Type
...
Dim td As TDict Ptr
Python (dodatek)
class TDict


    def __init__(self, k, d):
        self.next  = None
        self.key   = k
        self.value = v
...
td = None # Wskazanie początku
          # listy ze słownikiem

Na początek:  podrozdziału   strony 

Algorytmy

Operacje na słowniku będą sprowadzały się do operacji na tworzącej go liście. Poniżej przedstawiamy algorytmy najważniejszych z nich.

Algorytmy operacji na słowniku utworzonym na liście

d_del(td, k) - Usuwa ze słownika td klucz i związaną z nim wartość (k, v).

Algorytm przegląda listę td i jeśli znajdzie w niej element z kluczem k, to usuwa go z listy. Jeśli klucz k nie występuje w liście, to nic nie jest wykonywane.

Wejście:

td : referencja do zmiennej zawierającej adres początku listy.
k : poszukiwany klucz.

Wyjście:

Lista td z usuniętym elementem o kluczu k.

Elementy pomocnicze:

p,r : wskazania węzła.

Lista kroków:

K01: Jeśli td = nil, ; Lista pusta?
     to zakończ
K02: Jeśli td→key <> k, ; Pierwszy węzeł?
     to idź do kroku K07
K03: r ← td→next ; Zapamiętujemy następny węzeł
K04: Usuń td ; Usuwamy węzeł początkowy
K05: td ← r ; Jako pierwszy będzie węzeł następny
K06: Zakończ
K07: p ← td ; Przeszukujemy listę
K08: Dopóki p→next <> nil i p→next→key <> k,
K09: wykonuj p ← p→next
K10: Jeśli p→next = nil, ; Jeśli klucza brak
     to zakończ
K11: r ← p→next→next ; zapamiętujemy element następny
K12: Usuń p→next ; usuwamy węzeł z kluczem
K13: p→next ← r
K14: Zakończ

d_put(td, k, v) - Umieszcza w słowniku nową parę (k, v) lub modyfikuje istniejącą parę o kluczu k

Algorytm umieszcza w słowniku parę (k, v). Jeśli w słowniku istnieje para o kluczu k, to zostanie zastąpiona nową parą (k, v).

Wejście:

td : referencja do zmiennej zawierającej adres początku listy.
k : klucz.
v : wartość.

Wyjście:

Słownik z nową parą (k, v).

Elementy pomocnicze:

p : wskazanie węzła.
d_del(td, k) : usuwa ze słownika parę o kluczu k.

Lista kroków:

K01: d_del(td, k) ; usuwamy starą parę o kluczu k
K02: Utwórz nowy węzeł p
K03: p→next ← td ; węzeł wstawiamy na początek listy
K04: p→key ← k
K05: p→value ← v
K06: td ← p
K06: Zakończ

d_get(td, k) - Zwraca wartość związaną z kluczem k lub wartość specjalną, jeśli klucza k nie ma w słowniku.

Wejście:

td : wskazanie początku listy.
k : klucz.

Wyjście:

Wartość v pary (k, v) lub wartość specjalna, jeśli w słowniku brak klucza k.

Elementy pomocnicze:

p : wskazanie węzła.
wartość specjalna : wartość zwracana w przypadku nieznalezienia klucza k.

Lista kroków:

K01: p ← td ; przeglądamy listę
K02: Dopóki p ≠ nil i p→key ≠ k,
     wykonuj p ← p→next
K03: Jeśli p ≠ nil,
     to zakończ z wynikiem p→value
K04: Zakończ z wynikiem wartość specjalna

d_size(td) - Oblicza liczbę kluczy w słowniku td

Algorytm liczy liczbę kluczy w słowniku td.

Wejście:

td : wskazanie początku listy.

Wyjście:

Liczba kluczy w słowniku td.

Elementy pomocnicze:

p : wskazanie węzła.
c : licznik kluczy.

Lista kroków:

K01: c ← 0 ; zerujemy licznik kluczy
K02: p ← td; rozpoczynamy od początku listy
K03: Dopóki p ≠ nil,
     wykonuj kroki K04...K05
K04:   c ← c + 1
K05:   p ← p→next
K06: Zakończ z wynikiem c

Na początek:  podrozdziału   strony 

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 słownik w liście. Klucze są tekstami imion męskich. Wartości są liczbami rzeczywistymi z zakresu od 0 do 10. Do słownika zostaje wprowadzone 7 elementów w przypadkowej kolejności. Następnie do słownika zostaje wprowadzone 5 dalszych elementów, które mogą już występować w słowniku. Usuwamy ze słownika 5 kluczy, których może nie być w słowniku. Na koniec szukamy 10 przypadkowych kluczy i jeśli są, wypisujemy związane z nimi wartości, klucze mogą się powtarzać.
Pascal
// Program testowy dla słownika na liście
// Data: 4.11.2024
// (C)2024 mgr Jerzy Wałaszek
//---------------------------------------

program dlist_test;

// Typ elementów listy
//--------------------
type
  PDict = ^TDict;
  TDict =  record
    next  : PDict;
    key   : String;
    value : double;
  end;

const
  // Wartość specjalna
  SV = -1000000.0;

// Usuwa klucz ze słownika
//------------------------
procedure d_del(var td : PDict; k : string);
var
  p, r : PDict;

begin
  if td = nil then Exit;
  if td^.key = k then
  begin
    r := td^.next;
    dispose(td);
    td := r;
    Exit;
  end;
  p := td;
  while (p^.next <> nil) and
        (p^.next^.key <> k) do
    p := p^.next;
  if p^.next = nil then Exit;
  r := p^.next^.next;
  dispose(p^.next);
  p^.next := r;
end;

// Umieszcza w słowniku parę (k,v)
//--------------------------------
procedure d_put(var td : PDict;
                     k : String;
                     v : double);
var
  p : PDict;

begin
  d_del(td, k);
  new(p);
  p^.next := td;
  p^.key := k;
  p^.value := v;
  td := p
end;

// Zwraca wartość v skojarzoną z kluczem k
// lub wartość specjalną SV, jeśli słownik
// nie zawiera klucza k.
function d_get(td : PDict; k : string)
                             : double;
var
  p : PDict;

begin
  p := td;
  while (p <> nil) and (p^.key <> k) do
    p := p^.next;
  if p <> nil then Exit(p^.value);
  Exit(SV);
end;

// Funkcja oblicza liczbę kluczy w słowniku
//-----------------------------------------
function d_size(td : PDict) : cardinal;
var
  p : PDict;
  c : cardinal;

begin
  c := 0; // zerujemy licznik
  p := td;
  while p <> nil do
  begin
    inc(c); // zwiększamy licznik o 1
    p := p^.next;
  end;
  Exit(c);
end;

// Procedura wyświetla zawartość słownika
//---------------------------------------
procedure d_print(td : PDict);
var
  i : cardinal;
  p : PDict;

begin
  writeln('Liczba kluczy : ', d_size(td));
  p := td;
  i := 1;
  while p <> nil do
  begin
    writeln('Para #', i,
            ' k = ', p^.key,
            ' v = ', p^.value:5:2);
    inc(i);
    p := p^.next;
  end;
  writeln;
end;

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

var
  // Klucze
  names : array[0..9] of string =
    ('Janusz', 'Marian',
     'Henryk', 'Adrian',
     'Bogdan', 'Cyprian',
     'Dariusz','Zenon',
     'Tadeusz','Karol');
  i,x : integer;
  v   : real;
  td : PDict; // Słownik

begin
  randomize();
  td := nil;

  // W słowniku umieszamy 7 danych
  writeln('TWORZENIE');
  for i := 1 to 7 do
  begin
    x  := random(10);
    v  := random * 10;
    d_put(td,names[x],v);
    writeln('(',names[x],',',
            v:5:2,')');
  end;
  d_print(td);

  // Dodajemy 5 elementów
  writeln('DODAWANIE');
  for i := 1 to 5 do
  begin
    x  := random(10);
    v  := random * 10;
    d_put(td,names[x],v);
    writeln('(',names[x],',',
            v:5:2,')');
  end;
  d_print(td);

  // Usuwamy 5 kluczy
  writeln('USUWANIE');
  for i := 1 to 5 do
  begin
    x := random(10);
    d_del(td,names[x]);
    writeln('(',names[x],',*)');
  end;
  d_print(td);

  // Szukamy 10 kluczy
  writeln('WYSZUKIWANIE');
  for i := 1 to 10 do
  begin
    x := random(10);
    v := d_get(td,names[x]);
    if v <> SV then
    begin
      writeln('klucz ',
        names[x],
        ' obecny, v = ',
        v:5:2)
    end
    else
    begin
      writeln('klucza ',
      names[x],' brak');
    end;
  end;

  // Usuwamy słownik z pamięci
  while td <> nil do
    d_del(td,td^.key);
end.
C++
// Program testowy dla słownika na liście
// Data: 6.11.2024
// (C)2024 mgr Jerzy Wałaszek
//---------------------------------------

#include <iostream>
#include <iomanip>
#include <string>
#include <cstdlib>
#include <ctime>

using namespace std;

// Typ elementów listy
//--------------------
struct TDict
{
  TDict * next;
  string key;
  double value;
};

// Wartość specjalna
const double SV = -1000000.0;

// Usuwa klucz ze słownika
//------------------------
void d_del(TDict * & td, string k)
{
  TDict * p, * r;

  if(!td) return;
  if(td->key == k)
  {
    r = td->next;
    delete td;
    td = r;
    return;
  }
  p = td;
  while(p->next && p->next->key != k)
    p = p->next;
  if(!p->next) return;
  r = p->next->next;
  delete p->next;
  p->next = r;
  return;
}

// Umieszcza w słowniku parę (k,v)
//--------------------------------
void d_put(TDict * & td,
              string k,
              double v)
{
  TDict * p;

  d_del(td, k);
  p = new(TDict);
  p->next = td;
  p->key = k;
  p->value = v;
  td = p;
}

// Zwraca wartość v skojarzoną z kluczem k
// lub wartość specjalną SV, jeśli słownik
// nie zawiera klucza k.
double d_get(TDict * td, string k)
{
  TDict * p;

  p = td;
  while(p && p->key != k)
    p = p->next;
  if(p) return p->value;
  return SV;
}

// Funkcja oblicza liczbę kluczy w słowniku
//-----------------------------------------
int d_size(TDict * td)
{
  TDict * p;
  int c;

  c = 0; // zerujemy licznik
  p = td;
  while(p)
  {
    c++; // zwiększamy licznik o 1
    p = p->next;
  }
  return c;
}

// Procedura wyświetla zawartość słownika
//---------------------------------------
void d_print(TDict * td)
{
  int i;
  TDict * p;

  cout << "Liczba kluczy : "
       << d_size(td) << endl;
  p = td;
  for(i = 1; p; i++,p = p->next)
    cout << "Para #" << i
         << " k = " << p->key
         << " v = " << setw(5)
         << p->value << endl;
  cout << endl;
}

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

int main()
{
  // Klucze
  string names[] =
    {"Janusz", "Marian",
     "Henryk", "Adrian",
     "Bogdan", "Cyprian",
     "Dariusz","Zenon",
     "Tadeusz","Karol"};
  int i,x;
  double v;
  TDict * td; // Słownik

  cout << fixed
       << setprecision(2);
  srand(time(nullptr));
  td = nullptr;

  // W słowniku umieszamy 7 danych
  cout << "TWORZENIE" << endl;
  for(i = 0; i < 7; i++)
  {
    x  = rand()%10;
    v  = 10*rand()/double(RAND_MAX);
    d_put(td,names[x],v);
    cout << "(" << names[x]
         << "," << setw(5)
         << v << endl;
  }
  d_print(td);

  // Dodajemy 5 elementów
  cout << "DODAWANIE" << endl;
  for(i = 0; i < 5; i++)
  {
    x  = rand()%10;
    v  = 10*rand()/double(RAND_MAX);
    d_put(td,names[x],v);
    cout << "(" << names[x]
         << "," << setw(5)
         << v << endl;
  }
  d_print(td);

  // Usuwamy 5 kluczy
  cout << "USUWANIE" << endl;
  for(i = 0; i < 5; i++)
  {
    x  = rand()%10;
    d_del(td,names[x]);
    cout << "(" << names[x]
         << ",*)" << endl;
  }
  d_print(td);

  // Szukamy 10 kluczy
  cout << "WYSZUKIWANIE" << endl;
  for(i = 0; i < 10; i++)
  {
    x  = rand()%10;
    v = d_get(td,names[x]);
    if(v != SV)
      cout << "klucz " << names[x]
           << " obecny, v = "
           << setw(5) << v << endl;
    else
      cout << "klucza " << names[x]
           << " brak" << endl;
  }

  // Usuwamy słownik z pamięci
  while(td)
    d_del(td,td->key);
  return 0;
}
Basic
' Program testowy dla słownika na liście
' Data: 6.11.2024
' (C)2024 mgr Jerzy Wałaszek
'---------------------------------------

' Typ elementów listy
'--------------------
Type TDict
  next  As TDict Ptr
  key   As String
  value As Double
End Type

' Wartość specjalna
Const SV = -1000000.0

' Usuwa klucz ze słownika
'------------------------
Sub d_del(ByRef td As TDict Ptr, _
          ByRef k  As String)
  Dim As TDict Ptr p, r

  If td = 0 Then Return
  If td->key = k Then
    r = td->next
    delete td
    td = r
    Return
  End If
  p = td
  While (p->next <> 0) AndAlso _
        (p->next->key <> k)
    p = p->next
  Wend
  If p->next = 0 Then Return
  r = p->next->next
  delete p->next
  p->next = r
  Return
End Sub

' Umieszcza w słowniku parę (k,v)
'--------------------------------
Sub d_put(ByRef td As TDict Ptr, _
          ByRef k  As String, _
          ByVal v  As Double)
  Dim As TDict Ptr p

  d_del td, k
  p = New TDict
  p->next = td
  p->key = k
  p->value = v
  td = p
End Sub

' Zwraca wartość v skojarzoną z kluczem k
' lub wartość specjalną SV, jeśli słownik
' nie zawiera klucza k.
Function d_get(ByVal td As TDict Ptr, _
               ByRef k  As String) _
                        As Double
  Dim As TDict Ptr p

  p = td
  While (p <> 0) AndAlso (p->key <> k)
    p = p->next
  Wend
  If p <> 0 Then Return p->value
  Return SV
End Function

' Funkcja oblicza liczbę kluczy w słowniku
'-----------------------------------------
Function d_size(ByVal td As TDict Ptr) _
                         As Integer
  Dim As TDict Ptr p
  Dim As Integer c

  c = 0 ' zerujemy licznik
  p = td
  While p <> 0
    c += 1 ' zwiększamy licznik o 1
    p = p->next
  Wend
  Return c
End Function

' Procedura wyświetla zawartość słownika
'---------------------------------------
Sub d_print(ByVal td As TDict Ptr)
  Dim As Integer i
  Dim As TDict Ptr p

  Print "Liczba kluczy : ";d_size(td)
  p = td
  i = 1
  While p <> 0
    Print "Para #"; i; " k = "; _
          p->key; " v = ";
    Print Using "##.##"; p->value
    i += 1
    p = p->next
  Wend
  Print
End Sub

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

' Klucze
Dim As String names(9) = _
    {"Janusz", "Marian", _
     "Henryk", "Adrian", _
     "Bogdan", "Cyprian",_
     "Dariusz","Zenon",  _
     "Tadeusz","Karol"}
Dim As Integer i,x
Dim As Double v
Dim As TDict Ptr td ' Słownik

Randomize
td = 0
' W słowniku umieszamy 7 danych
Print "TWORZENIE"
For i = 1 To 7
  x = Int(Rnd*10)
  v = Rnd*10
  d_put td,names(x),v
  Print "(";names(x);",";
  Print Using "##.##";v
Next
d_print td

' Dodajemy 5 elementów
Print "DODAWANIE"
For i = 1 To 5
  x = Int(Rnd*10)
  v = Rnd*10
  d_put td,names(x),v
  Print "(";names(x);",";
  Print Using "##.##)";v
Next  
d_print td

' Usuwamy 5 kluczy
Print "USUWANIE"
For i = 1 To 5
  x = Int(Rnd*10)
  d_del td,names(x)
  Print "(";names(x);",*)"
Next
d_print td

' Szukamy 10 kluczy
Print "WYSZUKIWANIE"
For i = 1 To 10
  x = Int(Rnd*10)
  v = d_get(td,names(x))
  If v <> SV Then
    Print "klucz ";names(x);" obecny, v = ";
    Print Using "##.##";v
  Else
    Print "klucza ";names(x);" brak"
  End If
Next

' Usuwamy słownik z pamięci
While td <> 0
  d_del td,td->key
Wend
End
Python (dodatek) 
# Program testowy dla słownika na liście
# Data: 7.11.2024
# (C)2024 mgr Jerzy Wałaszek
#---------------------------------------

import random


# Typ elementów listy
class TDict:
    def __init__(self,n,k,v):
        self.next  = n
        self.key   = k
        self.value = v


# Wartość specjalna
SV = -1000000.0


# Usuwa klucz ze słownika
def d_del(td,k):
    if not td: return None
    if td.key == k:
        r = td.next
        del td
        td = None
        return r
    p = td
    while p.next and p.next.key != k:
        p = p.next
    if not p.next: return td
    r = p.next.next
    del p.next
    p.next = r
    return td


# Umieszcza w słowniku parę (k,v)
def d_put(td,k,v):
    td = d_del(td, k)
    p = TDict(td,k,v)
    return p


# Zwraca wartość v skojarzoną z kluczem k
# lub wartość specjalną SV, jeśli słownik
# nie zawiera klucza k.
def  d_get(td,k):
    global SV
    p = td
    while p and p.key != k:
        p = p.next
    if p: return p.value
    return SV


# Funkcja oblicza liczbę kluczy w słowniku
def d_size(td):
    c = 0 # zerujemy licznik
    p = td
    while p:
        c += 1 # zwiększamy licznik o 1
        p = p.next
    return c


# Procedura wyświetla zawartość słownika
def d_print(td):
    print("Liczba kluczy :",d_size(td))
    p = td
    i = 1
    while p:
        print("Para nr",i,"k =",
              p.key,"v = %5.2f" % p.value)
        i += 1
        p = p.next
    print()


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

# Klucze
names = ["Janusz", "Marian",
         "Henryk", "Adrian",
         "Bogdan", "Cyprian",
         "Dariusz","Zenon",
        "Tadeusz","Karol"]
td = None # Słownik

# W słowniku umieszamy 7 danych
print("TWORZENIE SŁOWNIKA:")
for i in range(7):
    x = random.randrange(10)
    v = random.uniform(0.0,10.0)
    td = d_put(td,names[x],v)
    print("(",names[x],", %5.2f)" % v, sep="")
d_print(td)

# Dodajemy 5 elementów
print("DODAWANIE ELEMENTÓW:")
for i in range(5):
    x = random.randrange(10)
    v = random.uniform(0,10)
    td = d_put(td,names[x],v)
    print("(",names[x],", %5.2f)" % v, sep="")
d_print(td)

# Usuwamy 5 kluczy
print("USUWANIE KLUCZY:")
for i in range(5):
    x = random.randrange(10)
    td = d_del(td,names[x])
    print("(",names[x],",*)",sep="")
d_print(td)

# Szukamy 10 kluczy
print("WYSZUKIWANIE KLUCZY:")
for i in range(10):
    x = random.randrange(10)
    v = d_get(td,names[x])
    if v != SV:
        print("klucz",names[x],
              "obecny, v = %5.2f" % v)
    else:
        print("klucza",names[x],"brak")

# Usuwamy słownik z pamięci
while td:
    td = d_del(td,td.key)
Wynik: 
TWORZENIE
(Bogdan, 2.11)
(Henryk, 6.88)
(Janusz, 2.18)
(Bogdan, 8.93)
(Bogdan, 8.44)
(Karol, 9.70)
(Dariusz, 7.22)
Liczba kluczy : 5
Para #1 k = Dariusz v =  7.22
Para #2 k = Karol v =  9.70
Para #3 k = Bogdan v =  8.44
Para #4 k = Janusz v =  2.18
Para #5 k = Henryk v =  6.88

DODAWANIE
(Henryk, 8.93)
(Marian, 0.83)
(Cyprian, 6.27)
(Adrian, 8.44)
(Zenon, 5.06)
Liczba kluczy : 9
Para #1 k = Zenon v =  5.06
Para #2 k = Adrian v =  8.44
Para #3 k = Cyprian v =  6.27
Para #4 k = Marian v =  0.83
Para #5 k = Henryk v =  8.93
Para #6 k = Dariusz v =  7.22
Para #7 k = Karol v =  9.70
Para #8 k = Bogdan v =  8.44
Para #9 k = Janusz v =  2.18

USUWANIE
(Cyprian,*)
(Adrian,*)
(Cyprian,*)
(Bogdan,*)
(Dariusz,*)
Liczba kluczy : 5
Para #1 k = Zenon v =  5.06
Para #2 k = Marian v =  0.83
Para #3 k = Henryk v =  8.93
Para #4 k = Karol v =  9.70
Para #5 k = Janusz v =  2.18

WYSZUKIWANIE
klucz Henryk obecny, v =  8.93
klucz Zenon obecny, v =  5.06
klucz Henryk obecny, v =  8.93
klucz Marian obecny, v =  0.83
klucz Marian obecny, v =  0.83
klucza Adrian brak
klucza Tadeusz brak
klucz Marian obecny, v =  0.83
klucza Cyprian brak
klucz Karol obecny, v =  9.70

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.