吴尊电视剧全集:26个字母的HUFFMAN建立和编码器的实现

//你稍加修改频度数据即可
//本程序根据26个英文字母出现的频度，得到了它们的一种哈夫曼编码方案
//by jirgal 2005.4.18
#include<iostream.h>
#include<iomanip.h>
#define NUM 26 //字母数
#define TNUM 51 //
#define LTH 15 //编码最大长度

class Node
{
public:
char data;
int weight;
int parent;
int lchild;
int rchild;
};

void main()
{
char ch[NUM]={'a','b','c','d','e','f','g','h','i','j','k','l',
'm','n','o','p','q','r','s','t','u','v','w','x','y','z'};//26个字母

int weit[NUM]={856,139,279,378,1304,289,199,528,627,13,42,
339,249,707,797,199,12,677,607,1045,249,92,149,17,199,8};//出现频率

Node nodes[TNUM]; //用对象数组存储哈夫曼树

int i,j,one,two,a,b;
int hc[NUM][LTH]; //用于存储编码
int m,n;

//初始化数组
for(i=0;i<NUM;i++)
{
nodes[i].data=ch[i];
nodes[i].weight=weit[i];
nodes[i].parent=-1;
nodes[i].lchild=-1;
nodes[i].rchild=-1;
}
for(i=NUM;i<TNUM;i++)
{
nodes[i].data='@';
nodes[i].weight=-1;
nodes[i].parent=-1;
nodes[i].lchild=-1;
nodes[i].rchild=-1;
}

//建立哈夫曼树
for(i=NUM;i<TNUM;i++)
{
a=b=-1;
one=two=10000; //最大权数
for(j=0;j<i;j++)
{
if(nodes[j].parent==-1)
{
if(nodes[j].weight<=two)
{
one=two;
two=nodes[j].weight;
a=b;
b=j;
}
else if(nodes[j].weight>two&&nodes[j].weight<=one)
{
one=nodes[j].weight;
a=j;
}
}
}//for语句得到 parent=-1(即尚没有父结点)且weight最小的两个结点
nodes[a].parent=i;
nodes[b].parent=i;
nodes[i].lchild=a;
nodes[i].rchild=b;
nodes[i].weight=nodes[a].weight+nodes[b].weight;
}

//初始化hc
for(i=0;i<LTH;i++)
{
for(j=0;j<NUM;j++)
{
hc[j][i]=7;
}
}

//编码
for(i=0;i<NUM;i++)
{
j=LTH-1;
for(m=i,n=nodes[i].parent;m!=-1;m=n,n=nodes[n].parent)
{
if(nodes[n].lchild==m)
{
hc[i][j]=0;
}
else
{
hc[i][j]=1;
}
j--;
}

}

//输出 nodes
cout<<"HuffmanTree:"<<endl;
cout<<setw(4)<<"NO."<<setw(6)<<"data"<<setw(8)<<"weight"<<setw(6)
<<"parnt"<<setw(6)<<"lchd"<<setw(6)<<"rchd"<<endl;
for(i=0;i<TNUM;i++)
{
cout<<setw(4)<<i<<setw(6)<<nodes[i].data<<setw(8)<<nodes[i].weight<<setw(6)
<<nodes[i].parent<<setw(6)<<nodes[i].lchild<<setw(6)<<nodes[i].rchild<<endl;
}

//输出编码
cout<<endl<<"Result:"<<endl;
cout<<setw(6)<<"char"<<setw(10)<<"frequency"<<setw(16)<<"huffmancode\n";
for(i=0;i<NUM;i++)
{
cout<<setw(6)<<ch[i]<<setw(8)<<weit[i];
cout<<" ";
for(j=0;j<LTH;j++)
{
if(hc[i][j]!=7)
{
cout<<hc[i][j];
}
}
cout<<endl;
}
cout<<"\nDone.\n"<<endl;
}

//我们也做过这样的作业，直接编译即可执行，（C＋＋实现）
#include <iostream>
#include <string>
using namespace std;
typedef struct{
char lett;
int freq;
int parent,left,right;
}ELEM,*HuffmanTree;
typedef char **HuffmanCode;
void Select(HuffmanTree,int,int&,int&); //find min
void Create(HuffmanTree &ht,int *frq,char *s,int n)
{
int i,m;
int s1,s2;
HuffmanTree p;
m=2*n-1; //create 2*n-1 nodes for n charactors
ht=(HuffmanTree)malloc((m+1)*sizeof(ELEM));//assign memory
for(p=ht+1,i=1;i<=n;i++,p++,frq++,s++) {//initialize huffman trees
p->lett=*s;
p->freq=*frq;
p->parent=p->left=p->right=0;
}
for(i=n+1;i<=m;++i,++p){
p->freq=p->parent=p->right=p->left=0;
}
for(i=n+1;i<=m;++i)
{
Select(ht,i-1,s1,s2); // find the minvalue fromHT[1...i-1],s1,s2
ht[s1].parent=ht[s2].parent=i;
ht[i].freq=ht[s1].freq+ht[s2].freq;
ht[i].left=s1;
ht[i].right=s2;
}
}
void Coding(HuffmanTree ht,HuffmanCode &hc,int n){
int i,c,f,start;
char *cd;
hc=new char *[n+1];
cd=new char [n];
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].left==c) cd[--start]='0'; //left:'0'
else cd[--start]='1'; //right:'1'
hc[i]=new char [n-start];
strcpy(hc[i],&cd[start]);
}
free(cd);
}
void Select(HuffmanTree ht,int i,int&s1,int&s2){
unsigned int sm1 , sm2; // using for compare of the frequency
s1 = 1;
s2 = 1;
int m=0; // temp minimum frequency
for(m=1;m<=i;m++)
{
if(ht[m].parent!=0) continue;
else
{
sm1=ht[m].freq;
s1=m;
break;
}
}
for(int j=m+1;j<=i;j++)
{
if(ht[j].parent!=0) continue;
else
{
if(sm1>ht[j].freq)
{
sm1=ht[j].freq;
s1=j;
}
}
}
for(m=1;m<=i;m++)
{
if(ht[m].parent!=0) continue;
else
{
sm2=ht[m].freq;
s2=m;
if(s2==s1) continue;
else break;
}
}
for(int k=m+1;k<=i;k++)
{

if(ht[k].parent!=0) continue;
else
{
if((ht[k].freq<sm2)&&(k!=s1))
{
sm2=ht[k].freq;
s2=k;
}
}
}
}
void View(HuffmanTree ht,HuffmanCode hc, char *c,int n){
//view the code table
int i;
for(i=1;i<=n;i++){
cout<<ht[i].lett<<"---"<<hc[i]<<endl;
}
cout<<endl;
}
void Encode(HuffmanTree ht,HuffmanCode hc,string s,int n){
//make a string to codes
int m=s.length();
for(int i=0;i<m;i++){
for(int j=0;j<n;j++){
if(s.at(i)==ht[j+1].lett)
cout<<hc[j+1];
}
}cout<<endl;
}
void Decode(HuffmanTree ht,HuffmanCode hc,string s1,int n)
{
int k=s1.length();
int i=0,m;
while(i!=k){
m=2*n-1;
while(ht[m].left!=0&&ht[m].right!=0){
if(s1[i]=='0')m=ht[m].left;
else if(s1[i]=='1')m=ht[m].right;
i++;
}
cout<<ht[m].lett;
}
cout<<endl;
}
void line() {cout<<"--------------------------------------------------------------"<<endl;}
void showMenu(){
line();
cout<<"----------------------*Huffman Tree*--------------------------"<<endl;
cout<<"----------------designed by FuYuandi 2005.11.20---------------"<<endl;
line();
cout<<" 1.Create Huffman Tree"<<endl;
cout<<" 2.View Huffman Tree"<<endl;
cout<<" 3.Encode String"<<endl;
cout<<" 4.Decoding"<<endl;
cout<<" 0.exit this program"<<endl;
line();
}
void showTip(){
line();
cout<<"done successfully---------------------select 0 to 4 to continue"<<endl<<"\x1A";
}

int main(){
HuffmanTree ht;
HuffmanCode hc;
int n; //number of charactor
int *frq;//frequency
string i="-1";
string s,s1;
char *c;
int k=1;
showMenu();
cout<<"select 0 to 4 above for operation!\nTree has not been initialized,you must choose '1'at first!"<<endl;
line();
cout<<"\x1A";
cin>>i;
while(i!="0")
{ if(i=="1")
{ system("cls");
showMenu();
cout<<"you have chosen 1,now it will create a tree"<<endl;
cout<<"input total charactor number:"<<endl;
line();
cout<<"\x1A";
cin>>n;
frq=new int [n];
c=new char [n];
for(int i=0;i<n;i++){
system("cls");
showMenu();
cout<<"input charactor "<<i+1<<endl;
line();
cout<<"\x1A";
cin>>c[i];
system("cls");
showMenu();
cout<<"input frequency "<<i+1<<endl;
line();
cout<<"\x1A";
cin>>frq[i];
}
Create(ht,frq,c,n); //create huffman tree
Coding(ht,hc,n); //coding
showTip();
}
else if(i=="2")
{system("cls");
showMenu();
cout<<"you have chosen 2,the code table is:"<<endl;
line();
View(ht,hc,c,n);
showTip();
}

else if(i=="3")
{system("cls");
showMenu();
cout<<"you have chosen 3,please in put a string for coding"<<endl;
cout<<"input the string"<<endl;
line();
cout<<"\x1A";
cin>>s;
cout<<"after encode the result is : "<<endl;
line();
Encode(ht,hc,s,n);
showTip();
}

else if(i=="4")
{system("cls");
showMenu();
cout<<"you have chosen 4,please input codes for decoding"<<endl;
cout<<"input the codes"<<endl;
line();
cout<<"\x1A";
cin>>s1;
cout<<"after decode the result is : "<<endl;
line();
Decode(ht,hc,s1,n);
showTip();
}
else {
system("cls");
showMenu();
cout<<"invalid input,please input again!"<<endl;
line();
cout<<"\x1A";
}
cin>>i;
system("cls");
}
return 0;
}

program huffman (input,output,hcdfile,hyanfile);
{设计哈夫曼编码，hcdfile,hyanfile分别存放编码和字符。}
const n=26;
{26为26个英文字母，m为2*n-1}
type sqlist=record
chan: char;
num:integer
end;
{数组单元,chan存放字符，num存放字符个数}
linklist=^linlist;
linlist=record
chan:char;
num:integer;
next:linklist
end;
linklisttp=linklist;
sqlisttp=array[1..n]of sqlist;
var
hyanfile:FILE of char;
hcdfile:FILE of codetype;
LL:sqlisttp;
LA:linklist;
HCD:hufcode;
Procedure CRT_list(L:sqlisttp);
var
ch:char;
j1,i:integer;
L:sqlisttp;
begin
j1:=0;
for i:=1 to 26 do
begin
L[i].num:=0;
L[i].chan:=chr(i+96);
end;
read(ch);
while ch<>'!' do
begin
if( ch>='A') and( ch<='Z')
then
begin
ch:=chr(ord(ch)+32) ;
if ch=L[ord(ch)-96].chan
then L[ord(ch)-96].num:=L[ord(ch)-96].num+1 ;
end
else
begin
if ch=L[ord(ch)-96].chan
then L[ord(ch)-96].num:=L[ord(ch)-96].num+1;
end;
read(ch)
end;

for i:=1 to 26 do
begin
write(L[i].chan,':',L[i].num:5);
if i mod 3=0
then writeln ;
j1:= j1+L[i].num;
end;
writeln(j1);
end.
Procedure CRT_linklist(var la:linklisttp);
var
i,j:integer;
L:sqlisttp;
p:linklist;
begin
CRT_list(L);
j:=0;
new(la);
la^.next:=nil;
for i:=n downto 1 do
begin
if L[i].num<>0
then begin
new(p);
p^.chan:=L[i].chan;
p^.num:=L[i].num;
p^.next:=la^.next;
la^.next:=p;
j:=j+1
end;
end;
write('Bu xiang tong zi fu ge shu wei:',j)
end;
Procedure Print_linklist(la:linklisttp);
var
p:linklist;
begin
p:=la^.next;
while p<>nil do
begin
writeln(la^.chan, ':',la^.num);
p:=p^.next
end
end;
Function Lengh_linklisttp(la:linklisttp):integer;
var
p:linklist;
o:integer;
begin
p:=la^.next;
while (p<>nil) do
begin
p:=p^.next;
o:=o+1
end;
Lengh_linklisttp:=o
end;
procedure Select_mint(i:integer; var s1,s2:integer);
var
s,min1,min2,k,o,j:integer;
ht:huftree;
la:linklist;
begin
CRT_linklist(la);
Print_linklist(la);
o:=Lengh_linklist(la);
if (i<1) or(i>o)
then write('The number is not excepted.')
else begin
min1:=ht[1].weight;
for j:=3 to o do
begin
if min1>ht[j].weight
then
begin
min1:=ht[j].weight;
s1:=j
end
end;
min2:=ht[2].weight;
for k:=3 to s1-1 do
begin
if(min2>ht[k].weight) and (ht[k].parent=0)
then
begin
min2:=ht[k].weight;
s2:=k
end
end;
for s:=1 to o-s1 do
begin
if(min2>ht[s].weight) and (ht[s].parent=0)
then
begin
min2:=ht[s].weight;
s2:=s
end
end
end
end;
Procedure CRT_huftree (var ht:huftree);
nodetype=record
cha:char;
weight:integer;
parent,lch,rch:0..n
end;
bit=0..1;
codetype=record
bits:array[1..n] of bit;
start:1..n;
end;
hufcode=array[1..Lengh_linklisttp(la:linklisttp)]of codetype;
huftree=array[1..(2*Lengh_linklisttp(la:linklisttp))]of nodetype;
var
s1,s2 ,i, j,o:integer;
q:linklist;
la:linklisttp;
begin
j:=Lengh_linklisttp(la);
o:=2*j-1;
for i:=1 to(o) do
begin
ht[i].parent:=0;
ht[i].lch:=0;
ht[i].rch:=0
end;
new(q);
q:=la^.next;
for i:=1 to j do
begin
ht[i].weight:=q^.num;
ht[i].cha:=q^.chan;
q:=q^.next;
end;
for i:=j+1 to o do
begin
Select_mint(i-1,s1,s2);
ht[s1].parent:=i;
ht[s2].parent:=i;
ht[i].lch:=s1;
ht[i].rch:=s2;
ht[i].weight:=ht[s1].weight+ht[s2].weight
end
end;
Procedure Get_hufcode(var hcd:hufcode);
var
i,j,c,f:integer;
la:linklisttp;
ht:huftree;
cd:codetype;
begin
j:=Lengh_linklisttp(la);
rewrite(hcdfile);
rewrite(hyanfile);
for i:=1 to j do
begin
cd.start:=j;
c:=i;
f:=ht[c].parent;
while f<>0 do
begin
if ht[f].lch=c
then cd.bits[cd.start]:=0
else cd.bits[cd.start]:=1;
cd.start:=cd.start-1;
c:=f;
f:=ht[f].parent
end;
hcd[i]:=cd;
write (hcdfile,hcd[i]);
write(hyanfile,ht[f].cha)
end;
end;
Procedure Print_hufcode(la:linklisttp);
var
i:integer;
hcd:array[1..n] of codetype;
begin
reset(hyanfile);
reset(hcdfile);
for i:=1 to (Lengh_linklisttp(la)) do
begin
read(hcdfile,hcd[i]);
write(hcdfile,hcd[i])
end
end;
{以下为主程序}
begin
CRT_list(LL);
CRT_linklist(LA);
GET_hufcode(HCD);
Print_hufcode(LA)
end.