数据结构哈弗曼编码实验

1、哈弗曼编码及译码代码#include "iostream.h"#include "math.h"#include "stdlib.h"#include <string.h>#define MAXSIZE 100 /最多子叶数#define MAXCODE 10000 /编码最大长度typedef struct char info; /关联字符信息 unsigned int weight; /每个节点的权职 unsigned int parent, lchild, rchild;HTNode,*HuffmanTree;typ

2、edef char *HuffmanCode; /存储哈弗曼编码void Select(HuffmanTree HT, int j,int &s1,int &s2)/选择双亲节点为0，并且最小的两个子叶节点 int i=1,m; while(HTi.parent!=0) i+; /找第一个双亲节点为0的子叶结点 for(s2=s1=i;i<j;i+) /保证s1中的权值最小，s2次小 if(HTi.parent=0 && HTi.weight<HTs1.weight) s2=s1; s1=i; else if(HTi.parent=0 &&a

3、mp; HTi.weight>=HTs1.weight && HTi.weight<=HTs2.weight) s2=i; while(HTi.parent=0 && s1=s2) m=i; m+; while(HTm.parent!=0) m+; s2=m; void HuffmanCoding(HuffmanTree &HT, HuffmanCode &HC, int *w, int n, char *info)/哈弗曼编码 int i,m; HuffmanTree p; if(n<1) return; m = 2*n-1;

4、 HT = (HuffmanTree)malloc(m+1)*sizeof(HTNode); for(p=HT+1,i=1;i<=n;+i,+p,+w,+info) /初始化所有已存在的子叶信息 p->info = *info; p->weight = *w; p->parent = 0; p->lchild = 0; p->rchild = 0; /for for(; i<=m;+i,+p) /构造所需要的过度根节点 p->weight = 0; p->parent = 0; p->lchild = 0; p->rchild

5、= 0; /for for(i=n+1;i<=m;+i) /建立哈弗曼树 int s1,s2; Select(HT,i-1,s1,s2); HTs1.parent =i; HTs2.parent =i; HTi.lchild = s2; HTi.rchild = s1; HTi.weight = HTs1.weight+HTs2.weight; /for /哈弗曼编码 HC = (HuffmanCode)malloc(n+1)*sizeof(char *); char* cd = (char*)malloc(n*sizeof(char); cdn-1 = '0' for(

6、i=1;i<=n;+i) int f; unsigned int c; int start=n-1; for(c=i,f=HTi.parent;f!=0;c=f,f=HTf.parent) if(HTf.lchild=c) cd-start = '0' else cd-start = '1' HCi=(char*)malloc(n-start)*sizeof(char); strcpy(HCi, &cdstart); /for free(cd);/HuffmanCodingvoid CheckCoding(HuffmanTree HT, Huffm

7、anCode HC, char *strcheck, int m)/查询哈弗曼编码信息/ char *strcopy=new charMAXCODE; for(int i=0; i<m; i+) for(int j=1; HT != strchecki; j+); cout<<HCj; cout<<endl;/CheckCodingvoid HuffmanTranslateCoding(HuffmanTree HT, int n,char*c)/译码过程 int m=2*n-1; int i,j=0; while(cj!='0') i=

8、m; while(HTi.lchild && HTi.rchild) if(cj='0') i=HTi.lchild; else if(cj='1') i=HTi.rchild; j+; cout<<HT; cout<<endl;void main() int n,*w,m; w=new intMAXSIZE; char *info; char *strcheck=new charMAXSIZE; info=new charMAXSIZE; char *ch=new charMAXSIZE; HuffmanTr

9、ee HT=new HTNodeMAXSIZE; HuffmanCode HC=NULL; cout<<"*"<<endl; cout<<"* HuffmanCode and HUffmanTranslate *"<<endl; cout<<"* 西安电子科技大学 计算机学院 030514班 *"<<endl; cout<<"* 学号： 03051433 制作人：王甲楼 *"<<endl; cout<<&qu

10、ot;*"<<endl; cout<<"读入叶子节点数 n= " cin>>n; for(int i=0; i<n;i+) cout<<"读入第"<<i+1<<"个叶子结点的权值：" cin>>wi; cout<<"读入编码字符: " cin>>infoi; HuffmanCoding( HT, HC, w, n,info); cout<<"读入要查询的字符串中字符个数:

11、 " cin>>m; cout<<"读入要编码的字符串: " cin>>strcheck; CheckCoding(HT,HC,strcheck,m); cout<<"读入编码: "<<endl; cin>>ch; HuffmanTranslateCoding(HT,n,ch); #include<stdio.h>#include<conio.h>#include<iostream.h>#include<string.h>#i

12、nclude<stdlib.h>#define MAXVALUE 10000 /*权值最大值*/#define MAXLEAF 30 /*叶子最多个数*/#define MAXNODE MAXLEAF*2-1 /* 结点数的个数*/#define MAXBIT 50 /*编码的最大位数*/typedef struct node /*结点类型定义*/ char letter; int weight; int parent; int lchild; int rchild;HNodeType;typedef struct /*编码类型定义*/ char letter; int bitMA

13、XBIT; int start;HCodeType;typedef struct /*输入符号的类型*/ char s; int num;lable;void HuffmanTree(HNodeType HuffNode,int n,lable a) int i,j,m1,m2,x1,x2,temp1; char temp2; for (i=0;i<2*n-1;i+) /*结点初始化*/ HuffNodei.letter=0; HuffNodei.weight=0; HuffNodei.parent=-1; HuffNodei.lchild=-1; HuffNodei.rchild=-1

14、; for (i=0;i<n-1;i+) for (j=i+1;j<n-1;j+) /*对输入字符按权值大小进行排序*/ if (aj.num>ai.num) temp1=ai.num; ai.num=aj.num; aj.num=temp1; temp2=ai.s; ai.s=aj.s; aj.s=temp2; for (i=0;i<n;i+) HuffNodei.weight=ai.num; HuffNodei.letter=ai.s; for (i=0;i<n-1;i+) /*构造huffman树*/ m1=m2=MAXVALUE; x1=x2=0; for

15、 (j=0;j<n+i;j+)/*寻找权值最小与次小的结点*/ if (HuffNodej.parent=-1&&HuffNodej.weight<m1) m2=m1; x2=x1; m1=HuffNodej.weight; x1=j; else if (HuffNodej.parent=-1&&HuffNodej.weight<m2) m2=HuffNodej.weight; x2=j; HuffNodex1.parent=n+i; HuffNodex2.parent=n+i; /*权值最小与次小的结点进行组合*/ HuffNoden+i.w

16、eight=HuffNodex1.weight+HuffNodex2.weight; HuffNoden+i.lchild=x1; HuffNoden+i.rchild=x2; void HuffmanCode(int n,lable a) HNodeType HuffNodeMAXNODE; HCodeType HuffCodeMAXLEAF,cd; int i,j,c,p; HuffmanTree(HuffNode,n,a); for (i=0;i<n;i+) /*按结点位置进行编码*/ cd.start=n-1; c=i; p=HuffNodec.parent; while (p!

17、=-1) if (HuffNodep.lchild=c) cd.bitcd.start=0; else cd.bitcd.start=1; cd.start-; c=p; p=HuffNodec.parent; for (j=cd.start+1;j<n;j+) /*储存编码*/ HuffCodei.bitj=cd.bitj; HuffCodei.start=cd.start; for (i=0;i<n;i+) HuffCodei.letter=HuffNodei.letter; printf(" %c ",HuffCodei.letter); for (j=H

18、uffCodei.start+1;j<n;j+) printf("%d",HuffCodei.bitj); printf("n"); int main() lable data30; char s100,*p; int i,count=0; for (;) cout<<" / 求哈夫曼编码,直到输入为end结束! /"<<endl; printf(" Input some letters:"); scanf("%s",s); if (!strcmp(s,"

19、end") exit(0); for (i=0;i<30;i+) datai.s=0; datai.num=0; p=s; while (*p) /*计算字符个数与出现次数(即权值)*/ for (i=0;i<=count+1;i+) if (datai.s=0) datai.s=*p; datai.num+; count+; break; else if (datai.s=*p) datai.num+; break; p+; printf("n"); printf(" different letters:%dn",count);

20、for (i=0;i<count;i+) printf(" %c ",datai.s); printf("weight:%dn",datai.num); HuffmanCode(count,data); count=0; getch();数据结构哈夫曼编码实验默认分类 2007-12-06 14:41:40 阅读100 评论0 字号：大中小 / hufuman.cpp : Defines the entry point for the console application./#include "stdafx.h"#includ

21、e"iostream.h"#define maxbit 10#define maxleaf 30 /定义hfmtree中的叶子结点个数#define maxvalue 10 /定义最大权值#define maxnode maxleaf*2-1typedef struct int weight; int parent; int lchild; int rchild; char zifu; HNodeType;HNodeType HuffNodemaxnode;typedef struct char bitmaxbit; int start; HcodeType;HcodeTy

22、pe HuffCodemaxleaf;int n; /字符集大小，即叶子结点个数/*子函数初始化*/void init();void creathfmtree();void hfmCode();void hfmtrans();/*子函数定义*/void init() int i; cout<<"请输入字符集大小，即叶子结点个数n:"<<endl; cin>>n; cout<<"请输入字符："<<endl; for(i=0;i<n;i+) cin>>HuffNodei.zifu;

23、 for(i=0;i<2*n-1;i+) /初始化 HuffNodei.weight=0; HuffNodei.parent=-1; HuffNodei.lchild=-1; HuffNodei.rchild=-1; for(i=0;i<n;i+) cout<<"请输入字符"<<HuffNodei.zifu<<"的权值：" cin>>HuffNodei.weight; void creathfmtree() int i,j,m1,m2,x1,x2; for(i=0;i<n-1;i+) m1

24、=m2=maxvalue; x1=x2=0; for(j=0;j<n+i;j+) /找最小次小权重值及其下标值 if(HuffNodej.parent=-1&&HuffNodej.weight<m1) m2=m1; x2=x1; m1=HuffNodej.weight; x1=j; else if(HuffNodej.parent=-1&&HuffNodej.weight<m2) m2=HuffNodej.weight; x2=j; /将两颗子树合并成为一棵子树 HuffNodex1.parent=n+i; HuffNodex2.parent=

25、n+i; HuffNoden+i.weight=HuffNodex1.weight+HuffNodex2.weight; HuffNoden+i.lchild=x1; HuffNoden+i.rchild=x2; void hfmCode() HcodeType cd; int i,j , c, p; for(i=0;i<n;i+) /求每个叶子结点的哈夫曼编码 cd.start=maxbit-1; c=i; p=HuffNodec.parent; while(p!=-1) /由叶子结点向上直到树根 if(HuffNodep.lchild=c) cd.bitcd.start='0' else cd.bitcd.start='1' cd.start-; c