❶ 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()為主函數