shortest_fuc.h

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

void DistanceFrom0(Feature *feat,int num,Dist* Distance)
{
	int i,I;
	double DF0=0.0;//
	for(i=0;i<num;i++,feat++)
	{
		for(I=1;I<=128;I++)
			DF0=DF0+(feat->descr[I-1])*(feat->descr[I-1]);
		Distance[i].Distance_0=DF0;
		Distance[i].count=i;
	}
}//

int Serach_Bin(Dist* Distance,double DF0,int num1)
{
	int low=0,high=num1-1,mid;
	while(low<=high)
	{
		mid=(low+high)/2;
		if(DF0==Distance[mid].Distance_0)
			return mid;
		else if(DF0<Distance[mid].Distance_0)
			high=mid-1;
		else low=mid+1;
	}
	return mid;
}
/*************************************************************/
void QuickSort(Dist* Distance,int low,int high)
{
	int pivotloc;		
	Dist temp;
	int t1;	
	double pivotkey;
	if(low<high)
	{		
			temp=Distance[low];
			pivotkey=Distance[low].Distance_0;
			while(low<high)
			{
				while(low<high&&Distance[high].Distance_0>=pivotkey)
					--high;
				t1=Distance[low].count;

				Distance[low]=Distance[high];
				Distance[low].count=t1;

				while(low<high&&Distance[low].Distance_0<=pivotkey)
					++low;
				t1=Distance[high].count;

				Distance[high]=Distance[low];
				Distance[high].count=t1;
			}//
			t1=Distance[low].count;	
			Distance[low]=temp;
			Distance[low].count=t1;	
			pivotloc=low;
		QuickSort(Distance,low,pivotloc);
		QuickSort(Distance,pivotloc+1,high);
	}
}
/**********************************************************************/
void Shorter(double DF0,Dist* Distance,int* ShorterLen,int num1)
{
	int p,snum=0,up,down,t,i=1,j=1;
	p=Serach_Bin(Distance,DF0,num1);
	up=down=p;

	ShorterLen[snum++]=Distance[p].count;

	while(snum<L)
	{
		while(down>0&&down<num1&&Distance[down-1].Distance_0==DF0&&snum<L)
		{
			ShorterLen[snum]=Distance[down-1].count;
			down--;
			snum++;
		}
		while(up>=0&&up<num1-1&&Distance[up+1].Distance_0==DF0&&snum<L)
		{
			ShorterLen[snum]=Distance[up+1].count;
			up++;
			snum++;
		}
		break;
	}//
	if(down==p)	down--;
	if(up==p)	up++;
	while(snum<L)
	{
		i=1;
		t=(L-snum)/2+1;
		while(down>=0&&down<num1&&snum<L&&i<=t)
		{
			ShorterLen[snum]=Distance[down].count;
			down--;
			snum++;
			i++;
		}
		j=1;
		while(up>=0&&up<num1&&snum<L&&j<=t)
		{
			ShorterLen[snum]=Distance[up].count;
			up++;
			snum++;
			j++;
		}
	}//
}
/****************************************************/
void SearchShortest(Feature *feat1,Feature *feat2,Dist* Distance,int num1,int num2)
{
	int i,j,I,J,ShorterLen[L],Maxcount=0,True=0;
	FILE*fp,*fp0;
	double DF0=0.0,XL=0.0,MAX=MINSIZE,Shortest=2000000.0;//
	float *Stand,s;
	fp=fopen("r.txt","w+");
	fp0=fopen("Result.txt","r");

	Stand=(float*)malloc(num2*sizeof(float));
	for(i=0;i<num2;i++)
		fscanf(fp0,"%f",&Stand[i]);
	fclose(fp0);
	for(i=0;i<num2;i++,feat2++)
	{
		for(I=1;I<=128;I++)
			DF0=DF0+(feat2->descr[I-1])*(feat2->descr[I-1]);
		Shorter(DF0,Distance,ShorterLen,num1);
		for(j=0;j<L;j++)
		{
			for(J=1;J<=128;J++)
				XL=XL+((feat2->descr[J-1])-((feat1+ShorterLen[j])->descr[J-1]))*((feat2->descr[J-1])-((feat1+ShorterLen[j])->descr[J-1]));
			if(Shortest>XL)
			{
				Shortest=XL;
				s=j;
			}
			XL=0.0;
		}
		if((int)(sqrt(Shortest)*10000)==(int)(Stand[i]*10000))	
			True++;
		fprintf(fp,"文件2中第%d个数据在文件1中的最短距离是： %f\n",i,sqrt(Shortest));
		printf("文件2中第%d个数据在文件1中的最短距离是： %f\n",i,sqrt(Shortest));
		Shortest=2000000.0;
	}
	fprintf(fp,"TRue is %f",(((float)True)/((float)num2)));
	fclose(fp);

}