Algorytmy i Struktury Danych - Słownik w tablicy

Zwykłe tablice mogą posłużyć do utworzenia prostej struktury słownika, jednakże nie jest to sposób efektywny, ale łatwy do zrozumienia i implementacji, dlatego wybraliśmy go na początek. Tablice możemy zastosować, jeśli tworzony słownik nie będzie posiadał docelowo zbyt dużo elementów.

Słownik zbudowany jest z par (klucz, wartość). Dlatego musimy utworzyć dwie tablice: jedną na klucze i drugą na wartości. Elementem słownika będą elementy o tym samym indeksie z obu tablic. Tablice muszą być odpowiednio duże, aby pomieścić wszystkie elementy słownika:

Klucze będą prostymi danymi: liczby całkowite, łańcuchy znakowe, itp. Klucze nie mogą się powtarzać, ponieważ służą one do wyboru odpowiedniej pary (klucz, wartość),

Wartości są dowolnego typu. Wartości mogą się powtarzać.

Jeśli klucze i wartości są tego samego typu (np. liczby lub teksty), to można użyć pojedynczej tablicy i słownik staje się symetryczny, tzn. klucze mogą łatwo stać się wartościami, a wartości kluczami, jeśli zachowana jest unikalność kluczy i wartości.

Dostęp do wartości w słowniku odbywa się przy pomocy kluczy. Wygląda to tak: Znajdujemy interesujący nas klucz w tablicy kluczy. W ten sposób otrzymamy indeks klucza. Następnie wykorzystujemy ten indeks do odwołania się w tablicy wartości do wartości skojarzonej z tym kluczem. Kolejność kluczy będzie dowolna. Umówmy się, iż pozycja pusta w tablicy kluczy (czyli taka, która nie zawiera żadnego klucza) będzie przechowywała wartość 0 lub pusty łańcuch tekstowy (żaden klucz takiej wartości nie może przyjmować). Nowe pary (klucz, wartość) będą wstawiane do tablic na pierwsze wolne miejsce.

Zamiast tablic statycznych można użyć tablic dynamicznych, jednakże wtedy zmodyfikować należy odpowiednio procedury słownika.

Deklaracje tablic słownika są następujące:

Pascal

...
const
  // Maksymalny rozmiar słownika
  MAX_D = rozmiar;

var
   // Tablica kluczy
   keys : array[0..MAX_D-1] of typ_kluczy;
   // Tablica wartości
   values : array[0..MAX_D-1] of typ_wartości;
...

C++

...
// Maksymalny rozmiar słownika
const int MAX_D = rozmiar;

// Tablica kluczy
typ_kluczy keys[MAX_D];
// Tablica wartości
typ_wartości values[MAX_D];
...

Basic

...
' Maksymalny rozmiar słownika
CONST MAX_D = rozmiar

' Tablica kluczy
DIM AS typ_kluczy keys(MAX_D-1)
' Tablica wartości
DIM AS typ_wartości values(MAX_D-1)
...

Python (dodatek)

# Maksymalny rozmiar słownika
MAX_D = rozmiar

# Tablica kluczy
keys = [...] * MAX_D
# Tablica wartości
values = [None] * MAX_D

do podrozdziału do strony

Przedstawione tu algorytmy zakładają, iż zostały utworzone obie tablice keys[ ] i values[ ] o rozmiarze MAX_D, do których mają bezpośredni dostęp.

Algorytmy operacji na słowniku utworzonym w tablicach

d_del(k) - Usuwa ze słownika parę (k, ...).

Algorytm przegląda tablicę keys[ ] i jeśli znajdzie w niej klucz k, to zastępuje go kluczem pustym, usuwa z tej samej pozycji wartość w tablicy values[ ] i zwraca indeks usuniętego klucza. Jeśli klucza nie znajdzie, to zwraca indeks pierwszej pustej pozycji. Jeśli słownik jest pełny, to zwraca -1.

Wejście:

k : poszukiwany klucz.

Wyjście:

Indeks pozycji usuniętej pary (klucz k, wartość) lub indeks pierwszej pustej pozycji lub -1, jeśli w słowniku brak klucza k, a słownik jest pełny.

Elementy pomocnicze:

i : zmienna pętli.
ip : indeks pierwszej pustej pozycji.
pusty : klucz nie związany z wartością.

Lista kroków:

K01: ip ← -1 ; to będzie indeks pustej pozycji
K02: Dla i = 0,1,...,MAX_D-1: ; szukamy klucza k
     wykonuj kroki K03...K09
K03:   Jeśli k = keys[i], ; klucz k znaleziony?
       to idź do kroku K07
K04:   Jeśli ip = -1 i keys[i] = pusty ; zapamiętujemy
K05:   to ip ← i ; pierwszą pustą pozycję
K06:   Następny obieg pętli K02
K07:   keys[i] ← pusty ; klucz k znaleziony, usuwamy go
K08:   Usuń wartość values[i] ; operacja zależna od typu wartości
K09:   Zakończ z wynikiem i ; zwracamy pozycję usuniętej pary
K10: Zakończ z wynikiem ip ; zwracamy pustą pozycję lub
     ; -1, jeśli słownik jest pełny

d_put(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) i zwraca w wyniku indeks tej pary. Jeśli w słowniku istnieje para o kluczu k, to zostanie zastąpiona nową parą (k, v). Jeśli słownik jest pełny, to nic nie jest w nim zmieniane, a operacja zwraca wartość -1.

Wejście:

k : klucz.
v : wartość.

Wyjście:

Indeks pozycji wstawionej pary (k, v) lub -1, jeśli w słowniku brak miejsca na nową parę (k, v).

Elementy pomocnicze:

ip : indeks wstawianej pary.
d_del(k) : usuwa ze słownika parę o kluczu k.

Lista kroków:

K01: ip ← d_del(k) ; usuwamy starą parę. W ip znajdzie się
     ; indeks usuniętej pary lub wolnego miejsca lub
     ; -1, jeśli słownik jest pełny
K02: Jeśli ip = -1, ; Jeśli w słowniku brak miejsca,
     to idź do kroku K05 ; to kończymy
K03: keys[ip] ← k ; umieszczamy w słowniku nową parę
K04: values[ip] ← v ; (k, v) i zwracamy jej pozycję
K05: Zakończ z wynikiem ip

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

Wejście:

k : klucz.

Wyjście:

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

Elementy pomocnicze:

i : indeks.
wartość specjalna : wartość zwracana w przypadku nieznalezienia klucza k.

Lista kroków:

K01: Dla i = 0,1,...,MAX_D-1: ; szukamy klucza k
     wykonuj krok K02
K02:   Jeśli k = keys[i], ; jeśli znaleziony, to
       to zakończ z wynikiem values[i] ; kończymy
K03: Zakończ z wynikiem wartość specjalna

d_size( ) - Oblicza liczbę kluczy w tablicy keys[ ]

Algorytm liczy liczbę kluczy w tablicy keys[ ].

Wyjście:

Liczba kluczy w słowniku.

Elementy pomocnicze:

i : indeksy.
c : licznik kluczy.
pusty : klucz nie związany z wartością.

Lista kroków:

K01: c ← 0 ; zerujemy licznik kluczy
K02: Dla i = 0,1,...,MAX_D-1: ; zliczamy klucze
     wykonuj krok K03
K03:   Jeśli keys[i] ≠ pusty, 
       to c ← c+1
K04: Zakończ z wynikiem c ; wynikiem jest liczba kluczy

do podrozdziału do strony

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 dwóch tablicach o pojemności 10 elementów. 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 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

// Przykładowy słownik w tablicach
// Data: 1.10.2024
// (C)2024 mgr Jerzy Wałaszek
//---------------------------

program dict;

const
  // Maksymalny rozmiar słownika
  MAX_D = 10;
  // Wartość specjalna
  SV = -1;

var
  keys   : array[0..MAX_D-1] of string;
  values : array[0..MAX_D-1] of real;

// Usuwa parę (klucz,wartość) ze słownika
// k - klucz usuwanej pary
//---------------------------------------
function d_del(k : string) : integer;
var
  i,ip : integer;

begin
  ip := -1;
  // Szukamy klucza k
  for i := 0 to MAX_D-1 do
  begin
    if k = keys[i] then
    begin
      keys[i] := '';
      values[i] := 0;
      ip := i;
      break;
    end;
    if (ip = -1) and (keys[i] = '') then
      ip := i;
  end;
  d_del := ip;
end;

// Wstawia do słownika nową parę
// (klucz, wartość)
// k - klucz
// v - wartość
//------------------------------
function d_put(k : string;
               v : real)
                 : integer;
var
  ip : integer;

begin
  ip := d_del(k);
  if ip > -1 then
  begin
    keys[ip]   := k;
    values[ip] := v;
  end;
  d_put := ip;
end;

// Zwraca wartość związaną
// z kluczem k
//------------------------
function d_get(k : string)
                 : real;
var
  i : integer;

begin
  d_get := SV;
  for i := 0 to MAX_D-1 do
    if k = keys[i] then
    begin
      d_get := values[i];
      break;
    end;
end;

// Zwraca liczbę kluczy
//---------------------
function d_size(): integer;
var
  c,i : integer;

begin
  c := 0;
  for i := 0 to MAX_D-1 do
    if keys[i] <> '' then inc(c);
  d_size := c;
end;

// Wyświetla zawartość słownika
// pomijając puste klucze
//-----------------------------
procedure d_print();
var
  i : integer;

begin
   writeln('Liczba kluczy: ',
           d_size());
   for i := 0 to MAX_D-1 do
     if keys[i] <> '' then
       writeln(keys[i]:7,' : ',
               values[i]:4:2);
   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;

begin
  randomize();

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

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

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

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

C++

// Przykładowy słownik w tablicach
// Data: 2.10.2024
// (C)2024 mgr Jerzy Wałaszek
//---------------------------

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

using namespace std;

// Maksymalny rozmiar słownika
const int MAX_D = 10;
// Wartość specjalna
const double SV = -1;

string keys[MAX_D];
double values[MAX_D];

// Usuwa parę (klucz,wartość) ze słownika
// k - klucz usuwanej pary
//---------------------------------------
int d_del(string k)
{
  int i,ip;

  ip = -1;
  // Szukamy klucza k
  for(i = 0; i < MAX_D; i++)
  {
    if(k == keys[i])
    {
      keys[i]   = "";
      values[i] = 0.0;
      ip = i;
      break;
    }
    if((ip == -1) && (keys[i] == ""))
      ip = i;
  }
  return ip;
}

// Wstawia do słownika nową parę
// (klucz, wartość)
// k - klucz
// v - wartość
//------------------------------
int d_put(string k, double v)
{
  int ip;

  ip = d_del(k);
  if(ip > -1)
  {
    keys[ip]   = k;
    values[ip] = v;
  }
  return ip;
}

// Zwraca wartość związaną
// z kluczem k
//------------------------
double d_get(string k)
{
  int i;

  for(i = 0; i < MAX_D; i++)
    if(k == keys[i])
      return values[i];
  return SV;
}

// Zwraca liczbę kluczy
//---------------------
int d_size()
{
  int c,i;

  c = 0;
  for(i = 0; i < MAX_D; i++)
    if(keys[i] != "") c++;
  return c;
}

// Wyświetla zawartość słownika
// pomijając puste klucze
//-----------------------------
void d_print()
{
  int i;

  cout << setprecision(2) << fixed;
  cout << "Liczba kluczy: "
       << d_size() << endl;
  for(i = 0; i < MAX_D; i++)
    if(keys[i] != "")
      cout << setw(7) << keys[i]
           << " : "
           << setw(4) << values[i]
           << 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;

  srand(time(NULL));

  // 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(names[x],v);
  }
  d_print();

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

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

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

Basic

' Przykładowy słownik w tablicach
' Data: 1.10.2024
' (C)2024 mgr Jerzy Wałaszek
'---------------------------

' Maksymalny rozmiar słownika
Const MAX_D = 10
' Wartość specjalna
Const SV = -1.0

Dim Shared As String keys(MAX_D-1)
Dim Shared As Double values(MAX_D-1)

' Usuwa parę (klucz,wartość) ze słownika
' k - klucz usuwanej pary
'---------------------------------------
Function d_del(ByRef k As String) _
                       As Integer
  Dim As Integer i,ip

  ip = -1
  ' Szukamy klucza k
  For i = 0 To MAX_D-1
    If k = keys(i) Then
      keys(i) = ""
      values(i) = 0.0
      ip = i
      Exit For
    End If
    If (ip = -1) AndAlso _
       (keys(i) = "") Then ip = i
  Next
  d_del = ip
End Function

' Wstawia do słownika nową parę
' (klucz, wartość)
' k - klucz
' v - wartość
'------------------------------
Function d_put(ByRef k As String, _
               ByVal v As Double) _
                       As Integer
  Dim As Integer ip

  ip = d_del(k)
  If ip > -1 Then
    keys(ip)   = k
    values(ip) = v
  End If
  d_put = ip
End Function

' Zwraca wartość związaną
' z kluczem k
'------------------------
Function d_get(ByRef k As String) _
                       As Double
  Dim As Integer i

  d_get = SV
  For i = 0 To MAX_D-1
    If k = keys(i) Then
      d_get = values(i)
      Exit For
    End If
  Next
End Function

' Zwraca liczbę kluczy
'---------------------
Function d_size As Integer
  Dim As Integer c,i

  c = 0
  For i = 0 To MAX_D-1
    If keys(i) <> "" Then c += 1
  Next
  d_size = c
End Function

' Wyświetla zawartość słownika
' pomijając puste klucze
'-----------------------------
Sub d_print
  Dim As Integer i

   Print "Liczba kluczy: "; d_size
   For i = 0 To MAX_D-1
     If keys(i) <> "" Then _
       Print Using "\     \ : #.##";_
                   keys(i);values(i)
   Next
   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

Randomize

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

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

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

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

Python (dodatek)

# Przykładowy słownik w tablicach
# Data: 1.10.2024
# (C)2024 mgr Jerzy Wałaszek
#---------------------------

import random

# Maksymalny rozmiar słownika
MAX_D = 10
# Wartość specjalna
SV = -1.0

# Tablica kluczy
keys = [""] * MAX_D
# Tablica wartości
values = [0] * MAX_D


# Usuwa parę (klucz,wartość) ze słownika
# k - klucz usuwanej pary
#---------------------------------------
def d_del(k):
    global keys, values, MAX_D
    ip = -1
    # Szukamy klucza k
    for i in range(MAX_D):
        if k == keys[i]:
            keys[i] = ""
            values[i] = 0
            ip = i
            break
        if (ip == -1) and (keys[i] == ""):
            ip = i
    return ip


# Wstawia do słownika nową parę
# (klucz, wartość)
# k - klucz
# v - wartość
#------------------------------
def d_put(k, v):
    global keys, values
    ip = d_del(k)
    if ip > -1:
        keys[ip]   = k
        values[ip] = v
    return ip


# Zwraca wartość związaną
# z kluczem k
#------------------------
def d_get(k):
    global keys, values, MAX_D, SV

    for i in range(MAX_D):
        if k == keys[i]:
            return values[i]
    return SV


# Zwraca liczbę kluczy
#---------------------
def d_size():
    global keys, MAX_D
    c = 0
    for i in range(MAX_D):
        if keys[i] != "":
            c += 1
    return c


# Wyświetla zawartość słownika
# pomijając puste klucze
#-----------------------------
def d_print():
    global keys, values, MAX_D
    print("Liczba kluczy:", d_size())
    for i in range(MAX_D):
       if keys[i] != "":
           print("%7s : %4.2f" %
             (keys[i],values[i]))
    print("--------------")


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

# Klucze
names = ["Janusz", "Marian",
         "Henryk", "Adrian",
         "Bogdan", "Cyprian",
         "Dariusz","Zenon",
         "Tadeusz","Karol"]

# W słowniku umieszamy 7 danych
print("TWORZENIE")
for i in range(7):
    x = random.randrange(10)
    v = random.randrange(1000)/100
    d_put(names[x],v)
d_print()

# Dodajemy 5 elementów
print("DODAWANIE")
for i in range(5):
    x = random.randrange(10)
    v = random.randrange(1000)/100
    d_put(names[x],v)
d_print()

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

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

Wynik:

TWORZENIE
Liczba kluczy: 5
 Janusz : 4.86
 Adrian : 0.40
  Zenon : 2.77
Cyprian : 8.79
 Henryk : 3.90
--------------
DODAWANIE
Liczba kluczy: 6
 Janusz : 4.86
 Adrian : 0.40
  Zenon : 5.67
Cyprian : 1.52
 Henryk : 3.90
Dariusz : 1.81
--------------
USUWANIE
Liczba kluczy: 3
 Janusz : 4.86
 Henryk : 3.90
Dariusz : 1.81
--------------
WYSZUKIWANIE
klucza Cyprian brak
klucz Dariusz obecny, v = 1.81
klucza Cyprian brak
klucza Bogdan brak
klucz Janusz obecny, v = 4.86
klucz Henryk obecny, v = 3.90
klucz Janusz obecny, v = 4.86
klucza Cyprian brak
klucza Zenon brak
klucza Adrian brak

do podrozdziału do 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.

Słownik w tablicy

Implementacja

Algorytmy

Algorytmy operacji na słowniku utworzonym w tablicach

d_del(k) - Usuwa ze słownika parę (k, ...).

Wejście:

Wyjście:

Elementy pomocnicze:

Lista kroków:

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

Wejście:

Wyjście:

Elementy pomocnicze:

Lista kroków:

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

Wejście:

Wyjście:

Elementy pomocnicze:

Lista kroków:

d_size( ) - Oblicza liczbę kluczy w tablicy keys[ ]

Wyjście:

Elementy pomocnicze:

Lista kroków:

Przykładowe programy