]]>
]]>
]]>
]]>
El siguiente listado implementa un contenedor cola simplemente enlazada. Las inserciones al inicio o final de la cola son muy eficientes. Pero para acceder a un valor, se requiere recorrer todos los elementos previos. Se provee una clase Iterator para poder hacer este recorrido.
]]>
]]>
En un árbol binario de búsqueda cada nodo conoce cuales son sus nodos hijos: uno a la izquierda y otro a la derecha, de tal forma que cualquier nodo que se encuentre a la izquierda tiene un valor menor que el nodo y a la derech a un valor mayor o igual al nodo. El siguiente implementa algunos métodos de un árbol binario de búsqueda no balanceado.
]]>
]]>
Un mapa, también llamado arreglo asociativo, hash o diccionario; es una estructura de datos que permite asociar una llave con un valor. Tanto las llaves como sus valores asociados pueden ser de cualquier tipo de datos. Por ejemplo, se puede asociar una palabra con su definición, o una palabra con su frecuencia de aparición en un texto, o un nivel de educación (un número) contra las personas que la han alcanzado (una lista enlazada de objetos), etc. El siguiente ejemplo muestra el contenedor std::map<Key, Value> de la Biblioteca Estándar de Plantillas (STL) de C++.
]]>
El siguiente ejemplo es un contador de palabras. Recibe una lista de nombres de archivo por parámetro. Cada palabra del archivo es cargada a un mapa (implementado como un árbol binario de búsqueda balanceado). Cada palabra es asociada con un entero largo, el cual indica la cantidad de veces que se ha encontrado la palabra en el archivo. El operador [] del mapa recibe una llave y retorna una referencia a su valor asociado. Cada vez que se encuentra una palabra, se incrementa su contador (con el operador ++). Finalmente el programa imprime cada una de las palabras y su conteo en la salida estándar.
]]>
Ejercicio. Modifique el ejemplo del contador de palabras únicas para que ignore caracteres especiales que se cargan al inicio o final de las palabras. Indague sobre los métodos de la clase std::string.
Ejercicio. Modifique el programa anterior, de tal forma que para cada palabra almacene las posiciones en el archivo donde la palabra aparece. Es decir, en su mapa cada palabra debe estar asociada con una lista enlazada de enteros (streampos). Indague sobre el método ifstream::tellg(). Su programa debe imprimir cada palabra única, la cantidad de veces que aparece en el archivo, y la lista de posiciones donde se encuentra.
Ejercicio. Modifique el contador de palabras únicas para que imprima las palabras en orden descendente de aparición. Sugerencia: cree otro mapa donde asocie la frecuencia de aparición con una lista de palabras. Recorra el mapa original para llenar el segundo. Luego imprima el segundo mapa de tal forma que las palabras más frecuentes aparezcan primero.