Apostar y ganar

Click Now!

sábado, 1 de junio de 2013

Ordenacion y busqueda c ejercicios resueltos

//BUSQUEDA.CPP (Ordenacion y busqueda)
//El programa fue compilado con Turbo C++ 3.0
//Descripcion de BUSQUEDA.CPP
//Los metodos de ordenacion que se desarrollaron son:
//Shell, Burbuja, Insercion, Sacudida,Seleccion y el Quicksort
//Nota.- El Quicksort se elaboro recursivamente e iterativamente.
//Los metodos de busqueda que se programaron fueron:
//Busqueda lineal y Busqueda Binaria.
//para que estos metodos funciones correctamente la lista debe estar ordenada.

#include <iostream.h>//para cout y cin
#include <conio.h>   //para getch
#include <stdlib.h>  //para exit y system

#define NUMEL 50

class BUSQUEDA{
private:
int izquierda,derecha,puntomedio,max,nums[NUMEL];
int elemento,ubicacion,ubicacion2,i;

public:
BusquedaBinaria(int[],int,int);
BusquedaLineal(int[],int,int);
MenuMain(void);
void Pedir(int *,int);
};

class ORDENACION{
private:
int min,indicemin,temp,movimientos;
int i,j,mitad,x;
int inter,opc;
int a[5];
OrdRap(int*,int,int);
void qs(int *,int,int);
public:

void Quicksort_Iterativo(int[],int);
Quicksort(int*,int);
Seleccion(int*,int);
Burbuja(int*,int);
Shell(int*,int);
Sacudida(int*,int);
Insercion(int*,int);

void Pedir(int*,int);
void Visualiza(int*,int,int,int);
Elementos();
MenuMain(void);
Menu_Asc_Des(void);

};

int ORDENACION::Quicksort(int *num,int numel)
{
 int mov=OrdRap(num,0,numel-1);
 return mov;
}

  ORDENACION::OrdRap(int *num,int inf,int sup)
{
 register int izq,der;
 movimientos=0;
 izq=inf; der=sup;
 mitad=num[(izq+der)/2];
 do{
   while(num[izq]<mitad && izq < sup) izq++; movimientos++;
   while(mitad<num[der] && der > inf) der--; movimientos++;
   if(izq<=der){
   x=num[izq],num[izq]=num[der],num[der]=x;
   izq++; der--; movimientos++;
   }

 }while(izq<=der);
 if(inf<der) OrdRap(num,inf,der);
 if(izq<sup) OrdRap(num,izq,sup);
 return movimientos;
}

void ORDENACION::Quicksort_Iterativo(int *num,int numel)
{
  qs(num,0,numel-1);
}

void ORDENACION::qs(int *num,int inf,int sup)
{
  struct TipoPila{
  int inf,sup;
  }Pila[NUMEL];
  register int izq,der;
  int mitad,x,p;
  p=1,Pila[p].inf=inf,Pila[p].sup=sup;
  do{
inf=Pila[p].inf,sup=Pila[p].sup,p--;
do{
 izq=inf; der=sup;
 mitad=num[(izq/der)/2];
 do{
while(num[izq] < mitad && izq < sup) izq++;
while(mitad < num[der] && der > inf) der--;
if(izq<=der){
 x=num[izq],num[izq]=num[der],num[der]=x;
 izq++; der--;
}
 }while(izq<=der);
 if(izq<sup){
  p++,Pila[p].inf=izq,Pila[p].sup=sup;
 }
 sup=der;
}while(inf<der);
  }while(p);
}

ORDENACION::Insercion(int *num,int numel)
{
  movimientos=0;
  for(i=1;i<numel;++i){
   temp=num[i];
   for(j=i-1;(j>=0)&&(temp<num[j]);j--)
num[j+1]=num[j];
num[j+1]=temp;
movimientos++;
  }
  return movimientos;
}

 ORDENACION::Shell(int *num,int numel)
{

 movimientos=0;
 a[0]=9;a[1]=5;a[2]=3;a[3]=2;a[4]=1;
 for(register int k=0;k<5;k++){
  temp=a[k];
  for(i=temp;i<numel;++i){
   x=num[i];
   for(j=i-temp;(x<num[j])&&(j>=0);j=j-temp)
num[j+temp]=num[j];
num[j+temp]=x;

   }
   movimientos++;
  }
  return movimientos;
}

ORDENACION::Sacudida(int *num,int numel)
{

  movimientos=0;
  do{

inter=0;
for(i=numel-1;i>0;--i){
if(num[i-1]>num[i]){
 temp=num[i-1];
 num[i-1]=num[i];
 num[i]=temp;
 inter=1;
 movimientos++;
}
}
for(i=1;i<numel;++i){
 if(num[i-1]>num[i]){
  temp=num[i-1];
  num[i-1]=num[i];
  num[i]=temp;
  inter=1;
  movimientos++;
 }
}

   }while(inter);
  return movimientos;
}

ORDENACION::Seleccion(int *num,int numel)
{
  movimientos=0;
  for(i=0;i<(numel-1);i++){
min=num[i];
indicemin=i;
for(j=i+1;j<numel;++j){
if(num[j]<min){
 min=num[j];
 indicemin=j;
}
}
if(min<num[i]){
temp=num[i];
num[i]=min;
num[indicemin]=temp;
movimientos++;
}

  }
  return movimientos;
}

ORDENACION::Burbuja(int *num,int numel)
{
 movimientos=0;
 for(i=0;i<numel-1;i++){
  for(j=1;j<numel;j++){
   if(num[j]<num[j-1]){
temp=num[j];
num[j]=num[j-1];
num[j-1]=temp;
movimientos++;
   }
  }
 }
 return movimientos;
}

  int BUSQUEDA::MenuMain(void)
  {
   int opc;
   while(opc<1 || opc > 3){
 system("cls");
 gotoxy(29,9);
 cout<<"METODOS DE BUSQUEDA.";
 gotoxy(32,10); cout<<"1. Busqueda Lineal.";
 gotoxy(32,11); cout<<"2. Busqueda Binaria.";
 gotoxy(32,12); cout<<"3. Salir.";
 gotoxy(32,14); cout<<"opcion-> ";
 cin>>opc;
   }
   return opc;
  }

  int ORDENACION::MenuMain(void)
  {
   int opc;
   while(opc < 1 || opc > 7)
{
 system("cls");
 gotoxy(29,9);  cout<<"METODOS DE ORDENACION\n";
 gotoxy(33,10); cout<<"1. Burbuja";
 gotoxy(33,11); cout<<"2. Insercion";
 gotoxy(33,12); cout<<"3. Quicksort";
 gotoxy(33,13); cout<<"4. Shell";
 gotoxy(33,14); cout<<"5. Seleccion";
 gotoxy(33,15); cout<<"6. Sacudida";
 gotoxy(33,16); cout<<"7. Salir.";
 gotoxy(33,18); cout<<"Opcion-> ";
 cin>>opc;
}
   return opc;
}
   void BUSQUEDA::Pedir(int *num,int n)
  {
int i;
system("cls");
for(i = 0; i < n; i++)
{
 gotoxy(22, i + 1);
 cout<<"Ingresa valor "<<i+1<<": ";
 cin>>num[i];
}
  }

  void ORDENACION::Pedir(int *num,int n)
  {
system("cls");
for(i = 0; i < n; i++)
{
 gotoxy(22, i + 1);
 cout<<"Ingresa valor "<<i+1<<": ";
 cin>>num[i];
}
  }

  int ORDENACION::Menu_Asc_Des(void)
  {
   int opc;
   while(opc < 1 || opc > 2){
 system("cls");
 gotoxy(29,9);  cout<<"METODOS DE ORDENACION\n";
 gotoxy(33,10); cout<<"1. Ascendente\n";
 gotoxy(33,11); cout<<"2. Descendente\n";
 gotoxy(33,12); cout<<"Opcion: ";
 cin>>opc;
}
return(opc);
}



 BUSQUEDA::BusquedaBinaria(int lista[],int tamanho,int clave)
 {

  izquierda=0;
  derecha=tamanho-1;
  while(izquierda<=derecha)
  {
   puntomedio=((izquierda+derecha)/2);
   if(clave==lista[puntomedio])
   {
return puntomedio;
   }
   else if (clave>lista[puntomedio])
izquierda=puntomedio+1;
   else
derecha=puntomedio-1;
   }
   return -1;
  }

BUSQUEDA::BusquedaLineal(int lista[],int tamanho,int clave)
{
 for(register int i=0;i<tamanho;i++)
 {
  if(lista[i]==clave)
  return i;
 }
 return -1;
}

  void ORDENACION::Visualiza(int *num, int numel,int opc,int mov)
{
if(numel >= 40) x = 1;
else x = 40 - numel;
 do{
if(opc==1){
system("cls");
gotoxy(x-14,11); cout<<"Los movimientos que se hicieron son: ";
cout<<mov;
gotoxy(x-14,12); cout<<"Los Numeros Ordenados Ascendentemente son : ";
gotoxy(x,15);
for(i = 0; i<numel; i++)
cout<<num[i]<<" ";
getch();
}
if(opc==2){
system("cls");
gotoxy(x-14,11); cout<<"Los movimientos que se hicieron son: ";
cout<<mov;
gotoxy(x-14,12); cout<<"Los Numeros Ordenados Descendentemente son : "<<endl;
gotoxy(x,14);
for(int j = numel; j>0; j--)
cout<<num[j-1]<<" ";
getch();
}

  }while(opc<1||opc>2);
}

  void Ordenaciones(void)
{
int numel, opc,OPC;
char salir;
int num[NUMEL]={0};
ORDENACION p;

  do{
system("cls");
gotoxy(19,12);
cout<<"Numero de elementos: ";
cin>>numel;
if(numel == 0){
 cout<<"\n\t\t  Numero no valido";
 getch();
 exit(1);
}
opc = p.MenuMain();
if(opc == 7){
 exit(1);
}
p.Pedir(num, numel);
OPC=p.Menu_Asc_Des();
switch(opc)
{
 case 1: int res=p.Burbuja(num, numel);
 p.Visualiza(num, numel,OPC,res);  break;
 case 2: int res2=p.Insercion(num, numel);
 p.Visualiza(num, numel,OPC,res2); break;
 case 3: int res3=p.Quicksort(num, numel);
 p.Visualiza(num, numel,OPC,res3); break;
 case 4: int res4=p.Shell(num, numel);
 p.Visualiza(num, numel,OPC,res4); break;
 case 5: int res5=p.Seleccion(num, numel);
 p.Visualiza(num, numel,OPC,res5); break;
 case 6: int res6=p.Sacudida(num,numel);
 p.Visualiza(num, numel,OPC,res6); break;
}
gotoxy(25,18);
cout<<"Desea volver a introducir datos (s/n): ";
cin>>salir;
  }while(salir!='n');
  system("cls");

}


   void Busquedas(void)
   {
BUSQUEDA b;
int numel, opc,clave;
char OPC;
int *num=NULL;
do{
system("cls");
gotoxy(19,12); cout<<"Numero de elementos: ";
cin>>numel;
if(numel == 0){
 cout<<"\n\t\t  Numero no valido";
 getch();
 exit(1);
}
opc = b.MenuMain();
if(opc == 3){
 exit(1);
}
 b.Pedir(num, numel);
 switch(opc){
  case 1: system("cls");
  gotoxy(25,5);
  cout<<"Numero a buscar: ";
  cin>>clave;
  int res1=b.BusquedaLineal(num,numel,clave);
  if(res1==-1){
gotoxy(25,6);
cout<<"El Numero no se encontro en la lista.";
getch();
  }
  else{
gotoxy(25,6);
cout<<"El Numero si se encontro en la ubicacion del indice: "<<res1+1;
getch();
  }
  break;

  case 2: system("cls");
  gotoxy(25,5);
  cout<<"Numero a buscar: ";
  cin>>clave;
  int res2=b.BusquedaBinaria(num,numel,clave);
  if(res2==-1){
gotoxy(25,8);
cout<<"El Numero no se encontro en la lista.";
getch();
  }
  else{
gotoxy(25,8);
cout<<"El numero si se encontro en la ubicacion del indice: "<<res2+1;
getch();
  }
  break;
 }
  gotoxy(25,13);
  cout<<"Desea Introducir mas datos (s/n): ";
  cin>>OPC;
   }while(OPC!='n');
   system("cls");
}

  int main(void)
  {
   int opc;
   system("cls");
   gotoxy(30,8);  cout<<"Ordenacion y Busqueda.";
   gotoxy(30,10); cout<<"1. Tipos de Ordenaciones.";
   gotoxy(30,11); cout<<"2. Tipos de Busqueda.";
   gotoxy(30,12); cout<<"3. Salir.";
   gotoxy(30,14); cout<<"Opcion -> ";
   cin>>opc;
   switch(opc){
case 1: Ordenaciones();
break;
case 2: Busquedas();
break;
case 3: exit(0);
system("cls");
break;
   }
   return 0;
}

Todo codigos