fork download
copy 
  1. #include <stdio.h>
  2. #include <stdlib.h>
  3. #include <string.h>
  4. #include <math.h>
  5.  
  6. typedef struct dicionario
  7. {
  8.     char chave[21];
  9.  
  10.     int* linhas;
  11.  
  12.     int tam_linhas;
  13.  
  14. }Dicionario;
  15.  
  16. void inicializa(Dicionario* tabela, int tam)
  17. {
  18.     int i;
  19.  
  20.     for(i=0; i < tam; i++)
  21.         tabela[i].tam_linhas = 0;
  22. }
  23.  
  24. int code(char str[])//gera um codigo p a chave
  25. {
  26.     int tam_str = strlen(str),aux=0, i, j;
  27.  
  28.     for(i=0,j=tam_str-1; i < tam_str; i++,j--)
  29.         aux = aux + (str[i]-'a')*(pow(26,j));
  30.  
  31.     return aux;
  32. }
  33.  
  34. int hash(int chave, int tam, int i)
  35. {
  36.     return (chave%tam + i);
  37. }
  38.  
  39. int naoTemRepeticaoDaLinha(int linha, int v[], int tam)
  40. {
  41.     int i;//índice de reaplicação do Hash
  42.  
  43.     char existe = 'N';
  44.  
  45.     for(i = 0; i < tam; i++)
  46.         if(v[i] == linha)
  47.             existe = 'S';
  48.  
  49.     return (existe == 'N');
  50. }
  51.  
  52. void insereTabela(char* aux, Dicionario* tabela, int tam, int num_linha, int* num_chaves)
  53. {
  54.     int pos, i=0;
  55.  
  56.     char op_efetuada = 'N';
  57.  
  58.     pos = hash(code(aux), tam, i);
  59.  
  60.     //printf("%d\n", pos);
  61.  
  62.     while(op_efetuada == 'N')
  63.     {
  64.  
  65.         if(tabela[pos].tam_linhas == 0)//se nao houve conflito
  66.         {
  67.             strcpy(tabela[pos].chave, aux);//atualiza a chave
  68.  
  69.             tabela[pos].tam_linhas++;//atualiza o tamanho
  70.  
  71.             tabela[pos].linhas = (int*) malloc(sizeof(int));//cria o vetor de linhas
  72.  
  73.             if(tabela[pos].linhas == NULL)
  74.             {
  75.                 printf("\nmemoria insuficiente");
  76.  
  77.                 exit(1);
  78.             }
  79.  
  80.             tabela[pos].linhas[tabela[pos].tam_linhas - 1] = num_linha;//add a linha atual
  81.  
  82.             op_efetuada = 'S';
  83.  
  84.             *num_chaves = *num_chaves + 1;
  85.  
  86.         }
  87.         else//houve conflito
  88.         {
  89.  
  90.             if(strcmp(aux, tabela[pos].chave) == 0)//se a chave coincidir
  91.             {
  92.                 if(naoTemRepeticaoDaLinha(num_linha, tabela[pos].linhas, tabela[pos].tam_linhas))//se não houver repeticao de linha
  93.                 {
  94.                     tabela[pos].tam_linhas++;
  95.  
  96.                     tabela[pos].linhas = (int*) realloc(tabela[pos].linhas, (tabela[pos].tam_linhas)*sizeof(int) );
  97.  
  98.                     if(tabela[pos].linhas == NULL)
  99.                     {
  100.                         printf("\nmemoria insuficiente");
  101.  
  102.                         exit(1);
  103.                     }
  104.  
  105.                     tabela[pos].linhas[tabela[pos].tam_linhas - 1] = num_linha;
  106.  
  107.                     op_efetuada = 'S';
  108.                 }
  109.             }
  110.             else//procura outra posicao
  111.             {
  112.                 i++;
  113.  
  114.                 pos = hash(code(aux), tam, i);
  115.             }
  116.  
  117.         }
  118.     }
  119. }
  120.  
  121. void reallocaTabela(Dicionario* tabela, Dicionario* tabela2, int tam, int tam_temp)
  122. {
  123.     int i,
  124.         j,
  125.         k,
  126.         pos;
  127.  
  128.     char op_efetuada;
  129.  
  130.     for(i=0; i < tam_temp; i++)
  131.     {
  132.         op_efetuada == 'N';
  133.  
  134.         if(tabela[i].tam_linhas != 0)
  135.         {
  136.             j=0;
  137.  
  138.             pos = hash(code(tabela[i].chave), tam, j);
  139.  
  140.             while(op_efetuada == 'N')
  141.             {
  142.                 if(tabela2[pos].tam_linhas == 0)//se nao houve conflito
  143.                 {
  144.                     strcpy(tabela2[pos].chave, tabela[i].chave);//atualiza a chave
  145.  
  146.                     tabela2[pos].tam_linhas = tabela[i].tam_linhas;//atualiza o tamanho
  147.  
  148.                     tabela2[pos].linhas = (int*) malloc(tabela2[pos].tam_linhas*sizeof(int));//cria o vetor de linhas
  149.  
  150.                     if(tabela2[pos].linhas == NULL)
  151.                     {
  152.                         printf("\nmemoria insuficiente");
  153.  
  154.                         exit(1);
  155.                     }
  156.  
  157.                     for(k=0; k < tabela2[pos].tam_linhas; k++)
  158.                         tabela2[pos].linhas[k] = tabela[i].linhas[k];
  159.  
  160.                     op_efetuada = 'S';
  161.  
  162.                 }
  163.                 else//procura outra posicao
  164.                 {
  165.                     j++;
  166.  
  167.                     pos = hash(code(tabela[i].chave), tam, j);
  168.                 }
  169.             }
  170.         }
  171.     }
  172. }
  173.  
  174.  
  175. ///MAIN
  176.  
  177.  
  178. int main()
  179. {
  180.     int tam=11,
  181.         num_chaves=0,
  182.         i,//coeficiente anti-colisão
  183.         num_linha = 1,
  184.         tam_temp,
  185.         k,
  186.         pos;
  187.  
  188.     float load_factor=0;//razão entre o número de chaves distintas na tabela e a capacidade máxima da tabela
  189.  
  190.     char str[101], op_efetuada;
  191.  
  192.     Dicionario* tabela = (Dicionario*) malloc(tam*sizeof(Dicionario));
  193.  
  194.     Dicionario* tabela2;
  195.  
  196.     if(tabela == NULL)
  197.     {
  198.         printf("\nmemoria insuficiente");
  199.  
  200.         exit(1);
  201.     }
  202.  
  203.     inicializa(tabela, tam);//inicializa tabela com tam_linhas = 0;
  204.  
  205.     freopen("L3Q1.in","r",stdin);
  206.     freopen("L3Q1.out","w",stdout);
  207.  
  208.     gets(str);//lê $TEXTO
  209.  
  210.     //enquanto tiver linhas do texto para ler
  211.     while (scanf(" %100[^\n]", str) && strcmp(str, "$CONSULTAS") != 0)
  212.     {
  213.         load_factor = (float) num_chaves/tam;
  214.  
  215.         if(load_factor > 0.5 && num_chaves < 6000)//se load_factor for maior que 1/2
  216.         {
  217.             tam_temp = tam;
  218.  
  219.             tam = tam*2 + 1;//duplique o tam
  220.  
  221.             tabela2 = (Dicionario*) malloc(tam*sizeof(Dicionario));
  222.  
  223.             if(tabela2 == NULL)
  224.             {
  225.                 printf("\nmemoria insuficiente");
  226.  
  227.                 exit(1);
  228.             }
  229.  
  230.             inicializa(tabela2, tam);
  231.  
  232.             reallocaTabela(tabela, tabela2, tam, tam_temp);
  233.  
  234.             free(tabela);
  235.  
  236.             tabela = tabela2;
  237.         }
  238.  
  239.         char* aux = strtok(str, " ");//strtok vai separar a string nas palavras
  240.  
  241.  
  242.         while (aux != NULL)
  243.         {
  244.             //printf("%s\n", aux);
  245.             insereTabela(aux, tabela, tam, num_linha, &num_chaves);
  246.  
  247.             aux = strtok(NULL, " ");
  248.         }
  249.  
  250.         num_linha++;
  251.     }
  252.  
  253.     //como no loop acima ja lemos o $CONSULTAS, so precisamos ler as consultas
  254.     while (scanf(" %20[^\n]", str) == 1)//enquanto tiver consulta para ler
  255.     {
  256.         i=0;
  257.  
  258.         k=num_chaves;
  259.  
  260.         op_efetuada == 'N';
  261.  
  262.         pos = hash(code(str), tam, i);
  263.  
  264.         while(op_efetuada == 'N')
  265.         {
  266.             if(strcmp(tabela[pos].chave,str) == 0)
  267.             {
  268.                 printf("%s: ",str);
  269.  
  270.                 //tam_temp faz papel de contador
  271.                 for(tam_temp = 0; tam_temp < tabela[pos].tam_linhas; tam_temp++)
  272.                     printf("%d ", tabela[pos].linhas[tam_temp]);
  273.  
  274.                 printf("\n");
  275.  
  276.                 op_efetuada == 'S';
  277.             }
  278.             else
  279.             {
  280.                 if(k>0)
  281.                 {
  282.                     i++;
  283.  
  284.                     pos = hash(code(str), tam, i);
  285.  
  286.                     k--;
  287.                 }
  288.                 else
  289.                 {
  290.                     op_efetuada == 'S';
  291.  
  292.                     printf("%s: \n",str);
  293.                 }
  294.             }
  295.         }
  296.  
  297.     }
  298.  
  299.   return 0;
  300. }
  301.  
Runtime error #stdin #stdout 0s 2376KB
comments ()
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/rbhYhZ
language:
C (gcc 8.3)
created:
10 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!