ICC2 2010-2 TrabalhoSUB

Trabalho substitutivo ICC2 2010/1

Descrição

Esse trabalho substitui a menor nota obtida entre os trabalhos, mesmo que a nota NTSUB < min{NT1,NT2,NT3}

• Esse trabalho é complexo por envolver estruturas de dados, ordenação e hashing, e leva tempo para ser implementado, portanto comece já
• Desenvolvam os seus próprios arquivos com casos de teste adicionais, prevendo diferentes situações
• O horário máximo de entrega é até o dia 9 às 23h59 no relógido do servidor SQTPM, portanto envie com antecedência.

• Enunciado (pdf)
• Casos de Teste (tar.gz)

• Dicas:

1. comece implementando uma TAD lista encadeada ordenada; depois que o TAD estiver implementado e funcionando crie uma Tabela Hash com ponteiros para diversas dessas listas e utilize-a para resolver o problema
2. considere que a entrada estará sempre correta, com palavras válidas e sempre com tamanho entre 2 e 64 caracteres
3. faça alocação dinâmica de cada palavra incluída na tabela, utilizando a função (int)strlen(palavra) para detectar o tamanho da palavra.
4. Para verificar memory leaks em executáveis c/c++ utilize a linha de comando abaixo [1]

 $ valgrind --leak-check=full ./seu_programa_executavel

Uma idéia da implementação

1.) Criar um vetor de ponteiros, do qual cada posicao será a cabeça de uma lista encadeada (ou seja, que aponta para o 1º elemento de uma lista) 2.) Ler as palavras do arquivo de testes (entrada) até encontrar o fim de arquivo (EOF).

2.1) a cada palavra lida, o programa tentará inserir: para inserir uma palavra, calcula o índice utilizando a função hash e insira de forma ordenada na lista encadeada correspondente àquele índice

2.2) se a palavra já existir na tabela é preciso apenas incrementar seu número de ocorrências

Se considerarmos M=3, para exemplo, no início teremos a tabela vazia:

0 |*| ->NULL

1 |*| ->NULL

2 |*| ->NULL

Ao ler a palavra "carro", vamos supor que h("carro")=2, inserimos carro na lista encadeada da posicao 2, com uma ocorrência

0 |*| ->NULL

1 |*| ->NULL

2 |*| ->(carro,1)->NULL

Ao ler a palavra "bacia", vamos supor que h("bacia")=2, inserimos na lista encadeada da posicao 2, com uma ocorrência, mas vamos percorrer a lista para encontrar a posição correta de forma a inserir esse elemento ordenado

0 |*| ->NULL

1 |*| ->NULL

2 |*| ->(bacia,1)->(carro,1)->NULL

E assim por diante. Caso apareça novamente a palavra "carro", por exemplo, temos apenas que incrementar seu número de ocorrências. Uma sugestão é implementar a função de busca com um parâmetro de incremento. Caso você queira apenas saber se a palavra existe na tabela você passa o parâmetro com 0 (zero), se você quiser verificar se a palavra está na tabela e, se existir, incrementar seu número de ocorrências, passa o parâmetro com 1 (um).

0 |*| ->NULL

1 |*| ->NULL

2 |*| ->(bacia,1)->(carro,2)->NULL

3.) na saída, como cada lista está em ordem, você vai removendo os primeiros elementos de cada lista, em ordem, até que todas as listas estejam vazias

vamos supor M=3 e a tabela já preenchida, com as palavras e o numero de ocorrências de cada uma delas.

0 |*| ->(ana,4)->(banana,3)->(so,5)->NULL

1 |*| ->(em,6)->(virus,7)->NULL

2 |*| ->(bacia,1)->(carro,7)->NULL

uma forma de realizar a remoção é como uma intercalação entre as listas repetindo os seguintes passos:

Enquanto as listas (todas) nao forem vazias

percorra todas as listas para encontrar o menor elemento, e retira o elemento da lista, imprimindo a palavra e número de ocorrências se satisfazer as condições

Nesse exemplo "ana" é próximo menor elemento, entao é preciso retirar esse elemento e verificar se ele satisfaz as condições: i) possuir 3 caracteres ou mais e ii) 3 ocorrencias ou mais. como esse satisfaz, imprime:

ana 4

A tabela ficaria assim: 0 *| ->(banana,3)->(so,5)->NULL

1 *| ->(em,6)->(virus,7)->NULL

2 *| ->(bacia,1)->(carro,7)->NULL

Percorre-se novamente para encontrar o proximo menor elemento, que será "bacia", só que esse nao possui 3 ocorrencias entao apenas remove sem imprimir 0 *| ->(banana,3)->(so,5)->NULL

1 *| ->(em,6)->(virus,7)->NULL

2 *| ->(carro,7)->NULL

Na sequencia remove o elemento "banana" e imprime

banana 3

0 *| ->(so,5)->NULL

1 *| ->(em,6)->(virus,7)->NULL

2 *| ->(carro,7)->NULL

Na sequencia remove o elemento "carro" e imprime

carro 7

0 *| ->(so,5)->NULL

1 *| ->(em,6)->(virus,7)->NULL

2 *| ->NULL

Repare que já temos uma lista vazia, mas ainda restam as outras a serem intercaladas. O proximo elemento é "em" que não satisfaz uma das condições, e portanto é apenas retirado sem imprimir

0 *| ->(so,5)->NULL

1 *| ->(virus,7)->NULL

2 *| ->NULL

E a seguir teríamos:

0 *| ->NULL

1 *| ->(virus,7)->NULL

2 *| ->NULL

E a última palavra impressa:

virus 7

0 *| ->NULL

1 *| ->NULL

2 *| ->NULL

Ao percorrer a tabela verifica-se que todas as listas estão vazias então o algoritmo termina.