北邮数据结构实验报告[范本]

北邮数据结构实验报告北京邮电大学信息与通信工程学院 XX级数据结构实验报告 实验名称： 实验三哈夫曼编/解码器的实现 学生姓名：陈聪捷 日 期： XX年11月28日 1.实验要求 一、实验目的： 了解哈夫曼树的思想和相关概念; 二、实验内容： 利用二叉树结构实现哈夫曼编/解码器 1.初始化：能够对输入的任意长度的字符串s进行统计，统计每个字符的频度，并建立哈夫曼树。 2.建立编码表：利用已经建好的哈夫曼树进行编码，并将每个字符的编码输出。 3.编码：根据编码表对输入的字符串进行编码，并将编码后的字符串输出。 4.译码：利用已经建好的哈夫曼树对编码后的字符串进行译码，并输出译码结果。 5.打印：以直观的方式打印哈夫曼树。 6.计算输入的字符串编码前和编码后的长度，并进行分析，讨论哈夫曼编码的压缩效果。 7.用户界面可以设计成“菜单”方式，能进行交互，根据输入的字符串中每个字符出现的次数统计频度，对没有出现的字符一律不用编码。 2. 程序分析 存储结构 二叉树 template class BiTree public: BiTree(); /构造函数，其前序序列由键盘输入 BiTree(void); /析构函数 BiNode* Getroot(); /获得指向根结点的指针 protected: BiNode *root; /指向根结点的头指针 ; /声明类BiTree及定义结构BiNode Data： 二叉树是由一个根结点和两棵互不相交的左右子树构成 哈夫曼树类的数据域，继承节点类型为int的二叉树 class HuffmanTree:public BiTree data: HCode* HCodeTable;/编码表 int tSize; /编码表中的总字符数 二叉树的节点结构 template struct BiNode /二叉树的结点结构 T data; /记录数据 T lchild; /左孩子 T rchild; /右孩子 T parent; /双亲 ; 编码表的节点结构 struct HCode char data; /编码表中的字符 char code; /该字符对应的编码 ; 待编码字符串由键盘输入，输入时用链表存储，链表节点为 struct Node char 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* New1=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变量为默认值 replace=0; tSize=n; /tSize记录的是编码表中字符个数 CreateHTree(front,n); /创建哈夫曼树 pfront=front; while(pfront) /销毁整个链表 front=pfront; pfront=pfront-next; front; 时间复杂度： 若输入的字符串长度为n，则时间复杂度为O(n) 2.创建哈夫曼树(void HuffmanTree: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;i root.data=front-count; root.lchild=-1; root.rchild=-1; root.parent=-1; front=front-next; front=p; int New1,New2; for(i=n;i SelectMin(New1,New2,0,i); /从0i中选出两个权值最小的结点 root.parent=root.parent=i; /用两个权值最小的结点生成新结点， 新节点为其双亲 root.data=root.data+root.data;/新结点的权值为其孩子的权值的和 root.lchild=New1; root.rchild=New2; root.parent=-1; CreateCodeTable(p); /创建编码表 时间复杂度： 在选取两个权值最小的结点的函数中要遍历链表，时间复杂度为O(n),故该函数 的时间复杂度为O(n2) 3.创建编码表(void HuffmanTree:CreateCodeTable(Node *p) 算法伪代码： 1.初始化编码表 2.初始化一个指针，从链表的头结点开始，遍历整个链表 将链表中指针当前所指的结点包含的字符写入编码表中 得到该结点对应的哈夫曼树的叶子结点及其双亲 如果哈夫曼树只有一个叶子结点，将其字符对应编码设置为0 如果不止一个叶子结点，从当前叶子结点开始判断 如果当前叶子结点是其双亲的左孩子，则其对应的编码为0，否 则为1 child指针指向叶子结点的双亲，parent指针指向child指针的双亲， 重复的操作 将已完成的编码倒序 取得链表中的下一个字符 3.输出编码表 源代码： void HuffmanTree:CreateCodeTable(Node *p) HCodeTable=new HCode; /初始化编码表 Node *front=p-next; for(int i=0;i HCodeTable.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， 否则编码为1 HCodeTable.code=0; else HCodeTable.code=1; k+; child=parent; parent=root.parent; HCodeTable.code=; Reverse(HCodeTable.code); /将编码逆置 front=front-next; /得到下一个字符 coutfor(i=0;i coutparent=root.lchild; else /编码为1则寻找右孩子 parent=root.rchild; i+; if(tSize=1) /如果编码表只有一个字符，则根结点即为叶子结点 i+; (1,HCodeTable.data);/将叶子节点对应的字符追加到解码串中 cout 时间复杂度： 设待解码串长度为n，则复杂度为O(n) 8. 计算哈夫曼编码的压缩比(void HuffmanTree:Calculate(string s1,string s2) 算法伪代码： 1. 获得编码前字符串的长度，即其占用的字节数 2. 获得编码后的字符串的长度，将其除以8然后向上取整，得到其占用的字 节数 3. 压缩比将两个相除 源代码： void HuffmanTree:Calculate(string s1,string s2) int cal1=(); int cal2=(); cal2=ceill(float)cal2/8); /将编码串的比特数转化为字节数 coutcoutcout 时间复杂度： O(1) 9. 打印哈夫曼树(void HuffmanTree:PrintTree(int TreeNode,int layer) ) 算法伪代码： 1. 如果待打印结点为空，则返回 2. 递归调用函数打印当前结点的右子树 3. 根据当前结点所在的层次确定其前面要输出多少空格，先输出空格，在打 印当前结点的权值 4. 递归调用函数打印当前结点的左子树 源代码： void HuffmanTree:PrintTree(int TreeNode,int layer) if(TreeNode=-1) /如果待打印结点为空，则返回 return; else PrintTree(root.rchild,layer+1); /先打印该结点的右子树，layer记录 的是该结点所在的层次 for(int i=0;i 空格 coutcoutPrintTree(root.lchild,layer+1); /打印该结点的左子树 时间复杂度： 中序遍历哈夫曼树，复杂度为O(n) 10. 菜单函数(void HuffmanTree:Menu() 算法伪代码： 1. 逐一读取键盘缓存区中的字符，并将它们逐一追加到记录输入字符串的 string变量中，直到读到回车输入符为止 2. 删除string变量末尾的回车输入符 3.利用string变量创建哈夫曼树，初始化编码表。 4. 直观打印哈夫曼树 5. 对输入的字符串进行编码 6. 对编码后的字符串进行解码 7. 计算编码前后的压缩比并输出 源代码： void HuffmanTree:Menu() coutstring Input; char letter; do /将字符逐个读入Input变量中 letter=(); (1,letter); while(letter!= ); ()-1,1); /去掉Input末尾的回车符 Init(Input); /根据输入的字符串创建哈夫曼树及其编码表 coutPrintTree(2*tSize-1-1,1); /打印哈夫曼树 coutstring d1,d2; coutEncode(Input,d1); /编码并打印编码串 coutDecode(d1,d2); /解码并打印解码串 coutCalculate(Input,d1); /计算编码前后的压缩比 其他 1.由于题目要求能输入任