Huffman编码完整代码-huffman编码c语言

时间:2017-05-05 14:04:30 C语言答案 我要投稿

Huffman编码完整代码-huffman编码c语言

  huffman编码是一种可变长编码方式,于1952年由huffman提出。依据字符在需要编码文件中出现的概率提供对字符的唯一编码,并且保证了可变编码的平均编码最短,被称为最优二叉树,有时又称为最佳编码。以下是由阳光网小编整理关于Huffman编码完整代码的内容,希望大家喜欢!

  Huffman编码完整代码

  //利用哈夫曼树进行编码,

  #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; //结点权值

  int parent,lchild,rchild; //结点的父指针,左右孩子指针

  }HTNode,*HuffmanTree;

  typedef char **HuffmanCode; //数组存储哈夫曼编码表

  void CreateHuffmanTree(HuffmanTree &,unsigned int*,int ); //生成哈夫曼树

  void HuffmanCoding(HuffmanTree,HuffmanCode &,int ); //哈夫曼树编码

  void PrintHuffmanCode(HuffmanCode,unsigned int*,int); //显示编码结果

  void Select(HuffmanTree,int,int&,int&); //在数组中寻找权值最小的两个结点

  void main()

  {HuffmanTree HT; //哈夫曼树HT

  HuffmanCode HC; //哈夫曼编码表HC

  int n,i; //n是哈夫曼树叶子结点数

  unsigned int *w; //w存放叶子结点权值

  cout<<"huffman编码使用说明"<<endl ; //使用说明

  cout<<"例如:输入需要进行编码的字符数目2"<<endl;

  cout<<"然后输入每个字符的权值(整数)"<<endl;

  cout<<"例如:5 29 "<<endl;

  cout<<"则构造一棵哈夫曼树,哈夫曼编码如下"<<endl;

  cout<<" 5---0"<<endl<< "29---1"<<endl;

  printf("请需要进行编码的字符数目:");

  scanf("%d",&n);

  w=(unsigned int*)malloc(n*sizeof(unsigned int));

  printf("输入每个字符的权值(整数):\n");

  for(i=0;i<n;i++) scanf("%d",&w[i]); //输入各字符出现的次数/权值

  CreateHuffmanTree(HT,w,n); //生成哈夫曼树

  HuffmanCoding(HT,HC,n); //进行编码

  PrintHuffmanCode(HC,w,n); //显示编码

  }

  void CreateHuffmanTree(HuffmanTree &HT,unsigned int *w,int n)

  {//构造哈夫曼树

  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)); //开辟空间

  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结点的父指针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)

  {//将哈夫曼树进行编码,所编的码存放在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'; //

  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;

  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且权值最小的两个结点,其序号分别为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放较小的序号

  {i=s1;s1=s2;s2=i;}

  }

  Huffman代码流程


看过“Huffman编码完整代码”的人还看了:

1.课后答案免费下载合集

2.神秘国度爱情故事完整代码(C语言)

【Huffman编码完整代码-huffman编码c语言】相关文章:

1.信息论与编码(陈运著)课后答案下载

2.编码技巧在统计学教学中的运用论文

3.信息论与编码(傅祖芸著)课后答案下载

4.信息论与编码理论(王育民著)课后答案下载

5.信息论与纠错编码(孙丽华著)课后答案下载

6.差错控制编码第2版(林舒著著)课后答案下载

7.c语言编程实习心得

8.c语言实习心得