huffman编码

  • m2_720345
    了解作者
  • 881.1KB
    文件大小
  • rar
    文件格式
  • 0
    收藏次数
  • VIP专享
    资源类型
  • 0
    下载次数
  • 2022-04-15 09:46
    上传日期
huffman编码(编码加解码三个),这个编码是信息论以及各种数据结构的实验,都有用的东西
huffman.rar
  • huffman
  • Debug
  • vc60.pdb
    108KB
  • 1.obj
    258.6KB
  • vc60.idb
    73KB
  • huffman.exe
    544.1KB
  • huffman.ilk
    784KB
  • huffman.pdb
    1.1MB
  • huffman.pch
    2MB
  • huffman.dsw
    522B
  • huffman.ncb
    33KB
  • huffman.opt
    47.5KB
  • huffman.dsp
    4.2KB
  • huffman.plg
    1.4KB
  • 1.cpp
    4.4KB
内容介绍
#include <iostream> #include <cstdlib> #include <string> using namespace std; typedef struct { unsigned int weight;//结点权值 unsigned int parent,lchild,rchild;//结点的父指针,左右孩子指针 }HTNode,*HuffmanTree;//动态分配数组存储哈夫曼树 typedef char **HuffmanCode;//动态分配数组存储哈夫曼编码表 HuffmanTree HT;//哈夫曼树HT HuffmanCode HC;//哈夫曼编码表HC unsigned int *w;//w存放叶子结点权值 void CreateHuffmanTree(HuffmanTree &,unsigned int*,int);//生成一棵哈夫曼树 void HuffmanCoding(HuffmanTree,HuffmanCode&,int);//对哈夫曼树进行编码 void PrintHuffmanCode(HuffmanCode,unsigned int*,int);//显示哈夫曼编码 void Select(HuffmanTree,int,int&,int&);//在数组中寻找权值最小的两个结点 int main() { int n,i; //n是哈夫曼树叶子结点数 char choose='y'; //用于选择程序是否退出 while(choose!='N' && choose!='n') { cout << "请输入叶子结点数目:"; do { cin >> n;//输入叶子结点数 cin.clear(); cin.ignore(); } while( n<=1 ); w=(unsigned int*)malloc(n*sizeof(unsigned int));//开辟空间存放权值 for(i=0;i<n;i++) { cout << "W" << i+1 << "的权值:"; cin >> w[i];//输入各叶子结点权值 } CreateHuffmanTree(HT,w,n);//生成哈夫曼树 HuffmanCoding(HT,HC,n);//进行哈夫曼编码 cout << endl; PrintHuffmanCode(HC,w,n);//显示哈夫曼编码 cout << "还要继续吗?(Y/N)"; cin >> choose; } system("pause"); return 0; } void CreateHuffmanTree(HuffmanTree &HT,unsigned int *w,int n) {//w存放n个结点的权值,将构造一棵哈夫曼树HT int i,m; int s1,s2; HuffmanTree p; if(n<=1) return; m=2*n-1;//n个叶子结点的哈夫曼树,有2*n-1个结点 HT=(HuffmanTree)malloc((m+1)*sizeof(HTNode));//开辟2*n各结点空间,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->weight=0; p->parent=0; p->lchild=0; p->rchild=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=i; HT[s2].parent=i;//修改s1和s2结点的父指针parent HT[i].lchild=s1; HT[i].rchild=s2;//修改i结点的左右孩子指针 HT[i].weight=HT[s1].weight+HT[s2].weight;//修改权值 } } void HuffmanCoding(HuffmanTree HT,HuffmanCode &HC,int n) { //将有n个叶子结点的哈夫曼树HT进行编码,所编的码存放在HC中 //方法是从叶子到根逆向求每个叶子结点的哈夫曼编码 int i,c,f,start; char *cd; HC=(HuffmanCode)malloc((n+1)*sizeof(char*));//分配n个编码的头指针向量 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';//若是左孩子编为'0' else cd[--start]='1';//若是右孩子编为'1' HC[i]=(char *)malloc((n-start)*sizeof(char));//为第i个编码分配空间 strcpy(HC[i],&cd[start]);//将编码从cd复制到HC中 } free(cd);//释放工作空间 } void PrintHuffmanCode(HuffmanCode HC,unsigned int *w,int n) { //显示有n个叶子结点的哈夫曼树的编码表 int i; cout << "哈夫曼编码如下:/n"; for(i=1;i<=n;i++) { cout << HC[i]<<"/t" <<"W"<<i<< "è¨?μ?a£o" <<w[i-1]<<endl; } cout<<endl; } void Select(HuffmanTree HT,int t,int&s1,int&s2) { //在HT[1...t]中选择parent不为0且权值最小的两个结点,其序号分别为s1和s2,s1存放最小的,s2存放次小的 int i=0; int j=0; int k=0; int least=0; int second=0; for(i=1;i<=t;i++) { if(HT[i].parent==0) break; } for(j=i+1;j<=t;j++) { if(HT[j].parent==0) break; } if(HT[i].weight<HT[j].weight) { least=i; second=j; } else { least=j; second=i; } for(k=j+1;k<=t;k++) { if(HT[k].parent==0) { if(HT[k].weight<HT[least].weight) { second=least; least=k; } else if(HT[k].weight>=HT[least].weight&&HT[k].weight<HT[second].weight) second=k; } } s1=least; s2=second; }
评论