精华内容
下载资源
问答
  • 哈夫曼树的生成以及编码 #include <stdio.h> #include <stdlib.h> #include <string.h> #include<iostream> using namespace std; typedef int ELEMTYPE; typedef struct HuffmanTree { ...

    哈夫曼树的生成以及编码

    #include <stdio.h>
    #include <stdlib.h>
    #include <string.h>
    #include<iostream>
    using namespace std;
    
    typedef int ELEMTYPE;
    typedef struct HuffmanTree
    {
    	ELEMTYPE weight;
    	char value;
    	struct HuffmanTree* lchild;
    	struct HuffmanTree* rchild;
    }HuffmanNode;
    
    // 构建哈夫曼树
    HuffmanNode* createHuffmanTree(int* a,char* b,int n)
    {
    	int i, j;
    	HuffmanNode **temp, *hufmTree;
    	temp = (HuffmanNode **)malloc(n * sizeof(HuffmanNode));
    	for (i = 0; i < n; ++i)     // 将数组a中的权值赋给结点中的weight
    	{
    		temp[i] = (HuffmanNode*)malloc(sizeof(HuffmanNode));
    		temp[i]->weight = a[i];
    		temp[i]->lchild = temp[i]->rchild = NULL;
    		temp[i]->value = b[i];
    	}
    
    	for (i = 0; i < n - 1; ++i)       // n-1次合并
    	{
    		int small1 = -1, small2;      // small1、small2分别作为最小和次小权值的下标
    		for (j = 0; j < n; ++j)         // 先将最小的两个下标赋给small1、small2(注意:对应权值未必最小)
    		{
    			if (temp[j] != NULL && small1 == -1)
    			{
    				small1 = j;
    				continue;
    			}
    			else if (temp[j] != NULL)
    			{
    				small2 = j;
    				break;
    			}
    		}
    		if (small1 > small2)
    		{
    			int t = small1;
    			small1 = small2;
    			small2 = t;
    		}
    		for (j = small2; j < n; ++j)    // 比较权值,挪动small1和small2使之分别成为最小和次小权值的下标
    		{
    			if (temp[j] != NULL)
    			{
    				if (temp[j]->weight < temp[small1]->weight)
    				{
    					small2 = small1;
    					small1 = j;
    				}
    				else if (temp[j]->weight < temp[small2]->weight)
    				{
    					small2 = j;
    				}
    			}
    		}
    		hufmTree = (HuffmanNode*)malloc(sizeof(HuffmanNode));
    		hufmTree->weight = temp[small1]->weight + temp[small2]->weight;
    		hufmTree->lchild = temp[small1];
    		hufmTree->rchild = temp[small2];
    
    		temp[small1] = hufmTree;
    		temp[small2] = NULL;
    	}
    	return hufmTree;
    }
    
    
    // 递归进行哈夫曼编码
    void HuffmanCode(HuffmanNode* hufmTree, int depth,int*code)      // depth是哈夫曼树的深度
    {
    	if (hufmTree)
    	{
    		if (hufmTree->lchild == NULL && hufmTree->rchild == NULL)
    		{
    			printf("%c的哈夫曼编码为 ",  hufmTree->value);
    			int i;
    			for (i = 0; i < depth; ++i)
    			{
    				printf("%d", code[i]);
    			}
    			printf("\n");
    		}
    		else
    		{
    			code[depth] = 0;
    			HuffmanCode(hufmTree->lchild, depth + 1,code);
    			code[depth] = 1;
    			HuffmanCode(hufmTree->rchild, depth + 1,code);
    		}
    	}
    }
    
    
    
    int main()
    {
    	int i, n;
    	char string[100];
    	printf("请输入叶子结点的个数:\n");
    	
    
    	scanf("%d", &n);
    	
    	int* arr;
    	arr = (int*)malloc(n * sizeof(ELEMTYPE));
    	printf("请输入%d个叶子结点的权值及其各自代表的字符:\n", n);
    	for (i = 0; i < n; ++i)
    	{
    		printf("第%d个",i+1); 
    		scanf("%d", &arr[i]);
    		scanf("%c", &string[i]);
    	}
    	HuffmanNode* hufmTree = NULL;
    	hufmTree = createHuffmanTree(arr,string,n);
    	int code[100];
    	printf("\n各叶子结点的哈夫曼编码为:\n");
    	HuffmanCode(hufmTree, 0,code);
    
    	return 0;
    }
    
    
    
    

    注意输入时权值与字符之间不加符号,否则会将空格当作字符,可以加一个getchar()来实现

    本文改编自
    https://blog.csdn.net/F__shigang/article/details/65442550

    删改了一些内容。

    展开全文
  • 哈夫曼树的生成及哈夫曼编码

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

    首先构造哈夫曼树结构体,初始化哈夫曼树的四个无符号整型域,输入文本,统计各个字符的权值,然后构建哈夫曼树,从根到叶子逆向求哈夫曼树的编码。

    #include"stdio.h"
    #include"string.h"
    #include"malloc.h"
    #include"iostream"
    using namespace std;
    typedef struct{
        unsigned int weight;
        unsigned int parent,lchild,rchild;
    }HTNode,*HuffTree;
    typedef  char  **HuffCode;
    
    
    void Select(HuffTree &Ht, int m, int &S1, int &S2)     
    {/*
     Select函数,每次从前面数据中选择2个权值(weight值)最小的,将 
    最小的两个下标赋给s1,s2 
    
    */
        int j;
        S1 = 0;
        S2 = 0;
        for (j = 1; j <= m; j++)
        {
            if (Ht[j].parent == 0 && Ht[j].weight != 0)
            {
                if (Ht[j].weight<Ht[S1].weight)
                    S1 = j;
            }
        }
        for (j = 1; j <= m; j++)
        {
            if (Ht[j].parent == 0 && j != S1&&Ht[j].weight != 0)
            {
                if (Ht[j].weight<Ht[S2].weight)
                    S2 = j;
            }
        }
    
    } 
    
    
    
    void HuffmanCoding(HuffTree &Ht,HuffCode &Hc,int n){  //哈夫曼编码函数 
    if(n<=1)return;
    int m,i,s1, s2;
    HuffTree p;
    m =2*n-1; 
    Ht = (HuffTree)malloc((m + 1) * sizeof(HTNode));
    char ch[100];
    for (p = Ht + 1, i = 1; i <= m; ++i, ++p) {     //初始化哈夫曼树各个值 
        p->weight = 0;
        p->parent = 0;
        p->lchild = 0;
        p->rchild = 0;
    }
    cin >> ch;                                   //读入一段文本 
    for (int i = 0; ch[i] !='\0'; i++) {
        Ht[ch[i] - 'a'+1].weight++;               //当文本还没有结束时,统计各个字符的权值 
    }
    for(i=n+1;i<=m;++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;
    }
    
    // 从叶子到根逆向求每个字符的哈夫曼编码 
    Hc=(HuffCode)malloc((n+1)*sizeof(char*));
    char * cd=(char*)malloc((n)*sizeof(char));
    int c,f;
    cd[n-1]='\0';                 //编码结束符 
    int start;
    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)cd[--start]='0';
        else cd[--start]='1';
        }
        //cd[n-1]='\0';
        Hc[i]=(char *)malloc((n-start)*sizeof(char));
        strcpy(Hc[i],&cd[start]);
    }
    free(cd);
    
    }
    
    void show(HuffCode &Hc, int n)//输出哈夫曼编码  
    {
        int i, k;
        cout<<"  输出哈夫曼编码:\n"; //输出哈夫曼编码  
        for (i = 1; i<=n; i++)
        {
                cout<< Hc[i];
                cout<<"\n"; 
        }
    
    }
    

    然后在主函数中调用,加入输入输出语句即可

    #include"1.h"
    
    using namespace std;
    
    int main()
    {
        HuffTree ht;
        HuffCode hc;
        int n;
        cout << "请输入文本";
        HuffmanCoding(ht,hc,26);
        show(hc,26);
        system("pause");
    }
    
    展开全文
  • 构造哈夫曼树生成哈夫曼编码

    千次阅读 多人点赞 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带权路径长度较小,...

    一、什么是哈夫曼树?

    哈夫曼树是一种带权路径长度最短的二叉树,也称为最优二叉树。用一幅图来说明:

    它们的带权路径长度分别为:

    图a: WPL=5*2+7*2+2*2+13*2=54

    图b: WPL=5*3+2*3+7*2+13*1=48

    可见,图b的带权路径长度较小,可以证明图b就是哈夫曼树(也称为最优二叉树)。

    二、如何构建哈夫曼树

    一般按下面步骤构建:

    1,将所有左,右子树都为空的作为根节点。

    2,在森林中选出两棵根节点的权值最小的树作为一棵新树的左,右子树,且置新树的附加根节点的权值为其左,右子树上根节点的权值之和。注意,左子树的权值应小于右子树的权值。

    3,从森林中删除这两棵树,同时把新树加入到森林中。

    4,重复2,3步骤,直到森林中只有一棵树为止,此树便是哈夫曼树。

    下面是构建哈夫曼树的图解过程:

    三、哈夫曼编码

    利用哈夫曼树求得的用于通信的二进制编码称为哈夫曼编码。树中从根到每个叶子节点都有一条路径,对路径上的各分支约定指向左子树的分支表示"0"码,指向右子树的分支表示"1"码,取每条路径上的"0"或"1"的序列作为各个叶子节点对应的字符编码,即是哈夫曼编码。

    上图例子来说:

    A,B,C,D对应的哈夫曼编码分别为:111,10,110,0

    用图说明如下:

    记住,设计电文总长最短的二进制前缀编码,就是以n个字符出现的频率作为权构造一棵哈夫曼树,由哈夫曼树求得的编码就是哈夫曼编码。

    四、算法实现

    /**
    *    实验题目:
    *        构造哈夫曼树和生成哈夫曼编码
    *    实验目的:
    *        领会哈夫曼的构造过程以及哈夫曼编码的生成过程
    *    实验内容:
    *        设计程序,构造一颗哈夫曼树,输出对应的哈夫曼
    *    编码和平均查找长度。并用如下数据进行验证:
    *    单词以及出现的频度
    *    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
    *    备注:二叉树中叶子结点个数为n,则二叉树中结点总数为(2 * n - 1)
    */

    #include <stdio.h>
    #include <string.h>

    #define N   (50)        // 树中叶子结点数最大值
    #define M   (2 * N - 1) // 树中结点总数最大值

    typedef struct
    {
        char data[5]; // 结点值
        int weight; // 权重
        int parent; // 双亲结点
        int lchild; // 左孩子结点
        int rchild; // 右孩子结点
    }HTNode; // 声明哈夫曼树结点类型

    typedef struct
    {
        char cd[N]; // 存放哈夫曼编码
        int start;
    }HCode; // 声明哈夫曼编码类型

    /*-------------由含有n个叶子结点的ht构造完整的哈夫曼树-----------------*/
    static void create_huffman_tree(HTNode ht[], int n)
    {
        int i;
        int k;
        int lnode;
        int rnode;
        int min1;
        int min2;

        // 所有结点的相关域设置初值为-1
        for(i = 0; i < 2 * n - 1; i++)
            ht[i].parent = ht[i].lchild = ht[i].rchild = -1;
        for(i = n; i < 2 * n - 1; i++) // 构造哈夫曼树的分支结点
        {
            min1 = min2 = 32767;
            lnode = rnode = -1;
            for(k = 0; k <= i - 1; k++) // 查找最小和次小的结点
            {
                if(ht[k].parent == -1) // 只在尚未构造二叉树的结点中查找
                {
                    if(ht[k].weight < min1)
                    {
                        min2 = min1;
                        rnode = lnode;
                        min1 = ht[k].weight;
                        lnode = k;
                    }
                    else if(ht[k].weight < min2)
                    {
                        min2 = ht[k].weight;
                        rnode = k;
                    }
                }
            }
            ht[lnode].parent = i; // 合并两个最小和次小的结点
            ht[rnode].parent = i;
            ht[i].weight = ht[lnode].weight + ht[rnode].weight; // 计算双亲结点的权重
            ht[i].lchild = lnode; // 设置双亲结点的左孩子
            ht[i].rchild = rnode; // 设置双亲结点的右孩子
        }
    }

    /*-------------由哈夫曼树ht构造哈夫曼编码hcd-----------------*/
    static void create_huffman_code(HTNode ht[], HCode hcd[], int n)
    {
        int i;
        int f;
        int c;
        HCode hc;

        for(i = 0; i < n; i++) // 根据哈夫曼树构造所有叶子结点的哈夫曼编码
        {
            hc.start = n;
            c = i;
            f = ht[i].parent;
            while(f != -1) // 循环直到树根结点
            {
                if(ht[f].lchild == c) // 处理左孩子结点
                    hc.cd[hc.start--] = '0';
                else // 处理右孩子结点
                    hc.cd[hc.start--] = '1';
                c = f;
                f = ht[f].parent;
            }
            hc.start++; // start指向哈夫曼编码最开始字符
            hcd[i] = hc;
        }
    }

    /*-------------输出哈夫曼编码-----------------*/
    static void display_huffman_code(HTNode ht[], HCode hcd[], int n)
    {
        int i;
        int k;
        int sum = 0;
        int m = 0;
        int j;

        printf("输出哈夫曼编码:\n");
        for(i = 0; i < n; i++)
        {
            j = 0;
            printf("      %s:\t", ht[i].data);
            for(k = hcd[i].start; k <= n; k++)
            {
                printf("%c", hcd[i].cd[k]);
                j++;
            }
            m += ht[i].weight;
            sum += ht[i].weight * j;
            printf("\n");
        }

        printf("\n平均长度 = %g\n", 1.0 * sum / m);
    }

    int main(void)
    {
        int n = 15;
        int i;
        HTNode ht[M];
        HCode hcd[N];
        char *str[] = {"The", "of", "a", "to", "and", "in", "that", "he", "is", "at", "on", "for", "His", "are", "be"};
        int fnum[] = {1192, 677, 541, 518, 462, 450, 242, 195, 190, 181, 174, 157, 138, 124, 123};

        for(i = 0; i < n; i++)
        {
            strcpy(ht[i].data, str[i]);
            ht[i].weight = fnum[i];
        }
        create_huffman_tree(ht, n); // 创建哈夫曼树
        create_huffman_code(ht, hcd, n); // 构造哈夫曼编码
        display_huffman_code(ht, hcd, n); // 输出哈夫曼编码

        return 0;
    }
    测试结果:

    输出哈夫曼编码:
         The:      01
         of:       101
         a:        001
         to:       000
         and:      1110
         in:       1101
         that:     11110
         he:       11001
         is:       11000
         at:       10011
         on:       10010
         for:      10001
         His:      10000
         are:      111111
         be:       111110

    平均长度 = 3.56208

    展开全文
  • C/C++实现哈夫曼树生成哈夫曼编码

    千次阅读 2019-07-01 14:52:39
    然后将相加得到的值从新放入,然后又从中找到最小的两个值,然后用这个两个值一直相加,直到只剩最后一个值,将这个值作为哈夫曼树的根。 生成哈夫曼编码,如果是左子树的话为0,右子树的话为1,从父节点还是往下找...

    用C语言实现哈夫曼树和生成哈夫曼编码,首先生成哈夫曼树,哈夫曼树是从中选取权值最小的两个进行相加,将这两个分别做为生成的左子树和右子树,左子树要比右子树小。然后将相加得到的值从新放入,然后又从中找到最小的两个值,然后用这个两个值一直相加,直到只剩最后一个值,将这个值作为哈夫曼树的根。
    生成哈夫曼编码,如果是左子树的话为0,右子树的话为1,从父节点还是往下找。然后这串代码就是哈夫曼编码。

    上代码

    
    
    
     #include <iostream>
    #include <stdio.h>
    #include <stdlib.h>
    #include<bits/stdc++.h>
    
    
    using namespace std;
    
    
    const int Lsize  = 1000000;
    
    typedef struct{
    
       int order;//序号
       char character;//字符值
       int weight;//权重
       int parent;
       int lift_Child;
       int right_Child;
       int deep;
       int code[100];//哈夫曼编码
    }Nodetree,*HuffmanTree;
    
    
    typedef struct node{
    
       char symbol;
       int quantity;
       struct node *next;
    }Node;
    
    
    
    
    int getListSize(char *pStr){
    
        int len=0;
        char *start = pStr;
        while(*start){
            len++;
            start++;
        }
        return len;
    }
    
    int getLIstLink(Node *head){
    
       int a = 0;
       Node *p = head->next;
       while(p){
         a++;
         p = p->next;
       }
       return a;
    };
    
    //打印链表
    void print(struct node *head){
    
        struct node *p ;
        printf("开始打印\n");
        p=head->next ;
        if(p == NULL){
            printf("值为空\n");
        }
        while(p!=NULL){
         printf("          %c",p->symbol);
         printf("         %d\n",p->quantity);
         p=p->next;
        }
    };
    
    
    
    int QueryNOde(Node *head,char ch){
    
        Node *p;
        p = head->next;
        while(p!=NULL){
            if(p->symbol == ch){
                p->quantity = p->quantity + 1;//字符存在节点加1
                return 1;//这个字符已经存在
            }
            p = p->next;
        }
       return 0;//这个字符不存在
    };
    
    //生成权值
    Node *createWeight(char *str){
    
        Node *head , *q ,*p;
        int list_size = getListSize(str);
        q=head=(struct node*)malloc(sizeof(struct node));
         for(int i = 0 ; i < list_size ; i++){
                //printf("当前的值:%c\n",*str);
                if(QueryNOde(head,*str)==1){//如果该数据已经存在,则节点加1
                      //  printf("开始遍历\n");
                    // Node *boos = head = (struct node*)malloc(sizeof(struct node));
                       // printf("开始查找\n");
                    // while(boos){
                      //  printf("进入查找\n");
                       // printf("当前遍历值为:%c\n",boos->symbol);
                       // if(boos->symbol == *str){
                          //  printf("开始修改值\n");
                           // boos->quantity = boos->quantity + 1;
                           // printf("值相同\n");
                           // break;
                       // }
                       // boos = boos->next;
                     //}
                    } else{//生成新的权值
                        p = (struct node*)malloc(sizeof(struct node));
                        p->quantity = 1;
                        p->symbol = *str;
                        p->next = NULL;
                        q->next = p;
                        q = p;
                        //printf("值不同\n");
                    }
                     str++;
                }
                return head;
    };
    
    
    void createTree(HuffmanTree &root,int n,Node *head){
    
        if(n<=0){
            return;
        }
        Node *q;
        q = head->next;
        int length = 2*n - 1;
        printf("n is %d\n",n);
        int HFCode[100];//哈夫曼编码数组
        root = new Nodetree[length+1];
        //初始化哈夫曼树
        for(int i = 1;i<=length;i++){
            root[i].order = i;
            root[i].character = 0;
            root[i].parent = 0;
            root[i].lift_Child = 0;
            root[i].right_Child = 0;
        }
        //给哈夫曼树赋值
        for(int i = 1;i<=n;i++){
            root[i].character = q->symbol;
            root[i].weight = q->quantity;
            q = q->next;
        }
    
    
        //开始建立哈夫曼树
    
          for(int i = n+1; i <=length; i++){  //进行 n-1 次循环建立哈夫曼树
            //k1表示森林中具有最小权值的树根结点的下标,k2为次最小的下标
            int k1 = -1 , k2;
            for(int j = 0; j < i; j++){
                if ( root[j].parent == 0  && k1 == -1 && root[j].weight > 0){
                    k1 = j;
                    continue;
                }
                if (root[j].parent == 0 && root[j].weight > 0){
                    k2 = j;
                    break;
                }
            }
            //将指针数组中的指针指向的最小值赋值给索引号为k1的,次小值赋值给索引号为k2的
            for (int j = k2; j < i; j++){
                if(root[j].parent == 0 ){
                    if(root[j].weight < root[k1].weight){
                        k2 = k1;
                        k1 = j;
                    }else if(root[j].weight < root[k2].weight){
                        k2 = j;
                    }
                }
            }
            //开始生成新的哈夫曼树节点
            root[k1].parent = i;
            root[k2].parent = i;
           // printf(" i is:%d\n",i);
           // printf("k1 is :%d\n",k1);
           // printf("k2 is :%d\n",k2);
           // printf(" k1 weight is:%d\n",root[k1].weight);
           // printf(" k2 weight is:%d\n",root[k2].weight);
            root[i].order = i;
            root[i].lift_Child = k1;
            root[i].right_Child = k2;
            root[i].weight = root[k1].weight + root[k2].weight;
          }
              int start;
             // HFCode[n-1]='\0';
             //生成哈夫曼编码
          for(int i = 1;i<=n;i++){
              start = 0;
              int deep = 0;//节点的深度
              int c = i;
              int f = root[i].parent;
              while(f!=0){
                //printf("tart is:%d\n",start);
                if(root[f].lift_Child == c){
                    root[i].code[start] = 0;//如果为左子树就为0
                }else{
                   root[i].code[start] = 1;//右子树就为1
                }
                deep++;
                start++;
                c = f;
                f = root[f].parent;
              }
              root[i].deep = deep;
             // printf("code is:%d\n",root[i].code[start]);
          }
    
    };
    
    
    
    //void CreatHFCode(Nodetree *root,)
    //打印哈夫曼树的表态结构
    void printTree(Nodetree *root,int n){
    
       int length = 2*n -1;
       for(int i = 1 ;i<=length;i++){
        printf("order is %d   character is %c"   "  parent is %d  LiftC is %d  rightC is %d   weight is %d  deep is %d   ",root[i].order, root[i].character, root[i].parent,root[i].lift_Child,root[i].right_Child, root[i].weight,root[i].deep);
           int deep = root[i].deep;
             printf("HFCode is  :");
            for(int j=deep-1;j>=0;j--){
                printf("%d",root[i].code[j]);
            }
            printf("\n");
       }
    
    };
    
     void QueryCOde(Nodetree *root,int n){
    
         int query_list[100];//哈夫曼编码整数数组
         int flag ;//哈夫曼编码匹配判断标志
         int c;
         int code_Size;
         char query_char[100];//用来接收哈夫曼编码
         scanf("%s",&query_char);
         //printf("%s\n",query_char);
         code_Size = getListSize(query_char);//输入的哈夫曼编码长度
    
         //将输入的哈夫曼编码有字符数组转换为整数数组
         for(int i = 0;i<code_Size;i++){
            c = query_char[i]-'0';
            query_list[i] = c;
           // printf("n is:%d\n",c);
         }
    
       // for(int i=0;i<code_Size;i++){
           //  printf("%d ",query_list[i]);
        // }
    
         for(int i=1;i<=n;i++){
            int deep = root[i].deep;
            int j ;
            //若哈夫曼的深度和输入的哈夫曼编码长度相同则开始查找
            if(deep==code_Size){
                //printf("deep is:%d code_size is:%d\n",deep,code_Size);
                 j=0;
                 int code = code_Size-1;
                deep--;
                //开始匹配值
                flag = i;
                while(deep>=0){
               // printf("开始匹配deep %d\n",deep);
                if(root[i].code[j]!=query_list[code]){
                   //printf("值不相同\n");
                   flag = -1;
                   break;
                }
                j++;
                code--;
                //printf("%d deep is %d\n",i,deep);
                deep--;
            }
            }
            //判断是否找到对应的权重的值
           // printf("deep is:%d\n",deep);
            if(deep<0){
                flag = i;
                i = n+1;
            }
    
         }
        // printf("flag is:%d\n",flag);
         if(flag>0){
            printf("翻译结果值:%c\n",root[flag].character);
         }
         else{
            printf("没有与编码匹配的数据值\n");
         }
    
     };
    
    
    
    int main()
    {
        int Link_size ;
        struct node *head;
        Nodetree *root;
        char input_list[Lsize];
    
    
    
         printf("........................功能列表...................\n");
         printf("..............         输入报文  ................\n");
         printf("..............         打印频度  ................\n");
         printf("..............         建立哈夫曼树  ................\n");
         printf("..............         翻译报文  ................\n");
         //printf("..............         5.退出  ................\n");
    
    
    
    
    
        printf("..............输入想要赋值的字符串\n");
        scanf("%s",&input_list);
        gets(input_list);
        printf("%s\n",input_list);
        head = createWeight(input_list);
        printf("..............出现频度为\n");
        print(head);
        Link_size = getLIstLink(head);
        printf("..............链表长度为:%d\n",Link_size);
        createTree(root,Link_size,head);
        printTree(root,Link_size);
    
        int flag = 1;
        while(flag==1){
            printf("..............输入你想要查找的代码\n");
            QueryCOde(root,Link_size);
            printf("..............想继续查找输入1,不想输入0\n");
            scanf("%d",&flag);
        }
    
    }
    

    代码里面有备注,不清楚的可以留言,有错误的欢迎指出。

    展开全文
  • //哈夫曼编码里的权值,赋值给哈夫曼树里面的权值 HT[i].lchild = HT[i].rchild = HT[i].parent = 0;//双亲,左右子树全部赋值为0 } /*整个树的节点数是2*length-1,刨去第0个,就是2*length 上面一个循环已经...
  • 构造哈夫曼树生成哈夫曼编码 参考 程序员小灰-漫画:什么是 “哈夫曼树” ? 程序员小灰-漫画:“哈夫曼编码” 是什么鬼? 编写一个程序exp7-5.cpp,构造一棵哈夫曼树, 输出对应哈夫曼编码和平均查找长度, 并对...
  • #include <iostream> using namespace std; #define MAX 50 ...typedef struct //哈夫曼树结点结构 { char data; int weight; int parent; int lchild; int rchild; }HuffNode; typedef struct ...
  • 哈夫曼编码:从队列中取出权重最小两个节点,进行构造  将新生成的节点作为父节点   使用结构体:  Node(node1,node2,weight) //权重边信息保存  HuffmanTree(weight,family,lchild,rchil
  • 一、对图片压缩与解压缩,涉及以下内容:1.文件读写2.创建Huffman3.生成Huffman编码4.压缩图片文件5 ....任务三:解压压缩文件,恢复原文件下面开始完整步骤:三、统计权值、生成Huffman1.Huffma...
  • 生成哈夫曼树

    2020-01-05 20:43:23
    哈夫曼树的模板题,每次去两个最小的数,相加,再把它们的和加入数组。 #include<iostream> #include<string> #include<cstring> #include<cmath> #include<cstdio> #include<qu...
  • 哈夫曼树与哈夫曼编码

    千次阅读 2016-12-16 20:37:17
    1、使学生熟练掌握哈夫曼树的生成算法。 2、熟练掌握哈夫曼编码的方法。 二、实验内容 本次实验提供4个题目,难度相当,学生可以根据自己的情况选做,其中题目一是必做题,其它选作! 题目:哈夫曼树和哈夫曼...
  • 最小生成树与哈夫曼树

    千次阅读 2019-08-25 10:41:44
    转载自添加链接描述 最小生成树 定义:在连通网的所有生成树中,所有边的代价和最小的生成树,称为最小生成树。 算法: Kruskal算法(加边法):初始最小生成树边数为0,每迭代一次就选择一条...哈夫曼树 定义:...
  • 哈夫曼树的左分支为0,右分支为1,从根节点到每个节点比如经历两次右分支则,编码就是11.二叉排序树选取第一个为根节点,然后把下一个要插入的节点与根节点进行比较,大的放在右子树,小的放在左子树位置。最小生成...
  • 二叉树带权路径长度:设二叉树有n个带有权值的叶子结点,每个叶子到根的路径长度乘以其...哈夫曼树的构造过程假定有n个具有权值的结点,则哈夫曼树的构造算法如下: ① 根据n个权值,构造n棵二叉树,其中每棵二叉树...
  • 需要用这些叶结点生成哈夫曼树,根据哈夫曼树的概念,这些结点有权值,即weight,题目需要输出哈夫曼树的带权路径长度(WPL)。 输入格式: 第一行输入一个数n,第二行输入n个叶结点(叶结点权值不超过1000,2<=n&...
  • 需要用这些叶结点生成哈夫曼树,根据哈夫曼树的概念,这些结点有权值,即weight,题目需要输出所有结点的值与权值的乘积之和。 输入描述: 输入有多组数据。 每组第一行输入一个数n,接着输入n个叶节点(叶节点...
  • 哈夫曼树

    千次阅读 多人点赞 2017-08-05 23:34:19
    生成哈夫曼树的第一步就是在结点集合中找到两个权值最小的结点,然后生成一棵二叉树 树中任意节点的权值一定大于自己的左右孩子,但不能保证一定不小于其他下一任结点的权值。设哈夫曼树中的叶子结点总数为m,若用...
  • 编程得出哈夫曼的码表;输入一段英文字符,利用码表对其编码、译码。 开发环境: VS2015(C++) 2.数据处理 数据归一化,使各英文字符概率之和为1。由于文献中各字符概率之和大于1,对数据进行归一化。将当前各...
  • 哈夫曼树的建立

    2018-06-26 08:54:00
    掌握生成哈夫曼树的算法。 二、实验原理 哈夫曼树,即最优树,是带权路径长度最短的树。有着广泛的应用。在解决某些判定问题上,及字符编码上,有着重要的价值。 构造一棵哈夫曼树,哈夫曼最早给出了算法,称为...
  • 没啥好说 本来只想免费分享出去很早以前课程设计 资源分最低最低只能选2,我就把二叉树 哈夫曼树 和 最小树放到一起了 作为参考啊
  • 2、哈夫曼树的构造 ——>——>——>——> 算法:先选取两个权值最小的——用最小堆 二、哈夫曼编码 a:00 u:01 x:10 z:11 可以发现,如果他们都在叶结点上,那么任意一个字母...
  • #include #include #include #include #include using namespace std;...//根据哈夫曼树的概念,这些结点有权值,即weight, //题目需要输出所有节点的值与权值的乘积之和 priority_queue , greater > Q; //建立一
  • 哈夫曼树的特点性质:(节点为的度数为0 表示 n0,以此类推) ①哈夫曼树中只存在度为2和度为0的节点,及n1=0。 ②哈夫曼树中,度为0和度为2的节点关系:n2=n0-1 由以上两个性质,本题就很好解出答案: n0+n2=115 =&...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 609
精华内容 243
关键字:

哈夫曼树的生成