PDA

Visualizza la versione completa : [C++] Algoritmo di hashing su vettore


gaten
06-05-2011, 18:24
Salve ragazzi, stò cercando di creare una cosa particolare attraverso un array di strutture(nel mio caso un array di liste).

Praticamente io ho un array di interi (int A[100]), dopodichè attraverso una function, calcolo la posizione del puntatore ad una delle liste in questo modo:

int elem;
elem=rand() % 100;
position=elem % 100;

quindi, se l'elemento generato dalla function rand è 60, io avrò: 60 / 100 = 0.6 quindi, 0.
In definitiva, 60, dovrà essere il primo elemento di una lista, la quale viene puntata dalla posizione 0 dell'array A. Quindi avrò una cosa del tipo:

|*||_|_|_|_|_|_|
|
|
if elementi[position]==NULL
elementi[position]->value=elem;
elementi[position]->link=NULL;

in seguito, l'elemento di rand sarà 21, position sarà uguale a 10 e quindi:


|_||_|_|_|_|_|_|_|_|_|*|

|
|
if elementi[position]==NULL
elementi[position]->value=elem;
elementi[position]->link=NULL;

Però, potrebbe capitare che rand = 100 quindi, position è nuovamente uguale a 0 e abbiamo visto in precedenza che in 0 già c'era 60 quindi 100 deve andare nell'elemento successivo della lista con positione 0

Io ho pensato una cosa di questo tipo:



#include<iostream>
#include<stdlib.h>

#define DIM 100

using namespace std;


typedef struct nodo {
int value;
nodo *link;
} lista;


/* prototipi delle functions */
void hash(int A[DIM], lista *elementi);
bool searchElement(int A[DIM], int elemento, lista *elementi);

int main()
{

lista *elementi=NULL;
int elemento;
int A[DIM];

/* utilizzo il metodo hash */
hash(A, elementi);
cout<<"Qual'è l'elemento da cercare?"<<endl;
cin>>elemento;
searchElement(A, elemento, elementi);
}


void hash(lista *elementi){

int i, position, elem;
lista *new_element;

for (i=0; i<DIM; i++){

elem=rand() % 100;

position=elem % DIM;

if (elementi[position] == NULL){
elementi[position]->value=elem;
elementi[position]->link=NULL;
} else
{
new_element=new lista;

while (elementi[position] != NULL){
new_element->value=elem;
new_element->link=NULL;
elementi[position]->link=new_element;
}
}
}
}


bool searchElement(int elemento, lista *elementi){

int i, position;
bool exist=false;
lista *temp;

position=elemento % DIM;

i=0;
while (!exist && i<DIM){
if(elementi[position] == NULL){
exist=false;
}else
{
temp=elementi[position];
while (temp != NULL){
if (temp->value == elemento){
exist=true;
}else
{
temp=temp->link;
}

}
}
}

return exist;
}


Praticamente non saprei come fare puntare la posizione dell'array A alla lista di posizione , position(es. 10).

Grazie anticipatamente.

Loading