Tendo
completado três assuntos básicos sobre o tema, a noção do que realiza uma
tabela de dispersão, como a função de espalhamento distribui elementos e o
tratamento de colisão com encadeamento, será apresentado um código que utiliza
um exemplo que também foi discutido anteriormente.
Como pré-requisito, recomenda-se
a leitura de lista encadeada genérica parte 1 e parte 2, para evitar prolongar
o assunto, será utilizado o mesmo aplicativo que carrega as palavras de um
texto, alterando o mesmo para utilizar uma tabela de dispersão em vez de uma
lista encadeada.
De
forma bem simples, tem-se o tipo de dado SLINK utilizado pela lista encadeada,
que vem a ser no nó da lista, portanto a tabela que precisa ser criada será um
vetor deste tipo.
#define
TABLE_PRIME_SIZE 1999 // numero primo
SLINK m_ptrTable[TABLE_PRIME_SIZE];
|
Com a estrutura de dados que
gerencia a lista encadeada precisando de uma pequena alteração para ser
utilizada, no exemplo a seguir temos:
SLIST *L1;
char
strWord[64];
WORD wIndex;
// configura a estrutura de dados da lista encadeada
L1
= CreateLList( CreateData,
DeleteData,
DuplicatedNode,
NodeDataCmp);
// calcular a codificacaoh hash
wIndex =
HashDiv(HashPjw("Tabela"));
// insere na tabela
L1->slkHead =
m_ptrTable[wIndex];
AddNodeAscend(L1,
"Tabela");
m_ptrTable[wIndex] = L1->slkHead;
|
Com um mínimo de código
adicionado, modificou-se o exemplo de lista encadeada para uma tabela de
dispersão.
Isto se deve em parte pela
alteração do endereço de inicio de lista, quando se cria uma lista encadeada a
variável L1->slkHead é inicializada através da função AddNodeAscend sempre que está encontra um valor nulo.
Portanto cada vez que apontamos
para uma posição com valor nulo na tabela com L1->slkHead =
m_ptrTable[wIndex] indica-se uma lista vazia para ser inicializada com AddNodeAscend.
TABLE
|
||||
. . .
|
HEAD
|
NULL
|
||
SLINK[16]
|
NULL
|
|||
SLINK[17]
|
NULL
|
|||
SLINK[18]
|
NULL
|
|||
. . .
|
||||
A rotina AddNodeAscend
verifica se a variável de inicio de lista L1->slkHead foi
inicializada, sendo nula irá criar um nó e passar o endereço deste, portanto
após encontrar um endereço vazio cria o nó.
TABLE
|
||||
. . .
|
HEAD
|
0x1200
|
||
SLINK[16]
|
NULL
|
|||
SLINK[17]
|
NULL
|
|||
SLINK[18]
|
NULL
|
|||
. . .
|
||||
Com L1->slkHead apontando para um nó valido, atualiza a tabela com o endereço de inicio de
lista com m_ptrTable[wIndex] = L1->slkHead.
TABLE
|
||||
. . .
|
HEAD
|
0x1200
|
||
SLINK[16]
|
NULL
|
|||
SLINK[17]
|
0x1200
|
|||
SLINK[18]
|
NULL
|
|||
. . .
|
||||
Conforme ocorre o
preenchimento da tabela, cada posição irá apontar para um inicio de lista,
sempre que a rotina encontrar um link valido irá percorrer até a posição
desejada e inserir o novo dado, como pode acontecer de ser um novo inicio de
lista, atualiza o endereço da tabela com o de inicio.
Declarar
uma global e utilizar no programa é uma péssima pratica de programação,
permitindo a situação de a variável ser modificada em qualquer local do
programa, que acaba ficando dependente da mesma, esse potencial de criar
dependências mutuas é ilimitado e acaba gerando uma complexidade crescente
conforme o código aumenta.
Para
efeitos de explicação utilizamos uma tabela declarada de tal maneira devido à
simplicidade, entretanto não se deve utilizar esta solução na pratica, para
corrigir este aspecto, segue abaixo as rotinas da tabela de dispersão que
complementam a de lista encadeada genérica.
O
arquivo de cabeçalho hashtab.h irá
incluir o TAD (tipo abstrato de dado) tabela de dispersão como um superconjunto
da TAD lista encadeada, conceito conhecido como herança na programação OO
(Orientada a Objetos) ao qual uma linguagem estruturada como C não oferece
suporte.
// uma estrutura de dados de uma tabela de dispersaoh encadeada
typedef struct tagSHASHTABLE
{
SLIST *ptrList; // lista
encadeada
SLINK *ptrTable; // tabela de
dispersão
int iSize; // tamanho da tabela
int ( * fDataLen )( void
* ); // tamanho do dado
}
SHASHTABLE;
|
Alem da
estrutura de gerenciamento da lista, temos a tabela, o tamanho da mesma e a
rotina especifica da aplicação que retorna o tamanho do dado, essa rotina é
necessária para calcular o espalhamento na tabela, durante a conversão do dado
em chave, é necessário saber o quanto da informação deve ser codificado.
Portanto
alem das rotinas de criar, apagar, comparar e tratar duplicado que fazem parte
do arquivo llapp.c, teremos a de
tamanho de dado.
int DataLen(void
*data)
{
return ( (int)
strlen( data ));
}
|
As rotinas abaixo fazem parte das
primitivas genéricas para tabela de dispersão encadeada, tais funções gerenciam
somente os acessos à tabela, sendo completamente independentes da aplicação e
não devem ser alteradas.
Função
|
InitHashTable
|
||||||||||||
Propósito
|
Cria e inicia uma estrutura de gerenciamento para tabela de dispersão
|
||||||||||||
Parâmetros
|
ponteiro para as funções especifica da lista
ponteiro para as funções especifica da tabela
|
||||||||||||
Retorno
|
ponteiro SHASHTABLE
pHT -> estrutura de dados
que gerencia tabela de dispersão
NULL - não conseguiu criar
a tabela
|
||||||||||||
Descrição
|
Cria uma estrutura de tabela de dispersão encadeada no tamanho
indicado e retorna um ponteiro da mesma. Em erro, retorna NULL. Esta função
aceita ponteiros para as cinco funções especificas e inicializa a estrutura
com elas.
|
SHASHTABLE
*InitHashTable(
void *( * fCreateData ) ( void * ),
BOOL ( * fDeleteData ) ( void * ),
int ( *
fDuplicatedNode ) ( SLINK, SLINK ),
int ( *
fNodeDataCmp ) ( void *, void *),
int iTableSize,
int ( *
fDataLen ) ( void * ) )
{
SHASHTABLE *pHT;
// cria a
estrutura de gerenciamento da tabela
pHT = (SHASHTABLE *) malloc(sizeof(SHASHTABLE));
// reserva a memoria da tabela
pHT->ptrTable = calloc(iTableSize, sizeof(SLINK));
// configura a
estrutura de dados da lista encadeada
pHT->ptrList = CreateLList( fCreateData,
fDeleteData,
fDuplicatedNode,
fNodeDataCmp);
// dados para
espalhamento
pHT->iSize = iTableSize;
pHT->fDataLen = fDataLen;
return (pHT); // devolve o enderecoh
}
|
Função
|
AddDataToTable
|
Propósito
|
Adiciona um nó em uma lista encadeada na tabela
|
Parâmetros
|
SHASHTABLE *pHT -> ponteiro
para estrutura de dados que trata uma tabela
void *pData -> dado a ser
inserido na tabela
|
Retorno
|
TRUE - adicionou na tabela um elemento
FALSE - não conseguiu inserir na tabela
|
Descrição
|
Adiciona um nó dentro de uma tabela de dispersão encadeada. Como o tipo de dado possui um gerenciador
de lista herdado, é preciso adaptar a lista em cima da tabela, portanto cada posição
da tabela se refere a um inicio de lista, para que as rotinas de lista tratem
corretamente, atualiza a variável inicio de lista para o apontamento da posição
da tabela e após o valor ser adicionado, atualizamos o apontamento na tabela
caso este tenha sido alterado.
|
BOOL AddDataToTable(SHASHTABLE *pHT, void *pData)
{
WORD wIndex;
// calcular a codificacaoh hash
wIndex =
HashData( pHT, pData );
// insere na tabela
pHT->ptrList->slkHead
= pHT->ptrTable[wIndex];
AddNodeAscend(pHT->ptrList,
pData);
// atualiza a
tabela, caso a informacaoh
// tenha sido
inserida no inicio
pHT->ptrTable[wIndex] =
pHT->ptrList->slkHead;
return
TRUE;
}
|
Função
|
FindNodeAscend
|
Propósito
|
Pesquisa na tabela de dispersão encadeada.
|
Parâmetros
|
SHASHTABLE *pHT -> estrutura de dados que gerencia a tabela
void *pData -> informação a ser comparada
|
Retorno
|
slkPCurr - aponta para o nó desejado na tabela
NULL - não encontrou o nó
|
Descrição
|
Encontra um nó, iniciando a busca na lista apontada pela posição
calculada na tabela, formata a informação para utilizar a rotina
FindNodeAscend
|
SLINK FindDataInTable(SHASHTABLE *pHT, void *pData)
{
WORD wIndex;
void *pInfo;
SLINK slk;
// calcula a codificacaoh hash
wIndex = HashData( pHT, pData );
// direciona
para tabela
pHT->ptrList->slkHead = pHT->ptrTable[wIndex];
// formata o dado para realizar a busca
pInfo = pHT->ptrList->fCreateData(pData);
slk =
FindNodeAscend(pHT->ptrList, pInfo);
// descarta o dado formatado
pHT->ptrList->fDeleteData(pInfo);
// retorna o
enderecoh na lista
return
slk;
}
|
Função
|
DelDataInTable
|
Propósito
|
Apaga um nó dentro da tabela de dispersão
|
Parâmetros
|
SHASHTABLE *pHT -> estrutura com as rotinas de busca e exclusão
void *pData -> informação a ser excluída
|
Retorno
|
TRUE - exclui o dado e
atualizou a tabela
FALSE - não era um dado valido p/ exclusa oh
|
Descrição
|
Após calcular a posição na tabela, formata o dado para buscar sua posição
na lista, caso tenha encontrado a informação desejada, elimina o nó
utilizando a função DeleteNode, para a função DeleteNode funcionar
corretamente é preciso atualiza as variáveis de gerenciamento da lista de
inicio e fim, com os valores apontados pela posição calculada da tabela, ao
fim da exclusão, atualiza o valor de apontamento na tabela.
|
BOOL DelDataInTable(SHASHTABLE *pHT, void
*pData)
{
WORD wIndex;
void *pInfo;
SLINK slk;
BOOL bOk;
// calcular a codificacaoh hash
wIndex =
HashData( pHT, pData );
// direciona
para tabela
pHT->ptrList->slkHead = pHT->ptrTable[wIndex];
// formata o dado para realizar a busca
pInfo = pHT->ptrList->fCreateData(pData);
slk =
FindNodeAscend(pHT->ptrList, pInfo);
// descarta o dado formatado
pHT->ptrList->fDeleteData(pInfo);
if (slk)
{
//
primeiro da lista
if
(slk->prior == NULL)
slk =
pHT->ptrList->slkHead;
//
ultimo da lista
if
(slk->next == NULL)
slk
= pHT->ptrList->slkTail;
// elimina o dado
bOk = DeleteNode(pHT->ptrList,
slk);
// atualiza tabela
pHT->ptrTable[wIndex]
= pHT->ptrList->slkHead;
}
else
bOk =
FALSE;
return bOk;
}
|
Função
|
EndHashTable
|
Propósito
|
Apaga a estrutura de gerenciamento da tabela de dispersão e suas
listas encadeadas
|
Parâmetros
|
SHASHTABLE *pHT -> estrutura de dados que gerencia tabela de dispersão
|
Retorno
|
TRUE - liberou toda a memória
utilizada pela tabela
FALSE - não conseguiu apagar a lista encadeada
|
Descrição
|
Após verificar que se trata de uma tabela valida, percorre a mesma,
apagando os nós individualmente, por fim, libera a memória usada pela própria
estrutura de gerenciamento da lista encadeada e da tabela de dispersão.
|
BOOL EndHashTable(SHASHTABLE *pHT)
{
int iCnt;
SLINK pCurr,
pBak;
if (pHT == NULL)
return FALSE;
// percorre
cada posicaoh da tabela
for (iCnt =
0; iCnt < pHT->iSize; ++iCnt)
{
pCurr =
pHT->ptrList->slkHead = pHT->ptrTable[iCnt];
if (pCurr != NULL)
{
//
percorre a lista apagando todos os nohs
while ( pCurr
!= NULL )
{
pBak
= pCurr;
pCurr
= pCurr->next;
if (pCurr == NULL)
pHT->ptrList->slkTail
= pBak;
DeleteNode(pHT->ptrList,
pBak);
}
}
}
// libera a
estrutura que trata a lista encadeada
free(pHT->ptrList);
// libera a
estrutura que trata a tabela
free(pHT);
return
TRUE;
}
|
Para o
calculo de índice na tabela, foi realizada uma alteração no modelo apresentado
na postagem de espalhamento, se utiliza a rotina especifica que retorna o
tamanho da informação que será processada para adquirir a chave. Caso a tabela
definida seja par, escolhe uma função diferente para a transformação da chave
em índice.
PRIVATE DWORD HashElf ( const
BYTE *ptrData, int iLen )
{
DWORD dwKey = 0,
dwTmp;
for ( ; iLen > 0; --iLen )
{
dwKey = ( dwKey << 4 ) +
*ptrData++;
if ( dwTmp
= dwKey & 0xF0000000 )
dwKey
^= dwTmp >> 24;
dwKey
&= ~dwTmp;
}
return dwKey;
}
WORD HashData(SHASHTABLE *pHT, void
*pData)
{
DWORD dwKey;
WORD wIndex;
WORD ( * fHash )
(DWORD, int);
// trasnforma os dados em uma chave
// parte
especifica do codigo dependente dos dados escolhidos
dwKey = HashElf(pData, pHT->fDataLen(pData));
// se tamanho da tabela for potencia de 2
fHash = (pHT->iSize & 1) ? HashDiv : HashMul;
// calcular o indice
wIndex = fHash(
dwKey , pHT->iSize );
return wIndex;
}
|
Por
fim, no arquivo main.c teremos a
aplicação que demonstra como criar e inicializar uma tabela de dispersão e
inserir as palavras de um texto na tabela.
#define
TABLE_PRIME_SIZE 997 // numero primo
int main(int argc, char
*argv[])
{
FILE *fin;
char
strWord[64];
char *ptrStr;
int iChar;
SHASHTABLE *sHT;
fin =
fopen(argv[1], "rt");
// cria uma
estrutura de dados de dispersao encadeada
sHT = InitHashTable( CreateData,
DeleteData,
DuplicatedNode,
NodeDataCmp,
TABLE_PRIME_SIZE,
DataLen);
// comecah a processar o arquivo
while
(!feof(fin))
{
//
percorre o texto pulando os espacosh e pontuncaoesh
do {
iChar
= getc(fin);
} while ( iChar
!= EOF &&
(isspace(iChar)
|| ispunct(iChar)));
// tendo um caracter valido
//
comecah a montar a palavra
ptrStr = strWord;
do {
*ptrStr++
= iChar;
iChar
= getc(fin);
} while ( iChar
!= EOF &&
!isspace(iChar)
&&
!ispunct(iChar)
);
// fim do arquivo, sai do loop
if
(iChar == EOF)
break;
// fecha
a palavra com o terminador nulo
*ptrStr = '\0';
// todos
os caracteres em maiuscula
ptrStr = strupr(strWord);
// insere na tabela
AddDataToTable(sHT,
ptrStr);
} // while
(!feof(fin))
fclose(fin);
// mostra as estatistica de uso da tabela
ListTableStat(sHT);
// encerra a
EndHashTable(sHT);
return (EXIT_SUCCESS);
}
|
Ao final chama a rotina ListTableStat que mostra as estatísticas de uso da tabela.
C:\Projects\ExternalChaining>ExternalChaining
244.txt
16 listas encadeadas com 1 nohs
51 listas encadeadas
com 2 nohs
102 listas encadeadas com
3 nohs
148 listas encadeadas com
4 nohs
176 listas encadeadas com
5 nohs
160 listas encadeadas com
6 nohs
125 listas encadeadas com
7 nohs
87 listas encadeadas
com 8 nohs
62 listas encadeadas
com 9 nohs
36 listas encadeadas com
10 nohs
21 listas encadeadas com
11 nohs
6 listas encadeadas com
12 nohs
3 listas encadeadas com
13 nohs
5687 Nohs em 993 listas encadeadas
Tamanho da tabela de dispersão = 997
Tamanho medio das listas = 5.727090
Recipientes ocupados = 0.995988
Coeficiente de carregamento = 5.704112
|
Como sugestão para o teste acesse
o Projeto Gutenberg, que é um esforço voluntário para arquivar e
distribuir obras culturais através da digitalização de livros. Nele
é possível encontrar obras que estão em domínio publico em vários formatos como
EPUB, HTML e texto, no teste realizado foi utilizada a obra de Arthur Conan Doyle, Um Estudo em Vermelho cujo texto original em inglês pode ser encontrado
neste LINK.
Para evitar o excesso de
informação, algumas funções apresentadas não estão com o a verificação de erro
incluída, os arquivos do projeto que se encontram neste LINK vem com todas as checagens de
problemas.
