#include <stdio.h>
#define N 8
void kkfft(double pr[], double pi[], int n, int k, double fr[], double fi[], int l, int il)
void main()
{
double xr[N],xi[N],Yr[N],Yi[N],l=0,il=0
int i,j,n=N,k=3
for(i=0i<Ni++)
{
xr[i]=i
xi[i]=0
}
printf("------FFT------\n")
l=0
kkfft(xr,xi,n,k,Yr,Yi,l,il)
for(i=0i<Ni++)
{
printf("%-11lf + j* %-11lf\n",Yr[i],Yi[i])
}
printf("-----DFFT-------\n")
l=1
kkfft(Yr,Yi,n,k,xr,xi,l,il)
for(i=0i<Ni++)
{
printf("%-11lf + j* %-11lf\n",xr[i],xi[i])
}
getch()
}
void kkfft(double pr[], double pi[], int n, int k, double fr[], double fi[], int l, int il)
{
int it,m,is,i,j,nv,l0
double p,q,s,vr,vi,poddr,poddi
for (it=0 it<=n-1 it++)
{
m = it
is = 0
for(i=0 i<=k-1 i++)
{
j = m/2
is = 2*is+(m-2*j)
m = j
}
fr[[it][/it]it] = pr[is]
fi[[it][/it]it] = pi[is]
}
pr[0] = 1.0
pi[0] = 0.0
p = 6.283185306/(1.0*n)
pr[1] = cos(p)
pi[1] = -sin(p)
if (l!=0)
pi[1]=-pi[1]
for (i=2 i<=n-1 i++)
{
p = pr[i-1]*pr[1]
q = pi[i-1]*pi[1]
s = (pr[i-1]+pi[i-1])*(pr[1]+pi[1])
pr[i] = p-q
pi[i] = s-p-q
}
for (it=0 it<=n-2 it=it+2)
{
vr = fr[[it][/it]it]
vi = fi[[it][/it]it]
fr[[it][/it]it] = vr+fr[it+1]
fi[[it][/it]it] = vi+fi[it+1]
fr[it+1] = vr-fr[it+1]
fi[it+1] = vi-fi[it+1]
}
m = n/2
nv = 2
for (l0=k-2 l0>=0 l0--)
{
m = m/2
nv = 2*nv
for(it=0 it<=(m-1)*nv it=it+nv)
for (j=0 j<=(nv/2)-1 j++)
{
p = pr[m*j]*fr[it+j+nv/2]
q = pi[m*j]*fi[it+j+nv/2]
s = pr[m*j]+pi[m*j]
s = s*(fr[it+j+nv/2]+fi[it+j+nv/2])
poddr = p-q
poddi = s-p-q
fr[it+j+nv/2] = fr[it+j]-poddr
fi[it+j+nv/2] = fi[it+j]-poddi
fr[it+j] = fr[it+j]+poddr
fi[it+j] = fi[it+j]+poddi
}
}
/*逆傅立叶变换*/
if(l!=0)
{
for(i=0 i<=n-1 i++)
{
fr[i] = fr[i]/(1.0*n)
fi[i] = fi[i]/(1.0*n)
}
}
/*是否计算模和相角*/
if(il!=0)
{
for(i=0 i<=n-1 i++)
{
pr[i] = sqrt(fr[i]*fr[i]+fi[i]*fi[i])
if(fabs(fr[i])<0.000001*fabs(fi[i]))
{
if ((fi[i]*fr[i])>0)
pi[i] = 90.0
else
pi[i] = -90.0
}
else
pi[i] = atan(fi[i]/fr[i])*360.0/6.283185306
}
}
return
}
#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")
}
}
