C++基础（快速傅里叶变换（FFT）源代码）

　　using namespace std;

　　const double PI = 3.141592653579323846;　　int n; // 数据个数 = 2的logn次⽅　　int logn;

　　/// 复数结构体

　　struct stCompNum　　{

　　double re;　　double im;　　};

　　stCompNum* pData1 = NULL;　　stCompNum* pData2 = NULL;

　　/// Examda提⽰: 正整数位逆序后输出　　int reverseBits(int value, int bitCnt)　　{　　int i;

　　int ret = 0;　　for(i=0; i　　{

　　ret |= (value & 0x1) << (bitCnt - 1 - i);　　value >>= 1;　　}

　　return ret;　　}

　　void main()　　{

　　ifstream fin(\"data.txt\");　　int i,j,k;

　　// input logn　　fin>>logn;　　// calculate n

　　for(i=0, n=1; i　　// malloc memory space　　pData1 = new stCompNum[n];　　pData2 = new stCompNum[n];　　// input raw data

　　for(i=0; i>pData1[i].re;　　for(i=0; i>pData1[i].im;　　// FFT transform　　int cnt = 1;　　for(k=0; k　　{　　for(j=0; j　　{　　int len = n / cnt;

　　double c = - 2 * PI / len;　　for(i=0; i　　{　　int idx = len * j + i;

　　pData2[idx].re = pData1[idx].re + pData1[idx + len/2].re;　　pData2[idx].im = pData1[idx].im + pData1[idx + len/2].im;　　}

　　for(i=len/2; i　　{

　　double wcos = cos(c * (i - len/2));　　double wsin = sin(c * (i - len/2));　　int idx = len * j + i;　　stCompNum tmp;

　　tmp.re = pData1[idx - len/2].re - pData1[idx].re;　　tmp.im = pData1[idx - len/2].im - pData1[idx].im;　　pData2[idx].re = tmp.re * wcos - tmp.im * wsin;　　pData2[idx].im = tmp.re * wsin + tmp.im * wcos;

　　}　　}

　　cnt <<= 1;

　　stCompNum* pTmp = NULL;　　pTmp = pData1;　　pData1 = pData2;　　pData2 = pTmp;　　}

　　// resort

　　for(i=0; i　　{

　　int rev = reverseBits(i, logn);　　stCompNum tmp;　　if(rev > i)　　{

　　tmp = pData1[i];

　　pData1[i] = pData1[rev];　　pData1[rev] = tmp;　　}　　}

　　// output result data

　　for(i=0; i　　cout<　　for(i=0; i　　cout<　　// free memory space　　delete []pData1;　　delete []pData2;　　fin.close();

　　system(\"pause\");　　}

　　输⼊⽂件data.txt的内容如下：　　4

　　2.2 4.5 6.7 8.5 10.2 12.3 14.5 16.2 19.3 21.2 25.2 29.4 36.4 39.2 45.2 50.1　　0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0