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

时间：2022-09-28 14:32:05

I haven't written code in C for long time. Im trying to do a multi-leaf tree.Im trying to convert a C# trie implementation to C in order to run it on GPU with CUDA.But i've stuck on this.Can you help me?

我很久没有用C写代码了。我想做多叶树。我正在尝试将c# trie实现转换为C，以便与CUDA一起在GPU上运行。但我坚持了下来。你能帮我吗?

My node implementation as follows:

我的节点实现如下:

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

And here is my function that adds nodes to trie:

这是我在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);
    }
}
}

which i call it from main function like this:

我把它叫做主函数

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

But when i try to traverse tree i get wrong values and sometimes exceptions.(Possibly memory allocation problem of child nodes)

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

What am i doing wrong here?

我在这里做错了什么?

Ps:First node has child nodes and I have no problem with assigning values so ignore "getter" functions.I have changed them inorder to simplfy code.My problem is that i lose values after code completes this part.

第一个节点有子节点，我对赋值没有问题，所以忽略“getter”函数。为了简化代码，我修改了它们。我的问题是，在代码完成这一部分后，我将丢失值。

Thanks for fast response.I read values from a file.

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

The structure of file looks like this.

文件的结构是这样的。

< Key ConsAlterKey MasterKey VowelDeletion Data MasterData ChildCount or >

<关键的consalterkey masterkey元音删除数据masterdata childcount或> 。

If a line/item has no child nodes it ends with ">" else it ends with ChildCount value.And here "-" character presents NULL value.

如果一个行/项没有子节点，它以“>”结束，否则它以child count值结束。这里“-”字符表示空值。

< 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 - > 
 >
>

And not simplified version of my code as follows:

我的代码不简化版本如下:

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);
        }


    }
}

}

}

}

}

Traverse function as follows:

遍历函数如下:

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]));
    }
}

}

And output is:

和输出是:

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 个解决方案

#1

3  

Ah, with more code it's easy: Your problem is that char string[50] is a local variable and you save many pointers into this local array which is lost when AddAsChildren2 returns. Depending on whether you ever need to free this structure you could strdup() the whole line and then save the tokens from it or strdup() each individual token (to simplify freeing).

啊，有了更多的代码就很简单了:您的问题是，char字符串[50]是一个局部变量，您将许多指针保存到这个本地数组中，当AddAsChildren2返回时，该数组将丢失。根据您是否需要释放这个结构，您可以对整个行进行strdup()，然后从它中保存令牌或strdup()每个单独的令牌(以简化释放)。

#1

3  

Ah, with more code it's easy: Your problem is that char string[50] is a local variable and you save many pointers into this local array which is lost when AddAsChildren2 returns. Depending on whether you ever need to free this structure you could strdup() the whole line and then save the tokens from it or strdup() each individual token (to simplify freeing).

啊，有了更多的代码就很简单了:您的问题是，char字符串[50]是一个局部变量，您将许多指针保存到这个本地数组中，当AddAsChildren2返回时，该数组将丢失。根据您是否需要释放这个结构，您可以对整个行进行strdup()，然后从它中保存令牌或strdup()每个单独的令牌(以简化释放)。

标签：

相关文章