pku2418.cpp

来自「这是ACM 方面的资料 是PKU的 北京大学的出来的」· C++ 代码 · 共 91 行

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
int SZ, Total, End;
typedef struct node
{
	char s[32];
	int n;
	int l, r;
} Node;

Node arr[10010];

int Insert(int h, char *s)
{
	int P;
	P = strcmp(arr[h].s, s);
	if (P == 0)
	{
		arr[h].n++;
		return;
	}
	else if (P > 0)
	{
		if (arr[h].l == -1)
		{
			arr[h].l = End;
			strcpy(arr[End].s, s);
			arr[End].n = 1;
			arr[End].l = arr[End].r = -1;
			End++;
			return;
		}
		else
		{
			Insert(arr[h].l, s);
		}
	}
	else
	{
		if (arr[h].r == -1)
		{
			arr[h].r = End;
			strcpy(arr[End].s, s);
			arr[End].n = 1;
			arr[End].l = arr[End].r = -1;
			End++;
			return;
		}
		else
		{
			Insert(arr[h].r, s);
		}
	}
}

void DFS(int h)
{
	if (h == -1)
	{
		return;
	}
	DFS(arr[h].l);
	printf("%s %.4lf\n", arr[h].s, arr[h].n * 100.0 / Total);
	DFS(arr[h].r);
}

int main()
{
	char s[31];
	Total = 1;
	End = 1;
	SZ = sizeof(Node);
	gets(s);
	strcpy(arr[0].s, s);
	arr[0].n = 1;
	arr[0].l = arr[0].r = -1;
	while (gets(s))
	{
		if (strcmp(s, "") == 0)
		{
			break;
		}
		Insert(0, s);
		Total++;
	}
	DFS(0);
	return 0;
}