Arboles AVL - Estructura de datos c++

Programa desarrollado en el lenguaje c++, muestra el funcionameinto de la estructura de datos tipo arbol AVL.
aqui les dejamos la parte importante del codigo.

inserta_avl(nodo *&raiz,int dato)
{
nodo *q,*r,*x;
  if(raiz != NULL)
  {
      if(dato < raiz->inf)
      {
         raiz->inserta_avl(raiz -> izq,dato);
         if(cen==1)
         {
          switch(raiz->fe)
          {
            case 1:raiz->fe=0;
                  cen=0;
                  break;
            case 0:raiz->fe=-1;
                 break;
            case -1:q=raiz->izq;
            if(q->fe<=0)
            {
             //rotacion I.I.
             raiz->izq=q->der;
             q->der=raiz;
             raiz->fe=0;
             raiz=q;
            }
            else
            {
             //rotacion I.D.
               r=q->der;
               raiz->izq=r->der;
               r->der=raiz;
               q->der=r->izq;
               r->izq=q;
               if(r->fe==-1)
               {
                  raiz->fe=1;
               }
               else
               {
                 raiz->fe=0;
               }
               if(r->fe==1)
               {
                 q->fe=-1;
               }
               else
               {
                q->fe=0;
               }
               raiz=r;
            }
        raiz->fe=0;
        cen=0;
        break;
      }
    }
  }
  else
  {
   if(dato > raiz->inf)
   {
     raiz->inserta_avl(raiz->der,dato);
     if(cen==1)
     {
        switch(raiz->fe)
        {
           case -1:raiz->fe=0;
                   cen=0;
                   break;
          case 0:raiz->fe=1;
                   break;
          case 1:q=raiz->der;
          if(q->fe>=0)
          {
             //rotacion D.D.
             raiz->der=q->izq;
             q->izq=raiz;
             raiz->fe=0;
             raiz=q;
          }
          else
          {
             //rotacion D.I.
            r=q->izq;
            raiz->der=r->izq;
            r->izq=raiz;
            q->izq=r->der;
            r->der=q;
            if(r->fe==1)
            {
               raiz->fe=-1;
            }
            else
            {
              raiz->fe=0;
            }
            if(r->fe==-1)
            {
              q->fe=1;
            }
            else
            {
              q->fe=0;
            }
            raiz=r;
          }
          raiz->fe=0;
          cen=0;
          break;
        }
     }
   }
      else
      {
        clrscr();
        gotoxy(25,15);cout<<"La clave"<< raiz-> inf<<" ya existe";
       getch();
      }
   }
 }
 else
 {
    raiz=new(nodo);
    raiz->inf=dato;
    raiz->izq=NULL;
    raiz->der=NULL;
    raiz->fe=0;
    cen=1;
 }
return (raiz);
}

Si gustan todo el programa, pueden dejarme un comentario y se los enviare en el tiempo mas corto posible....gracias..!!

Aplicacion Pilas - Expresiones Aritmeticas

Programa diseñado para convertir una expresion infija a postfija..(Ejm. a+b -> ab+)

#include < conio.h >
#include < iostream.h >
#include < stdio.h >
#include < string.h >
#define MAX 25
class pila
{
    public:
       int tope;
       char x[MAX];
   public:
       void posfija(char ei[],char x[],int tope);
       int prioridad(char ei);
       char operador(char ei);
};
void main()
{
char ei[MAX],dato;
pila ob;
ob.tope=-1;
char op;
   do
   {
       clrscr();
       gotoxy(29,7);cout<<"ÚÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄ¿";
       gotoxy(29,8);cout<<"³ APLICACION PILAS ³";
       gotoxy(29,9);cout<<"ÀÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÙ";
       gotoxy(20,12);cout<<"Tratamiento de Expresiones Aritmeticas";
       gotoxy(20,13);cout<<"ÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄ";
       gotoxy(26,16);cout<<"ingrese expresion aritmetica:";
       gotoxy(18,19);cout<<"Notacion INFIJA: ";gotoxy(35,19);cin>>ei;
       gotoxy(18,22);ob.posfija(ei,ob.x,ob.tope);
       gotoxy(15,25);cout<<"ÚÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄ¿";
       gotoxy(15,26);cout<<"³ ¨Desea transformar otra expresion (S/N)? [ ] ³";
       gotoxy(15,27);cout<<"ÀÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÙ";
       gotoxy(59,26);cin>>op;
   }while(op=='s' || op=='S');
}

void pila::posfija(char ei[],char x[],int tope)
{
char epos[MAX]=" ";
int i,j;
char dato;
i=0;
j=0;
    while(ei[i]!=NULL)
    {
        if(ei[i]=='(')
        {
           tope=tope+1;
           x[tope]=ei[i];
        }
        else
        {
             if(ei[i]==')')
             {
                 while(x[tope]!='(')
                 {
                    epos[j]=x[tope];
                    tope=tope-1;
                    j++;
                 }
                 tope=tope-1;
             }
             else
             {
                  dato=operador(ei[i]);
                  if(ei[i]!=dato)
                  {
                     epos[j]=ei[i];
                     j++;
                  }
                  else
                  {
                     while(tope>-1 && prioridad(ei[i])<=prioridad(x[tope]))
                     {
                         epos[j]=x[tope];
                         tope=tope-1;
                         j++;
                     }
                     tope=tope+1;
                     x[tope]=ei[i];
                  }
             }
         }
     i++;
    }
    while(tope>-1)
    {
       epos[j]=x[tope];
       tope=tope-1;
       j++;
    }
cout<<"Notacion POSTFIJA: "<< epos;
getch();

}
int pila::prioridad(char s)
{
   if (s=='+' || s=='-')
      return 0;
   else if (s=='*' || s=='/')
      return 1;
   else if (s=='^')
      return 2;
return -1;
}
char pila::operador(char ei)
{
char operadores[5], op=' ';
int i,cen;
operadores[1]='+';
operadores[2]='-';
operadores[3]='*';
operadores[4]='/';
operadores[5]='^';
i=1;
cen=0;
    while(i<=5 && cen==0)
    {
        if(operadores[i]==ei)
        {
           cen=1;
           op=operadores[i];
        }
    i++;
    }
return (op);
}

Cola Prioritaria - Listas Enlazadas C++

Programa efectuado con estructura de datos tipo lista enlazada simples, este programa simula la atencion de personas segun su orden de llegada pero se atienden segun la prioridad de su nivel(mientras su nivel sea mas alto este se atendera primero).

# include < conio.h >
#include < iostream.h >
#include < stdio.h >
#include < stdlib.h >
class nodo
{
     public:
         nodo *sig;
         char inf[10];
         int nivel;
    public:
         nodo *inserta_f(nodo *p);
         nodo *elimina_i(nodo *p);
         void recorre(nodo *p);

};
void main()
{
char op;
nodo *p=NULL;
    do
    {
        clrscr();
        gotoxy(25,10);cout<<"SISTEMA DE ATENCION - COLAS PRIORITARIAS";
        gotoxy(25,11);cout<<"ÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄ";
        gotoxy(28,13);cout<<"1.- INGRESAR USUARIOS";
        gotoxy(28,15);cout<<"2.- Reporte de atencion";
        gotoxy(38,20);cout<<"presione 'ESC' para salir";
        op=getch();
        switch(op)
        {
            case '1':p=p->inserta_f(p);
                    break;
            case '2':p->recorre(p);
                    break;
        }
    }while(op!=27);
}

nodo *nodo::inserta_f(nodo *p)
{
nodo *q,*r,*ref;
char op;
int n, cen;
    do
    {
        clrscr();
        q=new(nodo);
        cout<<"ingrese dato: ";
        cin>>q->inf;
        n=random(11);
        if(n==0)
        {
             q->nivel=1;
        }
        else
        {
            q->nivel=n;
        }
        cen=0;
        if(p!=NULL)
        {
            ref=p;
            cen=0;
            while(ref->nivel>=q->nivel &&(cen==0))
            {
                if(ref->sig!=NULL)
                {
                    r=ref;
                    ref=ref->sig;
                }
                else
                cen=1;
           }
           if(cen!=0)
           {
               ref->sig=q;
               q->sig=NULL;
           }
           else
           {
               q->sig=ref;
               if(p==ref)
               p=q;
               else
               r->sig=q;
           }
        }
        else
        {
            q->sig=NULL;
            p=q;
        }
        cout<<"mas datos (S/N)?: ";
        cin>>op;
    }while(op=='s' || op=='S');
return(p);
}

void nodo::recorre(nodo *p)
{
     clrscr();
     if(p!=NULL)
     {
         nodo *q=p;
         while(q!=NULL)
         {
                cout<< q->inf <<"------ "<< q->nivel<< endl;
                q=q->sig;
         }
          getch();
     }
     else
     {
         clrscr();
         gotoxy(30,10);cout<<"LA COLA ESTA VACIA";
         getch();
     }
}

Pilas en C++

Programa desarrollado en lenguaje C++, que soporta unicamente valores de tipo entero(int), logrando almacenar en su ejecucion 5 enteros, este valor se puede modificar, cambiando el valor de MAX al valor que desee.

#include < conio.h >
#include < iostream.h >
#include < stdio.h >
#define MAX 5
class pila
{
      public:
         int tope;
         int x[MAX];
      public:
         int insertar(int x[], int tope);
         int eliminar(int x[], int tope);
         void recorre(int x[],int tope);
};
void main()
{
pila ob;
ob.tope=-1;
char op;
    do
    {
       clrscr();
       gotoxy(35,8);cout<<"P I L A S";
       gotoxy(30,11);cout<<"1.- INSERTAR";
       gotoxy(30,13);cout<<"2.- ELIMINAR";
       gotoxy(30,15);cout<<"3.- RECORRE";
       gotoxy(40,20);cout<<"PRESIONE 'ESC' PARA SALIR";
       op=getch();
       switch(op)
       {
           case '1':ob.tope=ob.insertar(ob.x,ob.tope);
                    break;
           case '2':ob.tope=ob.eliminar(ob.x,ob.tope);
                    break;
           case '3':ob.recorre(ob.x,ob.tope);
                    break;
       }
    }while(op!=27);
}
int pila::insertar(int x[],int tope)
{
 clrscr();
    if(tope < MAX-1 )
    {
       tope=tope+1;
       cout<<"ingrese dato: ";
       cin>>x[tope];
    }
    else
    { 
       gotoxy(25,10);cout<<"Pila llena no se puede insertar";
       getch();
    }
return(tope);
}
int pila::eliminar(int x[], int tope)
{

    clrscr();
    if(tope>-1)
    {
       tope=tope-1;
       gotoxy(25,10);cout<<"descargando pila....!!";
       gotoxy(25,12);cout<<"solo quedan "<< tope+1 <<" datos";
       getch();
    }
    else
    {
       gotoxy(30,10);cout<<"La pila esta vacia";
       getch();
    }
return(tope);
}
void pila::recorre(int x[],int tope)
{
    clrscr();
    if(tope >-1)
    {
        for(int i=0;i<=tope;i++)
        {
           cout<< x[i] <<"\n";
           getch(); 
        }
    else
    {
        gotoxy(30,10);cout<<"LA PILA ESTA VACIA";
        getch();
    }
}

Invertir Lista Enlazada Simple

#include "conio.h"
#include "iostream.h"
#include "string.h"
class nodo
{
    public:
       nodo *sig;
       char inf[5];
    public:
      nodo *inserta(nodo *p);
      nodo *invertir(nodo *p);
      void recorre(nodo *p);
};
void main()
{
char op;
nodo *p=NULL;
    do
    {
       clrscr();
       cout<<"\t\t1.- cargar lista\n";
       cout<<"\t\t2.- invertir lista\n";
       cout<<"\t\t3.- recorrer";
       op=getch();
       switch(op)
       {
            case '1': p=p->inserta(p);
                     break;
            case '2': p=p->invertir(p);
                     break;
            case '3': p->recorre(p);
                     break;
       }
    }while(op!=27);
}
nodo *nodo::inserta(nodo *p)
{
char op;
nodo *q, *r;
   do
   {
      clrscr();
      q=new(nodo);
      cout<<"ingrese dato";
      cin>>q->inf;
      if(p!=NULL)
      {
           r=p;
           while(r->sig!=NULL)
           {
              r=r->sig;
           }
           r->sig=q;
           q->sig=NULL;
      }
      else
      {
          q->sig=NULL;
          p=q;
      }
      cout<<"mas datos(S/N)? ";
      cin>>op;
   }while(op=='s' || op=='S');
return(p);
}
nodo *nodo::invertir(nodo *p)
{
nodo *q,*r,*x,*y;
    q=p;
    while(q->sig!=NULL)
    {
       q=q->sig;
    }
    r=p->sig;
    q->sig=p;
    p->sig=NULL;
    y=p;
    while(r!=q)
    {
       x=r;
       r=r->sig;
       q->sig=x;
       x->sig=y;
       y=x;
    }
    p=q;
    p->recorre(p);
return(p);
}

Operaciones con Polinomios C++

Aqui les dejo un programa q suma, resta y deriva Polinomios de una variable:
cualquier consulta haganmela saber

class nodo
{
    public:
       nodo *sig;
       float coef;
       int expo;
    public:
       nodo *crea_pol(nodo *p, int n);
       nodo *insertar_f(nodo *f,float coef, int expo);
       void suma();
       void resta();
       void multiplicacion();
       void division();
       void derivar();
       void grado_pol();
       void recorre(nodo *p);
};
void main()
{
nodo *aux;
char op;
   do
   {
      clrscr();
      gotoxy(25,4);cout<<"OPERACIONES CON POLINOMIOS (1 variable)";
      gotoxy(25,5);cout<<"ÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄ";
      gotoxy(28,8);cout<<"1.-SUMA";
      gotoxy(28,10);cout<<"2.-RESTA";
      gotoxy(28,12);cout<<"3.-DERIVADA";
      gotoxy(35,14);cout<<"ELIJA OPCION [ ]";
      gotoxy(45,19);cout<<"->Presione 'ESC' para SALIR";
      gotoxy(49,14);op=getch();
      //cout<<"numero de terminos del polinomio";cin>>n;
      switch(op)
      {
         case '1':aux->suma();
                 break;
         case '2':aux->resta();
                 break;
         case '3': aux->derivar();
                 break;
      }
   }while(op!=27);
}
void nodo::suma()
{
nodo *r,*t,*f=NULL,*p=NULL,*q=NULL;
int n;
float suma;
      clrscr();
      gotoxy(27,3);cout<<"SUMA DE POLINOMIOS\n\n";
      cout<<"numero de terminos P(x): ";cin>>n;
      p=p->crea_pol(p,n);
      cout<<"numero de terminos Q(x): ";cin>>n;
      q=q->crea_pol(q,n);
      r=p;
      t=q;
      while(r!=NULL && t!=NULL)
      {
           if(r->expo==t->expo)
           {
               suma=r->coef+t->coef;
               if(suma!=0)
               {
                    f=f->insertar_f(f,suma,r->expo);
                    r=r->sig;
                    t=t->sig;
               }
           }
           else
           {
                if(r->expo > t->expo)
                {
                   f=f->insertar_f(f,r->coef,r->expo);
                   r=r->sig;
                }
                else
                {
                   f=f->insertar_f(f,t->coef,t->expo);
                   t=t->sig;
                }
           }
      }
      while(r!=NULL)
      {
          f=f->insertar_f(f,r->coef,r->expo);
          r=r->sig;
      }
      while(t!=NULL)
      {
          f=f->insertar_f(f,t->coef,t->expo);
          t=t->sig;
      }
      cout<<"P(x)+Q(x)= ";f->recorre(f);
}

void nodo::resta()
{
nodo *r,*t,*f=NULL,*p=NULL,*q=NULL;
int n;
float resta;
      clrscr();
      gotoxy(27,3);cout<<"RESTA DE POLINOMIOS\n\n";
      cout<<"numero de terminos P(x): ";cin>>n;
      p=p->crea_pol(p,n);
      cout<<"numero de terminos Q(x): ";cin>>n;
      q=q->crea_pol(q,n);
      r=p;
      t=q;
      while(r!=NULL && t!=NULL)
      {
           if(r->expo==t->expo)
           {
               resta=r->coef-t->coef;
               if(resta!=0)
               {
                  f=f->insertar_f(f,resta,r->expo);
                  r=r->sig;
                  t=t->sig;
               }
           }
           else
           {
               if(r->expo > t->expo)
               {
                   f=f->insertar_f(f,r->coef,r->expo);
                   r=r->sig;
               }
               else
               {
                   f=f->insertar_f(f,t->coef,t->expo);
                   t=t->sig;
               }
           }
      }
      while(r!=NULL)
      {
         f=f->insertar_f(f,r->coef,r->expo);
         r=r->sig;
      }
      while(t!=NULL)
      {
         f=f->insertar_f(f,t->coef,t->expo);
         t=t->sig;
      }
      cout<<"P(x)+Q(x)= ";f->recorre(f);
}
void nodo::derivar()
{
nodo *r,*p=NULL,*f=NULL;
int n,d;
float c;
      clrscr();
      gotoxy(27,3);cout<<"DERIVADA DE POLINOMIOS\n\n";
      cout<<"numero de terminos P(x): ";cin>>n;
      p=p->crea_pol(p,n);
      r=p;
      while(r!=NULL)
      {
         c=r->coef*r->expo;
         d=r->expo-1;
         if(c!=0)
         {
             f=f->insertar_f(f,c,d);
         }
         r=r->sig;
      }
      cout<<"DERIVADA DE P(x): ";f->recorre(f);
}

Listas Dobles Enlazadas

* Es un tipo de lista enlazada que permite moverse hacia delante y hacia atras.

* Cada nodo de una lista doblemente enlazada tiene dos enlaces, ademas de los campos de datos. Un enlace, el derecho, se utiliza para navegar la lista hacia delante. El otro enlace, el isquierdo, se utiliza para navegar la lista hacia atras.

Principales ventajas:

 1. Permite caminar en las dos direcciones de la lista.

 2. Inserción y eliminación de elementos son realizados con más facilidad.

Principales problemas:

 • Mayor espacio reservado

 • Manipulación de un puntero extra Implementación (Dinámica)

Por simplicidad los elementos almacenados serán números enteros. Los elementos serán insertados de forma ordenada. (Fig 4.2)La operación de inserción de un nuevo elemento en la posición anterior al elemento actual puede ser descrito como sigue (suponiendo que actual no es el primer elemento de la lista)

p:puntero de cabecera
f:puntero final de la lista //ambos punteros se pueden declarar como variables globales
FUNCION INSERTAR - LISTA DOBLE

insertar_di()
{
nodo *q;
char op;
  do
  {
      clrscr();
      q=new(nodo);
      cout<<"ingrese dato: ";
      cin>>q->inf;
      q->sig=p;
      q->ant=NULL;
      if(p==NULL)
      {
         f=q;
      }
      else
      {
         p->ant=q;
      }
      p=q;
      cout<<"mas datos";
      cin>>op;
  }while(op=='s' || op=='S');
}

Listas Enlazadas Circulares

Una lista circular es una lista lineal en la que el último nodo a punta al primero.

Las listas circulares evitan excepciones en la operaciones que se realicen sobre ellas. No existen casos especiales, cada nodo siempre tiene uno anterior y uno siguiente.

En algunas listas circulares se añade un nodo especial de cabecera, de ese modo se evita la única excepción posible, la de que la lista esté vacía.

El nodo típico es el mismo que para construir listas enlazadas simples:

FUNCION INSERTAR

inserta_fc(nodo *p)
{
nodo *q,*r;
char op;
   do
   {    
       clrscr();   
       q=new(nodo);
         cout<<"ingrese dato";
       cin>>q->inf;
      if(p!=NULL)
      {
        r=p;
        while(r->sig!=p)
        {
           r=r->sig;
        }
        r->sig=q;
        q->sig=p;
     }
     else
     {
       p=q;
       q->sig=p;
     }
    cout<<"mas datos()? ";
    cin>>op;
 }while(op=='s' || op=='S');
return(p);
}

FUNCION ELIMINAR

elimina_fc(nodo *p)
{
nodo *r, *t;
     clrscr();
     if(p!=NULL)
     {
        r=p;
        while(r->sig!=p)
        {
           t=r;
           r=r->sig;
        }
        if(p==r)
        {
           p=NULL;
        }
        else
        {
           t->sig=p;
        }
        delete(r);
        cout<<"el eltimo nodo fue eliminado";
        getch();
    }
    else
    {
       cout<<"la lista esta vacia";
       getch();
    }
return(p);
}

Listas Enlazadas Simples

1.1 Definición
La forma más simple de estructura dinámica es la lista abierta. En esta forma los nodos se organizan de modo que cada uno apunta al siguiente, y el último no apunta a nada, es decir, el puntero del nodo siguiente vale NULL.
En las listas abiertas existe un nodo especial: el primero. Normalmente diremos que nuestra lista es un puntero a ese primer nodo o llamaremos a ese nodo la cabeza de la lista. Eso es porque mediante ese único puntero podemos acceder a toda la lista.
Cuando el puntero que usamos para acceder a la lista vale NULL, diremos que la lista está vacía.
El nodo típico para construir listas tiene esta forma:

struct nodo
{
  char dato;
  nodo *siguiente;
};

1.2 Operaciones básicas con listas:
Con las listas tendremos un pequeño repertorio de operaciones básicas que se pueden realizar:
• Añadir o insertar elementos.
• Buscar o localizar elementos.
• Borrar elementos.
• Moverse a través de una lista, anterior, siguiente, primero.
FUNCION INSERTAR

inserta_por_el_inicio(nodo *p)
{
  nodo *q;
  q=new(nodo);
  cin>>q->inf;
  q->sig=p;
  p=q;
  return (p);
}

FUNCION ELIMINAR

elimina_f(nodo *p)
{
 nodo *r,*t;
 char op;
    if(p!=NULL)
    {
        clrscr();
        cout<<"\n\t¨ ESTA SEGURO QUE QUIERE ELIMINAR(S/N)?";
        cin>>op;
        if(op=='S' || op=='s')
        {
            r=p;
            while(r->sig!=NULL)
            {
                t=r;
                r=r->sig;
            }
            if(p==r)
            {
                p=NULL;
            }
            else
            {
                t->sig=NULL;
            }
            delete(r);
            cout<<"EL ULTIMO NODO DE LA LISTA AH SIDO ELIMINADO";
            getch();
        }
    }
    else
    {
    clrscr();
    cout<<"LA LISTA ESTA VACIA";
    getch();
    }
  return(p);
}