精华内容
下载资源
问答
  • 哈夫曼算法证明 哈夫曼算法是一种贪心算法,我们考虑证明其最优子结构和贪心选择性质: 最优子结构:假设一个树是哈夫曼树,则以其任意节点为根节点最大子树也是哈夫曼树。 证明:子树根节点值是其所有叶子...

    哈夫曼算法证明

    哈夫曼算法是一种贪心算法,我们考虑证明其最优子结构和贪心选择性质:

    • 最优子结构:假设一个树是哈夫曼树,则以其任意节点为根节点的最大子树也是哈夫曼树。

      证明:子树的根节点的值是其所有叶子节点出现权值之和,因此无论子树是什么形式,对子树上方的节点计算WPL2都没有影响。

      根据哈夫曼树的定义:WPL最小的二叉树。如果子树不是哈夫曼树,其WPL1就不会是最小,那么整个树的WPL=WPL1+WPL2就不会是最小,这与哈夫曼树的定义相悖,因此子树是哈夫曼树。

    • 贪心选择性质(哈夫曼算法):每次去掉权值最低的两个节点作为叶子节点形成一颗二叉树,并将其父亲节点放入待选节点中。

      证明:对于哈夫曼树我们总可以通过取出两个节点作为叶子节点并将其父亲节点重新作为叶子节点的方式构造,需要证明的是是否每次选择权值最低的节点可以构造成功。

      当含有2个及以下的叶子节点的时候,显然正确。

      假设当含有小于k个叶子节点的时候哈夫曼算法可以形成哈夫曼树

      对于含有k个叶子节点形成的树,设其中权重最小的叶子节点为a,其中深度最深的叶子节点为b,h表示节点的深度,w表示节点的权值。则:
      WPL1=+waha+wbhb WPL_1=\sum+w_a*h_a+w_b*h_b
      交换这两个节点:
      WPL2=+wbha+wahb WPL_2=\sum+w_b*h_a+w_a*h_b

    WPL1WPL2=(wawb)ha+(wbwa)hb=(hbha)(wbwa) WPL_1-WPL_2=(w_a-w_b)*h_a+(w_b-w_a)*h_b=(h_b-h_a)*(w_b-w_a)

    hbhah_b-h_awbwaw_b-w_a都为正(由a,b节点的性质),所以我们得到结论:对于任何一棵树,将权值小的节点尽可能移动到较深层的节点会使整个树的WPL比较小。

    对于k个节点,我们首先取出两个节点,将其合并成一个节点以后我们有k-1个节点,可以使用哈夫曼算法构造。

    如果这两个节点不是所有节点中权值最小的两个,则我们总可以通过交换使得构造的树的WPL减小,因此不是哈夫曼树。只有两个节点是所有节点中权值最小的两个时我们无法再降低树的WPL。因为我们总可以构造成功,所以选择权值最小的节点构造的树就是哈夫曼树。证毕。

    哈夫曼编码译码程序

    #pragma once
    #include<iostream>
    #include<fstream>
    #include<vector>
    #include<queue>
    #include<cstdio>
    #include<string>
    
    using namespace std;
    
    static const int MAXN = 1005;
    
    struct times
    {
    	double weight;//字符的权值
    	int num;//字符的序号,同时也是他的ASCALL值
    	times(int _num=0,double _weight=0) :num(_num),weight(_weight){}
    	friend bool operator < (const times & a,const times & b)
    	{
    		return a.weight > b.weight;
    	}
    }p,q;
    
    struct Chara:times
    {
    	int father;//父亲的序号
    	int lson, rson;//左右儿子的序号
    	string code;
    	Chara(int _num = 0, double _weight = 0, int _lson = 0, int _rson = 0, int _father = 0) :times(_num,_weight), lson(_lson), rson(_rson), father(_father)
    	{
    		code = "";//没有编码
    	}
    	void operator = (const Chara& x)
    	{
    		weight = x.weight; num = x.num; father = x.father; lson = x.lson; rson = x.rson;
    	}
    };
    
    struct txt
    {
    	string t;
    	double weight;
    	txt(string _t,double _weight):t(_t),weight(_weight){}
    };
    
    class HuffmanCode
    {
    public:
    	int n=0;//字符的个数
    	int cur;//当前所在位置
    	int root;//哈夫曼树根节点
    	Chara A[MAXN];//顺序表保存哈夫曼树
    	priority_queue<times> T;//用来构建哈夫曼树
    	void CreatHuffmanCode(int x, string now)
    	{
    		if (A[x].lson != 0)
    		{
    			CreatHuffmanCode(A[x].lson, now + "0");
    		}
    		if (A[x].rson != 0)
    		{
    			CreatHuffmanCode(A[x].rson, now + "1");
    		}
    		if (A[x].lson == 0 && A[x].rson == 0)//说明是字符
    		{
    			A[x].code = now;
    		}
    	}
    
    	void _HuffmanCode(int _n,vector<txt>& input)
    	{
    		string tmp;
    		n = _n;
    		for (int i = 0; i < n; i++)
    		{
    			tmp = input[i].t;
    			A[tmp[0]].num = tmp[0];
    			A[tmp[0]].weight = input[i].weight;
    			T.push(times(tmp[0], A[tmp[0]].weight));
    		}
    		cur = 500;
    
    		//构建哈夫曼树
    		while (T.size() > 1)
    		{
    			p = T.top(); T.pop(); q = T.top(); T.pop();
    			A[cur] = Chara(cur, p.weight + q.weight, p.num, q.num, 0); 
    			A[p.num].father = A[q.num].father = cur;
    			T.push(times(A[cur])); cur++;
    		}
    		T.pop(); root = cur-1;
    
    
    		CreatHuffmanCode(root, "");
    	}
    };
    
    class Huffman
    {
    	int n;
    	vector<txt> input;
    	HuffmanCode x;
    public:
    	void _Huffman()
    	{
    		string t; double weight; n = 0;
    		FILE* stream;
    		freopen_s(&stream,"hfmTree.txt","r",stdin);
    		while (1)
    		{
    			cin >> t;
    			if (t == "Esc") break;
    			n++;
    			cin >> weight;
    			input.push_back(txt(t, weight));
    		}
    		freopen_s(&stream, "CON", "r", stdin);
    		input.push_back(txt(" ", 10000.0));//给空格很大的权值
    		n++;
    		x._HuffmanCode(n, input);
    	}
    	Huffman()
    	{
    		string t; double weight; n = 0;
    		cout << "请输入字符集 \n[Delete撤销输入,Esc退出输入]\n[直接输入Default按照默认文件组成哈夫曼编码]\n[空格已经编码]"<< endl;
    
    		while(1)
    		{
    			cout << "请输入字符:";
    			cin >> t;
    			if (n == 0 && t == "Default")//按照默认文件构造哈夫曼树
    			{
    				_Huffman();
    				return;
    			}
    			else if (t == "Delete")
    			{
    				input.erase(input.end()-1);//删除最后一个输入的字符
    				n--;
    				continue;
    			}
    			else if (t == "Esc")
    			{
    				break;
    			}
    			n++;
    			cout << "请输入" << t[0] << "的权重:";
    			cin >> weight;
    			input.push_back(txt(t, weight));
    		}
    		FILE* stream;
    		freopen_s(&stream, "hfmTree.txt", "w", stdout);
    		for (int i = 0; i < n; i++)
    		{
    			cout << input[i].t << " " << input[i].weight << endl;
    		}
    		cout << "Esc" << endl;
    		freopen_s(&stream, "CON", "w", stdout);
    		input.push_back(txt(" ", 10000.0));//给空格很大的权值
    		n++;
    		x._HuffmanCode(n, input);
    	}
    	void HuffmanDisplay()
    	{
    
    		cout << "哈夫曼编码:" << endl;
    		for (int i = 0; i < n; i++)
    		{
    			cout << input[i].t[0] << ":" << x.A[input[i].t[0]].code << endl;
    		}
    	}
    	void GenerateCode()//压缩文件
    	{
    		cout << "请输入需要压缩文件的路径[输入Default将打开默认文件ToBeTran.txt]" << endl;
    		string in;
    		
    		cin >> in;
    		if (in == "Default")
    		{
    			in = "ToBeTran.txt";
    		}
    		cout << "请输入保存压缩后文件的路径[输入Default将打开默认文件CodeFile.txt]" << endl;
    		string out;
    
    		cin >> out;
    		if (out == "Default")
    		{
    			out = "CodeFile.txt";
    		}
    
    		ifstream infile(in, ios::in);
    		ofstream outfile(out, ios::out);
    
    		char c;
    		bool flag = true;
    		while ((c = infile.get()) != EOF)
    		{
    			if (x.A[c].code == "")
    			{
    				flag = false;
    				break;
    			}
    			outfile << x.A[c].code;
    		}
    
    		infile.close();
    		outfile.close();
    
    		if (!flag)
    		{
    			cout << "压缩失败,文件中出现了字符集中未包含的字符" << endl;
    			return;
    		}
    
    		//展示压缩的结果:
    		infile.open(out, ios::in);
    
    		string tmp;
    		infile >> tmp;
    
    		infile.close();
    
    		cout << "编码后的文件为:" << endl;
    
    		for (int i = 0; i < tmp.size(); i++)
    		{
    			if (i && i % 50 == 0) cout << endl;
    			cout << tmp[i];
    		}
    		cout << endl;
    
    		
    
    		//将结果放入文件中
    		outfile.open("CodePrint.txt", ios::out);
    		
    		for (int i = 0; i < tmp.size(); i++)
    		{
    			if (i % 50 == 0) outfile << endl;
    			outfile << tmp[i];
    		}
    
    		outfile.close();
    	}
    	void Decode()
    	{
    		cout << "请输入需要解码文件的路径[输入Default将打开默认文件CodeFile.txt]" << endl;
    		string in;
    		cin >> in;
    		if (in == "Default")
    		{
    			in = "CodeFile.txt";
    		}
    		cout << "请输入保存压缩后文件的路径[输入Default将打开默认文件TextFile.txt]" << endl;
    		string out;
    
    		cin >> out;
    		if (out == "Default")
    		{
    			out = "TextFile.txt";
    		}
    
    		ifstream infile(in, ios::in);
    		
    		string ss;
    		infile >> ss;
    		//cout << "test:" << ss << endl;
    		int i = 0;
    		string sss;
    
    		while (i < ss.size())
    		{
    			int t = x.root;
    			while ((x.A[t].lson != 0 || x.A[t].rson != 0) && i < ss.size())
    			{
    				if (ss[i] == '0') t = x.A[t].lson;
    				else t = x.A[t].rson;
    				i++;
    			}
    			if (x.A[t].lson == 0 || x.A[t].rson == 0)
    			{
    				sss = sss + (char)t;
    			}
    		}
    
    		infile.close();
    
    		cout << "解码后为:" << endl;
    		cout << sss << endl;
    
    		ofstream outfile(out,ios::out);
    
    		outfile << sss << endl;
    		
    		outfile.close();
    	}
    };
    

    测试代码

    #include"Huffman.h"
    
    #include<iostream>
    
    using namespace std;
    
    int main()
    {
    	
    	Huffman x;
    
    	x.HuffmanDisplay();
    	
    	x.GenerateCode();
    
    	x.Decode();
    
    
    }
    
    

    测试结果

    在这里插入图片描述

    展开全文
  • 问题描述:利用哈夫曼编码进行信息通讯可以大大提高信道利用率,缩短信息传输时间,降低传输成本。但是,这要求在发送端通过一个编码系统对待传输数据预先编码;在接受端将传来数据进行译码。对于双工信道(即...
  • 实验名 实 验 方 实 验 实验六 哈夫曼编码译码的算法设计与实现 称 案 成绩 实验日 实 验 信息系统设计与仿 实 验 操 2012-04-22 期 室 真室 I 作 实验台 班 级 姓 信工 11-1BF 李煌 实 验 结 34 号 号 名 峰 果 ...
  • 实 验 报 告 2015 / 2016 学年 第二学期 课程名称 数据结构A 实验名称 二叉树的基本操作及哈夫曼编码译码系统的实现 实验时间 2016 年 4 月 14 日 指导单位 计算机科学与技术系 指导教师 骆健 学生姓名 班级学号 ...
  • 哈夫曼编码/译码器设计与实现

    千次阅读 2020-06-12 22:28:45
    哈夫曼编码/译码器设计要求设计思路数据结构设计总体设计 设计要求 设计一个利用哈夫曼算法的编码和译码系统,重复地显示并处理以下项目,直到选择退出为止。 基本要求: (1)将权值数据存放在数据文件(文件名为...

    设计要求

    设计一个利用哈夫曼算法的编码和译码系统,重复地显示并处理以下项目,直到选择退出为止。
    基本要求:
    (1)将权值数据存放在数据文件(文件名为data.txt,位于执行程序的当前目录中)
    (2)分别采用动态和静态存储结构
    (3)初始化:键盘输入字符集大小n、n个字符和n个权值,建立哈夫曼树;
    (4)编码:利用建好的哈夫曼树生成哈夫曼编码;
    (5)输出编码;
    (6)设字符集及频度如下表:
    字符 空格 A B C D E F G H I J K L M
    频度 186 64 13 22 32 103 21 15 47 57 1 5 32 20
    字符 N O P Q R S T U V W X Y Z
    频度 57 63 15 1 48 51 80 23 8 18 1 16 1
    (7)译码功能;
    (8)显示哈夫曼树;
    (9)界面设计的优化。

    设计思路

    哈夫曼树的建立由赫夫曼算法的定义可知,初始森林中共有n棵只含有根结点的二叉树。算法的第二步是:将当前森林中的两棵根结点权值最小的二叉树,合并成一棵新的二叉树;每合并一次,森林中就减少一棵树,产生一个新结点。显然要进行n-1次合并,所以共产生n-1个新结点,它们都是具有两个孩子的分支结点。所以,最终求得的哈夫曼树中一共有2n-1个结点,其中n个结点是初始森林的n个孤立结点,剩余n-1结点为新合成节点。并且哈夫曼树中没有度数为1的分支结点。因此我们利用一个大小为2n–1的一维结构体数组来存储哈夫曼树中的结点。
    哈夫曼编码是可变字长编码。编码时借助哈夫曼树,也即带权路径长度最小的二叉树,来建立编码。
    译码的思想是:输入译码码值,并与原先生成的哈夫曼编码表比较,遇到相等时,就取出与之相对应的字符存入一个新串中。

    数据结构设计

    2)数据结构设计:
    全局变量:number 作用:用来打印哈夫曼树每个节点前空格数量。
    数组:HTNode HFT[26] 作用:静态存储哈夫曼树。
    结构体:

    typedef struct
    {
    	char character; 
    	int weight;		//权重
    	int parent,lchild,rchild;	//双亲,左、右孩子 
    }HTNode, *HuffmanTree;		//哈夫曼树(动态分配数组)
    typedef char * *HuffmanCode;	//哈夫曼编码表 
    

    作用:动态建立哈夫曼树。
    文件:据文件data.txt。作用:将权值数据存放在数据文件中。
    类:class Huffman 作用:创建哈夫曼树。

    总体设计

    软件结构设计:本程序主要分为4个模块(功能模块图见下图):主模块、编码模块、译码模块、显示哈夫曼树模块。程序的主体部分,分别调用各个模块,实现各项功能。编码模块:对每个出现的字符进行编码。译码模块:将已有编码译成字符,使之可以直接被读出。显示模块:将建立的哈夫曼书打印出来。

    原文地址:https://download.csdn.net/download/zjb18741809273/12518635
    展开全文
  • 实 验 报 告 实验目的 掌握哈夫曼树基本概念及所用存储结构 掌握哈夫曼树建立算法 掌握哈夫曼树应用哈夫曼树编码和译码 实验内容 给定权值529781423311建立哈夫曼树输出哈夫曼编码对上述给定哈夫曼树及...
  • 用哈夫曼算法构造扩充二叉树称为哈夫曼编码树或哈夫曼树。当然,还有编码和译码部分。本系统前端开发工具是Visual C++6.0。具有输入字符集大小及权值大小,构造哈夫曼树,并对用户输入字符串进行编码以及译码...
  • 采用三叉链表结构:每个节点包含左右孩子指针和父指针。构造函数中,每次选取权值最小两个根节点,构成新节点。 每个符号Huffman编码用0...编码算法实现了给定节点实现0\1串,译码算法实现给定0\1串找出该节点
  • 输入一串字符串,根据给定字符串中字符出现频率建立相应哈夫曼树,构造哈夫曼编码表,在此基础上可以对待压缩文件进行压缩(即编码),同时可以对压缩后二进制编码文件进行解压(即译码)。 输入 多组数据,每...

    本文是记录数据结构习题解析与实验指导的课后实验五------基于哈夫曼树的数据压缩算法。

    1 实验内容

    描述
    输入一串字符串,根据给定的字符串中字符出现的频率建立相应哈夫曼树,构造哈夫曼编码表,在此基础上可以对待压缩文件进行压缩(即编码),同时可以对压缩后的二进制编码文件进行解压(即译码)。

    输入
    多组数据,每组数据一行,为一个字符串(只考虑26个小写字母即可)。当输入字符串为“0”时,输入结束。

    输出
    每组数据输出2n+3行(n为输入串中字符类别的个数)。第一行为统计出来的字符出现频率(只输出存在的字符,格式为:字符:频度),每两组字符之间用一个空格分隔,字符按照ASCII码从小到大的顺序排列。第二行至第2n行为哈夫曼树的存储结构的终态(形如教材139页表5.2(b),一行当中的数据用空格分隔)。第2n+1行为每个字符的哈夫曼编码(只输出存在的字符,格式为:字符:编码),每两组字符之间用一个空格分隔,字符按照ASCII码从小到大的顺序排列。第2n+2行为编码后的字符串,第2n+3行为解码后的字符串(与输入的字符串相同)。

    样例输入1
    aaaaaaabbbbbccdddd
    aabccc
    0

    样例输出1
    a:7 b:5 c:2 d:4
    1 7 7 0 0
    2 5 6 0 0
    3 2 5 0 0
    4 4 5 0 0
    5 6 6 3 4
    6 11 7 2 5
    7 18 0 1 6
    a:0 b:10 c:110 d:111
    00000001010101010110110111111111111
    aaaaaaabbbbbccdddd
    a:2 b:1 c:3
    1 2 4 0 0
    2 1 4 0 0
    3 3 5 0 0
    4 3 5 2 1
    5 6 0 3 4
    a:11 b:10 c:0
    111110000
    aabccc

    2 基本思路

    这里可以参考课本P138–P141,给出的解法很详细。

    3 数据结构代码实现

    1.存储状态的数据结构:

    2 树的创建

    #include<stdio.h>
    
    typedef struct Node
    {
        int weight;
        int parent;
        int lChild;
        int rChild;
    }node;
    
    void initNode(node data[], int len)
    {
        for (int i = 0; i < len; ++i) {
            data[i].parent = 0;
            data[i].lChild = 0;
            data[i].rChild = 0;
        }
        data[0].weight = 65535; //用于下方最小两个数的查找
    }
    
    void createTree(node data[], int len)
    {
        int s1 = 0, s2 = 0;
        int solvedData[len/2];
        int point = 0;
        for (int i = len/2 + 1; i < len; ++i)
        {
            searchTwoNumber(data,i,&s1,&s2,solvedData,point);
            point += 2;
            data[s1].parent = i;
            data[s2].parent = i;
            data[i].weight = data[s1].weight + data[s2].weight;
            data[i].lChild = s1;
            data[i].rChild = s2;
        }
    }
    
    int contains(int solvedData[], int i, int point)
    {
        int flag = 1;
        for (int j = 0; j < point; ++j)
        {
            if (solvedData[j] == i)
                return 0;
        }
        return flag;
    }
    
    void searchTwoNumber(node data[], int end, int *s1, int *s2, int solvedData[], int point)
    {
        int m = 0, n = 0;
        for (int i = 1; i < end; ++i)
        {
            if (data[m].weight > data[i].weight && contains(solvedData,i,point) != 0)
            {
                n = m;
                m = i;
            }
            else if (data[n].weight > data[i].weight && contains(solvedData,i,point) != 0)
            {
                n = i;
            }
        }
        *s1 = m;
        *s2 = n;
        solvedData[point] = m;
        solvedData[point + 1] = n;
    }
    
    void getCharData(char data[], int *len, int *p)
    {
        int i = 0;
        while(data[i] != '\0')
        {
            p[data[i] - 97]++;
            i++;
        }
        i = 0;
        for (int j = 0; j < 26; j++) {
            if (p[j] != 0) {
                i++;
            }
        }
        *len = i;
    }
    
    void show(node data[], int len)
    {
        for (int i = 1; i < len; ++i)
        {
            printf("%d %d %d %d %d\n",i,data[i].weight,data[i].parent,data[i].lChild,data[i].rChild);
        }
    }
    
    int main()
    {
        char data[30] = {'a','a','b','c','c','c'};
        int asc[26] = {0};
        int len = 0;
        //scanf("%s",data);
        getCharData(data,&len,asc);
        node test[len*2];
        for (int i = 0, j = 1; i < 26; ++i)
        {
            if (asc[i] != 0)
            {
                test[j++].weight = asc[i];
                printf("%c:%d ",i+97,asc[i]);
            }
        }
        printf("\n");
        initNode(test,len*2);
        createTree(test,len*2);
        show(test, len*2);
        return 0;
    }
    
    

    首先是剥离字符串,获得不同字母的个数,并且将每个字母的个数存在asc数组中。

    接着构造一个2*len的数组,用于存储,下标0不用,从1开始存储,然后利用asc数组,初始化weight.并且打印出题目要求输出的第一行。

    接着初始化每个节点的weight,rChild,lChild,这里把下标为0的赋为无穷大,用于下方的查找。

    然后创建树,创建树的过程中有一个查找两个最小数据的过程。这时就用到了data[0].weight.并且将查过的数据放到solvedData数组中,以便判断是否已经查找过。

    3.利用构建好的树求解哈夫曼编码

    void coding(node data[], int id)
    {
        char result[8];
        char result2[8];
        int position = id;
        int point = 0;
        int temp;
        while (data[id].parent != 0)
        {
            temp = data[id].parent;
            if (data[temp].lChild == id)
            {
                result[point++] = '0';
            }
            else if (data[temp].rChild == id)
            {
                result[point++] = '1';
            }
            id = temp;
        }
        point--;
        int m = 0;
        while(point >= 0)
        {
            result2[m++] = result[point];
            point--;
        }
        result2[m] = '\0';
        printf("%c:%s ",position+96,result2);
    }
    

    从叶子节点开始网上找,直到根节点。左子树记0,右子树记1,然后因为是从底向上,所以要反转。

    4 全部代码

    #include<stdio.h>
    
    char code[100][100];
    typedef struct Node
    {
        int weight;
        int parent;
        int lChild;
        int rChild;
    }node;
    
    
    
    void initNode(node data[], int len)
    {
        for (int i = 0; i < len; ++i) {
            data[i].parent = 0;
            data[i].lChild = 0;
            data[i].rChild = 0;
        }
        data[0].weight = 65535; //用于下方最小两个数的查找
    }
    
    void createTree(node data[], int len)
    {
        int s1 = 0, s2 = 0;
        int solvedData[len/2];
        int point = 0;
        for (int i = len/2 + 1; i < len; ++i)
        {
            searchTwoNumber(data,i,&s1,&s2,solvedData,point);
            point += 2;
            data[s1].parent = i;
            data[s2].parent = i;
            data[i].weight = data[s1].weight + data[s2].weight;
            data[i].lChild = s1;
            data[i].rChild = s2;
        }
    }
    
    int contains(int solvedData[], int i, int point)
    {
        int flag = 1;
        for (int j = 0; j < point; ++j)
        {
            if (solvedData[j] == i)
                return 0;
        }
        return flag;
    }
    
    void searchTwoNumber(node data[], int end, int *s1, int *s2, int solvedData[], int point)
    {
        int m = 0, n = 0;
        for (int i = 1; i < end; ++i)
        {
            if (data[m].weight > data[i].weight && contains(solvedData,i,point) != 0)
            {
                n = m;
                m = i;
            }
            else if (data[n].weight > data[i].weight && contains(solvedData,i,point) != 0)
            {
                n = i;
            }
        }
        *s1 = m;
        *s2 = n;
        solvedData[point] = m;
        solvedData[point + 1] = n;
    }
    
    void getCharData(char data[], int *len, int *p)
    {
        int i = 0;
        while(data[i] != '\0')
        {
            p[data[i] - 97]++;
            i++;
        }
        i = 0;
        for (int j = 0; j < 26; j++) {
            if (p[j] != 0) {
                i++;
            }
        }
        *len = i;
    }
    
    
    
    void show(node data[], int len)
    {
        for (int i = 1; i < len; ++i)
        {
            printf("%d %d %d %d %d\n",i,data[i].weight,data[i].parent,data[i].lChild,data[i].rChild);
        }
    }
    
    void coding(node data[], int id)
    {
        char result[8];
        char result2[8];
        int position = id;
        int point = 0;
        int temp;
        while (data[id].parent != 0)
        {
            temp = data[id].parent;
            if (data[temp].lChild == id)
            {
                result[point++] = '0';
            }
            else if (data[temp].rChild == id)
            {
                result[point++] = '1';
            }
            id = temp;
        }
        point--;
        int m = 0;
        while(point >= 0)
        {
            result2[m++] = result[point];
            point--;
        }
        result2[m] = '\0';
        printf("%c:%s ",position+96,result2);
    }
    
    int main()
    {
        char data[30] = {'a','a','b','c','c','c'};
        int asc[26] = {0};
        int len = 0;
        //scanf("%s",data);
        getCharData(data,&len,asc);
        node test[len*2];
        for (int i = 0, j = 1; i < 26; ++i)
        {
            if (asc[i] != 0)
            {
                test[j++].weight = asc[i];
                printf("%c:%d ",i+97,asc[i]);
            }
        }
        printf("\n");
        initNode(test,len*2);
        createTree(test,len*2);
        show(test, len*2);
        for(int i = 1; i < len + 1; ++i)
        {
            coding(test, i);
        }
        printf("\n%s",data);
        return 0;
    }
    

    注意: 由于对c字符数组的存储忘得有些厉害,所以这里的编码并没有存储起来,并且也是按字符顺序输出的。和题目要求不太一样,但是编码已知,只需存储起来,然后遍历字符串,然后进行输出即可。

    如果看了有收获,可以点赞加关注😉,看计算机小白的成长之路。

    展开全文
  • 哈夫曼编码C++实现

    万次阅读 2009-06-16 12:15:00
    哈夫曼编码译码算法的c++实现,将功能模块封装成类Huffman 下载地址:http://download.csdn.net/source/1409937 文件main.cpp//main.cpp#include #include "Huffman.h"using namespace std;int main(){ Huffman ...

    哈夫曼编码、译码算法的c++实现,将功能模块封装成类Huffman

     

    下载地址:http://download.csdn.net/source/1409937

     

    文件main.cpp

     

     


     

    文件Huffman.h

     

     

     


     

    文件Huffman.cpp

    展开全文
  • PAGE 中南大学物理学院 数据结构课程 实验报告 实验名称 哈弗曼编码和译码 专业班级 电子...掌握哈夫曼树建立算法 掌握哈夫曼树应用哈夫曼编码译码 实验内容和原理 1.实验内容 用下表给出字符集和频度数据建
  • 哈夫曼编码

    千次阅读 多人点赞 2019-01-10 13:12:38
    1. 问题描述 假设某文本文档只包含26个英文字母,应用哈夫曼算法对该文档进行压缩和解压缩操作,使得该文档占用较少...根据上述问题描述,可以看出编写程序是通过利用二叉树结构实现哈夫曼编码译码,并且程序...
  • 哈夫曼编码的实验报告

    千次阅读 2020-11-28 19:49:24
    通过哈夫曼编、译码算法的实现,巩固二叉树及哈夫曼树相关知识的理解掌握,训练学生运用所学知识,解决实际问题的能力。 二.实验内容         已知每一个字符出现的频率,...
  • 该项目需设计并实现一个对任意英文文章编译码器。 编码功能包括:  统计英文文章中所有字母出现概率;  根据字母出现概率用HUFFMAN算法构造最优二叉树;  记录每个字母HUFFMAN编码于文件中;  ...
  • 电文的编码译码哈夫曼应用)

    千次阅读 多人点赞 2016-12-30 16:33:50
    一、 实验环境 学宝虚拟机,VC6.0二、 实验目的 从键盘接收一串电文字符,输出对应的哈夫曼编码,同时能翻译哈夫曼编码生成代码串,输出对应电文字符。三、 实验内容1.用C语言实现二叉树链式(二叉链表)...
  • 电文编码和译码 问题描述 从键盘接受一串电文字符输出对应的哈夫曼编码同时能翻译由哈夫曼编码生成代码串输出对应电文字符串 设计要求 构造一棵哈夫曼树 实现哈夫曼编码并用哈夫曼编码生成代码进行译码 ...
  • 哈弗曼编码(前缀编码):---哈夫曼树(最优二叉树)可以得到前缀编码,字符串二进制编码,不是固定长度,对于词频高可以短编码,词频低可以长编码,可以压缩数据,用于通信。前缀编码:更准确的译码,一个...
  • 哈夫曼编码-C语言

    千次阅读 多人点赞 2019-11-10 17:02:45
    了解二叉树定义,理解二叉树基本性质和存储结构,掌握哈夫曼树构造,实现哈夫曼编码译码算法。 2.实验内容 从键盘输入一串电文字符与权值,输出对应的哈夫曼编码;从键盘输入一串二进制代码,输出对应...
  • 实 验 报 告 实验目的 掌握哈夫曼树基本概念及所用存储结构 掌握哈夫曼树建立算法 掌握哈夫曼树应用哈夫曼树编码和译码 实验内容 给定权值529781423311建立哈夫曼树输出哈夫曼编码对上述给定哈夫曼树及...
  • 掌握哈夫曼树应用哈夫曼树编码和译码 二 实验内容 给定权值 529781423311建立哈夫曼树输出哈夫曼编码 对上述给定哈夫曼树及得到的哈夫曼编码 试输入一串二进制编码 输出它 哈夫曼译码 三 实验与算法分析 ...
  • 数据结构实验5-哈夫曼编码

    千次阅读 2018-03-03 10:56:00
    实验内容 程序代码 运行结果 实验内容 ...实现哈弗曼译码算法,对给定一组编码(110011111101110110),译出其对应报文部分 。 程序代码 #include &lt;iostream&gt; #includ...
  • 哈夫曼树-贪心算法的应用实例

    千次阅读 2014-12-07 23:11:35
    *哈夫曼编码-链式结构 * *功能实现: * 源文件字符权值确认操作 * 哈夫曼树建立操作 * 字符字典建立操作 * 源文件转码操作操作 * 二进制文件译码操作 * 文件输出操作 * 内存清理操作 */ #include #...
  • 实验项目:哈夫曼编码译码方法 哈夫曼编码是一种以哈夫曼树(最优二叉树,带权路径长度最小二叉树)为基础基于统计学变长编码方式。...本实验要求利用贪心算法实现一个完整的哈夫曼编码译码系统...
  • 实验目的: 1.掌握二叉树二叉链表...3.掌握二叉树先序、中序、后序递归实现方法。 4.掌握哈夫曼概念。 5.掌握哈夫曼构造过程。 6.掌握哈夫曼编码。 7.掌握哈夫曼译码。 实验内容: 在 ...
  • 哈夫曼树及其应用

    千次阅读 2020-02-06 21:05:31
    文章目录哈夫曼树基本概念哈夫曼树构造算法哈夫曼树算法实现哈夫曼编码思想哈夫曼编码的算法实现文件编码和译码 哈夫曼树基本概念 路径:从树中一个结点到另一个结点之间分支构成这两个结点间路径 结点...
  • (一)设计描述 1.题目描述 ...3) 编码:利用建好哈夫曼树生成哈夫曼编码,并输出编码; 4) 译码,即输入每个字符对应二进制编码(0或1),然后输出对应字符。 5) 结束操作。 2.设计目的...
  • 利用哈夫曼编码进行通信,可以压缩通信数据量,提高传输效率,缩短信息传输时间,还有一定保密性。现在要求编写一程序模拟传输过程,实现在发送前将要发送字符信息进行编码,然后进行发送,接收后将传来...
  • 算法的关键是构建最优二叉树(即哈夫曼树),接着对最优二叉树叶子结点进行编码即可,接着就可以输入二进制数进行译码。 构建最优二叉树:将通信字符结点初始化放入二叉树集,每个结点初始是一颗单节点...

空空如也

空空如也

1 2 3
收藏数 50
精华内容 20
关键字:

哈夫曼编码译码的实现算法