2021年3月21日 星期日

glib tree example

編譯:gcc -g -Wall -O0 fuck.c -o fuck `pkg-config --libs --cflags glib-2.0`

1.树的基本操作


这里是在树中可以执行的一些基本操作:

#include <glib.h>
#include
<stdio.h>

int main(int argc, char** argv) {
GTree
* t = g_tree_new((GCompareFunc)g_ascii_strcasecmp);
g_tree_insert(t,
"c", "Chicago");
printf(
"The tree height is %d because there's only one node\n", g_tree_height(t));
g_tree_insert(t,
"b", "Boston");
g_tree_insert(t,
"d", "Detroit");
printf(
"Height is %d since c is root; b and d are children\n", g_tree_height(t));
printf(
"There are %d nodes in the tree\n", g_tree_nnodes(t));
g_tree_remove(t,
"d");
printf(
"After remove(), there are %d nodes in the tree\n", g_tree_nnodes(t));
g_tree_destroy(t);
return 0;
}

***** Output *****

The tree height is 1 because there's only one node
Height is 2 since c is root; b and d are children
There are 3 nodes in the tree
After remove(), there are 2 nodes in the tree

2.替换和提取


在前面的 GHashTable 部分已经看到了 replace 和 steal 函数名, 关于 GTree 的函数也是如此。

g_tree_replace 会同时替换一个 GTree 条目的键和值,不同于 g_tree_insert,如果要插入的键是重复的,则它只是将值替换。

不需要调用任何 GDestroyNotify 函数,g_tree_steal 就可以删除一个节点。 这里是一个示例:

#include <glib.h>
#include
<stdio.h>

void key_d(gpointer data) {
printf(
"Key %s destroyed\n", data);
}
void value_d(gpointer data) {
printf(
"Value %s destroyed\n", data);
}
int main(int argc, char** argv) {
GTree
* t = g_tree_new_full((GCompareDataFunc)g_ascii_strcasecmp,
NULL, (GDestroyNotify)key_d, (GDestroyNotify)value_d);
g_tree_insert(t,
"c", "Chicago");
g_tree_insert(t,
"b", "Boston");
g_tree_insert(t,
"d", "Detroit");
printf(
">Replacing 'b', should get destroy callbacks\n");
g_tree_replace(t,
"b", "Billings");
printf(
">Stealing 'b', no destroy notifications will occur\n");
g_tree_steal(t,
"b");
printf(
">Destroying entire tree now\n");
g_tree_destroy(t);
return 0;
}

***** Output *****

>Replacing 'b', should get destroy callbacks
Value Boston destroyed
Key b destroyed
>Stealing 'b', no destroy notifications will occur
>Destroying entire tree now
Key d destroyed
Value Detroit destroyed
Key c destroyed
Value Chicago destroyed


3.查找数据


GTree 具备只查找键或者同时查找键和值的方法。这与在 GHashTable 部分中接触到的非常类似;

有一个 lookup 以及一个 lookup_extended。这里是一个示例:

#include <glib.h>
#include
<stdio.h>

int main(int argc, char** argv) {
GTree
* t = g_tree_new((GCompareFunc)g_ascii_strcasecmp);
g_tree_insert(t,
"c", "Chicago");
g_tree_insert(t,
"b", "Boston");
g_tree_insert(t,
"d", "Detroit");
printf(
"The data at 'b' is %s\n", g_tree_lookup(t, "b"));
printf(
"%s\n", g_tree_lookup(t, "a") ? "My goodness!" : "As expected, couldn't find 'a'");

gpointer
* key = NULL;
gpointer
* value = NULL;
g_tree_lookup_extended(t,
"c", (gpointer*)&key, (gpointer*)&value);
printf(
"The data at '%s' is %s\n", key, value);
gboolean found
= g_tree_lookup_extended(t, "a", (gpointer*)&key, (gpointer*)&value);
printf(
"%s\n", found ? "My goodness!" : "As expected, couldn't find 'a'");

g_tree_destroy(t);
return 0;
}

***** Output *****

The data at 'b' is Boston
As expected, couldn't find 'a'
The data at 'c' is Chicago
As expected, couldn't find 'a'


4.使用 foreach 列出树


GTree 提供了一个 g_tree_foreach 函数,用来以有序的顺序遍历整棵对。这里是一个示例:

#include <glib.h>
#include
<stdio.h>

gboolean iter_all(gpointer key, gpointer value, gpointer data) {
printf(
"%s, %s\n", key, value);
return FALSE;
}
gboolean iter_some(gpointer key, gpointer value, gpointer data) {
printf(
"%s, %s\n", key, value);
return g_ascii_strcasecmp(key, "b") == 0;
}
int main(int argc, char** argv) {
GTree
* t = g_tree_new((GCompareFunc)g_ascii_strcasecmp);
g_tree_insert(t,
"d", "Detroit");
g_tree_insert(t,
"a", "Atlanta");
g_tree_insert(t,
"c", "Chicago");
g_tree_insert(t,
"b", "Boston");
printf(
"Iterating all nodes\n");
g_tree_foreach(t, (GTraverseFunc)iter_all, NULL);
printf(
"Iterating some of the nodes\n");
g_tree_foreach(t, (GTraverseFunc)iter_some, NULL);
g_tree_destroy(t);
return 0;
}

***** Output *****

Iterating all nodes
a, Atlanta
b, Boston
c, Chicago
d, Detroit
Iterating some of the nodes
a, Atlanta
b, Boston

5.搜索


可以使用 g_tree_foreach 搜索条目,如果知道键,可以使用 g_tree_lookup。 不过,要进行更复杂地搜索,可以使用 g_tree_search 函数。

这里是其工作方式:

#include <glib.h>
#include
<stdio.h>

gint finder(gpointer key, gpointer user_data) {
int len = strlen((char*)key);
if (len == 3) {
return 0;
}
return (len < 3) ? 1 : -1;
}
int main(int argc, char** argv) {
GTree
* t = g_tree_new((GCompareFunc)g_ascii_strcasecmp);
g_tree_insert(t,
"dddd", "Detroit");
g_tree_insert(t,
"a", "Annandale");
g_tree_insert(t,
"ccc", "Cleveland");
g_tree_insert(t,
"bb", "Boston");
gpointer value
= g_tree_search(t, (GCompareFunc)finder, NULL);
printf(
"Located value %s; its key is 3 characters long\n", value);
g_tree_destroy(t);
return 0;
}

***** Output *****

Located value Cleveland; its key is 3 characters long


6.不只是二叉:n-叉 树


GLib n-叉 树实现基于 GNode 数据结构;以前所述,它允许每个父节点有多个子节点。 好像很少会用到它,不过,完整起见,这里给出一个用法示例:

#include <glib.h>
#include
<stdio.h>

gboolean iter(GNode
* n, gpointer data) {
printf(
"%s ", n->data);
return FALSE;
}
int main(int argc, char** argv) {
GNode
* root = g_node_new("Atlanta");
g_node_append(root, g_node_new(
"Detroit"));
GNode
* portland = g_node_prepend(root, g_node_new("Portland"));
printf(
">Some cities to start with\n");
g_node_traverse(root, G_PRE_ORDER, G_TRAVERSE_ALL,
-1, iter, NULL);
printf(
"\n>Inserting Coos Bay before Portland\n");
g_node_insert_data_before(root, portland,
"Coos Bay");
g_node_traverse(root, G_PRE_ORDER, G_TRAVERSE_ALL,
-1, iter, NULL);
printf(
"\n>Reversing the child nodes\n");
g_node_reverse_children(root);
g_node_traverse(root, G_PRE_ORDER, G_TRAVERSE_ALL,
-1, iter, NULL);
printf(
"\n>Root node is %s\n", g_node_get_root(portland)->data);
printf(
">Portland node index is %d\n", g_node_child_index(root, "Portland"));
g_node_destroy(root);
return 0;
}

***** Output *****

>Some cities to start with
Atlanta Portland Detroit
>Inserting Coos Bay before Portland
Atlanta Coos Bay Portland Detroit
>Reversing the child nodes
Atlanta Detroit Portland Coos Bay
>Root node is Atlanta
>Portland node index is 1

REF

沒有留言:

張貼留言