C语言数据结构算法之实现快速傅立叶变换
更新时间:2020年4月25日 17:30 点击:1692
C语言数据结构算法之实现快速傅立叶变换
本实例将实现二维快速傅立叶变换,同时也将借此实例学习用c语言实现矩阵的基本操作、复数的基本掾作,复习所学过的动态内存分配、文件操作、结构指针的函数调用等内容。
很久以来,傅立叶变换一直是许多领域,如线性系统、光学、概率论、量子物理、天线、数字图像处理和信号分析等的一个基本分析工具,但是即便使用计算速度惊人的计算机计算离散傅立叶变换所花费的时间也常常是难以接受的,因此导致了快速傅立叶变换(FFT)的产生。
本实例将对一个二维数组进行正、反快速傅立叶变换。正傅立叶变换时dfft()函数先调用fft()按行对数组进行变换,再对结果调用fft()按列进行变换,此时完成了快速傅立叶变换,再调用rdfft()函数进行傅立叶逆变换。如果程序设计正确的话,变换的结果应与原数组相同。
实例代码:
#include <stdio.h> #include <stdlib.h> #include <math.h> #define PI 3.14159265358979323846 struct COMPLEX { float re; float im; } cplx , * Hfield , * S , * R , * w; int n , m; int ln , lm; void initiate (); void dfft (); void rdfft (); void showresult (); void fft (int l , int k); int reverse (int t , int k); void W (int l); int loop (int l); void conjugate (); void add (struct COMPLEX * x , struct COMPLEX * y , struct COMPLEX * z); void sub (struct COMPLEX * x , struct COMPLEX * y , struct COMPLEX * z); void mul (struct COMPLEX * x , struct COMPLEX * y , struct COMPLEX * z); struct COMPLEX * Hread(int i , int j); void Hwrite (int i , int j , struct COMPLEX x); void main () { initiate (); printf("\n原始数据:\n"); showresult(); getchar (); dfft (); printf("\n快速复利叶变换后的结果:\n"); showresult (); getchar (); rdfft (); printf("\n快速复利叶逆变换后的结果:\n"); showresult (); getchar (); free (Hfield); } void initiate () {//程序初始化操作,包括分配内存、读入要处理的数据、进行显示等 FILE * df; df = fopen ("data.txt" , "r"); fscanf (df , "%5d" , &n); fscanf (df , "%5d" , &m); if ((ln = loop (n)) == -1) { printf (" 列数不是2的整数次幂 "); exit (1); } if ((lm = loop (m)) == -1) { printf (" 行数不是2的整数次幂 "); exit (1); } Hfield = (struct COMPLEX *) malloc (n * m * sizeof (cplx)); if (fread (Hfield , sizeof (cplx) , m * n , df) != (unsigned) (m * n)) { if (feof (df)) printf (" Premature end of file "); else printf (" File read error "); } fclose (df); } void dfft () {//进行二维快速复利叶变换 int i , j; int l , k; l = n; k = ln; w = (struct COMPLEX *) calloc (l , sizeof (cplx)); R = (struct COMPLEX *) calloc (l , sizeof (cplx)); S = (struct COMPLEX *) calloc (l , sizeof(cplx)); W (l); for ( i = 0 ; i < m ; i++ ) {//按行进行快速复利叶变换 for (j = 0 ; j < n ; j++) { S[j].re = Hread (i , j)->re; S[j].im = Hread (i , j)->im; } fft(l , k); for (j = 0 ; j < n ; j++) Hwrite (i , j , R[j]); } free (R); free (S); free (w); l = m; k = lm; w = (struct COMPLEX *) calloc (l , sizeof (cplx)); R = (struct COMPLEX *) calloc (l , sizeof (cplx)); S = (struct COMPLEX *) calloc (l , sizeof (cplx)); W (l); for (i = 0 ; i < n ; i++) {//按列进行快速复利叶变换 for(j = 0 ; j < m ; j++) { S[j].re = Hread(j , i)->re; S[j].im = Hread(j , i)->im; } fft(l , k); for (j = 0 ; j < m ; j++) Hwrite (j , i , R[j]); } free (R); free (S); free (w); } void rdfft () { conjugate (); dfft (); conjugate (); } void showresult () { int i , j; for (i = 0 ; i < m ; i++) { printf ( " \n第%d行\n " , i); for (j = 0 ; j < n ; j++) { if (j % 4 == 0) printf (" \n "); printf(" (%5.2f,%5.2fi) " , Hread (i , j)->re , Hread (i , j)->im); } } } void fft (int l , int k) { int i , j , s , nv , t; float c; struct COMPLEX mp , r; nv = l; c = (float) l; c = pow (c , 0.5); for (i = 0 ; i < k ; i++) { for (t = 0 ; t < l ; t += nv) { for (j = 0 ; j < nv / 2 ; j++) { s = (t + j) >> (k - i -1); s = reverse(s , k); r.re = S[t + j].re; r.im = S[t + j].im; mul (&w[s] , &S[t + j + nv / 2] , &mp);/////////讲解传递结构指针和结构本身的区别 add (&r , &mp , &S[t + j]); sub (&r , &mp , &S[t + j + nv / 2]); } } nv = nv >> 1; } for (i = 0 ; i < l ; i++) { j = reverse(i , k); R[j].re = S[i].re / c; R[j].im = S[i].im / c; } } int reverse (int t , int k) { int i , x , y; y = 0; for (i = 0 ; i < k ; i++) { x = t & 1; t = t >> 1; y = (y << 1) + x; } return y; } void W (int l) { int i; float c , a; c = (float) l; c = 2 * PI / c; for (i = 0 ; i < l ; i++) { a = (float) i; w[i].re = (float) cos(a * c); w[i].im = -(float) sin(a * c); } } int loop (int l) {//检验输入数据是否为2的整数次幂,如果是返回用2进制表示时的位数 int i , m; if (l != 0) { for (i = 1 ; i < 32 ; i++) { m = l >> i; if (m == 0) break; } if (l == (1 << (i - 1))) return i - 1; } return -1; } void conjugate () {//求复数矩阵的共轭矩阵 int i , j; for (i = 0 ; i < m ; i++) { for (j = 0 ; j < n ; j++) { Hread (i , j)->im *= -1; } } } struct COMPLEX * Hread (int i , int j) {//按读矩阵方式返回Hfield中指定位置的指针 return (Hfield + i * n + j); } void Hwrite (int i , int j , struct COMPLEX x) {//按写矩阵方式将复数结构x写到指定的Hfield位置上 (Hfield + i * n + j)->re = x.re; (Hfield + i * n + j)->im = x.im; } void add (struct COMPLEX * x , struct COMPLEX * y , struct COMPLEX * z) {//定义复数加法 z->re = x->re + y->re; z->im = x->im + y->im; } void sub (struct COMPLEX * x , struct COMPLEX * y , struct COMPLEX * z) {//定义复数减法 z->re = x->re - y->re; z->im = x->im - y->im; } void mul (struct COMPLEX * x , struct COMPLEX * y , struct COMPLEX * z) {//定义复数乘法 z->re = (x->re) * (y->re) - (x->im) * (y->im); z->im = (x->im) * (y->re) + (x->re) * (y->im); }
感谢阅读,希望能帮助到大家,谢谢大家对本站的支持!
上一篇: C++中的构造函数与析造函数详解
下一篇: C语言线性表顺序存储结构实例详解
相关文章
- 这篇文章主要为大家详细介绍了C语言实现放烟花的程序,有音乐播放,文中示例代码介绍的非常详细,具有一定的参考价值,感兴趣的小伙伴们可以参考一下...2021-02-23
- 本篇文章主要介绍C语言中char的知识,并附有代码实例,以便大家在学习的时候更好的理解,有需要的可以看一下...2020-04-25
- 这篇文章主要介绍了详解如何将c语言文件打包成exe可执行程序,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习学习吧...2021-02-25
- 这篇文章主要介绍了C#数据结构之队列(Quene),结合实例形式较为详细的讲述了队列的功能、原理与C#实现队列的相关技巧,需要的朋友可以参考下...2020-06-25
- free函数是释放之前某一次malloc函数申请的空间,而且只是释放空间,并不改变指针的值。下面我们就来详细探讨下...2020-04-25
- 这篇文章主要介绍了C语言中计算正弦的相关函数总结,包括正弦和双曲线正弦以及反正弦的函数,需要的朋友可以参考下...2020-04-25
详解C语言中的rename()函数和remove()函数的使用方法
这篇文章主要介绍了详解C语言中的rename()函数和remove()函数的使用方法,是C语言入门学习中的基础知识,需要的朋友可以参考下...2020-04-25- 这篇文章主要介绍了C语言中求和、计算平均值、方差和标准差的实例,具有很好的参考价值,希望对大家有所帮助。一起跟随小编过来看看吧...2020-12-10
- 本篇文章主要讲解C语言 基本语法,这里提供简单的示例和代码来详细讲解C语言的基本语法,开始学习C语言的朋友可以看一下,希望能够给你带来帮助...2021-09-18
- 这篇文章主要介绍了C语言中send()函数和sendto()函数的使用方法,是C语言入门学习中的基础知识,需要的朋友可以参考下...2020-04-25
- 今天小编就为大家分享一篇C语言实现从文件读入一个3*3数组,并计算每行的平均值,具有很好的参考价值,希望对大家有所帮助。一起跟随小编过来看看吧...2020-04-25
- 这篇文章主要介绍了C语言中memcpy 函数的用法详解的相关资料,需要的朋友可以参考下...2020-04-25
- 这篇文章主要介绍了使用C语言操作文件的基本函数整理,包括创建和打开以及关闭文件的操作方法,需要的朋友可以参考下...2020-04-25
- 这篇文章主要介绍了C#常用数据结构和算法,这里我们总结了一些知识点,可以帮助大家理解这些概念。...2020-06-25
- 这篇文章主要介绍了C语言中查找字符在字符串中出现的位置的方法,分别是strchr()函数和strrchr()函数的使用,需要的朋友可以参考下...2020-04-25
- 很多同学在学习c语言的时候是不是会碰到a++和++a都有甚么作用啊。今天我们就来探讨下...2020-04-25
- 这篇文章主要对C语言中const关键字的用法进行了详细的分析介绍,需要的朋友可以参考下...2020-04-25
- 下面小编就为大家带来一篇C语言实现时间戳转日期的算法(推荐)。小编觉得挺不错的,现在就分享给大家,也给大家做个参考。一起跟随小编过来看看吧...2020-04-25
- 这篇文章主要介绍了C语言之整数划分问题(递归法)实例代码的相关资料,需要的朋友可以参考下...2020-04-25
- 本文给大家简单介绍下c实现linux下的数据库备份的方法和具体的源码,十分的实用,有需要的小伙伴可以参考下。...2020-04-25