hfm.c

C语言链表实现的huffman编码

#include<stdio.h>
#include<conio.h>
typedef struct HFMN
{
    char name[15];
    int weight;
    int visited;
    char code[15];
    struct HFMN *mother;
    struct HFMN *lchild;
    struct HFMN *rchild;
    struct HFMN *next;
}HFMN;

/******************************************************************************/
HFMN *add(HFMN *head)
{
    HFMN *p,*note,*tp;
    int inflag=1;
    p=tp=head;
    if(p==NULL)return head;
    while(inflag)
    {
        note=(HFMN *)malloc(sizeof(HFMN));
        printf("\nNote name please: ");
        scanf("%s",note->name);
        while(p)
        {
            if(strcmp(note->name,p->name)==0)
            {
                printf("\nSorry!You have ENTERED this data list!!");
                printf("\nPress any key back...");
                getch();
                note=NULL;
                goto goon;
            }
            p=p->next;
        }
        printf("\nAnd weight: ");
        scanf("%d",&note->weight);
        note->visited=0;
        note->mother=NULL;
        note->lchild=NULL;
        note->rchild=NULL;
        note->next=NULL;
        if(!head)
        {
            head=p=tp=note;
        }
        else
        {
            p=tp=head;
            while(p)
            {
                if(note->weight<=p->weight)
                {
                    if(p==head)
                    {
                        note->next=p;
                        head=tp=note;
                    }
                    else
                    {
                        note->next=p;
                        tp->next=note;
                    }
                    p=NULL;
                    break;
                }
                else
                {
                    if(p->next==NULL)
                    {
                        p->next=note;
                        p=NULL;
                        break;
                    }
                    else
                    {
                        tp=p;
                        p=p->next;
                    }
                }
            }
        }
        p=tp=head;
        note=NULL;
        break;
goon:
        printf("\nGo on?1(yes)/0(no)  ");
        scanf("%d",&inflag);
    }
    return head;

}
/*----------------------------------------------------------------------------*/
HFMN *del(HFMN *head)
{
    HFMN *p,*tp;
    char delname[15];
    p=tp=head;
    printf("\nNote name please: ");
    scanf("%s",delname);
    while(p)
    {
        if(strcmp(p->name,delname)==0)
        {
            if(p==head)
            {
                head=p=head->next;
            }
            else
            {
                tp->next=p->next;
            }
            printf("\nDelete sucessfully!!");
            printf("\nAny key back...");
            getch();
            return head;
        }
        else
        {
            tp=p;
            p=p->next;
        }
    }
    printf("\nThe data you want to delete is not exist.");
    printf("\nAny key back...");
    getch();
    return head;
}
/*----------------------------------------------------------------------------*/
HFMN *create()
{
    int inflag=1;
    HFMN *note,*head,*p,*tp;
    head=p=tp=NULL;
    while(inflag)
    {
        note=(HFMN *)malloc(sizeof(HFMN));
        printf("\nNote name please: ");
        scanf("%s",note->name);
        while(p)
        {
            if(strcmp(note->name,p->name)==0)
            {
                printf("\nSorry!You have ENTERED this data list!!");
                printf("\nPress any key back...");
                getch();
                note=NULL;
                goto goon;
            }
            p=p->next;
        }
        printf("\nAnd weight: ");
        scanf("%d",&note->weight);
        note->visited=0;
        note->mother=NULL;
        note->lchild=NULL;
        note->rchild=NULL;
        note->next=NULL;
        if(!head)
        {
            head=p=tp=note;
        }
        else
        {
            p=tp=head;
            while(p)
            {
                if(note->weight<=p->weight)
                {
                    if(p==head)
                    {
                        note->next=p;
                        head=tp=note;
                    }
                    else
                    {
                        note->next=p;
                        tp->next=note;
                    }
                    p=NULL;
                    break;
                }
                else
                {
                    if(p->next==NULL)
                    {
                        p->next=note;
                        p=NULL;
                        break;
                    }
                    else
                    {
                        tp=p;
                        p=p->next;
                    }
                }
            }
        }
        p=tp=head;
        note=NULL;
goon:
        printf("\nGo on?1(yes)/0(no)  ");
        scanf("%d",&inflag);
    }/*
    p=head;
    while(p)
    {
        printf("\n %s",p->name);
        printf("\n %d",p->weight);
        p=p->next;
    }  */
    return head;
}
/*----------------------------------------------------------------------------*/
HFMN *hfmcode(HFMN *head)
{
    int flag=1;
    char *charp="+";
    HFMN *note,*p,*tp,*l,*r;
    p=tp=head;
    if(p->next==NULL)return head;
    while(flag)
    {
        note=(HFMN *)malloc(sizeof(HFMN));
        while(p)
        {
            if(p->visited==0)break;
            p=p->next;
        }
        p->visited=1;
        l=p;
        p=head;
        while(p)
        {
            if(p->visited==0)break;
            p=p->next;
        }
        p->visited=1;
        r=p;
        *note->name='\0';
        strcat(note->name,r->name);
        strcat(note->name,charp);
        strcat(note->name,l->name);
        note->weight=l->weight+r->weight;
        note->lchild=l;
        note->rchild=r;
        note->next=NULL;
        note->visited=0;
        note->mother=NULL;
        l->mother=r->mother=note;
        p=head;
        while(p)
        {
            if(note->weight<=p->weight)
            {
                if(p==head)
                {
                     note->next=p;
                     head=tp=note;
                }
                else
                {
                     note->next=p;
                     tp->next=note;
                }
                p=NULL;
                break;
            }
            else
            {
                if(p->next==NULL)
                {
                     p->next=note;
                     p=NULL;
                     break;
                }
                else
                {
                     tp=p;
                     p=p->next;
                }
            }
        }
        flag=0;
        p=head;
        while(p->next)
        {
            if(p->visited==0)flag=1;
            p=p->next;
        }
        p=tp=head;
    }
    p=head;
    while(p)
    {
        printf("\nName: %s",p->name);
        printf("\nWeight: %d",p->weight);
        p=p->next;
    } 
    getch();
    return head;

}
/*----------------------------------------------------------------------------*/
void coding(HFMN *mom,HFMN *l,HFMN *r)
{
    char *one="1",*zero="0";
    if(l!=NULL&&r!=NULL)
    {
        strcpy(l->code,mom->code);
        strcat(l->code,zero);
        coding(l,l->lchild,l->rchild);
        strcpy(r->code,mom->code);
        strcat(r->code,one);
        coding(r,r->lchild,r->rchild);
    }
    else return ;
}
/*----------------------------------------------------------------------------*/
HFMN *decode(HFMN *head)
{
    HFMN *p,*r,*l,*mom,*tp;
    char *one="1",*zero="0";
    p=head;
    while(p->mother)
    {
        p=p->next;
    }
    mom=p;
    *mom->code='\0';
    r=mom->rchild;
    l=mom->lchild;
    strcpy(r->code,mom->code);
    strcat(r->code,one);
    strcpy(l->code,mom->code);
    strcat(l->code,zero);
    if(r)coding(r,r->lchild,r->rchild);
    if(l)coding(l,l->lchild,l->rchild);
    p=head;

    printf("\n");
    while(p->next)
    {
        if(p->lchild==NULL&&p->rchild==NULL)
        {
            printf("\nName: %s",p->name);
            printf("\nWeight= %d",p->weight);
            printf("\nHuffmancode: %s",p->code);
        }
        p=p->next;
    }
    getch();
    return head;
}
/*----------------------------------------------------------------------------*/

main()
{
    int i=0,order=1;
    HFMN *head,*p;
    head=p=NULL;
    clrscr();
    while(order)
    {
        printf("\nGive me your command,please.");
        printf("\n1.Create database.");
        printf("\n2.Add a data list.");
        printf("\n3.Delete a data list.");
        printf("\n4.Huffman coding.");
        printf("\n0.Quit to windows.\n");
        scanf("%d",&order);
        switch(order)
        {
            case 1:head=create();
                   break;
            case 2:head=add(head);break;
            case 3:head=del(head);break;
            case 4:
                   head=hfmcode(head);
                   head=decode(head);
                   printf("\n Press any to quit!");
                   getch();
                   exit(0);
            case 0:exit(1);
            default:printf("\nBad command!!\nAny key back...");getch();break;
        }
        p=head;

        while(p)
        {
            printf("\n %d.  name: %s",++i,p->name);
            printf("\n     weight= %d",p->weight);
            *p->code='\0';
            p=p->next;
        }
    }
    getch();

}