首页 > POJ 2418 Hardwood Species(trie 树）

POJ 2418 Hardwood Species(trie 树）

题目链接

开始想用map的，字典序不会搞，还是老老实实的用trie树把。好久没写了，忘得差不多了。

 1 #include 
 2 #include 
 3 #include 
 4 #include 
 5 #include 
 6 #include 
 7 #include <string>
 8 #include 
 9 #include 
10 #include 
11 using namespace std;
12 struct node
13 {
14     int data;
15     struct node *next[129];
16 };
17 int num = 0;
18 char o[51];
19 struct node *build()
20 {
21     int i;
22     node *p;
23     p = new node;
24     p -> data = 0;
25     for(i = 0; i <= 128; i ++)
26         p -> next[i] = NULL;
27     return p;
28 }
29 void insert(struct node *head,char *str)
30 {
31     int i,len;
32     len = strlen(str);
33     node *p;
34     p = head;
35     for(i = 0; i < len; i ++)
36     {
37         if(p->next[str[i]] == NULL)
38         {
39             p->next[str[i]] = build();
40         }
41         p = p->next[str[i]];
42     }
43     p -> data ++;
44 }
45 void dfs(struct node *head,int step)
46 {
47     int i;
48     node *p;
49     p = head;
50     if(p->data > 0)
51     {
52         o[step] = '';
53         printf("%s %.4lf
",o,p->data*100.0/num);
54     }
55     for(i = 0; i <= 128; i ++)
56     {
57         if(p->next[i] != NULL)
58         {
59             o[step] = i;
60             dfs(p->next[i],step+1);
61         }
62     }
63 }
64 int main()
65 {
66     char p[51];
67     node *head;
68     head = build();
69     while(gets(p) != 0)
70     {
71         insert(head,p);
72         num ++;
73     }
74     dfs(head,0);
75     return 0;
76 }

 

转载于:https://www.cnblogs.com/naix-x/archive/2013/01/18/2866930.html

更多相关：

  • PCL点云分割（2）

    关于点云的分割算是我想做的机械臂抓取中十分重要的俄一部分，所以首先学习如果使用点云库处理我用kinect获取的点云的数据，本例程也是我自己慢慢修改程序并结合官方API 的解说实现的，其中有很多细节如果直接更改源程序，可能会因为数据类型，或者头文件等各种原因编译不过，会导致我们比较难得找出其中的错误，首先我们看一下我自己设定的一个场景，...

  • PCL点云配准（2）

    /* 使用正态分布变换进行配准的实验 。其中room_scan1.pcd room_scan2.pcd这些点云包含同一房间360不同视角的扫描数据 */ #include #include #include #include

  • PCL点云变换与移除NaN

    #include #include #include #include ...

  • PCL滤波介绍(3)

    #include #include #include #include #include #include...

  • PCL滤波介绍（2）

    #include #include #include #include int main (int argc,...

  • 二叉树：二叉搜索树的编码和解码

    二叉搜索树的编码和解码描述： 编码：即将一个二叉搜索树编码，节点数值转换为字符串 解码：即将一个字符串解码，数值转换为对应的二叉搜索树的节点 过程导图如下： 针对性编码实现如下: /*数字转字符串*/ void change_num_to_string(int val, string &tmp) {string buf;whil...

  • 二叉树：二叉搜索树的创建和插入

    二叉搜索树又名二叉排序树。 大概简略的思维导图如下，方便记忆特性 基本二叉搜索树创建过程如下 /*数据结构如下*/ typedef struct tree {int data;struct tree *left = NULL;struct tree *right = NULL; }Tree,*TreeNode;/*Node 为二...

  • Linux安装Nodejs

    Linux安装Nodejs 　　 　　　阿里云镜像： https://npm.taobao.org/mirrors/node/ 选择所需版本，进行下载。 　　　我这边下载的是：https://npm.taobao.org/mirrors/node/v8.2.1/node-v8.2.1-linux-x64.tar.gz  　　　 　　　...

  • Hadoop自学笔记（二）HDFS简单介绍

    1. HDFS Architecture 一种Master-Slave结构。包括Name Node, Secondary Name Node,Data Node Job Tracker, Task Tracker。JobTrackers: 控制全部的Task Trackers 。这两个Tracker将会在MapReduce课程里...

  • Sublime Text3配置Node.js开发环境

    下载Nodejs插件，下载zip压缩包后解压链接: http://pan.baidu.com/s/1hsBk60k 密码: jrcv打开Sublime Text3，点击菜单“首选项（N）” =>“浏览插件（B）”打开“Packages”文件夹，并将第1部的Nodejs文件夹剪切进来打开文件“Nodejs.sublime-build”，...

  • 剑指offer：面试题35. 复杂链表的复制

    题目：复杂链表的复制 请实现 copyRandomList 函数，复制一个复杂链表。在复杂链表中，每个节点除了有一个 next 指针指向下一个节点，还有一个 random 指针指向链表中的任意节点或者 null。 示例 1： 输入：head = [[7,null],[13,0],[11,4],[10,2],[1,0]] 输出...

  • leetcode-86 分隔链表

    给定一个链表和一个特定值 x，对链表进行分隔，使得所有小于 x 的节点都在大于或等于 x 的节点之前。 你应当保留两个分区中每个节点的初始相对位置。 示例: 输入: head = 1->4->3->2->5->2, x = 3 输出: 1->2->2->4->3->5 使用双指针的方式，各自构造一个大元素的头节点和小元素...

  • leetcode-142 环形链表II

    给定一个链表，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。 为了表示给定链表中的环，我们使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。 如果 pos 是 -1，则在该链表中没有环。 说明：不允许修改给定的链表。 示例 1： 输入：head = [3,2,0,-4], pos = 1...

  • leetcode-92 反转链表II

    题目描述如下： 反转从位置 m 到 n 的链表。请使用一趟扫描完成反转。 说明: 1 ≤ m ≤ n ≤ 链表长度。 示例: 输入: 1->2->3->4->5->NULL, m = 2, n = 4 输出: 1->4->3->2->5->NULL 很明显这个题目是206 反转链表的进阶版 需要记录第m-1个节点和第n+1个...

  • leetcode-206 反转链表

    描述如下： 反转一个单链表。 示例: 输入: 1->2->3->4->5->NULL 输出: 5->4->3->2->1->NULL 方法一：原地反转 数据结构如下 struct ListNode {int val;ListNode *next;ListNode(int x) : val(x), next(NULL) {}...

©2024 11GX.COM