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

Origem: Wikilivros, livros abertos por um mundo aberto.
[edição verificada][edição não verificada]
Conteúdo apagado Conteúdo adicionado
Sem resumo de edição
Linha 1: Linha 1:
1º Está tudo MAL!
2ª Já não faço NADA!
3ª Pois está tudo MAL!

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.



Revisão das 16h32min de 30 de janeiro de 2013

1º Está tudo MAL! 2ª Já não faço NADA! 3ª Pois está tudo MAL!

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 nenhuma normalização quanto as primitivas usadas para a manipulação de uma lista.
Abaixo você pode ver uma lista com algumas delas .

  • Colocar o índice sobre o primeiro elemento da lista.
  • Colocar o índice sobre o último 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 está 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 último elemento  : Retorna verdadeiro se o elemento atual é o último, se não, falso.
  • Verificar o número de elementos da lista : Retorna o número de elementos da lista.
  • Adicionar um elemento no início : Adicionar um elemento antes do primeiro elemento da lista .
  • Adicionar um elemento no fim : Adicionar um elemento depois do último elemento da lista .
  • Inserção : Inserir um elemento antes do elemento atual .
  • Troca : Trocar o elemento atual .
  • Remoção : Remover o elemento atual .
  • Listar todos os elementos da lista .

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

int 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

int 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;
            }
            else 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;
                 
        }
    }
}