下载文档第一篇：数据结构实验三哈夫曼树实验报告
实验报告3：哈夫曼编/译码器
题目：哈夫曼编/译码器
一、题目要求：
写一个哈夫曼码的编/译码系统，要求能对要传输的报文进行编码和解码。构造哈夫曼树时，权值小的放左子树，权值大的放右子树，编码时右子树编码为1，左子树编码为0.二、概要设计：
数据结构：
typedef struct { int bit[MAXBIT];int start;} HCodeType;/* 编码结构体 */
typedef struct { int weight;int parent;int lchild;int rchild;char value;} HNode;/* 结点结构体 */ 函数：
void DEMONHuffmanTree(HNode HuffNode[MAXNODE], int n)作用：构造一个哈夫曼树，并循环构建 int main()作用：运用已经构建好的哈弗曼树，进行节点的处理，达到成功解码编译
三、详细设计： 哈夫曼树的建立：
void DEMONHuffmanTree(HNode HuffNode[MAXNODE], int n){
int i = 0, j, m1, m2, x1, x2;
char x;
/* 初始化存放哈夫曼树数组 HuffNode[] 中的结点 */
while(i { HuffNode[i].weight = 0;//权值 实验报告3：哈夫曼编/译码器 HuffNode[i].parent =-1; HuffNode[i].lchild =-1; HuffNode[i].rchild =-1; scanf(“%c”,&x); scanf(“%c”,&HuffNode[i].value);//实际值，可根据情况替换为字母 i++; } /* 输入 n 个叶子结点的权值 */ scanf(“%c”,&x);for(i=0;i { scanf(“%d”, &HuffNode[i].weight); } for(i=n;i<2*n-1;i++) { HuffNode[i].weight = 0;//权值 HuffNode[i].parent =-1; HuffNode[i].lchild =-1; HuffNode[i].rchild =-1; HuffNode[i].value=i; } /* 循环构造 Huffman 树 */ for(i=0;i { m1=m2=MAXQZ; // m1、m2中存放两个无父结点且结点权值最小的两个结点 x1=x2=0;//找出所有结点中权值最小、无父结点的两个结点，并合并之为一颗二叉树 for(j=0;j { if(HuffNode[j].weight < m1 && HuffNode[j].parent==-1) { m2=m1;//m1中是最小 x2=x1; m1=HuffNode[j].weight; x1=j; } else if(HuffNode[j].weight < m2 && HuffNode[j].parent==-1) { m2=HuffNode[j].weight; x2=j; } 实验报告3：哈夫曼编/译码器 } /* end for */ /* 设置找到的两个子结点 x1、x2 的父结点信息 */ HuffNode[x1].parent = n+i; HuffNode[x2].parent = n+i; HuffNode[n+i].weight = HuffNode[x1].weight + HuffNode[x2].weight; HuffNode[n+i].lchild = x1; HuffNode[n+i].rchild = x2; } } 叶子节点的哈夫曼编码的保存： for(j=cd.start+1;j HuffCode[i].bit[j] = cd.bit[j]; HuffCode[i].start = cd.start; 主函数展示： int main(){ HNode HuffNode[MAXNODE]; HCodeType HuffCode[MAXLEAF],cd; int i, j, c, p, n,k=0; char wen[100]; char z; scanf(“%d”, &n); HuffmanTree(HuffNode, n); for(i=0;i < n;i++) { cd.start = n-1; c = i; p = HuffNode[c].parent; while(p!=-1) /* 父结点存在 */ { if(HuffNode[p].lchild == c) cd.bit[cd.start] = 0; else cd.bit[cd.start] = 1; cd.start--; /* 求编码的低一位 */ c=p; p=HuffNode[c].parent; /* 设置下一循环条件 */ } /* end while */ 实验报告3：哈夫曼编/译码器 for(j=cd.start+1;j HuffCode[i].bit[j] = cd.bit[j]; HuffCode[i].start = cd.start; } /* end for */ z=getchar(); z=getchar(); for(;z!='n';z=getchar()){ wen[k++]=z; for(i=0;i { if(z==HuffNode[i].value) { for(j=HuffCode[i].start+1;j < n;j++) printf(“%d”, HuffCode[i].bit[j]); break; } else; } } printf(“n”);for(i=0;i { printf(“%c”,wen[i]); } printf(“n”); return 0;} 四、调试分析与心得体会： 虽然哈夫曼树的建立有书上的参考，但是实际写整个代码的时候还是问题重重。首先就是哈弗曼树忘记了初始的赋值，导致最后出现了问题。这样的错误还是很容易解决，但是之后就出现了WA的情况。在同学的帮助下，最后发现是因为在选取节点的时候，循环出现了问题，虽然看起来编译没有错，但是边缘情况就会出现数据错误，这个还是很令人警醒，而这种思考的不全面的问题，在debug的过程中会耗去大量的时间，这是要注意的。 五、用户操作说明： 输入表示字符集大小为n（n <= 100）的正整数，以及n个字符和n个权值（正整数，值 越大表示该字符出现的概率越大）； 输入串长小于或等于100的目标报文。实验报告3：哈夫曼编/译码器 六、运行结果： 附带自己的算法完成的结果图，可以通过Prt Sc和图片编辑器获得； 实验报告3：哈夫曼编/译码器 七、附录： #include #define MAXBIT 100 #define MAXLEAF 30 #define MAXNODE MAXLEAF*2-1 #define MAXQZ 10000 //权值 typedef struct { int bit[MAXBIT];int start;} HCodeType;/* 编码结构体 */ 实验报告3：哈夫曼编/译码器 typedef struct { int weight;int parent;int lchild;int rchild;char value;} HNode;/* 结点结构体 */ /* 构造一颗哈夫曼树 */ void HuffmanTree(HNode HuffNode[MAXNODE], int n){ int i = 0, j, m1, m2, x1, x2;char x;/* 初始化存放哈夫曼树数组 HuffNode[] 中的结点 */ while(i scanf(“%c”,&x);scanf(“%c”,&HuffNode[i].value);//实际值，可根据情况替换为字母 i++;} /* 输入 n 个叶子结点的权值 */ scanf(“%c”,&x);i = 0;while(i for(i=n;i<2*n-1;i++){ HuffNode[i].weight = 0;//权值 HuffNode[i].parent =-1;HuffNode[i].lchild =-1;HuffNode[i].rchild =-1;HuffNode[i].value=i;} 实验报告3：哈夫曼编/译码器 /* 循环构造 Huffman 树 */ for(i=0;i x1=x2=0;//找出所有结点中权值最小、无父结点的两个结点，并合并之为一颗二叉树 for(j=0;j } } int main(){ HNode HuffNode[MAXNODE];/* 定义一个结点结构体数组 */ HCodeType HuffCode[MAXLEAF],cd;/* 定义一个编码结构体数组，同时定义一个临时变量来存放求解编码时的信息 */ int i, j, c, p, n,k=0;char wen[100];char z;scanf(“%d”, &n);HuffmanTree(HuffNode, n);8 3：哈夫曼编/译码器 for(i=0;i < n;i++){ cd.start = n-1;c = i;p = HuffNode[c].parent;while(p!=-1)/* 父结点存在 */ { if(HuffNode[p].lchild == c)cd.bit[cd.start] = 0;else cd.bit[cd.start] = 1;cd.start--;/* 求编码的低一位 */ c=p;p=HuffNode[c].parent;/* 设置下一循环条件 */ } /* end while */ /* 保存求出的每个叶结点的哈夫曼编码和编码的起始位 */ for(j=cd.start+1;j z=getchar();z=getchar();for(;z!='n';z=getchar()){ wen[k++]=z; for(i=0;i { if(z==HuffNode[i].value) { for(j=HuffCode[i].start+1;j < n;j++) printf(“%d”, HuffCode[i].bit[j]); break; } else; } } printf(“n”);i = 0;while(i { printf(“%c”,wen[i]);实验报告 实验报告3：哈夫曼编/译码器 } printf(“n”);return 0;} i++; 实验报告3：哈夫曼编/译码器 上机实习要求： 1、认真准备，按时参加上机实习，不得无故缺席，抽查不到者扣分； 2、独立完成老师布置的题目，上机完成程序并调试正确，课后完成实验报告的编写，将上机程序和实验报告打包后交给辅导老师评定分数，实验报告要求和评分标准见后面； 3、提倡创新，可对课本上提供的算法进行改进； 4、上机程序必须在程序中提供足够的注释，详细为好。 5、实验报告不用写出算法，只要写出对课程设计的见解，如对某一算法的改进思想，算法设计思想，调试算法过程中出现的问题及改进方法，调试程序的体会等。只要是自己编程和调试就会写出相应的报告。 考核标准 1、机试程序和结果、设计报告缺一不可，机试程序和结果压缩打包后上交给辅导老师，设计报告主要是自己的设计过程和调试心得，报告中不必附带全部的源程序）。机试成绩占总成绩60%，设计报告占40%。 2、上机程序和设计报告必须独立完成，严禁抄袭，若发现雷同，原创者视上机结果最多60分，抄袭者按0分计，若找不到原创，都按0分计。 所以原创同学注意，我们的检查专门针对抄袭情况，一旦发现将严肃处理！！ 题目：哈夫曼编/译码器 一、题目要求： 写一个哈夫曼码的编/译码系统，要求能对要传输的报文进行编码和解码。构造哈夫曼树时，权值小的放左子树，权值大的放右子树，编码时右子树编码为1，左子树编码为0.二、概要设计： 数据结构： typedef struct { int bit[MAXBIT];int start;} HCodeType;/* 编码结构体 */ typedef struct { int weight;int parent;int lchild;int rchild;char value;} HNode;/* 结点结构体 */ 函数： void DEMONHuffmanTree(HNode HuffNode[MAXNODE], int n)作用：构造一个哈夫曼树，并循环构建 int main()作用：运用已经构建好的哈弗曼树，进行节点的处理，达到成功解码编译 三、详细设计： 哈夫曼树的建立： void DEMONHuffmanTree(HNode HuffNode[MAXNODE], int n){ int i = 0, j, m1, m2, x1, x2; char x; /* 初始化存放哈夫曼树数组 HuffNode[] 中的结点 */ while(i { HuffNode[i].weight = 0;//权值 HuffNode[i].parent =-1; HuffNode[i].lchild =-1; HuffNode[i].rchild =-1; scanf(“%c”,&x); scanf(“%c”,&HuffNode[i].value);//实际值，可根据情况替换为字母 i++; } /* 输入 n 个叶子结点的权值 */ scanf(“%c”,&x);for(i=0;i { scanf(“%d”, &HuffNode[i].weight); } for(i=n;i<2*n-1;i++) { HuffNode[i].weight = 0;//权值 HuffNode[i].parent =-1; HuffNode[i].lchild =-1; HuffNode[i].rchild =-1; HuffNode[i].value=i; } /* 循环构造 Huffman 树 */ for(i=0;i { m1=m2=MAXQZ; // m1、m2中存放两个无父结点且结点权值最小的两个结点 x1=x2=0;//找出所有结点中权值最小、无父结点的两个结点，并合并之为一颗二叉树 for(j=0;j { if(HuffNode[j].weight < m1 && HuffNode[j].parent==-1) { m2=m1;//m1中是最小 x2=x1; m1=HuffNode[j].weight; x1=j; } else if(HuffNode[j].weight < m2 && HuffNode[j].parent==-1) { m2=HuffNode[j].weight; x2=j; } } /* end for */ /* 设置找到的两个子结点 x1、x2 的父结点信息 */ HuffNode[x1].parent = n+i; HuffNode[x2].parent = n+i; HuffNode[n+i].weight = HuffNode[x1].weight + HuffNode[x2].weight; HuffNode[n+i].lchild = x1; HuffNode[n+i].rchild = x2; } } 叶子节点的哈夫曼编码的保存： for(j=cd.start+1;j HuffCode[i].bit[j] = cd.bit[j]; HuffCode[i].start = cd.start; 主函数展示： int main(){ HNode HuffNode[MAXNODE]; HCodeType HuffCode[MAXLEAF],cd; int i, j, c, p, n,k=0; char wen[100]; char z; scanf(“%d”, &n); HuffmanTree(HuffNode, n); for(i=0;i < n;i++) { cd.start = n-1; c = i; p = HuffNode[c].parent; while(p!=-1) /* 父结点存在 */ { if(HuffNode[p].lchild == c) cd.bit[cd.start] = 0; else cd.bit[cd.start] = 1; cd.start--; /* 求编码的低一位 */ c=p; p=HuffNode[c].parent; /* 设置下一循环条件 */ } /* end while */ for(j=cd.start+1;j HuffCode[i].bit[j] = cd.bit[j]; HuffCode[i].start = cd.start; } /* end for */ z=getchar(); z=getchar(); for(;z!='n';z=getchar()){ wen[k++]=z; for(i=0;i { if(z==HuffNode[i].value) { for(j=HuffCode[i].start+1;j < n;j++) printf(“%d”, HuffCode[i].bit[j]); break; } else; } } printf(“n”);for(i=0;i { printf(“%c”,wen[i]); } printf(“n”); return 0;} 四、调试分析与心得体会： 虽然哈夫曼树的建立有书上的参考，但是实际写整个代码的时候还是问题重重。首先就是哈弗曼树忘记了初始的赋值，导致最后出现了问题。这样的错误还是很容易解决，但是之后就出现了WA的情况。在同学的帮助下，最后发现是因为在选取节点的时候，循环出现了问题，虽然看起来编译没有错，但是边缘情况就会出现数据错误，这个还是很令人警醒，而这种思考的不全面的问题，在debug的过程中会耗去大量的时间，这是要注意的。 五、用户操作说明： 输入表示字符集大小为n（n <= 100）的正整数，以及n个字符和n个权值（正整数，值 越大表示该字符出现的概率越大）； 输入串长小于或等于100的目标报文。 六、运行结果： 附带自己的算法完成的结果图，可以通过Prt Sc和图片编辑器获得； 七、附录： #include #define MAXBIT 100 #define MAXLEAF 30 #define MAXNODE MAXLEAF*2-1 #define MAXQZ 10000 //权值 typedef struct { int bit[MAXBIT];int start;} HCodeType;/* 编码结构体 */ typedef struct { int weight;int parent;int lchild;int rchild;char value;} HNode;/* 结点结构体 */ /* 构造一颗哈夫曼树 */ void HuffmanTree(HNode HuffNode[MAXNODE], int n){ int i = 0, j, m1, m2, x1, x2;char x;/* 初始化存放哈夫曼树数组 HuffNode[] 中的结点 */ while(i scanf(“%c”,&x);scanf(“%c”,&HuffNode[i].value);//实际值，可根据情况替换为字母 i++;} /* 输入 n 个叶子结点的权值 */ scanf(“%c”,&x);i = 0;while(i for(i=n;i<2*n-1;i++){ HuffNode[i].weight = 0;//权值 HuffNode[i].parent =-1;HuffNode[i].lchild =-1;HuffNode[i].rchild =-1;HuffNode[i].value=i;} /* 循环构造 Huffman 树 */ for(i=0;i x1=x2=0;//找出所有结点中权值最小、无父结点的两个结点，并合并之为一颗二叉树 for(j=0;j } } int main(){ HNode HuffNode[MAXNODE];/* 定义一个结点结构体数组 */ HCodeType HuffCode[MAXLEAF],cd;/* 定义一个编码结构体数组，同时定义一个临时变量来存放求解编码时的信息 */ int i, j, c, p, n,k=0;char wen[100];char z;scanf(“%d”, &n);HuffmanTree(HuffNode, n);8 for(i=0;i < n;i++){ cd.start = n-1;c = i;p = HuffNode[c].parent;while(p!=-1)/* 父结点存在 */ { if(HuffNode[p].lchild == c)cd.bit[cd.start] = 0;else cd.bit[cd.start] = 1;cd.start--;/* 求编码的低一位 */ c=p;p=HuffNode[c].parent;/* 设置下一循环条件 */ } /* end while */ /* 保存求出的每个叶结点的哈夫曼编码和编码的起始位 */ for(j=cd.start+1;j z=getchar();z=getchar();for(;z!='n';z=getchar()){ wen[k++]=z; for(i=0;i { if(z==HuffNode[i].value) { for(j=HuffCode[i].start+1;j < n;j++) printf(“%d”, HuffCode[i].bit[j]); break; } else; } } printf(“n”);i = 0;while(i { printf(“%c”,wen[i]); } printf(“n”);return 0;} i++; 上机实习要求： 1、认真准备，按时参加上机实习，不得无故缺席，抽查不到者扣分； 2、独立完成老师布置的题目，上机完成程序并调试正确，课后完成实验报告的编写，将上机程序和实验报告打包后交给辅导老师评定分数，实验报告要求和评分标准见后面； 3、提倡创新，可对课本上提供的算法进行改进； 4、上机程序必须在程序中提供足够的注释，详细为好。 5、实验报告不用写出算法，只要写出对课程设计的见解，如对某一算法的改进思想，算法设计思想，调试算法过程中出现的问题及改进方法，调试程序的体会等。只要是自己编程和调试就会写出相应的报告。 考核标准 1、机试程序和结果、设计报告缺一不可，机试程序和结果压缩打包后上交给辅导老师，设计报告主要是自己的设计过程和调试心得，报告中不必附带全部的源程序）。机试成绩占总成绩60%，设计报告占40%。 2、上机程序和设计报告必须独立完成，严禁抄袭，若发现雷同，原创者视上机结果最多60分，抄袭者按0分计，若找不到原创，都按0分计。 所以原创同学注意，我们的检查专门针对抄袭情况，一旦发现将严肃处理！！ 树和哈夫曼树实验报告 一．实验目的 练习树和哈夫曼树的有关操作，和各个算法程序，理解哈夫曼树的编码和译码 二．实验环境 Microsoft visual c++ 三．实验问题描述 1.问题描述：建立一棵用二叉链表方式存储的二叉树，并对其进行遍历（先序、中序和后序），打印输出遍历结果。 基本要求：从键盘接受输入先序序列，以二叉链表作为存储结构，建立二叉树（以先序来建立），并将此二叉树按照“树状形式”打印输出，然后对其进行遍历（先序、中序和后序），最后将遍历结果打印输出。在遍历算法中要求至少有一种遍历采用非递归方法。测试数据： ABCØØDEØGØØFØØØ（其中Ø表示空格字符）输出结果为： 先序：ABCDEGF 先序：CBEGDFA 先序：CGEFDBA 2.问题描述：利用哈夫曼编码进行通信可以大大提高信道利用率，缩短信息传输时间，降低传输成本。但是，这要求在发送端通过一个编码系统对待传数据预先编码，在接受端将传来的数据进行译码（复原）。对于双工信道（即可以双向传输信息的信道），每端都需要一个完整的编/译码系统。试为这样的信息收发站写一个哈夫曼码的编/译码系统。基本要求：(至少完成功能1-2）一个完整的系统应具有以下功能： I：初始化（Initialization）。从终端读入字符集大小n，以及n个字符和n个权值，建立哈夫曼树，并将它存于文件hfmTree中。基本要求： E：编码（Encoding）。利用已建好的哈夫曼树（如不在内存，则从文件hfmTree中读入），对文件ToBeTran中的正文进行编码，然后将结果存入文件CodeFile中。 D：译码（Decoding)。利用已建好的哈夫曼树将文件CodeFile中的代码进行译码，结果存入文件TextFile中。 P：印代码文件（Print）。将文件CodeFile以紧凑格式显示在终端上，每行50个代码。同时将此字符形式的编码文件写入文件CodePrint中。T：印哈夫曼树（TreePrinting）。将已在内存中的哈夫曼树以直观的方式（树或凹入表形式）显示在终端上，同时将此字符形式的哈夫曼树写入文件TreePrint中。测试数据： 设权值w=（5，29，7，8，14，23，3，11），n=8。 按照字符‘0’或‘1’确定找左孩子或右孩子，则权值对应的编码为： 5：0001，29：11，7：1110，8：1111 14：110，23：01，3：0000，11：001 用下表给出的字符集和频度的实际统计数据建立哈夫曼树，并实现以下报文的编码和译码：“THIS PROGRAM IS MY FAVORITE”。四．实验主要程序流 实验题目一主要程序： 1．void CreatBiTree(BitTree *bt)//用扩展先序遍历序列创建二叉树，如果是#当前树根置为空，否则申请一个新节点// { char ch;ch=getchar();if(ch=='.')*bt=NULL;else { *bt=(BitTree)malloc(sizeof(BitNode));(*bt)->data=ch;CreatBiTree(&((*bt)->LChild));CreatBiTree(&((*bt)->RChild));} } 2．void Visit(char ch)//访问根节点 { printf(“%c ”,ch);} 3． void PreOrder(BitTree root){ if(root!=NULL){ Visit(root->data);PreOrder(root->LChild);PreOrder(root->RChild);} } 4． void InOrder(BitTree root){ if(root!=NULL){ InOrder(root->LChild);Visit(root->data);InOrder(root->RChild);} } 5．int PostTreeDepth(BitTree bt)//后序遍历求二叉树的高度递归算法// { int hl,hr,max;if(bt!=NULL){ hl=PostTreeDepth(bt->LChild);//求左子树的深度 hr=PostTreeDepth(bt->RChild);//求右子树的深度 max=hl>hr?hl:hr;//得到左、右子树深度较大者 return(max+1);//返回树的深度 } else return(0);//如果是空树，则返回0 } 6．void PrintTree(BitTree Boot,int nLayer)//按竖向树状打印的二叉树 // { int i;if(Boot==NULL)return;PrintTree(Boot->RChild,nLayer+1);for(i=0;i // 函数功能：建立哈夫曼树（调用键盘建立哈夫曼树或调用从文件建立哈夫曼树的函数）void HuffmanTree::CreateHuffmanTree(){char Choose;cout<<“你要从文件中读入哈夫曼树(按1)，还是从键盘输入哈夫曼树(按2)？”;cin>>Choose;if(Choose=='2'){ //键盘输入建立哈夫曼树 CreateHuffmanTreeFromKeyboard();}//choose=='2' else { //从哈夫曼树文件hfmTree.dat中读入信息并建立哈夫曼树 CreateHuffmanTreeFromFile();} } 3.// 从键盘建立哈夫曼树函数 // 函数功能：从键盘建立哈夫曼树 //函数参数：无 //参数返回值：无 void HuffmanTree::CreateHuffmanTreeFromKeyboard(){ int Num;cout<<“n请输入源码字符集个数：”;cin>>Num;if(Num<=1){ cout<<“无法建立少于2个叶子结点的哈夫曼树。nn”;return;} LeafNum=Num;Node=new HuffmanNode[2*Num-1];for(int i=0;i cout<<“请输入第”< int pos1,pos2;int max1,max2;pos2=pos1=j;max2=max1=numeric_limits //pos2最后应指向权重第二小的根结点的下标 //max1存放当前找到的权重最小的根结点的权重 //max2存放当前找到的权重第二小的根结点的权重 for(int k=j-1;k>=0;k--){ if(Node[k].parent==-1){//如果是某棵子树的根结点 if(Node[k].weight max2=max1;max1=Node[k].weight;pos2=pos1;pos1=k;} else if(Node[k].weight max2=Node[k].weight;pos2=k;} }//if(Node[j].parent==-1)} //for //在下标i处新构造一个哈夫曼树的内部结点，其左、右孩子就是以上pos1、pos2所指向的结点 Node[pos1].parent=j;Node[pos2].parent=j;Node[j].lchild=pos1;Node[j].rchild=pos2;Node[j].parent=-1;Node[j].weight=Node[pos1].weight+Node[pos2].weight;} //for //产生所有叶子结点中字符的编码 for(int m=0;m int j=m;int j1;while(Node[j].parent!=-1){ //从叶结点开始往根结点走，每往上走一层，就产生一位编码存入code[] j1=Node[j].parent;if(Node[j1].lchild==j)Node[m].code.insert(0,“0”);else Node[m].code.insert(0,“1”);j=j1;}} cout<<“哈夫曼树已成功构造完成。n”; //把建立好的哈夫曼树写入文件hfmTree.dat char ch;cout<<“是否要替换原来的哈夫曼树文件(Y/N):”;cin>>ch;if(ch!='y'&&ch!='Y')return;ofstream fop;fop.open(“hfmTree.dat”,ios::out|ios::binary|ios::trunc);//打开文件 if(fop.fail()){ cout<<“n哈夫曼树文件打开失败，无法将哈夫曼树写入hfmTree.dat文件。n”;return;} fop.write((char*)&Num,sizeof(Num));//先写入哈夫曼树的叶子结点个数 for(int n=0;n<2*Num-1;n++){ //最后写入哈夫曼树的各个结点（存储在Node[]中） fop.write((char*)&Node[n],sizeof(Node[n]));flush(cout);} fop.close();//关闭文件 cout<<“n哈夫曼树已成功写入hfmTree.dat文件。n”;} 4.// 从文件建立哈夫曼树函数 // 函数功能：从文件建立哈夫曼树 //函数参数：无 //参数返回值：无 void HuffmanTree::CreateHuffmanTreeFromFile(){ ifstream fip;fip.open(“hfmTree.dat”,ios::binary|ios::in);if(fip.fail()){ cout<<“哈夫曼树文件hfmTree.dat打开失败，无法建立哈夫曼树。n”;return;} fip.read((char*)&LeafNum,sizeof(LeafNum));if(LeafNum<=1){ cout<<“哈夫曼树文件中的数据有误，叶子结点个数少于2个，无法建立哈夫曼树。n”;fip.close();return;} Node=new HuffmanNode[2*LeafNum-1];for(int i=0;i<2*LeafNum-1;i++)fip.read((char*)&Node[i],sizeof(Node[i]));fip.close();cout<<“哈夫曼树已从文件成功构造完成。n”;} 5.// 编码函数 // 函数功能：为哈夫曼树编码 //函数参数：无 //参数返回值：无 void HuffmanTree::Encoder(){ if(Node==NULL){ //内存没有哈夫曼树，则从哈夫曼树文件hfmTree.dat中读入信息并建立哈夫曼树 CreateHuffmanTreeFromFile();if(LeafNum<=1){ cout<<“内存无哈夫曼树。操作撤销。nn”;return;} }//if char *SourceText;//字符串数组，用于存放源文 //让用户选择源文是从键盘输入，还是从源文文件ToBeTran.txt中读入 char Choose;cout<<“你要从文件中读入源文(按1)，还是从键盘输入源文(按2)？”;cin>>Choose;if(Choose=='1'){ ifstream fip1(“ToBeTran.txt”);if(fip1.fail()){ cout<<“源文文件打开失败!无法继续执行。n”;return;} char ch;int k=0;while(fip1.get(ch))k++;//第一次读文件只统计文件中有多少个字符，将字符数存入k fip1.close();SourceText=new char[k+1];//申请存放源文的字符数组空间 ifstream fip2(“ToBeTran.txt”);//第二次读源文文件，把内容写入SourceText[] k=0;while(fip2.get(ch))SourceText[k++]=ch;fip2.close();SourceText[k]='';} else { //从键盘输入源文 string SourceBuff;cin.ignore();cout<<“请输入需要编码的源文(可输入任意长，按回车键结束):n”;getline(cin,SourceBuff,'n');int k=0;while(SourceBuff[k]!='')k++;SourceText=new char[k+1];k=0;while(SourceBuff[k]!=''){ SourceText[k]=SourceBuff[k];k++;} SourceText[k]='';} cout<<“需编码的源文为：”;cout< ofstream fop(“CodeFile.dat”,ios::trunc);//打开码文存放文件 int k=0;while(SourceText[k]!='')//源文串中从第一个字符开始逐个编码 { int i;for(i=0;i if(Node[i].sourcecode==SourceText[k]){ //将对应编码写入码文文件 fop< // 函数功能：对哈夫曼树进行译码 //函数参数：无 //参数返回值：无 void HuffmanTree::Decoder(){//如果内存没有哈夫曼树，则从哈夫曼树文件hfmTree.dat中读入信息并建立哈夫曼树 if(Node==NULL){ CreateHuffmanTreeFromFile();if(LeafNum<=1){ cout<<“内存无哈夫曼树。操作撤销。nn”;return;} } //将码文从文件CodeFile.dat中读入 CodeStr[] ifstream fip1(“CodeFile.dat”);if(fip1.fail()){ cout<<“没有码文，无法译码。n”;return;} char* CodeStr;int k=0;char ch;while(fip1.get(ch)){ k++;} fip1.close();CodeStr=new char[k+1];ifstream fip2(“CodeFile.dat”);k=0;while(fip2.get(ch))CodeStr[k++]=ch;fip2.close();CodeStr[k]=''; cout<<“经译码得到的源文为：”;ofstream fop(“TextFile.dat”); int j=LeafNum*2-1-1;//j指向哈夫曼树的根 int i=0;//码文从第一个符号开始，顺着哈夫曼树由根下行，按码文的当前符号决定下行到左孩子还是右孩子 while(CodeStr[i]!=''){ //下行到哈夫曼树的叶子结点处，则译出叶子结点对应的源文字符 if(CodeStr[i]=='0')j=Node[j].lchild;else j=Node[j].rchild;if(Node[j].rchild==-1){ //因为哈夫曼树没有度为1的结点，所以此条件等同于Node[j]为叶结点 cout< fop< } i++;} fop.close(); cout<<“n译码成功且已存到文件TextFile.dat中。nn”;} 7.// 输出码文函数 // 函数功能：从文件中输出哈夫曼树的码文 //函数参数：无 //参数返回值：无 void HuffmanTree::PrintCodeFile(){ char ch;int i=1;ifstream fip(“CodeFile.dat”);ofstream fop(“CodePrin.dat”);if(fip.fail()){ cout<<“没有码文文件，无法显示码文文件内容。n”;return;} while(fip.get(ch)){cout< // 函数功能：从内存或文件中直接输出哈夫曼树 //函数参数：无 //参数返回值：无 void HuffmanTree::PrintHuffmanTree(){ //如果内存没有哈夫曼树，则从哈夫曼树文件hfmTree.dat中读入信息并建立哈夫曼树 if(Node==NULL){ CreateHuffmanTreeFromFile();if(LeafNum<=1){ cout<<“内存无哈夫曼树。操作撤销。nn”;return;}} ofstream fop(“TreePrint.dat”,ios_base::trunc);fop.close();PrintHuffmanTree_aoru(2*LeafNum-1-1);return;} 【需求分析】 本实验需要设计程序，输入叶子结点和权值，建立一颗哈弗曼树，并根据哈弗曼树进行编码和译码操作。键盘中输入或者从文件中读入哈弗曼树；键盘中输入或者从源文件中读入需要编码的源文，然后将源文根据哈弗曼树的权值，译码为二进制代码。最后实现凹入显示法显示哈弗曼树。【概念设计】 本程序由HaffmanTree.h、HaffmanTree.cpp、main.cpp三个文件构成。HaffmanTree.h中定义了哈弗曼树的储存结构体HaffmanNode，里面定义了weight、parent、lchild、rchild四个变量来描述哈弗曼树的储存结构。在HaffmanTree.h中还定义了一个名为HaffmanTree的类，里面定义的是建树、编码、译码和凹入显示哈弗曼树等函数，而相关的实现代码则在HaffmanTree.cpp中给出。main.cpp中主要是实现内部函数与用户界面的对接。【详细设计】 具体代码实现如下： //HaffmanTree.h #include class HuffmanTree //哈夫曼树 { private: HuffmanNode *Node;//Node[]存放哈夫曼树 char *Info;//Info[]存放源文用到的字符——源码，如'a','b','c','d','e'，此内容可以放入结点中，不单独设数组存放 int LeafNum;//哈夫曼树的叶子个数，也是源码个数 public: HuffmanTree();~HuffmanTree();void CreateHuffmanTree();/*在内存中建立哈夫曼树，存放在Node[]中。让用户从两种建立哈夫曼树的方法中选择： 1.从键盘读入源码字符集个数，每个字符，和每个字符的权重，建立哈夫曼树，并将哈夫曼树写入文件hfmTree中。2.从文件hfmTree中读入哈夫曼树信息，建立哈夫曼树*/ void CreateHuffmanTreeFromKeyboard();void CreateHuffmanTreeFromFile();void Encoder();/*使用建立好的哈夫曼树（如果不在内存，则从文件hfmTree中读入并建立内存里的哈夫曼树），对文件ToBeTran中的正文进行编码，并将码文写入文件CodeFile中。 ToBeTran的内容可以用记事本等程序编辑产生。*/ void Decoder();/*待译码的码文存放在文件CodeFile中，使用建立好的哈夫曼树（如果不在内存，则从文件hfmTree中读入并建立内存里的哈夫曼树）将码文译码，得到的源文写入文件TextFile中，并同时输出到屏幕上。*/ void PrintCodeFile();/*将码文文件CodeFile显示在屏幕上*/ void PrintHuffmanTree();/*将哈夫曼树以直观的形式（凹入表示法，或广义表，或其他树形表示法）显示在屏幕上，同时写入文件TreePrintFile中*/ void PrintHuffmanTree_aoru(int T,int layer=1);/*凹入表示法显示哈夫曼树，由PrintHuffmanTree()调用*/ }; ///////////////////////////////////////////////////////////////////HuffmanTree.cpp #include //****************************************************** HuffmanTree::HuffmanTree(){ Node=NULL;} //****************************************************** HuffmanTree::~HuffmanTree(){ delete[]Node;} //****************************************************** void HuffmanTree::CreateHuffmanTree(){ char Choose;cout<<“你要从文件中读入哈夫曼树(按1)，还是从键盘输入哈夫曼树(按2)？”;cin>>Choose;if(Choose=='2'){//键盘输入建立哈夫曼树 CreateHuffmanTreeFromKeyboard();}//choose=='2' else { //从哈夫曼树文件hfmTree.dat中读入信息并建立哈夫曼树 CreateHuffmanTreeFromFile();} } //****************************************************** void HuffmanTree::CreateHuffmanTreeFromKeyboard(){ int Num; cout<<“n请输入源码字符集个数：”; cin>>Num; if(Num<=1) { cout<<“无法建立少于2个叶子结点的哈夫曼树。nn”; return; } LeafNum=Num; Node=new HuffmanNode[2*Num-1]; Info=new char[2*Num-1]; for(int i=0;i cout<<“请输入第”< getchar(); Info[i]=getchar();//源文的字符存入字符数组Info[] getchar(); cout<<“请输入该字符的权值或频度”; cin>>Node[i].weight;//源文的字符权重存入Node[].weight Node[i].parent=-1; Node[i].lchild=-1; Node[i].rchild=-1; } for(i=Num;i<2*Num-1;i++) {//循环建立哈夫曼树内部结点 int pos1=-1,pos2=-1; int max1=32767,max2=32767; for(int j=0;j if(Node[j].parent==-1)//是否为根结点 if(Node[j].weight { max2=max1; max1=Node[j].weight; pos2=pos1; pos1=j; } else if(Node[j].weight { max2=Node[j].weight; pos2=j; } Node[pos1].parent=i; Node[pos2].parent=i; Node[i].lchild=pos1; Node[i].rchild=pos2; Node[i].parent=-1; Node[i].weight=Node[pos1].weight+Node[pos2].weight; } //for cout<<“哈夫曼树已成功构造完成。n”; //把建立好的哈夫曼树写入文件hfmTree.dat char ch; cout<<“是否要替换原来的哈夫曼树文件(Y/N):”; cin>>ch; if(ch!='y'&&ch!='Y')return; else { ofstream fop; fop.open(“hfmTree.dat”,ios::out|ios::binary|ios::trunc);//打开文件 if(fop.fail()) { cout<<“n哈夫曼树文件打开失败，无法将哈夫曼树写入hfmTree.dat文件。n”; return; } fop.write((char*)&Num,sizeof(Num));//先写入哈夫曼树的叶子结点个数 for(i=0;i { //再写入源文字符集的所有字符（存储在Info[]中） fop.write((char*)&Info[i],sizeof(Info[i])); flush(cout); } for(i=0;i<2*Num-1;i++) { //最后写入哈夫曼树的各个结点（存储在Node[]中） fop.write((char*)&Node[i],sizeof(Node[i])); flush(cout); } fop.close();//关闭文件 cout<<“n哈夫曼树已成功写入hfmTree.dat文件。n”; } } //****************************************************** void HuffmanTree::CreateHuffmanTreeFromFile(){ ifstream fip;fip.open(“hfmTree.dat”,ios::binary|ios::in);if(fip.fail()){ cout<<“哈夫曼树文件hfmTree.dat打开失败，无法建立哈夫曼树。n”; return;} fip.read((char*)&LeafNum,sizeof(LeafNum));if(LeafNum<=1){ cout<<“哈夫曼树文件中的数据有误，叶子结点个数少于2个，无法建立哈夫曼树。n”; fip.close(); return;} Info=new char[LeafNum];Node=new HuffmanNode[2*LeafNum-1];for(int i=0;i fip.read((char*)&Info[i],sizeof(Info[i]));for(i=0;i<2*LeafNum-1;i++) fip.read((char*)&Node[i],sizeof(Node[i]));fip.close();cout<<“哈夫曼树已成功构造完成。n”;} //****************************************************** void HuffmanTree::Encoder(){ if(Node==NULL){//内存没有哈夫曼树，则从哈夫曼树文件hfmTree.dat中读入信息并建立哈夫曼树 CreateHuffmanTreeFromFile(); if(LeafNum<=1) { cout<<“内存无哈夫曼树。操作撤销。nn”; return; } }//if char *SourceText;//字符串数组，用于存放源文 //让用户选择源文是从键盘输入，还是从源文文件ToBeTran.txt中读入 char Choose;cout<<“你要从文件中读入源文(按1)，还是从键盘输入源文(按2)？”;cin>>Choose;if(Choose=='1'){ ifstream fip1(“ToBeTran.txt”); if(fip1.fail()) { cout<<“源文文件打开失败!无法继续执行。n”; return; } char ch; int k=0; while(fip1.get(ch))k++;//第一次读文件只统计文件中有多少个字符，将字符数存入k fip1.close(); SourceText=new char[k+1];//申请存放源文的字符数组空间 ifstream fip2(“ToBeTran.txt”);//第二次读源文文件，把内容写入SourceText[] k=0; while(fip2.get(ch))SourceText[k++]=ch; fip2.close(); SourceText[k]=''; cout<<“需编码的源文为：”; cout< string SourceBuff; cin.ignore(); cout<<“请输入需要编码的源文(可输入任意长，按回车键结束):n”; getline(cin,SourceBuff,'n'); int k=0; while(SourceBuff[k]!='') k++; SourceText=new char[k+1]; k=0; while(SourceBuff[k]!='') { SourceText[k]=SourceBuff[k]; k++; } SourceText[k]=''; cout<<“覆盖已有的编码原文件?（Y/N）”; char ch; cin>>ch; if(ch=='y'||ch=='Y') { ofstream fip2; fip2.open(“ToBeTran.txt”); if(!fip2) { cerr<<“文件打开失败！”< abort(); } fip2< fip2.close(); cout<<“需编码的源文已写入ToBeTran.txt中”< } } //开始编码 ofstream fop(“CodeFile.dat”,ios::trunc);//打开码文存放文件 char *code;code=new char[LeafNum];//存放一个源文字符的编码 int k=0;while(SourceText[k]!='')//源文串中从第一个字符开始逐个编码 { int star=0; char ch=SourceText[k]; for(int i=0;i if(Info[i]==ch)//求出该文字所在的单元编号 break; int j=i; while(Node[j].parent!=-1) { j=Node[j].parent; if(Info[Node[j].lchild]==Info[i])code[star++]='0'; else code[star++]='1'; i=j; } code[star]=''; for(i=0;i { int j=code[i]; code[i]=code[star-i-1]; code[star-i-1]=j; } i=0;//将源文的当前字符的对应编码写入码文文件 while(code[i]!='') { fop< i++; } k++;//源文串中的字符后移一个 } fop.close();cout<<“已完成编码，码文已写入文件CodeFile.dat中。nn”;} //****************************************************** void HuffmanTree::Decoder(){ //如果内存没有哈夫曼树，则从哈夫曼树文件hfmTree.dat中读入信息并建立哈夫曼树 if(Node==NULL){ CreateHuffmanTreeFromFile(); if(LeafNum<=1) { cout<<“内存无哈夫曼树。操作撤销。nn”; return; } } //将码文从文件CodeFile.dat中读入 CodeStr[] ifstream fip1(“CodeFile.dat”);if(fip1.fail()){ cout<<“没有码文，无法译码。n”; return;} char* CodeStr;int k=0;char ch;while(fip1.get(ch)){ k++;} fip1.close();CodeStr=new char[k+1];ifstream fip2(“CodeFile.dat”);k=0;while(fip2.get(ch))CodeStr[k++]=ch;fip2.close();CodeStr[k]=''; cout<<“经译码得到的源文为：”;ofstream fop(“TextFile.dat”); int j=LeafNum*2-1-1;//j指向哈夫曼树的根 int i=0;//码文从第一个符号开始，顺着哈夫曼树由根下行，按码文的当前符号决定下行到左孩子还是右孩子 while(CodeStr[i]!=''){ //下行到哈夫曼树的叶子结点处，则译出叶子结点对应的源文字符 if(CodeStr[i]=='0')j=Node[j].lchild; else j=Node[j].rchild; if(Node[j].rchild==-1) { cout< fop< j=LeafNum*2-1-1; } i++;} fop.close(); cout<<“n译码成功且已存到文件TextFile.dat中。nn”;} //****************************************************** void HuffmanTree::PrintCodeFile(){ char ch;int i=1;ifstream fip(“CodeFile.dat”);ofstream fop(“CodePrin.dat”);if(fip.fail()){ cout<<“没有码文文件，无法显示码文文件内容。n”; return;} while(fip.get(ch)){ cout< fop< if(i==50) { cout< fop< i=0; } i++;} cout< if(Node==NULL){ CreateHuffmanTreeFromFile(); if(LeafNum<=1) { cout<<“内存无哈夫曼树。操作撤销。nn”; return; } } ofstream fop(“TreePrint.dat”,ios_base::trunc);fop.close();PrintHuffmanTree_aoru(2*LeafNum-1-1,0);return;} //****************************************************** void HuffmanTree::PrintHuffmanTree_aoru(int T,int layer){ for(int i=0;i } ///////////////////////////////////////////////////////////////////main.cpp #include“HuffmanTree.h” #include using namespace std; int main(){ HuffmanTree huftree;char Choose;while(1){ cout<<“nn**********************欢迎使用哈夫曼编码/译码系统***********************”< cout<<“您可以进行以下操作:”< cout<<“1 建立哈夫曼树 3 译码(码文已在文件CodeFile中)5 显示哈夫曼树”< cout<<“2 编码(源文已在文件ToBeTran中，或键盘输入)4 显示码文 6 退出 ”< cout<<“请选择一个操作:”; cin>>Choose; switch(Choose) { case '1': huftree.CreateHuffmanTree(); break; case '2': huftree.Encoder(); break; case '3': huftree.Decoder(); break; case '4': huftree.PrintCodeFile(); break; case '5': huftree.PrintHuffmanTree(); break; case '6': cout<<“n*************************统!***********************nn”; system(“pause”); return 0; }//switch }//while }//main 感谢使用本系【用户手册】 进入哈弗曼树系统，出现以下界面： 1建立弗曼树 2、编码（源文中读入，键盘输入） 3、译码 4、显示码文 5、显示哈弗曼树 6、退出 用户根据该提示，选择前面数字，就能进入各个功能函数，实现函数功能。【运行结果】 截图一： 截图二： 截图三： 【心得体会】 本实验是有老师提供模板，然后自己增加功能函数的代码实现的。因此，在完成未完成的功能函数之前还必须要细心阅读所给出代码，整体观察各个部分之前的联系，搞清楚已给出和未完成的代码功能之后，才根据算法，设计出该功能的函数代码。 在完成实验时，有发现老师所给出代码也有纰漏的地方，如在源 文件读入的时候，多出了一个值，得要增加下表减这个代码来去掉。还有就是在译码的时候，由于变量定义的混淆，在编译的时候通过，但执行时却出现意料不到的结果，在自己细心观察、思考之前也还没找出错误之处。后来通过请教老师，在和老师讨论检查之后才知道了错误之所在，最后改正错误。实验成功完成。 【参考文献】 数据结构与算法（课本） C++语言基础 哈夫曼编码与解码的实现 一、设计思想 (一)哈夫曼树的设计思想 对于一组具有确定权值的叶子结点可以构造出多个具有不同带权路径长度的二叉树，其中具有最小带权路径长度的二叉树称作哈夫曼树或最优二叉树。 首先给定n个权值制造n个只含根结点的二叉树，得到一个二叉树林；再在这二叉树林里面找根结点的权值最小和次小的两棵树作成新的二叉树，其中新的二叉树的根结点的权值为左右子根结点权值之和；最后在二叉树林中把组合过的二叉树删除，再重复第二步，直到最后就剩一颗二叉树的时候得到的这棵二叉树就是哈夫曼树。 （二）哈夫曼编码与解码的设计思想 在数据通讯中，经常要将传送的文字转换为二进制字符0和1组成的二进制串，称这个过程为编码。与子相对的是解码或是译码，就是用与编码相同的方式将二进制串转换称编码前的文字的过程称作解码。在这里是通过哈夫曼树实现编码与解码的，所以称作是哈夫曼编码与解码。 首先输入一个字符串，还有相应的在哈夫曼树里的权值，这样用哈夫曼树把字符串用二进制串代替它，这个过程要注意树和编码问题，其中树的问题在上面已经解决，主要看编码的问题，就是根据我们输入的字符串和权值建立相应的树模型，这一步完成那编码就已经完成了，最后打印就行了；然后就是解码，完成编码相应的解码就相对简单了，就是先找到在编码的时候建的那个模型树，将编码中的二进制串再根据权值转换为相应的字符串，这样一步步解码就行了。 以上就是通过用哈夫曼树进行哈夫曼编码与解码如何实现的主要设计思想。 哈夫曼编码与解码的实现 for(i=n+1;i<=2*n-1;i++) { s1=s2=10000; x1=x2=0; for(j=1;j<=i-1;j++) { if(myHaffTree[j].parent==0&&myHaffTree[j].weight { s2=s1;x2=x1; s1=myHaffTree[j].weight;x1=j; } else if(myHaffTree[j].parent==0&&myHaffTree[j].weight { s2=myHaffTree[j].weight;x2=j; } } myHaffTree[x1].parent=i; myHaffTree[x2].parent=i; myHaffTree[i].weight=s1+s2; myHaffTree[i].lchild=x1; myHaffTree[i].rchild=x2; } } void HaffmanCode(int n){ int start,c,f,i,j,k;char *cd;cd=(char *)malloc(n*sizeof(char));myHaffCode=(struct Coding *)malloc((n+1)*sizeof(struct Coding));cd[n-1]='';for(i=1;i<=n;++i){ start=n-1; for(c=i,f=myHaffTree[i].parent;f!=0;c=f,f=myHaffTree[f].parent) if(myHaffTree[f].lchild==c)cd[--start]='0'; else cd[--start]='1'; for(j=start,k=0;j { myHaffCode[i].bit[k]=cd[j]; k++; } myHaffCode[i].ch=myHaffTree[i].ch; myHaffCode[i].weight=myHaffTree[i].weight;} /*取编码对应的权值*/ /*n个叶子结点的哈夫曼编码*/ /*构造n个结点哈夫曼编码*/ /*左右子组合为新树*/ /*分配左右结点*/ /*构造哈夫曼树的非叶子结点*/ /*树的初始化*/ 哈夫曼编码与解码的实现 { for(j=1;j<=m;j++) if(myHaffCode[j].ch==*p) printf(“%sn”,myHaffCode[j].bit);} } void Caozuo_D(int n){ int i,c;char code[1000],*p;printf(“please input the coding：”);scanf(“%s”,code);for(p=code,c=2*n-1;*p!='';p++) { if(*p=='0') { c=myHaffTree[c].lchild; { printf(“%c”,myHaffTree[c].ch); c=2*n-1; continue; } } else if(*p=='1') { c=myHaffTree[c].rchild; if(myHaffTree[c].lchild==0) { printf(“%c”,myHaffTree[c].ch); c=2*n-1; continue; } } } printf(“n”);} void main(){ int n; char char1; n=Init(); /*定义字符*/ /*函数的调用*/ /*赋值*/ /*结束*/ /*赋值*/ /* 扫描*/ if(myHaffTree[c].lchild==0) /*结束条件*/ /*进行解码*/ /*输入二进制编码*/ /*解码函数*/ 哈夫曼编码与解码的实现 五、遇到的问题及解决 这部分我主要遇到了如下三个问题，其内容与解决方法如下所列： 问题1: 刚开始不知道如何建一个好树，因为我开始试着建了几个二叉树，不知道什么原因运行的时候那编码总是不对，跟在草稿纸上自己画的那个二叉树总是不相符，就找原因。解决方法: 开始时总是编码出错，就试着找错，树的初始化不可能出错，所以首先看那叶子结点的for函数，没什么错误，接着看非叶子结点的for函数，非叶子结点不好弄，找起来麻烦一些，就是费时间，盘查到最后也没什么错，最后就是左右子结点重生结点的一块了，这也比较好查，可是结果却是错处在这儿了，没想到最放心的一块第二篇：数据结构实验三哈夫曼树实验报告
第三篇：树和哈夫曼树实验报告
第四篇：数据结构哈夫曼树编码译码实验报告
第五篇：数据结构__课程设计之哈夫曼编码
