Newsgroup: it.comp.lang.c
Titolo: ordinare una lista

Ho una lista di strutture che hanno come record una stringa e tre
interi.
Vorrei ordinare la lista prima per nome usando il campo descrizione
che e'  una stringa, e poi per valore di uno dei tre campi numerici.
Ho trovato i vari algoritmi di bubblesort, quick ecc, ma lavorano
tutti su array di lunghezza definita.
Mi devo rifare completamente l'algoritmo sfruttando quello che ho
trovato come modello?
Qualcuno ha degli algoritmi di ordinamento gia' fatti che funzionano
con le liste?
Grazie
Ciao
james

con le liste?
Secondo me ti conviene trasformare la lista in albero binario e
ritrasformarla in lista mediante l'attraversamento in ordine.

 con le liste?
Eccolo qua...
-- 
Maurizio Loreti                      
http://wwwcdf.pd.infn.it/~loreti/mlo.html
Un. of Padova, Dept. of Physics - Padova, Italy          
lor...@padova.infn.it
----------------------Begin included file: msort.h----------------------
#ifndef MSORT_H_
#define MSORT_H_
Mylist *msort (Mylist *list, int (*cmp)(const Mylist *, const Mylist *));
Mylist *msort2(Mylist *list, int (*cmp)(const Mylist *, const Mylist *));
#endif /* MSORT_H_ */
-----------------------End included file: msort.h-----------------------
----------------------Begin included file: msort.c----------------------
/* Generic sort-routine for linked lists (=^= qsort for arrays)
 *
 * Permission to use, copy, modify, and distribute this software for any
 * purpose and without fee is hereby granted, provided that the above
 * copyright notice appears in all copies and that both that copyright
 * notice and this permission notice appear in supporting documentation.
 * This software is provided "as is" without expressed or implied warranty.
 *
 * Copyright 1993-1999 Maurizio Loreti (
lor...@pd.infn.it
)
 * #define TEST for a quick and dirty test program.
 *
 * Usage (example):
 *
 *     #include "msort.h"
 *     typedef struct sMylist { ...
 *                              struct sMylist *next;
 *                              ...
 *                            } Mylist;
 *     Mylist *list;
 *
 *     list = msort(list, cmp);
 *
 *
 * cmp(Mylist *a, Mylist *b) is similar to the compare-functions used in
 * qsort() and bsearch(). It compares two Mylist-structs and returns
 *      0  if both are equal,
 *     <0  if a->something < b->something
 *     >0  otherwise.
 *
 *
 * For double-linked lists, msort2() sorts along one link-pointer and then
 * re-adjusts the second link-pointers:
 *
 *      #include "msort.h"
 *      typedef struct sMylist { ...
 *                               struct sMylist *next,
 *                               struct sMylist *prev,
 *                               ...
 *                             } Mylist;
 *
 *      Mylist *list;
 *
 *      list = msort2(list, cmp);
 *
 * This sorts the list along the next-pointers and then re-adjusts the
 * prev-pointers.  msort2() calls msort() to do the sorting, thus the prev-
 * pointers are not needed for the sorting.  In fact, you can build an un-
 * sorted double-linked list like a single-linked list without careing about
 * the prev-pointers, then call msort2() to get a sorted list with valid
 * link pointers for both directions.
 */
#ifdef TEST
typedef struct sMylist {        /* List node */
  struct sMylist    *next;
  struct sMylist    *prev;
  unsigned long int  data;
} Mylist;
#endif /* TEST */
#include "msort.h"
static Mylist *ms_split(Mylist *, int (*)(const Mylist *, const Mylist *));
static Mylist *ms_merge(Mylist *, Mylist *,
                        int (*)(const Mylist *, const Mylist *));
Mylist *msort(
  Mylist *list,
  int (*cmp)(const Mylist *, const Mylist *)
) {
  Mylist *ptr;
  ptr  = ms_split(list,      cmp);
  list = ms_merge(list, ptr, cmp);
  return list;
}
Mylist *msort2(
  Mylist *list,
  int (*cmp)(const Mylist *, const Mylist *)
) {
  if (list) {
    Mylist *pp, *p;
    pp = list = msort(list, cmp);
    for (pp->prev = 0;   (p = pp->next);   p->prev = pp,  pp = p) { }
  }
  return list;
}
static Mylist *ms_split(
  Mylist *list,
  int (*cmp)(const Mylist *, const Mylist *)
) {
  Mylist *p, *newlist;
  for (newlist = 0;   (p = list->next);   ) {
    if (cmp(list, p) > 0) {
      list->next = p->next;
      p->next    = newlist;
      newlist    = p;
    } else {
      list = p;
    }
  }
  if (newlist) {                /* msort() on newlist */
    p       = ms_split(newlist,    cmp);
    newlist = ms_merge(newlist, p, cmp);
  }
  return newlist;
}
static Mylist *ms_merge(
  Mylist *a,
  Mylist *b,
  int (*cmp)(const Mylist *, const Mylist *)
) {
  Mylist *newlist;
  Mylist **p;
  for (newlist = 0,  p = &newlist;   a && b;   p = &((*p)->next)) {
    if (cmp(a, b) < 0) {
      *p = a;
      a  = a->next;
    } else {
      *p = b;
      b  = b->next;
    }
  }
  *p = a ? a : b;
  return newlist;
}
#ifdef TEST
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#define NTRIES 100
static int cmp(const Mylist *, const Mylist *);
static void ins(const unsigned long int);
static void prt(void);
static void rem(void);
static void upl(void);
Mylist *root = 0, *last = 0;
int main()
{
  int i;
  srand(time(0));
  for (i=0; i<NTRIES; i++) ins(rand());
  prt();
  puts("-----");
  root = msort2(root, cmp);
  upl();
  prt();
  rem();
  return 0;
}
static int cmp(                 /* Compare function */
  const Mylist *left,
  const Mylist *right
) {
  return (left->data - right->data);
}
static void ins(                /* Create a node (at the end) with data = i */
  const unsigned long int i
) {
  Mylist *p = malloc(sizeof(Mylist));
  p->data = i;
  p->next = 0;
  p->prev = last;
  if (!root) root = p;
  if (last) last->next = p;
  last = p;
}
static void prt(void)           /* Print the whole list */
{
  if (!root) {
    puts("List is empty.");
  } else {
    Mylist *p;
    int i;
    printf("First node contains %lu; last node contains %lu.\n",
           root->data, last->data);
    printf("Forward:");
    for (i=0, p=root; p; i++, p=p->next) {
      if (!(i%5)) puts("");
      printf("%15lu", p->data);
    }
    printf("\nBackward:");
    for (i=0, p=last; p; i++, p=p->prev) {
      if (!(i%5)) puts("");
      printf("%15lu", p->data);
    }
    puts("");
  }
}
static void rem(void)           /* Memory cleanup */
{
  while (root) {
    Mylist *p = root->next;
    free(root);
    root = p;
  }
  root = last = 0;
}
static void upl(void)           /* Check sorting; update 'last'. */
{
  Mylist *p = root;
  while (p->next) {
    if (p->data > p->next->data) puts("***FAILED***");
    p = p->next;
  }
  last = p;
}
#endif /* TEST */
-----------------------End included file: msort.c-----------------------