Arvores

Índice

Introdução 2

Listas Ligadas 3

Estrutura das Listas Ligadas 3

Operações de Listas Ligadas 4

Função de inicialização 4

Função de inserção 4

Função que percorre os elementos da lista 5

Função que verifica se lista está vazia 5

Função de busca 5

Função que retira um elemento da lista 6

Função para liberar a lista 7

Vantagens 7

Desvantagens 7

Tipos de Listas Ligadas 8

Listas Ligadas Simples 8

Propriedadas das Listas Ligadas Simples 8

Listas duplamente ligadas 8

Vantagens 9

Desvantagens 9

Listas circulares 9

Lista circular duplamente encadeada 10

Vantagens 10

Desvantagens 10

Projecto 11

Conclusão 12

Referências Bibliográficas 13

Introdução

Frequentemente precisamos agrupar vários elementos/dados num conjunto. A partida podemos não saber o número exacto de elementos a ser agrupados. Em cada instante podemos acrescentar ou remover elemento ao conjunto. Em programação consideramos dois tipos de estruturas que permitem guardar uma colecção de elementos: estrutura estática e estrutura dinâmica. Os elementos podem ser organizados de um modo distinto.

Uma matriz é uma estrutura que é fornecido em linguagens de programação. No entanto, tem pelo menos duas limitações: (1) rearranjar o tamanho da matriz necessária para criar uma matriz com o tamanho pré-arranjo com o novo tamanho, e (2) nos dados de matriz são próximas umas das outras sequencialmente na memória, o que significa que para inserir um item para a matriz deve ser movido por outro arranjo. Esta limitação pode ser ultrapassada pela utilização de estruturas ligadas.

A estrutura relacionada é uma coleção de nós que armazena os dados e links para outros nós. Assim, os nós podem ser localizado em qualquer lugar da memória e da passagem a partir de um nó para o outro dentro da estrutura ligada é conseguido através do armazenamento das referências ou para outro nó ou nós na estrutura.

Uma lista encadeada é a forma mais simples de representar uma colecção de elementos que juntos formam uma ordenação linear. Cada elemento da colecção é representado pelo objecto da classe No .

Mesmo quando as estruturas ligadas pode ser implementado numa variedade de formas, mais flexível é a utilização de um objeto separado para cada nó.

Listas de dados são conjuntos de elementos de dados "alienado em uma linha", as inserções e exclusões são feitas em qualquer parte de uma lista encadeada.

As pilhas são importantes para compiladores e sistemas operativos, as inserções e deleções são feitas apenas com uma extremidade da pilha isto é, na parte superior.

As filas de espera representam linhas, as inserções são feitas no final (também conhecido como o calcanhar) de uma fila, e deleções são feitas a partir do topo (também conhecido como a cabeça) de uma fila.

As árvores fornecem busca e arquivos de dados ordinamiento sytem e expressões compilação em linguagem de máquina. Cada uma destas estruturas de dados tem muitas outras aplicações interessantes.

O presente trabalho tem como objectivo fazer uma abordagem as listas ligadas, para melhor compreensão e com isso sermos capazes de desenvolver uma aplicação cujo seja capaz de registar vários serviços num Registo Cívil como registos de nascimentos, casamentos entre outros.

Listas Ligadas

Uma lista ligada é uma estrutura linear e dinâmica, que corresponde a uma sequência lógica de entradas ou nós. Tipicamente, em uma lista ligada há um ou dois pontos conhecidos de acesso, normalmente o topo da lista (seu primeiro elemento) e eventualmente o fim da lista (seu último elemento).

Cada nó armazena também a localização do próximo elemento na seqüência, ou seja, de seu nó sucessor. Desse modo, o armazenamento de uma lista não requer uma área contígua de memória.

Fig. 1 Representa graficamente uma estrutura de lista ligada.

Estrutura das Listas Ligadas

A estrutura consiste numa seqüência encadeada de elementos, em geral chamados de nós da lista. A lista é representada por um ponteiro para o primeiro elemento (ou nó).

Do primeiro elemento, podemos alcançar o segundo seguindo o encadeamento, e assim por diante. O último elemento da lista aponta para NULL, sinalizando que não existe um próximo elemento.

Para exemplificar a implementação de listas encadeadas em C, vamos considerar um exemplo simples em que queremos armazenar valores inteiros numa lista encadeada. O

nó da lista pode ser representado pela estrutura abaixo:

struct lista {

int info;

struct lista* prox;

};

typedef struct lista Lista;

Podemos notar que trata-se de uma estrutura auto-referenciada, pois, além do campo que armazena a informação (no caso, um número inteiro), há um campo que é um ponteiro para uma próxima estrutura do mesmo tipo. Embora não seja essencial, é uma boa estratégia definirmos o tipo Lista como sinônimo de struct lista, conforme mostrado acima.

O tipo Lista representa um nó da lista e a estrutura de lista encadeada é representada pelo ponteiro para seu primeiro elemento (tipo Lista*).

Considerando a definição de Lista, podemos definir as principais funções necessárias para implementarmos uma lista encadeada.

As listas ligadas apresentam operações como: inicializa uma lista vazia, cria