请用C语言写出傅里叶变换的算法

傅里叶变换的算法可以使用库函数实现，也可以手动编写实现。这里给出手动编写实现的C语言代码：

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

#define PI 3.14159265358979323846

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

    double even_x[n/2], even_y[n/2], odd_x[n/2], odd_y[n/2];
    for (int i = 0; i < n/2; i++) {
        even_x[i] = x[2*i];
        even_y[i] = y[2*i];
        odd_x[i] = x[2*i+1];
        odd_y[i] = y[2*i+1];
    }

    fft(even_x, even_y, n/2);
    fft(odd_x, odd_y, n/2);

    for (int k = 0; k < n/2; k++) {
        double t_re = cos(2*PI*k/n) * odd_x[k] + sin(2*PI*k/n) * odd_y[k];
        double t_im = cos(2*PI*k/n) * odd_y[k] - sin(2*PI*k/n) * odd_x[k];

        x[k] = even_x[k] + t_re;
        y[k] = even_y[k] + t_im;
        x[k+n/2] = even_x[k] - t_re;
        y[k+n/2] = even_y[k] - t_im;
    }
}

int main()
{
    int n = 8;
    double x[n], y[n];

    // 输入原始数据
    printf("请输入 %d 个实数：\n", n);
    for (int i = 0; i < n; i++) {
        scanf("%lf", &x[i]);
        y[i] = 0;
    }

    // 傅里叶变换
    fft(x, y, n);

    // 输出结果
    printf("傅里叶变换后的结果：\n");
    for (int i = 0; i < n; i++) {
        printf("%lf + %lfi\n", x[i], y[i]);
    }

    return 0;
}

其中，`fft` 函数是实现傅里叶变换的核心算法，输入参数 `x` 和 `y` 是原始数据的实部和虚部，输出结果也存储在 `x` 和 `y` 中。在 `main` 函数中，先输入原始数据，然后调用 `fft` 函数进行傅里叶变换，最后输出结果。