精华内容
下载资源
问答
  • 刚刚学习了哈夫曼树算法而且画了一张方便理解。。迫不及待的贴出来嘚瑟 hh~ 哈夫曼算法基本思想: (1) 以权值分别为W1,W2...Wn的n各结点,构成n棵二叉树T1,T2,...Tn并组成森林F={T1,T2,...Tn},其中每...

    我胡汉三又肥来了。。
    刚刚学习了哈夫曼树算法而且画了一张图方便理解。。迫不及待的贴出来嘚瑟 hh~
    哈夫曼算法基本思想:

    (1) 以权值分别为W1,W2...Wn的n各结点,构成n棵二叉树T1,T2,...Tn并组成森林F={T1,T2,...Tn},其中每棵二叉树 Ti仅有一个权值为 Wi的根结点;

    (2) 在F中选取两棵根结点权值最小的树作为左右子树构造一棵新二叉树,并且置新二叉树根结点权值为左右子树上根结点的权值之和(根结点的权值=左右孩子权值之和,叶结点的权值= Wi);

    (3) 从F中删除这两棵二叉树,同时将新二叉树加入到F中;

    (4) 重复(2)、(3)直到F中只含一棵二叉树为止,这棵二叉树就是Huffman树。
      在这里插入图片描述
     哈夫曼算法的存储结构

    考虑到对于有n个叶子结点的哈夫曼树有2n-1个结点,并且进行n-1次合并操作,为了便于选取根节点权值最小的二叉树以及合并操作,设置一个数组haftree[2n-1],保存哈夫曼树中的各个结点的信息,数组元素的结点结构如下图所示:
    在这里插入图片描述
    weight保存结点权值;

    lchild保存该节点的左孩子在数组中的下标;

    rchild保存该节点的右孩子在数组中的下标;

    parent保存该节点的双亲孩子在数组中的下标。

    struct element
    {
    int weight; // 权值域
    int lchild, rchild, parent; // 该结点的左、右、双亲结点在数组中的下标
    };
    哈夫曼算法C++实现
    https://www.cnblogs.com/smile233/p/8184492.html

    展开全文
  • #include"stdio.h"#defineN010#defineinfi1000000structnode{intw,lch,rch,parent;}ht[2*N0];structnode1{charch;unsignedcharcode[N0+1];intstart;//codelength}hc[N0+1];intn,m,roo...#include "stdio.h"#define N...

    #include"stdio.h"#defineN010#defineinfi1000000structnode{intw,lch,rch,parent;}ht[2*N0];structnode1{charch;unsignedcharcode[N0+1];intstart;//codelength}hc[N0+1];intn,m,roo...

    #include "stdio.h"

    #define N0 10

    #define infi 1000000

    struct node

    { int w, lch, rch, parent;

    }ht[2*N0];

    struct node1

    { char ch;

    unsigned char code[N0+1];

    int start;// code length

    }hc[N0+1];

    int n, m, root;

    void readData()

    { int i, a[256]={ 0 };

    char ch;

    freopen("huffman.in", "r", stdin);

    while( (ch=getchar()) != EOF )

    a[ch]++;

    n=0;

    for(i=0; i<256; i++)

    if( a[i] )

    { ht[ ++n ].w=a[i];

    hc[ n ].ch=i;

    }

    m=root=2*n-1;

    }

    void select3(int t, int *s1, int *s2 )

    { int i, w1=infi, w2=infi;

    for( i=1; i<=t; i++)

    if( ht[i].parent==0 )

    if( ht[i].w

    { w2=w1;

    *s2=*s1;

    w1=ht[i].w;

    *s1=i;

    }

    else if( ht[i].w

    { w2=ht[i].w;

    *s2=i;

    }

    }

    void create_ht_hc()

    { int i, s1, s2, child, parent;

    for( i=n+1; i<=m; i++ )

    { select3( i-1, &s1, &s2);

    ht[i].w=ht[s1].w+ht[s2].w;

    ht[i].lch=s1;

    ht[i].rch=s2;

    ht[s1].parent=ht[s2].parent=i;

    }

    for( i=1; i<=n; i++)

    { child=i;

    parent=ht[child].parent;

    while( child != root )

    { if( child==ht[parent].lch )

    hc[i].code[hc[i].start++]='0';

    else hc[i].code[hc[i].start++]='1';

    child=parent;

    parent=ht[child].parent;

    }

    }

    }

    void showCode()

    { int i,j;

    for( i=1; i<=n; i++)

    { printf("%c:", hc[i].ch);

    for(j=hc[i].start-1; j>=0; j--)

    printf("%c", hc[i].code[j]);

    printf("\n");

    }

    }

    void showTree(int root, int tab)

    { if(root)

    { int i;

    for( i=1; i<=tab; i++)

    printf(" ");

    printf("%d", ht[root].w);

    if( ht[root].lch==0 )

    printf("%c\n", hc[root].ch);

    else printf("\n");

    showTree( ht[root].lch, tab+3 );

    showTree( ht[root].rch, tab+3 );

    }

    }

    void str2code()

    { int i,j,ch;

    freopen("huffman.in", "r", stdin);

    freopen("huffman.code", "w", stdout);

    while( (ch=getchar() )!=EOF )

    { for(i=1; i<=n; i++)

    if( hc[i].ch==ch )

    for(j=hc[i].start-1; j>=0; j--)

    printf("%c", hc[i].code[j]);

    }

    }

    void code2str()

    { int i=root,ch;

    freopen("huffman.code", "r", stdin);

    freopen("huffman.txt", "w", stdout);

    while( (ch=getchar() )!=EOF )

    { if( ch=='0' ) i=ht[i].lch;

    else i=ht[i].rch;

    if(ht[i].lch==0)

    { printf("%c", hc[i].ch);

    i=root;

    }

    }

    }

    int main()

    {

    readData();

    create_ht_hc();

    showTree(root, 0);

    showCode();

    str2code();

    code2str();

    return 0;

    }

    符合要求的多加分(qq:873485472)

    c语言描述的Huffman

    展开

    展开全文
  • ![在这里插入图片描述](https://img-blog.csdnimg.cn/20200405212647438.jpg?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzI5MTMxOTA3,size_16,...t...

    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述

    
    #include <iostream>
    using namespace std;
    typedef struct TreeNode *Huffman;
    typedef struct HeapStruct *MinHeap;
    #define Maxsize 1000
    #define Mindata -1000
    int A[] = { 1,2,3,4,5};
    int A_length = 5;
    struct TreeNode
    {
    	int weight;
    	Huffman left;
    	Huffman right;
    };
    struct HeapStruct
    {
    	Huffman *data;
    	int size;
    	int capacity;
    
    };
    Huffman Create()
    {
    	Huffman h=new TreeNode;
    	h->weight = 0;
    	h->left = NULL;
    	h->right = NULL;
    	return h;
    }
    MinHeap create()
    {
    	MinHeap H= new HeapStruct;
    	H->size = 0;
    	H->capacity = Maxsize;
    	H->data = (Huffman*)malloc(sizeof(struct TreeNode)*(Maxsize + 1));
       Huffman  h = Create();
       h->weight = Mindata;
       H->data[0] = h;
       return H;
    }
    void sort(MinHeap H, int i)
    {
    	int parent, child;
    	int temp = H->data[i]->weight;
    	for (parent = i; parent * 2 <= H->size; parent = child)
    	{
    		child = parent * 2;
    		if (child != H->size&&H->data[child]->weight > H->data[child + 1]->weight)
    			child++;
    		if (H->data[child]->weight >= temp)
    			break;
    		else
    			H->data[parent] = H->data[child];
    	}
    	H->data[parent]->weight = temp;
    }
    
    
    void Adjust(MinHeap H)
    {
    	for (int i = H->size / 2; i > 0; i--)
    	{
    		sort(H, i);
    	}
    }
    
    void Build(MinHeap H)
    {
    	Huffman h;
    	for (int i = 0; i < A_length; i++)
    	{
    		h = Create();
    		h->weight = A[i];
    		H->data[++H->size] = h;
    	}
    	Adjust(H);
    }
    
    void Insert(MinHeap H, Huffman h)
    {
    	int weight = h->weight;
    	int i = ++H->size;
    	for (; H->data[i / 2]->weight > weight; i /= 2)
    		H->data[i] = H->data[i / 2];
    	H->data[i] = h;
    }
    
    void Pre(Huffman h)
    {
    	if (h)
    		cout << h->weight<<" ";
    	if (h->left)
    		Pre(h->left);
    	if (h->right)
    		Pre(h->right);
    }
    Huffman Del(MinHeap H)
    {
    	int parent, child;
    	Huffman h = H->data[1];
    	Huffman temp = H->data[H->size--];
    	for (parent = 1; 2 * parent <= H->size; parent = child)
    	{
    		child = 2 * parent;
    		if (child != H->size&&H->data[child]->weight> H->data[child + 1]->weight)
    			child++;
    		if (H->data[child]->weight >= temp->weight)
    			break;
    		else
    			H->data[parent] = H->data[child];
    	}
    	H->data[parent] = temp;
    	return h;
    
    }
    Huffman huffmantree(MinHeap H)
    {
    	Huffman T;
    	Build(H);
    	int times = H->size;
    	for (int i = 1; i < times; i++)
    	{	
    		T = new TreeNode;
    		T->left = Del(H);
    		T->right = Del(H);
    		T->weight = T->left->weight + T->right->weight;
    		Insert(H, T);
    	}
    	T = Del(H);
    	return T;
    }
    int main()
    {
    	MinHeap H;
    	Huffman h;
    	H = create();
    	h = huffmantree(H);
    	Pre(h);
    	
    
    	system("pause");
    	return 0;
    	}
    

    哈夫曼树 编码 解码

    void Huffmancode(Huffman T, int h)
    {	
    	static int c[10];
    	if (T)
    	{
    		if ((T->left == NULL) && (T->right == NULL))
    		{
    			cout << "字符:" << T->ch << "对应的权值为" << T->weight <<"哈夫曼编码为:"<< endl;
    			for (int i = 0; i < h; i++)
    			{
    				cout << c[i] ;
    
    			}
    		}
    		else
    		{
    			c[h] = 0;
    			Huffmancode(T->left,h+1);
    
    			c[h] = 1;
    			Huffmancode(T->right, h + 1);
    		}
    	}
    }
    
    void HuffmanSolve(char ch[], Huffman T)//解码
    {
    	int count;
    	int num[100];
    	Huffman temp;
    	for (int i = 0; i < strlen(ch); i++)
    	{
    		if (ch[i] = '0')
    		{
    			num[i] = 0;
    		}
    		else
    		{
    			num[i] = 1;
    		}
    
    	}
    	if (T)
    	{
    		count = 0;
    		while (count< strlen(ch))
    		{
    			temp = T;
    			while ((temp->right!=NULL)&&(temp->left!=NULL))
    			{
    				if (num[count] == 0)
    				{
    					temp = temp->left;
    				}
    				else
    				{
    					temp = temp->right;
    				}
    				count++;
    			}
    			cout << temp->ch << endl;
    		}
    		
    	}
    
    }
    
    
    
    展开全文
  • 这里写自定义目录标题JavaFX实现哈夫曼树和哈夫曼编码的GUI界面的显示原理及作用GUI界面功能如何改变文本的样式插入链接与图片如何插入一段漂亮的代码片生成一个适合你的列表创建一个表格设定内容居中、居左、居右...

    JavaFX实现哈夫曼树和哈夫曼编码的GUI界面的显示

    原理及作用

    哈夫曼树又称最优二叉树,是带权路径长度(WPL)最短的树,可以生成哈夫曼编码,出现频率高的字符用较短的编码,这样可以用于数据传输,数据压缩,来提高效率。

    功能

    • 输入字符串后再点击Show Huffman Tree在界面生成哈夫曼树,及相关编码信息。
    • 在下方输入二进制编码产生相应的字符串信息。
    • 产生的信息通过弹窗展示
    • 对输入的内容进行合法判断

    思路

    开始对字符串中的字符进行计算权重,再创建对应的结点,加入ArrayList数组中。这是哈夫曼树中的一个小二叉树,哈夫曼树由多个它组成。
    在这里插入图片描述
    生成哈夫曼树时的过程:
    在这里插入图片描述

    GUI界面

    运行时初始界面运行时初始界面
    代码:
    在这里插入图片描述
    showHuffmanTree方法:

    • 第一个for循环用来统计输入字符串中的Ascii值。在第二个循环中会用到。
    • 第一个if语句用来判断字符串长长度,要求大于一
    • 第二个if语句用来判断输入的字符串是否全为一个字符,否则也无意义。
    • 最后的else方法来执行createTree方法,传入需要生成树的结点,以及输入的字符串信息。并通过getCode方法获取相应的哈夫曼编码信息显示到弹窗。

    decode方法

    • 第一个if判断是否生成了哈夫曼树,否则你无法来解码。
    • 第二个判断是否输入bits字符串
    • 第三个判断输入的字符串是否为01组成。
    • 最后调用getChar方法

    getCode方法

    • 由于执行了createTree方法,生成了哈夫曼树,相应的编码也存入了codeMap集合中,可以直接通过键来获取值,存储到字符串并在循环结束后返回。

    getChar方法

    • 原理和getCode方法一样,只不过现在是通过值来获取键。但是有一点要考虑到,你输入的bits码可能不能全转换为字符,所以要在里面进行判断。
    • 获取键的方法为遍历codeMap集合,将值与bits字符串的前n位比较,n为当前集合值的长度(此时又会发生另外一种情况,若bits字符串的长度已经小于了值的长度就会产生越界异常)所以这里我们定义一个length来获取n与bits长度的最小值。若匹配就分割bits字符串,去掉已匹配的字符串。直到匹配完成。
    • 如果bits剩下的字符串不能匹配到集合中的值,会在字符串的长度次循环中跳出循环,并弹出提示框。

    createTree方法

    • 创建一个树对象,调用该对象的printTree方法,传入相关参数,x是X轴的偏移量,y是Y轴的偏移量。deep是树的深度。由于根节点在结点中央,所以直接传入的500。当然也可以用其他的方法。
    • 用定义的sp的setContent方法添加结点到父结点。

    TreeNode类

    在这里插入图片描述
    c用来储存字符信息
    code用来储存哈夫曼编码
    weight来存放权值
    lTreeNode和rTreeNode分别存放左右孩子

    Tree类

    代码:
    在这里插入图片描述其中这个片段我想到之前写的有点不好修改了一下
    这里清空al的主要是释放内存。

    //当集合中只有两个结点时,连接到root结点并break
    if(al.size() == 2) {
    	root.lTreeNode = al.get(0);
    	root.rTreeNode = al.get(1);
    	al.clear();
    	break;
    }

    测试结果

    在这里插入图片描述
    上方的图片为生成的哈夫曼树
    下左为点击Show Huffman Tree后弹出的提示框
    下右为点击Decode Text后弹出的提示框
    如果输入的bits字符串不能全部按照哈夫曼编码解码会弹出一个提示框说明还剩哪些字符串没有解码
    **例如:**上图中产生的编码对应关系为
    r ——>000
    d ——>001
    o ——>01
    h ——>100
    e ——>1010
    w ——>1011
    l ——>11
    假如我输入0000010110
    解码为rdo,剩下的10无法通过哈夫曼编码转化为字符。
    在这里插入图片描述

    展开全文
  • 一、课程设计题目:哈夫曼树应用 二、课程设计要求: 1) 从终端读入字符集大小n,以及n个字符和n个权值,建立哈夫曼树并将它存于文件hfmTree中.将已在内存中的哈夫曼树以直观的方式(比如树)显示在终端上; 2) 利用...
  • 利用C语言数据结构知识实现哈弗曼的编/译码器 1.题目重述 2.题目功能描述 3. 概要设计图 4. 程序源代码及注释 5. 流程图 6. 截图与数据分析 7.所采用的存储结构的优缺点及采用理由 8.实验心得体会
  • 构造哈夫曼树,这一篇就够了

    千次阅读 2020-05-15 20:27:32
    什么是哈夫曼编码? 哈夫曼编码(Huffman Coding),又称霍夫曼编码,是一种编码方式,哈夫曼编码是可变...哈夫曼编码算法流程图 哈夫曼编码的算法是查找最优路径的一种算法,首先在所有未分配parent域的节点中找出最小的
  • 文件压缩总结-哈夫曼树

    多人点赞 2017-08-18 16:20:01
    详细源代码请移步下载:https://github.com/HsTime/file-campress 项目:文件压缩流程图 建立小堆代码:#pragma once#include using namespace std; #include #include"huffman.h"template struct Less { bo
  • 任务:按给定的数据建立赫夫曼 要求:可以建立函数输入二叉树,并输出其赫夫曼。在上交资料中请写明:存储结构、基本算法(可以使用程序流程图)、输入输出、源程序、测试数据和结果。提供良好的菜单操作界面
  • 一、设计题目对一幅BMP格式的灰度图像(个人证件照片)进行二元霍夫曼...②:二元霍夫曼编码:程序流程图:详细设计:统计像素点频率,首先通过python自带的PIL库的图像像素点读取函数read()获取灰度图像的所有像素点...
  • 概念哈夫曼编码(Huffman Coding),又称霍夫曼编码,是一种编码方式,哈夫曼编码是可变字长编码(VLC)的一种...哈夫曼原理哈夫曼算法流程图哈夫曼树给定n个权值作为n个叶子结点,构造一棵二叉树,若带权路径长度达到最...
  • 中南大学 数据结构课程设计报告 题 目 哈夫曼编译器 学生姓名 指导教师 学 院 信息科学与工程学院 专业班级 计科1302 目录 实验要求3 问题描述3 问题解决方法3 程序模块功能及流程图4 调试与测试8 测试结果9 心得...
  • 概念 哈夫曼编码(Huffman Coding),又称霍夫曼编码,是一种编码方式,哈夫曼编码是可变字长编码(VLC)的一种。...哈夫曼算法流程图 哈夫曼树 给定n个权值作为n个叶子结点,构造一棵二叉树,若带...
  • . . . 中南大学 数据结构课程设计报告 题 目 哈夫曼编译器 学生姓名 指导教师 学 院 信息...(1)从键盘读入字符集大小n , 以及n个字符和权值建立哈夫曼树 (2)利用已建好的哈夫曼树对文件正文进行编码将结果存入相关文件
  • 数据结构——哈夫曼编/译码器

    千次阅读 2019-02-01 12:36:38
    在上交资料中请写明:存储结构、基本算法(可以使用程序流程图)、输入输出、源程序、测试数据和结果、算法的时间复杂度、另外可以提出算法的改进方法; 利用哈夫曼编码进行通信可以大大提高信道利用率,缩短信息...
  • 在上交资料中请写明:存储结构、基本算法(可以使用程序流程图)、输入输出、源程序、测试数据和结果、算法的时间复杂度、另外可以提出算法的改进方法; 利用哈夫曼编码进行通信可以大大提高信道利用率,缩短信息...
  • 赫夫曼编码也翻译为 哈夫曼编码(Huffman Coding),又称霍夫曼编码,是一种编码方式, 属于一种程序算法赫夫曼编码是赫哈夫曼树在电讯通信中的经典的应用之一。2.赫夫曼编码广泛地用于数据文件压缩。其压缩率通常在20%...
  • 博客作业04--

    2019-09-27 15:03:00
    需要记住很多基础代码才能顺利的做题,如建二叉树哈夫曼树之类的代码,凭自己写很难也很浪费时间。 2.PTA实验作业 2.1 题目1:题目名称6-4 jmu-ds-表达式树 2.2 设计思路(伪代码或流程图) void InitExpTree...
  • 树,我们在计算机中很常见了,有二叉树,哈夫曼树等等,总结一下共同点的时候就是,对一个当前节点而言,下一个个节点有多个节点可以选择的结构。简单的说就是有分叉的结构就是树(可能这样说也不严谨)。而决策树...
  • 3、领会哈夫曼树的构造过程以及哈夫曼编码的生成过程; 4、掌握二叉树遍历算法的应用,熟练使用先序、中序、后序3种递归遍历算法进行二叉树问题的求解; 二、使用仪器、器材 微机一台 操作系统:WinXP 编程软件:C/...
  • 霍夫曼编码

    2019-08-10 20:23:17
    关于字符串的一些算法的github ...使用IDEA写的,jdk8.0以及以上就...1.建立哈夫曼树 (1)统计叶子节点(每个字符)的权重 (2)初始化优先队列 (3)依次找到队列中最小和次小的节点,创建新节点作为这两个节点父节点,权重为...
  • 2.4.3 三种基本结构和改进的流程图 28 2.4.4 用N-S 流程图表示算法 29 2.4.5 用伪代码表示算法 30 2.4.6 用计算机语言表示算法 31 2.5 结构化程序设计方法 31 3 数据类型、运算符与表达式 3.1 C语言的数据类型 32 ...

空空如也

空空如也

1 2
收藏数 26
精华内容 10
关键字:

哈夫曼树流程图