基2时间快速傅里叶变换，用c语言实现。

#include 
#include
#include
#include
#define PI 3.14159265

complex* fft(int* array,int N,int L,int s);
int reversal(int num,int m)     //倒序数组，如1倒置后为4，x[1]对应的是采样数组中下标为4的元素
{
   int answer=0x00,i,temp=1;
   for(i=1;i<=m;i++)
   {
      temp=num%2;
      temp=temp<<(m-i);
      num=num/2;
      answer|=temp;
   }
   return answer;
}
complex wnk(int n,int k)//求复数e-j2pik/N
{
    return cos(2*PI*k/n)-sin(2*PI*k/n)*1i;
}
int main(void)
{
    int i=0,n=16,l=log2(n),s=0;
    l=((pow(2,l)+0.0001)=0)
     printf("第%2d个点:%f+%fin",i,creal(X[i]),cimag(X[i]));
    else
     printf("第%2d个点:%f%fin",i,creal(X[i]),cimag(X[i]));
    }
    return 0;
}
complex* fft(int* array,int n,int l,int s)
{
    int i=0,m=log2(n);
    if(l==1)//最后一级
    {
        complex *array3=malloc(3*sizeof(complex));
        int x1=array[reversal(s,m)],x2=array[reversal(s+1,m)];
        array3[0]=x1+x2*wnk(n,0);
        array3[1]=x1-x2*wnk(n,0);
        return array3;
    }
    else
    {
     int interval=(int)(pow(2,l-1)+0.0001);
       complex *array1 =fft(array,n,l-1,s);
       complex *array2 =fft(array,n,l-1,s+interval);//X[k]=X1[k]+X2[k]*Enk
       complex *array3 =malloc((n+1)*sizeof(complex));//X[k+n/2]=X1[k]-X2[k]*Enk
       for(i=0;i