北邮数据结构实验报告

《北邮数据结构实验报告》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、北邮数据结构实验报告　　北京邮电大学信息与通信工程学院　　XX级数据结构实验报告　　实验名称：实验三哈夫曼编/解码器的实现　　学生姓名：陈聪捷　　日期：XX年11月28日　　1.实验要求　　一、实验目的：　　了解哈夫曼树的思想和相关概念;　　二、实验内容：　　利用二叉树结构实现哈夫曼编/解码器　　1.初始化：能够对输入的任意长度的字符串s进行统计，统计每个字符的频度，并建立哈夫曼树。　　2.建立编码表：利用已经建好的哈夫曼树进行编码，并将每个字符的编码输出。　　3.编码：根据编码表对输入的字符串进行编码，并将编码后的

2、字符串输出。　　4.译码：利用已经建好的哈夫曼树对编码后的字符串进行译码，并输出译码结果。　　5.打印：以直观的方式打印哈夫曼树。　　6.计算输入的字符串编码前和编码后的长度，并进行分析，讨论哈夫曼编码的压缩效果。　　7.用户界面可以设计成“菜单”方式，能进行交互，根据输入的字符串中每个字符出现的次数统计频度，对没有出现的字符一律不用编码。　　2.程序分析　　存储结构　　二叉树　　template　　classBiTree　　{　　public:　　BiTree();//构造函数，其前序序列由键盘输入　　~BiTre

3、e(void);//析构函数　　BiNode*Getroot();//获得指向根结点的指针　　protected:　　BiNode*root;//指向根结点的头指针　　};　　//声明类BiTree及定义结构BiNode　　Data：　　二叉树是由一个根结点和两棵互不相交的左右子树构成　　哈夫曼树类的数据域，继承节点类型为int的二叉树classHuffmanTree:publicBiTree　　　data:　　HCode*HCodeTable;//编码表　　inttSize;//编码表中的总字符数　　二叉树的节点结

4、构　　template　　structBiNode//二叉树的结点结构{　　Tdata;//记录数据　　Tlchild;//左孩子　　Trchild;//右孩子　　Tparent;//双亲　　};　　编码表的节点结构　　structHCode　　{　　chardata;//编码表中的字符　　charcode;//该字符对应的编码　　};　　待编码字符串由键盘输入，输入时用链表存储，链表节点为structNode　　{　　charcharacter;//输入的字符　　unsignedintcount;//该字符的权值　

5、　boolused;//建立树的时候该字符是否使用过　　Node*next;//保存下一个节点的地址　　};　　示意图：　　　关键算法分析　　1.初始化函数(voidHuffmanTree::Init(stringInput))　　算法伪代码：　　1.初始化链表的头结点　　2.获得输入字符串的第一个字符，并将其插入到链表尾部,n=1(n记录的是链表　　中字符的个数)　　3.从字符串第2个字符开始，逐个取出字符串中的字符　　将当前取出的字符与链表中已经存在的字符逐个比较，如果当前取出　　的字符与链表中已经存在的某个字符

6、相同，则链表中该字符的权值加1。　　如果当前取出的字符与链表中已经存在的字符都不相同，则将其加入　　到链表尾部，同时n++　　=n(tSize记录链表中字符总数，即哈夫曼树中叶子节点总数)　　5.创建哈夫曼树　　6.销毁链表　　源代码：　　voidHuffmanTree::Init(stringInput)　　{　　Node*front=newNode;//初始化链表的头结点　　if(!front)　　throwexception("堆空间用尽");　　front->next=NULL;　　front->charac

7、ter=NULL;　　front->count=0;　　Node*pfront=front;　　charch=Input;//获得第一个字符　　Node*New1=newNode;　　if(!New1)　　throwexception("堆空间用尽");　　New1->character=ch;//将第一个字符插入链表　　New1->count=1;　　New1->next=pfront->next;　　pfront->next=New1;　　boolreplace=0;//判断在已经写入链表的字符中是否有与当前读出

8、的字符相同的字符intn=1;//统计链表中字符个数　　for(inti=1;i　　{　　ch=Input;//获得第i个字符　　do　　{　　pfront=pfront->next;　　if((int)pfront->character==(int)ch)//如果在链表中有与当前字符相同的字符，　　该字符权值加1　　{　　pfront->co