two.c

四个小算法。红黑树

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

int N;

void coordinate(int *mtrix,int start,int end)
{
	int i,r;
	
	r=mtrix[start];
	for(i=2*start;i<=end;i=2*i)
	{
		if(i<end&&mtrix[i]<mtrix[i+1])
			i++;
		if(r>=mtrix[i])
			break;
		mtrix[start]=mtrix[i];
		start=i;
	}
	mtrix[start]=r;
}
void heapsort(int *mtrix,int n)
{
	int i,m;

	for(i=n/2;i>=1;i--)
		coordinate(mtrix,i,n);

	for(i=n;i>1;i--)
	{
		m=mtrix[1];
		mtrix[1]=mtrix[i];
		mtrix[i]=m;
		coordinate(mtrix,1,i-1);
	}
	return;
}

int search_median(int *mtrix_a,int *mtrix_b,int start_a,int end_a,int start_b,int end_b)
{
	if(start_a==end_a || start_b==end_b)
	{
		if(start_a+1==end_a)
		{
			printf("alice send bob:    ");
			printf("%d--------%d\n",start_a+1,mtrix_a[start_a+1]);
			return mtrix_a[start_a+1];
		}
		if(start_b+1==end_b)
		{
			printf("bob send alice:    ");
                        printf("%d--------%d\n",start_b+1,mtrix_b[start_b+1]);
			return mtrix_b[start_b+1];
		}
		if(mtrix_a[start_a]>mtrix_b[start_b])		
			return mtrix_a[start_a];
		else
			return mtrix_b[start_b];
	}

	int m,n;

	m=start_a+(end_a-start_a)/2;
	n=start_b+(end_b-start_b)/2;
	printf("alice send bob:    ");
	printf("%d--------%d\n",m,mtrix_a[m]);
	printf("bob send alice:	   ");
	printf("%d--------%d\n",n,mtrix_b[n]);
	if(mtrix_a[m]>mtrix_b[n])
		return search_median(mtrix_a,mtrix_b,start_a,m,n,end_b);
	else
		return search_median(mtrix_a,mtrix_b,m,end_a,start_b,n);
}

int main(int argc,char **argv)
{
	int i,n,m;
	int *mtrix_a,*mtrix_b;

	printf("please input the number alice or bob have:	");
	scanf("%d",&n);

	N=n;	//just for useful

	mtrix_a=(int *)malloc(sizeof(int)*(n+1));
	mtrix_b=(int *)malloc(sizeof(int)*(n+1));

	printf("please input the number alice haved:	\n");
	for(i=1;i<=n;i++)
		scanf("%d",&mtrix_a[i]);
	printf("please input the number bob haved:	\n");
	for(i=1;i<=n;i++)
		scanf("%d",&mtrix_b[i]);
	heapsort(mtrix_a,n);
	heapsort(mtrix_b,n);
	printf("alice number sort is:	");
	for(i=1;i<=n;i++)
		printf("%d  ",mtrix_a[i]);
	printf("\nbob number sort is:	");
	for(i=1;i<=n;i++)
		printf("%d  ",mtrix_b[i]);
	printf("\n");
	m=search_median(mtrix_a,mtrix_b,1,n,1,n);
	printf("\nthe m is:	%d\n",m);
	free(mtrix_a);
	free(mtrix_b);
	return 0;
}