二、GLib——GSList
1 单链接基本概念
1.1 单链表是什么
单链表是一种常见的数据结构，它由一个个节点组成，每个节点包含一个数据元素和一个指向下一个节点的指针
1.2 单链表需要实现那些基本功能
基本的操作为：增、删、查、改
具体为：
-
插入元素：将新元素插入到链表的指定位置，可以是链表的头部、尾部或中间位置。
-
删除元素：从链表中删除指定位置的元素。
-
查找元素：根据给定的值，在链表中查找对应的元素，并返回其位置。
-
遍历链表：按顺序访问链表中的每个元素。
-
获取链表长度：获取链表中元素的个数。
-
判断链表是否为空：判断链表是否为空链表。
-
清空链表：删除链表中的所有元素，使其成为一个空链表。
2 Glib实现单链表
-
GSList没有在类型系统注册对象，也就是没有G_SLIST，没有引用计数。 -
没有new和unref函数，而是
g_slist_append创建链接节点，g_slist_free释放节点内存空间。 -
GSList不是多线程安全的。
2.1 单链表结构体
typedef struct _GSList GSList;
struct _GSList
{
gpointer data;
GSList *next;
};
2.2 单链表节点插入
2.2.1 链表末尾插入元素
/**
* @brief: 该函数会遍历链表到末尾，插入元素，最后返回值等于变量@list给定的单链表。
* @param list: 如果 list 赋值为 NULL，创建的是头节点。
* @param data: 链表的数据
* @return: 如果 @list == NULL，返回创建的头节点，否则返回 @list
*
* @note: 这个@list不一定是一个单链表的开头，可以是中间某个元素，如果@list是中间某个元素，则返回值也是中间某个元素。
*/
GSList* g_slist_append (GSList *list,
gpointer data);
2.2.2 向前插入元素
/**
* @brief: list之前如果有数据，会替换掉该数据，返回list之前的指针。（返回头节点）
*/
GSList* g_slist_prepend (GSList *list,
gpointer data);
2.2.3 指定节点之前插入元素
GSList* g_slist_insert_before (GSList *slist,
GSList *sibling,
gpointer data)
- slist：一个链表
- sibling：在那个节点之前要插入数据
- data：数据
- Returns：返回一个新的头指针
- Note：如果slist = NULL，sibling = NULL，就会创建一个新的单链表。
2.2.4 指定位置插入元素
GSList* g_slist_insert (GSList *list,
gpointer data,
gint position)
- 如果position大于链表或者是负数，就在链表末尾插入数据。
2.2.5 根据排序函数插入元素
GSList* g_slist_insert_sorted (GSList *list,
gpointer data,
GCompareFunc func)
根据排序插入的问题：
/**
* @brief: 如果原先的链表没有按顺序排列，最新按排序插入的节点，会在第一个符合该节点的位置插入
*
* 比如现在原先的顺序是 16 13，所以现在 14 < 16 就直接插入到最前面了，他再遍历后面的
*/
static void
test_slist_7 () {
GSList *list = g_slist_append (NULL, GINT_TO_POINTER(16));
g_print ("list = %p\n", list);
list = g_slist_append (list, GINT_TO_POINTER(13));
g_print ("list = %p\n", list); /* 返回的是头节点 */
list = g_slist_insert_sorted (list, GINT_TO_POINTER(14), sort_r);
g_slist_foreach(list, print, NULL);
g_slist_free (list);
}
/* 打印输出是： 14, 16, 13 */
2.3 单链表内存释放
/**
* @brief: 释放整个链表的内存（因为插入元素的时候会再堆上申请节点所需内存）
*/
void g_slist_free (GSList *list);
/**
* @brief: 释放整个链表内存前，先遍历整个链表，对每个节点调用 @free_func 函数
*/
void
g_slist_free_full (GSList *list,
GDestroyNotify free_func)
2.4 单链表查找
2.4.1 根据位置查找链表节点地址
GSList* g_slist_nth (GSList *list,
guint n);
- list：一个单链表
- n：这个单链接的第n个位置
- Note：值得注意的是，第n个位置，是从输入参数list数起，不是单链表的头结点数起。如果数到结尾，则返回NULL。
2.4.2 根据data查找链表节点位置
gint g_slist_index (GSList *list,
gconstpointer data);
2.4.3 根据用户提供func和data查询节点
GSList* g_slist_find_custom (GSList *list,
gconstpointer data,
GCompareFunc func);
typedef gint (*GCompareFunc) (gconstpointer a,
gconstpointer b);
- a：链表的list->data
- b：参数2的data
- fun return：如果返回0，就把该节点作为g_slist_find_custom返回值。
2.4.4 根据节点查询位置
gint g_slist_position (GSList *list,
GSList *llink);
2.5 反转链表
GSList* g_slist_reverse (GSList *list)
- Note：从给定的list开始到末尾NULL，开始翻转。
2.6 单链表复制
/**
* @brief: 这是浅拷贝，只会把data地址赋值给新拷贝的 list->data
*/
GSList* g_slist_copy (GSList *list);
2.7 通过比较data删除节点
/*删除所有相同data节点*/
GSList* g_slist_remove_all (GSList *list,
gconstpointer data);
/*如果有n个相同data的，则删除第一个相同节点*/
GSList* g_slist_remove (GSList *list,
gconstpointer data)
2.8 排序
GSList* g_slist_sort (GSList *list,
GCompareFunc compare_func);
typedef gint (*GCompareFunc) (gconstpointer a,
gconstpointer b);
根据compare_func返回值进行排序，如果返回值等于0，a和b的值相等。如果a大于b，则返回负数/负数，反则正数/负数。
GSList* g_slist_sort_with_data (GSList *list,
GCompareDataFunc compare_func,
gpointer user_data)
2.9 遍历链表data
void g_slist_foreach (GSList *list,
GFunc func,
gpointer user_data);
typedef void (*GFunc) (gpointer data,
gpointer user_data);
2.10 链表拼接
GSList* g_slist_concat (GSList *list1,
GSList *list2)