赫夫曼树编码代码绝对可用.docx

赫夫曼树的设计思路及代码网上的很多代码用起来都会出现问题，下面的代码确实可以使用，只需要新主函数和头文件，注意：这是在vc6.0下编译的，不同的编译器效果可能不同。然后/***/里面的内容按照提示复制到相应的主函数或者头文件就可以了就可以了。下面附上设计思路和效果图（最后面可以联系我1651901588）。一：实验分析 赫夫曼树又称最优树，在电文的传输过程中我们总是想提高电文的传输效率，我们可以根据电文中字幕出现的概率来对电文是现编码；赫夫曼树的构建过程是假设有n个权值，则构造出的哈夫曼树有n个叶子结点。 n个权值分别设为 w1、w2、…、wn，则哈夫曼树的构造规则为：将w1、w2、…，wn看成是有n 棵树的森林(每棵树仅有一个结点)；在森林中选出两个根结点的权值最小的树合并，作为一棵新树的左、右子树，且新树的根结点权值为其左、右子树根结点权值之和； (3)从森林中删除选取的两棵树，并将新树加入森林； (4)重复(2)、(3)步，直到森林中只剩一棵树为止，该树即为所求得的哈夫曼树二：系统分析 我写的代码分为以下几个部分： 1，select（）函数的作用是从权值中选出最小的两个权值 2，createhfmtree()的作用是构建并初始化一个赫夫曼树 3，createhfmcode（）的作用是对一颗赫夫曼树进行初始化 4，bianma（）的作用是把输入的字符串转化成0/1码 5，yima()函数的作用是把0/1码传换成字符串 6，jiemian（）的作用是显示提示和调用之前定义的函数Select（）的设计思路 我先在输入的节点中用for循环中，找到一个没有双亲节点的节点，然后用for循环找出最小的一个，然后再用for循环找出最小的一个权值的编号，然后再用for循环找出不等于第一个去找权值的节点的编号；Cretehfmtree（）函数的设计思路首先我们对钱n个节点进行权值的赋值，我们再输入权值后，然后对赫夫曼树构建的总结点2n-1个节点进行初始化，没有的权值我们要赋值为0，然后再调用前面的select函数选出最小的两个节点多次循环后赫夫曼树构建完成；Createhfmcode()的设计思路 因为我们之前已经设计了赫夫曼树，现在我们开始对赫夫曼树进行编码的工程，我们要编码的是n个子叶节点，我们从第一个节点开始编码，如果我们发现这个节点是这个节点双亲的的左孩子，如果是的话，我们就赋值为0,否则的话就复制为1，直到所有的节点构建完成；bianma()的设计思路 我们对输入的字符串进行编码的时候，要根据构建好的赫夫曼树进行编码，编码的时候，先按顺序在字符串中选出一个字符，从子叶节点开始找，如果找到了就输出这个节点对对应的赫夫曼编码，然后换下一个，直到一串字符串编码完成；Yima()的设计思路 我们对输入的0/1字符串在译码的时候要从根节点开始译码，译码的时候遇见0就找他的左孩子，遇见1就找他的右孩子，直到找到一个节点，这个节点没有左孩子，也没有右孩子，输出这个节点的字符，知道代码译码完成；Jiemian(）的设计思路我们在界面函数中提示调用命令，然后调用随影的函数；知道函数执行完成； 开始界面三；流程图 Select（）选出两个最小的权值的节点 不断地反复调用，直到赫夫曼树构建完成调用前面的函数，构建和初始化赫夫曼树，知道赫夫曼树构建完成结束赫夫曼树的编码构件的初始化译码函数译码函数译码结果编码结果开始调用界面函数四：试验执行效果图 /************这是主函数部分*******************************************/ #includeiostream#includestdlib.h#includestring.h#includemalloc.husing namespace std;#define ERROR 0#define OK 1int tn;typedef int Status;#includefujian.hint main(){ hfmtree HT; hfmcode HC; jiemian(HT,HC); return 0;}/*******************主函数部分结束***********************************//**********************这是头文件*****************************************/typedef struct HTNode{//赫夫曼树结构体定义char c;int weight;int parent,lchild,rchild;}HTNode,*hfmtree;typedef char **hfmcode;/**********************************