发布时间 : 星期日 文章数据结构实习报告更新完毕开始阅读
中国地质大学（武汉）
数据结构实习报告
姓 名： 班 级： 指导教师： 杨勇
1 题目要求....................................................................................................................................... 3
1.1 自适应哈夫曼编解码 ........................................................................................................ 3 1.2 嵌入式系统的内存管理 .................................................................................................... 3 1.3 （平衡搜索二叉树）AVL树 ............................................................................................. 3 2 报告内容....................................................................................................................................... 3
2.1 自适应哈夫曼编解码 ........................................................................................................ 3
2.1.1 算法原理 ................................................................................................................. 3 2.1.2 程序流程图 ............................................................................................................. 9 2.1.3 数据结构图 ........................................................................................................... 12 2.1.4 程序代码 ............................................................................................................... 12 2.2 嵌入式系统的内存管理 .................................................................................................. 26
2.2.1 算法原理与数据结构 ........................................................................................... 26 2.2.2 算法总结 ............................................................................................................... 29 2.3 （平衡搜索二叉树）AVL树 ........................................................................................... 29
2.3.1 插入....................................................................................................................... 29 2.3.2 查找....................................................................................................................... 32 2.3.3 删除....................................................................................................................... 33 2.3.4 遍历....................................................................................................................... 36 2.3.5 高度....................................................................................................................... 37 2.3.6 核心数据类型 ....................................................................................................... 38 2.3.7 数据结构 ............................................................................................................... 39
3 实习总结..................................................................................................................................... 39
2
1 题目要求
1.1 自适应哈夫曼编解码
（1）阅读文献，理解算法。（2）编程实现压缩解压缩算法，对英文文本进行压缩解压缩。（3）撰写报告。报告内容包括压缩解压缩算法原理、程序流程图、核心数据类型及核心数据结构（图示）、程序代码（详细的注释）。
1.2 嵌入式系统的内存管理
（1）阅读文献，理解内存管理算法。（2）阅读代码（某开源代码），理解内存管理的具体实现。（3）撰写报告。报告内容包括开源代码所使用的内存管理算法原理、开源代码中的核心数据类型及核心数据结构（图示）。
1.3 （平衡搜索二叉树）AVL树
（1）阅读文献，理解AVL树这种数据结构的基本操作。（2）编程实现基本操作（AVL树的插入，查找，删除，遍历，高度）。（3）撰写报告。报告内容包括基本操作的实现原理、程序流程图、核心数据类型及核心数据结构（图示）、程序代码（详细的注释）。
2 报告内容
2.1 自适应哈夫曼编解码 2.1.1 算法原理
使用基于静态 Huffman 编码树的算法对输入的符号流进行编码， 必须进行两遍扫描。 第一遍扫描统计被编码对象中符号出现的几率，并创建 Huffman 编码树， 第二遍扫描按照 Huffman 编码树对输入符号进行编码。并且，在储存或传输 Huffman 编码结果之前， 还必须先储存或传输 Huffman 编码树。这些问题使静态 Huffman 编码树并不实用，尤其是对于短小的符号流来说，加上 Huffman 编码树的编码结果在尺寸上很可能更大， 甚至大出很多。为了解决这些问题，自适应 Huffman 编码顺应而生。 严格的说，自适应 Huffman 编码不仅涉及到编码树的构造问题， 还与编码、 解码过程相关。 由于其实用性大大提高， 因而应用领域也非常广泛。这看似复杂的自适应 Huffman 编码方案背后的概念却十分简单， 如下所示： 初始化编码树； 对每一个输入符号
3
{
对符号编码； 更新编码树； }
解码算法与编码算法类似， 当编码方和解码方都使用相同的初始化状态，以及相同的更新编码树策略时， 在编码方输入的符号将正确的在解码方还原。现在，问题变为如何更新编码树。 为了让压缩编码过程具有自适应性， 我们应该在每次处理完一个符号时调整该符号的权重值（ 加一），并重新建立Huffman编码树。但是很明显，这样的算法将有极差的效率。 为了增加算法的效率， 在实际的自适应 Huffman 编码算法中使用了一个技巧： 每次只更新受影响的那一部分编码树结构。
初始化编码树时， 由于只允许对待编码数据流进行单遍扫描， 因此不可能预先知道各种符号的出现频率。 为了对所有符号一致对待， 编码树的初始状态只包含一个叶节点， 包含符号NYT（ Not Yet Transmitted，尚未传送），权重值为 0。 NYT是一个逸出码（escapecode），不同于任何一个将要传送的符号。 当有一个尚未包含在编码树中的符号需要被编码时，系统就输出 NYT 编码， 然后跟着符号的原始表达。当解码器解出一个 NYT 之后，它就知道下面的内容暂时不再是 Huffman 编码，而是一个从未在编码数据流中出现过的原始符号。 这样，任何符号都可以在增加到编码树之前进行传送， 虽然这样做不仅没有对数据进行压缩，反而使其更加冗长，但至少是一种对不存在于编码树之中的符号进行编码的手段。
包含 NYT 符号的节点还有另外一个作用， 就是作为新符号的插入点。在需要插入一个新符号时，总是先构造一个新的子树，子树包含NYT符号与新符号两个叶节点，然后将旧的 NYT 节点由这个子树替代。由于包含 NYT 符号的节点权重值为 0，而包含新符号的叶节点的权重值为 1，因此最终效果相当于原 NYT 节点位置的权重值由 0 变为 1。因此， 下一步将试图对其父节点执行权重值“ 加一操作”。
对符号编码的过程与第一节中给出的方法完全一致。每次符号编码完成之后，也将试图对包含符号的节点执行权重值“ 加一操作”。
将一个新的符号插入编码树或者输出某一个已编码符号后，相应的符号的出现次数增加了 1，继而编码树中各种符号的出现频率发生了改变。 此时，原有的 Huffman 编码树已经不一定符合具有最小加权路径长度这一条件， 因此必须进行调整， 以使其继续满足这一条件， 保持其合法 Huffman 编码树的状态。这一操作，在本文中称为“ 加一操作”。
在说明“ 加一操作” 的调整方法之前，我们必须给每个节点引入两个新的属性：节点编号（ node number） 和所属块（ block）。其中节点编号是一个全局唯一的值，不同的节点拥有不同的节点编号，而块指具有相同权重的一组节点。 节点编号具有一些特点： (1) 权重值较大的节点，节点编号也较大；
(2) 父节点的节点编号总是大于子节点的节点编号。
以上两点称为兄弟属性（ sibling property）。在每一次调整节点权重值时，都需要相应的调整节点编号，以避免兄弟属性被破坏。 在对某一个节点权重值进行“ 加一操作” 时，应该首先检查该节点是否具有所在的块中的最大节点编号， 如果不是，则应该将该节点与所在块中具有最大节点编号的节点交换位置。然后再对节点的权重值加一，这样， 由于该节点的节点编号已经处于原来所属块中的最大值， 因此权重值加一之后兄弟属性仍然得到满足。 最后， 由于节点的权重发生了变化， 必须递归地对节点的父节点进行“ 加一操作”。 如发送的字符为：abcddbb
4