Listas Ligadas - Parte 2

Continuando a nossa série, vamos continuar a falar sobre estruturas de dados, vendo dois exemplos importantes de como as estruturas de dados primitivas podem ser combinadas para gerar estruturas mais complexas.

Estruturas

O termo estrutura é usado para indicar uma estrutura não-primitiva composta por uma conjunto estruturado de dados primitivos. Por exemplo, podemos representar um ponto na tela por uma sequencia de dois inteiros contendo as duas coordenadas do ponto. Em C:

struct ponto
{
int x;
int y;
};

Neste exemplo, x e y são os campos da estrutura ponto. Na linguagem C utiliza-se a notação a.b para indicar o campo b da variável a. Por exemplo:

struct ponto pt;
pt.x = 10;
pt.y = 20;

Um campo de uma estrutura pode ser uma outra estrutura, criando um conjunto hierarquizado. Por exemplo, vamos definir uma estrutura para representar um círculo, composta por um ponto (centro) e um valor inteiro (raio):

struct circulo
{
struct ponto centro;
int raio;
};

struct circulo c;
c.centro.x = 20;

Repare no exemplo a notação c.centro.x para indicar o campo x do campo centro da variável c.

A linguagem C permite o uso de ponteiros com estruturas. Por exemplo:

struct circulo *pc;
struct circulo c;
int r, xis;

pc = &c;
r = (*pc).raio;
xis = (*pc).centro.x;

Para simplificar a codificação, a linguagem C permite substituir a notação “(*p).” por “p->” :

r = pc->raio;
xis = pc->centro.x;

Ao definir estruturas mais complexas (como as listas ligadas), pode surgir a necessidade de colocar dentro da estrutura um ponteiro para uma estrutura do mesmo tipo.Em C:

struct circulo
{
struct ponto centro;
int raio;
struct circulo *pc;
};

É importante entender que nessa declaração não estamos colocando uma estrutura dentro dela mesma (o que geraria uma recursão infinita). A linha “struct circulo *pc;” acima simplesmente acrescenta à estrutura circulo uma variável que conterá o endereço de uma outra variável do tipo círculo.

Vetores e Matrizes

Matrizes são conjuntos ordenados com um número fixo de elementos, não é possível acrescentar (inserir) ou retirar (remover) elementos. Um elemento de uma matriz é referenciado através de um conjunto de números inteiros sequenciais, os índices. A quantidade de índices usados para acessar uma matriz é a sua dimensão, uma matriz com dimensão um é um vetor.

Esta definição formal fica mais simples se examinarmos alguns exemplos. Comecemos examinando um vetor com 10 inteiros. Na linguagem C, podemos declará-lo da seguinte forma:

int v[10];

O vetor v é um conjunto com 10 elementos. Os elementos individuais são acessados através dos números 0, 1, 2, 3, 4, 5, 6, 7, 8 e 9, usando a seguinte notação:

v[5] = 3;

Este comando coloca o valor 3 no elemento de índice 5, que é o sexto elemento do vetor v.

Obs.: Na linguagem C os índices começam sempre de 0. Desta forma, um vetor com “n” elementos é acessado por índices de 0 a n-1. O elemento de índice “i” é o elemento “(i+’)-ésimo” do vetor.

Uma forma de visualizar um vetor é como uma sequência de elementos consecutivos:

v[0]

v[1]

v[2]

v[3]

v[4]

v[5]

v[6]

v[7]

v[8]

v[9]

Uma matriz bi-dimensional pode ser visualizada como uma tabela. Por exemplo, considerando uma matriz de inteiros cujo primeiro índice varia de 0 a 2 e o segundo de 0 a 3:

int mat[3][4];

mat[0][0] = 3;
mat[2][3] = 2 * mat[0][0];

mat[0][0]	mat[0][1]	mat[0][2]	mat[0][3]
mat[1][0]	mat[1][1]	mat[1][2]	mat[1][3]
mat[2][0]	mat[2][1]	mat[2][2]	mat[2][3]

A linguagem C trata de forma muito semelhante vetores e ponteiros:

• as matrizes são armazenadas em posições sequênciais de memória.
  

• O nome de uma váriavel do tipo matriz representa o endereço do primeiro elemento:
  

int vet[10];
int *p;

p = &vet[0]; // p recebe o endereço do primeiro
  //   elemento de vet
p = vet; // idem

• Somar ou subtrair “n” a um ponteiro equivale a avançar ou recuar “n” elementos:
  

p = vet+2; // p aponta para o terceiro elemento

p = vet; // p aponta para o primeiro elemento
*(p+1) = 2; // (p+1) aponta para o 2o elemento
  //    ou seja, equivale a vet[1] = 2

• Expandindo o exemplo acima, o C considera p[n] equivalente a *(p+n). Ou seja, a última linha acima poderia ser escrita como
  

p[1] = 2;

• Portanto, usa-se a mesma notação para acessar elementos apontados por um ponteiro (p) e elementos de um vetor (vet).


• É importante lembrar que “int vet[10];” cria 10 variáveis do tipo inteiro, enquanto que “int *p;” cria apenas uma variável do tipo ponteiro para inteiro. A variável p só poderá ser utilizada para acessar elementos depois de ter sido inicializada.

No próximo post vamos encerrar esta introdução falando um pouco sobre a alocação dinâmica de memória no C.