哈夫曼樹編解碼設計過程

① 哈夫曼編碼/解碼器編程

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define M 10000 //定義字元串最大長度
#define N 128 //定義葉子節點個數
typedef struct node //定義哈夫曼樹節點結構體
{
int weight;
struct node *LChild,*RChild,*Parent; //分別指向該節點的左孩子，右孩子，和雙親節點
struct node *next; //指向建立的哈夫曼樹的下一個節點
}HFMNode,*HFMTree;
typedef struct //定義哈夫曼編碼的結構體
{
char ch; //存儲對應的字元
char code[N+1]; //存儲對應字元的編碼
int start; //存儲編碼的起始位置
}CodeNode;int n; //存儲真正葉子節點個數
void clearscreen()
{
system("cls");
}
void Open(char s[]) //打開存放字元或編碼的文件，將其存入字元串數組中
{
char name[10];
FILE *fp;
int i=0;
printf("請輸入要打開的文件名：");
gets(name); //要打開的文件名
if((fp=fopen(name,"rt"))==NULL)
{
printf("打開失敗！\n"); //若打開失敗，則直接退出
exit(1);
}
s[i++]=fgetc(fp);
while(s[i-1]!=EOF)
s[i++]=fgetc(fp);
s[i]='\0'; //存取字元串結束
fclose(fp);
}
void Save(char s[]) //保存字元或編碼到文件中
{
char name[10];
FILE *fp;
printf("請輸入要保存的文件名：");
gets(name);
if((fp=fopen(name,"wt"))==NULL)
{
printf("存儲失敗！");
exit(1);
}
fputs(s,fp);
printf("\n保存成功，文件名為:%s。\n",name);
printf("\n按回車鍵繼續...");
getchar();
fclose(fp);} void SearchStr(char s[],char str[],int count[])
{
//查找字元串中字元的個數和每個字元出現的次數
int i,j,k=0;
for(i=0;i<N;i++) //初始化每個字元出現的次數
count[i]=0;
for(i=0;s[i];i++)
{
for(j=0;j<k;j++) //在str[]中查找是否有該字元
if(str[j]==s[i])
{
count[j]++;
break;
}
if(j==k) //在str[]中無該字元，將其存入最後一個單元
{
str[k]=s[i];
count[k++]++;
}
}
str[k]='\0'; //將字元串結尾置\0
n=k; //將實際的字元個數作為葉子節點個數存入n
}void SelectMin(HFMTree HT,int k,HFMTree *HT1,HFMTree *HT2)
{
//查找哈夫曼鏈表中兩個權值最小的節點
int i,min;
HFMTree p;
min=32767;
for(i=0,p=HT;i<k;i++,p=p->next)
if(p->weight<min&&p->Parent==0)
{
min=p->weight;
*HT1=p;
}
min=32767;
for(i=0,p=HT;i<k;i++,p=p->next)
if(p->weight<min&&p->Parent==0&&p!=*HT1) //令第二個最小的節點不等於第一個節點
{
min=p->weight;
*HT2=p;
}}
void CreatHFMTree(HFMTree *HT,int count[])
{
//創建哈夫曼樹
int i;
HFMTree p,HT1,HT2; //HT1，HT2分別存放權值最小和次小的節點的位置
p=*HT=(HFMTree)malloc(sizeof(HFMNode));
p->next=p->LChild=p->RChild=p->Parent=NULL; //初始化哈夫曼鏈表且有2n-1個節點
for(i=1;i<2*n-1;i++)
{
p->next=(HFMTree)malloc(sizeof(HFMNode));
p=p->next;
p->next=p->LChild=p->RChild=p->Parent=NULL;
}for(i=0,p=*HT;i<n;i++) //將各個字元出現的次數作為權值
{ //存入哈夫曼鏈表的前n個單元中
p->weight=count[i];
p=p->next;
}for(i=n;i<2*n-1;i++) //將後n-1個節點賦權值，建樹
{
SelectMin(*HT,i,&HT1,&HT2); //每次從前i個節點中選取權值最小的兩個節點
HT1->Parent=HT2->Parent=p;
p->LChild=HT1;
p->RChild=HT2;
p->weight=HT1->weight+HT2->weight; //將兩個節點的權值相加存入最後一個節點中
p=p->next; //p指向下一個沒有存儲權值的節點
}}
void HFMCode(HFMTree HT,CodeNode HC[],char str[])
{
//從每個葉子節點開始，利用哈夫曼樹對每個字元進行編碼，最終建立一個哈夫曼表
int i;
HFMTree q,p=HT;
for(i=0;i<n;i++) //將字元存入哈夫曼編碼結構體數組的字元單元中
{
HC[i].ch=str[i];
HC[i].code[n-1]='\0'; //初始化編碼的最後一位
}
for(i=0;i<n;i++)
{
HC[i].start=n-1;
for(q=p;q->Parent;q=q->Parent) //判斷q所指向的節點，左孩子置0，右孩子置1
if(q==q->Parent->LChild)
HC[i].code[--HC[i].start]='0';
else HC[i].code[--HC[i].start]='1';
p=p->next; //判斷下一個葉子節點
}
}
void TotalCoding(char s[],CodeNode HC[],char code[])
{
//利用哈夫曼編碼表對整個字元串進行編碼
int i,j;
code[0]='\0'; //編碼數組初始化
for(i=0;s[i];i++) //將每個字元在哈夫曼編碼表中對應的編碼存入存放總編碼的數組中
for(j=0;j<n;j++)
if(s[i]==HC[j].ch)
strcpy(code+strlen(code),HC[j].code+HC[j].start);
}void DeCoding(char code[],HFMTree HT,char str[],char s[])
{
//對哈夫曼編碼進行解碼，放入字元串s中
int i,j,k=0;
HFMTree root,p,q;
for(root=HT;root->Parent;root=root->Parent); //用root指向哈夫曼樹的根結點
for(i=0,p=root;code[i];i++) //從根結點開始按編碼順序訪問樹
{
if(code[i]=='0')
p=p->LChild;
else p=p->RChild;
if(p->LChild==NULL&&p->RChild==NULL) //到根節點時將該節點對應的字元輸出
{
for(j=0,q=HT;q!=p;q=q->next,j++);
s[k++]=str[j];
p=root; //回溯到根結點
}
}
s[k]='\0'; //解碼完畢，在字元串最後一個單元存入'\0'
}
void Coding(char s[],char str[],char code[],int count[],HFMTree *HT,CodeNode HC[])
{
clearscreen();
printf("\n打開存放字元串的文件...\n\n");
Open(s); //打開源碼文件
SearchStr(s,str,count); //查找字元串中不同的字元及其出現的次數
CreatHFMTree(HT,count); //用每個字元出現的次數作為葉子節點的權值建立哈夫曼樹
HFMCode(*HT,HC,str); //利用哈夫曼樹對每個葉子節點進行編碼，存入編碼表中
TotalCoding(s,HC,code); //利用編碼表對字元串進行最終編碼
printf("\n讀入的字元串為:\n");
puts(s);
printf("\n最終的哈夫曼編碼是:\n");
puts(code);
printf("\n保存編碼,");
Save(code); //保存最終的哈夫曼編碼
}
void TransCode(char code[],char str[],char ss[],HFMTree *HT,CodeNode HC[])
{
clearscreen();
printf("\n打開編碼的文件...\n\n");
Open(code); //打開編碼文件
DeCoding(code,*HT,str,ss); //將編碼進行解碼存入字元串數組ss[]中
printf("\n得到的最終字元串為:\n");
puts(ss);
printf("\n保存解碼，");
Save(ss); //保存解碼後的字元串
}void main()
{
//主函數
char s[M],ss[M]; //定義字元串數組，s[]存放將要編碼的字元串，ss[]存解碼後的字元串
char str[N]; //存放輸入的字元串中n個不同的字元
int count[N]; //存放n個不同字元對應的在原字元串中出現的次數
char code[M]; //存放最終編碼完成後的編碼
char choice;
HFMTree HT; //定義一個哈夫曼樹的鏈表
CodeNode HC[N]; //定義一個哈夫曼編碼表的數組，存放每個字元對應的哈夫曼編碼
do
{
clearscreen();
printf("\n\n");
printf(" ************哈夫曼樹************\n");
printf(" ** **\n");
printf(" ** 1.編碼。 **\n");
printf(" ** 2.解碼。 **\n");
printf(" ** 0.退出。 **\n");
printf(" ** **\n");
printf(" ** **\n");
printf(" ** **\n");
printf(" ** 請輸入相應操作的序號(0-2) **\n");
printf(" ********************************\n");
scanf("%c",&choice);
getchar();
switch(choice)
{
case '1': Coding(s,str,code,count,&HT,HC);break; //對字元串進行編碼
case '2': TransCode(code,str,ss,&HT,HC);break; //對編碼進行解碼
case '0': break;
default : printf(" 輸入錯誤！請重新輸入！\n");
}
}while(choice!='0');
}

② 哈夫曼編碼的解碼過程的大致思路是什麼（不要代碼）

哈夫曼樹和字元編碼對應你都弄完了，得到是如a :01 b :101對應關系，通過這個關系直接將像「asdsdfdfg」直接轉換為「01110101」這樣二進制編碼。解碼的時候，讀取二進制編碼，先讀取一位，然後在關系表中查找該二進制數對應的字元，如果沒有找到，繼續讀取二位，然後繼續在關系表中查找該二位二進制對應的字元。如此循環，知道找到字元位置，然後將二進制數替換為相應的字元，知道所有的數都替換完為止。

③ 哈夫曼樹編碼與解碼

#define INT_MAX 10000
#define ENCODING_LENGTH 1000
#include "stdio.h"
#include "string.h"
#include "malloc.h"
typedef enum{none,left_child,right_child} Which;//標記是左孩子還是右孩子
typedef char Elemtype;
typedef struct TNode{
Elemtype letter;
int weight;
int parent;
Which sigh;
char *code;
}HTNode,*HuffmanTree;
int n;
char coding[50];//儲存代碼
char str[ENCODING_LENGTH];//保存要翻譯的句子
void InitTreeNode(HuffmanTree &HT){//初始前N個結點,後M-N個結點置空
int i;int w;char c;
int m=2*n-1;
HuffmanTree p;
HT=(HuffmanTree)malloc((m)*sizeof(HTNode));
printf("input %d database letter and weight",n);
p=HT;
getchar();
for (i=1;i<=n;i++){
scanf("%c%d",&c,&w);
p->code='\0';
p->letter=c;
p->parent=0;
p->sigh=none;
p->weight=w;
p++;
getchar();
}
for (;i<=m;i++,p++){
p->code='\0';
p->letter=' ';
p->parent=0;
p->sigh=none;
p->weight=0;
}
}//INITTREENODE
void Select(HuffmanTree HT,int end,int *s1,int *s2){//在0~END之間,找出最小和次小的兩個結點序號,返回S1,S2
int i;
int min1=INT_MAX;
int min2;
for (i=0;i<=end;i++){//找最小的結點序號
if (HT[i].parent==0&&HT[i].weight<min1){
*s1=i;
min1=HT[i].weight;
}
}
min2=INT_MAX;
for(i=0;i<=end;i++){//找次小結點的序號
if (HT[i].parent==0&&(*s1!=i)&&min2>HT[i].weight){
*s2=i;
min2=HT[i].weight;
}
}
}
void HuffmanTreeCreat(HuffmanTree &HT){//建立HUFFMAN樹
int i;int m=2*n-1;
int s1,s2;
for(i=n;i<m;i++){
Select(HT,i-1,&s1,&s2);
HT[s1].parent=i;
HT[s2].parent=i;
HT[s1].sigh=left_child;
HT[s2].sigh=right_child;
HT[i].weight=HT[s1].weight+HT[s2].weight;
}
}

void HuffmanTreeCode(HuffmanTree HT){//HUFFMAN解碼
int i;
char *temp;
temp=(char *)malloc(n*sizeof(char));
temp[n-1]='\0';
int p;int s;
for (i=0;i<n;i++){
p=i;
s=n-1;
while (HT[p].parent!=0){//從結點回溯,左孩子為0,右孩子為1
if (HT[p].sigh==left_child)
temp[--s]='0';
else if (HT[p].sigh==right_child)
temp[--s]='1';
p=HT[p].parent;
}
HT[i].code=(char *)malloc((n-s)*sizeof(char));//分配結點碼長度的內存空間
strcpy(HT[i].code,temp+s);
printf("%s\n",HT[i].code);
}
}
void GetCodingSen(char *sencence){//輸入要編碼的句子
int l;
gets(sencence);
l=strlen(sencence);
sencence[l]='\0';
}
void HuffmanTreeEncoding(char sen[],HuffmanTree HT){//將句子進行編碼
int i=0;int j;
while(sen[i]!='\0'){
for(j=0;j<n;j++){
if (HT[j].letter==sen[i]) //字母吻合則用代碼取代
{strcat(coding,HT[j].code);
break;
}
}
i++;
if (sen[i]==32) i++;
}
printf("\n%s",coding);
}
void HuffmanTreeDecoding(HuffmanTree HT,char code[]){//HUFFMAN解碼過程,將代碼翻譯為句子
char sen[100];
char temp[50];
char voidstr[]=" ";
int i;int j;
int t=0;int s=0;
for(i=0;i<strlen(code);i++){
temp[t++]=code[i];
for(j=0;j<n;j++){
if (strcmp(HT[j].code,temp)==0){//代碼段吻合
sen[s]=HT[j].letter;s++;
strcpy(temp,voidstr);//將TEMP置空
t=0;
break;
}
}
}
printf("\n%s",sen);
}

void main(){
HTNode hnode;
HuffmanTree huff;
huff=&hnode;
printf("input the letter for coding number\n");
scanf("%d",&n);
InitTreeNode(huff);
HuffmanTreeCreat(huff);
HuffmanTreeCode(huff);
GetCodingSen(str);
HuffmanTreeEncoding(str,huff);
HuffmanTreeDecoding(huff,coding);

④ 哈夫曼樹的建立、編解碼

typedef struct{
int weight;
int flag;
int parent;
int leftchild;
int rightchild;
} haffnode;
typedef struct
{
int bit[MAXN];
int start;
int weight;
}code;
void haffman(int weight[],int n,haffnode hafftree[])
{
int i,j,m1,m2,x1,x2;
for(i=0;i<2*n-1;i++)
{
if(i<n)hafftree[i].weight=weight[i];
else hafftree[i].weight=0;
hafftree[i].parent=-1;
hafftree[i].flag=0;
hafftree[i].leftchild=-1;
hafftree[i].rightchild=-1;
}
for(i=0;i<n-1;i++)
{
m1=m2=maxvalue;
x1=x2=0;
for(j=0;j<n+i;j++)
{
if(hafftree[j].weight<m1&&hafftree[j].flag==0)
{
m2=m1;
x2=x1;
m1=hafftree[j].weight;
x1=j;
}
else if(hafftree[j].weight<m2&&hafftree[j].flag==0)
{
m2=hafftree[j].weight;
x2=j;
}
}
hafftree[x1].parent=n+i;
hafftree[x2].parent=n+i;
hafftree[x1].flag=1;
hafftree[x2].flag=1;
hafftree[n+i].weight=hafftree[x1].weight+hafftree[x2].weight;
hafftree[n+i].leftchild=x1;
hafftree[n+i].rightchild=x2;
}
}

⑤ 哈夫曼編碼與解碼

什麼叫N—S流程圖？

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

int m,s1,s2;

typedef struct {
unsigned int weight;
unsigned int parent,lchild,rchild;
}HTNode,*HuffmanTree; //動態分配數組存儲哈夫曼樹
typedef char *HuffmanCode; //動態分配數組存儲哈夫曼編碼表

void Select(HuffmanTree HT,int n) {
int i,j;
for(i = 1;i <= n;i++)
if(!HT[i].parent){s1 = i;break;}
for(j = i+1;j <= n;j++)
if(!HT[j].parent){s2 = j;break;}
for(i = 1;i <= n;i++)
if((HT[s1].weight>HT[i].weight)&&(!HT[i].parent)&&(s2!=i))s1=i;
for(j = 1;j <= n;j++)
if((HT[s2].weight>HT[j].weight)&&(!HT[j].parent)&&(s1!=j))s2=j;
}

void HuffmanCoding(HuffmanTree &HT, HuffmanCode HC[], int *w, int n) {
// 演算法6.13
// w存放n個字元的權值(均>0)，構造哈夫曼樹HT，
// 並求出n個字元的哈夫曼編碼HC
int i, j;
char *cd;
int p;
int cdlen;

if (n<=1) return;
m = 2 * n - 1;
HT = (HuffmanTree)malloc((m+1) * sizeof(HTNode)); // 0號單元未用
for (i=1; i<=n; i++) { //初始化
HT[i].weight=w[i-1];
HT[i].parent=0;
HT[i].lchild=0;
HT[i].rchild=0;
}
for (i=n+1; i<=m; i++) { //初始化
HT[i].weight=0;
HT[i].parent=0;
HT[i].lchild=0;
HT[i].rchild=0;
}
puts("\n哈夫曼樹的構造過程如下所示：");
printf("HT初態:\n 結點 weight parent lchild rchild");
for (i=1; i<=m; i++)
printf("\n%4d%8d%8d%8d%8d",i,HT[i].weight,
HT[i].parent,HT[i].lchild, HT[i].rchild);
printf(" 按任意鍵，繼續 ...");
getchar();
for (i=n+1; i<=m; i++) { // 建哈夫曼樹
// 在HT[1..i-1]中選擇parent為0且weight最小的兩個結點，
// 其序號分別為s1和s2。
Select(HT, i-1);
HT[s1].parent = i; HT[s2].parent = i;
HT[i].lchild = s1; HT[i].rchild = s2;
HT[i].weight = HT[s1].weight + HT[s2].weight;
printf("\nselect: s1=%d s2=%d\n", s1, s2);
printf(" 結點 weight parent lchild rchild");
for (j=1; j<=i; j++)
printf("\n%4d%8d%8d%8d%8d",j,HT[j].weight,
HT[j].parent,HT[j].lchild, HT[j].rchild);
printf(" 按任意鍵，繼續 ...");
getchar();
}

//------無棧非遞歸遍歷哈夫曼樹，求哈夫曼編碼
cd = (char *)malloc(n*sizeof(char)); // 分配求編碼的工作空間
p = m; cdlen = 0;
for (i=1; i<=m; ++i) // 遍歷哈夫曼樹時用作結點狀態標志
HT[i].weight = 0;
while (p) {
if (HT[p].weight==0) { // 向左
HT[p].weight = 1;
if (HT[p].lchild != 0) { p = HT[p].lchild; cd[cdlen++] ='0'; }
else if (HT[p].rchild == 0) { // 登記葉子結點的字元的編碼
HC[p] = (char *)malloc((cdlen+1) * sizeof(char));
cd[cdlen] ='\0'; strcpy(HC[p], cd); // 復制編碼(串)
}
} else if (HT[p].weight==1) { // 向右
HT[p].weight = 2;
if (HT[p].rchild != 0) { p = HT[p].rchild; cd[cdlen++] ='1'; }
} else { // HT[p].weight==2，退回退到父結點，編碼長度減1
HT[p].weight = 0; p = HT[p].parent; --cdlen;
}
}
} // HuffmanCoding
void main() {
HuffmanTree HT;HuffmanCode *HC;int *w,n,i;
puts("輸入結點數:");
scanf("%d",&n);
HC = (HuffmanCode *)malloc(n*sizeof(HuffmanCode));
w = (int *)malloc(n*sizeof(int));
printf("輸入%d個結點的權值\n",n);
for(i = 0;i < n;i++)
scanf("%d",&w[i]);
HuffmanCoding(HT,HC,w,n);
puts("\n各結點的哈夫曼編碼:");
for(i = 1;i <= n;i++)
printf("%2d(%4d):%s\n",i,w[i-1],HC[i]);
getchar();
}

⑥ 哈夫曼樹及哈夫曼編碼解碼的實現（根據程序畫流程圖及對每句程序注釋）

這是以前寫的，可是我不想加註釋了，Huffman編碼其實原理很簡單的，你自己好好學下吧，一句一句注釋也太誇張了啊。

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

int m,s1,s2;

typedef struct {
unsigned int weight;
unsigned int parent,lchild,rchild;
}HTNode,*HuffmanTree;

typedef char ** HuffmanCode;

void Select(HuffmanTree HT,int n)
{
int i,j;
for(i=1;i<=n;i++)
if(HT[i].parent==0)
{s1=i;
break;
}
for(j=i+1;j<=n;j++)
if(HT[j].parent==0)
{
s2=j;
break;
}
for(i=1;i<=n;i++)
{
if(HT[i].parent==0)
if(HT[s1].weight>HT[i].weight)
if(s2!=i)
s1=i;
}
for(j=1;j<=n;j++)
{
if(HT[j].parent==0)
if(HT[s2].weight>HT[j].weight)
if(s1!=j)
s2=j;
}
if(s1>s2)
{
int temp=s1;
s1=s2;
s2=temp;
}
}

void HuffmanCoding(HuffmanTree &HT, HuffmanCode &HC, int *w, int n)
{
int i,j;
char *cd;
int p;
int cdlen;
if (n<=1) return;
m = 2 * n - 1;
HT = (HuffmanTree)malloc((m+1) * sizeof(HTNode));
for (i=1; i<=n; i++)
{
HT[i].weight=w[i-1];
HT[i].parent=0;
HT[i].lchild=0;
HT[i].rchild=0;
}
for (i=n+1; i<=m; i++)
{
HT[i].weight=0;
HT[i].parent=0;
HT[i].lchild=0;
HT[i].rchild=0;
}

//添加查看，便於調試
printf("構造過程顯示：\n");
for(i=1;i<=m;i++)
printf("%4d%4d%4d%4d%4d\n",i,HT[i].weight, HT[i].parent,HT[i].lchild, HT[i].rchild);
system("pause");

for(i=n+1;i<=m;i++)
{
Select(HT,i-1);
HT[s1].parent = i; HT[s2].parent = i;
HT[i].lchild = s1; HT[i].rchild = s2;
HT[i].weight = HT[s1].weight + HT[s2].weight;
//添加查看，便於調試
/*printf("s1=%d,s2=%d\n",s1,s2);
for(j=1;j<=i;j++)
printf("%d%4d%4d%4d",j,HT[j].weight,HT[j].parent,HT[j].lchild, HT[j].rchild);
system("pause");
*/
}
cd = (char *)malloc(n*sizeof(char));
p=m;
cdlen=0;
for(i=1;i<=m;i++)
HT[i].weight=0;
while(p)
{
if(HT[p].weight==0)
{
HT[p].weight=1;
if(HT[p].lchild!=0)
{
p=HT[p].lchild;
cd[cdlen++]='0';
}
else if(HT[p].rchild==0)
{
HC[p]=(char *)malloc((cdlen+1)*sizeof(char));
cd[cdlen]='\0';
strcpy(HC[p],cd);
}
}
else if(HT[p].weight==1)
{
HT[p].weight=2;
if(HT[p].rchild!=0)
{
p=HT[p].rchild;
cd[cdlen++]='1';
}
}
else
{
HT[p].weight=0;
p=HT[p].parent;
--cdlen;
}
}

}

int main()
{
HuffmanTree HT;
HuffmanCode HC;
int *w,n,i;
printf("請輸入節點數：\n");
scanf("%d",&n);
HC = (HuffmanCode)malloc(n*sizeof(HuffmanCode));
w=(int *)malloc(n*sizeof(int));
printf("請輸入節點的權值：\n");
for(i=0;i<n;i++)
scanf("%d",&w[i]);
HuffmanCoding(HT,HC,w,n);
printf("輸出編碼：\n");
for(i=1;i<=n;i++)
printf("%2d(%4d):%s\n",i,w[i-1],HC[i]);
return 0;
system("pause");
}