INSTITUTO POLITÉCNICO NACIONAL
ESCUELA SUPERIOR DE CÓMPUTO
Licenciatura en Ciencias de Datos
Materia:
Algoritmos y estructuras de datos
Profesora:
Ana Belem Juárez Méndez
Alumnos:
Pérez Hernández Angel Adrián
Tellez Calan Fernando Iván
Grupo:
2AV2
Practica 3. Algoritmos de busqueda.
Objetivo.
Aplicar los conocimientos de algoritmos de ordenamiento en el lenguaje C.
Introducción.
En el siguiente reporte se hará una descripción de la implementación de un programa
en C que simula la rifa de una computadora entre 50 alumnos de ESCOM. La rifa
considera el nombre de los participantes, cargados desde un archivo y su número de
boleta entre 100 y 999 generado aleatoriamente.
Se utilizo una función para ordenar las boletas de los alumnos y posteriormente
utilizar búsqueda binaria e indexada para determinar al ganador de la rifa, cada una
en una función aparte.
Desarrollo.
Las constantes principales son ALUMNOS, MAX_BOLE, MIN_BOLE y MAX_NOMBRE.
Se definen dos estructuras: Alumno (para almacenar datos de alumnos) e Indice
(para crear un índice de búsqueda).
Se utilizo un archivo de nombres, que al leerlo el programa generaba los nombres de
los alumnos.
Las funciones utilizadas son las siguientes:
indexed_search: Busca un alumno utilizando un índice.
binary_search: Realiza una búsqueda binaria en un arreglo ordenado.
llenarAlumnosDesdeArchivo: Lee los datos de los alumnos desde un archivo.
crearIndice: Crea un índice para facilitar la búsqueda.
compararBoletas: Compara dos boletas para ordenar los alumnos.
Algoritmo en seudocódigo:
CONSTANTES:
ALUMNOS = 50
MAX_BOLE = 999
MIN_BOLE = 100
MAX_NOMBRE = 50
ESTRUCTURAS:
Estructura Alumno:
Entero boleta
Cadena nombres[MAX_NOMBRE]
Estructura Indice:
Entero boleta
Entero posición
FUNCIÓN indexed_search(Alumno alumnos[], Indice grupos[], Entero n, Entero s):
INICIO
Entero start = 0, end = 0, set = 0, GN = 5
Entero i = 0, j = 0
Entero G = n / GN
PARA i DESDE 0 HASTA G-1 HACER:
grupos[i].posicion = j
grupos[i].boleta = alumnos[j].boleta
j = j + GN
SI s < grupos[0].boleta ENTONCES:
RETORNAR -1
SINO:
PARA i DESDE 1 HASTA G-1 HACER:
SI s < grupos[i].boleta ENTONCES:
start = grupos[i-1].posicion
end = grupos[i].posicion - 1
set = 1
SALIR DEL BUCLE
SI set == 0 ENTONCES:
start = grupos[G-1].posicion
end = n - 1
RETORNAR binary_search(alumnos, s, start, end)
FIN
FUNCIÓN binary_search(Alumno alumnos[], Entero s, Entero ini, Entero fin):
INICIO
Entero mit
MIENTRAS ini <= fin HACER:
mit = (ini + fin) / 2
SI alumnos[mit].boleta == s ENTONCES:
RETORNAR mit
SINO SI s < alumnos[mit].boleta ENTONCES:
fin = mit - 1
SINO:
ini = mit + 1
RETORNAR -1
FIN
FUNCIÓN llenarAlumnosDesdeArchivo(Alumno alumnos[], Cadena nombreArchivo):
INICIO
Archivo archivo = abrir(nombreArchivo, "r")
SI archivo == NULL ENTONCES:
MOSTRAR "Error al abrir el archivo."
SALIR DEL PROGRAMA
PARA i DESDE 0 HASTA ALUMNOS-1 HACER:
SI fscanf(archivo, "%d %49s", &alumnos[i].boleta, alumnos[i].nombres) != 2
ENTONCES:
MOSTRAR "Error al leer los datos del archivo en la línea " + (i + 1)
CERRAR archivo
SALIR DEL PROGRAMA
CERRAR archivo
FIN
FUNCIÓN crearIndice(Indice grupos[], Alumno alumnos[]):
INICIO
Entero i = 0, j = 0, GN = 5
PARA i DESDE 0 HASTA (ALUMNOS / GN) - 1 HACER:
grupos[i].boleta = alumnos[j].boleta
grupos[i].posicion = j
j = j + GN
FIN
FUNCIÓN compararBoletas(Puntero a, Puntero b):
INICIO
Alumno *alumnoA = (Alumno *)a
Alumno *alumnoB = (Alumno *)b
RETORNAR (alumnoA->boleta - alumnoB->boleta)
FIN
FUNCIÓN PRINCIPAL:
INICIO
Entero ganadorIndex
Entero boletaGanadora
Alumno alumnos[ALUMNOS]
Indice grupos[ALUMNOS / 5]
llenarAlumnosDesdeArchivo(alumnos, "nombres.txt")
ORDENAR alumnos USANDO qsort CON compararBoletas
crearIndice(grupos, alumnos)
INICIALIZAR semilla aleatoria CON tiempo actual
Entero indiceAleatorio = número aleatorio entre 0 y ALUMNOS-1
boletaGanadora = alumnos[indiceAleatorio].boleta
ganadorIndex = indexed_search(alumnos, grupos, ALUMNOS, boletaGanadora)
SI ganadorIndex == -1 ENTONCES:
MOSTRAR "Error: No se encontró al ganador. Esto no debería ocurrir."
SINO:
MOSTRAR "El ganador es: " + alumnos[ganadorIndex].nombres + " con boleta " +
alumnos[ganadorIndex].boleta
RETORNAR 0
FIN
Código en C:
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>
#define ALUMNOS 50
#define MAX_BOLE 999
#define MIN_BOLE 100
#define MAX_NOMBRE 50
typedef struct
{
int boleta;
char nombres[MAX_NOMBRE];
} Alumno;
typedef struct
{
int boleta;
int posicion;
} Indice;
int indexed_search(Alumno alumnos[], Indice grupos[], int n, int s);
int binary_search(Alumno alumnos[], int s, int ini, int fin);
void llenarAlumnosDesdeArchivo(Alumno alumnos[], const char *nombreArchivo);
void crearIndice(Indice grupos[], Alumno alumnos[]);
int compararBoletas(const void *a, const void *b);
int main()
{
int ganadorIndex;
int boletaGanadora;
Alumno alumnos[ALUMNOS];
Indice grupos[ALUMNOS / 5];
llenarAlumnosDesdeArchivo(alumnos, "nombres.txt");
qsort(alumnos, ALUMNOS, sizeof(Alumno), compararBoletas);
crearIndice(grupos, alumnos);
srand(time(NULL));
int indiceAleatorio = rand() % ALUMNOS;
boletaGanadora = alumnos[indiceAleatorio].boleta;
ganadorIndex = indexed_search(alumnos, grupos, ALUMNOS, boletaGanadora);
if (ganadorIndex == -1)
{
printf("\nError: No se encontro al ganador. Esto no deberia ocurrir.\n");
}
else
{
printf("\nEl ganador es: %s con boleta %d\n", alumnos[ganadorIndex].nombres,
alumnos[ganadorIndex].boleta);
}
return 0;
}
int compararBoletas(const void *a, const void *b)
{
Alumno *alumnoA = (Alumno *)a;
Alumno *alumnoB = (Alumno *)b;
return (alumnoA->boleta - alumnoB->boleta);
}
int binary_search(Alumno alumnos[], int s, int ini, int fin)
{
int mit;
while (ini <= fin)
{
mit = (ini + fin) / 2;
if (alumnos[mit].boleta == s)
{
return mit;
}
else if (s < alumnos[mit].boleta)
{
fin = mit - 1;
}
else
{
ini = mit + 1;
}
}
return -1;
}
int indexed_search(Alumno alumnos[], Indice grupos[], int n, int s)
{
int start = 0, end = 0, set = 0, GN = 5;
int i = 0, j = 0;
int G = n / GN;
for (i = 0; i < G; i++)
{
grupos[i].posicion = j;
grupos[i].boleta = alumnos[j].boleta;
j = j + GN;
}
if (s < grupos[0].boleta)
{
return -1;
}
else
{
for (i = 1; i < G; ++i)
{
if (s < grupos[i].boleta)
{
start = grupos[i - 1].posicion;
end = grupos[i].posicion - 1;
set = 1;
break;
}
}
if (set == 0)
{
start = grupos[G - 1].posicion;
end = n - 1;
}
}
return binary_search(alumnos, s, start, end);
}
void llenarAlumnosDesdeArchivo(Alumno alumnos[], const char *nombreArchivo)
{
FILE *archivo = fopen("nombres.txt", "r");
if (archivo == NULL)
{
printf("Error al abrir el archivo.\n");
exit(1);
}
for (int i = 0; i < ALUMNOS; i++)
{
if (fscanf(archivo, "%d %49s", &alumnos[i].boleta, alumnos[i].nombres) != 2)
{
printf("Error al leer los datos del archivo en la línea %d.\n", i + 1);
fclose(archivo);
exit(1);
}
}
fclose(archivo);
}
void crearIndice(Indice grupos[], Alumno alumnos[])
{
int i = 0, j = 0, GN = 5;
for (i = 0, j = 0; i < ALUMNOS / GN; i++, j += GN)
{
grupos[i].boleta = alumnos[j].boleta;
grupos[i].posicion = j;
}
}
Resultados:
Captura de pantalla.
Conclusiones (Tellez Calan Fernando Iván)
¿Cuál fue su experiencia con la práctica?
La practica no fue tan difícil como la primera, pues teníamos los códigos de las
búsquedas. Algo que si considere un poco complicado fue el cargar los nombres de
los alumnos del archivo que utilizamos.
Si tuvieron errores, ¿Cómo los solucionaron?
Tuvimos un error para lograr hacer que el código leyera el archivo donde estaban los
nombres de los alumnos, lo solucionamos utilizando IA, pues nosotros no podíamos
encontrar la solución adecuada.
Si aprendieron algo nuevo, ¿Qué fue?
La utilidad y eficiencia de la búsqueda binaria para cantidades más grandes de datos.
Conclusiones (Pérez Hernández Angel Adrián)
¿Cuál fue su experiencia con la práctica?
El programa no fue tan complicado de programar ya que teníamos los algoritmos para
codificar las búsquedas.
Si tuvieron errores, ¿Cómo los solucionaron?
Al momento de hacer que leyera el archivo para que detectara los nombres con sus
números de boleta, no lograba leerlo ya hasta que se hizo uso de la IA para solucionar
el problema
Si aprendieron algo nuevo, ¿Qué fue?
Aprendimos como es más rápido la búsqueda Binaria en momentos más complejos
de una lista, ya que la lineal se basa en la partida donde hay pequeñas búsquedas y el
código no es muy complejo
