单链表是一种数据结构，由若干个结点组成。每个结点包含数据和下一个结点的地址。从头结点开始，通过下一个结点的地址找到下一个结点，如此循环，直到下一个结点的地址为空。

现给出一个单链表，每个结点包含的数据是一个字符（大写英文字母）。求该链表上的结点数据中各个字母所占比例。

输入格式:

第一行给出链表第一个结点的地址H和要给出的结点总个数N。其中结点地址H用5位非负整数表示，N为不大于10000的正整数。 之后N行，每行按如下格式给出结点信息：

Address Data Next

Address为结点地址，Data为A-Z中的一个字母，Next为下一个结点的地址，Address和Next格式同H。当Next为-1时表示该结点没有下一个结点，链表遍历结束。

输出格式:

按A-Z的顺序，按以下格式输出各个字母所占比例：

Character Percentage

其中Character为英文字母， Percentage为百分比，保留到小数点后2位。中间以空格分隔。 如果该字母没有出现过，则不输出。

输入样例:

1
2
3
4
5
6
7
8
9
10
11
00001 10
01044 E 01055
00100 C 01011
00001 D 00100
09996 D 00253
01011 A 00045
00045 V 09876
09876 E 09996
00253 D 00999
00999 A 01044
01055 G -1

输出样例:

1
2
3
4
5
6
A 20.00%
C 10.00%
D 30.00%
E 20.00%
G 10.00%
V 10.00%

思路

根据输入，我们先考虑下用什么来存这些节点信息。由于这里的地址都是五位非负整数，所以我大可开两个大小为100000的数组来表示下标即地址(这样拿到地址便可直接通过下标访问节点了)的节点的数据与它下一个节点的地址。输入存好信息以后，我们直接从给定的链表首节点地址开始遍历链表就好，边遍历边去更新对应字母出现的次数，最后输出出现字母的次数就好。由于这里按字母序输出，所以存次数可以选用map<char,int>就好。代码如下：

有可能题目给定的n个结点并不都在链表中

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
#include <bits/stdc++.h>

using namespace std;

const int maxn=100000;

char Data[maxn];
int Next[maxn];//千万别写成next，不然会后悔的！
map<char,int> m;

int main()
{
    int start;
    cin>>start;
    int N;
    cin>>N;
    for(int i=0;i<N;i++)
    {
        int address;
        cin>>address;
        cin>>Data[address]>>Next[address];
    }
    int n=0;//第一次递交后因为没满分，凭经验估计是它输入的节点可能不是都在一个链表，然而我只要算给定开始节点的链表即可
    int head=start;
    while(head!=-1)
    {
        n++;//！
        m[Data[head]]++;
        head=Next[head];
    }
    for(auto it=m.begin();it!=m.end();it++)
    {
        printf("%c %.2lf%%\n",it->first,(double)it->second/n*100.0);
    }
}