哈夫曼编码毕业论文

1.哈夫曼编码压缩概念的基本思想?如何回答(精简的说)

A,e的出现概率很高，而z的出现概率则最低，该方法完全依据字符出现概率来构造异字头的平均长 度最短的码字，有时称之为最佳编码，一般就叫作Huffman编码，这便使编码之后的字符串的平均期望长度降低，从而达到无损压缩数据的目的）。

二者相比，e使用了一般编码的1/。 以哈夫曼树─即最优二叉树。

倘若我们能实现对于英文中各个字母出现概率的较准确的估算。这一术语是指使用一张特殊的编码表将源字符（例如某文件中的一个符号）进行编码，带权路径长度最小的二叉树，经常应用于数据压缩。

在计算机信息处理中，哈夫曼编码是可变字长编码（VLC）的一种。 Huffman于1952年提出一种编码方法。

这张编码表的特殊之处在于，它是根据每一个源字符出现的估算概率而建立起来的（出现概率高的字符使用较短的编码，反之出现概率低的则使用较长的编码.Huffman发展起来的。 例如，在英文中；8的长度，z则使用了3倍多。

这种方法是由David。当利用哈夫曼编码对一篇英文进行压缩时，e极有可能用一个位（bit）来表示，而z则可能花去25个位（不是26）。

用普通的表示方法时，每个英文字母均占用一个字节（byte），即8个位，“哈夫曼编码”是一种一致性编码法（又称"熵编码法"），用于数据的无损耗压缩哈夫曼编码（Huffman Coding）是一种编码方式，就可以大幅度提高无损压缩的比例。

2.数据结构课程设计题目

给你个大概的代码，把显示跟调用那里改改#include #include #include#include typedef struct { unsigned int weight; unsigned int parent,lchild,rchild,ch; }HTNode,*HuffmanTree； //动态分配数组存储哈夫曼树 typedef char *HuffmanCode； //动态分配数组存储哈夫曼编码表 int m,s1,s2; HuffmanTree HT;void Select(int n){ //选择两个权值最小的结点int i,j; for(i=1;iHT[i]。

weight)&&(!HT[i]。parent)&&(s2!=i)){ s1=i; } } for(j=1;jHT[j]。

weight)&&(!HT[j]。parent)&&(s1!=j)){ s2=j; } } } void HuffmanCoding(HuffmanCode HC[], int *w, int n) { // w存放n个字符的权值（均>0），构造哈夫曼树HT， // 并求出n个字符的哈夫曼编码HC int i, j; char *cd; int p; int cdlen;int start;if (n0;r--){ cout">a; while(a=='0'||a=='1'){ if(a=='0')i=HT[i]。

lchild; else if(a=='1') i=HT[i]。rchild; if(HT[i]。

lchild==0){ cout>a; }}void main() { HuffmanTree HT;HuffmanCode *HC;int *w,n,i,j;char b,c;puts（"输入结点数："）； scanf("%d",&n); HC = (HuffmanCode *)malloc(n*sizeof(HuffmanCode)); w = (int *)malloc(n*sizeof(int)); printf（"输入%d个结点的权值 "，n）; for(i=0;i>b;j=(int)(b-64);while(j){ cout>b; j=(int)(b-64);}coutsystem("pause"); }。

3.哈夫曼编码与译码设计要求:针对字符集A及其各字符的频率值(可统

#include #include #include #include #define NN 10000#define M 2*NN-1#define IN 0#define OUT 1#define MAX_INT 32767#define PRINTLN printf(" ");typedef struct{ int wi; char c; int tag; int parent, lchild, rchild;}huffmtype;typedef char* encodetype[NN 1];typedef struct{ char c; int times;}codetype;void PRINT(){ PRINTLN; printf(" Huffman编/译码器 ")； printf(" ==================== "); printf(" 1。

编码 2。译码 3。

退出 ")； printf（" >>选择："）；}FILE* OpenFile(char filename[20], char type[3]){ FILE *fp = NULL; if((fp = fopen(filename, type)) == NULL) exit(1); return fp;}int ReadCode(codetype* code, FILE* fp){ char c；//保存某次从文件中读入字符- int n = 1；//记录首次出现字符在数组中的下标- int i；//循环变量- int cnt = 1; int tag；//标志某次读入字符是否为首次出现字符，tag=1表示是首次出现；tag=0表示本次读入字符为已有字符 while((c = fgetc(fp)) != EOF）//当文件没有结束时读入字符- { //从fp指向文件中读取字符，存入字符变量c中- tag = 1；//假设本次读取字符为首次出现字符- for(i = 1; i { if(c == code[i]。 c)//如果本次读入字符为存储在下标为i已有字符- { code[i]。

times ；//权值加1- tag = 0；//标记本字符为已有字符- break；//在已有数组元素中找到本次读入字符，结束for（；；)循环- } } if(tag)//当本字符为首次出现字符时- { code[n]。 c = c；//把改字符存入n指向的数组单元中- code[n]。

times = 1；//记字符出现次数为1- n ;//n指向下一个数组地址- } } return n - 1；//返回文件中字符集合的元素个数-}void InitHuffmanTree(huffmtype* huffmtree, int real_n, int real_m)//初始化-{ int i; for(i = real_n; i { huffmtree[i]。 wi = 0; huffmtree[i]。

c = 0; huffmtree[i]。tag = IN; huffmtree[i]。

lchild = huffmtree[i]。 rchild = huffmtree[i]。

parent = 0; }}void ReadDataWeight_Init(huffmtype* huffmtree, codetype* code, int real_n)//获取权值及数值域值-{ int i; for(i = 1; i { huffmtree[i]。 wi = code[i]。

times; huffmtree[i]。c = code[i]。

c; huffmtree[i]。tag = IN; huffmtree[i]。

lchild = huffmtree[i]。 rchild = huffmtree[i]。

parent = 0; }}int LeastNode(huffmtype *huffmtree, int max_i)//找到最小权值节点地址-{ int i; int least_i; int max = MAX_INT; for(i = 1; i { if(huffmtree[i]。 wi { max = huffmtree[i]。

wi；//刷新max值- least_i = i；//保存当前节点地址- } } huffmtree[least_i]。 tag = OUT；//将最小权值节点从森林中移除- return least_i；//返回最小节点地址}void Slect(huffmtype *huffmtree, int max_i, int *x1, int *x2)//找到权值最小的两个节点，并将其下标值保存在x1,x2中-{ *x1 = LeastNode(huffmtree, max_i)；//计算合法最下权值下标- *x2 = LeastNode(huffmtree, max_i);//}void CreatHuffmanTree(huffmtype* huffmtree, int real_n, int real_m)//创建哈弗曼树-{ int i; int x1, x2; for(i = real_n 1; i { Slect(huffmtree, i-1, &x1, &x2)；//找到权值最小的两个节点，并将其下标值保存在x1,x2中- huffmtree[i]。

wi = huffmtree[x1]。wi huffmtree[x2]。

wi；//计算双气节点权值- huffmtree[x1]。parent = huffmtree[x2]。

parent = i；//计算双亲节点地址- huffmtree[i]。 lchild = x1; huffmtree[i]。

rchild = x2；//计算双亲节点左右孩子地址- }}void Encode(huffmtype *huffmtree, encodetype encode, int real_n)//依据已创建的HuffmanTree对字符进行编码-{ char *cd; int i; int start; int c, p; cd = (char*)malloc(real_n*sizeof(char));//cd用来存放某次运行时当前字符编码- cd[real_n - 1] = '。

4.你好!请问:对一幅图像进行哈夫曼编码,如何用MATLAB实现? 爱

给你一段程序，自己研究下吧！clcclearclose all；%定义HufData/Len为全局变量的结构体global HufData;global Lendisp（'计算机正在准备输出哈夫曼编码结果，请耐心等待……'）；%原始码字的灰度a=imread('kids。

tif')；%分区画出原始图像和灰度直方图figure;subplot(1,2,1)imshow(a)；%取消坐标轴和边框axis offbox offtitle('MATLAB自带图像'，'fontsize',13);subplot(1,2,2);axis offbox offimhist(a);title（'图像灰度直方图'，'fontsize',13）；%图像的灰度统计GrayStatistics=imhist(a);GrayStatistics=GrayStatistics';GrayRatioo=GrayStatistics/sum(GrayStatistics);GrayRatioNO=find(GrayRatioo~=0);Len=length(GrayRatioNO)；%初始化灰度集，防止系统随即赋予其垃圾值GrayRatio=ones(1,Len);for i=1:LenGrayRatio(i)=GrayRatioo(i); endGrayRatio=abs(sort(-GrayRatio)）；%将图像灰度概率赋予结构体for i=1:Len HufData(i)。 value=GrayRatio(i);end% 哈夫曼编码/霍夫曼编码HuffmanCode(Len)；%输出码字zippedHuffman=1;for i=1:Len tmpData=HufData(i)。

code; str=''; for j=1:length(tmpData) str=strcat(str,num2str(tmpData(j))); zippedHuffman=zippedHuffman 1; end disp(strcat('a',num2str(i),'= ',str))endi；%计算计算机一共输出多少个哈夫曼编码/霍夫曼编码zippedHuffman；%计算在删去0灰度级压缩之前的原始图像字节容量unzipped_delete=i*8；%计算压缩比率ratio_delete=zippedHuffman/unzipped_delete；%计算图像的压缩比率ad=num2str(ratio_delete*100);str2=strcat(ad,'%');disp(strcat（'哈夫曼编码压缩比率'，'= '，str2））%子程序：哈夫曼编码/霍夫曼编码函数HuffmanCode。 mfunction HuffmanCode(OriginSize)global HufData;global Lenfor i=1:Len %%霍夫曼编码树左边纪录为1 HufData(i)。

left=1； %%霍夫曼编码树右边纪录为0 HufData(i)。right=0； %%输出码初始化为0 HufData(i)。

code=[]； %%排序列表初始化 SortList(i)。symbol=i; SortList(i)。

value=HufData(i)。value;end%初始化原始消息数目newsymbol=OriginSize;for n=OriginSize:-1:2%将N个消息进行排序 SortList=sortdata(SortList,n)；%将最后两个出现概率最小的消息合成一个消息newsymbol=newsymbol 1;HufData(newsymbol)。

value=SortList(n-1)。value SortList(n)。

value;HufData(newsymbol)。left=SortList(n-1)。

symbol;HufData(newsymbol)。 right=SortList(n)。

symbol；%将消息添加到列队的最后，为N-1个消息重新排序作好准备SortList(n-1)。symbol=newsymbol;SortList(n-1)。

value=HufData(newsymbol)。value;end%遍历霍夫曼树，获得霍夫曼编码/哈夫曼编码visit(newsymbol,Len,[]);end%子程序：冒泡排序法函数sortdata。

m function reData=sortdata(SortList,n)%根据消息概率进行排序for k=n:-1:2 for j=1:k-1 min=SortList(j)。 value; sbl=SortList(j)。

symbol; if(min0) %遍历左分支接点输出1，这里采用子函数嵌套调用 ocode1=[ocode 1]; visit(HufData(node)。 left,n,ocode1); end if(HufData(node)。

right>0） %遍历右分支接点输出0，这里采用子函数嵌套调用 ocode2=[ocode 0]; visit(HufData(node)。 right,n,ocode2); endendend。

5.构造哈夫曼树并设计哈夫曼编码用C语言问题描述:已知每一个字符出

手打的，你最好编译一下以免我哪里敲错了 //哈夫曼树和~编码的存储表示 typedef struct{ unsigned int weight；//权值 unsigned int parent,lchild,rchild; }HTNode, *HuffmanTree；//动态分配数组存储哈夫曼树 typedef char * *HuffmanCode；//动态分配数组存储哈夫曼编码表 void HoffmanCoding(HuffmanTree &HT,HuffmanCode &HC,int *w,int n){ //w存放n个字符的权值（均>0），构造哈夫曼树HT，并求出n个字符的哈夫曼编码HC if (n 。

i-1]选择parent为0且weight最小的两个结点编号分别为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"；//编码结束符 for (i=1;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[start])；//从cd复制编码（串）到HC } free(cd)；//释放工作空间 }//HuffmanCoding 。

6.急

我编的一个哈夫曼树，你参考参考#include int m[15],z=0; /*code*/int i=0,js; /*ecode*/int e=53; /*ecode*/typedef struct hf{int l,r,p,w;}elem,*def；/*----------初始化-set------------*/set(def h){int w[27]={186,64,13,22,32,103,21,15,47,57,1,5,32,20,57,63,15,1,48,51,80,23,8,18,1,16,1};int i,j;h=(def)malloc(55*sizeof(elem));for(i=0;iw1&&h[i]。

w=0;n--){ j=j/2; if(m[n]==1) y=y-j; else y=y j; x =2; } /*if(s[x][y]==0){*/ if(h[i]。 l==0) s[x][y]=i 95; else s[x][y]=i;z=0;j=256;x=0;y=256;}for(i=0;i95) fprintf(fp,"%c",s[i][j]); else fprintf(fp,"%d",s[i][j]); } else fprintf(fp,"_");}fprintf(fp," ");}}/*--------------main------------*/main（){/* 定义各种变量 */def h;FILE *fp1,*fp2,*fp3,*fp,*fp5;int n,j,k=0;char ec;char a[27]；/* 读出tobetran中的字符 */h=set(h)； /*初始化*/create(h)； /*创建哈夫曼树*/print(h);fp3=fopen("tobetran。

txt","r");for(i=0;i=0;j--){ fprintf(fp1,"%d",m[j]); }fprintf(fp1," ");z=0;}fclose(fp1)；/*==========将codefile中的编码翻译成字符，并写入textfile中===*/j ;fp=fopen("textfile。 txt","w");fp5=fopen("cprint。

txt","w");while(k==0){ fscanf(fp2,"%c",&ec); e=ecode(ec,h); if(h[e]。 l==0){ if(e!=1) fprintf(fp,"%c",e 95); else fprintf(fp," "); js=1; } if(js==1) e=53；/*-------每行50个写入cprint。

txt--------*/ if(ec!=' ') fprintf(fp5,"%c",ec); j ; if(jP==0) fprintf(fp5," ");k=feof(fp2);}fclose(fp2);fclose(fp);}。

7.C++课程设计：哈夫曼编码器

#include #include #include #include #include //typedef int TElemType;const int UINT_MAX = 1000;typedef struct{ int weight; int parent, lchild, rchild;} HTNode, *HuffmanTree;typedef char **HuffmanCode;HuffmanTree HT;HuffmanCode HC;int *w, i, j, n;char *z;int flag = 0;int numb = 0;int min(HuffmanTree t, int i){int j, flag; int k = UINT_MAX; for (j = 1; j <= i; j++) if (t[j].weight < k && t[j].parent == 0) k = t[j].weight, flag = j; t[flag].parent = 1; return flag;}void select(HuffmanTree t, int i, int &s1, int &s2){int j; s1 = min(t, i); s2 = min(t, i); if (s1 > s2) { j = s1; s1 = s2; s2 = j; }}void HuffmanCoding(HuffmanTree &HT, HuffmanCode &HC, int *w, int n){int m, i, s1, s2, start; //unsigned c,f; int c, f; HuffmanTree p; char *cd; if (n <= 1) return ;m = 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->parent = 0; for (i = n + 1; i <= m; ++i){ 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; }HC = (HuffmanCode)malloc((n + 1) *sizeof(char*));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'; HC[i] = (char*)malloc((n - start) *sizeof(char)); strcpy(HC[i], &cd[start]); } free(cd); }void Initialization(){ flag = 1; int num; int num2; cout << " The initial hoffman linked list " << endl << "Please enter a number of nodes n:"; cin >> num; n = num; w = (int*)malloc(n *sizeof(int)); z = (char*)malloc(n *sizeof(char)); cout << "\n Please please input" << n << "\n Characters (character type) note: must end to enter:" << endl; char base[2]; for (i = 0; i < n; i++) { cout << " The first " << i + 1 << " characters:" << endl; gets(base); *(z + i) = *base; } for (i = 0; i <= n - 1; i++) { cout << setw(6) << *(z + i); } cout << "\n Please please input" << n << " A weights:" << endl; for (i = 0; i <= n - 1; i++) { cout << endl << " The first " << i + 1 << " A character metric:"; cin >> num2; *(w + i) = num2; } HuffmanCoding(HT, HC, w, n);cout << " Characters corresponding coding for:" << endl; for (i = 1; i <= n; i++) { //cout<<" characters "<<*(z+i-1)<<" coding "; puts(HC[i]); }cout << " Below will hoffman code written to the file " << endl << "。

.." << endl; FILE *htmTree; char r[] = { ' ', '\0' }; if ((htmTree = fopen("htmTree.txt", "w")) == NULL) { cout << "can not open file" << endl; return ; } fputs(z, htmTree); for (i = 0; i < n + 1; i++) { fprintf(htmTree, "%6d", *(w + i)); fputs(r, htmTree); } for (i = 1; i <= n; i++) { fputs(HC[i], htmTree); fputs(r, htmTree); } fclose(htmTree); cout << "Characters and corresponding coding has written to the root directory file htmTree.txt中" << endl << endl;}void InputCode(){ //cout<<" Please input your want to code of characters "< n) { cout << " Characters mistake, can't coding!" << endl; break; } } } } } cout << " Coding work" << endl << "Code written to the directory codefile.txt" << endl << endl; fclose(tobetran); fclose(codefile); free(tran);}void Decoding(){ cout << "To root directory file codefile.txt the characters of decode" << endl; FILE *codef, *txtfile; if ((txtfile = fopen("Textfile.txt", "w")) == NULL) { cout << " Cannot open file " << endl; } //txtfile=fopen("Textfile.txt","w"); if ((codef = fopen("codefile.txt", "r")) == NULL) { cout << " Cannot open file " << endl; } //codef=fopen("codefile.txt","r"); char *work, *work2, i2; int i4 = 0, i, i3; unsigned long length = 10000; work = (char*)malloc(length *sizeof(char)); fgets(work, length, codef); work2 = (char*)malloc(length *sizeof(char)); i3 = 2 * n - 1; for (i = 。

8.赫夫曼编码的设计与实现（C++）

哈弗曼树的构造和编码#include int n; class Huffcode { public: char std[20]; int start; }; class Huffman { public: int left; int right; int parent; char val; int weight; }; Huffcode q[20]; Huffman p[40]; //p=new Huffman [n]; void creatcode(Huffman *p) { int i; Huffcode d; // d.std=new char [n]; //q=new Huffcode [n]; //for(i=0;i>p[i].val>>p[i].weight; } for(int j=n;j<2*n;j++) { int temp1,temp2,l,r; temp1=temp2=32567; l=r=0; for(i=0;i>n;// p=new Huffman [n]; //k.getnum(); creat(); creatcode(p); display(); }。

9.题目：哈夫曼编码系统 设计任务：

#include #include #include #include #include #include using namespace std; struct HuffmanNode //哈夫曼树的一个结点 { int weight; int parent; int lchild,rchild; char sourcecode； //存放源文字符集里的一个字符，如'a' std::string code； //存放字符sourcecode对应的编码 }； class HuffmanTree //哈夫曼树 { private: HuffmanNode *Node; //Node[]存放哈夫曼树 int LeafNum； //哈夫曼树的叶子个数，也是源码个数 public: HuffmanTree(); ~HuffmanTree(); void CreateHuffmanTree(); void (); void (); void Encoder(); void Decoder(); void PrintCodeFile(); void PrintHuffmanTree(); void PrintHuffmanTree_aoru(int T,int layer=1)； }； ////////////////////////////////////////////////////////////////////////////// // 构造函数 // 函数功能：初始化哈夫曼树 //函数参数：无 //参数返回值：无 HuffmanTree::HuffmanTree() { Node=NULL; LeafNum=0； } ////////////////////////////////////////////////////////////////////////////// // 析构函数 // 函数功能：将哈夫曼的数组的空间释放 //函数参数：无 //参数返回值：无 HuffmanTree::~HuffmanTree() { delete[] Node； } ////////////////////////////////////////////////////////////////////////////// // 建立哈夫曼树函数 // 函数功能：建立哈夫曼树（调用键盘建立哈夫曼树或调用从文件建立哈夫曼树的函数） //函数参数：无 //参数返回值：无 void HuffmanTree::CreateHuffmanTree() { char Choose; cout<<"你要从文件中读入哈夫曼树（按1），还是从键盘输入哈夫曼树（按2）?"; cin>>Choose; if(Choose=='2') { //键盘输入建立哈夫曼树 (); }//choose=='2' else { //从哈夫曼树文件hfmTree.dat中读入信息并建立哈夫曼树 （)； } } ////////////////////////////////////////////////////////////////////////////// // 从键盘建立哈夫曼树函数 // 函数功能：从键盘建立哈夫曼树 //函数参数：无 //参数返回值：无 void HuffmanTree::(){ int Num; cout<<"\n请输入源码字符集个数："； cin>>Num; if (Num<=1) { cout<<"无法建立少于2个叶子结点的哈夫曼树。

\n\n"; return; } LeafNum=Num; Node=new HuffmanNode[2*Num-1]; for(int i=0;i>Node[i].weight； //源文的字符权重存入Node[].weight Node[i].parent=-1; Node[i].lchild=-1; Node[i].rchild=-1; Node[i].code="\0"; } for(int j=Num;j<2*Num-1;j++) {//循环建立哈夫曼树内部结点 int pos1,pos2; int max1,max2; pos2=pos1=j; max2=max1=numeric_limits::max（ )； //在所有子树的根结点中，选权重最小的两个根结点，pos1最后应指向权重最小的根结点的下标 //pos2最后应指向权重第二小的根结点的下标 //max1存放当前找到的权重最小的根结点的权重 //max2存放当前找到的权重第二小的根结点的权重 for(int k=j-1;k>=0;k--) { if (Node[k].parent==-1){//如果是某棵子树的根结点 if (Node[k].weight>ch; if (ch!='y'&&ch!='Y') return; ofstream fop; fop.open("hfmTree.dat",ios::out|ios::binary|ios::trunc)； //打开文件 if(fop.fail()) { cout<<"\n哈夫曼树文件打开失败，无法将哈夫曼树写入hfmTree.dat文件。

\n"; return; } fop.write((char*)&Num,sizeof(Num)）； //先写入哈夫曼树的叶子结点个数 for(int n=0;n<2*Num-1;n++) { //最后写入哈夫曼树的各个结点（存储在Node[]中） fop.write((char*)&Node[n],sizeof(Node[n])); flush(cout); } fop.close（)； //关闭文件 cout<<"\n哈夫曼树已成功写入hfmTree.dat文件。\n"； } ////////////////////////////////////////////////////////////////////////////// // 从文件建立哈夫曼树函数 // 函数功能：从文件建立哈夫曼树 //函数参数：无 //参数返回值：无 void HuffmanTree::(){ ifstream fip; fip.open("。

转载请注明出处众文网 » 哈夫曼编码毕业论文