求哈夫曼编码,谢谢!不要加解释

求哈夫曼编码,谢谢!不要加解释
求哈夫曼编码,谢谢!
不要加解释

求哈夫曼编码,谢谢!不要加解释
完整的程序
#include
#include
#include
#define NULL 0
typedef struct huff_code_node //存储编码的链表
{
char ch; //编码对应的字符
char code[100]; //字符对应的哈夫曼码
struct huff_code_node *next;
}hnode,*huff;
typedef struct tree_Node //二叉树结点
{
char ch; //字符内容
int amount; //字符在字符串中出现的次数
struct tree_Node *left,*right; //指向左子树与右子树
}tnode,*bt;
typedef struct list_node //链表结点
{
char ch; //存储字符串中的字符
int amount; //字符在字符串中出现的次数
tnode *son; //链表结点带有二叉子树的根结点指针
struct list_node *next; //指向链表中下一个结点
}Node,*L;
typedef struct stack_node
{
char ch; //存储字符
int amount; //出现次数
bt son; //指向二叉树的某结点
struct stack_node *next;
}snode,*stack;
char t[200],*str,*c; //用于存储和处理输入的字符串
bt root=NULL; //哈夫曼树
L l,p,q,new_node; //链表结点
huff hlist; //计算得到的编码表
int char_num; //输入的不同字符数量
int char_amount; //输入的所有字符数量
int code_sum; //哈夫曼编码总长
void initial() //初始化操作
{
l=(Node*)malloc(sizeof(Node)); //建立空链表
l->ch='\0';
l->amount=0;
l->son=NULL;
l->next=NULL;
str=t; //将字符串指针指向字符串的第一个位置
//键盘输入字符串
printf("输入字符串进行哈夫曼编码:\n");
scanf("%s",str);
getchar();
}
void pull_in_list()
{
int exist; //表示当前字符是否存在于链表中,0为不存在,1为已存在
int n; //计算输入不同字符的数量,计算后赋值给全局变量char_num
int m; //计算输入所有字符的数量,计算后赋值给全局变量char_amount

c=str; //c指向第一个字符

while(*c!='\0') //若字符串未读完
{
exist=0;
p=l; //p指向链表头结点
//寻找该字符是否已经在链表中
while(p->next!=NULL) //若链表非空
{
p=p->next;
if(p->ch==*c) //若当前字符已经在链表中
{
exist=1;
p->amount++; //字符出现次数加1
break;
}
}
if(exist==0) //若当前字符不存在于链表中,则分配一个结点入表
{
new_node=(Node*)malloc(sizeof(Node));
new_node->ch=*c;
new_node->amount=1;
new_node->next=NULL;
new_node->son=NULL;
p->next=new_node;
p=new_node;
}
c++; //读下一个字符
}
printf("统计结果:\n");
p=l;
n=0;
m=0;
while(p->next!=NULL)
{
n++;
p=p->next;
m+=p->amount;
printf("%c——%d\n",p->ch,p->amount);
}
char_num=n;
char_amount=m;
printf("一共有%d种字符输入,字符总数%d\n",char_num,char_amount);
}
int list_element_amount() //计算链表中结点的数量（不包括头结点）
{
L temp; //定义临时指针
int n=0; //结点数量
temp=l;
while(temp->next!=NULL) //后面还有结点
{
n++;
temp=temp->next;
}
return n;
}
bt create() //建立最优二叉树
{
//
//两个最小结点找到,由这对结点级成一个二叉子树,将根结点插入链表中
if(min1_son==NULL) //该结点无二叉子树指针,则须新分配一个二叉树结点
{
left=(bt)malloc(sizeof(tnode)); //产生左孩子
left->amount=min1; //次数值复制
left->ch=min1_c; //字符复制
left->left=NULL;
left->right=NULL;
}
else //该结点为计算产生的结点,它已指向一个二叉子树
left=min1_son; //left直接指向已经生成的二叉子树的根结点
if(min2_son==NULL) //该结点无二叉子树指针,则须新分配一个二叉树结点
{
right=(bt)malloc(sizeof(tnode)); //产生右孩子
right->amount=min2; //次数值复制
right->ch=min2_c; //字符复制
right->left=NULL;
right->right=NULL;
}
else
right=min2_son; //left直接指向已经生成的二叉子树的根结点
root=(bt)malloc(sizeof(tnode));
root->amount=min1+min2;
root->ch='\0'; //对于计算产生的树结点,字符均为空
root->left=left;
root->right=right;
//二叉子树完成
//生成一个对应上面已产生二叉子树地址的链表结点
made=(L)malloc(sizeof(Node));
made->amount=root->amount;
made->ch=root->ch;
made->next=NULL;
made->son=root;
//将生成的链表结点插入链表中
temp_p=l;
while(temp_p->next!=NULL)
temp_p=temp_p->next;
//退出循环时temp_p指向链表最后一个结点
temp_p->next=made; //将生成的结点插入链表
}
temp_p=l->next;
return temp_p->son;
}
void encoding() //根据建立的哈夫曼树编码
{
stack code,top,temp,readcode;
bt r;
huff temp_huff,hp;
char huff[100]=""; //用于存储当前字符的哈夫曼编码串
int i,j,n=0;
hlist=(hnode*)malloc(sizeof(hnode));
hlist->ch='\0';
for(i=0;icode='\0';
hlist->next=NULL;
hp=hlist;
//建立空栈
code=(stack)malloc(sizeof(snode));
code->amount=0;
code->ch='\0';
code->next=NULL;
code->son=NULL; //栈的头结点指向树的根结点
top=code;
r=root;
temp=(stack)malloc(sizeof(snode)); //给哈夫曼树的根结点分配栈结点
temp->amount=r->amount;
temp->ch='0';
temp->next=top;
temp->son=r;
top=temp;

while(r!=NULL) //当前结点存在
{
if(r->left!=NULL&&r->left->amount!=-1) //当前结点有左孩子
{
r=r->left; //r转向左孩子
r->amount=-1;
temp=(stack)malloc(sizeof(snode)); //给左孩子分配栈结点
temp->amount=r->amount;
temp->ch='0';
temp->next=top;
temp->son=r;
top=temp;
}
else if(r->right!=NULL&&r->right->amount!=-1) //当前结点有右孩子
{
r=r->right; //r转向右孩子
r->amount=-1;
temp=(stack)malloc(sizeof(snode)); //给右孩子分配栈结点
temp->amount=r->amount;
temp->ch='1';
temp->next=top;
temp->son=r;
top=temp;
}
else //无未访问的孩子结点
{

if(r->left==NULL&&r->right==NULL) //当前结点为叶子结点
{
for(i=0;ich);
readcode=top;
i=0;
while(readcode!=code)
{
huff=readcode->ch; //将栈元素倒置入哈夫曼编码数组中
readcode=readcode->next;
}

temp_huff=(hnode*)malloc(sizeof(hnode)); //为当前字符及其编码创建结点
temp_huff->ch=r->ch; //存储编码的原字符
for(j=0;jcode[j]='\0';
j=0;
for(i=i-2;i>=0;i--) //依次读出哈夫曼编码数组中的编码串
{
printf("%c",huff);
temp_huff->code[j++]=huff;
}
temp_huff->next=NULL;
hp->next=temp_huff;
hp=temp_huff;
printf("\t\t");
if(++n%2==0)
printf("\n");
}
if(top->next!=code) //若栈非空
{
top=top->next;
r=top->son;
}
else
break;
}
}
}
void describe_tree() //交互式显示哈夫曼树
{
bt t;
stack s,top,temp;
int choice;
s=(stack)malloc(sizeof(snode));
s->amount=0;
s->ch='\0';
s->next=NULL;
s->son=NULL;
top=s;

t=root;//t指向哈夫曼树的根结点
temp=(stack)malloc(sizeof(snode)); //分配新栈结点
temp->amount=t->amount;
temp->ch=t->ch;
temp->next=top; //结点入栈
temp->son=t; //将当前二叉树结点指针给栈顶结点
top=temp; //修改栈顶指针
printf("输入1往左子树,输入2往右子树,输入3返回父结点,输入4退出程序,其它输入无效\n");
scanf("%d",&choice);
getchar();

while(choice==1||choice==2||choice==3)
{
if(choice==1) //往左子树
{
if(t->left!=NULL)
{
t=t->left;
temp=(stack)malloc(sizeof(snode)); //分配新栈结点
//新结点入栈
temp->amount=t->amount;
temp->ch=t->ch;
temp->next=top; //结点入栈
temp->son=t; //将当前二叉树结点指针给栈顶结点
top=temp; //修改栈顶指针
printf("%c,%d\n",t->ch,t->amount);
}
else //左子树不存在,当前结点已经是叶子结点
printf("无左孩子!\n");
}
else if(choice==2) //往右子树
{
if(t->right!=NULL)
{
t=t->right;
temp=(stack)malloc(sizeof(snode)); //分配新栈结点
//新结点入栈
temp->amount=t->amount;
temp->ch=t->ch;
temp->next=top; //结点入栈
temp->son=t; //将当前二叉树结点指针给栈顶结点
top=temp; //修改栈顶指针
printf("%c,%d\n",t->ch,t->amount);
}
else //右子树不存在,当前结点已经是叶子结点
printf("无右孩子!\n");
}
else if(choice==3) //返回父结点
{
if(top->next!=s) //栈非空
{
top=top->next;
t=top->son;
printf("%c,%d\n",t->ch,t->amount);
}
else
printf("已经在根结点了!\n");
}
//else if(choice==4) //退出程序
// exit(0);
scanf("%d",&choice);
getchar();
}
}
void codeoutput() //输出原始字符串的哈夫曼编码串
{
huff hp;
//char *s;
int i;
c=str; //c指向原始字符串str的首位置
printf("\n\n原始字符串为:%s\n哈夫曼编码为:",c);
code_sum=0;
//在编码链表中找寻与c匹配的编码串
while(*c!='\0') //字符串未读完
{
hp=hlist->next; //hp指向编码链表的第一个字符编码组

while(hp->ch!=*c&&hp->next!=NULL) //尚未找到匹配字符且后面还有字符
hp=hp->next;
//退出循环的原因可能是找到了匹配字符,也可能是链表读完,需要进一步判断
if(hp->ch==*c) //找到匹配字符
{
i=0;
while(hp->code!='\0')
printf("%c",hp->code);
}
code_sum+=i;
c++;
}
printf("\n\n");
}
void analyze() //编码性能分析
{
int n=0;
printf("\t\t\t性能分析中...\n\n");
while(pow(2,n)