📄 z29.html
字号:
<!DOCTYPE html PUBLIC "-//W3C//DTD HTML 4.0 Transitional//EN"><html> <head> <title> Data Structures </title> <meta name="GENERATOR" content= "Modular DocBook HTML Stylesheet Version 1.45"> <link rel="HOME" title="GTK+ / Gnome Application Development" href="ggad.html"> <link rel="UP" title="glib: Portability and Utility" href= "cha-glib.html"> <link rel="PREVIOUS" title="glib: Portability and Utility" href="cha-glib.html"> <link rel="NEXT" title="Other Features" href="z35.html"> </head> <body bgcolor="#FFFFFF" text="#000000" link="#0000FF" vlink= "#840084" alink="#0000FF"> <div class="NAVHEADER"> <table width="100%" border="0" bgcolor="#ffffff" cellpadding= "1" cellspacing="0"> <tr> <th colspan="4" align="center"> <font color="#000000" size="2">GTK+ / Gnome Application Development</font> </th> </tr> <tr> <td width="25%" bgcolor="#ffffff" align="left"> <a href="cha-glib.html"><font color="#0000ff" size="2"> <b><<< Previous</b></font></a> </td> <td width="25%" colspan="2" bgcolor="#ffffff" align= "center"> <font color="#0000ff" size="2"><b><a href="ggad.html"> <font color="#0000ff" size="2"><b> Home</b></font></a></b></font> </td> <td width="25%" bgcolor="#ffffff" align="right"> <a href="z35.html"><font color="#0000ff" size="2"><b> Next >>></b></font></a> </td> </tr> </table> </div> <div class="SECT1"> <h1 class="SECT1"> <a name="Z29">Data Structures</a> </h1> <p> glib implements many common data structures, so you don't have to reinvent the wheel every time you want a linked list. This section covers glib's implementation of linked lists, sorted binary trees, N-ary trees, and hash tables. </p> <div class="SECT2"> <h2 class="SECT2"> <a name="Z30">Lists</a> </h2> <p> glib provides generic single and doubly linked lists, <span class="STRUCTNAME">GSList</span> and <span class= "STRUCTNAME">GList</span>, respectively. These are implemented as lists of <span class="STRUCTNAME"> gpointer</span>; you can use them to hold integers with the <tt class="FUNCTION">GINT_TO_POINTER</tt> and <tt class="FUNCTION">GPOINTER_TO_INT</tt> macros. <span class="STRUCTNAME">GSList</span> and <span class= "STRUCTNAME">GList</span> have identical API's, except that there is a <tt class="FUNCTION"> g_list_previous()</tt> function and no <tt class= "FUNCTION">g_slist_previous()</tt>. This section will discuss <span class="STRUCTNAME">GSList</span> but everything also applies to the doubly linked list. </p> <p> In the glib implementation, the empty list is simply a <span class="STRUCTNAME">NULL</span> pointer. It's always safe to pass <span class="STRUCTNAME">NULL</span> to list functions since it's a valid list of length 0. Code to create a list and add one element might look like this: </p> <table border="0" bgcolor="#E0E0E0" width="100%"> <tr> <td><pre class="PROGRAMLISTING"> GSList* list = NULL;gchar* element = g_strdup("a string");list = g_slist_append(list, element); </pre> </td> </tr> </table> <p> glib lists have a noticeable Lisp influence; the empty list is a special "nil" value for that reason. <tt class= "FUNCTION">g_slist_prepend()</tt> works much like <tt class="APPLICATION">cons</tt>---it's a constant-time operation that adds a new cell to the front of the list. </p> <p> Notice that you must replace the list passed to list-modifying functions with their return value, in case the head of the list changes. glib will handle memory issues, deallocating and allocating list links as needed. </p> <p> For example, the following code would remove the above-added element and empty the list: </p> <table border="0" bgcolor="#E0E0E0" width="100%"> <tr> <td><pre class="PROGRAMLISTING"> list = g_slist_remove(list, element); </pre> </td> </tr> </table> <p> <span class="STRUCTNAME">list</span> is now <span class= "STRUCTNAME">NULL</span>. You still have to free <span class="STRUCTNAME">element</span> yourself, of course. To clear an entire list, use <tt class="FUNCTION"> g_slist_free()</tt>, which removes all the links in one fell swoop. <tt class="FUNCTION">g_slist_free()</tt> has no return value because it would always be <span class= "STRUCTNAME">NULL</span>, and you can simply assign that value to your list if you like. Obviously, <tt class= "FUNCTION">g_slist_free()</tt> frees only the list cells; it has no way of knowing what to do with the list contents. </p> <p> To access a list element, you refer to the <span class= "STRUCTNAME">GSList</span> struct directly: </p> <table border="0" bgcolor="#E0E0E0" width="100%"> <tr> <td><pre class="PROGRAMLISTING"> gchar* my_data = list->data; </pre> </td> </tr> </table> <p> To iterate over the list, you might write code like this: </p> <table border="0" bgcolor="#E0E0E0" width="100%"> <tr> <td><pre class="PROGRAMLISTING"> GSList* tmp = list;while (tmp != NULL) { printf("List data: %p\n", tmp->data); tmp = g_slist_next(tmp); } </pre> </td> </tr> </table> <p> <a href="z29.html#FL-LISTCHANGING">Figure 13</a> shows the basic functions for changing <span class= "STRUCTNAME">GSList</span> contents. For all of these, you must assign the return value to your list pointer in case the head of the list changes. Note that glib does <i class="EMPHASIS">not</i> store a pointer to the tail of the list, so prepending is a constant-time operation, while append, insert, and remove are proportional to the list's size. </p> <p> In particular, this means that constructing a list using <tt class="FUNCTION">g_slist_append()</tt> is a <i class= "EMPHASIS">terrible</i> idea; use <tt class="FUNCTION"> g_slist_prepend()</tt> and then call <tt class= "FUNCTION">g_slist_reverse()</tt> if you need items in a particular order. If you anticipate frequently appending to a list, you can also keep a pointer to the last element. The following code can be used to perform efficient appends: </p> <table border="0" bgcolor="#E0E0E0" width="100%"> <tr> <td><pre class="PROGRAMLISTING"> voidefficient_append(GSList** list, GSList** list_end, gpointer data){ g_return_if_fail(list != NULL); g_return_if_fail(list_end != NULL); if (*list == NULL) { g_assert(*list_end == NULL); *list = g_slist_append(*list, data); *list_end = *list; } else { *list_end = g_slist_append(*list_end, data)->next; }} </pre> </td> </tr> </table> <p> To use this function, you would store the list and its end somewhere, and pass their address to <tt class= "FUNCTION">efficient_append()</tt>: </p> <table border="0" bgcolor="#E0E0E0" width="100%"> <tr> <td><pre class="PROGRAMLISTING"> GSList* list = NULL; GSList* list_end = NULL; efficient_append(&list, &list_end, g_strdup("Foo")); efficient_append(&list, &list_end, g_strdup("Bar")); efficient_append(&list, &list_end, g_strdup("Baz")); </pre> </td> </tr> </table> <p> Of course you have to be careful not to use any list functions that might change the end of the list without updating <span class="STRUCTNAME">list_end</span>. </p> <div class="FIGURE"> <a name="FL-LISTCHANGING"></a> <div class="FUNCSYNOPSIS"> <a name="FL-LISTCHANGING.SYNOPSIS"></a> <table border="0" bgcolor="#E0E0E0" width="100%"> <tr> <td><pre class="FUNCSYNOPSISINFO">#include <glib.h></pre> </td> </tr> </table> <p> <code><code class="FUNCDEF">GSList* <tt class= "FUNCTION">g_slist_append</tt></code>(GSList* <tt class="PARAMETER"><i>list</i></tt>, gpointer <tt class="PARAMETER"><i>data</i></tt>);</code> </p> <p> <code><code class="FUNCDEF">GSList* <tt class= "FUNCTION">g_slist_prepend</tt></code>(GSList* <tt class="PARAMETER"><i>list</i></tt>, gpointer <tt class="PARAMETER"><i>data</i></tt>);</code> </p> <p> <code><code class="FUNCDEF">GSList* <tt class= "FUNCTION">g_slist_insert</tt></code>(GSList* <tt class="PARAMETER"><i>list</i></tt>, gpointer <tt class="PARAMETER"><i>data</i></tt>, gint <tt class= "PARAMETER"><i>position</i></tt>);</code> </p> <p> <code><code class="FUNCDEF">GSList* <tt class= "FUNCTION">g_slist_remove</tt></code>(GSList* <tt class="PARAMETER"><i>list</i></tt>, gpointer <tt class="PARAMETER"><i>data</i></tt>);</code> </p> </div> <p> <b>Figure 13. Changing linked list contents</b> </p> </div> <p> For accessing list elements, the functions in <a href= "z29.html#FL-LISTACCESS">Figure 14</a> are provided. None of these change the list's structure. <tt class= "FUNCTION">g_slist_foreach()</tt> applies a <span class= "STRUCTNAME">GFunc</span> to each element of the list. A <span class="STRUCTNAME">GFunc</span> is defined as follows: </p> <table border="0" bgcolor="#E0E0E0" width="100%"> <tr> <td><pre class="PROGRAMLISTING"> typedef void (*GFunc)(gpointer data, gpointer user_data); </pre> </td> </tr> </table> <p> Used in <tt class="FUNCTION">g_slist_foreach()</tt>, your <span class="STRUCTNAME">GFunc</span> will be called on each <span class="STRUCTNAME">list->data</span> in <span class="STRUCTNAME">list</span>, passing the <span class="STRUCTNAME">user_data</span> you provided to <tt class="FUNCTION">g_slist_foreach()</tt>. <tt class= "FUNCTION">g_slist_foreach()</tt> is comparable to Scheme's "map" function. </p> <p> For example, you might have a list of strings, and you might want to be able to create a parallel list with some transformation applied to the strings. Here is some code, using the <tt class="FUNCTION">efficient_append()</tt> function from an earlier example: </p> <table border="0" bgcolor="#E0E0E0" width="100%"> <tr> <td><pre class="PROGRAMLISTING"> typedef struct _AppendContext AppendContext;struct _AppendContext { GSList* list; GSList* list_end; const gchar* append;};⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -