HeapSort en C++

Hola amig@s esta vez les traigo otro de los metodos de ordenacion interna en esta ocasion se trata del Heapsort este metodo es el mas eficiente de todos los metodos de ordenacion interna ya que consiste en almacenar todos los elementos del vector de N elementos a ordenar en un montículo (heap), y luego extraer el nodo que queda como nodo raíz del montículo (cima) en sucesivas iteraciones obteniendo el conjunto ordenado. Basa su funcionamiento en una propiedad de los montículos, por la cual, la cima contiene siempre el menor elemento (o el mayor, según se haya definido el montículo) de todos los almacenados en él.

La estructura de un monticulo es similar a la de un arbol biario por lo que tendra un nodo padre y 2 nodo hijos en nuestro caso tomaremos nuestro monticulo como maximal esto quiere decir que para construir dicho monticulo  el nodo padre siempre tendra que ser mayor que sus hijos cuando se cumpla dicha condicion extraeremos el nodo raiz (al decir extraer es intercambiar el nodo raiz que se encuentra en la primera posicion del vector por el ultimo de dicho vector) y volveremos a reconstruir el monticulo esta vez con el vector de N-1 y asi sucesivamente hasta que quede completamente ordenado.

Imagen:

Codigo:

Heapsort.cpp

#include"Heapsort.h"
#include<iostream>
using namespace std;
void main(){
 Heapsort h;
 int c;
 cout<<"cuantos datos: ";
 cin>>c;
 for(int i=1;i<=c;i++){
  system("cls");
  cout<<"dato["<<i<<"]: ";
  cin>>h.lista[i];
 }
 system("cls");
 /**/cout<<"Lista Original"<<endl<<endl;
 for(int i=1;i<=c;i++){
  cout<< h.lista[i]<<"  ";
 }
 h.heapsort(h.lista,c);
 cout<<endl;
 cout<<endl<<"Lista Ordenada"<<endl<<endl;
 for(int i=1;i<=c;i++){
  cout<< h.lista[i]<<"  ";
 }cout<<endl<<endl;
 system("pause");
}

Heapsort.h:

#include<iostream>
#include<windows.h>
using namespace std;
#define MAX 100
class Heapsort{
public:
 int lista[MAX]; 
 int j,temp,hijo;
 bool esmonticulo;
 void heapsort(int[] ,int );
 void monticulo(int[] ,int ,int );
};
void Heapsort::monticulo(int lista[],int primero,int ultimo){
 cout<<endl<<endl<<"Nuevo Monticulo"<<endl<<endl;
 esmonticulo=false;
 for(int k=primero; k<=ultimo; k++){
  cout<<lista[k]<<"\t";
 }cout<<endl;
 while((primero<=ultimo/2)&&!esmonticulo){
  if(2*primero==ultimo){
   hijo=2*primero;
  }
  else{
   if(lista[2*primero]>lista[2*primero+1]){
    hijo=2*primero; 
   }else{
    hijo=2*primero+1;
   }
  }if(lista[primero]<lista[hijo]){
   cout<<endl<<endl<<"Cambio de "<<lista[primero]<<" por "<<lista[hijo]<<endl<<endl;
   temp=lista[primero];
   lista[primero]=lista[hijo];
   lista[hijo]=temp;
   primero=hijo;
  }else{
   esmonticulo=true;
  }
 }
}

void Heapsort::heapsort(int lista[],int n){
 for(j=n/2;j>=0;j--){
  monticulo(lista,j,n);
 }
 for(j=n;j>=1;j--){
  temp=lista[0];
  lista[0]=lista[j];
  lista[j]=temp;
  cout<<endl<<"Sacamos al dato "<<lista[j]<<" de la lista."<<endl<<endl;
  cout<<endl<<"************************************************************"<<endl<<"Nueva Lista: "<<endl<<endl;
  for(int k=0; k<j; k++){
  cout<<lista[k]<<"\t";
  }Sleep(2000);cout<<endl;
  monticulo(lista,0,j-1);
 }
 
}

Descarga el código fuente desde aquí:

SplashSreen en Java con Barra de Carga Utilizando Hilos (Threads)

Hola amig@s esta vez les les mostrare como hacer que sus aplicaciones parezcan un poco mas profesionales añadiendoles un SplashScreen para ello vamos a utilizar hilos para hacer que se complete una barra de progreso y utilizaremos una imagen .png con transparencia para utilizarla como un logo (No es necesario que la imagen sea con transparencia ni tiene que ser únicamente .png, todo queda al gusto de cada quien).

Capturas:

Descarga el código desde aquí.

Libreria Console.h v1.0 C++

Hola amig@s esta vez les traigo algo distinto que solo subir código de programas. En esta ocasión quiero compartir con ustedes un conjunto de funciones que he recopilado y otras que de alguna forma he escrito a mi conveniencia y decidí crear una librería estática pero esto no quiere decir que solo subiré el .h y el .lib y que ustedes tengan que linkear la librería para poder utilizar las funciones contenidas en dicha librería sino que pondré 3 diferentes formas de descarga la primera sera descargar todo el proyecto que por el momento esta en VS2010 express; la segunda el .lib con sus respectivos archivos fuentes y la tercera forma son únicamente los archivos fuentes.

Archivos Contenidos:

- CONSOLE.h : contiene todos los prototipos de las funciones de la librería.

- CONSOLE.cpp : contiene todas las definiciones de las funciones.

- Keyboard.h : contiene las definiciones de los códigos de algunas teclas. En la próxima versión espero poder completado esta cabecera ya que solo resta incluir las teclas especiales (alt,ctrl,f1,etc), también símbolos entre otras.

- testLIB.cpp : contiene un pequeño ejemplo de como utilizar el mouse en consola y del teclado.

Funciones:

void initConsole( void );//iniciamos los manejadores de entrada y salida de la consola 
void Color( int );//Cambiamos el color de la fuente 
void OcultaCursor( void );//Ocultamos el cursor
void gotoxy( int , int );//Posicionamos el cursor en las cordenadas x y
void clearToColor( int );//Borramos la consola por un color de 0 a 15 (0 = Negro, 15 = Blanco Brillante)
void textOut(int, int, char*, int );//Mostramos texto en las cordenada x y 
void ErrorExit ( char*, char* );//Si ocurre un error Mostramos un mensaje y salimos de la aplicacion
void drawRect( int[2], int[2], int );//Dibuja un un rectangulo del color que querramos
void drawRect( int[2], int[2], char*, int );//Dibuja un un rectangulo del color que querramos y le enviamos el caracter que queremos de muestre  
void drawFillRect( int[2], int[2], int );//Dibuja un un rectangulo relleno del color que querramos
void drawFillRect( int[2], int[2], char*, int );//Dibuja un un rectangulo relleno del color que querramos y le enviamos el caracter que queremos de muestre
void drawLineH( int[2], int, int );//Dibuja una linea horizontal del color que querramos
void drawLineH( int[2], int, char*, int );//Dibuja una linea horizontal del color y caracter que querramos
void drawLineV( int, int[2], int );//Dibuja una linea vertical del color que querramos
void drawLineV( int, int[2], char*, int );//Dibuja una linea vertical del color y caracter que querramos
COORD CoordMouse( void );//obtiene las coordenadas del mouse
void readConsole( void );//leemos los eventos que estan ocurriendo en la consola
bool keypressed( void );//vemos si se ha presionado una tecla
int readKey( void );//leemos el codigo de la tecla presionada
bool dobleClick( void );//vemos si se ha hecho doble click
int click( void );//vemos si se ha hecho click izq retorna 1 y si es derch retorna 2

Capturas:

Codigo:

#include
#include"CONSOLE.h"
using namespace std; 
int main(){
	int x[]={3,15},y[]={3,20},x2[]={20,32},y2[]={3,20};
	int f=0;
	COORD cr;
	/**/textOut(10,0,"Dibujando rectangulos",6);
	drawRect(x,y,7);
	drawRect(x2,y2,"*",9);
	Sleep(3000);
	clearToColor(1);
	textOut(10,0,"Dibujando rectangulos rellenos",6);
	drawFillRect(x,y,7);
	drawFillRect(x2,y2,"*",9);
	Sleep(3000);
	clearToColor(1);
	textOut(10,0,"Dibujando Lineas Horizontales",6);
	drawLineH(x,3,9);
	drawLineH(x2,3,"M",7);
	Sleep(3000);
	clearToColor(1);
	textOut(10,0,"Dibujando Lineas Verticales",6);
	drawLineV(3,y,9);
	drawLineV(6,y,"N",8);
	Sleep(2000);
	clearToColor(1);
	textOut(10,10,"Uso del mouse y teclado",6);
	Sleep(4000);
	clearToColor(1);
	fflush(stdin);
	fflush(stdout);
	/*Libera la vieja consola y comienza con una nueva ya 
	que por el momento hay conflicto la funcion clearToColor() con el uso del mouse dentro
	de la consola*/
	FreeConsole();
	AllocConsole();
	initConsole();
	do{
		Color(7);
		readConsole();
		cr=CoordMouse();
		gotoxy(1,0);cout<<"x: "<<(int)cr.X<<"Y: "<<(int)cr.Y;
		gotoxy(1,1);cout<<"tecla: "<<(char)f;
		textOut(1,2,"Para salir presione enter",8);
		
		if(click() == 1){
			cr=CoordMouse();
			gotoxy(cr.X,cr.Y);cout<<"CLICK IZQ";
		}else
			if(click() == 2){
				cr=CoordMouse();
				gotoxy(cr.X,cr.Y);cout<<"CLICK DER";
			}
		/* Reporta si se dio un doble click */
		if (dobleClick()){
			cr=CoordMouse();
			gotoxy(cr.X,cr.Y);cout<<"DOBLE CLICK ";
		}

		
		if(keypressed())
			f=readKey();
		Sleep(60);
	}while(f!=KEY_ENTER);
	ErrorExit("Saliendo del programa","TEST");
	return 0;
}

Descarga:

- Proyecto VS2010.

- Librería estática mas fuentes.

- Archivos Fuentes.

Recorrido por Niveles En Arboles

Hola amig@s en esta ocacion les mostrare la funcion de recorrido por niveles (anchura) en arboles.
Como funciona este recorrido pues como su nombre lo dice va por niveles comenzando por la raiz hasta llegar al ultimo nodo del arbol; primeramente ingresamos el nodo raiz en una cola, luego sacamos este valor de la cola y mostramos su contenido y ahora vemos si hay valores en los nodos izquerdo y derecho respectivamente si no son nulos insertamos sus valores en la cola repetimos esto hasta que la cola quede vacia.

Seudocodigo:

recorrido_nivel(Tarbol a)
nodo aux;
si (a != NULL)
encolar(a);
mientras (!colavacia()) hacer
aux=desencolar();
   mostrar aux
si (aux->izq != NULL) encolar(aux->izq);
si (aux->der != NULL) encolar(aux->der);
fin mientras
fin si


Capturas:

Codigo:

Recorrido por nivel:

void arbol::Recorrido_Nivel(TREE aux){
	if(aux){
	Cola cola;
	TREE a;
		cola.insertar(aux);
		while(!cola.colavacia()){
			a=cola.quitar();
			cout<valor<Izdo!=NULL){
				cola.insertar(a->Izdo);
			}
			if(a->Dcho!=NULL){
				cola.insertar(a->Dcho);
			}
		}
	}
}

Cola.h

#include 
#include 
using namespace std;

////////////////////////cola
class nodoc{
public:
	Tarbol dato;
	nodoc *siguiente;
	nodoc(Tarbol n, nodoc *sig=NULL){
		dato=n;
		siguiente=sig;
	}
};
typedef nodoc *pnodo;

class Cola{
//private:
public:
	pnodo frente;
	pnodo final;

	Cola(){
		frente=NULL;
		final=NULL;
	}
	bool colavacia();
	void insertar(int v);
	int quitar();
};


bool Cola::colavacia(){return frente==NULL;}

void Cola::insertar(int v){
	if(colavacia()){
		frente=new nodoc(v);
		final=frente;
	}else{
		final->siguiente=new nodoc(v);
		final=final->siguiente;
	}
}
Tarbol Cola::quitar(){
	pnodo aux;
	Tarbol x;
	if(colavacia())
		return 0;
	aux=frente;
	x=aux->dato;
	frente=frente->siguiente;
	delete(aux);
	return x;
}

descarga el código aquí.