哈夫曼編解碼論文

1. 哈夫曼編碼原理

赫夫曼碼的碼字（各符號的代碼）是異前置碼字，即任一碼字不會是另一碼字的前面部分，這使各碼字可以連在一起傳送，中間不需另加隔離符號，只要傳送時不出錯，收端仍可分離各個碼字，不致混淆。

哈夫曼編碼，又稱霍夫曼編碼，是一種編碼方式，哈夫曼編碼是可變字長編碼(VLC)的一種。Huffman於1952年提出一種編碼方法，該方法完全依據字元出現概率來構造異字頭的平均長度最短的碼字，有時稱之為最佳編碼，一般就叫做Huffman編碼。

(1)哈夫曼編譯碼論文擴展閱讀

赫夫曼編碼的具體方法：先按出現的概率大小排隊，把兩個最小的概率相加，作為新的概率
和剩餘的概率重新排隊，再把最小的兩個概率相加，再重新排隊，直到最後變成1。

每次相
加時都將「0」和「1」賦與相加的兩個概率，讀出時由該符號開始一直走到最後的「1」，
將路線上所遇到的「0」和「1」按最低位到最高位的順序排好，就是該符號的赫夫曼編碼。

例如a7從左至右，由U至U″″，其碼字為1000；

a6按路線將所遇到的「0」和「1」按最低位到最高位的順序排好，其碼字為1001…

用赫夫曼編碼所得的平均比特率為：Σ碼長×出現概率

上例為：0.2×2+0.19×2+0.18×3+0.17×3+0.15×3+0.1×4+0.01×4=2.72 bit

可以算出本例的信源熵為2.61bit，二者已經是很接近了。

2. 哈夫曼編碼

/* algo6-1.c 求哈夫纖搏顫曼編碼。實現演算法6.12的程序 */
//------------------- 公用的常量和類型 ----------------------------
#include<stdio.h>
#include <malloc.h>
#include <銀茄stdlib.h>
#include <string.h>
//函數結果狀態代碼
#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define INFEASIBLE -1
#define OVERFLOW -2
#define UINT_MAX 1000
typedef int Status;

/* c6-7.h 哈夫曼樹和哈夫曼編碼的存儲表示 */
typedef struct HTNode
{
char leaf;
unsigned int weight;
unsigned int parent,lchild,rchild;
}HTNode,*HuffmanTree; /* 動態分配數組存儲哈夫曼編碼表 */

typedef char **HuffmanCode; /* 動態分配數組存儲哈夫曼編碼表 */
typedef struct Node
{
char leaf;
unsigned int weight;
struct Node * next;
}LeafNode,*LeafLink;

typedef struct
{
LeafLink head;
unsigned len;
}LeafLinkList;

int min1(HuffmanTree t,int i)
{ /* 函數void select()調用 */
int j,flag;
unsigned int k=UINT_MAX; /* 取k為毀敗不小於可能的值 */
for(j=1;j<=i;j++)
if(t[j].weight<k&&t[j].parent==0)
k=t[j].weight,flag=j;
t[flag].parent=1;
return flag;
}

void select(HuffmanTree t,int i,int *s1,int *s2)
{ /* s1為最小的兩個值中序號小的那個 */
int j;
*s1=min1(t,i);
*s2=min1(t,i);
if(*s1>*s2)
{
j=*s1;
*s1=*s2;
*s2=j;
}
}

void HuffmanCoding(HuffmanTree &HT,HuffmanCode &HC, LeafLinkList L) /* 演算法6.12 */
{ /* w存放n個字元的權值(權值均需大於0),構造哈夫曼樹HT,並求出n個字元的哈夫曼編碼HC*/
int m,i,s1,s2,start;
int n=L.len;
unsigned c,f;
LeafLink ptr;
HuffmanTree p;
char *cd;
if(n<=1)
return;
m=2*n-1;
printf("表長為%d\t哈夫曼樹含節點數為%d\n",n,m);
HT=(HuffmanTree)malloc((m+1)*sizeof(HTNode)); /* 0號單元未用 */
ptr=L.head->next;
for(p=HT+1,i=1;i<=n;++i,++p,ptr=ptr->next)
{
(*p).leaf=ptr->leaf;
printf("%d\t",(*p).leaf);
(*p).weight=ptr->weight;
printf("%d\n",(*p).weight);
(*p).parent=0;
(*p).lchild=0;
(*p).rchild=0;
}
for(;i<=m;++i,++p)
{
(*p).parent=0;
(*p).leaf=0;
}
for(i=n+1;i<=m;++i) /* 建哈夫曼樹 */
{ /* 在HT[1~i-1]中選擇parent為0且weight最小的兩個結點,其序號分別為s1和s2 */
select(HT,i-1,&s1,&s2);
HT[s1].parent=HT[s2].parent=i;
HT[i].lchild=s1;
HT[i].rchild=s2;
HT[i].weight=HT[s1].weight+HT[s2].weight;
}
/* 從葉子到根逆向求每個字元的哈夫曼編碼 */
HC=(HuffmanCode)malloc((n+1)*sizeof(char*));
/* 分配n個字元編碼的頭指針向量([0]不用) */
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';
else
cd[--start]='1';
HC[i]=(char*)malloc((n-start)*sizeof(char));
/* 為第i個字元編碼分配空間 */
strcpy(HC[i],&cd[start]); /* 從cd復制編碼(串)到HC */
}
free(cd); /* 釋放工作空間 */
for(i=1;i<=n;i++)
{
printf("%c編碼為%s:\n",HT[i].leaf,HC[i]);
}
}

void InitLeafList(LeafLinkList &L)
{
L.head=(LeafLink)malloc(sizeof(LeafLink));
L.head->next=NULL;
L.len=0;
}
void PrintList(LeafLinkList L)
{
LeafLink p;
p=L.head->next;
printf("列印鏈表\n");
printf("表長為%d\n",L.len);
while(p!=NULL)
{
printf("%c or %d,%u\t",p->leaf,p->leaf,p->weight);
printf("列印一個節點\n");
p=p->next;
}
printf("列印結束\n");
printf("\n");
}

void EnLeafList(LeafLinkList &L,char ch)
{
LeafLink p,pre,temp;
int flag=0;
pre=p=L.head;
printf("%d即為%c******\n\n",ch,ch);
if(p->next==NULL) //p->next=NULL則為第一次插入操作
{
printf("第一次插入\n");
temp=(LeafLink)malloc(sizeof(LeafNode));
temp->leaf=ch;
temp->weight=1;
temp->next=NULL;
p->next=temp;
L.len++;
}

else
{

p=p->next;
while(p!=NULL)
{

if(ch==p->leaf)
{
p->weight++;
printf("加權\n");
p=NULL;
flag=1;
} //權重加一
else if(ch<p->leaf) //插入
{
printf("插入A\n");
temp=(LeafLink)malloc(sizeof(LeafNode));
temp->leaf=ch;
temp->weight=1;
temp->next=p;
pre->next=temp;
L.len++;
flag=1;
p=NULL;
}
else //繼續尋找插入點
{
pre=p;
p=p->next;
}
}

if(p==NULL&&flag!=1) //若p=NULL則插到鏈尾
{
printf("插入B\n");
temp=(LeafLink)malloc(sizeof(LeafNode));
temp->leaf=ch;
temp->weight=1;
temp->next=NULL;
pre->next=temp;
L.len++;
}
}

}
void EnCoding()
{
FILE *fp,*fr,*fc;
HuffmanTree HT;
HuffmanCode HC;
int i,n;
LeafLinkList L;
InitLeafList(L);
char filename[15];
char ch;
printf("請輸入文件名:\n ");
scanf("%s",filename);
if( !(fp=fopen(filename,"r")) )
{
printf("打開文件失敗，請輸入正確的文件名!! ");
exit(0);
}
ch=getchar(); //接收執行scanf語句時最後輸入的回車符
printf("文件已經打開\n");
while(!feof(fp))
{

ch=fgetc(fp);
if(ch==-1)
{
printf("結束統計\n");
}
else
{
EnLeafList(L,ch);
}
}
PrintList(L);
HuffmanCoding(HT,HC, L);
n=L.len;
for(i=1;i<=n;i++)
{
puts(HC[i]);
}
char TreeName[15];
printf("把哈夫曼樹存入文件，請輸入文件名:\n ");
scanf("%s",TreeName);
if( !(fr=fopen(TreeName,"wb")) )
{
printf("打開文件失敗，請輸入正確的文件名!! ");
exit(0);
}
ch=getchar(); //接收執行scanf語句時最後輸入的回車符
printf("文件已經打開\n");
//把哈夫曼樹存入文件
printf("%d\n",n);
printf("把樹的長度先存入\n");
putw(n,fr); //把樹的長度先存入
for(i=1;i<=2*n-1;i++)
if(fwrite(&HT[i],sizeof(struct HTNode),1,fr)!=1)
printf("文件寫入出錯\n");
fclose(fr);

printf("列印原來的樹\n");
for(i=1;i<=2*n-1;i++)
printf("%c %u %u %u %u\n",HT[i].leaf ,HT[i].weight,HT[i].parent,HT[i].lchild,HT[i].rchild );
fclose(fr);

printf("把編碼結果存入文件，請輸入文件名:\n ");
char CodeFileName[15];
scanf("%s",CodeFileName);
if( !(fc=fopen(CodeFileName,"wb")) )
{
printf("打開文件失敗，請輸入正確的文件名!! ");
exit(0);
}
ch=getchar(); //接收執行scanf語句時最後輸入的回車符

printf("待編碼的文件位置指針重新指向開始位置\n");
printf("對待編碼文件進行編碼，編碼同步顯示，並將結果存入指定的文件\n");
rewind(fp);
while(!feof(fp))
{

ch=fgetc(fp);
printf("%c\n",ch);
if(ch==-1)
{
printf("結束編碼\n");
}
else
{
for(int tap=0,i=1;tap==0&&i<=n;) //查找，該葉子對應的編碼串
{
if(ch==HT[i].leaf) //找到，列印出對應的編碼，並存入文件
{
printf("%s\n",HC[i]);
fputs(HC[i],fc); //將編碼字元串存入文件

tap=1;
}
else
{
i++;
}
}
}
}
fclose(fp); //關閉文件
fclose(fc); //關閉文件
}
int decode(FILE *fc,HuffmanTree HT,int n)
{
while(!feof(fc))
{
char ch=fgetc(fc);
if(ch=='0')
{
n=HT[n].lchild;
if(HT[n].leaf!=0)
{
printf("%c",HT[n].leaf);
return OK;
}
else
{
decode(fc,HT,n);
return OK;
}
}
else if(ch=='1')
{

n=HT[n].rchild;
if(HT[n].leaf!=0)
{
printf("%c",HT[n].leaf);
return OK;
}
else
{
decode(fc,HT,n);
return OK;
}
}
else return OK;
}
return ERROR;
}

void Decoding() //解碼文件，並將結果顯示出來
{
FILE *fc,*fr;
char CodeFileName[15],ch,TreeName[15];
int i;
printf("解碼文件，請輸入文件名(如*.dat):\n ");
scanf("%s",CodeFileName);
if( !(fc=fopen(CodeFileName,"r")) )
{
printf("打開文件失敗，請輸入正確的文件名!! ");
exit(0);
}
ch=getchar(); //接收執行scanf語句時最後輸入的回車符
printf("存放編碼結果文件已經打開\n");

//讀入哈夫曼樹

HuffmanTree HT;
printf("取出對應的哈夫曼樹文件，請輸入文件名,\n");
scanf("%s",TreeName);
if( !(fr=fopen(TreeName,"rb")) ) //打開存放哈夫曼樹的文件
{
printf("打開文件失敗，請輸入正確的文件名!! ");
exit(0);
}
int n=getw(fr); //將葉子數目取出
printf("葉子數目%d\n",n);
HT=(HuffmanTree)malloc((2*n)*sizeof(HTNode)); /* 然後分配空間，0號單元未用 */

for(i=1;i<=2*n-1;i++)
if(fread(&HT[i],sizeof(struct HTNode),1,fr)!=1)
printf("文件讀出出錯\n");
int length=2*n-1; //總長度
printf("總結點數目為：%d\n",n);
printf("該文件解碼後得到的源文件為：\n");
printf("**************************************\n");
while(!feof(fc))
{
decode(fc,HT,length);
}
printf("**************************************\n");
printf("\n\n");
}

int PreOrderPrint(HuffmanTree HT,int n,int count)
{
if(HT[n].lchild)
{
for(int i=0;i<count;i++)
printf(" ");
printf("%u\n",HT[n].weight);
if( PreOrderPrint(HT,HT[n].lchild, ++count) )
if (PreOrderPrint(HT,HT[n].rchild, ++count))
return OK;
return ERROR;
}
else return OK;
}
void PrintTree()
{
//讀入哈夫曼樹
FILE *fr;
char TreeName[15];
HuffmanTree HT;
printf("取出對應的哈夫曼樹文件(如*.dat)，請輸入文件名,\n");
scanf("%s",TreeName);
if( !(fr=fopen(TreeName,"rb")) ) //打開存放哈夫曼樹的文件
{
printf("打開文件失敗，請輸入正確的文件名!! ");
exit(0);
}
int n=getw(fr); //將葉子數目取出
printf("含葉子數%d\n",n);
HT=(HuffmanTree)malloc((2*n)*sizeof(HTNode)); /* 然後分配空間，0號單元未用 */

for(int i=1;i<=2*n-1;i++)
if(fread(&HT[i],sizeof(struct HTNode),1,fr)!=1)
printf("文件讀出出錯\n");
int count=0;
n=2*n-1;
printf("總結點數目為；%d\n",n);
printf("哈夫曼樹的存儲形式為：\n");
for(i=1;i<=n;i++)
{
printf("%c,%u,%u,%u,%u\n",HT[i].leaf,HT[i].weight,HT[i].parent,HT[i].lchild,HT[i].rchild);
}
printf("哈夫曼樹的凹入表形式為：\n");
PreOrderPrint(HT,n,count);
}
void PrintCodeFile()
{
FILE *fc;
printf("列印編碼後的文件，請輸入文件名(如*.dat):\n ");
char CodeFileName[15];
scanf("%s",CodeFileName);

if( !(fc=fopen(CodeFileName,"r")) )
{
printf("打開文件失敗，請輸入正確的文件名!! ");
exit(0);
}

char ch=getchar(); //接收執行scanf語句時最後輸入的回車符
printf("列印編碼後的文件，列印方法一\n");
int flag=1;
while(!feof(fc))
{

ch=fgetc(fc);
if(ch==-1)
{
printf("結束列印\n");
}
else
{
printf("%c",ch);
if(flag<=49)
flag++;
else
{
flag=1;
printf("\n");
}
}
}
printf("列印編碼後的文件，列印方法二\n");
rewind(fc);
char str[50];
while(!feof(fc))
{
fgets(str,51,fc);
puts(str);
}
fclose(fc); //關閉文件
}

void Initialization() //系統初始化
{
printf("**************************************\n");
printf("*編碼文件請輸入e\n*解碼文件請輸入d\n*列印編碼後的文件請輸入p\n*列印哈夫曼樹請輸入t\n*結束請輸入q \n");
printf("**************************************\n");
printf("\n\n\t\t字元:\n\n\n");
printf("**************************************\n");
printf("* 輸入一個字元:e,d,p,t or q *\n");
printf("**************************************\n");
}

int read(char cmd)
{
int i,flag=0;
char choice[10]={'e','E','d','D','p','P','T','t','Q','q'};
for(i=0;i<10;i++)
{
if(cmd==choice[i]) flag++;
}
if(flag==1) return FALSE;
else return TRUE;
}
void ReadCommand(char &cmd) // 讀入操作命令符
{
do
{
cmd=getchar();
}
while(read(cmd));
}
void Interpret(char cmd) //解釋執行操作命令
{
switch(cmd)
{
case 'e':case'E':
EnCoding();
Initialization();
break;
case 'd':case'D':
Decoding();
Initialization();
break;
case 'p':case'P':
PrintCodeFile();
Initialization();
break;
case't':case'T':
PrintTree(); // Print();
Initialization();
break;
case 'q': case'Q': exit(0);
break;
default: printf("Error\n");break;
}
}
void main() //用戶驅式
{
char cmd;
Initialization(); //初始化
do
{
ReadCommand(cmd); //讀入一個操作命令符
Interpret(cmd); //解釋執行操作命令符
}
while(cmd!='q'&&cmd!='Q');
EnCoding();
Decoding();

}

3. 哈夫曼編碼/解碼器

注釋非常詳細，希望對你有所幫助！
#ifndef Huffman_Tree_h
#define Huffman_Tree_h
#endif

#include <stdio.h>

typedef struct {
unsigned int weight;
unsigned int parent,lchild,rchild;
}HTNode, * HuffmanTree; //存儲赫夫曼樹的結點類型

typedef char * * HuffmanCode; //用於存儲字元集中各個字元相應的赫夫曼編碼

void strcpy(char *S1,char *S2){ //將字元串S2復制到S1
int i = 0;
while( S2[i] != '\0' ){
S1[i] = S2[i];
i++;
}
S1[i] = '\0';
}

void Select(HuffmanTree HT,int t,int &s1,int &s2){ //在HT[1]到HT[t-1]中找出權值最小的兩個S1和S2
int i = 1;
s1 = s2 = 0;
HT[0].weight = 65535;
while( i <= t ){ //遍歷查找權值最小的結點S1
if( HT[i].parent == 0 && HT[i].weight < HT[s1].weight )
s1 = i;
i++;
}
i = 1;
while( i <= t ){ //遍歷查找除S1外權值最小的結點S2
if( i != s1 && HT[i].parent == 0 && HT[i].weight < HT[s2].weight )
s2 = i;
i++;
}
}

int HuffmanCoding( HuffmanTree &HT,HuffmanCode &HC,int *w,int n){ //根據各個字元的權值構造赫夫曼樹HT，將對應的赫夫曼編碼存儲在HC中
int s1,s2,m,i,start;
unsigned int c,f;
HTNode * p;
char *cd;
if( n <= 1 ) return 0;
m = 2 * n - 1; //赫夫曼樹的總結點樹為m
HT = (HuffmanTree)malloc((m + 1) * sizeof(HTNode)); //申請存儲赫夫曼樹的空間
for(p = HT + 1, i = 1; i <= n; ++i, ++p, ++w){ //將各個葉子結點的weight賦以相應的權值，parent,lchild,rchild均賦為0
p->weight = *(w+1);
p->parent = p->lchild = p->rchild = 0;
}
for( ; i <= m; ++i, ++p ){ //將各個非葉子結點的weight,parent,lchild,rchild均賦為0
p->weight = p->parent = p->lchild = p->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].weight = HT[s1].weight + HT[s2].weight;
}
HC = (HuffmanCode)malloc((n + 1) * sizeof(char *)); //申請空間，用於存儲指向存儲各個字元相應赫夫曼編碼的字元數組的指針
cd = (char *)malloc(n * sizeof(char)); //申請用於求赫夫曼編碼
cd[n - 1] = '\0'; //編碼結束符
for( i = 1; i <= n; ++i){ //逐個字元求赫夫曼編碼
start = n -1; //編碼在數組cd[]中的最前位置
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((n - start)*sizeof(char)); //為第i個字元編碼分配空間
strcpy(HC[i], &cd[start]); //將cd[]數組的start位置到n-1位置復制給HC[i]
}
free(cd); //釋放空間
return 1;
}
以上為第一部分

#include <stdio.h>
#include <stdlib.h>
#include "Huffman_Tree.h"
#define Yes 1 //當程序已經調用過初始化赫夫曼樹的InitHuff_T()函數，或已從htfTree文件讀取過，則將Init_Mode置為Yes，否則為No
#define No 0

void InitHuff_T( HuffmanTree &HT, HuffmanCode &HC, char ch[],int &n ){ //初始化赫夫曼數，要求用戶輸入字元和相應權值
int i = 1,w[100],tem,j;
char a[20];
FILE *save;
printf("請輸入編碼字元集的大小n:");
scanf("%d",&n); //獲取用戶輸入的字元集個數
while( i <= n ){ //獲取用戶輸入的字元和相應權值，分別存儲在ch[]和w[]數組中
printf("請輸入第%d個字元和該字元的權值w:",i);
fflush(stdin);
scanf("%c%d",&ch[i],&w[i]);
i++;
}
ch[i] = '\0';
HuffmanCoding(HT,HC,w,n); //根據用戶的輸入，生成赫夫曼數及各個字元相應的赫夫曼編碼，分別存在HT樹和HC中
if(( save = fopen("htfTree","w")) == NULL ){ //打開用於存儲赫夫曼樹的文件
printf("Open file fail......\n");
exit(0);
}
tem = n; //接下來的14行是將字元集大小轉換成字元形式寫入到文件中
j = 0;
while( tem != 0 ){
tem = tem / 10;
j++;
}
tem = n;
a[j] = '\0';
while( tem != 0 ){
a[j - 1] = (char)(tem % 10 + 48);
tem = tem / 10;
j--;
}
fputs(a,save);
printf("%d\n",n); //向屏幕輸出字元集大小n
fputc('\n',save);
for( i = 1; i <= n; i++ ){ //分別向文件和屏幕輸出各個字元和相應的赫夫曼編碼
fputc(ch[i],save); printf("%c\t",ch[i]);
fputc('\t',save);
fputs(HC[i],save); printf("%s\n",HC[i]);
fputc('\n',save);
}
for(i = 1; i <= 2 * n - 1; i++ ){ //將赫夫曼樹各個結點的parent,lchild,rchild分別寫入到文件中
tem = HT[i].parent; //將i結點的parent轉換成字元並寫入到文件中
if(tem == 0){
fputc(tem + 48,save);
fputc(' ',save);
}
else{
j = 0;
while( tem != 0 ){
tem = tem / 10;
j++;
}
tem = HT[i].parent;
a[j] = '\0';
while( tem != 0 ){
a[j - 1] = (char)(tem % 10 + 48);
tem = tem / 10;
j--;
}
fputs(a,save);
fputc(' ',save);
}

tem = HT[i].lchild; //將i結點的lchild轉換成字元並寫入到文件中
if(tem == 0){
fputc(tem + 48,save);
fputc(' ',save);
}
else{
j = 0;
while( tem != 0 ){
tem = tem / 10;
j++;
}
tem = HT[i].lchild;
a[j] = '\0';
while( tem != 0 ){
a[j - 1] = (char)(tem % 10 + 48);
tem = tem / 10;
j--;
}
fputs(a,save);
fputc(' ',save);
}

tem = HT[i].rchild; //將i結點的rchild轉換成字元並寫入到文件中
if(tem == 0){
fputc(tem + 48,save);
fputc('\n',save);
}
else{
j = 0;
while( tem != 0 ){
tem = tem / 10;
j++;
}
tem = HT[i].rchild;
a[j] = '\0';
while( tem != 0 ){
a[j - 1] = (char)(tem % 10 + 48);
tem = tem / 10;
j--;
}
fputs(a,save);
fputc('\n',save);
}
}
fclose(save);
}

void Encoding(HuffmanTree &HT, HuffmanCode &HC, char ch[]){ //根據赫夫曼編碼將用戶指定的文件中的字元編成相應的編碼,並將所得編碼存儲到用戶指定文件
FILE *ToBeTran,*CodeFile;
char ToBeTran_Name[100],CodeFile_Name[100]; //存儲用戶指定文件的文件名
int i;
char c;
printf("請輸入所要進行編碼的文件的文件名:");
scanf("%s",ToBeTran_Name); //獲得所要進行編碼的文件的文件名
if(( ToBeTran = fopen(ToBeTran_Name,"r")) == NULL ){ //打開文件
printf("Open file fail......\n");
exit(0);
}
printf("請輸入編碼後編碼表示的信息所存儲到的文件的文件名:");
scanf("%s",CodeFile_Name); //獲得編碼後編碼表示的信息所存儲到的文件的文件名
if(( CodeFile = fopen(CodeFile_Name,"w")) == NULL ){ //打開文件
printf("Open file fail......\n");
exit(0);
}
c = fgetc(ToBeTran); //從文件讀取一個字元
while( c != EOF ){ //對文件中的各個字元進行編碼，直至文件結尾
i = 1;
while( c != ch[i] && ch[i] != '\0' ) //在ch[]數組中查找從文件讀取的字元
i++;
if(ch[i] == '\0'){ //未找到，c不在ch[]數組中，c無法被識別，程序出錯，退出
printf("字元%c無法識別，程序將退出。\n",c);
exit(0);
}
fputs(HC[i],CodeFile); //若找到，則將c相應的赫夫曼編碼寫入到文件中
printf("%s",HC[i]); //將c相應的赫夫曼編碼輸出到屏幕
c = fgetc(ToBeTran); //讀入文件中的下一個字元
}
printf("\n");
fclose(ToBeTran);
fclose(CodeFile);
}

void Decoding(HuffmanTree HT, char ch[] , int n){ //對指定的存儲由赫夫曼編碼表示的信息的文件進行解碼，翻譯成相應的字元表示，並存儲到指定文件
int p,i = 1;
char code[1000],c;
char CodeFile_Name[100],TextFile_Name[100]; //存儲用戶指定文件的文件名
p = 2 * n - 1;
FILE *CodeFile,*TextFile;
printf("請輸入所要譯的文件名:");
scanf("%s",CodeFile_Name); //獲得所要譯的文件的文件名
if(( CodeFile = fopen("CodeFile","r")) == NULL ){ //打開文件
printf("Open file fail......\n");
exit(0);
}
printf("請輸入譯後的字元存儲到的文件的文件名:");
scanf("%s",TextFile_Name); //獲得譯後的字元存儲到的文件的文件名
if(( TextFile = fopen(TextFile_Name,"w")) == NULL ){ //打開文件
printf("Open file fail......\n");
exit(0);
}
c = fgetc(CodeFile);
while( c != EOF ){
code[i] = c;
i++;
c = fgetc(CodeFile);
}
code[i] = '\0'; //從文件讀取字元，存儲在code[]數組中
i = 1;
while ( code[i] != '\0' && p != 0 ){ //對數組code[]中的赫夫曼編碼進行解碼
if ( code[i] == '0' )
p=HT[p].lchild; //進入左分支
else
p = HT[p].rchild; //進入右分支
if (!HT[p].lchild&& !HT[p].rchild){ //進入葉子結點
fputc(ch[p], TextFile); //將相應的字元寫入到文件中
printf("%c",ch[p]); //將相應的字元輸出到屏幕
p = 2 * n - 1; //重新從樹根出發進行解碼
}
i++;
}
printf("\n");
}

void ReadHuff_T( HuffmanTree &HT, HuffmanCode &HC, char ch[], int &n){ //從文件讀取赫夫曼樹
FILE *htfTree;
char c[100],ch1;
int i,j,t;
if(( htfTree = fopen("htfTree","r")) == NULL ){ //打開存有赫夫曼樹信息的文件
printf("Open file fail......\n");
exit(0);
}
fgets(c,10,htfTree); //獲取赫夫曼樹葉子結點個數的字元串表示形式
i = 0; //以下6行將字元串形式轉換成整數形式
while( c[i] != '\n' )
i++;
n = 0;
for( j = 0; j < i; j++ )
n = 10 * n + c[j] - '0'; //求出葉子結點數n
HC = (HuffmanCode)malloc((n + 1) * sizeof(char *)); //申請HC空間
HT = (HuffmanTree)malloc((2 * n) * sizeof(HTNode)); //申請赫夫曼樹存儲空間
i = 1;
while( i <= n ){
ch[i] = fgetc(htfTree); //讀取字元集中的一個字元
HC[i] = (char *)malloc((10)*sizeof(char)); //申請用於存儲讀取到的字元集中的字元的赫夫曼編碼的空間
fgetc(htfTree); //將『\t』輸出
ch1 = fgetc(htfTree); //讀取赫夫曼編碼，存儲在相應的HC[i][]數組里
int j = 0;
while( ch1 != '\n' ){
HC[i][j] = ch1;
j++;
ch1 = fgetc(htfTree);
}
HC[i][j] = '\0';
i++;
}
ch[i] = '\0';
i = 0;
while( i < 2 * n - 1 ){ //讀取赫夫曼樹的各個結點的parent,lchild,rchild.並賦值到赫夫曼樹HT中
ch1 = fgetc(htfTree); //讀取parent的字元串形式,存儲在c[]中，並將其轉換成整數形式，賦給HT[i].parent
j = 0;
while( ch1 != ' ' ){
c[j] = ch1;
j++;
ch1 = fgetc(htfTree);
}
HT[i+1].parent = 0;
for( t = 0; t < j; t++ )
HT[i+1].parent = 10 * HT[i+1].parent + c[t] - '0';
ch1 = fgetc(htfTree); //讀取lchild的字元串形式，並將其轉換成整數形式，賦給HT[i].lchild
j = 0;
while( ch1 != ' ' ){
c[j] = ch1;
j++;
ch1 = fgetc(htfTree);
}
HT[i+1].lchild = 0;
for( t = 0; t < j; t++ )
HT[i+1].lchild = 10 * HT[i+1].lchild + c[t] - '0';
ch1 = fgetc(htfTree); //讀取rchild的字元串形式，並將其轉換成整數形式，賦給HT[i].rchild
j = 0;
while( ch1 != '\n' ){
c[j] = ch1;
j++;
ch1 = fgetc(htfTree);
}
HT[i+1].rchild = 0;
for( t = 0; t < j; t++ )
HT[i+1].rchild = 10 * HT[i+1].rchild + c[t] - '0';
i++;
}
}

int main(){
HuffmanTree HT;
HuffmanCode HC;
char ch[100]; //用於存儲字元集
int n,Init_Mode = No; //n為字元集的大小，Init_Mode = No 表示內存中沒有赫夫曼樹的信息
char mode; //讓用戶選擇不同的操作
printf("請輸入你要選擇的功能\n");
printf("\t\tI -- 初始化\t\tE -- 編碼\n");
printf("\t\tD -- 解碼 \t\tQ -- 退出程序\n");
scanf("%c",&mode); //獲得用戶選擇的操作
while( mode != 'Q' && mode != 'q' ){ //當用戶輸入不為Q或q時，執行相應操作
switch(mode){
case 'I' :
InitHuff_T(HT,HC,ch,n);
Init_Mode = Yes;
break;
case 'i' :
InitHuff_T(HT,HC,ch,n);
Init_Mode = Yes;
break;
case 'E' :
if( No == Init_Mode )
ReadHuff_T(HT,HC,ch,n);
Encoding(HT,HC,ch);
Init_Mode = Yes;
break;
case 'e' :
if( No == Init_Mode )
ReadHuff_T(HT,HC,ch,n);
Encoding(HT,HC,ch);
Init_Mode = Yes;
break;
case 'D' :
if( No == Init_Mode )
ReadHuff_T(HT,HC,ch,n);
Decoding(HT,ch,n);
Init_Mode = Yes;
break;
case 'd' :
if( No == Init_Mode )
ReadHuff_T(HT,HC,ch,n);
Decoding(HT,ch,n);
Init_Mode = Yes;
default :
printf("您的輸入有錯，請重新選擇.\n");
}
printf("請輸入你要選擇的功能\n");
printf("\tI -- 初始化\tE -- 編碼\n");
printf("\tD -- 解碼 \tQ -- 退出程序\n");
fflush(stdin);
scanf("%c",&mode); //讓用戶繼續選擇相應的操作，直至用戶選擇退出
}
return 0;
}

4. 哈夫曼編、解碼器

這個是我課程設計弄的，也是哈弗曼編碼解碼器
#include<iostream>
#include<stdlib.h>
#include<string.h>
using namespace std;

typedef struct{
int weight;
int parent,lchild,rchild;
int asc;
}HTNode,*HuffmanTree; //定義赫夫曼存儲結構

struct node{
int ASCII;
int n;
};
struct node a[127];
struct node w[127];
//一些全局變數
int count;
HTNode H_T[250];
char ** HC;
char filename[20];

//函數聲明
void menu1(); //菜單1
HuffmanTree HeapSort(HuffmanTree HT,int length); //堆排序
void MinHeapify(HuffmanTree HT, int k,int len); //調整成一個小頂堆
void buildMinHeap(HuffmanTree HT,int len); //建一個小頂堆
void swap(HTNode &t1,HTNode &t2); //交換兩結構體
void savefile(); //把輸入的英文文章保存到文件
void loadfile(); //從文件中讀取文章
HuffmanTree CreateHuffman(HuffmanTree &HT,struct node *w,int n); //建立赫夫曼數並存入文件
void BianMa(HuffmanTree HT,int n ); //字元編碼
void BianMa_all(HuffmanTree HT,char**HC,char *filename); //整篇文章編碼
int loadfile2(); //從文件讀入文章
void JieMa(); //解碼

//主函數
int main()
{
char s;
while(s!='0')
{
system("cls");
cout<<"\n\n\n";
cout<<"\t\t\t\t赫夫曼編碼/解碼器"<<endl<<endl<<endl<<endl<<endl;
cout<<"\t\t\t\t 1.編碼"<<endl<<endl<<endl<<endl;
cout<<"\t\t\t\t 2.解碼"<<endl<<endl<<endl<<endl;
cout<<"\t\t\t\t 0.退出"<<endl<<endl<<endl<<endl;
cout<<"\t請輸入0—2進行選擇，按回車確認";
cin>>s;
switch(s)
{
case '1': menu1(); break;
case '2':
{
system("cls");
JieMa();
system("pause");
break;
}

}

}
}

//菜單1
void menu1(){
char s;
int i;
int a;
char c;
char fpname[20]="article.txt";
HuffmanTree HT;
while(s!='0'){

system("cls");
cout<<"\n\t\t\t\t編碼界面";
cout<<"\n\n\n\t\t\t\t1.輸入英文文章"<<endl;
cout<<"\n\n\t\t\t\t2.從文件中讀入文章"<<endl;
cout<<"\n\n\t\t\t\t0.返回上一層"<<endl;
cout<<"\n\t請輸入0—2進行選擇，按回車確認";
cin>>s;
switch(s){
case'1':
system("cls");
savefile();
loadfile();
CreateHuffman(HT,w,count);
BianMa(HT,count);
BianMa_all(HT,HC,fpname);
system("cls");
cout<<"出現字元種類共計：";
cout<<count<<endl;
for(i=1;i<=count;i++)
{ a=HT[i].asc;
c=(char)a;

cout<<"________________________________________________________________________________"<<endl;
cout<<"\t\t\t字元：";
cout<<c<<endl;
cout<<"\t\t\tASCII碼：";
cout<<a<<endl;
cout<<"\t\t\t頻數：";
cout<<HT[i].weight<<endl;
cout<<"\t\t\t赫夫曼編碼：";
cout<<HC[i]<<endl;

}
cout<<"________________________________________________________________________________";
cout<<"\n\t\t整篇文章的編碼已存入文件「赫夫曼編碼.txt」"<<endl;

system("pause");
break;

case'2':
system("cls");
if(loadfile2())
{ system("pause");
return;}
CreateHuffman(HT,w,count);
BianMa(HT,count);
BianMa_all(HT,HC,filename);
system("cls");
cout<<"出現字元種類共計：";
cout<<count<<endl;
for(i=1;i<=count;i++)
{ a=HT[i].asc;
c=(char)a;

cout<<"________________________________________________________________________________"<<endl;
cout<<"\t\t\t字元：";
cout<<c<<endl;
cout<<"\t\t\tASCII碼：";
cout<<a<<endl;
cout<<"\t\t\t頻數：";
cout<<HT[i].weight<<endl;
cout<<"\t\t\t赫夫曼編碼：";
cout<<HC[i]<<endl;

}
cout<<"________________________________________________________________________________";
cout<<"\n\t\t整篇文章的編碼已存入文件「赫夫曼編碼.txt」"<<endl;
system("pause");
break;
}

}

}

//交換結構體
void swap(HTNode &t1,HTNode &t2)
{
HTNode m;

m = t1;
t1 = t2;
t2 = m;
}

//從鍵盤輸入文章並保存
void savefile(){

FILE *fp;
char article;
if((fp=fopen("article.txt","w"))==NULL){

printf("打開文件不成功！");
exit(0);
}
cout<<"請輸入英文文章,以#結束:";
getchar();
article=getchar();
while(article!='#'){

fputc(article,fp);

article=getchar();
}
fclose(fp);
}

//從文件讀取文章，並統計字元出現頻數
void loadfile(){

FILE *fp;
char ch;
int i,k,j=0;
count=0;
for(i=0;i<=127;i++) //把所有字元的ascii碼存在數組
{ a[i].ASCII=i;
a[i].n=0;

}
if((fp=fopen("article.txt","r"))==NULL){

printf("打開文件不成功！");
exit(0);
}
ch=fgetc(fp);
k=(int)ch;
a[k].n++;
while(!feof(fp)){
ch=fgetc(fp);
k=(int)ch;
a[k].n++;
}
fclose(fp);

for(i=0;i<=127;i++) //統計字元種類總數
{
ch=(char)i;
if(a[i].n){
count++;
}
}
for(i=0;i<=127;i++)
{
for(;j<count;)
{
if(a[i].n)
{
w[j].n=a[i].n;
w[j].ASCII=a[i].ASCII;
j++;
break;
}
else break;
}
}

}

//調整為小頂堆
void MinHeapify(HuffmanTree HT, int k,int len)
{
int left=k*2;
int right=k*2+1;
int large;
int l=len;

large = k;
if (left<=l&&HT[left].weight<HT[large].weight)
large = left;

if (right<=l&& HT[right].weight<HT[large].weight)
large=right;

if (large!=k)
{
swap(HT[k],HT[large]);
MinHeapify(HT,large,l);
}
}

//建立小頂堆
void buildMinHeap(HuffmanTree HT,int len)
{
int i;
for (i=len/2;i>=1;i--)
{
MinHeapify(HT,i,len);
}
}

//堆排序
HuffmanTree HeapSort(HuffmanTree HT,int length)
{
int i;
int l=length;
buildMinHeap(HT,length);
for (i=length;i>= 2;i--)
{
swap(HT[1],HT[i]);
length--;
MinHeapify(HT,1,length);
}

return HT;
}

//建立赫夫曼數
HuffmanTree CreateHuffman(HuffmanTree &HT,struct node *w,int n)
{
int i,m,s1,s2,k1,k2,j,x,a;
FILE *fp,*fp2;

if(n<=1) return HT;
m=2*n-1;
HT=(HuffmanTree)malloc((m+1)*sizeof(HTNode));//0不用

for(i=1,j=0;i<=n;i++,j++)
{ HT[i].asc=w[j].ASCII;
HT[i].weight=w[j].n;
HT[i].parent=0;
HT[i].lchild=0;
HT[i].rchild=0;
}
for(;i<=m;i++)
{ a=250+i;
HT[i].asc=a;//父親節點的asc可以是大於127的任意值
HT[i].weight=0;
HT[i].parent=0;
HT[i].lchild=0;
HT[i].rchild=0;
}
for(i=1;i<=n;i++){

H_T[i].asc=HT[i].asc;
H_T[i].parent=HT[i].parent;
H_T[i].lchild=HT[i].lchild;
H_T[i].rchild=HT[i].rchild;
H_T[i].weight=HT[i].weight;
}

for(i=n+1,x=n;i<=m;i++,x--)
{

HeapSort(H_T,x);
k1=H_T[x].asc;
k2=H_T[x-1].asc;
for(j=1;j<=127;j++)
{
if(HT[j].asc==k1)

}

for(j=1;j<=127;j++)
{
if(HT[j].asc==k2)

}

HT[s2].parent=i;
HT[s1].parent=i;
HT[i].lchild=s1;
HT[i].rchild=s2;
HT[i].weight=HT[s1].weight+HT[s2].weight;

H_T[x-1].asc=HT[i].asc;
H_T[x-1].lchild=HT[i].lchild;
H_T[x-1].parent=HT[i].parent;
H_T[x-1].rchild=HT[i].rchild;
H_T[x-1].weight=HT[i].weight;

}
if((fp2=fopen("count.txt","w"))==NULL) //保存赫夫曼樹
{
cout<<"文件打開不成功！"<<endl;
exit(0);
}
fputc(count,fp2);
if((fp=fopen("HuffmanTree.dat","wb"))==NULL)
{ cout<<"文件打開不成功！"<<endl;
exit(0);

}

for(i=1;i<=(2*count-1);i++){
fwrite(&HT[i],sizeof(HTNode),1,fp);
}
fclose(fp);
fclose(fp2);
return HT;

}

//逆向編碼
void BianMa(HuffmanTree HT,int n){
char *cd,temp;

int c,f,i,j,len,p,q;

cd=(char *)malloc(n*sizeof(char));
HC=(char * *)malloc(n*sizeof(char*));
for(i=1;i<=n;i++){
for(c=i,f=HT[i].parent,j=0;f!=0;c=f,f=HT[f].parent,j++)
{ if(HT[f].lchild==c) cd[j]='0';
else cd[j]='1';
if(HT[f].parent==0)
cd[j+1]='\0';

}

len=strlen(cd);
for(p=0,q=len-1;p<=q;p++,q--)
{
temp=cd[q];
cd[q]=cd[p];
cd[p]=temp;
}
cd[len]='\0';
HC[i]=(char*)malloc((len+10)*sizeof(char));
strcpy(HC[i],cd);

}

}

//整篇文章編碼，並存入文件
void BianMa_all(HuffmanTree HT,char**HC,char *filename){
char ch;
int k,i;
FILE *fp,*fp2;

char code[100];
if((fp=fopen(filename,"r"))==NULL){

printf("打開文件不成功！");
exit(0);
}
if((fp2=fopen("赫夫曼編碼.txt","w"))==NULL){

printf("打開文件不成功！");
exit(0);
}
ch=fgetc(fp);
k=(int)ch;
while(!feof(fp))
{

for(i=1;i<=count;i++)
{
if(k==HT[i].asc)
strcpy(code,HC[i]);

}
fputs(code,fp2);
ch=fgetc(fp);
k=(int)ch;

}
fclose(fp);
fclose(fp2);

}

void JieMa(){
int i,k,a,t,n=0;
FILE *fp1,*fp2,*fp3;
char ch,c;
HuffmanTree ht;
if((fp3=fopen("count.txt","r"))==NULL) //從文件讀出字元總數
{
printf("打開文件不成功！");
exit(0);
}
n=fgetc(fp3);
ht=(HuffmanTree)malloc(2*n*sizeof(HTNode));
if((fp1=fopen("赫夫曼編碼.txt","r"))==NULL)
{

printf("打開文件不成功！");
exit(0);
}

if((fp2=fopen("HuffmanTree.dat","rb"))==NULL)
{ cout<<"文件打開不成功！"<<endl;
exit(0);

}
for(i=1;i<=2*n-1;i++)

fread(&ht[i],sizeof(HTNode),1,fp2);

for(i=1;i<=2*n-1;i++)
{
if(ht[i].parent==0)
}

ch=fgetc(fp1);
while(!feof(fp1)){
if(ch=='0')
{
k=ht[k].lchild;
if(ht[k].lchild==0)
{a=ht[k].asc;
c=(char)a;
printf("%c",c);;

k=t;
}
}
if(ch=='1')
{
k=ht[k].rchild;
if(ht[k].lchild==0)
{ a=ht[k].asc;
c=(char)a;
printf("%c",c);

k=t;
}

}

ch=fgetc(fp1);
}
fclose(fp1);
fclose(fp2);

}

//讀取文件中的文章，可自己選擇文件
int loadfile2(){

FILE *fp;
char ch;
int i,k,j=0;
count=0;
for(i=0;i<=127;i++)
{ a[i].ASCII=i;
a[i].n=0;

}
cout<<"\n\n\n\t\t\t請輸入你要打開的文件名：";
cin>>filename;
if((fp=fopen(filename,"r"))==NULL){

printf("打開文件不成功！");
return 1;
}
ch=fgetc(fp);
k=(int)ch;
a[k].n++;
while(!feof(fp)){
ch=fgetc(fp);
k=(int)ch;
a[k].n++;
}
fclose(fp);

for(i=0;i<=127;i++){
ch=(char)i;
if(a[i].n){
count++;
}
}
for(i=0;i<=127;i++)
{
for(;j<count;)
{
if(a[i].n)
{
w[j].n=a[i].n;
w[j].ASCII=a[i].ASCII;
j++;
break;
}
else break;
}
}
return 0;
}

5. 哈夫曼編碼和解碼

class HaffmanNode //哈夫曼樹的結點類
{
int weight; //權值老孝
int parent,left,right; //父母結點和左右孩子下標

public HaffmanNode(int weight)
{
this.weight = weight;
this.parent=-1;
this.left=-1;
this.right=-1;
}
public HaffmanNode()
{
this(0);
}
public String toString()
{
return this.weight+", "+this.parent+", "+this.left+", "+this.right;
}
return code;
}

public static void main(String[] args)
{
int[] weight={5,29,7,8,14,23,3,11}; /塵侍/指定權值集合
HaffmanTree htree = new HaffmanTree(weight);
System.out.println("哈夫曼樹的結點數組:\n"+htree.toString());
String[] code = htree.haffmanCode();
System.out.println("哈夫曼編碼:");
for (int i=0; i<code.length; i++)
System.out.println(code[i]);
}
}
希望能解決您的問題。派含吵

6. 哈夫曼編碼與解碼

#include <stdio.h>
#include <string.h>
#include <malloc.h>
#include <stdlib.h>
#include <conio.h>
#define NN 10000
#define M 2*NN-1
#define IN 0
#define OUT 1
#define MAX_INT 32767
#define PRINTLN printf("\n\n\n\n\n\n\n\n");

typedef struct
{
int wi;
char c;
int tag;
int parent, lchild, rchild;
}huffmtype;

typedef char* encodetype[NN+1];

typedef struct
{
char c;
int times;
}codetype;

void PRINT()
{
PRINTLN;
printf("\t\t\t Huffman編/解碼器\n");
printf("\t\t\t ====================\n");
printf("\t\t\t 1.編碼 2.解碼 3.退出\n\n");
printf("\t\t\t >>選擇:");
}

FILE* OpenFile(char filename[20], char type[3])
{
FILE *fp = NULL;

if((fp = fopen(filename, type)) == NULL) exit(1);

return fp;
}

int ReadCode(codetype* code, FILE* fp)
{
char c;//保存某次從文件中讀入字元-
int n = 1;//記錄首次出現字元在數組中的下標-
int i;//循環變數-
int cnt = 1;
int tag;//標志某次讀入字元是否為首次出現字元，tag=1表示是首次出現;tag=0表示本次讀入字元為已有字元

while((c = fgetc(fp)) != EOF)//當文件沒有結束時讀入字元-
{
//從fp指向文件中讀取字元，存入字元變數c中-
tag = 1;//假設本次讀取字元為首次出現字元-
for(i = 1; i < n; i++)
{
if(c == code[i].c)//如果本次讀入字元為存儲在下標為i已有字元-
{
code[i].times++;//權值加1-
tag = 0;//標記本字元為已有字元-
break;//在已有數組元素中找到本次讀入字元，結束for(;;)循環-
}
}

if(tag)//當本字元為首次出現字元時-
{
code[n].c = c;//把改字元存入n指向的數組單元中-
code[n].times = 1;//記字元出現次數為1-
n++;//n指向下一個數組地址-
}
}

return n - 1;//返迴文件中字元集合的元素個數-

}

void InitHuffmanTree(huffmtype* huffmtree, int real_n, int real_m)//初始化-
{
int i;

for(i = real_n; i <= real_m; i++)
{
huffmtree[i].wi = 0;
huffmtree[i].c = 0;
huffmtree[i].tag = IN;
huffmtree[i].lchild = huffmtree[i].rchild = huffmtree[i].parent = 0;
}
}

void ReadDataWeight_Init(huffmtype* huffmtree, codetype* code, int real_n)//獲取權值及數值域值-
{
int i;

for(i = 1; i <= real_n; i++)//-
{
huffmtree[i].wi = code[i].times;
huffmtree[i].c = code[i].c;
huffmtree[i].tag = IN;
huffmtree[i].lchild = huffmtree[i].rchild = huffmtree[i].parent = 0;
}
}

int LeastNode(huffmtype *huffmtree, int max_i)//找到最小權值節點地址-
{
int i;
int least_i;
int max = MAX_INT;

for(i = 1; i <= max_i; i++)//遍歷1到max_i節點-
{
if(huffmtree[i].wi < max && huffmtree[i].tag == IN)//若節點權值比max小並且在森林中-
{
max = huffmtree[i].wi;//刷新max值-
least_i = i;//保存當前節點地址-
}
}

huffmtree[least_i].tag = OUT;//將最小權值節點從森林中移除-

return least_i;//返回最小節點地址
}

void Slect(huffmtype *huffmtree, int max_i, int *x1, int *x2)//找到權值最小的兩個節點，並將其下標值保存在x1，x2中-
{
*x1 = LeastNode(huffmtree, max_i);//計算合法最下權值下標-
*x2 = LeastNode(huffmtree, max_i);//
}

void CreatHuffmanTree(huffmtype* huffmtree, int real_n, int real_m)//創建哈弗曼樹-
{
int i;
int x1, x2;

for(i = real_n + 1; i <= real_m; i++)
{
Slect(huffmtree, i-1, &x1, &x2);//找到權值最小的兩個節點，並將其下標值保存在x1，x2中-
huffmtree[i].wi = huffmtree[x1].wi + huffmtree[x2].wi;//計算雙氣節點權值-
huffmtree[x1].parent = huffmtree[x2].parent = i;//計算雙親節點地址-
huffmtree[i].lchild = x1; huffmtree[i].rchild = x2;//計算雙親節點左右孩子地址-
}
}

void Encode(huffmtype *huffmtree, encodetype encode, int real_n)//依據已創建的HuffmanTree對字元進行編碼-
{

char *cd;

int i;

int start;

int c, p;

cd = (char*)malloc(real_n*sizeof(char));//cd用來存放某次運行時當前字元編碼-

cd[real_n - 1] = '\0';//作為字元結束符-

for(i = 1; i <= real_n; i++)//對real_n個節點進行遍歷-

{

start = real_n-1;

c = i;//c保存當前節點地址（下標）-

p = huffmtree[i].parent;//p保存當前節點雙親地址-

while(p)

{

start--;//計算編碼的起始地址-

if(huffmtree[p].lchild == c)//若當前節點為其雙親的左孩子-

{

cd[start] = '0';//編碼為0-

}

else//若為右孩子-

{

cd[start] = '1';//編碼為1-

}

c = p;//節點前進-

p = huffmtree[p].parent;//計算前進後節點雙親節點地址-

}

encode[i] =(char*)malloc((real_n - start)*sizeof(char));//申請空間用於存放編碼-

strcpy(encode[i], &cd[start]);//將本次編碼存入encode數組中-

}

free(cd);//釋放閑置存儲空間-

}

void WriteToFile(FILE *fp, encodetype encode, codetype *code, int real_n, char *readfile)//將編碼輸出到文件

{

int i;

char cod[NN];

FILE *fp2;

char c;

int cnt = 1, j;

fp2 = fopen(readfile, "rt");

while((c = fgetc(fp2)) != EOF)

{

cod[cnt++] = c;

}

fclose(fp2);

for(i = 1; i < cnt; i++)

{

for(j = 1; j <=real_n; j++)

{

if(cod[i] == code[j].c)

{

break;

}

}

fprintf(fp, "%s", encode[j]);

}

fclose(fp);

}

int IsError(FILE *fp)//對打開文件進行出錯判斷-

{

if(!fp)

{

printf("\t\t\t ×打開文件錯誤\n");

printf("\t\t\t 任意鍵返回主菜單");

getch();

return 1;//文件打開失敗-

}

return 0;//文件打開成功-

}

void GetFilename(char *filename, char type[13])//得到用戶輸入相關文件名

{

system("cls");

PRINTLN;

printf("\t\t\t %s:", type);

fflush(stdin);

gets(filename);

}

int PutIntoCode(codetype code[], huffmtype huffmtree[])//編碼函數

{

encodetype encode;

FILE* fp;//文件類型指針-

int real_n;//用來存放字元集長度-

char readfile[20];//從readfile文件中讀取字元，寫入到writefile文件中-

GetFilename(readfile, "讀取源文件");//從鍵盤讀取文件名-

fp=OpenFile(readfile, "rt");//打開待編碼文件-

if(IsError(fp))//判斷是否正確打開文件-

{

return 0;//打開文件失敗，返回主菜單-

}

real_n=ReadCode(code, fp);//從readfile文件讀取字元，將字元集合元素存入code數組，將集合元素個數存入real_n-

fclose(fp);//關閉文件-

ReadDataWeight_Init(huffmtree, code, real_n);//初始化HuffmanTree中從1到real_n的元素-

InitHuffmanTree(huffmtree, real_n, 2*real_n-1);//初始化HuffmanTree中real_n到2*real_n的元素-

CreatHuffmanTree(huffmtree, real_n, 2 * real_n - 1);//創建HuffmanTree-

Encode(huffmtree, encode, real_n);//根據HuffmanTree對字元進行編碼，編碼結果保存到encode數組中-

fp = OpenFile("CodeFile.txt", "wb");//打開待寫入文件-

WriteToFile(fp, encode, code, real_n, readfile);//將encode數組中元素寫入到文件中-

fclose(fp);//關閉文件-

printf("\t\t\t 完成編碼並保存至CodeFile.txt文件中");//列印完成編碼信息-

getch();//等待用戶輸入任意鍵返回主菜單-

return real_n;

}

void Translate(codetype code[], huffmtype huffmtree[], int real_n)//解碼函數

{

FILE *fp,*fp2;

int i, real_m;

char c;

char writefile[20];

GetFilename(writefile, "保存解碼文件到");

fp = OpenFile("CodeFile.txt", "rb");

fp2 = OpenFile(writefile, "wt");

if(IsError(fp))

{

return;

}

i = real_m = 2*real_n - 1;

while((c = fgetc(fp)) != EOF)

{

if(c == '0')

{

i = huffmtree[i].lchild;

}

else

{

i = huffmtree[i].rchild;

}

if(huffmtree[i].lchild == 0)
{
fputc(code[i].c, fp2);
i = real_m;
}
}

fclose(fp);
fclose(fp2);
printf("\t\t\t 完成解碼任務");
getch();

}

int main(void)
{
int choice;
int real_n = 0;

codetype code[NN];
huffmtype huffmtree[NN];

while(1)
{
system("cls");
PRINT();

scanf("%d",&choice);
switch(choice)
{
case 1 :
real_n = PutIntoCode(code, huffmtree);
break;//編碼函數
case 2 :
if(real_n) Translate(code, huffmtree, real_n);break;//解碼函數
case 3 :
exit(1);//退出程序
default :
printf("\t\t\t ★無效輸入");
getch();
break;
}
}

return 0;

}

7. 課程設計-哈夫曼編碼/解碼的設計與實現

哈哈~~~南工的同志？？、、、、、、我也不會。

8. 利用 數據結構 實現 哈夫曼編碼/解碼實現

//D:\2010 代碼\haffman\haffman\Node_statement.h
#define MAXVALUE 1000//定義最大權值
#define MAXBIT 100//定義哈夫曼樹中葉子結點個數
typedef struct
{
char data;//字元值
int num;//某個值的字元出現的次數
}TotalNode;
//統計結點，包括字元種類和出現次數
typedef struct
{
TotalNode tot[300];//統計結點數組
int num;//統計數組中含有的字元個數
}Total;
//統計結構體，包括統計數組和字元種類數
typedef struct
{
char mes[300];//字元數組
int num;//總字元數
}Message;
//信息結構體，包括字元數組和總字元數
typedef struct{
int locked[500];//密碼數組
int num;//密碼總數
}Locking;
//哈夫曼編碼後的密文信息
typedef struct
{
char data;//字元
int weight;//權值
int parent;//雙親結點在數組HuffNode[]中的序號
int lchild;//左孩子結點在數組HuffNode[]中的序號
int rchild;//右孩子結點在數組HuffNode[]中的序號
}HNodetype;
//哈夫曼樹結點類型，包括左右孩子，權值和信息
typedef struct
{
int bit[MAXBIT];
int start;
}HCodetype;
//哈夫曼編碼結構體，包括編碼數組和起始位

void reading_file(Message *message);//從文件中讀取信息
int writing_file(Message *message);//將信息寫進文件
void total_message(Message *message,Total *total);//統計信息中各字元的次數
void HaffmanTree(Total *total,HNodetype HuffNode[]);//構建哈夫曼樹
void HaffmanCode(HNodetype HuffNode[],HCodetype HuffCode[],Total *total);//建立哈夫曼編碼
void writing_HCode(HNodetype HuffNode[],HCodetype HuffCode[],Total *total);//將編碼規則寫進文件
void lock(Message *message,HNodetype HuffNode[],HCodetype HuffCode[],Total *total,Locking *locking);//給文件信息加密編碼
void writing_lock(Locking *locking);//將已編碼信息寫進文件
void first_function(HNodetype HuffNode[],HCodetype HuffCode[],Total *total,Message *message);
void display(Total *total,HNodetype HuffNode[]);
void writing_translate(Locking *locking,HCodetype HuffCode[],HNodetype HuffNode[],Total *total);//將已編碼信息翻譯過來並寫進文

//D:\2010 代碼\haffman\haffman\function_mian.cpp
#include"Node_statement.h"
#include<iostream>
#include<fstream>
#include "cstdlib"
using namespace std;
int main()
{
int i,j,choice,mark=0;//mark標記文件信息是否讀入到內存中
HNodetype HuffNode[500];//保存哈夫曼樹中各結點信息
HCodetype HuffCode[300];
Locking *locking;
Total *total;
Message *message;
locking=new Locking;
locking->num=0;
total=new Total;
total->num=0;
message=new Message;
message->num=0;
//初始化變數
printf("┏ ┓\n");
printf("┣ haffman_code system ┫ \n");
printf("┗ ┛\n");
printf("\n\n");
choice=0;
while(choice!=7 )
{

printf("＃〓§〓〓〓〓〓§〓〓〓〓§〓〓〓〓§〓＃ \n ");
printf(" 0:go \n");
printf("※********** 1：從文件讀取信息**********************※\n");
printf(" *********** 2：顯示編碼規則 ********************* \n");
printf(" ********** 3：將原文件信息寫進文件 ************ \n");
printf(" ********* 4：將編碼規則寫進文件 ************ \n");
printf(" ********** 5：將編碼後的信息寫進文件 ********** \n");
printf(" *********** 6：將解碼後的信息寫進文件 *********\n");
printf("※***********7：退出 *****************************※\n");
printf("＃〓§〓〓〓〓〓§〓〓〓〓§〓〓〓〓§〓＃ \n ");
printf(" please input the choice ");
cin>>choice;
switch(choice)
{
case 1:
reading_file(message);//從文件中讀取信息
mark=1;
break;
case 2://顯示編碼規則
if(mark==0)cout<<"請先從文件中讀取信息!"<<endl;
else
{
first_function(HuffNode,HuffCode,total,message);
cout<<"編碼規則為"<<endl;
for(i=0;i<total->num;i++)//顯示編碼規則
{
cout<<total->tot[i].data<<" ";
for(j=HuffCode[i].start+1;j<total->num;j++)
cout<<HuffCode[i].bit[j];
cout<<endl;
}
}
break;
case 3://將原文件信息寫進文件a_test1.txt
if(mark==0)cout<<"請先從文件中讀取信息!"<<endl;
else

writing_file(message);//將信息寫進文件
break;
case 4://將編碼規則寫進文件
if(mark==0)cout<<"請先從文件中讀取信息!"<<endl;
else
{
first_function(HuffNode,HuffCode,total,message);
writing_HCode(HuffNode,HuffCode,total);//將編碼規則寫進文件
}
break;
case 5://將編碼後的信息寫進文件
if(mark==0)cout<<"請先從文件中讀取信息!"<<endl;
else
{
first_function(HuffNode,HuffCode,total,message);
writing_lock(locking);//將已編碼信息寫進文件
}
break;
case 6://將解碼後的信息寫進文件
if(mark==0)cout<<"請先從文件中讀取信息!"<<endl;
else
{
first_function(HuffNode,HuffCode,total,message);
writing_translate(locking,HuffCode,HuffNode,total);//將已編碼信息翻譯過來並寫進文件
}
break;
}
}

/**
列印haffman樹
**/
display(total,HuffNode);
system("PAUSE");
return 0;
}

void display(Total *total,HNodetype HuffNode[])
{
int i,j;
for(i=0;i<2*total->num-1;i++)
{
printf("data weight lchild rchild parent \n");
printf(" %c %d %d %d %d\n",HuffNode[i].data,HuffNode[i].weight,HuffNode[i].lchild,HuffNode[i].rchild,HuffNode[i].parent);
}

}

void reading_file(Message *message)
/**
絕對路徑下讀取a_test.txt file
message 中的num記錄suoyou字元總數 ，放在nes【】中
equal to the buffer
**/
{
int i=0;
char ch;
ifstream infile("a_test.txt",ios::in | ios::out);
if(!infile)//打開失敗則結束
{
cout<<"打開a_test.txt文件失敗"<<endl;
exit(1);
}
else
cout<<"讀取文件成功"<<endl;
while(infile.get(ch) && ch!='#')//讀取字元直到遇到#
{
message->mes[i]=ch;
i++;
}
message->num=i;//記錄總字元數
infile.close();//關閉文件
}

int writing_file(Message *message)
/**
把從數組message 的信息write to disk，a_test1.txt to save
**/
{ /*
int i;
ifstream outfile("a_test1.txt",ios::in ); //打開文件
if( !outfile )//打開失敗則結束
{
cout<<"打開a_test1.txt文件失敗"<<endl;
return -1;
}
for(i=0;i<message->num;i++)//寫文件
outfile.put(message->mes[i]);
cout<<"信息寫進文件成功"<<endl;
outfile.close();//關閉文件
return 0;*/
int i;
FILE *fp1=NULL;

if((fp1 = fopen("a_test1.txt","at"))==NULL)
{
printf("can't open the file\n");
exit(0);
}
for(i=0;i<message->num;i++)
fprintf(fp1,"%d ",message->mes[i]);
printf("文件寫入成功!\n");
i=fclose(fp1);
if(i==0)
printf("文件關閉成功!\n");

else
printf("文件關閉失敗!\n");
}

void total_message(Message *message,Total *total)
/**
統計message中不同字元 的個數，和相同字元重復的次數，重復字元用mark標記，
total.tot[] 放不同字元，TotalNode 類型（char，num）
total.num 統計不同字元個數
使total這塊內存空間有數據，
**/
{
int i,j,mark;
for(i=0;i<message->num;i++)//遍歷message中的所有字元信息
{
if(message->mes[i]!=' ')//字元不為空格時
{
mark=0;
for(j=0;j<total->num;j++)//在total中搜索當前字元
if(total->tot[j].data==message->mes[i])//搜索到，則此字元次數加1，mark標志為1
{
total->tot[j].num++;
mark=1;
break;
}
if(mark==0)//未搜索到，新建字元種類，保存進total中，字元類加1
{
total->tot[total->num].data=message->mes[i];
total->tot[total->num].num=1;
total->num++;
}
}
}
}

void HaffmanTree(Total *total,HNodetype HuffNode[])
/**create the haffman tree
不同字元個數為葉子節點個數對應書上的n，
相同字元的個數為其權值weight；
get HuffNode to store the tree
**/
{
int i,j,min1,min2,x1,x2;
for(i=0;i<2*(total->num)-1;i++)//初始化哈夫曼樹並存入葉子結點權值和信息
{
if(i<=total->num-1)
HuffNode[i].data=total->tot[i].data;
HuffNode[i].weight=total->tot[i].num;
HuffNode[i].parent=-1;
HuffNode[i].lchild=-1;
HuffNode[i].rchild=-1;
}
for(i=0;i<total->num-1;i++)
{
min1=min2=MAXVALUE;
x1=x2=0;
for(j=0;j<total->num+i;j++)//選取最小x1和次小x2的兩權值
{
if(HuffNode[j].parent==-1&&HuffNode[j].weight<min1)
{
min2=min1;
x2=x1;
min1=HuffNode[j].weight;
x1=j;
}
else
if(HuffNode[j].parent==-1&&HuffNode[j].weight<min2)
{
min2=HuffNode[j].weight;
x2=j;
}
}
HuffNode[x1].parent=total->num+i;//修改親人結點位置
HuffNode[x2].parent=total->num+i;
HuffNode[total->num+i].weight=HuffNode[x1].weight+HuffNode[x2].weight;
HuffNode[total->num+i].lchild=x1;//左孩子比右孩子權值小
HuffNode[total->num+i].rchild=x2;
}
}

void HaffmanCode(HNodetype HuffNode[],HCodetype HuffCode[],Total *total)
/***
haffman to code (0,10,110,)
得到每個不同字元（葉子）的編碼，
存貯在數組HuffCode【】中,bit[] store the char,start store the loction
**/
{

int i,j,c,p;
HCodetype cd;
for(i=0;i<total->num;i++)//建立葉子結點個數的編碼
{
cd.start=total->num-1;//起始位初始化
p=HuffNode[i].parent;
c=i;
while(p!=-1)//從葉結點向上爬直到到達根結點
{
if(HuffNode[p].lchild==c)//左分支則為0
cd.bit[cd.start]=0;
else
cd.bit[cd.start]=1;//右分支則為1
cd.start--;//起始位向前移動
c=p;
p=HuffNode[p].parent;
}
for(j=cd.start+1;j<total->num;j++)//保存求出的每個葉結點編碼和起始位
HuffCode[i].bit[j]=cd.bit[j];
HuffCode[i].start=cd.start;

}
}

void writing_HCode(HNodetype HuffNode[],HCodetype HuffCode[],Total *total)
/**
HuffNode[]to input the leaf
HuffCode[]to input the code
all is to the a_test2.txt ,save the code
**/
{
/*打開HCode文件，失敗則結束。將信息寫進文件*/
int i,j;
FILE *fp2=NULL;

if((fp2 = fopen("a_test2.txt","at"))==NULL)
{
printf("can't open the file\n");
exit(0);
}
for(i=0;i<total->num;i++)
{fprintf(fp2,"%d ",HuffNode[i].data);
printf(" ");
for(j=HuffCode[i].start+1;j<total->num;j++)
fprintf(fp2,"%d ",HuffCode[i].bit[j]);
}
printf("編碼規則寫進文件成功!\n");
i=fclose(fp2);
if(i==0)
printf("文件關閉成功!\n");

else
printf("文件關閉失敗!\n");
}

void lock(Message *message,HNodetype HuffNode[],HCodetype HuffCode[],Total *total,Locking *locking)
/***
對messag操作，對所有字元加密，
結果存貯在數組locked[]中，locking 記錄已經加密後的密文
**/

{
int i,j,m;
for(i=0;i<message->num;i++)//把相同的不同的字元全部 遍歷
{
if(message->mes[i]==' ')//碰到空格則以-1形式保存進locked數組中
{
locking->locked[locking->num]=-1;
locking->num++;
}
else
for(j=0;j<total->num;j++)//從total中找到對應的字元
{
if(HuffNode[j].data==message->mes[i])
//找到在HuffNode 中對應字元，找到下標j
// 在HuffCode

for(m=HuffCode[j].start+1;m<total->num;m++)///////// !
{
locking->locked[locking->num]=HuffCode[j].bit[m];//加密
locking->num++;
}
}
}
}

void writing_lock(Locking *locking)
/*
將密文寫到a_test3.txt
*/
{
int i;
FILE *fp3=NULL;

if((fp3= fopen("a_test3.txt","at"))==NULL)
{
printf("can't open the file\n");
exit(0);
}
for(i=0;i<locking->num;i++)
{
if(locking->locked[i]==-1)
printf(" ");
else
fprintf(fp3,"%d ",locking->locked[i]);
}
printf("已編碼信息寫進文件成功!\n");
i=fclose(fp3);
if(i==0)
printf("文件關閉成功!\n");

else
printf("文件關閉失敗!\n");

}

void writing_translate(Locking *locking,HCodetype HuffCode[],HNodetype HuffNode[],Total *total)
/**
密文翻譯成明文，然後存到文件 a_test4.txt
**/
{
int i,j,mark[100],start[100],min,max;
FILE *fp4=NULL;

if((fp4 = fopen("a_test4.txt","at"))==NULL)
{
printf("can't open the file\n");
exit(0);
}

for(i=0;i<total->num;i++)//start數組初始化
{
start[i]=HuffCode[i].start+1;//。。。。
}
for(i=0;i<total->num;i++)//mark數組初始化
{
mark[i]=1;
}
min=0;

for(max=0;max<locking->num;max++)//寫文件
{
if(locking->locked[max]==-1)//碰到空格信息則直接輸出空格
{
printf(" ");//把空格寫到文件
min++;
}
else
{
for(i=min;i<=max;i++)//查找從min開始到max的編碼對應的信息
{
for(j=0;j<total->num;j++)
{
if(start[j] == total->num+1)
mark[j]=0; //對應編碼比所給編碼短則不在比較
if(mark[j]==1&&locking->locked[i]==HuffCode[j].bit[start[j]])
start[j]++;
else
mark[j]=0;
}
}
for(i=0;i<total->num;i++)//找到對應信息，則寫進文件
{
if(mark[i]==1&&start[i]==total->num)
{
fprintf(fp4,"%d ",HuffNode[i].data);//寫到文件outfile
break;
}
}
if(i!=total->num)
min=max+1;
for(i=0;i<total->num;i++)//start數組初始化
{
start[i]=HuffCode[i].start+1;
}
for(i=0;i<total->num;i++)//mark數組初始化
{
mark[i]=1;
}
}
}
printf("文件寫入成功!\n");
i=fclose(fp4);
if(i==0)
printf("文件關閉成功!\n");

else
printf("文件關閉失敗!\n");
}
void first_function(HNodetype HuffNode[],HCodetype HuffCode[],Total *total,Message *message)
{
total_message(message,total);//統計信息中各字元的出現次數
HaffmanTree(total,HuffNode);//構建哈夫曼樹
HaffmanCode(HuffNode,HuffCode,total);//建立哈夫曼編碼

}