Programar em C/Listas encadeadas: diferenças entre revisões

Saltar para a navegação Saltar para a pesquisa

Programar em C/Listas encadeadas (editar)

Revisão das 03h02min de 23 de junho de 2009

1 711 bytes adicionados ,  23 de junho de 2009
sem resumo de edição
(Ver alterações pendentes à versão publicada)
[edição não verificada][edição não verificada]
VisualTexto wiki
Sem resumo de edição
Sem resumo de edição
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.
 
==StructPrimitivas==
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.
Cada nó de uma lista encadeada irá possuir guardar o valor do nó e o endereço do próximo nó.▼
* 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 .
 
<source lang="C">
struct No{
char *pStringp_dados;
struct No *pProxp_prox;
};
</source>
 
<source lang="C">
void criarListacriar_Lista(struct No **pRaizp_Raiz){
*pRaizp_Raiz = NULL;
}
</source>
==Inserção==
 
Existem 23 tipos de inserção numaem uma lista, pode-se inserir no começo ou, no final ou entre dois elementos da lista.
 
===Inserção no início===
 
<source lang="C">
void inserirNoInicioinserir_No_Inicio(struct No **pRaizp_Raiz, char *pStringp_String){
struct No *pNovop_Novo;
/** Alocação dinâmica da memoria */
pNovoif((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(*pRaizp_Raiz == NULL){
*pRaizp_Raiz = pNovop_Novo;
pNovop_Novo->pProxp_prox = NULL;
}else{
pNovop_Novo->pProxp_prox = *pRaizp_Raiz;
*pRaizp_Raiz = pNovop_Novo;
}
}
 
<source lang="C">
void inserirNoFiminserir_No_Fim(struct No **pRaizp_Raiz, char *pStringp_String){
struct No *pNovop_Novo;
pNovoif(( p_Novo = (struct No *) malloc(sizeof(struct No));) == NULL ){
puts( "Falta Memoria\n"); return -1 ;
pNovo->pString = pString;
pNovo->pProx = NULL;}
p_Novo->p_dados = p_String;
p_Novo->p_prox = NULL;
if(*pRaizp_Raiz == NULL){
*pRaizp_Raiz = pNovop_Novo;
}else{
struct No *pAuxe_atual; /*@ Elemento atual*/
pAuxe_atual = *pRaizp_Raiz; /*@ Primeiro elemento*/
while(pAuxe_atual->pProxp_prox != NULL){
pAuxe_atual = pAuxe_atual->pProxp_prox;
}
pAuxe_atual->pProxp_prox = pNovop_Novo;
}
}
==Remoção==
 
Assim como na inserção também existem 23 tipos de remoção, no início e, no fim ou entre dois elementos da lista.
 
===Remoção no início===
 
<source lang="C">
void removerNoInicioremover_No_Inicio(struct No **pRaizp_Raiz){
if(*pRaizp_Raiz == NULL) printf("\nA lista ja esta vazia\n");
else{
struct No *pAuxp_atual;
pAuxp_atual = *pRaizp_Raiz;
*pRaizp_Raiz = (*pRaizp_Raiz)->pProxp_prox;
free(pAuxp_atual);
}
}
 
<source lang="C">
void removerNoFimremover_No_Fim(struct No **pRaizp_Raiz){
if(*pRaizp_Raiz == NULL) printf("\nA lista ja esta vazia");
else{
struct No *pAuxFrentep_atual, *pAuxTrasp_anterior ;
pAuxFrentep_atual = *pRaizp_Raiz;
while(pAuxFrentep_atual->pProxp_prox != NULL){
pAuxTrasp_anterior = pAuxFrentep_atual ;
pAuxFrentep_atual = pAuxFrentep_atual->pProxp_prox;
}
pAuxTrasp_anterior->pProxp_prox = NULL;
free(pAuxFrentep_atual);
}
}
 
<source lang="C">
void mostrarDoFimParaRaizmostrar_Do_Fim_Para_Raiz(struct No *pRaizp_Raiz){
if(pRaizp_Raiz == NULL) printf("\nLista vazia");
else{
struct No *pAuxCorredorp_Atual_Corredor, *pAuxFimp_Atual_Fim;
pAuxCorredorp_Atual_Corredor = pRaizp_Raiz;
pAuxFimp_Atual_Fim = pRaizp_Raiz;
while(pAuxFimp_Atual_Fim->pProxp_prox != NULL){ //ir para o ultimo elemento
pAuxFimp_Atual_Fim = pAuxFimp_Atual_Fim->pProxp_prox;
}
while(pAuxCorredorp_Atual_Corredor != pAuxFimp_Atual_Fim){
if(pAuxCorredorp_Atual_Corredor->pProxp_prox == pAuxFimp_Atual_Fim){
printf(" <- %s", pAuxFimp_Atual_Fim->pStringp_dados);
pAuxFimp_Atual_Fim = pAuxCorredorp_Atual_Corredor;
pAuxCorredorp_Atual_Corredor = pRaizp_Raiz;
}
pAuxCorredorp_Atual_Corredor = pAuxCorredorp_Atual_Corredor->pProxp_prox;
}
printf(" <- %s", pAuxFimp_Atual_Fim->pStringp_dados);
}
}
===Da raiz para o fim===
<source lang="C">
void mostrarDaRaizParaFimmostrar_Da_Raiz_Para_Fim(struct No *pRaizp_Raiz){
if(pRaizp_Raiz == NULL) printf("\nLista vazia");
else{
struct No *pAuxp_atual;
pAuxp_atual = pRaizp_Raiz;
while(pAuxp_atual != NULL){
printf("%s", pAuxp_atual->pStringp_dados);
pAuxp_atual = pAuxp_atual->pProxp_prox;
}
}
Utilizador anónimo
Obtido em "https://pt.wikibooks.org/wiki/Especial:MobileDiff/130004"

Menu de navegação