用C语言写基于蝶形算法FFT

好的，下面是基于蝶形算法FFT的C语言代码：

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

#define PI 3.14159265358979323846

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

// 计算FFT的蝶形操作
void butterfly(Complex *x, int n) {
    int i, j, k;
    Complex t, w;

    for (i = 1, j = n / 2; i < n - 1; i++) {
        if (i < j) {
            t = x[j];
            x[j] = x[i];
            x[i] = t;
        }

        k = n / 2;

        while (k <= j) {
            j -= k;
            k /= 2;
        }

        j += k;
    }

    for (k = 1; k < n; k *= 2) {
        for (j = 0; j < k; j++) {
            w.real = cos(PI * j / k);
            w.imag = -sin(PI * j / k);

            for (i = j; i < n; i += 2 * k) {
                t.real = w.real * x[i + k].real - w.imag * x[i + k].imag;
                t.imag = w.real * x[i + k].imag + w.imag * x[i + k].real;
                x[i + k].real = x[i].real - t.real;
                x[i + k].imag = x[i].imag - t.imag;
                x[i].real += t.real;
                x[i].imag += t.imag;
            }
        }
    }
}

int main() {
    int n, i;
    Complex *x;

    printf("请输入序列长度n：");
    scanf("%d", &n);

    // 分配内存空间
    x = (Complex*)malloc(n * sizeof(Complex));

    printf("请输入序列x：\n");
    for (i = 0; i < n; i++) {
        scanf("%lf", &x[i].real);
        x[i].imag = 0.0;
    }

    // 计算FFT
    butterfly(x, n);

    printf("FFT的结果为：\n");
    for (i = 0; i < n; i++) {
        printf("%.2f + %.2fi\n", x[i].real, x[i].imag);
    }

    // 释放内存空间
    free(x);

    return 0;
}

这是一个简单的基于蝶形算法的FFT实现，可以对输入的序列进行FFT计算，并输出计算结果。在代码中，我们使用了复数结构体来表示序列中的数值，通过蝶形操作和旋转因子计算FFT。