Glib实例学习（6）双端队列

4613阅读　0评论2011-07-04　onezeroone
分类：C/C++

1：结构

  1. typedef struct {
  2.   GList *head;
  3.   GList *tail;
  4.   guint length;
  5. } GQueue;

2：原型

  1. GQueue* g_queue_new (void);
  2. void g_queue_free (GQueue *queue);
  3. #define G_QUEUE_INIT
  4. void g_queue_init (GQueue *queue);
  5. void g_queue_clear (GQueue *queue);
  6. gboolean g_queue_is_empty (GQueue *queue);
  7. guint g_queue_get_length (GQueue *queue);
  8. void g_queue_reverse (GQueue *queue);
  9. GQueue* g_queue_copy (GQueue *queue);
  10. void g_queue_foreach (GQueue *queue,
  11.                                                          GFunc func,
  12.                                                          gpointer user_data);
  13. GList* g_queue_find (GQueue *queue,
  14.                                                          gconstpointer data);
  15. GList* g_queue_find_custom (GQueue *queue,
  16.                                                          gconstpointer data,
  17.                                                          GCompareFunc func);
  18. void g_queue_sort (GQueue *queue,
  19.                                                          GCompareDataFunc compare_func,
  20.                                                          gpointer user_data);
  21. void g_queue_push_head (GQueue *queue,
  22.                                                          gpointer data);
  23. void g_queue_push_tail (GQueue *queue,
  24.                                                          gpointer data);
  25. void g_queue_push_nth (GQueue *queue,
  26.                                                          gpointer data,
  27.                                                          gint n);
  28. gpointer g_queue_pop_head (GQueue *queue);
  29. gpointer g_queue_pop_tail (GQueue *queue);
  30. gpointer g_queue_pop_nth (GQueue *queue,
  31.                                                          guint n);
  32. gpointer g_queue_peek_head (GQueue *queue);
  33. gpointer g_queue_peek_tail (GQueue *queue);
  34. gpointer g_queue_peek_nth (GQueue *queue,
  35.                                                          guint n);
  36. gint g_queue_index (GQueue *queue,
  37.                                                          gconstpointer data);
  38. void g_queue_remove (GQueue *queue,
  39.                                                          gconstpointer data);
  40. void g_queue_remove_all (GQueue *queue,
  41.                                                          gconstpointer data);
  42. void g_queue_insert_before (GQueue *queue,
  43.                                                          GList *sibling,
  44.                                                          gpointer data);
  45. void g_queue_insert_after (GQueue *queue,
  46.                                                          GList *sibling,
  47.                                                          gpointer data);
  48. void g_queue_insert_sorted (GQueue *queue,
  49.                                                          gpointer data,
  50.                                                          GCompareDataFunc func,
  51.                                                          gpointer user_data);
  52. void g_queue_push_head_link (GQueue *queue,
  53.                                                          GList *link_);
  54. void g_queue_push_tail_link (GQueue *queue,
  55.                                                          GList *link_);
  56. void g_queue_push_nth_link (GQueue *queue,
  57.                                                          gint n,
  58.                                                          GList *link_);
  59. GList* g_queue_pop_head_link (GQueue *queue);
  60. GList* g_queue_pop_tail_link (GQueue *queue);
  61. GList* g_queue_pop_nth_link (GQueue *queue,
  62.                                                          guint n);
  63. GList* g_queue_peek_head_link (GQueue *queue);
  64. GList* g_queue_peek_tail_link (GQueue *queue);
  65. GList* g_queue_peek_nth_link (GQueue *queue,
  66.                                                          guint n);
  67. gint g_queue_link_index (GQueue *queue,
  68.                                                          GList *link_);
  69. void g_queue_unlink (GQueue *queue,
  70.                                                          GList *link_);
  71. void g_queue_delete_link (GQueue *queue,
  72.                                                          GList *link_);
3：实例
  1. #include <stdio.h>
  2. #include <glib.h>
  3. #include <glib/gprintf.h>

  5. struct map {
  6.     int key;
  7.     char *value;
  8. } m[10] = {
  9.     {0,"zero"},
  10.     {1,"one"},
  11.     {2,"two"},
  12.     {3,"three"},
  13.     {4,"four"},
  14.     {5,"five"},
  15.     {6,"six"},
  16.     {7,"seven"},
  17.     {8,"eight"},
  18.     {9,"nine"},
  19. };
  20. typedef struct map map;

  22. static void
  23. myPrintInt(gpointer p1, gpointer fmt)
  24. {
  25.     g_printf(fmt, *(gint *)p1);
  26. }

  28. static void
  29. myPrintStr(gpointer p1, gpointer fmt)
  30. {
  31.     g_printf(fmt, (gchar *)p1);
  32. }

  34. static void
  35. test_queue_1(void)
  36. {
  37. // GQueue* g_queue_new(void);
  38.     GQueue *queue = g_queue_new();
  39. // gboolean g_queue_is_empty(GQueue *queue);
  40.     gboolean b = g_queue_is_empty(queue);
  41.     g_printf("The queue should be empty now.\t\tResult: %s.\n", b ? "YES" : "NO");

  43. // void g_queue_push_tail(GQueue *queue, gpointer data);
  44.     gint i;
  45.     for (i = 0; i < sizeof (m) / sizeof (m[0]); i++)
  46.         g_queue_push_tail(queue, m[i].value);
  47.     
  48. // void g_queue_foreach(GQueue *queue, GFunc func, gpointer user_data);
  49.     g_printf("Now the queue[after push tail] :\n");
  50.     g_queue_foreach(queue, myPrintStr, "%s, ");
  51.     g_printf("\n");

  53. // guint g_queue_get_length(GQueue *queue);
  54.     g_printf("The lenght should be '%d' now.\t\tResult: %d.\n", 10, g_queue_get_length(queue));

  56. // void g_queue_reverse(GQueue *queue);
  57.     g_queue_reverse(queue);
  58.     g_printf("Now the queue[after reverse] :\n");
  59.     g_queue_foreach(queue, myPrintStr, "%s, ");
  60.     g_printf("\n");

  62. // gpointer g_queue_pop_head(GQueue *queue);
  63.     g_printf("The head should be '%s' now.\t\tResult: %s.\n", "nine", (gchar *)g_queue_pop_head(queue));

  65. // gpointer g_queue_pop_tail(GQueue *queue);
  66.     g_printf("The tail should be '%s' now.\t\tResult: %s.\n", "zero", (gchar *)g_queue_pop_tail(queue));
  67.     g_printf("Now the queue[after pop head and tail] :\n");
  68.     g_queue_foreach(queue, myPrintStr, "%s, ");
  69.     g_printf("\n");

  71. // gpointer g_queue_pop_nth(GQueue *queue, guint n);
  72.     g_printf("The head should be '%s' now.\t\tResult: %s.\n", "eight", (gchar *)g_queue_pop_nth(queue, 0));

  74. // void g_queue_push_head(GQueue *queue, gpointer data);
  75.     g_queue_push_head(queue, "zero");
  76.     g_queue_push_head(queue, "eight");

  78. // void g_queue_push_nth(GQueue *queue, gpointer data, gint n);
  79.     g_queue_push_nth(queue, "nine", 2);

  81.     g_printf("Now the queue[after push 'zero' 'eight' 'nine'] :\n");
  82.     g_queue_foreach(queue, myPrintStr, "%s, ");
  83.     g_printf("\n");

  85. // gpointer g_queue_peek_head(GQueue *queue);
  86.     g_printf("The head should be '%s' now.\t\tResult: %s.\n", "eight", (gchar *)g_queue_peek_head(queue));

  88. // gpointer g_queue_peek_tail(GQueue *queue);
  89.     g_printf("The tail should be '%s' now.\t\tResult: %s.\n", "zero", (gchar *)g_queue_peek_tail(queue));

  91. // gpointer g_queue_peek_nth(GQueue *queue, guint n);
  92.     g_printf("The head should be '%s' now.\t\tResult: %s.\n", "eight", (gchar *)g_queue_peek_nth(queue, 0));

  94. /*
  95. // void g_queue_clear(GQueue *queue);
  96.     g_queue_clear(queue);
  97.     g_printf("Now the queue[after clear] :\n");
  98.     g_queue_foreach(queue, myPrintStr, "%s, ");
  99.     g_printf("\n");
  100. */

  102. // void g_queue_free(GQueue *queue);
  103.     g_queue_free(queue);
  104. }

  106. static gint
  107. sort(gconstpointer p1, gconstpointer p2, gpointer user_data)
  108. {
  109.     gint32 a, b;
  110.     
  111.     a = *(gint*)(p1);
  112.     b = *(gint*)(p2);

  114.     return (a > b ? +1 : a == b ? 0 : -1);
  115. }

  117. static gint
  118. myCompareInt(gconstpointer p1, gconstpointer p2)
  119. {
  120.     const int *a = p1;
  121.     const int *b = p2;

  123.     return *a - *b;
  124. }


  127. static gint
  128. sort_r(gconstpointer p1, gconstpointer p2, gpointer user_data)
  129. {
  130.     gint32 a, b;
  131.     
  132.     a = *(gint*)(p1);
  133.     b = *(gint*)(p2);

  135.     return (a < b ? +1 : a == b ? 0 : -1);
  136. }

  138. static void
  139. test_queue_2(void)
  140. {
  141.     GQueue *queue = NULL;
  142. /*
  143. // void g_queue_init(GQueue *queue);
  144.     g_queue_init(queue);
  145. */
  146.     queue = g_queue_new();

  148. // void g_queue_insert_sorted(GQueue *queue, gpointer data, GCompareDataFunc func gpointer user_data);
  149.     gint i;
  150.     for (i = 0; i < sizeof (m) / sizeof (m[0]); i++)
  151.         g_queue_insert_sorted(queue, &m[i].key, sort_r, NULL);

  153.     g_printf("Now the queue[after insert sorted] :\n");
  154.     for (i = 0; i < queue->length; i++)
  155.         g_printf("%d, ", *(gint *)g_queue_peek_nth(queue, i));
  156.     g_printf("\n");

  158. // void g_queue_remove(GQueue *queue, gconstpointer data);
  159.     g_queue_remove(queue, &m[3].key);
  160.     g_printf("Now the queue[after remove '%d'] :\n", m[3].key);
  161.     for (i = 0; i < queue->length; i++)
  162.         g_printf("%d, ", *(gint *)g_queue_peek_nth(queue, i));
  163.     g_printf("\n");

  165. // GList* g_queue_find_custom(GQueue *queue, gconstpointer data, GCompareFunc func);
  166. // void g_queue_insert_before(GQueue *queue, GList *sibling, gpointer data);
  167. // void g_queue_insert_after(GQueue *queue, GList *sibling, gpointer data);
  168.     g_queue_insert_before(queue, g_queue_find_custom(queue, &m[5].key, myCompareInt), &m[3].key);
  169.     g_queue_insert_after(queue, g_queue_find_custom(queue, &m[5].key, myCompareInt), &m[3].key);

  171.     g_printf("Now the queue[after insert '%d' around '%d'] :\n", m[3].key, m[5].key);
  172.     g_queue_foreach(queue, myPrintInt, "%d, ");
  173.     g_printf("\n");

  175. // void g_queue_sort(GQueue *queue, GCompareDataFunc compare, gpointer user_data);
  176.     g_queue_sort(queue, sort, NULL);

  178.     g_printf("Now the queue[sorted] :\n");
  179.     g_queue_foreach(queue, myPrintInt, "%d, ");
  180.     g_printf("\n");

  182. // GQueue* g_queue_copy(GQueue *queue);
  183.     GQueue *q = g_queue_copy(queue);
  184.     g_printf("Now the queue[copy] :\n");
  185.     g_queue_foreach(q, myPrintInt, "%d, ");
  186.     g_printf("\n");

  188. // void g_queue_remove_all(GQueue *queue, gconstpointer data);
  189.     g_queue_remove_all(q, &m[3].key);
  190.     g_printf("Now the queue[remove '%d'] :\n", m[3].key);
  191.     g_queue_foreach(q, myPrintInt, "%d, ");
  192.     g_printf("\n");

  194.     g_queue_free(q);
  195.     g_queue_free(queue);
  196. }

  198. int
  199. main(void)
  200. {
  201.     printf("BEGIN:\n************************************************************\n");
  202.     printf("\n------------------------------------------------------------\ntest_queue_1:\n");
  203.     test_queue_1();
  204.     printf("------------------------------------------------------------\n");
  205.     printf("\n------------------------------------------------------------\ntest_queue_2:\n");
  206.     test_queue_2();
  207.     printf("------------------------------------------------------------\n");
  208.     printf("\n************************************************************\nDONE\n");

  210.     return 0;
  211. }

4：结果

  1. [xied1@soho use]$ gcc `pkg-config --cflags --libs glib-2.0` -Wall -O2 -o queue queue.c
  2. [xied1@soho use]$ ./queue
  3. BEGIN:
  4. ************************************************************

  6. ------------------------------------------------------------
  7. test_queue_1:
  8. The queue should be empty now. Result: YES.
  9. Now the queue[after push tail] :
  10. zero, one, two, three, four, five, six, seven, eight, nine,
  11. The lenght should be '10' now. Result: 10.
  12. Now the queue[after reverse] :
  13. nine, eight, seven, six, five, four, three, two, one, zero,
  14. The head should be 'nine' now. Result: nine.
  15. The tail should be 'zero' now. Result: zero.
  16. Now the queue[after pop head and tail] :
  17. eight, seven, six, five, four, three, two, one,
  18. The head should be 'eight' now. Result: eight.
  19. Now the queue[after push 'zero' 'eight' 'nine'] :
  20. eight, zero, nine, seven, six, five, four, three, two, one,
  21. The head should be 'eight' now. Result: eight.
  22. The tail should be 'zero' now. Result: one.
  23. The head should be 'eight' now. Result: eight.
  24. ------------------------------------------------------------

  26. ------------------------------------------------------------
  27. test_queue_2:
  28. Now the queue[after insert sorted] :
  29. 9, 8, 7, 6, 5, 4, 3, 2, 1, 0,
  30. Now the queue[after remove '3'] :
  31. 9, 8, 7, 6, 5, 4, 2, 1, 0,
  32. Now the queue[after insert '3' around '5'] :
  33. 9, 8, 7, 6, 3, 5, 3, 4, 2, 1, 0,
  34. Now the queue[sorted] :
  35. 0, 1, 2, 3, 3, 4, 5, 6, 7, 8, 9,
  36. Now the queue[copy] :
  37. 0, 1, 2, 3, 3, 4, 5, 6, 7, 8, 9,
  38. Now the queue[remove '3'] :
  39. 0, 1, 2, 4, 5, 6, 7, 8, 9,
  40. ------------------------------------------------------------

  42. ************************************************************
  43. DONE

5：小结



上一篇：Glib实例学习（5）平衡二叉树
下一篇：Glib实例学习（7）关系/元组