正文

如何在 C 中实现多分支树结构

 2023-03-16  216

关键词：

【中文标题】如何在 C 中实现多分支树结构【英文标题】：How to implement a multibranch tree structure in C 【发布时间】：2011-08-27 13:14:14 【问题描述】：

我很久没有用 C 写代码了。我正在尝试做一棵多叶树。我正在尝试将 C# trie 实现转换为 C，以便使用 CUDA 在 GPU 上运行它。但我一直坚持这一点。你能帮我吗？

我的节点实现如下：

struct Node2 
char *Key;
char *ConsAlterKey;
char *MasterKey;
bool VowelDeletion;
char *Data;
char *MasterData;
Node2 *Childs;
int ChildCount;
;

这是我将节点添加到 trie 的函数：

void AddAsChildren2(Node2 *Trie,int count)


//Trie->Childs=new Node2[count];
Trie->Childs=(Node2 *)malloc(sizeof(Node2)*count);

for(int i=0;i<count;i++)

    Trie->Childs[i].Key= GetKey();
    Trie->Childs[i].ConsAlterKey=GetConsAlterKey();
    Trie->Childs[i].MasterKey=GetMasterKey();
    Trie->Childs[i].VowelDeletion=GetVowelDeletion();
    Trie->Childs[i].Data=GetData();
    Trie->Childs[i].MasterData=GetMasterData();
    Trie->Childs[i].ChildCount=GetChildCount();

    if(Trie->Childs[i].ChildCount> 0)
    
        AddAsChildren2(&(Trie->Childs[i]),Trie->Childs[i].ChildCount);

我在主函数中这样称呼它：

Node2 NodeNew;
    .
    .
    . 
AddAsChildren2(&NodeNew,NodeNew->ChildCount);
TraverseTree2(&NodeNew);

但是当我尝试遍历树时，我会得到错误的值，有时还会出现异常。（可能是子节点的内存分配问题）

我在这里做错了什么？

Ps：第一个节点有子节点，我没有分配值的问题，所以忽略“getter”函数。我已经更改了它们以简化代码。我的问题是代码完成这部分后我丢失了值。

感谢您的快速响应。我从文件中读取值。

文件的结构是这样的。

如果一行/项目没有子节点，则以“>”结尾，否则以 ChildCount 值结尾。这里“-”字符表示 NULL 值。

< root - - - - - 2
 < a - - False - - 4
  < aö - - False 184 - > 
  < dfı - - False 188 - > 
  < et ed - False 189 - 3 
   < aö - - False 184 - > 
   < dfı - - False 188 - > 
   < k ğ - False 191 - > 
  >
  < k ğ - False 191 - > 
 >
 < a - - False - - 4
  < aö - - False 184 - > 
  < dfı - - False 188 - > 
  < et ed - False 189 - 3 
   < aö - - False 184 - > 
   < dfı - - False 188 - > 
   < k ğ - False 191 - > 
  >
  < k ğ - False 191 - > 
 >
>

而不是我的代码的简化版本如下：

void AddAsChildren2(Node2 *Trie,FILE *fp,int count)


  char string[50];
  char *line=NULL;
  char *Temp;

  Trie->Childs=(Node2 *)malloc(sizeof(Node2)*count);
  //Trie->Childs=new Node2[count];


  for(int i=0;i<count;i++)
  
if(fgets(string,50,fp))

        line=strtok(string," ");

    if(strcmp (line,"<")==0)
    
        line=strtok( NULL, " ");
        Trie->Childs[i].Key= (strcmp(line,"-")==0?"":line);

        line=strtok( NULL, " ");
        Trie->Childs[i].ConsAlterKey=(strcmp(line,"-")==0?"":line);

        line=strtok( NULL, " ");
        Trie->Childs[i].MasterKey=(strcmp(line,"-")==0?"":line);

        line=strtok( NULL, " ");
        Trie->Childs[i].VowelDeletion=(strcmp(line,"-")==0?"":line);

        line=strtok( NULL, " ");
        Trie->Childs[i].Data=(strcmp(line,"-")==0?"":line);

        line=strtok( NULL, " ");
        Trie->Childs[i].MasterData=(strcmp(line,"-")==0?"":line);


        Temp = strtok( NULL, " ");

        if(strcmp(Temp,">")==0)
        
                             //ends with >
            Trie->Childs[i].ChildCount=0;
        
        else if((strcmp(Temp,"\n")!=0)&&(strlen(Temp)> 0))
        
                           //ends with childcount value so it have childs

            Trie->Childs[i].ChildCount=atoi(Temp);

            AddAsChildren2(&(Trie->Childs[i]),fp,Trie->Childs[i].ChildCount);

遍历函数如下：

void traversetree2(Node2 *tree)


printf("Key %s\n",tree->Key);
printf("ConsAlterKey %s\n",tree->ConsAlterKey);
printf("MasterKey %s\n",tree->MasterKey);

printf("Data %s\n",tree->Data);
printf("MasterData %s\n",tree->MasterData);

if(tree->ChildCount>0)

    for(int i=0;i<tree->ChildCount;i++)
    
        traversetree2(&(tree->Childs[i]));

输出是：

Key root
ConsAlterKey
MasterKey
Data
MasterData
Key ╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠
╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠
ConsAlterKey
MasterKey
Data
MasterData
Key ╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠░÷E
ConsAlterKey
MasterKey
Data ╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠░÷E
MasterData
Key ╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠░÷E
ConsAlterKey
MasterKey
Data ╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠░÷E
MasterData
Key ╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠░÷E
ConsAlterKey ╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠░÷E
MasterKey
Data ╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠░÷E
MasterData
Key ╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠
╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠
╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠§E
ConsAlterKey
MasterKey
Data ╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠
╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠
╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠§E
MasterData
Key ╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠
╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠
╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠§E
ConsAlterKey
MasterKey
Data ╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠
╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠
╠╠╠╠╠╠╠╠╠╠╠╠╠╠§E
MasterData
Key ╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠
╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠
╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠§E
ConsAlterKey ╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠
╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠
╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠§E
MasterKey
Data ╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠
╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠
╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠╠§E
MasterData

【问题讨论】：

我认为您显示的代码没有任何问题。您是否也在某个时候释放了尝试？你能显示回溯吗？ 【参考方案1】：

啊，使用更多代码很容易：您的问题是char string[50] 是一个局部变量，并且您将许多指针保存到该局部数组中，当AddAsChildren2 返回时这些指针会丢失。根据您是否需要释放此结构，您可以strdup() 整行然后从中保存令牌或strdup() 每个单独的令牌（以简化释放）。

【讨论】：

非常感谢；我不能说我是多么感激它。你为我节省了几个小时。请原谅我的新手问题，但我还有一个问题要问你。我已将Trie->Childs[i].Key= (strcmp(line,"-")==0?"":line) 更改为Trie->Childs[i].Key= (strcmp(line,"-")==0?"":**strdup(line)**)。像这样将这些值分配给节点的属性后，我应该立即释放它们吗？我的意思是我应该在每次分配后使用LocalFree(line) 吗？不，strdup(line) 就可以了。如果您想释放整个结构，挑战就来了。你不能释放你的文字 "" 字符串。最好使用strdup( cond ? "" : line )，以便分配每个字符串，如果你曾经处理过整个 Trie，你可以free(Trie->Childs[i].Key)。

如何在 PostgreSQL 中实现多对多关系？

】如何在PostgreSQL中实现多对多关系？【英文标题】：Howtoimplementamany-to-manyrelationshipinPostgreSQL?【发布时间】：2012-04-0502:14:21【问题描述】：我相信标题是不言自明的。如何在PostgreSQL中创建表结构以建立多对多关系。我的例子：Pro... 查看详情

如何在angular js中实现多路由

】如何在angularjs中实现多路由【英文标题】：Howtoachievemultipleroutinginangularjs【发布时间】：2018-11-2223:10:07【问题描述】：我在AngularJS中练习routing。到目前为止，我已经研究了2页路由，但现在我想实现3页路由。(function()\'usestrict\';... 查看详情

如何在 laravel 护照中实现多身份验证

】如何在laravel护照中实现多身份验证【英文标题】：howtoimplementmultiauthinlaravelpassport【发布时间】：2018-09-0120:51:57【问题描述】：我有两个用户admin/user我想验证这两个用户的api，它适用于一个用户，但不适用于管理员看看我尝试... 查看详情

我应该如何在角度材料中实现多项选择选项？

】我应该如何在角度材料中实现多项选择选项？【英文标题】：HowamIsupposedtoimplementmultipleselectoptioninangular-material?【发布时间】：2015-04-2317:22:12【问题描述】：我已经检查了文档和演示，但是唉！！我还没有找到任何关于使用angul... 查看详情

如何在 Firebase 身份验证中实现多用户帐户登录和切换？

】如何在Firebase身份验证中实现多用户帐户登录和切换？【英文标题】：HowdoIwantimplementmultipleuseraccountloginandswitchinginFirebaseAuthentication?【发布时间】：2018-05-0713:08:55【问题描述】：在GmailAndroid应用中，您可以在用户帐户视图上滑... 查看详情

如何使用 Java Spring 在 MySql 中实现多租户 [关闭]

】如何使用JavaSpring在MySql中实现多租户[关闭]【英文标题】：HowcanIachievemultitenancyinMySqlbyusingJavaSpring[closed]【发布时间】：2018-02-2605:13:48【问题描述】：如何使用MySqlJavaSpring最佳实践实现多租户，并建议使用任何其他数据库代替MyS... 查看详情

如何在 Sonata Media Bundle 中实现多对多关系

】如何在SonataMediaBundle中实现多对多关系【英文标题】：Howtoimplementmany-to-manyrelationshipsinSonataMediaBundle【发布时间】：2012-07-2117:08:54【问题描述】：我正在尝试将SonataMediaBundle与另一个实体相关联：Products与ManyToMany关系。架构和关... 查看详情

请问如何在delphi中实现多选打印功能！

参考技术A标签打印请问如安在delphi中实现多选打印功能！具体的情况是：DBgrid傍边有很多字段，有很多记录请求做到：第一步，记录的若干是动态的，但要能选择记录打印，数量不限。第二步，字段有很多，再上一步的基本上... 查看详情

如何在gridview中实现多选

GridView实现跨页多选，参考如下：JS前台：//GridView中实现多选效果function CheckAllC(oCheckbox) var GridView1 = document.getElementById(\'gvDataList\'); for (i = 1; i < gvDataList.rows.length; i++) GridView1.rows[i].cells[0].getEleme... 查看详情

如何使用 Visual Studio for Mac 在 Xamarin.Forms 中实现多目标？

】如何使用VisualStudioforMac在Xamarin.Forms中实现多目标？【英文标题】：HowtomultitargetinXamarin.FormswithVisualStudioforMac?【发布时间】：2019-07-2323:37:14【问题描述】：我开始创建一个.NETStandardLibrary并打算创建一个NuGet-但后来发现我还需要... 查看详情

在 iPad App 中实现多用户聊天

...登录该应用的用户发送文本或音频片段。我正在寻找有关如何实现这一点的指针。我阅读了许多文章。我已经缩小到1)XMPP(Jabber)和2)网络套接字基于解决方案查看详情

如何在solr中实现多core查询

参考技术A　　/****多核查询测试*@throwsException*/publicstaticvoidqueryMultiCore()throwsException//查询a和b下面的数据，HttpSolrClientsc=newHttpSolrClient("http://192.168.1.215:8983/solr/a");Stringshards="192.168.1.215:8983/solr/a,192.168.1.214:8983/solr/b";Mod... 查看详情

如何在 C# 中实现交互式决策树

】如何在C#中实现交互式决策树【英文标题】：HowtoimplementaninteractivedecisiontreeinC#【发布时间】：2020-02-0312:58:31【问题描述】：我需要允许用户通过在屏幕上显示的两个简单选项之间进行选择来选择自己的路径，以便进入下一组选... 查看详情

java示例代码_在Java中实现多线程池

java示例代码_在Java中实现多线程池查看详情

使用消息传递接口在 Python 中实现多处理 [关闭]

】使用消息传递接口在Python中实现多处理[关闭]【英文标题】：ImplementmultiprocessinginPythonwithamessagepassinginterface[closed]【发布时间】：2021-03-1204:49:55【问题描述】：我正在尝试将一些JavaScript代码转换为Python，但是JavaScript以异步方式... 查看详情

如何在 Haskell 中实现 B+ 树？

】如何在Haskell中实现B+树？【英文标题】：HowtoimplementB+treeinHaskell?【发布时间】：2013-12-1701:14:23【问题描述】：B+树的叶节点链接在一起。将B+树的指针结构视为有向图，它不是循环的。但是忽略指针的方向并将其视为无向的叶... 查看详情

我可以使用优化实验在 Anylogic 中实现多目标优化问题吗？

】我可以使用优化实验在Anylogic中实现多目标优化问题吗？【英文标题】：CanIimplementamultiobjectiveoptimizationprobleminAnylogicusingoptimizationexperiment?【发布时间】：2021-02-1517:06:14【问题描述】：我正在尝试在Anylogic中使用基于Anylogic代理... 查看详情

如何在swift中实现多播套接字？(代码片段)

...用Perfect-Net模块也没有运气，也没有使用CocoaAsyncSocket。我如何使用swift实现发送方和接收方？任何可能的片段都会非常有用。我一直在阅读关于多播的内容，当涉及到接收器时，我注意到在大多数语言（即java或c＃）中，接收器... 查看详情