/**********************************
名稱：編程實現基于時間抽取的基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