Atividade 03 - Vetor de apontadores

Um vetor de apontadores é uma estrutura formada por campos homogêneos que guardam registros. Cada registro possui um campo inteiro, o qual indica a posição do próximo registro no vetor. Esse campo inteiro (também chamado de apontador) permite a ordenação lógica dos registros no vetor, facilitando a operação de inclusão, já que não há necessidade de movimentação de registros.

A implementação de um vetor de apontadores em memória secundária é feita utilizando arquivos ordenados por links. Os mesmos registros do vetor são também utilizados no arquivo, com a diferença de que o campo inteiro (denominado link no arquivo) indica a posição física do próximo registro no arquivo.


1) Composição física dos registros
Os registros de arquivo ordenado por link devem possuir o campo link para indicar a posição do próximo registro, um campo chave usado para ordenar logicamente os registros e quaisquer outros campos de dados. Uma declaração geral seria:

TipoRegistro = registro
Chave: TipoChave;
Link: Inteiro;
{outros componentes}
fimRegistro

2) Exemplos
Considere o arquivo ordenado por link abaixo, cuja chave de ordenação é o campo nome:

Ind. ------- Nome -------------- Dados --------------------- Link
__________________________________________________
0 ----------------------------------- ------------------------- 3
1 ---------- Pedro ----------- {outros dados} ---------------- -1
2 ---------- Carlos -----------{outros dados} ----------------- 1
3 ---------- Ana -------------{outros dados} ----------------- 2
__________________________________________________

Percebe-se que o registro índice zero não é utilizado para armazenar dados do arquivo, mas somente o link do registro inicial. Dessa forma, quando uma busca é realizada no arquivo, o registro índice zero indica por qual registro começar, no caso o registro índice 3, cujo nome é Ana.

Ana por sua vez possui o link para o próximo registro, que no caso é Carlos. Este possui link para o próximo, Pedro, que possui link igual a -1, já que não há logicamente mais registros depois dele.

É importante notar que embora os registros estejam desordenados fisicamente, há uma ordenação lógica, graças ao campo link.


3) Descrição da operação de inclusão
Considerando o exemplo anterior, vamos incluir o registro a seguir:
Ind. ------- Nome -------------- Dados --------------------- Link
__________________________________________________
----------- Beto ----------- {outros dados} ----------------
__________________________________________________

Para incluir esse registro, deve-se realizar os seguintes passos:

1. Inserir o registro no final do arquivo;
2. Buscar no arquivo ordenado por link (através dos links) o primeiro registro cuja chave é maior que a chave do registro a ser incluído;
3. Fazer o link do registro a ser incluído apontar para o índice do primeiro registro maior;
4. Fazer o link do registro anterior ao primeiro maior apontar para o novo registro.

Dessa forma, incluir-se-ia Beto no final do arquivo. Depois seria necessário percorrer o arquivo, passando por Ana e encontrando Carlos como o primeiro maior. O link de Beto então apontaria para o índice de Carlos (no caso 2), e o link de Ana apontaria para o índice de Beto (no caso 4). O resultado seria:

Ind. ------- Nome -------------- Dados --------------------- Link
__________________________________________________
0 ----------------------------------- ------------------------- 3
1 ---------- Pedro ----------- {outros dados} ---------------- -1
2 ---------- Carlos -----------{outros dados} ----------------- 1
3 ---------- Ana -------------{outros dados} ----------------- 4
4 ---------- Beto ------------ {outros dados} ----------------- 2
__________________________________________________


4) Descrição da operação de exclusão:
A operação de exclusão pode ser de dois tipos: lógica ou física. Será descrita a exclusão lógica, já que normalmente antes de uma exclusão física são realizadas várias exclusões lógicas. Devem-se seguir os seguintes passos para a exclusão lógica:

1. Buscar o registro a ser excluído a partir de uma chave informada;
2. Mudar o campo chave do registro a ser excluído para um valor não válido ("XXXXXXX", por exemplo);
3. Fazer o link do registro anterior ao que será excluído apontar para o primeiro registro após ao que será excluído.

Dessa forma, para excluir Beto deve-se percorrer o arquivo até encontrar o registro com o nome Beto e alterar o nome para um valor inválido, "XXXXXXXX" nesse caso. Em seguida o registro anterior a Beto (no caso Ana) apontaria para o primeiro registro após Beto, que seria Carlos. O resultado seria:


Ind. ------- Nome -------------- Dados --------------------- Link
__________________________________________________
0 ----------------------------------- ------------------------- 3
1 ---------- Pedro ----------- {outros dados} ---------------- -1
2 ---------- Carlos -----------{outros dados} ----------------- 1
3 ---------- Ana -------------{outros dados} ----------------- 2
4 -------- XXXXXX --------- {outros dados} ----------------- 2
__________________________________________________

Vale ressaltar que mesmo Beto permanecendo no arquivo, ele nunca será acessado se a busca for realizada pelos links.

Costuma-se realizar uma exclusão física após certo número de exclusões lógicas, pois deixar no arquivo os registros excluídos logicamente consome espaço de armazenamento desnecessário.

Atividade 04

Resolução da questão: "Código para registrar a produção diária de um dado artesão"

leia(artesao);
nomeArq <- artesao+'.dat';
associar(arqLogico,nomeArq);
abrir(arqLogico);
posicione(arqLogico,tamArquivo(arqLógico));
leia(regArt.dia);
leia(regArt.hora);
leia(regArt.totalPecas);
leia(regArt.obs);
escreva(arqLógico,regArt);
fechar(arqLógico);