Ordenar listas enlazadas
Hola. Me gustaria saber como puedo ordenar listas enlazadas segun un valor de un campo entero.
Yo conozco los metodos tradicionales de ordenacion de arrays estaticos: burbuja, etc.
Pero ¿ son convenientes en listas enlazadas ?
¿ Como deberia ser la lista ? ¿ Simple, doble ?
¿ Seria posible usar la funcion qsort del C estandar definida en stdlib.h ???
Yo los nodos de la lista los tengo definidos del tipo:
struct nodo
{
int clave;
struct nodo* sig;
}
¿ Alguien sabe algun codigo de ejemplo ?
Yo conozco los metodos tradicionales de ordenacion de arrays estaticos: burbuja, etc.
Pero ¿ son convenientes en listas enlazadas ?
¿ Como deberia ser la lista ? ¿ Simple, doble ?
¿ Seria posible usar la funcion qsort del C estandar definida en stdlib.h ???
Yo los nodos de la lista los tengo definidos del tipo:
struct nodo
{
int clave;
struct nodo* sig;
}
¿ Alguien sabe algun codigo de ejemplo ?
ESTO TE SIRVE...
#include<stdio.h>
#include<conio.h>
#include<alloc.h>
struct nodo //definicion de tipo
{
int clave;
nodo *sig; //guarda el nodo completo
}
*primero;
//CENTRA TEXTO
void centra(char *txt,int f)
{
gotoxy( ( 80 - strlen(txt) ) / 2, f ); printf("%s",txt);
}
//CONSULTA GRAL
void consulta(nodo *primero)
{
int col=3,band=0,cont=0;
clrscr();
centra("CONSULTA GENERAL",4);
nodo *indice;
for(indice=primero;indice!=NULL;indice=indice->sig)
{
band=1;
gotoxy(col,8);printf("%d,",indice->clave);
col+=3;
cont++;
}
if(!band)
{
centra("LA LISTA ESTA VACIA",24);
}
if(band)
{
gotoxy(55,45);printf("Total de datos %d",cont);
}
getch();
}
//AGREGA ORDENADAMENTE
nodo *agregar(nodo *primero)
{
nodo *p,*actual,*anterior;
int dato;
clrscr();
centra("AGREGA ORDENADAMENTE",4);
gotoxy(3,10);printf("Introduce el dato: ");
scanf("%d",&dato);
p=(nodo*)malloc(sizeof(nodo));
if(p!=NULL)
{
p->clave=dato;
p->sig=NULL;
}
if(primero==NULL)
{
primero=p;
}
else
{
if( p->clave > primero->clave ) //checa que no se mas grande
{ //que el primero
p->sig=primero;
primero=p;
}
else
{
actual=primero;
while((actual!=NULL) && (actual-> clave > dato ))
{
anterior=actual;
actual=actual->sig;
}
anterior->sig=p;
p->sig=actual;
}
}//
getch();
return primero;
}//fin
void main()
{
nodo *primero=NULL;
char opc;
do
{
clrscr();
centra("LISTAS ENLAZADAS",19);
centra("Insertar Datos........................1",22);
centra("Ver Datos.............................2",24);
centra("Salir.................................3",26);
centra("Elige Opcion.........................[ ]",29);
gotoxy(58,29);opc=getch();
switch(opc)
{
case '1': primero=agregar(primero); break;
case '2': consulta(primero); break;
}
}
while(opc!='3');
}
#include<stdio.h>
#include<conio.h>
#include<alloc.h>
struct nodo //definicion de tipo
{
int clave;
nodo *sig; //guarda el nodo completo
}
*primero;
//CENTRA TEXTO
void centra(char *txt,int f)
{
gotoxy( ( 80 - strlen(txt) ) / 2, f ); printf("%s",txt);
}
//CONSULTA GRAL
void consulta(nodo *primero)
{
int col=3,band=0,cont=0;
clrscr();
centra("CONSULTA GENERAL",4);
nodo *indice;
for(indice=primero;indice!=NULL;indice=indice->sig)
{
band=1;
gotoxy(col,8);printf("%d,",indice->clave);
col+=3;
cont++;
}
if(!band)
{
centra("LA LISTA ESTA VACIA",24);
}
if(band)
{
gotoxy(55,45);printf("Total de datos %d",cont);
}
getch();
}
//AGREGA ORDENADAMENTE
nodo *agregar(nodo *primero)
{
nodo *p,*actual,*anterior;
int dato;
clrscr();
centra("AGREGA ORDENADAMENTE",4);
gotoxy(3,10);printf("Introduce el dato: ");
scanf("%d",&dato);
p=(nodo*)malloc(sizeof(nodo));
if(p!=NULL)
{
p->clave=dato;
p->sig=NULL;
}
if(primero==NULL)
{
primero=p;
}
else
{
if( p->clave > primero->clave ) //checa que no se mas grande
{ //que el primero
p->sig=primero;
primero=p;
}
else
{
actual=primero;
while((actual!=NULL) && (actual-> clave > dato ))
{
anterior=actual;
actual=actual->sig;
}
anterior->sig=p;
p->sig=actual;
}
}//
getch();
return primero;
}//fin
void main()
{
nodo *primero=NULL;
char opc;
do
{
clrscr();
centra("LISTAS ENLAZADAS",19);
centra("Insertar Datos........................1",22);
centra("Ver Datos.............................2",24);
centra("Salir.................................3",26);
centra("Elige Opcion.........................[ ]",29);
gotoxy(58,29);opc=getch();
switch(opc)
{
case '1': primero=agregar(primero); break;
case '2': consulta(primero); break;
}
}
while(opc!='3');
}