dict.c

给定一本字典dict和一段文本text

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

typedef struct btnode *btlink;
typedef struct btnode{
	char str[20];
	btlink left;
	btlink right;
	int count;
}Btnode;


btlink NewBSnode(char *x)
{
	btlink r;
	r=malloc(sizeof(Btnode));
//	r->str=x;
	strcpy(r->str,x);
	r->left=0;
	r->right=0;
	r->count=0;
	return r;
}


void dicttree(btlink A,btlink B){
	if (strcmp(A->str,B->str)>0)
	{
		if (!B->right)B->right=A;
		else dicttree(A,B->right);
	}
	if (strcmp(A->str,B->str)<0)
	{
		if (!B->left)B->left=A;
		else dicttree(A,B->left);
	}
}


void insertnew(char *a,btlink b,int flag)
{
	btlink w;
	w=NewBSnode(a);
	w->count=1;
	w->left=0;
	w->right=0; 
	if (flag==1)
		b->right=w;
	else b->left=w;
}


int Search(btlink x,int max)    //递归求出现的最大次数
{
	btlink p,q;
	if(x->left) {
		p=x->left;
		if ((p->count)>max) max=p->count;
		max=Search(p,max);
	}
	if (x->right){
		q=x->right;
		if ((q->count)>max) max=q->count;
		max=Search(q,max);
	}
	return max;
}


int main ()
{
	int i,n,m,flag=1,max=0;
	char text[20];
//	btlink *p;
	btlink q;
	btlink current;
	btlink root,nd;

	freopen("input.txt","r",stdin);
	freopen("output.txt","w",stdout);
	scanf ("%d",&n);
//	p=(btlink*)malloc(n*sizeof(int));
//	for(i=0;i<n;i++) p[i]=(btlink)malloc(sizeof(btlink));
	root=malloc(sizeof(Btnode));
//	scanf ("%s",p[0]->str);
//	p[0]->right=0;
//	p[0]->left=0;
//	p[0]->count=0;
	scanf("%s",root->str);
	root->left=root->right=NULL;
	root->count=0;

	for (i=1;i<n;i++){
		nd=malloc(sizeof(Btnode));
	//	scanf ("%s",p[i]->str);
	//	p[i]->right=0;
	//	p[i]->left=0;
	//	p[i]->count=0;
		scanf("%s",nd->str);
		nd->left=nd->right=NULL;
		nd->count=0;
		dicttree(nd,root);
//		dicttree(p[i],p[0]);
	}   
	scanf ("%d",&m);

	for (i=1;i<=m;i++)
	{
		scanf ("%s",text);
	//	q=&p[0];
		q=root;
		while (q)
		{
			if (strcmp(text,(q)->str)>0)
			{ 
				flag=1;
				current=q;
				q=q->right;
			}
			else if (strcmp(text,(q)->str)<0)
			{
				flag=2;
				current=q;
				q=(q)->left;
			}
			else 
			{
				if ((q)->count){
					(q)->count++;
					if (((q)->count)>max) max=(q)->count;
				}
				flag=0;
				break;
			}
		}
		if (flag){
			insertnew(text, current, flag);
			if (max<1) max=1;
		}

//		max=Search(p[0],max);
	}

	printf ("%d\n",max);
	return 0;
}