glib庫單向鏈表GSList介紹

_mystic

    glib庫里實現(xiàn)了一些基本的數(shù)據(jù)結(jié)構(gòu)，比如單向鏈表，雙向鏈表、隊列、樹、hash表和數(shù)組。這篇文章里我主要介紹在linux平臺下使用glib庫中的單向鏈表進行編程，以后的文章我會陸續(xù)介紹雙向鏈表、隊列和其它數(shù)據(jù)結(jié)構(gòu)的用法。    單向鏈表（即GSList）是glib庫里最簡單的容具，它把一系列的節(jié)點鏈接在一起，可以從一個節(jié)點訪問到下一個節(jié)點。glib庫里對GSList結(jié)構(gòu)的定義如下：struct GSList
{
  gpointer data;
  GSList *next;
};
data成員定義為gpointer（即void*），可以放任何類型的數(shù)據(jù)。下面舉個例子來說明怎么使用GSList來創(chuàng)建、添加、插入、排序、反轉(zhuǎn)和銷毀單向鏈表。/*
* file: g_slist_one.c
* desc: 這個文件用于演示glib庫里單向鏈表的創(chuàng)建、添加、插入、排序、反轉(zhuǎn)與銷毀
* 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;
    /*
     * 這里沒有調(diào)用創(chuàng)建鏈表的函數(shù)，只需要聲明一個指向GSList結(jié)構(gòu)體的指針，
     * g_slist_append函數(shù)返回指向鏈表首部的指針，所以一定要保存這個指針
     */
    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);
    /*
     * 在鏈表首部加入，復(fù)雜度是O(1)，記得要保存函數(shù)返回的指針
     */
    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);
    /*
     * 在鏈表的指定位置插入一個節(jié)點
     */
    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);
    /*
     * 向鏈表中插入節(jié)點并排序，這里我傳入了一個用于排序鏈表元素的比較函數(shù)，
     * 這個函數(shù)只是簡單的調(diào)用了strcmp。這里可以直接到strcmp作為第三個參數(shù)
     * 傳給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);
    /*
     * 反轉(zhuǎn)鏈表
     */
    printf("Reverse the list:\n");
    list = g_slist_reverse(list);
    display_list(list);
    /*
     * 刪除鏈表，如果list為NULL的話，g_slist_free函數(shù)會直接返回
     */
    g_slist_free(list);
    return 0;
}
    從上面的例子里我們可以看到，使用一個單向鏈表前只需要聲明一個指向GSList結(jié)構(gòu)的指針就可以了，聲明該指 針以后就可以用該指針來對鏈表進行操作，只需要記住每次對鏈表進行操作后，都要保存返回的鏈表頭指針就可以了。
    下面的一個例子用于演法對單鏈表的查找、刪除與合并。/*
* 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;
    /*
     * 查找內(nèi)容為"three"的節(jié)點，返回指向找到的第一個節(jié)點的指針
     */
    printf("Find data "three" in the list:\n");
    it = g_slist_find(list, "three");
    printf("%s ", (char*) it->data);
    /*
     * 查找第三個節(jié)點，鏈表里節(jié)點的索引號為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個節(jié)點的數(shù)據(jù)，如果超出鏈表尾部，返回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);
   
    /*
     * 刪除數(shù)據(jù)為"two"的節(jié)點，這里只會刪除找到的第一個節(jié)點，
     * 后面的節(jié)點不會被刪除
     */
    printf("Remove the first data "two" from the list:\n");
    list = g_slist_remove(list, "two");
    display_list(list);
    /*
     * 另一種刪除節(jié)點的方法，先把節(jié)點從鏈表里刪除，再刪除節(jié)點的數(shù)據(jù)
     */
    printf("Remove the 3rd item from list:\n");
    it = g_slist_nth(list, 2);
    /* 執(zhí)行完下面這一步it->next==NULL */
    list = g_slist_remove_link(list, it);
   
    /* 刪除節(jié)點及其數(shù)據(jù) */
    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