我正在研究一个特里数据结构，其中每个节点都是一个列表，其中包含一个值和对与该值对应的子节点的引用的条目，但似乎列表中的引用没有相互分开 - 所以例如，如果“the”和“sin”都在trie中，我的CONTAINS()函数将为“she”返回true，因为“s”在第一级，“h”在第二级，而“e”即使这些角色应该在不同的分支中，也处于第三级。我已经阅读了有关python引用的内容，无法弄清楚为什么会发生这种情况。
class triepair:
value = None
next = None
def __init__(self, value=None, next=None):
self.value = value
self.next = next
def NEXT(self,next):
self.next = next
def GETNEXT(self):
return self.next
class trienode:
nodespace = []
def __int__(self,nodespace=[]):
self.nodespace = nodespace
def APPEND(self,value):
newnext = trienode()
newpair = triepair(value,newnext)
self.nodespace.append(newpair)
def NEXT(self, value):
for triepair in self.nodespace:
if triepair.value == value:
return triepair.GETNEXT()
print("ERROR: value not found")
return None
def CONTAINS(self, value):
for triepair in self.nodespace:
if triepair.value == value:
return True
return False
def INSERT(self, word):
c = word[:1]
rest = word[1:]
if self.CONTAINS(c):
if len(rest) > 0:
nextnode = self.NEXT(c)
nextnode.INSERT(rest)
else:
self.APPEND(c)
if len(rest) > 0:
nextnode = self.NEXT(c)
nextnode.INSERT(rest)
def TRACE(self, word):
c = word[:1]
rest = word[1:]
if self.CONTAINS(c):
print "found character ",c
if self.NEXT(c) is not None and len(rest) > 0:
self.NEXT(c).TRACE(rest)
else:
print "trace complete"
def HASWORD(self, word):
c = word[:1]
rest = word[1:]
if self.CONTAINS(c):
#print str(self)," contains ",c
if len(rest) > 0:
return self.NEXT(c).HASWORD(rest)
else:
return True
else:
return False
class trie:
root = trienode()
def __init__(self):
self.root = trienode()
def INSERT(self,word):
self.root.INSERT(word)
def TRACE(self,word):
if self.root is not None:
self.root.TRACE(word)
else:
print("null trie")
def CONTAINS(self, word):
return self.root.HASWORD(word)
大声笑，这花了我一段时间来调试，但我找到了。
改变这个：
class trienode:
nodespace = []
def __int__(self,nodespace=[]):
self.nodespace = nodespace
对此：
class trienode:
nodespace = []
def __init__(self):
self.nodespace = []
首先，__int__这不是问题，但这只是问题的一部分。
在不知道确切原因的完整 Pythonic 细节的情况下，根nodespace正在被重用。
因此，当您在 中创建一个新的时APPEND()，它实际上并没有发生，并且您nodespace在新的“子项”中得到相同的结果。
结果，一切都是平的。所有value -> trienode对都处于同一级别，并且 trienode 引用始终指向同一事物。
总之，上述变化可以确保你有一个新的空启动nodespace，从而APPEND()和.NEXT().CONTAINS()等，将更加像你期望他们。
本文收集自互联网，转载请注明来源。
如有侵权，请联系 [email protected] 删除。
我来说两句