Encadeamento de nós

Entendendo o encadeamento de nós nas estruturas:

As estruturas de dados giram em torno do encadeamento dos nós que contém as informações armazenadas e processadas nestas estruturas. Em todas as estruturas nós temos a ocorrências de nós. E cada nó aponta para um ou vários nós de seu tipo.

Em C, o perfeito entendimento do encadeamento de nós é essencial para assimilar as estruturas de dados. Sendo assim, considero que a leitura desta dica o ajudará muito na implementação e alteração dos códigos contidos na minha seção de estruturas de dados.

Nas estruturas de dados em C, um nó é implementado como uma estrutura. Assim, a seguinte estrutura:


struct Pessoa{
  int codigo;
  char nome[80];
  struct Pessoa *proximo;
};


representa uma pessoa, contendo um código, um nome e um ponteiro para uma estrutura do mesmo tipo, ou seja, outra pessoa. Analise o código a seguir cuidadosamente:



#include <stdio.h>
#include <stdlib.h>
#include <string.h>

// estrutura Pessoa
struct Pessoa{
  int codigo;
  char nome[80];
  struct Pessoa *proximo;
};
// fim da estrutura Pessoa

int main(int argc, char *argv[])
{
  // vamos criar a primeira Pessoa
  struct Pessoa *pessoa1 = (struct Pessoa*)malloc(
    sizeof(struct Pessoa));
  pessoa1->codigo = 1;
  strcpy(pessoa1->nome, "Osmar J. Silva");
  pessoa1->proximo = NULL;

  // vamos criar a segunda Pessoa
  struct Pessoa *pessoa2 = (struct Pessoa*)malloc(
    sizeof(struct Pessoa));
  pessoa2->codigo = 2;
  strcpy(pessoa2->nome, "Marcos S. Teixeira");
  pessoa2->proximo = NULL;

  // vamos criar a terceira Pessoa
  struct Pessoa *pessoa3 = (struct Pessoa*)malloc(
    sizeof(struct Pessoa));
  pessoa3->codigo = 3;
  strcpy(pessoa3->nome, "Fernanda Souza Xavier");
  pessoa3->proximo = NULL;

  // vamos exibir os dados destas estruturas
  printf("%d - %s\n", pessoa1->codigo, pessoa1->nome);
  printf("%d - %s\n", pessoa2->codigo, pessoa2->nome);
  printf("%d - %s\n\n", pessoa3->codigo, pessoa3->nome);

  system("pause");
  return 0;
}




Neste código nós temos a criação de três estruturas do tipo Pessoa, cada uma contendo dados diferentes. Note que o campo proximo de cada uma recebe o valor NULL, ou seja, não aponta para lugar nenhum. Vamos concentrar nossa atenção neste campo proximo. Veja o trecho de código a seguir:



// o campo proximo da primeira pessoa aponta para a
// segunda pessoa
pessoa1->proximo = pessoa2;
// o campo proximo da segunda pessoa aponta para a
// terceira pessoa
pessoa2->proximo = pessoa3;
// só temos três pessoas, então o campo proximo da
// terceira pessoa continua apontando para lugar nenhum
pessoa3->proximo = NULL;



É aqui que a mágica do encadeamento acontece. Note que o campo proximo de cada estrutura aponta para a estrutura seguinte, com exceção da terceira estrutura, que continua apontando para NULL.

E, agora que o encadeamento está feito, "pular" de uma estrutura para outra é questão de seguir a ligação entre os nós. Veja, por exemplo, como exibimos os dados da terceira estrutura a partir de uma referência à primeira estrutura:


printf("%d - %s\n", pessoa1->proximo->proximo->codigo,
  pessoa1->proximo->proximo->nome);



É claro que se tivermos algumas centenas de nós, o uso desta forma de encadeamento não é nada viável. Mas isso é assunto para as outras dicas. Para finalizar, veja o código completo para esta discussão:



#include <stdio.h>
#include <stdlib.h>
#include <string.h>

// estrutura Pessoa
struct Pessoa{
  int codigo;
  char nome[80];
  struct Pessoa *proximo;
};
// fim da estrutura Pessoa

int main(int argc, char *argv[])
{
  // vamos criar a primeira Pessoa
  struct Pessoa *pessoa1 = (struct Pessoa*)malloc(
    sizeof(struct Pessoa));
  pessoa1->codigo = 1;
  strcpy(pessoa1->nome, "Osmar J. Silva");
  pessoa1->proximo = NULL;

  // vamos criar a segunda Pessoa
  struct Pessoa *pessoa2 = (struct Pessoa*)malloc(
    sizeof(struct Pessoa));
  pessoa2->codigo = 2;
  strcpy(pessoa2->nome, "Marcos S. Teixeira");
  pessoa2->proximo = NULL;

  // vamos criar a terceira Pessoa
  struct Pessoa *pessoa3 = (struct Pessoa*)malloc(
    sizeof(struct Pessoa));
  pessoa3->codigo = 3;
  strcpy(pessoa3->nome, "Fernanda Souza Xavier");
  pessoa3->proximo = NULL;

  // o campo proximo da primeira pessoa aponta para a
  // segunda pessoa
  pessoa1->proximo = pessoa2;
  // o campo proximo da segunda pessoa aponta para a
  // terceira pessoa
  pessoa2->proximo = pessoa3;
  // só temos três pessoas, então o campo proximo da
  // terceira pessoa continua apontando para lugar nenhum
  pessoa3->proximo = NULL;

  // exibe os dados do primeiro nó
  printf("%d - %s\n", pessoa1->codigo,
    pessoa1->nome);

  // exibe os dados do segundo nó
  printf("%d - %s\n", pessoa1->proximo->codigo,
    pessoa1->proximo->nome);

  // exibe os dados do terceiro nó
  printf("%d - %s\n", pessoa1->proximo->proximo->codigo,
    pessoa1->proximo->proximo->nome);

  system("pause");
  return 0;
}

Este Vídeo é um trechinho da aula do Professor Valente, onde ele aborda alguns aspectos desse assunto: