http://blog.csdn.net/rstevens/article/details/3839877
数组
概念
到目前为止我们已经介绍了两类有序集合：GSList 和
GList。它们非常相似，因为都依赖于指针来从一个元素链接到下一个条目，或者，在 GList
中，链接到前一个条目。不过，有另外一类不使用链接的有序集合；它的功能与 C 数组多少有些类似。
它叫做 GArray，提供一个具备索引的单一类型的有序集合，能够为了容纳新条目而增加大小。
相对于链表，数组有什么优势？一方面，索引访问。也就是说，如果想获得数组中的第十五个元素，只需要调用一个能够在常数时间内获取它的函数；不需要手工地遍历到那个位置，那将是一个
O(n) 操作。数组知道自己的大小，所以查询其大小是一个 O(1) 操作而不是 O(n) 操作。
基本操作
这里是向数组添加和删除数据的一些主要方法：
//ex-garray-1.c
#include
int main(int argc, char** argv) {
GArray* a = g_array_new(FALSE, FALSE,
sizeof(char*));
char* first = "hello", *second = "there", *third
= "world";
g_array_append_val(a, first);
g_array_append_val(a, second);
g_array_append_val(a, third);
g_printf("There are now %d items in the array/n",
a->len);
g_printf("The first item is '%s'/n",
g_array_index(a, char*, 0));
g_printf("The third item is '%s'/n",
g_array_index(a, char*, 2));
g_array_remove_index(a, 1);
g_printf("There are now %d items in the array/n",
a->len);
g_array_free(a, FALSE);
return 0;
}
***** Output *****
There are now 3 items in the array
The first item is 'hello'
The third item is 'world'
There are now 2 items in the array
需要考虑的几点：
* 在创建一个
GArray 时需要考虑一些选项。在上面的示例中，g_array_new
的前两个参数表明了数组是否要以零元素作为终止符，是否数组中的新元素自动设置为零。第三个参数告诉数组它将要保存哪种类型的数据。在这个示例中要创建一个保存
char* 类型数据的数组；在数组中放入任何其他东西都会导致段错误（segfaults）。
*
g_array_append_val 是一个设计不能接受字面值（literal value）的宏，所以不能调用
g_array_append_val(a, 42)。而是那个值需要放入一个变量，然后将那个变量传递到
g_array_append_val 中。作为对这种不方便之处的一种慰藉，g_array_append_val
的速度非常快。
* GArray
是具有一个成员变量 len 的结构体，所以为了获得数组的大小，只需要直接引用那个变量；不需要函数调用。
*
GArray 的大小以二幂次系数增长。也就是说，如果某个 GArray
包含四个条目，而且您又增加了另一个，那么在内部它会创建另一个拥有八个元素的
GArray，将四个现有元素拷贝到它，然后添加新的元素。这个改变大小的过程需要时间，所以，如果知道将要有大量的元素，那么创建
GArray 时预分配期望的大小会更有效。
更多 new/free 选项
本示例中包含创建和销毁 GArray 的一些不同方法：
//ex-garray-2.c
#include
int main(int argc, char** argv) {
GArray* a = g_array_sized_new(TRUE, TRUE,
sizeof(int), 16);
g_printf("Array preallocation is hidden, so array
size == %d/n", a->len);
g_printf("Array was init'd to zeros, so 3rd item
is = %d/n", g_array_index(a, int, 2));
g_array_free(a, FALSE);
// this creates an empty array, then resizes it
to 16 elements
a = g_array_new(FALSE, FALSE,
sizeof(char));
g_array_set_size(a, 16);
g_array_free(a, FALSE);
a = g_array_new(FALSE, FALSE,
sizeof(char));
char* x = g_strdup("hello world");
g_array_append_val(a, x);
g_array_free(a, TRUE);
return 0;
}
***** Output *****
Array preallocation is hidden, so array size == 0
Array was init'd to zeros, so 3rd item is = 0
注意，由于 GArray
以二幂次系数增长，所有，将数组的大小设置为接近二的某次幂（比如十四）的值会令效率较低。不要那样，而是直接使用最接近的二的某次幂。
添加数据的更多方法
到目前为止您已经看到如何使用 g_array_append_val
将数据添加到数组。不过，有其他的方式可以将数据置入数组，如下所示：
//ex-garray-3.c
#include
void prt(GArray* a) {
g_printf("Array holds: ");
int i;
for (i = 0; i <
a->len; i++)
g_printf("%d ", g_array_index(a, int, i));
g_printf("/n");
}
int main(int argc, char** argv) {
GArray* a = g_array_new(FALSE, FALSE,
sizeof(int));
g_printf("Array is empty, so appending some
values/n");
int x[2] = {4,5};
g_array_append_vals(a, &x,
2);
prt(a);
g_printf("Now to prepend some values/n");
int y[2] = {2,3};
g_array_prepend_vals(a, &y,
2);
prt(a);
g_printf("And one more prepend/n");
int z = 1;
g_array_prepend_val(a, z);
prt(a);
g_array_free(a, FALSE);
return 0;
}
***** Output *****
Array is empty, so appending some values
Array holds: 4 5
Now to prepend some values
Array holds: 2 3 4 5
And one more prepend
Array holds: 1 2 3 4 5
可以将多个值附加到数组，可以在最前添加一个值，也可以在最前添加多个值。不过，在向最前添加值的时候要小心；它是一个 O(n) 操作，因为
GArray
必须要将当前所有值向后移动，为新的数据腾出空间。在附加或者向最前添加多个值时，还需要使用变量，不过这是相当直观的，因为可以附加或者向最前添加整个数组。
插入数据
也可以向数组中各个不同的位置插入数据；不是限于只能附加或者向最前添加条目。这里是其工作方式：
//ex-garray-4.c
#include
void prt(GArray* a) {
g_printf("Array holds: ");
int i;
for (i = 0; i <
a->len; i++)
g_printf("%d ", g_array_index(a, int, i));
g_printf("/n");
}
int main(int argc, char** argv) {
GArray* a = g_array_new(FALSE, FALSE,
sizeof(int));
int x[2] = {1,5};
g_array_append_vals(a, &x,
2);
prt(a);
g_printf("Inserting a '2'/n");
int b = 2;
g_array_insert_val(a, 1, b);
prt(a);
g_printf("Inserting multiple values/n");
int y[2] = {3,4};
g_array_insert_vals(a, 2, y, 2);
prt(a);
g_array_free(a, FALSE);
return 0;
}
***** Output *****
Array holds: 1 5
Inserting a '2'
Array holds: 1 2 5
Inserting multiple values
Array holds: 1 2 3 4 5
注意，这些插入函数涉及到了向后拷贝列表中当前元素，目的是为新条目准备空间，所以使用 g_array_insert_vals 比反复使用
g_array_insert_val 更好。
删除数据
有三种方法可以从 GArray 删除数据：
*
g_array_remove_index 和 g_array_remove_range，这两个函数会保持现有顺序
*
g_array_remove_index_fast，不保持现有顺序
这里是所有三种方法的示例：
//ex-garray-5.c
#include
void prt(GArray* a) {
int i;
g_printf("Array holds: ");
for (i = 0; i <
a->len; i++)
g_printf("%d ", g_array_index(a, int, i));
g_printf("/n");
}
int main(int argc, char** argv) {
GArray* a = g_array_new(FALSE, FALSE,
sizeof(int));
int x[6] = {1,2,3,4,5,6};
g_array_append_vals(a, &x,
6);
prt(a);
g_printf("Removing the first item/n");
g_array_remove_index(a, 0);
prt(a);
g_printf("Removing the first two items/n");
g_array_remove_range(a, 0, 2);
prt(a);
g_printf("Removing the first item very
quickly/n");
g_array_remove_index_fast(a, 0);
prt(a);
g_array_free(a, FALSE);
return 0;
}
***** Output *****
Array holds: 1 2 3 4 5 6
Removing the first item
Array holds: 2 3 4 5 6
Removing the first two items
Array holds: 4 5 6
Removing the first item very quickly
Array holds: 6 5
不只是您可能会对 g_array_remove_fast 的使用情形感到奇怪；三个开放源代码的应用程序都没有使用这个函数。
排序
对 GArray 排序很直观；它使用的是在 GList 和 GSList 部分已经出现过的 GCompareFunc：
//ex-garray-6.c
#include
void prt(GArray* a) {
int i;
g_printf("Array holds: ");
for (i = 0; i <
a->len; i++)
g_printf("%d ", g_array_index(a, int, i));
g_printf("/n");
}
int compare_ints(gpointer a, gpointer b) {
int* x = (int*)a;
int* y = (int*)b;
return *x - *y;
}
int main(int argc, char** argv) {
GArray* a = g_array_new(FALSE, FALSE,
sizeof(int));
int x[6] = {2,1,6,5,4,3};
g_array_append_vals(a, &x,
6);
prt(a);
g_printf("Sorting/n");
g_array_sort(a,
(GCompareFunc)compare_ints);
prt(a);
g_array_free(a, FALSE);
return 0;
}
***** Output *****
Array holds: 2 1 6 5 4 3
Sorting
Array holds: 1 2 3 4 5 6
注意，比较函数会得到指向数据条目的一个指针，所以在这种情况下，需要将它们强制类型转换为指向正确类型的指针，然后反引用那个指针，得到实际的数据条目。GArray
还包括另一个排序函数，即 g_array_sort_with_data，它会接受指向另外一段数据的一个指针。
顺便提一句，这三个示例应用程序都没有使用 g_array_sort 和
g_array_sort_with_data。不过，无论如何，知道它们是可用的，都会有所帮助。
指针数组
GLib 还提供了 GPtrArray，这是一个为保存指针专门设计的数组。使用它比使用基本的 GArray
更简单，因为在创建或者添加、索引元素时不需要指定具体类型。它与 GArray
非常类似，所以我们将只是回顾基本操作的一些示例：
//ex-garray-7.c
#include
#include
int main(int argc, char** argv) {
GPtrArray* a = g_ptr_array_new();
g_ptr_array_add(a, g_strdup("hello "));
g_ptr_array_add(a, g_strdup("again "));
g_ptr_array_add(a, g_strdup("there "));
g_ptr_array_add(a, g_strdup("world "));
g_ptr_array_add(a, g_strdup("/n"));
g_printf(">Here are the GPtrArray
contents/n");
g_ptr_array_foreach(a, (GFunc)g_printf,
NULL);
g_printf(">Removing the third
item/n");
g_ptr_array_remove_index(a, 2);
g_ptr_array_foreach(a, (GFunc)g_printf,
NULL);
g_printf(">Removing the second and
third item/n");
g_ptr_array_remove_range(a, 1, 2);
g_ptr_array_foreach(a, (GFunc)g_printf,
NULL);
g_printf("The first item is '%s'/n",
g_ptr_array_index(a, 0));
g_ptr_array_free(a, TRUE);
return 0;
}
***** Output *****
>Here are the GPtrArray contents
hello again there world
>Removing the third item
hello again world
>Removing the second and third item
hello
The first item is 'hello '
可以了解如何使用只支持指针的数组编写更为直观的 API。这可能能够解释为什么在 Evolution 中使用
g_ptr_array_new 的次数为 178 次，而 g_array_new 只使用了 45
次。大部分情况下只支持指针的数组就足够了!
字节数组
GLib 提供了另一个特定类型的数组是
GByteArray。它与您已经了解的类型非常类似，不过有一些区别，因为它是为存储二进制数据而设计的。它非常便于在循环中读取二进制数据，因为它隐藏了“read
into a buffer-resize buffer-read some more”的周期。这里是一些示例代码：
//ex-garray-8.c
#include
int main(int argc, char** argv) {
GByteArray* a = g_byte_array_new();
guint8 x = 0xFF;
g_byte_array_append(a, &x,
sizeof(x));
g_printf("The first byte value (in decimal) is
%d/n", a->data[0]);
x = 0x01;
g_byte_array_prepend(a, &x,
sizeof(x));
g_printf("After prepending, the first value is
%d/n", a->data[0]);
g_byte_array_remove_index(a, 0);
g_printf("After removal, the first value is again
%d/n", a->data[0]);
g_byte_array_append(g_byte_array_append(a,
&x, sizeof(x)), &x,
sizeof(x));
g_printf("After two appends, array length is
%d/n", a->len);
g_byte_array_free(a, TRUE);
return 0;
}
***** Output *****
The first byte value (in decimal) is 255
After prepending, the first value is 1
After removal, the first value is again 255
After two appends, array length is 3
还可以发现，在这里使用了一个新的 GLib 类型：guint8。这是跨平台的
8-位无符号整数，有益于在本例中准确描述字节。
另外，在这里可以了解到 g_byte_array_append 如何返回
GByteArray。所以，这就使得可以像编写方法链（method
chaining）那样将一些附加动作嵌套起来。不过，嵌套多于两个或三个可能并不是一个好办法，除非想让代码变更得 LISP
那样。
实际应用
在示例应用程序中使用了各种不同的 GLib 数组类型，虽然不如已经接触的其他容器那样广泛。
Gaim 只使用了 GPtrArrays，而且只在一两种情形下使用到了。gaim-1.2.1/src/gtkpounce.c 使用一个
GPtrArray 来保持对一些 GUI 窗口小部件的追踪，在发生各种事件（比如好友登录进来）时它们会被触发。
Evolution 所使用的大部分是 GPtrArrays，不过也使用了很多 GArrays 和 GByteArrays：
*
evolution-2.0.2/widgets/misc/e-filter-bar.h 在 GPtrArrays
中保持一些搜索过滤器的类型。
*
evolution-2.0.2/camel/providers/imap4/camel-imap4-store.c 使用
GPtrArray 来追踪 IMAP 文件夹中的条目；它使用 g_ptr_array_sort 以及一个委派给 strcmp 的
GCompareFunc。
GIMP 使用了相当多的 GArray，只使用了很少 GPtrArrays 和 GByteArrays：
*
gimp-2.2.4/app/tools/gimptransformtool.c 使用 GArray 来追踪 GimpCoord
实例列表。
*
gimp-2.2.4/app/base/boundary.c 中，由点（points）填充起来的 GArray 是极好的
simplify_subdivide 函数的一部分；递归传递的指向 GArray 的双重间接指针是边界简化（boundary
simplification）例程的一部分。
*
树
概念
树 是另一个实用的容器。树中有一个可以拥有子节点的根节点，每个子节点可以有更多子节点，依此类推。
树结构体的示例包括文件系统或者电子邮件客户机；它其中有包含文件夹的文件夹，文件夹中可以有更多文件夹。另外，是否还记得哈希表部分的最后出现的多值示例？（例如，以字符串作为键，GList
作为值。）由于那些 GLish 值可以容纳更多 GHashTables，那就成为 GHashTable
中构造树结构体的示例。相对于付出努力想使用树一样使用其他容器，使用 GTree 简单得多。
GLib 包括两种树结构：GTree（平衡二叉树 实现）以及 GNode（n-叉 树实现）。
二叉树的特殊属性是，树中每个节点拥有不超过两个子节点；平衡二叉树表示元素以特定的次序保持，以进行更快速地搜索。保持元素的平衡意味着删除和插入可能会较慢，因为树本身可能需要进行内部重新平衡，不过寻找某个条目是
O(log n) 操作。
相反，n-叉 树 节点可以有很多子节点。本教程主要关注二叉树，不过也会有一些 n-叉 树的示例。
中序遍历：：左子树－＞根－＞右子树 eg::DBGEACHFI
前序遍历：：根－＞左子树－＞右子树 eg::ABDEGCFHI
前序遍历：：左子树－＞右子树 －＞根eg::GEBHIFCA
树的基本操作
这里是在树中可以执行的一些基本操作：
//ex-gtree-1.c
#include
int main(int argc, char** argv) {
GTree* t = g_tree_new((GCompareFunc)g_ascii_strcasecmp);
g_tree_insert(t, "c", "Chicago");
g_printf("The tree height is %d because there's only one node/n",
g_tree_height(t));
加载中…