c语言实现快速傅里叶变换

实现快速傅里叶变换需要用到递归和分治的思想，以下是一个简单的C语言实现：

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

#define PI 3.14159265358979323846

typedef struct {
    double real;
    double imag;
} complex;

void fft(complex *x, int n)
{
    if (n <= 1) {
        return;
    }

    complex even[n / 2], odd[n / 2];
    for (int i = 0; i < n / 2; i++) {
        even[i] = x[2 * i];
        odd[i] = x[2 * i + 1];
    }

    fft(even, n / 2);
    fft(odd, n / 2);

    for (int i = 0; i < n / 2; i++) {
        complex t = {cos(2 * PI * i / n), -sin(2 * PI * i / n)};
        t.real *= odd[i].real;
        t.imag *= odd[i].imag;

        x[i].real = even[i].real + t.real;
        x[i].imag = even[i].imag + t.imag;
        x[i + n / 2].real = even[i].real - t.real;
        x[i + n / 2].imag = even[i].imag - t.imag;
    }
}

int main()
{
    int n = 8;
    complex x[n];

    for (int i = 0; i < n; i++) {
        x[i].real = sin(2 * PI * i / n);
        x[i].imag = 0;
    }

    fft(x, n);

    for (int i = 0; i < n; i++) {
        printf("(%f, %f)\n", x[i].real, x[i].imag);
    }

    return 0;
}

这里使用了一个复数结构体来表示复数，`fft`函数实现了快速傅里叶变换，其中递归调用了自己，将原始序列分为偶数项和奇数项，计算其DFT，然后合并成整个序列的DFT。主函数中生成了一个正弦波信号，调用`fft`函数得到其频域表示，并输出到控制台。