数据结构实验一线性表数据结构实验报告.doc

文档介绍：
数据结构实验一线性表 数据结构实验报告
数据结构实验报告
题目与内容
哈夫曼(Huffman)树与哈夫曼码
输入一个文本，统计各字符出现的频度，输出结果 :
使用二叉链表或三叉链表作存储结构，构造哈夫曼
(Huffma;

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(“ Frequency as follows:characters
frequency ”);
while(p!=NULL){
printf(“%c %d ”,p->data,p->m);
p=p->parent;
size++; /_统计字符的个数_/
}
生成树/____________________________

生成树
__________________________________
void ctree{
struct tree _t,_r,_p,_e,_q;
int n;
/____给链表排序生成频度递增链表_____/
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; /_交换信息_/
p->m=n;
n=q->data;
q->data=p->data;
p->data=n;
}
}
}
/___________生成哈夫曼树 ___________/
p=head;
while(p!=NULLp->parent!=NULL){
/_取递增链表前两个为左右儿子生成哈夫曼树_/

q=p->parent->parent; /_然后把它们从链表中删掉 _/
t=(struct tree_)malloc(sizeof(struct tree));
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!=NULLr->m m){
e=r;
r=r->parent;
}
t->parent=r;
e->parent=t;
}
p=head;
root=t;
}
else break; /_如果链表为空则结束 _/
/______________________________
______________________________
void ccode(
struct tree _p,_q;
int j;
printf(” codes as follows: characters code “);

for(j=0;j
head=NULL;
p=ps; /_从叶到根求编码_/
printf(”%c ”,p->data);
while(p->parent!=NULL){ /_把编码存入栈中1_/
q=(struct stack _)malloc(sizeof(struct stack));
q->data=p->sign;
q->ne_t=head;
head=q;
p=p->parent;
}
q=head; /_输出编码_/
while(q!=NULL){
printf(“%d”,q->data);
q=q->ne_t;
}
printf(“”);
}
}
/____________________________