C Dado um conjunto de números, descubra a quantidade de Números repetidos.

Gina Santos · 22 de junho de 2021

Preciso criar um programa em c e estou tendo dificuldades na implementação dele.

Ele pede o seguinte:

Input

Em cada entrada há vários casos de teste. Um caso de teste segue a forma: primeira linha contém dois números: 1) representa a quantidade de números do conjunto (1 ≤ C ≤ 10 7 ) e 2) quantidade dos N menores números duplicados a serem listados (0 ≤ N ≤ 10 7 ). A segunda linha contém C números, que representam os números do conjunto (1 ≤ Ci ≤ 10 9 ).

Output

Para cada caso de teste, imprima duas linhas: a primeira contendo a quantidade total de números duplicados e a segunda com uma lista ordenada dos N menores números duplicados, separados uns dos outros por um espaço (exceto no final – último número da lista). Caso N seja zero ou não tenham números duplicados, escreva “empty” (sem aspa). Se N for maior do que a quantidade de números duplicados, liste todos os duplicados. Se N for menor doque a quantidade total de números duplicados, liste apenas o Ns menores e em ordem crescente. Restrições da Solução C Seu código não pode usar rotinas de biblioteca para manipular/alterar os dados. Apenas as rotinas de biblioteca p/ interação com o teclado/tela (ex., printf, scanf, gets, ...) e as rotinas relacionadas à alocação de memória (ex. malloc, calloc, ...) são permitidas. Seu código não deve usar variáveis globais. Seu programa deve usar alocação dinâmica de memória. Não utilize Vetores/matrizes como estrutura de dados. Seu código deve ser formado por funções e/ou procedimentos criados por você. Deve haver no mínimo 1 funções/procedimentos.

Example

Input:

13 5

1 1 3 3 5 5 7 7 10 10 10 11 11

13 3

1 1 3 3 5 5 7 7 10 10 10 11 11

Output:

13

1 3 5 7 10

13

1 3 5

O meu código ficou assim, tem alguém que possa me auxiliar para que o programa possa somar a quantidade de digitos repetidos na entrada e na saída somar essa quantidade e ordenar a lista em ordem crescente?

Output: 13 1 3 5 7 10 13 1 3 5

#include <stdlib.h>
#include <stdio.h>
#define MAX 10


typedef struct {
  int Chave;
} TipoItem;

typedef struct TipoCelula *TipoApontador;

typedef struct TipoCelula {
  TipoItem Item;
  TipoApontador Prox;
} TipoCelula;

typedef struct {
  TipoApontador Primeiro, Ultimo;
} TipoLista;


void FLVazia(TipoLista *Lista)
{ Lista -> Primeiro = (TipoApontador) malloc(sizeof(TipoCelula));
  Lista -> Ultimo = Lista -> Primeiro;
  Lista -> Primeiro -> Prox = NULL;
}

int Vazia(TipoLista Lista)
{ return (Lista.Primeiro == Lista.Ultimo);
}

void Insere(TipoItem x, TipoLista *Lista)
{ Lista -> Ultimo -> Prox = (TipoApontador) malloc(sizeof(TipoCelula));
  Lista -> Ultimo = Lista -> Ultimo -> Prox;
  Lista -> Ultimo -> Item = x;
  Lista -> Ultimo -> Prox = NULL;
}

void Retira(TipoApontador p, TipoLista *Lista, TipoItem *Item)
{ /*  ---   Obs.: o item a ser retirado e  o seguinte ao apontado por  p --- */
  TipoApontador q;
  if (Vazia(*Lista) || p == NULL || p -> Prox == NULL)
  { printf(" Erro: Lista vazia ou posicao não existe\n");
    return;
  }
  q = p -> Prox;
  *Item = q -> Item;
  p -> Prox = q -> Prox;
  if (p -> Prox == NULL) Lista -> Ultimo = p;
  free(q);
}

void Imprime(TipoLista Lista)
{ TipoApontador Aux;
  Aux = Lista.Primeiro -> Prox;
  while (Aux != NULL)
    { printf("%d\n", Aux -> Item.Chave);
      Aux = Aux -> Prox;
    }
}


Me ajudem preciso incluir algumas funções e não estou dando conta.

devair1010 · 23 de junho de 2021

@Gina Santos você está usando typedef struct para um programa simples , isso é como um canhão para uma mosca , você pode fazer com um vetor , e não precisaria de nenhuma função , mas com elas seu código poderia ser assim :

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

void cls(int *,int);
void asdrubaL(int *,int);
int main()
{
    int n,d,i;
    int num[1000];
    while( 1 )
    {
        printf("\nqtd de numeros e os duplicados ");
        scanf("%d%d",&n,&d);
        for(i=0; i<n; i++)
        {
            scanf("%d",&num[i]);
        }
        // uma funçãozinha
        cls(num,n);

        printf("\n%d\n",n);

        // outra função
        asdrubaL(num,d);
      
        printf("\n");
    }
    return 0;
}
void cls(int    *num, int n)
{
    int j,i,aux;
    for(i=0; i<n; i++)
    {
         for(j=i+1; j<n; j++)
        {
            if( num[i] > num[j])
            {
                aux    = num[i];
                num[i] = num[j];
                num[j] =    aux;
            }
        }
    }
}
void asdrubaL(int*   num,int d)
{
    int i,ax,n;
    for(i=0,ax=0; i<d; ax++,i++)
    {
        n = num[ax];
        printf("%d ",n);
        while(num[ax+1] == n)ax++;
    }
}

Midori · 23 de junho de 2021

@Gina Santos Acho que dessa forma vai dar mais trabalho, se seu código tiver só uma estrutura talvez fique mais simples. Fiz com algumas funções para inserir, imprimir e mostrar o resultado ordenado. Ainda não tive tempo de testar mais e talvez tenha que fazer alguma correção, mas é algo assim (não fiz exatamente como pedido, é mais para tirar os repetidos e mostrar o resultado ordenado),

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

typedef struct lista{
    int numero;
    struct lista *proximo;
}Lista;

Lista *imprime(Lista *lista){
    for(Lista *p = lista; p != NULL; p = p->proximo){
        printf (" %d", p->numero);
    }
    return lista;
}

Lista *ordena(Lista *lista) {
    for(Lista *i = lista; i->proximo != NULL; i = i->proximo){
        for(Lista *j = lista; j != i->proximo; j = j->proximo){
            if(i->proximo->numero < j->numero){
                int aux = i->proximo->numero;
                i->proximo->numero = j->numero;
                j->numero = aux;
            }
        }
    }
    return lista;
}

Lista *insere(int numero, Lista *lista){
   Lista *novo = (Lista *)malloc(sizeof(Lista));
   novo->numero = numero;
   novo->proximo = lista;
   return novo;
}

Lista *resultado(Lista *lista){
    Lista *novo = (Lista *)malloc(sizeof(Lista *));
    Lista *i;
    novo = NULL;
    for(i = lista; i->proximo != NULL; i = i->proximo){
        if(i->numero != i->proximo->numero){
            novo = insere(i->numero, novo);
        }
    }
    novo = insere(i->numero, novo);
    novo = ordena(novo);
    return novo;
}

int main(){
    Lista *lista = NULL;

    lista = insere(3, lista);
    lista = insere(10, lista);
    lista = insere(1, lista);
    lista = insere(1, lista);
    lista = insere(3, lista);
    lista = insere(5, lista);
    lista = insere(5, lista);
    lista = insere(7, lista);
    lista = insere(7, lista);
    lista = insere(10, lista);
    lista = insere(10, lista);
    lista = insere(11, lista);
    lista = insere(11, lista);
    
    lista = ordena(lista);
    imprime(resultado(lista));

    return 0;
}

9 horas atrás, devair1010 disse:

você pode fazer com um vetor

O enunciado diz para não usar vetor.

Gina Santos · 23 de junho de 2021

11 horas atrás, devair1010 disse:

@Gina Santos você está usando typedef struct para um programa simples , isso é como um canhão para uma mosca , você pode fazer com um vetor , e não precisaria de nenhuma função , mas com elas seu código poderia ser assim :

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

void cls(int *,int);
void asdrubaL(int *,int);
int main()
{
    int n,d,i;
    int num[1000];
    while( 1 )
    {
        printf("\nqtd de numeros e os duplicados ");
        scanf("%d%d",&n,&d);
        for(i=0; i<n; i++)
        {
            scanf("%d",&num[i]);
        }
        // uma funçãozinha
        cls(num,n);

        printf("\n%d\n",n);

        // outra função
        asdrubaL(num,d);
      
        printf("\n");
    }
    return 0;
}
void cls(int    *num, int n)
{
    int j,i,aux;
    for(i=0; i<n; i++)
    {
         for(j=i+1; j<n; j++)
        {
            if( num[i] > num[j])
            {
                aux    = num[i];
                num[i] = num[j];
                num[j] =    aux;
            }
        }
    }
}
void asdrubaL(int*   num,int d)
{
    int i,ax,n;
    for(i=0,ax=0; i<d; ax++,i++)
    {
        n = num[ax];
        printf("%d ",n);
        while(num[ax+1] == n)ax++;
    }
}

Seria ótimo! Realmente, bem mais prático, mas não posso usar vetor. Mesmo assim, muito obrigada,

arfneto · 23 de junho de 2021

12 horas atrás, devair1010 disse:

você está usando typedef struct para um programa simples , isso é como um canhão para uma mosca , você pode fazer com um vetor , e não precisaria de nenhuma função

Não, não é o caso. Antes de tudo, uso de typedef e struct facilita muito o desenvolvimento e não o contrário.
Usar funções mais ainda. C sem funções é ultra complicado. Qualquer linguagem na verdade sem funções --- ou classes --- é inútil.

IMPORTANTE: considere o enunciado:

19 horas atrás, Gina Santos disse:

Não utilize Vetores/matrizes como estrutura de dados

E

19 horas atrás, Gina Santos disse:

Seu código deve ser formado por funções e/ou procedimentos criados por você

Assim é.

19 horas atrás, Gina Santos disse:

O meu código ficou assim, tem alguém que possa me auxiliar para que o programa possa somar a quantidade de digitos repetidos na entrada e na saída somar essa quantidade e ordenar a lista em ordem crescente?

@Gina SantosSeu programa parece bem construído apesar de alguns vícios que dificultam a leitura.

Para uma vida mais simples escreva em torno dos dados e modifique a inserção na lista: insira os caras na ordem já, e apenas se ainda não estiverem na lista. Assim na hora de mostrar o resultado é só mostrar os primeiros N elementos da lista e tudo estará naturalmente resolvido.

Seu programa não ganhou nada por ter todos os typedef iniciando por Tipo só fica mais comprido e chato de ler e digitar. Use uma convenção mais simples como a clássica: apenas a primeira letra em maiúscula.

NUNCA crie tipos para ponteiros. Só vai confundir você e todo mundo. Se X é um tipo X* é um ponteiro. Foi resolvido nos anos '60.

Compare essas estruturas (na direita do modo como escreveu)

Talvez concorde que na esquerda fica claro que a Lista é de Celula e a Celula tem Item.

E do lado direito não tem como saber que TipoApontador aponta para Item, o simples e trivial Item*. Se tivesse meia dúzia desses no meio do programa teria que fica olhando para as declarações toda hora até se acostumar.

E esse monte de Tipoxxx não ajuda muito. Sugiro reservar a primeira letra maiúscula para esses casos e seguir adiante.

Coloque todos os #define ANTES do primeiro include...

Use protótipos.

entenda que manter o tamanho atualizado DENTRO da lista vai economizar muito tempo.

usar ponteiro para um lado só não é mais fácil e sim muito mais difícil de programar. Uma lista "duplamente encadeada" é muito mais simples do que uma lista com ponteiros para um lado só. Ao não ter ponteiros para um lado por exemplo de pouco ou nada adiante ter ponteiros (como declarou) para o início e o fim... E qualquer operação na lista implica em se posicionar de novo no início ou no fim conforme o ponteiro que tenha.

Usar ponteiros para um só lado só tem sentido em situações muito restritas, como uma lista que não é alterada ou uma situação em que o espaço de mais um ponteiro seja significativo

Gina Santos · 23 de junho de 2021

@Midori

No int main caso eu siga a sua lógica ao invés de já aparecer na tela eu poderia tipo inseri-los? trocaria o codigo seu do int main por:

int main(){
int contador= 0;
int id;
char entrada[10];
Lista *lista = NULL;

while(scanf("%s",entrada)!= -1){
if(strcmp(entrada,"Entrada")==0){
lista = imprime(lista);
contador=contador+1;
}
if (strcmp(entrada, "Saida")==0){
if(lista != NULL){
contador=contador-1;
printf("%d/n",lista->numero,contador);
}
lista = ordena(lista);
imprime(resultado(lista));
}
}

}

arfneto · 23 de junho de 2021

14 minutos atrás, Gina Santos disse:

while(scanf("%s",entrada)!= -1){

Não é uma boa ideia: não ler nada não é um erro. scanf() vai retornar zero e vai entrar no loop com o mesmo valor que tinha antes em entrada

No geral esse tipo loop não é boa ideia para um programa em desenvolvimento: não faça NADA interativo. É muito chato e improdutivo ficar em frente ao terminal inventando parâmetros.

Compare com esse exemplo que mostra

20 19 18 17 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1

#define MAX 10
#include <stdio.h>

typedef struct
{
  int Chave;

}   Item;


typedef struct
{
    Item    item;
    Item*   prox;

}   Celula;


typedef struct
{
  Item*     primeiro;
  Item*     ultimo;
  unsigned  tamanho;

}   Lista;

Lista* Insere(Item,Lista*);

int main(void)
{
    Lista*  l = NULL;
    for ( int i = 20; i>0; i-=1 ) l = Insere((Item){i}, l);
    printf( "\n");
    return 0;
};

Lista* Insere(Item x, Lista* L)
{
  printf( "%d ", x.Chave);
  return NULL;
}

Modifique Insere() para inserir os valores já por ordem de Chave. E ignore as duplicatas, como eu expliquei antes. Assim ao terminar de inserir só precisa mostrar os primeiros N valores. É muito mais simples e poderá usar sempre se escrever direito.

Gina Santos · 23 de junho de 2021

@arfneto Eu fiz as alterações realmente a estrutura fica mais fácil de entender só que na hora em que fui fazer a troca me confundi toda, eu confundo um pouco pode dar uma olha no que fiz e me ajudar a corrigir?

9 minutos atrás, arfneto disse:
Não é uma boa ideia: não ler nada não é um erro. scanf() vai retornar zero e vai entrar no loop com o mesmo valor que tinha antes em entrada

No geral esse tipo loop não é boa ideia para um programa em desenvolvimento: não faça NADA interativo. É muito chato e improdutivo ficar em frente ao terminal inventando parâmetros.

Compare com esse exemplo que mostra
20 19 18 17 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 
12 minutos atrás, arfneto disse:
Não é uma boa ideia: não ler nada não é um erro. scanf() vai retornar zero e vai entrar no loop com o mesmo valor que tinha antes em entrada

No geral esse tipo loop não é boa ideia para um programa em desenvolvimento: não faça NADA interativo. É muito chato e improdutivo ficar em frente ao terminal inventando parâmetros.

Compare com esse exemplo que mostra
20 19 18 17 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 
#define MAX 10
#include <stdio.h>

typedef struct
{
  int Chave;

}   Item;


typedef struct
{
    Item    item;
    Item*   prox;

}   Celula;


typedef struct
{
  Item*     primeiro;
  Item*     ultimo;
  unsigned  tamanho;

}   Lista;

Lista* Insere(Item,Lista*);

int main(void)
{
    Lista*  l = NULL;
    for ( int i = 20; i>0; i-=1 ) l = Insere((Item){i}, l);
    printf( "\n");
    return 0;
};

Lista* Insere(Item x, Lista* L)
{
  printf( "%d ", x.Chave);
  return NULL;
}
Modifique Insere() para inserir os valores já por ordem de Chave. E ignore as duplicatas, como eu expliquei antes. Assim ao terminar de inserir só precisa mostrar os primeiros N valores. É muito mais simples e poderá usar sempre se escrever direito.
Vou tentar aqui fazer como me explicou.

Modifique Insere() para inserir os valores já por ordem de Chave. E ignore as duplicatas, como eu expliquei antes. Assim ao terminar de inserir só precisa mostrar os primeiros N valores. É muito mais simples e poderá usar sempre se escrever direito.

arfneto · 23 de junho de 2021

3 horas atrás, Gina Santos disse:

Seria ótimo! Realmente, bem mais prático, mas não posso usar vetor

Não, não seria ótimo muito menos mais prático. Tente depois que resolver usando uma estrutura de dados

Um vetor é só uma lista sequencial. É muito rápido de acessar, e simples. Mas para aí.

Por essa razão alguém cria e alguém estuda estruturas de dados: listas, pilhas, filas, grafos, dicionários, tabelas hash, todas tem uma inteligência embutida e habilidades que vem junto.

O vetor é cru. Nada tem. E pode ser usado para implementar essas estruturas com sucesso.

Se usar uma estrutura "herda" --- e esse é o termo em C++ ou java por exemplo --- os métodos da estrutura.

Uma pilha tem TOP POP e PUSH sempre e você pode contar com isso para ver o primeiro, ou para tirar ou por algo numa pilha. E como só tem acesso ao primeiro da pilha, tem uma segurança que vem a partir disso. Pode usar um vetor? Claro. Mas aí toda a disciplina fica por sua conta. E uma pilha de char é a mesma coisa que uma pilha de registros struct que descrevam algo incrivelmente complicado: você usa as mesmas funções. Esse é o conceito de abstração. Junto ao conceito de herança que citei há pouco, são dois dos pilares da orientação a objetos, somados à noção de polimorfismo, que envolve funções que operam com diferentes argumentos mas tem o mesmo nome.

Por isso eu disse que se fizer isso direito (escrever uma boa implementação de lista) vai usar sempre: abstração. E por isso essas estruturas são chamadas de ADS (EAD) --- Abstract Data Strucutures na literatura.

1 hora atrás, Gina Santos disse:

Eu fiz as alterações realmente a estrutura fica mais fácil de entender só que na hora em que fui fazer a troca me confundi toda, eu confundo um pouco pode dar uma olha no que fiz e me ajudar a corrigir?

Podia perguntar algo sobre o que confundiu você...

E postar o código como está.

Em relação às mudanças a maioria dos IDE e editores altera o programa usando control H ou F2 ou controlR...

int main(void)
{
    Lista*  l = NULL;
    for ( int i = 20; i>0; i-=1 ) l = Insere((Item){i}, l);
    printf( "\n");
    return 0;
};

Notou que no programa que te mostrei os valores são inseridos em ordem decrescente? Assim se você inserir na ordem já vai testar um dos cenários.. Ao percorrer a lista eles devem estar arrumadinhos de 1 a 20 e aí não fica nada difícil achar os N menores...

Midori · 23 de junho de 2021

4 horas atrás, Gina Santos disse:

No int main caso eu siga a sua lógica ao invés de já aparecer na tela eu poderia tipo inseri-los? trocaria o codigo seu do int main por

Refiz o código e acho que desta forma fica mais simples. Agora com a função existe evito que entre um número duplicado na lista. E na função insere o número já é colocado em ordem crescente.

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

typedef struct lista{
    int numero;
    struct lista *proximo;
}Lista;

int existe(Lista *L, int numero){
    while(L != NULL){
        if(L->numero == numero){
            return 1;        
        }
        L = L->proximo;
    }
    return 0;
}

Lista *insere(Lista *L, int numero){
    Lista *N;
    Lista *P = L;
    Lista *A = NULL;

    if(existe(L, numero)){
        return L;
    }        
    N = (Lista *)malloc(sizeof(Lista));
    N->numero = numero;
    
    while(P != NULL && P->numero < numero){
        A = P;
        P = P->proximo;
    }
    if(A == NULL){
        N->proximo = L;
        L = N;
    }else{
        N->proximo = A->proximo;
        A->proximo = N;
    }
    return L;
}

Lista *imprime(Lista *L){
    while(L != NULL){
        printf(" %d", L->numero);
        L = L->proximo;
    }
    return L;
}

int main(){
    Lista *lista = NULL;
    Lista *resultado = NULL;
    int c;
    int n;
    
    scanf("%d %d", &c, &n);
    while(c){
        int numero;
        scanf("%d", &numero);
        lista = insere(lista, numero);
        c -= 1;
    }
    while(n){
        resultado = insere(resultado, lista->numero);
        lista = lista->proximo;
        n -= 1;
    }
    imprime(resultado);
    return 0;
}

Usei este material como base para fazer,

https://www.ic.unicamp.br/~ra069320/PED/MC102/1s2008/Apostilas/Cap10.pdf

arfneto · 23 de junho de 2021

15 minutos atrás, Midori disse:

Agora com a função existe evito que entre um número duplicado na lista. E na função insere o número já é colocado em ordem crescente #10

5 horas atrás, arfneto disse:

Para uma vida mais simples escreva em torno dos dados e modifique a inserção na lista: insira os caras na ordem já, e apenas se ainda não estiverem na lista. Assim na hora de mostrar o resultado é só mostrar os primeiros N elementos da lista e tudo estará naturalmente resolvido #5

Pois é... Foi o que eu disse no tópico #5