TrabalhosGratuitos.com - Trabalhos, Monografias, Artigos, Exames, Resumos de livros, Dissertações
Pesquisar

Trabalho Ind

Por:   •  30/5/2013  •  3.496 Palavras (14 Páginas)  •  611 Visualizações

Página 1 de 14

INTRODUÇÃO

Neste trabalho apresentaremos os conteúdos estudados no semestre, sobre Banco de Dados II, Analise de Sistemas II, Algoritmo e Estrutura de Dados, Desenvolvimento Orientado a Objeto. Sobre as quais trataremos ao decorrer do trabalho sobre listas lineares, suas definições , conceitos de FIFO, FILO, seus apontadores suas ordens para inclusão, exclusão e pesquisa, com exemplos do cotidiano e da informática de lista lineares .Os conceitos de alocação simplesmente encadeada, alocação duplamente encadeada, representações gráficas das duas alocações.. Bem como também iremos abordar as propriedades Acide (Atomicidade, Confiabilidade, Integridade e Durabilidade), das transações no Banco de Dados. As vantagens de se utilizar a Orientação a Objetos e como pode ser representado no diagrama de classe.

DESENVOLVIMENTO

2.1- FILAS

Uma fila é uma estrutura de dados que admite inserção de novos elementos e remoção de elementos antigos. Mais especificamente, uma fila (=queue) é uma estrutura sujeita à seguinte regra de operação: sempre que houver uma remoção, o elemento removido é o que está na estrutura há mais tempo. Em outras palavras, o primeiro objeto inserido na fila é também o primeiro a ser removido. Essa política é conhecida pela sigla FIFO (=First-In-First-Out).

A ) Implementação em um vetor

Suponha que nossa fila FIFO mora em um vetor fila[0..N-1]. Suponha que os elementos do vetor são inteiros (isso é só um exemplo; os elementos da fila poderiam ser quaisquer outros objetos). A parte do vetor ocupada pela fila será

fila[ini..fim-1].

0 ini fim N-1

O primeiro elemento da fila está na posição ini e o último na posição fim-1. A fila está vazia se ini==fim e cheia se fim==N. Para remover (=dalete = de-queue) um elemento da fila basta fazer

x = fila[inii++];

Isso equivale ao par de instruções "x=fila[ini]; ini+=1;", nesta ordem. É claro que você só deve fazer isso se tiver certeza de que a fila não está vazia. Para inserir (=insert =enqueue) um objeto y na fila basta fazer

fila[fim++] = y;

Note como a coisa funciona bem mesmo quando a fila está vazia. É claro que você só deve inserir um elemento na fila se ela não estiver cheia; caso contrário a fila transborda (transbordar = to overflow). Em geral, a tentativa de inserir em uma fila cheia é uma situação excepcional, que indica um mau planejamento lógico do seu programa.

2.2- Aplicação: distâncias

Eis uma aplicação clássica do conceito de fila. Imagine 6 cidades numeradas de 0 a 5 e interligadas por estradas de mão única. (É claro que você pode trocar "6" pelo seu número favorito.) As ligações entre as cidades são representadas por uma matriz A da seguinte maneira:

A[i][j] vale 1 se existe estrada da cidade i para a cidade j

e vale 0 em caso contrário. Suponha que a matriz tem zeros na diagonal, embora isso não seja importante. Exemplo:

0 1 2 3 4 5

0 0 0 0 0 0 0

1 1 0 0 0 0 0

2 0 1 0 0 1 0

3 0 0 1 0 1 0

4 1 0 0 0 0 0

5 0 1 0 0 0 0

A distância de uma cidade c a uma outra j é o menor número de estradas que devo percorrer para ir de c a j. Nosso problema: dada uma cidade c,

determinar a distância de c a cada uma das demais cidades.

As distâncias serão armazenadas em um vetor d: a distância de c a j será d[j]. Que fazer se é impossível chegar de c a j? Poderíamos dizer nesse caso que d[j] é infinito. Mas é mais limpo e prático dizer que d[j] vale 6, pois nenhuma distância "real" pode ser maior que 5. Se adotarmos c igual a 3 no exemplo acima, teremos d iguala

0 1 2 3 4 5

2 2 1 0 1 6

Eis a ideia de um algoritmo que usa o conceito de fila para resolver nosso problema: uma cidade é considerada ativa se já foi visitada mas as estradas que começam nela ainda não foram exploradas; mantenha uma fila das cidades ativas; em cada iteração, remova da fila uma cidade

...

Baixar como (para membros premium)  txt (18.2 Kb)  
Continuar por mais 13 páginas »
Disponível apenas no TrabalhosGratuitos.com