Record – Ejemplo 1

Enunciado

Escribir el subprograma de búsqueda binaria aplicado a un vector de registros. Suponer que se quiere buscar la posición que ocupa un cierto elemento tipo registro en un vector. Cada registro está formado por los siguientes campos :

* Apellido y Nombre ( 20 caracteres )

* Legajo ( 4 dígitos )

* Categoría ( 1 .. 10 )

El vector contiene todos los datos de los empleados de una empresa y está ordenado por apellido y nombre. Se quieren obtener todos los datos correspondientes a un dado empleado cuyo nombre es dato de entrada. Escribir un programa principal de prueba.

Código

Python

def BusBin(lista, k):
    i=0
    s=len(lista)-1
    pm= (i+s) // 2
    
    while i<=s and lista[pm]!=k :
        if k>lista[pm]:
            i=pm+1
        else:
            s=pm-1
            
        pm=(i+s) // 2
        
    if i>s: pm=-1
    
    return pm


def main():
    empls = {}
    
    apnom = input("Nombre/Name: ").title()
    while apnom !="S":
        legajo = int(input("Legajo/File: "))
        categ = int(input("Categoria/Category: "))
        
        empls[apnom] = [legajo, categ]
        
        apnom = input("Nombre/Name\nPresionar S para salir/Press S to exit\n: ").title()
    
    print("\n")
    print("Nombre".rjust(10),"Legajo".rjust(35),
"Categoría".rjust(20),"\n")
    for cod, dato in empls.items():
        print( cod.rjust(10), str(dato[0]).rjust(35), 
str(dato[1]).rjust(20), "\n")
    
    claves = list(empls)
    
    while True:
        apnom = input( '\nIngresar Nombre a buscar/ Enter name to search: ').title() 

        i = BusBin( claves , apnom )
        
        if i!=-1:
            print( "\nSe encuentra en la posicion/It is found at position: ", i )
        else:
            print( "\nNo se encontro/not found\n" )
            
        resp = input("\nPresionar S para salir/Press S to exit\n").upper()
        if resp == "S": break
main()

C++

#include <iostream>
#include <iomanip>
using namespace std ;
#include <conio.h>
#include <string.h>

struct TEmpleado
{
    char  apnom[20] ;
    int   legajo ;
    int   categ ;
} ;

void BusBin( TEmpleado lista[], char buscado[], int n, 
             int *posicion )
{   
     int i, j, m ;

     *posicion = -1 ; i = 0 ; j = n ;
     do
     {
        m = ( i + j ) / 2 ; 
	if ( strcmp( buscado, lista[m].apnom )<0 )
	    j =  m - 1 ;
      	else 
	    i = m + 1 ;
     }
     while ( strcmp( buscado, lista[m].apnom ) != 0 
             && i <= j ) ;
	if ( strcmp( buscado, lista[m].apnom )==0 )  
            *posicion = m ;
}

int main()
{    
     TEmpleado empls[200], empl ;
     int i, cant ;
   
     i = 0 ;
     printf( "El listado debe ingresarse ordenado 
              alfabeticamente\n" ) ;
     printf( "The list must be entered in 
              alphabetical order\n" ) ;
	
     printf( "\nEnter para comenzar o ESC para salir 
              /Enter to start or ESC to exit\n");
     while( getch() != char (27) )
     {
	printf( "Nombre / Name: " ) ; 
        scanf( "%s", &empls[i].apnom ) ;
	printf( "Legajo / File: " ) ; 
        scanf( "%d", &empls[i].legajo ) ;
	printf( "Categoria / Category: " ) ; 
        scanf( "%d", &empls[i].categ ) ;
      	i++ ;
     }
     cant = i ;
     do
     {
	printf( "\nIngresar Nombre a buscar/Enter 
                 name to search: ") ; 
        scanf( "%s", &empl.apnom ) ;
	BusBin( empls , empl.apnom , cant , &i ) ;
	if ( i >= 0 ) 
           printf( "Se encuentra en la posicion/
                    It is found at position: %d\n", 
                    i ) ;
	else 
           printf( "No se encontro/not found " ) ;

      	printf("\nPresionar ESC para salir/Press 
                ESC to exit\n") ;
     }
     while( getch() != char (27) );
}

Pascal

Program Problema19_2 ;
uses CRT ;
const
    maxcant = 200 ;
type
    nombre = string[20] ;
    empleado  = record
	           apnom : string[20] ;
	           legajo : word ;
	           categ : 1..10 ;
		end ;
    dim = 0..maxcant ;
    listaempls = array[dim] of empleado ;
var
    empls : listaempls ;
    empl  : empleado ;
    i , cant : dim ;

Procedure BusBin( lista: listaempls ; buscado: nombre ; 
                  n: dim ; var posicion: dim) ;
var i , j , m : dim ;
begin
    posicion := 0 ; 
    i := 1 ; 
    j := n ;
    repeat
	m := ( i + j ) div 2 ;
	if buscado < lista[m].apnom
	then j :=  m - 1
	else i := m + 1 ;
    until (buscado = lista[m].apnom) or (i > j) ;
    if buscado = lista[m].apnom then posicion := m ;
end;

begin
    ClrScr ;
    i := 0 ;
    writeln( 'El listado debe ingresarse ordenado 
              alfabeticamente' ) ;
    writeln( 'The list must be entered in 
              alphabetical order' ) ;
    writeln ;
    writeln( 'Enter para comenzar o ESC para salir/
              Enter to start or ESC to exit' ) ;
    while ReadKey<>#27 do
    begin
	i := i+1 ;
	with empls[i] do
	begin
            write( 'Nombre/Nome: ') ; 
            readln( apnom ) ;
            write( 'Legajo/File: ') ; 
            readln( legajo ) ;
            write( 'Categoria/Category: ') ; 
            readln( categ ) ;
	end ;
	writeln( 'Enter para comenzar o ESC para 
                  salir/Enter to start or ESC 
                  to exit' ) ;
    end ;
    cant := i ;
    repeat
	 write( 'Ingresar Nombre a buscar/Enter 
                 name to search: ') ; 
	 readln( empl.apnom ) ;
	 BusBin( empls, empl.apnom, cant, i ) ;
	 if i > 0 
         then writeln( 'Se encuentra en la 
                        posicion/It is found 
                        at position: ', i )
	 else writeln( 'No se encontro/not found' ) ;
	 writeln( 'Presionar ESC para salir/
                   Press ESC to exit' ) ;
    until ReadKey=#27
end.

Diagramas

Subprograma

Programa Principal