综合实验哈夫曼编码的实现

华北科技学院计算机系综合性实验实验报告课程名称数据结构B实验学期2023至2023学年第1学期学生所在系部计算机学院年级10级专业班级学生姓名学号任课教师实验成绩计算机系制《数据结构B》课程综合性实验报告开课实验室：实验题目哈夫曼编码的实现一、实验目的1、掌握线性链表的插入、删除等算法。3、掌握Huffman树的概念及构造方法。4、掌握二叉树的存储结构及遍历算法。5、构造Huffman树及Huffman编码二、设备与环境微型计算机、Windows系列操作系统、VisualC++6.0软件三、实验内容根据字符出现的频率情况，创建Huffman树，再将各字符对应的哈夫曼编码显示在屏幕上四、实验结果及分析#include<stdio.h>#include<string.h>#include<stdlib.h>typedefstruct{ unsignedintweight,parent,lchild,rchild;}HTNode,*HuffmanTree;//动态分配数组存储哈夫曼树typedefchar**HuffmanCode;//动态分布数组存储哈夫曼编码表voidSelect(HuffmanTreeHT,intn,int&s1,int&s2){//在HT[1...n]选择parent为且weight最小的两个节点,分别赋给s1,s2//s1最小，s2次小intmin=0,minn=0; HT[0].weight=10000; for(inti=1;i<=n;i++) { if(HT[i].parent==0) { if(HT[i].weight<HT[min].weight) { minn=min; min=i; }elseif(HT[i].weight<HT[minn].weight) minn=i; } } s1=min; s2=minn;}voidHuffmanCoding(HuffmanTree&HT,HuffmanCode&HC,int*h,intn){ //w存放n个字符的权值(均>0)，构造哈夫曼编码HT，并求出n个字符的哈夫曼编码HC。 inti,m,s1,s2; HuffmanTreep; if(n<=1) printf("结点数过少"); m=n*2-1; HT=(HuffmanTree)malloc((m+1)*sizeof(HTNode));//0号单元未用 for(p=HT+1,i=1;i<=n;++i,++p,++h) { (*p).weight=*h; (*p).lchild=0; (*p).rchild=0; (*p).parent=0; }//初始化赫夫曼树 for(;i<=m;++i,++p) { (*p).weight=0; (*p).parent=0; (*p).lchild=0; (*p).rchild=0; } for(i=n+1;i<=m;++i) { //建立哈夫曼树 Select(HT,i-1,s1,s2);//在HT[1..i-1]选择parent为且weight最小的两个结点，其序号分别为s1和s2 HT[s1].parent=i; HT[s2].parent=i; HT[i].lchild=s1; HT[i].rchild=s2; HT[i].weight=HT[s1].weight+HT[s2].weight; } //---从叶子到根逆向求每个字符的哈夫曼编码--- char*mr; unsignedintstart,c,f; HC=(HuffmanCode)malloc((n+1)*sizeof(char*));//分配n个字符编码的头指针向量 mr=(char*)malloc(n*sizeof(char));//分配求编码的工作空间 mr[n-1]='\0';//编码结束符 for(i=1;i<=n;++i)//逐个字符求赫夫曼编码 { start=n-1; for(c=i,f=HT[i].parent;f!=0;c=f,f=HT[f].parent)//从叶子到根逆向求编码 if(HT[f].lchild==c) mr[--start]='0'; elsemr[--start]='1'; HC[i]=(char*)malloc((n-start)*sizeof(char));//为第i个字符编码分配空间 strcpy(HC[i],&mr[start]); } free(mr);//释放工作空间}//HuffanCodingvoidmain(){ HuffmanTreeHT; HuffmanCodeHC; int*w,*p,i,n,k; printf("输入结点个数：k="); scanf("%d",&k); w=(int*)malloc(k*sizeof(int)); p=w; printf("请输入每个结点的权值:\n"); for(i=1;i<=k;++i,++w) { scanf("%d",w); } HuffmanCoding(HT,HC,p,k); printf("赫夫曼树:\n"); printf("weightparentlchildrchild\n"); n=k*2-1; for(i=1;i<=n;i++) { printf("%d%8d%8d%8d%8d\n",i,HT[i].weight,HT[i].parent,HT[i].lchild,HT[i].rchild); } printf("赫夫曼编码:\n"); for(i=1;i<=k;++i) { printf("%d",i); puts(HC[i]); }}五、收获和体会Huffman树，又称为最优树，是一类带权路径长度最短的树，有着广泛的应用。通过对数据结构的学习，让我更加的对Ｃ语言的编程有了深刻的理解和体会。虽然对数据结构的掌握还不够好，但是有Ｃ语言的编程做基础，就会很好的理解，对于huffman树的存储开始掌握的不是很好，但是看了其他同学的程序后，对它的理解有了更深的体会。现在通过这次综合性试验我已完全