Conceitos lineares, listas, FIFO, FILO, seus ponteiros, ordens de inclusão, de exclusão e de pesquisa

SUMÁRIO

1 INTRODUÇÃO 3

2 LISTAS LINEARES 4

2.1 FIFO 4

2.1.1 Aplicações FIFO 4

2.1.2 Vantagens e Desvantagens do FIFO 5

2.2 FILO 5

2.3 ALOCAÇÃO SIMPLISMENTE ENCADEADA 6

2.3.1 Exemplos de algoritmos para as operações de inserção e retirada de um elemento numa pilha com alocação contígua: 6

2.3.2 Exemplo de algoritmo para a operação de inserção de um elemento numa fila com alocação contígua: 7

2.3.3 Exemplo de algoritmo para a operação de retirada de um elemento numa fila com alocação contígua: 7

2.4 ALOCAÇÃO DUPLAMENTE ENCADEADA 8

2.4.1 Implementação de Algumas Operações de Lista Duplamente Encadeada Com Alocação Dinâmica 8

2.4.1.1 Inserção à direita de pont 9

2.4.1.2 Inserção à esquerda de pont 9

2.4.1.3 Eliminação à direita de pont 10

2.4.1.4 Eliminação do próprio pont 10

2.4.1.5 Busca em uma lista circular 10

3 ACID 12

3.1 TRANSAÇÕES 12

3.2 ATOMICIDADE 12

3.3 CONSISTÊNCIA 12

3.4 ISOLAMENTO 12

3.5 DURABILIDADE 13

3.6 IMPORTÂNCIA DO ACID PARA UM SGBD 13

4 BANCO DE DADOS RELACIONAL COM A PROGRAMAÇÃO ORIENTADA A OBJETOS 14

4.1 ORIENTAÇÃO A OBJETOS VS MODELO ENTIDADE RELACIONAMENTO 14

5 OBJECT RELATIONAL MAPPING (ORM) – MAPEAMENTO DE OBJETO RELACIONAL 15

5.1 FERRAMENTAS PARA FAZER ORM (OBJECT RELATIONAL MAPPING) 18

5.1.1 JPA e Hibernate 18

6 HERANÇA E POLIMORFISMO 19

6.1 HERANÇA 19

6.1.1 Diagrama de Classe (Herança) 19

6.2 POLIMORFISMO 20

6.2.1 Diagrama de Classe (Polimorfismo) 21

7 CONCLUSÃO 22

REFERÊNCIAS 23

1 INTRODUÇÃO

Neste trabalho será abordada toda a matéria do 3º Semestre, dentro deste contexto serão apresentados os conceitos de listas lineares, FIFO, FILO, seus apontadores, ordens de inclusão, exclusão e pesquisa. Definirei também os conceitos de alocação simplesmente encadeada, alocação duplamente encadeada, com representações gráficas das duas.

Em relação a banco de dados, definirei os conceitos das propriedades ACID de uma transação e sua importância para um SGBD; e serão apresentadas duas ferramentas para se fazer ORM, bem como a explanação sobre o que é ORM e seus paradigmas.

No que tange a UML será mostrado os conceitos de polimorfismo e herança, bem como exemplos que os representem em diagramas de classe.

2 LISTAS LINEARES

Lista Linear é a estrutura que permite representar um conjunto de dados afins, de forma a preservar a relação de ordem linear de seus elementos.

Exemplos diários de listas lineares:

- Letras de uma palavra

- Palavras de uma frase

- Pessoas esperando ônibus

2.1 FIFO

As listas são amplamente utilizadas em programação para implementar filas de espera. Em uma fila de tipo FIFO os elementos vão sendo colocados na fila e retirados (ou processados) por ordem de chegada. A ideia fundamental da fila é que só podemos inserir um novo elemento no final da fila e só podemos retirar o elemento do início.

Como exemplo de aplicação para filas, pode-se citar a fila de processos de um sistema operacional. Nela, é estabelecido um tempo a ser usado por cada um dos processos. Se durante a execução de um processo o tempo passa de a, este é posto na fila e o processo seguinte é executado. Se o processo seguinte não terminar de ser executado no tempo, ele é posto na fila e o processo subsequente é executado, e assim por diante até todos os processos serem executados.

2.1.1 Aplicações FIFO

Os algoritmos FIFO's são comumente usados em circuitos eletrônicos de buffer e controle de fluxo, que vai desde o hardware até o software. Na forma de um hardware o FIFO consiste basicamente de um conjunto de ler e escrever ponteiros, armazenamento e lógica de controle. Armazenamento pode ser SRAM, flip-flops, fechos ou qualquer outra forma adequada de armazenamento. Para o FIFO, de tamanho não trivial, uma SRAM de porta dupla geralmente é utilizada quando uma porta é usada para a escrita e a outra para leitura.

O FIFO síncrono aonde o mesmo clock é usado para leitura e escrita. Um FIFO assíncrono utiliza diferentes relógios para leitura e escrita. Uma aplicação comum de um FIFO assíncrono utiliza um código de Gray (código binário refletido), ou qualquer unidade de código à distância, para ler e escrever os ponteiros para garantir a geração de bandeira confiável. Uma nota mais preocupante é que se deve necessariamente usar a aritmética de ponteiro para gerar bandeiras para implementações assíncronas FIFO. Por outro lado, pode-se usar a abordagem de um balde "de fuga" ou a aritmética de ponteiro para gerar bandeiras nas implementações síncronas FIFO.

Exemplos de sinalizadores de status FIFO incluem: cheios, vazios, quase cheio, quase vazio, etc.

2.1.2 Vantagens e Desvantagens do FIFO

 Vantagens:

• O mais simples entre os processos de escalonamento;

• Todos os processos tendem a serem atendidos.

 Desvantagens:

• Muito sensível à ordem de chegada;

• Se