数据结构 哈夫曼编码与译码.doc

数 据 结 构课程设计说明书题 目哈夫曼编码与译码学 号1267159206姓 名张燕斌指导教师康懿日 期2014.01.02任务书课程名称数据结构课程设计设计题目Huffman编码和译码指导教师康懿时间2013年秋学期第15周至第19周一、教学要求1. 掌握数据结构与算法的设计方法，具备初步的独立分析和设计能力2. 初步掌握软件开发过程的问题分析、系统设计、程序编码、测试等基本方法和技能3. 提高综合运用所学的理论知识和方法独立分析和解决问题的能力4. 训练用系统的观点和软件开发一般规范进行软件开发，培养软件工作者所应具备的科学的工作方法和作风二、设计资料及参数每个学生在教师提供的课程设计题目中任意选择一题，独立完成，题目选定后不可更换。Huffman编码和译码根据给定的字符集和各字符的频率值，求出其中给定字符Huffman编码，并针对一段文本（定义在该字符集上）进行编码和译码，实现一个Huffman编码/译码系统。要求设计类（或类模板）来描述Huffman树及其操作，包含必要的构造函数和析构函数，以及其他能够完成如下功能的成员函数：v 求Huffman编码v 输入字符串，求出编码v 输入一段编码，实现译码 并设计主函数测试该类。三、设计要求及成果1. 分析课程设计题目的要求2. 写出详细设计说明3. 编写程序代码，调试程序使其能正确运行4. 设计完成的软件要便于操作和使用5. 设计完成后提交课程设计报告四、进度安排资料查阅与讨论（1天）系统分析（2天）系统的开发与测试（5天）编写课程设计说明书和验收（2天）五、评分标准1. 根据平时上机考勤、表现和进度，教师将每天点名和检查2. 根据课程设计完成情况，必须有可运行的软件。3. 根据课程设计报告的质量，如有雷同，则所有雷同的所有人均判为不及格。4. 根据答辩的情况，应能够以清晰的思路和准确、简练的语言叙述自己的设计和回答教师的提问六、建议参考资料1数据结构 （C语言版）严蔚敏、吴伟民 主编 清华大学出版社 2004.112数据结构课程设计案例精编（用C/C+描述），李建学 等 编著，清华大学出版社 2007.23.数据结构:用面向对象方法与C+语言描述，殷人昆 主编，清华大学出版社 2007目录第一章 需求分析4第二章 总体设计5第三章 抽象数据类型定义63.1 LinkList抽象数据类型的设计63.2 HuffmanTree抽象数据的设计6第四章 详细设计.7第五章 测试8第六章 总结9附录：程序代码10第一章 需求分析哈夫曼编码是一种编码方式，以哈夫曼树即最优二叉树，带权路径长度最小的二叉树，经常应用于数据压缩。哈弗曼编码使用一张特殊的编码表将源字符（例如某文件中的一个符号）进行编码。这张编码表的特殊之处在于，它是根据每一个源字符出现的估算概率而建立起来的（出现概率高的字符使用较短的编码，反之出现概率低的则使用较长的编码，这便使编码之后的字符串的平均期望长度降低，从而达到无损压缩数据的目的）。赫夫曼编码的应用很广泛，利用赫夫曼树求得的用于通信的二进制编码称为赫夫曼编码。树中从根到每个叶子都有一条路径，对路径上的各分支约定：指向左子树的分支表示“0”码，指向右子树的分支表示“1”码，取每条路径上的“0”或“1”的序列作为和各个叶子对应的字符的编码，这就是赫夫曼编码。哈弗曼译码输入字符串可以把它编译成二进制代码，输入二进制代码时可以编译成字符串。第二章 总体设计（1） 输入一个字符串用结构体链表存储字符串中出现的不同字符及其出现的次数。（2） 定义赫夫曼数的结点结构体，把不同的字符及其在字符串中出现的次数作为叶子结点的元素及其权值，统计叶子结点的个数n，开辟可以存储2*n个结点的顺序表，来赫夫曼树的各个结点，然后按照一定的规则构造赫夫曼树。（3） 开辟一个可以存储叶子结点元素及指向存储其赫夫曼编码链表的指针的顺序表，然后从叶子结点开始向上访问，是左孩子的把“0”接进链表是右孩子的把“1”接进链表，直到根结点，然后把叶子结点的元素及存储其赫夫曼链表的头指针读入顺序表，直到把所有的叶子结点的元素及指向存储其赫夫曼编码链表的头指针读入顺序表，这样得到的赫夫曼编码是倒序的。（4） 从存储其叶子结点及指向存储其赫夫曼编码链表头指针的顺序表表头开始顺序访问各元素，在输出其赫夫曼编码之前，把链表中的编码顺序读入到等长的栈中，然后编码出栈就会得到顺序的赫夫曼编码，直到把所有的叶子结点都访问到。（5） 用一个字符型的指针指向字符串的第一个字符，从存储叶子结点元素及指向存储其赫夫曼编码链表的头指针的顺序表表头开始访问顺序表中的各元素，直到找到叶子结点的元素和当前字符相等就结束访输出赫夫曼编码，直到输出字符串的最后一个字符的赫夫曼编码，这样就得到输入字符串的赫夫曼编码。第三章 抽象数据类型定义3.1 LinkList抽象数据类型的设计ADT LinkList数据对象：D = ai | aiElemSet,i = 1,2,n,n0 数据关系：R1= | ai-1,aiD,i = 2,n 基本操作：ListEmpty( L )初始条件：线性表L已存在。操作结果：若L表为空表，则返回TRUE，否则返回FALSE。ListLength( L )初始条件：线性表L已存在。操作结果：返回L中数据元素个数。GetElem( L , i , &e )初始条件：线性表L已存在。1iListLength( L )。操作结果：用e返回L中第i个数据元素的值。ListTraverse( L , visit( ) )初始条件：线性表L已存在。操作结果：依次对L的每个数据元素调用函数visit( )。一旦visit（）失败，则操作失败。ADT LinkList3.2 HuffmanTree抽象数据的设计 typedef struct /赫夫曼树的结构体char ch;int weight; /权值int parent,lchild,rchild;htnode,*hfmtree;第四章 详细设计开始结点数是否大于1将data和权值赋给ht输出根结点和权值调用SELECT函数计算根结点函数父结点为两子结点之和输出两子结点和已构造的结点是否为根结点？左子是否为空？此时编码为0I2*N?I+编码为1结束否否否右子是否为空是是否否是是是第五章 测试图表 1 5.1图5.1为 哈夫曼编码与译码。第六章 总结通过本次实验首先学习了霍夫曼树及其编码，接着分析写出了建立霍夫曼树和计算霍夫曼编码算法的代码，在huffman编码当中虽出现许多错误但通过了进一步的学习都可以学习改正,基本上可以实现Huffman编码算法的实现与编程应用。两个星期的不懈努力，哈夫曼编译码系统课程设计顺利结束了，在这个过程中我收获了不少，同时也了解自己在某些方面做的还不够。在此，感谢两星期来一直指导我们的班主任和那些为我解决设计过程中遇到的难题的同学们，谢谢大家！今后我将继续努力，争取编出一套完整的哈夫曼编译码系统。 附录：程序代码#include #include /系统自带的字符串库函数#include using namespace std;struct Node char data; / 节点数据域为字符型 Node *next; Node() next = NULL; Node(char item, Node *link = NULL) data = item; next = link;class LinkList/仅保留几个用得到的成员函数protected: Node *head; Node *curPtr; int count,curPosition; Node *GetElemPtr(int position); / 返回指向第position个结点的指针public: LinkList(); int Length() const; bool Empty() const; void Traverse() ; void Insert(int position, const char &e); char GetElem(int position) ;Node * LinkList:GetElemPtr(int position) if (curPosition position) curPosition = 0; curPtr = head; for (; curPosition next; return curPtr;char LinkList:GetElem(int position) Node *tmpPtr; tmpPtr = GetElemPtr(position); char e = tmpPtr-data; return e;LinkList:LinkList() head = new Node; / 构造头指针，带表头结点的链表 curPtr = head; curPosition =0; count = 0;int LinkList:Length() const return count;bool LinkList:Empty() const return head-next = NULL;void LinkList:Traverse() for (Node *tmpPtr = head-next; tmpPtr != NULL; tmpPtr = tmpPtr-next) coutdata); void LinkList:Insert(int position, const char &e) Node *tmpPtr; tmpPtr = GetElemPtr(position - 1); Node *newPtr; newPtr = new Node(e, tmpPtr-next); tmpPtr-next = newPtr; curPosition = position; curPtr = newPtr; count+;/ 哈夫曼树结点类struct HuffmanTreeNode int weight; unsigned int parent, leftChild, rightChild; / 双亲,左右孩子域 HuffmanTreeNode(); HuffmanTreeNode(int w, int p = 0, int lChild = 0, int rChild = 0);HuffmanTreeNode:HuffmanTreeNode() parent = leftChild = rightChild = 0;HuffmanTreeNode:HuffmanTreeNode(int w, int p, int lChild, int rChild) / 右孩子 weight = w; / 权 parent = p; / 双亲 leftChild = lChild; / 左孩子 rightChild = rChild; / 右孩子class HuffmanTreeprotected:/ HuffmanTreeNode *nodes; / 存储结点信息,nodes0未用 char *LeafChars; / 叶结点字符信息,LeafChars0未用 string *LeafCharCodes; / 叶结点字符编码信息,LeafCharCodes0未用 int curPos; / 译码时从根结点到叶结点路径的当前结点 int num; / 叶结点个数/ 辅助函数: void Select(int cur, int &r1, int &r2); / nodes1 cur中选择双亲为0,权值最小的两个结点r1,r2 void CreatHuffmanTree(char ch, int w, int n); public: HuffmanTree(char ch, int w, int n); / 由字符,权值和字符个数构造哈夫曼树 virtual HuffmanTree(); / 析构函数 string Encode(char ch); / 编码 LinkList Decode(string strCode); / 译码;void HuffmanTree:Select(int cur, int &r1, int &r2) r1 = r2 = 0; / 0表示空结点 for (int pos = 1; pos = cur; pos+) if (nodespos.parent != 0) continue; / 只处理双亲为0的结点 if (r1 = 0) r1 = pos; else if (r2 = 0) r2 = pos; else if (nodespos.weight nodesr1.weight) r1 = pos; else if (nodespos.weight nodesr2.weight) r2 = pos; void HuffmanTree:CreatHuffmanTree(char ch, int w, int n) num = n; / 叶结点个数 int m = 2 * n - 1; / 结点个数 nodes = new HuffmanTreeNodem + 1; / nodes0未用 LeafChars = new charn + 1; / LeafChars0未用 LeafCharCodes = new stringn + 1; / LeafCharCodes0未用 int pos; / 临时变量 for (pos = 1; pos = n; pos+) / 存储叶结点信息 nodespos.weight = wpos - 1; / 权值 LeafCharspos = chpos - 1; / 字符 for (pos = n + 1; pos = m; pos+) / 建立哈夫曼树 int r1, r2; Select(pos - 1, r1, r2); nodesr1.parent = nodesr2.parent = pos; / r1,r2双亲为pos nodespos.leftChild = r1; / r1为pos的左孩子 nodespos.rightChild = r2; / r2为pos的右孩子 nodespos.weight = nodesr1.weight + nodesr2.weight;/pos的权为r1,r2的权值之和 for (pos = 1; pos = n; pos+) / 求n个叶结点字符的编码 LinkList charCode; / 暂存叶结点字符编码信息 for (unsigned int child = pos, parent = nodeschild.parent; parent != 0; child = parent, parent = nodeschild.parent) if (nodesparent.leftChild = child) charCode.Insert(1,0); else charCode.Insert(1,1); for(int i=1;i=charCode.Length();i+) LeafCharCodespos.append(1, charCode.GetElem(i);/没有直接可以从链表为字符串赋值的函数，只能一个字符一个字符的追加过去 curPos = m;HuffmanTree:HuffmanTree(char ch,int w, int n) CreatHuffmanTree(ch, w, n);HuffmanTree:HuffmanTree() if (nodes != NULL) delete nodes; / 释放结点信息 if (LeafChars != NULL) delete LeafChars; / 释放叶结点字符信息 if (LeafCharCodes != NULL) delete LeafCharCodes; / 释放叶结点字符编码信息string HuffmanTree:Encode(char ch) for (int pos = 1; pos = num; pos+) if (LeafCharspos = ch) return LeafCharCodespos;/ 找到字符,得到编码 LinkList HuffmanTree:Decode(string strCode)/ 操作结果：对编码串strCode进行译码,返回编码前的字符序列 LinkList charList; / 编码前的字符序列 for (int pos = 0; pos strCode.length(); pos+) / 处理每位编码 if (strCodepos = 0) curPos = nodescurPos.leftChild; / 0表示左分支 else curPos = nodescurPos.rightChild; / 1表示左分支 if (nodescurPos.leftChild =