Redispersió en taules de dispersió amb sinònims encadenats indirectes X64175


Statement
 

pdf   zip   main.cc

html

Donada la classe dicc que permet gestionar diccionaris amb claus enteres, cal implementar els mètodes:

// Pre: Cert // Post: Retorna el factor de càrrega de la taula de dispersió float factor_de_carrega() const; // Pre: Cert // Post: Redimensiona la taula de dispersió amb una mida el doble que // l’anterior més un (_M => 2*_M+1) void redispersio();

Els diccionaris s’implementen amb taules de dispersió amb sinònims encadenats indirectes. Les llistes de sinònims estan ordenades per la clau.

Cal enviar a jutge.org la següent especificació de la classe dicc i la implementació dels mètodes dins del mateix fitxer (la resta de mètodes públics ja estan implementats).

#include <iostream> using namespace std; typedef unsigned int nat; class dicc { // Taula de dispersió sinònims encadenats indirectes // Les llistes de sinònims estan ordenades per clau public: // Constructora per defecte. Crea un diccionari buit // en una taula de dispersió de mida m > 0 dicc(nat m); // Destructora ~dicc(); // Retorna quants elements (claus) té el diccionari. nat quants() const; // Impressió per cout de totes les claus del diccionari segons l’ordre // en que estan a cadascuna de les llistes encadenades indirectes void print() const; // Pre: Cert // Post: Insereix la clau k en el diccionari. Si ja hi era, no fa res. // Redimensiona la taula de dispersió amb una mida el doble que // l’anterior més un si el factor de càrrega és superior a 0.8 void insereix(const int &k); // Pre: Cert // Post: Retorna el factor de càrrega de la taula de dispersió float factor_de_carrega() const; // Pre: Cert // Post: Redimensiona la taula de dispersió amb una mida el doble que // l’anterior més un (_M => 2*_M+1) void redispersio(); private: struct node_hash { int _k; // Clau node_hash* _seg; }; node_hash **_taula; // Taula amb punters a les llistes de sinònims nat _M; // Mida de la taula nat _quants; // Nº d’elements guardats al diccionari static long const MULT = 31415926; // Calcula un valor de dispersió entre 0 i LONG_MAX a partir de k static long h(int k); // Destrueix la llista de nodes apuntats per p static void esborra_nodes(node_hash *p); // Aquí va l’especificació dels mètodes privats addicionals }; // Aquí va la implementació dels mètodes públics factor_de_carrega, redispersio i // dels mètodes privats addicionals };



Degut a que jutge.org només permet l’enviament d’un fitxer amb la solució del problema, en el mateix fitxer hi ha d’haver l’especificació de la classe i la implementació dels mètodes factor_de_carrega i redispersio (el que normalment estarien separats en els fitxers .hpp i .cpp).

Per testejar la classe disposes d’un programa principal que llegeix un conjunt d’elements, els insereix en un diccionari i mostra el seu contingut, desprès llegeix un segon conjunt d’elements, els insereix en el mateix diccionari i mostra novament el seu contingut.

Entrada

L’entrada té tres línies: la primera conté un natural positiu amb la dimensió inicial de la taula de dispersió i les altres dos contenen enters separats amb espais, són els enters que s’insereixen en el diccionari.

Sortida

Escriu el contingut del diccionari dos vegades: desprès d’inserir el primer conjunt d’enters i desprès d’inserir el segon conjunt d’enters. Cada vegada es mostra en diferents línies la quantitat d’elements que té i els elements que conté cadascuna de les llistes de sinònims encadenats indirectes (els elements de cada llista apareixen separats amb un espai i en el mateix ordre en que es guarden).

Observació

Per calcular el valor de dispersió utilitza el mètode h que ja està implementat i que permet calcular un valor de dispersió entre 0 i LONG_MAX (el valor long int més gran que permet el compilador) a partir d’una clau entera.

Només cal enviar la classe requerida i la implementació dels mètodes factor_de_carrega i redispersio. Pots ampliar la classe amb mètodes privats. Segueix estrictament la definició de la classe de l’enunciat.

Public test cases

  • Input

    13
5 -3 8 2 -1 7 -7 -6
7 -2 9 5 -3 2 -7 4

    Output

    Nº elem: 8
Factor de càrrega: 0.615385
0: -1 7 
1: 
2: 
3: 8 
4: 
5: -3 2 
6: -6 5 
7: 
8: 
9: -7 
10: 
11: 
12: 
-----------
Nº elem: 11
Factor de càrrega: 0.407407
0: -1 
1: 
2: 
3: 
4: -3 -2 2 
5: 7 
6: 
7: -7 
8: 
9: 
10: 9 
11: 
12: 
13: 8 
14: 
15: -6 5 
16: 
17: 
18: 
19: 4 
20: 
21: 
22: 
23: 
24: 
25: 
26: 
-----------

  • Input

    29
5 -5 3 -3 9 -9 2 -2 -5 5 1 -1 7 -7 0 4 -4 8 -8 6 -6
2 11 4 12 8 14 0 10 17 13

    Output

    Nº elem: 19
Factor de càrrega: 0.655172
0: -1 0 
1: 
2: -2 1 9 
3: -7 6 
4: -3 2 
5: 
6: 
7: -8 7 
8: -4 3 
9: 
10: 
11: -6 5 
12: 
13: 
14: 
15: 
16: 
17: -9 -5 4 8 
18: 
19: 
20: 
21: 
22: 
23: 
24: 
25: 
26: 
27: 
28: 
-----------
Nº elem: 25
Factor de càrrega: 0.423729
0: -1 0 
1: 
2: 
3: 
4: 
5: 
6: 9 
7: 
8: -5 4 
9: 
10: 17 
11: 
12: -6 5 
13: 
14: 
15: 
16: 10 
17: 
18: 
19: -4 3 
20: 12 
21: 
22: 
23: -2 1 
24: 
25: -9 8 
26: 
27: 
28: 
29: 
30: 
31: 11 
32: 
33: 
34: 
35: 
36: 
37: 
38: 
39: -3 2 
40: 
41: 
42: 
43: 
44: 
45: 
46: 
47: 
48: 13 
49: -8 7 
50: 
51: 
52: -7 6 
53: 14 
54: 
55: 
56: 
57: 
58: 
-----------

  • Input

    13
5 -5 3 -3 9 -9 2 -2 -5 5 1 -1 7 -7 0 4 -4 8 -8 6 -6
2 11 4 12 8 14 0 10 17 13

    Output

    Nº elem: 19
Factor de càrrega: 0.703704
0: -1 0 
1: 
2: 
3: 
4: -3 -2 1 2 
5: -8 7 
6: 
7: -7 6 
8: -4 3 
9: 
10: 9 
11: 
12: 
13: -9 8 
14: 
15: -6 5 
16: 
17: 
18: 
19: -5 4 
20: 
21: 
22: 
23: 
24: 
25: 
26: 
-----------
Nº elem: 25
Factor de càrrega: 0.454545
0: -1 0 
1: 
2: 
3: -5 4 
4: 
5: 
6: 
7: 
8: 
9: 
10: 
11: 
12: 
13: 
14: 
15: 
16: 
17: 
18: 
19: -2 1 
20: 
21: 
22: -8 7 
23: 
24: 
25: 10 
26: 
27: 
28: 
29: 
30: 
31: 
32: -6 5 
33: 
34: 9 
35: 
36: 
37: 
38: 14 
39: 
40: 17 
41: 11 12 
42: -7 6 
43: -9 8 
44: 
45: -4 3 
46: 
47: 
48: 
49: 13 
50: -3 2 
51: 
52: 
53: 
54: 
-----------
    • Information
    Author
    Jordi Esteve
    Language
    Catalan
    Official solutions
    C++
    User solutions
    C++