精华内容
下载资源
问答
  • 这是数据结构课设 哈夫曼树的c语言实现 大家可以借鉴一下
  • 哈夫曼树代码实现 请看代码: 例子用上一节,请自行对比 #include<iostream> #include<deque> #include<vector> #include<algorithm> using namespace std; typedef struct _...

    哈夫曼树用代码实现

    请看代码:
    例子用的上一节,请自行对比

    #include<iostream>
    #include<deque>
    #include<vector>
    #include<algorithm>
    using namespace std;
    
    typedef struct _HuffumanTree
    {
    	int weight;//权值
    	_HuffumanTree *left;//左儿子节点
    	_HuffumanTree *right;//右儿子节点
    }HuffumanTree;
    
    //构造哈夫曼树
    HuffumanTree * CreateHuffumanTree(vector<int> &m_vc)
    {
    	deque<HuffumanTree *>m_HfVc;
    	//1.根据权值先创建树节点
    	for (auto p :m_vc)
    	{
    		
    		HuffumanTree *m_hf = (HuffumanTree *)malloc(sizeof(HuffumanTree));
    		m_hf->weight = p;
    		m_hf->left = nullptr;
    		m_hf->right = nullptr;
    
    		m_HfVc.push_back(m_hf);
    	}
    
    	//2.将装有树节点的队列按照从小到大的顺序排列,并且取出最小的两个
    	int nsize = m_HfVc.size();
    	int a = 0;
    	int b = 0;
    	HuffumanTree *m_leftChild{ nullptr };//左
    	HuffumanTree *m_rightChild{ nullptr };//右
    	HuffumanTree* newtree{ nullptr };
    	for (int i = 0; i < nsize-1;i++)
    	{
    
    		sort(m_HfVc.begin(), m_HfVc.end(), [](HuffumanTree *t1, HuffumanTree *t2){return t1->weight < t2->weight; });
    		
    		m_leftChild = m_HfVc.front();
    		m_HfVc.pop_front();
    
    		m_rightChild = m_HfVc.front();
    		m_HfVc.pop_front();
    
    		newtree = (HuffumanTree *)malloc(sizeof(HuffumanTree));
    		newtree->weight = m_leftChild->weight + m_rightChild->weight;
    		newtree->left = m_leftChild;
    		newtree->right = m_rightChild;
    		
    		m_HfVc.push_back(newtree);
    	}
    
    	return  m_HfVc.front();
    }
    
    //打印哈夫曼树
    void printHfTree(HuffumanTree *root)
    {
    	if (root)
    	{
    		cout << root->weight << endl;
    		if (root->left)
    		{
    			cout << root->left->weight << "    ";
    		}
    		else{
    			cout << "没有左孩子\n";
    		}
    
    		if (root->right)
    		{
    			cout << root->right->weight << "    ";
    		}
    		else{
    			cout << "没有右孩子\n";
    		}
    		cout << endl;
    		printHfTree(root->left);
    		printHfTree(root->right);
    
    	}
    
    
    }
    void main()
    {
    	vector<int> m_vc{ 19, 21, 2, 3, 6,7,10,32 };
    	
    	HuffumanTree *m_hf = CreateHuffumanTree(m_vc);
    
    	printHfTree(m_hf);
    
    	system("pause");
    }
    

    结果:
    在这里插入图片描述

    展开全文
  • 数据结构(15)--哈夫曼树以及哈夫曼编码的实现

    万次阅读 多人点赞 2016-03-01 17:28:40
    参考书籍:数据结构(C语言版)严蔚敏吴伟民编著清华大学出版社 本文中的代码可从这里下载:https://github.com/qingyujean/data-structure 1.哈夫曼树 假设有n个权值{w1, w2, ..., wn},试构造一棵含有n个叶子...

    参考书籍:数据结构(C语言版)严蔚敏吴伟民编著清华大学出版社

    本文中的代码可从这里下载:https://github.com/qingyujean/data-structure

    1.哈夫曼树

        假设有n个权值{w1, w2, ..., wn},试构造一棵含有n个叶子结点的二叉树,每个叶子节点带权为wi,则其中带权路径长度WPL最小的二叉树叫做最优二叉树或者哈夫曼树

        特点:哈夫曼树中没有度为1的结点,故由n0 = n2+1以及m= n0+n1+n2,n1=0可推出m=2*n0-1,即一棵有n个叶子节点的哈夫曼树共有2n-1个节点。

    2.哈夫曼编码

        通信传送的目标是使总码长尽可能的短。

        变长编码的原则:
        1.使用频率高的字符用尽可能短的编码(这样可以减少数据传输量);
        2.任一字符的编码都不能作为另一个字符编码的开始部分(这样就使得在两个字符的编码之间不需要添加分隔符号)。这种编码称为前缀编码

        根据每种字符在电文中出现的次数构造哈夫曼树,将哈夫曼树中每个分支结点的左分支标上0,右分支标上1,把从根结点到每个叶子结点的路径上的标号连接起来,作为叶结点所代表的字符的编码。这样得到的编码称为哈夫曼编码

        思考为什么哈夫曼编码符合变长编码的原则?哈夫曼树所构造出的编码的长度是不是最短的?

         哈夫曼树求得编码为最优前缀码的原因: 在构造哈夫曼树的过程中:

        1.权值大的在上层,权值小的在下层。满足出现频率高的码长短。
     2.树中没有一片叶子是另一叶子的祖先,每片叶子对应的编码就不可能是其它叶子编码的前缀。即上述编码是二进制的前缀码。
        假设每种字符在电文中出现的次数为wi (出现频率即为权值),其码长为li,电文中只有n种字符,则编码后电文总码长为,而哈夫曼树是WPL最小的二叉树,因此哈夫曼编码的码长最小。

    3.哈夫曼编码实例

    四种字符以及他们的权值:a:30, b:5, c:10, d:20

    第一步:构建哈夫曼树

    第二步:为哈夫曼树的每一条边编码

    第三步:生成哈夫曼编码表

    4.代码实现

    4.1哈夫曼树定义

    哈夫曼树的存储结构:采用静态三叉链表

    #include<stdio.h>
    #include<stdlib.h>
    #include<string.h>
    
    #define N 4//带权值的叶子节点数或者是需要编码的字符数
    #define M 2*N-1//n个叶子节点构造的哈夫曼树有2n-1个结点
    #define MAX 10000
    typedef char TElemType;
    //静态三叉链表存储结构
    typedef struct{
    	//TElemType data;
    	unsigned int weight;//权值只能是正数
    	int parent;
    	int lchild;
    	int rchild;
    }HTNode;//, *HuffmanTree;
    typedef HTNode HuffmanTree[M+1];//0号单元不使用
    
    typedef char * HuffmanCode[N+1];//存储每个字符的哈夫曼编码表,是一个字符指针数组,每个数组元素是指向字符指针的指针

     

    4.2构造哈夫曼树

    //构造哈夫曼树
    void createHuffmanTree(HuffmanTree &HT, int *w, int n){
    	if(n <= 1)
    		return;
    	//对树赋初值
    	for(int i = 1; i <= n; i++){//HT前n个分量存储叶子节点,他们均带有权值
    		HT[i].weight = w[i];
    		HT[i].lchild = 0;
    		HT[i].parent = 0;
    		HT[i].rchild = 0;
    	}
    	for(int i=n+1; i <=M; i++){//HT后m-n个分量存储中间结点,最后一个分量显然是整棵树的根节点
    		HT[i].weight = 0;
    		HT[i].lchild = 0;
    		HT[i].parent = 0;
    		HT[i].rchild = 0;
    	}
    	//开始构建哈夫曼树,即创建HT的后m-n个结点的过程,直至创建出根节点。用哈夫曼算法
    	for(int i = n+1; i <= M; i++){
    		int s1, s2;
    		select(HT, i-1, s1, s2);//在HT[1...i-1]里选择parent为0的且权值最小的2结点,其序号分别为s1,s2,parent不为0说明该结点已经参与构造了,故不许再考虑
    		HT[s1].parent = i;
    		HT[s2].parent = i;
    		HT[i].lchild = s1;
    		HT[i].rchild = s2;
    		HT[i].weight = HT[s1].weight + HT[s2].weight;
    	}
    }

     

    //在HT[1...k]里选择parent为0的且权值最小的2结点,其序号分别为s1,s2,parent不为0说明该结点已经参与构造了,故不许再考虑
    void select(HuffmanTree HT, int k, int &s1, int &s2){
    	//假设s1对应的权值总是<=s2对应的权值
    	unsigned int tmp = MAX, tmpi = 0;
    	for(int i = 1; i <= k; i++){
    		if(!HT[i].parent){//parent必须为0
    			if(tmp > HT[i].weight){
    				tmp = HT[i].weight;//tmp最后为最小的weight
    				tmpi = i;
    			}
    		}
    	}
    	s1 = tmpi;
    	
    	tmp = MAX;
    	tmpi = 0;
    	for(int i = 1; i <= k; i++){
    		if((!HT[i].parent) && i!=s1){//parent为0
    			if(tmp > HT[i].weight){
    				tmp = HT[i].weight;
    				tmpi = i;
    			}
    		}
    	}
    	s2 = tmpi;
    }

     

    打印哈夫曼树

    //打印哈夫曼满树
    void printHuffmanTree(HuffmanTree HT, char ch[]){
    	printf("\n");
    	printf("data, weight, parent, lchild, rchild\n");
    	for(int i = 1; i <= M; i++){
    		if(i > N){
    			printf("  -, %5d, %5d, %5d, %5d\n", HT[i].weight, HT[i].parent, HT[i].lchild, HT[i].rchild);
    		}else{
    			printf("  %c, %5d, %5d, %5d, %5d\n", ch[i], HT[i].weight, HT[i].parent, HT[i].lchild, HT[i].rchild);
    		}
    	}
    	printf("\n");
    }

     

    4.3编码

    为哈夫曼树的每一条分支编码,并生成哈夫曼编码表HC

    //为每个字符求解哈夫曼编码,从叶子到根逆向求解每个字符的哈夫曼编码
    void encodingHuffmanCode(HuffmanTree HT, HuffmanCode &HC){
    	//char *tmp = (char *)malloc(n * sizeof(char));//将每一个字符对应的编码放在临时工作空间tmp里,每个字符的编码长度不会超过n
    	char tmp[N];
    	tmp[N-1] = '\0';//编码的结束符
    	int start, c, f;
    	for(int i = 1; i <= N; i++){//对于第i个待编码字符即第i个带权值的叶子节点
    		start = N-1;//编码生成以后,start将指向编码的起始位置
    		c = i;
    		f = HT[i].parent;
    
    		while(f){//f!=0,即f不是根节点的父节点
    			if(HT[f].lchild == c){
    				tmp[--start] = '0';
    			}else{//HT[f].rchild == c,注意:由于哈夫曼树中只存在叶子节点和度为2的节点,所以除开叶子节点,节点一定有左右2个分支
    				tmp[--start] = '1';
    			}
    			c = f;
    			f = HT[f].parent;
    		}
    		HC[i] = (char *)malloc((N-start)*sizeof(char));//每次tmp的后n-start个位置有编码存在
    		strcpy(HC[i], &tmp[start]);//将tmp的后n-start个元素分给H[i]指向的的字符串
    	}
    }

    打印哈夫曼编码表,当编码表生成以后,以后就可以对字符串进行编码了,只要对应编码表进行转换即可

    //打印哈夫曼编码表
    void printHuffmanCoding(HuffmanCode HC, char ch[]){
    	printf("\n");
    	for(int i = 1; i <= N; i++){
    		printf("%c:%s\n", ch[i], HC[i]);
    	}
    	printf("\n");
    }

     

    4.4解码

    //解码过程:从哈夫曼树的根节点出发,按字符'0'或'1'确定找其左孩子或右孩子,直至找到叶子节点即可,便求得该字串相应的字符
    void decodingHuffmanCode(HuffmanTree HT, char *ch, char testDecodingStr[], int len, char *result){
    	int p = M;//HT的最后一个节点是根节点,前n个节点是叶子节点
    	int i = 0;//指示测试串中的第i个字符
    	//char result[30];//存储解码以后的字符串
    	int j = 0;//指示结果串中的第j个字符
    	while(i<len){
    		if(testDecodingStr[i] == '0'){
    			p = HT[p].lchild;
    		}
    		if(testDecodingStr[i] == '1'){
    			p = HT[p].rchild;
    		}
    
    		if(p <= N){//p<=N则表明p为叶子节点,因为在构造哈夫曼树HT时,HT的m个节点中前n个节点为叶子节点
    			result[j] = ch[p];
    			j++;
    			p = M;//p重新指向根节点
    		}
    		i++;
    	}
    	result[j] = '\0';//结果串的结束符	
    }

     

    4.5演示

    int main(){
    	HuffmanTree HT;
    	
    	TElemType ch[N+1];//0号单元不使用,存储n个等待编码的字符
    	int w[N+1];//0号单元不使用,存储n个字符对应的权值
    	printf("请输入%d个字符以及该字符对应的权值(如:a,20):\n", N);
    	for(int i = 1; i <= N; i++){
    		scanf("%c,%d", &ch[i], &w[i]);
    		getchar();//吃掉换行符
    	}//即w里第i个权值对应的是ch里第i个字符元素
    
    
    	createHuffmanTree(HT, w , N);//构建哈夫曼树
    	printHuffmanTree(HT, ch);
    	
    	HuffmanCode HC;//HC有n个元素,每个元素是一个指向字符串的指针,即每个元素是一个char *的变量
    	encodingHuffmanCode(HT, HC);//为每个字符求解哈夫曼编码
    	printHuffmanCoding(HC, ch);
    
    	//解码测试用例:abaccda----01000101101110
    	char * testDecodingStr = "01000101101110";
    	int testDecodingStrLen = 14;
    	printf("编码%s对应的字符串是:", testDecodingStr);
    	char result[30];//存储解码以后的字符串
    	decodingHuffmanCode(HT, ch, testDecodingStr, testDecodingStrLen, result);//解码(译码),通过一段给定的编码翻译成对应的字符串
    	printf("%s\n", result);
    
        return 0;
    }


     

    本文中的代码可从这里下载:https://github.com/qingyujean/data-structure

    展开全文
  • C++实现哈夫曼树的生成已经解码。绝对好用!
  • #define MAXLEAFNUM 50 //最优二叉树中最多叶子数目 typedef struct node{ char ch;//结点表示字符 int weight;//权值 int parent;//结点父结点下标,为0表示无父结点 int lChild,rChild;//结点左右...
    #define MAXLEAFNUM 50 //最优二叉树中的最多叶子数目
    
    typedef struct node{
        char ch;//结点表示的字符
        int weight;//权值
        int parent;//结点的父结点的下标,为0表示无父结点
        int lChild,rChild;//结点的左右孩子结点的下标,为0表示无孩子结点
    }HuffmanTree[2*MAXLEAFNUM];
    
    typedef char* HuffmanCode[MAXLEAFNUM + 1];
    
    void select(HuffmanTree HT,int n,int &s1,int &s2)
    {
        s1 = 1;
        s2 = 2;
        int nMinW = HT[1].weight;
    
        for(int  i = 1; i <= n;i++){
            if(HT[i].parent != 0){
                continue;
            }
            if(nMinW > HT[i].weight){
                nMinW = HT[i].weight;
                s1 = i;
            }
        }
        if(s1 != 1){
            nMinW = HT[1].weight;
        }else{
            nMinW = HT[2].weight;
        }
        for(int  i = 1; i <= n -1;i++){
            if(HT[i].parent != 0 || i == s1){
                continue;
            }
    
            if(nMinW > HT[i].weight){
                nMinW = HT[i].weight;
                s2 = i;
            }
        }
    }
    
    //创建哈夫曼树
    void createHTree(HuffmanTree HT,char *c,int *w,int n)
    {
        int i,s1,s2;
        if(n <= 1){
            return;
        }
    
        for(i = 1; i <= n;i++){//构造n棵只有根结点的树
            HT[i].ch = c[i - 1];
            HT[i].weight = w[i - 1];
            HT[i].parent = HT[i].lChild = HT[i].rChild = 0;
        }
        for(;i < 2 * n;i++){
            HT[i].parent = HT[i].lChild = HT[i].rChild = 0;
        }
    
        for(i = n + 1; i < 2 *n; i++){
            select(HT,i - 1,s1,s2);
            HT[s1].parent = i;
            HT[s2].parent = i;
            HT[i].lChild = s1;
            HT[i].rChild = s2;
            HT[i].weight = HT[s1].weight + HT[s2].weight;
        }
    }
    
    //根据给定的哈夫曼树,从每个叶子结点出发追溯到根,逆向找出最优二叉树中叶子结点的编码
    //n个叶子结点在哈夫曼HT中的下标为1~n,第i(1<= i <= n)个叶子的编码存放在HC[i]中
    void HuffmanCoding(HuffmanTree HT,HuffmanCode HC,int n)
    {
        char *cd;
        int i,start,c,f;
    
        if(n <= 1){
            return;
        }
        cd = (char*)malloc( n * sizeof(char));//申请足够的空间存储编码
        cd[n -1] = '\0';//结尾符
        for(i = 1; i <= n;i++){
            start = n - 1;
            for(c = i,f = HT[i].parent;f != 0;c = f,f = HT[f].parent){//执行完一次后继续向上回溯结点
                if(HT[f].lChild == c){//如果当前结点与父结点的左节点相等,则对应字符编码为0,否则为1
                    cd[start] = '0';
                }else{
                    cd[start] = '1';
                }
                start--;
            }
            HC[i] = (char*)malloc((n - start) * sizeof(char));
            strcpy(HC[i],&cd[start]);
            free(cd);
        }
    }
    
    //利用最优二叉树译码
    void Decoding(HuffmanTree HT,int n,char *buff)
    {
        int p = 2 * n - 1;
        while (*buff) {
            if((*buff) == '0'){
                p = HT[p].lChild;
            }else{
                p = HT[p].rChild;
            }
    
            if(HT[p].lChild == 0 && HT[p].rChild == 0){
                cout << HT[p].ch << endl;
                p = 2 * n - 1;
            }
            buff++;
        }
    }
    

     

    展开全文
  • 大部分代码是以前写,所以是C语言,只完成了生成哈夫曼树。 复习期间又完善了哈夫曼树生成编码部分。 如果使用C++/Java实现,利面向对象优势应该更好。 这里不再阐述哈夫曼编码为何是最短前缀编码理论知识 ...

    数据结构1:哈夫曼数和哈夫曼编码
    C语言,如果使用C++/Java实现,利面向对象的优势应该更好。

    这里不再阐述哈夫曼编码为何是最短前缀编码的理论知识
    哈夫曼编码实现原理非常简单:
    1.利用贪心的思想,构造当前最优树
    2.进而构造出整体的最优树
    3.再利用哈夫曼树生成哈夫曼编码
    实现的难点在于数据结构的设计,操作数据结构也要仔细。
    尽量通过模块化的思想逐步解决。

    首先是结构体和函数声明
    主要是三个函数:

    1. Huffman_List *init_huffman_list(char *c, int n);
      根据输入的字符串信息,生成森林list,存放huffman结点。

    2. Huffman_Tree *construct_huffman_tree(char *c, int n);
      从list中,不断移除掉两个权值最小结点,加入到哈夫曼树,并根据权值这和创建新的结点加入到list。

    3. Huffman_Table *generate_huffman_table(char *c, int n);
      根据遍历哈夫曼树,并生成哈夫曼编码

    #include<stdio.h>
    #include<string.h>
    #include<stdlib.h>
    
    typedef struct huffman_node {
    	int weight;
    	char value;
    	char code;//被放置在左孩子则是0,右孩子则是1
    	struct huffman_node *parent;
    	struct huffman_node *next;
    	struct huffman_node *left;
    	struct huffman_node *right;
    }Huffman_Node;
    
    typedef struct huffman_tree {
    	Huffman_Node *root;
    }Huffman_Tree;
    
    //list:森林,即没有加入哈夫曼树的结点或者根节点,链表实现,便于插入删除操作
    typedef struct huffman_list {
    	int n;
    	Huffman_Node *head;
    }Huffman_List;
    
    //编码
    typedef struct huffman_code {
    	char value;
    	char *code_str;
    	struct huffman_code *next;
    }Huffman_Code;
    
    //编码表,存储多个编码
    typedef struct huffman_table {
    	Huffman_Code *head;
    }Huffman_Table;
    
    Huffman_List *init_huffman_list(char *c, int n);
    Huffman_Tree *construct_huffman_tree(char *c, int n);
    Huffman_Table *generate_huffman_table(char *c, int n);
    void generate_huffman_code(Huffman_Node *root, Huffman_Table *huffman_table, char code, int deep);
    void add_code_str(Huffman_Table *huffman_table, char value, char *code_str);
    void free_huffman_node(Huffman_Node *root);
    int find_and_upweight(Huffman_List *huffman_list, char key);
    Huffman_Node *add_node(Huffman_List *huffman_list, char value, int weight);
    Huffman_Node *remove_min(Huffman_List *huffman_list);
    

    下面是详细代码

    Huffman_Node *remove_min(Huffman_List *huffman_list)//把最大的结点从list中移除,并将结点返回
    {
    	Huffman_Node *pre_p = (Huffman_Node *)malloc(sizeof(Huffman_Node));//辅助结点,表示当前结点的前一个结点,便于删除结点
    	Huffman_Node *bak = pre_p;//备份,便于释放内存
    	pre_p->next = huffman_list->head;
    	Huffman_Node *min_pre_node = pre_p;
    	Huffman_Node *p = pre_p->next;
    	int min_weight = p->weight;
    	while (p != NULL)
    	{
    		if (p->weight < min_weight)
    		{
    			min_pre_node = pre_p;
    			min_weight = p->weight;
    		}
    		pre_p = p;
    		p = p->next;
    	}
    	//如果最小的结点是头结点,pre_p仍然指向辅助的结点,修改它对List没有作用,所以特殊处理
    	if (min_pre_node->next == huffman_list->head)
    	{
    		p = huffman_list->head;
    		huffman_list->head = huffman_list->head->next;
    	}
    	else
    	{
    		p = min_pre_node->next;
    		min_pre_node->next = p->next;
    	}
    	huffman_list->n--;
    	free(bak);
    	return p;
    }
    /*
    添加一个结点到list,并将新结点返回
    在头部插入,比在尾部插入效率更高
    */
    Huffman_Node *add_node(Huffman_List *huffman_list,char value,int weight)
    {
    	Huffman_Node *new_node = (Huffman_Node *)malloc(sizeof(Huffman_Node));
    	new_node->weight = weight;
    	new_node->value = value;
    	new_node->next = huffman_list->head;
    	new_node->parent = new_node->left = new_node->right = NULL;//不要忘记初始化为NULL
    	huffman_list->head = new_node;
    	huffman_list->n++;
    	return new_node;
    }
    /*
    查找是否存在相同字符,找到则weight+1
    返回0或1
    */
    int find_and_upweight(Huffman_List *huffman_list,char key)
    {
    	Huffman_Node *p = huffman_list->head;
    	while (p != NULL)
    	{
    		if (p->value == key)
    		{
    			p->weight=p->weight+1;
    			return 1;
    		}
    		p = p->next;
    	}
    	return 0;
    }
    
    void free_huffman_node(Huffman_Node *root)//递归释放树结点
    {
    	if (root == NULL)return;
    	Huffman_Node *left = root->left;
    	Huffman_Node *right = root->right;
    	free(root);
    	free_huffman_node(left);
    	free_huffman_node(right);
    }
    
    void add_code_str(Huffman_Table *huffman_table, char value, char *code_str)
    {
    	Huffman_Code *new_code = (Huffman_Code*)malloc(sizeof(Huffman_Code));
    	new_code->value = value;
    	new_code->code_str = code_str;
    	new_code->next = huffman_table->head;
    	huffman_table->head = new_code;
    }
    
    
    Huffman_List *init_huffman_list(char *c, int n)//初始化list
    {
    	Huffman_List *huffman_list = (Huffman_List*)malloc(sizeof(Huffman_List));
    	Huffman_Node *p = (Huffman_Node*)malloc(sizeof(Huffman_Node));
    	p->value = c[0];
    	p->weight = 1;
    	p->parent =p->next =p->left=p->right= NULL;
    	huffman_list->head = p;
    	huffman_list->n = 1;
    	int i = 1;
    	while (i < n)
    	{
    		if (!find_and_upweight(huffman_list, c[i]))//没有找到,则添加
    			add_node(huffman_list,c[i],1);//出现一次新的字符,增加node,weight=1
    		i++;
    	}
    	return huffman_list;
    }
    
    /*
    构造哈夫曼树
    */
    Huffman_Tree *construct_huffman_tree(char *c,int n)
    {
    	Huffman_List *huffman_list =init_huffman_list(c,n);
    	Huffman_Tree *huffman_tree = (Huffman_Tree *)malloc(sizeof(Huffman_Tree));
    	//huffman_tree->leaf_nodes_n = huffman_list->n;//叶子结点数等于初始的list->n
    
    	Huffman_Node *left;
    	Huffman_Node *right;
    	Huffman_Node *root;
    	int weight_sum;
    	//哈夫曼算法核心:贪心思想
    	while (huffman_list->n > 1)//只剩下1个结点,说明只有root,构造完成
    	{
    		left = remove_min(huffman_list);
    		right = remove_min(huffman_list);
    		weight_sum = left->weight + right->weight;
    		root = add_node(huffman_list, '#', weight_sum);//每次循环,删除两个最小的,再把权值加起来的新结点插入list
    		left->parent = right->parent = root;
    		root->left = left;
    		root->right = right;
    	}
    	free(huffman_list);//构造哈夫曼树之后,释放list
    	huffman_tree->root = root;
    	printf("成功构造哈夫曼树\n");
    	return huffman_tree;
    }
    
    void generate_huffman_code(Huffman_Node *root,Huffman_Table *huffman_table,char code,int deep)//codes[i],value[j]
    {
    	root->code = code;
    	if (root->left == NULL && root->right == NULL)//访问到叶子结点,则生成一串编码
    	{
    		Huffman_Node *p = root;
    		char *code_str=(char *)malloc((deep+1)*sizeof(char));//根据树深度(高度),动态申请code内存,+1个字节用来保存结束符\0
    		code_str[deep] = '\0';
    		int i = deep-1;
    		while (p != NULL)
    		{
    			code_str[i] = p->code;
    			p = p->parent;
    			i--;
    		}
    		add_code_str(huffman_table,root->value,code_str);
    		return;
    	}
    	generate_huffman_code(root->left, huffman_table, '0',deep+1);
    	generate_huffman_code(root->right, huffman_table, '1', deep + 1);
    }
    
    Huffman_Table *generate_huffman_table(char *c, int n)//生成哈夫曼表
    {
    	Huffman_Tree *huffman_tree = construct_huffman_tree(c, n);//根据字符串构建哈夫曼树
    	Huffman_Table *huffman_table = (Huffman_Table*)malloc(sizeof(Huffman_Table));
    	huffman_table->head = NULL;//不要忘了初始化为NULL
    	generate_huffman_code(huffman_tree->root, huffman_table,'0',1);//递归去遍历树,并生成哈夫曼编码表,根设为0,后面要去掉
    
    	free_huffman_node(huffman_tree->root);//利用哈夫曼树生成编码之后,记得释放所有树结点
    	free(huffman_tree);
    	printf("成功生成哈夫曼编码\n");
    	return huffman_table;
    }
    

    测试:

    int main()
    {
    	char c[100] = {0};
    	scanf("%s",c);
    	Huffman_Table *huffman_table=generate_huffman_table(c,(int)strlen(c));
    	Huffman_Code *p = huffman_table->head;
    	Huffman_Code *p_next = p->next;
    
    	while(p!=NULL)
    	{
    		printf("%c:%s\n",p->value,p->code_str);
    		p = p->next;
    	}
    
    	//释放编码表
    	p= huffman_table->head;
    	while (p != NULL)
    	{
    		p_next = p->next;
    		free(p);
    		p = p_next;
    	}
    	free(huffman_table);
    	system("pause");
    	return 0;
    }
    

    测试结果:
    输入abcdefgabca即:{a:3},{b:2},{c:2},{d:1},{e:1},{f:1}
    不要看第一个字符:
    如a的编码应该是是:11
    在这里插入图片描述

    根据编码表,从根结点开始,0是往左走,1是往右走,得到的树应该长这样:
    在这里插入图片描述
    只是简单测试了一下,有哪里不对的地方请指出。

    展开全文
  • 本文实例讲述了C++数据结构与算法之哈夫曼树的实现方法。分享给大家供大家参考,具体如下: 哈夫曼树又称最优二叉树,是一类带权路径长度最短的树。 对于最优二叉树,权值越大的结点越接近树的根结点,权值越小的...
  • 哈夫曼树的基本概念 二叉树的经典应用就是哈夫曼(Haffman)树,也称最优二叉树,是指对于一组带有确定权值的叶结点、构造的具有最小带权路径长度的二叉树。 二叉树的路径长度是指由根结点到所有的叶结点的路径...
  • 概念上说,哈夫曼树是给定一组具有确定权值叶子结点,带权路径长度最小二叉树。 叶子结点权值:对叶子结点赋予一个有意义数值量。 二叉树带权路径长度:设二叉树具有n个带权值叶子结点,从根结点到...
  • 代码实现 哈夫曼树 哈夫曼树又称最优二叉树,是一种带权路径长度最短的二叉树。所谓树的带权路径长度,就是树中所有的叶结点的权值乘上其到根结点的路径长度(若根结点为0层,叶结点到根结点的路径长度为叶结点的层...
  • 代码实现哈夫曼树的创建,建立,构造,实现哈夫曼编码,实现思路和要点: 抓住哈夫曼树的性质,每轮选出2个权值最小的点进行构造树。 抓住哈夫曼编码的性质,从根出发,向左标0,向右标1. 哈夫曼树的构造思路: 已知...
  • 哈夫曼树(一)定义带权...没有度为1的结点2.n个叶子节点的哈夫曼树共有2n-1个结点树的特点:度为2结点和叶结点的关系n2=n0-1所以:当叶结点为n时,度为二的结点数为n-1因为哈夫曼没有度为一的结点,所以一共在树中...
  • 前言哈夫曼树是数据压缩编码算法基础,本文使用JavaScript语言实现了该算法。算法流程:输入待编码字符...算法实现树节点既然是树数据结构,就要有树节点,下面是树节点定义class Node {constructor(value, char...
  • 哈夫曼编码C代码实现--数据结构

    千次阅读 热门讨论 2019-06-14 16:56:02
    请读者结合上一篇哈夫曼树的博客,便于理解该篇文章。简单来说,哈夫曼编码是将构造的哈夫曼树按照左孩子都标记为0 右孩子都标记为1的原则。通过此种标记的手段标记的哈弗曼树能够将编码的长度压缩到最小。本程序中...
  • 哈夫曼树 (一)定义 带权路径长度WPL: 哈夫曼树(最优二叉树): WPL最小二叉树 (二)构造 将权值从小到大排序,后将权值最小两个并在一起成新二叉树 A5,E10,B15,D30,C40 (三...
  • 【C++数据结构哈夫曼树代码实现

    千次阅读 2017-03-14 21:00:59
    HuffeManTree.h#pragma once #include "Stack.h" // 我自己写栈 #include "Stack.cpp"template class CTree { public: CTree(void);public: T data = NULL; int weight = 1; CTree* lNode = nu
  • 数据结构实验之——哈夫曼树的实现目录说明代码测试用例 目录 说明 哈夫曼树的这个实验我是采用常用的左‘0’右‘1’来实现的,输入是用文本输入的,大家在用之前目录下要记得创建“HT.txt”文件o,下面的测试用例也...
  • 今天继续二叉树,今天讲讲哈夫曼树(Huffman Tree)。 文章目录Huffman Tree Huffman Tree 定义: Huffman Tree也是一种特殊的二叉树,这种树的所有叶子结点都带有权值,从中构造出带权路径长度最短的二叉树,即...
  • 数据结构哈夫曼树 在写代码前,我们先要了解一下什么是哈夫曼树 基本介绍 1) 给定 n 个权值作为 n 个叶子结点,构造一棵二叉树,若该树的带权路径长度(wpl)达到最小,称这样的二叉树为 最优二叉树,也称为哈夫曼树...
  • 题目是根据输入的字符以及字符出现的次数产生哈夫曼树并输出编码 思路大概都在注释里面,写了...typedef struct shu//定义哈夫曼树的结点 { char x; int number; struct shu* left; struct shu* right; }shu; typ
  • 数据结构之二叉树(五):哈夫曼树 基本介绍: 给定n个权值作为n个叶子节点,若该树的带权路径长度(WPL)达到最小,称这样的二叉树为最优二叉树,也称为哈夫曼树哈夫曼树是带权路径长度最短的树,权值最大的节点离...
  • 哈夫曼树的js实现

    2020-02-25 20:09:25
    前言 哈夫曼树是数据压缩编码算法的基础,本文使用...本文仅包含实现的代码以及注释。 注释比较丰富,相信不难理解。 算法实现 树节点 既然是树数据结构,就要有树节点,下面是树节点定义 class Node { construc...
  • //显示有n个叶子结点的哈夫曼树的编码表 int i; printf("哈夫曼编码如下 :\n"); putchar('\n'); cout 权值" 原始码" 哈夫曼编码" ; for (i = 1; i ; i++) { printf(" %d", w[i - 1]); printf(" %3c\t ", ...
  • HuffmanTree.h文件: 哈夫曼树的存储结构与创建函数 HuffmanCreatTest.cpp文件: 用于测试 效果图:(如下) 效果图: HuffmanTree.h文件: #include <stdio.h> #include <stdlib.h> typedef struct...
  • 前言本篇章主要介绍哈夫曼树及哈夫曼编码,包括哈夫曼树的一些基本概念、构造、代码实现以及哈夫曼编码,并用Python实现。1. 基本概念哈夫曼树(Huffman(Huffman(Huffman Tree)Tree)Tree),又称为最优二叉树,指的是...

空空如也

空空如也

1 2 3 4 5 ... 12
收藏数 229
精华内容 91
关键字:

哈夫曼树的代码实现数据结构

数据结构 订阅