数据实验报告书-哈夫曼树与哈夫曼编码

数据结构实验报告 计科111杨涛201100814***第第页《数据结构》实验报告书实验内容：哈夫曼树与哈夫曼编码201100814***计科111 ***前言计算机编程中加工处理的对象是数据，而数据具有一定的组织结构，所以学习计算机编程仅仅了解计算机语言是不够的，还必须掌握数据的组织、存储和运算的一般方法，这便是数据结构课程中所研究的内容，也是我们编写计算机程序的重要基础，由于它对计算机学科起到承前启后的作用，因此本课程被列为计算机等相关专业最重要的专业基础课；同时数据结构是计算机专业教学的一门核心课程。计算机各领域都要用到各种数据结构，而且要从事计算机科学与技术工作，尤其是计算机领域的软件开发工作，必须具备较强的数据结构基础。数据结构课程内容丰富、学习量大，实践性强；隐含在各部分内容中的方法和技术多；算法设计具有动态性和抽象性等特点，看懂听明白与掌握会应用之间有相当大的一段距离。所以学生必须多实践才能进一步加深对课程的理解，理解和掌握算法设计所需的方法和技术，为整个专业学习打下良好的基础。

一、实验目的1、使学生熟练掌握哈夫曼树的生成算法。2、熟练掌握哈夫曼编码的方法。二、实验内容[问题描述]已知n个字符在原文中出现的频率，求它们的哈夫曼编码。[基本要求]1.初始化：从键盘读入n个字符，以及它们的权值，建立Huffman树。（具体算法可参见教材P147的算法6.12）

2.编码：根据建立的Huffman树，求每个字符的Huffman编码。对给定的待编码字符序列进行编码。

[选作内容]１.译码：利用已经建立好的Huffman树，对上面的编码结果译码。译码的过程是分解电文中的字符串，从根结点出发，按字符’0’和’1’确定找左孩子或右孩子，直至叶结点，便求得该子串相应的字符。4.打印

Huffman树。［测试数据］利用教材P.148例6－2中的数据调试程序。可设8种符号分别为A,B,C,D,E,F,G,H。编/译码序列为“CFBABBFHGH”(也可自己设定数据进行测试)。［实验前的准备工作］1、掌握树的逻辑结构。2、掌握哈夫曼树的定义及生成算法。3、掌握哈夫曼编码的方法。［实验报告要求］1、实验报告要按照实验报告格式规范书写。2、实验上要写出多批测试数据的运行结果。3、结合运行结果，对程序进行分析。算法设计程序所需头文件已经预处理宏定义以及变量如下#include<stdio.h>#include<stdlib.h>#include<conio.h>#include<string.h>typedefstructnode{charch;intdata;structnode*parent;structnode*lchild,*rchild,*next;}hufnode;typedefhufnode*linkhuf;typedefstructHFcode{charch;intdata;intcode[20];inttop;}tagHFcode;linkhufinsert(linkhufroot,linkhufs){linkhufp1,p2;if(root==NULL)root=s;else{p1=NULL;p2=root;while(p2&&p2->data<s->data){p1=p2;p2=p2->next;}s->next=p2;if(p1==NULL)root=s;elsep1->next=s;}returnroot;}创建哈夫曼树voidcreatehuffman(linkhuf*root){linkhufs,r1,rr;while(*root&&(*root)->next){r1=*root;rr=(*root)->next;*root=rr->next;s=(linkhuf)malloc(sizeof(hufnode));s->next=NULL;s->data=r1->data+rr->data;s->parent=NULL;s->lchild=r1;s->rchild=rr;r1->parent=s;rr->parent=s;r1->next=rr->next=NULL;*root=insert(*root,s);}}voidinorder(linkhuft){if(t){inorder(t->lchild);printf("%5d",t->data);inorder(t->rchild);}}哈夫曼编码voidHFcoding(linkhufroot,linkhuftemp,tagHFcodeHFcode[],int*leaftop){if(root!=NULL){if(root->lchild==NULL&&root->rchild==NULL){temp=root;HFcode[(*leaftop)].top=0;HFcode[(*leaftop)].ch=root->ch;HFcode[(*leaftop)].data=root->data;//HFcode[(*leaftop)].data=root->data;//HFcode[(*leaftop)].ch=root->ch;while(temp->parent!=NULL){if(temp->parent->lchild==temp)HFcode[(*leaftop)].code[HFcode[(*leaftop)].top]=0;elseHFcode[(*leaftop)].code[HFcode[(*leaftop)].top]=1;HFcode[(*leaftop)].top++;temp=temp->parent;}(*leaftop)++;}HFcoding(root->lchild,temp,HFcode,leaftop);HFcoding(root->rchild,temp,HFcode,leaftop);}}输出求得的哈夫曼编码voidOutCoding(tagHFcodeHFcode[],intleaftop){inti,j=0;for(i=0;i<leaftop;i++){printf("%d\t",HFcode[i].data);j=HFcode[i].top-1;while(j>=0){printf("%d",HFcode[i].code[j]);j--;}printf("\n");}}调试与测试我们开始测试数据：如输入：ABCDEFGH输出结果如图说明我们成功的完成了程序。五、总结通过做这次实验，发现自己在数据结构这门课中还有很多不足有很多知识还没掌握，所以在写程序的时候出现了很多的错误，及还有很多的知识不以灵活运用，特别是对栈和队列的操作问题。因为以前C语言没有掌握好，所以这次做本次实验还是有点吃力，刚开始完全没有思，后来经过查找资料，在自己的努力下和同学的帮助下，终于完了本次实验。此次实验发现的自己的不足，我相信在以后的学习中，我会更加的努力。源代码#include<stdio.h>#include<stdlib.h>#include<conio.h>#include<string.h>typedefstructnode{charch;intdata;structnode*parent;structnode*lchild,*rchild,*next;}hufnode;typedefhufnode*linkhuf;typedefstructHFcode{charch;intdata;intcode[20];inttop;}tagHFcode;linkhufinsert(linkhufroot,linkhufs){linkhufp1,p2;if(root==NULL)root=s;else{p1=NULL;p2=root;while(p2&&p2->data<s->data){p1=p2;p2=p2->next;}s->next=p2;if(p1==NULL)root=s;elsep1->next=s;}returnroot;}voidcreatehuffman(linkhuf*root){linkhufs,r1,rr;while(*root&&(*root)->next){r1=*root;rr=(*root)->next;*root=rr->next;s=(linkhuf)malloc(sizeof(hufnode));s->next=NULL;s->data=r1->data+rr->data;s->parent=NULL;s->lchild=r1;s->rchild=rr;r1->parent=s;rr->parent=s;r1->next=rr->next=NULL;*root=insert(*root,s);}}voidinorder(linkhuft){if(t){inorder(t->lchild);printf("%5d",t->data);inorder(t->rchild);}}voidHFcoding(linkhufroot,linkhuftemp,tagHFcodeHFcode[],int*leaftop){if(root!=NULL){if(root->lchild==NULL&&root->rchild==NULL){temp=root;HFcode[(*leaftop)].top=0;HFcode[(*leaftop)].ch=root->ch;HFcode[(*leaftop)].data=root->data;while(temp->parent!=NULL){if(temp->parent->lchild==temp)HFcode[(*leaftop)].code[HFcode[(*leaftop)].top]=0;elseHFcode[(*leaftop)].code[HFcode[(*leaftop)].top]=1;HFcode[(*leaftop)].top++;temp=temp->parent;}(*leaftop)++;}HFcoding(root->lchild,temp,HFcode,leaftop);HFcoding(root->rchild,temp,HFcode,leaftop);}}//输出求得的哈夫曼编码voidOutCoding(tagHFcodeHFcode[],intleaftop){inti,j=0;for(i=0;i<leaftop;i++){printf("%d\t",HFcode[i].data);j=HFcode[i].top-1;while(j>=0){printf("%d",HFcode[i].code[j]);j--;}printf("\n");}}intmain(){tagHFcodeHFcode[20];linkhuff=NULL;linkhuftemp=NUL