u010259017 2015-11-14 01:45 采纳率: 60%
浏览 1855

请问如何用用java语言实现IP地址字典树?谢谢

用java语言实现IP地址字典树
字典树,又称单词查找树,Trie树,是一种树形结构,是一种哈希树的变种。典型应用是用于统计,排序和保存大量的字符串(但不仅限于字符串),所以经常被搜索引擎系统用于文本词频统计。它的优点是:利用字符串的公共前缀来减少查询时间,最大限度地减少无谓的字符串比较,查询效率比哈希树高。
字典树示例:图片说明

字典树的基本性质:
(1)根节点不包含字符,除根节点外每一个节点都只包含一个字符;
(2)从根节点到某一节点,路径上经过的字符连接起来,为该节点对应的字符串;
(3)每个节点的所有子节点包含的字符都不相同。
字典树的基本操作有:查找、插入和删除,
搜索字典项目的方法为:
(1)从根结点开始一次搜索;
(2)取得要查找关键词的第一个字母,并根据该字母选择对应的子树并转到该子树继续进行检索;
(3)在相应的子树上,取得要查找关键词的第二个字母,并进一步选择对应的子树进行检索。
(4)迭代过程……
(5)在某个结点处,关键词的所有字母已被取出,则读取附在该结点上的信息,即完成查找。

根据字典树的上述特性,设计一种字典树,实现下列要求:
(1)该字典树能够实现对IP地址的查找。IP地址采用点分形式表示,如:192.168.1.1,即字典树每个节点只能包含0-9和”.”十一个字符中的一个。
(2)该字典树具有插入和查找和统计的功能
(3)用一组IP地址(期中一些IP地址以192开始)初始化该字典树
(4)在该字典树中查找以192开始的IP地址的个数,并打印出查找结果。
(5)查找10.10.10.10是否在该字典数据中存在,并打印出查找结果。

  • 写回答

2条回答 默认 最新

  • threenewbee 2015-11-14 04:16
    关注

    说的很清楚了,按照说的做就可以了。但是实际上,出这个题目的人根本就不理解ip地址是什么,以及字典树是干嘛的。这个题目出的完全是牵强附会。
    你可以理解出这个题目的人无非就是把ip地址当成字符串了(只是这个字符串只包括0-9以及点号)。

    这里有个例子
    http://www.java3z.com/cwbwebhome/article/article8/83591.html?id=4750

    你需要的修改是
    private int SIZE = 26;
    ->
    private int SIZE = 11;

    int pos = letters[i] - 'a';

    ->
    if (letters[i] == '.')
    pos = 10;
    else
    pose = letters[i] - '0';

    评论

报告相同问题?

悬赏问题

  • ¥15 想问一下stata17中这段代码哪里有问题呀
  • ¥15 flink cdc无法实时同步mysql数据
  • ¥100 有人会搭建GPT-J-6B框架吗?有偿
  • ¥15 求差集那个函数有问题,有无佬可以解决
  • ¥15 【提问】基于Invest的水源涵养
  • ¥20 微信网友居然可以通过vx号找到我绑的手机号
  • ¥15 寻一个支付宝扫码远程授权登录的软件助手app
  • ¥15 解riccati方程组
  • ¥15 使用rabbitMQ 消息队列作为url源进行多线程爬取时,总有几个url没有处理的问题。
  • ¥15 Ubuntu在安装序列比对软件STAR时出现报错如何解决