5

Estou implementando a função decodificar, que tem como objetivo chamar funções auxiliares para inverter todas as sequências de não-vogais. Por exemplo, se a palavra for "monstros legais", seguirá para "mortsnol segais".

void inverterNvs(NO* elemento, NO* anteriorAoElemento) {
    if (elemento->prox != NULL) {
        inverterNvs(elemento->prox, elemento);
    }
    elemento->prox = anteriorAoElemento;
}


bool verificaSequencia(NO* dado) {
    if (dado->letra != 'a' || dado->letra != 'e' || dado->letra != 'i' || dado->letra != 'o' || dado->letra != 'u'){
        return true;
    }
    else{
        return false;
    }
}

void decodificar(LISTA* resp) {
    NO* pNv = NULL; // Primeira não-vogal encontrada.
    NO* ultNv = NULL; // Última não-vogal encontrada.

    NO* atual = resp->inicio; // Ponteiro para percorrer a lista.

    /* Laço para percorrer toda lista. */
    while (atual->prox != NULL) {

        /* Enquanto atual apontar para uma não-vogal. */
        if (verificaSequencia(atual)) {
            /* Salva o primeiro caso encontrado de não-vogal. */
            pNv = atual;

            /* Procura na lista o último caso de não-vogal. */
            while (verificaSequencia(atual->prox)) {
                atual = atual->prox;
            }
            /* Quando a próxima letra for uma vogal, então foi atingido o fim da sequência de não-vogais. */
            ultNv = atual;

            /* Se existir uma sequência de não-vogais, ou seja, pNv e ultNv não apontarem para o mesmo elemento, então a troca de posições deve ser efetuada. */
            if (pNv != ultNv) {
                /* Chama uma função recursiva para efetuar a troca de posições sem precisar criar uma nova lista. */
                inverterNvs(pNv->prox, pNv);
            }
        }

        /* Move para o próximo elemento. */
        atual = atual->prox;
    }
}

Gostaria de saber se meu código resolve o problema e como completá-lo para que ele funcione, pois as inversões não estão sendo feitas. Meu program está terminando com status 0, de acordo com o CodeBlocks, mesmo após chamar a função decodificar. Código completo: https://repl.it/KrQg/3

0

3 Respostas 3

3

Você pode separar esse problema em dois pequenos problemas:

  1. Encontrar a "sub lista" que contém a sequência de não vogais (consoantes)
  2. Inverter uma lista simplesmente encadeada.

O primeiro problema de certa forma é mais fácil de resolver, você pode abordar de diversas maneiras possíveis. No código abaixo, eu utilizei de uma Função Recursiva chamada InverteElementos.

Todavia, é possível (e na minha opinião mais fácil de entender) criar uma nova lista temporária que servirá para auxiliar a inverter as posições da sequencia de não vogais. Não tomei esse caminho por não saber como foram implementadas as funções de criar a sua estrutura LISTA, e também porque não sei se seu problema permite a utilização de memória auxiliar.

A função inverterNvs, percorre a lista simplesmente encadeada, membro por membro, e ao encontrar uma sequência de consoantes, efetua a troca das posições dos membros da sequência usando uma função recursiva.

Vale ressaltar que a função ehNaoVogal serve apenas para deixar o código mais legível.

void inverterNvs(LISTA* resp) {
    NO* pNv = NULL; // Primeira não-vogal encontrada.
    NO* ultNv = NULL; // Última não-vogal encontrada.

    NO* atual = resp->inicio; // Ponteiro para percorrer a lista.

    /* Laço para percorrer toda lista. */
    while (atual->prox != NULL) {

        /* Enquanto atual apontar para uma não-vogal. */
        if (ehNaoVogal(atual)) {
            /* Salva o primeiro caso encontrado de não-vogal. */
            pNv = atual;

            /* Procura na lista o último caso de não-vogal. */
            while (ehNaoVogal(atual->prox)) {
                atual = atual->prox;
            }
            /* Quando a próxima letra for uma vogal, então foi atingido o fim da sequência de não-vogais. */
            ultNv = atual;

            /* Se existir uma sequência de não-vogais, ou seja, pNv e ultNv não apontarem para o mesmo elemento, então a troca de posições deve ser efetuada. */
            if (pNv != ultNv) {
                /* Chama uma função recursiva para efetuar a troca de posições sem precisar criar uma nova lista. */
                inverteElementos(pNv->prox, pNv);
            }
        }

        /* Move para o próximo elemento. */
        atual = atual->prox;
    }
}

void inverteElementos(NO* elemento, NO* anteriorAoElemento) {
    if (elemento->prox != NULL) {
        inverteElementos(elemento->prox, elemento);
    }
    elemento->prox = anteriorAoElemento;
}

bool ehNaoVogal(NO* dado) {
    if (dado->letra != 'a' || dado->letra != 'e' || dado->letra != 'i' || dado->letra != 'o' || dado->letra != 'u'){
        return true;
    }
    else{
        return false;
    }
}
1
  • Muito obrigado pela ajuda, Marcos. Contudo, não foi possível fazer a inversão das não-vogais. Segue código para maiores detalhes: repl.it/Kdko/21 Commented 5/09/2017 às 12:39
2
+50

A logica que está a utilizar faz sentido, e responde ao problema, mas existem vários pormenores da implementação que não estão corretos.

Começando pela inversão dos nós:

void inverterNvs(NO* elemento, NO* anteriorAoElemento) {
    if (elemento->prox != NULL) {
        inverterNvs(elemento->prox, elemento);
    }
    elemento->prox = anteriorAoElemento;
}

Neste caso a navegação está a ser feita até ao NULL para inverter apenas um trecho da frase, o que não responde ao que o método pretende fazer, que é para na consoante final. Ou seja se queremos inverter "nstr" de "n" até "r" então temos de indicar o "r" de alguma maneira caso contrário vai até ao fim da frase.

Logo pode-se alterar incluindo um ponteiro de fim:

void inverterNvs(NO* elemento, NO* anteriorAoElemento, NO* fim /*novo fim aqui*/) { 
    if (elemento != fim) { //teste agora com o fim em vez de NULL
        inverterNvs(elemento->prox, elemento, fim);
    }
    elemento->prox = anteriorAoElemento;
}

A função verificaSequencia:

bool verificaSequencia(NO* dado) {
    if (dado->letra != 'a' || dado->letra != 'e' || dado->letra != 'i' || dado->letra != 'o' || dado->letra != 'u'){
        return true;
    }
    else{
        return false;
    }
}

Também não está correta no if pois valida com ou(||) quando devia validar com e(&&). Se tivermos um 'e' o primeiro teste de dado->letra != 'a'true e como é com ou(||) já nem testa o resto e dá true como resultado quando deveria dar false.

Basta alterar o if para que fique:

if (dado->letra != 'a' && dado->letra != 'e' && dado->letra != 'i' && dado->letra != 'o' && dado->letra != 'u'){

A função decodificar é a que necessita de mais alterações para que responda totalmente á logica.

É necessário:

  • Ajustar as condições dos 2 while
  • Voltar a ligar o bloco invertido com o resto da lista
  • Atualizar o atual após a inversão

Considerando tudo isso, fica agora assim (cortei os seus comentários para focar apenas nas alterações que eu fiz):

void decodificar(LISTA* resp) {
    NO* pNv = NULL;
    NO* ultNv = NULL;

    NO* atual = resp->inicio;

    //ponteiro necessário para voltar a ligar o bloco invertido com o resto
    NO* anterior = NULL; 

    //este while foi alterado de atual->prox!=NULL para atual!=NULL uma vez que o while
    //de dentro mexe também no atual e o atual=atual->prox do fim pode meter o atual 
    //a NULL fazendo com que atual->prox!=NULL pudesse dar erro aqui
    while (atual != NULL) {

        if (verificaSequencia(atual)) {
            pNv = atual;

            //se o while utiliza atual, é necessário não deixar passar o NULL senão
            //dá erro, e por isso adicionei aqui atual->prox != NULL &&
            while (atual->prox != NULL && verificaSequencia(atual->prox)) {
                atual = atual->prox;
            }

            ultNv = atual;

            if (pNv != ultNv) {

                //guardar o nó seguinte à inversão para depois voltar a ligar o bloco invertido
                NO* proximoOriginal = ultNv->prox;

                //chamada agora inclui também o ultNv como ponteiro de fim
                inverterNvs(pNv->prox, pNv, ultNv);

                //o pNv que era o primeiro é agora o ultimo, e por isso o seu prox
                //tem de apontar para o antigo próximo
                pNv->prox = proximoOriginal;

                //o ultNv que era o ultimo é agora o primeiro, e por isso o antes 
                //deste (o anterior) tem de agora apontar para ultNv. É necessário 
                //considerar o caso em que o anterior é nulo, que é quando inverte 
                //logo da primeira letra
                if (anterior == NULL){
                    resp->inicio = ultNv;
                }
                else {
                    anterior->prox = ultNv;
                }

                //o atual fica no ultimo após inversão
                atual = pNv;
            }
        }

        anterior = atual; //atualiza o anterior
        atual = atual->prox;
    }
}

Repare que tive que acrescentar tanto o ponteiro anterior com o ponteiro proximoOriginal para conseguir ligar o bloco invertido com a lista que já existia. Porque no quando é feita a inversão de o"nstr" para o"rtsn" o o continuava a apontar para o n quando deveria agora apontar para o r, que é o que faz a instrução:

anterior->prox = ultNv;

De igual forma o n que é agora o novo fim tem que apontar para a letra que vem a seguir a este bloco, que é o que é feito nesta instrução:

pNv->prox = proximoOriginal;

Veja a funcionar no Ideone a funcionar

8
  • Sua resposta é exatamente o que eu precisava. Muito obrigado! Commented 8/09/2017 às 18:35
  • @CaioIgnm De nada, boa sorte para o resto do trabalho
    – Isac
    Commented 8/09/2017 às 18:46
  • acabei de notar dois erros: a última letra está sendo ignorada(em "vai chover" a letra "r" não é tratada); entradas contendo frases com mais de duas palavras acabam com "non-zero status", por exemplo, "vai chover amanha". Commented 8/09/2017 às 18:57
  • @CaioIgnm o "vai chover""vaihc over" que de acordo com a logica era o esperado. Qual era o resultado que "vai chover" deveria dar? E vejo o mesmo para "vai chover amanha" que devolve "vaich ove ramahna" que na minha otica era o esperado
    – Isac
    Commented 8/09/2017 às 20:21
  • @CaioIgnm O pormenor do ponto não foi indicado na pergunta, e por isso "vai chover." vai resultar em "vaihc ove.r", que suspeito que não era o que queria ? É suposto programa ignorar caracteres de acentuação como '?', '!','.',etc.. ?
    – Isac
    Commented 9/09/2017 às 13:02
1

Isto não é uma resposta directa à pergunta colocada, mas apenas uma solução do problema posto.

Segue um filtro que usando expressões regulares procura apenas as zonas críticas e escreve-as invertido. No caso vou usar flex, que gera C:

%%
[^aeiou\n]{2,}  {for( int i=yyleng-1; i>=0; i--) putchar(yytext[i]) ;}
%%

Modo de usar:

$ flex -o filtro.c filtro.fl
$ cc filtro.c -o filtro -lfl
$ echo "monstros legais"| filtro
mortsnol segais

Por último esta substituição é trivial em linguagens que tenham suporte bom para processamento de expressões regulares. Exemplo:

$ echo "monstros legais"| perl -pe 's/([^aeiou]{2,})/reverse($1)/ge'
mortsnol segais
2
  • 1
    Obrigado, JJoao. Como se trata de um trabalho acadêmico devo utilizar somente ponteiros e listas simplesmente encadeadas Commented 5/09/2017 às 15:43
  • @ CaioIgnm, OK.
    – JJoao
    Commented 5/09/2017 às 15:45

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 .