霍夫曼算法代码

① 哈夫曼编码的算法代码是什么

// 哈夫曼编码(算法)#include <stdio.h>
#include <stdlib.h>
#include <string.h>typedef char *HuffmanCode; //动态分配数组，存储哈夫曼编码typedef struct
{
unsigned int weight; //用来存放各个结点的权值
unsigned int parent,LChild,RChild; //指向双亲、孩子结点的指针
} HTNode, *HuffmanTree; //动态分配数组，存储哈夫曼树//选择两个parent为0，且weight最小的结点s1和s2
void Select(HuffmanTree *ht,int n,int *s1,int *s2)
{
int i,min;
for(i=1; i<=n; i++)
{
if((*ht)[i].parent==0)
{
min=i;
break;
}
}
for(i=1; i<=n; i++)
{
if((*ht)[i].parent==0)
{
if((*ht)[i].weight<(*ht)[min].weight)
min=i;
}
}
*s1=min;
for(i=1; i<=n; i++)
{
if((*ht)[i].parent==0 && i!=(*s1))
{
min=i;
break;
}
}
for(i=1; i<=n; i++)
{
if((*ht)[i].parent==0 && i!=(*s1))
{
if((*ht)[i].weight<(*ht)[min].weight)
min=i;
}
}
*s2=min;
}//构造哈夫曼树ht。w存放已知的n个权值
void CrtHuffmanTree(HuffmanTree *ht,int *w,int n)
{
int m,i,s1,s2;
m=2*n-1;
*ht=(HuffmanTree)malloc((m+1)*sizeof(HTNode));
for(i=1; i<=n; i++) //1--n号存放叶子结点，初始化
{
(*ht)[i].weight=w[i];
(*ht)[i].LChild=0;
(*ht)[i].parent=0;
(*ht)[i].RChild=0;
}
for(i=n+1; i<=m; i++)
{
(*ht)[i].weight=0;
(*ht)[i].LChild=0;
(*ht)[i].parent=0;
(*ht)[i].RChild=0;
} //非叶子结点初始化
printf("\nHuffmanTree: \n");
for(i=n+1; i<=m; i++) //创建非叶子结点，建哈夫曼树
{
//在(*ht)[1]~(*ht)[i-1]的范围内选择两个parent为0
//且weight最小的结点，其序号分别赋值给s1、s2
Select(ht,i-1,&s1,&s2);
(*ht)[s1].parent=i;
(*ht)[s2].parent=i;
(*ht)[i].LChild=s1;
(*ht)[i].RChild=s2;
(*ht)[i].weight=(*ht)[s1].weight+(*ht)[s2].weight;
printf("%d (%d, %d)\n",(*ht)[i].weight,(*ht)[s1].weight,(*ht)[s2].weight);
}
printf("\n");
} //哈夫曼树建立完毕//从叶子结点到根，逆向求每个叶子结点对应的哈夫曼编码
void CrtHuffmanCode(HuffmanTree *ht, HuffmanCode *hc, int n)
{
char *cd;
int i,start,p;
unsigned int c;
hc=(HuffmanCode *)malloc((n+1)*sizeof(char *)); //分配n个编码的头指针
cd=(char *)malloc(n*sizeof(char)); //分配求当前编码的工作空间
cd[n-1]='\0'; //从右向左逐位存放编码，首先存放编码结束符
for(i=1; i<=n; i++) //求n个叶子结点对应的哈夫曼编码
{
start=n-1; //初始化编码起始指针
for(c=i,p=(*ht)[i].parent; p!=0; c=p,p=(*ht)[p].parent) //从叶子到根结点求编码
if( (*ht)[p].LChild==c)
cd[--start]='0'; //左分支标0
else
cd[--start]='1'; //右分支标1
hc[i]=(char *)malloc((n-start)*sizeof(char)); //为第i个编码分配空间
strcpy(hc[i],&cd[start]);
}
free(cd);
for(i=1; i<=n; i++)
printf("HuffmanCode of %3d is %s\n",(*ht)[i].weight,hc[i]);
printf("\n");
}void main()
{
HuffmanTree HT;
HuffmanCode HC;
int *w,i,n,wei,m;
printf("\nn = " );
scanf("%d",&n);
w=(int *)malloc((n+1)*sizeof(int));
printf("\ninput the %d element's weight:\n",n);
for(i=1; i<=n; i++)
{
printf("%d: ",i);
fflush(stdin);
scanf("%d",&wei);
w[i]=wei;
}
CrtHuffmanTree(&HT,w,n);
CrtHuffmanCode(&HT,&HC,n);
}

② 求高手写个关于哈夫曼编码的算法

恩，楼主这个题目相当复杂啊
首先读文件，按字符读。一个一个读，统计所有出现字符的频数。
记录到一个链表里吧
第二步，建树。霍夫曼树……复杂程度可想而知。
Huffman 算法
思想： 权大的外结点靠近根， 权小的远离根。
算法： 从m个权值中找出两个最小值W1，W2构成
w
w1 w2 W=W1+W2表通过该结点的频度。
依次往上找……
估计你的100个字符的短文，出现的字符数量估计平均有20个左右，建的树的高度就12就算低的。
3 按结点到跟的距离编码，从左到右编码为0 1 0 1依次进行……
生成霍夫曼编码
把每个字幕的二进制编码记录，打出，这就是密码表
然后对原来的文件进行打印，碰到相应的字母打印出相应的密码（二进制啊，汗……）
估计只有拿到密码才能看明白那一串的01！！
如果某一电文出现的字符为D={M，S，T，A，Q， K} ， 每个字符出现的频率为W={10，29，4，8，15，7}，
则用改算法生成的密码为：
S：0 A：100 M：101 Q：111
T：1100 K：1101
100 1100 101 0 111 0 1101 0 0 密文的含义是：
A T M S Q S K S S

③ 霍夫曼编码算法在何时效率最高何时效率最低

霍夫曼(Huffman)编码是1952年为文本文件而建立，是一种统计编码。属于无损压缩编码。
霍夫曼编码的码长是变化的，对于出现频率高的信息，编码的长度较短;而对于出现频率低的信息，编码长度较长。这样，处理全部信息的总码长一定小于实际信息的符号长度。
霍夫曼计算法步骤进行：
l)将信号源的符号按照出现概率递减的顺序排列。
2)将两个最小出现概率进行合并相加，得到的结果作为新符号的出现概率。
3)重复进行步骤1和2直到概率相加的结果等于1为止。
4)在合并运算时，概率大的符号用编码0表示，概率小的符号用编码1表示。
5)记录下概率为1处到当前信号源符号之间的0，l序列，从而得到每个符号的编码。
霍夫曼计算法举例：

霍夫曼优点：
霍夫曼码的码长虽然是可变的，但却自带同步代码。例如，码串中的第1位为0，那末肯定是符号A，因为表示其他符号的代码没有一个是以0开始的，因此下一位就表示下一个符号代码的第1位。同样，如果出现“110”，那么它就代表符号D。如果事先编写出一本解释各种代码意义的“词典”，即码簿，那么就可以根据码簿一个码一个码地依次进行译码。
霍夫曼编码方法的编码效率比香农-范诺编码效率高一些
霍夫曼缺点：
① 霍夫曼码没有错误保护功能，在译码时，如果码串中没有错误，那么就能一个接一个地正确译出代码。但如果码串中有错误，哪仅是1位出现错误，不但这个码本身译错，更糟糕的是一错一大串，全乱了套，这种现象称为错误传播(error propagation)。计算机对这种错误也无能为力，说不出错在哪里，更谈不上去纠正它。
② 霍夫曼码是可变长度码，因此很难随意查找或调用压缩文件中间的内容，然后再译码，这就需要在存储代码之前加以考虑。硬件实现有难度。
③ 由于"0"与"1"的指定是任意的，故由上述过程编出的最佳码不是唯一的，但其平均码长是一样的，故不影响编码效率与数据压缩性能。
④ 压缩与还原相当费时。
⑤ 对不同信号源的编码效率不同

④ 哈夫曼编码 C源代码

#include <stdio.h>
#define MAXBIT 10 /*定义哈夫曼编码的最大长度*/
#define MAXVALUE 10000 /*定义最大权值*/
#define MAXLEAF 30 /*定义哈夫曼树中最多叶子节点个数*/
#define MAXNODE MAXLEAF*2-1 /*哈夫曼树最多结点数*/
typedef struct { /*哈夫曼编码信息的结构*/
int bit[MAXBIT];
int start;}Hcodetype;
typedef struct { /*哈夫曼树结点的结构*/
int weight;
int parent;
int lchild;
int rchild;
}Hnodetype;
void huffmantree(Hnodetype huffnode[MAXNODE],int n) /*构造哈夫曼树的函数*/
{
int i,j,m1,m2,x1,x2;
for(i=0;i<2*n-1;i++) /*存放哈夫曼树结点的数组huffnode[]初始化*/
{
huffnode[i].weight=0;
huffnode[i].parent=-1;
huffnode[i].lchild=-1;
huffnode[i].rchild=-1;
}
for(i=0;i<n;i++) /*输入入N个叶子节点的权值*/
{
printf("please input %d character's weight\n",i);
scanf("%d",&huffnode[i].weight);
}
for(i=0;i<n-1;i++) /*开始循环构造哈夫曼树*/
{
m1=m2=MAXVALUE;
x1=x2=0;
for(j=0;j<n+i;j++)
{
if(huffnode[j].weight<m1&&huffnode[j].parent==-1)
{
m2=m1;x2=x1;m1=huffnode[j].weight;x1=j;
}
else if(huffnode[j].weight<m2&&huffnode[j].parent==-1)
{
m2=huffnode[j].weight;x2=j;
}
}
huffnode[x1].parent=n+i;
huffnode[x2].parent=n+i;
huffnode[n+i].weight=huffnode[x1].weight+huffnode[x2].weight;
huffnode[n+i].lchild=x1;
huffnode[n+i].rchild=x2;
}
}
void main()
{
Hnodetype huffnode[MAXNODE];
Hcodetype huffcode[MAXLEAF],cd;
int i,j,c,p,n;
printf("please input n\n");
scanf("%d",&n); /*输入叶子节点个数*/
huffmantree(huffnode,n); /*建立哈夫曼树*/
for(i=0;i<n;i++) /*该循环求每个叶子节点对应字符的哈夫曼编码*/
{
cd.start=n-1;c=i;
p=huffnode[c].parent;
while(p!=-1)
{
if(huffnode[p].lchild==c) cd.bit[cd.start]=0;
else cd.bit[cd.start]=1;
cd.start--;c=p;
p=huffnode[c].parent;
}
for(j=cd.start+1;j<n;j++) /*保存求出的每个叶节点的哈夫曼编码和编码的起始位*/
huffcode[i].bit[j]=cd.bit[j];
huffcode[i].start=cd.start;
}
for(i=0;i<n;i++) /*输出每个叶子节点的哈夫曼编码*/
{
printf("%d character is:",i);
for(j=huffcode[i].start+1;j<n;j++)
printf("%d",huffcode[i].bit[j]);
printf("\n");
}
}

⑤ Huffman编码的算法

霍夫曼编/译码器c/c++代码#include<iostream.h>#include"stdio.h" #include"stdlib.h"#include"string.h"typedef char ElemType;typedef struct { ElemType elem; unsigned int m_weight; unsigned int parent,lchild,rchild;}HTNode,*HuffmanTree;typedef char** HuffmanCode;typedef int Status; typedef struct weight{ char elem; unsigned int m_weight;}Weight;void HuffmanCoding(HuffmanTree *,HuffmanCode *,Weight *,int);void Select(HuffmanTree,int,int *,int *); void OutputHuffmanCode(HuffmanTree,HuffmanCode,int);Status main(void){ HuffmanTree HT; HuffmanCode HC; Weight *w; char c; int i,n; int wei; printf("请输入要编码的字符种类数:" ); scanf("%d",&n); w=(Weight *)malloc(n*sizeof(Weight)); for(i=0;i<n;i++) { printf("输入元素和所占比例:"); scanf("%1s%d",&c,&wei); w[i].elem=c; w[i].m_weight=wei;} HuffmanCoding(&HT,&HC,w,n); OutputHuffmanCode(HT,HC,n); return 1;} void HuffmanCoding(HuffmanTree *HT,HuffmanCode *HC,Weight *w,int n){int i,m,s1,s2,start,c,f; </p><p> char *cd; </p><p> if(n<=1) </p><p> return;</p><p> m=2*n-1; </p><p> </p><p>(*HT)=(HuffmanTree)malloc((m+1)*sizeof(HTNode));</p><p> for(i=1;i<=n;++i)</p><p>{ (*HT)[i].elem=w[i-1].elem;</p><p> (*HT)[i].m_weight=w[i-1].m_weight; </p><p> (*HT)[i].parent=(*HT)[i].lchild=(*HT)[i].rchild=0; </p><p>} for(;i<=m;++i) { (*HT)[i].elem='0'; (*HT)[i].m_weight=(*HT)[i].parent=(*HT)[i].lchild=(*HT)[i].rchild=0;} for(i=n+1;i<=m;++i){ Select(*HT,i-1,&s1,&s2); (*HT)[s1].parent=i;(*HT)[s2].parent=i; (*HT)[i].lchild=s1;(*HT)[i].rchild=s2; (*HT)[i].m_weight=(*HT)[s1].m_weight+(*HT)[s2].m_weight;} (*HC)=(HuffmanCode)malloc(n*sizeof(char*)); cd=(char *)malloc(n*sizeof(char)); cd[n-1]='\0'; for(i=1;i<=n;++i) { start=n-1; for(c=i,f=(*HT)[i].parent;f!=0;c=f,f=(*HT)[f].parent) {if((*HT)[f].lchild==c) cd[--start]='0'; </p><p> else cd[--start]='1'; </p><p> } (*HC)[i]=(char *)malloc((n-start)*sizeof(char)); strcpy((*HC)[i],&cd[start]); } } void Select(HuffmanTree HT,int n,int *s1,int *s2){ int i; (*s1)=(*s2)=0; for(i=1;i<=n;i++) { if(HT[i].m_weight<HT[(*s2)].m_weight&&HT[i].parent==0&&(*s2)!=0) { if(HT[i].m_weight<HT[(*s1)].m_weight) { (*s2)=(*s1); (*s1)=i; } else (*s2)=i; } if(((*s1)==0||(*s2)==0)&&HT[i].parent==0) { if((*s1)==0) (*s1)=i; else if((*s2)==0) { if(HT[i].m_weight<HT[(*s1)].m_weight) { (*s2)=(*s1); (*s1)=i; } else (*s2)=i; } } } if((*s1)>(*s2)) { i=(*s1); (*s1)=(*s2); (*s2)=i; } }void OutputHuffmanCode(HuffmanTree HT,HuffmanCode HC,int n) { char SCE[100],K; printf("\nnumber--element--weight--huffman code\n"); for(int i=1;i<=n;i++) printf(" %-5d %-5c %-7d %-8s\n",i,HT[i].elem,HT[i].m_weight,HC[i]); printf("input the scentence :\n"); for(int j=0;K!='q';j++){cin>>K;SCE[j]=K;} printf("output the code :\n"); for(int k=0;k<=j-2;k++) for(int m=1;m<=n;m++) if(SCE[k]==HT[m].elem)cout<<HC[m]<<" ";}

⑥ 3. 找到最优树(霍夫曼树)问题分别用C、C++进行算法描述、流程图以及可实现的具体程序

霍夫曼树： 带权路径长度达到最小的扩充二叉树即为霍夫曼树。
在霍夫曼树中，权值大的结点离根最近。
霍夫曼算法
(1) 由给定的n个权值{w0, w1, w2, …, wn-1}，构造具有n棵扩充二叉树的森林F = {T0, T1, T2, …, Tn-1}，其中每一棵扩充二叉树Ti只有一个带有权值wi的根结点，其左、右子树均为空。
(2) 重复以下步骤, 直到F中仅剩下一棵树为止：
① 在F中选取两棵根结点的权值最小的扩充二叉树, 做为左、右子树构造一棵新的二叉树。置新的二叉树的根结点的权值为其左、右子树上根结点的权值之和。
② 在F中删去这两棵二叉树。
③ 把新的二叉树加入F。

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <conio.h>

typedef struct
{
unsigned int Weight;
unsigned int Parent;
unsigned int lChild;
unsigned int rChild;
}HTNode,*HuffmanTree;

typedef char **HuffmanCode;

int LookFor(char *str,char letter,int count);
void OutputWeight(char *Data,int Length,
char **WhatLetter,
int **Weight,int *Count);
void HuffmanCoding(HuffmanTree *HT,
HuffmanCode *HC,
int *Weight,
int Count);
void Select(HuffmanTree HT,int Count,int *s1,int *s2);
int main()
{
HuffmanTree HT;
HuffmanCode HC;
char Data[100];
char *WhatLetter;
int *Weight;
int Count;
int i;

printf("Please input the line:");
/* Example: aaaaaaaaaaaaaabcccccc*/
scanf("%s",Data);
printf("\n");

OutputWeight(Data,strlen(Data),
&WhatLetter,
&Weight,
&Count);

HuffmanCoding(&HT,&HC,Weight,Count);

printf(" Letter Weight Code\n");
for(i=0;i<Count;i++)
{
printf(" %c ",WhatLetter[i]);
printf("%d ",Weight[i]);
printf("%s\n",HC[i+1]);
}
printf("\n");
getch();
return 0;
}

void HuffmanCoding(HuffmanTree *HT,
HuffmanCode *HC,
int *Weight,
int Count)
{
int i;
int s1,s2;
int TotalLength;
HuffmanTree p;
char* cd;
unsigned int c;
unsigned int f;
int start;

if(Count<=1) return;
TotalLength=Count*2-1;
(*HT)=(HuffmanTree)malloc((TotalLength+1)*sizeof(HTNode));

p=((*HT)++);
for(i=1;i<=Count;i++)
{
(*HT)[i].Parent=0;
(*HT)[i].rChild=0;
(*HT)[i].lChild=0;
(*HT)[i].Weight=(*Weight);
Weight++;
}
for(i=Count+1;i<=TotalLength;i++)
{
(*HT)[i].Weight=0;
(*HT)[i].Parent=0;
(*HT)[i].lChild=0;
(*HT)[i].rChild=0;
}
/*///////////////////Create HuffmanTree////////////////*/
for(i=Count+1;i<=TotalLength;++i)
{
Select((*HT),i-1,&s1,&s2);
(*HT)[s1].Parent=i;
(*HT)[s2].Parent=i;
(*HT)[i].lChild=s1;
(*HT)[i].rChild=s2;
(*HT)[i].Weight=(*HT)[s1].Weight+(*HT)[s2].Weight;
}
/*///////////////////Output Huffman Code///////////////*/
(*HC)=(HuffmanCode)malloc((Count+1)*sizeof(char*));
cd=(char*)malloc(Count*sizeof(char));
cd[Count-1]='\0';
for(i=1;i<=Count;++i)
{
start=Count-1;
for(c=i,f=(*HT)[i].Parent;f!=0;c=f,f=(*HT)[f].Parent)
{
if((*HT)[f].lChild==c)
cd[--start]='0';
else
cd[--start]='1';
(*HC)[i]=(char*)malloc((Count-start)*sizeof(char));
strcpy((*HC)[i],&cd[start]);
}
}
}
void Select(HuffmanTree HT,int Count,int *s1,int *s2)
/*/(*s1) is smallest,(*s2) is smaller.*/
{
int i;
unsigned int temp1=0;
unsigned int temp2=0;
unsigned int temp3;
for(i=1;i<=Count;i++)
{
if(HT[i].Parent==0)
{
if(temp1==0)
{
temp1=HT[i].Weight;
(*s1)=i;
}
else
{
if(temp2==0)
{
temp2=HT[i].Weight;
(*s2)=i;
if(temp2<temp1)
{
temp3=temp2;
temp2=temp1;
temp1=temp3;

temp3=(*s2);
(*s2)=(*s1);
(*s1)=temp3;
}
}
else
{
if(HT[i].Weight<temp1)
{
temp2=temp1;
temp1=HT[i].Weight;

(*s2)=(*s1);
(*s1)=i;
}
if(HT[i].Weight>temp1&&HT[i].Weight<temp2)
{
temp2=HT[i].Weight;
(*s2)=i;
}
}
}
}
}
}

int LookFor(char *str,char letter,int count)
{
int i;
for(i=0;i<count;i++)
{
if(str[i]==letter) return i;
}
return -1;
}
void OutputWeight(char *Data,int Length,
char **WhatLetter,
int **Weight,int *Count)
{
int i;
char* Letter=(char*)malloc(Length);
int* LetterCount=(int *)malloc(Length);
int AllCount=0;
int Index;
int Sum=0;
float Persent=0;

for(i=0;i<Length;i++)
{
if(i==0)
{
Letter[0]=Data[i];
LetterCount[0]=1;
AllCount++;
}
else
{
Index=LookFor(Letter,Data[i],AllCount);
if(Index==-1)
{
Letter[AllCount]=Data[i];
LetterCount[AllCount]=1;
AllCount++;
}
else
{
LetterCount[Index]++;
}
}
}
for(i=0;i<AllCount;i++)
{
Sum=Sum+LetterCount[i];
}
(*Weight)=(int*)malloc(AllCount);
(*WhatLetter)=(char*)malloc(AllCount);

for(i=0;i<AllCount;i++)
{
Persent=(float)LetterCount[i]/(float)Sum;
(*Weight)[i]=(int)(1000*Persent);
(*WhatLetter)[i]=Letter[i];
}
(*Count)=AllCount;
}

⑦ huffman算法，解决文件压缩，先读入一个文件，再将文件变成huffman编码，在解压成原文件。

//这个是关于huffmantree构造的代码
#include <iostream>
#include <map>
#include <vector>
#include <set>
#include <algorithm>
#include <iterator>
#include <queue>
using namespace std;

struct HuffNode
{
char chr;
int val_int;
vector<int> code;
HuffNode * left;
HuffNode * right;
bool leaf;
HuffNode(int val,HuffNode * l,HuffNode * r)
{
this->val_int=val;
this->left=l;
this->right=r;
}
};

class HuffTree
{
public:
HuffTree()
{
root=NULL;
}
HuffTree(multimap<int,char> &rhs)
{
root=creatTree(rhs);
}
map<char,vector<int>> gethuffcode()
{
return this->huffcode;
}
bool operator<(HuffNode* p)
{
return (this->root->val_int)<(p->val_int);
}
bool less(HuffNode * s,HuffNode * t)
{
return (s->val_int)<(t->val_int);
}
//用于检查该huffman tree 是否构造成功。
void inorder_recursive(void (*visit)(int x))
{
inorder_recursive(root,visit);
}

//利用level_order() 得到每一个节点的huffmancode
void level_order()
{
queue<HuffNode*> temp;
if(root!=NULL)
{
temp.push(root);
}

while (!temp.empty())
{
(calculateCode)(temp.front());//调用函数，计算该节点的huffmancode

if(temp.front()->left)
{
temp.push(temp.front()->left);
}

if(temp.front()->right)
{
temp.push(temp.front()->right);
}

temp.pop();
}
}

private:
//calculate the huffman code of each HuffNode
void calculateCode(HuffNode* & t)
{
if(t->left )
{

t->left->code=t->code;
t->left->code.push_back(0);
}
if(t->right)
{
t->right->code=t->code;
t->right->code.push_back(1);
}
if(t->leaf)
{
this->huffcode.insert(make_pair(t->chr,t->code));
}
}

HuffNode * root;
map<char,vector<int> > huffcode;//store the huffcode of the huffnode
void inorder_recursive(HuffNode* t, void (*visit)(int x))
{
if(t==NULL)
{
return;
}
else
{
inorder_recursive(t->left,visit);
(visit)(t->val_int);
inorder_recursive(t->right,visit);
}
}
//构造HuffTree
HuffNode * creatTree(multimap<int,char> & rhs)
{
vector<HuffNode*> v_huffNode;
multimap<int,char>::iterator it=rhs.begin();
while (it!=rhs.end ())
{
HuffNode * p=new HuffNode ((*it).first,NULL,NULL);
p->chr=(*it).second;
p->leaf=true;
v_huffNode.push_back(p);
it++;
}

while(v_huffNode.size()>1)
{
sort(v_huffNode.begin(),v_huffNode.end());

HuffNode * ptrHuff1=*v_huffNode.begin();
int temp1=(*v_huffNode.begin())->val_int;
v_huffNode.erase(v_huffNode.begin());
HuffNode * ptrHuff2=*v_huffNode.begin();
int temp2=(*v_huffNode.begin())->val_int;
v_huffNode.erase(v_huffNode.begin());
HuffNode * ptrHuff=new HuffNode(temp1+temp2,ptrHuff1,ptrHuff2);
v_huffNode.push_back(ptrHuff);
}
return *v_huffNode.begin();
}

};
//用于遍历检查
void print(int x)
{
cout<<x<<" ";
}

map<char,vector<int> > huffcode_turnBinary(const multimap<int,char> & rhs)
{
multimap<int,char> another_map(rhs);
HuffTree huftree1(another_map);//构造huffTree
//检查构造的hufftree 利用中序
/*
cout<<"已经构造完hufftree"<<endl;
cout<<"检查构造的huffTree：use inorder"<<endl;
huftree1.inorder_recursive(print);
cout<<endl;
*/
huftree1.level_order();

map<char,vector<int> > result=huftree1.gethuffcode();

return result;

}
//关于将文件解压会的代码
//#include <iostream>
#include <fstream>
#include <vector>
#include <iterator>
#include <map>
#include <iomanip>
#include "changemap.h"
#include "readwenjian.h"
using namespace std;

void huff_to_wenjian(char * f,const map<char, vector<int> > &rhs)
{

map<vector<int>,char> huff_code_new = changemap1(rhs);//huff_code_new 用于将huffcode转为正常文件
map<vector<int>,char>::iterator huff_code_new_it=huff_code_new.begin();
cout<<"用于解码的Huffcode如下"<<endl;
cout<<setw(8)<<"HuffCode"<<setw(8)<<"字符"<<endl;
while(huff_code_new_it!=huff_code_new.end())
{

( (*huff_code_new_it).first.begin(),(*huff_code_new_it).first.end(),ostream_iterator<int>(cout,""));
cout<<setw(4)<<(*huff_code_new_it).second<<endl;
huff_code_new_it++;

}
cout<<"下面开始进行解码先读取huffcode文件"<<endl;
system("pause");
system("cls");

cout<<"读取huffcode 文件"<<endl;
vector<char> ch_huff_wenjian=readwenjian(f);
vector<int> v_hu_wenjian;//文件的huffcode全部将用它进行下一步的解码
//由 char 0 1转化为int 0 1
vector<char>::iterator it_ch=ch_huff_wenjian.begin();
while(it_ch!=ch_huff_wenjian.end())
{
v_hu_wenjian.push_back( (*it_ch)-'0' );
it_ch++;
}
ch_huff_wenjian.clear();

//检查读入huffcode的情况

(v_hu_wenjian.begin(),v_hu_wenjian.end(),ostream_iterator<int> (cout,""));
cout<<"读入的是01文件，下面开始解码！"<<endl;
system("pause");
system("cls");

cout<<"解码正在进行中，可能你要等一下时间…………"<<endl;
vector<int>::iterator v_it=v_hu_wenjian.begin();
vector<int> temp_huff;
string wenjian;//用于存放转化的文件
map<vector<int>,char>::iterator index=huff_code_new.begin();
while(v_it!=v_hu_wenjian.end())
{
temp_huff.push_back((*v_it) );
index=huff_code_new.find(temp_huff);
if(index!=huff_code_new.end())
{
wenjian.push_back((*index).second);
temp_huff.clear();
}
v_it++;
}
cout<<"huffcode 文件已经成功解码！"<<endl;
cout<<"解码文件如下"<<endl;
system("pause");
cout<<wenjian<<endl;

ofstream output;
output.open("newwenjian.txt");
output<<wenjian;
output.close();
wenjian.clear();
cout<<"已经成功将文件储存在newwenjian.txt中！"<<endl;
cout<<"程序运行结束!"<<endl;
system("pause");

return;
}

⑧ 哈夫曼编码的算法代码

//本程序根据26个英文字母出现的频度，得到了它们的一种哈夫曼编码方案 //by jirgal 2005.4.18 #include<iostream.h> #include<iomanip.h> #define NUM 26 //字母数 #define TNUM 51 // #define LTH 15 //编码最大长度 class Node { public: char data; int weight; int parent; int lchild; int rchild; }; void main() { char ch[NUM]={'a','b','c','d','e','f','g','h','i','j','k','l', 'm','n','o','p','q','r','s','t','u','v','w','x','y','z'};//26个字母 int weit[NUM]={856,139,279,378,1304,289,199,528,627,13,42, 339,249,707,797,199,12,677,607,1045,249,92,149,17,199,8};//出现频率 Node nodes[TNUM]; //用对象数组存储哈夫曼树 int i,j,one,two,a,b; int hc[NUM][LTH]; //用于存储编码 int m,n; //初始化数组 for(i=0;i<NUM;i++) { nodes[i].data=ch[i]; nodes[i].weight=weit[i]; nodes[i].parent=-1; nodes[i].lchild=-1; nodes[i].rchild=-1; } for(i=NUM;i<TNUM;i++) { nodes[i].data='@'; nodes[i].weight=-1; nodes[i].parent=-1; nodes[i].lchild=-1; nodes[i].rchild=-1; } //建立哈夫曼树 for(i=NUM;i<TNUM;i++) { a=b=-1; one=two=10000; //最大权数 for(j=0;j<i;j++) { if(nodes[j].parent==-1) if(nodes[j].weight<=two) one=two; two=nodes[j].weight; a=b; b=j; } else if(nodes[j].weight>two&&nodes[j].weight<=one) { one=nodes[j].weight; a=j; } } }//for语句得到 parent=-1(即尚没有父结点)且weight最小的两个结点 nodes[a].parent=i; nodes[b].parent=i; nodes[i].lchild=a; nodes[i].rchild=b; nodes[i].weight=nodes[a].weight+nodes[b].weight; } //初始化hc for(i=0;i<LTH;i++) { for(j=0;j<NUM;j++) { hc[j][i]=7; } } //编码 for(i=0;i<NUM;i++) { j=LTH-1; for(m=i,n=nodes[i].parent;m!=-1;m=n,n=nodes[n].parent) { if(nodes[n].lchild==m) { hc[i][j]=0; } else { hc[i][j]=1; } j--; } } //输出 nodes cout<<"HuffmanTree:"<<endl; cout<<setw(4)<<"NO."<<setw(6)<<"data"<<setw(8)<<"weight"<<setw(6) <<"parnt"<<setw(6)<<"lchd"<<setw(6)<<"rchd"<<endl; for(i=0;i<TNUM;i++) { cout<<setw(4)<<i<<setw(6)<<nodes[i].data<<setw(8)<<nodes[i].weight<<setw(6) <<nodes[i].parent<<setw(6)<<nodes[i].lchild<<setw(6)<<nodes[i].rchild<<endl; } //输出编码 cout<<endl<<"Result:"<<endl; cout<<setw(6)<<"char"<<setw(10)<<"frequency"<<setw(16)<<"huffmancode\n"; for(i=0;i<NUM;i++) { cout<<setw(6)<<ch[i]<<setw(8)<<weit[i]; cout<<" "; for(j=0;j<LTH;j++) { if(hc[i][j]!=7) { cout<<hc[i][j]; } } cout<<endl; } cout<<"\nDone.\n"<<endl; }

⑨ 霍夫曼编程采用的是哪种编程原理

霍夫曼编码的matlab实现一、实验内容：用Matlab语言编程实现霍夫曼（Huffman）编码。二、实验原理及编码步骤：霍夫曼（Huffman）编码算法是满足前缀条件的平均二进制码长最短的编-源输出符号，而将较短的编码码字分配给较大概率的信源输出。算法是：在信源符号集合中，首先将两个最小概率的信源输出合并为新的输出，其概率是两个相应输出符号概率之和。这一过程重复下去，直到只剩下一个合并输出为止，这个最后的合并输出符号的概率为1。这样就得到了一张树图，从树根开始，将编码符号1和0分配在同一节点的任意两分支上，这一分配过程重复直到树叶。从树根到树叶途经支路上的编码最后就构成了一组异前置码，就是霍夫曼编码输出。

⑩ Huffman编码

这个是一个简单的，没有文件导入，需要编码的是自己输入的数组，你将它换成文件读取基本就可以实现对文章中的字符进行Huffman编码，这是我自己曾经做的一个程序，是VC6.0的,没有解码部分，解码部分你反过来推一下算法然后编一下代码就可以了。我还有一个是文件是用matlab作的huffman编码，你要的话给我邮箱，我给你发过去。
#include<iostream.h>
#include<string.h>
#define N 100
typedef struct
{
int wei; //权值
int prt; //父节点
int lch; //左子节点
int rch; // 右子节点
int tmp; //中间变量，tmp=0 还未进行遍历 tmp=1 已近进行过向左遍历 tmp=2 已经进行过左右遍历 向上找到节点
char code[N];
}huffmantree;
void input();
void print(huffmantree );
void select(huffmantree *HT,int n,int &i,int &j)
{
int k;
i=1;
while(HT[i].prt!=0)
{
i++;

}
for(k=i+1;k<=n;k++)
{
if((HT[k].prt=0)&&(HT[k].wei <HT[i].wei))
i=k;
}
j=1;
while((j==i)||(HT[j].prt!=0))
{
j++;
}
for(k=j+1;k<=n;k++)
{
if((HT[k].prt=0)&&k!=i&&HT[k].wei<HT[j].wei)
j=k;
}
}

void huffman(int w[],huffmantree *HT,int n) //w存放n个字符的权值
{
int m=2*n-1;
int i,k,j;
huffmantree *p=0;
for(p=HT+1,i=1;i<=m;i++,p++)
{
HT[i].prt=0;
HT[i].lch=0;
HT[i].rch=0;
}
for(p=HT+1,i=1;i<=n;i++,p++)
{
HT[i].wei=w[i-1];
}
for(p=HT+n+1,i=n+1;i<=m;i++,p++)
{ HT[i].wei=0;}
for(k=n+1;k<=m;k++)
{
select(HT,k-1,i,j); // 找最小值和次小值的位置
HT[i].prt=k,HT[j].prt=k; // 找到i j 的父节点付给k
HT[k].lch=i,HT[k].rch=j; // 父节点的左右指针分别指向i, j
HT[k].wei=HT[i].wei+HT[j].wei;
}
}
void huffmancoding(huffmantree *HT,int n) //n个叶子结点的huffman编码 从根节点开始编码
{
int BT=2*n-1;
int m=BT;
int l,r,p;
char s1[100]="0",s2[100]="1";
for(int i=0;i<=m;i++) //中间变量赋初值
{ HT[i].tmp=0; }
strcpy(HT[m].code," ");
while(1)
{
l=HT[BT].lch;
r=HT[BT].rch;
p=HT[BT].prt;
if(p==0&&HT[BT].tmp==2)
break;
if(l==0||r==0)
{
HT[BT].tmp=2; //如果是叶子结点则给中间变量赋值2向上返回一节结点

}
if(HT[BT].tmp==0) //未进行过遍历，开始向左遍历
{
HT[BT].tmp=1; //已经进行过向左遍历
l=HT[BT].lch;
strcpy(HT[l].code,HT[BT].code);
strcat(HT[l].code,s1);
BT=l;
}
else
if(HT[BT].tmp==1)
{
HT[BT].tmp=2;
r=HT[BT].rch;
strcpy(HT[r].code,HT[BT].code);
strcat(HT[r].code,s2);
BT=r;
}
else if(HT[BT].tmp==2)
{
p=HT[BT].prt;
BT=p;
}
}
}

void print(huffmantree HT[],int n) //总共n个叶子节点
{
int i;
cout<<"源码："<<endl;
for(i=1;i<=n;i++)
cout<<HT[i].wei<<endl;
cout<<"Huffman编码："<<endl;
for(i=1;i<=n;i++)
{

cout<<HT[i].code<<endl;
}
}
void input(int w[],int n)
{
int t,*p;
int i=0;
cout<<"对应的输入源码出现权值：(以-1结束)"<<endl;
cin>>t;
while(t>=0)
{
p=new int;
*p=t;
w[i]=*p;
i++;
cin>>t;
}

}
void main()
{
int n,m;
cout<<"输入源码个数：";
cin>>n;
int *w;
w=new int[n+1];
input(w,n);
m=2*n-1;
huffmantree *HT;
HT=new huffmantree[m+1];
huffman(w,HT,n);
huffmancoding(HT,n);
print(HT,n);
delete w,HT;
}