不学网

 找回密码
 立即注册

只需一步,快速开始

手机号码,快捷登录

查看: 451|回复: 0

[c/c++] [C数据结构]通用树(复用链表)

[复制链接]
j2cat 发表于 2018-1-6 19:47:39 | 显示全部楼层 |阅读模式

马上注册,结交更多好友,享用更多功能,让你轻松玩转社区。

您需要 登录 才可以下载或查看,没有帐号?立即注册

x
GTree.h
  1. #ifndef _GTREE_H_
  2. #define _GTREE_H_

  3. typedef void GTree;
  4. typedef void GTreeData;
  5. typedef void (GTree_Printf)(GTreeData*);

  6. GTree* GTree_Create();

  7. void GTree_Destroy(GTree* tree);

  8. void GTree_Clear(GTree* tree);

  9. int GTree_Insert(GTree* tree, GTreeData* data, int pPos);

  10. GTreeData* GTree_Delete(GTree* tree, int pos);

  11. GTreeData* GTree_Get(GTree* tree, int pos);

  12. GTreeData* GTree_Root(GTree* tree);

  13. int GTree_Height(GTree* tree);

  14. int GTree_Count(GTree* tree);

  15. int GTree_Degree(GTree* tree);

  16. void GTree_Display(GTree* tree, GTree_Printf* pFunc, int gap, char div);

  17. int GTree_Search(GTree* tree, GTreeData* data, GTree_Printf* pFunc);

  18. #endif

复制代码
GTree.c
  1. #include <stdio.h>
  2. #include <malloc.h>
  3. #include "GTree.h"
  4. #include "LinkList.h"


  5. typedef struct _tag_GTreeNode GTreeNode;
  6. struct _tag_GTreeNode
  7. {
  8.         GTreeData* data;
  9.         GTreeNode* parent;
  10.         LinkList* child;
  11. };


  12. typedef struct _tag_TLNode TLNode;
  13. struct _tag_TLNode
  14. {
  15.         TLinkListNode header;
  16.         GTreeNode* node;
  17. };


  18. static void recursive_display(GTreeNode* node, GTree_Printf* pFunc, int format, int gap, char div)
  19. {
  20.         int i = 0;

  21.         if ((node != NULL) && (pFunc != NULL))
  22.         {
  23.                 for (i = 0; i<format; i++)
  24.                 {
  25.                         printf("%c", div);
  26.                 }

  27.                 pFunc(node->data);

  28.                 printf("\n");

  29.                 for (i = 0; i<LinkList_Length(node->child); i++)
  30.                 {
  31.                         TLNode* trNode = (TLNode*)LinkList_Get(node->child, i);

  32.                         recursive_display(trNode->node, pFunc, format + gap, gap, div);
  33.                 }
  34.         }
  35. }

  36. static void recursive_delete(LinkList* list, GTreeNode* node)
  37. {
  38.         if ((list != NULL) && (node != NULL))
  39.         {
  40.                 GTreeNode* parent = node->parent;
  41.                 int index = -1;
  42.                 int i = 0;

  43.                 for (i = 0; i<LinkList_Length(list); i++)
  44.                 {
  45.                         TLNode* trNode = (TLNode*)LinkList_Get(list, i);

  46.                         if (trNode->node == node)
  47.                         {
  48.                                 LinkList_Delete(list, i);

  49.                                 free(trNode);

  50.                                 index = i;

  51.                                 break;
  52.                         }
  53.                 }

  54.                 if (index >= 0)
  55.                 {
  56.                         if (parent != NULL)
  57.                         {
  58.                                 for (i = 0; i<LinkList_Length(parent->child); i++)
  59.                                 {
  60.                                         TLNode* trNode = (TLNode*)LinkList_Get(parent->child, i);

  61.                                         if (trNode->node == node)
  62.                                         {
  63.                                                 LinkList_Delete(parent->child, i);

  64.                                                 free(trNode);

  65.                                                 break;
  66.                                         }
  67.                                 }
  68.                         }

  69.                         while (LinkList_Length(node->child) > 0)
  70.                         {
  71.                                 TLNode* trNode = (TLNode*)LinkList_Get(node->child, 0);

  72.                                 recursive_delete(list, trNode->node);
  73.                         }

  74.                         LinkList_Destroy(node->child);

  75.                         free(node);
  76.                 }
  77.         }
  78. }

  79. static int recursive_height(GTreeNode* node)
  80. {
  81.         int ret = 0;

  82.         if (node != NULL)
  83.         {
  84.                 int subHeight = 0;
  85.                 int i = 0;

  86.                 for (i = 0; i<LinkList_Length(node->child); i++)
  87.                 {
  88.                         TLNode* trNode = (TLNode*)LinkList_Get(node->child, i);

  89.                         subHeight = recursive_height(trNode->node);

  90.                         if (ret < subHeight)
  91.                         {
  92.                                 ret = subHeight;
  93.                         }
  94.                 }

  95.                 ret = ret + 1;
  96.         }

  97.         return ret;
  98. }

  99. static int recursive_degree(GTreeNode* node)
  100. {
  101.         int ret = -1;

  102.         if (node != NULL)
  103.         {
  104.                 int subDegree = 0;
  105.                 int i = 0;

  106.                 ret = LinkList_Length(node->child);

  107.                 for (i = 0; i<LinkList_Length(node->child); i++)
  108.                 {
  109.                         TLNode* trNode = (TLNode*)LinkList_Get(node->child, i);

  110.                         subDegree = recursive_degree(trNode->node);

  111.                         if (ret < subDegree)
  112.                         {
  113.                                 ret = subDegree;
  114.                         }
  115.                 }
  116.         }

  117.         return ret;
  118. }

  119. GTree* GTree_Create()
  120. {
  121.         return LinkList_Create();
  122. }

  123. void GTree_Destroy(GTree* tree)
  124. {
  125.         GTree_Clear(tree);
  126.         LinkList_Destroy(tree);
  127. }

  128. void GTree_Clear(GTree* tree)
  129. {
  130.         GTree_Delete(tree, 0);
  131. }

  132. int GTree_Insert(GTree* tree, GTreeData* data, int pPos)
  133. {
  134.         LinkList* list = (LinkList*)tree;
  135.         int ret = (list != NULL) && (data != NULL) && (pPos < LinkList_Length(list));

  136.         if (ret)
  137.         {
  138.                 TLNode* trNode = (TLNode*)malloc(sizeof(TLNode));
  139.                 TLNode* cldNode = (TLNode*)malloc(sizeof(TLNode));
  140.                 TLNode* pNode = (TLNode*)LinkList_Get(list, pPos);
  141.                 GTreeNode* cNode = (GTreeNode*)malloc(sizeof(GTreeNode));

  142.                 ret = (trNode != NULL) && (cldNode != NULL) && (cNode != NULL);

  143.                 if (ret)
  144.                 {
  145.                         cNode->data = data;
  146.                         cNode->parent = NULL;
  147.                         cNode->child = LinkList_Create();

  148.                         trNode->node = cNode;
  149.                         cldNode->node = cNode;

  150.                         LinkList_Insert(list, (TLinkListNode*)trNode, LinkList_Length(list));

  151.                         if (pNode != NULL)
  152.                         {
  153.                                 cNode->parent = pNode->node;

  154.                                 LinkList_Insert(pNode->node->child, (TLinkListNode*)cldNode, LinkList_Length(pNode->node->child));
  155.                         }
  156.                 }
  157.                 else
  158.                 {
  159.                         free(trNode);
  160.                         free(cldNode);
  161.                         free(cNode);
  162.                 }
  163.         }

  164.         return ret;
  165. }

  166. GTreeData* GTree_Delete(GTree* tree, int pos)
  167. {
  168.         TLNode* trNode = (TLNode*)LinkList_Get(tree, pos);
  169.         GTreeData* ret = NULL;

  170.         if (trNode != NULL)
  171.         {
  172.                 ret = trNode->node->data;

  173.                 recursive_delete(tree, trNode->node);
  174.         }

  175.         return ret;
  176. }

  177. GTreeData* GTree_Get(GTree* tree, int pos)
  178. {
  179.         TLNode* trNode = (TLNode*)LinkList_Get(tree, pos);
  180.         GTreeData* ret = NULL;

  181.         if (trNode != NULL)
  182.         {
  183.                 ret = trNode->node->data;
  184.         }

  185.         return ret;
  186. }

  187. GTreeData* GTree_Root(GTree* tree)
  188. {
  189.         return GTree_Get(tree, 0);
  190. }

  191. int GTree_Height(GTree* tree)
  192. {
  193.         TLNode* trNode = (TLNode*)LinkList_Get(tree, 0);
  194.         int ret = 0;

  195.         if (trNode != NULL)
  196.         {
  197.                 ret = recursive_height(trNode->node);
  198.         }

  199.         return ret;
  200. }

  201. int GTree_Count(GTree* tree)
  202. {
  203.         return LinkList_Length(tree);
  204. }

  205. int GTree_Degree(GTree* tree)
  206. {
  207.         TLNode* trNode = (TLNode*)LinkList_Get(tree, 0);
  208.         int ret = -1;

  209.         if (trNode != NULL)
  210.         {
  211.                 ret = recursive_degree(trNode->node);
  212.         }

  213.         return ret;
  214. }

  215. void GTree_Display(GTree* tree, GTree_Printf* pFunc, int gap, char div)
  216. {
  217.         TLNode* trNode = (TLNode*)LinkList_Get(tree, 0);

  218.         if ((trNode != NULL) && (pFunc != NULL))
  219.         {
  220.                 recursive_display(trNode->node, pFunc, 0, gap, div);
  221.         }
  222. }

  223. static void recursive_search(GTreeNode* node, GTree_Printf* pFunc) {
  224.         if (NULL != node) {
  225.                 recursive_search(node->parent, pFunc);
  226.                 pFunc(node->data);
  227.         }


  228. }

  229. int GTree_Search(GTree* tree, GTreeData* data, GTree_Printf* pFunc) {
  230.         int ret = -1;
  231.         for (int i = 0; i < LinkList_Length(tree); i++) {
  232.                 TLNode* trNode = (TLNode*)LinkList_Get(tree, i);
  233.                 if (data == trNode->node->data) {
  234.                         ret = i;
  235.                         recursive_search(trNode->node, pFunc);
  236.                         break;
  237.                 }
  238.         }

  239.         return ret;
  240. }
复制代码
main.c
  1. #include <stdio.h>
  2. #include "GTree.h"

  3. void printf_data(GTreeData* data)
  4. {
  5.         printf("%c", (int)data);
  6. }

  7. int main(int argc, char *argv[])
  8. {
  9.         GTree* tree = GTree_Create();
  10.         int i = 0;

  11.         GTree_Insert(tree, (GTreeData*)'A', -1);
  12.         GTree_Insert(tree, (GTreeData*)'B', 0);
  13.         GTree_Insert(tree, (GTreeData*)'C', 0);
  14.         GTree_Insert(tree, (GTreeData*)'D', 0);
  15.         GTree_Insert(tree, (GTreeData*)'E', 1);
  16.         GTree_Insert(tree, (GTreeData*)'F', 1);
  17.         GTree_Insert(tree, (GTreeData*)'H', 3);
  18.         GTree_Insert(tree, (GTreeData*)'I', 3);
  19.         GTree_Insert(tree, (GTreeData*)'J', 3);

  20.         /*printf("Tree Height: %d\n", GTree_Height(tree));
  21.         printf("Tree Degree: %d\n", GTree_Degree(tree));
  22.         printf("Full Tree:\n");

  23.         GTree_Display(tree, printf_data, 2, ' ');

  24.         printf("Get Tree Data:\n");

  25.         for (i = 0; i<GTree_Count(tree); i++)
  26.         {
  27.                 printf_data(GTree_Get(tree, i));
  28.                 printf("\n");
  29.         }

  30.         printf("Get Root Data:\n");

  31.         printf_data(GTree_Root(tree));

  32.         printf("\n");

  33.         GTree_Delete(tree, 3);

  34.         printf("After Deleting D:\n");

  35.         GTree_Display(tree, printf_data, 2, '-');*/

  36.         //GTree_Clear(tree);

  37.         //printf("After Clearing Tree:\n");

  38.         //GTree_Display(tree, printf_data, 2, '.');

  39.         GTree_Search(tree, (GTreeData*)'I', printf_data);

  40.         GTree_Destroy(tree);
  41.         getchar();
  42.         return 0;
  43. }
复制代码


回复

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

QQ|手机版|小黑屋|不学网

GMT+8, 2018-9-19 04:53

Powered by Discuz! X3.4

© 2001-2017 Comsenz Inc.

快速回复 返回顶部 返回列表