数据结构实验报告

1、数据结构实验报告实验题目：Huffman编码与解码学号:院系：实验名称：Huffman编码与解码实验问题描述：本实验需要以菜单形式完成以下功能：输入电文串统计电文串中各个字符及其出现的次数构造哈弗曼树进行哈弗曼编码将电文翻译成比特流并打印出来将比特流还原成电文数据结构的描述：逻辑结构：本实验可用二叉树实现，其逻辑结构为一对二的形式，即一个结点对应两个结点。在实验过程中我们也应用到了栈的概念。存储结构：使用结构体来对数据进行存储：typedef structint weight;int parent,lc,rc;HTNode,*HuffmanTree;typedef struct LNodech

2、ar *elem;int stacksize;int top;SqStack;在main函数里面定义一个哈弗曼树并实现上述各种功能。程序结构的描述：本次实验一共构造了 10个函数：void HuffTree(HuffmanTree &HT,int n,int mun);此函数根据给定的mun个权值构建哈弗曼树，n用于存放num个权值。void Select(HuffmanTree &HT,int n,int i,int &s1,int &s2);此函数用于在HT1,i-1 中选择parent为0且weight为最小的两个结点，其 下标分别为s1,s2.void HuffmanCoding(Hu

3、ffmanTree HT,char *&HC,int n);此函数从哈弗曼树HT上求得n个叶子结点的哈弗曼编码并存入数组HC 中。void Coding(HuffmanTree HT,char *HC,int root,SqStack &S)；此函数用于哈弗曼编码，先序遍历哈弗曼树HT，求得每个叶子结点的编码 字符串，存入数组HC, S为一个顺序栈，用来记录遍历路径，root是哈弗曼数 组HT中根结点的位置下标。void InitStack(SqStack &S);此函数用于初始化一个栈。void Pop(SqStack &S,char e);此函数为出栈操作。void Push(SqStac

4、k &S,char e);此函数为进栈操作。8.int StackLength(SqStack S);此函数用于求栈长，返回一个int型的值。9.int Find(char a,char s,int num);此函数用于查找字符a在电文串中的位置。10.int Recover(HuffmanTree HT,char *HC,char string,char a,char b,int n);此函数用于将比特流还原成电文。调试分析：输入任意一个字符串，如输入welcometoustc:运行结果如下：习,习,习,习,习,习,习,习,习,次次次次次次次次次现现现现现现现现现rrrrrr出出出出出出出出

5、出O4XXXXXX于: TOC o 1-5 h z 4164io12141&16is哈弗曼编码： bl : 1110 e : 911 1 : 1111 E : 180 : 101 n - 000 t : 119 LL : 001 S : 010该电文的哈弗景编码为： 11100111111100101000011110101001010110100 请输入哈弗曼编码：按照提示输入任意一个或多个哈弗曼编码，如输入11111110101 :请输入哈弗景编码:11111110101 1U0结果正确。若输入一个11111 :请输入哈弗景编码,11111mi?结果正确。实验完成

6、！实验体会和收获:本次实验提高了对哈弗曼树的认识，同时加深了对二叉树的理解，在栈的运用上 更加熟练，对数组的应用也有了提高。源代码：#include#include#include#includetypedef structint weight;int parent,lc,rc;HTNode,*HuffmanTree;typedef struct LNode char *elem;int stacksize;int top;SqStack;#define size 20void HuffTree(HuffmanTree &HT,int n,int mun);void Select(Huffma

7、nTree &HT,int n,int i,int &s1,int &s2);void HuffmanCoding(HuffmanTree HT,char *&HC,int n);void Coding(HuffmanTree HT,char *HC,int root,SqStack &S);void InitStack(SqStack &S);void Pop(SqStack &S,char e);void Push(SqStack &S,char e);int StackLength(SqStack S);int Find(char a,char s,int num);int Recove

8、r(HuffmanTree HT,char *HC,char string,char a,char b,int n);int main()int i=0,nsize=0,j=0,k=1,num=0;char stringsize=0,msize=0,asize=0,bsize=0;char* HC;HuffmanTree HT;printf(请输入电文串:n);scanf(%s,string);strcpy(m,string);while(stringj)if(stringj! = #) ak=stringj;i=i；while(stringi)if(stringi=ak)stringi =

9、#;nk + + ;i+；if(nk!=0)printf(该电文中字符%c出现次数为%dn,ak,nk);num+ + ;k+ + ;j + + ;printf(哈弗曼树:n);HuffTree(HT,n,num);for(i = 1;i=2*num-1;i +)printf(%dt%dt%dt%dn,HTi.weight,HTi.parent,HTi.lc,HTi.rc);printf(哈弗曼编码:n);HuffmanCoding(HT,HC,num);for(i = 1;i = num;i +)printf(%c : %sn,ai,HCi);printf(n该电文的哈弗曼编码为:n);i=

10、0;while(stringi)printf(%s,HCFind(mi + +,a,num);printf(n请输入哈弗曼编码：n);scanf(%s,string);if(Recover(HT,HC,string,a,b,num) printf(%sn,b);else printf(代码有误!n”);system(pause);return 0;void HuffTree(HuffmanTree &HT,int n,int num)int i,m,s1,s2;m=2*num-1;HT=(HuffmanTree)malloc(m+1)*sizeof(HTNode);for(i = 1;i =

11、m;i+)HTi.weight=i = num?ni:0;HTi.lc=HTi.rc=HTi.parent=0;for(i = num+1;i = m;i +)Select(HT,num,i,s1,s2);HTi.lc=s1;HTi.rc=s2;HTi.weight=HTs1.weight+HTs2.weight;HTs1.parent=HTs2.parent=i;void Select(HuffmanTree &HT,int n,int i,int &s1,int &s2)int k,t;s1=s2=-1;k=1;while(s1= = -1)if(HTk.parent=0)s1=k;k+;

12、k=1;while(s2= = -1|s2=s1)if(HTk.parent=0)s2=k;k+ + ;if(HTs2.weightHTs1.weight)t=s2;s2=s1;s1=t;for(k=1;ki;k+)if(HTk.parent=0)if(HTk.weightHTs1.weight&k!=s1&k!二s2)s2=s1;s1=k;elseif(HTk.weight = HTs1.weight&k!=s1&k!二s2) s2=k;void HuffmanCoding(HuffmanTree HT,char *&HC,int n)SqStack S;InitStack(S);HC=(c

13、har*)malloc(n+1)*sizeof(char*);Coding(HT,HC,2*n-1,S);void Coding(HuffmanTree HT,char *HC,int root,SqStack &S)if(root!=0)if(HTroot.lc=0)Push(S,0);HCroot=(char*)malloc(StackLength(S);strcpy(HCroot,S.elem);Pop(S,0);Push(S,0);Coding(HT,HC,HTroot.lc,S);Pop(S,0);Push(S,1);Coding(HT,HC,HTroot.rc,S);Pop(S,0

14、);void InitStack(SqStack &S)S.elem=(char *)malloc(size*sizeof(char);S.stacksize二size;S.top=-1;void Push(SqStack &S,char e)S.elem+S.top=e;void Pop(SqStack &S,char e)if(S.top= = -1) return;e=S.elemS.top-;return;int StackLength(SqStack S)if(S.top= = -1) return(0);return(S.top);int Find(char a,char s,in

15、t num)int i;for(i = 1;i = num;i +)if(a=si) return i;return 0;int Recover(HuffmanTree HT,char *HC,char string,char a,char b,int n)int i=0,j=0,k,m=0,t=0,h=0;char ssize;k=2*n-1;while(stringi)if(!HTk.lc&!HTk.rc)if(stringi = = 0) (sj=0;k=2*n-1;t=1;j=0;)if(stringi = = 1)sj=0;k=2*n-1;t=1;j=0;for(h=1;h = n;h +)if(!strcmp(HCh,s)bm+=ah;elseif(stringi = = 0) (k=HTk.lc;sj +