Lista duplamente encadeada

joaovirgili
(usa Ubuntu)

Enviado em 23/03/2016 - 15:35h

Boa tarde, sou novo no fórum, se estiver fazendo algo fora das normas me alertem, por favor.
Estou aprendendo linguagem C, atualmente implementando listas duplamente encadeadas (ja aprendi pilha dinamica).
Eis o meu código:

#include <stdio.h>

#include <stdlib.h>

#include <stdbool.h>



struct Tipo_Lista {

	int Item;

	struct Tipo_Lista *Prox;

	struct Tipo_Lista *Ant;

};



int Tamanho_Lista=0;

struct Tipo_Lista *Primeiro, *Ultimo;



void Inicia ();

void Insere (int x);

void Imprime ();



int main (void) {

	Insere (2);

	Imprime();

	return 0;

}

#include <stdio.h>

#include <stdlib.h>

#include <stdbool.h>



struct Tipo_Lista {

	int Item;

	struct Tipo_Lista *Prox;

	struct Tipo_Lista *Ant;

};



int Tamanho_Lista=0;

struct Tipo_Lista *Primeiro, *Ultimo;



void Inicia ();

void Insere (int x);

void Imprime ();



int main (void) {

	Insere (2);

	Imprime();

	return 0;

}



void Inicia () {

	struct Tipo_Lista *aux;

	aux = (struct Tipo_Lista*)malloc(sizeof(struct Tipo_Lista));

	Primeiro = aux;

	Ultimo = Primeiro;

	Primeiro->Ant = NULL;

}



void Insere (int x) {

	struct Tipo_Lista *aux;

	aux = (struct Tipo_Lista*)malloc(sizeof(struct Tipo_Lista));

	aux->Item = x;

	aux->Ant = Ultimo;

	Ultimo = aux;

	Ultimo->Prox = NULL;

}



void Imprime () {

	struct Tipo_Lista *aux;

	aux = (struct Tipo_Lista*)malloc(sizeof(struct Tipo_Lista));

	aux = Primeiro;

	printf("\n");

	while (aux->Prox != NULL) {

		printf("%d", aux->Item);

		aux = aux->Prox;

	}

}



void Inicia () {

	struct Tipo_Lista *aux;

	aux = (struct Tipo_Lista*)malloc(sizeof(struct Tipo_Lista));

	Primeiro = aux;

	Ultimo = Primeiro;

	Primeiro->Ant = NULL;

}



void Insere (int x) {

	struct Tipo_Lista *aux;

	aux = (struct Tipo_Lista*)malloc(sizeof(struct Tipo_Lista));

	aux->Item = x;

	aux->Ant = Ultimo;

	Ultimo = aux;   //erro aqui

	Ultimo->Prox = NULL;

}



void Imprime () {

	struct Tipo_Lista *aux;

	aux = (struct Tipo_Lista*)malloc(sizeof(struct Tipo_Lista));

	aux = Primeiro;

	printf("\n");

	while (aux->Prox != NULL) {

		printf("%d", aux->Item);

		aux = aux->Prox;

	}

} 

Está dando erro segment fault, na linha "Ultimo = aux" dentro da função Insere quando tento fazer o teste. Não entendo o porquê desse erro, alguem pode me ajudar?
A meu ver é assim: Quando insiro um novo elemento na lista, tenho o ponteiro Prox (apontando para o proximo elemento, nesse caso tem q ser nulo pois será o ultimo) e o ponteiro Ant (apontando para o elemento anterior). Faço deste novo elemento um auxiliador, atribuo o X ao aux->Item, o ultimo elemento ao aux->Ant. Assim, ele ja está inserido na lista. Após isso, faço que Ultimo = aux, para o novo elemento ser o ultimo. Finalizo com Ultimo->Prox = NULL.

paulo1205
(usa Ubuntu)

Enviado em 23/03/2016 - 18:20h

A linha que você aponta como sendo aquela em que o erro ocorre não deveria dar erro de modo nenhum, pois trata-se de uma manipulação trivial de uma variável global do programa. Como você sabe que o erro está ali?

Se você estiver usando um debugger, tome cuidado com otimizações do compilador, pois às vezes elas confundem a correspondência entre o código fonte e o compilado (por causa de técnicas de otimização que podem mudar a ordem de execução de instruções, otimizar transferência de valores de retorno, expandir laços de repetição, entre outras técnicas). Se for o caso, desligue otimizações na hora de compilar (no GCC, usa-se a opção -O0).

Quanto ao código, uma coisa que eu achei estranha é que em nenhum momento você garante a lista vazia (tanto o primeiro quanto o último apontando para NULL). Sua função Inicia(), contrariamente ao que o nome indica, cria uma lista já com um elemento.

Aliás, reparei agora você não chama Inicia() em momento nenhum. Assim sendo, o valor de Primeiro nunca é inicializado (i.e., como é uma variável global, ele permanece com o valor NULL durante todo o programa). Quem indica onde começa sua lista?

Na hora de imprimir, para que você aloca memória, para logo em seguida apagar a referência a essa memória recém-alocada (vazamento de memória) com o valor sempre nulo de Primeiro? Poucas linhas abaixo, você tenta acesso a aux->Prox num momento em que aux é nulo, logo a tentativa de chegar ao campo Prox necessariamente será inválida.


Tenho algumas sugestões para você:

1) Faça uma função Inicia() que crie uma lista completamente vazia (Primeiro e Ultimo apontando para nulo).

2) Não faz sentido ter uma lista duplamente encadeada se você só a percorre num sentido (tanto na hora de inserir quanto na de consultar/imprimir). Portanto, possivelmente você deveria dividir sua operação de inclusão de novos elementos em duas, para permitir, respectivamente, inclusão antes ou depois de um determinado nó (casos particulares disso são inclusão no início e no fim da lista).

3) Não deve haver nenhum tipo de alocação de memória nas funções de consulta. Você simplesmente percorre numa determinada direção (que pode ser para frente ou para trás, já que a lista é duplamente encadeada) até encontrar um nó que não tenha sucessor (ou antecessor).

joaovirgili
(usa Ubuntu)

Enviado em 23/03/2016 - 18:49h

Primeiramente obrigado por analisar profundamente meu código, quando voltar pra casa vou ler atentamente. Mas antes disso só deixar umas observações. É, estava usando debugger sim (eu acho), pq da maneira normal estava dando falha de segmento, algo assim. Não conheço muito bem sobre Linux, sou novo, sempre uso gcc nome.c -o nome.
O código não está completo, só estava fazendo função por função e testando elas. Realmente esqueci de chamar a função Incia(); , pode ser esse o problema. Vou testar e levar em conta o que você disse, depois trago mais informações !
Obrigado.

joaovirgili
(usa Ubuntu)

Enviado em 23/03/2016 - 22:58h

Acho que um dos principais problemas de me fazer implementar este código foi não ter estudado antes a lista encadeada, agora que estudei, vejo meus erros mais claramente. Porém tenho umas dúvidas sobre a diferença entre encadeada e duplamente encada. Quais as vantagens e desvantagens? Dei uma breve pesquisada mas não encontrei/entendi muito. O fato de eu poder percorrer ambos os sentidos?
Uma lista duplamente encadeada então se comporta como Fila e Pilha ao mesmo tempo?

paulo1205
(usa Ubuntu)

Enviado em 24/03/2016 - 01:32h

Sim, a principal vantagem do duplo encadeamento é poder percorrer a lista nos dois sentidos.

A principal diferença entre pilha, fila e lista está na característica de onde a operações de inserção, remoção e consulta podem ser realizadas. Uma pilha pura só realiza operações no topo, e por isso geralmente só se guarda referência a esse topo. Uma fila tem de ter duas referências, porque ela só realiza inserções no final, e todas as remoções ou consultas se dão no início. Já a lista permite realizar consultas, inserções e remoções em qualquer posição, desde que você a percorra até chegar à posição desejada.

Por sua flexibilidade, uma lista pode ser usada como forma de implementar pilhas e filas, bastando limitar as operações utilizadas àquelas que estão definidas para pilhas e filas.

joaovirgili
(usa Ubuntu)

Enviado em 24/03/2016 - 03:46h

Entendi! Muito obrigado, suas colocações me ajudaram bastante.
Terminei o código de Lista Duplamente Encadeado depois de um bom tempinho (:
Segue meu código, acredito que esteja correto, todos os testes deram certo.


obs: a main está assim pois estáva testando as funções.
duvida: devo sempre desalocar as memorias reservadas com malloc??

RamonSales
(usa Ubuntu)

Enviado em 24/03/2016 - 07:20h

#include <stdio.h>
#include <cstdlib>

struct Tipo_Lista {

int Item;
struct Tipo_Lista *Prox;
struct Tipo_Lista *Ant;
struct Tipo_Lista *inicio;

};

int Tamanho_Lista=0;
struct Tipo_Lista *Lista;

bool Lista_Vazia(Tipo_Lista*); // aqui temos uma função pra conferir quando a lista estiver vazia
void Inicia();
void Insere_fim(int x);
void Imprime ();

int main () {

Inicia();
Insere_fim(10);
Insere_fim(20);
Insere_fim(30);
Imprime();
return 0;
}

void Inicia () {
Lista = new Tipo_Lista;
Lista->inicio = NULL;
}

bool Lista_Vazia(Tipo_Lista *x){
return x->inicio == NULL;
}

void Insere_fim (int x) {
struct Tipo_Lista *aux,*aux2;
aux = new Tipo_Lista;
aux2 = Lista->inicio;

aux->Item = x;
aux->Prox = NULL;

if(!Lista_Vazia(Lista)){ // olha só caso a lista esteja vazia

while(aux2->Prox) // esse while vai andar a lista até o fim
aux2 = aux2->Prox;
aux->Ant = aux2->Prox; // e aqui aponta o ponteiro anterior pro fim da Lista
aux2->Prox = aux; // e aqui encaixa a nova lista no fim

}else{

aux->Ant = Lista->inicio;
Lista->inicio = aux;

}

}

void Imprime () {
struct Tipo_Lista *aux;
aux = (struct Tipo_Lista*)malloc(sizeof(struct Tipo_Lista));
aux = Lista->inicio;
printf("\n");
while (aux) {
printf("%d ", aux->Item);
aux = aux->Prox;
}
}

Vamos por partes, não precisa usar "malloc" nem "sizeof", basta o operador new, dei uma editada no seu código, mas não fiz todo, temos que trabalhar com três hipóteses:

1- Se a pessoa quiser inserir no fim da lista
2- Inicio da lista
2- Numa posição determinada

coloquei só a opção de inserir no fim da lista você completa o resto das funções

RamonSales
(usa Ubuntu)

Enviado em 24/03/2016 - 08:36h

Ah! faltou também definir o inicio da lista

paulo1205
(usa Ubuntu)

Enviado em 24/03/2016 - 08:41h

SalesRamon, você precisa pegar o jeito desta comunidade.

Tanto pedir quanto dar respostas prontas são considerados comportamentos inadequados pela maioria dos membros. Em suas postagens recentes, você já incorreu em ambos os desvios.

Além disso, nas respostas que você dá, você geralmente fala coisas errôneas e descabidas e entrega código de qualidade questionável. Neste tópico mesmo, a pergunta original foi específica em dizer que se trata de linguagem C, mas você, por algo que parece ser uma ânsia de aparecer, nem sequer percebeu isso, e deu uma resposta em C++ que provavelmente não será útil para o autor da pergunta (ao menos enquanto ele estiver estudando especificamente C). E no código que você mostrou, você manteve erros da postagem original, misturou inconsistentemente C com C++, e ainda introduziu um membro absolutamente inútil Inicio em todos os nós da lista.

Não estou sugerindo que você deixe de participar deste fórum. Muito pelo contrário: meu desejo sincero é que você melhore a qualidade de suas participações, em benefício de todos, a começar por você mesmo.

paulo1205
(usa Ubuntu)

Enviado em 24/03/2016 - 09:39h

Se me permitir, gostaria de fazer alguns comentários.

Muitas de suas funções devolvem valores booleanos para indicar sucesso ou falha de execução. Porém, elas também exibem mensagens de diagnóstico e de erro. Num programa de teste, isso até é aceitável. Para cenários de uso real, a sinalização por meio do valor de retorno é suficiente, e o usuário das funções é que deve decidir, com base no valor retornado, de quer ou não imprimir coisas na saída.

Além disso, quando você imprimir mensagens desse tipo, separe-a da saída padrão do texto normal do programa. Usualmente, o C tem uma saída padrão (stdout, que é a saída usada por printf(), puts() e putchar()), e uma saída separada para erros (stderr, que pode ser passada como argumento para fprintf(), fputs(), fputc(), fwrite() etc.). Acostume-se a direcionar suas mensagens de erros e diagnósticos para stderr.

Notou que, do jeito como está, Primeiro nunca aponta realmente para o primeiro nó, mas que quem o faz realmente é Primeiro->Prox? Pergunto-lhe o motivo de você ter feito assim, pois acaba sendo um desperdício. Para mim, faria mais sentido que se Primeiro!=NULL, então Primeiro->Item deve ter um valor válido.

Eu sei que se você fizer essa mudança terá de mexer em praticamente todas as funções do programa (e talvez até tenha de recorrer ao uso de ponteiro para ponteiro). Mesmo assim, incentivo-o a pensar a respeito e a fazer as devidas mudanças agora, enquanto você está aprendendo, para que não aprenda erroneamente e depois tenha de reaprender.

Eu sei que seu programa é introdutório, e por isso mesmo ele implementa uma única lista, usando variáveis globais fixas para implementar nós com significados especiais. Experimente, no entanto, fazer o exercício de imaginar um meio de ter várias listas no mesmo programa. Dica: em vez de variáveis globais dentro de cada função, imagine passar como argumento qual lista você quer manipular.



Sempre que uma região de memória obtida por alocação dinâmica estiver prestes a ficar inacessível, porque não haverá mais nenhum ponteiro do programa apontando para ela, essa região de memória deve ser liberada, sim. Em particular, sua função de remoção deve chamar free() sobre a memória que será liberada e devolvida ao sistema (ao contrário de Java, por exemplo, atribuir nulo não é suficiente para liberar memória).

O único caso em que a liberação de memória seria opcional é quando um programa estiver prestes a ser encerrado, porque a maioria dos sistemas operacionais consegue reaver todos os recursos do programa de uma vez só. Mesmo assim, a liberação explícita dentro do programa continua sendo recomendável, pois é possível que exista um sistema operacional ou ambiente de execução que compartilhe a alocação de objetos entre vários programas diferentes, e em que o término de um programa não garanta a liberação de seus recursos para uso pelos demais. O próprio MS-DOS (e assemelhados, e que ainda são eventualmente usados hoje em dia) é um exemplo de sistema em isso pode ocorrer em algumas situações.

joaovirgili
(usa Ubuntu)

Enviado em 25/03/2016 - 00:35h

É, eu coloco os printfs dentro das funções booleanas apenas para testes, a depender do usuário eu edito. Tem problema utilizar uma função booleana com printf? Eu faço função booleana pq prefiro trabalhar com ela.

Não entendi muito bem o q vc quis dizer nesse segundo paragrafo, foi mal :/

É pq pelo que entendi, Primeiro não é o primeiro item da lista, ela apenas mostra qual é o primeiro item, com Primeiro->Prox apontado para ele. Se tiver 3 itens na lista, é como se tivessem 4 declarados, onde 1 declarado (Primeiro) não está na lista, está apenas mostrando qual é o primeiro item da lista. Aprendi por este video : https://www.youtube.com/watch?v=fzT3g4T9TiI

Então devo liberar a memoria no final de tds as funções? Não né? Porque no caso da Insere , se eu liberar, perco os valores armazenados na lista. Devo então no final do programa liberar ou apenas liberar em funções como a do auxiliador, em q eu armazeno informações e depois não usa mais.

Outra dúvida, qual o editor de texto do linux mais recomenda? estou usando o notepadd, que é o notepad++ do windows mas no linux. Como disse, sou novo no linux, sempre usei o linux e alguma ide.. Estou me adaptando a ele por causa da faculdade.

paulo1205
(usa Ubuntu)

Enviado em 25/03/2016 - 11:22h

Se você não vai usar o valor retornado pela função, poderia simplesmente não retornar nada (tipo de retorno void).



Sobre sinalizar erros na saída de erros?

Em termos práticos, em vez de você usar o mesmo canal para mensagens normais e mensagens de erro, você deveria usar o canal separado para erros oferecido pelo C. Compare as duas formas.

/* Misturando mensagens normais com mensagens de erro. */

printf("Esta é uma mensagem normal.\n");

printf("Esta é uma mensagem de erro.\n"); 

/* Separando mensagens de erro das normais. */

printf("Esta é uma mensagem normal.\n");

fprintf(stderr, "Esta é uma mensagem de erro.\n"); 

Normalmente, tanto a saída padrão quanto a saída de erros são associadas ao terminal, mas você pode mudar isso por meio de redirecionamentos, podendo redirecionar apenas um dos canais, ou redirecionar ambos para destinos separados.

Vai ser extremamente útil para você agora? Possivelmente não para um programa pequeno como o seu, que tem pequenas chances de dar erro. De todo modo, trata-se de uma boa prática, usada universalmente. No mínimo, seria bom adequar-se a ela só para estar de acordo com o que a comunidade de programadores em C esperaria encontrar. Contudo, se você seguir a carreira de desenvolvimento de software, verá, mais cedo ou mais tarde, que é muito útil, durante a depuração de programas complexos, separar mensagens de naturezas diferentes.



Não consegui abrir o vídeo (meu computador morreu -- está aberto aqui do meu lado, com eu tentando salvar os dados, mas até o RAID1 que eu tinha parece que foi detonado na pane elétrica --, e o notebook que literalmente tive de desengavetar não conseguiu abrir o YouTube porque está com plugins muito velhos). Mas nem precisa.

Se você usa Primeiro->Prox para aceder ao primeiro elemento, não deveria também, por simetria, usar Ultimo->Ant para designar o último, especialmente numa lista duplamente encadeada? Só que você não faz isso, e as coisas funcionam. Isso necessariamente implica, por simetria, que pode também usar Primeiro diretamente para aceder ao primeiro elemento de fato.

Em tempo: quando eu estudei listas encadeadas na faculdade (e não era faculdade varejão-do-ensino, não; eu estudei na UFRJ), fizeram a mesma coisa que o cara do YouTube cujo vídeo você viu. E eu sempre achei um desperdício um nó alocado e sem uso, a não ser pelo ponteiro. Numa estrutura simples (como a sua, cujo dado é apenas um valor inteiro), isso pode ser pouco relevante, e menos relevante ainda quando se está num sistema com vários gigabytes de memória. Mas a coisa não é bem assim quando o dado é complexo e volumoso, ou quando se está num sistema de pequeno porte, como hardware embarcado usando microcontroladores com quantidade de memória que às vezes é menor do que 1kiB.

Mais tarde eu entendi, quando tentei por conta própria implementar uma lista sem o desperdício, que fazer do modo como foi mostrado na faculdade ajudava a simplificar algumas operações. Na verdade, talvez fosse o único meio de fazer lá na faculdade, usando aquela linguagem fedorenta chamada Pascal (que era o que se ensinava nas faculdades brasileiras em 1991 -- e era Pascal ISO, nem era o Turbo Pascal, que era um pouquinho mais amigável). Mas, em C, certamente dá para fazer melhor.



Como eu disse antes, você deve liberar memória que esteja prestes a ficar completamente inacessível, por não haver mais nenhum ponteiro apontando para elas. Não é o caso de sua função de inserção, pois mesmo quando a função acaba e, consequentemente, aux deixa de existir, você já fez com que um dos ponteiros da lista passasse a apontar para a região alocada.

Na verdade, eu até frisei que o lugar mais provável para fazer a liberação seria na função que remove itens da lista.



Eu não gosto de recomendar editores porque passa por uma questão de gosto e de cultura. O que eu posso fazer sem receio é dizer qual o editor que eu mais uso no dia-a-dia e por quê, e também fazer alguns comentários acerca dessa escolha.

Minha principal ferramenta de edição de texto, incluindo programas de pequeno porte (que constituem a maioria dos programa que eu faço, pois eu não sou desenvolvedor, mas sim um profissional de infraestrutura que faz programas que automatizem ou simplifiquem algumas tarefas, é o vim. Algumas razões pelas quais ele é o que eu mais uso são as seguintes:

- antes de conhecer o vim, eu já usava o vi ou nvi havia alguns anos, então já estava acostumado com o jeito de trabalhar (para você ter uma ideia, eu não uso as teclas de setas para navegar pelo texto, mas as mesmas teclas usadas nos velhos terminais seriais de texto puro, através dos quais eu comecei a mexer com UNIX);

- eu gosto de usar expressões regulares em operações de busca e substituição;

- muito frequentemente eu edito textos dentro de uma sessão remota, estabelecida com ssh, e boa parte dessas máquinas não tem X11 instalado, de modo que não dá exportar display ou permitir uso de VNC, a fim de usar um editor gráfico (além do quê, mesmo se fosse possível, seria mais lento);

- eu gosto de poder usar filtros de texto por meio de comandos externos, sem ter de sair do editor ou usar copy-and-paste de/para outro documento;

- quando quero alguma coisa além do que o vi original oferecia, normalmente os recursos do vim são suficientes para as coisas de pequeno porte com que lido (por exemplo, syntax highlighting).

Por outro lado, eu estou longe de ser muito proficiente com o vim. Por exemplo, eu sei que existe um modo de edição em bloco visual, mas eu nunca usei. Suponho que existam também recursos de refactoring[, mas como eu só preciso desse tipo de coisa muito raramente (ainda mais com meus programas pequenos), nunca procurei conhecê-los.

Ao mesmo tempo, como programar não é a alma do meu trabalho diário, nunca tive interesse em estudar um editor ou ambiente que pudesse maximizar meu desempenho como programador.

Nas raras vezes em que programei para ambiente gráfico, gostei muito de usar o QtCreator. Seu editor tem um bocado de recursos, incluindo refactoring e até algum grau de sincronização entre arquivos correlatos. Ele tem até um modo básico de compatibilidade com vim. Mesmo assim, senti falta de coisas que faço no dia-a-dia com o vim, e que não têm correspondente imediato.