复盘理解/实验报告梳理 数据结构PTA实验三

2023-12-17 13:39:05

一、哈夫曼编码

????????首先看输入,输入首先给了结点数,结点数个结点名和结点权值,之后是下面要检测的哈夫曼编码组数,然后是每组哈夫曼编码。

????????我们先处理初始给到的结点权值,存入到一个含有val和weight的结构体数组中。

????????之后去思考这道题具体的内容要求,即检测哈夫曼编码正确与否,这里要去思考哈夫曼编码有什么特别之处,发现,其如果正确,势必要满足条件有:该编码为前缀编码;来自于哈夫曼树,符合权值的大小。根据这两个条件,发现,前缀编码只需要比对每个给到的编码前几位是否相同,例如,01和011就不符合这个条件。后面要满足哈夫曼树的特点,根据思考,可以找到,哈夫曼树特有的WPL带权路径长度之和,哈夫曼编码一定是满足哈夫曼树的,也就是说,无论编码是什么,其计算出的WPL有且只有一个值。

????????下面使用构建哈夫曼树的函数,先用题目给的权值,构建一颗哈夫曼树,方便下面求权值。用静态链表的哈夫曼树的构建代码中,首先初始化了所有的结点,将所有结点的父节点,孩子结点们全部置为0,下标代表地址,之后根据哈夫曼树构建原理,先找出两个小的权值的结点(small1和small2用于比较找到小权值,p1和p2用于记录小权值结点的下标,不同的是p1中存的将是最新找到的结点,每次p1更新的同时,会将上一个最小权值结点存到p2中,假如新找到的结点的权重大于p1小于p2,那么就单单更新p2的内容),加和得到他们的父结点,存入静态链表中所有带权结点下面空的位置上,并将其孩子结点们的内容置为上面两个小权值的结点的下标。将孩子节点的父节点置为其的下标,经过循环,就可以成功创造出哈夫曼树。

????????求WPL权值。老师上课曾提出:哈夫曼树上非叶子结点的结点的权值相加等于带权路径长度。所以下面通过这个方式,快速求得了权值(当然,我们仍然可以用传统方法:“每个叶子的权值 * 所在层数”求和,这个方法可以和求哈夫曼树编码一起使用,那个算法就是倒序存哈夫曼编码,同时计算每次向上寻找根节点的权值求和)。

????????之后我们就可以找到权值和输入进来的“哈夫曼编码”比对,这里根据经验我们不难发现,编码长度就是一个结点的深度(或是说从根到这个结点的层数),这样我们就可以求出每组编码的“权值”,然后和上面求得的正确权值比对,如果错误,就直接不满足,break打印no便可,如果满足,就去下面继续检测前缀码内容是否满足,检测前缀码,就是一个个检测是否有重复(前文已经说过了),通过这两个,如果全部问题都没有,就可以打印yes了。

????????最后检测一下代码能否成功运行,会发现,有的时候回车会被错误的输入进去,经过debug,在合适的位置插入getchar()吸收回车,最后也成功解决这个疑难杂症。


二、线索二叉树的建立和遍历

? ? ? ? (这里不太会了,ai生成了一部分解释)

????????明确输出,先序序列,没有元素的内容用@符号代替,所以可轻而易举的使用先序输入递归构建一棵树,之后就是想办法去将其线索化。

????????中序线索化,先设置一个指针去寻找前驱,用左中右的顺序去遍历,根据线索化的定义,设置了左右tag去标记是否有左右孩子,没有就会置为1,之后,检查前驱节点pre是否存在。如果存在,它会根据pre的rtag和ltag的值,更新pre的lchild和rchild指针。最后,将当前节点设置为前驱节点,并递归地对右子树进行中序线索树的创建。

????????最后,对线索中序的遍历输出。最左节点为中序遍历的首结点。函数首先将指针p指向根节点root。然后,通过一个while循环,不断向左子树移动,直到找到一个ltag为1的节点。接下来,进入另一个while循环,不断地向右子树移动,直到找到一个rtag为1的节点或者没有右子树为止。在每次移动的过程中,如果找到了rtag为1的节点,就将指针p指向该节点;否则,继续向左子树移动,直到找到一个ltag为1的节点。每次循环完输出结点的内容,左右tag。


文章来源:https://blog.csdn.net/FellAveal/article/details/135043309
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。