精华内容
下载资源
问答
  • 构造哈夫曼树生成哈夫曼编码 参考 程序员小灰-漫画:什么是 “哈夫曼树” ? 程序员小灰-漫画:“哈夫曼编码” 是什么鬼? 编写一个程序exp7-5.cpp,构造一棵哈夫曼树, 输出对应的哈夫曼编码和平均查找长度, 并对...

    构造哈夫曼树生成哈夫曼编码

    参考
    程序员小灰-漫画:什么是 “哈夫曼树” ?
    程序员小灰-漫画:“哈夫曼编码” 是什么鬼?

    编写一个程序exp7-5.cpp,构造一棵哈夫曼树,
    输出对应的哈夫曼编码和平均查找长度,
    并对下表(表7.8)所示的数据进行验证。
    
    表7.8 单词及出现的频度
    单词	The	of	a	to	and	in	that	he	is	at	on	for	His	are	be
    频度	1192	677	541	518	462	450	242	195	190	181	174	157	138	124	123
    
    #include<iostream>
    #include<bits/stdc++.h>
    using namespace std;
    
    struct TreeNode{
        int weight=0;
        string word;
        string huffmancode;
        struct TreeNode* lChild;
        struct TreeNode* rChild;
    };
    
    TreeNode *w_node[15];
    
    class cmp{
        public:
        bool operator()(const TreeNode *n1,const TreeNode *n2)const{
            return n1->weight > n2->weight;
        }
    };
    
    //创建哈夫曼树
    TreeNode* CreateHuffmanTree(int w[],string s[]){
        priority_queue<TreeNode*,vector<TreeNode*>,cmp > q;
        for(int i = 0;i < 15; i++){
            TreeNode* node = new TreeNode;
            node->lChild = node->rChild = NULL;
            node->weight = w[i];
            node->word = s[i];
            q.push(node);
            w_node[i] = node;  //记录下原本的点
        }
        
        while (q.size()>1)
        {
            TreeNode *parent = new TreeNode;
            parent->lChild = q.top();
            q.pop();
            parent->rChild = q.top();
            q.pop();
            parent->weight = parent->lChild->weight + parent->rChild->weight;
            q.push(parent);
        }
        return q.top();
    }
    
    //递归编码
    void encode(TreeNode *node,string code){
        if(node==NULL)return;
        node->huffmancode = code;
        encode(node->lChild,code+'0');
        encode(node->rChild,code+'1');
    }
    
    //WPL
    int getWPL(TreeNode *node,int depth){
        if(node->lChild==NULL&&node->rChild==NULL){
            return node->weight*depth;
        }
        return getWPL(node->lChild,depth+1)+getWPL(node->rChild,depth+1);
    }
    
    int main(){
        int weight[] = {1192,677,541,518,462,450,242,195,190,181,174,157,138,124,123};
        string s[] = {"The","of","a","to","and","in","that","he","is","at","on","for","His","are","be"};
        TreeNode *root = CreateHuffmanTree(weight,s);
        encode(root,"");
        for(int i=0;i<15;i++){
            cout<<w_node[i]->word<<":"<<w_node[i]->huffmancode<<endl;
        }
        cout<<"平均查找长度:"<<getWPL(root,0);
        system("pause");
        return 0;
    }
    
    展开全文
  • 哈夫曼树生成程序,直接gcc编译即可,无需修改
  • //哈夫曼编码里的权值,赋值给哈夫曼树里面的权值 HT[i].lchild = HT[i].rchild = HT[i].parent = 0;//双亲,左右子树全部赋值为0 } /*整个树的节点数是2*length-1,刨去第0个,就是2*length 上面一个循环已经...
    #include <stdio.h>
    #include <stdlib.h>
    #include <string.h>
    
    #define MaxSize 50
    #define MAX 32767
       /* int 8位整数*/
    typedef struct{
        char c;                       /* 字符;  */
        int w;                        /* 字符权值;  */
        char *code;                   /*字符的Huffman编码;  */
    }HuffmanCode[MaxSize];
    
    typedef struct{
        int weight;                   /* 权值;  */
        int lchild,rchild,parent;
    }HTNode,HuffmanTree[MaxSize];
    
    /* ================================================================================  */
    void CreateHuffmanTree(HuffmanTree HT,int length,HuffmanCode hc);        /* 生成Huffman树;  */
    void SelectHTNode(HuffmanTree HT,int n,int *min1,int *min2);    /* 查找最小和次小序号;  */
    void HuffmanCoding1(HuffmanTree HT,int n,HuffmanCode hc);            /* 生成Huffman编码;  */
    
    /* ================================================================================  */
    int main()
    {
        HuffmanTree HT;       /* Huffman树;  */
        HuffmanCode HC;       /* Huffman编码;  */
    
        int i,n;
        printf("--------HuffmanCode--------\n");
        printf("\nPlease input the number of char:");
        scanf("%d",&n);
        system("cls");
        printf("the number of char: %2d\n\n",n);
        printf("Input the char and its weight: (e.g.:  \"a16[enter]\" ): \n");
        for(i=1;i <= n;i++)
        {
            while(getchar() != '\n')    NULL;
            printf("No.%2d:  ",i);
            HC[i].c = getchar();
            scanf("%d",&HC[i].w);
        }
        CreateHuffmanTree(HT,n,HC);
        HuffmanCoding1(HT,n,HC);
    
        printf("\nOutput the Huffman Code:\n");
        for(i = 1;i<=n;i++)
        {
            printf("\n %c :",HC[i].c);
            puts(HC[i].code);
        }
    /* 测试Huffman树结构;  */
        printf("\n\nOutput the structure of Huaffman tree:");system("pause");
        printf("\nHT[i]:\tweight\tparent\tLchild\tRchild\n");
        for(i = 1;i<2*n;i++)
        {
            if(i <= n)    printf("(%c)",HC[i].c);
            printf("%2d:\t %2d;\t%2d,\t %2d,\t %2d.\n", i,HT[i].weight,HT[i].parent,HT[i].lchild,HT[i].rchild);
        }
        getch();
        return 0;
    }
    
    
    /* ================================================================================  */
    void CreateHuffmanTree(HuffmanTree HT,int length,HuffmanCode HC)       /* Huffman树初始化;  */
    {
        int i;
        int min1,min2;//最小的两个权值
    
        HT[0].weight = MAX;//哈夫曼树丛0开始储存权值
        
        /*先把叶子节点的双亲,左右变量全部赋值为0*/
        for(i = 1;i <= length;i++)
        {
            HT[i].weight = HC[i].w;//哈夫曼编码里的权值,赋值给哈夫曼树里面的权值
            HT[i].lchild = HT[i].rchild = HT[i].parent = 0;//双亲,左右子树全部赋值为0
        }
        
        /*整个树的节点数是2*length-1,刨去第0个,就是2*length
        上面一个循环已经把叶子的权值存放
        剩下的节点就是树里面非叶子节点,里面不存放权值,
        初始化的时候,这里先把左右、双亲变量赋值为0*/
        for(;i < 2*length;i++)            /* i初值 = length+1;  */
        {
            HT[i].lchild = HT[i].rchild = HT[i].parent = 0;
        }
    
        for(i = length+1;i < 2*length;i++)
        {
            SelectHTNode(HT,i,&min1,&min2);
            HT[min1].parent = i;
            HT[min2].parent = i;
            HT[i].lchild = min1;
            HT[i].rchild = min2;
            HT[i].weight = HT[min1].weight + HT[min2].weight;
        }
    }
    /*==========================================================================*/
    void SelectHTNode(HuffmanTree HT,int n,int *min1,int *min2) /* 查找最小和次小序号;  */
    {
        int i;
        *min1 = *min2 = 0;
        for(i = 1;i < n;i++)
        {
            if(HT[i].parent == 0)
            {
               /* printf("\n i=%d,*min1=%d, HT[*min1].weight=%d",i,*min1,HT[*min1].weight);
                printf("\n i=%d,*min2=%d, HT[*min2].weight=%d",i,*min2,HT[*min2].weight);  */
                if(HT[*min1].weight >= HT[i].weight)
                {
                    *min2 = *min1;
                    *min1 = i;
                  /*printf("\n i=%d: *min1=%d, *min2=%d ",i,*min1,*min2); */
    
                }
                else
                    if(HT[*min2].weight > HT[i].weight)
                     {
                       *min2 = i;
                     /* printf("\n i=%d: *min1=%d, *min2=%d ",i,*min1,*min2);  */
                      }
            }
        }
    }
    
    /* 生成Huffman编码===============================================================  */
    void HuffmanCoding1(HuffmanTree HT,int n,HuffmanCode HC)
    {
      int i,start,c,f;
      char *cd;
      cd=(char * )malloc(n*sizeof(char)); /* 分配求编码的工作空间 */
      cd[n-1]='\0';
      for(i=1;i<=n;i++)                      /* 逐个字符求Huffman编码,注意i从1开始 */
      {
        start=n-1;                           /* 编码结束符位置 */
        for(c=i,f=HT[i].parent;f!=0;c=f,f=HT[f].parent )  /* 从叶子到根逆向求编码 */
        {
          if (HT[f].lchild ==c)
              cd[--start]='0';
          else
              cd[--start]='1';
         }
         HC[i].code =(char*) malloc((n-start)*sizeof(char));  /* 为第i个字符编码分配空间 */
         strcpy(HC[i].code,&cd[start]);   /* 从cd 复制到HC[i].code */
    
      }
      free(cd);
    
    }
    /* ================================================================================  */
    

     

    展开全文
  • #include <iostream> using namespace std; #define MAX 50 ...typedef struct //哈夫曼树结点结构 { char data; int weight; int parent; int lchild; int rchild; }HuffNode; typedef struct ...

    在这里插入图片描述

    #include <iostream>
    using namespace std;
    #define MAX 50
    #define MAXNUM 60
    typedef struct	//哈夫曼树结点结构
    {
    	char data;
    	int weight;
    	int parent;
    	int lchild;
    	int rchild;
    }HuffNode;
    
    typedef struct
    {
    	char cd[MAX];	//存放字符的编码
    	int start;	//编码的起始位置
    }HuffCode;
    
    void Select(HuffNode huffTree[], int k, int& i1, int& i2) {
    	/*选择根结点权值最小的两个结点。*/
    	int i, j;
    	for (i = 0; i < k; i++)
    		if (huffTree[i].parent == -1) { i1 = i; break; }
    	for (j = i + 1; j < k; j++)
    		if (huffTree[j].parent == -1) { i2 = j; break; }
    	for (i = 0; i < k; i++)
    		if ((huffTree[i].parent == -1) && (huffTree[i].weight < huffTree[i1].weight) && (i2 != i))
    		{
    			i1 = i;
    		}
    	for (j = 0; j < k; j++)
    		if ((huffTree[j].parent == -1) && (huffTree[j].weight < huffTree[i2].weight) && (i1 != j))
    		{
    			i2 = j;
    		}
    }
    
    void HuffmanTree(HuffNode huffTree[], int n) {
    	/*此处完成构造哈夫曼树huffTree []*/
    	int i, k;
    	// 初始化
    	for (i = 0; i < 2 * n - 1; i++)
    	{
    		huffTree[i].parent = -1;
    		huffTree[i].lchild = -1;
    		huffTree[i].rchild = -1;
    	}
    
    	#if 0
    	for (k = n; k < 2 * n - 1; k++) {
    		int i1, i2;
    		Select(huffTree, k, i1, i2);
    		/* 在 huffTree [0] ~ huffTree [k-1] 的范围内选择两个parent为-1且
    		weight最小的结点,其序号分别赋值给i1、i2返回 */
    		huffTree[k].weight = huffTree[i1].weight + huffTree[i2].weight;
    		huffTree[i1].parent = k; huffTree[i2].parent = k;
    		huffTree[k].lchild = i1; huffTree[k].rchild = i2;
    	}
    	#else
    		//优化算法	
    		/*
    			// 基本思想:先排序,然后每次前面在顺序取权值,k+1和后面新增的比较,
    			// 如果前面k+1比后面小,取前面k 和 k+1,且取完相加等到新的 i_12,
    			// 如果后面的比k+1小,则取k 和 后面的 i_12-1 相加得到新的i_12
    
    			1. 排序
    			2. 依次选2个相加得到最小权值
    				2.1 判断k++是否 大于等于n,如果是则退出
    		*/
    	// 排序
    	HuffNode temp;
    	for (int i = 0; i < n - 1; ++i)
    	{
    		for (int j = i + 1; j < n; ++j)
    		{
    			if (huffTree[i].weight > huffTree[j].weight)
    			{
    				temp = huffTree[i];
    				huffTree[i] = huffTree[j];
    				huffTree[j] = temp;
    			}
    		}
    	}
    
    	int i1, i2;
    	// i1, i2 之和的下标
    	int i_12 = n - 1;
    	for (k = 0; k < n ; k++) {
    		i_12++;
    		i1 = k;
    
    		// 如果i_12存在,判断 i_12 与 k+1 的权值大小
    		if (huffTree[i_12 - 1].weight < huffTree[k + 1].weight && huffTree[i_12 - 1].lchild != -1)
    			i2 = i_12 - 1;
    		else
    		{
    			// index 的权值大于 i1+1, 选择小的权值
    			i2 = ++k;
    
    			if (i2 >= n)
    			{
    				// 表示i1 是最后一个值,与i_12进行相加,得到最终值
    				i2 = i_12 - 1;
    				huffTree[i_12].weight = huffTree[i1].weight + huffTree[i2].weight;
    				huffTree[i1].parent = i_12; huffTree[i2].parent = i_12;
    				huffTree[i_12].lchild = i1; huffTree[i_12].rchild = i2;
    
    				break;
    			}
    			else
    			{
    				// 第一次只有1个权值和
    				if (k > 2)
    				{
    					huffTree[i_12].weight = huffTree[i1].weight + huffTree[i2].weight;
    					huffTree[i1].parent = i_12; huffTree[i2].parent = i_12;
    					huffTree[i_12].lchild = i1; huffTree[i_12].rchild = i2;
    
    					i1 = i_12;
    					i2 = i_12 - 1;
    					i_12++;
    				}
    			}
    		}
    
    		huffTree[i_12].weight = huffTree[i1].weight + huffTree[i2].weight;
    		huffTree[i1].parent = i_12; huffTree[i2].parent = i_12;
    		huffTree[i_12].lchild = i1; huffTree[i_12].rchild = i2;
    	}
    	#endif
    }
    
    
    char* strcut(char* dest, char* src, int start)
    {
    	/*
    		功能: 截取start 后面的字符串
    	*/
    	if (dest == NULL || src == NULL)
    		return NULL;
    
    	char* pdst = (char*)dest;
    	char* psrc = (char*)src + start;
    
    	if (start > 0)
    	{		
    		while (*psrc != '\0')
    		{
    			*pdst++ = *psrc++;
    			if (*psrc == '\0')
    			{
    				*pdst = '\0';
    				break;
    			}
    		}
    	}
    	else
    	{
    		dest = psrc;
    	}
    
    	return dest;
    }
    
    
    void Encoding(HuffNode ht[], HuffCode hcd[], int n)
    {
    
    	//此处完成哈夫曼编码以及输出哈夫曼编码
    
    
    	// 计算 n 字符的 编码  左为0, 右为1
    	// 每个叶子结点即为一个字符(数组前n个结点)
    	
    
    	// 从第一个结点开始找
    	for (int i = 0; i < n; ++i)
    	{
    		//编码的起始位置
    		hcd[i].start = n - 1;
    
    		hcd[i].cd[hcd[i].start] = '\0';
    
    		// c 表示当前结点
    		int c = i;
    		// f 表示当前结点的父结点
    		int f = ht[i].parent;
    
    
    		while (f != -1)	// 根结点退出循环
    		{
    			if (ht[f].lchild == c)
    				// 当前孩子结点是当前父节点的左孩子,则编码0
    				hcd[i].cd[--hcd[i].start] = '0';
    			else
    				// 当前孩子结点是当前父节点的左孩子,则编码1
    				hcd[i].cd[--hcd[i].start] = '1';
    
    			// 循环直到根结点
    			c = f;
    			f = ht[f].parent;
    		}
    
    		//hcd[i] = strcpy(hcd[i].cd, &cd[start])
    		char* dest = new char[n - hcd[i].start];
    		dest = strcut(dest, hcd[i].cd, hcd[i].start);
    
    		cout << ht[i].data << ": " << dest << endl;
    
    	}
    	
    }
    
    
    int main()
    {
    	int n, i;
    	HuffNode huffTree[MAXNUM];//创建huffTree类型的一维数组,用于存储哈夫曼树
    	HuffCode hcd[MAXNUM];//创建hcd类型的一维数组,每个数组元素存储一个叶子结点的哈夫曼编码
    	cout << "请输入字符个数" << endl;
    	cin >> n;
    	for (i = 0; i < n; i++)
    	{
    		cout << "输入第" << i + 1 << "个字符:";
    		cin >> huffTree[i].data;
    		cout << "输入第" << i + 1 << "个字符的权值:";
    		cin >> huffTree[i].weight;
    	}
    
    	HuffmanTree(huffTree, n);//构造哈夫曼树
    
    	Encoding(huffTree, hcd, n);//求得哈夫曼树huffTree的对应的哈夫曼编码,并输出每个叶子结点的哈夫曼编码
    
    	return 0;
    }
    
    展开全文
  • 编程得出哈夫曼的码表;输入一段英文字符,利用码表对其编码、译码。 开发环境: VS2015(C++) 2.数据处理 数据归一化,使各英文字符概率之和为1。由于文献中各字符概率之和大于1,对数据进行归一化。将当前各...

     

    1.任务要求

    将英文字符的统计概率作为权值。编程得出哈夫曼的码表;输入一段英文字符,利用码表对其编码、译码。

    开发环境: VS2015(C++)

    2.数据处理

    数据归一化,使各英文字符概率之和为1。由于文献中各字符概率之和大于1,对数据进行归一化。将当前各字符概率值除以当前的概率之和,得出的结果保留小数点后5位,作为新的概率值(相当于权值,这步可以省略,不影响最后结果)。

                                                            

    归一化后个字符概率如下图所示。经过检验,归一化之前的概率之和:1.2069;归一化后的概率之和:1.0000。

    3.建立哈夫曼树

    哈夫曼树(Huffman)即最优二叉树,它是在n个权重作为叶子结点的数值构成的二叉树中,选取并实现带权路径长度(WPL)最短的二叉树。要构造一棵最优二叉查找树就应在离根结点比较近的地方放置查找概率高的结点。

    定义两个结构体,分别用于存储字符信息和哈夫曼树结点信息。 

    typedef struct Alphabet
    {	//字符结构体
    	char data;//字符	
    	double probability;//概率值
    	char *code;//编码
    } English;
    

    节点信息结构体,用于生成哈夫曼树和实现译码操作。

    typedef struct Node
    {  //节点结构体
    	double weight;//权值
    	int id;//编号
    	bool visit;//是否加入树中
    	struct Node *right;//右子节点
    	struct Node *left;//左子节点
    	const English *point;//字符信息
    } *HuffmanTree;
    

    一个哈夫曼树如果存在n个待编码的叶子节点,一定存在n-1个非叶子节点。节点总数为2n-1个[2]。

    首先初始化所有节点,分配存储空间。定义0-26号节点为叶子节点,point指针按照概率值的大小依次指向字符结构体元素。27-52号节点非叶子节点,point指针指向NULL,左右子节点也为NULL。

    然后,进行n-1次循环建立哈夫曼树。首先在结构体数组中找出当前权值最小的两个节点(当新生成的节点权值和叶子节点相同时,选择之前的叶子节点),返回它们的位置到minP数组中。再将这两节点合成新的节点,用两者的概率之和合成新节点的权值。

    生成树的关键代码如下所示。

    for (i = N; i < total; ++i){
    	FindLittleNode(HT, i - N);//找出当前概率值最小的两个节点
    	(*HT)[i].left = (struct Node *)(*HT + minP[0]);
    	(*HT)[i].right = (struct Node *)(*HT + minP[1]);
    	(*HT)[i].weight = (*HT + minP[0])->weight + (*HT + minP[1])->weight;
    	(*HT)[i].point = NULL;
    	printf("%2d \t %.4f \t %2d \t %.4f \t %4d \t\t %.4f\n", minP[0], (*HT + minP[0])->weight, minP[1], (*HT + minP[1])->weight, i,(*HT)[i].weight);
    	cout << endl;
    }
    

    寻找最小概率值节点,核心代码如下所示。一次遍历,选出将当前未被加入树中的两个最小节点。得出它们的位置信息。

    for (int i = n + 1; i < n + N; i++){
    		if ((*tree)[i].visit){
    			continue;
    		}
    		if ((*tree + i)->weight < min1){
    			min2 = min1;
    			minP[1] = minP[0];
    			//将最小数值及位置赋值到min1和minP[0]中
    			min1 = (*tree + i)->weight;
    			minP[0] = i;
    		}else if ((*tree + i)->weight < min2){
    			//次小值节点信息
    min2 = (*tree + i)->weight;
    			minP[1] = i;
    		}
    }
    

    4.生成哈夫曼码表

    在哈夫曼树创建完成后,利用递归算法进行前序遍历。在遍历过程中,将得出的编码序列存储在字符结构体中。

    如果左节点存在,编码序列末尾添加0;如果右节点存在,编码序列末尾添加1;如果节点为叶子节点,将当前遍历得出的编码序列复制到字符结构体的编码信息中。关键代码如下所示。

    void enCode(HuffmanTree HT, string code, English *en){
    	if (HT){
    		if (HT->point != NULL){
    			(en + HT->id)->code = (char *)malloc(sizeof(char) * code.length());
    			strcpy((en + HT->id)->code, code.c_str());
    		}
    		enCode(HT->left, code + "0", en);
    		enCode(HT->right, code + "1", en);
    	}
    }
    

    5.编码

    在生成码表的时候已将字符编码信息保存至字符结构体中。根据输入的英文序列遍历一次即可得出,程序如下所示。

    • 首先将字符结构体按照字符ASCII值排序(升序)。
    • 读取需要编码是英文字符序列,逐一判断。如果是空格符,取结构体数组的第一个编码;否则,取字符结构体数组第n位的编码。
    • 将读取的编码逐一加入新的string对象中,可得到编码的01序列。
    string AfterEncode(English *en, string str){
    	string res;
    	string::iterator it = str.begin();
    	while (it != str.end()){
    		if (*it == ' '){
    			res += en->code;
    		}else{
    			res += (en + (*it) - 64)->code;
    		}
    		++it;
    	}
    	return res;
    }
    

    将生成的01序列,按照bit来存储传输可以显著降低原英文序列的大小。

    6.译码

    经过编码后的英文字符序列变为了‘0’‘1’序列,将得出的序列根据哈夫曼树遍历一次即可解出原始英文序列。程序流程如下图所示。

    首先判断当前编码序列是0还是1。若为0,访问左节点;若为1,访问右节点。以此进行遍历,直到访问到叶子节点。再回到根节点进行下一编码序列的解码。

    string AfterDecCode(HuffmanTree HT, string encstr){
    	string decstr;
    	HuffmanTree p;
    	p = HT + 52;//指向根节点
    	string::iterator it = encstr.begin();
    	while (it != encstr.end()){
    		if (*it == '0')
    			p = p->left;
    		if (*it == '1')
    			p = p->right;
    		if (p->point != NULL){
    			decstr += p->point->data;//回到根节点
    			p = HT + 2 * N - 2;}
    		++it;
    	}
    return decstr;}
    

    7.结果展示

    7.1建树过程

    7.2 哈夫曼树结构

    7.3 码表

    7.4 编译码过程

    自己定义输入一段英文字符序列(不含空格以外的其它符号),程序会自动将输入的序列转换为大写字符。

    首先,程序会自动打印出编码后的01序列;然后根据该01序列译码得出原始的英文序列

    8.  程序示例

    #include <iostream>
    #include <string>
    #include <string.h>
    #include <algorithm>
    #include <malloc.h>
    #include <bitset>
    using namespace std;
    
    #define N 27
    #define _MAX INFINITY
    
    int main()
    {
    	English en[27] = { { ' ', 0.2 },{ 'A', 0.063, },{ 'B', 0.0105 },{ 'C', 0.023 },{ 'D', 0.035 },{ 'E', 0.105 },{ 'F', 0.225 },
    	{ 'G', 0.011 },{ 'H', 0.047 },{ 'I', 0.055 },{ 'J', 0.001 },{ 'K', 0.003, },{ 'L', 0.029 },{ 'M', 0.021 },{ 'N', 0.059 },
    	{ 'O', 0.0654 },{ 'P', 0.0175 },{ 'Q', 0.001 },{ 'R', 0.054 },{ 'S', 0.052 },{ 'T', 0.072 },{ 'U', 0.0225 },
    	{ 'V', 0.008 },{ 'W', 0.012 },{ 'X', 0.002 },{ 'Y', 0.012 },{ 'Z', 0.001 }
    	};
    	//数据归一化,使概率和为1
    	double sum = 0;
    	for (int i = 0; i < N; ++i) {
    		sum += en[i].probability;
    	}
    	cout << "概率之和: " << sum << endl;
    	
    	for (int i = 0; i < N; ++i) {
    		en[i].probability = en[i].probability / sum;
    		en[i].probability = (int)(en[i].probability * 100000 + 0.5)*1.0/ 100000.0;
    	}
    	sum = 0;
    	for (int i = 0; i < N; ++i) {
    		sum += en[i].probability;
    	}
    	printf("归一化后,概率之和:%.4f\n", sum);
    
    
    	//英文字符排序
    	sort(en, en + N, compare1);
    	//输出英文字符信息
    	//for (char i = 0; i < 27; ++i) {
    	//	cout << en[i].data << "  " << en[i].probability << endl;
    	//}
    	HuffmanTree Tree;
    	
    	CreateHuffmanTree(&Tree, en);
    
    	cout << "生成哈夫曼树结构如下:" << endl;
    	PrintHuffmanTree(Tree + 52);
    	cout <<"哈夫曼码表如下"<< endl;
    	enCode(Tree + 52, "", en);
    
    	cout << "输入一段英文字符" << endl;
    	string myWords, encString, decString;
    	getline(std::cin, myWords, '\n');//读取到换行符才停止
    
    	transform(myWords.begin(), myWords.end(), myWords.begin(), ::toupper);
    	cout << "输入字符如下(大写):" << endl;
    	cout << myWords << endl;
    	//按照字符ASCII值排序
    	sort(en, en + N, compare2);
    	//输出英文字符码表信息
    	cout << "字符\t权重\t编码" << endl;
    	for (char i = 0; i < N; ++i)
    	{
    		cout << en[i].data << "\t" << en[i].probability << "\t" << en[i].code << endl;
    	}
    	cout << "编码之后:" << endl;
    	encString = AfterEncode(en, myWords);
    
    	cout << encString << endl;
    
    	sort(en, en + N, compare1);
    	cout << "解码之后:" << endl;
    	decString = AfterDecCode(Tree, encString);
    	cout << decString << endl;
    	system("pause");
    	return 0;
    }

     

    展开全文
  • 哈夫曼编码:从队列中取出权重最小的两个节点,进行构造  将新生成的节点作为父节点   使用结构体:  Node(node1,node2,weight) //权重边信息保存  HuffmanTree(weight,family,lchild,rchil
  • //生成哈夫曼树 select ( huff , k ) ; huff [ i1 ] . p = huff [ i2 ] . p = k ; huff [ k ] . weight = huff [ i1 ] . weight + huff [ i2 ] . weight ; huff [ k ] . l = i1 ; huff [ k ] ....
  • 当队列中只剩一个节点时,哈夫曼树生成就结束了。假设有n个叶子节点,则每次队列中都会减少一个节点,由此可知最后将额外生成n-1个节点。每次生成新的节点时,都需要从存放节点的数组中寻找两个还未使用并且权值...
  • //初始化哈夫曼树结点 void GetMin(HTreeNode* array , int start, int end, int &s1, int &s2); //取两个权重最新的结点 void CreateHTree(HTreeNode* array , int num); //创建哈弗曼树 ...
  • C/C++实现哈夫曼树生成哈夫曼编码

    千次阅读 2019-07-01 14:52:39
    用C语言实现哈夫曼树生成哈夫曼编码,首先生成哈夫曼树哈夫曼树是从中选取权值最小的两个进行相加,将这两个分别做为生成的左子树和右子树,左子树要比右子树小。然后将相加得到的值从新放入,然后又从中找到...
  • 构造哈夫曼树生成哈夫曼编码

    万次阅读 多人点赞 2019-01-25 17:12:36
    一、什么是哈夫曼树哈夫曼树是一种带权路径长度最短的二叉树,也称为最优二叉树。用一幅图来说明: 它们的带权路径长度分别为: 图a: WPL=5*2+7*2+2*2+13*2=54 图b: WPL=5*3+2*3+7*2+13*1=48 可见,图b...
  • 构造哈夫曼树,并生成编码 构造哈夫曼树,并生成编码
  • 哈夫曼树生成以及编码

    千次阅读 2019-11-11 00:08:47
    哈夫曼树生成以及编码 #include <stdio.h> #include <stdlib.h> #include <string.h> #include<iostream> using namespace std; typedef int ELEMTYPE; typedef struct HuffmanTree { ...
  • 哈夫曼树生成及哈夫曼编码

    千次阅读 2017-12-20 22:43:07
    首先构造哈夫曼树结构体,初始化哈夫曼树的四个无符号整型域,输入文本,统计各个字符的权值,然后构建哈夫曼树,从根到叶子逆向求哈夫曼树的编码。#include"stdio.h" #include"string.h" #include"malloc.h" #...
  • 哈夫曼树原理,及构造方法

    万次阅读 多人点赞 2018-08-05 12:13:21
    哈夫曼树(最优二叉树) 百度百科:https://baike.baidu.com/item/%E5%93%88%E5%A4%AB%E6%9B%BC%E6%A0%91/2305769?fr=aladdin 一. 目的: 找出存放一串字符所需的最少的二进制编码 二. 构造方法: 首先统计出每...
  • 生成哈夫曼树

    2019-09-26 02:00:33
    给定权集{5,7,2,3,6,8,9}构造哈夫曼树 #include <stdio.h> #include <stdlib.h> #define ElemType int #define MAXSIZE 20 #define length 7 typedef struct HFNode{ ElemType weight; str....
  • 哈夫曼树哈夫曼树编码

    千次阅读 2015-09-09 15:50:57
    本文转自哈夫曼树哈夫曼树编码 在一般的数据结构的书中,树的那章后面,著者一般都会介绍一下哈夫曼(HUFFMAN) 树和哈夫曼编码。哈夫曼编码是哈夫曼树的一个应用。哈夫曼编码应用广泛,如 JPEG中就应用...
  • 哈夫曼树/赫夫曼树 Python实现赫夫曼树 Python实现哈夫曼树 哈夫曼编码 哈夫曼压缩 哈夫曼解压 最简单的方式实现哈夫曼树
  • 本程序实现了哈夫曼树生成及编码的生成
  • 哈夫曼编码是能够使电文总长度最短的编码,哈夫曼编码的生成离不开哈夫曼树。本文围绕哈夫曼树和哈夫曼编码介绍了如下内容: 1、什么叫树的带权路径长度WPL;...4、如何由哈夫曼树生成哈夫曼编码。
  • 哈夫曼树

    万次阅读 多人点赞 2017-08-05 23:34:19
    生成哈夫曼树的第一步就是在结点集合中找到两个权值最小的结点,然后生成一棵二叉树 树中任意节点的权值一定大于自己的左右孩子,但不能保证一定不小于其他下一任结点的权值。设哈夫曼树中的叶子结点总数为m,若用...
  • 哈夫曼树哈夫曼树编码

    千次阅读 2014-05-28 14:50:01
    哈夫曼编码是哈夫曼树的一个应用。哈夫曼编码应用广泛,如 JPEG中就应用了哈夫曼编码。 首先介绍什么是哈夫曼树哈夫曼树又称最优二叉树, 是一种带权路径长度最短的二叉树。所谓树的带权路径长度,就是树中...
  • 最小生成树与哈夫曼树

    千次阅读 2019-08-25 10:41:44
    转载自添加链接描述 最小生成树 定义:在连通网的所有生成树中,所有边的代价和最小的生成树,称为最小生成树。 算法: Kruskal算法(加边法):初始最小生成树边数为0,每迭代一次就选择一条...哈夫曼树 定义:...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 9,871
精华内容 3,948
关键字:

哈夫曼树的生成