document.write('要想实现反向DNS查找缓存，主要需要完成如下功能：
(1)将IP地址添加到缓存中的URL映射。
(2)根据给定IP地址查找对应的URL。
对于本题，常见的一种解决方案是使用字典法(使用字典来存储IP地址与URL之间的映射关系)，由于
这种方法相对比较简单，这里就不做详细的介绍了。下面重点介绍另外一种方法：Trie树。这种方法的
主要优点如下：
(1)使用Trie树，在最坏的情况下的时间复杂度为O(1)，而哈希方法在平均情况下的时间复杂度为
O(1)；
(2)Trie树可以实现前缀搜索(对于有相同前缀的IP地址，可以寻找所有的URL)。
当然，由于树这种数据结构本身的特性，所以使用树结构的一个最大的缺点就是需要耗费更多的内
存，但是对于本题而言，这却不是一个问题，因为Internet IP地址只包含有11个字母(0到9和.)。所
以，本题实现的主要思路为：在Trie树中存储IP地址，而在最后一个结点中存储对应的域名。实现代码
如下：
# Trie树的结点
class TrieNode:
def __init__(self):
CHAR_COUNT=11
self.isLeaf=False
self.url=None
self.child=[None]*CHAR_COUNT #TrieNode[CHAR_COUNT]# CHAR_COUNT
i=0
while i＜CHAR_COUNT:
self.child[i]=None
i+=1
def getIndexFromChar(c):
return 10 if c==\'.\' else (ord(c)-ord(\'0\'))
def getCharFromIndex(i):
return \'.\'if i==10 else (\'0\'+str(i))
class DNSCache:
def __init__(self):
self.CHAR_COUNT=11 #IP地址最多有11个不同的字符
self.root=TrieNode()#IP地址最大的长度
def insert(self,ip,url):
#IP地址的长度
lens=len(ip)
pCrawl=self.root
level=0
while level＜lens:
#根据当前遍历到的IP中的字符, 找出子结点的索引
index=getIndexFromChar(ip[level])
#如果子结点不存在 ,则创建一个
if pCrawl.child[index]==None:
pCrawl.child[index]=TrieNode()
#移动到子结点 #/
pCrawl=pCrawl.child[index]
#在叶子结点中存储IP对应的URL
pCrawl.isLeaf=True
pCrawl.url=url
level+=1
#通过IP地址找到对应的URL
def searchDNSCache(self,ip):
pCrawl=selfroot
lens=len(ip)
#遍历IP地址中所有的字符
level=0
while level＜lens:
index=getIndexFromChar(ip[level])
if pCrawl.child[index]=None:
return None
pCrawl=pCrawl.child[index]
level+=1
#返回找到的URL
if pCrawl!=None and pCrawl.isLeaf:
return pCrawl.url
return None
if __name__=="__main__":
ipAdds=["10.57.11.127", "121.57.61.129","66.125.100.103"]
url=["www.samsung.com", "www.samsung.net", "www.google.in"]
n=len(ipAdds)
cache=DNSCache()
for i in range(n):
cache.insert(ipAdds[i],url[i])
i+=1
ip="121.57.61.129"
res_url=cache.searchDNSCache(ip)
if res_url!=None:
print "找到了IP对应的URL: \\n"+ip+"---＞"+res_url
else:
print "没有找到对应的URL\\n"
程序的运行结果为：
找到了IP对应的URL：
121.57.61.129--＞www.samsung.net
显然，由于上述算法中涉及的IP地址只包含特定的11个字符(数字和.)，所以，该算法也有一些异常情
况不能处理，例如不能处理用户输入的不合理的IP地址的情况，有兴趣的读者可以继续朝着这个思路完
善后面的算法。
');