pku1583.cpp

这是ACM 方面的资料 是PKU的 北京大学的出来的

#include <stdio.h>
#include <string.h>
#define size 600

typedef struct Node
{
	char s[14];
	int l, r, cnt;
} Node;

Node STree[size];
int STreeEnd;
int Max;

int isChar(char x)
{
	if (x >= 'A' && x <= 'Z')
		return 1;
	if (x >= 'a' && x <= 'z')
		return 1;
	if (x >= '0' && x <= '9')
		return 1;
	return 0;
}

char toLower(char x)
{
	if (x >= 'A' && x <= 'Z')
	{
		return x + 32;
	}
	return x;
}

void Insert(char *s, int p)
{
	int res;
	if (STreeEnd == 0)
	{
		strcpy(STree[0].s, s);
		STree[0].cnt = 1;
		STreeEnd++;
		return;
	}
	res = strcmp(s, STree[p].s);
	if (res == 0)
	{
		STree[p].cnt++;
		Max = STree[p].cnt > Max ? STree[p].cnt : Max;
		return;
	}
	if (res < 0)
	{
		if (STree[p].l == 0)
		{
			STree[STreeEnd].cnt++;
			strcpy(STree[STreeEnd].s, s);
			STree[p].l = STreeEnd;
			STreeEnd++;
			return;
		}
		else
		{
			Insert(s, STree[p].l);
		}
	}
	else if (res > 0)
	{
		if (STree[p].r == 0)
		{
			STree[STreeEnd].cnt++;
			strcpy(STree[STreeEnd].s, s);
			STree[p].r = STreeEnd;
			STreeEnd++;
			return;
		}
		else
		{
			Insert(s, STree[p].r);
		}
	}
}

void DFS(int p)
{
	if (STree[p].l)
		DFS(STree[p].l);
	if (STree[p].cnt == Max)
		printf("%s\n", STree[p].s);
	if (STree[p].r)
		DFS(STree[p].r);
}

int main()
{
	char x, s[80];
	int i, j;
	i = 0;
	Max = 0;
	memset(STree, 0, sizeof(STree));
	STreeEnd = 0;
	while (EOF != scanf("%c", &x))
	{
		if (isChar(x))
		{
			s[i++] = toLower(x);
		}
		else if (i > 0)
		{
			Insert(s, 0);
			i = 0;
			memset(s, 0, sizeof(s));
		}
	}
	printf("%d occurrences\n", Max);
	DFS(0);
	return 0;
}