Hlavní navigace

GLib: Jednosměrné seznamy

Michal Burda

V dnešní kapitole o knihovně GLib si představíme jednosměrné seznamy. Jelikož jejich podobnost s obousměrnými seznamy je natolik výrazná, že opětovným popisováním funkcí bychom se vlastně nic nového nedověděli, rozhodl jsem se dnešní výklad pojmout trochu jinou formou.

Jednosměrné seznamy jsou těžkou analogií k obousměrným. Základní rozdíl, v čem se tyto dva typy liší, je skutečnost, že jednosměrné seznamy lze procházet jen v jednom směru, tj. nedisponují pointery na „předcházející“ prvky ( prev).

Uzly jednosměrných seznamů jsou definovány strukturou GSList:

struct GSList
{
  gpointer data;
  GSList *next;
};

Jak vidíte, položka prev skutečně chybí.

Drtivá většina skutečností řečených v minulých dílech o obousměrných seznamech (GLib část 12. a GLib část 13.) platí i pro jednosměrné seznamy. GSList y mají sadu funkcí, které jsou takřka shodné s funkcemi pro práci s  GList y ( g_list_...). Každá funkce nebo makro, které má co do činění s jednosměrnými seznamy, začíná „ g_slist_...“.

Následující tabulka shrnuje seznam funkcí pro práci s obousměrnými seznamy a jejich obdob pro manipulaci s jednosměrnými seznamy:

Tabulka č. 78
GSList GList Stručný popis
GSList* g_slist_append(GSList *list, gpointer data); GList* g_list_append(GList *list, gpointer data); Přidání prvku na konec seznamu
GSList* g_slist_prepend(GSList *list, gpointer data); GList* g_list_prepend(GList *list, gpointer data); Přidání prvku na začátek seznamu
GSList* g_slist_insert(GSList *list, gpointer data, gint position); GList* g_list_insert(GList *list, gpointer data, gint position); Přidání prvku na pozici position
GSList* g_slist_insert_sorted(GSList *list, gpointer data, GCompareFunc func); GList* g_list_insert_sorted(GList *list, gpointer data, GCompareFunc func); Vložení prvku tak, aby byl seznam seřazený
GSList* g_slist_remove(GSList *list, gpointer data); GList* g_list_remove(GList *list, gpointer data); Odstranění uzlu ze seznamu s následnou dealokací
GSList* g_slist_remove_link(GSList *list, GSList *llink); GList* g_list_remove_link(GList *list, GList *llink); Odstranění uzlu (prvku) seznamu bez jeho dealokace
void g_slist_free(GSList *list); void g_list_free(GList *list); Uvolnění celého seznamu z paměti
void g_slist_free_1(GSList *list); void g_list_free_1(GList *list); Dealokace uzlu (prvku) seznamu
guint g_slist_length(GSList *list); guint g_list_length(GList *list); Zjištění délky seznamu
GSList* g_slist_copy(GSList *list); GList* g_list_copy(GList *list); Vytvoření kopie seznamu
GSList* g_slist_reverse(GSList *list); GList* g_list_reverse(GList *list); Změna pořadí prvků (první – poslední,…)
GSList* g_slist_sort(GSList *list, GCompareFunc compare_func); GList* g_list_sort(GList *list, GCompareFunc compare_func); Seřazení prvků v seznamu
GSList* g_slist_concat(GSList *list1, GSList *list2); GList* g_list_concat(GList *list1, GList *list2); Spojení dvou seznamů do jednoho
void g_slist_foreach(GSList *list, GFunc func, gpointer user_data); void g_list_foreach(GList *list, GFunc func, gpointer user_data); Provedení funkce func na každou položku seznamu
není k dispozici GList* g_list_first(GList *list); Vrácení prvního prvku seznamu
GSList* g_slist_last(GSList *list); GList* g_list_last(GList *list); Vrácení posledního prvku seznamu
není k dispozici #define g_list_previous(list) Vrácení předcházejícího prvku
#define g_slist_next(slist) #define g_list_next(slist) Vrácení následujícího prvku
GSList* g_slist_nth(GSList *list, guint n); GList* g_list_nth(GList *list, guint n); Vrácení n-tého prvku seznamu
gpointer g_slist_nth_data(GSList *list, guint n); gpointer g_list_nth_data(GList *list, guint n); Vrácení dat n-tého prvku
GSList* g_slist_find(GSList *list, gpointer data); GList* g_list_find(GList *list, gpointer data); Hledání prvku podle dat
GSList* g_slist_find_custom(GSList *list, gpointer data, GCompareFunc func); GList* g_list_find_custom(GList *list, gpointer data, GCompareFunc func); Hledání prvku s plnou kontrolou nad operací porovnávání
gint g_slist_position(GSList *list, GSList *llink); gint g_list_position(GList *list, GList *llink); Vrácení pozice prvku v seznamu
gint g_slist_index(GSList *list, gpointer data); gint g_list_index(GList *list, gpointer data); Vrácení pozice prvku podle dat

Funkce jsou téměř stejné a stejné jsou i jejich vlastnosti. Patrně jste si všimli, že pro jednoduché seznamy neexistuje žádná funkce g_slist_first() či makro g_slist_previous(). Je to logické: jednosměrné seznamy neposkytují pointery na předcházející prvky a proto by jeho nalezení, popřípadě nalezení prvního prvku seznamu bylo jako škrábat se levou nohou za pravým uchem.

Pro jakýkoliv bližší popis funkcí odkazuji čtenáře na dříve uvedené články o obousměrných seznamech, kde jsou všechny funkce dopodrobna vysvětleny. Jejich popis se dá aplikovat i na jednosměrné seznamy.

A použití?

Jednosměrné seznamy, protože ve svých prvcích GSList postrádají jeden pointer, jsou trochu úspornější co do obsazení paměti než obousměrné seznamy. Jejich použitím si však uzavíráte možnost procházení seznamem ve zpětném směru. Je to opět klasický kompromis mezi výkonností a nároky na paměť (hardware).

Příklad:

/* Nalezeni "predchazejiciho prvku"
 * k danemu prvku jednosmerneho seznamu */
#include <glib.h>
/* Funkce, ktera vyhleda v seznamu list
 * predchozi prvek k prvku link */
GSList* my_g_slist_previous(GSList *list, GSList* link)
{
  GSList* l;

  l = list;
  while (l != NULL) {
    if (l->next == link) {
      return l;
    }
    l = l->next;
  }

  return l;
}

gint main(void)
{
  GSList *list = NULL;
  GSList *l1, *l2;

  /* vytvoreni nejakeho jednosmerneho seznamu */
  list = g_slist_append(list, "Josef");
  list = g_slist_append(list, "Karel");
  list = g_slist_append(list, "Tonda");
  list = g_slist_append(list, "Tomas");

  /* ziskani odkazu na "nejaky" prvek seznamu */
  l1 = list->next->next->next;

  /* nalezeni predchazejiciho prvku */
  l2 = my_g_slist_previous(list, l1);

  /* kontrolni tisk */
  printf("Predchazejicim prvkem k prvku %s je %s.\n",
    l1->data, l2->data);

  /* dealokace a konec */
  g_slist_free(list);
  return(0);
}
Našli jste v článku chybu?
Vitalia.cz: Nestlé vyvinulo nový typ „netloustnoucího“ cukru

Nestlé vyvinulo nový typ „netloustnoucího“ cukru

Měšec.cz: Zdravotní a sociální pojištění 2017: Připlatíte

Zdravotní a sociální pojištění 2017: Připlatíte

Podnikatel.cz: Přehledná titulka, průvodci, responzivita

Přehledná titulka, průvodci, responzivita

Měšec.cz: Air Bank zruší TOP3 garanci a zdražuje kurzy

Air Bank zruší TOP3 garanci a zdražuje kurzy

Podnikatel.cz: K EET. Štamgast už peníze na stole nenechá

K EET. Štamgast už peníze na stole nenechá

Podnikatel.cz: Chaos u EET pokračuje. Jsou tu další návrhy

Chaos u EET pokračuje. Jsou tu další návrhy

120na80.cz: Na ucho teplý, nebo studený obklad?

Na ucho teplý, nebo studený obklad?

Vitalia.cz: 9 největších mýtů o mase

9 největších mýtů o mase

Lupa.cz: Propustili je z Avastu, už po nich sahá ESET

Propustili je z Avastu, už po nich sahá ESET

Lupa.cz: Insolvenční řízení kvůli cookies? Vítejte v ČR

Insolvenční řízení kvůli cookies? Vítejte v ČR

120na80.cz: Co všechno ovlivňuje ženskou plodnost?

Co všechno ovlivňuje ženskou plodnost?

Vitalia.cz: Spor o mortadelu: podle Lidlu falšovaná nebyla

Spor o mortadelu: podle Lidlu falšovaná nebyla

Vitalia.cz: Znáte „černý detox“? Ani to nezkoušejte

Znáte „černý detox“? Ani to nezkoušejte

120na80.cz: Pánové, pečujte o svoje přirození a prostatu

Pánové, pečujte o svoje přirození a prostatu

Podnikatel.cz: Snížení DPH na 15 % se netýká všech

Snížení DPH na 15 % se netýká všech

Lupa.cz: Teletext je „internetem hipsterů“

Teletext je „internetem hipsterů“

Lupa.cz: Co se dá měřit přes Internet věcí

Co se dá měřit přes Internet věcí

Vitalia.cz: Taky věříte na pravidlo 5 sekund?

Taky věříte na pravidlo 5 sekund?

Podnikatel.cz: Chtějte údaje k dani z nemovitostí do mailu

Chtějte údaje k dani z nemovitostí do mailu

Vitalia.cz: Paštiky plné masa ho zatím neuživí

Paštiky plné masa ho zatím neuživí