C++ Como remover elementos repetidos de uma Fila que utilizada ponteiros em C/C++

[Lucas Rocha Fernandes]

#include <iostream>

using namespace std;

struct No
{
   int Info;
   No *Lig;
};

typedef No *NoPtr;

struct Fila
{
   NoPtr Com;
   int Nro;
   NoPtr Fim;
};

void IniciaFila(Fila &F)
{
   F.Nro = 0;
   F.Com = NULL;
   F.Fim = NULL;
}

bool FilaVazia(Fila F)
{
   return !F.Nro;
}

void InsereFila(Fila &F, int Novo)
{
   NoPtr P = new No;
   P->Info = Novo;
   P->Lig = NULL;
   if (F.Nro == 0)
      F.Com = F.Fim = P;
   else
   {
      F.Fim->Lig = P;
      F.Fim = P;
   }
   F.Nro++;
}

bool RetiraFila(Fila &F, int &Valor)
{
   if (FilaVazia(F))
      return false;
   else
   {
      NoPtr P = F.Com;
      Valor = P->Info;
      F.Com = P->Lig;
      F.Nro--;
      if (F.Nro == 0)
         F.Fim = NULL;
      delete P;
   }
   return true;
}

int main()
{

   Fila F;
   IniciaFila(F);
   InsereFila(F, 10);
   InsereFila(F, 10);
   InsereFila(F, 20);
   InsereFila(F, 20);
   InsereFila(F, 30);
   InsereFila(F, 30);
   InsereFila(F, 20);
   InsereFila(F, 10);
   InsereFila(F, 10);
   InsereFila(F, 20);
   InsereFila(F, 20);
   InsereFila(F, 120);

   return 0;
}

 

[devair1010]

@Lucas Rocha Fernandes       melhor do que remover os repetidos seria não incluir   esses tais ,  fazendo comparação antes de incluir. 

[arfneto]

Você postou um programa em C na verdade. Exceto por

• trocar stdio.h por iostream
• usar bool, que está até disponível em C via o quase inútil stdbool.h através de uma macro.
• alguns argumentos passados como referência, que C não tem
• E por uma referência a

struct No

dentro da declaração de No ---  forward reference --- que não existe em C

 

Recomendo muito usar C++ de fato. É uma linguagem muito mais expressiva e é MUITO mais fácil representar as coisas em C++ do que em C, mesmo sem usar muita coisa da (enorme) linguagem em si. É provável  perda de tempo e oportunidade usar C assim, mascarada como C++.

 

Sobre a parte C

 

    typedef No *NoPtr;

 

Não há razão para usar typedef em C++.

 

Em C recomendo MUITO nunca definir um nome para um ponteiro. Isso sempre cai na sua cabeça, Porque? Simples: veja acima: NoPtr é um ponteiro. Tem empresas e autores que usam um p_ como prefixo no nome. Aqui se usou o sufixo Ptr. Tem gente que usa um P na frente, como a Microsoft usou por décadas. Desde os 70 se sabe como declarar um ponteiro: trata-se do operador *. E para pegar o endereço tem o inverso, o operador &.

 

Se No é um nome, então é claro que pode declarar 
 

    No    um_no;
    No    outro_no;
    No*   pNo;
    No**  algomais;

 

Então qual a vantagem de usar 
 

    NoPtr		outro;

 

Se

 

    No*    outro;

 

É a mesma coisa?

Só torna o programa mais difícil de ler. O typedef acrescenta um nome a mais e não soma nada ao programa. E pode ficar mais difícil de ler e entender as declarações.

 

    typedef No *NoPtr;

 

E escrever desse modo ainda torna mais difícil entender as coisas: typedef define um nome e associa a um tipo. Qual o nome aqui? NoPtr. E qual o tipo de NoPtr? Isso é C, NoPtr é No*. O compilador pode te dizer isso. Então se está aprendendo evite esse vício e declare as coisas como são de fato:
 

    typedef  No*    NoPtr;

 

Porque está declarando NoPtr como um nome alternativo para No*.  E é claro que se NoPtr é No* então *NoPtr é No. É C afinal. Mas isso é consequência e não o que está sendo declarado. Nomes são declarados. Veja o protótipo comum de main:
 

    int main( int argc, char**  argv);

 

É comum encontrar

 

    int main( int argc, char   **argv);

 

Que é equivalente. Para o compilador espaços são desprezados. Só que os argumentos são argc e argv. E os tipos são int e char**.  Então isso dificulta pro cara que está aprendendo ver o que é o que.

 

De volta a Lista e C++

 

Essa seria uma maneira de definir a tal Fila em C++. 

 

struct No
{
    int Info;
    No* Lig;
};

struct Fila
{
    No*      Com;
    int      Nro;
    No*      Fim;
    unsigned tamanho;

    Fila();
    ~Fila();
    bool Vazia();
    void Insere(int);
    bool Retira(int&);
};

 

Repare que é muito mais simples e legível. As funções fazem parte da struct. E faz sentido.

 

Retira()

 

Não consigo entender essa função. Vai apenas retirar o primeiro da fila?

 

E em todo caso vendo o código

 

bool RetiraFila(Fila &F, int &Valor)
{
    if (FilaVazia(F))
        return false;
    else
    {
        NoPtr P = F.Com;
        Valor   = P->Info;
        F.Com   = P->Lig;
        F.Nro--;
        if (F.Nro == 0) F.Fim = NULL;
        delete P;
    }
    return true;
}

 

Não seria melhor algo mais expressivo como Atende()? 

 

Porque um else depois de um return? Não seria mais legível escrever

 

bool Retira(Fila &F, int &Valor)
{
    if (FilaVazia(F)) return false;
    No *p = F.Com; // salva F.Com
    Valor = F.Com->Info;
    F.Com = F.Com->Lig;
    delete p;
    F.Nro--;
    return true;
}

 

 

Sobre remover os elementos repetidos

 

Use um loop dentro da lista e dentro dele apenas use outro loop comparando e removendo os elementos iguais a partir do elemento que está focado no primeiro loop. Então o loop externo varre todos elementos e o interno varre os restantes a partir deste. Como a lista é "viva" ela pode ir diminuindo durante o loop. Considere por exemplo uma lista que tenha 10 valores, todos iguais.

 

Ao estilo Highlander --- o filme --- ao final só pode haver um. Um de cada.