Huffman树与Huffman树编码算法

实验七Huffman树与Huffman树编码算法实验(4学时)*数学与软件科学学院实验报告学期：2011至2012第1学期2012年5月12日课程名称:数据结构专业:信息与计算科学班级2010级5班实验编号：实验七实验项目Huffman树与Huffman树编码算法实验指导教师**姓名：**学号：201**实验成绩：实验名称：Huffman树与Huffman树编码算法实验实验目的：掌握Huffman树的编码方法和算法实现。实验内容：(类C算法的程序实现)(1)建立Huffman树编码的表示结构，对给定输入信息集合进行Huffman编码，输出编码结果(必做)(2)利用Huffman编码算法实现给定信息串的编码结果(必做)实验准备：1)计算机设备；2)程序调试环境的准备，如TC环境；3)实验内容的算法分析与代码设计与分析准备。实验步骤：（1）算法思想对于随机输入的一串字符1统计字符串中各类字符。2统计各类字符在字符串中的个数3创建haffman树。4字符进行huffman编码。5输出字符串的haffman编码。（2）设计算法的数据结构1）/*数据结构*/typedefstructHTTree{DataTypeweight;/*字符的个数*/intflag;/*标记元素*/charname;/*字符名字*/intparents,leftChild,rightChild;/*父亲结点、子节点*/}HTNode,*HuffmanTree;（3）算法基本操作和描述1）统计字符串中各类字符，统计各类字符在字符串中的个数。*函数*/intIpChar(char*a,int**a1,char*b){/*统计字符串中元素的种类*/intt=0,i=0,h=0,n=0;while(a[t]!='\0'){for(i=0;it;i++){if(a[t]==a[i])break;}if(i==t){h++;b[n]=a[t];/*将元素种类放到静态数组中*/printf(%c,b[n]);n++;}t++;}b[n]='\0';/*printf(\n%d\n,h);*/*a1=(int*)malloc((h+1)*sizeof(int));for(i=1;i=h;i++){(*a1)[i]=0;}i=0;t=0;while(b[i]!='\0'){for(t=0;a[t]!='\0';t++){if(b[i]==a[t])(*a1)[i+1]++;/*统计各类元素在字符串中元素的个数*/}i++;}/*for(i=1;i=h;i++){printf(%d,(*a1)[i]);}*/printf(\n\n);returnh;}2）创建haffman树。voidCreatHT(HTNode**p,intn){/*创建Huffman树*/inti;intt;intS1,S2;for(i=n+1;i2*n;i++){t=Select(p,i,&S1,&S2);/*寻找p中i个数中最小的两个数的序号S1和S2，并返回parents的weight为0的序号，且S1S2*/(*p)[S1].parents=t;(*p)[S2].parents=t;/*将返回第一个weight为0的序号，作为S1和S2的父节点。S1作为左节点，S2作为右节点*/(*p)[t].leftChild=S1;(*p)[t].rightChild=S2;(*p)[t].weight=(*p)[S1].weight+(*p)[S2].weight;/*S1、S2的weight之和作为父节点的weight*/}}3）字符进行huffman编码、输出字符串的haffman编码。intHTencod(charw[],charh[],HTTree*p,intn){char*cd;char**HC;inti=1,a,b,t;intstart=1;cd=(char*)malloc(n*sizeof(char));/*存储编码字符串的数组*/HC=(char**)malloc((n+1)*sizeof(char*));/*存储每个字符的编码数组*/cd[n-1]='\0';printf(Haffmanbianma::\n);for(i=1;i=n;i++){start=n-1;for(a=i,b=p[a].parents;b;a=b,b=p[b].parents)/*从根节点开始遍历，找出根结点的父节点，子节点为父节点的右儿子则编码为‘1’，左二子编码为‘0’*/{if(p[b].leftChild==a)cd[--start]='0';elsecd[--start]='1';}HC[i]=(char*)malloc((n-start)*sizeof(char));/*为每个字母的编码分配存储空间*/strcpy(HC[i],&cd[start]);printf(%c:%s\n,p[i].name,HC[i]);/*输出每一个字母的haffman编码*/}printf(\n\noutputHuaffmanbianma::\n);for(i=0;istrlen(w);i++){for(t=1;t=n;t++){if(w[i]==h[t-1])printf(%s,HC[t]);/*输出haffman编码*/}}returnok;}4）原程序代码。#includestdio.h#includestdlib.h#includemalloc.h#includestring.h/*宏定义*/#defineok1#defineTRUE1#defineFALSE0#defineERROR-1#defineoverflow-2#definemax100/*替换*/typedefintStatus;typedefintDataType;/*数据结构*/typedefstructHTTree{DataTypeweight;intflag;charname;intparents,leftChild,rightChild;}HTNode,*HuffmanTree;/*函数*/intIpChar(char*a,int**a1,char*b){/*统计字符串中元素的种类*/intt=0,i=0,h=0,n=0;while(a[t]!='\0'){for(i=0;it;i++){if(a[t]==a[i])break;}if(i==t){h++;b[n]=a[t];/*将元素种类放到静态数组中*/printf(%c,b[n]);n++;}t++;}b[n]='\0';/*printf(\n%d\n,h);*/*a1=(int*)malloc((h+1)*sizeof(int));for(i=1;i=h;i++){(*a1)[i]=0;}i=0;t=0;while(b[i]!='\0'){for(t=0;a[t]!='\0';t++){if(b[i]==a[t])(*a1)[i+1]++;/*统计各类元素在字符串中元素的个数*/}i++;}/*for(i=1;i=h;i++){printf(%d,(*a1)[i]);}*/printf(\n\n);returnh;}voidInitTree(DataType*a,intn,HTNode**p,char*h){/*初始化Huffman树*/inti;*p=(HuffmanTree)malloc((2*n)*sizeof(HTNode));for(i=1;i=2*n;i++){if(i=n)/*将所有1...n的weight赋为a[1...n]*/{(*p)[i].weight=a[i];(*p)[i].flag=0;(*p)[i].name=h[i-1];(*p)[i].leftChild=0;(*p)[i].rightChild=0;(*p)[i].parents=0;}else/*将所有在n...2*n的weight赋为0*/{(*p)[i].weight=0;(*p)[i].flag=0;(*p)[i].leftChild=0;(*p)[i].rightChild=0;(*p)[i].parents=0;}}}intSelect(HTNode**p,intn,int*a,int*b){/*返回线性表中第一个父节点为0的结点，并返回表中flag==0的两个最小的结点且ab*/inti;intmin1=100,min2=100;for(i=1;i=n;i++){if((*p)[i].weightmin1&&(*p)[i].weight!=0&&(*p)[i].flag==0){min1=(*p)[i].weight;*a=i;}}(*p)[(*a)].flag=1;for(i=1;i=n;i++){if((*p)[i].weightmin2&&(*p)[i].weight!=0&&(*p)[i].flag==0){min2=(*p)[i].weight;*b=i;}}(*p)[(*b)].flag=1;for(i=1;i=n;i++){if((*p)[i].weight==0){break;}}returni;}voidCreatHT(HTNode**p,intn){/*创建Huffman树*/inti;intt;intS1,S2;for(i=n+1;i2*n;i++){t=Select(p,i,&S1,&S2);/*寻找p中i个数中最小的两个数的序号S1和S2，并返回parents的weight为0的序号，且S1S2*/(*p)[S1].parents=t;(*p)[S2].parents=t;/*将返回第一个weight为0的序号，作为S1和S2的父节点。S1作为左节点，S2作为右节点*/(*p)[t].leftChild=S1;(*p)[t].rightChild=S2;(*p)[t].weight=(*p)[S1].weight+(*p)[S2].weight;/*S1、S2的weight之和作为父节点的weight*/}}voidshow(HTTree*p,intn){inti;printf(OutputHuaffman'sweight::\n);for(i=1;i2*n;i++){printf(p[%d].weight=%d\n,i,p[i].weight);/*输出每个结点的权值*/}printf(\n\n);}intHTencod(charw[],charh[],HTTree*p,intn){char*cd;char**HC;inti=1,a,b,t;intstart=1;cd=(char*)malloc(n*sizeof(char));HC=(char**)malloc((n+1)*sizeof(char*));cd[n-1]='\0';printf(Haffmanbianma::\n);for(i=1;i=n;i++){start=n-1;for(a=i,b=p[a].parents;b;a=b,b=p[b].parents)/*从根节点开始遍历，找出根结点的父节点，子节点为父节点的右儿子则编码为‘1’，左二子编码为‘2’*/{if(p[b].leftChild==a)cd[--start]='0';elsecd[--start]='1';}HC[i]=(char*)malloc((n-start)*sizeof(char));/*为每个字母的编码分配存储空间*/strcpy(HC[i],&cd[start]);printf(%c:%s\n,p[i].name,HC[i]);/*输出每一个字母的haffman编码*/}printf(\n\noutputHuaffmanbianma::\n);for(i=0;istrlen(w);i++){for(t=1;t=n;t++){if(w[i]==h[t-1])printf(%s,HC[t]);/*输出haffman编码*/}}returnok;