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 = registroA 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:
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 --------------------- LinkConsidere o arquivo ordenado por link abaixo, cuja chave de ordenação é o campo nome:
__________________________________________________
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:
- Inserir o registro no final do arquivo;
- 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;
- Fazer o link do registro a ser incluído apontar para o índice do primeiro registro maior;
- Fazer o link do registro anterior ao primeiro maior apontar para o novo registro.
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:
- Buscar o registro a ser excluído a partir de uma chave informada;
- Mudar o campo chave do registro a ser excluído para um valor não válido ("XXXXXXX", por exemplo);
- Fazer o link do registro anterior ao que será excluído apontar para o primeiro registro após ao que será excluído.
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.
