傅里叶变换和傅里叶逆变换的C++代码，亲测

傅里叶变换和傅里叶逆变换的C++代码，亲测，有详细的解释。 有问题可以留言。

//#include “stdafx.h“
//#include  

#include“math.h“
#include 
#include “fft.h“
using namespace std;

int wh（int Width）
{
	int wp=0;//存储w的2的幂数
	int w=1;
	while（w	{
		w=w*2;
		wp++;
	}
	return（w）;
	
}

//这个函数调用二维傅里叶变换函数，并将得到的结果shift
//int FFT2shifft（unsigned char*aint lWidthint lHeightcomplex *FDshift）
//{
//	
//	int w=1; 
//	int h=1;
//	int wp=0;//存储w的2的幂数
//	int hp=0;//存储h的2的幂数 
//	
//	int ij;
//	complex *TD;
//	complex *FD;
//	//////计算刚好大于或等于lWidth，lHeight的2的整数次幂，和相应的幂数///////////////
//	
//	while（w//	{
//		w=w*2;
//		wp++;
//	}
//	while（h//	{
//		h=h*2;
//		hp++;
//	}	 
//	
//	//这2行是对指针进行赋值，使它指向一个复数一维数组的首地址
//    TD=new complex[w*h];
//	FD=new complex[w*h];
//	for（  i=0;i//	{
//		FD[i]=complex（0.00.0）;//FD初值设为0
//	}
//    TD=DataFitFormat（alWidthlHeight）;//调用已有函数DataFitFormat初始化TD
//
//	FFT_2D（ TD FD  lWidth lHeight）;//调用已有函数FFT_2D二维FFT返回的FD，即是复数矩阵，比原来大。
//    
//	for（i=0;i//		for（j=0;j//		{
//			int i1=（i//			int j1=（j//			FDshift[i1*w+j1]=FD[i*w+j];
//			
//		}
//		
//		//在哪里创建就在哪里释放	
//		delete [] FD;
//		FD = NULL ;
//		delete [] TD;
//		TD = NULL ;
//		
//		return 0;
//		
//}


//将数组转换为适合FFT处理的数据（数组长度为2的整数次幂）填充的数据补零操作.
//当lHeight=1时表示为对一维数组处理.data为对二维数据的一维表示，是按照从左到右，从上到下。
complex * DataFitFormat（double *dataint lWidthint lHeight）
{
	complex *TD;
	int w=1;
	int h=1;
	int wp=0;//存储w的2的幂数
	int hp=0;//存储h的2的幂数
//////计算刚好大于或等于lWidth，lHeight的2的整数次幂，和相应的幂数///////////////
	while（w	{
		w=w*2;
		wp++;
	}
	while（h	{
		h=h*2;
		hp++;
	}
	TD=new complex[w*h];
////////////////////////////////////////////////////////////////////////////////
	for（int i=0;i	{
		if（i		{
			for（int j=0;j			{
				if（j< lWidth）
				{
					TD[i*w+j]=complex（data[i*lWidth+j]0）;//将char数据，准换为实数为data数据，虚数为0的复数
				}
				else
				{
					TD[i*w+j]=complex（00）;//对于超出原数据的数据进行补零操作
				}

			}
		}
		else
		{
			for（int j=0;j			{
				TD[i*w+j]=complex（00）;//对于超出原数据的数据进行补零操作
		
			}
		}
	}

 return TD;

}
  
 
 
//一维FFT运算，len为一维数组的真实长度。而TD和FD数组的长度都是
//经过 InitTDAndFD得到的适合FFT处理的数组长度为2的整数次幂的数组 。
void FFT_1D（complex *TDcomplex*FDint Len）
{
	 
	int l=1;
	int lp=0;
	int p=0;
	double angle=0;//中间变量及角度
	complex *W*X1*X2*X;

	while（l	{
		l=l*2;
		lp++;
	}
	int r=lp;

	long N=1<	//?为什么没有X
	W=new complex[N/2];//存放旋转系数
	X1=new complex[N];//
    X2=new complex[N];//分配运算的存储器
	for（long i=0;i	{
		angle=-i*PI*2/N;
		W[i]=complex（cos（angle）sin（angle））;
	}

	memcpy（X1TDsizeof（complex）*N）;//将TD所在的内存数据拷贝到X1中

///////////////////////////核心算法：蝶形运算/////////////
	for（long k

 属性            大小     日期    时间   名称
----------- ---------  ---------- -----  ----

     文件      44544  2013-11-27 00:33  testfft\Debug\testfft.exe

     文件     347952  2013-11-27 00:33  testfft\Debug\testfft.ilk

     文件     658432  2013-11-27 00:33  testfft\Debug\testfft.pdb

     文件   16777216  2013-11-28 00:59  testfft\ipch\testfft-a5d448ac\testfft-545235cc.ipch

     文件       4014  2013-11-27 00:33  testfft\testfft\Debug\cl.command.1.tlog

     文件      55328  2013-11-27 00:33  testfft\testfft\Debug\CL.read.1.tlog

     文件       3126  2013-11-27 00:33  testfft\testfft\Debug\CL.write.1.tlog

     文件      60178  2013-11-27 00:33  testfft\testfft\Debug\fft.obj

     文件          2  2013-11-27 00:33  testfft\testfft\Debug\link-cvtres.read.1.tlog

     文件          2  2013-11-27 00:33  testfft\testfft\Debug\link-cvtres.write.1.tlog

     文件          2  2013-11-27 00:33  testfft\testfft\Debug\link.5288-cvtres.read.1.tlog

     文件          2  2013-11-27 00:33  testfft\testfft\Debug\link.5288-cvtres.write.1.tlog

     文件          2  2013-11-27 00:33  testfft\testfft\Debug\link.5288.read.1.tlog

     文件          2  2013-11-27 00:33  testfft\testfft\Debug\link.5288.write.1.tlog

     文件          2  2013-11-27 00:33  testfft\testfft\Debug\link.9400-cvtres.read.1.tlog

     文件          2  2013-11-27 00:33  testfft\testfft\Debug\link.9400-cvtres.write.1.tlog

     文件          2  2013-11-27 00:33  testfft\testfft\Debug\link.9400.read.1.tlog

     文件          2  2013-11-27 00:33  testfft\testfft\Debug\link.9400.write.1.tlog

     文件       3346  2013-11-27 00:33  testfft\testfft\Debug\link.command.1.tlog

     文件       6538  2013-11-27 00:33  testfft\testfft\Debug\link.read.1.tlog

     文件       1858  2013-11-27 00:33  testfft\testfft\Debug\link.write.1.tlog

     文件      37536  2013-11-27 00:33  testfft\testfft\Debug\main.obj

     文件        786  2013-11-27 00:33  testfft\testfft\Debug\mt.command.1.tlog

     文件        882  2013-11-27 00:33  testfft\testfft\Debug\mt.read.1.tlog

     文件        518  2013-11-27 00:33  testfft\testfft\Debug\mt.write.1.tlog

     文件       1648  2013-11-27 00:33  testfft\testfft\Debug\rc.command.1.tlog

     文件       1246  2013-11-27 00:33  testfft\testfft\Debug\rc.read.1.tlog

     文件        958  2013-11-27 00:33  testfft\testfft\Debug\rc.write.1.tlog

     文件        406  2013-11-26 13:38  testfft\testfft\Debug\testfft.exe.embed.manifest

     文件        472  2013-11-27 00:33  testfft\testfft\Debug\testfft.exe.embed.manifest.res

............此处省略24个文件信息