快速傅里叶变换C代码实现

以下是快速傅里叶变换的C代码实现：

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

#define PI 3.14159265358979323846

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

// 计算复数加法
complex add(complex a, complex b) {
    complex c;
    c.real = a.real + b.real;
    c.imag = a.imag + b.imag;
    return c;
}

// 计算复数减法
complex sub(complex a, complex b) {
    complex c;
    c.real = a.real - b.real;
    c.imag = a.imag - b.imag;
    return c;
}

// 计算复数乘法
complex mul(complex a, complex b) {
    complex c;
    c.real = a.real * b.real - a.imag * b.imag;
    c.imag = a.real * b.imag + a.imag * b.real;
    return c;
}

// 快速傅里叶变换
void fft(complex a[], int n, int flag) {
    if (n == 1) {
        return;
    }

    // 求偶数项和奇数项
    complex a0[n / 2], a1[n / 2];
    for (int i = 0; i < n / 2; i++) {
        a0[i] = a[i * 2];
        a1[i] = a[i * 2 + 1];
    }

    // 递归计算偶数项和奇数项的FFT
    fft(a0, n / 2, flag);
    fft(a1, n / 2, flag);

    // 计算旋转因子
    complex w = {1, 0};
    complex wn = {cos(2 * PI / n), flag * sin(2 * PI / n)};

    // 计算DFT
    for (int i = 0; i < n / 2; i++) {
        complex t = mul(w, a1[i]);
        a[i] = add(a0[i], t);
        a[i + n / 2] = sub(a0[i], t);
        w = mul(w, wn);
    }
}

int main() {
    // 输入序列长度和序列元素
    int n;
    printf("Enter the length of sequence: ");
    scanf("%d", &n);

    complex a[n];
    printf("Enter the sequence: ");
    for (int i = 0; i < n; i++) {
        scanf("%lf", &a[i].real);
        a[i].imag = 0;
    }

    // 计算FFT
    fft(a, n, 1);

    // 输出结果
    printf("FFT result: ");
    for (int i = 0; i < n; i++) {
        printf("(%g, %g) ", a[i].real, a[i].imag);
    }

    return 0;
}

该代码实现了快速傅里叶变换，并可以计算任意长度的序列的FFT。其中，add、sub、mul函数分别用于计算复数的加法、减法和乘法，而fft函数实现了递归计算FFT的过程。在fft函数中，通过计算旋转因子和DFT，可以实现对输入序列的FFT计算。最后，输出结果即为FFT的计算结果。