七：哈夫曼编码及应用
- 格式：doc
- 大小：68.50 KB
- 文档页数：7
广州中医药大学医学信息工程学院
实验报告
课程名称：数据结构与算法
专业班级：计算机科学与技术( )级
学生学号：
学生姓名：
实验名称：
实验成绩：
课程类别：必修 限选□公选□其它□
哈夫曼编码及应用
实验目的：了解哈夫曼树的应用，掌握哈夫曼树的构造方法及前缀码的应用。
实验性质：设计性，应用性。
实验步骤：
(1)输入一串字符，统计其中所有的不同字符及其个数，得出每个不同字符在文中出现
的频率。
(2)根据每个字符频率建立哈夫曼树，输出字符对应的编码。
[实验要求]
1、实验要求独立完成。
2、迟交或不交的或源代码雷同者一律不做作业登记评分。
[作业提交]
(实验报告写在此处)
给出含有6，8，11个字符的实例，统计他们的频率，画出哈夫曼树，并用算法验证结果。
代码写在此处
#include"stdio.h"
#include<malloc.h>
#define MAXNODE 20
#define MAXLEAF 30
#define MAXINT 234567
struct HtNode
{
int ww;
int parent,lchild,rchild;
};
struct HtTree
{
int root;
struct HtNode ht[MAXNODE];
};
typedef struct HtTree PHtTree;
PHtTree *huffman(int m,int *w);
void main()
{ char s[MAXNODE];
int m=0;char w[MAXNODE]; int count=0; int t=0;
int a[MAXNODE];
int *b;
char *code;
code=(char *)malloc(sizeof(char));
b=(int *)malloc(sizeof(int));
printf("请输入字符窜：\n");
for(int i=0;i<MAXNODE;i++){
scanf("%c ",&s[i]);
++count;
if(s[i]=='#')
break;
}
for(i=0;i<count-1;i++)
{ a[i]=0;b[m]=0;
for(int j=0;j<count-1;j++)
{
if(s[i]==s[j]&&i<=j)
{
a[i]=a[i]+1;
}
if(s[i]==s[j]&&i>j){
a[i]=a[i]+1;
s[i]=NULL;
}
}
if(s[i]!=NULL){
b[m]=a[i];
w[m]=s[i];
m++;
printf("%c的个数%d,频率为%f\n",w[m-1],b[m-1],(float)a[i]/(count-1));
}
}
PHtTree *pht;
pht=(PHtTree *)malloc(sizeof(PHtTree));
pht=huffman(m,b);
for(i=0;i<2*m-1;i++)
{
printf("%d",pht->ht[i].ww);
}
printf("\n");
for(i=0;i<m;i++)
{ int c;c=i;t=0;
int p=pht->ht[i].parent;
while(p!=-1)
{
if(pht->ht[p].lchild==c)
{
code[t]='0';
t++;
}
if(pht->ht[p].rchild==c)
{ code[t]='1';
t++;
}
pht->root--;
c=p;
p=pht->ht[p].parent;
}
printf("%c的编码是",w[i]);
for(int y=t-1;y>=0;y--)
printf("%c",code[y]);
printf("\n");
}
}
PHtTree *huffman(int m,int *w)//构造具有m各节点的哈弗曼树{
PHtTree *pht;
int i,j,x1,x2,m1,m2;
pht=(PHtTree *)malloc(sizeof(PHtTree));
if(pht==NULL){
printf("out of space!\n");
return pht;
}
for(i=0;i<2*m-1;i++){
pht->ht[i].lchild=-1;
pht->ht[i].rchild=-1;
pht->ht[i].parent=-1;
if(i<m)
pht->ht[i].ww=w[i];
else
pht->ht[i].ww=-1;
}
for(i=0;i<m-1;i++)
{
m1=MAXINT;
m2=MAXINT;
x1=-1;
x2=-1;
for(j=0;j<m+i;j++)
if(pht->ht[j].ww<m1&&pht->ht[j].parent==-1)
{
m2=m1;
x2=x1;
m1=pht->ht[j].ww;
x1=j;
}
else if(pht->ht[j].ww<m2&&pht->ht[j].parent==-1)
{
m2=pht->ht[j].ww;
x2=j;
}
pht->ht[x1].parent=m+i;
pht->ht[x2].parent=m+i;
pht->ht[m+i].ww=m1+m2;
pht->ht[m+i].lchild=x1;
pht->ht[m+i].rchild=x2;
pht->root=m+i;
}
return pht;
}
（作业提交说明：实验完成后，将此文档和相关的程序文件一并压缩后提交上来）。
