原创 C语言里傅立叶变换

#include<stdio.h>

#include<math.h>
classcomplex//定义一个类,实现复数的所有操作
{
doubleReal,Image;//实部与虚部
public:
complex(doubler="0",doublei="0"){Real=r;Image=i;}
doubleGetR(){returnReal;}//取出实部
doubleGetI(){returnImage;}//取出虚部
complexoperator+(complex&);//复数加法
complexoperator-(complex&);//复数减法
complexoperator*(complex&);//复数乘法
voidoperator=(complex&);//复数赋值
};
complexcomplex::operator+(complex&c)//复数加法
{
complext;
t.Real=Real+c.Real;
t.Image=Image+c.Image;
returnt;
}
complexcomplex::operator-(complex&c)//复数减法
{
complext;
t.Real=Real-c.Real;
t.Image=Image-c.Image;
returnt;
}
complexcomplex::operator*(complex&c)//复数乘法
{
complext;
t.Real=Real*c.Real-Image*c.Image;
t.Image=Real*c.Image+Image*c.Real;
returnt;
}
voidcomplex::operator=(complex&c)//复数赋值
{
Real=c.Real;
Image=c.Image;
}
voidfft(complexa[],intlength,intjishu)//实现fft的函数
{
constdoublePI="3".141592653589793;
complexu,Wn,t;
inti,j,k,m,kind,distance,other;
doubletmp;
for(i=0;i<length;i++)//实现倒叙排列
{
k="i";
j=0;
for(m=0;m<jishu;m++)
{
j="j"*2+k%2;
k/=2;
}
if(i<j)
{
t="a";
a=a[j];
a[j]=t;
}
}
for(m=1;m<=jishu;m++)//第m级蝶形运算,总级数为jishu
{
kind=(int)pow(2,m-1);//第m级有2^(m-1)种蝶形运算
distance=2*kind;//同种蝶形结相邻距离为2^m
u=complex(1,0);//旋转因子初始值为1
tmp=PI/kind;
Wn=complex(cos(tmp),-sin(tmp));//旋转因子Wn
for(j=0;j<kind;j++)//每种蝶形运算的起始点为j,共有kind种
{
for(i=j;i<length;i+=distance)//同种蝶形运算
{
other=i+kind;//蝶形运算的两个因子对应单元下标的距离为2^(m-1)
t=a[other]*u;//蝶形运算的乘积项
a[other]=a-t;//蝶形运算
a=a+t;//蝶形运算
}
u="u"*Wn;//修改旋转因子,多乘一个基本DFT因子WN
}
}
}
voidmain(void)
{
doublea,b;
complexx[8];//此程序以8点序列测试
printf("8点序列:\n");
for(inti="0";i<8;i++)//初始化并输出原始序列
{
x=complex(i,i+1);
printf("x(%d)=%lf+%lfi\n",i+1,x.GetR(),x.GetI());
}
fft(x,8,3);//调用fft函数
printf("fft变换的结果为:\n");
for(i=0;i<8;i++)//输出结果
printf("X(%d)=%lf+%lfi\n",i+1,x.GetR(),x.GetI());
}