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.
- Dicas:
- 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
- considere que a entrada estará sempre correta, com palavras válidas e sempre com tamanho entre 2 e 64 caracteres
- 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.
- 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.
