C++基礎(快速傅裡葉變換（FFT）源代碼)

爲了看明白那堆積分變換，不得不把複變函數掃了一遍，可看完了，才發現原來這堆變換說白了衹是一些數字遊戯，Examda提示: 也沒用到啥複變函數的知識。最後，用C 程序實現了下FFT，也算告一段落，代碼如下：
　　#include
　　#include
　　#include
　　using namespace std;
　　const double PI = 3.14159265358979323846;
　　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) >= 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 i)
　　{
　　tmp = pData1[i];
　　pData1[i] = pData1[rev];
　　pData1[rev] = tmp;
　　}
　　}
　　// output result data
　　for(i=0; i　　cout