23.2.4. Списки

23.2.4. Списки

Библиотека Glib содержит средства для работы с одно- и двусвязными списками. Особенность двусвязного списка заключается в том, что по нему можно перемещаться в обоих направлениях — назад и вперед. В файле gslist.h (Glib Single List) описаны средства для работы с односвязными списками, а в файле glist.h — для работы с двусвязным списком.

Вот структуры односвязного и двусвязного списков:

// односвязный список

typedef struct _GSList GSList;

struct _GSList {

 gpointer data;

 GSList *next; // указатель на следующий элемент списка

};

// двусвязный список

typedef struct _GList GList;

struct _GList {

 gpointer data;

 GList *next; // указатель на следующий элемент списка

 GList *prev; // указатель на предыдущий элемент списка

};

Поле data предназначено для хранения данных списка, причем они могут быть любого типа, ведь gpointer — это тип void*.

Работать со списками очень просто. Для начала нужно объявить список:

GList *list = NULL;

GSList *slist = NULL;

Затем добавить элементы в список. Это можно сделать с помощью двух функций — g_list_append() или g_slist_prepend() — в зависимости от используемого типа списка:

gchar *el = g_strdup("это первый элемент");

list = g_list_append(list, el);

Функции g_list_append() и g_slist_append() добавляют элемент в конец списка. Если вы хотите добавить элемент в начало списка, нужно использовать функции:

g_list_prepend(GList *list, gpointer data);

g_slist_prepend{GSList *list, gpointer data);

Чтобы вставить новый элемент в определенную позицию, нужно использовать функции:

GList *g_list_insert(GList *list, gpointer data, gint position);

GSList *g_slist_insert(GSList *list, gpointer data, gint position);

Здесь position — это номер элемента, перед которым нужно вставить новый элемент. Если position=0, то элемент будет добавлен в начало списка, то есть перед бывшим первым элементом.

Для удаления элемента используются функции:

GList *g_list_remove(GList *list, gpointer data);

GSList *g_slist_remove(GSList *list, gpointer data);

Для передвижения по списку используются функции:

g_list_next(), g_slist_next() — на "шаг" вперед

g_list_prev() — назад

Вот небольшой пример работы со списком — вывод на консоль всех его элементов:

// double_list должен быть определен и содержать элементы

GList *list = double_list;

while (list!=NULL) {

 printf("%s ",list->data);

 list = g_list_next(list);

}

По окончании работы со списком не забудьте освободить память:

void g_list_free(GList *list);

void g_slist_free(GSList *slist);

Для сортировки списка используется функция:

GSList *g_slist_sort(GSList * slist, GCompareFunc f);

Первый параметр — это список, который нужно отсортировать. Второй — это функция сравнения двух элементов. Вот ее прототип:

typedef gint (*GCompareFunc) (gconstpointer a, gconstpointer b); Данную функцию вы должны написать самостоятельно. Она должна принимать два параметра и возвращать целое значение:

? если a<b, то -1 (точнее, любое число меньше 0);

? если a==b, то 0;

? если a>b, то 1 (любое число больше 0).

Библиотека Glib также содержит средства для работы с деревьями — как бинарными, так и произвольными, но мы эти средства рассматривать не будем.