73哈夫曼树实验报告

中南大学《数据结构》课程实验实验报告题目hafuman编码学生姓名柯鑫鑫学生学号3901130604专业班级1306需求分析设字符集为26个英文字母，其出现频度如下表所示。以二叉链表作存储结构，编写程序，实现如下的功能：1、根据所提供的字母数据建立一个Huffman树；2、根据生成的Huffman树的结构，显示输出所有字母的Huffman编码。3、（选作内容）根据产生的Huffman编码，实现Huffman编/译码器。概要设计要结构体存放每个节点的信息，要数组存放字母频率表的信息，节点与节点之间用二叉链表连接。结构体的结构如下structNode{chardate;intweight;Node*parent;Node*lchild;Node*rchild;};date表示存放的字母，weight表示权重。把叶子节点方在前面。叶子节点与总节点的关系为总结点=叶子节点*2-1；（注：可以把常量定义成#defineNUM94//字符数#defineTNUM187//#defineLTH20//编码最大长度好处如下便于程序的升级有利于直观的理解，而不只是数字）初始化各个节点如下for(inti=0;iNUM;i++){node[i]-date=chars[i];node[i]-parent=NULL;node[i]-weight=weight[i];node[i]-lchild=NULL;node[i]-rchild=NULL;}for(inti=NUM;iTNUM;i++){node[i]-parent=NULL;node[i]-weight=-1;node[i]-lchild=NULL;node[i]-rchild=NULL;}详细设计找出没有父节点的最小的两个节点for(inti=NUM;iTNUM;i++){intone=10000;inttwo=10000;inta=0;intb=0;intj=0;for(;ji;j++){if(node[j]-parent==NULL){if(node[j]-weight=one){two=one;b=a;one=node[j]-weight;a=j;}elseif(node[j]-weightone&&node[j]-weight=two){two=node[j]-weight;b=j;}}}node[j]-lchild=node[a];node[j]-rchild=node[b];node[a]-parent=node[j];node[b]-parent=node[j];node[j]-weight=node[a]-weight+node[b]-weight;}定义数组来存储哈夫曼编码并初始化charHT[NUM][LTH];for(inti=0;iLTH;i++){for(intj=0;jNUM;j++){HT[j][i]='7';}}二叉链表从下往上走，如果是左孩子哈夫曼编码为0，如果是右孩子哈夫曼编码为1；数组从最右往前走；for(inti=0;iNUM;i++){intj=LTH-1;Node*m=node[i];while(m-parent!=NULL){Node*temp=m-parent;if(m==temp-lchild){HT[i][j]='0';}if(m==temp-rchild){HT[i][j]='1';}m=m-parent;j--;}}输出哈夫曼编码表strings[NUM];for(inti=0;iNUM;i++){for(intj=0;jLTH;j++){if(HT[i][j]!='7'){s[i].append(1,HT[i][j]);}}}for(inti=0;iNUM;i++){coutnode[i]-dates[i]endl;}system(pause);哈夫曼编码//编码stringcode;for(inti=0;iinputt.size();i++){if(inputt.at(i)-'a'+1==-64)code.append(s[0]);elseif(97=inputt.at(i)&&inputt.at(i)=122)code.append(s[inputt.at(i)-'a'+1]);elseif(65=inputt.at(i)&&inputt.at(i)=90)code.append(s[26+inputt.at(i)-65+1]);elseif(48=inputt.at(i)&&inputt.at(i)=57)code.append(s[53+inputt.at(i)-'0']);elseif(33=inputt.at(i)&&inputt.at(i)=47)code.append(s[63+inputt.at(i)-'!']);elseif(58=inputt.at(i)&&inputt.at(i)=64)code.append(s[78+inputt.at(i)-':']);elseif(91=inputt.at(i)&&inputt.at(i)=96)code.append(s[85+inputt.at(i)-'[']);elseif(123=inputt.at(i)&&inputt.at(i)=125)code.append(s[91+inputt.at(i)-'{']);}coutcodeendl;ofstreamoutput;output.open(code.txt);outputcode;output.close();此处的编码为文件读入哈夫曼的译码stringyima;Node*head=node[TNUM-1];for(inti=0;icode.size();i++){if(code.at(i)=='1'&&head-rchild!=NULL)head=head-rchild;if(code.at(i)=='0'&&head-lchild!=NULL)head=head-lchild;if(head-lchild==NULL){yima.append(1,head-date);head=node[TNUM-1];}}coutthewordis:yimaendl;system(pause);return0;实验截图说明如果是文本输入的话要注意附录：完整代码简单键盘输入#includeiostream#includestringusingnamespacestd;#defineNUM27//字母数#defineTNUM53//#defineLTH15//编码最大长度structNode{chardate;intweight;Node*parent;Node*lchild;Node*rchild;};intmain(){charchars[]={'','a','b','c','d','e','f','g','h','i','j','k','l','m','n','o','p','q','r','s','t','u','v','w','x','y','z'};intweight[]={183,64,13,22,32,103,21,15,47,57,1,5,32,20,57,63,15,1,48,51,80,23,8,18,1,16,1};Node*node[TNUM];for(inti=0;iTNUM;i++){node[i]=newNode;}for(inti=0;iNUM;i++){node[i]-date=chars[i];node[i]-parent=NULL;node[i]-weight=weight[i];node[i]-lchild=NULL;node[i]-rchild=NULL;}for(inti=NUM;iTNUM;i++){node[i]-parent=NULL;node[i]-weight=-1;node[i]-lchild=NULL;node[i]-rchild=NULL;}for(inti=NUM;iTNUM;i++){intone=10000;inttwo=10000;inta=0;intb=0;intj=0;for(;ji;j++){if(node[j]-parent==NULL){if(node[j]-weight=one){two=one;b=a;one=node[j]-weight;a=j;}elseif(node[j]-weightone&&node[j]-weight=two){two=node[j]-weight;b=j;}}}node[j]-lchild=node[a];node[j]-rchild=node[b];node[a]-parent=node[j];node[b]-parent=node[j];node[j]-weight=node[a]-weight+node[b]-weight;}charHT[NUM][LTH];for(inti=0;iLTH;i++){for(intj=0;jNUM;j++){HT[j][i]='7';}}for(inti=0;iNUM;i++){intj=LTH-1;Node*m=node[i];while(m-parent!=NULL){Node*temp=m-parent;if(m==temp-lchild){HT[i][j]='0';}if(m==temp-rchild){HT[i][j]='1';}m=m-parent;j--;}}strings[NUM];for(inti=0;iNUM;i++){for(intj=0;jLTH;j++){if(HT[i][j]!='7'){s[i].append(1,HT[i][j]);}}}for(inti=0;iNUM;i++){coutnode[i]-dates[i]endl;}//编码stringcode;stringinput;coutpleaseentertheword:;cininput;for(inti=0;iinput.size();i++){code.append(s[input.at(i)-'a'+1]);}coutcodeendl;//译码stringyima;Node*head=node[TNUM-1];for(inti=0;icode.size();i++){if(code.at(i)=='1'&&head-rchild!=NULL)head=head-rchild;if(code.at(i)=='0'&&head-lchild!=NULL)head=head-lchild;if(head-lchild==NULL){yima.append(1,head-date);head=node[TNUM-1];}}coutthewordis:yimaendl;system(pause);return0;}全ascall码文本输入代码#includeiostream#includefstream#includestringusingnamespacestd;#defineNUM94//字符数#defineTNUM187//#defineLTH20//编码最大长度structNode{chardate;intweight;Node*parent;Node*lchild;Node*rchild;};intmain(){ifstreaminputm;inputm.open(wenben.txt);stringinputt;charc[1000000];if(inputm.fail()){coutFiledoesnotexistendl;