哈夫曼编码
一、源程序
#include
#include
#include
#include
/* Huffman 树的存储结构*/
#define n 8 /*叶子数目根据需要设定*/
#define m 2*n-1 /* Huffman 树中结点总数*/
typedef struct
{int weight; /*结点的权值*/
int lchild,rchild,parent; /*左、右孩子及双亲的下标*/
}htnode;
typedef htnode huffmantree[m+1];/* huffmantree是结构数组类型,其0号单元不用，存储哈夫曼树*/
typedef struct
{char ch; /*存储字符*/
char code[n+1]; /*存放编码位串*/
}codenode;
typedef codenode huffmancode[n+1];/*huffmancode是结构数组类型,其0号单元不用,存储哈夫曼编码*/
void inithuffmantree(huffmantree ht) /*初始化哈夫曼树函数inithuffmantree()*/
{int i;
for(i=0;i<=m;i++)
{ht[i].weight=0;
ht[i].lchild=ht[i].rchild=ht[i].parent=0;
}
}
void inputweight(huffmantree ht) /*输入权值函数*/
{int i;
for(i=1;i<=n;i++)
{printf("请输入第%d个权值: ",i);
scanf("%d",&ht[i].weight);
}
}
void selectmin(huffmantree ht, int i, int *p1, int *p2)
/* 在ht[1..i]中选两个权值最小的根结点，其序号为*p1和*p2，*p1中放权值最小的根结点的序号，*p2中放权值次小的根结点的序号*/
{int j,min1,min2; /* min1,min2分别是最小权值和次小权值*/
min1=min2=32767;
*p1=*p2=0;
for(j=1;j<=i;j++)
{if(ht[j].parent==0) /* j 为根结点*/
if(ht[j].weight { if(min1!=32767) {min2=min1; *p2=*p1;} min1=ht[j].weight; *p1=j; } else if(ht[j].weight {min2=ht[j].weight; *p2=j;} } } void createhuffmantree(huffmantree ht) /*构造huffman树，ht[m]为其根结点*/ { int i,p1,p2; inithuffmantree(ht); /* 将ht初始化*/ inputweight(ht); /* 输入叶子权值至ht [1..n]的weight域*/ for(i=n+1;i<=m;i++) /* 共进行n-1次合并，新结点依次存于ht[i]中*/ {selectmin(ht,i-1,&p1,&p2); /*在ht [1.. i-1]中选择两个权值最小的根结点，其序号分别为p1和p2*/ ht[p1].parent=ht[p2].parent=i; ht[i].lchild=p1; /* 最小权值的根结点是新结点的左孩子*/ ht[i].rchild=p2; /* 次小权值的根结点是新结点的右孩子*/ ht[i].weight=ht[p1].weight+ht[p2].weight; } } void huffmancodes(huffmantree ht,huffmancode hcd) /*根据huffman树ht求huffman编码*/ { int c,p,i; /* c和p分别指示ht中孩子和双亲的位置*/ char cd[n+1]; /* 临时存放编码*/ int start; /* 指示编码在cd 中的起始位置*/ cd[n]='\0'; getchar(); /* 编码结束符*/ printf("请输入字符"); for(i=1;i<=n;i++) /* 依次求叶子ht [i]的编码*/ { hcd[i].ch=getchar(); /* 读入叶子ht [i]对应的字符*/ start=n; /* 编码起始位置的初值*/ c=i; /* 从叶子ht [i]开始上溯*/ while((p=ht[c].parent)!=0) /* 直至上溯到ht [ c]是树根为止*/ { cd[--start]=(ht[p].lchild==c)?'0':'1'; /*若ht [ c]是ht[p]的左孩子，则生成代码0，否则生成代码1*/ c=p; /* 继续上溯*/ } strcpy(hcd[i].code,&cd[start]); /* 复制编码位串*/ } printf("\n"); for(i=1;i<=n;i++) printf("第%d个字符%c的编码为%s\n",i,hcd[i].ch,hcd[i].code); } void main() {huffmantree t; huffmancode h; printf("\n请输入%d个权值\n",n); createhuffmantree(t); /* 构造huffman树*/ huffmancodes(t,h); /* 构造huffman编码*/ } 运行结果 心得 getch与getchar基本功能相同,差别是getch直接从键盘获取键值,不等待用户按回车,只要用户按一个键,getch就立刻返回, getch返回值是用户输入的ASCII码,出错返回-1.输入的字符不会回显在屏幕上. getch函数常用于程序调试中,在调试时,在关键位置显示有关的结果以待查看,然后用getch函数暂停程序运行,当按任意键后程序继续运行. #include using namespace std; struct htnode //哈夫曼树结点结构定义 { char ch; //结点值 int weight; //结点权值 int parent; //父结点下标 int lchild,rchild; //左、右孩子结点下标 }; class huffmantree //哈夫曼树类定义 { public: void code(char str1[],int w[],int n); //编码 void uncode(char str1[],char str2[],int n); //解码 private: htnode ht[3000]; //用数组存储哈夫曼树 void creathuffmantree(char str1[],int w[],int n); // 创建哈夫曼树 void select(int pos,int &r1,int &r2); }; //在数组ht中从0到pos位置，查找未加入哈夫曼树的权值最小的两个数的位置r1,r2 //r1为权值最小的位置，r2为权值第二小的位置 void huffmantree::select(int pos,int &r1,int &r2) { r1=r2=0; //初始化为0位置 for(int i=1;i<=pos;i++) { if(ht[i].parent!=0) //父结点不等于0，表示已加入哈夫曼树 continue; //继续向前查找 if(r1==0) //把r1设置为1 r1=i; else if(r2==0) //把r2设置为2 r2=i; //从i等于3开始比较。我认为这里程序有问题，无法得到权最小的两位置，你自己再改改else if(ht[i].weight r1=i; else if(ht[i].weight r2=i; } } // 创建哈夫曼树，str1[]为结点值数组，w[]为权值数组，共n个结点 void huffmantree::creathuffmantree(char str1[],int w[],int n) { int pos; //把结点值和权值复制到数组ht for(pos=1;pos<=n;pos++) //注意没有使用ht数组位置为0的空间 { ht[pos].weight=w[pos-1]; //结点权值 ht[pos].ch=str1[pos-1]; //结点值 ht[pos].parent=ht[pos].lchild=ht[pos].rchild=0; //父结点为0表示未加入哈夫曼树，左右孩子都为0表示叶子结点 } //这是构造哈夫曼树的过程，即设置数组ht的其他结点 for(pos=n+1;pos<=2*n-1;pos++) //注意用n个数值构造的哈夫曼树有2*n-1个结点 { int r1,r2; select(pos-1,r1,r2); ht[r1].parent=ht[r2].parent=pos; //把r1，r2结点加入哈夫曼树，并设置他们的父结点位置为pos ht[pos].lchild=r1; //设置pos结点的左孩子为r1 ht[pos].rchild=r2; //设置pos结点的右孩子为r2 ht[pos].weight=ht[r1].weight+ht[r2].weight; //设置pos结点的权值为左右孩子权值的和ht[pos].parent=0; //其父结点为0 } } //求哈夫曼编码 void huffmantree::code(char str1[],int w[],int n) { creathuffmantree(str1,w,n); //建立哈夫曼树 int start,c,i,f,j; char *cd; cd=new char[n]; //用于保存哈夫曼编码 cd[n-1]='\0'; //设置字符串结束符 for(i=1;i<=n;i++) //分别输出n个结点的哈夫曼编码 { start=n-1; //注意从cd数组的末尾向前加入编码 for(c=i,f=ht[i].parent;f!=0;c=f,f=ht[c].parent) //从叶子结点往上走到根结点为止 { //左0，右1 if(ht[f].lchild==c) cd[--start]='0'; else cd[--start]='1'; } cout<<"结点"< for(j=start;j cout< cout< } delete []cd; //撤销 } //翻译哈夫曼编码,str1[]为结点值,str2[]为哈夫曼编码，共n个结点 //输出哈夫曼编码为str2的结点值 void huffmantree::uncode(char str1[],char str2[],int n) { int i,f; char c; for(i=0;i { //根结点在数组ht最后一个位置 //从上往下也是左0右1 for(f=2*n-1;ht[f].lchild!=0&&ht[f].rchild!=0;) { c=str2[i]; if(c=='1') //等于1往右走 { f=ht[f].rchild; i++; } else //等于0往左走 { f=ht[f].lchild; i++; } } cout< } cout< } //这个不用注释了吧 int main() { char str[27],str2[3000],c; char ch[]={'a','b','c','d','e','f','g','h','i','j','k','l','m','n','o','p','q','r','s','t','u','v','w','x','y','z'}; int cd[27],s,len,i,w[27]; sb1: cout<<"请输入要编码的字符串"< cin>>str; huffmantree obj; s=0; memset(cd,0,sizeof(cd)); len=strlen(str); for(i=0;i { cd[str[i]-'a']++; } for(i=0;i<26;i++) { if(cd[i]) { str[s]=ch[i]; w[s]=cd[i]; s++; } } cout<<"各节点编码如下："< obj.code(str,w,s); sb2: cout<<"请输入要解码的01串"< cout<<"解码结果如下："< cout<<"是否继续解码?(Y/N)"< c=getchar(); if(c=='Y') goto sb2; cout<<"是否继续编码?(Y/N)"< c=getchar(); if(c=='Y') goto sb1; return 0; }
相关主题
文本预览