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