Chinaunix首页 | 论坛 | 博客

onezeroone的ChinaUnix博客onezeroone.blog.chinaunix.net

首页　| 　博文目录　| 　关于我

onezeroone

  • 博客访问： 368681
  • 博文数量： 100
  • 博客积分： 2500
  • 博客等级： 大尉
  • 技术积分： 1209
  • 用 户 组： 普通用户
  • 注册时间： 2011-04-15 21:24
文章分类

全部博文（100）

文章存档

2011年（100）

我的朋友
最近访客
推荐博文
相关博文
Glib实例学习（5）平衡二叉树

分类： C/C++

2011-07-03 13:15:18

1：概述
   平衡二叉树：对有序序列的一种优化，可以用来高效的查找和遍历等的一种树形结构。

2：原型

  1. GTree* g_tree_new (GCompareFunc key_compare_func);
  2. GTree* g_tree_new_with_data (GCompareDataFunc key_compare_func,
  3.                                                          gpointer key_compare_data);
  4. GTree* g_tree_new_full (GCompareDataFunc key_compare_func,
  5.                                                          gpointer key_compare_data,
  6.                                                          GDestroyNotify key_destroy_func,
  7.                                                          GDestroyNotify value_destroy_func);
  8. void g_tree_insert (GTree *tree,
  9.                                                          gpointer key,
  10.                                                          gpointer value);
  11. void g_tree_replace (GTree *tree,
  12.                                                          gpointer key,
  13.                                                          gpointer value);
  14. gint g_tree_nnodes (GTree *tree);
  15. gint g_tree_height (GTree *tree);
  16. gpointer g_tree_lookup (GTree *tree,
  17.                                                          gconstpointer key);
  18. gboolean g_tree_lookup_extended (GTree *tree,
  19.                                                          gconstpointer lookup_key,
  20.                                                          gpointer *orig_key,
  21.                                                          gpointer *value);
  22. void g_tree_foreach (GTree *tree,
  23.                                                          GTraverseFunc func,
  24.                                                          gpointer user_data);
  25. gpointer g_tree_search (GTree *tree,
  26.                                                          GCompareFunc search_func,
  27.                                                          gconstpointer user_data);
  28. gboolean g_tree_remove (GTree *tree,
  29.                                                          gconstpointer key);
  30. gboolean g_tree_steal (GTree *tree,
  31.                                                          gconstpointer key);
  32. void g_tree_destroy (GTree *tree);

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 gint
  23. myCompare(gconstpointer p1, gconstpointer p2)
  24. {
  25.     const char *a = p1;
  26.     const char *b = p2;

  28.     return *a - *b;
  29. }

  31. static gint
  32. mySearch(gconstpointer p1, gconstpointer p2)
  33. {
  34.     return myCompare(p1, p2);
  35. }

  37. static gint
  38. myTraverse(gpointer key, gpointer value, gpointer fmt)
  39. {
  40.     g_printf(fmt, *(gint*)key, (gchar*)value);
  41.     
  42.     return FALSE;
  43. }

  45. static void
  46. test_avl_tree(void)
  47. {
  48.     GTree *tree;
  49.     gint i;

  51. // GTree* g_tree_new(GCompareFunc key_compare_func);
  52.     tree = g_tree_new(myCompare);
  53.     
  54. // void g_tree_insert(GTree *tree, gpointer key, gpointer value);
  55.     for (i = 0; i < sizeof(m)/sizeof(m[0]); i++)
  56.         g_tree_insert(tree, &m[i].key, m[i].value);

  58. // void g_tree_foreach(GTree *tree, GTraverseFunc func, gpointer user_data);
  59.     g_printf("Now the tree:\n");
  60.     g_tree_foreach(tree, myTraverse, "Key:\t%d\t\tVaule:\t%s\n");
  61. // gint g_tree_nnodes(GTree *tree);
  62.     g_printf("The tree should have '%d' items now.\t\tResult: %d.\n", 10, g_tree_nnodes(tree));
  63. // gint g_tree_height(GTree *tree);
  64.     g_printf("The height of tree is '%d' now.\n", g_tree_height(tree));

  66. // void g_tree_replace(GTree *tree, gpointer key, gpointer value);
  67.     g_tree_replace(tree, &m[3].key, "3333");
  68.     g_printf("Now the vaule of '%d' should be '3333' now.\n", m[3].key);
  69.     g_tree_foreach(tree, myTraverse, "Key:\t%d\t\tVaule:\t%s\n");

  71.     gchar *tmp = NULL;
  72. // gpointer g_tree_lookup(GTree *tree, gconstpointer key);
  73.     g_printf("Now the vaule of '%d' should be '%s' now[lookup].\n",
  74.             m[3].key,
  75.             (tmp = (gchar *)g_tree_lookup(tree, &m[3].key)) != NULL ? tmp : NULL);

  77. // gboolean g_tree_remove(GTree *tree, gconstpointer key);
  78.     gboolean b = g_tree_remove(tree, &m[3].key);
  79.     g_printf("The key '%d' has %sbeen found and removed now.\n", m[3].key, b ? "" : "NOT");

  81. // gpointer g_tree_search(GTree *tree, GCompareFunc search_func, gconstpointer user_data);
  82.     g_printf("Now the vaule which should be removed of '%d' should be '%s' now[search].\n",
  83.             m[3].key,
  84.             (tmp = (gchar *)g_tree_search(tree, mySearch, &m[3].key)) != NULL ? tmp : NULL);

  86.     g_printf("Now the tree look like:\n");
  87.     g_tree_foreach(tree, myTraverse, "Key:\t%d\t\tVaule:\t%s\n");

  89. // void g_tree_destroy(GTree *tree);
  90.     g_tree_destroy(tree);
  91. }

  93. int
  94. main(void)
  95. {
  96.     printf("BEGIN:\n************************************************************\n");

  98.     test_avl_tree();

  100.     printf("\n************************************************************\nDONE\n");

  102.     return 0;
  103. }

4：结果
  1. BEGIN:
  2. ************************************************************
  3. Now the tree:
  4. Key: 0 Vaule: zero
  5. Key: 1 Vaule: one
  6. Key: 2 Vaule: two
  7. Key: 3 Vaule: three
  8. Key: 4 Vaule: four
  9. Key: 5 Vaule: five
  10. Key: 6 Vaule: six
  11. Key: 7 Vaule: seven
  12. Key: 8 Vaule: eight
  13. Key: 9 Vaule: nine
  14. The tree should have '10' items now. Result: 10.
  15. The height of tree is '4' now.
  16. Now the vaule of '3' should be '3333' now.
  17. Key: 0 Vaule: zero
  18. Key: 1 Vaule: one
  19. Key: 2 Vaule: two
  20. Key: 3 Vaule: 3333
  21. Key: 4 Vaule: four
  22. Key: 5 Vaule: five
  23. Key: 6 Vaule: six
  24. Key: 7 Vaule: seven
  25. Key: 8 Vaule: eight
  26. Key: 9 Vaule: nine
  27. Now the vaule of '3' should be '3333' now[lookup].
  28. The key '3' has been found and removed now.
  29. Now the vaule which should be removed of '3' should be '(null)' now[search].
  30. Now the tree look like:
  31. Key: 0 Vaule: zero
  32. Key: 1 Vaule: one
  33. Key: 2 Vaule: two
  34. Key: 4 Vaule: four
  35. Key: 5 Vaule: five
  36. Key: 6 Vaule: six
  37. Key: 7 Vaule: seven
  38. Key: 8 Vaule: eight
  39. Key: 9 Vaule: nine

  41. ************************************************************
  42. DONE

5：小结
  • 创建： g_tree_new()
  • 插入： g_tree_insert()
  • 查找： g_tree_lookup() g_tree_search()
  • 删除： g_tree_remove()
  • 属性： g_tree_nnodes() g_tree_height()
  • 遍历： g_tree_foreach()
  • 销毁： g_tree_destroy()

阅读(3325) | 评论(0) | 转发(1) |
0

上一篇：CMake 实例学习（4）动/静态库共存

下一篇：Glib实例学习（6）双端队列

给主人留下些什么吧！~~
关于我们 | 关于IT168 | 联系方式 | 广告合作 | 法律声明 | 免费注册

Copyright 2001-2010 ChinaUnix.net All Rights Reserved 北京皓辰网域网络信息技术有限公司. 版权所有

感谢所有关心和支持过ChinaUnix的朋友们

16024965号-6