O arquivo de entrada consistirá de vários grupos de dados. Cada grupo terá um inteiro n seguido de n operações a serem feitas na hash table, uma por linha. As operações podem ser:
O arquivo termina com um grupo onde n = 0. Este grupo não deve ser processado.
Sua Hash Table deverá ter tamanho 1024 (h = 1024).
A função de Hash a ser utilizada é a da pag. 282, item 8, do Sara Baase:
hash(k) = (a k) mod h, onde a = (8 ëh/23û) + 5
A função de rehash encontra-se na seção 6.5.2 do mesmo:rehash(pos, d) = (pos + d) mod h, onde d = 2 k + 1
Entrada exemplo:
6
i 10
i 20
b 10
b 150
r 20
r 13
4
i 3
i 1027
r 3
b 1027
10
i 7
i 1036
b 7
b 12
i 12
r 1036
b 12
r 12
i 14
i 12
0
SAÍDA
Saída da entrada acima:
Grupo #1
10 inserido em 498
20 inserido em 996
10 encontrado em 498
150 inexistente
20 removido de 996
13 inexistente
Grupo #2
3 inserido em 47
1027 inserido em 54
3 removido de 47
1027 encontrado em 54
Grupo #3
7 inserido em 451
1036 inserido em 188
7 encontrado em 451
12 inexistente
12 inserido em 213
1036 removido de 188
12 encontrado em 213
12 removido de 213
14 inserido em 902
12 inserido em 188
Obs.:
O arquivo de entrada consiste de vários grupos de dados. Cada grupo de dados contém duas linhas: a primeira linha contém o número de elementos deste grupo (1<=N<=1000) e a segunda linha contém um número (0<=M<=1000) indicando a quantidade de operações que vai ser processada sobre este grupo de dados. As M seguintes linhas vão conter uma operação cada. Inicialmente, em cada grupo de dados, todos os elementos (1..N) estão representando conjuntos disjuntos, correspondendo a uma operação de create (especificada na pg 284 do Sara Baase).A seguir serão processadas as operações na ordem em que aparecem na entrada. As operações possíveis são: find(i) e wunion(i,j). A operação find estará especificada da seguinte forma: a string "find" seguida de um número i (1<=i<=N) em uma linha. Como está explicado no Sara Baase, cada conjunto representa uma árvore e a operação find i imprime na saída (em uma linha) a raiz da árvore a qual i pertence, ou seja, o identificador deste conjunto. A operação wunion i j (a string "wunion" seguida de dois números em uma linha,1<=i,j<=N)) une os dois conjuntos a que pertencem i e j, ou seja, une as raízes das árvores destes conjuntos. No caso das alturas das árvores de i e j serem iguais, a árvore i passará a ser uma sub-árvore de j. O grupo de dados que iniciar com 0 (zero), como número de elementos, indica fim de execução e esse grupo não deve ser processado.
2
1
find 2
4
5
wunion 1 2
wunion 3 4
wunion 1 3
find 1
find 3
12
18
wunion 1 2
wunion 3 4
wunion 1 3
wunion 5 6
find 5
wunion 7 8
wunion 9 10
wunion 11 12
wunion 6 8
wunion 9 12
find 5
find 10
wunion 6 10
find 7
find 10
wunion 9 1
find 2
find 11
1
2
wunion 1 1
find 1
0
Saída da entrada acima:
Obs.: