gladiator.cpp

四个小算法。红黑树

#include "stdio.h"
#include "stdlib.h"
#include "time.h"
#include "memory.h"
typedef struct Gnode
{
	int weight;
	int uppos;
    int midpos;
	int lowpos;
    Gnode *left;
	Gnode *right;
}Gnode;
typedef struct Aera
{
	int uppos;
	int lowpos;
	Gnode *nodepos;
}Aera;
void GenerateRand(int nGladiator[10000],int nContestants[10000]);
int Partition(int nGladiator[10000],int p,int r,int median);
void QuickSort(int nGladiator[10000],int nContestants[10000],Aera Apos);
Gnode *NodeTree;
int pos,count;
int main()
{
	int nGladiator[10000];
	int nContestants[10000];
	count=0;
	Aera Apos;
	NodeTree=(Gnode*)malloc(sizeof(Gnode));
	Apos.lowpos=0;
	Apos.uppos=9999;
	Apos.nodepos=NodeTree;
	pos=0;
	GenerateRand(nGladiator,nContestants);
	QuickSort(nGladiator,nContestants,Apos);
	for(int k=0;k<10000;k++)
		printf("%d ",nGladiator[k]);
    printf("\n");
	printf("%d",count);
    return 1;
}

void GenerateRand(int nGladiator[10000],int nContestants[10000])
{
	int i,j,tmp;
    for(i=0;i<10000;++i)
	{   
		
		nGladiator[i]=i;
		nContestants[i]=i;
	}
	srand(time(0));
	for(i=0;i<10000;++i)
	{   
		int chpos=rand()%10000;
		tmp=nGladiator[i];
		nGladiator[i]=nGladiator[chpos];
        nGladiator[chpos]=tmp;

	}
	srand(time(0)+100);
	for(i=0;i<10000;++i)
	{   
		int chpos=rand()%10000;
		tmp=nContestants[i];
		nContestants[i]=nContestants[chpos];
        nContestants[chpos]=tmp;
		
	}
	

}

int Partition(int nGladiator[10000],int p,int r,int median)
{
	int i,j,tmp,k;
	for(i=p,j=r;i<j;)
	{
		while(nGladiator[i]<median && i<j)
		{
			i++;
			count++;
		}
		while(nGladiator[j]>median && i<j)
		{
			j--;
			count++;
		}
		if(i<j)
		{
			tmp=nGladiator[j];
		    nGladiator[j]=nGladiator[i];
		    nGladiator[i]=tmp;
		}
		//for(k=0;k<100;k++)
		//	printf("%d ",nGladiator[k]);
		//printf("\n");
		//getchar();
	}

	if(nGladiator[i]==median)
		return i;
	if(nGladiator[j]==median)
		return j;
	if(nGladiator[i]<median)
		return i;
	if(nGladiator[j]>median)
		return j;

}

void MakeTree(Gnode *nodepos,Gnode node)
{
	*nodepos=node;
}
Aera GetNode(int weight)
{
	int i(0),dir(0);
	Aera Apos;
	Gnode *tmpnode,*nodepre;
	tmpnode=NodeTree;
	while(tmpnode!=NULL)
	{
		nodepre=tmpnode;
		if(weight<tmpnode->weight)
		{
			tmpnode=tmpnode->left;
			dir=0;
		}
		else if(weight>tmpnode->weight)
		{
			tmpnode=tmpnode->right;
			dir=1;
		}
		count++;
	}
	
	if(dir==0)
	{
		nodepre->left=(Gnode*)malloc(sizeof(Gnode));
		Apos.uppos=nodepre->midpos-1;
        Apos.lowpos=nodepre->lowpos;
		Apos.nodepos=nodepre->left;
	}
	else
	{
		nodepre->right=(Gnode*)malloc(sizeof(Gnode));
		Apos.uppos=nodepre->uppos;
        Apos.lowpos=nodepre->midpos+1;
		Apos.nodepos=nodepre->right;
	}
	return Apos;
	
}
void QuickSort(int nGladiator[10000],int nContestants[10000],Aera Apos)
{
	int i;
	Gnode node;
	while(pos<10000)
	{
		printf("%d ",pos);
		printf("\n");
		i=Partition(nGladiator,Apos.lowpos,Apos.uppos,nContestants[pos]);
		node.weight=nContestants[pos];
		node.uppos=Apos.uppos;
		node.lowpos=Apos.lowpos;
		node.midpos=i;
		node.left=NULL;
		node.right=NULL;
        MakeTree(Apos.nodepos,node);
		pos++;
		if(pos==10000)
			break;
		Apos=GetNode(nContestants[pos]);
	}
}