Programar em C/Listas encadeadas: diferenças entre revisões
[edição não verificada] | [edição não verificada] |
Sem resumo de edição |
Sem resumo de edição |
||
Linha 1: | Linha 1: | ||
Listas encadeadas são estruturas de dados lineares e dinâmicas, a grande vantagem que elas possuem em relação ao uso de vetor é o fato de terem tamanho máximo relativamente infinito (o tamanho máximo é o da memória do computador), ao mesmo tempo que podem ter o tamanho mínimo de 1 elemento evitando o desperdício de memória. |
Listas encadeadas são estruturas de dados lineares e dinâmicas, a grande vantagem que elas possuem em relação ao uso de vetor é o fato de terem tamanho máximo relativamente infinito (o tamanho máximo é o da memória do computador), ao mesmo tempo que podem ter o tamanho mínimo de 1 elemento evitando o desperdício de memória. |
||
== |
==Primitivas== |
||
Não existe nem uma normalização quanto as primitivas usadas para a manipulação de uma lista.<br> |
|||
Em-baixo você pode ver uma lista com algumas delas . |
|||
* Colocar o índice sobre o primeiro elemento da lista. |
|||
⚫ | |||
* Colocar o índice sobre o ultimo elemento da lista . |
|||
* Colocar o índice sobre o elemento que segue o elemento atual . |
|||
* Colocar o índice sobre o elemento que precede o elemento atual . |
|||
* Verificar se a lista esta vazia : Se a lista estiver vazia retorna verdadeiro, se não falso. |
|||
* Verificar se é o primeiro elemento : Retorna verdadeiro se o elemento atual é o primeiro, se não falso. |
|||
* Verificar se é o ultimo elemento : Retorna verdadeiro se o elemento atual é o ultimo, se não falso. |
|||
* Verificar o numero de elementos da lista : Retorna o numero de elementos da lista. |
|||
* Adicionar um elemento no inicio : Adicionar um elemento antes do primeiro elemento da lista . |
|||
* Adicionar um elemento no fim : Adicionar um elemento depois do ultimo elemento da lista . |
|||
* Inserção : Inserir um elemento antes do elemento atual . |
|||
* Troca : Trocar o elemento atual . |
|||
* Remoção : Remover o elemento atual . |
|||
==Lista encadeada linear== |
|||
⚫ | |||
Em uma lista encadeada linear o ultimo elemento aponta para NULL . |
|||
<source lang="C"> |
<source lang="C"> |
||
struct No{ |
struct No{ |
||
char * |
char *p_dados; |
||
struct No * |
struct No *p_prox; |
||
}; |
}; |
||
</source> |
</source> |
||
Linha 17: | Linha 36: | ||
<source lang="C"> |
<source lang="C"> |
||
void |
void criar_Lista(struct No **p_Raiz){ |
||
* |
*p_Raiz = NULL; |
||
} |
} |
||
</source> |
</source> |
||
Linha 24: | Linha 43: | ||
==Inserção== |
==Inserção== |
||
Existem |
Existem 3 tipos de inserção em uma lista, pode-se inserir no começo, no final ou entre dois elementos da lista. |
||
===Inserção no início=== |
===Inserção no início=== |
||
<source lang="C"> |
<source lang="C"> |
||
void |
void inserir_No_Inicio(struct No **p_Raiz, char *p_String){ |
||
struct No * |
struct No *p_Novo; |
||
/** Alocação dinâmica da memoria */ |
|||
if((p_Novo = (struct No *) malloc(sizeof(struct No))) == NULL ){ |
|||
pNovo->pString = pString; |
|||
puts( "Falta Memoria\n"); return -1 ; |
|||
} |
|||
p_Novo->p_dados = p_String; |
|||
if(* |
if(*p_Raiz == NULL){ |
||
* |
*p_Raiz = p_Novo; |
||
p_Novo->p_prox = NULL; |
|||
}else{ |
}else{ |
||
p_Novo->p_prox = *p_Raiz; |
|||
* |
*p_Raiz = p_Novo; |
||
} |
} |
||
} |
} |
||
Linha 47: | Linha 70: | ||
<source lang="C"> |
<source lang="C"> |
||
void |
void inserir_No_Fim(struct No **p_Raiz, char *p_String){ |
||
struct No * |
struct No *p_Novo; |
||
if(( p_Novo = (struct No *) malloc(sizeof(struct No))) == NULL ){ |
|||
puts( "Falta Memoria\n"); return -1 ; |
|||
pNovo->pString = pString; |
|||
} |
|||
p_Novo->p_dados = p_String; |
|||
p_Novo->p_prox = NULL; |
|||
if(* |
if(*p_Raiz == NULL) |
||
* |
*p_Raiz = p_Novo; |
||
else{ |
|||
struct No * |
struct No *e_atual; /*@ Elemento atual*/ |
||
e_atual = *p_Raiz; /*@ Primeiro elemento*/ |
|||
while( |
while(e_atual->p_prox != NULL){ |
||
e_atual = e_atual->p_prox; |
|||
} |
} |
||
e_atual->p_prox = p_Novo; |
|||
} |
} |
||
} |
} |
||
Linha 69: | Linha 94: | ||
==Remoção== |
==Remoção== |
||
Assim como na inserção também existem |
Assim como na inserção também existem 3 tipos de remoção, no início, no fim ou entre dois elementos da lista. |
||
===Remoção no início=== |
===Remoção no início=== |
||
<source lang="C"> |
<source lang="C"> |
||
void |
void remover_No_Inicio(struct No **p_Raiz){ |
||
if(* |
if(*p_Raiz == NULL) printf("\nA lista ja esta vazia\n"); |
||
else{ |
else{ |
||
struct No * |
struct No *p_atual; |
||
p_atual = *p_Raiz; |
|||
* |
*p_Raiz = (*p_Raiz)->p_prox; |
||
free( |
free(p_atual); |
||
} |
} |
||
} |
} |
||
Linha 89: | Linha 114: | ||
<source lang="C"> |
<source lang="C"> |
||
void |
void remover_No_Fim(struct No **p_Raiz){ |
||
if(* |
if(*p_Raiz == NULL) printf("\nA lista ja esta vazia"); |
||
else{ |
else{ |
||
struct No * |
struct No *p_atual, *p_anterior ; |
||
p_atual = *p_Raiz; |
|||
while( |
while(p_atual->p_prox != NULL){ |
||
p_anterior = p_atual ; |
|||
p_atual = p_atual->p_prox; |
|||
} |
} |
||
p_anterior->p_prox = NULL; |
|||
free( |
free(p_atual); |
||
} |
} |
||
} |
} |
||
Linha 109: | Linha 134: | ||
<source lang="C"> |
<source lang="C"> |
||
void |
void mostrar_Do_Fim_Para_Raiz(struct No *p_Raiz){ |
||
if( |
if(p_Raiz == NULL) printf("\nLista vazia"); |
||
else{ |
else{ |
||
struct No * |
struct No *p_Atual_Corredor, *p_Atual_Fim; |
||
p_Atual_Corredor = p_Raiz; |
|||
p_Atual_Fim = p_Raiz; |
|||
while( |
while(p_Atual_Fim->p_prox != NULL){ //ir para o ultimo elemento |
||
p_Atual_Fim = p_Atual_Fim->p_prox; |
|||
} |
} |
||
while( |
while(p_Atual_Corredor != p_Atual_Fim){ |
||
if( |
if(p_Atual_Corredor->p_prox == p_Atual_Fim){ |
||
printf(" <- %s", |
printf(" <- %s", p_Atual_Fim->p_dados); |
||
p_Atual_Fim = p_Atual_Corredor; |
|||
p_Atual_Corredor = p_Raiz; |
|||
} |
} |
||
p_Atual_Corredor = p_Atual_Corredor->p_prox; |
|||
} |
} |
||
printf(" <- %s", |
printf(" <- %s", p_Atual_Fim->p_dados); |
||
} |
} |
||
} |
} |
||
Linha 133: | Linha 158: | ||
===Da raiz para o fim=== |
===Da raiz para o fim=== |
||
<source lang="C"> |
<source lang="C"> |
||
void |
void mostrar_Da_Raiz_Para_Fim(struct No *p_Raiz){ |
||
if( |
if(p_Raiz == NULL) printf("\nLista vazia"); |
||
else{ |
else{ |
||
struct No * |
struct No *p_atual; |
||
p_atual = p_Raiz; |
|||
while( |
while(p_atual != NULL){ |
||
printf("%s", |
printf("%s", p_atual->p_dados); |
||
p_atual = p_atual->p_prox; |
|||
} |
} |
||
} |
} |
Revisão das 03h02min de 23 de junho de 2009
Listas encadeadas são estruturas de dados lineares e dinâmicas, a grande vantagem que elas possuem em relação ao uso de vetor é o fato de terem tamanho máximo relativamente infinito (o tamanho máximo é o da memória do computador), ao mesmo tempo que podem ter o tamanho mínimo de 1 elemento evitando o desperdício de memória.
Primitivas
Não existe nem uma normalização quanto as primitivas usadas para a manipulação de uma lista.
Em-baixo você pode ver uma lista com algumas delas .
- Colocar o índice sobre o primeiro elemento da lista.
- Colocar o índice sobre o ultimo elemento da lista .
- Colocar o índice sobre o elemento que segue o elemento atual .
- Colocar o índice sobre o elemento que precede o elemento atual .
- Verificar se a lista esta vazia : Se a lista estiver vazia retorna verdadeiro, se não falso.
- Verificar se é o primeiro elemento : Retorna verdadeiro se o elemento atual é o primeiro, se não falso.
- Verificar se é o ultimo elemento : Retorna verdadeiro se o elemento atual é o ultimo, se não falso.
- Verificar o numero de elementos da lista : Retorna o numero de elementos da lista.
- Adicionar um elemento no inicio : Adicionar um elemento antes do primeiro elemento da lista .
- Adicionar um elemento no fim : Adicionar um elemento depois do ultimo elemento da lista .
- Inserção : Inserir um elemento antes do elemento atual .
- Troca : Trocar o elemento atual .
- Remoção : Remover o elemento atual .
Lista encadeada linear
Cada nó ou elemento de uma lista encadeada irá possuir guardar o valor do nó e o endereço do próximo nó. Em uma lista encadeada linear o ultimo elemento aponta para NULL .
struct No{
char *p_dados;
struct No *p_prox;
};
Iniciar uma lista
A função abaixo demonstra como iniciar uma lista criando o espaço da raiz na memória.
void criar_Lista(struct No **p_Raiz){
*p_Raiz = NULL;
}
Inserção
Existem 3 tipos de inserção em uma lista, pode-se inserir no começo, no final ou entre dois elementos da lista.
Inserção no início
void inserir_No_Inicio(struct No **p_Raiz, char *p_String){
struct No *p_Novo;
/** Alocação dinâmica da memoria */
if((p_Novo = (struct No *) malloc(sizeof(struct No))) == NULL ){
puts( "Falta Memoria\n"); return -1 ;
}
p_Novo->p_dados = p_String;
if(*p_Raiz == NULL){
*p_Raiz = p_Novo;
p_Novo->p_prox = NULL;
}else{
p_Novo->p_prox = *p_Raiz;
*p_Raiz = p_Novo;
}
}
Inserção no fim
void inserir_No_Fim(struct No **p_Raiz, char *p_String){
struct No *p_Novo;
if(( p_Novo = (struct No *) malloc(sizeof(struct No))) == NULL ){
puts( "Falta Memoria\n"); return -1 ;
}
p_Novo->p_dados = p_String;
p_Novo->p_prox = NULL;
if(*p_Raiz == NULL)
*p_Raiz = p_Novo;
else{
struct No *e_atual; /*@ Elemento atual*/
e_atual = *p_Raiz; /*@ Primeiro elemento*/
while(e_atual->p_prox != NULL){
e_atual = e_atual->p_prox;
}
e_atual->p_prox = p_Novo;
}
}
Remoção
Assim como na inserção também existem 3 tipos de remoção, no início, no fim ou entre dois elementos da lista.
Remoção no início
void remover_No_Inicio(struct No **p_Raiz){
if(*p_Raiz == NULL) printf("\nA lista ja esta vazia\n");
else{
struct No *p_atual;
p_atual = *p_Raiz;
*p_Raiz = (*p_Raiz)->p_prox;
free(p_atual);
}
}
Remoção no fim
void remover_No_Fim(struct No **p_Raiz){
if(*p_Raiz == NULL) printf("\nA lista ja esta vazia");
else{
struct No *p_atual, *p_anterior ;
p_atual = *p_Raiz;
while(p_atual->p_prox != NULL){
p_anterior = p_atual ;
p_atual = p_atual->p_prox;
}
p_anterior->p_prox = NULL;
free(p_atual);
}
}
Exibição
Do fim para a raiz
void mostrar_Do_Fim_Para_Raiz(struct No *p_Raiz){
if(p_Raiz == NULL) printf("\nLista vazia");
else{
struct No *p_Atual_Corredor, *p_Atual_Fim;
p_Atual_Corredor = p_Raiz;
p_Atual_Fim = p_Raiz;
while(p_Atual_Fim->p_prox != NULL){ //ir para o ultimo elemento
p_Atual_Fim = p_Atual_Fim->p_prox;
}
while(p_Atual_Corredor != p_Atual_Fim){
if(p_Atual_Corredor->p_prox == p_Atual_Fim){
printf(" <- %s", p_Atual_Fim->p_dados);
p_Atual_Fim = p_Atual_Corredor;
p_Atual_Corredor = p_Raiz;
}
p_Atual_Corredor = p_Atual_Corredor->p_prox;
}
printf(" <- %s", p_Atual_Fim->p_dados);
}
}
Da raiz para o fim
void mostrar_Da_Raiz_Para_Fim(struct No *p_Raiz){
if(p_Raiz == NULL) printf("\nLista vazia");
else{
struct No *p_atual;
p_atual = p_Raiz;
while(p_atual != NULL){
printf("%s", p_atual->p_dados);
p_atual = p_atual->p_prox;
}
}
}