课程设计样板选编.doc

数据结构 课 程 设 计 题 目 基于Huffman算法的编码与译码技术的探究 系 (部) 电子与信息工程系 班 级 08级计算机科学与技术 姓 名 张 苗 学 号 0828014006 指导教师 王 静 2010年01月07日电子与信息工程系 课程设计任务书 设计题目 已知技术参数和设计要求 设计内容与步骤 设计工作计划与进度安排 设计考核要求 计算机教研室制 注意：本设计模板字体，均小了一号，正确的应该是 论文分三级标题： 一级标题：左对齐顶格，左对齐顶格， 三级标题：左起齐顶格，Times New Roman 12号）； 参考文献宋体五号。 基于Huffman算法的编码与译码技术的探究 张 苗 安康学院 计算机科学与技术08级 陕西省 安康市 725000 摘要：本文采用了哈弗曼算法，通过对编码与译码技术的探究，利用C语言实现了从文件中读取数据，并进行编码和译码的功能，同时克服了C语言下数组长度的有限性。经实验验证，效果良好。 关键字：哈夫曼树；哈夫曼编码；数据的带权路径长度；译码 引言 数据编码技术在计算机数字通信中一直占据着重要的地位。而在数据通信过程中往往存在很多问题：每次对数据编码量有限，传递的数据编码的长度和数据译码容易产生二义性等。以上问题使得数据编码技术的优劣在很大程度上影响着通信质量。 在信息编码领域中，哈弗曼树即最优二叉树的应用十分广泛，其权值被赋为某个符号出现的频率，利用哈夫曼树对每个数据进行不等长编码，频率越高的数据其编码越短，使得数据带权路径长度WPL最小，这样就保证了整个电文的编码长度达到最短。“哈夫曼编码是一种一致性编码路径和路径长度 在一棵树中，从一个结点往下可以达到的孩子或子孙结点之间的通路，称为路径。通路中分支的数目称为路径长度。若规定根结点的层数为1，则从根结点到第L层结点的路径长度为L-1。 结点的权及带权路径长度 若将树中结点赋给一个有着某种含义的数值，则这个数值称为该结点的权。结点的带权路径长度为：从根结点到该结点之间的路径长度与该结点的权的乘积。 树的带权路径长度 树的带权路径长度规定为所有叶子结点的带权路径长度之和，记为WPL哈夫曼编码(Huffman Coding)是一种编码方式，哈夫曼编码是可变字长编码(VLC)的一种有时称之为最佳编码，一般就叫作Huffman编码。 createht(struct htnode ht[],int n)函数实现。 3.2 哈弗曼编码算法 3.2.1 对每个叶结点进行编码 根据所建的哈夫曼树，则需要编码的字符集合即叶子结点，利用回溯法，对于每个叶结点，都是从叶结点出发，向上回溯至根结点为止。上溯时走左分支则生成代码0，走右分支则生成代码1.由于生成的编码与要求的编码反序，将生成的第i个字符的代码，从后往前依次存放在一个数组hcd[i].cd[n]中，指针start指示编码在数组中的位置（start初始时指示数组的结束位置，编码结束后start指向哈弗曼编码最开始字符）。由于叶子结点总数为n，则不等长编码的长度不会超过n，故在每一叶结点的编码末加一标识符“#”，以便于对字符数据进行译码。 该功能由createhcode(struct htnode ht[],struct hcode hcd[],int n)函数实现。 3.2.2 对文件中所有字符数据进行编码 （1）从文件1（源文件）中读取一定长度的字符放在数组S2[]中。 （2）将S2[]中的字符依次和3.1.2所建哈弗曼树中的叶结点进行比较，若相同，则将相同字符的相应编码写入数组str[]中，直到S2[]中所有字符均被编码，并将其编码写入文件2（编码文件）中。 （3）重复（1）和（2），直到文件1（源文件）中所有字符均被编码并写入文件2（编码文件）。 该功能由函数encode(struct htnode ht[],struct hcode hcd[],char s2[],char str[])实行。 3.3哈弗曼译码算法 （1）从文件2（编码文件）中读取一定长度的字符编码。 （2）将读取的字符编码逐个与3.2.1中叶子结点的编码进行比较，找到与其相同的编码的叶子结点，将这些叶子结点的字符写入文件3（译码文件）。 （3）重复（1）和（2），直到文件2中的所