Resumo_ListaEncadeada

Esta é uma pré-visualização de arquivo. Entre para ver o arquivo original

Resumo Lista Encadeada:
************************************************************************************
OBS: Essa matéria cai na P2 e P3!
************************************************************************************
- Definição:
Lista Encadeada é basicamente um conjunto de elementos em sequência, sendo que cada elemento além de armazenar uma (ou mais de uma) informação, também armazena >> obrigatoriamente << um ponteiro para o próximo elemento da lista!
Daqui em diante vamos precisar alcançar um nível maior de abstração pra entender com facilidade os novos conteúdos. Mas pra facilitar, sempre que o assunto envolver lista encadeada, tenta imaginar como um conjunto de retângulos que são chamados de >Nós< conectados por um cabo ou setinha! (ponteiro que "aponta" para o próximo elemento)
Imagem de exemplo: (Sempre visualize a lista dessa forma!)
http://2.bp.blogspot.com/-m9GPnybVvfc/UWRKByx4xoI/AAAAAAAAA6o/oaJezKhXWzs/s320/lista.jpg
OBS: Nessa imagem, id é a informação e *prox é o ponteiro que "aponta" para o próximo elemento da lista! Lembrando que o ponteiro para o último elemento da lista é >SEMPRE< NULL!
-------------------------------------//--------------------------------------------
- Vantagem: 
É uma nova forma de armazenar um conjunto de dados, assim como em vetores, mas com a vantagem de >>NÃO<< precisar definir um tamanho máximo de elementos! Ou seja, podemos inserir ou remover elementos da lista sem se preocupar com nada! 
OBS: >>NÃO<< faz sentido usar recursão em lista encadeada! Pois dependendo do tamanho da lista, existe um alto risco de estourar a Pilha. (WHAT!? Pilha!? :O )
Pilha é como se fosse um pedaço da memória do sistema que é reservado e vai sendo utilizado a cada chamada de função, assim que a função encerra, a memória é devolvida, o problema é que a recursão primeiro faz todas as chamadas de uma vez e só começa a devolver a memória no fim da lista! 
Imagina se for uma lista quilométrica, quase infinita, existe um risco bem alto da recursão consumir bem mais memória do que a Pilha possui! E Quando isso acontece, dizemos que a "Pilha estourou".
Então mesmo se o seu professor passar algum exercício com recursão em lista, as chances de ser cobrado em prova são quase nulas! E sim, não precisar lidar com a temida recursão é uma das vantagens! :D
OBS: Pilha é uma das matérias da P3 que só será explicado com detalhes no "Resumo_Pilha"! :)
- Desvantagem: 
>>NÃO<< existe ordenação! A >>ÚNICA<< forma de percorrer uma lista é de forma LINEAR! Então sim, já era busca binária. 
OBS: Bom, dependendo do ponto de vista isso pode ser uma vantagem também. Haha
------------------------------------//---------------------------------------------
- Protótipo da struct de uma lista encadeada: 
typedef struct no{
 int info;
 struct no *prox;
}No;
OBS: A base do protótipo de uma lista é >>SEMPRE<< esse! O único detalhe que pode mudar é o nome da struct e a quantidade das informações que ela armazena!
***********************************************************************************
Regra Importante: (Essencial pra todas as matérias da P3 também!)
Um erro comum é fazer isso aqui no protótipo: >> No *prox; <<
Cuidado! Isso é um erro extra fatal! Pois só podemos usar o typedef >>a partir<< do momento que ele é definido em diante!!!
OBS: A >> ÚNICA << exceção é numa matéria da P3 chamada TAD!
E pra piorar mais ainda, o Visual Studio simplesmente não avisa esse erro! (Pelo menos uma vantagem da prova ser escrita né x.x) 
********************************************************************************** 
Operações básicas de toda Lista:
- Como criar uma lista? 
No *lst = NULL;
OBS: Essa é a forma que eu recomendo e é a mais simples de se criar uma lista. Primeiro declara uma variável da struct e é só atribuir NULL. 
Alguns enunciados podem disponibilizar uma função que cria uma lista: 
No * lst_cria(){
 return NULL;
}
No *lst = lst_cria();
OBS: Chamar uma função só pra retonar NULL, algo que você pode simplesmente colocar manualmente...Sem comentários né D:
Lembra que toda lista termina em NULL? Mas no momento da criação colocamos NULL, então qual é a lógica? 
Sim, é exatamente isso! Apesar da gente visualizar cada elemento (Nó da lista) seguido um do outro e terminando em NULL. Na verdade aquela é a ordem de acesso aos elementos da lista! A lista é criada exatamente na ordem inversa! Começando pelo NULL e o último elemento que inserimos na lista será o começo da lista!
OBS: >>TODA<< lista é representada pelo ponteiro para o seu começo! (Primeiro elemento) Lembrando que se caso inserirmos mais um Nó (Novo elemento), esse será o novo começo da lista! Ou seja, o ponteiro da lista deve ser sempre atualizado pra representar >>SEMPRE<< o começo da lista!
-----------------------------------//---------------------------------------------
- Como inserir um novo elemento na lista?
A forma mais tranquila de inserir um novo elemento é sempre no começo da lista!
typedef struct no{
 int info;
 struct no *prox;
}No;
No * insere (No *lst, int info){
 No *novo = (No*) malloc (sizeof(No));
 if(!novo){
 puts("Falha na insercao!");
 return lst;
 }
 novo->info = info;
 novo->prox = lst;
 return novo;
}
int main (void){
 No *lst = NULL; //Criando da lista
 int info = 10;
 lst = insere (lst, info); 
}
A função insere precisa retornar um novo Nó da lista, então o tipo de retorno dela é No * (De acordo com o nome da sua struct lista!)
Sempre recebe como parâmetro o ponteiro para o começo da lista e a informação que deve ser armazenada. (Dependendo do enunciado, pode ser o usuário que digite a informação na função!)
Primeiro passo é alocar dinamicamente um novo elemento, atribuir a informação no campo novo->info. Nessa parte, imagina um retângulo solto que não faz parte da lista ainda, por isso, precisamos "conectar" ele na lista usando o ponteiro *prox!
OBS: Se caso der erro na alocação, devemos sempre retornar a lista intacta!!! Imagina se temos uma lista com uns 10 elementos, se um deles falha, não faz sentido nenhum destruir a lista inteira!
novo->prox = lst; 
Com essa atribuição, estamos dizendo que o elemento que vem >>DEPOIS<< do que a gente acabou de criar (*novo) é justamente o começo antigo da lista! E com isso, conseguimos "conectar" o novo elemento com a lista. 
Mas peraí, se tem um elemento que vem antes do começo da lista, esse >>NÃO<< é mais o começo! Lembra que sempre precisamos atualizar o ponteiro pro começo da lista? :) 
lst = insere (lst, info);
Nesse trecho da main, estamos ao mesmo tempo criando um elemento novo (Através da fumção) e atualizando o ponteiro do começo da lista!
Então é justamente por isso que é só retornar o novo elemento na função insere que por causa desse trecho, ele será o novo começo da lista! 
Outra forma pra facilitar o entendimento: 
novo->info = info;
novo->prox = lst;
lst = novo;
return lst;
>lst< é o ponteiro do começo da lista. Nessa atribuição lst = novo, estamos dizendo que a lista começa no novo elemento! E logo em seguida retornamos o próprio lst.
OBS: Recomendo retornar novo direto pra facilitar, mas tem casos, como por exemplo remoção, que é mais fácil fazer dessa forma, "ajustando" e usando sempre a variável lst!
-------------------------------------//--------------------------------------------
- Função que testa se uma lista é vazia: 
int ehVazia (No *lst){
 return lst == NULL;
}
Queremos saber se uma lista é vazia ou não. A forma mais prática e simples de conseguir a resposta é retornando (lst == NULL), como se fosse uma condição 'if' que pode ser verdadeiro ou falso. 
***********************************************************************************
Regra Importante: 
Em C e muitas outras linguagens, esse tipo de teste verdadeiro e falso é feito da seguinte
forma. 
return lst == NULL;
O compilador testa essa condição, lst é NULL? como se fosse uma pergunta mesmo! 
Se for verdade: Retorna 1!
Se for falso: Retorna zero!
OBS: Decore isso urgentemente! Essa teoria Vai ser muito útil nas matérias da P3! :)
**********************************************************************************
Outra forma de solução: 
int ehVazia (No *lst){
 if(!lst) return 1;
 return 0;
}
Eu recomendo ir se acostumando com a primeira forma de solução, mas pode usar essa daqui sem problemas, totalmente opcional!
OBS: Se lst == NULL é porque a lista > É < vazia, então retornamos 1. (Ou qualquer número diferente de zero!)
Se não for o caso, é porque a lista >NÃO< é vazia, então retornamos 0!
-------------------------------------//--------------------------------------------
- Como imprimir os dados de uma lista? 
void imprime (No *lst){
 
 while(lst){
 printf("%d\n",lst->info);
 lst = lst->prox;
 }
}
OBS: É só ir andando na lista e imprimindo a informação de cada Nó! Lembrando que >>NÃO<< precisamos de variável auxiliar, podemos usar o próprio 'lst', pois não vamos precisar retornar e nem modificar o começo da lista!
lst = lst->prox; 
Essa é a forma de avançar na lista! >NÃO< precisa se preocupar que o começo da lista será perdido nem nada! O começo da lista está são e salvo lá na main! :D
Pense nesse parâmetro No *lst como uma variável local, exclusiva da função imprime!
Então nesse trecho é o mesmo que dizer: "Avança para o próximo elemento da lista!"
-------------------------------------//--------------------------------------------
- Como fazer buscas numa lista? 
Como em lista não existe nenhum tipo de ordenação, a >>ÚNICA<< busca possível é a Linear!
Por exemplo: Queremos achar o ponteiro do Nó que contém uma certa informação.
No * busca (No *lst, int val){
 
 while(lst){
 if(lst->info == val) 
 return lst;
 lst = lst->prox;
 }
 return NULL;
}
Enquanto a lista >NÃO< estiver vazia, comparamos o valor recebido como parâmetro como o valor do elemento atual, se for igual, retornamos o próprio lst, pois ele representa o ponteiro para o elemento atual, onde achamos o valor! 
E se caso for diferente, continuamos avançando na lista até chegar no fim. E retornamos NULL pra indicar que esse elemento não foi encontrado na lista! (Semelhante a retornar -1 quando não acha algo na busca linear!)
OBS: Tudo depende do que é pedido pra buscar no enunciado, se fosse pra verificar se um elemento existe ou não na lista, o tipo de retorno seria int! Encontrando o elemento retornamos 1, após percorrer tudo se não achar, retornamos zero!
-------------------------------------//--------------------------------------------
- Como se libera uma lista?
OBS: Lembrando que só podemos liberar (Dar free) em variáveis alocadas dinamicamente!!! Mas sem riscos, todos os elementos de qualquer lista são sempre alocados dinamicamente.
Void libera (No *lst){
 No *e;
 while(lst){
 e = lst->prox;
 free(lst);
 lst = e;
 }
}
OBS: A função libera é >>SEMPRE<< assim! Decore urgentemente! =D 
A ideia é a seguinte: Temos uma lista com vários elementos, um seguido do outro. A variável 'lst' representa o endereço do primeiro elemento da lista, ou seja, o começo da lista. Se der free na 'lst' direto vamos liberar o primeiro elemento e perder o resto! 
Por isso precisamos de uma variável auxiliar pra percorrer a lista e ir liberando um elemento por vez! A ideia é: "Salvar" o próximo elemento, liberar o atual e após isso, o próximo passa a ser o atual e isso se repete até a lista estar vazia. 
OBS: Vamos liberando cada elemento enquanto a lista >NÃO< é vazia! while (lst) que é o mesmo que while (lst != NULL) 
OBS2: Sempre temos que liberar a lista >>ANTES<< de encerrar o programa!
---------------------------------------//------------------------------------------
- Como remover > UM < elemento da lista?
 
OBS: Essa é uma das operações mais tensas, recomendo nem piscar! :)
Pra começar, temos um pequeno problema: Queremos remover um elemento da lista, mas e se esse elemento for o primeiro? Não sabemos! Ele pode estar no começo, meio ou no fim! 
Se ele estiver no começo, remover ele não será o problema, mas lembra que precisamos sempre atualizar o ponteiro do começo da lista? Exatamente...o começo da lista vai mudar!
E se o elemento estiver no meio ou no fim? Vamos simplesmente remover ele e deixar a lista "cortada" em duas partes? 
NÃO! Precisamos emendar a lista com um "Band-Aid" pra conectar o elemento >>ANTERIOR<< com o elemento que vem >>DEPOIS<< do que acabamos de remover! :D
No * remove (No *lst, int val){
 No *e = lst;
 No *ant = NULL;
 while(e && e->info != val){
 ant = e;
 e = e->prox;
 }
 if(!ant){
 lst = e->prox;
 free(e);
 }
 else{
 ant->prox = e->prox; 
 free(e);
 }
 return lst;
}
Antes de tudo, precisamos de uma variável auxiliar pra percorrer a lista! Pois em qualquer tipo de remoção sempre precisamos retornar o ponteiro do começo da lista atualizado! (A não ser que o enunciado deixe bem claro que o elemento a ser removido >NÃO< é o primeiro!)
Além disso, precisamos de mais uma variável auxiliar pra ir armazenando o elemento anterior. Pois é a única forma de tratarmos todas as possibilidades! (Elemento no começo, meio ou fim) e por padrão inicializamos ele com NULL! 
while(e && e->info != val){
 ant = e;
 e = e->prox;
} 
Enquanto a lista não é vazia && a informação do elemento atual for diferente do que valor que queremos, avançamos na lista, mas sempre armazenando o elemento anterior! 
if(!ant)
Se após sair do while, o ponteiro 'ant' ainda for NULL quer dizer que o bloco do while > NÃO < foi executado nenhuma vez, ou seja, pra isso acontecer ou é porque a lista estava vazia ou encontramos o elemento que queremos remover no começo da lista!
Nesse caso, dizemos que o novo começo da lista é em e->prox (O elemento que vem logo depois que que vamos remover) e eliminamos ele com a função free.
Mas e se 'ant' >NÃO< for NULL? Quer dizer que executou o bloco do while pelo menos uma vez! Então o elemento que queremos eliminar pode ser o segundo em diante! 
ant->prox = e->prox;
Nessa parte, temos acesso a três elementos. (O anterior, o atual que será removido e o que vem depois do atual) 
Se vamos remover o elemento que está no meio, >ANTES< de tudo, precisamos fazer a ligação do elemento anterior com o próximo do atual! (Sim, esse é o momento propício para aplicar o Band-Aid! :D )
OBS: Precisa usar o Band-Aid sempre antes da remoção! pois lembra que só temos acesso ao próximo elemento através do ponteiro *prox do elemento atual? 
Então se a gente eliminar ele antes, vamos perder acesso ao próximo elemento!
OBS2: Percebe a importância da variával auxiliar pra armazenar o elemento anterior? Através dela sabemos se o elemento que queremos remover está no começo, meio ou fim!
OBS3: O tratamento para o elemento encontrado no meio e no fim são iguais! A única diferença é que estamos fazendo a ligação do elemento anterior com o NULL que representa o final da lista! Mas o procedimento é exatamente o mesmo! 
Se não foi nenhum dos casos anteriores, é porque a lista era vazia ou o elemento não foi encontrado! Em ambos os casos já resolvemos nosso problema e é só retornar a lista!
OBS: A base de >TODA< função remove é sempre assim! Decore urgentemente! :D
------------------------------------//---------------------------------------------
- Como remover > vários < elementos de uma lista? 
OBS: Esse tipo de remoção tem grande chance de ser cobrado na prova! Bem parecido com a remoção simples, só muda uns pequenos detalhes. Então recomendo entender 100% como funciona a remoção simples antes de ler essa parte!
Exemplo:
O enunciado pede pra vc remover >Todos< os elementos da lista em que a informação é igual a zero.
No * removeNulos (No *lst){
 No *e = lst;
 No *ant = NULL;
 while(e){
 if(e->info == 0){
 if(!ant){
 lst = e->prox;
 free(e);
 e = lst;
 }
 else{
 ant->prox = e->prox;
 free(e);
 e = ant->prox;
 }
 }
 else{
 ant = e;
 e = e->prox;
 }
 }
 return lst;
}
A grande diferença aqui é que a maior parte da função está dentro do while!
Enquanto a lista Não estiver vazia, checamos cada elemento pra ver se sua informação é zero:
- Se for zero: Pode ser um elemento do começo da lista. if(!ant) OU um elemento que está no meio/fim da lista! 
OBS: Uma pequena diferença, se o elemento estiver no começo da lista, após remover precisamos colocar o ponteiro auxiliar 'e' de volta na lista! Exatamente no próximo elemento que será verificado! Por isso usamos: e = lst;
Se o elemento estiver no meio/fim fazemos o mesmo esquema pra colocar o ponteiro 'e' de volta na lista, só que dessa vez com e = ant->prox; pois ant->prox é justamente o próximo elemento que queremos verificar! 
- Se NÃO for zero: Não precisamos remover nada e simplesmente avançamos na lista! Sem esquecer de ir salvando o anterior sempre!
ant = e;
e = e->prox;
E após percorrer a lista inteira, retornamos o ponteiro lst que representa o começo da nossa lista! (Independente se houve mudanças no começo da lista ou não, sempre retornamos esse ponteiro no final!)
---------------------------------------//-----------------------------------------
- Como separar uma lista em duas? 
OBS: Esse é outro assunto que é constantemente cobrado em provas!
Exemplo: Temos uma lista de números em ordem crescente (Sem repetições!) e assim que encontrarmos o Nó que armazena o >> valor zero <<, precisamos separar essa lista em duas partes (A primeira só com os números negativos e a segunda só com os positivos)
Considere que a lista possui pelo menos um número negativo e por último precisamos retornar o ponteiro do começo da lista dos números positivos:
OBS: Se o enunciado disse que a lista possui pelo menos um número negativo, não precisamos alterar o começo da lista e nem usar uma variável auxiliar pra andar na lista!
No * separaPositivos (No *lst){
 No *ant = NULL;
 while(lst){
 if(lst->info == 0){
 ant->prox = NULL;
 return lst;
 }
 ant = lst;
 lst = lst->prox;
 }
 return NULL;
}
Imagina que a lista desse exemplo é assim: 
-2 -> -1 -> 0 -> 1 -> 2 -> 3 -> NULL 
Pra procurar o elemento com o zero, basta usar o mesmo esquema de quase todos os exemplos de lista! Enquanto a lista >>NÃO<< estiver vazia, verifica se o Nó possui o valor que queremos achar. 
Mas nesse caso, assim que achar, precisamos separar a lista em dois! Essa é a segunda situação em que precisamos ir >> SEMPRE << armazenando o elemento anterior!
Após achar, zero é o elemento atual e -1 o anterior, só que não podemos simplesmente deixar a primeira lista terminando no -1!
Lembra que pra ser oficialmente uma lista, ela precisa terminar sempre em NULL? :)
ant->prox = NULL;
É só dizer que o próximo elemento do anterior é o NULL pra fechar essa primeira lista!
OBS: Muito cuidado pra não esquecer de terminar toda lista com NULL, pois é um erro tão grave quanto se esquecer do '\0' em strings!
-2 -> -1 -> NULL (Primeira lista , só com os negativos)
0 -> 1 -> 2 -> 3 -> NULL (Segunda lista, só com os positivos)
E pra fechar, retornamos o ponteiro pro começo da lista dos positivos! Que é justamente o elemento atual! (O zero)
return lst; 
E se caso o elemento não for zero ainda, é só ir avançando na lista!
--------------------------------------//-------------------------------------------
 
Bom, isso resume praticamente tudo sobre lista, levando em conta que costumam cobrar mais a parte de remoção e separação nas provas, então recomendo entender e/ou decorar essas duas operações urgentemente! :D