Mostrando entradas con la etiqueta estructura de datos. Mostrar todas las entradas
Mostrando entradas con la etiqueta estructura de datos. Mostrar todas las entradas

viernes, 3 de enero de 2014

Ordenación Externa: Mezcla Equilibrada en C++

Mezcla Equilibrada.

La idea central de este método consiste en realizar las particiones tomando secuencias ordenadas de máxima longitud en lugar de secuencias de tamaño fijo previamente determinadas.

Luego realiza la fusión de las secuencias ordenadas, alternativamente sobre dos archivos aplicando estas acciones en forma repetida se lograra que el archivo original quede ordenado.

Para la realización de este proceso de ordenación se necesitarán cuatro archivos. El archivo original F y tres archivos auxiliares a los que se denominaran F1, F2 y F3. De estos archivos, dos serán considerados de entrada y dos de salida; esto, alternativamente, con el objeto de realizar la fusión-partición. El proceso termina cuando en la realización de una fusión-partición el segundo archivo quede vacío.

F: 09 75 14 68 29 17 31 25 04 05 13 18 72 46 61

PARTICIÓN INICIAL F2: 09 75 29 25 46 61 F3: 14 68 17 31 04 05 13 18 72

PRIMERA FUSION-PARTICION F: 09 14 68 75 04 05 13 18 25 46 61 72 F1: 17 29 31

SEGUNDA FUSION-PARTICION F2: 09 14 17 29 31 68 75 F3: 04 05 13 18 25 46 61 72

TERCERA FUSION-PARTICION F: 04 05 09 13 14 17 18 25 29 31 46 61 68 72 75 F1:
10. Si B1=FALSO entonces Escribir R1 en F 11. {Fin del condicional del paso 10} 12. Si B2=FALSO entonces Escribir R2 en F 13. {Fin del condicional del paso 12} 14. Repetir (mientras no sea el fin de archivo de F1) Leer R1 de F1 Escribir R1 en F 15. {Fin del condicional del paso 14} 16. Repetir (mientras no sea el fin de archivo de F2) Leer R2 de F2 Escribir R2 en F 17. {Fin del condicional del paso 16}

Obsérvese que al realizar la tercera fusión-partición el segundo archivo queda vació, por lo que se puede afirmar que el archivo ya se encuentra ordenado.

Ordenación Externa: Mezcla Directa

Mezcla Directa.

El método de ordenación por mezcla directa es probablemente el más utilizado por su fácil comprensión.

La idea central de este algoritmo consiste en la realización sucesiva de una partición y una fusión que produce secuencias ordenadas de longitud cada vez mayor. En la primera pasada la partición es de longitud 1, y la fusión o mezcla produce secuencias ordenadas de longitud 2. En la segunda pasada la partición es de longitud 2, y la fusión o mezcla produce secuencias ordenadas de longitud 4. Este proceso se repite hasta que la longitud de la secuencia de la secuencia para la partición sea mayor o igual que el número de elementos del archivo original.

Ejemplo:

Supóngase que se desea ordenar las claves del archivo F. para realizar tal actividad se utilizan dos archivos auxiliares a los que se les denominará. F1 y F2.

F: 09 75 14 68 29 17 31 25 04 05 13 18 72 46 61.

Primera pasada:

Partición en secuencias de longitud 1.

F1: 09’ 14’ 29’ 31’ 04’ 13’ 72’ 61’

F2: 75’ 68’ 17’ 25’ 05’ 18’ 46’

Fusión en secuencias de longitud dos:

F: 09 75’ 14 68’ 17 29’ 25 31’ 04 05’ 13 18’ 46 72’ 61’

Segunda pasada:

Partición de secuencia de longitud 2

F1: 09 75’ 17 29’ 04 05’ 46 72’

F2: 14 68’ 25 31’ 13 18’ 61’

Fusión en secuencias de longitud 4.

F: 09 14 68 75’ 17 25 29 31’ 04 05 13 18’ 46 61 72’

Tercera pasada.

Partición en secuencia de longitud 4.

F1: 09 14 68 75’ 04 05 13 18’

F2: 17 25 29 31’ 46 61 72’

Fusión en secuencias de longitud 8

F: 09 14 17 25 29 31 68 75’ 04 05 13 18 46 61 72’

Cuarta pasada.

Partición en secuencia de longitud 8

F1: 09 14 17 25 29 31 68 75’

F2: 04 05 13 18 46 61 72’

Fusión en secuencias de longitud 16

F: 04 05 09 13 14 17 18 25 29 31 46 61 68 72 75

jueves, 2 de enero de 2014

Ordenación Externa: Intercalación de Archivos en C++

Intercalación de archivos.

Por intercalación de archivos se entiende la unión de dos o más archivos ordenados de acuerdo con un campo clave en un solo archivo.

Ejemplo: se tienen dos archivos F1, F2 ordenados de acuerdo a un capo clave.

F1: 06 09 18 20 35

F2: 10 16 25 28 66 82 87

Debe producirse entonces un archivo F3 ordenado como resultado de la mezcla de F1 y F2. Solo pueden ser accedidas directamente dos claves la primera del archivo F1 y la segunda del archivo F2.

Las comparaciones que se realizan para producir el archivo F3 son las siguientes.

(06 < 10) , si se cumple la condición se escribe 06 en el archivo de salida F3, y se vuelve a leer otra clave de F1 (09)

(09 <10), si se cumple la condición se escribe 09 en el archivo F3 y se vuelve a leer otra clave de F1 (18)

(18<10), no se cumple la condición , se escribe 10 en el archivo de salida F3 y se vuelve a leer otra clave de F2,

El estado de los archivos F1, F2 Y F3 hasta el momento es el siguiente.

F1: 06 09 18 20 35

F2: 10 16 25 28 66 82 87

F3: 06 09 10

El proceso continúa hasta que en uno u otro archivo se detecte el fin de archivo, en tal caso solo se tendrán que trascribir las claves del archivo no vacío al archivo de salida F3. Este es el resultado final de la intercalación de F1 y F2

F3: 06 09 10 16 18 20 25 28 35 66 82 87.



Imagen:





Código:

APP Intercalación De Archivo.cpp:
#include<iostream>
using namespace std;

#include"gotoxy.h"
#include"Clase_Intercalacion_De_Archivo.h"
#include"Menu_Intercalación_De_Archivo.h"

int main(){
	Menu_Intercalacion_De_Archivo();
	return 0;
}

Clase_Intercalacion_De_Archivo.h:
#include<fstream> //Libreria para los ficheros

class Intercalacion{
private:
	void abrir(fstream *f, char nom[], int tip=1);
	void cerrar(fstream *f);
public:
	void limpiar();
	bool hayDatos(char nom[]);
	void mostrar(char nom[]);
	void insertar(int d, char nom[]);
	void ordenar();
};
//-- Metodos para los ficheros --//
void Intercalacion::abrir(fstream *f, char nom[], int tip){
	if(tip==1) //LECTURA
		(*f).open(nom, ios::in );//->
  //MODO TEXTO (Acceder a los datos) usaré ">>"
	else if(tip==2) //ESCRITURA SIN BORRAR
		(*f).open(nom, ios::out | ios::app);	//->
  //MODO TEXTO (Colocar datos y no borrará) usaré "<<"
	else						//ESCRITURA y BORRAR
		(*f).open(nom, ios::out);	//->
  //MODO TEXTO (Colocar datos) usaré "<<"
}
void Intercalacion::cerrar(fstream *f){
	(*f).close();
}
void Intercalacion::limpiar(){
  fstream F1, F2, F3;
	abrir(&F1, "F1.txt", 3);
	abrir(&F2, "F2.txt", 3);
	abrir(&F3, "F3.txt", 3);
	cerrar(&F1);
	cerrar(&F2);
	cerrar(&F3);
}
bool Intercalacion::hayDatos(char nom[]){
	fstream F;
	abrir(&F, nom,1);
	int x=-10001;
	F>>x;
	if(x!=-10001)
		return true;
	else
		return false;
	cerrar(&F);
}

void Intercalacion::mostrar(char nom[]){
	fstream F;
	abrir(&F, nom,1);
	int dato;
	F>>dato;
	while(!F.eof()){
		cout<<dato<<" ";
	  F>>dato;
	}
	cerrar(&F);
}
void Intercalacion::insertar(int d, char nom[]){
	fstream F;
	abrir(&F, nom, 2);
	F<<d<<" ";
	cerrar(&F);
}
//-- Metodo propio de Intercalación de Archivo --//
void Intercalacion::ordenar(){
	fstream F1, F2, F3;
	abrir(&F1, "F1.txt",1);
	abrir(&F2, "F2.txt",1);
	abrir(&F3, "F3.txt",3);

	int  r1, r2;
	F1>>r1;
	F2>>r2;
	//-- Escribir en orden cuando los dos tengan datos.
	while(!F1.eof() && !F2.eof())
	  if(r1 < r2){
	    F3<<r1<<" ";
			F1>>r1;
	  }
	  else{
			F3<<r2<<" ";
		  F2>>r2;
	  }
  //-- Escribir lo sobrante.
	if(!F1.eof())
		while(!F1.eof()){
		  F3<<r1<<" ";
		  F1>>r1;
	  }
	else if(!F2.eof())
		while(!F2.eof()){
		  F2<<r2<<" ";
		  F2>>r2;
		}
	cerrar(&F1);
	cerrar(&F2);
	cerrar(&F3);
}

Menu_Intercalación_De_Archivo.h
void Menu_Intercalacion_De_Archivo(){
	Intercalacion A;
	char *z[1];
	char *principal[5]={"MENU METODO DE INTERCALACION DE ARCHIVO:",
											"INGRESAR DATOS A UN FICHERO.",
											"ORDENAR LOS DATOS.",
											"MOSTRAR LOS DATOS DE UN FICHERO.",
											"ATRAS"};
	char *a[4]={"MENU METODO DE INTERCALACION DE ARCHIVO (INGRESAR):", 
							"INGRESAR UN NUMERO.",
							"INGRESAR VARIOS NUMEROS.",
							"ATRAS."};
	char *b[4]={"MENU METODO DE INTERCALACION DE ARCHIVO: ",
						 "FICHERO 1.",
						 "FICHERO 2.",
						 "FICHERO 3."};

	int op1=1, op2, op3, N, dato, mayor1, mayor2;
	char nomFic[7];
	mayor1=mayor2= -1001;
	A.limpiar();
	do{
		op1=construirMenu(principal, 5, op1 + 1);
		switch(op1){
			case 1: 
				op2=1;
				do{
					op2=construirMenu(a, 4, op2 + 1);
					if(op2!=3){
						op3=construirMenu(b, 3);
						if(op3==1)
							strcpy(nomFic,"F1.txt");
						else
							strcpy(nomFic,"F2.txt");
					}
					if(op2==1 || op2==2){ //UNO O VARIOS DATOS.
						N=1;
						while(op2==2 && (N<=1 || N>=1000)){
							z[0]="Digite cuantos datos desea ingresar:";
							construirMenu(z,1);
							cin>>N;
						}
						for(int i=0; i<N ; i++){
							do{
								z[0]="Digite un dato para colocarlo:";
								construirMenu(z,1);
								cin>>dato;
								if(op3==1 && dato > mayor1)
									mayor1=dato;
								else if(op3==2 && dato > mayor2)
									mayor2=dato;
								else{
									z[0]="El dato debe ser mayor.";
									construirMenu(z,1);
									system("pause>>NULL");
									dato=-10001;
								}
							}while(dato<-10000 || dato>10000);
							A.insertar(dato, nomFic);
							z[0]="Se ha colocado el dato.";
							construirMenu(z,1);
							system("pause>>NULL");
						}
					}
				}while(op2!=3);
				break;
			case 2:
				if(A.hayDatos("F1.txt") && A.hayDatos("F2.txt")){//Si hay datos.
					z[0]="Se ha ordenado los ficheros y se ha guardado en el fichero 3.";
					A.ordenar();
				}else if(!A.hayDatos("F1.txt"))
					z[0]="El fichero 1 no se ha ingresado al menos un dato.";
				else
					z[0]="El fichero 2 no se ha ingresado al menos un dato.";
				construirMenu(z,1);
			  system("pause>>NULL");
				break;
			case 3:
				op3=construirMenu(b, 4);
				if(op3==1)
					strcpy(nomFic,"F1.txt");
				else if(op3==2)
					strcpy(nomFic,"F2.txt");
				else
					strcpy(nomFic,"F3.txt");
				if(A.hayDatos(nomFic)){//Si hay datos.
					z[0]="Los datos son: ";
					construirMenu(z,1);
					A.mostrar(nomFic);
				}else{
					z[0]="No hay datos en el fichero.";
					construirMenu(z,1);
				}
			  system("pause>>NULL");
				break;
		}
	}while(op1!=4);
}

gotoxy.h
#include<iostream>
#include<cstdlib>
#include<conio.h>
#include<windows.h>

using namespace std;
void limpiar(){
  system("cls");
  fflush(stdin);
  cin.clear();
}
void texcolor(int x){
	SetConsoleTextAttribute(GetStdHandle (STD_OUTPUT_HANDLE),x);
}
void gotoxy(int x, int y) {
	COORD Cursor_Pos = {x,y};
	SetConsoleCursorPosition(GetStdHandle (STD_OUTPUT_HANDLE), Cursor_Pos);
}
int construirMenu(char *opciones[], int can, int seleccion=2, int X=15, int Y=3){
	bool ban=true;
	int i,lim, tecla, opc=seleccion;
	limpiar();
	do{
		//-- Buscar la frase más larga --//
		for(lim=i=0; i<can && ban; i++){
			if(strlen(opciones[i])>lim)
				lim=strlen(opciones[i]);
		}
		for(i=Y; i<=(can + Y + 1) && ban; i++){
			gotoxy(X, i);
			//-- Esquinas y lineas verticales del lado izquierdo. --//
			if(i==Y)					cout<<"É";
			else if(i!=can + Y + 1)	cout<<"º";
			else							cout<<"È";
			//-- Lineas horizontales y las opciones.--//
			if(i==Y || i==can + Y + 1){
				for(int j=0; j<lim + 6; j++) cout<<"Í";
			}else{
				//-- Cambio de Color --//
				if(opc==i- Y)
					texcolor(4);
				//-- Las letras --//
				if(i- (Y + 1) == 0)
					gotoxy(X + 1 +(lim + 1 - strlen(opciones[i- (Y + 1)]))/2,i); // Centrado
				else
					gotoxy(X + 1, i);
				cout<<"   "<<opciones[i- (Y + 1)];
				texcolor(7);
			}
			//-- Esquinas y lineas verticales del lado derecho. --//
			gotoxy(X + lim + 6 + 1, i);
			if(i==Y)					cout<<"»";
			else if(i!=can + Y + 1)	cout<<"º";
			else							cout<<"¼";
		}
		//-- Funciones de reconocer las teclas --//
		if(can==1){
			gotoxy(X, i);
			return 0;
		}else
			tecla = getch();
		if(tecla==72){
			if(opc!=2)//-- Flecha Arriba del teclado 
				opc--;
			else
				opc=can;
			ban=true;
		}else if(tecla==80){//-- Flecha Abajo del teclado
			if(opc!=can)
				opc++;
			else
				opc=2;
			ban=true;
		}else
			ban=false;
 }while(tecla!=13);
	return opc - 1;
}

Descarga el código  fuente desde aquí.

miércoles, 18 de diciembre de 2013

Método de Ordenación Radix en C++

Hola amig@s para terminar la entrega de Métodos de ordenación lo haremos con el método Radix. En informática, el ordenamiento Radix (radix sort en inglés) es un algoritmo de ordenamiento que ordena enteros procesando sus dígitos de forma individual. Como los enteros pueden representar cadenas de caracteres (por ejemplo, nombres o fechas) y, especialmente, números en punto flotante especialmente formateados, radix sort no está limitado sólo a los enteros.

La mayor parte de los ordenadores digitales representan internamente todos sus datos como representaciones electrónicas de números binarios, por lo que procesar los dígitos de las representaciones de enteros por representaciones de grupos de dígitos binarios es lo más conveniente. Existen dos clasificaciones de radix sort: el de dígito menos significativo (LSD) y el de dígito más significativo (MSD). Radix sort LSD procesa las representaciones de enteros empezando por el dígito menos significativo y moviéndose hacia el dígito más significativo. Radix sort MSD trabaja en sentido contrario.

Las representaciones de enteros que son procesadas por los algoritmos de ordenamiento se les llama a menudo "claves", que pueden existir por sí mismas o asociadas a otros datos. Radix sort LSD usa típicamente el siguiente orden: claves cortas aparecen antes que las claves largas, y claves de la misma longitud son ordenadas de forma léxica. Esto coincide con el orden normal de las representaciones de enteros, como la secuencia "1, 2, 3, 4, 5, 6, 7, 8, 9, 10". Radix sorts MSD usa orden léxico, que es ideal para la ordenación de cadenas de caracteres, como las palabras o representaciones de enteros de longitud fija. Una secuencia como "b, c, d, e, f, g, h, i, j, ba" será ordenada léxicamente como "b, ba, c, d, e, f, g, h, i, j". Si se usa orden léxico para ordenar representaciones de enteros de longitud variable, entonces la ordenación de las representaciones de los números del 1 al 10 será "1, 10, 2, 3, 4, 5, 6, 7, 8, 9", como si las claves más cortas estuvieran justificadas a la izquierda y rellenadas a la derecha con espacios en blanco, para hacerlas tan largas como la clave más larga, para el propósito de este ordenamiento.



Imagen:



Código:

RadixSort.cpp:

#include "RadixSort.h"
void main(){
 RadixSort RS;
 RS.inicia();
}


RadixSort.h:
#include <iostream>
#include <windows.h>
#include <math.h>
using namespace std;
#define MAX 100

struct{
 int inf;
 int sig;
}nodo[MAX];

class RadixSort{
public:
 int vector[MAX], post[MAX],frente[MAX];
 void inicia(void);
 void radixSort(int[] ,int);
};

void RadixSort::inicia(){
 int n;
 cout<<"Ingrese el numeo de elementos que desea insertar: ";cin>>n;
 for(int i=0;i<n;i++){
  cout<<endl<<"Elemento["<<i+1<<"]: ";cin>>vector[i];
 }
 system("cls");
 cout<<endl<<endl<<"Elementos desordenados:"<<endl<<endl;
 for(int i=0;i<n;i++){
  cout<<endl<<vector[i];
 }
 radixSort(vector,n);
 cout<<endl<<endl<<"Elementos ordenados por metodo Radix Sort:"<<endl<<endl;
 for(int i=0;i<n;i++){
  cout<<endl<<vector[i];
 }
 system("pause>null");
}

void RadixSort::radixSort(int V[], int N){
 int exp, primero, p, q, y,j,i,k;
 for (int i = 0; i < N-1; i++) {
  nodo[i].inf = V[i];
  nodo[i].sig = i+1;
 }
 nodo[N-1].inf = V[N-1];
 nodo[N-1].sig = -1;
 primero = 0;
 for ( k = 1; k < 5; k++) {
  for ( i = 0; i < 10; i++) {
   post[i] = -1;
   frente[i] = -1;
  }

  while (primero != -1) {
   p = primero;
   primero = nodo[primero].sig;
   y = nodo[p].inf;
   exp = pow((double)10, k-1);
   j = (y/exp) % 10;
   q = post[j];
   if (q == -1)
    frente[j] = p;
   else
    nodo[q].sig = p;
   post[j] = p;
  }

  for (j = 0; j < 10 && frente[j] == -1; j++);
  ;//no hacemos nada unicamente nos desplazamos x el vector hasta q salga del ciclo
  primero = frente[j];
  while (j <= 9) {
   for ( i = j+1; i < 10 && frente[i] == -1; i++);
   ;//no hacemos nada unicamente nos desplazamos x el vector hasta q salga del ciclo
   if (i <= 9){
    p = i;
    nodo[post[j]].sig = frente[i];
   }
   j = i;
  }
  nodo[post[p]].sig = -1;
 }
 for ( i = 0; i < N; i++) {
  V[i] = nodo[primero].inf;
  primero = nodo[primero].sig;
 }
}

Descarga el código desde aquí.

miércoles, 4 de diciembre de 2013

Metódo de Ordenación Comb Sort en C++

Hola amig@s continuando con la entrega de los metodós de ordenación esta vez es el turno de el metodo de Comb Sort este metódo en ciencias de la computación, el comb sort (comb=peine) es un algoritmo de ordenamiento relativamente simple diseñado por Wlodzimierz Dobosiewicz en 1980. Posteriormente fue redescubierto y popularizado por Stephen Lacey y Richard Box en un artículo publicado por la revista Byte en abril de 1991. El algoritmo comb sort mejora el algoritmo de ordenamiento de burbuja y rivaliza en velocidad con algoritmos más complejos como el Quicksort. La idea básica es eliminar tortugas, o pequeños valores cerca del final de la lista, ya que en el algoritmo de ordenamiento de burbuja esto reduce la velocidad de ordenamiento tremendamente. (Los conejos, grandes valores alrededor del inicio de la lista, no plantean un problema en el algoritmo de ordenamiento de burbuja.)
En el ordenamiento de burbuja, cuando dos elementos cualquiera se comparan, siempre tienen un espacio (distancia entre ellos) de 1. La idea básica del algoritmo comb sort es que el espacio pueda ser mucho mayor de uno. El ordenamiento Shell también se basa en esta idea, pero es una modificación del algoritmo de ordenamiento por inserción más que del algoritmo de ordenamiento de burbuja.
El espacio se inicia como la longitud de la lista a ordenar dividida por el factor de encogimiento (generalmente 1,3 o 1.3), y la lista se ordena con este valor (redondeado a la baja a un entero si es necesario) para el espacio. Después el espacio se divide por el factor de encogimiento de nuevo, la lista se ordena con este nuevo espacio, y el proceso se repite hasta que el espacio es 1. En este momento, el algoritmo comb sort continua usando un espacio de 1 hasta que la lista está completamente ordenada. La etapa final del ordenamiento es así equivalente al algoritmo de ordenamiento de burbuja, pero en este momento la mayoría de las tortugas ya han sido tratadas, de manera que un algoritmo de ordenamiento de burbuja será eficiente.




Imagen:



Código:

CombSort.cpp:
#include "CombSort.h"
void main(){
 CombSort CS;
 int n;
 do{cout<<"Cuantos elementos desea ingresar: ";cin>>n;}while(n<1||n>100);
 for(int i=0;i<n;i++){
  cout<<endl<<"Dato["<<i+1<<"]: ";cin>>CS.Vector[i];
 }
 system("cls");
 cout<<endl<<endl<<"Vector original:"<<endl<<endl;
 for(int i=0;i<n;i++){
  cout<<CS.Vector[i]<<" ";
 }
 CS.combSort(CS.Vector,n);
 cout<<endl<<endl<<"Vector Ordenado Con El Metodo Comb Sort :"<<endl<<endl;
 for(int i=0;i<n;i++){
  cout<<CS.Vector[i]<<" ";
 }
 system("pause>null");
}

CombSort.h:
#include <iostream>
#include <windows.h>
using namespace std;
class CombSort{
public:
 int Vector[100];
 void combSort(int[], int );
};
void CombSort::combSort(int v[], int N){
    const float reducir = 1.3f;
    int aux;
    int i, brecha = N;
    bool intercambiado = false;
 
    while ((brecha > 1) || intercambiado) {
        if (brecha > 1) {
            brecha = (int)((float)brecha / reducir);
        }
 
        intercambiado = false;
 
        for (i = 0; brecha + i < N; ++i) {
            if (v[i] - v[i + brecha] > 0) {
                aux = v[i];
                v[i] = v[i + brecha];
                v[i + brecha] = aux;
                intercambiado = true;
            }
        }
    }
}

descarga el código fuente desde aquí.

Metodo de Ordenacion Shaker Sort en C++

Hola amig@s en esta ocasión y continuando con los métodos de ordenación les mostare el Shaker sort es también, y mejor, conocido como Cocktail Sort y en castellano como Burbuja Didireccional o Sacudida es la mejora del método de burbuja en el que el proceso se realiza desde la primera posición a la última de la disposición en la dirección opuesta, impidiendo así artículos más pequeños se lleva más tiempo para "subir" a las primeras posiciones.






Imagen:



Código:

ShakerSort.cpp:
#include "ShakerSort.h"
void main(){
 ShakerSort SK;
 int n;
 do{cout<<"Cuantos elementos desea ingresar: ";cin>>n;}while(n<1||n>100);
 for(int i=0;i<n;i++){
  cout<<endl<<"Dato["<<i+1<<"]: ";cin>>SK.vector[i];
 }
 system("cls");
 cout<<endl<<endl<<"Vector original:"<<endl<<endl;
 for(int i=0;i<n;i++){
  cout<<SK.vector[i]<<" ";
 }
 SK.shakerSort(SK.vector,n);
 cout<<endl<<endl<<"Vector Ordenado Con El Metodo Shaker Sort (Sacudida):"<<endl<<endl;
 for(int i=0;i<n;i++){
  cout<<SK.vector[i]<<" ";
 }
 system("pause>null");
}

ShakerSort.h:
#include <iostream>
#include <windows.h>
using namespace std;
class ShakerSort{
public:
 int vector[100];
 void shakerSort(int[] ,int );
};
void ShakerSort::shakerSort(int v[],int N){
 int i = 0 , izq = 1 , der = N-1 , k = N-1 , aux = 0;
 while( der >= izq ){      
  for( i = der ; i>= izq ; i-- )          
   if( v[i-1] > v[i]){
    aux = v[i-1];      
    v[i-1]=v[i];
    v[i]=aux;
    k=i;
   }
   izq = k + 1;
   for( i = izq ; i <= der ; i++)
    if( v[i-1] > v[i] ){
     aux = v[i-1];
     v[i-1]=v[i];
     v[i]=aux;
     k=i;
   }
    der = k-1;
 }
}

Descarga el código fuente desde aquí.

miércoles, 27 de noviembre de 2013

Método de Ordenación Inserción Binaria en C++

Hola amig@s aquí esta otro de los métodos de ordenación interna en esta ocasión se trata de Inserción Binaria este método es una mejora del método de ordenación por  inserción directa.

La mejora consiste en realizar una búsqueda binaria en lugar de una  búsqueda secuencial,para insertar el elemento en la posición que le corresponde.

Imagen:


Codigo:

InsercionBinaria.cpp:

#include "InsercionBinaria.h"
void main(){
 InsercionBinaria IB;
 int n;
 do{cout<<"Cuantos elementos desea ingresar: ";cin>>n;}while(n<1||n>100);
 for(int i=0;i<n;i++){
  cout<<endl<<"Dato["<<i+1<<"]: ";cin>>IB.vector[i];
 }
 system("cls");
 cout<<endl<<endl<<"Vector original:"<<endl<<endl;
 for(int i=0;i<n;i++){
  cout<<IB.vector[i]<<" ";
 }
 IB.insercionBinaria(IB.vector,n);
 cout<<endl<<endl<<"Vector Ordenado Con Metodo de Insercion Binaria:"<<endl<<endl;
 for(int i=0;i<n;i++){
  cout<<IB.vector[i]<<" ";
 }
 system("pause>null");
}


InsercionBinaria.h

#include <iostream>
#include <windows.h>
using namespace std;
class InsercionBinaria{
public:
 int vector[100],i,j,aux,izq,der,m;
 void insercionBinaria(int[], int );
 void mostrar(int[], int );
};

void InsercionBinaria::insercionBinaria(int V[],int N){
 for(i=1;i<N;i++){
  aux = V[i];
  izq=0;
  der=i-1;
  while(izq<=der){
   m=((izq+der)/2);
   if (aux<V[m])
    der=m-1;
   else
    izq=m+1;              
  }
  j=i-1;
  while(j>=izq){
   V[j+1]=V[j];
   j=j-1;
  }
  V[izq]=aux;
 }  
}

void InsercionBinaria::mostrar(int V[],int N){
 for(int i=0;i<N;i++){
  cout<<V[i]<<" ";
 }
}

descarga el código fuente desde aquí.

Metodo de Ordenacion por Insercion Directa en C++

Hola amig@s en esta ocasión les traigo otro método de ordenación interna como lo es el de Inserción Directa es un algoritmo relativamente sencillo y se comporta razonablemente bien en gran cantidad de situaciones.

 Se basa en intentar construir una lista ordenada en el interior del array a ordenar.

 De estos tres algoritmos es el que mejor resultado da a efectos prácticos. Realiza una cantidad de comparaciones bastante equilibrada con respecto a los intercambios, y tiene un par de características que lo hacen aventajar a los otros dos en la mayor parte de las situaciones.

 Este algoritmo se basa en hacer comparaciones, así que para que realice su trabajo de ordenación son imprescindibles dos cosas: un array o estructura similar de elementos comparables y un criterio claro de comparación, tal que dados dos elementos nos diga si están en orden o no.


Imagen:


Código:

InsercionDirecta.cpp:

#include "InsercionDirecta.h" void main(){ InsercionDirecta ID; int n; do{cout<<"Cuantos elementos desea ingresar: ";cin>>n;}while(n<1||n>100); for(int i=0;i<n;i++){ cout<<endl<<"Dato["<<i+1<<"]: ";cin>>ID.vector[i]; } system("cls"); cout<<endl<<endl<<"Vector original:"<<endl<<endl; for(int i=0;i<n;i++){ cout<<ID.vector[i]<<" "; } ID.insercionDirecta(ID.vector,n); cout<<endl<<endl<<"Vector Ordenado Con Metodo de Insercion Directa:"<<endl<<endl; for(int i=0;i<n;i++){ cout<<ID.vector[i]<<" "; } system("pause>null"); }

InsercionDirecta.h

#include <iostream> #include <windows.h> using namespace std; class InsercionDirecta{ public: int vector[100],i,j; void insercionDirecta(int[], int ); void mostrar(int[], int ); }; void InsercionDirecta::insercionDirecta(int V[],int N){ int i,j,v; for (i = 1; i < N; i++){ v = V[i]; j = i - 1; while (j >= 0 && V[j] > v){ V[j + 1] = V[j]; j--; } V[j + 1] = v; } } void InsercionDirecta::mostrar(int V[],int N){ for(int i=0;i<N;i++){ cout<<V[i]<<" "; } }

Descarga el código fuente desde aquí.

martes, 26 de noviembre de 2013

Método de Ordenamiento Shell Sort en C++

Hola amig@s esta vez les traigo otro método de ordenación interna como lo es el Shell sort este método es una generalización del ordenamiento por inserción, teniendo en cuenta dos observaciones:

1- El ordenamiento por inserción es eficiente si la entrada está "casi ordenada".
2- El ordenamiento por inserción es ineficiente, en general, porque mueve los valores sólo una posición cada vez.

El algoritmo Shell sort mejora el ordenamiento por inserción comparando elementos separados por un espacio de varias posiciones. Esto permite que un elemento haga "pasos más grandes" hacia su posición esperada. Los pasos múltiples sobre los datos se hacen con tamaños de espacio cada vez más pequeños. El último paso del Shell sort es un simple ordenamiento por inserción, pero para entonces, ya está garantizado que los datos del vector están casi ordenados.





Codigo:

ShellSort.cpp:


#include "ShellSort.h" void main(){ ShellSort SS; int n; do{cout<<"Cuantos elementos desea ingresar: ";cin>>n;}while(n<1||n>100); for(int i=0;i<n;i++){ cout<<endl<<"Dato["<<i+1<<"]: ";cin>>SS.vector[i]; } system("cls"); cout<<endl<<endl<<"Vector original:"<<endl<<endl; for(int i=0;i<n;i++){ cout<<SS.vector[i]<<" "; } SS.shellSort(SS.vector,n); cout<<endl<<endl<<"Vector Ordenado Con Metodo de ShellSort:"<<endl<<endl; for(int i=0;i<n;i++){ cout<<SS.vector[i]<<" "; } system("pause>null"); }


ShellSort.h:


#include <iostream> #include <windows.h> using namespace std; class ShellSort{ public: int vector[100],temp,inc,i,j; void shellSort(int[], int ); void mostrar(int[], int ); }; void ShellSort::shellSort(int V[], int N){ for(inc = 1 ; inc<N;inc=inc*3+1); while (inc > 0){ for ( i=inc; i < N; i++){ j = i; temp = V[i]; while ((j >= inc) && (V[j-inc] > temp)){ V[j] = V[j - inc]; j = j - inc; } V[j] = temp; } inc/= 2; } } void ShellSort::mostrar(int V[],int N){ for(int i=0;i<N;i++){ cout<<V[i]<<" "; } }

Descarga el código fuente desde aquí.

Metodo de Burbuja (Bubble Sort) en C++

Hola amig@s esta ves les traigo el Método de Ordenación de Burbuja o Bubble Sort (en ingles) este método funciona revisando cada elemento de la lista que va a ser ordenada con el siguiente, intercambiándolos de posición si están en el orden equivocado. Es necesario revisar varias veces toda la lista hasta que no se necesiten más intercambios, lo cual significa que la lista está ordenada. Este algoritmo obtiene su nombre de la forma con la que suben por la lista los elementos durante los intercambios, como si fueran pequeñas "burbujas". También es conocido como el método del intercambio directo. Dado que solo usa comparaciones para operar elementos, se lo considera un algoritmo de comparación, siendo el más sencillo de implementar.


Imagen:



Código:

BubbleSort.cpp:



#include "Bubblesort.h" void main(){ BubbleSort BS; int n; do{cout<<"Cuantos elementos desea ingresar: ";cin>>n;}while(n<1||n>100); for(int i=0;i<n;i++){ cout<<endl<<"Dato["<<i+1<<"]: ";cin>>BS.vector[i]; } system("cls"); cout<<endl<<endl<<"Vector original:"<<endl<<endl; for(int i=0;i<n;i++){ cout<<BS.vector[i]<<" "; } BS.bubbleSort(BS.vector,n); cout<<endl<<endl<<"Vector Ordenado Con Metodo de la burbuja:"<<endl<<endl; for(int i=0;i<n;i++){ cout<<BS.vector[i]<<" "; } system("pause>null"); }


BubbleSort.h:



#include <iostream> #include <windows.h> using namespace std; class BubbleSort{ public: int vector[100],tmp; void bubbleSort(int[],int); void mostrar(int[],int); }; void BubbleSort::bubbleSort(int V[],int N){ for(int i=0;i<N;i++){ for(int j=i+1;j<N;j++){ if(V[i]>V[j]){ tmp=V[i]; V[i]=V[j]; V[j]=tmp; } } } } void BubbleSort::mostrar(int V[],int N){ for(int i=0;i<N;i++){ cout<<V[i]<<" "; } }


Descarga el código fuente desde aquí.

domingo, 24 de noviembre de 2013

Quicksort en C++

Hola amig@s esta vez les traigo uno de los métodos de ordenación interna en esta ocasión se trata del Quicksort. este método se basa en dividir los n elementos de la lista a ordenar en dos partes o particiones separadas por un elemento.

La ordenación rápida implica la selección de un elemento de una lista y a continuación reordenar todos los elementos restantes de la sublista. De tal modo que todos los elementos que son más pequeños que el elemento dado se ponen en una sublista y todos los elementos que son más grandes que el elemento dado se ponen en una segunda sublista. Por consiguiente. El método elige un elemento denominado pivote pone en una sub lista todos los elementos mayores que el pivote y los elementos más pequeños en otra sublista.

El algoritmo trabaja de la siguiente forma:

- Elegir un elemento de la lista de elementos a ordenar, al que llamaremos pivote.
-Resituar los demás elementos de la lista a cada lado del pivote, de manera que a un lado queden todos los menores que él, y al otro los mayores. Los elementos iguales al pivote pueden ser colocados tanto a su derecha como a su izquierda, dependiendo de la implementación deseada. En este momento, el pivote ocupa exactamente el lugar que le corresponderá en la lista ordenada.
-La lista queda separada en dos sublistas, una formada por los elementos a la izquierda del pivote, y otra por los elementos a su derecha.
-Repetir este proceso de forma recursiva para cada sublista mientras éstas contengan más de un elemento. Una vez terminado este proceso todos los elementos estarán ordenados.


Imagen:


Codigo:

Quicksort.cpp:

#include<iostream>
#include"Quicksort.h"
using namespace std;

void main(){
 int i;
 Quicksort q;
 int c;
 cout<<"cuantos datos: ";
 cin>>c;
 for(i=0;i<c;i++){
  system("cls");
  cout<<"dato["<<i+1<<"]: ";
  cin>>q.lista[i];  
 } system("cls");
 cout<<endl;
 q.quicksort(q.lista,0,c-1);
 /**/cout<<endl;
 cout<<endl<<"Arreglo ordenado"<<endl<<endl;
 for(i=0;i<c;i++){
  cout<< q.lista[i]<<"  ";
 }cout<<endl<<endl;
 system("pause>null");
}



Quicksort.h:


#include<iostream>
#include<windows.h>
using namespace std;
#define MAX 100
class Quicksort{
public:
 int i,j,pivote,centro,primero,ultimo,temp;
 int lista[MAX];
 void quicksort(int[] ,int ,int );
};

void Quicksort::quicksort(int lista[],int primero,int ultimo){
 centro=(primero+ultimo)/2;
 pivote=lista[centro];
 i=primero;
 j=ultimo;
 cout<<endl<<endl<<"****************************************************"<<endl<<endl<<"ARREGLO: "<<endl<<endl;
 for(int k=primero; k<=ultimo; k++){
  cout<<lista[k]<<"\t";
 }
 cout<<endl<<endl<<"pivote: "<<pivote<<endl<<"primero: "<<primero<<endl<<"ultimo: "<<ultimo<<endl;
 Sleep(1500);cout<<endl;
 do{
  while(lista[i]<pivote){i++;}
  while(lista[j]>pivote){j--;}
  if(i<=j){
   cout<<endl<<"Cambio de "<<lista[i]<<" por "<<lista[j]<<endl;
   temp=lista[i];
   lista[i]=lista[j];
   lista[j]=temp;
   i++;
   j--;
  }
 }while(i<=j);
 if(primero<j){
  quicksort(lista,primero,j);
 }
 if(i<ultimo){
  quicksort(lista,i,ultimo);
 }
}


Descarga el código fuente desde aquí.

sábado, 23 de noviembre de 2013

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í:

miércoles, 25 de septiembre de 2013

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í.

jueves, 25 de julio de 2013

Grafos en C++

Hola amig@s en esta entrega les tengo el código de grafos en el cual podremos utilizar un grafo pre-guardado o crear uno nuevo, crear la matriz de adyacencia, la matriz de caminos, mostrar la lista de nodos adyacentes, recorrido en profundidad, recorrido en anchura, mostrar la matriz de Floyd y mostrar la matriz de Warshall.

Capturas:









Descarga el código desde aquí.

martes, 16 de julio de 2013

Búsqueda Secuencial en C++

Hola amig@s esta vez les traigo el código de Búsqueda secuencial en C++.

Explicación:

Búsqueda secuencial

Consiste en recorrer el archivo comparando la clave buscada con la clave del registro en curso. El recorrido lineal del archivo termina cuando se encuentra el elemento, o bien cuando se alcanza el final del archivo. Se puede representar algunas variantes dependiendo de si el archivo está o no ordenado.

Captura:



Código:


#include<iostream>
#include <fstream>
using namespace std;

void insertar();
void BusquedaSecuencial(int numBus);

int main(){
insertar();
cout<<endl<<endl<<"Valor a buscar: 10"<<endl<<endl;
BusquedaSecuencial(10);
system("pause");
return 0;
}
void insertar(){
ofstream out;
out.open("Salida.txt");
out<<1<<" "<<endl;
out<<2<<" "<<endl;
out<<4<<" "<<endl;
out<<6<<" "<<endl;
out<<7<<" "<<endl;
out.close();
}
void BusquedaSecuencial(int numBus){
ifstream in;
in.open("Salida.txt");
bool bandera=false;
int num;
while(!in.eof() && bandera==false){
in>>num;
if(num>=numBus){
bandera=true;
}
}
if(num==numBus){
cout<<"el elemento esta en el archivo"<<endl;
}else
cout<<"el elemento no esta en el archivo"<<endl;
}


Descarga el código desde aquí.

Busqueda Binaria C++

Hola amig@s esta vez les he traído el código de la búsqueda binaria.

Explicacion:


Binaria:
Consiste en dividir intervalos de búsqueda en dos partes , comparando el
elemento buscado con el central. En caso de no ser iguales se redefinen
los extremos del intervalos(según el elemento central sea mayor o menor
que el buscado) disminuyendo el espacio de búsqueda
El proceso concluye cuando el elemento es encontrado.

Este método funciona únicamente para arreglos ordenados .

Con cada iteración del método el espacio de búsqueda se reduce a la
mitad , por lo tanto el número de comparaciones se reduce notablemente.
Esta disminución resulta significativa cuanto más grande sea el arreglo.


Código:


#include<iostream>
using namespace std;
void binaria(int x,int v[],int n);
int main(){
 int x,v[100],n;
 do{
  cout<<"\nnumero de datos: ";
  cin>>n;
 }while(n<1||n>100);
 for(int i=0;i<n;i++){
  v[i]=i;
 }
 cout<<"\nnumero a buscar: ";
 cin>>x;
 binaria(x,v,n);
 system("pause");
 return 0;
}
void binaria(int x,int v[],int n){
 int izq=1,der=n,cent;
 bool bandera=false;
 while((izq<=der)&&(bandera==false)){
  cent=int(izq+der)/2;
  if(x==v[cent]){
   bandera=true;
  }else{
   if(x>v[cent]){izq=cent+1;}else{der=cent-1;}
  }
 }
 if(bandera==true){cout<<"\nel elemento esta en la posicion: "<<cent<<"\n\n";}
 else{cout<<"\nel elemento no se encuentra en el arreglo"<<"\n\n";}
}



Descarga el código desde aquí.

Arbol Binario en C++

Hola amigos esta vez les mostrare un arbol binario con los recorrios in-orden, post-orden y pre-orden.

Captura:



Codigo:

Arbol.cpp


#include<iostream>
#include"arbol.h"
using namespace std;

void arbol::insertar(tarbol &aux,int v){
 if(aux==NULL){
  aux=new nodo(v);
 }
 else{
  if(v<aux->dato){
   insertar(aux->izquierda,v);
  }
  else{
   if(v>aux->dato){
    insertar(aux->derecha,v);
   }
  }
 }
}

void arbol::ind(tarbol aux){
 if(aux!=NULL){
  ind(aux->izquierda);
  cout<<" num :  "<<aux->dato<<endl;
  ind(aux->derecha);
 } 
 
}

void arbol::nid(tarbol aux){
 if(aux!=NULL){
  cout<<" num :  "<<aux->dato<<endl;
  nid(aux->izquierda);
  nid(aux->derecha);
 }

}
void arbol::idn(tarbol aux){
 if(aux!=NULL){
  idn(aux->izquierda);
  idn(aux->derecha);
  cout<<" num :  "<<aux->dato<<endl;
 }
}

int main(){
 arbol a;
 cout<<"Datos: 5,4,2,6,7"<<endl<<endl;
 a.insertar(a.miarbol,5);
 a.insertar(a.miarbol,4);
 a.insertar(a.miarbol,2);
 a.insertar(a.miarbol,6);
 a.insertar(a.miarbol,7);
 cout<<"Inorden"<<endl<<endl;
 a.ind(a.miarbol);
 cout<<endl<<endl;
 cout<<"Postorden"<<endl;
 a.idn(a.miarbol);
 cout<<endl<<endl;
 cout<<"Preorden"<<endl;
 a.nid(a.miarbol);
 cout<<endl<<endl;fflush(stdin);
 system("pause");
 return 0;
}

Arbol.h


class nodo{
public: 
 int dato;
  nodo *izquierda;
  nodo *derecha;
  nodo(int v,nodo *iz=NULL,nodo *de=NULL){
   dato=v;
   izquierda=iz;
   derecha=de;
  }
class arbol;
};
typedef nodo *tarbol;

class arbol{
public:
 tarbol miarbol;
 arbol(){
  miarbol=NULL;
 }
 void arbol::insertar(tarbol &aux, int v);
 void ind(tarbol aux);
 void nid(tarbol aux);
 void idn(tarbol aux);
};



Descarga el codigo desde aqui.

lunes, 15 de julio de 2013

Agenda Electrónica con árbol AVL en C++

Hola amig@s en esta vez les traigo como hacer una agenda electrónica implementando un árbol AVL las opciones de la agenda son agregar  un nuevo contacto, buscar, eliminar, mostrar, mostrar el numero de contactos y salir.

Capturas:



Codigo:

ArbolAVL.cpp

#include 
#include 
#include 
#include 
#include "ArbolAVL.h"
using namespace std;

int main()
{

  arbol A;
  tarbol b;
  char nombre[50];
  char telefono[10];
  char direccion[50];
  char email[50];
  char op;
  int t;
 
  do{
   fflush(stdin);
      system("cls");
   cout<<"\tMenu\n\n";
   cout<<"\t1- Agregar\n";
   cout<<"\t2- Buscar\n";
   cout<<"\t3- Eliminar\n";
   cout<<"\t4- Mostrar\n";
   cout<<"\t5- Estadistica\n";
   cout<<"\t6- Salir\n\n";
   cout<<"Ingrese la opcion: ";
   cin>>op;
   fflush(stdin);
   switch(op)
   {
  case '1': {
   fflush(stdin);
      system("cls");
   cout<<"\nIngrese Nombre: ";
   gets(nombre);
   fflush(stdin);
   do{
   cout<<"\nIngrese Telefono 0000-0000: ";
   gets(telefono);
   fflush(stdin);
   t=strlen(telefono);
     }while(t!=9);
   cout<<"\nIngrese Direccion: ";
   gets(direccion);
   fflush(stdin);
   cout<<"\nIngrese Email: ";
   gets(email);
   fflush(stdin);
   A.insertar(A.miarbolito,nombre,telefono,direccion,email);
   break;
     }
  case '2':{
   fflush(stdin);
   system("cls");
   cout<<"\nNombre: ";
   gets(nombre);
   fflush(stdin);
   b=A.buscar(A.miarbolito,nombre);
   if(b!=NULL)
   {
   fflush(stdin);
   system("cls");
   cout<<"\nContacto encontrado:";
   cout<<"\n\nNombre: "<nombre;
   cout<<"\nTelefono: "<telefono;
   cout<<"\nEmail: "<email;
   cout<<"\nDireccion: "<direccion;
   system("pause");
   }
     break;
        }
  case '3':{
   system("cls");fflush(stdin);
   cout<<"\nNombre: ";
   gets(nombre);
   fflush(stdin);
   A.borrar(A.miarbolito,nombre);
   system("pause");
   break;
     }
  case '4':{
   system("cls");
            cout<<"\n\n";
   A.IDN(A.miarbolito);system("pause");
   break; 
        }
  case '5':{
      system("cls");
            A.pe=0;
   cout<<"\nNumero de contactos: "<nombre)<0 data-blogger-escaped-aux-="" data-blogger-escaped-insertar="">Izdo,nom,tel,dir,em); 
   }
   else 
   { if(strcmpi(nom,aux->nombre)>0)
    {
    insertar(aux->Dcho,nom,tel,dir,em);
    }
   }
 }
}
tarbol arbol::buscar(tarbol aux,char nom[50])
{  
 if (aux==NULL)
 {  
  return NULL;
 }
 else
 {
  if (strcmpi(nom,aux->nombre)==0)
  {
   return aux;
  }
  else
  { if (strcmpi(nom,aux->nombre)<0 data-blogger-escaped-aux-="" data-blogger-escaped-buscar="" data-blogger-escaped-return="">Izdo, nom);
   }
   else
   {
    return buscar(aux->Dcho, nom);
   }
  }
 }
}
void arbol::borrar(tarbol &aux,char nom[50])
{
 if (aux==NULL)
 {
  cout<<"contacto no encontrado no encontrado !!\n\n";
 }
 else
 {if (strcmpi(nom,aux->nombre)<0 data-blogger-escaped-aux-="" data-blogger-escaped-borrar="">Izdo, nom);
   }
    else 
    {
     if (strcmpi(nom,aux->nombre)>0)
     {
    borrar(aux->Dcho,nom);
     }
    else
    { 
    tarbol temp=aux;
    if (aux->Izdo== NULL)
     {
     aux = aux->Dcho;
     }
     else 
     {
      if (aux->Dcho == NULL)
      {
        aux = aux->Izdo;
      }
      else 
      {
       actualizar(temp,temp->Izdo);
      }
      delete  temp;
     
     }
    }
   }
 }
}
void arbol::actualizar(tarbol &temp, tarbol &aux)
{ 
 if(aux->Dcho!=NULL)
 {
  actualizar(temp,aux->Dcho);}

 else
 {
  strcpy(temp->nombre,aux->nombre);
  strcpy(temp->telefono,aux->telefono);
  strcpy(temp->email,aux->email);
  strcpy(temp->direccion,aux->direccion);
     temp=aux;
  aux=temp->Izdo;
 }
}
void arbol::IDN( tarbol aux)
{
     if(aux!=NULL)
  { 
          IDN(aux->Izdo);
          if(strcmpi(aux->nombre,"M")!=0)
    {
              cout<<"Nombre: "<< aux->nombre<<" "<telefono<<" "<email<<" "<direccion<<" "<Dcho);
      }
}

int arbol::Peso( tarbol aux)
{
    if(aux!=NULL)
 {
  pe++; 
  Peso(aux->Izdo); 
  Peso(aux->Dcho);
  return  pe;
 }
 else
 {
  return -1;
    }
}
int arbol::maximo(int a, int b)
{ 
 if(a > b)
 return a;
 else return b;
}
int arbol::altura(tarbol &aux)
{
 if(aux)
 return aux->eq;
 else return -1;    
}
void arbol::balance (tarbol &aux, char nom[50])
{ 
  if (aux)
 {       
  if (strcmpi(nom,(aux)->nombre)>0)
  {balance(aux->Dcho,nom);
  }
  else {if (strcmpi(nom,(aux)->nombre)<0 data-blogger-escaped-aux-="" data-blogger-escaped-balance="">Dcho,nom);
    }
    }
        int fe=altura(aux->Dcho)-altura(aux->Izdo);
  switch (fe)
  {
  case -2:
   {
    if (altura(aux->Izdo->Izdo) > altura(aux->Izdo->Dcho))
    RII(aux);
    else RID(aux);
    break;
   }
  case 2:
   {
   if (altura(aux->Dcho->Dcho) > altura(aux->Dcho->Izdo))
    RDD(aux);
   else 
      RDI(aux);
   break;
   }
  default:
   aux->eq = maximo(altura(aux->Izdo),altura(aux->Dcho)) +1;
  }
 }
}
void arbol::RII(tarbol &aux){
        tarbol n1=aux->Izdo;
  aux->Izdo=n1->Dcho;
  n1->Dcho=aux;
  aux=n1;
  n1 = aux->Dcho;
  if(n1)
  n1->eq = maximo(altura(n1->Izdo),altura(n1->Dcho))+1;
  aux->eq = maximo(altura(aux->Izdo),altura(aux->Dcho))+1; 
}
void arbol::RDD(tarbol &aux){
     tarbol temp;
     temp=aux->Dcho;
     aux->Dcho=temp->Izdo;
     temp->Izdo=aux;
     aux=temp;
     temp = aux->Izdo;
     if(temp)
     temp->eq = maximo(altura(temp->Izdo),altura(temp->Dcho))+1;
     aux->eq = maximo(altura(aux->Izdo),altura(aux->Dcho))+1;
}
void arbol::RID(tarbol &aux){
  RDD(aux->Izdo);
     RII(aux);
}
void arbol::RDI(tarbol &aux){
 RII(aux->Dcho);
 RDD(aux);
}

ArbolAVL.h

#include

class nodo{
public:
 char nombre[50];
 char telefono[10];
 char direccion[50];
 char email[50];
 int eq;
 nodo *Izdo, *Dcho;
 nodo(char nom[50],char tel[10],char dir[50],char em[50], nodo *Iz=NULL, nodo *Dr=NULL,int t=0){
 strcpy(nombre,nom);
 strcpy(telefono,tel);
 strcpy(direccion,dir);
 strcpy(email,em);
 eq=t;
 Izdo=Iz;
 Dcho=Dr; 
 }
 class arbol;
};
typedef nodo *tarbol; 
class arbol{
public: 
      tarbol miarbolito;   
     int pe;
  int a;
   arbol(){
   miarbolito=NULL;
   pe=0;
   a=0;
       }    
      void insertar(tarbol &aux,char nom[50],char tel[10],char dir[50],char em[50]);
      tarbol buscar(tarbol aux,char nom[50]);
      void borrar(tarbol &aux,char nom[50]);
      void actualizar(tarbol &temp, tarbol &aux);
      void balance(tarbol &aux, char nom[50]);
      int maximo(int a, int b);
      void IDN(tarbol aux);
      void RDD(tarbol &aux);
      void RDI(tarbol &aux);
      void RID(tarbol &aux);
      void RII(tarbol &aux);
      int Peso(tarbol aux);
      int altura(tarbol &aux);
};


puedes descargar el proyecto desde aquí.

Agenda Electronica con Arboles ABB en C++

Esta vez les traigo una agenda electronica implemetando arboles ABB, las funciones de la agenda son: agregar un nuevo contacto, buscar, eliminar, mostrar todos los contactos y mostrar el numero de contactos dentro de la agenda.

 Capturas:




Codigo:

Agenda.cpp


#include 
#include 
#include "agenda.h"
using namespace std;

int main()
{
  arbol A;
  Tarbol b;
  char nombre[30];
  char telefono[10];
  char direccion[30];
  char Email[40];
  int op;
  A.insertar(A.miarbol,"m"," 1"," 1"," 1");
  cout<>op;
	  switch(op)
	  {
	  case 1:
		  {fflush(stdin); system("cls");
			  //agregar
			
			cout<nombre<telefono<Email<direccion<nombre)<0){
			 insertar(aux->Izdo,nom,tel,dir,e); 
			}else if(strcmpi(nom,aux->nombre)>0 ){
			insertar(aux->Dcho,nom,tel,dir,e);}
	
	    }

}
Tarbol arbol::buscar(Tarbol aux,char nom[30])
{  
	if (aux==NULL){  
		return NULL;}
	else {if (strcmpi(nom,aux->nombre)==0){
				return aux;}
	else {	if (strcmpi(nom,aux->nombre)<0){
				return buscar(aux->Izdo, nom);}
			else{ return buscar(aux->Dcho, nom);}}
		}
}

void arbol::borrar( Tarbol &aux,char nom[30])
{
	if (aux==NULL){
		cout<<"contacto no encontrado no encontrado !!";}
	else {if (strcmpi(nom,aux->nombre)<0){
	           borrar(aux->Izdo, nom);}
	      else {if (strcmpi(nom,aux->nombre)>0){
				borrar(aux->Dcho,nom);}
				else{ Tarbol temp=aux;
				if (aux->Izdo== NULL){
					aux = aux->Dcho;
					}else {if (aux->Dcho == NULL){
								aux = aux->Izdo;}
							else {reemplazar(temp,temp->Izdo);}
						
					delete  temp;
					}
				}
		  }
	}
}
void arbol::reemplazar(Tarbol &temp, Tarbol &aux)
{ 
	if(aux->Dcho!=NULL){
		reemplazar(temp,aux->Dcho);}
	else{
		strcpy(temp->nombre,aux->nombre);
		strcpy(temp->telefono,aux->telefono);
		strcpy(temp->Email,aux->Email);
		strcpy(temp->direccion,aux->direccion);
		
	    temp=aux;
		aux=temp->Izdo;
	}
}



void arbol::Inorden( Tarbol aux){//muestra de la A-Z
if(aux!=NULL){
 Inorden(aux->Izdo); //recorre el subárbol Izquierdo
 if(strcmpi(aux->nombre,"m")!=0){
	 cout<<"--NOMBRE: "<< aux->nombre<<" "<telefono<<" "<Email<<" "<direccion<<" "<Dcho); //recorre el subárbol Derecho
}

}


int arbol::Peso( Tarbol aux)//muestra el numero de contactos
{
   	if(aux!=NULL){
		p++; 
		Peso(aux->Izdo); //recorre el subárbol Izquierdo
		Peso(aux->Dcho);
		return  p;
	}else {
		return -1;}

}




Agenda.h

#include


class nodo{
public:
	char nombre[30];
	char telefono[10];
	char direccion[30];
	char Email[40];
	nodo *Izdo, *Dcho;

	nodo(char nom[30],char tel[10],char dir[30],char e[40], nodo *Iz=NULL, nodo *Dr=NULL){
	strcpy(nombre,nom);
	strcpy(telefono,tel);
	strcpy(direccion,dir);
	strcpy(Email,e);
	Izdo=Iz;
	Dcho=Dr;	
	}
 class arbol;
};
typedef nodo *Tarbol; 
class arbol{
public: 
      Tarbol miarbol;	  
    	int p;
		int a;
			arbol(){
			miarbol=NULL;
			p=0;
			a=0;
	  		  }
void insertar(Tarbol &aux,char nom[30],char tel[10],char dir[30],char e[40]);
Tarbol buscar(Tarbol aux,char nom[30]);
void borrar(Tarbol &aux,char nom[30]);
void reemplazar(Tarbol &temp, Tarbol &aux);


void Inorden(Tarbol aux);


int arbol::Peso(Tarbol aux);


};


descarga todo el proyecto desde aqui.