Trabalho Ind

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 i e insira na fila todas as cidades vizinhas de i que ainda não foram visitadas.

// Recebe uma matriz A que representa as interligações entre

// cidades 0,1,..,5: há uma estrada (de mão única) de i a j

// se e só se A[i][j] == 1. Devolve um vetor d que registra

// as distâncias da cidade c a cada uma das outras: d[i] é a

// distância de c a i.

int *distancias (int A[][6], int c)

{

int *d, j;

int fila[6], ini, fim;

d = mallocc (6 * sizeof (int));

for (j = 0; j < 6; ++j) d[j] = 6;

d[c] = 0;

ini = 0; fim = 1; fila[0] = c; // c entra na fila

while (ini != fim) {

int i, di;

i = fila[ini++]; // i sai da fila

di = d[i];

for (j = 0; j < 6; ++j)

if (A[i][j] == 1 && d[j] >= 6) {

d[j] = di + 1;

fila[fim++] = j; // j entra na fila

}

}

return d;

}

(Se fosse escrito semm os “++”, o código ficaria ligeiramente menos eficiente.) Para compreender o algoritmo (e provar que ele está correto), observe que as