Exibir código-fonte para 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.

* [[Media:ICC2-Trabalho_SUB.pdf‎|Enunciado (pdf)]]
* [[Media:ICC2_TrabalhoSUB_Casos.tar.gz‎|Casos de Teste (tar.gz)]]
:* 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 [http://www.sergioprado.org/2010/07/29/memory-leak-em-linguagem-c/]
  $ 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.