基于C语言的哈夫曼转化软件_给出一组关键值,建立哈夫曼树,显示该哈夫曼树

作者：爱喝兽奶帝天荒 | 2024-07-21 02:05:47

踩

给出一组关键值,建立哈夫曼树,显示该哈夫曼树

题目

哈夫曼树、编码：给出一组关键值，建立哈夫曼树，显示该哈夫曼树，并给出每个关键值的哈夫曼编码。

说明：关键值的获得可以选择通过以下途径：

给定的一组关键值；
给定的一个文本；
随机输入的一段文本。

软件功能

首先给出主页面显示：

在这里插入图片描述

该软件可实现如下功能：

用户可以通过点击“打开文件”按钮打开本地计算机中任意一个文本文件，点击确认将其文本导入到程序输入文本框中，也可以直接在文本框中通过键盘键入文本。
文本支持 UTF-8 格式，可以随意输入英文、数字和中文交给程序运行处理。
点击“开始”按钮可以开始程序，点击后该按钮变成“终止”按钮，点击即可终止程序。程序执行过程中，首先将字符逐个添加到右侧的编码表中，新添加一栏或者频率加一，正在处理的字符在文本框和编码表内都会有高亮颜色突出显示，不同的字符也会随机赋予不同的颜色显示，进行有效区分。
会按照字符出现频率将字符从上到下排序，出现频率即对应权重，首先将所有字符输入到树结构中当做初始节点，然后按照构建哈夫曼树的算法逐渐把节点按权重升序添加到哈夫曼树中，中间的树视图会将这一过程进行动态展示，过程中会对当前添加节点进行高亮颜色突出显示。
哈夫曼树建好之后，根据各个节点在树上的位置，对各个字符进行编码，显示到右侧的编码表中。
获得了字符编码后，即可对字符串的哈夫曼编码进行动态输出，输出在左下角的富文本框中，同样的，输出过程会有当前字符及其对应编码的高亮显示。
点击“停止”按钮可在程序执行过程中暂停程序，点击后按钮变为“继续”，再次点击即可继续执行。
当上一步点击“停止”后，可以点击“下一步”按钮，一步步的进行程序运行，仔细观察程序运行的每一步。
配有速度拖动条可以动态调节程序执行速度，每一步 1ms-1800ms 的变化区间，非常灵活，是通过控制 timer 控件的间隔来实现的。
程序会显示当前的运行步骤，主要有五个阶段（终止，读入，建树，编码，输出）
随机生成颜色种子，不同的字符会有不同的颜色显示，包括其对应的编码。
通过 ToolTip 控件，当程序执行完后，鼠标落在树节点上会显示树节点的路径权重编码信息，直观明了。

设计思想

可视化图形界面采用 C# .net framwork 编写，初步接触窗体程序设计，感觉和网页页面的前端后端类似，“前端”即窗体程序显示界面，通过.net framework 框架工具箱里的各个组件灵活进行搭配，至于“后端”，即各个模块对应的处理程序代码及其相应的算法。题目要求通过多种方式读入字符串，我考虑通过调用计算机本地文本文件或者直接输入两种方式输入字符串，这就需要一个按钮调用 openFileDialog 组件和一个文本输入框，题目要求给出哈夫曼树的构建显示过程并输出哈夫曼编码，没有涉及到解码过程，这就简单多了，哈弗曼编码的过程简单说就是先对所有字符排序，把它们当做初始节点，然后按照权重由小到大一个一个往哈夫曼树里增添。最后根据字符在哈夫曼树中的位置，进行相应的 0、1 编码，这样每个字符都会获得自己的一个独有的编码，最后按照字符串中字符的顺序依次输出编码，初始想法是这样。因此需要输入模块、控制模块、执行模块、输出模块，每个模块都会有不同的属性和功能。因此，首先通过 VS 可视化操作将整体页面设计完善，然后进入代码页面赋予对应模块相应的功能，最后达到程序正常运转。之后考虑到调整程序速度或者逐步执行以便详细观察哈夫曼编码过程，考虑添加 timer 计数器模块，通过控制其计时间隔控制程序执行速度，开始或者暂停。

程序按照以下步骤展开：
在这里插入图片描述

运行过程可分为以下几个过程：

将字符逐个添加到编码表中，计算频率并进行排序
按照各个字符出现频率（权重）有小到大插入到哈夫曼树中根据字符在书中节点位置给出对应 0、1 编码根据字符编码输出字符串哈夫曼编码

逻辑结构与物理结构

存储数据用的.net framework 表格组件 DataGridView，实质是二维数组，属于逻辑结构。

public class DataGridView : Control, ISupportInitialize public DataGridViewCell this[string columnName, int rowIndex] {    get;    set;} public DataGridViewCell this[int columnIndex, int rowIndex] { get; set; }
1

树结构用的.net framework 树视图组件 TreeView，其节点表示为

public class TreeNode : MarshalByRefObject, ICloneable, ISerializable public TreeNode(string text, TreeNode[] children)
1

本软件实例中其 children 数一直为 2，即

public TreeNode(string text, TreeNode *left,TreeNode *right)
1

由于 C#没有指针，所以采用连续的数组表示，树结构属于链式存储，是物理结构。重要函数（方法）：

在这里插入图片描述

输入操作：

private void button1_Click(object sender, EventArgs e)//导入文本文件
1

按钮控制操作：

private void richTextBox_input_Enter(object sender, EventArgs e)//获取焦点 private void richTextBox_input_Leave(object sender, EventArgs e)//失去焦点 private void button2_Click(object sender, EventArgs e)  //点击开始按钮 private void trackBar1_Scroll(object sender, EventArgs e) //拖动速度条 private void button3_Click(object sender, EventArgs e)  //点击暂停按钮 private void button4_Click(object sender, EventArgs e)  //点击下一步
1

程序执行：

private void timer1_Tick(object sender, EventArgs e)//计时器 private void Next_Algrithm_State()//下一个状态
private void Read()  //读入 private void BuildingTree()   //构建哈夫曼树 private void GenerateCode()  //编码 private void Walking(string PathWay, TreeNode No)//朝左，朝右 private void GenerateOutput()//输出，到DataGridView private void Painting(string PathWay, TreeNode No, bool CleaningUp)
//richTextBox_output输出 private void richTextBox_output_TextChanged(object sender, EventArgs e)//文本框
1
2
3

内容改变

private 	void 	dataGridView1_RowStateChanged_1(object 	sender,
        DataGridViewRowStateChangedEventArgs e)//DataGridView编码表状态改变
1
2

开发平台

CPU:AMD Ryzen 7 4800H with Radeon Graphics 2.90GHz
1

系统类型：Windows10 64 位，基于 X64

开发环境：Visual Studio 2019 professional

Visual C#
.Net Framework
1
2

调用的系统命名空间：

using System;using System.Collections;using System.ComponentModel;using System.Drawing;using System.IO;using System.Text;using System.Windows.Forms;
1

系统的运行结果分析说明

利用 Visual Studio C# .Net Framework 集成开发环境，先设计好整体页面，将各组件布置到位，然后依次完成输入、控制、运行（数据插入数组，排序，插入树节点，输出哈弗曼编码）以及其他的一些操作的逻辑构建，代码编写，逐步调试，如果出现错误，则通过加入断点，判断出错位置，进行修正。经过验证，本软件运行正确，与手写推倒的结果一致，运行过程稳定，并且可以在运行中选择暂停、继续、加速、减速等操作，稳定性良好。考虑了没有输入文本就开始运行等状况，容错性良好。基本上达到了题目的要求并且进行了一些功能的优化和改进。虽然题目没要求进行解码，但我认为解码也是很有必要的，目前没有加入这一模块，这是一个缺点和遗憾，另外，界面美观度,UI 设计也有待改善。

操作说明

打开可执行文件

在这里插入图片描述