C语言之霍夫曼编码学习(二)

? ? ? ? getchar();

? ? ? ? tree[i].ch=c;

? ? ? ? tree[i].weight=f;

? ? }

? ? //进行n-1次合并，产生n-1个新结点

? ? for(i=n;i

? ? {

? ? ? ? p1=0;p2=0;

? ? ? ? //maxval是float类型的最大值

? ? ? ? small1=maxval;small2=maxval;

? ? ? ? //选出两个权值最小的根结点

? ? ? ? for(j=0;j

? ? ? ? {

? ? ? ? ? ? ? if(tree[j].parent==0)

? ? ? ? ? ? ? if(tree[j].weight

? ? ? ? ? ? ? {

? ? ? ? ? ? ? ? ? ? small2=small1; //改变最小权、次小权及对应的位置

? ? ? ? ? ? ? ? ? ? small1=tree[j].weight;

? ? ? ? ? ? ? ? ? ? p2=p1;

? ? ? ? ? ? ? ? ? ? p1=j;

? ? ? ? ? ? ? }

? ? ? ? ? ? ? else if(tree[j].weight

? ? ? ? ? ? ? ? {

? ? ? ? ? ? ? ? small2=tree[j].weight; //改变次小权及位置

? ? ? ? ? ? ? ? p2=j;

? ? ? ? ? ? ? ? }

? ? ? ? ? ? ? tree[p1].parent=i;

? ? ? ? ? ? ? tree[p2].parent=i;

? ? ? ? ? ? ? tree[i].lchild=p1; //最小权根结点是新结点的左孩子

? ? ? ? ? ? ? tree[i].rchild=p2; //次小权根结点是新结点的右孩子

? ? ? ? ? ? ? tree[i].weight=tree[p1].weight+tree[p2].weight;

? ? ? ? }

? }

}

?

?

//根据哈夫曼树求出哈夫曼编码，code[]为求出的哈夫曼编码，tree[]为已知的哈夫曼???

void huffmancode(codetype code[],frequencies tree[])

{

? ? int i,c,p;

? ? codetype cd; //缓冲变量

? ? for(i=0;i

? ? {

? ? ? ? ? cd.start=n;

? ? ? ? ? cd.ch=tree[i].ch;

? ? ? ? ? c=i; //从叶结点出发向上回溯

? ? ? ? ? p=tree[i].parent; //tree[p]是tree[i]的双亲

? ? ? ? ? while(p!=0)

? ? ? ? ? {

? ? ? ? ? ? ? cd.start--;

? ? ? ? ? ? ? if(tree[p].lchild==c)

? ? ? ? ? ? ? ? ? ? cd.bits[cd.start]=\'0\'; //tree[i]是左子树，生成代码\'0\'

? ? ? ? ? ? ? else

? ? ? ? ? ? ? ? ? ? cd.bits[cd.start]=\'1\'; //tree[i]是右子树，生成代码\'1\'

? ? ? ? ? ? ? c=p;

? ? ? ? ? ? ? p=tree[p].parent;

? ? ? ? ? }

? ? ? ? ? code[i]=cd; //第i+1个字符的编码存入code[i]

? ? }

}

?

?

?

?

//根据哈夫曼树解码

void decode(hufmtree tree[])

{

? ? int i,j=0;

? ? char b[maxsize];

? ? char endflag=\'2\'; //电文结束标志取2

? ? i=m-1; //从根结点开始往下搜索

? ? printf(\"输入发送的编码(以\'2\'为结束标志)：\");

? ? gets(b);

? ? printf(\"编码后的字符为\");

? ? while(b[j]!=\'2\')

? ? {

? ? ? ? ? if(b[j]==\'0\')

? ? ? ? ? i=tree[i].lchild; //走向左子节点

? ? ? ? ? else

? ? ? ? ? i=tree[i].rchild; //走向右子节点

? ? ? ? ? if(tree[i].lchild==-1) //tree[i]是叶结点

? ? ? ? ? {

? ? ? ? ? ? printf(\"%c\",tree[i].ch);

? ? ? ? ? ? i=m-1; //回到根结点

? ? ? ? ? }

? ? ? ? ? j++;

? ? }

? ? printf(\"\\n\");

? ? if(tree[i].lchild!=-1&&b[j]!=\'2\') //文本读完，但尚未到叶子结点

? ? printf(\"\\nERROR\\n\"); //输入文本有错

}

?

void main()

{

? ? printf(\"---------------—— 哈夫曼编码实战 ——\\n\");

? ? printf(\"总共有%d个字符\\n\",n);

? ? frequencies tree[m];

? ? codetype code[n];

? ? int i,j;//循环变量

? ? huffMan(tree);//建立哈夫曼树

? ? huffmancode(code,tree);//根据哈夫曼树求出哈夫曼编码

? ? printf(\"【输出每个字符的哈夫曼编码】\\n\");

? ? for(i=0;i

? ? {

? ? ? ? ? printf(\"%c: \",code[i].ch);

? ? ? ? ? for(j=code[i].start;j

? ? ? ? ? printf(\"%c \",code[i].bits[j]);

? ? ? ? ? printf(\"\\n\");

? ? }

? ? printf(\"【读入内容，并进行编码】\\n\");

? ? // 开始编码

? ? decode(tree);

}

将C语言梳理一下，分布在以下10个章节中：