#include "stdlib.h"
#include "stdio.h"
#include "conio.h"
#include "iostream.h"
#include "ctype.h"
#include "time.h"
// Declaracion de Prototipos
void inicializa ( int a [ 100 ], int *n );
void menu ( char *opcion );
void lee_n_a ( int a [ 100 ], int *n );
void lee_x_a ( int a [ 100 ], int *n );
void lee_r_a ( int a [ 100 ], int *n );
void lee_f_a ( int a [ 100 ], int *n );
void escribe_a ( int a [ 100 ], int n );
void busqueda_l ( int a [ 100 ], int n );
void busqueda_b ( int a [ 100 ], int n );
void lineal ( int a [ 100 ], int n, int x, int *lugar, int *encontrado );
void binary ( int a [ 100 ], int n, int x, int *lugar, int *encontrado, int izq, int der );
void quick ( int a [ 100 ], int n, int izq, int der );
void partition ( int a [ 100 ], int n, int izq, int der, int *m );
void intercambia ( int *a, int *b );
// Declaracion del void main
void main ( void )
{
int corriendo;
char opcion;
int a [ 100 ];
int n;
inicializa ( a, &n );
corriendo = 1;
while ( corriendo == 1 )
{
menu ( &opcion );
switch ( opcion )
{
case 'n': lee_n_a ( a, &n ); break;
case 'x': lee_x_a ( a, &n ); break;
case 'r': lee_r_a ( a, &n ); break;
case 'f': lee_f_a ( a, &n ); break;
case 'e': escribe_a ( a, n ); break;
case 'l': busqueda_l ( a, n ); break;
case 'b': busqueda_b ( a, n ); break;
case 'z': corriendo = 0; break;
default: corriendo = 1; break;
}
}
}
// Declaracion de los voids
void inicializa ( int a [ 100 ], int *n )
{
*n = 3;
a [ 0 ] = 0;
a [ 1 ] = 1;
a [ 2 ] = 2;
}
void lee_n_a ( int a [ 100 ], int *n )
{
int k = 0;
int z;
clrscr ();
cout << endl << "Dame n: "; cin >> *n;
while ( k <= *n - 1 )
{
cout << endl << "Dame a [ " << k << " ]: "; cin >> z;
a [ k ] = z;
k++;
}
}
void lee_x_a ( int a [ 100 ], int *n )
{
char resp;
int k;
int z;
clrscr ();
k = -1;
cout << endl << "Desea Leer Datos ( s / n ): ";
resp = getche ();
resp = tolower ( resp );
while ( resp == 's' )
{
k++;
cout << endl << "Dame a [ " << k << " ]: "; cin >> z;
a [ k ] = z;
cout << endl << "Desea Seguir Leyendo Datos ( s / n ): ";
resp = getche ();
resp = tolower ( resp );
}
*n = k + 1;
}
void lee_r_a ( int a [ 100 ], int *n )
{
int k = 0;
clrscr ();
cout << endl << "Dame n: "; cin >> *n;
randomize ();
while ( k <= *n - 1 )
{
a [ k ] = random ( 100 );
k++;
}
}
void lee_f_a ( int a [ 100 ], int *n )
{
int z;
int k = -1;
int leyendo;
FILE *archivo;
if ( ( archivo = fopen ( "C:\\CUADERNO\\C4Q15.CPP", "r+" ) ) == NULL )
{
cout << endl << "Archivo no Existe!";
}
else
{
leyendo = 1;
while ( leyendo == 1 )
{
if ( ! ( feof ( archivo ) ) )
{
k++;
leyendo = 1;
fscanf ( archivo, "%d\n", &z );
a [ k ] = z;
}
else
{
leyendo = 0;
*n = k + 1;
}
}
cout << endl << "n: " << *n;
getch();
fclose ( archivo );
}
}
void menu ( char *opcion )
{
clrscr();
cout << endl << "n lectura de n elementos ";
cout << endl << "x lectura de x elementos ";
cout << endl << "r lectura de n elementos al azar ";
cout << endl << "f lectura de n elementos por archivo";
cout << endl;
cout << endl << "e escritura del arreglo ";
cout << endl;
cout << endl << "l busqueda lineal ";
cout << endl << "b busqueda binaria ";
cout << endl;
cout << endl << "z alir ";
cout << endl;
cout << endl << "Opcion: ";
*opcion = getche();
*opcion = tolower ( *opcion );
}
void busqueda_l ( int a [ 100 ], int n )
{
int x;
int lugar;
int encontrado;
cout << endl << "Dame el Numero a Buscar x: "; cin >> x;
cout << endl << " Numero a Buscar x: " << x;
lineal ( a, n, x, &lugar, &encontrado );
if ( encontrado == 1 )
{
cout << endl << "Exito!";
cout << endl << "El Numero x = " << x;
cout << endl << "Se Encontro Aplicando Algoritmo de Busqueda Lineal ";
cout << endl << "Lugar = " << lugar;
getch ();
}
else
{
cout << endl << "Fracaso!";
cout << endl << "No se Encontro en Ningun Lugar";
getch ();
}
}
void busqueda_b ( int a [ 100 ], int n )
{
int x;
int lugar;
int encontrado;
cout << endl << "Dame el Numero a Buscar x: "; cin >> x;
cout << endl << " Numero a Buscar x: " << x;
quick ( a, n, 0, n - 1 );
binary ( a, n, x, &lugar, &encontrado, 0, n - 1 );
if ( encontrado == 1 )
{
cout << endl << "Exito!";
cout << endl << "El Numero x = " << x;
cout << endl << "Se Encontro Aplicando Algoritmo de Busqueda Binaria ";
cout << endl << "Lugar = " << lugar;
getch ();
}
else
{
cout << endl << "Fracaso!";
cout << endl << "No se Encontro en Ningun Lugar";
getch ();
}
}
void lineal ( int a [ 100 ], int n, int x, int *lugar, int *encontrado )
{
int buscando = 1;
int k = 0;
while ( buscando == 1 )
{
if ( x == a [ k ] )
{
buscando = 0;
*encontrado = 1;
*lugar = k;
}
else
{
k++;
if ( k <= n - 1 )
{
buscando = 1;
}
else
{
buscando = 0;
*encontrado = 0;
*lugar = -1;
}
}
}
}
void binary ( int a [ 100 ], int n, int x, int *lugar, int *encontrado, int izq, int der )
{
int m;
if ( der < izq )
{
*lugar = -1;
*encontrado = 0;
}
else
{
if ( izq == der )
{
if ( x == a [ izq ] )
{
*lugar = der;
*encontrado = 1;
}
else
{
*lugar = -1;
*encontrado = 0;
}
}
else
{
m = ( izq + der ) / 2;
if ( x == a [ m ] )
{
*lugar = m;
*encontrado = 1;
}
else
{
if ( x < a [ m ] )
{
binary ( a, n, x, &*lugar, &*encontrado, izq, m - 1 );
}
else
{
binary ( a, n, x, &*lugar, &*encontrado, m + 1, der );
}
}
}
}
}
void escribe_a ( int a [ 100 ], int n )
{
clrscr ();
int k = 0;
while ( k <= n - 1 )
{
cout << endl << "a [ " << k << " ] = " << a [ k ];
k++;
}
cout << endl << "n = " << n;
getch ();
}
void partition ( int a [ 100 ], int n, int izq, int der, int *m )
{
int temp;
int bajo;
int alto;
temp = a [ izq ];
alto = der;
bajo = izq;
while ( bajo < alto )
{
while ( a [ bajo ] <= temp && bajo < alto )
{
bajo++;
}
while ( temp < a [ alto ] )
{
alto--;
}
if ( bajo < alto )
{
intercambia ( &a [ bajo ], &a [ alto ] );
}
}
a [ izq ] = a [ alto ];
a [ alto ] = temp;
*m = alto;
}
void intercambia ( int *a, int *b )
{
int temp;
temp = *a;
*a = *b;
*b = temp;
}
void quick ( int a [ 100 ], int n, int izq, int der )
{
int m;
if ( der <= izq )
{ // Termina llamada recursiva;
}
else
{ // Haciendo Particion;
partition ( a, n, izq, der, &m );
quick ( a, n, izq, m - 1 );
quick ( a, n, m + 1, der );
}
}