❶ c语言题：哈夫曼编码（coding）求代码，谢谢~急~满意加分
#include<stdio.h>
#include<stdlib.h>
typedefstructnode
{
charc;
intcount;
}nd;
intcmp(constvoid*p1,constvoid*p2)
{
nd*c=(nd*)p1;
nd*d=(nd*)p2;
if(c->count!=d->count)returnd->count-c->count;
elsereturnc->c-d->c;
}
intmain()
{
nda[26];
inti;
for(i=0;i<26;i++)
{
a[i].c='a'+i;
a[i].count=0;
}
chars[128];
while(scanf("%s",s)!=EOF)
{
for(i=0;s[i]!=0;i++)
{
a[s[i]-'a'].count++;
}
qsort(a,26,sizeof(a[0]),cmp);
for(i=0;a[i].count;i++)
{
printf("%c%d ",a[i].c,a[i].count);
}
}
return0;
}
❷ 哈夫曼编码C语言实现
我写了一个注释较为完整且压缩、解压缩比较全面的：
#include <stdio.h>
#include <conio.h>
#define MAX_FILE 5000/* 假设的文件最大长度 */
#define MAXLIST 256/* 最大MAP值 */
#define MAX_HOFFMAN_LENGTH 50/* 哈夫曼编码长度 */
char dictionary[MAXLIST][2]={0};/* Hash映射,[][0]为权值,[][1]为字符 */
char fileContent[MAX_FILE];/* 处理的字符串大小 */
int Hoffman[MAXLIST][MAX_HOFFMAN_LENGTH]={2};/* 哈夫曼编码序列 */
char HoffmanList[MAXLIST]={0};/* 哈夫曼编码对应的字符有序序列 */
char HoffFileCode[MAX_FILE]={0};/* 哈夫曼编码字符串序列 */
char HoffFile[MAX_FILE]={0};
/* 编码到假设的文件的哈夫曼压缩格式： 依次存储 原字符串长度(1字节存储:可扩展到2字节)、哈夫曼编码数(1字节)、每个哈夫曼编码的长度序列、每个哈夫曼编码对应的字符序列、编码过的哈夫曼字符串 */
char GetFile[MAX_FILE]={0};/* 解码序列 */
void ShellSort(char pData[MAXLIST][2],int Count)/* Shell排序，用于准备有序化要构造的编码权值构造哈夫曼树做准备 */
{
int step[4]={9,5,3,1};/* 增量序列 */
int iTemp,cTemp;
int k,s,w,i,j;
for(i=0;i<4;i++)
{
k=step[i];
s=-k;
for(j=k;j<Count;j++)
{iTemp=pData[j][0];
cTemp=pData[j][1];
w=j-k;
if(s==0)
{
s=-k;
s++;
pData[s][0]=iTemp;
pData[s][1]=cTemp;
}
while((iTemp<pData[w][0])&&(w>=0)&&(w<=Count))
{
pData[w+k][0]=pData[w][0];/* 权值交换 */
pData[w+k][1]=pData[w][1];/* 字符交换 */
w=w-k;
}
pData[w+k][0]=iTemp;
pData[w+k][1]=cTemp;
}
}
}
struct TNode/* 哈夫曼树结点 */
{
struct TNode* pNode;
struct TNode* lNode;
struct TNode* rNode;
char dictionary;
char weight;
};
void TNode_init(struct TNode*tn,char dic,char wei)
{
tn->pNode=0;
tn->lNode=0;
tn->rNode=0;
tn->dictionary=dic;
tn->weight=wei;
}
struct LNode/* 链表结点,用于存储哈夫曼树结点,进而构造哈夫曼树(保证每一步链表结点包含的哈夫曼结点都是有序的) */
{
struct LNode* prev;
struct LNode* next;
struct TNode* tnode;
};
void LNode_init(struct LNode* ln)
{
ln->prev=ln->next=0;
ln->tnode=0;
}
int len=0;/* 哈夫曼编码数 */
int deep=-1;/* 深度 */
void Preorder(struct TNode * p);/* 前序遍历 */
void byLeft(struct TNode*p)/* 经由左结点 */
{
deep++;
Hoffman[len][deep]=0;
Preorder(p);
Hoffman[len][deep]=2;
deep--;
}
void byRight(struct TNode*p)/* 经由右结点 */
{
deep++;
Hoffman[len][deep]=1;
Preorder(p);
Hoffman[len][deep]=2;
deep--;
}
void Preorder(struct TNode * p)
{
int i;
if(p->lNode!=0)/* 当左子结点非空则遍历 */
{
byLeft(p->lNode);
}
if(p->rNode!=0)/* 当右子结点非空则遍历 */
{
byRight(p->rNode);
}
if((p->lNode==0)&&(p->rNode==0))/* 当左右结点都为空，则增加哈夫曼编码数到另一个记录 */
{
Hoffman[len][deep+1]=2;
i=0;
for(;Hoffman[len][i]!=2;i++)
{
Hoffman[len+1][i]=Hoffman[len][i];
}
Hoffman[len+1][i]=2;
HoffmanList[len]=p->dictionary;
len++;
}
}
char generateOne(int k)/* 产生k个连续1的二进制串,比如111,1111,111111,用于编码进假设的文件 */
{
char c=0;
for(;k!=0;k--)
{
c|=(1<<(k-1));
}
return c;
}
int compareBits(char b1,char b2,char c,int l,int d)/* 判断由 [b1,b2] 组成的16位二进制数以d为起点,是否是长度为l的c二进制串（哈夫曼编码）的前缀 */
{
unsigned char t=(((((0x00ff&b1)<<8)|(0x00ff&b2))>>(8-d))&0x00ff);
return (((t)&((generateOne(l)<<(8-l))&0xff))==((c<<(8-l))&0xff));
}
int main()
{
struct LNode* t,*p;
struct LNode* head;
struct TNode *tempTNode,*k1;
int i=0,j,k;
unsigned short fileLen=0;
int len=0,l,b1,b2,d;
char c;
int code[500],h=0;
int codeLen=0,total=0;
/* 或许假定的文件字符串向量中的字符串 */
printf("please Enter string to be pressed:");
scanf("%s",&fileContent);
/* Hash进dictionary */
for(;fileContent[i]!='\0';i++,fileLen++)
{
++dictionary[fileContent[i]][0];
dictionary[fileContent[i]][1]=fileContent[i];
}
/* 把Hash了的dictionary向前靠拢 */
{
for(i=0;i!=MAXLIST;i++)
{
if(dictionary[i][0]!=0)
{
dictionary[len][0]=dictionary[i][0];
dictionary[len][1]=dictionary[i][1];
len++;
}
}
}
printf("the number of Huffman's codes:%d\n",len);
/* 对dictionary按权值进行排序 */
ShellSort(dictionary,len);
/* 构造链表,链表中放有序dictionary权值的树结点 */
head=(struct LNode*)malloc(sizeof(struct LNode)),p=head;
LNode_init(head);
head->next=(struct LNode*)malloc(sizeof(struct LNode));
LNode_init(head->next);
tempTNode=(struct TNode*)malloc(sizeof(struct LNode));
TNode_init(tempTNode,dictionary[0][1],dictionary[0][0]);
head->tnode=tempTNode;
{
for(i=0;i!=len-1;i++)
{
p->next->prev=p->next;
p=p->next;
p->next=(struct LNode*)malloc(sizeof(struct LNode));
LNode_init(p->next);
tempTNode=(struct TNode*)malloc(sizeof(struct TNode)) ;
TNode_init(tempTNode,dictionary[i+1][1],dictionary[i+1][0]);
p->tnode=tempTNode;
}
}
free(p->next);
p->next=0;
/* 每次最小权值的前面两个链表结点中的树结点组成一个子树,子树有合权值,子数的根按权值排序进链表*/
for(p=head;p->next!=0;)
{
p->tnode->pNode=(struct TNode*)malloc(sizeof(struct TNode)) ;
TNode_init(p->tnode->pNode,'\0',(p->tnode->weight)+(p->next->tnode->weight));
p->next->tnode->pNode=p->tnode->pNode;
p->tnode->pNode->lNode=p->tnode;
p->tnode->pNode->rNode=p->next->tnode;
head=p->next;
free(p);
p=head;
p->tnode=p->tnode->pNode;
for(t=head;t->next!=0;t=t->next)
{
if(t->tnode->weight>t->next->tnode->weight)
{
k1=t->tnode;
t->tnode=t->next->tnode;
t->next->tnode=k1;
}
}
}
/* 前序遍历构造哈夫曼编码 */
Preorder(p->tnode);
{
for(i=0;i!=len;i++)
dictionary[HoffmanList[i]][0]=i;
}
/* 存储字符串的哈夫曼压缩编码串,并且打包文件格式 */
{
for(i=0;i!=fileLen;i++)
{
int j=dictionary[fileContent[i]][0];
for(k=0;Hoffman[j][k]!=2;k++)
{
HoffFileCode[codeLen]|=(Hoffman[j][k]<<(7-total%8));
code[h++]=Hoffman[j][k];
if(((total+1)%8)==0)
{
HoffFile[1+len*3+1+codeLen]=HoffFileCode[codeLen];
codeLen++;
}
total++;
}
}
}
HoffFile[1+len*3+1+codeLen]=HoffFileCode[codeLen];
HoffFile[0]=(fileLen);
/* 解压缩假定的文件HoffFile成为原字符串序列 */
printf("Huffman's code list:\n");
HoffFile[1]=len;
{
for(i=0,j=0;i!=len;i++,j=0)
{
for(;Hoffman[i][j]!=2;j++);
HoffFile[i+2]=j;
HoffFile[i+2+2*len]=HoffmanList[i];
for( k=0;k!=j;k++)
{
printf("%d",Hoffman[i][k]);
HoffFile[i+2+len]|=(Hoffman[i][k]<<(j-1-k));
}
printf(":%d\n",HoffmanList[i]);
}
}
{
for(i=0,j=0;i!=(HoffFile[0]&0xff);i++)
{
for(k=0;k!=HoffFile[1];k++)
{
l=HoffFile[2+k],d=j%8,b1=HoffFile[j/8+2+HoffFile[1]*3],b2=HoffFile[j/8+1+2+HoffFile[1]*3];
c=HoffFile[HoffFile[1]+2+k];
if(compareBits(b1,b2,c,l,d))
{
j+=HoffFile[2+k];
GetFile[i]=HoffFile[2+HoffFile[1]*2+k];
break;
}
}
}
}
{
printf("Huffman code List Pressed :\n");
for(i=0;i!=h;i++)
{
printf("%c",code[i]);
if((i+1)%8==0)
printf(" ");
}
}
printf("\n");
{
printf("Huffman code packaged:\n");
for(i=0;i!=HoffFile[0]+HoffFile[1]*3;i++)
{
printf("%c",HoffFile[i]);
}
printf("\n");
}
printf("The initial len :%d\n",fileLen);
printf("The string len pressed:%d\n",(h)/8+1);
printf("The rate%.2f\%",((h/8.0+1)/fileLen)*100);
{
printf("The number of bytes:%d\n",(HoffFile[0]&0xff));
printf("The string decoded:");
for(i=0;i!=(HoffFile[0]&0xff);i++)
{
printf("%c",GetFile[i]);
}
printf("\n");
}
getch();
return 1;
}
❸ 利用C++行程编码编写一款压缩软件，思路：读取，编码，解码。
用哈夫曼压缩文件(C语言）
利用哈夫曼编码制作压缩软件，内容如下：
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<conio.h>
structhead
{
unsignedcharb;//记录字符在数组中的位置
longcount;//字符出现频率（权值）
longparent,lch,rch;//定义哈夫曼树指针变量
charbits[256];//定义存储哈夫曼编码的数组
}
header[512],tmp;
/*压缩*/
voidcompress()
{
charfilename[255],outputfile[255],buf[512];
unsignedcharc;
longi,j,m,n,f;
longmin1,pt1,flength,length1,length2;
doublediv;
FILE*ifp,*ofp;
printf(" 请您输入需要压缩的文件：");
gets(filename);
ifp=fopen(filename,"rb");
if(ifp==NULL)
{
printf(" 文件打开失败! ");
return;
}
printf(" 请您输入压缩后的文件名：");
gets(outputfile);
ofp=fopen(strcat(outputfile,".hub"),"wb");
if(ofp==NULL)
{
printf(" 压缩文件失败! ");
return;
}
flength=0;
while(!feof(ifp))
{
fread(&c,1,1,ifp);
header[c].count++;//字符重复出现频率+1
flength++;//字符出现原文件长度+1
}
flength--;
length1=flength;//原文件长度用作求压缩率的分母
header[c].count--;
for(i=0;i<512;i++)
{
if(header[i].count!=0)header[i].b=(unsignedchar)i;
/*将每个哈夫曼码值及其对应的ASCII码存放在一维数组header[i]中，
且编码表中的下标和ASCII码满足顺序存放关系*/
elseheader[i].b=0;
header[i].parent=-1;header[i].lch=header[i].rch=-1;//对结点进行初始化
}
for(i=0;i<256;i++)//根据频率（权值）大小，对结点进行排序，选择较小的结点进树
{
for(j=i+1;j<256;j++)
{
if(header[i].count<header[j].count)
{
tmp=header[i];
header[i]=header[j];
header[j]=tmp;
}
}
}
for(i=0;i<256;i++)if(header[i].count==0)break;
n=i;//外部叶子结点数为n个时，内部结点数为n-1，整个哈夫曼树的需要的结点数为2*n-1.
m=2*n-1;
for(i=n;i<m;i++)//构建哈夫曼树
{
min1=999999999;//预设的最大权值，即结点出现的最大次数
for(j=0;j<i;j++)
{
if(header[j].parent!=-1)continue;
//parent!=-1说明该结点已存在哈夫曼树中，跳出循环重新选择新结点*/
if(min1>header[j].count)
{
pt1=j;
min1=header[j].count;
continue;
}
}
header[i].count=header[pt1].count;
header[pt1].parent=i;//依据parent域值（结点层数）确定树中结点之间的关系
header[i].lch=pt1;//计算左分支权值大小
min1=999999999;
for(j=0;j<i;j++)
{
if(header[j].parent!=-1)continue;
if(min1>header[j].count)
{
pt1=j;
min1=header[j].count;
continue;
}
}
header[i].count+=header[pt1].count;
header[i].rch=pt1;//计算右分支权值大小
header[pt1].parent=i;
}
for(i=0;i<n;i++)//哈夫曼无重复前缀编码
{
f=i;
header[i].bits[0]=0;//根结点编码0
while(header[f].parent!=-1)
{
j=f;
f=header[f].parent;
if(header[f].lch==j)//置左分支编码0
{
j=strlen(header[i].bits);
memmove(header[i].bits+1,header[i].bits,j+1);
//依次存储连接“0”“1”编码
header[i].bits[0]='0';
}
else//置右分支编码1
{
j=strlen(header[i].bits);
memmove(header[i].bits+1,header[i].bits,j+1);
header[i].bits[0]='1';
}
}
}
fseek(ifp,0,SEEK_SET);//从文件开始位置向前移动0字节，即定位到文件开始位置
fwrite(&flength,sizeof(int),1,ofp);
/*用来将数据写入文件流中，参数flength指向欲写入的数据地址，
总共写入的字符数以参数size*int来决定，返回实际写入的int数目1*/
fseek(ofp,8,SEEK_SET);
buf[0]=0;//定义缓冲区,它的二进制表示00000000
f=0;
pt1=8;
/*假设原文件第一个字符是"A"，8位2进制为01000001，编码后为0110识别编码第一个'0'，
那么我们就可以将其左移一位，看起来没什么变化。下一个是'1'，应该|1，结果00000001
同理4位都做完，应该是00000110，由于字节中的8位并没有全部用完，我们应该继续读下一个字符，
根据编码表继续拼完剩下的4位，如果字符的编码不足4位，还要继续读一个字符，
如果字符编码超过4位，那么我们将把剩下的位信息拼接到一个新的字节里*/
while(!feof(ifp))
{
c=fgetc(ifp);
f++;
for(i=0;i<n;i++)
{
if(c==header[i].b)break;
}
strcat(buf,header[i].bits);
j=strlen(buf);
c=0;
while(j>=8)//对哈夫曼编码位操作进行压缩存储
{
for(i=0;i<8;i++)
{
if(buf[i]=='1')c=(c<<1)|1;
elsec=c<<1;
}
fwrite(&c,1,1,ofp);
pt1++;//统计压缩后文件的长度
strcpy(buf,buf+8);//一个字节一个字节拼接
j=strlen(buf);
}
if(f==flength)break;
}
if(j>0)//对哈夫曼编码位操作进行压缩存储
{
strcat(buf,"00000000");
for(i=0;i<8;i++)
{
if(buf[i]=='1')c=(c<<1)|1;
elsec=c<<1;
}
fwrite(&c,1,1,ofp);
pt1++;
}
fseek(ofp,4,SEEK_SET);
fwrite(&pt1,sizeof(long),1,ofp);
fseek(ofp,pt1,SEEK_SET);
fwrite(&n,sizeof(long),1,ofp);
for(i=0;i<n;i++)
{
fwrite(&(header[i].b),1,1,ofp);
c=strlen(header[i].bits);
fwrite(&c,1,1,ofp);
j=strlen(header[i].bits);
if(j%8!=0)//若存储的位数不是8的倍数，则补0
{
for(f=j%8;f<8;f++)
strcat(header[i].bits,"0");
}
while(header[i].bits[0]!=0)
{
c=0;
for(j=0;j<8;j++)//字符的有效存储不超过8位，则对有效位数左移实现两字符编码的连接
{
if(header[i].bits[j]=='1')c=(c<<1)|1;//|1不改变原位置上的“0”“1”值
elsec=c<<1;
}
strcpy(header[i].bits,header[i].bits+8);//把字符的编码按原先存储顺序连接
fwrite(&c,1,1,ofp);
}
}
length2=pt1--;
div=((double)length1-(double)length2)/(double)length1;//计算文件的压缩率
fclose(ifp);
fclose(ofp);
printf(" 压缩文件成功! ");
printf(" 压缩率为%f%% ",div*100);
return;
}
/*解压缩*/
voincompress()
{
charfilename[255],outputfile[255],buf[255],bx[255];
unsignedcharc;
longi,j,m,n,f,p,l;
longflength;
FILE*ifp,*ofp;
printf(" 请您输入需要解压缩的文件：");
gets(filename);
ifp=fopen(strcat(filename,".hub"),"rb");
if(ifp==NULL)
{
printf(" 文件打开失败! ");
return;
}
printf(" 请您输入解压缩后的文件名：");
gets(outputfile);
ofp=fopen(outputfile,"wb");
if(ofp==NULL)
{
printf(" 解压缩文件失败! ");
return;
}
fread(&flength,sizeof(long),1,ifp);//读取原文件长度，对文件进行定位
fread(&f,sizeof(long),1,ifp);
fseek(ifp,f,SEEK_SET);
fread(&n,sizeof(long),1,ifp);
for(i=0;i<n;i++)
{
fread(&header[i].b,1,1,ifp);
fread(&c,1,1,ifp);
p=(long)c;//读取原文件字符的权值
header[i].count=p;
header[i].bits[0]=0;
if(p%8>0)m=p/8+1;
elsem=p/8;
for(j=0;j<m;j++)
{
fread(&c,1,1,ifp);
f=c;
itoa(f,buf,2);//将f转换为二进制表示的字符串
f=strlen(buf);
for(l=8;l>f;l--)
{
strcat(header[i].bits,"0");
}
strcat(header[i].bits,buf);
}
header[i].bits[p]=0;
}
for(i=0;i<n;i++)//根据哈夫曼编码的长短，对结点进行排序
{
for(j=i+1;j<n;j++)
{
if(strlen(header[i].bits)>strlen(header[j].bits))
{
tmp=header[i];
header[i]=header[j];
header[j]=tmp;
}
}
}
p=strlen(header[n-1].bits);
fseek(ifp,8,SEEK_SET);
m=0;
bx[0]=0;
while(1)//通过哈夫曼编码的长短，依次解码，从原来的位存储还原到字节存储
{
while(strlen(bx)<(unsignedint)p)
{
fread(&c,1,1,ifp);
f=c;
itoa(f,buf,2);
f=strlen(buf);
for(l=8;l>f;l--)//在单字节内对相应位置补0
{
strcat(bx,"0");
}
strcat(bx,buf);
}
for(i=0;i<n;i++)
{
if(memcmp(header[i].bits,bx,header[i].count)==0)break;
}
strcpy(bx,bx+header[i].count);/*从压缩文件中的按位存储还原到按字节存储字符，
字符位置不改变*/
c=header[i].b;
fwrite(&c,1,1,ofp);
m++;//统计解压缩后文件的长度
if(m==flength)break;//flength是原文件长度
}
fclose(ifp);
fclose(ofp);
printf(" 解压缩文件成功! ");
if(m==flength)//对解压缩后文件和原文件相同性比较进行判断（根据文件大小）
printf(" 解压缩文件与原文件相同! ");
elseprintf(" 解压缩文件与原文件不同! ");
return;
}
/*主函数*/
intmain()
{
intc;
while(1)//菜单工具栏
{
printf(" _______________________________________________ ");
printf(" ");
printf(" *压缩、解压缩小工具* ");
printf(" _______________________________________________ ");
printf(" _______________________________________________ ");
printf(" || ");
printf(" |1.压缩| ");
printf(" |2.解压缩| ");
printf(" |0.退出| ");
printf(" |_______________________________________________| ");
printf(" ");
printf(" 说明：（1）采用哈夫曼编码 ");
printf(" （2）适用于文本文件 ");
printf(" ");
do//对用户输入进行容错处理
{
printf(" *请选择相应功能(0-2):");
c=getch();
printf("%c ",c);
if(c!='0'&&c!='1'&&c!='2')
{
printf(" @_@请检查您的输入在0~2之间！ ");
printf(" 请再输入一遍！ ");
}
}while(c!='0'&&c!='1'&&c!='2');
if(c=='1')compress();//调用压缩子函数
elseif(c=='2')uncompress();//调用解压缩子函数
else
{
printf(" 欢迎您再次使用该工具^_^ ");
exit(0);//退出该工具
}
system("pause");//任意键继续
system("cls");//清屏
}
return0;
}
❹ 求助：关于C语言压缩MP3算法！
具体怎样将记录了模拟音频信号的文件转换为mp3格式文件，我也不知道具体，原理还是可以告诉你！
但是，无论什么文件，都可以使用huffman编码来压缩，
huffman编码是一种无损的编码，就是可以还原样的编码
给你一个我大一看的一huffman编码程序，可以编码也可以解码
比楼上的强一点，找qq:504449327要，就说要huffman编码的程序
这个是我同学的哈夫曼编码程序
另外还有解码的程序，要的话再商量
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#define TRUE 1
#define ERROR 0
#define OK 1
#define FALSE 0
#define INFEASIBLE -1
#define OVERFLOW -2
#define Status int
#define MAXLENGTH 128
typedef struct HTnode
{
long weight;
int parent;
int lchild;
int rchild;
}HTNode, *HuffmanTree;
typedef struct CTnode
{
long weight;
char *coded_string;
}CharacterTable;
typedef char * *HuffmanCode;
FILE *fp=NULL;
void Analyse (CharacterTable * *character_table, long * *w, char * *chara, int &n)//分析所有不同的字符的权值
{
long *tmpw;
char ch, *tmpchara;
int i;
(*character_table)=(CharacterTable *)malloc(128*sizeof(CharacterTable));//定义存放字母的数组
for(i=0; i<128; i++)
{
(*character_table)[i].weight=0; //初始化
(*character_table)[i].coded_string=NULL;
}
ch=fgetc(fp);
while(!feof(fp))//诺到文件末尾，函数值为真
{
//m=ch;
if(ch<128 && ch>=0)
(*character_table)[ch].weight++;//获得各个字母在文件中出现的次数
ch=fgetc(fp);
}
for(i=0, n=0; i<128; i++)
if((*character_table)[i].weight)
n++; //统计有多少不同的字符数
(*w)=(long *)malloc(n*sizeof(long));//deliver the character and the weight to main
(*chara)=(char *)malloc(n*sizeof(char));
tmpw=(*w);
tmpchara=(*chara);
for(i=0; i<128; i++)
if((*character_table)[i].weight)
{//将权值放入*w数组中
*(*w)=(*character_table)[i].weight;
*(*chara)=i;//这里i是字符
(*w)++;
(*chara)++;
}
(*w)=tmpw;
(*chara)=tmpchara;//指针返回数组头
}
void Select (HuffmanTree *HT, int i, int *Min1, int *Min2)
{
int j, n, tmp1=-1, tmp2=-2;
for(n=0; n<i; n++)
{
if(!(*HT)[n].parent)
{
if(tmp1 == -1)
{
tmp1=n;
continue;
}
if(tmp2 == -2)
{
tmp2=n;
if((*HT)[tmp1].weight > (*HT)[tmp2].weight)
{
j=tmp1;
tmp1=tmp2;
tmp2=j;
}
continue;
}
if((*HT)[n].weight < (*HT)[tmp2].weight) //scan and change
if((*HT)[n].weight < (*HT)[tmp1].weight)
tmp1=n;
else
tmp2=n;
}
}
*Min1=tmp1;
*Min2=tmp2; //tmp[Min2].weight >= tmp[Min1].weight
}
Status Huffman(HuffmanTree *HT, HuffmanCode *HC,long *w, int n)
{
int m, i, Min1, Min2, p1, p2, start, *M1, *M2;
char *cd;
HuffmanTree *HTp;
if(n<1) return ERROR;
m=2*n-1;
(*HT)=(HTNode *)malloc(m*sizeof(HTNode)); //intialise Hc in main
HTp=HT;
for(i=0; i<n; i++, w++)
{
(*HTp)[i].weight=*w;
(*HTp)[i].parent=0;
(*HTp)[i].lchild=0;
(*HTp)[i].rchild=0;
}
for(; i<m; i++)
{
(*HTp)[i].weight=0;
(*HTp)[i].parent=0;
(*HTp)[i].lchild=0;
(*HTp)[i].rchild=0;
}
M1=&Min1;
M2=&Min2;
for(i=n; i<m; i++)
{
Select(HT, i, M1, M2);
(*HTp)[Min1].parent=i;
(*HTp)[Min2].parent=i;
(*HTp)[i].lchild=Min1; //左孩子要小一些
(*HTp)[i].rchild=Min2;
(*HTp)[i].weight=(*HTp)[Min1].weight + (*HTp)[Min2].weight;
}
//coded the weight below
(*HC)=(HuffmanCode)malloc(n*sizeof(char *));
cd=(char *)malloc(n*sizeof(char));
cd[n-1]='\0';
for(i=0; i<n; i++)
{
start=n-1;
for(p1=i, p2=(*HTp)[p1].parent; p2!=0; p1=p2, p2=(*HTp)[p1].parent)
{
if( (*HTp)[p2].lchild ==p1) //编码, 左孩子为0, 右孩子为1
cd[--start]='0';
else
cd[--start]='1';
}
(*HC)[i]=(char *)malloc((n-start)*sizeof(char));
strcpy((*HC)[i],&cd[start]);
} //over
return OK;
}
void Weinumber_to_stringnumber(char * *stringnumber, long *w, int leaves)
{//将权值以字符数组形式存放在上米的数组中
char tmp[30];
long i, j, k;
int start;
for(i=0; i<leaves; i++)
{
start=29;
tmp[start--]='\0';
for(k=w[i], j=k%10; k!=0; k=k/10, j=k%10)
tmp[start--]=j+'0';
stringnumber[i]=(char *)malloc((29-start)*sizeof(char));
strcpy(stringnumber[i], &tmp[start+1]);
}
}
void Save_huffman_weight_dictionary(long *w, char *character, int leaves, HuffmanCode *HC)
{
char * *stringnumber;
int i;
FILE *fp1;
fp1=fopen("weight.txt", "w");
stringnumber=(char * *)malloc(leaves * sizeof(char *));
Weinumber_to_stringnumber(stringnumber, w, leaves);
for(i=0; i<leaves; i++)
{
fputc(' ', fp1); // for unhuffman add '
fputc(character[i], fp1);
fputc('\t', fp1);
fputs(stringnumber[i], fp1);
fputc('\t', fp1);
fputc('\'', fp1);
fputs((*HC)[i], fp1);
fputc('\'', fp1);
fputc('\n', fp1);
}
fclose(fp1);
}
void Huffman_file_convert(HuffmanCode *HC, CharacterTable *character_table) //fp had opened
{
int i;
char ch;
FILE *fp2=fopen("coded.txt","w");
for( i=0; i<128; i++)
if(character_table[i].weight)
{
character_table[i].coded_string=*(*HC);
(*HC)++;
}
ch=fgetc(fp);
while(!feof(fp))
{
if( (ch>=0 && ch<128) && (character_table[ch].weight) )//it is very importan to add (ch>=0 && ch<128)
fputs(character_table[ch].coded_string,fp2);
ch=fgetc(fp);
}
fclose(fp2);
}
void fileopen1() //通过指针fp传递信息
{
char filename[100];
do{
printf("\n\n\t请输入要编码的文件:");
scanf("%s", filename);
if ((fp=fopen(filename,"r"))==NULL)
printf("\n\t不能打开此文件! 请重新输入!\n");
}while(!fp);
}
void main()
{
HuffmanTree Ht, *ht;//three level pointer
HuffmanCode Hc, *hc;
CharacterTable *CT, * *character_table;
long *weight, * *w;
char * character, * *chara;
int leave; //the all leaves number
ht=&Ht;
hc=&Hc;
w=&weight;
chara=&character;
character_table=&CT;
fileopen1();
Analyse(character_table, w, chara, leave);
fseek(fp, 0, 0);//将文件指针还原
Huffman(ht, hc, weight, leave);//构建哈弗曼树！
Save_huffman_weight_dictionary(weight, character, leave, hc);
Huffman_file_convert(hc, CT);
fclose(fp);
}
❺ 如何用C语言实现数据压缩
首先你要熟悉套接字的使用，然后要对ftp协议，
包括其中的数据包，通信过程有一定了解。
c语言开发网络程序一般都是用socket套接字这一套函数，你可以去看看资料
❻ 哈夫曼编码做压缩软件的问题c++
因为32个0、1是4个字节。（因为8个0、1是一个字节）
但是它这个东西算出来的是一个0、1占一个字节的那种
所以要变成32个0、1占4字节的那种
❼ C语言都有哪些经典的无损压缩算法
C语言经典的无损压缩算法有：哈夫曼算法、LZ。
哈夫曼算法：
哈夫曼编码是David A. Huffman于1952年发明的一种满足对编码算法要求的一种编码算法。
哈夫曼算法是利用频率信息构造一棵二叉树，频率高的离根节点近（编码长度短），频率低的离根节点远（编码长度长），手动构造方法是先将字母按照频率从小到大排序，然后不断选择当前还没有父节点的节点中权值最小的两个，构造新的父节点，父节点的值为这两个节点值的和，直到构造成一棵二叉树。
LZ算法：
LZ算法及其衍生变形算法是压缩算法的一个系列。LZ77和LZ78算法分别在1977年和1978年被创造出来。虽然他们名字差不多，但是算法方法完全不同。这一系列算法主要适用于字母数量有限的信息，比如文字、源码等。流行的GIF和PNG格式的图像，使用颜色数量有限的颜色空间，其压缩就采用了两种算法的灵活变形应用。
❽ 哈夫曼编码的C语言源代码
/*文件名:exp7-6.cpp*/
#include <stdio.h>
#include <string.h>
#define N 50 /*叶子结点数*/
#define M 2*N-1 /*树中结点总数*/
typedef struct
{
char data[5]; /*结点值*/
int weight; /*权重*/
int parent; /*双亲结点*/
int lchild; /*左孩子结点*/
int rchild; /*右孩子结点*/
} HTNode;
typedef struct
{
char cd[N]; /*存放哈夫曼码*/
int start;
} HCode;
void CreateHT(HTNode ht[],int n)
{
int i,k,lnode,rnode;
int min1,min2;
for (i=0;i<2*n-1;i++) /*所有结点的相关域置初值-1*/
ht[i].parent=ht[i].lchild=ht[i].rchild=-1;
for (i=n;i<2*n-1;i++) /*构造哈夫曼树*/
{
min1=min2=32767; /*lnode和rnode为最小权重的两个结点位置*/
lnode=rnode=-1;
for (k=0;k<=i-1;k++)
if (ht[k].parent==-1) /*只在尚未构造二叉树的结点中查找*/
{
if (ht[k].weight<min1)
{
min2=min1;rnode=lnode;
min1=ht[k].weight;lnode=k;
}
else if (ht[k].weight<min2)
{
min2=ht[k].weight;rnode=k;
}
}
ht[lnode].parent=i;ht[rnode].parent=i;
ht[i].weight=ht[lnode].weight+ht[rnode].weight;
ht[i].lchild=lnode;ht[i].rchild=rnode;
}
}
void CreateHCode(HTNode ht[],HCode hcd[],int n)
{
int i,f,c;
HCode hc;
for (i=0;i<n;i++) /*根据哈夫曼树求哈夫曼编码*/
{
hc.start=n;c=i;
f=ht[i].parent;
while (f!=-1) /*循序直到树根结点*/
{
if (ht[f].lchild==c) /*处理左孩子结点*/
hc.cd[hc.start--]='0';
else /*处理右孩子结点*/
hc.cd[hc.start--]='1';
c=f;f=ht[f].parent;
}
hc.start++; /*start指向哈夫曼编码最开始字符*/
hcd[i]=hc;
}
}
void DispHCode(HTNode ht[],HCode hcd[],int n)
{
int i,k;
int sum=0,m=0,j;
printf(" 输出哈夫曼编码:\n"); /*输出哈夫曼编码*/
for (i=0;i<n;i++)
{
j=0;
printf(" %s:\t",ht[i].data);
for (k=hcd[i].start;k<=n;k++)
{
printf("%c",hcd[i].cd[k]);
j++;
}
m+=ht[i].weight;
sum+=ht[i].weight*j;
printf("\n");
}
printf("\n 平均长度=%g\n",1.0*sum/m);
}
void main()
{
int n=15,i;
char *str[]={"The","of","a","to","and","in","that","he","is","at","on","for","His","are","be"};
int fnum[]={1192,677,541,518,462,450,242,195,190,181,174,157,138,124,123};
HTNode ht[M];
HCode hcd[N];
for (i=0;i<n;i++)
{
strcpy(ht[i].data,str[i]);
ht[i].weight=fnum[i];
}
printf("\n");
CreateHT(ht,n);
CreateHCode(ht,hcd,n);
DispHCode(ht,hcd,n);
printf("\n");
}
以前写的，你照着改下就行的.
❾ 压缩问题
利用哈夫曼编码制作压缩软件，内容如下：
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <conio.h>
struct head
{
unsigned char b; //记录字符在数组中的位置
long count; //字符出现频率（权值）
long parent,lch,rch; //定义哈夫曼树指针变量
char bits[256]; //定义存储哈夫曼编码的数组
}
header[512],tmp;
/*压缩*/
void compress()
{
char filename[255],outputfile[255],buf[512];
unsigned char c;
long i,j,m,n,f;
long min1,pt1,flength,length1,length2;
double div;
FILE *ifp,*ofp;
printf("\t请您输入需要压缩的文件：");
gets(filename);
ifp=fopen(filename,"rb");
if(ifp==NULL)
{
printf("\n\t文件打开失败!\n\n");
return;
}
printf("\t请您输入压缩后的文件名：");
gets(outputfile);
ofp=fopen(strcat(outputfile,".hub"),"wb");
if(ofp==NULL)
{
printf("\n\t压缩文件失败!\n\n");
return;
}
flength=0;
while(!feof(ifp))
{
fread(&c,1,1,ifp);
header[c].count++; //字符重复出现频率+1
flength++; //字符出现原文件长度+1
}
flength--;
length1=flength; //原文件长度用作求压缩率的分母
header[c].count--;
for(i=0;i<512;i++)
{
if(header[i].count!=0) header[i].b=(unsigned char)i;
/*将每个哈夫曼码值及其对应的ASCII码存放在一维数组header[i]中，
且编码表中的下标和ASCII码满足顺序存放关系*/
else header[i].b=0;
header[i].parent=-1;header[i].lch=header[i].rch=-1; //对结点进行初始化
}
for(i=0;i<256;i++) //根据频率（权值）大小，对结点进行排序，选择较小的结点进树
{
for(j=i+1;j<256;j++)
{
if(header[i].count<header[j].count)
{
tmp=header[i];
header[i]=header[j];
header[j]=tmp;
}
}
}
for(i=0;i<256;i++) if(header[i].count==0) break;
n=i; //外部叶子结点数为n个时，内部结点数为n-1，整个哈夫曼树的需要的结点数为2*n-1.
m=2*n-1;
for(i=n;i<m;i++) //构建哈夫曼树
{
min1=999999999; //预设的最大权值，即结点出现的最大次数
for(j=0;j<i;j++)
{
if(header[j].parent!=-1) continue;
//parent!=-1说明该结点已存在哈夫曼树中，跳出循环重新选择新结点*/
if(min1>header[j].count)
{
pt1=j;
min1=header[j].count;
continue;
}
}
header[i].count=header[pt1].count;
header[pt1].parent=i; //依据parent域值（结点层数）确定树中结点之间的关系
header[i].lch=pt1; //计算左分支权值大小
min1=999999999;
for(j=0;j<i;j++)
{
if(header[j].parent!=-1) continue;
if(min1>header[j].count)
{
pt1=j;
min1=header[j].count;
continue;
}
}
header[i].count+=header[pt1].count;
header[i].rch=pt1; //计算右分支权值大小
header[pt1].parent=i;
}
for(i=0;i<n;i++) //哈夫曼无重复前缀编码
{
f=i;
header[i].bits[0]=0; //根结点编码0
while(header[f].parent!=-1)
{
j=f;
f=header[f].parent;
if(header[f].lch==j) //置左分支编码0
{
j=strlen(header[i].bits);
memmove(header[i].bits+1,header[i].bits,j+1);
//依次存储连接“0”“1”编码
header[i].bits[0]='0';
}
else //置右分支编码1
{
j=strlen(header[i].bits);
memmove(header[i].bits+1,header[i].bits,j+1);
header[i].bits[0]='1';
}
}
}
fseek(ifp,0,SEEK_SET); //从文件开始位置向前移动0字节，即定位到文件开始位置
fwrite(&flength,sizeof(int),1,ofp);
/*用来将数据写入文件流中，参数flength指向欲写入的数据地址，
总共写入的字符数以参数size*int来决定，返回实际写入的int数目1*/
fseek(ofp,8,SEEK_SET);
buf[0]=0; //定义缓冲区,它的二进制表示00000000
f=0;
pt1=8;
/*假设原文件第一个字符是"A"，8位2进制为01000001，编码后为0110识别编码第一个'0'，
那么我们就可以将其左移一位，看起来没什么变化。下一个是'1'，应该|1，结果00000001
同理4位都做完，应该是00000110，由于字节中的8位并没有全部用完，我们应该继续读下一个字符，
根据编码表继续拼完剩下的4位，如果字符的编码不足4位，还要继续读一个字符，
如果字符编码超过4位，那么我们将把剩下的位信息拼接到一个新的字节里*/
while(!feof(ifp))
{
c=fgetc(ifp);
f++;
for(i=0;i<n;i++)
{
if(c==header[i].b) break;
}
strcat(buf,header[i].bits);
j=strlen(buf);
c=0;
while(j>=8) //对哈夫曼编码位操作进行压缩存储
{
for(i=0;i<8;i++)
{
if(buf[i]=='1') c=(c<<1)|1;
else c=c<<1;
}
fwrite(&c,1,1,ofp);
pt1++; //统计压缩后文件的长度
strcpy(buf,buf+8); //一个字节一个字节拼接
j=strlen(buf);
}
if(f==flength) break;
}
if(j>0) //对哈夫曼编码位操作进行压缩存储
{
strcat(buf,"00000000");
for(i=0;i<8;i++)
{
if(buf[i]=='1') c=(c<<1)|1;
else c=c<<1;
}
fwrite(&c,1,1,ofp);
pt1++;
}
fseek(ofp,4,SEEK_SET);
fwrite(&pt1,sizeof(long),1,ofp);
fseek(ofp,pt1,SEEK_SET);
fwrite(&n,sizeof(long),1,ofp);
for(i=0;i<n;i++)
{
fwrite(&(header[i].b),1,1,ofp);
c=strlen(header[i].bits);
fwrite(&c,1,1,ofp);
j=strlen(header[i].bits);
if(j%8!=0) //若存储的位数不是8的倍数，则补0
{
for(f=j%8;f<8;f++)
strcat(header[i].bits,"0");
}
while(header[i].bits[0]!=0)
{
c=0;
for(j=0;j<8;j++) //字符的有效存储不超过8位，则对有效位数左移实现两字符编码的连接
{
if(header[i].bits[j]=='1') c=(c<<1)|1; //|1不改变原位置上的“0”“1”值
else c=c<<1;
}
strcpy(header[i].bits,header[i].bits+8); //把字符的编码按原先存储顺序连接
fwrite(&c,1,1,ofp);
}
}
length2=pt1--;
div=((double)length1-(double)length2)/(double)length1; //计算文件的压缩率
fclose(ifp);
fclose(ofp);
printf("\n\t压缩文件成功!\n");
printf("\t压缩率为 %f%%\n\n",div*100);
return;
}
/*解压缩*/
void uncompress()
{
char filename[255],outputfile[255],buf[255],bx[255];
unsigned char c;
long i,j,m,n,f,p,l;
long flength;
FILE *ifp,*ofp;
printf("\t请您输入需要解压缩的文件：");
gets(filename);
ifp=fopen(strcat(filename,".hub"),"rb");
if(ifp==NULL)
{
printf("\n\t文件打开失败!\n");
return;
}
printf("\t请您输入解压缩后的文件名：");
gets(outputfile);
ofp=fopen(outputfile,"wb");
if(ofp==NULL)
{
printf("\n\t解压缩文件失败!\n");
return;
}
fread(&flength,sizeof(long),1,ifp); //读取原文件长度，对文件进行定位
fread(&f,sizeof(long),1,ifp);
fseek(ifp,f,SEEK_SET);
fread(&n,sizeof(long),1,ifp);
for(i=0;i<n;i++)
{
fread(&header[i].b,1,1,ifp);
fread(&c,1,1,ifp);
p=(long)c; //读取原文件字符的权值
header[i].count=p;
header[i].bits[0]=0;
if(p%8>0) m=p/8+1;
else m=p/8;
for(j=0;j<m;j++)
{
fread(&c,1,1,ifp);
f=c;
itoa(f,buf,2); //将f转换为二进制表示的字符串
f=strlen(buf);
for(l=8;l>f;l--)
{
strcat(header[i].bits,"0");
}
strcat(header[i].bits,buf);
}
header[i].bits[p]=0;
}
for(i=0;i<n;i++) //根据哈夫曼编码的长短，对结点进行排序
{
for(j=i+1;j<n;j++)
{
if(strlen(header[i].bits)>strlen(header[j].bits))
{
tmp=header[i];
header[i]=header[j];
header[j]=tmp;
}
}
}
p=strlen(header[n-1].bits);
fseek(ifp,8,SEEK_SET);
m=0;
bx[0]=0;
while(1) //通过哈夫曼编码的长短，依次解码，从原来的位存储还原到字节存储
{
while(strlen(bx)<(unsigned int)p)
{
fread(&c,1,1,ifp);
f=c;
itoa(f,buf,2);
f=strlen(buf);
for(l=8;l>f;l--) //在单字节内对相应位置补0
{
strcat(bx,"0");
}
strcat(bx,buf);
}
for(i=0;i<n;i++)
{
if(memcmp(header[i].bits,bx,header[i].count)==0) break;
}
strcpy(bx,bx+header[i].count); /*从压缩文件中的按位存储还原到按字节存储字符，
字符位置不改变*/
c=header[i].b;
fwrite(&c,1,1,ofp);
m++; //统计解压缩后文件的长度
if(m==flength) break; //flength是原文件长度
}
fclose(ifp);
fclose(ofp);
printf("\n\t解压缩文件成功!\n");
if(m==flength) //对解压缩后文件和原文件相同性比较进行判断（根据文件大小）
printf("\t解压缩文件与原文件相同!\n\n");
else printf("\t解压缩文件与原文件不同!\n\n");
return;
}
/*主函数*/
int main()
{
int c;
while(1) //菜单工具栏
{
printf("\t _______________________________________________\n");
printf("\n");
printf("\t * 压缩、解压缩 小工具 * \n");
printf("\t _______________________________________________\n");
printf("\t _______________________________________________\n");
printf("\t| |\n");
printf("\t| 1.压缩 |\n");
printf("\t| 2.解压缩 |\n");
printf("\t| 0.退出 |\n");
printf("\t|_______________________________________________|\n");
printf("\n");
printf("\t 说明：（1）采用哈夫曼编码\n");
printf("\t （2）适用于文本文件\n");
printf("\n");
do //对用户输入进行容错处理
{
printf("\n\t*请选择相应功能(0-2):");
c=getch();
printf("%c\n",c);
if(c!='0' && c!='1' && c!='2')
{
printf("\t@_@请检查您的输入在0~2之间！\n");
printf("\t请再输入一遍！\n");
}
}while(c!='0' && c!='1' && c!='2');
if(c=='1') compress(); //调用压缩子函数
else if(c=='2') uncompress(); //调用解压缩子函数
else
{
printf("\t欢迎您再次使用该工具^_^\n");
exit(0); //退出该工具
}
system("pause"); //任意键继续
system("cls"); //清屏
}
return 0;
}
❿ 急求霍夫曼编码c语言实现的源程序
int get_code_len(int index)
{
check();
if (index < 0 || index >= (int)code_lens.size())
throw new huffman_exception("参数非法");
return code_lens[index];
}
vector<int> get_all_code_lens(void)
{
check();
return code_lens;
}
unsigned long get_code(int index)
{
check();
if (index < 0 || index >= (int)codes.size())
throw new huffman_exception("参数非法");
return codes[index];
}
vector<unsigned long> get_all_codes(void)
{
check();
return codes;
}
string get_code_str(int index)
{
check();
if (index < 0 || index >= (int)codes.size())
throw new huffman_exception("参数非法");
return long_to_string(codes[index], code_lens[index]);
}
vector<string> get_all_code_strs(void)
{
check();
vector<string> v;
for(int i = 0; i < (int)codes.size(); i++)
v.push_back(long_to_string(codes[i], code_lens[i]));
return v;
}
int find(unsigned long code)
{
check();
for(int i = 0; i < (int)codes.size(); i++)
if (codes[i] == code)
return i;
return -1;
}
int find(const string& code)
{
return find(string_to_long(code.c_str()));
}
inline void check()
{
if (codes.size() <= 0)
throw new huffman_exception("尚未调用过generate_codes()");
}
unsigned long string_to_long(const char* code)
{
unsigned long ret = 0;
int len = (int)strlen(code);
for(int i = len - 1; i >= 0; i--)
if (code[i] == '1')
ret |= (1ul << (len - i - 1));
return ret;
}
string long_to_string(unsigned long code, int code_len)
{
char* buf = new char[code_len + 1];
if (buf == NULL)
throw new huffman_exception("no enough memory.");
memset(buf, 0, code_len + 1);
unsigned long bit = 1 << (code_len - 1);
for(int i = 0; i < code_len; i++)
{
if (code & bit)
buf[i] = '1';
else
buf[i] = '0';
bit >>= 1;
}
string ret(buf); delete buf;
return ret;
}
void generate_canonical_codes()
{
if (code_lens.size() <= 0)
throw new huffman_exception("生成Canonical Huffman编码前，应已知所有元素码长");
int max_code_len = 0;
int min_code_len = 1000;
const int tmp = sizeof(unsigned long) * 8 + 1;
int len_count[tmp];
unsigned long min_code[tmp];
memset(len_count, 0, tmp * sizeof(int));
memset(min_code, 0, tmp * sizeof(unsigned long));
int num = (int)code_lens.size();
// 统计码长信息
for (int i = 0; i < num; i++)
{
int codelen = code_lens[i];
// huffman_base用unsigned long存储编码，因此
// 码长要限制在sizeof(unsigned long)*8以内
// 这里对超长的编码都简单忽略掉了
if ((unsigned long)codelen > sizeof(unsigned long)*8)
continue;
if (codelen > max_code_len)
max_code_len = codelen;
if (codelen < min_code_len)
min_code_len = codelen;
len_count[codelen]++;
}
// 计算特定码长的所有元素中最小的编码,这里使用的是
// Canonical Huffman编码规则,请参见相关文献
for (int i = max_code_len - 1; i >= 0; i--)
min_code[i] = (min_code[i + 1] + len_count[i + 1]) >> 1;
// 已知特定码长的所有元素中最小的编码,同样码长的元素,
// 编码逐个加1就可以了
codes.clear();
for (int i = 0; i < num; i++)
if (code_lens[i] > 0 && (unsigned long)code_lens[i] <= sizeof(unsigned long)*8)
codes.push_back(min_code[code_lens[i]]++);
else
codes.push_back(0);
}
bool verify()
{
check();
int max = 0;
const int code_len_limit = 100; // 这里能检验的最大码长是100
int len_count[code_len_limit + 1];
memset(len_count, 0, sizeof(int)*(code_len_limit+1));
for(int i = 0; i < (int)code_lens.size(); i++)
{
if (code_lens[i] > code_len_limit)
return true; // 如果有超长码，就不检验了
len_count[code_lens[i]]++;
if (code_lens[i] > max) max = code_lens[i];
}
// 从根开始，算每层分支结点数目，如果最后一层不为0，就表明Huffman树有错误
int nonleaf = 1;
for(int i = 1; i <= max; i++)
nonleaf = nonleaf * 2 - len_count[i];
return (nonleaf == 0);
}
//主函数
void generate_codes(int num, const unsigned long* weights)
{
if (num <= 1 || weights == NULL)
throw new huffman_exception("参数非法");
int heap_num, i, nonzero_count;
// 分配生成Huffman树时使用的堆结构,其大小是元素数目的2倍
unsigned long* heap = new unsigned long[2*num];
if (heap == NULL) throw new huffman_exception("内存不足");
// 将所有元素权值值(叶子结点)复制到堆的后半部分,堆的前半部分置0
memcpy(heap + num, weights, sizeof(unsigned long)*num);
memset((char *)heap, 0, num * sizeof (*heap));
// 将堆的前半部分视作指针,按顺序指向后半部分的叶子结点
// 同时统计权值非0的叶子结点数目
for (nonzero_count = i = 0; i < num; i++)
if (heap[num + i])
heap[nonzero_count++] = num + i;
/* 将堆的前半部分视作指针,按照指针所指的权值大小,把堆的前半部分组织成为
堆排序(Heap Sort)算法中定义的"堆",即:堆对应一棵完全二叉树，且所有非叶
结点的值均不大于其子女的值，根结点的值是最小的.在这里,根结点是heap[0]
参见数据结构或算法书籍中的堆排序(Heap Sort)算法介绍 */
heap_num = nonzero_count;
for (i = heap_num / 2; i > 0; i--)
{
register int curr, child;
curr = i;
child = curr * 2;
while (child <= heap_num)
{
if (child < heap_num && heap[heap[child]] < heap[heap[child - 1]])
child++;
if (heap[heap[curr - 1]] > heap[heap[child - 1]])
{
register unsigned long temp;
temp = heap[child - 1];
heap[child - 1] = heap[curr - 1];
heap[curr - 1] = temp;
curr = child;
child = 2 * curr;
}
else
break;
}
}
/* 创建Huffman树
这里,创建Huffman树的过程利用了堆排序(Heap Sort)算法的基本原理,即根结点是
最小的元素,树中最后一个元素是最大的元素.选出根结点后,把最后的元素调到根
结点,从树根到树叶,让最后的元素移动到合适的位置,重新建成堆.这样,总是可以
找出2个最小的子树,将这两个子树合并后,再作为新元素放到堆中.所有子树都合并
后,Huffman树就建成了.(参见数据结构或算法书籍中的堆排序算法介绍)
这一段代码的运行结果是整个heap数组成了一棵Huffman树,heap[0]未用,树根是
heap[1],其中保存所有权值值的总和, heap[2]..heap[num-1]对应于所有根以外
的分支结点,其中保存的是双亲结点的索引值, heap[num]..heap[num*2-1]对应于所
有叶子结点(即所有要编码的元素),其中保存的是双亲结点的索引值 */
/* 当用于堆排序的二叉树中还有结点时循环 */
while (heap_num > 1)
{
int pos[2];
/* 循环2次,找出2个最小的子树,存入pos中 */
for (i = 0; i < 2; i++)
{
register int curr, child;
/* 根结点就是最小的结点 */
pos[i] = heap[0];
/* 将最后的结点移动到根结点处,总结点数目减1 */
heap[0] = heap[--heap_num];
/* 以下是重建堆的过程 */
curr = 1;
child = 2;
while (child <= heap_num)
{
if (child < heap_num &&
heap[heap[child]] < heap[heap[child - 1]])
child++;
if (heap[heap[curr - 1]] > heap[heap[child - 1]])
{
register int temp;
temp = heap[child - 1];
heap[child - 1] = heap[curr - 1];
heap[curr - 1] = temp;
curr = child;
child = 2 * curr;
}
else
break;
}
}
/* 合并子树,其结果作为新的结点放入堆中(但不在堆排序的二叉树内,实际
上,新加入的结点是和堆的后半段一起构成了Huffman树) */
heap[heap_num + 1] = heap[pos[0]] + heap[pos[1]];
/* 子树的左,右分支都指向子树的根结点 */
heap[pos[0]] = heap[pos[1]] = heap_num + 1;
/* 把子树根结点作为叶子结点，放到堆排序中的二叉树内 */
heap[heap_num] = heap_num + 1;
{
/* 在堆中,让新加入的叶子结点上升到合适的位置,不破坏堆的秩序 */
register int parent, curr;
heap_num++;
curr = heap_num;
parent = curr >> 1;
while (parent && heap[heap[parent - 1]] > heap[heap[curr - 1]])
{
register int temp;
temp = heap[parent - 1];
heap[parent - 1] = heap[curr - 1];
heap[curr - 1] = temp;
curr = parent;
parent = curr >> 1;
}
}
}
// 从根出发，求每个编码的码长
code_lens.clear();
heap[0] = (unsigned long)(-1l); // 双亲结点为0的叶子，可由此算得码长0
heap[1] = 0; // 根结点码长为0
for (i = 2; i < 2*num; i++)
heap[i] = heap[heap[i]] + 1; // 结点码长等于双亲结点码长加1
for (i = num; i < 2*num; i++)
code_lens.push_back(heap[i]);
// 由码长得到canonical huffman编码
generate_canonical_codes();
delete[] heap;
}
generate_codes()为主函数