我正在尝试制作一个 Trie 数据结构(学校作业)，我正在使用一个我自己制作的列表，并且可以很好地(测试)将 N 节点存储在 Trie 中。
无论如何，问题是，每个节点都应该存储一个节点列表，这样我就可以制作我的 N 元树/特里树，但我遇到了障碍...
当我调试并执行 for 循环时，我可以看到 currentNode 越来越深入我的树中。但是，当我从根的角度来看时，我的根只有一个链表，其中包含在循环的第一次迭代中创建的第一个节点。连续迭代不会在 ROOT NODE 的 BRANCH 中的 NODE 中注册...但它在 currentNode 中工作，就好像它们是单独的拷贝一样，即使 currentNode 是指向正确(我希望)节点的指针。
我的代码有问题吗？!？我误解了指针的工作原理吗？帮助!谢谢。
我的节点结构。
struct Node {
char letter;
ItemType item;
List<Node> * branches;
};
Node * root;
int size;
我的 put 函数。
ItemType put(KeyType newKey, ItemType newItem) {
Node * currentNode = root;
if (isEmpty()) {
//So build a new key
for (int levelIndex = 1; ((int) (newKey.length()) - levelIndex) >= 0; ++levelIndex) {
currentNode->branches = new List<Node>;
Node * tempNode = new Node;
tempNode->letter = newKey.at(levelIndex - 1);
currentNode->branches->add(*tempNode);
currentNode = tempNode;
}
//Store
currentNode->item = newItem;
++size;
return NULL; //The former item.
} else {
//Begin
return puttanesca(newKey, newItem, *(currentNode->branches), 1, 1);
}
}
编辑:哦，抱歉，我忘了说 puttanesca 是我用来遍历和放置节点等的递归函数。但我还没有真正测试过，因为这个问题，我被困在这里只是试图将第一个键添加到我的空 Trie 中......
更多编辑:
这是 puttanesca，虽然我不认为它与问题有任何关系，但是......无论如何就是这样。
我正在将 Node 结构中的 List 指针更改为一个对象，因此其中一些内容可能看起来不对，或者一开始可能就是错误的，因为我对 C++ 不是很好，而且我这里仍然有问题，但可以看到一般概念/算法...哦，我正在使用 typedef string KeyType 作为我的 key ，只是为了将来的一些验证和一个模板 ItemType。
ItemType puttanesca(KeyType newKey, ItemType newItem, List<Node> & tempList, int listIndex, int levelIndex) {
Node currentNode = tempList.get(listIndex);
//Am I at the right node? (searching)
if (newKey.at(levelIndex - 1) == currentNode.letter) { //Yes, I am.
//Is this a leaf node?
if (currentNode.branches == NULL) {
//Key does not already exist
if (newKey.length() != levelIndex) {
//So build a new key
for (; ((int) (newKey.length()) - levelIndex) >= 0; ++levelIndex) {
currentNode.branches = new List<Node>;
Node * tempNode = new Node;
tempNode->letter = newKey.at(levelIndex - 1);
currentNode.branches.add(*tempNode);
currentNode = *tempNode;
}
//Store
currentNode.item = newItem;
++size;
return NULL; //The former item.
} else { //Key matched!
//Replace with new item
ItemType currentItem = currentNode.item;
currentNode.item = newItem;
return currentItem; //which is actually the now old item after the previous statement
}
} else { //Not a leaf, keep going
//Go to the next level and start from the first index
ItemType currentItem = puttanesca(newKey, newItem, currentNode.branches, 1, levelIndex + 1);
if (currentItem == NULL) {
//Key found to be inexistant
//So build a new key - create new sibling
Node * tempNode = new Node;
tempNode->letter = newKey.at(levelIndex - 1);
currentNode.branches.add(*tempNode);
currentNode = *tempNode;
//Continue building key - extend sibling
for (++levelIndex; ((int) (newKey.length()) - levelIndex) >= 0; ++levelIndex) {
currentNode.branches = new List<Node>;
Node * tempNode = new Node;
tempNode->letter = newKey.at(levelIndex - 1);
currentNode.branches.add(*tempNode);
currentNode = *tempNode;
}
//Store
currentNode.item = newItem;
++size;
return NULL; //The former item
} else {
return currentItem; //The former item;
}
}
} else { //Wrong node
if (tempList.getLength() > listIndex) {
return puttanesca(newKey, newItem, tempList, ++listIndex, levelIndex);
} else {//End of the line, chump
return NULL; //Tell parent you failed
}
}
}
最佳答案
您的问题在这里: currentNode->branches->add(*tempNode);
您正在插入 tempNode 的拷贝, 不是 tempNode本身。您可能需要考虑使用 List<Node *> branches而不是 List<Node> branches ;
关于c++ - 在列表中的结构中访问/分配值的问题 - C++，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/2212465/