数据结构|PTA线性表—统计字母比例数据结构|链表

统计字母比例单链表是一种数据结构，由若干个结点组成。每个结点包含数据和下一个结点的地址。从头结点开始，通过下一个结点的地址找到下一个结点，如此循环，直到下一个结点的地址为空。
现给出一个单链表，每个结点包含的数据是一个字符（大写英文字母）。求该链表上的结点数据中各个字母所占比例。
输入格式:
第一行给出链表第一个结点的地址H和要给出的结点总个数N。其中结点地址H用5位非负整数表示，N为不大于10000的正整数。之后N行，每行按如下格式给出结点信息：
Address Data Next
Address为结点地址，Data为A-Z中的一个字母，Next为下一个结点的地址，Address和Next格式同H。当Next为-1时表示该结点没有下一个结点，链表遍历结束。
输出格式:
按A-Z的顺序，按以下格式输出各个字母所占比例：
【数据结构|PTA线性表—统计字母比例】Character Percentage
其中Character为英文字母， Percentage为百分比，保留到小数点后2位。中间以空格分隔。如果该字母没有出现过，则不输出。
输入样例:

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 结尾无空行

输出样例:

A 20.00% C 10.00% D 30.00% E 20.00% G 10.00% V 10.00% 结尾无空行

逻辑
模拟。
AC代码
顺序表

#include using namespace std; struct MyStruct { int address; char data; int next; }; int main() { int addr; int n; double cnt[26] = {}; MyStruct a[10005]; int all = 0; cin >> addr >> n; for (int i = 0; i < n; i++) { cin >> a[i].address >> a[i].data >> a[i].next; } for (int i = addr; i != -1; ) { for (int j = 0; j < n; j++) { if (a[j].address == i) { cnt[a[j].data - 65]++; all++; i = a[j].next; break; } } } for (int i = 0; i < 26; i++) { if (cnt[i] != 0) { printf("%c %.2f%%\n", 'A' + i, cnt[i] * 1.0 / all * 100); } } return 0; }

链式表

#include using namespace std; typedef struct LNode { int Address; char Data; int Next; struct LNode* next; }LNode,*Linklist; int main() { int addr,n; cin>>addr>>n; Linklist l,s,r; l=(Linklist)malloc(sizeof(LNode)); cin>>l->Address>>l->Data>>l->Next; l->next=NULL; r=l; for(int i=1; i>s->Address>>s->Data>>s->Next; r->next=s; r=r->next; } r->next=l; double a[26]={}; int cnt=0; for(int i=addr; i!=-1; ) { if(i==l->Address) {a[l->Data-65]++; cnt++; i=l->Next; } l=l->next; } for(int i=0; i<26; i++) { if(a[i]!=0) printf("%c %.2f%%\n",'A'+i,a[i]*1.0/cnt*100); } return 0; }