2474182_wa.cpp

来自「北大大牛代码 1240道题的原代码 超级权威」· C++ 代码 · 共 101 行

#include <stdio.h>
#include <stdlib.h>
#include <ctype.h>
#include <string.h>
#define INIT (tree *)malloc(sizeof(tree))

typedef struct node
{
	char name[31];
	char ape;
	struct node *l, *r;
}tree;
int tot = 0;

int cmp(char a[],char b[])
{
	char t1[31], t2[31];

	strcpy(t1,a);strcpy(t2,b);
	for(int i = 0; t1[i]!='\0'; i++)
		if(!isalpha(t1[i]))
		{
			strcpy(&t1[i],&t1[i+1]);
			i--;
		}
	for(i = 0; t2[i]!='\0'; i++)
		if(!isalpha(t2[i]))
		{
			strcpy(&t2[i],&t2[i+1]);
			i--;
		}
	return strcmp(t1,t2);
}

void visit(tree *s)
{
	if(s->l)
		visit(s->l);
	printf("%s %.4lf\n",s->name,s->ape*100.0/(1.0*tot));
	if(s->r)
		visit(s->r);
}

int main()
{
	int mark = 1, v;
	tree *root, *s, *p;
	char tmp[31];

	while(gets(tmp)!=NULL)
	{
		tot++;
		if(mark)
		{
			mark = 0;
			root = INIT;
			root->ape = 1;
			strcpy(root->name,tmp);
			root->l = root->r = NULL;
		}
		else
		{
			p = INIT;
			p->ape = 1;p->l = p->r = NULL;
			strcpy(p->name,tmp);
			s = root;
			while(s)
			{
				v = cmp(tmp,s->name);
				if(v>0)
				{
					if(s->r)
						s = s->r;
					else
					{
						s->r = p;
						break;
					}
				}
				else
					if(v<0)
					{
						if(s->l)
							s = s->l;
						else
						{
							s->l = p;
							break;
						}
					}
					else
					{
						s->ape++;
						break;
					}
			}
		}
	}
	visit(root);
	return 1;
}