glib库单向链表介绍
glib库里实现了一些基本的数据结构，比如单向链表，双向链表、队列、树、hash表和数组。这篇文章里我主要介绍在linux平台下使用glib库中的单向链表进行编程，以后的文章我会陆续介绍双向链表、队列和其它数据结构的用法。
单向链表（即GSList）是glib库里最简单的容具，它把一系列的节点链接在一起，可以从一个节点访问到下一个节点。glib库里对GSList结构的定义如下：
struct GSList
{
gpointer data;
GSList *next;
} ;
data成员定义为gpointer（即void*），可以放任何类型的数据。下面举个例子来说明怎么使用GSList来创建、添加、插入、排序、反转和销毁单向链表。
#include < glib.h >
void display_list(GSList * list)
{
GSList * iterator = NULL;
for (iterator = list; iterator; iterator = iterator -> next) {
printf( " %s " , ( char * )iterator -> data);
}
printf( " /n " );
}
int my_str_cmp(gconstpointer str1, gconstpointer str2)
{
return strcmp(str1, str2);
}
int main( int argc, char * argv[])
{
GSList * list = NULL;
/*
* 这里没有调用创建链表的函数，只需要声明一个指向GSList结构体的指针，
* g_slist_append函数返回指向链表首部的指针，所以一定要保存这个指针
*/
printf( " Creat single list:/n " );
list = g_slist_append(list, " one " );
list = g_slist_append(list, " two " );
list = g_slist_append(list, " three " );
display_list(list);
/*
* 在链表首部加入，复杂度是O(1)，记得要保存函数返回的指针
*/
printf( " Add at head of list:/n " );
list = g_slist_prepend(list, " first " );
list = g_slist_prepend(list, " second " );
list = g_slist_prepend(list, " third " );
display_list(list);
/*
* 在链表的指定位置插入一个节点
*/
printf( " Insert at index 1, 2, 3:/n " );
list = g_slist_insert(list, " 1 " , 1 );
list = g_slist_insert(list, " 2 " , 2 );
list = g_slist_insert(list, " 3 " , 3 );
display_list(list);
/*
* 向链表中插入节点并排序，这里我传入了一个用于排序链表元素的比较函数，
* 这个函数只是简单的调用了strcmp。这里可以直接到strcmp作为第三个参数
* 传给g_slist_insert_sorted
*/
printf( " Insert sorted:/n " );
list = g_slist_insert_sorted(list, " ONE " , my_str_cmp);
list = g_slist_insert_sorted(list, " TWO " , my_str_cmp);
list = g_slist_insert_sorted(list, " THREE " , my_str_cmp);
display_list(list);
/*
* 反转链表
*/
printf( " Reverse the list:/n " );
list = g_slist_reverse(list);
display_list(list);
/*
* 删除链表，如果list为NULL的话，g_slist_free函数会直接返回
*/
g_slist_free(list);
return 0 ;
}
程序的运行结果如下：
Creat single list:
one two three
Add at head of list:
third second first one two three
Insert at index 1, 2, 3:
third 1 2 3 second first one two three
Insert sorted:
ONE THREE TWO third 1 2 3 second first one two three
Reverse the list:
three two one first second 3 2 1 third TWO THREE ONE
从上面的例子里我们可以看到，使用一个单向链表前只需要声明一个指向GSList结构的指针就可以了，声明该指 针以后就可以用该指针来对链表进行操作，只需要记住每次对链表进行操作后，都要保存返回的链表头指针就可以了。
下面的一个例子用于演法对单链表的查找、删除与合并。
#include < glib.h >
void display_list(GSList * list)
{
GSList * iterator = NULL;
for (iterator = list; iterator; iterator = iterator -> next) {
printf( " %s " , ( char * ) iterator -> data);
}
printf( " /n " );
}
int main( int argc, char * argv[])
{
GSList * list = NULL;
printf( " Create single list:/n " );
list = g_slist_append(list, " one " );
list = g_slist_append(list, " two " );
list = g_slist_append(list, " three " );
list = g_slist_append(list, " four " );
list = g_slist_append(list, " five " );
display_list(list);
GSList * it = NULL;
/*
* 查找内容为"three"的节点，返回指向找到的第一个节点的指针
*/
printf( " Find data "three" in the list:/n " );
it = g_slist_find(list, " three " );
printf( " %s " , ( char * ) it -> data);
/*
* 查找第三个节点，链表里节点的索引号为0,1,2...
* 如果超出链表尾部（链表长度小于3）返回NULL
*/
printf( " Data of the 3rd item:/n " );
it = g_slist_nth(list, 2 );
if (it != NULL) {
printf( " %s " , ( char * ) it -> data);
}
/*
* 取第5个节点的数据，如果超出链表尾部，返回NULL
*/
printf( " Data of the 5th item:/n " );
printf( " %s " , g_slist_nth_data(list, 4 ));
list = g_slist_append(list, " two " );
display_list(list);
/*
* 删除数据为"two"的节点，这里只会删除找到的第一个节点，
* 后面的节点不会被删除
*/
printf( " Remove the first data "two" from the list:/n " );
list = g_slist_remove(list, " two " );
display_list(list);
/*
* 另一种删除节点的方法，先把节点从链表里删除，再删除节点的数据
*/
printf( " Remove the 3rd item from list:/n " );
it = g_slist_nth(list, 2 );
/* 执行完下面这一步it->next==NULL */
list = g_slist_remove_link(list, it);
/* 删除节点及其数据 */
g_slist_free_1(it);
display_list(list);
GSList * list2 = NULL;
printf( " The second list:/n " );
list2 = g_slist_append(list2, " six " );
list2 = g_slist_append(list2, " seven " );
list2 = g_slist_append(list2, " eight " );
display_list(list2);
/*
* 合并两个链表
*/
printf( " Concat two lists:/n " );
list = g_slist_concat(list, list2);
display_list(list);
g_slist_free(list);
return 0 ;
}
程序的运行结果如下：
Creat single list:
one two three
Add at head of list:
third second first one two three
Insert at index 1, 2, 3:
third 1 2 3 second first one two three
Insert sorted:
ONE THREE TWO third 1 2 3 second first one two three
Reverse the list:
three two one first second 3 2 1 third TWO THREE ONE
从上面的例子里我们可以看到，使用一个单向链表前只需要声明一个指向GSList结构的指针就可以了，声明该指 针以后就可以用该指针来对链表进行操作，只需要记住每次对链表进行操作后，都要保存返回的链表头指针就可以了。
下面的一个例子用于演法对单链表的查找、删除与合并。
#include < glib.h >
void display_list(GSList * list)
{
GSList * iterator = NULL;
for (iterator = list; iterator; iterator = iterator -> next) {
printf( " %s " , ( char * ) iterator -> data);
}
printf( " /n " );
}
int main( int argc, char * argv[])
{
GSList * list = NULL;
printf( " Create single list:/n " );
list = g_slist_append(list, " one " );
list = g_slist_append(list, " two " );
list = g_slist_append(list, " three " );
list = g_slist_append(list, " four " );
list = g_slist_append(list, " five " );
display_list(list);
GSList * it = NULL;
/*
* 查找内容为"three"的节点，返回指向找到的第一个节点的指针
*/
printf( " Find data "three" in the list:/n " );
it = g_slist_find(list, " three " );
printf( " %s " , ( char * ) it -> data);
/*
* 查找第三个节点，链表里节点的索引号为0,1,2...
* 如果超出链表尾部（链表长度小于3）返回NULL
*/
printf( " Data of the 3rd item:/n " );
it = g_slist_nth(list, 2 );
if (it != NULL) {
printf( " %s " , ( char * ) it -> data);
}
/*
* 取第5个节点的数据，如果超出链表尾部，返回NULL
*/
printf( " Data of the 5th item:/n " );
printf( " %s " , g_slist_nth_data(list, 4 ));
list = g_slist_append(list, " two " );
display_list(list);
/*
* 删除数据为"two"的节点，这里只会删除找到的第一个节点，
* 后面的节点不会被删除
*/
printf( " Remove the first data "two" from the list:/n " );
list = g_slist_remove(list, " two " );
display_list(list);
/*
* 另一种删除节点的方法，先把节点从链表里删除，再删除节点的数据
*/
printf( " Remove the 3rd item from list:/n " );
it = g_slist_nth(list, 2 );
/* 执行完下面这一步it->next==NULL */
list = g_slist_remove_link(list, it);
/* 删除节点及其数据 */
g_slist_free_1(it);
display_list(list);
GSList * list2 = NULL;
printf( " The second list:/n " );
list2 = g_slist_append(list2, " six " );
list2 = g_slist_append(list2, " seven " );
list2 = g_slist_append(list2, " eight " );
display_list(list2);
/*
* 合并两个链表
*/
printf( " Concat two lists:/n " );
list = g_slist_concat(list, list2);
display_list(list);
g_slist_free(list);
return 0 ;
}
程序的运行结果如下：
Create single list:
one two three four five
Find data "three" in the list:
three
Data of the 3rd item:
three
Data of the 5th item:
five
one two three four five two
Remove the first data "two" from the list:
one three four five two
Remove the 3rd item from list:
one three five two
The second list:
six seven eight
Concat two lists:
one three five two six seven eight
通过上面的两个子例我们可以看到，glib库中的单链表操作是很简单的。在这么多函数调用里，我们还可以发现glib库中操作数据结构的函数命名规则：g_容器名_函数名。对于我后面的文章将要讲到的双向链表、队列、树、hash表和数组，这一命名规则同样适用。
glib库的更多参考：
http://developer.gnome.org/doc/API/glib/index.html
http://developer.gnome.org/doc/API/2.0/glib/index.html
标签：glib,slist,GSList,list,two,链表,printf From： https://www.cnblogs.com/opensmarty/p/17979608