免费注册 查看新帖 |

Chinaunix

  平台 论坛 博客 文库
最近访问板块 发新帖
查看: 2470 | 回复: 0
打印 上一主题 下一主题

glib库单向链表GSList介绍 [复制链接]

论坛徽章:
0
跳转到指定楼层
1 [收藏(0)] [报告]
发表于 2010-02-04 16:51 |只看该作者 |倒序浏览
    glib库里实现了一些基本的数据结构,比如单向链表,双向链表、队列、树、hash表和数组。这篇文章里我主要介绍在linux平台下使用glib库中的单向链表进行编程,以后的文章我会陆续介绍双向链表、队列和其它数据结构的用法。    单向链表(即GSList)是glib库里最简单的容具,它把一系列的节点链接在一起,可以从一个节点访问到下一个节点。glib库里对GSList结构的定义如下:struct GSList
{
  gpointer data;
  GSList *next;
};
data成员定义为gpointer(即void*),可以放任何类型的数据。下面举个例子来说明怎么使用GSList来创建、添加、插入、排序、反转和销毁单向链表。/*
* file: g_slist_one.c
* desc: 这个文件用于演示glib库里单向链表的创建、添加、插入、排序、反转与销毁
* compile: gcc -o g_slist_one g_slist_one.c `pkg-config --cflags --libs glib-2.0`
*/
#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;
}
    从上面的例子里我们可以看到,使用一个单向链表前只需要声明一个指向GSList结构的指针就可以了,声明该指 针以后就可以用该指针来对链表进行操作,只需要记住每次对链表进行操作后,都要保存返回的链表头指针就可以了。
    下面的一个例子用于演法对单链表的查找、删除与合并。/*
* file: g_slist_two.c
* desc: 这个文件用于演示glib库单向链表的查找、删除与合并
* compile: gcc -o g_slist_two g_slist_two.c `pkg-config --cflags --libs glib-2.0`
*/
#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;
}


本文来自ChinaUnix博客,如果查看原文请点:http://blog.chinaunix.net/u2/88891/showart_2177959.html
您需要登录后才可以回帖 登录 | 注册

本版积分规则 发表回复

  

北京盛拓优讯信息技术有限公司. 版权所有 京ICP备16024965号-6 北京市公安局海淀分局网监中心备案编号:11010802020122 niuxiaotong@pcpop.com 17352615567
未成年举报专区
中国互联网协会会员  联系我们:huangweiwei@itpub.net
感谢所有关心和支持过ChinaUnix的朋友们 转载本站内容请注明原作者名及出处

清除 Cookies - ChinaUnix - Archiver - WAP - TOP