Listas Generalizadas

INSTITUTO FEDERAL DE EDUCAÇÃO, CIÊNCIA E TECNOLOGIA

RUANNA DE OLIVEIRA SANTANA

LISTAS GENERALIZADAS

ARAGUATINS
2011
INSTITUTO FEDERAL DE EDUCAÇÃO, CIÊNCIA E TECNOLOGIA
LICENCIATURA EM COMPUTAÇÃO

LISTAS GENERALIZADAS

RUANNA DE OLIVEIRA SANTANA

Trabalho apresentado como parte dos requisitos básicos da disciplina de Estrutura de Dados do curso de Computação.

Professor(a): Ricardo Sousa

ARAGUATINS
2011
SUMÁRIO

1 INTRODUÇÃO 4
2 FUNDAMENTOS 5
2.1 DEFINIÇÃO DE LISTAS GENERALIZADAS 5
2.2 EXEMPLOS 5
3 ÁRVORES COMO LISTAS GENERALIZADAS 5
4 REPRESENTAÇÃO 6
5 EXIBIÇÃO 7
6 APLICAÇÃO 7
7 IMPLEMENTAÇÃO 8
7.1 IMPLEMENTAÇÃO EM PASCAL 8
7.2 IMPLEMENTAÇÃO EM C 9
8 CONCLUSÃO 10
9 REFERÊNCIAS BIBLIOGRÁFICAS 11

1 – INTRODUÇÃO

A lista generalizada é uma das estruturas de dados mais flexíveis que existem. Por meio dela podemos representar tanto listas lineares quanto árvores de qualquer grau.
Além da sua importância própria como forma de armazenamento de dados, a lista generalizada é também uma estrutura de dados recursiva.
Neste presente trabalho, abordarei a estrutura de lista generalizada e a implementação de operações básicas que ela suporta.

2 – FUNDAMENTOS

2.1 – Definição de Listas Generalizadas

Lista generalizada é uma sequencia de itens L = [x1, x2, ..., xn], n ≥ 0, em que cada item x, é um átomo ou uma lista generalizada. Dois casos especiais de listas generalizadas são a lista nula, denotada por L = [], e a lista atômica, denotada por L = x1. Se L não é nula nem atômica, ela é própria. Se L é uma lista generalizada própria, então x1 e [x2, ..., xn] são denominados, respectivamente, cabeça e cauda de L. A definição de lista generalizada é recursiva, pois é preciso recorrer à notação previa de lista generalizada para poder defini-la. Ainda que algumas vezes pareça redundante, o uso