实验1:快速傅里叶变换(FFT). 下面是一个简单的快速傅里叶变换(FFT)的C语言实现，可以在C-Free或其他C编译器上编译执行。这个程序使用Cooley-Tukey算法，并能够打印出输入信号和变换后的频域信号的波形

实验1：快速傅立叶变换（FFT）是一种高效的算法，用于计算离散时间信号的频域表示。它将复杂的离散傅立叶变换(DFT)分解成较小规模的DFT，显著减少了计算量。在这个C语言示例中，我们通常会使用递归或迭代的方式实现Cooley-Tukey算法，这是FFT最常用的形式。

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

// 基本的复数结构体
typedef struct {
    double real;
    double imag;
} complex;

// Cooley-Tukey FFT函数
complex* fft(complex* x, int n) {
    if (n <= 1) return x; // 基线情况，直接返回

    // 分治策略：将数组分为两半，对每个半部分递归调用FFT
    complex* even = fft(x, n / 2);
    complex* odd = fft(x + n / 2, n / 2);

    // 合并两个半部分的结果
    complex* result = malloc(n * sizeof(complex));
    for (int k = 0; k < n; k++) {
        complex re = even[k].real - odd[k].imag * sqrt(-1.0); // 实部
        complex im = even[k].imag + odd[k].real * sqrt(-1.0); // 虚部

        result[k] = {re, im};
    }
    
    return result;
}

// 打印复数数组
void print_complex_array(complex* arr, int n) {
    for (int i = 0; i < n; i++) {
        printf("%.2f + %.2fi\n", arr[i].real, arr[i].imag);
    }
}

int main() {
    int N = 8; // 输入信号长度
    complex* input = malloc(N * sizeof(complex)); // 初始化输入信号

    // ... 这里填充输入信号 ...

    complex* output = fft(input, N);
    print_complex_array(output, N);

    free(input);
    free(output);
    return 0;
}