Algoritmos e Estrutura de Dados

SISTEMA DE ENSINO PRESENCIAL CONECTADO

CURSO SUPERIOR DE TECNOLOGIA EM ANÁLISE E DESENVOLVIMENTO DE SISTEMAS

xxxxxxxxxxxxxxx

PRODUÇÃO TEXTUAL INTERDISCIPLINAR

Alexânia

2012

xxxxxxxxxxxxxxxxxxx

PRODUÇÃO TEXTUAL INTERDISCIPLINAR

Trabalho apresentado ao curso de Análise e desenvolvimento de Sistemas da UNOPAR - Universidade do Norte do Paraná como requisito parcial para a obtenção de média bimestral nas disciplinas de: Análise de Sistemas II, Desenvolvimento Orientado a Objetos I, Banco de Dados II, Algoritmos e Estrutura de Dados.

Prof.ª Polyana P. Gomes Fabris

Prof. Marcio Chiaveli

Prof. Roberto Nishimura

Prof. Merris Mozer

Alexânia

2012

INTRODUÇÃO

Uma estrutura de dado armazena dados na memória do computador a fim de permitir o acesso eficiente dos mesmos. A maioria das estruturas de dados consideram a memória primária (a chamada RAM) como pilhas, filas, árvores binárias de busca, árvores AVL e árvores rubro-negras. Outras são especialmente projetadas e adequadas para serem armazenadas em memórias secundárias como o disco rígido, e.g. B-árvores. Uma estrutura de dado bem projetada permite a manipulação eficiente, em tempo e em espaço, dos dados armazenados através de operações específicas. Um conceito relacionado com a estrutura de dado é o tipo abstrato de dados.

Uma lista linear é um conjunto de n elementos (de informações) x1, x2, ..., xn, cuja propriedade estrutural envolve as posições relativas de seus elementos. Supondo n > 0, temos x1 é o primeiro elemento para 1 < k < n, xk é precedido por xk−1 e seguido por xk+1 xn é o último elemento. Algumas operações que podemos querer realizar sobre listas lineares: Ter acesso a xk , k qualquer, a fim de examinar ou alterar o conteúdo de seus campos.Inserir um elemento novo antes ou depois de xk Remover xk.Colocar todos os elementos da lista em ordem. Combinar 2 ou mais listas lineares em uma só. Quebrar uma lista linear em duas ou mais. Copiar uma lista linear em um outro espaço. As três primeiras operações, para k = 1 e k = n, casos considerados importantes e as listas lineares recebem nomes como pilha ou fila conforme a maneira essas operações são realizadas. A operação de ordenação é extensivamente estudada em cursos de Análise de Algoritmos.

A maneira de implementar listas lineares depende da classe de operações mais frequentes. Não existe, em geral, uma única implementação para a qual todas as operações são eficientes. Por exemplo, não existe uma implementação para atender às seguintes duas operações de maneira eficiente: 1 ter acesso fácil ao xk , para k qualquer 2 inserir ou remover elementos em qualquer posição da lista linear. A operação 1 fica eficiente se a lista é implementada em um vetor (array) em alocação seqüencial na memória. Já para a operação 2 é mais adequada a alocação encadeada ou ligada, com o uso de apontadores.

OBJETIVO

Este trabalho sera realizado com base em pesquisa bibliografica, que abordara temas relacionados à Estrutura de dados do tipo Fila, seus apontadores e estrutura, assim como, suas ordens para inclusão, exclusão e pesquisa. Neste contexto, será enfatizado à Estrutura de dados do tipo Pilha e mencionado quais são apontadores de cada estrutura, suas ordens para inclusão, exclusão e pesquisa. Não esquecendo também a alocação simplesmente encadeada e aalocação duplamente encadeada. Sera conceituado as propriedades ACID de uma transação. Assim como, Como usar um banco de dados relacional com a programação orientada a objetos. O que significa ORM mapeamento objeto relacional, e as ferramentas necessarias para faze-lo. Por fim será mostrado as vantagens do Diagrama de Atividades, quando se deve usar Decisão e Ponto de Merge, e a Concorrência de Bifurcação e União.

SUMÁRIO

INTRODUÇÃO 3

OBJETIVO 4

1. ESTRUTURA DE DADOS DO TIPO FILA SEUS APONTADORES DE ESTRUTURA, SUAS ORDENS PARA INCLUSÃO, EXCLUSÃO E PESQUISA. 7

1.1. FILAS - QUEUE .....................................................................................................7

2. ESTRUTURA DE DADOS DO TIPO PILHA E QUAIS SÃO APONTADORES DE CADA ESTRUTURA, SUAS ORDENS PARA INCLUSÃO, EXCLUSÃO E PESQUISA 10

2.1. IMPLEMENTAÇÃO EM UM VETOR ...........................................................10

2.1.1. APLICAÇÃO: PARÊNTESES E COLCHETES ........................................11

2.1.2. OUTRA APLICAÇÃO: NOTAÇÃO POLONESA .........................................13

2.2. ALOCAÇÃO SIMPLESMENTE ENCADEADA. 17

2.3. ALOCAÇÃO DUPLAMENTE ENCADEADA. 18

3. CONCEITOS