C语言中如何实现快速傅立叶变换算法？

本文共计1381个文字，预计阅读时间需要6分钟。

C语言实现快速傅里叶变换（FFT），实例包括二维FFT，同时学习C语言实现矩阵基本操作、复数基本运算，复习动态内存分配、文件操作等。

C语言数据结构算法之实现快速傅立叶变换

本实例将实现二维快速傅立叶变换，同时也将借此实例学习用c语言实现矩阵的基本操作、复数的基本掾作，复习所学过的动态内存分配、文件操作、结构指针的函数调用等内容。

很久以来，傅立叶变换一直是许多领域，如线性系统、光学、概率论、量子物理、天线、数字图像处理和信号分析等的一个基本分析工具，但是即便使用计算速度惊人的计算机计算离散傅立叶变换所花费的时间也常常是难以接受的，因此导致了快速傅立叶变换（FFT)的产生。

本实例将对一个二维数组进行正、反快速傅立叶变换。正傅立叶变换时dfft()函数先调用fft()按行对数组进行变换，再对结果调用fft()按列进行变换，此时完成了快速傅立叶变换，再调用rdfft()函数进行傅立叶逆变换。如果程序设计正确的话，变换的结果应与原数组相同。