C Alguém pode me explicas lista encadeada simples ?

[Guilgb]

To tendo muitos problemas em Programação estruturada por conta do meu professor anterior. Daí não consigo entender como funciona a lista encadeada simples. Se alguém puder me ajudar agradeço muuito.

[Flávio Pedroza]

você pode imaginar uma lista encadeada simples como uma corrente. Cada nó/elemento da lista (ou elo da corrente) está ligado ao próximo e apenas a ele. Essa ligação é realizada através de um campo que aponta para o próximo elemento da lista.

você pode percorrer a lista apenas em um sentido, do começo para o fim. Se quiser, por exemplo, acessar o último elemento, terá que percorrer toda lista.

Eu exemplo seria um edifício, em que não fosse possível descer, apenas subir. Os andares seriam elementos e as escadas os campos que apontam para o próximo elemento, ou, no caso, o próximo andar.

Para ir para o quinto andar, começo do térreo (primeiro elemento da lista) e percorro o primeiro, segundo, etc. andares até chegar o quinto. Não existe escadas ligando o primeiro e quinto diretamente. Cada lance escada liga um andar apenas ao próximo.

Em c seria assim:

struct andar
{
    int no_andar;
    andar *escada;//aponta para o proximo andar - ligacao entre um andar e outro
};

Espero ter ajudado.

[Guilgb]

Muito obrigado. E na implementação como posso implementar uma lista encadeada. fazer o nó referenciar o proximo, adicionar excluir buscar como posso fazer isso ?@Flávio Pedroza @Flávio Pedroza

Em 08/10/2019 às 15:31, Guilgb disse:

1 hora atrás, Flávio Pedroza disse:

você pode imaginar uma lista encadeada simples como uma corrente. Cada nó/elemento da lista (ou elo da corrente) está ligado ao próximo e apenas a ele. Essa ligação é realizada através de um campo que aponta para o próximo elemento da lista.

você pode percorrer a lista apenas em um sentido, do começo para o fim. Se quiser, por exemplo, acessar o último elemento, terá que percorrer toda lista.

Eu exemplo seria um edifício, em que não fosse possível descer, apenas subir. Os andares seriam elementos e as escadas os campos que apontam para o próximo elemento, ou, no caso, o próximo andar.

Para ir para o quinto andar, começo do térreo (primeiro elemento da lista) e percorro o primeiro, segundo, etc. andares até chegar o quinto. Não existe escadas ligando o primeiro e quinto diretamente. Cada lance escada liga um andar apenas ao próximo.

Em c seria assim:

struct andar
{
    int no_andar;
    andar *escada;//aponta para o proximo andar - ligacao entre um andar e outro
};

Espero ter ajudado.

 

 

[Flávio Pedroza]

você primeiramente cria o nó de início da lista. Seguindo o exemplo que dei, chamarei o nó de início de terreo. você também pode armazenar o nó final - o último elemento da lista, que chamarei de cobertura. 

struct andar
{
    int no_andar;
    andar *escada;//aponta para o proximo andar - ligacao entre um andar e outro
};


andar* terreo = (andar *)malloc(sizeof(andar));
andar* cobertura = terreo; //no início a lista só terah um andar, deste modo o fim e inicio (terreo e cobertura) serao iguais. 
terreo->no_andar = 0;
terreo->escada = NULL; //o predio nao tem escadas inicialmente

E então vá adicionando os elementos. Por exemplo, para adicionar 05 elementos novos:

//adiciona 05 andares
    for (int i =1; i <= 5; i++)
    {
        andar *novo = (andar *)malloc(sizeof(andar)); //cria um novo andar
        novo->no_andar = i;
        novo->escada = NULL; //como este sera o ultio andar, a escada nao aponta para lugar nenhum
        
        cobertura->escada = novo;   //liga o novo ultimo ao anterior antraves da escada 
        cobertura = novo; //o ultimo andar passa a ser este novo andar criado
    }
    

Para varrer a lista e imprimir todos os andares, começo do terreo:

andar* atual = terreo; //andar atual: terreo
    while (atual != NULL) //enquanto houver andares no prédio
    {
        printf("Andar no: %d\n", atual->no_andar);
        atual = atual->escada; //"sobe" a escada e vai para o proximo andar
    }

Veja se entende esses conceitos mais básicos.

[arfneto]

5 horas atrás, Guilgb disse:

To tendo muitos problemas em Programação estruturada por conta do meu professor anterior. Daí não consigo entender como funciona a lista encadeada simples

 

listas não tem a ver com programação, estruturada ou não. Que curso está fazendo? Normalmente isso é abordado em cursos de estruturas de dados e em alguns casos não se usam sequer programas, apenas algo tipo um pseudo-código com listas de instruções em linguagem comum.

 

Postei um código completo em C para tratar listas encadeadas " simples" dias atrás. Talvez pudesse baixar esse programa e rodar em sua máquina e te ajude a entender o mecanismo.

 

Em resumo, listas encadeadas são estruturas de dados onde cada elemento tem uma variável que aponta para o próximo, como uma fila em que cada cliente tivesse a sua senha e a senha do próximo. É só isso. 

 

Essa nomenclatura de lista simples não é muito feliz. A lista que não é essa " simples"  tem um ponteiro para o elemento anterior além de ter um ponteiro para o próximo. Digamos que ela é simples mas de mão dupla.

 

Um ponteiro pode ser simplesmente um índice em um vetor, ou por exemplo pensando no clássico roteiro de um carteiro, ele tem um roteiro de ruas e a cada entrega se preocupa somente com as próximas entregas: uma lista " simples". 

 

Essas estruturas tem grande aplicação prática, porque afinal descrevem um grande número de situações práticas.entre outras algoritmos de classificação. E faz sentido: se você está classificando um cadastro enorme por exemplo, pode estar em um dado momento classificando por CPF, em outro por nome, em outro por CEP, dependendo de seu interesse no momento.

 

Então faria sentido por exemplo usar listas encadeadas criando o que você faria talvez num papel: uma lista com ponteiros para frente e para trás e você vai inserindo os valores na posição certa, e acaba com várias listas que apontam para o cadastro original, mas sem mexer no mesmo.

 

O programa que eu postei, por exemplo, tem uma função que insere valores na ordem. 

 

Exemplo usado naquele programa:

struct lista
{
    Registro*        r;
    struct lista*    proximo;
};    // Lista
typedef struct lista Lista;

Essas funções estão implementadas lá:

int            apaga_registro( int(*)(Registro*, Registro*), Registro*,  Lista**);
int            da_um_fim_na_lista(    Lista**);
int            insere_ao_final( Registro*, Lista**);
int            insere_na_ordem( int (*)(Registro*, Registro*), Registro*, Lista**);
Registro*      pesquisa_registro( int(*)(Registro*, Registro*), Registro*, Lista**);
int            remove_item( Lista*, Lista**);
int            remove_registro( int(*)(Registro*, Registro*), Registro*, Lista**);

Aqui está o programa e tem um botão para download