2115419_ac_265ms_4492k.c

北大大牛代码 1240道题的原代码 超级权威

# include <stdio.h>
# include <string.h>
# include <stdlib.h>

typedef struct node
{
	int no;
	char dna[21];
	struct node *left;
	struct node *right;
}DNA;

void input()
{
	int i;
	int n, m;
	char tmp[21];
	DNA *root, *p, *q;
	int mark[20010];

	while(scanf("%d%d",&n,&m)==2&&m)
	{
		scanf("%s",tmp);
		memset(mark,0,(n+1)*sizeof(int));
		root = (DNA *)malloc(sizeof(DNA));
		strcpy(root->dna,tmp);
		root->no = 1;
		root->left = NULL;
		root->right = NULL;
		mark[1] = 1;
		for(i = 1; i < n; i++)
		{
    		scanf("%s",tmp);
			p = root;
			while(p)
			{
				if(strcmp(tmp,p->dna)==0)
				{
					p->no++;
					mark[p->no]++;
					mark[p->no-1]--;
					break;
				}
				else
					if(strcmp(tmp,p->dna)>0)
					{
						if(p->right)
							p = p->right;
						else
						{
							q = (DNA *)malloc(sizeof(DNA));
							q->left = NULL;q->right = NULL;
							strcpy(q->dna,tmp);
							q->no = 1;
							p->right = q;
							mark[1]++;
							break;
						}
					}
					else
					{
						if(p->left)
							p = p->left;
						else
						{
							q = (DNA *)malloc(sizeof(DNA));
							q->left = NULL;q->right = NULL;
							strcpy(q->dna,tmp);
							q->no = 1;
							p->left = q;
							mark[1]++;
							break;
						}
					}
			}
		}
		for(i = 1; i <= n; i++)
			printf("%d\n",mark[i]);
	}
}

int main()
{
	input();
	return 1;
}