Había puesto uan solución en forma de árbol, pero después de releerte como te viene un array, y necesitas hacer búsquedas es preferible tirar de una tabla hash (es más rápido en funcionamiento). Desconozco si estás forzado a algo predeterminado, pues no lo especificas).
Has dejado al aire ciertas cuestiones, como si puede modificarse los elementos de la clase, asumo que sí pues no lo acotas (aunque no lo llevo al terreno de árboles, porque quizás serían más cambios de los que te cabría pensar).
Supongamos que tu array ha de contener a lo sumo 100-200 elementos... no es mala idea proveer entonces un array de alrededor de 1000 elementos, donde podrán buscarse en tiempo 1 por hash.
Deájeme que simplifique el nombre del array a simplemente 'datos', e igualmente siempre me acomoda más usar paréntesis que llaves (son diferencias 'habituales' de la herencia entre Fortran y Algol que han trascendido hasta los lenguajes de hoy)...
Te llega el array, lo hasheas...
entero constante PRIMO_X = 1021
entero arrayHash(0 a PRIMO_X - 1)
entero espacioLibre
Menu datos()
// Cuando se recibe el array 'datos'... se invoca esta función.
funcion SetArray()
Menu item
borrarTablaHash
por cada item en datos()
add(item.Name, k)
siguiente
Fin funcion
Con esto ya tenemos todos los datos portados al arrayHash...
La búsqueda sería:
NOTA: No se provee solución al caso de una búsqueda sin haber recibido aún los datos, queda a tu esfuerzo dicho código, como para todas las comprobaciones 'obvias', además para no extenderse más de lo preciso.
Menu = Funcion Buscar(string Nombre)
entero j, k
k = Hashing(Nombre)
Si Existe(nombre, k) = TRUE
devolver datos(k)
sino
devolver null // no encontrado
fin si
fin funcion
Si existe (por referencia devuelve el índice donde se localiza en otro caso devuelve -1
Esta función típicamente es privada, la pública es 'buscar'.
Aquí se resuelven las colisiones... que es lo que hace la función un poco más compleja.
buleano = funcion Existe(string Nombre,por referencia entero index)
entero j, k
k= index
Hacer
j = arrayHash(index)
si (j => 0) // Si existe
si (datos(j).Nombre = nombre) // Comprobar si se trata de una colisión...
index = j // ojo... es devuelto por referencia.
devolver TRUE
sino // una colisión se resuelve buscando el próximo hueco libre.
index = ((index + 1) modulo PRIMO_X)
si (index = k) devolver FALSE // evitar bucle infinito...
fin si
sino
devolver FALSE
fin si
repetir
fin funcion
El bucle es incondicional, pero dentro está totalmente controlado. No es un bucle infinito a lo sumo recorre 1 vez todo el array de la tabla hash si está mal programado.
NOTA: (es la única comprobación que te pongo, porque para un novato 'puede ser fácil', incurrir en tal error...)
Restan las funciones Add, Hashing, etc...
buleano = funcion add(string name, entero index)
entero j,k
k = Hashing(name)
si Existe(name, k) = FALSE
arrayHash(k) = index
espacioLibre -= 1
devolver TRUE ó k // la devoluión es opcional... según el diseño y si otros métodos precisan más info...
sino
devolver FALSE ó -1
fin si
fin funcion
Se supone que la tabla hash es de un tamaño mucho mayor que el array 'datos', y que por ello siempre encontrará un hueco. 'espacioLibre', sirve para controlar esto...
Queda a tu esfuerzo que si se añaden elementos dinámicamente y hay una alta ocupación (cae el rendimiento de añadir y buscar, elementos) redimensionar la tabla a un tamaño mayor haciendo un rehashing de todos los elementos.
Como todo esto es algo más elaborado, no es para 'novatos', cuando te adentres más en la programación, ya explorarás medidas para controlar tamaño de tabla hash, funciones mejor diseñadas para evitar colisiones y como resolverlas, etc...). Mientras, para un simple ejemplo esto es suficiente...
// Borramos datos previos que constaran en la tabla hash
funcion borrarTabla
entero k
bucle para k desde 0 hasta PRIMO_X-1
arrayHash(k) = -1
siguiente
espacioLibre = PRIMO_X
fin funcion
entero = funcion Hashing(string nombre)
entero j, k
por cada par de caracteres (a,b) en nombre
j += (a*b) // se entiende que por 'a' y 'b' tomamos el valor del byte que supone cada char, superando el overflow del byte...
siguiente
Si tamaño(nombre) es impar
j += (nombre.primercarater * nombre.ultimocaracter)
fin si
devolver (j modulo PRIMO_X) // si se usa un solo valor debe ser primo, de otro modo las colisiones serán muy numerosas.
fin funcion
Y para algo básico eso es todo. Te toca pasar el pseudocódigo a código si quieres implementarlo o no si simplemente te basta con entenderlo (la práctica ayuda a la teoría).
Ahora algunas aclaraciones...
- La tabla hash puede a su vez ser una clase para que la lógica quede más clara, especialmente si se añaden más métodos... pués así encapsula toda su operatoria separada del resto, ahora mientras sean pocos métodos no enturbia que quede conjunto...
- Si la clase solo va a contener datos y no funcionalidad, quizás fuera preferible usar una estructura en vez de una clase (depende de otros factores, pero intenta examinar si es suficiente con una estructura).
- Si el campo 'Name', admite estar repetido, entonces el hashing no será aceptable. Para el hashing debe proveerse un campo de valor único (no repetible, en palabras claras), si no hay más remedio usa otro campo o bien concaténalo con URL, o incluso con 'id'... es decir con otro campo cuyo valor sea único.
- Sería conforme que tu clase contuviera un nodo 'parent' así tras la búsqueda exitosa, es fácil llegar hasta el padre x es meramente un bucle cuya funcionalidad es fácil de añadir... Ahora quizás dicho enlace esté señalado con el índice del campo 'Id'.... pero no hay suficientes explicaciones que lo aclaren.
- Si lo que te piden es un recorrido en profundidad (inorden, preorden, postorden), no me consta que quede aclarado, y he partido de la presunción de que tienes más código y bastante claro lo que te piden/quieres y has simplificado por la razón que sea. Con esos recorridos (no una búsqueda por nombre), conviene ceñirse entonces a un diseño de árbol en todo su concepto, en cambio si tienes libertad de elección esta solución suele ser la más eficaz, para búsqueda.
- Si el código es para tí (no un encargo para una empresa o cursillo) y si tu lengua materna no es el inglés, no veo motivo para que uses términos en inglés... (a mi me suena un poco pedante, pero es solo mi impresión otros opinarán distinto).
- Este pseudocódigo es mucho más eficiente que otras soluciones, si bien la función hash es bastante 'simple' y el valor del primo se ha elegido en base a la hipótesis de que tu array de datos no tendrá más de 200 elementos (el tamaño del array de la tabla hash debe mantener cierta premisa de proporción respecto de la cantidad máxima de elementos, si no es definible entonces debe ser un tamaño dinámico (que es algo más avanzado)...
Si tienes alguna duda, pregunta, pero procura ser claro, sin ausmir que uno tiene acceso a la especificación completa de lo que te piden, si no al final uno no hace más que asumir tal o cual cosa, donde la duda acecha.
...creo que se me queda alguna cosa en el tintero de las que tenía que señalarte, pero (mientas) al escribir al vuelo, es normal que luego unas se te vayan de la cabeza...