课程设计哈夫曼编码编程实现

1、课程设计报告课程名称：数据结构课程设计课程设计主题：霍夫曼编码编程实现领带：数学与计算科学系专门：信息与计算科学年级、班级：姓名：学生卡：导师：职称：讲师课程设计主题：使用霍夫曼编码进行通信可以大大提高信道利用率，缩短信息传输时间，降低传输成本。尝试设计一个霍夫曼编码系统。功能需求：从键盘输入消息（如“你做了什么让你这么开心”）或从文档中读取，输出消息的霍夫曼码。话题分析：根据项目要求，在编程中要实现字符统计、Huffman树的建立和树的Huffman码的读取。这三个是按顺序执行的。实现想法1、人物统计：字符统计就是计算字符出现的频率，它构成了霍夫曼树的叶子节点的权重。在实现中，我使用链表来表

2、示字符的统计信息。并将所有字符关联在一起。该链表在下文中称为承载统计字符的链表。链表中的节点是一个结构。结构信息节点字符 ch;整数频率；结构信息节点*下一个； *head0;其中ch用于记录对应的字符。频率用来记录字符出现的频率，最后用来形成霍夫曼树叶节点的权重。使用 head0 指向链表。其中，我自己在这个链表中的表头节点不作为统计字符的记录。并且其头节点的频率记录了链表中的字符和数字。实现以下功能很方便。无效统计（）字符 ch;while(ch=cin.get()!=#)/从输入流中断中获取字符if (!find_record(ch)/如果带字符的链表中有那个字符，则不记录。返回调用函数

3、 / 编号。recording(ch);/如果携带该字符的链表中没有该字符，则在该链表中插入一个节点 / 记录该字符。别的count(ch);/ 因为这个字符，在携带统计的字符链表中字符节点的编号记录项加1。2. 构建霍夫曼树：在构造霍夫曼树时，采用了它的构造方法，即从霍夫曼树中的叶子节点开始建立树。每次从没有父节点的节点中选出权重最小的两个节点，它们的权重之和用来构造一个新节点的权重，两个节点用来记录它们的父节点。关键是那个新节点。重复上述操作，直到构建出最终的树。而霍夫曼代码的读取可以通过遍历树来完成。在这里，我使用树的父母符号来表示树的结构。创建一个2*n-1的霍夫曼树节点空间，将n个节

4、点值输入到存放霍夫曼树节点的空间的前n个空间中，这n个节点就是叶子节点（其中n是不同的个数人物）。它们的相关数据来自于统计字符链表中的相应数据。对于叶子节点，需要读取统计字符链表中某个节点的数据。剩余空间用于存储其他节点，因为如果一棵 Huffman 树有 n 个叶子节点，那么这棵树总共有 2*n-1 个节点。叶节点是输入，即如何构造树的问题。我使用双亲符号来表示树的节点。每个节点都有一个结构类型。结构 huffman_number_node字符 ch;整数数据；诠释父母；int left_child;int right_child; *头;ch 是一个字符。数据用于记录权重。 parent

5、用于记录节点的位置，如果没有父节点，其值为-1，left_child 用于记录其左子节点的位置，如果没有左子树，则记录为0 . ritht_child 用于记录右子节点的位置。如果没有右孩子则记为0。最后用head指向那个存储空间。这可能是关联所有节点以形成树的好方法。使用构造霍夫曼树的方法来构造霍夫曼树。enter_huffman_values(n);/霍夫曼树叶节点的输入creat_huffman_tree(number,n);/创建霍夫曼树从霍夫曼树中读取霍夫曼代码：我使用叶节点来读取霍夫曼符号。读取的方法是从叶子节点开始，然后跟随叶子节点记录的父节点。访问其父节点。在父节点中记录为左子

6、树，将符号 0 入栈。否则为 1。这一直持续到访问根节点为止。此时，通过对之前读取的符号进行反向打印，就可以得到这个叶子节点的霍夫曼码。在前面的读取代码元素中，我使用了一个栈来存储读取的0和1。这样栈的输出就是叶子节点的霍夫代码。编程代码实现及详解主文件#include #include#include#include#include使用命名空间标准；bool find_record(char cha);/查找存储的字符void recording(char ch);/插入一个新字符void specific_recording(char ch);/判断该字符是否出现在携带不同字符的链表中。v

7、oid statistics(void);/字符频率统计的入口函数。void Initialization_of_head(void);/初始化一个链表头节点，用于后面的字符输入，并给它空间。int enter_huffman_values(int n);/霍夫曼树的叶子节点的输入void creat_huffman_tree(int number,int n);/创建霍夫曼树void go_further_read(struct huffman_number_node *pointer);/从树中读取对应字符的Huff码void reading_code();/打印对应字符的哈夫码void

8、read_huffman_code(void);/读取对应字符的Huff编码的入口函数void read_file(void);/从文件中读取字符void view(void);/用于从文件或键盘读取字符。结构信息节点字符 ch;整数频率；结构信息节点*下一个； *head0;/这是用于构造统计字符链表的节点类型的结构体。其中ch用于记录对应的字符。频率用来记录字符出现的频率，最后用来形成霍夫曼树叶节点的权重。结构 huffman_number_node字符 ch;整数数据；诠释父母；int left_child;int right_child; *头;/用于构建霍夫曼树节点的类型。 ch 是

9、一个字符。数据用于记录权重。 parent用于记录/记录节点的位置。如果它没有父节点，它的值为-1，left_child记录它的左子节点的位置。如果没有左子树，则记录为0。ritht_child用于记录右子节点的位置。如果没有右孩子则记为0。结构栈数据int one_zeros;结构栈结构 stack_data *base;结构堆栈数据*顶部； stack_operate;/创建一个栈来存放霍夫曼代码诠释主要（无效）Initialization_of_head();/初始化携带不同字符及其频率的链表头节点。看法（）;int n=head0-frequency;/将统计完成后携带字符的链表中的字

10、符总数赋值为整数/数n，用于参数传递完成后面函数的功能.enter_huffman_values(n);/这个函数的主要功能是创建要构造的树的所有节点空间/给叶子节点赋值。creat_huffman_tree(n,n);/根据上述函数完成的叶子节点的输入创建一棵霍夫曼树。coutendl;coutendl;read_huffman_code();/打印霍夫曼代码coutendl;系统（“暂停”）；返回0；无效视图（无效）cout* * *endl;cout 1.从文件中读取字符endl;cout 2. 从键盘读取字符endl;cout请选择相应的选项。select_number;开关（选择号码

11、）案例 1:read_file();system(cls);break;案例 2：statistics();system(cls);break;默认值：退出（0）；void read_huffman_code(void)/打印霍夫曼代码cout 在下面显示霍夫曼代码endlendl;struct huffman_number_node *pointer1=head;/使用指针访问霍夫曼树。for(int i=0;i频率;i+)/在这个循环中访问存储空间中的第一个head0-frequency叶子节点。并输出每个叶子节点的信息ch 数据项和霍夫曼代码。if(pointer1-ch!= &poin

12、ter1-ch!=n)/因为字符中可能出现空格和换行符，所以为了显示它们的ch数据项而对其进行了特殊处理。coutchch= )/如果是空格字符，用(a bland space)替换显示cout(一个平淡无奇的空格)=;别的cout(line feed)=;/如果是换行符，用(line feed)代替displaygo_further_read(pointer1);/输入读取相位字符的霍夫曼码。couttt;指针1+；if(i+1)%2=0) coutfrequency;/创建一个栈来存放对应的霍夫曼代码struct huffman_number_node *pointer1=pointer,

13、*pointer2;/辅助访问指针pointer1和pointer2stack_operate.top=stack_operate.base;/初始化栈。而（指针1-父级！=-1）/因为在输入节点数据的时候，根节点的父项记录为-1，是用来判断是否访问根节点的循环条件pointer2=head+(pointer1-parent-1);/pointer2指向pointer1的父节点。if(pointer1-head+1)=pointer2-left_child)/判断pointer1是父节点的左孩子还是右孩子。stack_operate.top-one_zeros=0;/如果是左子节点，则入栈0s

14、tack_operate.top+;别的stack_operate.top-one_zeros=1;/如果是右子节点，则入栈1stack_operate.top+;指针1=指针2；reading_code();/进入读栈函数void reading_code()/使用栈读取方式读取该字符的霍夫曼码。结构堆栈数据*指针；for(;stack_operate.top-stack_operate.base0;stack_operate.top-)指针=stack_operate.top-1；coutone_zeros;int enter_huffman_values(int n)头=新结构 huff

15、man_number_node2*n-1;/由于霍夫曼树有n个叶子节点，所以霍夫曼树应该有2*n-1个节点。于是创建了 2*n-1 个空间来存储对应的节点数据，并将空间的地址赋予 head。结构 huffman_number_node *pointer=head;/创建一个与霍夫曼树节点相同类型的指针，将相应的数据输入到那个空间。struct information_node *pointer1=head0-next;/创建一个指针来访问统计字符的链表。for(int i=0;ich=pointer1-ch;/这个叶子节点读取一个字符数据项，该数据项带有统计字符链表的一个节点。指针-数据=指针

16、1-频率；/这个叶子节点继续读取携带统计字符列表的节点的字符计数统计项。指针-父=-1；/因为Huffman树还没有形成，所以叶子节点的父节点的位置记为-1。父节点的位置是指其父节点所在节点的存储空间位置，存储空间第一个节点的位置为1。指针-left_child=0；/用0表示，节点没有左子节点。如果有，就是其左子节点的存储空间位置。pointer-right_child=0;/同上，但这里是右子节点。指针+；指针1=指针1-下一个；for(int i=n;ich=#;指针-父=-1；指针-left_child=0；指针-right_child=0；指针+；返回 n;bool find_rec

17、ord(char cha)/查找存储的字符结构信息节点*指针；/创建与承载字符链表的节点相同类型的指针，用于访问该链表。如果（头0-频率=0）返回假；/如果链表中没有插入字符，则将没有该字符的记录返回给调用函数。别的指针=head0-下一个；/如果链表中有字符，使用指针访问搜索，并告诉指针从哪里开始搜索。for(int i=0;i频率;i+)/这里使用链表头的总字符数来确定要访问多少个节点。如果（指针-ch=cha）/判断访问节点是否有要查找的字符。对调用函数回答是。pointer-frequency+=1;/因为有这个字符，所以给这个字符的编号记录项加1。返回真；指针=指针-下一个；retu

18、rn false;/如果还是没有找到，就返回no给调用函数。void recording(char ch)/插入一个新字符结构信息节点*指针=头0；/创建一个与携带统计字符的链表头节点同类型的指针，指向该头节点。而（指针-下一个！=NULL）/循环查找携带统计字符的链表的结束节点。用于插入新节点来存储新节点。指针=指针-下一个；头0-频率+=1；/因为，插入是在携带统计字符的链表中插入一个新节点，即如果有新字符，则对其表节点的字符统计加1。pointer-next=new struct information_node;/创建一个新节点来记录新字符。指针-下一个-ch=ch;pointer-n

19、ext-frequency=1;/同时记录这个字符的个数有一个。pointer-next-next=NULL;/将表尾节点的指针字段赋值为NULL，供以后判断。void specific_recording(char ch)/判断该字符是否出现在携带不同字符的链表中。if(find_record(ch)=true);/如果携带该字符的链表中有该字符，则不记录。返回调用函数。别的录音（ch）；/如果携带该字符的链表中没有该字符，则在该链表中插入一个节点来记录该字符。void statistics()/字符频率统计的入口函数。字符 ch;cout如果要计算字母个数的统计数据，请输入字母然后输入#

20、end enter endl;while(ch=cin.get()!=#)/中断从输入流中获取字符，直到遇到字符#。specific_recording(ch);/深入统计。void read_file()/从文件中读取字符。ifstream infile(data.txt,ios:in);如果（！infile）coutch=#;head0-frequency=0;/这个用来记录链表中的字符总数，链表加一个字符，它就加1。头0-下一个=空；void creat_huffman_tree(int number,int n)/构造哈夫曼树。if(number2*n-1)/判断进入数据树的节点是否小

21、于2*n-1诠释米；struct huffman_number_node *pointer=head,*pointer1,*pointer2;/创建的指针用于访问树节点存储空间。 Pointer1、pointer2分别用于指向该节点的数据数据项在存储空间中的最小和后两个节点，这两个节点的父数据项没有父节点记录。data 是记录字符的权重，即统计部分统计的输入字符集中对应字符出现的频率。int min=0,sec=0,最大值；/定义min表示pointer1所指向的节点在存储空间中的位置。初始为0。sec的定义用来表示pointer2所指向的节点在存储空间中的位置。最初为 0。声明 maximu

22、mun，这是为此目的而存储的 min 和 sec 的最大值。while(min=0|sec=0)&(指针头)数字)/这个循环是寻找前两个没有父节点记录的节点，分别用pointer1和pointer2指向它们。其中，pointer1指向数据项最小的节点。在这个循环的条件下，min和sec都不为0。也就是说pointer1和pointer2都必须有指针，并且必须找到前两个节点。 (pointer-head)父=-1&min=0）/如果第一次找到满足条件的节点。第一个，用pointer1指向它，用min记录位置。min=指针头+1；指针1=指针；别的if(pointer-parent=-1&sec=

23、0)/找到满足条件的第二个节点。如果（指针1-数据指针-数据）/如果这个节点的数据数据项小于第一个节点的数据数据项，用pointer1指向这个数据项，用pointer2指向第一个。秒=分钟；指针2=指针1；指针1=指针；min=指针头+1；else/否则，用指针指向这个节点，用sec记录这个节点的位置。sec=指针头+1；指针2=指针；指针+；如果（秒分钟）最大值=秒；别的最大值=最小值；for(int i=0;iparent=-1&(pointer-datadata)/如果访问节点没有父节点记录，则该节点的数据数据小于pointer2所指向的节点的数据数据项。使用pointer1 和poin

24、ter2 之一指向它。如果它的数据data小于pointer1的数据项，用pointer1指向它，pointer2指向之前pointer1指向的节点。否则，使用pointer2 指向它。同时，min 和 sec 也应该相应地改变记录。如果（指针-数据数据）秒=分钟；指针2=指针1；指针1=指针；最小=米；别的指针2=指针；秒=米；指针+；指针-数据=指针1-数据+指针2-数据；/这里的指针在搜索区域之外，它指向的节点就是要输入数据的节点，所以数据就输入到这个节点中。它的数据项是pointer1和pointer2的数据项之和，是Huffman树覆盖的方法。因为霍夫曼桑树中的树是从叶子节点开始的。

25、每次从没有父节点的节点中选出权重最小的两个节点，用它们的权重之和来构造一个新节点的权重，这两个节点要记录它们的父节点。就是那个新节点。重复上述操作，直到构建出最终的树。指针-left_child=min；/表示树的新节点的左孩子所在的位置。这指向 Tigon 中数据项最小的节点。指针-right_child=sec；/表示树的新节点的右孩子所在的位置。这是指向 Tigon 数据项的下一个节点。pointer1-parent=number+1;/既然记录了pointer1所指向的节点的父节点，就记录下来。pointer2-parent=number+1;/由于pointer2所指向的节点的父节点

26、是，记为。creat_huffman_tree(数字+1,n);/如果还有两个或更多的节点没有父节点记录，这意味着树必须继续构建。所以它被递归调用。进入下一个功能判断。这里的number+1表示2*n-1中的节点有number+1个节点输入数据。只要 number1 小于 2*n-1，就意味着有两个或多个没有父节点记录的节点。程序执行程序执行的第一个界面：有两个选项，现在选择 1 将 Huffman 对文件中的字符进行编码。在结果界面中，每个字符都与它的哈夫曼码行等号相连，表示其对应的哈夫曼码。在这里，文件中的空格和换行符也算在内，这是我的想法。我认为可以使信息在传输中可以完全保留信息开头的风

27、格。但我也意识到它也给会议带来了过剩的信息。 （如下）：在程序执行的第一个界面中选择第二个选项。所以输入用户自己输入的字符，然后统计，然后输出霍夫曼编码。程序执行结果界面如下：字符输入界面，字符输入后，以字符“#”结尾。跟随结果界面时间复杂度分析在这个程序中，影响程序执行时间的基本操作是赋值操作。由字符统计部分中的输入大小决定。时间复杂度分析主要从三个部分的功能进行。分别是统计部分的功能，哈夫曼树部分的构建功能，哈夫曼码读取功能。这里，如果输入字符数为N，则不同字符的总数为n。统计部分的时间复杂度分析和这部分要分析的函数有以下几个函数。bool find_record(char cha)/查找存储的字符void recording(char ch)