Estrutura de dados

Disponível somente no TrabalhosFeitos
  • Páginas : 6 (1410 palavras )
  • Download(s) : 0
  • Publicado : 28 de novembro de 2012
Ler documento completo
Amostra do texto
São Paulo, 2011

Algoritmos e estrutura de dados

Estrutura de Dados

28/11/2012

1

Sumário
Algoritmos e estrutura de dados

 Introdução  Conceitos gerais  Operações com pilhas  Notações infixa, pré-fixa, pós-fixa  Implementação de uma pilha

28/11/2012

2

Introdução
 Estruturas de dados: utilizam restrições de acesso aos dados.
Algoritmos e estrutura de dados

Benefícios:

 menos detalhes nas estruturas;
 implementações mais simples e flexíveis:

 menos operações suportadas.
 Estas restrições também conhecidas como políticas de acesso são:  Last In First Out (LIFO): utilizadas por estruturas do tipo Pilha.  First In First Out (FIFO): utilizadas por estruturas do tipo Fila.
28/11/2012 3

Conceitos gerais
 Estrutura do tipo Pilha:Algoritmos e estrutura de dados

 É uma lista linear;

 Inserções, retiradas e todos os acessos são feitos em apenas uma
das extremidades da lista;  Sua principal característica é:  O último item inserido é o primeiro item a ser retirado da lista.

28/11/2012

4

Conceitos gerais
Algoritmos e estrutura de dados

Primeiro elemento a sair

Último elemento a entrar

Último elementoa sair

Primeiro elemento a entrar

28/11/2012

5

Operações realizadas com pilhas
 Apenas duas operácões básicas estão envolvidas:
Algoritmos e estrutura de dados

 PUSH ou Empilha: Acrescentar no topo da pilha

 POP ou Desempilha: Retirar do topo da pilha
push (a) push (b) push (c) pop ( ) retorna c topo b a topo push (d)

a

topo

b a

topo

c b a

d b a

topo28/11/2012

6

Operações realizadas com pilhas
 PILHA: é uma lista do tipo seqüencial no qual:
Algoritmos e estrutura de dados

 O elemento 0 (ZERO) será definido como o fundo da pilha;

 Topo da pilha: TOPO índice que indica a 1ª posição livre da pilha.
 pilha vazia: TOPO = -1

 restrição: tamanho máximo definido (MAX - 1).

28/11/2012

7

Operações realizadas compilhas
 Outras operações utilizadas para manipular uma pilha:
Algoritmos e estrutura de dados

 Criar uma pilha vazia;

 Verificar se a pilha está vazia (retornará true ou false);
 Empilhar um item no topo da pilha;

 Desempilhar um item que está no topo da pilha;
 Verificar o tamanho atual da pilha.

28/11/2012

8

Operações realizadas com pilhas
Algoritmos e estrutura dedados

 Representação de uma pilha: Vetor.  Estrutura estática;  Limitação de tamanho – tamanho previamente conhecido;  Verificação máxima de elementos que podem ser armazenados.  Pode ser utilizada alocação dinâmica de memória para estruturas que

utilizam pilhas;

28/11/2012

9

Notação infixa, pré-fixa, pós-fixa
 Exemplo de aplicação de pilha:
Algoritmos e estrutura de dados

Calculadoras Hewlett-Packard (HP) – utilizam expressões pósfixadas:  Infixa: (1 - 2) * (4 + 5)

 pós-fixa: 1 2 – 4 5 + *.

28/11/2012

10

Notação infixa, pré-fixa, pós-fixa
 Expressão é composta de: operadores, operandos e delimitadores.
Algoritmos e estrutura de dados

 Operadores e respectivas relações de precedência

Expressão em notação infixa:  operadores separados pelosrespectivos operando:

(5 + 9) * 2 + 6 * 5

= 58

(5 + 9) * ((2 + 6) * 5) = 560
28/11/2012 11

Notação infixa, pré-fixa, pós-fixa
 Problema na avaliação: determinar ordem em que as operações devem
Algoritmos e estrutura de dados

ser realizadas.

 Notação infixa: a mudança na ordem é feita com o uso de parênteses.
 Notação polonesa reversa:

 Desenvolvida pelos poloneses.Nesta notação não utiliza-se
parênteses para definir uma outra ordem de avaliação das operações.

28/11/2012

12

Notação infixa, pré-fixa, pós-fixa
 Expressão em notação pré-fixa:
Algoritmos e estrutura de dados

 operadores antecedem os seus operandos: infixa (5 + 9) * 2 + 6 * 5 -> pós-fixa +*+592*65 = 58

(5 + 9) * ((2 + 6) * 5)

->

*+59*+265

=

560

28/11/2012...
tracking img