解析文本文件到C++有向图或邻接表？

我有一个文本文件，它是类似于：解析文本文件到C++有向图或邻接表？

person: head, body 
head: eyes, nose, ears, mouth 
body: arm, leg 
arm: elbow, hand 
leg: thigh, knee, foot

我想在任何一个邻接表或有向图来表示此。什么是最好的方法来做到这一点？我无法弄清楚最好的数据结构或如何用C++来表示它。

我使用结构的键控（人，头，等等）值试图和它的父指数，它是儿童作为载体：

struct Node 
{ 
    string key; 
    int parentIndex; 
    vector<string> children; 
};

但这似乎效率不高。有任何想法吗？

也许这会更好？

struct { 
    string key; 
    Node* parent; 
    vector<Node> children; 
};

来源

2015-11-03 bdeo

@Christophe我编辑了这个问题。 – bdeo

要阅读文件，你应该使用'std :: ifstream'。对于解析行，不要忘记C++是建立在C上的 - 查看C的'strtok'函数。为了存储，考虑一下'std :: map <[key]，[container]的味道''。 – Conduit

@Conduit是说我们应该使用map >？为了查询这个结构，我们希望使用像DFS等算法的图形。 – bdeo

有几个问题仍未得到你的数据样本的回答：是否总是有一个单一入口点（例如：人）？它总是自顶向下分解（即每个元素最多有一个父元素）？这些元素总是以正确的方式出现：首先是顶部，然后是底部？

如果你所有三个问题都是肯定的，那么你提出的结构是合适的：

这是很有效的，如果总是从顶部开始探索。
找到一个特定的节点会很耗时，因为你必须遍历整个结构。

还有几点需要解决：

这将是棘手的复制节点（因为指针家长必须为复制节点被改变，以及为它的子女和孩子的孩子。
添加元素的数组可能无效所有的孩子的父poitners和孩子的孩子。

正如你看到的，最佳的数据结构不仅取决于内容，但以及你将如何使用它。

有很多其他方法来做到这一点，以不同的方式平衡性能方面。例如：

class mygraph { 
    struct node { // nodes that you read: 
     string name; 
     int id;   // index of the node in the nodes vector 
     vector<int> in; // parent(s) that can lead to this node 
     vector<int> out; // children you can go to 
    }; 
    vector<node> nodes; // all the nodes in arbitrary sequential order 
    map<string, int> dict; // map converting the names into ids (redundant and optional, useful for efficien search by name); 
public: 
    // members to populate the structure and to acces the nodes cleanly. 
};

优点：

找到ID的任何节点是非常快的，因为它是唯一索引的数组。
你不需要担心结构的副本，因为没有指针。
由于进/出载体，您可以快速前进或后退任何你想要的节点。
冗余映射（即指数名称）加速按名称搜索节点

不便之处：有填充结构时的一些开销：你需要在地图上验证名称到每一个名字转换成一个id，如果没有建立在一个新的节点节点矢量并在地图中插入名称+新ID。

来源

2015-11-03 22:42:12 Christophe

每个“单词”都需要自己的节点。所以，你的第二个结构更接近。但是，只要确保子节点的容器类型可以在创建节点后动态增长并包含指向子节点的指针。

有两个原因：
（1）假设我们在数据的底部添加了一行：arm: wrist。在之后，需要将子节点添加到子节点之后。（2）目前，你的数据文件是有序的。但是，如果我们随机化数据行的顺序呢？这仍然有效吗？大多数有向图程序处理得很好

当你从左到右分析一行时，得到这个单词。搜索所有已知的节点，寻找匹配。第一行被解析后，你有三个节点：人，头，身体。头和身体在人的孩子[和他们的parent领域都将指向人]，但他们的子列表[当前]是空的。人将成为root节点。

如果您发现匹配，您将在第二行的头部使用现有的头节点，并填写孩子。如果不匹配，请创建节点。

如果搜索失败并且您必须创建一个新节点，那么您可能没有在您要构建的树中附加一个位置。在这种情况下，将其添加到“保留”列表[也是搜索的一部分]，直到有更多节点进入，您可以将保留项目附加为子项，在这种情况下，您可以将它们从保留列表中删除。

您可能必须更新root节点。对于示例数据，假设我们在底部添加了household: person dog。 root节点需要相应调整。我们还需要一个dog:行。如果我们最后没有它，那是未定义的值，并且需要被标记。您的节点定义将需要一个defined布尔才能标记此。

最后，任何仍在保留列表中的数据都是无关数据。例如，如果我们有一个zebra:行，则没有对它的引用[它的parent将为空]，并且还需要标记。

当连接东西时，给定的节点只能被引用一次。所以，如果我们添加household: arm，这将会发生冲突，因为手臂已经是身体的一个孩子。检测到parent已经非空

来源

2015-11-03 22:46:04

解析文本文件到C++有向图或邻接表？

回答

相关问题