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

《数据结构》

实验内容：

实 验 报 告 书

哈夫曼树与哈夫曼编码

第 1 页

201100814*** 计科111

***

数据结构实验报告 计科111 杨涛201100814***

前言

计算机编程中加工处理的对象是数据，而数据具有一定的组织结构，所以学习计算机编程仅仅了解计算机语言是不够的，还必须掌握数据的组织、存储和运算的一般方法，这便是数据结构课程中所研究的内容，也是我们编写计算机程序的重要基础，由于它对计算机学科起到承前启后的作用，因此本课程被列为计算机等相关专业最重要的专业基础课；同时数据结构是计算机专业教学的一门核心课程。计算机各领域都要用到各种数据结构，而且要从事计算机科学与技术工作，尤其是计算机领域的软件开发工作，必须具备较强的数据结构基础。

数据结构课程内容丰富、学习量大，实践性强；隐含在各部分内容中的方法和技术多；算法设计具有动态性和抽象性等特点，看懂听明白与掌握会应用之间有相当大的一段距离。所以学生必须多实践才能进一步加深对课程的理解，理解和掌握算法设计所需的方法和技术，为整个专业学习打下良好的基础。

第 2 页

数据结构实验报告 计科111 杨涛201100814***

一、实验目的

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、结合运行结果，对程序进行分析。

三、算法设计

1、程序所需头文件已经预处理宏定义以及变量如下

第 3 页

数据结构实验报告 计科111 杨涛201100814***

#include #include #include #include typedef struct node {

char ch; int data;

struct node *parent;

struct node *lchild,*rchild,*next; }hufnode;

typedef hufnode* linkhuf;

typedef struct HFcode {

char ch; int data; int code[20]; int top; }tagHFcode;

linkhuf insert(linkhuf root,linkhuf s) {

linkhuf p1,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; else p1->next = s; }

return root; }

2、创建哈夫曼树

void createhuffman(linkhuf *root) {

linkhuf s,r1,rr;

while(*root && (*root)->next)

第 4 页

数据结构实验报告 计科111 杨涛201100814***

{

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); } }

void inorder(linkhuf t) {

if(t) {

inorder(t->lchild); printf(\"%5d\ inorder(t->rchild); } }

3、哈夫曼编码

void HFcoding(linkhuf root,linkhuf temp,tagHFcode HFcode[],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; else

HFcode[(*leaftop)].code[HFcode[(*leaftop)].top] = 1; HFcode[(*leaftop)].top++; temp = temp->parent;

第 5 页

数据结构实验报告 计科111 杨涛201100814***

}

(*leaftop)++; }

HFcoding(root->lchild,temp,HFcode,leaftop); HFcoding(root->rchild,temp,HFcode,leaftop); } }

4、输出求得的哈夫曼编码

void OutCoding(tagHFcode HFcode[],int leaftop) {

int i,j=0;

for(i=0;iprintf(\"%d\\ j = HFcode[i].top - 1; while(j>=0 ) {

printf(\"%d\ j--; }

printf(\"\\n\"); } }

四、调试与测试 我们开始测试数据：

如输入：A B C D E F G H

输出结果如图

第 6 页

数据结构实验报告 计科111 杨涛201100814***

说明我们成功的完成了程序。

五、总结

通过做这次实验，发现自己在数据结构这门课中还有很多不足有很多知识还没掌握，所以在写程序的时候出现了很多的错误，及还有很多的知识不以灵活运用，特别是对栈和队列的操作问题。

因为以前C语言没有掌握好，所以这次做本次实验还是有点吃力，刚开始完全没有思，后来经过查找资料，在自己的努力下和同学的帮助下，终于完了本次实验。

此次实验发现的自己的不足，我相信在以后的学习中，我会更加的努力。

六、源代码

#include

#include #include #include typedef struct node {

char ch; int data;

struct node *parent;

struct node *lchild,*rchild,*next; }hufnode;

typedef hufnode* linkhuf;

第 7 页

数据结构实验报告 计科111 杨涛201100814***

typedef struct HFcode {

char ch; int data; int code[20]; int top; }tagHFcode;

linkhuf insert(linkhuf root,linkhuf s) {

linkhuf p1,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; else p1->next = s; }

return root; }

void createhuffman(linkhuf *root) {

linkhuf s,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;

第 8 页

数据结构实验报告 计科111 杨涛201100814***

*root = insert(*root,s); } }

void inorder(linkhuf t) {

if(t) {

inorder(t->lchild); printf(\"%5d\ inorder(t->rchild); } }

void HFcoding(linkhuf root,linkhuf temp,tagHFcode HFcode[],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; else

HFcode[(*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); } }

//输出求得的哈夫曼编码

void OutCoding(tagHFcode HFcode[],int leaftop) {

int i,j=0;

for(i=0;i第 9 页

数据结构实验报告 计科111 杨涛201100814***

printf(\"%d\\ j = HFcode[i].top - 1; while(j>=0 ) {

printf(\"%d\ j--; }

printf(\"\\n\"); } }

int main() {

tagHFcode HFcode[20]; linkhuf f = NULL; linkhuf temp = NULL; linkhuf p[6]; int i; int a[20]; char ch;

int leaftop = 0;

printf(\"请输入各节点的节点值和权值：\\n\"); for(i=0;i<7;i++) {

p[i] = (linkhuf)malloc(sizeof(hufnode)); scanf(\"%c\ getchar();

scanf(\"%d\ p[i]->lchild = NULL; p[i]->rchild = NULL; p[i]->next = NULL; f = insert(f,p[i]); }

createhuffman(&f); printf(\"\\n\\n\\n\");

printf(\"中序遍历hufman树的结果为：\\n\"); inorder(f);

HFcoding(f,temp,HFcode,&leaftop); printf(\"\\nhuffman编码为:\\n\"); OutCoding(HFcode,leaftop); printf(\"\\n\"); system(\"pause\"); return 0; }

第 10 页