用C语言写一个傅里叶变换

傅里叶变换是一种将信号从时域转换到频域的数学方法，可以分析信号的频域特性，广泛应用于信号处理、图像处理等领域。下面是一个用C语言实现的傅里叶变换的示例代码：

#include <stdio.h>
#include <stdlib.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 = (Complex *)malloc(N / 2 * sizeof(Complex));
    Complex *odd = (Complex *)malloc(N / 2 * sizeof(Complex));

    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++) {
        double angle = -2 * PI * i / N;
        Complex w = { cos(angle), sin(angle) };
        w.real *= odd[i].real;
        w.imag *= odd[i].imag;
        x[i].real = even[i].real + w.real;
        x[i].imag = even[i].imag + w.imag;
        x[i + N / 2].real = even[i].real - w.real;
        x[i + N / 2].imag = even[i].imag - w.imag;
    }

    free(even);
    free(odd);
}

void print_complex(Complex x) {
    printf("%.2f + %.2fi\n", x.real, x.imag);
}

int main() {
    int N = 8;
    Complex x[] = { {0, 0}, {1, 1}, {2, 2}, {3, 3}, {4, 4}, {5, 5}, {6, 6}, {7, 7} };

    fft(x, N);

    for (int i = 0; i < N; i++) {
        printf("X[%d] = ", i);
        print_complex(x[i]);
    }

    return 0;
}

这里实现的是基于递归的快速傅里叶变换（FFT），可以对长度为2的幂的序列进行变换。在实现中，使用了结构体Complex来表示复数，fft函数就是用来计算傅里叶变换的，print_complex函数用来输出复数。在main函数中定义一个长度为8的复数序列，然后调用fft函数进行变换，最后输出变换后的结果。