x--雙精度實(shí)型一維數(shù)組，長(zhǎng)度為n，開(kāi)始時(shí)存放要變換的數(shù)據(jù)的實(shí)部，最后存放變換結(jié)果的實(shí)部；
y--雙精度實(shí)型一維數(shù)組，長(zhǎng)度為n，開(kāi)始時(shí)存放要變換的數(shù)據(jù)的虛部，最后存放變換結(jié)果的虛部；
n--整型變量。數(shù)據(jù)長(zhǎng)度，必須是2的整數(shù)次冪；
sign--整型變量。sign=1時(shí)，離散府立葉正變換DFT；sign=-1時(shí)，是IDFT；


#include"math.h"
void fft(x,y,n,sign)
{
int n,sign;
double x[],y[];
{
int i,j,k,l,m,n1,n2;
double c,c1,e,s,s1,t,tr,ti;
for(j=1,i=1;i<16;i++)
{
m=i;
j=2*j;
if(j==n)break;
}
n1=n-1;
for(j=0,i=0;i<n1;i++)
{
if(i<j)
{
tr=x[j];
ti=y[j];
x[j]=x[i];
y[j]=y[i];
x[i]=tr;
y[i]=ti;
}
k=n/2;
while(k<(j+1))
{
j=j-k;
k=k/2;
}
j=j+k;
}
n1=1;
for(l=1,l<=m;l++)
{
n1=2*n1;
n2=n1/2;
e=3.141592654/n2;
c=1.0;
s=0.0;
c1=cos(e);
s1=-sign*sin(e);
for(j=0;j<n2;j++)
{
for(i=j;j<n;j+=n1)
{
k=i+n2;
tr=c*x[k]-s*y[k];
ti=c*y[k]+s*x[k];
x[k]=x[i]-tr;
y[k]=y[i]-ti;
x[i]=x[i]+tr;
y[i]=y[i]+ti;
}
t=c;
c=c*c1-s*s1;
s=t*s1+s*c1;
}
}
if(sign==-1)
{
for(i=0;i<n;i++)
{
x[i]/=n;
y[i]/=n;
}
}
}