Ir ao conteúdo
  • Cadastre-se

C eliminar elementos que se repitem em um array


debora jesus

Posts recomendados

 

Ola, eu fiz um menu, e uma das opções é eliminar um elemento do array. O problema é que o meu so elimina uma vez e se ha vezes repetidas estraga todo o array. alguém pode me ajudar?

 

Faço a carga antes, ne é numero de elementos do array.

//eliminar

    printf("\nQue numero desea eliminar?  ");
            scanf("%d",&eliminar);    
            for(i=ne-1;i>=0;i--)
            {
                if(v[i]==eliminar)
                {
                    for(j=i;j<ne;j++)
                    {
                        v[j]=v[j-1];
                    }
                    ne--;
                }
                
            }

//visualizar

for(i=0;i<ne;i++)
                {
                    printf("[%d] = %d  ",i,v[i]);
                }

 

 

  • Curtir 1
Link para o comentário
Compartilhar em outros sites

Cheguei nesse resultado. Não está bom, mas funciona:

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


int contarOcorrencias(int *array, int tamanho, int valor);

void eliminar(int *array, int *tamanho, int valor);

void imprimir(int *array, int tamanho);


int main() {
    int array[] = {0, 1, 2, 3, 3, 3, 4, 5};
    int tamanho = 8;
    int valor = 3;

    eliminar(array, &tamanho, valor);
    imprimir(array, tamanho);

    printf("Tamanho: %d \n", tamanho);

    return EXIT_SUCCESS;
}


int contarOcorrencias(int *array, int tamanho, int valor){
    int ocorrencias = 0;

    for (int i = 0; i < tamanho; i++) {
        if (array[i] == valor) ++ocorrencias;
    }

    return ocorrencias;
}

void eliminar(int *array, int *tamanho, int valor){
    int ocorrencias = contarOcorrencias(array, *tamanho, valor);
    int novoTamanho = *tamanho - ocorrencias;

    int resultado[novoTamanho];
    int indiceResultado = 0;

    for (int i = 0; i < *tamanho; i++) {
        if (array[i] != valor) {
            resultado[indiceResultado] = array[i];
            ++indiceResultado;
        }
    }

    *tamanho = novoTamanho;

    for(int i = 0; i < novoTamanho; ++i) {
        array[i] = resultado[i];
    }
}

void imprimir(int *array, int tamanho) {
    printf("[");

    for(int i = 0; i < tamanho; ++i) {
        printf("%d", array[i]);

        if(i + 1 < tamanho) printf(", ");
    }

    printf("] \n");
}

 

  • Curtir 2
Link para o comentário
Compartilhar em outros sites

2 horas atrás, AdrianoSiqueira disse:
void eliminar(int *array, int *tamanho, int valor);

 

Não precisa de verdade passar dois ponteiros para retornar o valor alterado. Bastaria retornar o total restante de elementos, @AdrianoSiqueira. E não precisa chamar outra função pra contar as ocorrências. Pode por exemplo apenas ir colocando as duplicatas ao final em um loop só.

 

Em português a noção comum de eliminar algo é eliminar algo de algum lugar então talvez fosse mais natural:

  • inverter  ordem dos parâmetros
  • retornar o novo total de elementos, aproveitando o loop único para colocar os duplicados ao final antes de naturalmente diminuir o tamanho

EXEMPLO

 

Eis a saída do programa exemplo (o código está ao final).

 

Vetor (5 elementos): { 1,2,2,2,1 }
Apagado 2
Vetor (2 elementos): { 1,1 }
Vetor (8 elementos): { 4,4,4,4,4,4,4,4 }
Apagado 4
Vetor VAZIO
Vetor (8 elementos): { 4,2,2,2,2,2,2,4 }
Apagado 4
Vetor (6 elementos): { 2,2,2,2,2,2 }

 

Usando algo assim

 

    int elimina(int elemento, int vetor[], int tamanho);

 

Retornando o tamanho do vetor depois de eliminado o elemento...

 

Uma implementação possível
 

int elimina(int elemento, int vetor[], int ne)
{
    int saldo = ne; // pode não ter nenhum
    int tem   = 1; // assume que tem algum a eliminar
    int inicio = 0;
    do {    
        tem = 0; // não tem
        for (int i = inicio; i < saldo; i += 1)
            if (vetor[i] == elemento)
            {  
                vetor[i] = vetor[saldo - 1]; // o ultimo
                saldo -= 1;
                if (saldo == 0) return saldo; // não sobrou nada
                inicio = i; // pode ter outros
                tem = 1; // entao tem
                break; // continua a busca
            };  // if()
    } while (tem);
    return saldo;
};

 

O código do teste

 

#include <stdio.h>

int elimina(int elemento, int vetor[], int tamanho);
int mostra(int vetor[], int tamanho);

int main(void)
{ 
    int v1[] = {1,2,2,2,1};
    int v2[] = {4, 4, 4, 4, 4, 4, 4, 4};
    int v3[] = {4, 2,2,2,2,2,2, 4};

    int ne = sizeof(v1) / sizeof(v1[0]);
    mostra(v1, ne);
    int el = 2;
    ne = elimina(el, v1, ne);
    printf("Apagado %d\n", el);
    mostra(v1, ne);

    ne = sizeof(v2) / sizeof(v2[0]);
    mostra(v2, ne);
    el = 4;
    ne = elimina(el, v2, ne);
    printf("Apagado %d\n", el);
    mostra(v2, ne);

    ne = sizeof(v3) / sizeof(v3[0]);
    mostra(v3, ne);
    el = 4;
    ne = elimina(4, v3, ne);
    printf("Apagado %d\n", el);
    mostra(v3, ne);

    return 0;
}

int elimina(int elemento, int vetor[], int ne)
{
    int saldo = ne; // pode não ter nenhum
    int tem   = 1; // assume que tem algum a eliminar
    int inicio = 0;
    do {    
        tem = 0; // não tem
        for (int i = inicio; i < saldo; i += 1)
            if (vetor[i] == elemento)
            {  
                vetor[i] = vetor[saldo - 1]; // o ultimo
                saldo -= 1;
                if (saldo == 0) return saldo; // não sobrou nada
                inicio = i; // pode ter outros
                tem = 1; // entao tem
                break; // continua a busca
            };  // if()
    } while (tem);
    return saldo;
};

int mostra(int vetor[], int tamanho)
{
    if (tamanho < 1)
    {   printf("Vetor VAZIO\n");
        return -1;
    }
    printf("Vetor (%d elementos): { ", tamanho);
    for (int i = 0; i < tamanho - 1; i += 1) printf("%d,", vetor[i]);
    printf("%d }\n", vetor[tamanho - 1]);
    return 0;
};

 

  • Curtir 1
Link para o comentário
Compartilhar em outros sites

5 horas atrás, arfneto disse:

Não precisa de verdade passar dois ponteiros para retornar o valor alterado. Bastaria retornar o total restante de elementos, @AdrianoSiqueira. E não precisa chamar outra função pra contar as ocorrências. Pode por exemplo apenas ir colocando as duplicatas ao final em um loop só.

 

Imaginei que o código não estaria bom, faz tempo que não programo nada em C 😅.

  • Curtir 2
Link para o comentário
Compartilhar em outros sites

@AdrianoSiqueira O exemplo que mostrei serviria em qualquer linguagem. Provavelmente faz o mínimo de comparações e varre o vetor uma única vez. E não precisa contar ocorrências nem alocar memória nem copiar o vetor.

 

Mudando uma linha vai ficar mais claro ainda:

 

int elimina(int elemento, int vetor[], int ne)
{
    int saldo = ne; // pode não ter nenhum
    int tem   = 1; // assume que tem algum a eliminar
    int inicio = 0;
    do {    
        tem = 0; // não tem
        for (int i = inicio; i < saldo; i += 1)
            if (vetor[i] == elemento)
            {  
                vetor[i] = vetor[saldo - 1]; // o ultimo
                saldo -= 1;
                if (saldo == 0) return saldo; // não sobrou nada
                inicio = i; // pode ter outros
                tem = 1; // entao tem
                break; // continua a busca
            };  // if()
    } while (tem);
    return saldo;
};

 

Depois de copiar o último valor para a primeira ocorrência do elemento se você incluir
 

                vetor[saldo - 1] = elemento; // "swap" 

 

Vai ver que esse algoritmo é o que se chama de partition na literatura:

  • separa um vetor a partir de uma função --- chamada predicate nos livros --- e que aqui é o fato do elemento ter valor diferente do valor a ser eliminado
    • os elementos de valor diferente ficam na frente
    • os elementos que não atendem ao predicado ficam depois
    • trocando a comparação por uma chamada a função pode usar isso para qualquer coisa
    • pode passar o ponteiro da função no algoritmo

 

Mudando o programa de teste para incluir essa linha e mostrando o vetor inteiro ao final, veja a saída:
 

Vetor (11 elementos): { 1,1,2,1,3,1,4,1,5,1,1 }
Apagado 1
Vetor (4 elementos): { 5,4,2,3 }

Vetor como ficou ao final:

Vetor (11 elementos): { 5,4,2,3,1,1,1,1,1,1,1 }

 

Se a ordem dos elementos fosse mantida seria o algoritmo chamado de stable partition. Entenda que todos os registros que satisfazem um predicado ficam separados, criando o esperado: uma partição.

 

EXEMPLO revisto
 

#include <stdio.h>

int elimina(int elemento, int vetor[], int tamanho);
int mostra(int vetor[], int tamanho);

int main(void)
{ 
    int v1[] = {1,1,2,1,3,1,4,1,5,1,1};
    int ne = sizeof(v1) / sizeof(v1[0]);
    mostra(v1, ne);
    int el = 1;
    int sem_esse = elimina(el, v1, ne);
    printf("Apagado %d\n", el);
    mostra(v1, sem_esse);

    printf("\nVetor como ficou ao final:\n\n");
    mostra(v1, ne);
    return 0;
}

int elimina(int elemento, int vetor[], int ne)
{
    int saldo = ne; // pode não ter nenhum
    int tem   = 1; // assume que tem algum a eliminar
    int inicio = 0;
    do {    
        tem = 0; // não tem
        for (int i = inicio; i < saldo; i += 1)
            if (vetor[i] == elemento)
            {  
                vetor[i] = vetor[saldo - 1]; // o ultimo
                vetor[saldo - 1] = elemento; // "swap" 
                saldo -= 1;
                if (saldo == 0) return saldo; // não sobrou nada
                inicio = i; // pode ter outros
                tem = 1; // entao tem
                break; // continua a busca
            };  // if()
    } while (tem);
    return saldo;
};

int mostra(int vetor[], int tamanho)
{
    if (tamanho < 1)
    {   printf("Vetor VAZIO\n");
        return -1;
    }
    printf("Vetor (%d elementos): { ", tamanho);
    for (int i = 0; i < tamanho - 1; i += 1) printf("%d,", vetor[i]);
    printf("%d }\n", vetor[tamanho - 1]);
    return 0;
};

 

 

@Midori @debora jesus

 

    v[j]=v[j-1];

 

Cuidado com as condições limite: o vetor pode terminar vazio se todos os valores forem eliminados e não vai ter como rodar essa linha...

  • Obrigado 1
  • Amei 1
Link para o comentário
Compartilhar em outros sites

[OFF TOPIC]

@arfneto Você escreveu sobre predicate, eu estudei sobre ele em Java. Você também mencionou sobre passar uma função para uma função. Por um acaso, esse código seria um exemplo de "programação funcional"?

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

int somar(int a, int b) {
    return a + b;
}

int multiplicar(int a, int b) {
    return a * b;
}

void interface(int (*funcao)(int, int), int a, int b) {
    int resultado = funcao(a, b);
    printf("Resultado: %d \n", resultado);
}

int main() {
    interface(somar, 1, 2);
    interface(multiplicar, 2, 3);
    return 0;
}

 

  • Curtir 1
Link para o comentário
Compartilhar em outros sites

@AdrianoSiqueira Sim, seria. Mas longe dos conceitos fundamentais, como imutabilidade ...

 

ON-TOPIC agora

 

Considere esse algoritmo de que falei, partition. Veja 3 "predicados" em C com one-liners:

 

    // criterios de exemplo
    int maior_que(int a, int b) { return a <= b; };
    int par(int a, int b) { return a & 1; };
    int diferente_de(int a, int b) { return a == b; };

 

O diferente_de() resolve a questão de @debora jesus no tópico. Basta trocar elimina() por reparte()

 

    int reparte(int elemento, int vetor[], int tamanho, int(*)(int, int));

 

E chamar assim 

 

    sem_esse = reparte(el, v1, ne, diferente_de);

 

reparte() vai retornar quantos são diferentes de x, na prática "eliminando" todo x...

 

Saída
 

Antes:  Vetor (11 elementos): { 1,1,2,1,3,1,4,1,5,1,1 }
Criterio 1: diferente de 1
Depois: Vetor (4 elementos): { 5,4,2,3 }
O vetor inteiro: Vetor (11 elementos): { 5,4,2,3,1,1,1,1,1,1,1 }

 

Ou mesmo 

 

Antes:  Vetor (11 elementos): { 1,1,1,1,1,1,1,1,1,1,1 }
Criterio 1: diferente de 1
Depois: Vetor VAZIO
O vetor inteiro: Vetor (11 elementos): { 1,1,1,1,1,1,1,1,1,1,1 }

 

OFF-TOPIC

 

Usando os outros 2 predicados

 


Criterio 2: par
Retornou 2
Vetor (2 elementos): { 2,4 }
O vetor inteiro: Vetor (11 elementos): { 2,4,3,1,1,1,1,1,1,1,5 }

Criterio 3: (x > 2)
Retornou 3
Vetor (3 elementos): { 5,4,3 }
O vetor inteiro: Vetor (11 elementos): { 5,4,3,1,1,1,1,1,1,1,2 }

 

O EXEMPLO COMPLETO

 

#include <stdio.h>

int reparte(int elemento, int vetor[], int tamanho, int(*)(int, int));
int mostra(int vetor[], int tamanho,const char*);

// criterios de exemplo
int maior_que(int a, int b) { return a <= b; };
int par(int a, int b) { return a & 1; };
int diferente_de(int a, int b) { return a == b; };

int main(void)
{
    int sem_esse = 0;
    int v1[]     = {1, 1, 2, 1, 3, 1, 4, 1, 5, 1, 1};
    //int v1[]     = {1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1};
    int ne       = sizeof(v1) / sizeof(v1[0]);
    mostra(v1, ne, "Antes:\t");
    int el       = 1;
    printf("Criterio 1: diferente de %d\n", el);
    sem_esse = reparte(el, v1, ne, diferente_de);
    mostra(v1, sem_esse, "Depois:\t");
    mostra(v1, ne, "O vetor inteiro: ");

    printf("\nCriterio 2: par\n");
    sem_esse = reparte(el, v1, ne, par);
    printf("Retornou %d\n", sem_esse);
    mostra(v1, sem_esse, NULL);
    mostra(v1, ne, "O vetor inteiro: ");

    printf("\nCriterio 3: (x > %d)\n",el=2);
    sem_esse = reparte(el, v1, ne, maior_que);
    printf("Retornou %d\n", sem_esse);
    mostra(v1, sem_esse, NULL);
    mostra(v1, ne, "O vetor inteiro: ");

    return 0;
}

int reparte( int elemento, int vetor[], int ne, int(*criterio)(int, int))
{
    int saldo  = ne;  // pode não ter nenhum
    int tem    = 1;   // assume que tem algum a eliminar
    int inicio = 0;
    do {
        tem = 0;  // não tem
        for (int i = inicio; i < saldo; i += 1)
            if ( criterio(vetor[i],elemento) )
            {
                int temp         = vetor[i];
                vetor[i]         = vetor[saldo - 1];  // o ultimo
                vetor[saldo - 1] = temp;              // "swap"
                saldo -= 1;
                if (saldo == 0) return saldo;  // não sobrou nada
                inicio = i;                    // pode ter outros
                tem    = 1;                    // entao tem
                break;                         // continua a busca
            };                                 // if()
    } while (tem);
    return saldo;
};

int mostra(int vetor[], int tamanho,const char* tit)
{
    if (tit != NULL) printf("%s", tit);
    if (tamanho < 1)
    {
        printf("Vetor VAZIO\n");
        return -1;
    }
    printf("Vetor (%d elementos): { ", tamanho);
    for (int i = 0; i < tamanho - 1; i += 1) printf("%d,", vetor[i]);
    printf("%d }\n", vetor[tamanho - 1]);
    return 0;
};

 

 

Antes:  Vetor (11 elementos): { 1,1,2,1,3,1,4,1,5,1,1 }
Criterio 1: diferente de 1
Depois: Vetor (4 elementos): { 5,4,2,3 }
O vetor inteiro: Vetor (11 elementos): { 5,4,2,3,1,1,1,1,1,1,1 }

Criterio 2: par
Retornou 2
Vetor (2 elementos): { 2,4 }
O vetor inteiro: Vetor (11 elementos): { 2,4,3,1,1,1,1,1,1,1,5 }

Criterio 3: (x > 2)
Retornou 3
Vetor (3 elementos): { 5,4,3 }
O vetor inteiro: Vetor (11 elementos): { 5,4,3,1,1,1,1,1,1,1,2 }

 

Entendeu o uso, @AdrianoSiqueira?
 

1 hora atrás, AdrianoSiqueira disse:

predicate, eu estudei sobre ele em Java


Muitos textos sobre java são um tanto pedantes, dando a entender que java criou ou representa de fato certos conceitos. Não acho que seja verdade. Coisas como filter(), map() e reduce() existem em muitas linguagens. A própria noção de código intermediário precede java em décadas, mas às vezes se vê isso como algo dessa linguagem. Me lembra a Apple :) em muitas coisas 

 

  • Curtir 1
  • Obrigado 1
Link para o comentário
Compartilhar em outros sites

Entendi sim. É incrível a quantidade de código que pode economizar seguindo esses princípios.

 

59 minutos atrás, arfneto disse:

Muitos textos sobre java são um tanto pedantes, dando a entender que java criou ou representa de fato certos conceitos.

Costumo fazer ligação com o Java porque é a linguagem que eu estudei mais a fundo e é a que eu tenho mais afinidade, assim eu entendo as coisas com mais facilidade.

  • Curtir 2
Link para o comentário
Compartilhar em outros sites

16 horas atrás, arfneto disse:

Cuidado com as condições limite: o vetor pode terminar vazio se todos os valores forem eliminados e não vai ter como rodar essa linha...

O que quer dizer com "condições limite"? É esperado que o vetor termine vazio se testar verdadeiro para todos os elementos. E nesse caso a variável 'ne' acaba com zero.

Link para o comentário
Compartilhar em outros sites

49 minutos atrás, Midori disse:

O que quer dizer com "condições limite"? É esperado que o vetor termine vazio se testar verdadeiro para todos os elementos. E nesse caso a variável 'ne' acaba com zero.



@Midori Sim, e essa linha 


 

17 horas atrás, arfneto disse:
 v[j]=v[j-1];

 

 

vai cancelar seu programa. O que vai fazer com o último elemento? Essa é a condição limite...

 

Como eu expliquei esse é um algoritmo simples, conhecido. É melhor usar algo como eu mostrei, preservando o vetor mas retornando um valor.

Link para o comentário
Compartilhar em outros sites

@Midori Esse é um algoritmo clássico. É chamado partição e é mais seguro (e produtivo) implementar como no exemplo que eu mostrei. Em especial porque pode

  • varrer o vetor uma única vez
  • mantem os dados disponíveis, todos
  • pode trocar o critério (chamado predicado na literatura) livremente e tudo continua funcionando. Pode separar os primos, as fichas dos idosos, os números ímpares ou qualquer coisa. E testar em separado e nunca mexer no programa. Veja a implementação de reparte() acima.
Link para o comentário
Compartilhar em outros sites

Crie uma conta ou entre para comentar

Você precisa ser um usuário para fazer um comentário

Criar uma conta

Crie uma nova conta em nossa comunidade. É fácil!

Crie uma nova conta

Entrar

Já tem uma conta? Faça o login.

Entrar agora

Sobre o Clube do Hardware

No ar desde 1996, o Clube do Hardware é uma das maiores, mais antigas e mais respeitadas comunidades sobre tecnologia do Brasil. Leia mais

Direitos autorais

Não permitimos a cópia ou reprodução do conteúdo do nosso site, fórum, newsletters e redes sociais, mesmo citando-se a fonte. Leia mais

×
×
  • Criar novo...