![\"\"](\"https:\/\/www.coupontoaster.com\/blog\/wp-content\/uploads\/2021\/09\/sitelogo-1.gif\")
<\/figure>\n<\/div>\n\n\nTitolo:Ordinamento della memoria di elenchi collegatiLingua:CAutore:Philip J. Erdelsky<\/p>\n\n\n\n
- pje@efgh.com<\/a><\/li>
- www.efgh.com<\/a><\/li><\/ul>\n\n\n\n
Data:31 luglio 1998Utilizzo:Dominio pubblico; nessuna restrizione d’usoPortabilit\u00e0: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 \u00e8 O(n log n) in tutti i casi. La funzione \u00e8 non ricorsiva e rientrante e modifica solo i collegamenti.<\/p>\n\n\n\n
Gli elenchi collegati e le routine di ordinamento sono molto comuni nella programmazione.<\/p>\n\n\n\n
La funzione sort_linked_list() ordiner\u00e0 virtualmente qualsiasi tipo di elenco con collegamento singolo, utilizzando una funzione di confronto fornita dal programma chiamante. Presenta i seguenti vantaggi rispetto a qsort():<\/p>\n\n\n\n
- Ordina elementi di dimensione variabile.<\/li>
- Richiede O(n log n) confronti, indipendentemente dall’ordine iniziale. Il tempo per ordinare un elenco \u00e8 prevedibile e coerente. Questa prestazione \u00e8 nota per essere ottimale per gli ordinamenti generali.<\/li>
- L’algoritmo \u00e8 iterativo, non ricorsivo, quindi non ci sono problemi di stack overflow. Il requisito dello stack \u00e8 prevedibile, coerente e ridotto.<\/li>
- Ordina l’elenco collegato modificando i puntatori, non spostando gli elementi stessi.<\/li>
- Pu\u00f2 ordinare un elenco troppo grande per essere inserito in un array.<\/li><\/ol>\n\n\n\n
La funzione ordina solo elenchi collegati singolarmente. Se una lista \u00e8 doppiamente collegata, i puntatori all’indietro possono essere ripristinati dopo l’ordinamento di poche righe di codice.<\/p>\n\n\n\n
Ogni elemento di una lista collegata da ordinare deve contenere, come primi membri, uno o pi\u00f9 puntatori. Uno dei puntatori, che deve trovarsi nella stessa posizione relativa in ogni elemento, \u00e8 un puntatore all’elemento successivo. Questo puntatore \u00e8 NULL nell’ultimo elemento.<\/p>\n\n\n\n
L’indice \u00e8 la posizione di questo puntatore in ogni elemento. \u00c8 0 per il primo puntatore, 1 per il secondo puntatore, ecc.<\/p>\n\n\n\n
Sia compare() una funzione di confronto che confronta due elementi come segue:<\/p>\n\n\n\n
n = confronta(p, q, puntatore); \n\n vuoto *p, *q; puntatori a due elementi della lista \n\n void *pointer; puntatore definito dall'utente passato a compare() da \n linked_list_sort() \n\n int n; risultato del confronto di *p e *q \n >0 se *p deve essere dopo *q in ordine \n <0 se *p deve essere prima di *q in ordine \n 0 se l'ordine di *p e *q \u00e8 irrilevante\n<\/pre>\n\n\n\n
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:<\/p>\n\n\n\n
first_sorted = \n sort_linked_list(first, index, compare, pointer, pcount);\n<\/pre>\n\n\n\n
Il quarto argomento (puntatore) viene passato a compare() senza modifiche. L’esempio qui fornito non fa uso del puntatore. Tuttavia, pu\u00f2 essere una caratteristica preziosa se due o pi\u00f9 metodi di confronto condividono una notevole quantit\u00e0 di codice e differiscono solo per uno o pi\u00f9 valori dei parametri.<\/p>\n\n\n\n
L’ultimo argomento (pcount) \u00e8 di tipo (unsigned long *). Se non \u00e8 NULL, allora *pcount \u00e8 uguale al numero di record nell’elenco.<\/p>\n\n\n\n
\u00c8 consentito ordinare un elenco vuoto. Se prima == NULL, anche il valore restituito sar\u00e0 NULL.<\/p>\n\n\n\n
Ad esempio, un elemento pu\u00f2 contenere sia un nome che un numero:<\/p>\n\n\n\n
struct element \n { \n struct element *next_in_alphabetical_order; \n elemento struttura *next_in_numerical_order; \n nome del carattere[9]; \n numero int; \n \/* altri membri, se presenti *\/ \n };\n<\/pre>\n\n\n\nInizialmente, i due puntatori in ogni elemento sono identici e l’elenco \u00e8 in ordine arbitrario, dove “first” \u00e8 un puntatore al primo elemento. Le seguenti due chiamate di funzione ordinano l’elenco due volte:<\/p>\n\n\n\n
first_in_alphabetical_order = \n sort_linked_list(first, 0, compare_names, NULL); \n first_in_numerical_order = \n sort_linked_list(first, 1, compare_numbers, NULL);\n<\/pre>\n\n\n\n
Ecco le funzioni di confronto:<\/p>\n\n\n\n
int compare_names(struct element *p, struct element *q, \n void *pointer) \n { \n return strcmp(p->name, q->name); \n } \n\n int compare_numbers(struct element *p, struct element *q, \n void *pointer) \n { \n return p->number > q->number ? 1 : -1; \n \/* NOTA: return p->number - q->number sar\u00e0 sufficiente se non \n c'\u00e8 pericolo di overflow numerico *\/ \n }\n<\/pre>\n\n\n\nUna versione precedente di questo tipo, pubblicata su una rivista tecnica, richiedeva che il collegamento in avanti fosse all’inizio di ogni elemento. Sebbene ci\u00f2 rendesse l’ordinamento un po’ pi\u00f9 efficiente, ne rendeva anche difficile l’uso con pi\u00f9 elenchi collegati.<\/p>\n\n\n\n
L’algoritmo \u00e8 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.<\/p>\n\n\n\n
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.<\/p>\n\n\n\n
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.<\/p>\n\n\n\n
Il processo continua, raddoppiando ogni volta la dimensione del blocco, finch\u00e9 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.<\/p>\n\n\n\n
Ogni unione richiede O(n) confronti, dove n \u00e8 il numero di elementi. Il numero di unioni \u00e8 O(log n). Quindi l’intero ordinamento richiede O(n log n) confronti.<\/p>\n\n\n\n
La funzione sort_linked_list() \u00e8 rientrante se la funzione di confronto \u00e8 rientrante.<\/p>\n\n\n\n
Gli appassionati saranno felici di sapere che questo algoritmo non pu\u00f2 essere codificato facilmente in Ada o Pascal perch\u00e9 si basa su typecast.<\/p>\n\n\n\n
La funzione sort_linked_list() pu\u00f2 essere chiamata facilmente da un programma C++ con un minimo di controllo del tipo se \u00e8 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 \u00e8 il seguente:<\/p>\n\n\n\n
#include \"llmsort.h\" \n\n first_sorted = sort_list(first, compare, pointer, pcount); \n\n la tua classe *prima; \n la tua classe *first_sorted; \n void *puntatore; \n unsigned long *pcount;\n<\/pre>\n\n\n\n
La funzione compare() viene chiamata come segue:<\/p>\n\n\n\n
n = confronta(p, q, puntatore); \n const la tua classe *p; \n const la tua classe *q; \n void *puntatore; \n int n;\n<\/pre>\n\n\n\n
Qui “yourclass” \u00e8 qualsiasi classe che puoi definire. Il compilatore verificher\u00e0 la coerenza dei tipi di argomento e generer\u00e0 la chiamata appropriata su sort_linked_list().<\/p>\n\n\n\n
Codice sorgente in formato testo:<\/p>\n\n\n\n
- www.efgh.com<\/a><\/li><\/ul>\n\n\n\n