c语言编写fft（测试通过，和matlab结果相同）

1、头文件

#ifndef __FFT_H__
#define __FFT_H__


#include 
#include 
#include 
#define PI 3.14159265358979

typedef struct Complex
{
   double real;
   double image;
} CPLX;

void _fft(CPLX buf[], CPLX out[], int n, int step);
int fft(CPLX buf[], int n);
#endif

2、实现文件

#include "fft.h"
#include

void _fft(CPLX buf[], CPLX out[], int n, int step)
{
   int i;
   CPLX t;
   double a, b, c, d, theta;

   if (step < n) 
   {
   	_fft(out, buf, n, step * 2);
   	_fft(out + step, buf + step, n, step * 2);

   	for (i = 0; i < n; i += 2 * step) 
   	{
   		theta = -PI * i / n;
   		a = cos(theta);
   		b = sin(theta);
   		c = out[i + step].real;
   		d = out[i + step].image;
   		t.real = a * c - b * d;
   		t.image = b * c + a * d;
   		buf[i / 2].real = out[i].real + t.real;
   		buf[i / 2].image = out[