The OpenNET Project / Index page

[ новости /+++ | форум | wiki | теги | ]

Каталог документации / Раздел "Программирование, языки" / Оглавление документа

Doubly-Linked Lists

Doubly-Linked Lists — Связанные списки содержащие целочисленные значения или указатели на данные, с возможностью выполнения итерации по списку в обоих направлениях.

Краткое описание


#include <glib.h>


            GList;

GList*      g_list_append                   (GList *list,
                                             gpointer data);
GList*      g_list_prepend                  (GList *list,
                                             gpointer data);
GList*      g_list_insert                   (GList *list,
                                             gpointer data,
                                             gint position);
GList*      g_list_insert_before            (GList *list,
                                             GList *sibling,
                                             gpointer data);
GList*      g_list_insert_sorted            (GList *list,
                                             gpointer data,
                                             GCompareFunc func);
GList*      g_list_remove                   (GList *list,
                                             gconstpointer data);
GList*      g_list_remove_link              (GList *list,
                                             GList *llink);
GList*      g_list_delete_link              (GList *list,
                                             GList *link_);
GList*      g_list_remove_all               (GList *list,
                                             gconstpointer data);
void        g_list_free                     (GList *list);

GList*      g_list_alloc                    (void);
void        g_list_free_1                   (GList *list);
#define     g_list_free1

guint       g_list_length                   (GList *list);
GList*      g_list_copy                     (GList *list);
GList*      g_list_reverse                  (GList *list);
GList*      g_list_sort                     (GList *list,
                                             GCompareFunc compare_func);
gint        (*GCompareFunc)                 (gconstpointer a,
                                             gconstpointer b);
GList*      g_list_insert_sorted_with_data  (GList *list,
                                             gpointer data,
                                             GCompareDataFunc func,
                                             gpointer user_data);
GList*      g_list_sort_with_data           (GList *list,
                                             GCompareDataFunc compare_func,
                                             gpointer user_data);
gint        (*GCompareDataFunc)             (gconstpointer a,
                                             gconstpointer b,
                                             gpointer user_data);
GList*      g_list_concat                   (GList *list1,
                                             GList *list2);
void        g_list_foreach                  (GList *list,
                                             GFunc func,
                                             gpointer user_data);
void        (*GFunc)                        (gpointer data,
                                             gpointer user_data);

GList*      g_list_first                    (GList *list);
GList*      g_list_last                     (GList *list);
#define     g_list_previous                 (list)
#define     g_list_next                     (list)
GList*      g_list_nth                      (GList *list,
                                             guint n);
gpointer    g_list_nth_data                 (GList *list,
                                             guint n);
GList*      g_list_nth_prev                 (GList *list,
                                             guint n);

GList*      g_list_find                     (GList *list,
                                             gconstpointer data);
GList*      g_list_find_custom              (GList *list,
                                             gconstpointer data,
                                             GCompareFunc func);
gint        g_list_position                 (GList *list,
                                             GList *llink);
gint        g_list_index                    (GList *list,
                                             gconstpointer data);

void        g_list_push_allocator           (gpointer allocator);
void        g_list_pop_allocator            (void);

Описание

Структура GList и связанные с ней функции обеспечивают стандартный двусвязный список структур данных.

Каждый элемент в списке содержит часть данных, вместе с указателями которые связаны с предыдущим и следующим элементом списка. Использование этих указателей позволяет элементам перемещаться через список в обоих направлениях (в отличие от односвязных списков, которые позволяют перемещение по списку только вперёд).

Данные содержащиеся в каждом элементе могут быть либо целочисленными значениями, при использовании одного из Type Conversion Macros, либо простыми указателями на любой тип данных.

Список элементов распределяется с помощью slice allocator, что более эффективно чем индивидуальное распределение элементов.

Помите что большинство функций GList предполагают помещение указателя на первый элемент в списке. Функции которые вставляют элементы, возвращают новое начало списка, которое может быть изменено.

Нет функции для создания GList. NULL рассматривается как пустой список, поэтому вы можете просто установить GList* в значение NULL.

Для добавления элементов используйте g_list_append(), g_list_prepend(), g_list_insert() и g_list_insert_sorted().

Для удаления элементов используйте g_list_remove().

Для поиска элементов в списке используйте g_list_first(), g_list_last(), g_list_next(), g_list_previous(), g_list_nth(), g_list_nth_data(), g_list_find() и g_list_find_custom().

Для поиска номера элемента используйте g_list_position() и g_list_index().

Для вызова функции для каждого элемента в списке используйте g_list_foreach().

Для освобождения полей списка используйте g_list_free().

Детали

GList

typedef struct {
  gpointer data;
  GList *next;
  GList *prev;
} GList;

Структура GList используется для каждого элемента двусвязного списка.

gpointer data; содержит элементы данных, которые могут быть указателем на любой вид данных, или любым целочисленным значением используя Type Conversion Macros.
GList *next; содержит ссылку на следующий элемент в списке.
GList *prev; содержит ссылку на предыдущий элемент в списке.

g_list_append ()

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

Добавляет новый элемент в конец списка.

Примечание

Возвращаемое значение является новым началом списка, которое может быть изменено, поэтому убедитесь что вы сохранили новое значение.

Примечание

Помните что g_list_append() должен пересечь все поля списка для нахождения конца, это не эффективно при добавлении множества элементов. Основная идиома в исключении неэффективности в том, чтобы приставлять элементы а затем перевернуть список, когда все элементы будут добавлены.

  /* Помните что это инициализирует пустой список. */
  GList *list = NULL, *number_list = NULL;

  /* Это список строк. */
  list = g_list_append (list, "first");
  list = g_list_append (list, "second");

  /* Это список целочисленных. */
  number_list = g_list_append (number_list, GINT_TO_POINTER (27));
  number_list = g_list_append (number_list, GINT_TO_POINTER (14));
list : указатель на GList.
data : данные для нового элемента.
Возвращает : новое начало GList.

g_list_prepend ()

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

Добавляет новый элемент в начало списка.

Примечание

Возвращаемое значение является новым началом списка, которое может изменится, поэтому убедитесь что вы сохранили новое значение.

  /* Помните что это инициализирует пустой список. */
  GList *list = NULL;
  list = g_list_prepend (list, "last");
  list = g_list_prepend (list, "first");
list : указатель на GList.
data : данные для нового элемента.
Возвращает : новое начало GList.

g_list_insert ()

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

Вставляет новый элемент в список в полученную позицию.

list : указатель на GList.
data : данные для нового элемента.
position : позиция для вставки элемента. Если отрицательное, или меньше чем количество элементов в списке, новый элемент добавляется в конец списка.
Возвращает : новое начало GList.

g_list_insert_before ()

GList*      g_list_insert_before            (GList *list,
                                             GList *sibling,
                                             gpointer data);

Вставляет новый элемент в список перед полученной позицией.

list : указатель на GList.
sibling : номер элемента перед которым вставляется новый элемент,или NULL для вставки в конец списка.
data : данные для нового элемента.
Возвращает : новое начало GList.

g_list_insert_sorted ()

GList*      g_list_insert_sorted            (GList *list,
                                             gpointer data,
                                             GCompareFunc func);

Вставляет новый элемент в список, использует полученную функцию сравнения для определения позиции.

list : указатель на GList.
data : данные для нового элемента.
func : функция для сравнения элементов в списке. Она должна возвращать число > 0 если первый параметр расположен после второго в порядке сортировки.
Возвращает : новое начало GList.

g_list_remove ()

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

Удаляет элемент из GList. Если два элемента содержат одинаковые данные, удаляется только первый. Если нет элементов содержащих данные, GList не изменяется.

list : GList.
data : данные удаляемого элемента.
Возвращает : новое начало GList.

g_list_remove_link ()

GList*      g_list_remove_link              (GList *list,
                                             GList *llink);

Удаляет элемент из GList, без освобождения элемента. У удалённого элемента ссылки на предыдущий и следующий устанавливаются в NULL, так чтобы он стал списком с единственным элементом.

list : GList.
llink : элемент в GList.
Возвращает : новое начало GList, без элемента.

g_list_delete_link ()

GList*      g_list_delete_link              (GList *list,
                                             GList *link_);

Удаляет узел link_ из list.

list : GList.
link_ : узел для удаления из list.
Возвращает : новый первый элемент list.

g_list_remove_all ()

GList*      g_list_remove_all               (GList *list,
                                             gconstpointer data);

Удаляет все узлы списка с данными равными data. Возвращает новый первый элемент списка. В отличие от g_list_remove(), которая удаляет только первый узел соответствующий полученным данным.

list : GList.
data : удаляемые данные.
Возвращает : новый первый элемент list.

g_list_free ()

void        g_list_free                     (GList *list);

Освобождает всю память используемую GList. Освобождает элементы возвращаемые распределителем слайсов.

Примечание

Если первый элемент содержит динамически-распределённую память, он должен быть освобождён первым.

list : GList.

g_list_alloc ()

GList*      g_list_alloc                    (void);

Распределяет пространство для одного элемента GList. Она вызывается с помощью g_list_append(), g_list_prepend(), g_list_insert() и g_list_insert_sorted() и очень редко используется самостоятельно.

Возвращает : указатель для вновь распределённого элемента GList.

g_list_free_1 ()

void        g_list_free_1                   (GList *list);

Освобождает один элемент GList. Она в основном используется после g_list_remove_link().

list : элемент GList.

g_list_free1

#define     g_list_free1

Другое имя для g_list_free_1().


g_list_length ()

guint       g_list_length                   (GList *list);

Определяет количество элементов в GList.

list : GList.
Возвращает : количество элементов в GList.

g_list_copy ()

GList*      g_list_copy                     (GList *list);

Копирует GList.

Помните что это "пустая" копия. Если список элементов содержит указатели на данные, указатели копируются, а реальные данные нет.

list : GList.
Возвращает : копия list.

g_list_reverse ()

GList*      g_list_reverse                  (GList *list);

Переворачивает GList. Она просто переключает предыдущие и следующие указатели в каждом элементе.

list : GList.
Возвращает : начало перевернутой GList.

g_list_sort ()

GList*      g_list_sort                     (GList *list,
                                             GCompareFunc compare_func);

Сортирует GList используя полученную функцию для сравнения.

list : GList.
compare_func : функция сравнения используемая для сортировки GList. Функция принимает данные из двух элементов GList и должна вернуть 0 если они равны, отрицательное значение если первый элемент помещается перед вторым, или положительное значение если первый элемент помещается после второго.
Возвращает : начало отсортированной GList.

GCompareFunc ()

gint        (*GCompareFunc)                 (gconstpointer a,
                                             gconstpointer b);

Определяет тип сравнивающей функции используемой для сравнения двух значений. Функция должна возвращать отрицательное целочисленное если первое значение расположено перед вторым, 0 если они равны, или положительное целочисленное если первое значение расположено после второго.

a : первое значение.
b : значение для сравнения.
Возвращает : отрицательное значение если a < b; ноль если a = b; положительное значение если a > b.

g_list_insert_sorted_with_data ()

GList*      g_list_insert_sorted_with_data  (GList *list,
                                             gpointer data,
                                             GCompareDataFunc func,
                                             gpointer user_data);

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

list : указатель на GList.
data : данные для нового элемента.
func : функция для сравнения элементов всписке. Она должна вернуть число > 0 если первый параметр расположен после второго параметра в порядке сортировки.
user_data : данные помещаемые в функцию сравнения.
Возвращает : новое начало GList. Начиная с версии 2.10

g_list_sort_with_data ()

GList*      g_list_sort_with_data           (GList *list,
                                             GCompareDataFunc compare_func,
                                             gpointer user_data);

Похожа на g_list_sort(), но функция сравнения принимает параметр пользовательских данных.

list : GList.
compare_func : функция сравнения.
user_data : пользовательские данные помещаемые в функцию сравнения.
Возвращает : новый первый элемент list.

GCompareDataFunc ()

gint        (*GCompareDataFunc)             (gconstpointer a,
                                             gconstpointer b,
                                             gpointer user_data);

Определяет тип функции сравнения используемой для сравнения двух значений. Функция должна возвращать отрицательное целочисленное если первое значение располагается перед вторым, 0 если они равны, или положительное целочисленное если первое значение располагается после второго.

a : первое значение.
b : значение для сравнения.
user_data : данные помещаемые в функцию сравнения.
Возвращает : отрицательное значение если a < b; ноль если a = b; положительное значение если a > b.

g_list_concat ()

GList*      g_list_concat                   (GList *list1,
                                             GList *list2);

Добавляет второй GList в конец первого GList. Помните что элементы второго GList не копируются. Они используются на прямую.

list1 : GList.
list2 : GList добавляемый в конец первого GList.
Возвращает : начало нового GList.

g_list_foreach ()

void        g_list_foreach                  (GList *list,
                                             GFunc func,
                                             gpointer user_data);

Вызывает функцию для каждого элемента GList.

list : GList.
func : функция вызываемая для каждого элемента данных.
user_data : данные помещаемые в функцию.

GFunc ()

void        (*GFunc)                        (gpointer data,
                                             gpointer user_data);

Определяет тип функции помещаемой в g_list_foreach() и g_slist_foreach().

data : элементы данных.
user_data : данные помещаемые в g_list_foreach() или g_slist_foreach().

g_list_first ()

GList*      g_list_first                    (GList *list);

Выдаёт первый элемент в GList.

list : GList.
Возвращает : первый элемент в GList, или NULL если GList не имеет элементов.

g_list_last ()

GList*      g_list_last                     (GList *list);

Выдаёт последний элемент в GList.

list : GList.
Возвращает : последний элемент в GList, или NULL если GList не имеет элементов.

g_list_previous()

#define     g_list_previous(list)

Удобный макрос для получения предыдущего элемента в GList.

list : элемент в GList.
Возвращает : предыдущий элемент, или NULL если нет предыдущих элементов.

g_list_next()

#define     g_list_next(list)

Удобный макрос для получения следующего элемента в GList.

list : элемент в GList.
Возвращает : следующий элемент, или NULL если нет больше элементов.

g_list_nth ()

GList*      g_list_nth                      (GList *list,
                                             guint n);

Определяет элемент в данной позиции GList.

list : GList.
n : позиция элемента, подсчёт с 0.
Возвращает : элемент, или NULL если позиция выходит за пределы GList.

g_list_nth_data ()

gpointer    g_list_nth_data                 (GList *list,
                                             guint n);

Определяет данные элемента в указанной позиции.

list : GList.
n : позиция элемента.
Возвращает : данные элемента, или NULL если позиция выходит за пределы GList.

g_list_nth_prev ()

GList*      g_list_nth_prev                 (GList *list,
                                             guint n);

Определяет элемент n помещаемый перед list.

list : GList.
n : позиция элемента, подсчёт с 0.
Возвращает : элемент, или NULL если позиция выходит за пределы GList.

g_list_find ()

GList*      g_list_find                     (GList *list,
                                             gconstpointer data);

Находит элемент в GList который содержит полученные данные.

list : GList.
data : данные элемента для поиска.
Возвращает : найденный элемент GList, или NULL если он не найден.

g_list_find_custom ()

GList*      g_list_find_custom              (GList *list,
                                             gconstpointer data,
                                             GCompareFunc func);

Ищет элемент в GList, используя предоставленную функцию для поиска желаемого элемента. Она перемещается по списку, вызывая полученную функцию которая должна вернуть 0 когда желаемый элемент найден. Функция принимает два аргумента gconstpointer, элемент данных GList как первый аргумент и полученные пользовательские данные.

list : GList.
data : пользовательские данные помещаемые в функцию.
func : функция вызываемая для каждого элемента. Она должна вернуть 0 когда желаемый элемент найден.
Возвращает : искомый элемент GList, или NULL если он не найден.

g_list_position ()

gint        g_list_position                 (GList *list,
                                             GList *llink);

Определяет позицию полученного элемента в GList (начиная с 0).

list : GList.
llink : элемент в GList.
Возвращает : позиция элемента в GList, или -1 если элемент не найден.

g_list_index ()

gint        g_list_index                    (GList *list,
                                             gconstpointer data);

Определяет позицию элемента содержащего полученные данные (начиная с 0).

list : GList.
data : искомые данные.
Возвращает : перечень элементов содержащих данные, или -1 если данные не найдены.

g_list_push_allocator ()

void        g_list_push_allocator           (gpointer allocator);

Внимание

g_list_push_allocator устарела начиная с версии 2.10 и не должна использоваться во вновь создаваемом коде. Она ничего не делает, так как GList был конвертирован в slice allocator

Заставляет использовать распределитель для распределения элементов GList. Использует g_list_pop_allocator() для восстановления предыдущего распределения.

Помните что эта функция не доступна если GLib скомпилирована с опцией --disable-mem-pools

allocator : GAllocator используемый для распределения элементов GList.

g_list_pop_allocator ()

void        g_list_pop_allocator            (void);

Внимание

g_list_pop_allocator устарела начиная с версии 2.10 и не должна использоваться во вновь создаваемом коде. Она ничего не делает, так как GList был конвертирован в slice allocator

Восстанавливает предыдущий GAllocator, используемый для распределения элементов GList.

Помните что эта функция недоступна если GLib скомпилирована с опцией --disable-mem-pools




Спонсоры:
Inferno Solutions
Hosting by Hoster.ru
Хостинг:

Закладки на сайте
Проследить за страницей
Created 1996-2021 by Maxim Chirkov
Добавить, Поддержать, Вебмастеру