Estruturas de Dados

Murilo Salgado Razoli

Estruturas de Dados Estruturas de dados são formas de armazenamento e organização de dados na memória de um computador, podem ser usadas em diversos tipos de aplicações.

Estruturas de Dados Clássicas Vetores( Arrays); Lista; Pilha; Filas; Grafos; Árvores:

Árvores Binárias.

“Estrutura de dados é o ramo da computação que estuda os diversos mecanismos de organização de dados para atender aos diferentes requisitos de processamento;

TAD

Uma Estrutura de Dados pode ser dividida em dois pilares fundamentais:Dados e Estrutura

Dados

Elemento que possui valor agregado e que pode ser utilizado para solucionar problemas computacionais.

Estrutura

Elemento Estrutural que é responsável por carregar informações dentro de uma estrutura de software

TAD – Tipo Abstrato de Dados

“Um tipo abstrato de dados define uma classe de objetos abstratos que é completamente caracterizada pelas operações disponíveis nestes objetos. Isto significa que um tipo abstrato de dados pode ser definido pela definição e caracterização das operações daquele tipo” (Liskov, 1974).

Tipos Abstratos de Dados (TAD)

Vantagens: Usam a TAD por meio da interface de acesso;

Sem conhecer os detalhes de representação. Não acessam o módulo de implementação;

Idealmente, a implementação é “invisível”; Programador usa TAD e cria uma lista de clientes e aplica operações

sobre ela, sem saber como ela é representada internamente.

Tipos Abstratos de Dados ou “TAD”: incluímos operações para a manipulação desses dados.

Funções que interagem com os dados. Ex:

- Criação da Estrutura; - Inclusão de um Elemento; - Remoção de um Elemento; - Acesso a um Elemento ; - Etc...

Encapsulamento e Segurança; Flexibilidade e Reutilização;

Exemplo: “TAD”Separa a Implementação da Aplicação.

Linguagem C - Descomplica

ListaEm geral as operações que podem ser realizadas em uma lista são:

- Inicializar- Inserir - Buscar- Acessar- Eliminar- Cadastro de funcionários- Tamanho da Lista- Destruir...

Exemplos: Lista Telefônica; Lista de clientes de uma agência bancária; Lista de setores de disco a serem acessados por um sistema operacional;

Lista Estática e Lista Dinâmica

Lista Estática:• O espaço da memória é Alocado no momento da Compilação;• Exige um número máximo de Elementos;• Acesso Sequencial;

Lista Dinâmica:• O espaço da memória é alocado em tempo de execução.• A lista cresce à medida que novos elementos são armazenados, e

diminui à medida que elementos são removidos.• Acesso encadeado.

Características Importantes: Consequência: As quatro primeiras operações são feitas em tempo constante. As

demais, porém, requererão mais cuidados.

Desvantagem: Movimentação quando eliminado/inserido elemento; Tamanho máximo pré –estimado;

Vantagem: Acesso direto indexado a qualquer elemento da lista Tempo constante para acessar o elemento i - dependerá somente do índice. Movimentação quando eliminado/inserido elemento; Tamanho máximo pré –estimado;

Quando usar: Listas pequenas Inserção/remoção no fim da lista Tamanho máximo bem definido

Lista Encadeada Dinâmica Representada por ponteiros.

~Quando utilizar essa “Lista”?Alocamos na memória ‘nó’ por ‘nó’

Características

Desvantagens: Necessidade de percorrer a lista para acessar um elemento. Acesso Indireto aos elementos.

Vantagens: Melhor utilização dos recursos de memória. Não precisa movimentar os elementos nas operações de inserção e

remoção.

Lista Duplamente Encadeada Um tipo de Lista onde cada elemento aponta para o seu sucessor e

antecessor da na “Lista”

Implementação: Algoritmo Cadastro de Funcionários.

   

Pilha (Stack)

A estrutura denominada pilha implementa o conceito de FILO (First-In, Last-Out) ;

Nessa estrutura, cada elemento armazena um ou vários dados e um ponteiro para o próximo elemento;

Aplicações: Inserção, consulta, remoção e esvaziar.

TOPO;

Uma Pilha é um tipo especial de “Lista” - Inserções e exclusões de elementos ocorrem apenas no inicio da “lista”

Aplicações

Verificação de parênteses.

Retirada de vagões de um trem.

Retirada de mercadorias em um caminhão de entregas.

Alocação dinâmica O espaço de memória é alocado em tempo de execução.

Alocação estática O espaço de memória é alocada no momento da compilação.

Aplicações: Análise de uma expressão matemática Avaliação de expressão pós-fixa

Calculadora pós fixada Um bom exemplo de aplicação de pilha é o

funcionamento das calculadoras da HP (Hewlett-Packard).

(1 – 2) * (4 + 5) assim: 1 2 – 4 5 + * .

Algoritmo Stack (Array Implemetation)

Algoritmo - Pilha Estática em um Vetor: https://www.cs.usfca.edu/~galles/visualization/StackArray.html

Pilha Dinâmica Cada elemento aponta para o seu sucessor na “pilha”.

Usa um ponteiro especial (ponteiro para ponteiro) para o primeiro elemento da “pilha ” e uma indicação de final de “pilha”

Assim as operações do TAD são as seguinte:

Inicializa Pilha;

Pilha Vazia;

Empilha;

Desempilha.

Algoritmo Stack (Linked List Implementaion)

Algoritmo - Pilha Dinâmica em um Vetor: https://www.cs.usfca.edu/~galles/visualization/StackLL.html

Grafos É um modelo matemático que representa relações entre objetos

Permite Representar: Cidades e Estradas Computadores e Conexões de Rede Pessoas e Relacionamentos

Representa pontos e ligações entre eles: Vértices e Arestas.

Problemas Reais

Grafos: É definido como um conjunto de vértices e um conjunto de

arestas que conectam qualquer par de vértices. G = (V,A)

V é o conjunto de vértices (não vazio). A é o conjunto de arestas. Se G(V,A), V = {1,2,3,4} A = ({1,2},{1,4},{2,3},{3,4}) Uma aresta sempre conecta dois vértices (v1,v2).

1

4

2

3

Grau de um vértice e Laço

• Grau de Entrada:• Arestas que chegam no vértice.

• Grau de Saída: • Arestas que partem do vértice.

Tipos de Grafos Representação de Grafos:

Como representar um grafo no computador? Linguagens C, Java...

Duas Abordagens são muito utilizadas: “Matriz de Adjacência” “Lista de Adjacência”

Matriz de Adjacência Algumas características:

Uma matriz NxN utilizada para armazenar o grafo, onde N é o número de vértices.

Alto custo computacional , (N^2). Uma aresta é representada por uma ”marca” na posição (i,j) da matriz.

Ideia de Representação:

Ideia de Representação:

Lista de Adjacência

Curiosidade Algoritmo de Dijkstra

Bibliografia http://pt.slideshare.net/mcastrosouza/grafos-representao

http://danielamaral.wikidot.com/introducao-a-teoria-dos-grafos

https://www.cs.usfca.edu/~galles/visualization/BST.html

http://cameraweb.ccuec.unicamp.br/watch_video.php?v=cwAwxa1z89

https://www.youtube.com/user/italogross

https://www.youtube.com/user/progdescomplicada

http://pt.slideshare.net/silvanooliveira/apostila-complementar-de-estrutura-de-dados-lista-pilha-fila-e-arvores-com-exerccios

http://usuarios.upf.br/~mcpinto/ed-tsi/ed_parte01.pdf

http://www.inf.ufes.br/~pdcosta/ensino/2012-1-estruturas-de-dados/slides/Aula9(listas).pdf