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?