技术标签: 哈夫曼字符串编码c语言实现
实验目的:
(1) 掌握二叉树的定义;
(2) 掌握哈夫曼树和哈夫曼编码算法的实现。???
实验内容:
实现一个哈夫曼编码系统,系统包括以下功能:
(1) 字符信息统计:读取待编码的源文件SourceFile.txt,统计出现的字符及其频率。
附:SourceFile.txt文件内容为
U ARE THE BEST IN MY HEART
(2) 建立哈夫曼树:根据统计结果建立哈夫曼树。
(3) 建立哈夫曼码表:利用得到的哈夫曼树,将各字符对应的编码表保存在文件Code.txt中。
(4) 对源文件进行编码:根据哈夫曼码表,将SourceFile.txt中的字符转换成相应的编码文件ResultFile.txt。
实现提示:
(1) 字符信息统计:假设源文件SourceFile.txt中的字符只有大小写英文字母(同一个字母的大小写看作一个字符),则字符统计算法的实现过程可以归纳为:先定义一个含有26个元素的整形数组,用来存储各个字母出现的次数,最后还要排除其中出现次数为0的数组元素。
(2) 建立哈夫曼树:参考教材算法5.10,补充函数Select的实现。
(3) 建立哈夫曼码表:参考教材算法5.11,将编译表HC中的内容写到文件Code.txt中。
(4) 对源文件进行编码:依次读入文件SourceFile.txt中的字符?c,在编码表?HC?中找到此字符,将字符c转换为编码表中存放的编码串,写入编码文件ResultFile.txt中,直到所有的字符处理完毕为止。
代码实现
#define _CRT_SECURE_NO_WARNINGS
#include
#include
#include
#include
#include
using namespace std;
typedef struct{
int weight;
int parent, lchild, rchild;
}HTNode, *HuffmanTree;
typedef char **HuffmanCode;
int a[24 + 1], b[24 + 1];
char c[24 + 1];
void Select(HuffmanTree &HT, int n, int &s1, int &s2){
for (int i = 1; i <= n; i++)
if (HT[i].parent == 0 && s1 == 0) { s1 = i; break; }
for (int i = 1; i <= n; i++)
if (HT[i].parent == 0 && HT[i].weight
for (int i = 1; i <= n; i++)
if (HT[i].parent == 0 && s2 == 0 && i != s1) { s2 = i; break; }
for (int i = 1; i <= n; i++)
if (HT[i].parent == 0 && HT[i].weight
}
void CreateHuffmanTree(HuffmanTree &HT, int n){
if (n <= 1) return;
int m = 2 * n - 1;//构造一棵哈夫曼树所需要的所有节点数
HT = new HTNode[m + 1];//m+1指从第一个结点开始,第0个结点不用
for (int i = 1; i <= m; i++){
HT[i].parent = 0;
HT[i].lchild = 0;
HT[i].rchild = 0;
}
for (int i = 1; i <= n; i++) HT[i].weight = b[i];//把字母出现的次数赋值给哈夫曼树的weight
for (int i = n + 1; i <= m; i++){
int s1 = 0, s2 = 0;
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;
}
}
void CreateHuffmanCode(HuffmanTree &HT, HuffmanCode &HC, int n){
HC = new char*[n + 1];
char *cd = new char[n];
cd[n - 1] = '\0';
for (int i = 1; i <= n; i++){
int start = n - 1, c = i, f = HT[i].parent;
while (f){
--start;
if (HT[f].lchild == c) cd[start] = '0';
else cd[start] = '1';
c = f;
f = HT[f].parent;
}
HC[i] = new char[n - start];
strcpy(HC[i], &cd[start]);
}
delete cd;
}
int main(){
freopen("SourceFile.txt", "r", stdin);//打开输入文件
memset(a, 0, sizeof(a));
string str;
getline(cin, str);//接收文件的字符串并保存到str中
for (int i = 0; i
a[str[i] - 64]++;
int n = 0;
for (int i = 1, j = 1; i <= 24; i++)//统计有多少个不同的字母以及把没出现的字母去除掉
if (a[i] != 0){
n++;
b[j] = a[i];
c[j++] = i + 64;
}
HuffmanTree HT;
HuffmanCode HC;
CreateHuffmanTree(HT, n);
CreateHuffmanCode(HT, HC, n);
freopen("Code.txt", "w", stdout);
for (int i = 1; i <= n; i++)
cout << c[i] << ':' << HC[i] << endl;
freopen("ResultFile.txt", "w", stdout);
for (int i = 0; i
for (int j = 1; j <= n; j++){
if (str[i] == c[j]) cout << HC[j];
}
}
return 0;
}
Code.txt
A:000
B:0110
E:111
H:001
I:0111
M:1000
N:1001
R:010
S:1010
T:110
U:1011
ResultFile.txt
101100001011111000111101101111010110011110011000001111000010110
实验结果
原文:https://www.cnblogs.com/zhengyu-ahu/p/12038832.html
文章浏览阅读1k次。通过使用ajax方法跨域请求是浏览器所不允许的,浏览器出于安全考虑是禁止的。警告信息如下:不过jQuery对跨域问题也有解决方案,使用jsonp的方式解决,方法如下:$.ajax({ async:false, url: 'http://www.mysite.com/demo.do', // 跨域URL ty..._nginx不停的xhr
文章浏览阅读2k次。关于在 Oracle 中配置 extproc 以访问 ST_Geometry,也就是我们所说的 使用空间SQL 的方法,官方文档链接如下。http://desktop.arcgis.com/zh-cn/arcmap/latest/manage-data/gdbs-in-oracle/configure-oracle-extproc.htm其实简单总结一下,主要就分为以下几个步骤。..._extproc
文章浏览阅读1.5w次。linux下没有上面的两个函数,需要使用函数 mbstowcs和wcstombsmbstowcs将多字节编码转换为宽字节编码wcstombs将宽字节编码转换为多字节编码这两个函数,转换过程中受到系统编码类型的影响,需要通过设置来设定转换前和转换后的编码类型。通过函数setlocale进行系统编码的设置。linux下输入命名locale -a查看系统支持的编码_linux c++ gbk->utf8
文章浏览阅读750次。今天准备从生产库向测试库进行数据导入,结果在imp导入的时候遇到“ IMP-00009:导出文件异常结束” 错误,google一下,发现可能有如下原因导致imp的数据太大,没有写buffer和commit两个数据库字符集不同从低版本exp的dmp文件,向高版本imp导出的dmp文件出错传输dmp文件时,文件损坏解决办法:imp时指定..._imp-00009导出文件异常结束
文章浏览阅读143次。当下是一个大数据的时代,各个行业都离不开数据的支持。因此,网络爬虫就应运而生。网络爬虫当下最为火热的是Python,Python开发爬虫相对简单,而且功能库相当完善,力压众多开发语言。本次教程我们爬取前程无忧的招聘信息来分析Python程序员需要掌握那些编程技术。首先在谷歌浏览器打开前程无忧的首页,按F12打开浏览器的开发者工具。浏览器开发者工具是用于捕捉网站的请求信息,通过分析请求信息可以了解请..._初级python程序员能力要求
文章浏览阅读7.6k次,点赞2次,收藏6次。@Service标注的bean,类名:ABDemoService查看源码后发现,原来是经过一个特殊处理:当类的名字是以两个或以上的大写字母开头的话,bean的名字会与类名保持一致public class AnnotationBeanNameGenerator implements BeanNameGenerator { private static final String C..._@service beanname
文章浏览阅读6.9w次,点赞73次,收藏463次。1.前序创建#include<stdio.h>#include<string.h>#include<stdlib.h>#include<malloc.h>#include<iostream>#include<stack>#include<queue>using namespace std;typed_二叉树的建立
文章浏览阅读7.1k次。在Asp.net上使用Excel导出功能,如果文件名出现中文,便会以乱码视之。 解决方法: fileName = HttpUtility.UrlEncode(fileName, System.Text.Encoding.UTF8);_asp.net utf8 导出中文字符乱码
文章浏览阅读2.1k次,点赞4次,收藏23次。第一次实验 词法分析实验报告设计思想词法分析的主要任务是根据文法的词汇表以及对应约定的编码进行一定的识别,找出文件中所有的合法的单词,并给出一定的信息作为最后的结果,用于后续语法分析程序的使用;本实验针对 PL/0 语言 的文法、词汇表编写一个词法分析程序,对于每个单词根据词汇表输出: (单词种类, 单词的值) 二元对。词汇表:种别编码单词符号助记符0beginb..._对pl/0作以下修改扩充。增加单词
文章浏览阅读773次。我在使用adb.exe时遇到了麻烦.我想使用与bash相同的adb.exe shell提示符,所以我决定更改默认的bash二进制文件(当然二进制文件是交叉编译的,一切都很完美)更改bash二进制文件遵循以下顺序> adb remount> adb push bash / system / bin /> adb shell> cd / system / bin> chm..._adb shell mv 权限
文章浏览阅读6.8k次,点赞12次,收藏125次。1. 单目相机标定引言相机标定已经研究多年,标定的算法可以分为基于摄影测量的标定和自标定。其中,应用最为广泛的还是张正友标定法。这是一种简单灵活、高鲁棒性、低成本的相机标定算法。仅需要一台相机和一块平面标定板构建相机标定系统,在标定过程中,相机拍摄多个角度下(至少两个角度,推荐10~20个角度)的标定板图像(相机和标定板都可以移动),即可对相机的内外参数进行标定。下面介绍张氏标定法(以下也这么称呼)的原理。原理相机模型和单应矩阵相机标定,就是对相机的内外参数进行计算的过程,从而得到物体到图像的投影_相机-投影仪标定
文章浏览阅读2.2k次。文章目录Wayland 架构Wayland 渲染Wayland的 硬件支持简 述: 翻译一篇关于和 wayland 有关的技术文章, 其英文标题为Wayland Architecture .Wayland 架构若是想要更好的理解 Wayland 架构及其与 X (X11 or X Window System) 结构;一种很好的方法是将事件从输入设备就开始跟踪, 查看期间所有的屏幕上出现的变化。这就是我们现在对 X 的理解。 内核是从一个输入设备中获取一个事件,并通过 evdev 输入_wayland