LISTAS.c

// OPERACIONES VARIAS CON LISTAS TIPO LISP

#include <stdio.h>
#include <stdlib.h>

struct numero
{
   int num;
   struct numero *sig;
};

struct valores
{
   struct numero *l1;
   struct numero *l2;
};

struct numero *vals;

void imprime(struct numero *l)
{
   printf("\nLista ordenada\n"); 
   while(l) 
   {
      printf("%d ", l->num); 
      l = l->sig; 
   }
}

struct numero *crea_espacio(void)
{
   struct numero *nodo;

   if (!(nodo = (struct numero *) malloc(sizeof(struct numero))))
      { puts("no hay memoria...\n"); return NULL; }
   nodo->sig = NULL;
   nodo->num = 0;
   return nodo;
}

struct numero *pide_numeros(void)
{
   int valor = 1;
   struct numero *nodo = NULL;
   struct numero *ant  = NULL;
   struct numero *sig  = NULL;
   struct numero *ini  = NULL;

   puts("\ntermine con un 0\n");

   while(valor != 0)
   {
      scanf("%d", &valor);
      if (!valor) break;
      nodo = crea_espacio();
      nodo->num = valor;
      if (!ini) { ini = nodo; ant = nodo; }
      else   { ant->sig = nodo; ant = nodo;}
   }
   return ini;
}


void append(struct numero *l, struct numero *nuevo)
{
   struct numero *temp = NULL;

   while(l)
   {
      temp = l;
      l = l->sig;
   }
   if(!temp) return;

   while(nuevo)
   {
      temp->sig = crea_espacio();
      temp->sig->num = nuevo->num;
      temp = temp->sig;
      nuevo = nuevo->sig;
   }
}

void divide(struct numero *l)
{
   int flag = 1;

   vals->l1 = crea_espacio();
   vals->l2 = crea_espacio();

   while(l)
   {
      if (flag)
      {
         if (!vals->l1->num)  vals->l1 = l;
         else {append(vals->l1, l); flag = 0;}
      }
      else
      {
         if (!vals->l2->num)  vals->l2->num = l->num;
         else {append(vals->l2, l); flag++;}
      }
      l = l->sig;
   }
   imprime(vals->l1);
   imprime(vals->l2);
}

struct numero *mezcla(struct numero *l01, struct numero *l02)
{
   struct numero *ant = NULL;
   struct numero *ini = NULL;
   struct numero *tem = NULL;

   printf("\n<<mezcla>>\n");
   while(l01 && l02)
   {
      tem = crea_espacio();
      if(l01->num < l02->num)
         { tem->num = l01->num; l01 = l01->sig;}
      else
         { tem->num = l02->num; l02 = l02->sig;}

      if(!ini) {ini = tem; ant = tem;}
      else {ant->sig = tem; ant = tem;}
   }
   if(l01) append(tem, l01);
   if(l02) append(tem, l02);
   return ini;
}

struct numero *ordena(struct numero *l)
{
   struct numero *l01=NULL;
   struct numero *l02=NULL;

   if(l && !l->sig) return l;

   printf("\ndato= %d",l->num);
   divide(l);
   l01 = ordena(vals->l1);
   l02 = ordena(vals->l2);
   return mezcla(l01, l02);
}

void main (void)
{
   struct numero *a;

   vals = (struct valores *) malloc(sizeof(struct valores));
   a = pide_numeros();
   a = ordena(a);
   imprime(a);
}