c语言实现傅里叶变换

C语言实现傅里叶变换可以使用FFT（快速傅里叶变换）算法。以下是一个简单的例子：

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

#define PI 3.14159265358979323846

void FFT(double complex *x, int N)
{
    if (N <= 1) 
        return;
    
    double 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 k = 0; k < N/2; k++) {
        double complex t = cexp(-2.0*I*PI*k/N) * odd[k];
        x[k] = even[k] + t;
        x[k+N/2] = even[k] - t;
    }
}

int main()
{
    double complex x[] = {1, 2, 3, 4};
    int N = sizeof(x)/sizeof(x[0]);
    
    FFT(x, N);
    
    for (int i = 0; i < N; i++) {
        printf("%.2f%+.2fi\n", creal(x[i]), cimag(x[i]));
    }
    
    return 0;
}

在上面的代码中，我们使用了C语言的complex.h库来处理复数，使用了递归的方式来实现FFT算法。在main函数中，我们定义了一个长度为4的复数数组x，调用FFT函数进行傅里叶变换。最后输出每个复数的实部和虚部。

需要注意的是，FFT算法只适用于长度为2的幂次的数组，因此有时需要对输入数据进行零填充以满足这一条件。此外，由于计算机的精度限制，对于实数数组的傅里叶变换需要进行一些特殊处理，例如将实数数组转换为复数数组，并将不必要的虚部设置为0。