betoesquivel

Estructura HASHING tarea 7

Nov 3rd, 2013
320
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 6.18 KB | None | 0 0
  1. /*
  2.  * =====================================================================================
  3.  *
  4.  *       Filename:  codigotarea.cpp
  5.  *
  6.  *    Description:  editando
  7.  *
  8.  *        Version:  1.0
  9.  *        Created:  11/03/2013 05:27:49 PM
  10.  *       Revision:  none
  11.  *       Compiler:  gcc
  12.  *
  13.  *         Author:  YOUR NAME (),
  14.  *   Organization:  
  15.  *
  16.  * =====================================================================================
  17.  */
  18.  
  19.  
  20. // Código para el tercer examen parcial de Estructuras de Datos, semestre AD12, elaborado por RMM
  21. #include <stdlib.h>
  22. #include <iostream>
  23. #include <fstream>
  24. #include <string>
  25. #include <cmath>
  26.  
  27. using namespace std;
  28. #define TAM 100  
  29.  
  30. //Implementación del nivel físico de un ABB
  31. template <class T>
  32. class NodoArbol
  33. { public:
  34.     T info;
  35.     NodoArbol<T> *izq, *der;
  36.     NodoArbol() { izq = der = NULL; }
  37.     NodoArbol(T dato) { info = dato; izq = der = NULL; }
  38. };
  39.  
  40. template <class T>
  41. class ABB
  42. {
  43. private:
  44.         NodoArbol<T> *raiz;
  45. public:
  46.         ABB() { raiz = NULL; }
  47.         void inserta (T dato);
  48.         void despliega() { inorden(raiz); }
  49.         int cuenta () { return contar(raiz); }
  50.         int altura () { return niveles(raiz); }
  51.         bool existe(T dato);
  52.         ~ABB() { libera(raiz); }
  53. };
  54.  
  55. template <class T>
  56. void libera (NodoArbol<T>* raiz)
  57. {
  58.     if (raiz != NULL)
  59.     {
  60.         libera(raiz->izq);
  61.         libera(raiz->der);
  62.         delete(raiz);
  63.     }
  64. }
  65.  
  66. template <class T>
  67. void inorden (NodoArbol<T>* raiz)
  68. {
  69.     if (raiz != NULL)
  70.     {
  71.         inorden(raiz->izq);
  72.         cout << raiz->info <<" ";
  73.         inorden(raiz->der);
  74.     }
  75. }
  76.  
  77. template <class T>
  78. int contar (NodoArbol<T>* raiz)
  79. {
  80.     if (raiz == NULL)
  81.         return 0;
  82.     return(1+contar(raiz->izq)+contar(raiz->der));
  83. }
  84.  
  85. template <class T>
  86. int niveles (NodoArbol<T>* raiz)
  87. {
  88.     int altizq, altder;
  89.     if (raiz == NULL)
  90.         return 0;
  91.     altizq = niveles(raiz->izq);
  92.     altder = niveles(raiz->der);
  93.     return(1+ (altizq>altder? altizq : altder));
  94. }
  95.  
  96. template <class T>
  97. void ABB<T>::inserta (T valor)
  98. {
  99.     NodoArbol<T> *NuevoNodo = new NodoArbol<T>(valor);
  100.     NodoArbol<T> *actual = raiz, *anterior = NULL;
  101.     while (actual != NULL)
  102.     {
  103.         anterior=actual;
  104.         actual=(actual->info>valor? actual->izq: actual->der);
  105.     }
  106.     if (anterior==NULL)
  107.         raiz = NuevoNodo;
  108.     else
  109.         if (anterior->info > valor)
  110.             anterior->izq = NuevoNodo;
  111.         else
  112.             anterior->der = NuevoNodo;
  113. }
  114.  
  115. template <class T>
  116. bool ABB<T>::existe(T dato)
  117. {
  118.     NodoArbol<T> *aux = raiz;
  119.     int comparaciones = 1;
  120.     while (aux != NULL && aux->info != dato){
  121.         aux = (dato < aux->info? aux->izq : aux->der);
  122.         comparaciones++;
  123.     }
  124.     if(aux==NULL){
  125.         cout<<comparaciones<<" comparaciones para saber que no existe en el arbol."<<endl;
  126.     }else{
  127.         cout<<comparaciones<<" comparaciones para encontrar el dato en el arbol."<<endl;
  128.     }
  129.     return !(aux == NULL);
  130. }
  131. // Implementación del nivel físico de una Tabla de Hash
  132.  
  133. template <class T>
  134. class tablaHash
  135. {
  136. private:
  137.     ABB<T> tabla[TAM];
  138.     int cantidad;
  139.    
  140. public:
  141.     tablaHash() {cantidad = 0;}
  142.     void inserta (T dato);
  143.     void inserta2 (T dato);
  144.     bool buscarDato (T dato);
  145.     bool buscarDato2 (T dato);
  146.     void despliega ();
  147.     double tamanioPromedioBuckets ();
  148.     double alturaPromedioBuckets ();
  149. };
  150.  
  151. template <class T>
  152. void tablaHash<T>::inserta (T dato)
  153. {
  154.     int posicion = dato / 100 % TAM;
  155.     tabla[posicion].inserta(dato);
  156.     cantidad++;
  157. }
  158.  
  159. template <class T>
  160. void tablaHash<T>::inserta2 (T dato)
  161. {
  162.     int posicion = dato % TAM;
  163.     posicion = pow(posicion,2);
  164.     posicion%=TAM;
  165.     cout<<"Se inserta el dato "<<dato<<" en la posicion: "<<posicion<<endl;
  166.     tabla[posicion].inserta(dato);
  167.     cantidad++;
  168. }
  169.  
  170. template <class T>
  171. void tablaHash<T>::despliega()
  172. {
  173.     cout << "Cantidad de datos: "<<cantidad<<"\n";
  174.     for (int i = 0; i < TAM; i++)
  175.     {
  176.         cout << "Posicion "<<i<<": "<<tabla[i].cuenta()<<" datos en "<<tabla[i].altura()<<" niveles ";
  177.         tabla[i].despliega();
  178.         cout << "\n";
  179.     }
  180. }
  181.  
  182. template <class T>
  183. double tablaHash<T>::tamanioPromedioBuckets()
  184. {
  185.     int suma = 0, bucketsLlenos = 0;
  186.     for (int i = 0; i < TAM; i++)
  187.     {
  188.         int nodosBucket = tabla[i].cuenta();
  189.         if (nodosBucket!=0) {
  190.             suma += nodosBucket;
  191.             bucketsLlenos++;
  192.         }
  193.     }
  194.     return ((suma*1.0)/bucketsLlenos);
  195. }
  196.  
  197. template <class T>
  198. double tablaHash<T>::alturaPromedioBuckets()
  199. {
  200.     int suma = 0, bucketsLlenos = 0;
  201.     for (int i = 0; i < TAM; i++)
  202.     {
  203.         int alturaBucket = tabla[i].altura();
  204.         if (alturaBucket!=0) {
  205.             suma += alturaBucket;
  206.             bucketsLlenos++;
  207.         }
  208.     }
  209.     return ((suma*1.0)/bucketsLlenos);
  210. }
  211.  
  212. template <class T>
  213. bool tablaHash<T>::buscarDato (T dato){
  214.     int datoTemp = dato;
  215.     int indice = datoTemp / 100 % TAM;
  216.     cout<<"Este es el indice donde esta el dato "<<dato<<": "<<indice<<endl;
  217.     return tabla[indice].existe(dato);
  218. }
  219.  
  220. template <class T>
  221. bool tablaHash<T>::buscarDato2 (T dato){
  222.     int datoTemp = dato;
  223.     int indice = datoTemp % TAM;
  224.     indice = pow(indice,2);
  225.     indice%=TAM;
  226.  
  227.     cout<<"Este es el indice donde esta el dato "<<dato<<": "<<indice<<endl;
  228.     return tabla[indice].existe(dato);
  229. }
  230. // Implementación del programa de aplicación
  231. int main()
  232. {
  233.     tablaHash<int> hashing;
  234.     tablaHash<int> hashing2;
  235.     ifstream arch;
  236.     string nomarch;
  237.     int dato;
  238.  
  239.     cout << "Ingrese el nombre del archivo a cargar: ";
  240.     cin >> nomarch;
  241.  
  242.     arch.open(nomarch.c_str());
  243.     while (!arch.eof())
  244.     {
  245.         arch >> dato;
  246.         hashing.inserta(dato);
  247.         hashing2.inserta2(dato);
  248.     }
  249.     arch.close();
  250.  
  251.     cout<<"HASH TABLE 1"<<endl;
  252.     hashing.despliega();   
  253.     cout<<endl;
  254.  
  255.     cout<<"HASH TABLE 2"<<endl;
  256.     hashing2.despliega();  
  257.     cout<<endl;
  258.  
  259.     cout<<"HASH TABLE 1, OPERACIONES"<<endl;
  260.  
  261.     cout<<"Buscando el dato 785958"<<endl;
  262.     hashing.buscarDato(785958);
  263.    
  264.     cout<<"Buscando el dato 143012"<<endl;
  265.     hashing.buscarDato(143012);
  266.    
  267.     cout<<"Tamanio promedio de los buckets: "<<hashing.tamanioPromedioBuckets()<<endl;
  268.     cout<<"Altura promedio de los buckets: "<<hashing.alturaPromedioBuckets()<<endl;
  269.     cout<<endl;
  270.  
  271.     cout<<"HASH TABLE 2, OPERACIONES"<<endl;
  272.  
  273.     cout<<"Buscando el dato 785958"<<endl;
  274.     hashing2.buscarDato2(785958);  
  275.    
  276.     cout<<"Buscando el dato 143012"<<endl;
  277.     hashing2.buscarDato2(143012);  
  278.    
  279.     cout<<"Tamanio promedio de los buckets: "<<hashing2.tamanioPromedioBuckets()<<endl;
  280.     cout<<"Altura promedio de los buckets: "<<hashing2.alturaPromedioBuckets()<<endl;
  281.  
  282.     return 0;
  283. }
Advertisement
Add Comment
Please, Sign In to add comment