哈夫曼树的建立及应用

哈夫曼树的建立及应用 专业: 班级: 姓名: 学号: 指导老师: 评分: 实验四 哈夫曼树的建立及应用 一、 实验目的 1、 掌握哈夫曼树的基本概念及所有的存储结构。 2、 掌握哈夫曼树的建立算法。 3、 掌握哈夫曼树的应用(哈夫曼编码和译码)。 二、 实习内容 1、 给定权值5，29，7，8，14，23，3，11，建立哈夫 曼树，输出哈夫曼编码。 2、对上述给定的哈夫曼树及得到的哈夫曼编码，试输入一 串二 进制编码，输出它的哈夫曼译码。 三、算法描述 将建立哈夫曼树、实现哈夫曼编码、哈夫曼译码都定义成子函数的形式，然后在主函数中调用它们。 建立哈夫曼树时，将哈夫曼树的结构定义为一个结构型的一维数组，每个元素含有四项:权值，双亲，左孩子，右孩子。给定的权值可以从键盘输入，要输出所建立的哈夫曼树，只要输出表示哈夫曼树的一维数组中的全部元素即可。 要实现哈夫曼编码，只要在所建立的哈夫曼树上进行二进制编码:往左走，编码为0，往右走，编码为1，然后将从根结点到树叶中的所有0、1排列起来，则得到该树叶的哈夫曼编码。哈夫曼编码可以用一个结构型的一维数组保存，每个元素包含:编码、编码的开始位置、编码所对应的字符三项。 四、程序清单: #include #include using namespace std; int x1,x2,s,mm; int ww[100]; struct element { int weight,lchild,rchild,parent; string bianma; }; element huffTree[100]; int huff[100];//存储100个权值的数组 void Select(element huffTree[],int m) { int min,min2,i; min=min2=1000; for(i=0;ihuffTree[i].weight ) { min2=min; min=huffTree[i].weight ; x2=x1; x1=i; } else if(min2>huffTree[i].weight ) { min2=huffTree[i].weight ; x2=i; } } //哈夫曼树函数 void HuffmanTree(element huffTree[]) { int i; cout<<"请设置叶子节点的数量: "; cin>>s; cout<<"请依次输入这"<>huff[i]; for(i=0;i<2*s-1;i++) { huffTree[i].parent =-1; huffTree[i].lchild =-1; huffTree[i].rchild =-1; } for(int i1=0;i1n-1;i--) { huffTree[huffTree[i].lchild ].bianma ="0"; huffTree[huffTree[i].rchild ].bianma ="1"; } for(i=0,j=0;j>mm; cout<<"请输入依次输入解码串(以回车或者空格为结束输 入一个字符): "<>ww[i1]; int j=n,j1; int i=0; while(huffTree[j].lchild !=-1&&i