数据结构与算法实验-（附加实验）文本串的哈夫曼编码和译码

2024-01-24 13:48
文章标签 算法 数据结构 实验 编码 文本 译码 附加 哈夫曼

本文主要是介绍数据结构与算法实验-（附加实验）文本串的哈夫曼编码和译码，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

文本串的哈夫曼编码和译码

哈夫曼编码是最基本的字符压缩编码。对文本进行哈夫曼编码后再进行信息通讯可以大大提高信道利用率，缩短信息传输时间，降低传输成本。但是，这要求在发送端通过一个编码系统对待传数据预先编码；在接收端将传来的数据进行译码(复原)。 请设计一个程序，输入一行字符文本串（最大长度为10000个字符），构造其哈夫曼编码。根据需要（传输前）选择对字符文本进行编码（将字符文本转换为哈夫曼0-1编码），或对已编码的数据（接收后）进行译码（将0-1编码还原为字符文本）。
具体：
（1）初试化（I）：读入一行文本，根据字符分布建立哈夫曼树，构造字符的哈夫曼编码(用于编码和译码)，输出“Huffman code established!“”；
（2）编码（C）：使用得到的哈夫曼编码对原始字符文本进行编码，输出；
（3）译码（D）：:对编码后的0-1文本进行译码（还原为原来的字符文本），输出；
（4）退出（X）：结束；注：如果编码或译码时，哈夫曼编码还没建立，应提示"Huffman code does not exist!”
例如:
样例输入：
I
Welcome to the school of computer science and technology.
C
D
11011001100100001000101101110111001001011100001101110111010000001110010000101011001101111010001000101111100011100111000111110101011101000011101101101000000111011111000100111101101110001100000110100100001010011111011111101010
X
样例输出：
Huffman code established!
11011001100100001000101101110111001001011100001101110111010000001110010000101011001101111010001000101111100011100111000111110101011101000011101101101000000111011111000100111101101110001100000110100100001010011111011111101010
Welcome to the school of computer science and technology.

要注意：
string不能malloc，要用new! string不能malloc，要用new! string不能malloc，要用new!
就是因为这个，codeblocks上边可以运行通过，OJ上不行，两天的段错误啊……
建立哈夫曼树的方法：
１．找到两个权值最小的点（若权值一样，则选择前面的），然后将这两个点连接到一个“根”上（根的权值是两个点权值之和），将“根”放到原序列最后，将选择的两个点从原序列删除（原序列指删除重复字符后的给定序列）；
２．重复上述操作，直至原序列剩余一个点，将其标记为根节点。

包括空格的字符串这样输入：

getchar();
char c;
scanf("%c",&c);
int i=0;
while(c!='\n')
{str[i]=c;i++;scanf("%c",&c);}
len=i;

完整代码如下：

#pragma GCC optimize(3,"Ofast","inline")
#pragma G++ optimize(3)
#include <bits/stdc++.h>
#include <iostream>
#include <cstdio>
#include <fstream>
#include <algorithm>
#include <cmath>
#include <deque>
#include <vector>
#include <queue>
#include <string>
#include <cstring>
#include <map>
#include <stack>
#include <set>
#include <sstream>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll,ll> pll;
typedef pair<int,int> pii;
typedef queue<int> q_i;
typedef queue<string> q_s;
typedef queue<double> q_d;
typedef queue<ll> q_ll;
typedef queue<char> q_c;
typedef priority_queue<int> pq_i;
typedef priority_queue<string> pq_s;
typedef priority_queue<double> pq_d;
typedef priority_queue<ll> pq_ll;
typedef stack<int> s_i;
typedef stack<string> s_s;
typedef stack<double> s_d;
typedef stack<ll> s_ll;
typedef stack<char> s_c;
typedef map<ll,ll> m_ll_ll;
typedef map<int,ll> m_i_ll;
typedef map<string,ll> m_s_ll;
typedef map<char,int> m_c_i;
typedef map<char,ll> m_c_ll;
#define rep(i,l,r) for(ll i=l;i<=r;i++)
#define per(i,l,r) for(ll i=r;i>=l;i--)
#define eif else if
#define N 3005
#define mm(dp) memset(dp,0,sizeof(dp))
#define mm1(dp) memset(dp,-1,sizeof(dp))
#define mm2(dp) memset(dp,0x3f,sizeof(dp))
#define IT set<int>::iterator
#define fs(n) fixed<< setprecision(n)
#define inf 0x3f3f3f3f
const double e=2.71828182845;
const double pi = acos(-1.0);
map<char,int>mapp;
map<char,string>mapp1;
typedef struct
{string s1;int num;
}STU;
typedef struct
{string s1,s0;int num;
}STU1;
bool cmp(STU x,STU y)
{return x.num>y.num;
}
typedef struct node
{string data;struct node *left,*right;
}HuffmanTreeNode,*PtrHuffman;
class Haffman
{public:PtrHuffman head=NULL;PtrHuffman p[100005];void create1(int nm,STU *stu){int u=0;rep(i,1,nm){PtrHuffman t=new HuffmanTreeNode;t->data = stu[i].s1;t->left = t->right = NULL;p[i]= t;}rep(i,1,nm-1){int fi=inf,se=inf;int fi1=0,se1=0;rep(j,1,nm+u){if(stu[j].num>0&&stu[j].num<fi){fi=stu[j].num;fi1=j;}}rep(j,1,nm+u){if(stu[j].num>0&&stu[j].num<se&&j!=fi1){se=stu[j].num;se1=j;}}PtrHuffman q=new HuffmanTreeNode;q->data=p[fi1]->data+p[se1]->data;q->left=p[fi1];q->right=p[se1];u++;stu[nm+u].s1=stu[fi1].s1+stu[se1].s1;stu[nm+u].num=stu[fi1].num+stu[se1].num;p[nm+u]=q;stu[fi1].num=-1;stu[se1].num=-1;head=q;}}void bianli(struct node *t1,int u){if(t1==NULL)return;if(u==0)cout<<t1->data<<endl;else{cout<<u<<" ";cout<<t1->data<<endl;}bianli(t1->left,u+1);bianli(t1->right,u+1);}void bianli1(struct node *t1,char ch,string str){if(t1==NULL)return;string s1="";s1+=ch;string ss=t1->data;if(ss==s1){mapp1[ch]=str;return;}else{string s=t1->data;int len=s.size();int flag=0;rep(i,0,len){if(s[i]==ch){flag=1;break;}}if(flag==0)return;else{bianli1(t1->left,ch,str+"0");bianli1(t1->right,ch,str+"1");}}}STU1 bianli2(struct node *t1,string str){if(t1->data.size()==1){STU1 stu;stu.s1=t1->data;int len=str.size();stu.s0=str;return stu;}char ch=str[0];int len=str.size();str=str.substr(1,len-1);if(ch=='0'){return bianli2(t1->left,str);}if(ch=='1'){return bianli2(t1->right,str);}}
};
int len;
int main()
{//ios::sync_with_stdio(false);//cin.tie(0);//cout.tie(0);Haffman ha;char str[10005];int uu=0;while(1){char ch;cin>>ch;if(ch=='X')break;eif(ch=='I'){getchar();char c;scanf("%c",&c);int i=0;while(c!='\n'){str[i]=c;i++;scanf("%c",&c);}len=i;string ss="";rep(i,0,len-1){if(mapp[str[i]]==0){mapp[str[i]]=1;ss+=str[i];}eif(mapp[str[i]]!=0){mapp[str[i]]++;}}int len1=ss.size();STU stu[10005];rep(i,0,len1-1){string s0="";char c=ss[i];s0+=c;stu[i+1].s1=s0;stu[i+1].num=mapp[c];}ha.create1(len1,stu);cout<<"Huffman code established!"<<endl;uu=1;}eif(ch=='C'){if(uu==0){cout<<"Huffman code does not exist!"<<endl;}else{rep(i,0,len-1){char cc=str[i];ha.bianli1(ha.head,cc,"");cout<<mapp1[str[i]];}cout<<endl;}}eif(ch=='D'){if(uu==0){cout<<"Huffman code does not exist!"<<endl;}else{string s2;cin>>s2;while(1){if(s2=="")break;STU1 huan=ha.bianli2(ha.head,s2);cout<<huan.s1;s2=huan.s0;}cout<<endl;}}}return 0;
}

这篇关于数据结构与算法实验-（附加实验）文本串的哈夫曼编码和译码的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

原文地址:
本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：http://www.chinasem.cn/article/639891。

相关文章

详解如何使用Python从零开始构建文本统计模型

详解如何使用Python从零开始构建文本统计模型

《详解如何使用Python从零开始构建文本统计模型》在自然语言处理领域,词汇表构建是文本预处理的关键环节,本文通过Python代码实践,演示如何从原始文本中提取多尺度特征,并通过动态调整机制构建更精确... 目录一、项目背景与核心思想二、核心代码解析1. 数据加载与预处理2. 多尺度字符统计3. 统计结果可
阅读更多...
使用雪花算法产生id导致前端精度缺失问题解决方案

使用雪花算法产生id导致前端精度缺失问题解决方案

《使用雪花算法产生id导致前端精度缺失问题解决方案》雪花算法由Twitter提出,设计目的是生成唯一的、递增的ID,下面：本文主要介绍使用雪花算法产生id导致前端精度缺失问题的解决方案,文中通过代... 目录一、问题根源二、解决方案1. 全局配置Jackson序列化规则2. 实体类必须使用Long封装类3.
阅读更多...
基于Go语言实现Base62编码的三种方式以及对比分析

基于Go语言实现Base62编码的三种方式以及对比分析

《基于Go语言实现Base62编码的三种方式以及对比分析》Base62编码是一种在字符编码中使用62个字符的编码方式,在计算机科学中,,Go语言是一种静态类型、编译型语言,它由Google开发并开源,... 目录一、标准库现状与解决方案1. 标准库对比表2. 解决方案完整实现代码（含边界处理）二、关键实现细
阅读更多...
Springboot实现推荐系统的协同过滤算法

Springboot实现推荐系统的协同过滤算法

《Springboot实现推荐系统的协同过滤算法》协同过滤算法是一种在推荐系统中广泛使用的算法,用于预测用户对物品（如商品、电影、音乐等）的偏好,从而实现个性化推荐,下面给大家介绍Springboot... 目录前言基本原理 算法分类 计算方法应用场景 代码实现 前言协同过滤算法（Collaborativ
阅读更多...
解决IDEA报错:编码GBK的不可映射字符问题

解决IDEA报错:编码GBK的不可映射字符问题

《解决IDEA报错:编码GBK的不可映射字符问题》：本文主要介绍解决IDEA报错:编码GBK的不可映射字符问题,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录IDEA报错:编码GBK的不可映射字符终端软件问题描述原因分析解决方案方法1：将命令改为方法2：右下jav
阅读更多...
C#TextBox设置提示文本方式(SetHintText)

C#TextBox设置提示文本方式(SetHintText)

《C#TextBox设置提示文本方式(SetHintText)》：本文主要介绍C#TextBox设置提示文本方式(SetHintText),具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑... 目录C#TextBox设置提示文本效果展示核心代码总结C#TextBox设置提示文本效果展示核心代
阅读更多...
openCV中KNN算法的实现

openCV中KNN算法的实现

《openCV中KNN算法的实现》KNN算法是一种简单且常用的分类算法,本文主要介绍了openCV中KNN算法的实现,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的... 目录KNN算法流程使用OpenCV实现KNNOpenCV 是一个开源的跨平台计算机视觉库，它提供了各
阅读更多...
springboot+dubbo实现时间轮算法

springboot+dubbo实现时间轮算法

《springboot+dubbo实现时间轮算法》时间轮是一种高效利用线程资源进行批量化调度的算法,本文主要介绍了springboot+dubbo实现时间轮算法,文中通过示例代码介绍的非常详细,对大家... 目录前言一、参数说明二、具体实现1、HashedwheelTimer2、createWheel3、n
阅读更多...
Python使用自带的base64库进行base64编码和解码

Python使用自带的base64库进行base64编码和解码

《Python使用自带的base64库进行base64编码和解码》在Python中,处理数据的编码和解码是数据传输和存储中非常普遍的需求,其中,Base64是一种常用的编码方案,本文我将详细介绍如何使... 目录引言使用python的base64库进行编码和解码编码函数解码函数Base64编码的应用场景注意
阅读更多...
C#数据结构之字符串(string)详解

C#数据结构之字符串(string)详解

《C#数据结构之字符串(string)详解》：本文主要介绍C#数据结构之字符串(string),具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录转义字符序列字符串的创建字符串的声明null字符串与空字符串重复单字符字符串的构造字符串的属性和常用方法属性常用方法总结摘
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2