Hlavní navigace

GLib: Mnohonásobné stromy

11. 9. 2000
Doba čtení: 4 minuty

Sdílet

Budete-li někdy potřebovat obecný datový typ strom s tím, aby s ním šlo vytvářet jakkoliv košaté stromy, vzpomeňte si na knihovnu GLib a její mnohonásobné stromy.

Máte-li pochybnosti o tom, co si v programátorské praxi představit pod pojmem „strom“, přečtěte si nejprve předcházející kapitolu tohoto seriálu nazvanou Binární stromy.

Jestliže (nám už dobře známé) binární stromy byly spíše jednoúčelové a sloužily k rychlému vyhledávání dat, mnohonásobné stromy implementují obecný datový typ „strom“ se vším, co k tomu patří. Proto také mají rozhodně širší použití.

Typ mnohonásobný strom (N-ary tree) je vystavěn kolem struktury GNode velkým množstvím funkcí. Samotný datový záznam GNode reprezentuje jeden prvek (uzel) stromu.

struct GNode
{
  gpointer data;
  GNode   *next;
  GNode   *prev;
  GNode   *parent;
  GNode   *children;
};

Pointer data je obecný ukazatel na data, která chcete ve stromu shromažďovat. Položky next a prev jsou pointery na následujícího a předcházejícího sourozence daného uzlu. (Sourozencem chápejte všechny uzly, které mají stejného rodiče). Položka parent pak je pointer na rodiče uzlu nebo NULL, pokud daný GNode je kořenem stromu. Položka children ukazuje na prvního potomka uzlu. Ostatní potomci jsou dosahováni použitím pointerů nextprev.

Na strom tedy můžeme pohlížet jako na jakýsi vícerozměrný či vnořený seznam. V jednom směru jsou prvky zřetězeny dvojicemi parent a children a ve druhých směrech pak pointery next a prev (viz obrázek).

Ukázka stromu a jeho realizace v paměti prostřednictvím uzlů GNode

Obrázek 1 – Ukázka stromu a jeho realizace v paměti prostřednictvím uzlů GNode (kde chybí ukazatel, např. uzlu 6 chybí next, prev i children, znamená to, že je stejně NULLový)

Příklad:

Tak například, máme-li v paměti strom jako na obrázku 1, uchováváme pouze pointer root na kořen (uzel 4) a chceme získat adresu uzlu 2, napíšeme něco jako:

root->children 

Kdybychom chtěli adresu uzlu 5, napíšeme:

root->children->next 

a pro uzel 6 stačí použít kód:

root->children->next->children 

Nové uzly stokrát jinak

GNode* g_node_new(gpointer data); 

…vytvoří nový uzel GNode, který bude uchovávat zadaná data. Funkce se obvykle používá k vytvoření kořene stromu. Vrácená hodnota je pointer na nově alokovanou strukturu  GNode.

Vkládání již vytvořených uzlů do stromu

Funkce, které budou následovat, slouží k připojení již vytvořeného uzlu na nějaké místo existujícího stromu. Vkládaný uzel může být i kořenem dalšího stromu. Smíte tedy vkládat jednotlivé uzly i spojovat dva stromy dohromady. Návratovou hodnotou je vždy vkládaný uzel.

GNode* g_node_insert(GNode *parent, gint position, GNode *node); 

…do daného stromu vloží GNode node jako position-tého potomka uzlu parent. Je-li position větší nebo rovno nule, node se vloží jako position-tý potomek uzlu parent (ostatní sourozenci se posunou). Index sourozenců začíná on nuly, takže první potomek odpovídá indexu 0, druhý 1 apod. Chcete-li tedy, aby node byl do seznamu potomků uložen na první pozici, zvolte position rovno 0. Je-li position menší než nula, uzel node se vloží na konec seznamu potomků.

GNode* g_node_insert_before(GNode *parent, GNode *sibling, GNode *node); 

…do stromu přidá GNode node jako potomka uzlu parent tak, aby se v seznamu potomků nacházel před sourozencem sibling. Je-li sibling roven NULL, node se vloží jako poslední potomek uzlu parent.

#define g_node_append(parent, node) 

…makro pro přidání uzlu node na pozici posledního potomka uzlu parent.

A konečně, funkce

GNode* g_node_prepend(GNode *parent, GNode *node); 

…přidá uzel node na pozici prvního potomka uzlu parent.

Vytvoření nového uzlu a jeho vložení do stromu

Každý programátor je od nátury lenoch a tvůrci knihovny GLib to dobře vědí. Proto pro náš komfort připravili následující čtveřici maker:

#define g_node_insert_data(parent, position, data)
#define g_node_insert_data_before(parent, sibling, data)
#define g_node_append_data(parent, data)
#define g_node_prepend_data(parent, data) 

Tyto makra (světe div se), dělají skoro přesně totéž, co funkce podobného jména, které jsem popsal výše. Jediné, co vykonají navíc, je, že vkládaný uzel nově alokují funkcí g_node_new() a uloží do něj data. Vrácená hodnota makra je pointer na nový uzel.

Tedy, g_node_insert_data() vloží nový uzel s daty data jako position-tého potomka uzlu parent, g_node_insert_data_before() jej vloží na pozici před sourozence sibling, g_node_append_da­ta() na konec a g_node_prepend_data() na začátek seznamu potomků uzlu parent.

Příklad:

Stejného účinku jako volání makra

g_node_append_data(nejaky_uzel, nejaka_data); 

byste dosáhli napsáním

g_node_append(nejaky_uzel, g_node_new(nejaka_data)); 

nebo

g_node_insert_before(nejaky_uzel, NULL, g_node_new(nejaka_data)); 

do čehož se makro g_node_append_da­ta() ve skutečnosti rozvine.

Rozdělování stromů

void g_node_unlink(GNode *node); 

Tato funkce rozdělí strom, jehož součástí je i uzel node, na dva stromy tak, že kořenem nového stromu bude právě uzel node.

Uvolnění stromu z paměti

Jako obvykle, na tomto místě nás čeká klasická funkce na uvolnění datové struktury z paměti.

UX DAy - tip 2

void g_node_destroy(GNode *root); 

…uvolní z paměti uzel root a všechny jeho následovníky. Není-li root kořenem stromu, dojde nejprve k odpojení podstromu voláním g_node_unlink(root) a následné dealokaci tohoto nového stromu. Uchovává-li strom nějaká dynamicky alokovaná data, musíte sami dealokovat nejprve je.

Pokračování příště.

Byl pro vás článek přínosný?

Autor článku

Michal Burda vystudoval informatiku a aplikovanou matematiku a nyní pracuje na Ostravské univerzitě jako odborný asistent. Zajímá se o data mining, Javu a Linux.