shortest_newest.c

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

#define FEATURE_MAX_D 128
#define MAXSIZE 922337
#define L 1000
typedef struct feature
{
	double descr[FEATURE_MAX_D];
}Feature;//存储文件数据的结构体
typedef struct 
{
	double Distance_0;//存储该特征值的指针
	int count;
}Dist;//存储特征值的结点结构
#include <stdio.h>
#include <math.h>
#include <malloc.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 t;	
	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;
			t=Distance[low].count; Distance[low]=Distance[high]; Distance[low].count=t;							

			while(low<high&&Distance[low].Distance_0<=pivotkey)
				++low;
			t=Distance[high].count; Distance[high]=Distance[low]; Distance[high].count=t;				
		}//
		t=Distance[low].count;Distance[low]=temp; Distance[low].count=t;	
		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++;
		}
	}//
}
/****************************************************/
float SearchShortest(Feature *feat1,Feature *feat2,Dist* Distance,int num1,int num2,float *Stand)
{
	int i,j,I,J,ShorterLen[L],Maxcount=0,True=0;
	FILE*fp;
	double DF0=0.0,XL=0.0,Shortest=2000000.0;//
	fp=fopen("r.txt","w+");
	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;
			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,"正确率是： %f\n",(((float)True)/((float)num2)));
	fclose(fp);
	return(((float)True)/((float)num2));
}
/********************/
void readfile(char*filename,int* num,Feature **feat)
{
	FILE*fp;
	scanf("%s",filename);
	fp=fopen(filename,"rb");
	fread(num,sizeof(int),1,fp);
	*feat=(Feature *)malloc(*num * sizeof(Feature));
	fread(*feat,sizeof(Feature),*num,fp);
	fclose(fp);
}//读文件
void ALLSearch(int DataNum1,int DataNum2,Feature *feat1,Feature *feat2,float *Stand)
{
	FILE*fp;
	int I=0,dim=0,J=0,count1=0,count2=0,nu;
	double sum=0,temp,min=MAXSIZE,distance;
	fp=fopen("Result.txt","w+");
	for(J=0;J<DataNum2;J++)
	{
		for(I=0;I<DataNum1;I++)
		{//从A中找数据
			for(dim=0;dim<128;dim++)
			{//每一维的平方和
				temp=feat1[I].descr[dim]-feat2[J].descr[dim];
				sum=sum+temp*temp;
			}
			distance=sqrt(sum);//计算欧式距离
			count2++;
			if(distance<min)
			{//求最短距离和该元素的位置
				min=distance;
				nu=count2;
			}
			sum=0;//sum置0；
		}
		count1++;
		//fprintf(fp,"%f\n",min);
		Stand[J]=min;
		min=MAXSIZE;count2=0;
	}
	fclose(fp);
}//搜索最短距离
/************************/

#include "time.h"
void main()
{
	Feature *feat1,*feat2;//定义feat1来读取文件数据
	Dist *Distance;
	float *Stand;
	int DataNum1=0,DataNum2=0;
	long T1,T2;
	float True;
	char filename1[10],filename2[10];	
	FILE *fp1,*fp2;
	clock_t sTime,eTime;
	printf("输入第一个文件名!\n");
	gets(filename1);
	fp1=fopen(filename1,"rb");//
	fread(&DataNum1, sizeof( int ), 1, fp1 );//读取该文件中数据的数目
	feat1=(Feature*)malloc(DataNum1*sizeof(Feature));//为feat申请空间
	fread(feat1,sizeof(Feature),DataNum1,fp1);//feat读取文件中的所有数据
	fclose(fp1);/////////////////
	Distance=(Dist*)malloc(DataNum1*sizeof(Dist));/////
	printf("输入第二个文件名!\n");
	gets(filename2);
	fp2=fopen(filename2,"rb");//
	fread(&DataNum2, sizeof( int ), 1, fp2 );//读取该文件中数据的数目
	feat2=(Feature*)malloc(DataNum2*sizeof(Feature));//为feat申请空间
	fread(feat2,sizeof(Feature),DataNum2,fp2);//feat读取文件中的所有数据
	fclose(fp2);//
	Stand=(float*)malloc(DataNum2*sizeof(float));

	printf("正在进行全搜索........\n");
	sTime=clock();
	ALLSearch(DataNum1,DataNum2,feat1,feat2,Stand);
	printf("全搜索结束，按任意健继续/n");
	getchar();
	eTime=clock();
	T1=eTime-sTime;
	printf("全搜索时间: %d ms\n",T1);

	DistanceFrom0(feat1,DataNum1,Distance);//
	QuickSort(Distance,0,DataNum1-1);//
	printf("正在进行改进搜索........\n");
	sTime=clock();
	True=SearchShortest(feat1,feat2,Distance,DataNum1,DataNum2,Stand);
	eTime=clock();
	T2=eTime-sTime;
	printf("正确率: %f \n",True);
	printf("改进搜索时间: %d ms\n",T2);
	printf("时间效率: %f ms\n",(float)T2/(float)T1);
	printf("算法效率: %f \n",True*(float)T1/(float)T2);
}//main