Razvrsti pomnilnik povezanih seznamov

Original: http://www.efgh.com/software/llmsort.htm

LOGO

Naslov:

Razvrsti pomnilnik povezanih seznamov

Jezik:

C

Avtor:

Philip J. Erdelsky

Datum:

31. julij 1998

Uporaba:

Javna domena; brez omejitev uporabe

Prenosljivost:

Vsak prevajalnik C

Ključne besede:

Povezani seznam, Sortiraj

Povzetek:

Funkcija C za razvrščanje povezanega seznama v pomnilniku z uporabo poljubne primerjalne funkcije in algoritma združevanja traku, ki je v vseh primerih O (n log n). Funkcija je ne-rekurzivna in ponovno vstopa in spreminja le povezave.

Povezani seznami in rutine so zelo pogosti pri programiranju.

Funkcija sort_linked_list () bo razvrstila skoraj vse vrste posamezno povezanih seznamov z uporabo primerjalne funkcije, ki jo ponuja klicni program. Ima naslednje prednosti nad qsort ():

  1. Vrne elemente spremenljive velikosti.
  2. Zahteva O (n log n) primerjave, ne glede na začetni red. Čas za razvrščanje seznama je predvidljiv in dosleden. Ta izvedba je znana kot optimalna za splošne vrste.
  3. Algoritem je iterativen, ne rekurziven, zato ni problema s prelivanjem stackov. Zahtevnost sklada je predvidljiva, dosledna in majhna.
  4. Razvrsti povezani seznam s spreminjanjem kazalcev, ne s premikom elementov samih.
  5. Razvrsti seznam prevelik, da se prilega v matriko.

Funkcija sortira le posamično povezane sezname. Če je seznam dvosmerno povezan, se lahko nazaj usmerjevalci obnovijo po razvrstitvi po nekaj vrsticah kode.

Vsak element povezanega seznama, ki ga je treba razvrstiti, mora vsebovati enega od prvih članov enega ali več kazalcev. Eden od kazalcev, ki mora biti v istem relativnem položaju v vsakem elementu, je kazalec na naslednji element. Ta kazalec je v zadnjem elementu NULL.

Indeks je položaj tega kazalca v vsakem elementu. To je 0 za prvi kazalec, 1 za drugi kazalec itd.

Naj primerjamo () primerjalno funkcijo, ki primerja dva elementa na naslednji način:

n = primerjati (p, q, kazalec);

prazen * p, * q; kazalnike na dva elementa seznama

void * kazalec; Uporabniško določen kazalec je posredoval primerjati () s
linked_list_sort ()

int n; rezultat primerjanja * p in * q
> 0, če je * p treba po * q v razvrščenem vrstnem redu
<0, če je * p pred * q v razvrščenem vrstnem redu
0, če je vrstni red * p in * q nepomemben

Naj bo “prvi” kazalec na prvi element seznama. Potem naslednji klic funkcij razvrsti seznam in vrne kazalec na prvi element na razvrščenem seznamu:

first_sorted =
sort_linked_list (najprej, indeks, primerjava, kazalec, pcount);

Četrti argument (kazalec) je posredovan za primerjavo () brez sprememb. Primer, ki je naveden tukaj, ne uporablja kazalca. Vendar pa je lahko neprecenljiva lastnost, če dve ali več primerjalnih metod delita znatno količino kode in se razlikujejo samo v eni ali več vrednostih parametrov.

Zadnji argument (pcount) je tipa (nepodpisan dolg *). Če ni NULL, je * pcount nastavljen enako številu zapisov na seznamu.

Dovoljen je razvrščanje praznega seznama. Če je prvi == NULL, bo vrnjena vrednost tudi NULL.

Element lahko na primer vsebuje tudi ime in številko:

struct element
{
struct element * next_in_alphabetical_order;
struct element * next_in_numerical_order;
char ime [9];
int število;
/ * drugi člani, če obstaja * /
};

Na začetku sta obe kazalci v vsakem elementu enaki in seznam je v poljubnem vrstnem redu, kjer je “prvi” kazalec na prvi element. Naslednji dve funkcijski klici dvakrat sortirajo seznam:

first_in_alphabetical_order =
sort_linked_list (najprej, 0, primerjati_names, NULL);
first_in_numerical_order =
sort_linked_list (najprej, 1, compare_numbers, NULL);

Tu so primerjalne funkcije:

int compare_names (struct element * p, struct element * q,
void * kazalec)
{
vrnitev strcmp (p-> ime, q-> ime);
}

int compare_numbers (struct element * p, struct element * q,
void * kazalec)
{
vrnitev p-> številka> q-> številka? 1: -1;
/ * OPOMBA: vrnitev p-> številka-q-> zadostuje, če obstaja
nobena nevarnost numeričnega prelivanja * /
}

Tovrstna prejšnja različica, ki je bila objavljena v tehnični reviji, je zahtevala, da je neposredna povezava na začetku vsakega elementa. Čeprav je to nekoliko bolj učinkovito, ga je težko uporabiti tudi z množico povezanih seznamov.

Algoritem je precej preprost. Povezani seznam (imenovan “trak” analogno starim magnetnim trakom) je najprej razdeljen na dva traka iste ali skoraj enake velikosti. To storite z izmenjavo pisalnih elementov na obeh trakovih.

Dve kaseti se nato združita, element po elementu, v razvrščene bloke, ki vsebujejo dva elementa. Bloki so izmenično napisani na dveh drugih trakovih.

Dve kaseti se nato združita, blokirana po blokih, v razvrščene bloke po štirih elementih, vsakokrat pa so bloki zapisani izmenično na dva druga traka.

Postopek se nadaljuje, vsakič pa podvojite velikost bloka, dokler niso vsi elementi v enem samem zapisanem bloku na enem traku. Funkcija vrne kazalec na prvi element tega traku.

Vsako združevanje zahteva primerjave O (n), kjer je n število elementov. Število združitev je O (log n). Zato celotna sorta primerja O (n log n).

Funkcija sort_linked_list () se ponovno vključi, če je funkcija primerjave ponovno vključena.

C aficionados bo z veseljem vedel, da tega algoritma ni mogoče zlahka kodirati v Adi ali Pascalu, ker se opira na tipke.

Funkcijo sort_linked_list () lahko preprosto pokličete iz programa C ++ z modicumom preverjanja tipa, če je vključena datoteka glave LLMSORT.H. Vsebuje predlogo za inline generiranje klica na sort_linked_list (). Oblika klica je naslednja:

#include “llmsort.h”

first_sorted = sort_list (najprej, primerjati, kazalec, pcount);

prvi razred *;
vaš razred * first_sorted;
void * kazalec;
nepodpisan dolg * pcount;

Funkcija primerjati () se imenuje takole:

n = primerjati (p, q, kazalec);
const yourclass * p;
const yourclass * q;
void * kazalec;
int n;

Tukaj je “yourclass” kateri koli razred, ki ga lahko določite. Prevajalnik bo preveril skladnost vrst argumentov in generiral ustrezen klic na sort_linked_list ().

Izvorna koda v besedilnem formatu: