没有合适的资源?快使用搜索试试~ 我知道了~
数据结构实验报告模板(2).docx
资源推荐
资源详情
资源评论
一、实验目的
掌握赫夫曼树和赫夫曼编码的基本思想和算法的程序实现。
二、实验内容及要求
1、任务描述
实验内容:
实现文件中数据的加解密与压缩:将硬盘上的一个文本文件进行加密,比较加密文件和原始文件
的大小差别;对加密文件进行解密,比较原始文件和解码文件的内容是否一致。
实验说明:
1.输入和输出:
(1)输入:硬盘上给定的原始文件及文件路径。
(2)输出:
硬盘上的加密文件及文件路径;
硬盘上的解码文件及文件路径;
原始文件和解码文件的比对结果。
2.实验要求:
提取原始文件中的数据(包括中文、英文或其他字符),根据数据出现的频率为权重,构建 Huffman
编码表;
根据 Huffman 编码表对原始文件进行加密,得到加密文件并保存到硬盘上;
将加密文件进行解密,得到解码文件并保存点硬盘上;
比对原始文件和解码文件的一致性,得出是否一致的结论。
3.参考类型定义 //双亲孩子表示法
typedef struct {
unsigned int weight;
unsigned int parent, lchild, rchild;
} HTNode, *HuffmanTree; //动态分配数组存储赫夫曼树
typedef char * * HuffmanCode; //动态分配数组存储赫夫曼编码表
2、主要数据类型与变量
typedef struct {
unsigned int weight;
unsigned int parent, lchild, rchild;
} HTNode, *HuffmanTree; //动态分配数组存储赫夫曼树
typedef char * * HuffmanCode; //动态分配数组存储赫夫曼编码表
//在链表中插入节点
代码中定义了两种结构体类型:LIST 和 TREE。它们都包含了一些整型变量(如 high、low 和
weight)、指针变量(如 NEXT、Left 和 Right)和字符数组(如 code)。此外,还定义了一些
全 局 变 量 , 包 括 整 型 数 组 queue 、 整 型 变 量 queue_index 、 sum_bit_coding 和
sum_bit_decoding,以及字符数组 file_in 和 file_out。
3、算法或程序模块
根据字符频率表构建哈夫曼树。
将每个字符都构建成一颗树,对森林进行 n – 1 次合并操作。每次选两个权值最小的
树进行合并,新树的权值为两者之和,并将新树加入森林,重复合并步骤。
build_tree(LIST head) 函数用于构建哈夫曼树,coding(TREE Tree) 函数用于生成哈夫曼
树,update_tree(TREE Tree) 函数用于更新信息并将每个字符的编码保存到对应节点之中,
save_file(TREE* a, int right, TREE Tree) 函数用于保存编码信息并压缩原文本文件,
decoding() 函数用于将哈夫曼编码解码并将得到的数据保存到新文件中。
//构建哈夫曼树,将链表转化为二叉树
TREE build_tree(LIST head)
{
TREE Tree = tree_node_init(head->high, head->low, 0);
TREE T = Tree;
LIST P = head->NEXT;
while (P)
{
T->NEXT = tree_node_init(P->high, P->low, P->weight);
T = T->NEXT;
Tree->weight++;
P = P->NEXT;
}
return Tree;
}
//更新信息,将每个字符的编码保存到对应节点之中
void update_tree(TREE Tree)
{
TREE a[1000];
int left = 0, right = 0;
if (!Tree) return;
a[right++] = Tree->NEXT;
while (left < right)
{
if (a[left]->Left)
{
a[right++] = a[left]->Left;
strcpy_s(a[left]->Left->code, a[left]->code);
a[left]->Left->code_index = strlen(a[left]->code);
a[left]->Left->code[a[left]->Left->code_index++] = '0';
}
if (a[left]->Right)
{
a[right++] = a[left]->Right;
strcpy_s(a[left]->Right->code, a[left]->code);
a[left]->Right->code_index = strlen(a[left]->code);
a[left]->Right->code[a[left]->Right->code_index++] = '1';
}
left++;
}
save_file(a, right, Tree);
}
//保存编码信息,压缩原文本文件
void save_file(TREE* a, int right, TREE Tree)
{
int left;
sum_bit_coding = 0;
FILE* P;
fopen_s(&P, file_in, "r");
char coding_file_name[100];
strcpy_s(coding_file_name, file_out);
strcat_s(coding_file_name, "coding.txt");
FILE* out;
fopen_s(&out, coding_file_name, "wb");
if (P == NULL)
printf("文件打开失败\n");
int ch;
while ((ch = fgetc(P)) != EOF)
{
LIST tmp = init_LIST(ch, -1, 1);
if (ch > 128)
tmp->low = fgetc(P);
for (left = 0; left < right; left++)
{
if (a[left]->high == tmp->high)
{
if (tmp->high > 128 && tmp->low == a[left]->low)
{
fprintf(out, "%s", a[left]->code);
sum_bit_coding += strlen(a[left]->code);
}
if (tmp->high <= 128)
{
fprintf(out, "%s", a[left]->code);
sum_bit_coding += strlen(a[left]->code);
}
}
}
free(tmp);
}
fclose(P);
fclose(out);
}
三、测试
1、方案
用记事本创建一个 txt 文件,命名为 shuju.txt,在文件里填充一些数据。
剩余20页未读,继续阅读
资源评论
西山早已
- 粉丝: 0
- 资源: 1
上传资源 快速赚钱
- 我的内容管理 展开
- 我的资源 快来上传第一个资源
- 我的收益 登录查看自己的收益
- 我的积分 登录查看自己的积分
- 我的C币 登录后查看C币余额
- 我的收藏
- 我的下载
- 下载帮助
安全验证
文档复制为VIP权益,开通VIP直接复制
信息提交成功