我的這個能實現(xiàn)編碼與譯碼；
成都創(chuàng)新互聯(lián)專注于企業(yè)網(wǎng)絡(luò)營銷推廣、網(wǎng)站重做改版、坊子網(wǎng)站定制設(shè)計、自適應(yīng)品牌網(wǎng)站建設(shè)、H5高端網(wǎng)站建設(shè)、購物商城網(wǎng)站建設(shè)、集團公司官網(wǎng)建設(shè)、成都外貿(mào)網(wǎng)站制作、高端網(wǎng)站制作、響應(yīng)式網(wǎng)頁設(shè)計等建站業(yè)務(wù)，價格優(yōu)惠性價比高，為坊子等各大城市提供網(wǎng)站開發(fā)制作服務(wù)。
//huffman.h
const int Lengh=1000;
char coding[100]; //存儲二進制字符串
int n; //定義全局變量
enum Child{none,lchild,rchild}; //采用枚舉標(biāo)記事左孩子還是右孩子
struct element
{
char letter,*code;
int weight; //權(quán)值域
int parent;
Child a;
};
void Select(element h[],int k,int *a,int *b);
void InitHuffmanTree(element huffTree[],char t[],int w[]) //哈夫曼樹的初始化
{
int i,m=2*n-1,s1,s2;
for(i=0;in;i++) //初始前n個結(jié)點
{
huffTree[i].code='\0';
huffTree[i].parent=-1;
huffTree[i].a=none;
huffTree[i].letter=t[i];
huffTree[i].weight=w[i];
}
for(;i=m;i++) //后m-n個結(jié)點置空
{
huffTree[i].code='\0';
huffTree[i].letter=' ';
huffTree[i].parent=-1;
huffTree[i].a=none;
huffTree[i].weight=0;
}
for(i=n;im;i++) //建立哈夫曼樹
{
Select(huffTree,i-1,s1,s2); //在huffTree中找權(quán)值最小的兩個結(jié)點s1,s2
huffTree[s1].parent=i; //將s1,s2合并，則s1,s2的雙親是k
huffTree[s2].parent=i;
huffTree[s1].a=lchild;
huffTree[s2].a=rchild;
huffTree[i].weight=huffTree[s1].weight+huffTree[s2].weight;
}
}
void Select(element h[],int k,int *a,int *b) //尋找最小和次小節(jié)點的序號
{
int i;
int min1=1000;
int min2=1000;
for (i=0;i=k;i++)//找最小的結(jié)點序號
{
if (h[i].parent==-1h[i].weightmin1)
{
*a=i;
min1=h[i].weight;
}
}
for(i=0;i=k;i++)//找次小結(jié)點的序號
{
if(h[i].parent==-1(*a!=i)h[i].weightmin2)
{
*b=i;
min2=h[i].weight;
}
}
}
void HuffmanTreeCode(element HT[]) //單個字符編碼
{
int i;
char *temp;
temp=(char *)malloc(n*sizeof(char)); //分配n個字符空間
temp[n-1]='\0';
int p;
int s;
for(i=0;in;i++)
{
p=i;
s=n-1;
while(HT[p].parent!=-1)//從結(jié)點回溯,左孩子為0,右孩子為1
{
if(HT[p].a==lchild)
temp[--s]='0';
else if(HT[p].a==rchild)
temp[--s]='1';
p=HT[p].parent;
}
HT[i].code=(char *)malloc((n-s)*sizeof(char));//分配結(jié)點碼長度的內(nèi)存空間
strcpy(HT[i].code,temp+s);
printf("%c",HT[i].letter);
printf(":"); printf(" ");
printf("%s\n",HT[i].code);
}
}
void HuffmanTreeYima(element huff[],char cod[],int b) //譯碼
{
char sen[100];
char temp[50];
char voidstr[]=" ";
int t=0; int s=0;
for(int i=0 ; ib; i++)
{
temp[t++]=cod[i];
temp[t] = '\0';
for(int j=0;jn;j++)
{
if (!strcmp(huff[j].code,temp)) //代碼段吻合
{
sen[s]=huff[j].letter;
s++;
strcpy(temp,voidstr); //將TEMP置空
t=0;
break;
}
}
}
sen[s]='\0';
cout"譯碼為:"endl;
coutsenendl;
}
//h.cpp
#include iostream.h
#include string.h
#include malloc.h
#include stdio.h
#include "huffman.h"
void main()
{
element h[Lengh];
char c,a[Lengh],p;
int i,b[Lengh];
int symbol=1;
cout"!!!!歡迎來到哈夫曼編碼與譯碼!!!!"endl;
cout"編碼："endl;
cout"請輸入要編碼字符的個數(shù)：";
cinn;
for(i=0;in;i++)
{
cin.get();//跳過輸入流中的一個字符(即獲取上次輸入的回車鍵)
cout"字符："; cin.get(c); a[i]=c;
cout"權(quán)值："; cinb[i];
}
InitHuffmanTree(h,a,b); //哈夫曼樹的初始化
HuffmanTreeCode(h); //編碼
cout"譯碼："endl;
cout"請輸入要譯碼的二進制字符串,輸入'#'結(jié)束：";
int k=0;
while(symbol)
{
cinp; coding[k]=p;
if(p=='#') symbol=0;
k++;
}
HuffmanTreeYima(h,coding,k-1); //進行譯碼
}
設(shè)某信源產(chǎn)生有五種符號u1、u2、u3、u4和u5，對應(yīng)概率P1=0.4，P2=0.1，P3=P4=0.2，P5=0.1。
霍夫曼編碼是變長編碼，思路：對概率大的編的碼字短，概率小的編的碼字長，這樣一來所編的總碼長就小，這樣編碼效率就高。上面那樣求是不對的，除非你這6個碼字是等概率的，各占1/6。應(yīng)該用對應(yīng)的概率*其對應(yīng)得碼長，再求和。
實際應(yīng)用中
除采用定時清洗以消除誤差擴散和采用緩沖存儲以解決速率匹配以外，主要問題是解決小符號集合的統(tǒng)計匹配，例如黑（1）、白（0）傳真信源的統(tǒng)計匹配，采用0和1不同長度游程組成擴大的符號集合信源。游程，指相同碼元的長度（如二進碼中連續(xù)的一串0或一串1的長度或個數(shù)）。
按照CCITT標(biāo)準(zhǔn)，需要統(tǒng)計2×1728種游程（長度），這樣，實現(xiàn)時的存儲量太大。事實上長游程的概率很小，故CCITT還規(guī)定：若l表示游程長度，則l=64q+r。
// c1.h (程序名)
#includestring.h
#includectype.h
#includemalloc.h // malloc()等
#includelimits.h // INT_MAX等
#includestdio.h // EOF(=^Z或F6),NULL
#includestdlib.h // atoi()
#includeio.h // eof()
#includemath.h // floor(),ceil(),abs()
#includeprocess.h // exit()
#includeiostream.h // cout,cin // 函數(shù)結(jié)果狀態(tài)代碼
#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define INFEASIBLE -1
// #define OVERFLOW -2 因為在math.h中已定義OVERFLOW的值為3,故去掉此行
typedef int Status; // Status是函數(shù)的類型,其值是函數(shù)結(jié)果狀態(tài)代碼，如OK等
typedef int Boolean; // Boolean是布爾類型,其值是TRUE或FALSE
// c6-7.h 赫夫曼樹和赫夫曼編碼的存儲表示
typedef struct
{
unsigned int weight;
unsigned int parent,lchild,rchild;
char data;
}HTNode,*HuffmanTree; // 動態(tài)分配數(shù)組存儲赫夫曼樹 typedef char **HuffmanCode; // 動態(tài)分配數(shù)組存儲赫夫曼編碼表
#include "..\c1.h"
#include "c6-7.h" int min(HuffmanTree t, int i)
{ // 返回i個結(jié)點中權(quán)值最小的樹的根結(jié)點序號，函數(shù)select()調(diào)用
int j,flag;
unsigned int k=UINT_MAX; // 取k為不小于可能的值(無符號整型最大值)
for(j=1;j=i;j++)
if(t[j].weightk t[j].parent==0) // t[j]是樹的根結(jié)點
k=t[j].weight,flag=j;
t[flag].parent=1; // 給選中的根結(jié)點的雙親賦1，避免第2次查找該結(jié)點
return flag;
} void select(HuffmanTree t,int i,int s1, int s2)
{ // 在i個結(jié)點中選擇2個權(quán)值最小的樹的根結(jié)點序號，s1為其中序號小的那個
int j;
s1=min(t,i);
s2=min(t,i);
if(s1s2)
{
j=s1;
s1=s2;
s2=j;
}
}
// HuffmanCoding1求赫夫曼編碼。實現(xiàn)算法6.12的程序
void HuffmanCoding1(HuffmanTree HT,HuffmanCode HC,int *w,int n) // 算法6.12
{ // w存放n個字符的權(quán)值(均0)，構(gòu)造赫夫曼樹HT，并求出n個字符的赫夫曼編碼HC
int m,i,s1,s2,start;
unsigned c,f;
HuffmanTree p;
char *cd;
if(n=1)
return;
m=2*n-1;
HT=(HuffmanTree)malloc((m+1)*sizeof(HTNode)); // 0號單元未用
for(p=HT+1,i=1;i=n;++i,++p,++w)
{
(*p).weight=*w;
(*p).parent=0;
(*p).lchild=0;
(*p).rchild=0;
} //2. 生成HT數(shù)組的前n個元素
for(;i=m;++i,++p)
(*p).parent=0; //3. 將n+1到2n-1個元素的parent初始化為0
for(i=n+1;i=m;++i) // 建赫夫曼樹
{ // 在HT[1～i-1]中選擇parent為0且weight最小的兩個結(jié)點，其序號分別為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;
} //4. 建立n+1到2n-1個元素
// 從葉子到根逆向求每個字符的赫夫曼編碼
HC=(HuffmanCode)malloc((n+1)*sizeof(char*));
// 分配n個字符編碼的頭指針向量([0]不用)
cd=(char*)malloc(n*sizeof(char)); // 分配求編碼的工作空間
cd[n-1]='\0'; // 編碼結(jié)束符
for(i=1;i=n;i++)
{ // 逐個字符求赫夫曼編碼
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';
HC[i]=(char*)malloc((n-start)*sizeof(char));
// 為第i個字符編碼分配空間
strcpy(HC[i],cd); // 從cd復(fù)制編碼(串)到HC
}
free(cd); // 釋放工作空間
}
// 實現(xiàn)算法6.13的程序
void HuffmanCoding2(HuffmanTree HT,HuffmanCode HC,int *w,int n) // 前半部分為算法6.12
{ // w存放n個字符的權(quán)值(均0)，構(gòu)造赫夫曼樹HT，并求出n個字符的赫夫曼編碼HC
int m,i,s1,s2; // 此句與algo6-1.cpp不同
unsigned c,cdlen; // 此句與algo6-1.cpp不同
HuffmanTree p;
char *cd;
if(n=1)
return;
m=2*n-1;
HT=(HuffmanTree)malloc((m+1)*sizeof(HTNode)); // 0號單元未用
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).parent=0;
for(i=n+1;i=m;++i) // 建赫夫曼樹
{ // 在HT[1～i-1]中選擇parent為0且weight最小的兩個結(jié)點，其序號分別為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;
}
// 以下為算法6.13，無棧非遞歸遍歷赫夫曼樹，求赫夫曼編碼，以上同算法6.12
HC=(HuffmanCode)malloc((n+1)*sizeof(char*));
// 分配n個字符編碼的頭指針向量([0]不用)
cd=(char*)malloc(n*sizeof(char)); // 分配求編碼的工作空間
c=m;
cdlen=0;
for(i=1;i=m;++i)
HT[i].weight=0; // 遍歷赫夫曼樹時用作結(jié)點狀態(tài)標(biāo)志
while(c)
{
if(HT[c].weight==0)
{ // 向左
HT[c].weight=1;
if(HT[c].lchild!=0)
{
c=HT[c].lchild;
cd[cdlen++]='0';
}
else if(HT[c].rchild==0)
{ // 登記葉子結(jié)點的字符的編碼
HC[c]=(char *)malloc((cdlen+1)*sizeof(char));
cd[cdlen]='\0';
strcpy(HC[c],cd); // 復(fù)制編碼(串)
}
}
else if(HT[c].weight==1)
{ // 向右
HT[c].weight=2;
if(HT[c].rchild!=0)
{
c=HT[c].rchild;
cd[cdlen++]='1';
}
}
else
{ // HT[c].weight==2，退回
HT[c].weight=0;
c=HT[c].parent;
--cdlen; // 退到父結(jié)點，編碼長度減1
}
}
free(cd);
}
void main()
{ // 主程序同algo6-1.cpp
HuffmanTree HT;
HuffmanCode HC;
int *w,n,i;
printf("請輸入權(quán)值的個數(shù)(1): ");
scanf("%d",n);
w=(int *)malloc(n*sizeof(int));
printf("請依次輸入%d個權(quán)值(整型):\n",n);
for(i=0;i=n-1;i++)
scanf("%d",w+i);
HuffmanCoding1(HT,HC,w,n);
for(i=1;i=n;i++)
puts(HC[i]); HuffmanCoding2(HT,HC,w,n);
for(i=1;i=n;i++)
puts(HC[i]); }
可以在Dog與Cat類中重寫Animal中的animalDo方法，通過調(diào)用animalDo方法，
然后會自動根據(jù)不同的實例調(diào)用不同類中的方法（多態(tài)知識）。
手打的,你最好編譯一下以免我哪里敲錯了
(百度不能顯示行首空格真是不爽)
//哈夫曼樹和~編碼的存儲表示
typedef struct{
unsigned int weight;//權(quán)值
unsigned int parent,lchild,rchild;
}HTNode, *HuffmanTree;//動態(tài)分配數(shù)組存儲哈夫曼樹
typedef char * *HuffmanCode;//動態(tài)分配數(shù)組存儲哈夫曼編碼表
void HoffmanCoding(HuffmanTree HT,HuffmanCode HC,int *w,int n){
//w存放n個字符的權(quán)值(均0),構(gòu)造哈夫曼樹HT,并求出n個字符的哈夫曼編碼HC
if (n=1) return;
m=2*n-1;
HT=(HuffmanTree) malloc ((m+1)*sizeof(HTNode));//0號單元未采用
for (p=HT,i=1;i=n;++i,++p,++w) *p={*w,0,0,0};
for (;i=m;++i;++p) *p={0,0,0,0}
for (i=n+1;i=m;++i){//建哈夫曼樹
//在HT[1..i-1]選擇parent為0且weight最小的兩個結(jié)點編號分別為s1,s2
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 *));//分配n個字符編碼的頭指針向量
cd=(char *)malloc(n*sizeof(char));//分配求編碼的工作空間
cd[n-1]="\0";//編碼結(jié)束符
for (i=1;i=n;++i){//逐個字符求哈夫曼編碼
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";
HC[i]=(char *)malloc((n-start)*sizeof(char));//為第i個字符編碼分配空間
strcpy(HC[i],cd);//從cd復(fù)制編碼(串)到HC
}
free(cd);//釋放工作空間
}//HuffmanCoding
真懶啊你真懶啊你真懶啊你真懶啊你真懶啊你真懶啊你真懶啊你真懶啊你真懶啊你真懶啊你
重慶分公司
重慶分公司
