用C语言实现FFT算法的编写，可与DFT时间作比较

编程实现基于时间抽取的基2的FFT算法 要求：实现任意长度的基于时间抽取的基2的FFT算法，统计算法运行所需时间，与DFT的直接实现进行运行时间对比，与现存的FFT算法运行时间进行对比。

/**********************************
名称：编程实现基于时间抽取的基2的FFT算法
要求：实现任意长度的基于时间抽取的基2的FFT算法，统计算法运行所需时间，与DFT的直接实现进行运行时间对比，与现存的FFT算法运行时间进行对比。
作者：朱振兴
QQ:1094296051
/**********************************/
#include 
#include 
#include 
#include 
#include 
#define PI 3.1415926535 
struct finger//---------------------复数结构体
{
	float shi;
	float xu; 
};

struct finger jiafa（struct finger astruct finger b）//---------------------复数加法
{
	struct finger result;
	result.shi = a.shi + b.shi;
	result.xu = a.xu + b.xu;
	return result;

}
struct finger jianfa（struct finger astruct finger b）//--------------------复数减法
{
	struct finger result;
	result.shi = a.shi - b.shi;
	result.xu  = a.xu - b.xu;
	return result;

}
struct finger chengfa（struct finger astruct finger b）//-------------------复数乘法
{
	struct finger result;
	result.shi = （a.shi * b.shi） - （a.xu * b.xu）;
	result.xu  = （a.shi * b.xu） + （a.xu * b.shi）;
	return result;

}
int daoxu（int aint n）//-------------------倒序实现
{
	int ibresult=0;
	  
		
		for（i=0;i		{
		b = a & 1;    
		a = a>>1; 
		result = result<<1;            
		result = result | b; 	        			
		}
		return result;	
}

struct finger xuanzhuanyinzi（int Nint P）//-------------------旋转因子计算
{
	
	struct finger wn; 	
	wn.shi = cos（2*PI/N*P）;		
	wn.xu = -sin（2*PI/N*P）;
	return wn;
	
	
} 
void diexingyunsuan（struct finger *pstruct finger *qstruct finger wn）//-------------------蝶形运算
{
	struct finger res1res2;
	struct finger temp;
    temp = chengfa（*qwn）;
	res1 = jiafa（*ptemp）;
	res2 = jianfa（*ptemp）;
	*q = res2;
	*p = res1;	
}

int log_2（int b）//-------------------log2的对数运算
{
	float result1cd;
	int result2;
	c = log10（b）; 
	d = log10（2）;
	result1 = c/d;	
	result2 = ceil（result1）; 
	return result2; 
	
 } 
void view1（）//---------------------界面1
{
	printf（“\n“）;
	printf（“\t\t\t---------------------\n“）;
	printf（“\t\t\t      FFT算法实现    \n“）;
	printf（“\t\t\t---------------------\n“）;
	printf（“\n“）;
}
void view2（）//---------------------界面2
{
	printf（“\n“）;
	printf（“\t\t\t---------------------\n“）;
	printf（“\t\t\t      DFT算法实现    \n“）;
	printf（“\t\t\t---------------------\n“）;
	printf（“\n“）;
}
/****************************************
                DFT算法
****************************************/
void DFT（）
{

	struct finger *A*x;
	struct  finger c;

	time_t  c_startc_end;
	int ijkLM=0N=0;
	view2（）;	
	printf（“注意：L 代表为2的L次方  \n“）;
	printf（“\nPlease input the size of L :  “）;//输入序列的大小
	scanf（“%d“&L）;
	N=pow（2L）;
	printf（“\n“）;
	M=log_2（N）;

	A = （struct finger*）malloc（N*sizeof（struct finger））;//---------------------设置动态数组
	if（!A）
	{
        printf（“Building the first array error!“）;
        exit（1）; 
    }
	else
		printf（“Building the first array successful!“）;
		

	x = （struct finger*）malloc（N*sizeof（struct finger））;
	if（!x）
	{
        printf（“Building the first a

 属性            大小     日期    时间   名称
----------- ---------  ---------- -----  ----
     目录           0  2018-11-24 00:44  FFT&DFT\
     目录           0  2018-11-24 00:44  FFT&DFT\Debug\
     文件      241720  2018-11-24 00:44  FFT&DFT\Debug\FFT&DFT.exe
     文件      262000  2018-11-24 00:44  FFT&DFT\Debug\FFT&DFT.ilk
     文件       20964  2018-11-24 00:43  FFT&DFT\Debug\FFT&DFT.obj
     文件      212968  2018-11-24 00:43  FFT&DFT\Debug\FFT&DFT.pch
     文件      467968  2018-11-24 00:44  FFT&DFT\Debug\FFT&DFT.pdb
     文件       33792  2018-11-24 00:44  FFT&DFT\Debug\vc60.idb
     文件       45056  2018-11-24 00:43  FFT&DFT\Debug\vc60.pdb
     文件        8082  2018-11-24 00:43  FFT&DFT\FFT&DFT.c
     文件        3413  2018-11-24 00:43  FFT&DFT\FFT&DFT.dsp
     文件         522  2018-11-24 00:44  FFT&DFT\FFT&DFT.dsw
     文件       33792  2018-11-24 00:44  FFT&DFT\FFT&DFT.ncb
     文件       48640  2018-11-24 00:44  FFT&DFT\FFT&DFT.opt
     文件         759  2018-11-24 00:44  FFT&DFT\FFT&DFT.plg