Huffman編碼完整代碼-huffman編碼c語(yǔ)言
huffman編碼是一種可變長(zhǎng)編碼方式，于1952年由huffman提出。依據(jù)字符在需要編碼文件中出現(xiàn)的概率提供對(duì)字符的唯一編碼，并且保證了可變編碼的平均編碼最短，被稱為最優(yōu)二叉樹，有時(shí)又稱為最佳編碼。以下是由陽(yáng)光網(wǎng)小編整理關(guān)于Huffman編碼完整代碼的內(nèi)容，希望大家喜歡!
Huffman編碼完整代碼
//利用哈夫曼樹進(jìn)行編碼，
#include <dos.h>
#include <conio.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include<iostream>
#include<malloc.h>
using namespace std;
typedef struct //定義哈夫曼樹
{ int weight; //結(jié)點(diǎn)權(quán)值
int parent,lchild,rchild; //結(jié)點(diǎn)的父指針，左右孩子指針
}HTNode,*HuffmanTree;
typedef char **HuffmanCode; //數(shù)組存儲(chǔ)哈夫曼編碼表
void CreateHuffmanTree(HuffmanTree &,unsigned int*,int ); //生成哈夫曼樹
void HuffmanCoding(HuffmanTree,HuffmanCode &,int ); //哈夫曼樹編碼
void PrintHuffmanCode(HuffmanCode,unsigned int*,int); //顯示編碼結(jié)果
void Select(HuffmanTree,int,int&,int&); //在數(shù)組中尋找權(quán)值最小的兩個(gè)結(jié)點(diǎn)
void main()
{HuffmanTree HT; //哈夫曼樹HT
HuffmanCode HC; //哈夫曼編碼表HC
int n,i; //n是哈夫曼樹葉子結(jié)點(diǎn)數(shù)
unsigned int *w; //w存放葉子結(jié)點(diǎn)權(quán)值
cout<<"huffman編碼使用說明"<<endl ; //使用說明
cout<<"例如：輸入需要進(jìn)行編碼的字符數(shù)目2"<<endl;
cout<<"然后輸入每個(gè)字符的權(quán)值(整數(shù))"<<endl;
cout<<"例如:5 29 "<<endl;
cout<<"則構(gòu)造一棵哈夫曼樹，哈夫曼編碼如下"<<endl;
cout<<" 5---0"<<endl<< "29---1"<<endl;
printf("請(qǐng)需要進(jìn)行編碼的字符數(shù)目:");
scanf("%d",&n);
w=(unsigned int*)malloc(n*sizeof(unsigned int));
printf("輸入每個(gè)字符的權(quán)值(整數(shù)):\n");
for(i=0;i<n;i++) scanf("%d",&w[i]); //輸入各字符出現(xiàn)的次數(shù)/權(quán)值
CreateHuffmanTree(HT,w,n); //生成哈夫曼樹
HuffmanCoding(HT,HC,n); //進(jìn)行編碼
PrintHuffmanCode(HC,w,n); //顯示編碼
}
void CreateHuffmanTree(HuffmanTree &HT,unsigned int *w,int n)
{//構(gòu)造哈夫曼樹
int i,m;
int s1,s2;
HuffmanTree p;
if(n<=1) return;
m=2*n-1; //n個(gè)葉子結(jié)點(diǎn)，共需2*n-1個(gè)結(jié)點(diǎn)
HT=(HuffmanTree)malloc((m+1)*sizeof(HTNode)); //開辟空間
for(p=HT+1,i=1;i<=n;++i,++p,++w) //初始化
{p->weight=*w;
p->parent=0;
p->lchild=0;
p->rchild=0;
}
for(;i<=m;++i,++p)
{p->weight=0;
p->parent=0;
p->lchild=0;
p->rchild=0;
}
for(i=n+1;i<=m;++i) //建哈夫曼樹
{Select(HT,i-1,s1,s2);
HT[s1].parent=i; HT[s2].parent=i; //修改s1和s2結(jié)點(diǎn)的父指針parent
HT[i].lchild=s1; HT[i].rchild=s2; //修改i結(jié)點(diǎn)的.左右孩子指針
HT[i].weight=HT[s1].weight+HT[s2].weight; //修改權(quán)值指向在數(shù)組中的位置
}
}
void HuffmanCoding(HuffmanTree HT,HuffmanCode &HC,int n)
{//將哈夫曼樹進(jìn)行編碼，所編的碼存放在HC，從葉子到根逆向求每個(gè)葉子結(jié)點(diǎn)的哈夫曼編碼
int i,c,f,start;
char *cd;
HC=(HuffmanCode)malloc((n+1)*sizeof(char *)); //分配n個(gè)編碼的頭指針向量
cd=(char *)malloc(n*sizeof(char)); //開辟一個(gè)求編碼的工作空間
cd[n-1]='\0'; //編碼結(jié)束符
for(i=1;i<=n;++i) //逐個(gè)地求哈夫曼編碼
{start=n-1; //編碼結(jié)束位置
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'; //若是右孩子編為'1'
HC[i]=(char *)malloc((n-start)*sizeof(char)); //為第i個(gè)編碼分配空間
strcpy(HC[i],&cd[start]); //將編碼從cd復(fù)制到HC中
}
free(cd);
}
void PrintHuffmanCode(HuffmanCode HC,unsigned int *w,int n)
{//顯示輸入的n個(gè)葉子結(jié)點(diǎn)的哈夫曼樹的編碼表
int i;
printf("HuffmanCode is :\n");
for(i=1;i<=n;i++)
{printf(" %3d---",w[i-1]);
puts(HC[i]);
}
printf("\n");
}
//在HT[1...t]中選擇parent不為0且權(quán)值最小的兩個(gè)結(jié)點(diǎn)，其序號(hào)分別為s1和s2
void Select(HuffmanTree HT,int t,int&s1,int&s2)
{ int i,m,n;
m=n=10000;
for(i=1;i<=t;i++)
{if(HT[i].parent==0&&(HT[i].weight<m||HT[i].weight<n))
if(m<n)
{n=HT[i].weight;s2=i;}
else {m=HT[i].weight;s1=i;}
}
if(s1>s2) //s1放較小的序號(hào)
{i=s1;s1=s2;s2=i;}
}
Huffman代碼流程
看過“Huffman編碼完整代碼”的人還看了：
【Huffman編碼完整代碼-huffman編碼c語(yǔ)言】相關(guān)文章：