Hash Table for text word incidence

Asked

Viewed 71 times

0


This problem was best illustrated here: Error in vector copy of structured type


Summary:

I am developing an index dictionary, which stores the incidence of a word of text (input) using a hash table closed address open with linear scan (linear Probing); And I’m having a rather strange mistake.

Ex:

 O mundo eh belo   [linha1]
 O mundo eh bacana [linha2]

key = world; lines= 1 and 2; one of incidences = 2;

I have the following structured type:

typedef struct dicionario
{
 char chave[21];//recebe uma string

 int* linhas;//recebe um vetor de inteiros

 int tam_linhas;//tamanho do vetor de inteiros

}Dicionario;

First, initialize Dictionary* table, and malloco the same. Second, initialize Dictionary* tabela2, but not malloco;

tabela2 will be my reserve table, which will only mallocar and use when my LOAD_FACTOR1 is greater than 0.5;

When mine load_factor1 is larger, I allocate space to tabela2, which will have approximately double the table size, and I invoke a function2 which aims to pass all table elements to tabela2;

However, nothing of tabela2 is changed by the function2. And if I try to change by main(), an error occurs.

The code is here: http://ideone.com/rbhYhZ

I just need to be able to make that function2 work properly;


1 ratio between the number of distinct keys in the table and the maximum capacity of the table

2void reallocaTabela(Dicionario* tabela, Dicionario* tabela2, int tam, int tam_antigo)

  • 1

    Your code’s a little long for a Stackoverflow question. Do you think you can reduce to something small enough to include in the post itself, without links to external websites? It is best to avoid an external link because it might stop working in the future and fewer people have time to find a bug in 300 lines.

  • 1

    I didn’t look at the relocation part in detail but there are some other things that are confusing in its code: 1) its data structure for the dictionary is very strange. The normal would be to store only the key and the number of occurrences in each bucket. I don’t know what lines and lines are doing there. 2) I would like to use char * instead of char [] in the hash table bucket; this allows for larger words and makes your life easier when inserting and transferring table items. 3) The idiomatic is to use 1 instead of’S' and 0 for 'N'. If you can use C99 tb you have true and false, which is even better.

  • 1

    Finally, the relocation function is very long and has a lot of code copied from its "main". If you had extracted the insertion logic into a reusable subroutine you could write the relocation in about 3 or 4 lines, simply taking everyone from Table 1 and reinserting in Table 2. How to choose the parameters and return values of the shared insertion function for everything to work out is an exercise :)

  • 1

    Another more subjective suggestion is that I think it becomes clearer to use return or break to interrupt the loops instead of filling the code with "flags" as "op_effected". Not everyone agrees with this but I think that the fewer variables interfering with the program flow the better.

  • @hugomg Thanks for the suggestions!

  • @hugomg, thinking about what you told me, I redid everything, isolating my problem. I created a new question, see if you can understand now: http://answall.com/questions/38551/erro-copiar-vector-type abstract

  • You needed to create a new question. you could have edited the old one.

Show 2 more comments
No answers

Browser other questions tagged

You are not signed in. Login or sign up in order to post.