0

Preciso pegar as palavras de um arquivo .txt e armazenar a palavra e a quantidade de vezes que ela aparece no arquivo em um vetor de structs. Cada palavra terá a sua posição do vetor.

O struct:

typedef struct
{
    char palavra[50];
    int ocorrencia;
} dicionario;

Depois de armazenar tudo no vetor, uma das funções que o programa deve executar é ordenar essas palavras em sentido crescente de ocorrência, por isso quero fazer o quickSort.

Minha tentativa de quickSort:

void quickSort(dicionario tabela[], int inicio, int tamanho)
{

    int i = inicio, j = tamanho;
    int temp;
    int pivot = tabela[(i + j) / 2].ocorrencia;

    while(i<=j)
    {
        while(tabela[i].ocorrencia < pivot) i++;
        while(tabela[j].ocorrencia > pivot) j--;
        if(i<=j)
        {
            temp = tabela[i].ocorrencia;
            tabela[i].ocorrencia = tabela[j].ocorrencia;
            tabela[j].ocorrencia = temp;
            i++;
            j++;
        }
    }

    if(inicio < j) quickSort(tabela,inicio,j);
    if(i < tamanho) quickSort(tabela,i,tamanho);

}

Quando executo essa parte, o programa simplesmente finaliza sem retornar nada (mesmo colocando printf embaixo nada acontece). Tentei pesquisar na internet mas tudo que acho com relação a isso está em C++.

3
  • 1
    Observação do autor da pergunta: ...não estou acostumado a mandar perguntas aqui, se precisarem de mais informações, só pedir... Commented 27/02/2022 às 21:28
  • Acho que seria melhor utilzar uma árvore binária balanceada.
    – teste-90
    Commented 28/02/2022 às 1:16
  • poste um programa inteiro, compilável
    – arfneto
    Commented 28/02/2022 às 20:58

1 Resposta 1

0

Você vai ter uma lista de palavras assim

int 23
main 1
teste 12
outro 22

E espera classificar pela segunda coluna e acabar com algo assim

main 1
teste 12
outro 22
int 23

quickSort() não entende vetores de struct ou de qualquer outra coisa: apenas considera um vetor de ponteiros e uma função de comparação. Veja o quick sort disponível em stdlib:

void qsort(void *base, size_t nitems, size_t size, int (*compar)(const void *, const void*))

E isso é muito prático porque classifica qualquer coisa sem saber o que é. Basta escrever uma função de comparação.

Sua estrutura

typedef struct
{
    char palavra[50];
    int ocorrencia;
} dicionario;

para usar

void quickSort(dicionario tabela[], int inicio, int tamanho)

Não está muito boa nem flexível. Compare com algo assim

typedef struct
{
    char* pal; // a palavra
    int   N; // quantas vezes aparece

}   Entrada;

Essa é uma entrada do seu tipo de dados.

E o dicionário?

typedef struct
{
    unsigned N; //quantos itens
    Entrada* item; // vetor de itens

}   Dict;

Exemplo em C usando qsort() e esses dados

Um programa que usa esses dados do exemplo e classifica

criando o dicionário

Dict* cria()
{
    Entrada const coisas[4] = {
        [0].pal = "teste", [0].N = 12,
        [1].pal = "int",   [1].N = 23,
        [2].pal = "outro", [2].N = 22,
        [3].pal = "main",  [3].N = 1};

    Dict* teste = (Dict*)malloc(sizeof(Dict));
    teste->N    = 4;
    teste->item =
        (Entrada*)malloc(teste->N * sizeof(Entrada));
    for (unsigned i = 0; i < teste->N; i += 1)
        teste->item[i] = coisas[i];
    return teste;
}

Essa função cria uma estrutura de testes como a que seu programa deve criar a partir do arquivo de entrada e retorna o endereço

A função de comparação

É uma função que compara duas entradas e retorna 1 se elas estão fora de ordem. Isso é o que falta em seu QuickSort

int compara(const void* v1, const void* v2)
{  // compara duas entradas do dicionario
    Entrada const* pal1 = v1;
    Entrada const* pal2 = v2;
    if (pal1->N < pal2->N) return -1;
    if (pal1->N > pal2->N) return +1;
    return 0;
}

main() para o teste

Este programa cria a tabela, mostra, classifica, mostra o resultado e apaga. Compare...

int main(void)
{
    Dict* teste = cria();
    mostra(teste, "tabela original\n\n");
    qsort(
        &(teste->item[0]), teste->N, sizeof(Entrada),
        compara);
    mostra(teste, "tabela classificada\n\n");
    // teste = apaga(teste);
    return 0;
}

saída do exemplo

tabela original


#N      Palavra
----    --------
12      teste
23      int
22      outro
1       main

tabela classificada


#N      Palavra
----    --------
1       main
12      teste
22      outro
23      int

O código completo

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

typedef struct
{
    char*    pal;  // a palavra
    unsigned N;    // quantas vezes aparece

} Entrada;

typedef struct
{
    unsigned N;     // quantos itens
    Entrada* item;  // vetor de itens

} Dict;

int   compara(const void* v1, const void* v2);
Dict* apaga(Dict*);
Dict* cria();
void  mostra(Dict*, const char*);

int main(void)
{
    Dict* teste = cria();
    mostra(teste, "tabela original\n\n");
    qsort(
        &(teste->item[0]), teste->N, sizeof(Entrada),
        compara);
    mostra(teste, "tabela classificada\n\n");
    // teste = apaga(teste);
    return 0;
}

int compara(const void* v1, const void* v2)
{  // compara duas entradas do dicionario
    Entrada const* pal1 = v1;
    Entrada const* pal2 = v2;
    if (pal1->N < pal2->N) return -1;
    if (pal1->N > pal2->N) return +1;
    return 0;
}

Dict* apaga(Dict* D)
{
    free(D->item);
    free(D);
    return NULL;
}

Dict* cria()
{
    Entrada const coisas[4] = {
        [0].pal = "teste", [0].N = 12,
        [1].pal = "int",   [1].N = 23,
        [2].pal = "outro", [2].N = 22,
        [3].pal = "main",  [3].N = 1};

    Dict* teste = (Dict*)malloc(sizeof(Dict));
    teste->N    = 4;
    teste->item =
        (Entrada*)malloc(teste->N * sizeof(Entrada));
    for (unsigned i = 0; i < teste->N; i += 1)
        teste->item[i] = coisas[i];
    return teste;
}

void mostra(Dict* dic, const char* tit)
{
    if (tit != NULL) printf("%s", tit);
    if (dic->N > 0)
        printf("\n#N\tPalavra\n----    --------\n");
    else
        printf("\nSem entradas\n");
    for (unsigned i = 0; i < dic->N; i += 1)
        printf(
            "%d\t%s\n", dic->item[i].N, dic->item[i].pal);
    printf("\n");
}
3
  • Obrigado! Acabei utilizando a função qsort mesmo. Pesquisando em alguns sites consegui criar uma função de comparação, não sei se é eficiente, mas obtive o resultado esperado. Mais uma vez obrigado pela ajuda Commented 1/03/2022 às 14:02
  • porque não usou simplesmente a que te mostrei? podia pesquisar nesse site nesse post apenas :) e teria uma função
    – arfneto
    Commented 1/03/2022 às 15:47
  • 1
    É porque eu tinha um prazo para entregar esse projeto. Só recebi a sua resposta depois que o prazo tinha se esgotado. Por isso não utilizei exatamente o que o senhor publicou. Mas mesmo assim eu agradeço a ajuda. Commented 2/03/2022 às 16:11

Você deve fazer log-in para responder a esta pergunta.

Esta não é a resposta que você está procurando? Pesquise outras perguntas com a tag .