http://www.li.facens.br/eletronica 1

1. GENERALIDADES

- Tipos de Estruturas de Dados

· matriz · cadeia de caracteres

· lista linear

· pilha

· fila

· árvore

· grafo

- Operações que podem ser feitas numa estrutura de dados:

· inserção · remoção

· leitura

· substituição

- Computadores servem para armazenar informações e programas para manipulá-las.

Programa é um algotritmo que manipula dados. Estrutura de dados retrata as relações lógicas existentes entre os dados.

2. MATRIZ

É uma estrutura de dados onde a informação armazenada (nó) tem a sua identificação feita através de uma linha e uma coluna.

Aplicações de Matrizes: - cálculo de potências num sistema de potência

3. CADEIA DE CARACTERES

O tipo de dados primitivo caracter consiste de um só caracter. No entanto, na prática, muitas vezes tem-se de manipular dados tais como nomes, frases e textos, que envolvem mais de um caracter e que são denominados CADEIA DE CARACTERES.

http://www.li.facens.br/eletronica 2

4. LISTA LINEAR 4.1 Introdução

É uma estrutura de dados que tem uma sequência ordenada de dados denominados nós.

Cada Lista Linear tem o seu nó inicial e o seu nó final, onde cada nó apresenta o mesmo tipo de dado.

Cada nó possue um campo de dados onde se armazenam as informações e um campo de ponteiros onde se armazenam os endereços que implementam as conexões entre os nós.

Existem vários tipos de Listas Lineares: - lista ligada simples

- lista duplamente ligada

4.2 Lista ligada simples cada nó tem:

4.3 Lista duplamente ligada cada nó tem:

4.4 Exemplos de Lista Linear inicio

(nó final) dados dados dados dados (nó inicial) dado end. próximo end. anterior dado end. próximo

(cabeça da lista) comprimento anterior dado 1 próxim. anterior dado 2 próxim. anterior dado n próxim.

http://www.li.facens.br/eletronica 3

- dias da semana - cartas de baralho

- andares de um edificio

5. PILHA

É uma estrutura linear LIFO ("Last In First Out") (Primeiro a Entrar Último a Sair)

Ex.: pilha de livros

É uma Lista Linear na qual todas as inserções e retiradas são feitas na mesma extremidade (o topo).

É uma estrutura linear FIFO ("First In First Out") (Primeiro a Entrar Primeiro a Sair).

Ex.: fila de pessoas em um guichê do banco

É uma Lista Linear na qual todas as inserções ocorrem numa extremidade (a traseira) e as retiradas ocorrem na outra extremidade (a frente)

7. ÁRVORE 7.1 Introdução

Na Árvore a relação existente entre os dados (denominados nós) é uma relação de hierarquia ou de composição, onde um conjunto de dados é hierarquicamente subordinado a outro.

Uma Árvore é um conjunto finito T de um ou mais nós, tais que: a) existe um nó raiz da árvore b) os demais nós formam conjuntos disjuntos, onde cada um destes conjuntos é uma árvore (denominada de subárvores) http://www.li.facens.br/eletronica 4

Exemplo:

Terminologia

- o número de subárvores de um nó é o grau daquele nó; - cada nó da Árvore é a raiz de uma subárvore;

- um nó de grau zero é denominado folha ou nó terminal;

- nível do nó: é igual ao número de "linhas" que o liga à raiz (a raiz tem nível zero);

- altura da Árvore é definida como sendo o nível mais alto da Árvore;

- floresta é um conjunto de zero ou mais Árvores disjuntas (se eliminarmos o nó raiz de uma árvore, o que dela restar forma uma floresta);

- a Árvore é ordenada quando a ordem dos subárvores é significativa;

- a Árvore é orientada quando a ordem das subárvores não é relevante.

para o caso de Árvore orientada, as duas árvores são iguais - a raiz de uma árvore é chamada de pai das raízes das suas subárvores

http://www.li.facens.br/eletronica 5

- as raízes das subárvores de um nó são chamadas de irmãos (que são filhos de seu nó pai)

- Árvores Binárias são estruturas do tipo Árvore, onde o grau de cada nó é menor ou igual a dois.

Para o exemplo temos:

Exemplos de Árvore:

- árvore genealógica de uma família - organograma de uma empresa

- índice de um livro

- diretórios e arquivos num sistema de computação

http://www.li.facens.br/eletronica 6

7.2 Aplicação de Árvores - Esquema hierárquico de uma universidade

http://www.li.facens.br/eletronica 7 o operador de menor prioridade da expressão aritmética aparece na raiz da Árvore http://www.li.facens.br/eletronica 8

7.3 Alocação das Árvores na Memória do Computador

- por adjacência - por encadeamento a) Alocação por Adjacência

- os nós da Árvore são representados seqüencialmente na memória, de acordo com uma determinada ordem convencionada em que eles aparecem na Árvore;

- os números que aparecem à direita da informação de cada nó na alocação seqüencial indicam o grau do nó correspondente.

A 3 B 1 G 0 C 0 D 2 E 0 F 0 representação na memória

- a alocação seqüencial não constitui na maioria dos casos uma maneira conveniente para representar Árvores (dificuldades para inserções, remoções e localizações de um nó particular)

- essa forma de alocação é útil para armazenamento permanente (em fita ou disco magnético) de Árvores representadas por encadeamento

http://www.li.facens.br/eletronica 9 b) Alocação por Encadeamento

- cada nó é um dado que pode ser alocado dinamicamente e possui espaço para representar tanto a informação do nó como as referências das subárvores daquele nó;

- o tipo de dado dos nós tem tantas referências quanto é o número máximo de subárvores que um nó possa ter.

http://www.li.facens.br/eletronica 10

7.4 Transformação de Árvore qualquer para Árvore Binária

- Árvore Binária -> grau máximo é 2 - para se fazer a transformação deve-se ligar os nós irmãos e remover a ligação entre um nó pai e os nós filhos, exceto os do primeiro filho.

- para se interpretar corretamente a hierarquia de uma Árvore transformada em Árvore Binária deve-se observar que a subárvore da esquerda de um nó é o filho deste nó, enquanto que a subárvore da direita é seu irmão.

http://www.li.facens.br/eletronica 1

8. GRAFO

Um Grafo G é constituído por um conjunto N de elementos e por uma relação binária A entre esses elementos.

A = conjunto cujos membros são pares ordenados (ni, nj), onde ni e nj são elementos de N.

Os elementos de N são denominados nós (ou vértices), enquanto os elementos de A são denominados arcos (ou arestas).

Nós adjacentes são nós ligados por arcos. Ex.: o nó 2 é adjacente a 1, 3 e 4.

<(a, n1), (n1, n2),, (n1-1, ni), (ni, b)>

Caminho = sequência de um ou mais arcos Quando a = b temos um circuito.

Grafo é conexo quando tem um nó do qual existem caminhos para todos os demais.

Subgrafo = subconjunto dos nós de um dado grafo http://www.li.facens.br/eletronica 12

1ª Aplicação de Grafos: 1736 sair de uma área de terra, passar por todas pontes somente uma vez, e voltar a área de terra inicial.

EULER provou que era impossível, sendo:

- áreas de terra = vértices - pontes = bordas grau de um vértice = número de bordas que lhe são incidentes

EULER mostrou que para existir um caminho é necessário que seja de valor par o grau de cada vertice.

Um grafo G consiste de 2 conjuntos V e E.

V = conjunto de vértices E = conjunto de bordas

Aplicações de Grafos:

D e b a d c e d c A

D f http://www.li.facens.br/eletronica 13

- análise de circuitos elétricos - verificação de caminhos mais curtos

- análise de planejamento de projetos

- identificação de produtos químicos

Comentários