数据结构实验三.doc

华北水利水电学院 数据结构 实验报告
20 10 ～20 11 学年 第 一 学期 2008级 计算机 专业
实验三 树的应用
一、 实验目的：
1．掌握二叉树基本操作；
2．掌握构造哈夫曼树及哈夫曼编码的方法
二、 实验要求：
1．C完成算法设计和程序设计并上机调试通过。
2．撰写实验报告，提供实验结果和数据。
3．写出算法设计小结和心得。
三、 实验内容：
1．采用二叉链表存储结构，编写程序实现按层次遍历二叉树。
2．从键盘输入若干字符，统计每个字符出现的频率，将字符出现的频率作为结点的权值，建立哈夫曼树，然后对各个字符进行哈夫曼编码，最后打印输出每个字符及对应的哈夫曼编码。
一个完整的哈夫曼编码/译码系统应具有以下功能：
（1）初始化：从终端读入一段英文字符，统计每个字符出现的频率，建立哈夫曼树；
（2）编码：利用建好的哈夫曼树对各字符进行编码，并输出结果（要求输出哈夫曼树存储结构的初态、终态及字符的哈夫曼编码）；
（3）译码：利用已建立的哈夫曼编码对输入的字符序列进行译码，并输出结果；（选做）
（4）解码：利用哈夫曼编码，对任意输入的0、1序列能正确解码，并输出结果。（选做）
四、 程序源代码：

第 5 页 共 5 页
（1）#include "stdio.h"
#include "conio.h"
#include "stdlib.h"

typedef char TElemType;
typedef struct BiTNode
{
TElemType data;
struct BiTNode *lchild,*rchild;
}BiTNode,*BiTree;

/*创建二叉树*/
void create(BiTree *T)
{
char c;
scanf("%c",&c);
if(c!='#')
{
*T=(BiTree)malloc(sizeof(BiTNode));
(*T)->data=c;
create(&((*T)->lchild));
create(&((*T)->rchild));
}
else *T=NULL;
}
/*按层遍历*/
void Traverse(BiTree T)
{
BiTree Queue[20];
BiTree p;
int front=0,rear=0;
if(T)
{
p=T;
Queue[rear]=p;
rear=(rear+1)%20;
while(front!=rear)
{
p=Queue[front];
printf("%c",p->data);
front=(front+1)%20;
if(p->lchild)
{
Queue[rear]=p->lchild;
rear=(rear+1)%20;
}
if(p->rchild)
{
Queue[rear]=p->rchild;
rear=(rear+1)%20;
}
}
}
}
main()
{
BiTree T;
create(&T);
Traverse(T);
getch();
}
（2）#include<stdio.h>
#include<conio.h>
#include<iostream.h>
#include<string.h>
#include<stdlib.h>

#define MAXVALUE 10000
#define MAXLEAF 30
#define MAXNODE MAXLEAF*2-1
#define MAXBIT 50

typedef struct node /*结点类型定义*/
{
char letter;
int weight;
int parent;
int lchild;
int rchild;
}HNodeType;

typedef struct /*编码类型定义*/
{
char letter;
int bit[MAXBIT];
int start;
}HCodeType;

typedef struct /*输入符号的类型*/
{
char s;
int num;
}lable;

void HuffmanTree(HNodeType HuffNode[],int n,lable a[])
{
int i,j,m1,m2,x1,x2,temp1;
char temp2;
for (i=0;i<2*n-1;i++) /*结点初始化*/
{
HuffNode[i].letter=0;
HuffNode[i].weight=0;
HuffNode[i].parent=-1;
HuffNode[i].lchild=-1;
HuffNode[i].rchild=-1;
}
for (i=0;i<n-1;i++)

for (j=i+1;j<n-1;j++)
if (a[j].num>a[i].num)
{
temp1=a[i].num;
a[i].num=a[j].num;
a[j].num=temp1;
temp2=a[i].s;
a[i].s=a[j].s;
a[j].s=temp2;
}

for (i=0;i<n;i++)
{
HuffNode[i].weight=a[i].num;
HuffNode[i].letter=a[i].s;
}
for (i=0;i<n-1;i++) /*构造huffman树*/
{
m1=m2=MAXVALUE;
x1=x2=0;
for (j=0;j<n+i;j++)
{
if (HuffNode[j].parent==-1&&HuffNode[j].weight<m1)
{
m2=m1;
x2=x1;
m1=HuffNode[j].weight;
x1=j;
}
else if (HuffNode[j].parent==-1&&HuffNode[j].weight<m2)
{
m2=HuffNode[j].weight;
x2=j;
}
}
HuffNode[x1].parent=n+i;
HuffNode[x2].parent=n+i;
HuffNode[n+i].weight=HuffNode[x1].weight+HuffNode[x2].weight;
HuffNode[n+i].lchild=x1;
HuffNode[n+i].rchild=x2;
}
}

void HuffmanCode(int n,lable a[])
{
HNodeType HuffNode[MAXNODE];
HCodeType HuffCode[MAXLEAF],cd;
int i,j,c,p;

HuffmanTree(HuffNode,n,a);

for (i=0;i<n;i++) /*按结点位置进行编码*/
{
cd.start=n-1;
c=i;
p=HuffNode[c].parent;
while (p!=-1)
{
if (HuffNode[p].lchild==c)
cd.bit[cd.start]=0;
else cd.bit[cd.start]=1;
cd.start--;
c=p;
p=HuffNode[c].parent;
}
for (j=cd.start+1;j<n;j++) /*储存编码*/
HuffCode[i].bit[j]=cd.bit[j];
HuffCode[i].start=cd.start;
}
for (i=0;i<n;i++)
{
HuffCode[i].letter=HuffNode[i].letter;
printf(" %c ",HuffCode[i].letter);

for (j=HuffCode[i].start+1;j<n;j++)
printf("%d",HuffCode[i].bit[j]);
printf("\n");
}
}

int main()
{
lable data[30];
char s[100],*p;
int i,count=0;
for (;;)
{
cout<<" / 求哈夫曼编码,输入end结束 /"<<endl;
printf(" 输入字符:");
scanf("%s",s);
if (!strcmp(s,"end"))
exit(0);
for (i=0;i<30;i++)
{
data[i].s=0;
data[i].num=0;
}
p=s;
while (*p) /*计算字符个数与出现次数*/
{
for (i=0;i<=count+1;i++)
{
if (data[i].s==0)
{
data[i].s=*p;
data[i].num++;
count++;
break;
}
else if (data[i].s==*p)
{
data[i].num++;
break;
}
}
p++;
}
printf("\n");
printf(" 不同字符数:%d\n",count);

for (i=0;i<count;i++)
{
printf(" %c ",data[i].s);
printf("weight:%d\n",data[i].num);
}
HuffmanCode(count,data);
count=0;
}
getch();
}

五、 测试结果
（1）

（2）