2474297_mle.cc

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

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

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

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 = strcmp(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;
}