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

1、数据结构实验报告实验标题：赫夫曼编码和解码名称：学号：学科：实验名称：霍夫曼编码和解码实验问题说明：此实验要求以菜单的形式完成以下功能：1.输入消息字符串2.统计消息字符串中的每个字符及其发生次数3.创建霍夫曼树4.霍夫曼编码5.将通信翻译成比特流打印6.将比特流还原为消息数据结构说明：逻辑结构：这个实验可以用二叉树来实现，其逻辑结构是一对对应两个节点的形式。在实验过程中，我们也应用到了堆栈的概念上。存储结构：使用结构存储数据：Typedef structInt weightInt parent、lc、RC； htnode，* Huffman tree；Typedef struct LNode

2、Char * elemInt stacksizeInt top SqStack在Main函数中定义Huffman树，并实现这些不同的功能。方案结构说明：这个实验共构成了10个函数。1.void hufftree(Huffman tree ht，int n ，int mun)；此函数根据给定mun个权重构建huff man树，n保留num个权重。2.void select(Huffman tree ht，int n，int I，ints1，int S2)；此函数用于选择下标为s1，s2的HT1，i-1中parent为0且weight最小的两个节点。3.void Huffman coding(Hu

3、ffman tree ht，char * * HC，int n)；此函数从Huffman树HT中获取n个叶节点的hufman编码，并将其放入数组HC中。4.void coding(Huffman tree ht，char * * HC，int root，sq stacks)；该函数用于hurfman编码，按顺序遍历hurfman树HT，获取每个叶节点的编码字符串，将其放入数组HC，s是记录遍历路径的顺序堆栈，root是hurfman数组HT中根节点的位置下标。void init stack(sq stack s)；此函数用于初始化堆栈。6.void Pop(SqStack S，char e)；

4、此函数是堆栈操作。7.void推送(SqStack S，char e)；此函数是堆栈操作。8.int stack length(sq stack S)；此函数用于查找堆栈的长度并返回int类型的值。9.int Find(char a，char s，int num)；此函数用于查找文本字符串中字符a的位置。10 . int recover(Huffman tree ht，char * * HC，char string ，char a ，char b ，int n)；此函数用于将特定流还原为消息。调试分析：输入任意字符串。例如，输入welcometoustc:将产生以下结果：按照提示输入一个或多个

5、赫夫曼代码，如下所示：结果正确。如果输入1111:结果正确。实验完成！实验经验和收获：这次实验提高了对哈夫曼树的认识，同时加深了对二叉树的理解，更熟练地使用了栈，并改进了对数组的应用。源代码：#include#include#include#includeTypedef structInt weightInt parent、lc、RC； htnode，* Huffman tree；Typedef struct LNodeChar * elemInt stacksizeInt top SqStack#define size 20void hufftree(Huffman树ht，int n ，in

6、t mun)；void select(Huffman tree ht，int n，int I，ints1，int S2)；void Huffman coding(Huffman tree ht，char * * HC，int n)；void coding(Huffman tree ht，char * * HC，int root，sq stacks)；void init stack(sq stack S)；Void Pop(SqStack S，char e)；Void推送(SqStack S，char e)；int stack length(sq stack S)；Int Find(char a

7、，char s，int num)；Int recover (Huffman tree ht，char * * HC，char string ，char a ，char b ，int n)；Int main()Int I=0，n size=0，j=0，k=1，num=0；Charstring size=0，m size=0，a size=0，b size=0Char * * HC赫夫曼树ht；输入printf( message string : )。 n )；scanf(“% s”，string)；Strcpy(m，string)；While(stringj)If(stringj)！=#)ak=

8、字符串j；I=j；While(stringi)If(stringi=ak)字串I=#；nk；I；If(nk)！=0)Printf(“此消息中的字符%c出现次数为%dn”，ak，nk)；Numk；j；printf( Huffman tree : n )；赫夫特里(ht，n，num)；for(I=1)；I=2 * num-1；I)printf(“% d t % d t % d t % d t % d n”，ht I)。weight，ht I。parent，ht I。LC，ht I。RC)；printf( Huffman编码3360 n )；霍夫曼编码(ht，HC，num)；for(I=1)；I=n

9、umI)printf( 360% s n ，a I，HCI)；Printf(n此消息的港湾编码为：n。 n )；I=0；While(stringi)Printf (%s ，HC find (m I，a，num)；Printf(n输入Huffman编码： n )；scanf(“% s”，string)；If (recover (ht，HC，string，a，b，num)printf(“% s n”，b)；Else printf(代码无效！ n )；system( pause )；return 0；void hufftree(Huffman树ht，int n ，int num)Int i、m、s1

10、、S2；m=2 * num-1；ht=(Huffman tree)malloc(m 1)* size of(htnode)；for(I=1)；I=m；I)HTi。weight=i=num？nI:0；Ht I。LC=ht I。RC=ht I。parent=0；for(I=num 1；I=m；I)Select(HT、num、I、s1、S2)；HTi。lc=s1HTi。rc=s2Ht I。weight=ht S1。weight S2。weightHTs1。parent=HTs2。parent=I；void select(Huffman tree ht，int n，int I，ints1，ints2)

11、Int k、t；S1=S2=-1；k=1；While(s1=-1)If(HTk)。parent=0)S1=k；k；k=1；While(s2=-1|s2=s1)If(HTk)。parent=0)S2=k；k；If (ht S2)。weight=ht S1。weighttk！=s1k！=S2)S2=k；void Huffman coding(Huffman tree ht，char * * HC，int n)sq stack S；init stack(S)；HC=(char *)malloc(n 1)* size of(char *)；Coding(HT，HC，2*n-1，S)；void codi

12、ng(Huffman tree ht，char * * HC，int root，sqstacks)If(根！=0)If(HTroot)。lc=0)Push(S， 0)；HCroot=(char *)malloc(stack length(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)；Void InitStack(SqStack S)s . elem=(char *)malloc(s

13、ize * sizeof(char)；S.stacksize=sizes . top=-1；Void推送(SqStack S，char e)s . elems . top=e；Void Pop(SqStack S、char e)if(s . top=-1)return；e=e=s . elems . top-；ReturnInt StackLength(SqStack S)if(s . top=-1)return(0)；return(s . top)；Int Find(char a，char s，int num)int I；for(I=1)；I=numI)if(a=sI)return I；return 0；Int recover (Huffman tree 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(string