数据结构实验报告(哈夫曼树)

数据结构实验报告实验题目：Huffman编码与解码姓名：学号：院系：实验名称：Huffman编码与解码实验问题描述：本实验需要以菜单形式完成以下功能：1.输入电文串2.统计电文串中各个字符及其出现的次数3.构造哈弗曼树4.进行哈弗曼编码5.将电文翻译成比特流并打印出来6.将比特流还原成电文数据结构的描述：逻辑结构：本实验可用二叉树实现，其逻辑结构为一对二的形式，即一个结点对应两个结点。在实验过程中我们也应用到了栈的概念。存储结构：使用结构体来对数据进行存储：typedefstruct{intweight;intparent,lc,rc;}HTNode,*HuffmanTree;typedefstructLNode{char*elem;intstacksize;inttop;}SqStack;在main函数里面定义一个哈弗曼树并实现上述各种功能。程序结构的描述：本次实验一共构造了10个函数：1.voidHuffTree(HuffmanTree&HT,intn[],intmun);此函数根据给定的mun个权值构建哈弗曼树，n[]用于存放num个权值。2.voidSelect(HuffmanTree&HT,intn,inti,int&s1,int&s2);此函数用于在HT[1,i-1]中选择parent为0且weight为最小的两个结点，其下标分别为s1,s2.3.voidHuffmanCoding(HuffmanTreeHT,char**&HC,intn);此函数从哈弗曼树HT上求得n个叶子结点的哈弗曼编码并存入数组HC中。4.voidCoding(HuffmanTreeHT,char**HC,introot,SqStack&S)；此函数用于哈弗曼编码，先序遍历哈弗曼树HT，求得每个叶子结点的编码字符串，存入数组HC，S为一个顺序栈，用来记录遍历路径，root是哈弗曼数组HT中根结点的位置下标。5.voidInitStack(SqStack&S);此函数用于初始化一个栈。6.voidPop(SqStack&S,chare);此函数为出栈操作。7.voidPush(SqStack&S,chare);此函数为进栈操作。8.intStackLength(SqStackS);此函数用于求栈长，返回一个int型的值。9.intFind(chara,chars[],intnum);此函数用于查找字符a在电文串中的位置。10.intRecover(HuffmanTreeHT,char**HC,charstring[],chara[],charb[],intn);此函数用于将比特流还原成电文。调试分析：输入任意一个字符串，如输入welcometoustc:运行结果如下：按照提示输入任意一个或多个哈弗曼编码，如输入11111110101：结果正确。若输入一个11111：结果正确。实验完成！实验体会和收获：本次实验提高了对哈弗曼树的认识，同时加深了对二叉树的理解，在栈的运用上更加熟练，对数组的应用也有了提高。源代码：#includestdio.h#includestdlib.h#includemalloc.h#includestring.htypedefstruct{intweight;intparent,lc,rc;}HTNode,*HuffmanTree;typedefstructLNode{char*elem;intstacksize;inttop;}SqStack;#definesize20voidHuffTree(HuffmanTree&HT,intn[],intmun);voidSelect(HuffmanTree&HT,intn,inti,int&s1,int&s2);voidHuffmanCoding(HuffmanTreeHT,char**&HC,intn);voidCoding(HuffmanTreeHT,char**HC,introot,SqStack&S);voidInitStack(SqStack&S);voidPop(SqStack&S,chare);voidPush(SqStack&S,chare);intStackLength(SqStackS);intFind(chara,chars[],intnum);intRecover(HuffmanTreeHT,char**HC,charstring[],chara[],charb[],intn);intmain(){inti=0,n[size]={0},j=0,k=1,num=0;charstring[size]={0},m[size]={0},a[size]={0},b[size]={0};char**HC;HuffmanTreeHT;printf(请输入电文串:\n);scanf(%s,string);strcpy(m,string);while(string[j]){if(string[j]!='#')a[k]=string[j];i=j;while(string[i]){if(string[i]==a[k]){string[i]='#';n[k]++;}i++;}if(n[k]!=0){printf(该电文中字符%c出现次数为%d\n,a[k],n[k]);num++;k++;}j++;}printf(哈弗曼树:\n);HuffTree(HT,n,num);for(i=1;i=2*num-1;i++)printf(%d\t%d\t%d\t%d\n,HT[i].weight,HT[i].parent,HT[i].lc,HT[i].rc);printf(哈弗曼编码:\n);HuffmanCoding(HT,HC,num);for(i=1;i=num;i++){printf(%c:%s\n,a[i],HC[i]);}printf(\n该电文的哈弗曼编码为:\n);i=0;while(string[i])printf(%s,HC[Find(m[i++],a,num)]);printf(\n请输入哈弗曼编码：\n);scanf(%s,string);if(Recover(HT,HC,string,a,b,num))printf(%s\n,b);elseprintf(代码有误!\n);system(pause);return0;}voidHuffTree(HuffmanTree&HT,intn[],intnum){inti,m,s1,s2;m=2*num-1;HT=(HuffmanTree)malloc((m+1)*sizeof(HTNode));for(i=1;i=m;i++){HT[i].weight=i=num?n[i]:0;HT[i].lc=HT[i].rc=HT[i].parent=0;}for(i=num+1;i=m;i++){Select(HT,num,i,s1,s2);HT[i].lc=s1;HT[i].rc=s2;HT[i].weight=HT[s1].weight+HT[s2].weight;HT[s1].parent=HT[s2].parent=i;}}voidSelect(HuffmanTree&HT,intn,inti,int&s1,int&s2){intk,t;s1=s2=-1;k=1;while(s1==-1){if(HT[k].parent==0)s1=k;k++;}k=1;while(s2==-1||s2==s1){if(HT[k].parent==0)s2=k;k++;}if(HT[s2].weightHT[s1].weight){t=s2;s2=s1;s1=t;}for(k=1;ki;k++){if(HT[k].parent==0){if(HT[k].weightHT[s1].weight&&k!=s1&&k!=s2){s2=s1;s1=k;}elseif(HT[k].weightHT[s2].weight&&HT[k].weight=HT[s1].weight&&k!=s1&&k!=s2)s2=k;}}}voidHuffmanCoding(HuffmanTreeHT,char**&HC,intn){SqStackS;InitStack(S);HC=(char**)malloc((n+1)*sizeof(char*));Coding(HT,HC,2*n-1,S);}voidCoding(HuffmanTreeHT,char**HC,introot,SqStack&S){if(root!=0){if(HT[root].lc==0){Push(S,'\0');HC[root]=(char*)malloc((StackLength(S)));strcpy(HC[root],S.elem);Pop(S,'\0');}Push(S,'0');Coding(HT,HC,HT[root].lc,S);Pop(S,'\0');Push(S,'1');Coding(HT,HC,HT[root].rc,S);Pop(S,'\0');}}voidInitStack(SqStack&S){S.elem=(char*)malloc(size*sizeof(char));S.stacksize=size;S.top=-1;}voidPush(SqStack&S,chare){S.elem[++S.top]=e;}voidPop(SqStack&S,chare){if(S.top==-1)return;e=S.elem[S.top--];return;}intStackLength(SqStackS){if(S.top==-1)return(0);return(S.top);}intFind(chara,chars[],intnum){inti;for(i=1;i=num;i++)if(a==s[i])returni;return0;}intRecover(HuffmanTreeHT,char**HC,charstring[],chara[],charb[],intn){inti=0,j=0,k,m=0,t=0,h=0;chars[size];k=2*n-1;while(string[i]){if(!HT[k].lc&&!HT[k].rc){if(string[i]=='0'){s[j]='\0';k=2*n-1;t=1;j=0;}if(string[i]=='1'){s[j]='\0';k=2*n-1;t=1;j=0;}for(h=1;h=n;h++)if(!strcmp(HC[h],s))b[m++]=a[h];}else{if(string[i]=='0'){k=HT[k].lc;s[j++]='0';}if(string[i]=='1'){k=HT[k].rc;s[j]='1';j++;}t=0;}if(!t)i++;}if(!HT[k].lc&&!HT[k].rc){if(string[i-1]=='0'){s[j]='\0';k=2*n-1;j=0;}if(string[i-1]=='1'){s[j]='\0';k=2*n-1;t=1;j=0;}for(h=1;h=n;h++)if(!strcmp(HC[h],s))b[m++]=a[h];}b[m]='\0';if(k==2*n-1)return1;elsereturn0;}