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

字號： 小 中 大

為了看明白那堆積分變換，不得不把復(fù)變函數(shù)掃了一遍，可看完了，才發(fā)現(xiàn)原來這堆變換說白了只是一些數(shù)字游戲，Examda提示: 也沒用到啥復(fù)變函數(shù)的知識。最后，用C++程序?qū)崿F(xiàn)了下FFT，也算告一段落，代碼如下：
    #include
    #include
    #include
    using namespace std;
    const double PI = 3.14159265358979323846;
    int n; // 數(shù)據(jù)個數(shù) = 2的logn次方
    int logn;
    /// 復(fù)數(shù)結(jié)構(gòu)體
    struct stCompNum
    {
    double re;
    double im;
    };
    stCompNum* pData1 = NULL;
    stCompNum* pData2 = NULL;
    /// Examda提示: 正整數(shù)位逆序后輸出
    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的內(nèi)容如下：
    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