#include <dos.h>
#include <stdio.h>
#include <stdlib.h>
#include <conio.h>
#include <windows.h>
#include<string.h>
#define largo 20
void menu(void);
int opcion;
struct nodoarbol{ //Estructura del Arbol
struct nodoarbol *izqnodo;
int info;
struct nodoarbol *dernodo;
};
typedef struct nodoarbol NODO; //Definicion de tipo nodo
typedef NODO *ARBOL;
void insertarnodonuevo(ARBOL *,int); //Declaracion de funciones
void inorden(ARBOL);
void preorden(ARBOL);
void postorden(ARBOL);
void treefree(ARBOL);
void burbuja(int *, const int);
void inserciondirecta(int n, int A[]);
void seleccionsort(int A[],int n);
void insercionBinaria(int A[],int n);
void quicksort (int A [],int izq, int der);
void ordenShell(int A[],int n);
void leercadena(int cant,int A[]);
void muestracadena(int cant,int A[]);
//Crea un nuevo nodo y coloca los valores del nuevo elemento en la posicion correspondiente
void insertarnodonuevo(ARBOL *rarbol,int nuevo){ //Creacion de un nodo nuevo
if(*rarbol==NULL){
*rarbol=(NODO *)malloc(sizeof(NODO));
if(*rarbol!=NULL){
//Asignacion de valores nuevos en el nodo
(*rarbol)->info=nuevo;
(*rarbol)->izqnodo=NULL;
(*rarbol)->dernodo=NULL;
}
else{printf("\n-----Memoria no disponible!!!!!\n");}
}
else
if (nuevo<(*rarbol)->info) //Checa si el elementonuevo es mayor que el elemento padre
insertarnodonuevo(&((*rarbol)->izqnodo),nuevo); //Coloca el elemento a la izquierda
else
if(nuevo>(*rarbol)->info) //Checa si el elemento nuevo es menor que el elemento padre
insertarnodonuevo(&((*rarbol)->dernodo),nuevo); //Coloca el elemento a la derecha
}
//^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
//Funcion iterativa la cual recorre el arbol buscando el nodo mas izquierdo que tiene el arbol
//osea hasta que la rama del ultimo nodo sea nulo, luego la imprime, despues la raiz del sub-arbol,
//y luego el nodo de la derecha
void preorden (ARBOL rarbol)
{
if(rarbol!=NULL)
{
printf("%c",rarbol->info);
preorden(rarbol->izqnodo);
preorden(rarbol->dernodo);
}
}
//!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
//Funcion iterativa la cual recorre el arbol buscando nodo mas izquierdo que contiene el arbol oseahasta la
//rama del ultimo nodo sea nulo, luego la imprime, despues la raiz del sub-arbol, y luego el nodo de la derecha.
void inorden(ARBOL rarbol)
{
if(rarbol!=NULL)
{
inorden(rarbol->izqnodo);
printf("%c ",rarbol->info);
inorden(rarbol->dernodo);
}
}
//+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
//Funcioniterativa la cual recorre el arbol buscando nodo mas izquierdo luego el nodo mas a la derecha
//y luego raiz de ese sub-arbol.
void postorden(ARBOL rarbol)
{
if(rarbol!=NULL)
{
postorden(rarbol->izqnodo);
postorden(rarbol->dernodo);
printf(" %c ",rarbol->info);
}
}
//$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$
//Funcion iterativa identifica al recorrido en postorden la unica diferencia es que en vez de imprimir
//en pantalla el valor de un nodo este es eliminado del arbol lnerado la memoria con la funcion free()
//,elegi esta forma ya que se elimina primero los nodos hijos del subarbol y luego la raiz ya que si se
//elimina la raiz primero, los hijos se deskonektan del arbol pero la memoria que okupaban sigue siendo
//utilizada y de esta forma se elimina el arbol de abajo hacia arriba(osea de hijos a la raiz)
void treefree(ARBOL rarbol)
{
if(rarbol!=NULL)
{
treefree(rarbol->izqnodo);
treefree(rarbol->dernodo);
free(rarbol);
}
}
void ordenShell(int A[],int n)
{
int i,j,inc,temp;
for(inc = 1; inc<n ;inc=inc*3+1);
while (inc >0)
{
for(i=inc;i<n;i++)
{
j = i;
temp = A[i];
while((j>=inc) && (A[j-inc] > temp))
{
A[j] = A[j - inc];
j = j- inc;
}
A[j] = temp;
}
inc/=2;
}
}
void burbuja(int *array, const int n)
{
int i ,j;
void swap(int *,int *);
for(j=0;j<n;j++)
for(i=0;i<n-1;i++)
if(array[i]>array[i+1])
swap(&array[i],&array[i+1]);
}
void swap(int *nodo1, int *nodo2)
{
int temp;
temp=*nodo1;
*nodo1=*nodo2;
*nodo2=temp;
}
void insercionBinaria(int A[],int n)
{
int i,j,aux,izq,der,m;
for(i=1;i<n;i++)
{
aux= A[i];
izq=0;
der=i-1;
while(izq<=der)
{
m=((izq+der)/2);
if(aux<A[m])
der=m-1;
else
izq=m+1;
}
j=i-1;
while(j>=izq)
{
A[j+1]=A[j];
j=j-1;
}
A[izq]=aux;
}
}
void inserciondirecta(int n, int A[])
{
int i,j,v;
v=0;
j=0;
for(i=1;i<n;i++)
{
v=A[i];
j=i-1;
while(j>=0 &&A[j]>v)
{
A[j+1]=A[j];
j--;
}
A[j+1]=v;
}
}
void quicksort(int A[],int izq, int der)
{
int i,j,x, aux;
i=izq;
j=der;
x=A[ (izq + der) /2];
do{
while( (A[i]<x) && (j<=der))
{
i++;
}
while((x<A[j]) && (j>izq))
{
j--;
}
if(i<=j)
{
aux = A[i] ; A[i] = A[j]; A[j] = aux;
i++; j--;
}
}while (i<=j);
if (izq<j)
quicksort(A, izq,j);
if (i<der)
quicksort(A,i,der);
}
void seleccionsort (int A[], int n)
{
int min,i,j,aux;
for(i=0;i<n-1;i++)
{
min=i;
for(j=i+1; j<n; j++)
if(A[min] >A[j])
min=j;
aux=A[min];
A[min]=A[i];
A[i]=aux;
}
}
void leecadena(int cant, int A[])
{
int i;
("CLSCR");
for(i=0;i<cant;i++)
{
printf("Ingresa numero de la posicion %6d --> ", i+1);
scanf("%6d",&A[i]);
}
}
void muestracadena(int cant, int A[])
{
int i;
i=0;
printf("\n\nRelacion de Numeros para la iNsercion Binaria \n\n");
for(i=0;i<cant;i++)
{
printf("Numero:%d", i+1);
printf("%6d\n",A[i]);
}
getch();
}
int main()
{
menu();
getch();
return 0;
}
void menu(void)
{
system("CLS");
printf("::Menu::\n\n");
printf("1.Burbuja\n\n");
printf("2.Insercion Binaria\n\n");
printf("3.Insercion Directa\n\n");
printf("4.Quicksort\n\n");
printf("5.Seleccion Directa\n\n");
printf("6.Shell\n\n");
printf("7.Metodos de Recorridos de Arbol\n\n");
printf("\n\n0.Salir\n\n\n");
printf("\n\n ||Daudet Hernandez||\n");
scanf("%d", &opcion);
switch (opcion)
{
case 1:
system("CLS");
printf("Metodo Burbuja");
void burbuja(int *, const int);
{
int i, a[10],n;
printf("\n\nOrdenamiento de la Burbuja");
printf("\n\nDar Numero de Elementos a Ordenar :");
scanf("%d",&n);
for(i=0;i<n;i++)
{
printf("Dar Valores:");
scanf ("%d" , &a[i]);
}
burbuja(a,n);
printf("\n\nLos Datos Ordenados en Ascendente Quedan:");
for(i=0;i<n;i++)
printf("%4d",a[i]);
printf("\n\n");
getch();
printf("\n\nRegresando al Menu");
Sleep(1500);
menu();
}
break;
case 2:system("CLS");
printf("\n\nMetodo de Insercion Binaria");
void insercionBinaria(int A[],int n);
{
int A[largo], n;
do{
printf("\n\nCantidad de numeros a ingresar: ");
scanf("%d",&n);
if (n<=0||n>largo)
printf("\n\nDebe ingrasar un valor > a 0 y < a %d", largo);
}while(n<=0||n>largo);
leecadena(n,A);
insercionBinaria(A,n);
muestracadena(n,A);
}
printf("\n\nRegresando al Menu");
Sleep(1500);
menu();
break;
case 3:system("CLS");
printf("\n\nMetodo de Insercion Directa");
void inserciondirecta(int n, int A[]);
{
int A[largo],n;
do{
printf("\n\nCantidad de numeros a ingresar para el Metodo de Insercion Directa:");
scanf("%d",&n);
if(n<=0 || n>largo)
{
printf("\n\nDebe ingresar un valor >a 0 y a 20 \n");
getch();
}
}while(n<=0 || n>largo);
leecadena(n,A);
inserciondirecta(n,A);
muestracadena(n,A);
}
printf("\n\nRegresando al Menu");
Sleep(1500);
menu();
break;
case 4:system("CLS");
printf("Metodo de QuickSort");
void quicksort(int A[],int izq, int der);
{
int A[largo],n;
do{
printf("\n\nCantidad de numeros a ingresar: ");
scanf("%6d",&n);
if(n<=0||n>largo)
{
printf("\n\nDebe ingresar un valor > a 0 y < a %d\n ",largo);
getch();
}
}while(n<=0||n>largo);
leecadena (n,A);
quicksort(A,0,n-1);
muestracadena(n,A);
}
printf("\n\nRegresando al Menu");
Sleep(1500);
menu();
break;
case 5:system("CLS");
printf("\n\nMetodo de Seleccion Directa");
void seleccionsort (int A[], int n);
{
int A[largo], n;
do {
printf("\n\n Cantidad de numeros a ingresar:");
scanf("%d",&n);
if (n<=0||n>largo)
{
printf("\n\nDebe ingresar un valor > a 0 y < a %d", largo);
getchar();
}
}while(n<=0||n>largo);
leecadena(n,A);
seleccionsort(A,n);
muestracadena(n,A);
}
printf("\n\nRegresando al Menu");
Sleep(1500);
menu();
break;
case 6:system("CLS");
printf("Metodo de Shell");
void ordenShell(int A[],int n);
{
int A[largo], n;
do{
printf("\n\nCantidad de numeros a ingresar: ");
scanf("%d",&n);
if (n<=0||n>largo)
printf("\n\nDebe ingrasar un valor > a 0 y < a %d", largo);
}while(n<=0||n>largo);
leecadena(n,A);
ordenShell(A,n);
muestracadena(n,A);
}
printf("\n\nRegresando al Menu");
Sleep(1500);
menu();
break;
case 7:system("CLS");
printf("\n\nMetodos de Recorrido de Arbol");
{
int i; //contador
char newnod, chain[200],elementos; //Declaracion de cadena,bandera y variable que contiene el nuevo valor a insertar
ARBOL raiz=NULL; //Declracion de variable tipo arbol
printf("\n\nRecorridos de arboles\n");
printf("\n\nIntroduzca una cadena de caracteres (max. 200 elementos):\n");
gets (chain);
elementos = strlen(chain); //Checa el tamano de la cadena y establece e
for (i=1;i<=elementos;i++)
{
newnod=chain[i-1];
insertarnodonuevo(&raiz,newnod);
}
printf("\n\nPreorden ==\t");
preorden(raiz); //Llamado a funcion de recorrido en preorden
printf("\n\n Inorden ==\t");
inorden(raiz); //Llamado a funcion de recorrido Inorden
printf("\n\n Postorden ==\t");
postorden(raiz); //LLamado a funcion de recorrido en postorden
getch();
treefree(raiz); //Liberacion de memoria del Arbol
raiz=NULL; //Asignacion de un valor nulo a la raiz
}
getch();
printf("\n\nRegresando al Menu");
Sleep(1500);
menu();
break;
default:system("CLS");
}
printf("Saliendo....");
Sleep(2100);
exit(0);
}