Atividade Aberta

1. Monte um quadro comparativo com as principais características (inserção – pesquisa – remoção) de cada arquivo visto no material de aula. Arq. Sequencial, Arq. Sequencial Indexado, Arq. Indexado e Arq. Aleatório.

Tipo de Arquivo	Inserção	Pesquisa	Remoção
Arq. Sequencial	Ordem física deve coincidir com a ordem lógica. Registros devem ser inseridos em ordem de chave no arquivo. A inserção direta teria um custo muito alto, pois seria necessário identificar a posição correta de inserção, e movimentar todos os demais registros para uma posição posterior gerando o local para inserção de determinado registro. A alternativa para minimizar este custo é inserir os registros em ordem numa área temporária e em determinado momento intercalar o arquivo com esta área temporária.	Pesquisa é feita sequencialmente no arquivo pela chave. Abre-se o arquivo apontando para o início. Enquanto não for o final do arquivo, pesquisa-se pela chave, registro por registro.	A remoção direta também teria um custo muito alto, pois seria necessário movimentar todos os demais registros posteriores ao registro a ser removido para uma posição anterior. A alternativa para minimizar este custo é inserir uma marca de remoção no registro desejado. Em determinado momento, faz-se a atualização do arquivo. Abre-se o arquivo apontando para o início. Enquanto não for o final do arquivo, lê registro por registro verificando se possui ou não a marca de exclusão. Se não possui, copia este registro para um arquivo novo, se possui a marca, pula para o próximo registro. Ao final do procedimento, renomeia o arquivo novo com o nome do arquivo original e apaga o arquivo que contém registros com marca de exclusão.
Arq. Seq. Indexado	Os registros são gravados da mesma forma que no Arquivo Sequencial. A diferença é que, além da inserção do registro no arquivo, faz-se um controle dessas inserções numa estrutura de índice. O índice é gerado em blocos com a informação da chave e da posição que marca o início de cada bloco. A nova inserção neste tipo de arquivo é feita num arquivo temporário mantendo-se a ligação entre os registros de um mesmo bloco. Em determinado momento escolhido pelo programador, faz-se a junção do arquivo original com o arquivo de extensão. Depois deste processo, é necessário refazer o índice.	Para pesquisar determinado registro neste arquivo, buscas e inicialmente o bloco onde o registro está inserido, ou seja, busca-se primeiro no índice. Identificando o bloco do registro procurado, acessa a posição do primeiro registro desse bloco diretamente (pesquisa aleatória – abre arquivo e acessa diretamente a posição indicada no índice), e depois faz a busca sequencial nesse bloco	A exclusão neste tipo de arquivo também é feita utilizando a marca de exclusão. Em determinado momento, faz-se a atualização do arquivo da mesma forma que no Arquivo Sequencial.
Arq. Indexado	Neste tipo de arquivo, os registros são gravados sempre no final do arquivo, sem necessidade de ordenação por nenhum atributo. Além da inserção no arquivo, faz-se a inserção no índice. No índice e inserida apenas a chave do registro e a posição do mesmo no arquivo. O índice pode ser implementado em qualquer estrutura de dados. Uma boa opção seria a árvore binária, já que, a pesquisa na mesma é muito eficiente (log n).	A pesquisa é feita primeiramente no índice. Ao identificar a chave no índice, abre o arquivo e acessa a posição do arquivo indicada diretamente. O custo da pesquisa é um acesso ao arquivo (quando a chave for encontrada no índice ou nenhum, quando a chave não for encontrada).	A exclusão neste tipo de arquivo também é feita utilizando a marca de exclusão, que consiste numa informação adicional ao registro de controle de exclusão. Depois, (em determinado momento escolhido pelo programador), faz-se a varredura completa no arquivo transcrevendo os registros sem marca de exclusão para um arquivo novo. Ao final, renomeia o arquivo novo com o nome do arquivo original, apaga o arquivo anterior (arquivo com registros com marca de exclusão) e atualiza o índice.
Arq. Aleatório	Neste tipo de arquivo, os registros são gravados na posição indicada por uma função Hash. Este tipo de arquivo é formado apenas pela área de dados e pela função Hash. Pode acontecer de dois ou mais registros serem direcionado para uma mesma posição de inserção. Dá-se o nome de colisão para este fato. Para tratamento da colisão, existem algumas técnicas. Uma delas, e a mais simples, são chamadas de próximo vago, que consiste em, ocorrendo a colisão, procurar a próxima posição vaga para inserção.	A pesquisa é feita aplicando a função Hash na chave a ser pesquisada. A posição gerada pela função hash deve ser acessada diretamente no arquivo. Verifica-se se o registro procurado é o registro cadastrado nesta posição do arquivo. Se não for, verificasse sequencialmente no arquivo pois pode ter acontecido uma colisão e o registro ter sido direcionado para outra posição	A exclusão neste tipo de arquivo também é feita utilizando a marca de exclusão, que consiste numa informação adicional ao registro de controle de exclusão. Uma nova inserção direcionada para uma posição, com registro com marca de exclusão, pode ser feita nessa posição, sobrescrevendo o registro com a marca. Dessa forma, para esse tipo de arquivo não é necessária a atualização do arquivo excluindo-se os registros com marca, pois estas posições podem ser reaproveitadas nas novas inserções.

1. Desenvolva o algoritmo para Inserção, Pesquisa e Remoção no Arquivo Sequencial. Justifique a escolha da chave.

Inserção:

procedimento atualizarArquivoSequencial (cadastro dados[])

{

abrir Arquivo Sequencial Original (ponteiro de leitura no início do arquivo);

criar Arquivo de Atualização (ponteiro de escrita no início do arquivo);

enquanto (não for o final do Arquivo Sequencial Original e não for o final do vetor)

{

se (dados.chave do registro do Arquivo Sequencial Original < dados.chave do vetor) //processo de intercalação

{

gravar dados do Registro do Arquivo Sequencial Original no Arquivo de Atualização);

ler próximo registro do Arquivo Sequencial Original);

...