c++ fft算法代码

以下是一个基于C语言的FFT算法代码示例：

#include <stdio.h>
#include <stdlib.h>
#include <math.h>

#define PI 3.14159265358979323846

// 计算快速傅里叶变换
void fft(double *real, double *img, int n) {
    int i, j, k;
    double *xr, *xi, *yr, *yi, *tr, *ti;
    double ur, ui, sr, si, tr1, ti1, tr2, ti2;

    xr = (double *)malloc(n * sizeof(double));
    xi = (double *)malloc(n * sizeof(double));
    yr = (double *)malloc(n * sizeof(double));
    yi = (double *)malloc(n * sizeof(double));
    tr = (double *)malloc(n / 2 * sizeof(double));
    ti = (double *)malloc(n / 2 * sizeof(double));

    for (i = 0; i < n; i++) {
        xr[i] = real[i];
        xi[i] = img[i];
    }

    j = 0;
    for (i = 0; i < n - 1; i++) {
        if (i < j) {
            tr1 = xr[i];
            ti1 = xi[i];
            xr[i] = xr[j];
            xi[i] = xi[j];
            xr[j] = tr1;
            xi[j] = ti1;
        }
        k = n / 2;
        while (k <= j) {
            j -= k;
            k /= 2;
        }
        j += k;
    }

    for (i = 1; i < n; i *= 2) {
        ur = cos(PI / i);
        ui = sin(PI / i);
        sr = 1.0;
        si = 0.0;
        for (j = 0; j < i; j++) {
            tr[j] = ur * xr[j + i] - ui * xi[j + i];
            ti[j] = ui * xr[j + i] + ur * xi[j + i];
            xr[j + i] = xr[j] - tr[j];
            xi[j + i] = xi[j] - ti[j];
            xr[j] += tr[j];
            xi[j] += ti[j];
            tr1 = sr * ur - si * ui;
            ti1 = si * ur + sr * ui;
            sr = tr1;
            si = ti1;
        }
    }

    for (i = 0; i < n; i++) {
        real[i] = xr[i];
        img[i] = xi[i];
    }

    free(xr);
    free(xi);
    free(yr);
    free(yi);
    free(tr);
    free(ti);
}

int main() {
    int i, n;
    double *real, *img;

    printf("请输入数据点数：\n");
    scanf("%d", &n);

    real = (double *)malloc(n * sizeof(double));
    img = (double *)malloc(n * sizeof(double));

    printf("请输入实部和虚部：\n");
    for (i = 0; i < n; i++) {
        scanf("%lf %lf", &real[i], &img[i]);
    }

    fft(real, img, n);

    printf("FFT结果为：\n");
    for (i = 0; i < n; i++) {
        printf("%lf + %lfi\n", real[i], img[i]);
    }

    free(real);
    free(img);

    return 0;
}