> 我的程序：用二叉排序树做的
> #include<stdio.h>
> #include<stdlib.h>
> #define maxstar 15001
> typedef struct star
> {
> 	int date;
> 	int lev;
> 	int lchild,rchild;
> 	};
> 	
> 	int root=-1;
> 	int level;
> 	int num[maxstar];
> 	star stars[maxstar];
> 	
>  void insert(int x,int i)
>   {
> 	  int p,q;
> 	   p=i;
> 	  if(root==-1)
> 	   {root=0;stars[root].date=x;stars[root].lev=1;stars[root].lchild=-1;stars[root].rchild=-1;num[level]++;return;}
> 	   
> 	   q=root;
> 	  while(1)
> 	   {
> 		   if(stars[q].date==x)
> 		     {level+=stars[q].lev;num[level]++;stars[q].lev++;return;}
> 		   if(stars[q].date>x)
> 		     {
> 			     if(stars[q].lchild!=-1)
> 			       {stars[q].lev++;q=stars[q].lchild;continue;}
> 			     else {stars[q].lev++;stars[q].lchild=p;stars[p].date=x;stars[p].lchild=-1;stars[p].rchild=-1;stars[p].lev=1;num[level]++;return;}
> 			   }
> 			  if(stars[q].date<x)
> 		     {
> 			     if(stars[q].rchild!=-1)
> 			       {level+=stars[q].lev;q=stars[q].rchild;continue;}
> 			     else {level+=stars[q].lev;stars[p].date=x;num[level]++;stars[q].rchild=p;stars[p].lchild=-1;stars[p].rchild=-1;stars[p].lev=1;return;}
> 			   }      
> 	 }  
> 		   
> 		   
> 		   } 
> 		   
> 	int main()
> 	{  int x,y,n,i;
> 		scanf("%d",&n);
> 		for(i=0;i<=n-1;i++)
> 		 {
> 			 scanf("%d%d",&x,&y);
> 			 level=0;
> 			 insert(x,i);
> 			 }
> 	for(i=0;i<=n-1;i++)	
> 	 printf("%d\n",num[i]);	
> 		}

• Re:怀疑bst会退化，O(n^2)就挂了 (0) fxzy 2006-01-11 19:13:19
  • Re:怀疑bst会退化，O(n^2)就挂了 (9) fxzy 2006-01-11 19:13:43