xx数据结构实验报告
北邮数据结构实验报告北京邮电大学信息与通信工程学院20XX级数据结构实验报告实验名称： 实验三哈夫曼编/解码器的实现学生姓名：陈聪捷日期：20XX年11月28日1. 实验要求一、实验目的：了解哈夫曼树的思想和相关概念 ；二、实验内容：利用二叉树结构实现哈夫曼编 /解码器1. 初始化：能够对输入的任意长度的字符串s进行统计,统计每个字符的频度，并建立哈夫曼树。2. 建立编码表：利用已经建好的哈夫曼树进行编码，并 将每个字符的编码输出。3. 编码：根据编码表对输入的字符串进行编码，并将编 码后的字符串输出。4. 译码：利用已经建好的哈夫曼树对编码后的字符串进 行译码，并输出译码结果。5. 打印：以直观的方式打印哈夫曼树。6. 计算输入的字符串编码前和编码后的长度，并进行分 析，讨论哈夫曼编码的压缩效果。7. 用户界面可以设计成“菜单”方式，能进行交互，根 据输入的字符串中每个字符出现的次数统计频度，对没有出 现的字符一律不用编码。2. 程序分析存储结构二叉树templateclass BiTree(public:BiTree ; /构造函数，其前序序列由键盘输入BiTree(void); /析构函数BiNode* Getroot ; /获得指向根结点的指针protected:BiNode *root; /指向根结点的头指针；/声明类BiTree 及定义结构 BiNodeData :二叉树是由一个根结点和两棵互不相交的左右子树构 成哈夫曼树类的数据域，继承节点类型为int的二叉树class HuffmanTree:public BiTreedata:HCode* HCodeTable;/ 编码表int tSize; / 编码表中的总字符数二叉树的节点结构templatestruct BiNode /二叉树的结点结构 T data; /记录数据T lchild; /左孩子T rchild; /右孩子T parent; /双亲;编码表的节点结构struct HCodechar data; /编码表中的字符char code; /该字符对应的编码;待编码字符串由键盘输入，输入时用链表存储，链表节点为 struct Nodechar character; / 输入的字符unsigned int count;/ 该字符的权值bool used; /建立树的时候该字符是否使用过Node* next; / 保存下一个节点的地址；示意图：关键算法分析1. 初始化函数(void HuffmanTree:Init(string Input)算法伪代码：1. 初始化链表的头结点2. 获得输入字符串的第一个字符，并将其插入到链表尾 部,n=1(n记录的是链表中字符的个数)3. 从字符串第2个字符开始，逐个取出字符串中的字符 将当前取出的字符与链表中已经存在的字符逐个比较，如果当前取出的字符与链表中已经存在的某个字符相同，则链表中该 字符的权值加1。如果当前取出的字符与链表中已经存在的字符都不相 同，则将其加入到链表尾部，同时 n+=n(tSize记录链表中字符总数，即哈夫曼树中叶子节点总数）5. 创建哈夫曼树6. 销毁链表源代码：void HuffmanTree:Init(string Input)(Node *front=new Node; /初始化链表的头结点if(!front)throw exception(" 堆空间用尽");front->next=NULL;front->character=NULL;front->count=0;Node *pfront=front;char ch=Input; / 获得第一个字符Node* New仁new Node;if(!New1)throw exception(" 堆空间用尽");New1->character=ch; /将第一个字符插入链表New1->count=1;New1->next=pfront->next;pfront->next=New1;bool replace=0; / 判断在已经写入链表的字符中是否有与当前读出的字符相同的字符int n=1; /统计链表中字符个数for(int i=1;i(ch=Input; / 获得第i个字符do(pfront=pfront->next;if(int)pfront->character = (int)ch) /如果在链表中有与当前字符相同的字符，该字符权值加1(pfront->count+;replace=1;break;while(pfront->next);if(!replace) /如果在链表中没找到与当前字符相同的字符，则将该字符作为新成员插入链表(Node* New=new Node;if(!New)throw exception(" 堆空间用尽");New->character=ch;New->count=1;New->next=pfront->next;pfront->next=New;n+;pfront=front; / 重置 pfront 和 replace 变H为默认 值 replace=0;tSize=n; /tSize记录的是编码表中字符个数CreateHTree(front,n); /创建哈夫曼树pfront=front;while(pfront) /销毁整个链表(front=pfront;pfront=pfront->next;front;时间复杂度：若输入的字符串长度为n,则时间复杂度为 O(n)2. 创 建 哈 夫 曼 树 (voidHuffmanTree:CreateCodeTable(Node *p)算法伪代码：1. 创建一个长度为 2*tSize-1的三叉链表2. 将存储字符及其权值的链表中的字符逐个写入三叉链表的前tSize个结点的data域，并将对应结点的孩子域和双亲域赋为空3. 从三叉链表的第tSize个结点开始，i=tSize从存储字符及其权值的链表中取出两个权值最小的结点x,y ,记录其下标x,y。将下标为x和y的哈夫曼树的结点的双亲设置为第i个结点将下标为x的结点设置为i结点的左孩子，将下标为y的结点设置为i结点的右孩子，i结点的权值为x结点的权值加上y结点的权值，i结点的双亲设置为空4. 根据哈夫曼树创建编码表源代码：void HuffmanTree:CreateHTree(Node *p,int n)root= new BiNode; /初始化哈夫曼树Node *front=p->next;if(n=0)throw exception("没有输入字符");for(int i=0;iroot.data=front->count;root.lchild=-1;root.rchild=-1;root.parent=-1;front=front->next;front=p;int New1,New2;for(i=n;inext;for(int i=0;iHCodeTable.data=front->character; / 将第 i 个字符写入编码表int child=i; / 得到第i个字符对应的叶子节点int parent=root.parent; / 得到第i个字符对应的叶子节点的双亲int k=0;if(tSize=1) /如果文本中只有一种字符，它的编码为0(HCodeTable.code=0;k+;while(parent!=-1) / 从第i个字符对应的叶子节点开始，寻找它到根结点的路径(if(child=root.lchild) /如果当前结点为双亲的左孩子，则编码为0,否则编码为1HCodeTable.code=0;elseHCodeTable.code=1;k+;child=parent;parent=root.parent;HCodeTable.code=;Reverse(HCodeTable.code); /将编码逆置front=front->next; /得到下一个字符cout运行结果：各函数运行正常，没有出现bug4. 总结经过这次实验，我了解了哈夫曼树的创建过程，了解了 一种不等长编码的方法，用设断点调试的方法更加熟练，同 时熟悉了 STL中string 类型的用法，对C+更加熟悉
