哈夫曼.c

数据结构的全部课程实验

    char huff[100]="";        //用于存储当前字符的哈夫曼编码串
    int i,j,n=0;

    hlist=(hnode*)malloc(sizeof(hnode));
    hlist->ch='\0';
    for(i=0;i<100;i++)
        hlist->code[i]='\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;i<100;i++)    //对哈夫曼编码数组初始化
                    huff[i]='\0';

                //先输出该叶子结点的编码
                printf("字符%c,编码为:",r->ch);
                readcode=top;
                i=0;

                while(readcode!=code)
                {
                    huff[i++]=readcode->ch;        //将栈元素倒置入哈夫曼编码数组中
                    readcode=readcode->next;
                }
                
                temp_huff=(hnode*)malloc(sizeof(hnode));    //为当前字符及其编码创建结点
                temp_huff->ch=r->ch;        //存储编码的原字符
                for(j=0;j<100;j++)        //初始化编码串数组
                    temp_huff->code[j]='\0';

                j=0;

                for(i=i-2;i>=0;i--)                //依次读出哈夫曼编码数组中的编码串
                {
                    printf("%c",huff[i]);
                    temp_huff->code[j++]=huff[i];
                }
                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[i]!='\0')
                printf("%c",hp->code[i++]);            
        }
        code_sum+=i;
       c++;
    }
    printf("\n\n");
}

void analyze()    //编码性能分析
{
    int n=0;
    printf("\t\t\t性能分析中...\n\n");
    while(pow(2,n)<char_num)    //计算等长编码情况下需要的编码位数
        n++;
    printf("等长码需要 %d 位,编码总长 %d 位,本次哈夫曼编码总长 %d , 压缩比 %g\n",n,n*char_amount,code_sum,(float)code_sum/(n*char_amount));

}

main()
{
    int choice;
    //初始化，操作包括建立空链表和键盘输入字符串
    initial();

    //将接收的字符串依次读入链表中，并统计出现的次数
    pull_in_list();

    //建立最优二叉树
    root=create();

    //交互式显示哈夫曼树
    if(root!=NULL)
    {
        printf("\n哈夫曼树构造完成，是否查看哈夫曼树，输入1查看，其它输入跳过");
        scanf("%d",&choice);
        getchar();

        if(choice==1)
            describe_tree();
    }
    else
    {
        printf("哈夫曼树未建立，查看字符串中是否只含一种字符，或者重试\n");
        exit();
    }

    //要挟据建立的最优二叉树进行编码
    encoding();

    //将原始字符串的哈夫曼编码串输出
    codeoutput();

    //编码性能分析
    analyze();

    printf("\n\n\t\t\tAll Copyright Are Presevered By cobby\n\n输入任何键退出\n");
    scanf("%d",&choice);
}