function.h

数据结构课程设计_任意大数的加减乘运算器

void Move(DataNode*c1,DataNode*c2)
{
	(*c1)=(*c2);
	if(c2->predim!=NULL)
	{c2->predim->nextdim=c1;c2->predim=NULL;}
	if(c2->nextdim!=NULL)
	{c2->nextdim->predim=c1;c2->nextdim=NULL;}
}//
/*****************************************************************/
int Partition(DataNode*cross,int low,int high)
{
	DataNode temp;
	double pivotkey;
	Move(&temp,&cross[low]);
	pivotkey=*(cross[low].data);
	while(low<high)
	{
		while(low<high&&*(cross[high].data)>=pivotkey)
			--high;
	/*	if(low!=high)	*/Move(&cross[low],&cross[high]);
		while(low<high&&*(cross[low].data)<=pivotkey)
			++low;
		Move(&cross[high],&cross[low]);
	}//
	/*	if(low!=high)*/	Move(&cross[low],&temp);
	return low;
}//
/*********************************************************************/
void QuickSort(DataNode*cross,int low,int high)
{
	int pivotloc;
	if(low<high)
	{
		pivotloc=Partition(cross,low,high);
		QuickSort(cross,low,pivotloc);
		QuickSort(cross,pivotloc+1,high);
	}
}//
/************************************构造搜索结构**************************/
void Buildserach(struct feature*feat,int num,crossdata *CrossData)
{
	int i,j;
	for(i=1;i<=FEATURE_MAX_D;i++)
		(*CrossData).Cross[i]=(DataNode*)malloc(num*sizeof(DataNode));//为每一列数据申请num个空间
	for(i=0;i<num;i++,feat++)
	{
		for(j=1;j<=FEATURE_MAX_D;j++)
			(*CrossData).Cross[j][i].data=&feat->descr[j-1];
	}
	for(i=1;i<=FEATURE_MAX_D;i++)
	{
		for(j=0;j<num;j++)
		{
			(*CrossData).Cross[i][j].Dim=i;
			(*CrossData).Cross[i][j].visit=0;
			if(i==1)
			{
				(*CrossData).Cross[i][j].predim=NULL;
				(*CrossData).Cross[i][j].nextdim=NULL;
			}
			else
			{
				(*CrossData).Cross[i][j].predim=&((*CrossData).Cross[i-1][j]);
				(*CrossData).Cross[i-1][j].nextdim=&((*CrossData).Cross[i][j]);
				(*CrossData).Cross[i][j].nextdim=NULL;
			}
		}
	}//
	for(i=1;i<=FEATURE_MAX_D;i++)
		QuickSort(CrossData->Cross[i],0,num-1);
}//Buildserach
/*****************************************************************/
int Serach_Bin(DataNode *Cross,double data2,int DataNum1)
{
	int low=0,high=DataNum1-1,mid;
	while(low<=high)
	{
		mid=(low+high)/2;
		if(data2==*(Cross[mid].data))
			return mid;
		else if(data2<*(Cross[mid].data))
			high=mid-1;
		else low=mid+1;
	}
	return mid;
}
/******************************************************************/
void Shorter(double data2,DataNode *Cross,DataNode** Shorterlen,int DataNum1)
{
	int p,snum=0,up,down;
	p=Serach_Bin(Cross,data2,DataNum1);
	up=down=p;
	Shorterlen[snum++]=&Cross[p];
	Cross[p].visit='1';

	while(snum<10)
	{
		while(down>0&&down<DataNum1&&*(Cross[down-1].data)==data2&&snum<10)
		{
			Shorterlen[snum]=&Cross[down-1];
			Cross[down-1].visit='1';////////
			down--;
			snum++;
		}
		while(up>=0&&up<DataNum1-1&&*(Cross[up+1].data)==data2&&snum<10)
		{
			Shorterlen[snum]=&Cross[up+1];
			Cross[up+1].visit='1';////////
			up++;
			snum++;
		}
		break;
	}//
	if(down==p)	down--;
	if(up==p)	up++;
	while(snum<10)
	{
		while(down>=0&&down<DataNum1/*&&Cross[down-1]==data2*/&&snum<10)
		{
			Shorterlen[snum]=&Cross[down];
			Cross[down].visit='1';////////
			down--;
			snum++;
		}
		while(up>=0&&up<DataNum1/*&&Cross[up+1]==data2*/&&snum<10)
		{
			Shorterlen[snum]=&Cross[up];
			Cross[up].visit='1';////////
			up++;
			snum++;
		}
	}//
}
/********************************************************************/
void Allsearch(DataNode* DATA,DataNode**s,int *t)
{
	DataNode* p;
	int T=0;
	if(DATA->visit=='1')
		T++;	
	p=DATA->predim;
	while(p!=NULL&&p->Dim>=1)
	{
		if(p->visit=='1')
			T++;
		p=p->predim;
	}

	p=DATA->nextdim;
	while(p!=NULL&&p->Dim<=128)
	{
		if(p->visit=='1')
			T++;
		p=p->nextdim;
	}
	if(*(t)<T)
	{
		*(t)=T;
		*s=DATA;
	}
}
/************************************************************************/
void PrintNum(DataNode*s,double* Descr)
{
	DataNode *s0=s;
	double result=0.0,temp;
	FILE*fp;
	

	int i;
	fp=fopen("r.txt","a+");
	while(s0->predim!=NULL&&s0->Dim>=1)
		s0=s0->predim;
	for(i=0;i<128;i++)
	{
		result=result+(Descr[i]-*(s0->data))*(Descr[i]-*(s0->data));			
		s0=s0->nextdim;
	}
			fprintf(fp,"%f\n",sqrt(result));
			//printf("\n");
}
/**************************************************************************************/
void SearchShortest(struct feature* feat2,int DataNum2,crossdata CrossData,int DataNum1)
{
	DataNode *Shorterlen[129][10],*S=NULL;	
	int i,j,I,temp=0;//temp
	for(i=0;i<DataNum2;i++,feat2++)
	{
		for(I=1;I<=FEATURE_MAX_D;I=I++)
			Shorter(feat2->descr[I-1],CrossData.Cross[I],Shorterlen[I],DataNum1);	
		for(I=1;I<=FEATURE_MAX_D;I=I++)
		{
			for(j=0;j<10;j++)
				Allsearch(Shorterlen[I][j],&S,&temp);
		}
		PrintNum(S,feat2->descr);
		//printf("\n");
		//getchar();
		if(i==500) return;
		temp=0;
	}//
}//