Hash

c-plus-plus

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <string.h>

#define M 5003

int hash_first(char* text,int lenght);
int hash_druha(char*text,int lenght);
int linear_search(char* text, int lenght,int pos);
int quadratic_search(char* text,int lenght,int pos);
int double_code(char* text,int lenght,int pos);

int main()
{
    char* tab1[M], *tab2[M], *tab3[M], znak,*text;
    int word_lenght,i,j,k=0,pos;
    float count_lin = 0,count_quad = 0,count_double = 0;
    for(i=0;i<M;i++)
        {
            tab1[i] = "-1";
            tab2[i] = "-1";
            tab3[i] = "-1";
        }
    srand(time(0));
    printf("\t Linear \t Kvadrat \t Dvoji hash. \n");
    for(i=0;i<M;i++)
        {
            word_lenght = rand() % 18 + 3; //lenght slova od 3 do 20 znaků; //vygeneruje ascii jednoho znaku;
            text = malloc(word_lenght*(sizeof(char)));
            //printf("lenght slova je %d \n alokovana velikost je %d \n\n",word_lenght,word_lenght*sizeof(char));
            for(j=0;j<word_lenght;j++)
                {
                    znak = (rand() % 26 + 97);
                    text[j] = znak;
                }

            pos = linear_search(text,word_lenght,k);
            count_lin++;
            if(tab1[pos] != "-1")
                {
                    while(tab1[pos] != "-1")
                        {
                            k++;
                            pos = linear_search(text,word_lenght,k);
                            count_lin++;
                        }
                    tab1[pos] = text;
                    //count_lin++;
                }
            else
                {
                    tab1[pos] = text;
                    //count_lin++;
                }
            k=0;
            pos = quadratic_search(text,word_lenght,k);
            count_quad++;
            if(tab2[pos] != "-1")
                {
                    while(tab2[pos] != "-1")
                        {
                            k++;
                            pos = quadratic_search(text,word_lenght,k);
                            count_quad++;
                        }
                    tab2[pos] = text;
                    //count_quad++;
                }
            else
                {
                    tab2[pos] = text;
                    //count_quad++;
                }

            k=0;
            pos = double_code(text,word_lenght,k);
            count_double++;
            if(tab3[pos] != "-1")
                {
                    while(tab2[pos] != "-1")
                        {
                            k++;
                            pos = double_code(text,word_lenght,k);
                            count_double++;
                        }
                    tab3[pos] = text;
                    //count_double++;
                }
            else
                {
                    tab3[pos] = text;
                    //count_double++;
                }

            //Výpisy po dosažení procent
            if(i == 2502)
                {
                    printf("50%% \t %f \t %f \t %f \n",(count_lin / 2502),(count_quad / 2502),(count_double / 2502));
                }
            if(i == 3752)
                {
                    printf("75%% \t %f \t %f \t %f \n",(count_lin / 3752),(count_quad / 3752),(count_double / 3752));
                }
            if(i == 4503)
                {
                    printf("90%% \t %f \t %f \t %f \n",(count_lin / 4503),(count_quad / 4503),(count_double / 4503));
                }
            if(i == 4753)
                {
                    printf("95%% \t %f \t %f \t %f \n",(count_lin / 4753),(count_quad / 4753),(count_double / 4753));
                }
        }

    return 0;
}

int hash_first(char* text,int lenght)
{
    int vysl,p = 127,q = 31;
    vysl = p*text[0] + q*text[1] + text[lenght-1] + lenght;
    vysl = vysl % M;
    return vysl;
}

int hash_second(char*text,int lenght)
{
    unsigned int vysl,p = 127,q = 31;
    vysl = 1 + (p*text[0] + q*text[1] + text[lenght-1] + lenght) % (M - 1);
    return vysl;
}

int linear_search(char* text, int lenght,int pos)
{
    int vysl;
    vysl = (hash_first(text,lenght) + pos)% M;
    return vysl;
}

int quadratic_search(char* text,int lenght,int pos)
{
    int vysl;
    vysl = (hash_first(text,lenght) + 3*pos + 5*pos*pos) % M;
    return vysl;
}

int double_code(char* text,int lenght,int pos)
{
    int vysl;
    vysl = (hash_first(text,lenght) + pos*hash_second(text,lenght)) % M;
    return vysl;
}

Neformátovaný

Přidáno: 9.12.2012
Expirace: Neuvedeno

Autor: Onda.Zadnik