Tabelas

Tabela é uma das estruturas de dados de fundamental importância para o desenvolvimento de software de sistema. Um de seus usos principais é na construção de tabelas de símbolos, amplamente utilizadas em compiladores e montadores. Tabelas são também amplamente utilizadas em sistemas operacionais para a manutenção de informação de apoio à execução de programas, como as tabelas de processos e as tabelas de arquivos.

Uma tabela é um agregado de elementos armazenados na forma de pares chave,valor, de tal forma que é possível ter acesso a valor (que pode eventualmente ser uma estrutura complexa) a partir da chave (Figura 2.2). Assim, deve ser possível obter o valor def a partir da especificação da chave $\beta$, ou o valor xyz a partir de $\zeta$.

Figura: Visão conceitual de uma tabela.

Em uma tabela de símbolos, a chave é usualmente o nome de uma variável e o valor é o conjunto de informações sobre a variável, tais como o seu tipo, endereço de memória e local de definição. Já em uma tabela de arquivos, a chave pode ser um identificador inteiro (por exemplo, o terceiro arquivo aberto pelo processo) e o valor o conjunto de informaçòes sobre o arquivo, tais como a posição corrente no arquivo.

Sob o ponto de vista funcional, a operação essencial associada a uma tabela é a busca de um valor a partir da especificação de uma chave:

GETVALUE(tabela,chave)

retorna o valor correspondente à chave especificada, se esta estiver presente na tabela; caso contrário, retorna uma indicação (por exemplo, um valor nulo) de que a chave não existe na tabela indicada.

Caso a tabela seja estática, ou seja, tenha um conteúdo que é determinado no momento da construção da tabela e não é alterado durante seu processamento, essa é a única operação definida para a manipulação da estrutura de dados, pois tais tabelas são utilizadas exclusivamente para consultas. Exemplos de tabelas desse tipo são as tabelas que descrevem as instruções de um processador, usadas em montadores.

Para a manipulação de tabelas que podem ter seu conteúdo construído e modificado ao longo da execução de um programa faz-se necessário definir outras operações, tais como:

INSERT(tabela,chave,valor)

é o procedimento para inserir uma nova informação na tabela;

REMOVE(tabela,chave)

é o procedimento para retirar da tabela o elemento que tem a chave especificada.