欧美bbbwbbbw肥妇,免费乱码人妻系列日韩,一级黄片

C語言數(shù)據(jù)結構算法之實現(xiàn)快速傅立葉變換

 更新時間:2017年06月25日 11:10:10   投稿:lqh  
這篇文章主要介紹了C語言數(shù)據(jù)結構算法之實現(xiàn)快速傅立葉變換的相關資料,需要的朋友可以參考下

C語言數(shù)據(jù)結構算法之實現(xiàn)快速傅立葉變換

本實例將實現(xiàn)二維快速傅立葉變換,同時也將借此實例學習用c語言實現(xiàn)矩陣的基本操作、復數(shù)的基本掾作,復習所學過的動態(tài)內存分配、文件操作、結構指針的函數(shù)調用等內容。 

很久以來,傅立葉變換一直是許多領域,如線性系統(tǒng)、光學、概率論、量子物理、天線、數(shù)字圖像處理和信號分析等的一個基本分析工具,但是即便使用計算速度驚人的計算機計算離散傅立葉變換所花費的時間也常常是難以接受的,因此導致了快速傅立葉變換(FFT)的產生。 

本實例將對一個二維數(shù)組進行正、反快速傅立葉變換。正傅立葉變換時dfft()函數(shù)先調用fft()按行對數(shù)組進行變換,再對結果調用fft()按列進行變換,此時完成了快速傅立葉變換,再調用rdfft()函數(shù)進行傅立葉逆變換。如果程序設計正確的話,變換的結果應與原數(shù)組相同。

實例代碼:

#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原始數(shù)據(jù):\n");
  showresult();
  getchar ();
  dfft ();
  printf("\n快速復利葉變換后的結果:\n");
  showresult ();
  getchar ();
  rdfft ();
  printf("\n快速復利葉逆變換后的結果:\n");
  showresult ();
  getchar ();
  free (Hfield);
}
 
void initiate ()
{//程序初始化操作,包括分配內存、讀入要處理的數(shù)據(jù)、進行顯示等
  FILE * df;
   
  df = fopen ("data.txt" , "r");
  fscanf (df , "%5d" , &n);
  fscanf (df , "%5d" , &m);
  if ((ln = loop (n)) == -1)
  {
    printf (" 列數(shù)不是2的整數(shù)次冪 ");
    exit (1);
  }
  if ((lm = loop (m)) == -1)
  {
    printf (" 行數(shù)不是2的整數(shù)次冪 ");
    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行\(zhòng)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);/////////講解傳遞結構指針和結構本身的區(qū)別
        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)
{//檢驗輸入數(shù)據(jù)是否為2的整數(shù)次冪,如果是返回用2進制表示時的位數(shù)
  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 ()
{//求復數(shù)矩陣的共軛矩陣
  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)
{//按寫矩陣方式將復數(shù)結構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)
{//定義復數(shù)加法
  z->re = x->re + y->re;
  z->im = x->im + y->im; 
}
 
void sub (struct COMPLEX * x , struct COMPLEX * y , struct COMPLEX * z)
{//定義復數(shù)減法
  z->re = x->re - y->re;
  z->im = x->im - y->im;
}
 
void mul (struct COMPLEX * x , struct COMPLEX * y , struct COMPLEX * z)
{//定義復數(shù)乘法
  z->re = (x->re) * (y->re) - (x->im) * (y->im);
  z->im = (x->im) * (y->re) + (x->re) * (y->im);
}



感謝閱讀,希望能幫助到大家,謝謝大家對本站的支持!

相關文章

  • C語言MFC基礎之計算器詳解

    C語言MFC基礎之計算器詳解

    這篇文章主要為大家介紹了MFC實現(xiàn)簡單的計算器,文中介紹的非常詳細,具有一定的參考價值,感興趣的小伙伴們可以參考一下,希望能夠給你帶來幫助
    2021-08-08
  • 用C++實現(xiàn)SLR語法分析程序

    用C++實現(xiàn)SLR語法分析程序

    大家好,本篇文章主要講的是用C++實現(xiàn)SLR語法分析程序,感興趣的同學趕緊來看一看吧,對你有幫助的話記得收藏一下
    2022-02-02
  • C++指針和數(shù)組:字符和字符串、字符數(shù)組的關聯(lián)和區(qū)別

    C++指針和數(shù)組:字符和字符串、字符數(shù)組的關聯(lián)和區(qū)別

    字符串是一種重要的數(shù)據(jù)類型,但是c語言并沒有顯示的字符串數(shù)據(jù)類型,因為字符串以字符串常量的形式出現(xiàn)或者存儲于字符數(shù)組中。在C++標準模板庫(STL)中提供了string類,實現(xiàn)了對字符串的封裝。
    2022-12-12
  • C語言也有封裝,繼承和多態(tài)你知道嗎

    C語言也有封裝,繼承和多態(tài)你知道嗎

    這篇文章主要為大家詳細介紹了C語言封裝,繼承,多態(tài),文中示例代碼介紹的非常詳細,具有一定的參考價值,感興趣的小伙伴們可以參考一下,希望能夠給你帶來幫助
    2022-03-03
  • C++多態(tài)的實現(xiàn)機制深入理解

    C++多態(tài)的實現(xiàn)機制深入理解

    這篇文章主要介紹了C++多態(tài)的實現(xiàn)機制理解的相關資料,非常不錯,具有參考借鑒價值,需要的朋友可以參考下
    2016-07-07
  • C++?Date類的具體使用(構建,重載等)

    C++?Date類的具體使用(構建,重載等)

    本文主要介紹了C++?Date類的具體使用(構建,重載等),文中通過示例代碼介紹的非常詳細,對大家的學習或者工作具有一定的參考學習價值,需要的朋友們下面隨著小編來一起學習學習吧
    2022-07-07
  • C++ LARGE_INTEGER解析與使用案例詳解

    C++ LARGE_INTEGER解析與使用案例詳解

    這篇文章主要介紹了C++ LARGE_INTEGER解析與使用案例詳解,本篇文章通過簡要的案例,講解了該項技術的了解與使用,以下就是詳細內容,需要的朋友可以參考下
    2021-08-08
  • Qt利用tablewidget模擬手指實現(xiàn)滑動

    Qt利用tablewidget模擬手指實現(xiàn)滑動

    這篇文章主要為大家詳細介紹了Qt如何利用tablewidget模擬手指實現(xiàn)滑動效果,文中的示例代碼講解詳細,對我們學習Qt有一定的幫助,需要的可以參考一下
    2023-01-01
  • Qt實現(xiàn)編輯數(shù)據(jù)庫數(shù)據(jù)的方法詳解

    Qt實現(xiàn)編輯數(shù)據(jù)庫數(shù)據(jù)的方法詳解

    這篇文章主要為大家詳細介紹了Qt是如何實現(xiàn)編輯數(shù)據(jù)庫數(shù)據(jù)的,文中的示例代碼簡潔易懂,對我們深入了解QT有一定的幫助,感興趣的小伙伴可以了解一下
    2023-02-02
  • C++生成dll和調用dll的方法實例

    C++生成dll和調用dll的方法實例

    C++生成dll和調用dll的方法實例,需要的朋友可以參考一下
    2013-03-03

最新評論