Advertisement
Guest User

Untitled

a guest
Oct 16th, 2018
104
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 5.74 KB | None | 0 0
  1. #include <iostream>
  2. #include <string>
  3.  
  4. class Data {
  5. public:
  6. Data(int d, int m, int a = 0);
  7. void Alterar(int d, int m, int a = 0);
  8. int Ano() const { return ano; }
  9. int Dia() const { return dia; }
  10. unsigned Hash(int limite) const;
  11. int Mes() const { return mes; }
  12. protected:
  13. int dia;
  14. int mes;
  15. int ano;
  16. };
  17.  
  18. class Funcionario {
  19. public:
  20. Funcionario() : nome(), nascimento(0, 0, 0) {}
  21. bool FazAniversarioEm(const Data& data);
  22. std::string nome;
  23. Data nascimento;
  24. };
  25.  
  26. // Um Noh guarda um funcionário em uma tabela
  27. class Noh {
  28. public:
  29. Noh(const Funcionario& func, Noh* proximo = NULL) :
  30. mValor(func), mProximo(proximo) {
  31. }
  32. Funcionario mValor;
  33. Noh* mProximo;
  34. };
  35.  
  36. // Uma lista guarda todos os Nos cuja chave foi mapeada na mesma posição.
  37. class ListaAux {
  38. friend class Hash;
  39. public:
  40. // construtor
  41. ListaAux() : mPrimeiro(NULL), mTamanho(0) {}
  42. // Adiciona um Noh a uma lista.
  43. void Adicionar(Noh* novoNoh);
  44. // Retorna o tamanho (quantidade de valores na estrutura).
  45. short int Tamanho() { return mTamanho; }
  46. private:
  47. Noh* mPrimeiro; // primeiro nó da ListaAux
  48. short int mTamanho; // quantidade de valores na ListaAux
  49. };
  50.  
  51. // Um hash guarda vários funcionários, considerando o seu nascimento como chave.
  52. class Hash {
  53. public:
  54. Hash(int cap = 100);
  55. ~Hash();
  56.  
  57. // Escreve o conteúdo interno do hash (para fins de depuração).
  58. void EscreverEstrutura(std::ostream& saida) const;
  59. // Insere um funcionario.
  60. void Inserir(const Funcionario& func);
  61. // Retorna a porcentagem de uso das posições da tabela hash.
  62. float PorcentagemDeUso() const;
  63. // Retorna a quantidade de aniversariantes numa data (dia/mes).
  64. unsigned QtdeAniversariantes(const Data& d);
  65. private:
  66. // vetor de ponteiros para lista
  67. ListaAux* mElementos;
  68. // quantidade de posições na tabela hash
  69. int mNroPosicoes;
  70. };
  71.  
  72. using namespace std;
  73. // === Data ===================================================================
  74. Data::Data(int d, int m, int a)
  75. : dia(d), mes(m), ano(a) {
  76. }
  77.  
  78. void Data::Alterar(int d, int m, int a) {
  79. dia = d;
  80. mes = m;
  81. ano = a; // ano tem valor default
  82. }
  83.  
  84. unsigned Data::Hash(int limite) const {
  85. return (unsigned(dia) * unsigned(mes) - 1) % unsigned(limite);
  86. }
  87.  
  88. istream& operator>> (istream& entrada, Data& d) {
  89. int dia, mes, ano;
  90. entrada >> dia >> mes >> ano;
  91. d.Alterar(dia, mes, ano);
  92. return entrada;
  93. }
  94.  
  95. ostream& operator<< (ostream& saida, Data& d) {
  96. saida << d.Dia() << '/' << d.Mes() << '/' << d.Ano();
  97. return saida;
  98. }
  99.  
  100. // === Funcionario ============================================================
  101. bool Funcionario::FazAniversarioEm(const Data& data) {
  102. return nascimento.Dia() == data.Dia() and nascimento.Mes() == data.Mes();
  103. }
  104.  
  105. ostream& operator<< (ostream& saida, Funcionario& f) {
  106. saida << f.nome << ' ' << f.nascimento;
  107. return saida;
  108. }
  109.  
  110. // === ListaAux ===============================================================
  111. void ListaAux::Adicionar(Noh* novoNoh) {
  112. //#warning ListaAux::Adicionar não foi implementado.
  113.  
  114. }
  115.  
  116. // === Hash ===================================================================
  117. Hash::Hash(int cap) // cap tem valor default
  118. : mElementos(new ListaAux[cap]), // chama construtor em todos
  119. mNroPosicoes(cap) {
  120. }
  121.  
  122. Hash::~Hash() {
  123. for (int i = 0; i < mNroPosicoes; ++i) {
  124. Noh* atual = mElementos[i].mPrimeiro;
  125. while (atual != NULL) {
  126. Noh* aux = atual;
  127. atual = atual->mProximo;
  128. delete aux;
  129. }
  130. }
  131. delete[] mElementos;
  132. }
  133.  
  134. void Hash::EscreverEstrutura(ostream& saida) const {
  135. Noh* atual = NULL;
  136. for (int i = 0; i < mNroPosicoes; ++i) {
  137. saida << i << ": ";
  138. atual = mElementos[i].mPrimeiro;
  139. while (atual != NULL) {
  140. saida << "[" << atual->mValor << "]->";
  141. atual = atual->mProximo;
  142. }
  143. saida << "NULL" << endl;
  144. }
  145. }
  146.  
  147. void Hash::Inserir(const Funcionario& func) {
  148. //#warning Hash::Inserir não foi implementado.
  149. //mElementos[pos] == posicao na hash
  150. int pos = Data(func.nascimento).Hash(mNroPosicoes);
  151. Noh* novo = new Noh(func);
  152. if(mElementos[pos].mPrimeiro==NULL){//caso no vetor nao há elementos
  153. mElementos[pos].mPrimeiro = novo;
  154. }else{//se estiver preciso adicionar na lista aux
  155. mElementos[pos].Adicionar(novo);
  156. }
  157. }
  158.  
  159. float Hash::PorcentagemDeUso() const {
  160. float elementos = 0;
  161. for(int i=0;i<mNroPosicoes;i++){
  162. if(mElementos[i].mPrimeiro!=NULL){
  163. elementos++;
  164. }
  165. }
  166. return elementos/mNroPosicoes;
  167.  
  168. }
  169.  
  170. unsigned Hash::QtdeAniversariantes(const Data& d) {
  171. unsigned elementos = 0;
  172. int pos = Data(d).Hash(mNroPosicoes);
  173. Noh* run = mElementos[pos].mPrimeiro;
  174. while(run!=NULL){
  175. elementos++;
  176. run = run->mProximo;
  177. }
  178. return elementos;
  179.  
  180. }
  181.  
  182. // === Programa ===============================================================
  183. int main( ) {
  184. unsigned qtde;
  185. cin >> qtde; // quantidade de posições na tabela
  186. Hash tabela(qtde); // cria uma tabela com 10 endereços
  187. Funcionario funcionario;
  188. cin >> qtde; // quantidade de funcionários a inserir
  189. for (unsigned int i = 0; i < qtde; ++i) {
  190. cin >> funcionario.nome >> funcionario.nascimento;
  191. tabela.Inserir(funcionario);
  192. }
  193. int dia, mes;
  194. cin >> dia >> mes;
  195. Data hoje(dia, mes);
  196. cout << tabela.QtdeAniversariantes(hoje) << ' '
  197. << tabela.PorcentagemDeUso() << endl;
  198.  
  199. return 0;
  200. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement