Programacion c++ – Método burbuja en listas dobles

Listas Dobles

En el siguiente programa, haremos uso de listas dobles que permita insertar, eliminar, modificar repetidos por el Método burbuja. La cual contará con un Menú de 10 opciones la cual se describe en la codificación.

#include<iostream.h>
#include<conio.h>

struct nodo{
     int nro;
      struct nodo*sgte;
      };

typedef struct nodo*TLista;
void insertaAlInicio(TLista &,int);
void insertaAlFinal(TLista &,int);
void insertaEnPosicion(TLista &, int, int);
void eliminaElemento(TLista &, int);
void eliminaLista(TLista &);
void eliminaRepetidos(TLista);
void burbuja(TLista);
void imprimir(TLista);
void modificar(TLista &,int, int);
void main(void)
{
clrscr();
getche();
TLista lista=NULL;
int opc,valor,pos,ps;
do
{
cout<<"PROGRAMA QUE REALIZA FUNCIONES PRINCIPALES CON LISTAS ENLAZADAS "<<endl;

cout<<"--------------------------------------------------------------- "<<endl<<endl;

cout<<"****  MENU ****"<<endl;

cout<<"1. Inserta al inicio"<<endl;
cout<<"2. Inserta al final"<<endl;
cout<<"3. Inserta en una posicion "<<endl;
cout<<"4. Listado"<<endl;
cout<<"5. Elimine elemento que ud desee: "<<endl;
cout<<"6. Elimina toda la lista "<<endl;
cout<<"7. Elimina elementos repetidos  "<<endl;
cout<<"8. Ordena por burbuja "<<endl;
cout<<"9. Modifcar elemento"<<endl;
cout<<"10. Salir"<<endl;
cout<<"ingrese su opcion: ";
cin>>opc;

switch(opc)
{
case 1: clrscr();cout<<"ingrese valor a insertar al inicio: \n";
 cin>>valor;
 insertaAlInicio(lista,valor);
 break;

case 2: clrscr();cout<<"ingrese valor a insertar al final: \n";
 cin>>valor;
 insertaAlFinal(lista,valor);
 break;

case 3: clrscr();cout<<"valor a insertar: \n";
 cin>>valor;
 cout<<"Posicion:\n ";cin>>pos;
 insertaEnPosicion(lista,valor,pos);
 break;

case 4: clrscr();cout<<endl<<"Listado \n"<<endl;
 imprimir(lista) ;
 break;

case 5: clrscr();cout<<endl<<"Elimina elemento :"<<endl;
        cout<<"valor del elemento ";cin>>valor;
 eliminaElemento(lista, valor);
 break;

case 6: clrscr();cout<<endl<<"..Elimina la lista "<<endl;
        eliminaLista(lista);
 break;

case 7: clrscr();cout<<endl<<"..Eliminando"<<endl;
        eliminaRepetidos(lista);
        break;

case 8: clrscr();cout<<endl<<"Lista ordenada "<<endl;
 burbuja(lista);
 imprimir(lista);break;

case 9:clrscr();cout<<"Ingrese la posicion a modificar:"<<endl;
       cin>>ps;
       cout<<"Ingrese el valor a ingresar:"<<endl;
       cin>>valor;
       modificar(lista,valor,ps);break;
      }
   }while(opc!=10);
}

void imprimir(TLista lista)
{ while (lista!=NULL)
   {cout<nro<<endl;
   lista=lista->sgte;
   }
cout<<endl;
}

void insertaAlInicio(TLista &lista, int valor)
{
TLista q;
q=new(struct nodo);
q->nro=valor;
q->sgte=lista;
lista=q;
}

void insertaAlFinal(TLista &lista, int valor)
{
TLista t, q=new(struct nodo);
q->nro=valor;
q->sgte=NULL;
if(lista==NULL)lista=q;
else {t=lista;
      while (t->sgte!=NULL) t=t->sgte;
      t->sgte=q;
      }
}

void insertaEnPosicion(TLista &lista, int valor, int pos)
{
TLista q,t;
int i;
q=new (struct nodo);
q->nro=valor;
if (pos==1) {q->sgte=lista;lista=q;}
else {t=lista;
      for(i=1;t!=NULL;i++)
      { if(i==pos-1) { q->sgte=t->sgte;
         t->sgte=q;
         return; }
      t=t->sgte;
      }
   }
cout<<"ERROR posicion erronea"<<endl;
}

void eliminaElemento(TLista & lista , int valor)
{
TLista p,ant;
p=lista;
while (p!=NULL)
{ if (p->nro==valor)
   { if(p==lista)
   lista=lista->sgte;
   else
   ant->sgte=p->sgte;
   delete(p);
   return;
   }
   ant=p;
   p=p->sgte;
   }
   }

void eliminaLista(TLista &lista)
{
TLista p;
while (lista!=NULL)
 { p=lista;
 lista=lista->sgte;
 delete(p);
 }
 }

void eliminaRepetidos(TLista lista)
{ TLista q,p,r,ant;
  int num;
  q=lista;
  while(q!=NULL)
  { num=q->nro;
    ant=q;
    r=q->sgte;
    while(r!=NULL)
    { if(num==r->nro)
      { ant->sgte=r->sgte;
      cout<<"Eliminando..."<<num<<endl;
      p=r;
      r=r->sgte;
      delete(p);
      }
    else { ant=r;
    r=r->sgte;
    }
    r=r->sgte;
    } //fin while
    q=q->sgte;
    } //fin while
  }

void burbuja(TLista lista)
{
TLista actual,siguiente,marca;
int t;
marca=NULL;
while(marca!=lista->sgte)
{ actual=lista;
  siguiente=actual->sgte;
  while(siguiente!=marca)
  { if(actual->nro>siguiente->nro)
     { t=siguiente->nro;
       siguiente->nro=actual->nro;
       actual->nro=t;
       }
     actual=actual->sgte;
     siguiente=actual->sgte;
     }
     marca=actual;
     }
  }//fin burbuja

void modificar(TLista &lista,int v,int ps)
{ TLista q,sgte;
  q=lista;
  int i;
  for(i=0;i<ps-1&&q->sgte!=NULL;i++)
     q=q->sgte;
     q->nro=v;
}

  Siguiendo con el Método burbuja, aquí te dejo otro ejercicio: Aplicación del Método burbuja para ordenar los elementos de un array.