C++, classe Lista Ligada

mar_tchello · 23 de março de 2007

Boa tarde senhores.

Bom, na aula de estrutura de dados to implementando uma classe de uma lista ligada. Sim, eu vi aquele topico acima da lista encadeada simples, mas alem dele estar em C não tem nada do que preciso.

Enfim, estou com algumas pequenas duvidas, então colocarei o arquivo HEADER (ou cabeçado, como preferir)

disponivel e os metodos que to com algumas duvidas na implementaçao.

Como sao muitas linhas de codigo e trocentos metodos vou colocar no post visivel apenas os que pretendo perguntar, oferecendo o maximo de informaçao util possivel.

Espero não estender tanto o topico pra não cansa los nem pra espanta los hehehehe... mas não garanto >_<.

#DUVIDA 1|-------------------------------------------------------------------------| //marcador pra diferenciar cada metodo.

Começando pelo metodos "remove_final"

ListaLig::remove_final(){

no*varre;

no*aux;

if(referencia==NULL){exit(1);}; //Verifica se a lista esta vazia

while(varre!=NULL){

aux=varre;

varre=varre->prox;};

delete aux; //REVER

}

referencia é um atributo da classe, ponteiro que fica no primeiro elemento da lista, se ele estiver apontando NULL significa que a lista esta vazia.

Como notaram varri a lista até chegar no ultimo elemento, deixei um ponteiro aux nesse ultimo e deletei o.

A minha duvida: eu acredito que deveria deixar o ponteiro do penultimo elemento apontando pra NULL, mas não o fiz, simplesmente deletei o ultimo e boa.

Como faço? pensei num modo mas ia usar mais dois ponteiros com mais uma varredura e acho que meu professor iria me rancar a cabeça fora se o fizer ehehehe

#DUVIDA 2|-------------------------------------------------------------------------|

Agora é o metodo insere_posic. Conceito simples: o usuario indica uma posiçao e esse metodo insere um novo elemento nessa posição. La vai:

ListaLig::insere_posic(){//Insersao em uma posiçao qualquer da lista

if(tamanho(qtd)==o){exit(1);};//******REVER variavel QTD

no*novo = new no;

no*varre;

no*aux;

while(varre!=Pos){//****REVER variavel POS

aux=varre;

varre=varre->prox;};

novo->prox = aux->prox;

aux->prox = novo;

novo->info = valor; //REVER********

};

Ta fácil de encontrar minhas duvidas ai, estão nos comentarios hehehe.

Primeiro: na classe existe um atributo inteiro chamado qtd, que armazena o tamanho da lista, inicializada pelo construtor como 0. Posso simplesmente modifica la dentro dos metodos assim? já fiz um metodo "quantidade" que foi chamado nesse ai na linha 2, dentro do if, ta certo o jeito que a chamei? tamanho(qtd)?

Segundo: variavel pos. Essa é a variavel que armazena o que o usuario inseriu, a posiçao que ele deseja. Por conceitos de reusabilidade do c++ não vou colocar "strtoint(edit1)" (no caso do builder) etc e tal, como faço então pra esse metodo "capturar" essa variavel?

Terceiro: informaçao contida nesse novo elemento da lista. Essa pergunta é semelhante a segunda desse metodo (listada acima), como devo capturar esse valor? como podem ver atribui um valor "valor" a ela, mas nem declarei nem nd. help!!

|-------------------------------------------------------------------------|

Bom galera, por enquanto é só. por enquanto ehehehehehe

Tem muitos outros metodos, mas me tirando essas duvidas já soluciono todos os outros facilmente.

Vou colocar agora o construtor e destrutor caso seja util.

ListaLig::ListaLig(){ //construtor

referencia=NULL;

qtd=0;

}

//--------------------------------------------------

ListaLig::~ListaLig(){ //destrutor

no*aux;

while(referencia!=NULL){

aux=referencia;

referencia=referencia->prox;

delete aux;

};

};

|-------------------------------------------------------------------------|

Agora o Header

#ifndef _classeListaLig_HPP

#define _classeListaLig_HPP

#include <iostream>

struc no{

string info;

no*prox;

};

class ListaLig

{

private:

no*referencia;

int qtd;

public:

ListaLig();

~ListaLig();

void insere_inicio(string);

void insere_final(string);

void insere_posic(string,int);

void insere_apos(string,int);//?

void insere_antes(string,int);//?

string remove_inicio();

string remove_final();

string remove_posic();

string remove_apos();//?

string remove_antes();//?

int tamanho(); //indica o tamanho da lista

int vazia(); //sim ou não se a lista esta vazia

string primeiro(); //indica qual o primeiro elemento da lista

string ultimo(); //indica qual o ultimo elemento da lista

string elemento(int);//indica qual elemento esta na posiçao dada

int find(string);

};

#endif

ps: como chama aquela ferramenta que simplifica citaçoes?

galera, perdoe me pelo tamanho do post, tentei ser o mais claro possivel e postar o necessario pra que não haja duvidas em relaçao ao que desejo.

Abraçooss!!!! e help aí!

EduardoS · 24 de março de 2007

#DUVIDA 1|-------------------------------------------------------------------------| //marcador pra diferenciar cada metodo.

Começando pelo metodos "remove_final"

ListaLig::remove_final(){

no*varre;

no*aux;

if(referencia==NULL){exit(1);}; //Verifica se a lista esta vazia

while(varre!=NULL){

aux=varre;

varre=varre->prox;};

delete aux; //REVER

}

referencia é um atributo da classe, ponteiro que fica no primeiro elemento da lista, se ele estiver apontando NULL significa que a lista esta vazia.

Como notaram varri a lista até chegar no ultimo elemento, deixei um ponteiro aux nesse ultimo e deletei o.

A minha duvida: eu acredito que deveria deixar o ponteiro do penultimo elemento apontando pra NULL, mas não o fiz, simplesmente deletei o ultimo e boa.

Como faço? pensei num modo mas ia usar mais dois ponteiros com mais uma varredura e acho que meu professor iria me rancar a cabeça fora se o fizer ehehehe

Nem a aux e nem a varre foram inicializadas, precisa inicializar uma das variáveis com a referência.

E você precisa manter uma referência ao penultimo elemento para marcar o prox dele como NULL.

Ao invés de testar varre com NULL você pode testar varre->prox, assim quando sair do while o varre estara apontando para o ultimo elemento e o aux para o penúltimo:


ListaLig::remove_final()
{
    no*varre = referencia;//inicializar a variavel
    no*aux = NULL;//essa tambem, por que não?
    if(referencia==NULL){exit(1);}; //Verifica se a lista esta vazia
    while(varre->prox!=NULL)
    {
        aux=varre;
        varre=varre->prox;
    };
    delete varre; //agora varre que é o ultimo
    if(aux)/*se a lista só tiver um elemento aux sera NULL e o prgrama vai dar pau, esse if resolve*/
        aux->prox = NULL;
}

#DUVIDA 2|-------------------------------------------------------------------------|

Agora é o metodo insere_posic. Conceito simples: o usuario indica uma posiçao e esse metodo insere um novo elemento nessa posição. La vai:
ListaLig::insere_posic()
{//Insersao em uma posiçao qualquer da lista
    if(tamanho(qtd)==o){exit(1);};//******REVER variavel QTD
    no*novo = new no;
    no*varre;
    no*aux;
    while(varre!=Pos)
    {//****REVER variavel POS
        aux=varre;
        varre=varre->prox;
    };
    novo->prox = aux->prox;
    aux->prox = novo;
    novo->info = valor; //REVER********
    };
Ta fácil de encontrar minhas duvidas ai, estão nos comentarios hehehe.

Primeiro: na classe existe um atributo inteiro chamado qtd, que armazena o tamanho da lista, inicializada pelo construtor como 0. Posso simplesmente modifica la dentro dos metodos assim? já fiz um metodo "quantidade" que foi chamado nesse ai na linha 2, dentro do if, ta certo o jeito que a chamei? tamanho(qtd)?

Pela declaração da função, ta errado, mas você pode usar um simples qtd, da mesma forma como você usa o referencia.

Segundo: variavel pos. Essa é a variavel que armazena o que o usuario inseriu, a posiçao que ele deseja. Por conceitos de reusabilidade do c++ não vou colocar "strtoint(edit1)" (no caso do builder) etc e tal, como faço então pra esse metodo "capturar" essa variavel?

Você poderia receber o Pos como parâmetro, e fora da classe insrerir elementos onde e como bem entender... ex: suaLista->insere_posic(posicao);

Terceiro: informaçao contida nesse novo elemento da lista. Essa pergunta é semelhante a segunda desse metodo (listada acima), como devo capturar esse valor? como podem ver atribui um valor "valor" a ela, mas nem declarei nem nd. help!!

Por parâmetros.

mar_tchello · 24 de março de 2007

Opa!

Sexta pela tarde fui conversar com um professor que me tirou a maioria das duvidas.

estava fazendo umas coisas beem erradas hehe, mas já estou acertando.

Ajudou me muito na parte da remoçao no final, gostei da sua sugestao, muito obrigado.

To mexendo no codigo aqui, jaja almoço (sim, as 17 horas) e quando voltar posto detalhadamente.

valeu!! (caso ainda não resolvido heehhe)

mar_tchello · 24 de março de 2007

Opa, como dito acima tive as duvidas sanadas, muito obrigado ^^

Agora tragoa publico (chique eim?) mais uma leva de perguntas sobre essa lista ligada

ps: o Arquivo header permanece semelhante ao postado, com uma correçaozinha.

Duvidas:

#1

Bom, to tendo problema com alguns tratamentos de exceção.

Por exemplo:

    
       string ListaLig::remove_final(){
        if(referencia==NULL){exit(1);}; //Tratamento de exceção
        no *varre;                     
        no *aux;
        varre = referencia;   
        while(varre->prox!=NULL){
                aux = varre;
                varre = varre->prox;};
        aux->prox = NULL;
        delete varre; 
        qtd--; };

Note onde ha o comentario "Tratamento de exceção" existe um exit(1) que, pelo que imaginei, apenas seria acionado caso a lista fosse vazia.

porém, entretanto, mas, isso não acontece, ele é sempre acionado.

Como posso fazer esse tratamento de exceção? quero não ter que usar o exit(1), ele acabaria matando meu programa impiedosamente, tadinho.

Alguma sugestao?

---------------------------------------------------

#2

Outro problema que to tendo é com o return.

Veja esse metodo:


     string ListaLig::primeiro(){
        if(referencia!=NULL){  //REVISAR tratamento de exceção, retorna os dois valores.
          return(0);}
        else{
          return(referencia->info);}
    };

Ele funcionou bem, quase perfeitamente, mas note o comentario que coloquei. Isso mesmo, ele esta retornando o 0 e a informaçao =(

Sugestoes?

---------------------------------------------------

#3

Nesse aqui deve ser simples e eu to comendo bolo a toa.

Esse metodo (find) procura por um determinado elemento na lista e retorna sua posiçao.

Ele esta funcionando bem, testei o, porém não pensei em algo muito eficiente que trate caso o elemento solicitado não exista na lista.

Eu poderia implementar esse tratamento no main, mas não seria melhor coloca lo no proprio metodo tornando minha classe mais eficiente?(esse conceito ta certo?)

La vai o codigo:


    int ListaLig::find(string El){
       // if(referencia==NULL){return(0);}; //Tratamento de exceção
        no *varre;                      //Rever tratamento caso o elemento não exista na lista  
        varre = referencia;
        int count=1;
        while(varre->info!=El){
                varre = varre->prox; count++; };
        return(count);
    };

-----------------------------------------------------

#4 (ultimo, prometo =X)

Esse é simples.

Fiz um metodo imprime (corretamente declarado no header) mas ele ta entrando num loop infinito e ta imprimindo quinem um louco.

codigo:


    string ListaLig::imprime(){    //REVER, cai num loop infinito
           no *varre;
           varre = referencia;
           while(varre!= NULL){
                  cout<<(varre->info);}              
                  varre = varre->prox;
                };

---------------------------------------------------------------

Bom, por enquanto é só galera, perdoem me por não ter sido estão breve e principalmente por ter feito perguntas estão <strike>estupidas</strike> triviais no primeiro post

Se quiser hospedo o projeto e coloco o link aqui pra facilitar.

Muito obrigado

EduardoS · 25 de março de 2007

Não vou quotar toda a mensagem para não deixar a resposta muito longa,

1) Por que não retornar não-zero para quando deletar o ultimo e zero para quando não deletar (no caso da referencia ser NULL).

2) O if-else não esta invertido?

3.1) As classes que procuram por alguma coisa em uma coleção geralmente retornam -1 ou 0 quando não encontram (-1 se o primeiro item for o 0 e 0 se o primeiro for o 1), você poderia fazer o mesmo.

3.2) Em relação ao conceito, pelos conceitos da OOP o tratamento deveria ser feito na classe já que essa ação esta tão ligada a lista quanto um "remove_final()", sobre as vantagens, caso algum dia você resolva usar uma lista encadeada em outra lugar e precisar dessa função ela já estara la, fácil de achar.

Ah se a "eficiência" que você falou for eficiente de processamento, sim, fazer esse tratamento na função tambem é mais eficiente.

4) O "}" do while ta na linha errada

ps) Não comentei nada sobre o porque de sempre cair no tratamento de exceção do item 1 porque pelo código disponível não da para saber.

mar_tchello · 25 de março de 2007

2) O if-else não esta invertido?

Nossa, realmente.

3.1) As classes que procuram por alguma coisa em uma coleção geralmente retornam -1 ou 0 quando não encontram (-1 se o primeiro item for o 0 e 0 se o primeiro for o 1), você poderia fazer o mesmo.

Hmm, acho que entendi o que você quis dizer, tentarei algo aqui e postarei de volta

4) O "}" do while ta na linha errada

Eu sou uma mula. uhahuauha:-)hua

Juro, juro mesmo que li esse trexo trocentas vezes e não vi isso, você talvez deva ter passado por isso algumas vezes, entende ehehe

ps) Não comentei nada sobre o porque de sempre cair no tratamento de exceção do item 1 porque pelo código disponível não da para saber.

Como funcionam aqueles esquema de tratamento de exceção com trow (é assim?) etc?

valeu rapaz, já ajudou a solucionar mais uns metodos!!

Abraços!

EduardoS · 25 de março de 2007

Sobre o thorw, isso funciona:


void teste()
{
    throw "teste";
}
int _tmain(int argc, _TCHAR* argv[])
{
    try
    {
        teste();
    }
    catch(char * excp)
    {
        printf(excp);
    }
    return 0;
}