.h 文件
.cpp 实现
'''c++
DFT_1D_TASK::DFT_1D_TASK()
{
Nfft = 0
_fftIn = nullptr
_fftOut = nullptr
}
DFT_1D_TASK::DFT_1D_TASK(size_t N)
{
Nfft = N
_fftIn = fftw_alloc_complex(Nfft)
_fftOut = fftw_alloc_complex(Nfft)
_fftPlan = fftw_plan_dft_1d(static_cast(Nfft), _fftIn, _fftOut, FFTW_FORWARD, FFTW_ESTIMATE)
_ifftPlan = fftw_plan_dft_1d(static_cast(Nfft), _fftIn, _fftOut, FFTW_BACKWARD, FFTW_ESTIMATE)
}
void DFT_1D_TASK::ResetNfft(size_t N)
{
ClearBuffer()
Nfft = N
_fftIn = fftw_alloc_complex(Nfft)
_fftOut = fftw_alloc_complex(Nfft)
_fftPlan = fftw_plan_dft_1d(static_cast(Nfft), _fftIn, _fftOut, FFTW_FORWARD, FFTW_ESTIMATE)
_ifftPlan = fftw_plan_dft_1d(static_cast(Nfft), _fftIn, _fftOut, FFTW_BACKWARD, FFTW_ESTIMATE)
}
DFT_1D_TASK::~DFT_1D_TASK()
{
ClearBuffer()
}
bool DFT_1D_TASK::DFT_R2C(const vector &input, vector>&output){
if(input.size()!= this->Nfft)
return false
for(size_t i = 0i
_fftIn[i][0] = input[i]
_fftIn[i][1] = 0
}
fftw_execute(_fftPlan)
if(output.size()!=this->Nfft)
output.resize(Nfft)
for(size_t i = 0i<(Nfft)i++)
{
output[i].real( _fftOut[i][0])
output[i].imag( _fftOut[i][1])
}
return true
}
bool DFT_1D_TASK::IDFT_C2R(const vector>&input, vector &output)
{
if(input.size()!= this->Nfft)
return false
for(size_t i = 0i
_fftIn[i][0] = input[i].real()
_fftIn[i][1] = input[i].imag()
}
fftw_execute(_ifftPlan)
if(output.size()!=this->Nfft)
output.resize(Nfft)
for(size_t i = 0i<(Nfft)i++)
{
output[i] = _fftOut[i][0]/Nfft
}
return true
}
bool DFT_1D_TASK::DFT_C2C (const vector>&input, vector>&output)
{
if(input.size()!= this->Nfft)
return false
for(size_t i = 0i
_fftIn[i][0] = input[i].real()
_fftIn[i][1] = input[i].imag()
}
fftw_execute(_fftPlan)
if(output.size()!=this->Nfft)
output.resize(Nfft)
for(size_t i = 0i<(Nfft)i++)
{
output[i].real( _fftOut[i][0])
output[i].imag( _fftOut[i][1])
}
return true
}
bool DFT_1D_TASK::IDFT_C2C(const vector>&input, vector>&output){
if(input.size()!= this->Nfft)
return false
for(size_t i = 0i
_fftIn[i][0] = input[i].real()
_fftIn[i][1] = input[i].imag()
}
fftw_execute(_ifftPlan)
if(output.size()!=this->Nfft)
output.resize(Nfft)
for(size_t i = 0i<(Nfft)i++)
{
output[i].real( _fftOut[i][0]/Nfft)
output[i].imag( _fftOut[i][1]/Nfft)
}
return true
}
void DFT_1D_TASK::ClearBuffer()
{
if(_fftIn != nullptr)
fftw_free(_fftIn)
if(_fftOut != nullptr)
fftw_free(_fftOut)
fftw_destroy_plan(_fftPlan)
fftw_destroy_plan(_ifftPlan)
}
'''
#include <stdio.h>#define N 7 /*叶子数目,需要时更改此值即可*/
#define M 2*N-1 /*节点总数*/
typedef struct
{
char bits[N]/*编码存储，位串*/
int start/*编码在位串中的位置*/
}codetype
typedef struct
{
float weight
int lchild,rchild,parent
}hufmtree
void HUFFMAN(tree1)
hufmtree tree1[]
{
int i,j,p1,p2
float small1,small2,f
hufmtree *tree
tree=tree1
for(i=0i<Mi++) /*初始化*/
{
tree[i].parent=0
tree[i].lchild=0
tree[i].rchild=0
tree[i].weight=0.0
}
printf("please input a possible data weight:\n")/*输入信源数据*/
for(i=0i<Ni++) /*输入前n个节点的权值*/
{
scanf("%f",&f)
tree[i].weight=f
}
for(i=Ni<Mi++) /* 进行n-1次合并，产生n-1个新的节点*/
{
p1=0,p2=0
small1=1small2=1
for(j=0j<=i-1j++) /*从所有的节点中，选出两个权值最小的根节点*/
if(tree[j].parent==0) /*parent值为0，则显示根节点，否则便是非根节点*/
if(tree[j].weight<small1)
{
small2=small1/*改变最小权，次小权及对应的位置*/
small1=tree[j].weight
p2=p1/*p1、p2记住这两个根节点在向量tree中的下标*/
p1=j
}
else if(tree[j].weight<small2)
{
small2=tree[j].weight/*次小权及位置*/
p2=j
}
tree[p1].parent=i+1/*节点分量与下标之间差值为1*/
tree[p2].parent=i+1/*节点的标号i+1*/
tree[i].lchild=p1+1/*最小值根节点是新节点的左孩子，分量标号是其下标加1*/
tree[i].rchild=p2+1/*次小权根节点是新节点的右孩子*/
tree[i].weight=tree[p1].weight+tree[p2].weight
}
}/*HUFFMANTREE()*/
void HUFFMANCODE(code1,tree1) /*根据哈夫曼树求出哈夫曼编码*/
codetype code1[]/*求出的哈夫曼编码所在*/
hufmtree tree1[]/*已知的哈夫曼树*/
{
int i,j,c,p
codetype cd/*缓冲变量*/
codetype *code
hufmtree *tree
code=code1
tree=tree1
for(i=0i<Ni++)
{
cd.start=N
c=i+1/*从叶节点出发向上回溯*/
p=tree[i].parent/*tree[p-1]是tree[i]的双亲*/
while(p!=0)
{
cd.start--
if(tree[p-1].lchild==c)
cd.bits[cd.start]='0'/*tree[i]是左子树。生成代码'0'*/
else
cd.bits[cd.start]='1'/*否则tree[i]是右子树。生成代码'1'*/
c=p
p=tree[p-1].parent
}
code[i]=cd/*第i+1个字符的编码存入code[i]*/
}
} /*HUFFMANCODE*/
#include "stdio.h"
main()
{
int k1,k2
hufmtree tree_fina[M]
hufmtree *p11=tree_fina
codetype code_fina[N]
codetype *p21=code_fina
HUFFMAN(p11)/*建立huffman树*/
HUFFMANCODE(p21,p11)/*haffman码*/
for(k1=0k1<Nk1++) /*输出编码*/
{
printf("number %d haffmancode: ",k1+1)
for(k2=code_fina[k1].startk2<Nk2++)
printf(" %c",code_fina[k1].bits[k2])
printf("\n")
}
}
