Forum
Aktif konular
Üyeler
Kurallar
Arama
Computed Chaining Sample Computed Chaining Sample
-
basit bir computed chaining örneğidir. c ile kodlanmıştır. isteyenlere c++ ile de kodlayabilirim.
işinize yaraması dileğimle.
#include "stdafx.h"
#include "stdlib.h"
#include <stack>
using std::stack;
void insert(int **numbers, int number);
int hash(int number, int key);
int increment(int number);
int search(int **numbers, int number);
void print(int **numbers);
void packingFactorCalculate(int **numbers);
int **resizeTable(int **numbers);
void del(int **numbers, int key);
int tableSize = 11; //this is a global variable for table size
double packingFactor = 0;
int _tmain(int argc, _TCHAR* argv[])
{
int **numbers;
numbers = (int **)malloc(sizeof(int)*2);
numbers[0] = (int*)malloc(tableSize*sizeof(int));
numbers[1] = (int*)malloc(tableSize*sizeof(int));
int number;
int i = 0;
for(int i = 0; i<tableSize; i++)
{
numbers[0][i] = -1;
numbers[1][i] = -1;
}
printf("Table size is 11 for begining !!\n---------------------------------\n");
while(1)
{
printf("\n1-Insert \n2-Search\n3-Delete\n4-Exit - > ");
scanf("%d",&number);
if(number == 1)
{
printf("\n\tEnter Number\n");
scanf("%d",&number);
insert(numbers,number);
packingFactorCalculate(numbers);
printf("\nPacking Factor -> %lf",packingFactor);
if(packingFactor >= 0.95)
{
numbers = resizeTable(numbers);
}
print(numbers);
}
else if (number == 2)
{
printf("\n\tEnter Number\n");
scanf("%d",&number);
number = search(numbers,number);
if(number != -1)
{
printf("\n\t%d. record is %d",number,numbers[0][number]);
}
else
{
printf("Record could not be found !!");
}
}
else if(number == 3)
{
printf("\n\tEnter Number to delete\n");
scanf("%d",&number);
del(numbers,number);
print(numbers);
}
else if(number == 4)
{
break;
}
}
return 0;
}
int **resizeTable(int **numbers)
{
int nextPrime = tableSize;
int i,j;
int counter = 0;
for(i = tableSize +1; i<99999; i++)
{
counter = 0;
for(j = 2; j<tableSize; j++)
{
if(i%j == 0)
{
counter++;
break;
}
}
if(counter == 0)
{
nextPrime = i;
counter = tableSize;
tableSize = i;
printf("\n\aNew Table size is %d\n",nextPrime);
break;
}
}
int **newNumbers;
newNumbers = (int **)malloc(sizeof(int)*2);
newNumbers[0] = (int *) malloc(tableSize*sizeof(int));
newNumbers[1] = (int *) malloc(tableSize*sizeof(int));
for( i = 0 ; i<tableSize; i++)
{
newNumbers[0][i] = -1;
newNumbers[1][i] = -1;
}
for(i = 0; i<counter;i++)
{
if(numbers[0][i] == -2)
insert(newNumbers,-1);
insert(newNumbers,numbers[0][i]);
}
free(numbers);
return newNumbers;
}
void print(int **numbers)
{
int i = 0;
printf("\nNo. Number Home Link incr\n-----------------------------\n");
for( i = 0; i<tableSize; i++)
{
printf("%-6d%-6d%-6d%-6d%-6d\n",i,numbers[0][i],hash(numbers[0][i],tableSize),numbers[1][i],increment(numbers[0][i]));
}
}
void packingFactorCalculate(int **numbers)
{
int i = 0;
int counter = 0;
for(i = 0;i<tableSize;i++)
{
if(numbers[0][i] != -1 && numbers[0][i] != -2)
counter++;
}
packingFactor = (double)counter / tableSize;
}
void insert(int **numbers, int number)
{
int hashAddress = hash(number,tableSize);
if(search(numbers,number) != -1)
{
printf("Dublicated record !");
return;
}
if(numbers[0][hashAddress] == -1 || numbers[0][hashAddress] == -2)
{
numbers[0][hashAddress] = number;
return;
}
else
{
int incr = 1;
int preAddress = hashAddress;
int nextAddress = (hashAddress + increment(numbers[0][hashAddress]*incr))%tableSize;
if(hash(numbers[0][hashAddress],tableSize) != hashAddress)
{
int hashAddresOfRecordNotAtHomeAddress = hash(numbers[0][hashAddress],tableSize);
int nextHashAddressForReplacement = hashAddresOfRecordNotAtHomeAddress;
int counter = 1;
while(1) //counts number of chain elements
{
if(numbers[1][nextHashAddressForReplacement] != -1)
{
counter = counter + 1;
nextHashAddressForReplacement = (nextHashAddressForReplacement + increment(numbers[0][nextHashAddressForReplacement])*numbers[1][nextHashAddressForReplacement])%tableSize;
}
else
{
break;
}
}
int *numbersTemp;
numbersTemp = (int *) malloc(sizeof(int)*counter);
hashAddresOfRecordNotAtHomeAddress = hash(numbers[0][hashAddress],tableSize);
nextHashAddressForReplacement = hashAddresOfRecordNotAtHomeAddress;
counter = 0;
while(1)
{
preAddress = nextHashAddressForReplacement;
numbersTemp[counter] = numbers[0][nextHashAddressForReplacement];
counter = counter + 1;
if(numbers[1][nextHashAddressForReplacement] != -1)
nextHashAddressForReplacement = (nextHashAddressForReplacement + increment(numbers[0][nextHashAddressForReplacement])*numbers[1][nextHashAddressForReplacement])%tableSize;
numbers[0][preAddress] = -1;
numbers[1][preAddress] = -1;
if(preAddress == nextHashAddressForReplacement)
break;
}
numbers[0][hashAddress] = number;
hashAddresOfRecordNotAtHomeAddress = hash(numbers[0][nextAddress],tableSize);
nextHashAddressForReplacement = hashAddresOfRecordNotAtHomeAddress;
for(int i = 0; i<counter; i++)
{
insert(numbers,numbersTemp[i]);
}
free(numbersTemp);
}
else
{
nextAddress = hashAddress;
preAddress = hashAddress;
incr = 1;
while(numbers[1][nextAddress] != -1)
{
nextAddress = (nextAddress + increment(numbers[0][nextAddress])*numbers[1][nextAddress])%tableSize;
preAddress = nextAddress;
}
nextAddress = preAddress;
while(1)
{
nextAddress = (preAddress + increment(numbers[0][preAddress])*incr)%tableSize;
if(numbers[0][nextAddress] != -1 && numbers[0][nextAddress] != -2)
{
incr = incr +1;
}
else
{
numbers[0][nextAddress] = number;
numbers[1][preAddress] = incr;
break;
}
}
/*while(1)
{
if(numbers[0][nextAddress] == -1 || numbers[0][nextAddress] == -2)
{
numbers[0][nextAddress] = number;
numbers[1][preAddress] = incr;
return;
}
else
{
if(numbers[1][nextAddress] != -1)
{
nextAddress = (temp + increment(numbers[0][temp])*incr)%tableSize;
incr = incr + 1;
}
else
{
incr = 1;
temp = nextAddress;
while(1)
{
nextAddress = (temp + increment(numbers[0][temp])*incr)%tableSize;
if(numbers[0][nextAddress] == -1 || numbers[0][nextAddress] == -2)
break;
else
incr = incr +1;
}
}
}
}*/
}
}
}
int search(int **numbers, int number)
{
int hashAddress = hash(number,tableSize);
if(numbers[0][hashAddress] == number)
{
return hashAddress;
}
else
{
int nextAddress = (hashAddress + increment(numbers[0][hashAddress])*numbers[1][hashAddress]) % tableSize;
while (1)
{
if(numbers[0][nextAddress] == number)
{
return nextAddress;
}
else if(numbers[0][nextAddress] == -1)
{
return -1;
}
else
{
if(numbers[1][nextAddress] == -1)
return -1;
nextAddress = (nextAddress + increment(numbers[0][nextAddress])*numbers[1][nextAddress]) % tableSize;
}
}
}
}
int hash(int number, int key)
{
return number%tableSize;
}
int increment(int number)
{
number = (number/tableSize)%tableSize;
if(number == 0)
return 1;
else
return number;
}
void del(int **numbers, int key)
{
int place = search(numbers,key);
if(place != -1)
numbers[0][place] = -2;
}
Kısayol
Şikayet
Özel Mesaj
Alıntı yap
Cevapla