请使用C语言写出fft

以下是C语言实现的FFT算法：

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

#define PI 3.14159265358979323846

void fft(double *x, double *y, int n)
{
    int i, j, k;
    double c, s, t1, t2;

    // Bit-reverse
    j = 0;
    for (i = 0; i < n; i++) {
        if (j > i) {
            t1 = x[j];
            t2 = y[j];
            x[j] = x[i];
            y[j] = y[i];
            x[i] = t1;
            y[i] = t2;
        }
        k = n / 2;
        while (k >= 1 && j >= k) {
            j -= k;
            k /= 2;
        }
        j += k;
    }

    // FFT
    for (k = 1; k < n; k *= 2) {
        for (i = 0; i < n; i += 2 * k) {
            for (j = 0; j < k; j++) {
                c = cos(-PI * j / k);
                s = sin(-PI * j / k);
                t1 = c * x[i + j + k] - s * y[i + j + k];
                t2 = s * x[i + j + k] + c * y[i + j + k];
                x[i + j + k] = x[i + j] - t1;
                y[i + j + k] = y[i + j] - t2;
                x[i + j] += t1;
                y[i + j] += t2;
            }
        }
    }
}

int main()
{
    int i, n;
    double *x, *y;

    printf("Enter the number of samples: ");
    scanf("%d", &n);

    x = (double *)malloc(n * sizeof(double));
    y = (double *)malloc(n * sizeof(double));

    printf("Enter the samples:\n");
    for (i = 0; i < n; i++) {
        scanf("%lf", &x[i]);
        y[i] = 0.0;
    }

    fft(x, y, n);

    printf("The FFT result is:\n");
    for (i = 0; i < n; i++) {
        printf("%lf + %lfi\n", x[i], y[i]);
    }

    free(x);
    free(y);

    return 0;
}

该程序接收用户输入的样本数和样本值，然后输出FFT变换结果。