[C++] Tablice Mieszające
: 11 lis 2013, o 21:36
Przeprowadzić eksperymenty dotyczące wstawiania do tablicy haszowanej rozmiaru m metodą
adresowania otwartego przy wykorzystaniu:
• adresowania linowego z funkcją \(\displaystyle{ h \left( k, i \right) = \left( h ' \left( k \right) + i \right) \mod m}\),
• adresowania kwadratowego z funkcją \(\displaystyle{ h \left( k, i \right) = \left( h ' \left( k \right) + c_1 \cdot i + c_2 \cdot i ^{2} \right) \mod m}\)
• adresowania dwukrotnego z funkcją \(\displaystyle{ h \left( k, i \right) = \left( h ' \left( k \right) + i \cdot h '' \left( k \right) \right) \mod m}\)
gdzie: \(\displaystyle{ k}\) – liczba całkowita nieujemna – jest wstawianym kluczem, \(\displaystyle{ h \left( k, i \right)}\) – miejsce wstawiania \(\displaystyle{ k}\)
w \(\displaystyle{ i}\)-tej próbie, oraz \(\displaystyle{ h ′ \left( k \right) = k \mod m}\), a \(\displaystyle{ h '' \left( k \right) = 1 + k \mod \left( m - 1 \right)}\)
A wiec napisałem taki kod:
Dla liniowego ładnie działa wszystko. Dla kwadratowego przy m=2200 wysypuje Naruszenie ochrony pamięci, A przy podwójnym niestety już przy m = 25 ma problem z obliczeniem tego i dochodzi do próby kilkuset tysiecznej i nie może wstawić. proba=i, length=m. Jakby był ktoś w stanie sprawdzić czemu tak sie dzieje, to byłbym bardzo wdzieczny.
adresowania otwartego przy wykorzystaniu:
• adresowania linowego z funkcją \(\displaystyle{ h \left( k, i \right) = \left( h ' \left( k \right) + i \right) \mod m}\),
• adresowania kwadratowego z funkcją \(\displaystyle{ h \left( k, i \right) = \left( h ' \left( k \right) + c_1 \cdot i + c_2 \cdot i ^{2} \right) \mod m}\)
• adresowania dwukrotnego z funkcją \(\displaystyle{ h \left( k, i \right) = \left( h ' \left( k \right) + i \cdot h '' \left( k \right) \right) \mod m}\)
gdzie: \(\displaystyle{ k}\) – liczba całkowita nieujemna – jest wstawianym kluczem, \(\displaystyle{ h \left( k, i \right)}\) – miejsce wstawiania \(\displaystyle{ k}\)
w \(\displaystyle{ i}\)-tej próbie, oraz \(\displaystyle{ h ′ \left( k \right) = k \mod m}\), a \(\displaystyle{ h '' \left( k \right) = 1 + k \mod \left( m - 1 \right)}\)
A wiec napisałem taki kod:
Kod: Zaznacz cały
#include <math.h>
#include <cstdlib>
#include <ctime>
#include <stdio.h>
#include <iostream>
void RandomNumber(int A[],int n)
{
int i=0;
while(i<n) //przechodzimy po każdym elemencie tablicy i przypisujemy mu jakąś losową wartość
{
A[i]=(rand()) % (n)+1 ; //(rand()) % (n*n-1) losuje liczbę i (%) przeprowadza operację modulo z (n*n-1) czyli zwraca resztę z dzielenia wylosowanej liczby przez (n*n-1)
// std::cout<<A[i]<<" "; // po odkomentowaniu drukuje nieposortowaną tablice
i++;
}
//std::cout<<"
";
}
void dwukrotne(int A[], int m,int c){
int i=0;
int proba=1;
int * tmp=new int[m];
while(i<m) {
tmp[i]=0;
i++;
}
i=0;
while(i<m){
while(true){
if(tmp[((A[i]%m) + proba * ((1+A[i])%(m-1))) % m]==0){
tmp[((A[i]%m) + proba * ((1+A[i])%(m-1))) % m]=A[i];
break;
}
//if(i%(long int)(m/50)==0){
//std::cout<<i+1<<" "<<proba<<" "<<"
";
//std::cout<<proba<<" "<<"
";
//}
std::cout<<proba<<", "<<"
";
proba++;
}
//std::cout<<proba<<" ";
proba=1;
i++;
}
i=0;
std::cout<<"
";
// while(i<m) {
//std::cout<<tmp[i]<<" ";
// i++;
//}
}
void kwadratowe(int A[], int m,int c){
int i=0,proba=1;
int * tmp=new int[m];
while(i<m) {
tmp[i]=0;
i++;
}
i=0;
while(i<m){
while(true){
if(tmp[(( int)((A[i]%m)+proba+c*pow(proba,2)) ) % m]==0){
tmp[((int)((A[i]%m)+proba+c*pow(proba,2)) ) % m]=A[i];
break;
}
proba++;
}
//if(i%(long int)(m/50)==0){
std::cout<<m<<", "<<"
";
//std::cout<<i+1<<" "<<proba<<" "<<"
";
//std::cout<<proba<<" "<<"
";
//}
proba=1;
i++;
}
i=0;
std::cout<<"
";
//while(i<m) {
//std::cout<<tmp[i]<<" ";
// i++;
//}
}
void liniowe(int A[], int m){
int i=1,proba=1,e=0;
int tmp[m];
while(i<m) {
tmp[i]=0;
i++;
}
i=0;
while(i<m){
while(true){
if(tmp[(A[i]+proba)%m]==0){
tmp[(A[i]+proba)%m]=A[i];
break;
}
proba++;
}
if(i%(int)floor(m/50)==0){
// std::cout<<m<<", "<<"
";
//std::cout<<i+1<<" "<<proba<<" "<<"
";
//std::cout<<proba<<" "<<"
";
e++;}
proba=1;
i++;
}
i=0;
//while(i<m) {
//std::cout<<tmp[i]<<" ";
// i++;
//}
}
int main(int argc, char **argv)
{
int length = 25;
srand( time( NULL ) );
while(length<=1000){
int* A= new int[length];
RandomNumber(A,4*length);
//liniowe(A,length);
kwadratowe(A,4*length,2*length);
//dwukrotne(A,length,length);
length+=25;
}
//kwadratowe(A,length,2*length);
//dwukrotne(A,length,2*length);
return 0;
}
Możesz debugować i szukać, czy nie ma tam błędu, aczkolwiek osobiście poprzestałbym na uzasadnieniu, że owa funkcja mieszająca jest do niczego.