Ordinamento della memoria di elenchi collegati

Titolo:Ordinamento della memoria di elenchi collegatiLingua:CAutore:Philip J. Erdelsky

Data:31 luglio 1998Utilizzo:Dominio pubblico; nessuna restrizione d’usoPortabilità:Qualsiasi compilatore CParole chiave:Elenco collegato, OrdinaAstratto:Funzione AC per ordinare una lista collegata in memoria, utilizzando una funzione di confronto arbitraria e un algoritmo di unione del nastro, che è O(n log n) in tutti i casi. La funzione è non ricorsiva e rientrante e modifica solo i collegamenti.

Gli elenchi collegati e le routine di ordinamento sono molto comuni nella programmazione.

La funzione sort_linked_list() ordinerà virtualmente qualsiasi tipo di elenco con collegamento singolo, utilizzando una funzione di confronto fornita dal programma chiamante. Presenta i seguenti vantaggi rispetto a qsort():

  1. Ordina elementi di dimensione variabile.
  2. Richiede O(n log n) confronti, indipendentemente dall’ordine iniziale. Il tempo per ordinare un elenco è prevedibile e coerente. Questa prestazione è nota per essere ottimale per gli ordinamenti generali.
  3. L’algoritmo è iterativo, non ricorsivo, quindi non ci sono problemi di stack overflow. Il requisito dello stack è prevedibile, coerente e ridotto.
  4. Ordina l’elenco collegato modificando i puntatori, non spostando gli elementi stessi.
  5. Può ordinare un elenco troppo grande per essere inserito in un array.

La funzione ordina solo elenchi collegati singolarmente. Se una lista è doppiamente collegata, i puntatori all’indietro possono essere ripristinati dopo l’ordinamento di poche righe di codice.

Ogni elemento di una lista collegata da ordinare deve contenere, come primi membri, uno o più puntatori. Uno dei puntatori, che deve trovarsi nella stessa posizione relativa in ogni elemento, è un puntatore all’elemento successivo. Questo puntatore è NULL nell’ultimo elemento.

L’indice è la posizione di questo puntatore in ogni elemento. È 0 per il primo puntatore, 1 per il secondo puntatore, ecc.

Sia compare() una funzione di confronto che confronta due elementi come segue:

     n = confronta(p, q, puntatore); 

     vuoto *p, *q; puntatori a due elementi della lista 

     void *pointer; puntatore definito dall'utente passato a compare() da 
                     linked_list_sort() 

     int n; risultato del confronto di *p e *q 
                       >0 se *p deve essere dopo *q in ordine 
                       <0 se *p deve essere prima di *q in ordine 
                        0 se l'ordine di *p e *q è irrilevante

Sia “first” un puntatore al primo elemento della lista. Quindi la seguente chiamata di funzione ordina l’elenco e restituisce un puntatore al primo elemento dell’elenco ordinato:

     first_sorted = 
       sort_linked_list(first, index, compare, pointer, pcount);

Il quarto argomento (puntatore) viene passato a compare() senza modifiche. L’esempio qui fornito non fa uso del puntatore. Tuttavia, può essere una caratteristica preziosa se due o più metodi di confronto condividono una notevole quantità di codice e differiscono solo per uno o più valori dei parametri.

L’ultimo argomento (pcount) è di tipo (unsigned long *). Se non è NULL, allora *pcount è uguale al numero di record nell’elenco.

È consentito ordinare un elenco vuoto. Se prima == NULL, anche il valore restituito sarà NULL.

Ad esempio, un elemento può contenere sia un nome che un numero:

    struct element 
    { 
      struct element *next_in_alphabetical_order; 
      elemento struttura *next_in_numerical_order; 
      nome del carattere[9]; 
      numero int; 
      /* altri membri, se presenti */ 
    };

Inizialmente, i due puntatori in ogni elemento sono identici e l’elenco è in ordine arbitrario, dove “first” è un puntatore al primo elemento. Le seguenti due chiamate di funzione ordinano l’elenco due volte:

    first_in_alphabetical_order = 
      sort_linked_list(first, 0, compare_names, NULL); 
    first_in_numerical_order = 
      sort_linked_list(first, 1, compare_numbers, NULL);

Ecco le funzioni di confronto:

    int compare_names(struct element *p, struct element *q, 
      void *pointer) 
    { 
      return strcmp(p->name, q->name); 
    } 

    int compare_numbers(struct element *p, struct element *q, 
      void *pointer) 
    { 
      return p->number > q->number ? 1 : -1; 
      /* NOTA: return p->number - q->number sarà sufficiente se non 
      c'è pericolo di overflow numerico */ 
    }

Una versione precedente di questo tipo, pubblicata su una rivista tecnica, richiedeva che il collegamento in avanti fosse all’inizio di ogni elemento. Sebbene ciò rendesse l’ordinamento un po’ più efficiente, ne rendeva anche difficile l’uso con più elenchi collegati.

L’algoritmo è abbastanza semplice. L’elenco collegato (chiamato “nastro” per analogia ai vecchi nastri magnetici) viene prima diviso in due nastri della stessa dimensione o quasi. Questo viene fatto “scrivendo” elementi sui due nastri alternativamente.

I due nastri vengono quindi uniti, elemento per elemento, in blocchi ordinati contenenti ciascuno due elementi. I blocchi vengono scritti alternativamente su altri due nastri.

I due nastri vengono quindi uniti, blocco per blocco, in blocchi ordinati di quattro elementi ciascuno, e i blocchi vengono scritti alternativamente su altri due nastri.

Il processo continua, raddoppiando ogni volta la dimensione del blocco, finché tutti gli elementi non si trovano in un unico blocco ordinato su un nastro. La funzione restituisce un puntatore al primo elemento di quel nastro.

Ogni unione richiede O(n) confronti, dove n è il numero di elementi. Il numero di unioni è O(log n). Quindi l’intero ordinamento richiede O(n log n) confronti.

La funzione sort_linked_list() è rientrante se la funzione di confronto è rientrante.

Gli appassionati saranno felici di sapere che questo algoritmo non può essere codificato facilmente in Ada o Pascal perché si basa su typecast.

La funzione sort_linked_list() può essere chiamata facilmente da un programma C++ con un minimo di controllo del tipo se è incluso il file di intestazione LLMSORT.H. Contiene un modello per la generazione in linea di una chiamata su sort_linked_list(). Il formato del bando è il seguente:

     #include "llmsort.h" 

     first_sorted = sort_list(first, compare, pointer, pcount); 

     la tua classe *prima; 
     la tua classe *first_sorted; 
     void *puntatore; 
     unsigned long *pcount;

La funzione compare() viene chiamata come segue:

     n = confronta(p, q, puntatore); 
     const la tua classe *p; 
     const la tua classe *q; 
     void *puntatore; 
     int n;

Qui “yourclass” è qualsiasi classe che puoi definire. Il compilatore verificherà la coerenza dei tipi di argomento e genererà la chiamata appropriata su sort_linked_list().

Codice sorgente in formato testo:

Una traduzione cinese di questa pagina è disponibile su https://mattressmozz.com/portfolio/llmsort .