数据结构实验报告.docx
《数据结构实验报告.docx》由会员分享，可在线阅读，更多相关《数据结构实验报告.docx（8页珍藏版）》请在冰点文库上搜索。
数据结构实验报告
数据结构实验报告
题目与内容
哈夫曼（Huffman）树与哈夫曼码
1.输入一个文本，统计各字符出现的频度，输出结果;
2.使用二叉链表或三叉链表作存储结构，构造哈夫曼（Huffman）树;
3.确定和输出各字符的哈夫曼码;
4.输入一个由0和1组成的代码序列，翻译并输出与之对应的文本;
二、数据结构及存储结构
在这个程序中我用了三叉链表tree作为哈夫曼树的结构：
左、右儿子和父亲
节点;并且在开始，我还用此结构生成了单链表，用来存储读取的字符。
编码的时候，我把编码放在栈结构stack中，然后逆序输出即为哈夫曼编码。
存放叶节点时用到了指针数组。
structtree（）{
chardata;
intm,sign;
structtree*lchild,*rchild,*parent;
}
structstack{
intdata;
structstack*next;
}
算法设计思想
先调用frequency函数读取字符，创建链表来存储字符及其相关信息;同时把字符放进数组中进行备份，因为后面编码时要用到这些字符（它们就是叶节点）。
然后遍历这个链表输出个字符的频度。
接着调用ctree函数来生成哈夫曼树。
在ctree函数中，首先对刚才那个链表按照频度排序，变成频度递增链表;然后取其前两个节点作为新建哈夫曼树的左右儿子（注：
左儿子的频度 心得体会
这次编程，从开始编到测试成功，我一共花了四天。
这主要是因为之前我花了不少时间看书，把数据结构和存储结构都想好了，还看了大量程序，不管是相关还是不相关的。
例如，有一个困扰我很久的问题：
当询问是否继续时，输入y就继续，否则跳出;以前用getchar要等按了回车才进行判断，如果按了好几个y，则后面几个y被当成以后的输入处理了，这样就会出错。
然而我在一个程序中看到了getche这个指令解决了这个问题，它不需等回车就进行处理。
另外在定义哈夫曼树结构时，我加了个sign变量来标志它是左子树还是右子树，这样后面编码时就很方便。
这次编程使我认识到：
要重视细节，虽然很小，但是它会使程序不能运行或出错。
这个程序中我由于把‘y’写成y，结果浪费了我半天的时间去查错。
五、程序清单
#include
#include
structtree{/*定义哈夫曼树的结构*/
chardata;/*存放字符*/
intm,sign;/*m存放字符出现的频率sign是左（0）或右
（1）儿子的标志*/
structtree*lchild,*rchild,*parent;/*左儿子右儿子父节点*/
};
structstack{/*定义栈的结构*/
intdata;
structstack*next;
};
structtree*ps,*root,*head;
/*数组存放字符root为二叉树的根结点head为链表的头节点*/
intsize;/*标志字符个数*/
/*************************统计各字符出现的频度***********************/
voidfrequency（）{
structtree*r,*p,*q;
intn,l,j=1;
/*录入第一个字符并创建链表*/
clrscr（）;/*清屏*/
head=NULL;
printf（"InputthetextendofENTER:
"）;
n=get）;
if（n!
=''）{
p=（structtree*）malloc（sizeof（structtree））;
p->data=n;
p->m=1;
p->sign=-1;
p->lchild=NULL;
p->rchild=NULL;
p->parent=NULL;
head=p;
ps=p;/*把字符（后面的叶节点）放进数组备份*/
n=get）;
}
/*录入其它字符*/
while（n!
=''）{
l=0;r=p;
for（q=head;q!
=NULL&&l==0;q=q->parent）{
if（q->data==n）{/*检查是否和已经录入的字符相同*/
q->m++;/*如果相同则此字符的频度变量加1*/
l=1;
}
r=p;
}
if（l==0）{/*如果不同则录入并加入链表*/
p=（structtree*）malloc（sizeof（structtree））;
p->data=n;
p->m=1;
p->sign=-1;
p->lchild=NULL;
p->rchild=NULL;
p->parent=NULL;
r->parent=p;
ps=p;/*把字符（后面的叶节点）放进数组备份*/
j++;
}
n=get）;
}
/*输出字符的频度*/
p=head;
size=0;
printf（"Frequencyasfollows:
charactersfrequency"）;
while（p!
=NULL）{
printf（"%c%d",p->data,p->m）;
p=p->parent;
size++;/*统计字符的个数*/
}
}
/****************************生成树**********************************/
voidctree（）{
structtree*t,*r,*p,*e,*q;
intn;
/****给链表排序生成频度递增链表*****/
for（p=head;p->parent!
=NULL;p=p->parent）{
for（q=p->parent;q!
=NULL;q=q->parent）{
if（p->m>q->m）{
n=q->m;/*交换信息*/
q->m=p->m;
p->m=n;
n=q->data;
q->data=p->data;
p->data=n;
}
}
}
/***********生成哈夫曼树***********/
p=head;
while（p!
=NULL&&p->parent!
=NULL）{
/*取递增链表前两个为左右儿子生成哈夫曼树*/
q=p->parent->parent;/*然后把它们从链表中删掉*/
t=（structtree*）malloc（sizeof（structtree））;
t->lchild=p;/*频度:
左儿子 t->rchild=p->parent;
t->m=p->m+p->parent->m;
t->rchild->parent=t;
t->rchild->sign=1;
t->lchild->parent=t;
t->lchild->sign=0;
t->sign=-1;
root=t;/*root为根结点*/
root->parent=NULL;
if（q!
=NULL）{/*判断链表是否为空*/
head=q;
r=head;
e=head;/*把新生成的根结点插入到链表中去*/
if（head->m>t->m）{/*判断是否为头节点*/
t->parent=q;
head=t;
}
else{
r=r->parent;
while（r!
=NULL&&r->mm）{
e=r;
r=r->parent;
}
t->parent=r;
e->parent=t;
}
p=head;
root=t;
}
elsebreak;/*如果链表为空则结束*/
}
}
/******************************编码******************************/
voidccode（）{
structtree*p,*q;
intj;
printf（"codesasfollows:
characterscode"）;
for（j=0;j
head=NULL;
p=ps;/*从叶到根求编码*/
printf（"%c",p->data）;
while（p->parent!
=NULL）{/*把编码存入栈中*/
q=（structstack*）malloc（sizeof（structstack））;
q->data=p->sign;
q->next=head;
head=q;
p=p->parent;
}
q=head;/*输出编码*/
while（q!
=NULL）{
printf（"%d",q->data）;
q=q->next;
}
printf（""）;
}
}
/******************************译码******************************/
chartranslate（）{
structtree*r,*p,*q;
intn;
charc;
/*读取01序列*/
Error:
printf（"Inputcodesconsistof0and1（endofENTER）:
"）;
n=get）;
if（n!
=''）{/*读取第一个字符*/
p=（structtree*）malloc（sizeof（structtree））;
p->data=n;
p->next=NULL;
head=p;
r=head;
n=get）;
}
while（n!
=''）{/*读取其它字符*/
p=（structtree*）malloc（sizeof（structtree））;
p->data=n;
p->next=NULL;
r->next=p;
r=p;
n=get）;
}
p=head;
while（p!
=NULL）{/*判断是否右非法字符*/
if（p->data!
='0'&&p->data!
='1'）{
printf（"Thereareilleagecharactersinyourcodes!
"）;
gotoError;
}
p=p->next;
}
printf（"Thetextofthecodesis:
"）;
p=head;
q=root;
while（p!
=NULL）{/*由根到叶遍历*/
if（q->lchild==NULL&&q->rchild==NULL）{/*判断是否叶节点*/
putq->data）;
q=root;
}
else{/*往下遍历*/
if（p->data=='0'）q=q->lchild;
elseq=q->rchild;
if（q->lchild==NULL&&q->rchild==NULL）{
putq->data）;
q=root;
}
}
p=p->next;
}
printf（"Inputcodesagain（y/n）?
"）;/*询问是否继续译码*/
c=getche（）;
printf（""）;
return（c）;/*返回是否继续的标志*/
}
/******************************主程序******************************/
voidmain（）{
charc,a;
do{
frequency（）;
ctree（）;
ccode（）;
c=translate（）;/*translate子函数返回值赋给c*/
for（;c=='y'||c=='Y';）{/*判断是否继续译码*/
c=translate（）;
}
printf（"Inputtextagain（y/n）?
"）;
a=getche（）;
}
while（a=='y'||a=='Y'）;/*判断是否循环*/
clrscr（）;
get）;
}
升级会员 