/*這個(gè)程序最多512個(gè)點(diǎn)，如果需要處理更多的數(shù)據(jù)，可以改動(dòng)R的值*/
#include???
#include???
#define???R???512
#define???PI???3.141592653
typedef?struct//定義一個(gè)復(fù)數(shù)結(jié)構(gòu)
?????{
??????double???real;//由于三角運(yùn)算結(jié)果是double型，所以不能用float定義
??????double???img;
??????}complex;
complex???x[R]?W[R];//FFT輸入和輸出的存儲(chǔ)空間
void???fft（）;?//快速傅里葉變換算法實(shí)現(xiàn)
void???change（）;

int???N=0;//定義并初始化序列的長(zhǎng)度，必須是2的自然數(shù)次冪，不能超過(guò)N
int???L=0;
void???add（complex???acomplex???bcomplex???*c）???//復(fù)數(shù)加法
???????????{???
?????????????c->real=a.real+b.real;???
?????????????c->img=a.img+b.img;???
????????????}???
????
?void???mul（complex???acomplex???bcomplex???*c）???//復(fù)數(shù)乘法
?????????????{???
???????????????c->real=a.real*b.real???-???a.img*b.img;???
???????????????c->img=a.real*b.img???+???a.img*b.real;???
??????????????}???
?void???sub（complex???acomplex???bcomplex???*c）???//復(fù)數(shù)減法
??????????????{???
????????????????c->real=a.real-b.real;???
????????????????c->img=a.img-b.img;???
???????????????}???
int???main（）
????????{
?????????int???i;
?????????printf（“序列長(zhǎng)度為2的L次方，請(qǐng)輸入L的值（1~9）:\n“）;//輸入指數(shù)值（1~9）確定序列的長(zhǎng)度
?????????scanf（“%d“&L）;
		?N=（int）?pow（2L）;
			?if（L<1）
				?printf（“L值輸入錯(cuò)誤“）;
			?else?if（N>R）
				?printf（“L值過(guò)大“）;
			?else												//只有在L值合法情況才執(zhí)行主程序
				{
				printf（“請(qǐng)依次輸入X（n）的復(fù)數(shù)序列值（實(shí)部?虛部）:\n“）;????????????????????????
				for（i=0;i					{
						scanf（“%lf?%lf“&x[i].real&x[i].img）;
??????????????
					}
				fft（）;??
				printf（“結(jié)果如下\n“）;???
????????????for（i=0;i???????????????{???
?????????????????printf（“%.4f“x[i].real）;???
?????????????????if（x[i].img>=0.0001）???
?????????????????printf（“+%.4fj\n“x[i].img）;???
?????????????????else???if（fabs（x[i].img）<0.0001）???
?????????????????printf（“\n“）;???
?????????????????else?????
?????????????????printf（“%.4fj\n“x[i].img）;???
???????????????}???
		????????return???0;
				}?
		}
????????????void???fft（）???
????????????????{???
??????????????????int???ai=0j=0k=0l=0;???
??????????????????complex???HILOOU;???//定義奇偶兩部分和結(jié)果的復(fù)數(shù)結(jié)構(gòu)
??????????????????change（）;???//倒序列?
					for（a=0;a					{???
						W[a].real=cos（2*PI/N*a）;???//指數(shù)從0到N-1的所有旋轉(zhuǎn)因子
						W[a].img=-1*sin（2*PI/N*a）;???
					}???
				??for（i=0;i???????????????????????{???????
?????????????????????????l=1<?????????????????????????for（j=0;j???????????????????????????{???????????????????????????
?????????????????????????????for（k=0;k????????????????????????????????{?????????????????
??????????????????????????????????mul（x[j+k+l]W[N*k/2/l]&OU）;??//一次蝶形運(yùn)算的過(guò)程?
??????????????????????????????????add（x[j+k]OU&HI）;???
??????????????????????????????????sub（x[j+k]OU&LO）;?
??????????????????????????????????x[j+k]=HI;???x[j+k+l]=LO;???
???????????????????????????????????}???
??????????????????????????????}???
?????????????????????????}???
????????????????????}?

void???change（）???//序列的倒序
????

?屬性????????????大小?????日期????時(shí)間???名稱
-----------?---------??----------?-----??----
?????目錄???????????0??2013-06-22?21:56??1\
?????文件????????4280??2013-06-22?21:56??1\1.dsp
?????文件?????????510??2013-06-18?21:30??1\1.dsw
?????文件???????50176??2013-06-22?21:56??1\1.ncb
?????文件???????48640??2013-06-22?21:56??1\1.opt
?????文件????????1564??2013-06-22?20:45??1\1.plg
?????目錄???????????0??2013-06-22?20:45??1\Debug\
?????文件???????50176??2013-06-22?20:45??1\Debug\1.bsc
?????文件??????225371??2013-06-22?20:45??1\Debug\1.exe
?????文件??????223736??2013-06-22?20:45??1\Debug\1.ilk
?????文件??????181740??2013-06-22?19:03??1\Debug\1.pch
?????文件??????484352??2013-06-22?20:45??1\Debug\1.pdb
?????文件???????10171??2013-06-22?20:45??1\Debug\Text1.obj
?????文件???????????0??2013-06-22?20:45??1\Debug\Text1.sbr
?????文件???????33792??2013-06-22?20:47??1\Debug\vc60.idb
?????文件???????53248??2013-06-22?20:45??1\Debug\vc60.pdb
?????文件????????3868??2013-06-22?20:45??1\Text1.c