char huff[100]="";        //用于存儲(chǔ)當(dāng)前字符的哈夫曼編碼串
    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;        //棧的頭結(jié)點(diǎn)指向樹(shù)的根結(jié)點(diǎn)
    top=code;

    r=root;
    temp=(stack)malloc(sizeof(snode));    //給哈夫曼樹(shù)的根結(jié)點(diǎn)分配棧結(jié)點(diǎn)
    temp->amount=r->amount;
    temp->ch='0';
    temp->next=top;
    temp->son=r;
    top=temp;
    
    while(r!=NULL)    //當(dāng)前結(jié)點(diǎn)存在
    {
        if(r->left!=NULL&&r->left->amount!=-1)    //當(dāng)前結(jié)點(diǎn)有左孩子
        {
            r=r->left;        //r轉(zhuǎn)向左孩子
            r->amount=-1;

            temp=(stack)malloc(sizeof(snode));    //給左孩子分配棧結(jié)點(diǎn)
            temp->amount=r->amount;
            temp->ch='0';
            temp->next=top;
            temp->son=r;
            top=temp;
        }
        else if(r->right!=NULL&&r->right->amount!=-1)        //當(dāng)前結(jié)點(diǎn)有右孩子
        {
            r=r->right;        //r轉(zhuǎn)向右孩子
            r->amount=-1;

            temp=(stack)malloc(sizeof(snode));    //給右孩子分配棧結(jié)點(diǎn)
            temp->amount=r->amount;
            temp->ch='1';
            temp->next=top;
            temp->son=r;
            top=temp;
        }
        else    //無(wú)未訪問(wèn)的孩子結(jié)點(diǎn)
        {
            
            if(r->left==NULL&&r->right==NULL)    //當(dāng)前結(jié)點(diǎn)為葉子結(jié)點(diǎn)
            {
                for(i=0;i<100;i++)    //對(duì)哈夫曼編碼數(shù)組初始化
                    huff[i]='\0';

                //先輸出該葉子結(jié)點(diǎn)的編碼
                printf("字符%c,編碼為:",r->ch);
                readcode=top;
                i=0;

                while(readcode!=code)
                {
                    huff[i++]=readcode->ch;        //將棧元素倒置入哈夫曼編碼數(shù)組中
                    readcode=readcode->next;
                }
                
                temp_huff=(hnode*)malloc(sizeof(hnode));    //為當(dāng)前字符及其編碼創(chuàng)建結(jié)點(diǎn)
                temp_huff->ch=r->ch;        //存儲(chǔ)編碼的原字符
                for(j=0;j<100;j++)        //初始化編碼串?dāng)?shù)組
                    temp_huff->code[j]='\0';

                j=0;

                for(i=i-2;i>=0;i--)                //依次讀出哈夫曼編碼數(shù)組中的編碼串
                {
                    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()    //交互式顯示哈夫曼樹(shù)
{
    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指向哈夫曼樹(shù)的根結(jié)點(diǎn)

    temp=(stack)malloc(sizeof(snode));    //分配新棧結(jié)點(diǎn)
    temp->amount=t->amount;        
    temp->ch=t->ch;
    temp->next=top;        //結(jié)點(diǎn)入棧
    temp->son=t;    //將當(dāng)前二叉樹(shù)結(jié)點(diǎn)指針給棧頂結(jié)點(diǎn)
    top=temp;        //修改棧頂指針

    printf("輸入1往左子樹(shù)，輸入2往右子樹(shù)，輸入3返回父結(jié)點(diǎn)，輸入4退出程序，其它輸入無(wú)效\n");
    scanf("%d",&choice);
    getchar();
    
    while(choice==1||choice==2||choice==3)
    {
        if(choice==1)        //往左子樹(shù)
        {
            if(t->left!=NULL)
            {
                t=t->left;
                temp=(stack)malloc(sizeof(snode));    //分配新棧結(jié)點(diǎn)
                //新結(jié)點(diǎn)入棧
                temp->amount=t->amount;        
                temp->ch=t->ch;
                temp->next=top;        //結(jié)點(diǎn)入棧
                temp->son=t;    //將當(dāng)前二叉樹(shù)結(jié)點(diǎn)指針給棧頂結(jié)點(diǎn)
                top=temp;        //修改棧頂指針
                printf("%c,%d\n",t->ch,t->amount);
            }
            else    //左子樹(shù)不存在，當(dāng)前結(jié)點(diǎn)已經(jīng)是葉子結(jié)點(diǎn)
                printf("無(wú)左孩子！\n");    
        }
        else if(choice==2)    //往右子樹(shù)
        {
            if(t->right!=NULL)
            {
                t=t->right;
                temp=(stack)malloc(sizeof(snode));    //分配新棧結(jié)點(diǎn)
                //新結(jié)點(diǎn)入棧
                temp->amount=t->amount;
                temp->ch=t->ch;
                temp->next=top;        //結(jié)點(diǎn)入棧
                temp->son=t;    //將當(dāng)前二叉樹(shù)結(jié)點(diǎn)指針給棧頂結(jié)點(diǎn)
                top=temp;        //修改棧頂指針
                printf("%c,%d\n",t->ch,t->amount);
            }
            else    //右子樹(shù)不存在，當(dāng)前結(jié)點(diǎn)已經(jīng)是葉子結(jié)點(diǎn)
                printf("無(wú)右孩子！\n");
        }
        else if(choice==3)    //返回父結(jié)點(diǎn)
        {
            if(top->next!=s)    //棧非空
            {
                top=top->next;
                t=top->son;
                printf("%c,%d\n",t->ch,t->amount);
            }
            else
                printf("已經(jīng)在根結(jié)點(diǎn)了！\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指向編碼鏈表的第一個(gè)字符編碼組
        
        while(hp->ch!=*c&&hp->next!=NULL)    //尚未找到匹配字符且后面還有字符
            hp=hp->next;
        //退出循環(huán)的原因可能是找到了匹配字符，也可能是鏈表讀完，需要進(jìn)一步判斷
        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)    //計(jì)算等長(zhǎng)編碼情況下需要的編碼位數(shù)
        n++;
    printf("等長(zhǎng)碼需要 %d 位,編碼總長(zhǎng) %d 位,本次哈夫曼編碼總長(zhǎng) %d , 壓縮比 %g\n",n,n*char_amount,code_sum,(float)code_sum/(n*char_amount));

}

main()
{
    int choice;
    //初始化，操作包括建立空鏈表和鍵盤(pán)輸入字符串
    initial();

    //將接收的字符串依次讀入鏈表中，并統(tǒng)計(jì)出現(xiàn)的次數(shù)
    pull_in_list();

    //建立最優(yōu)二叉樹(shù)
    root=create();

    //交互式顯示哈夫曼樹(shù)
    if(root!=NULL)
    {
        printf("\n哈夫曼樹(shù)構(gòu)造完成，是否查看哈夫曼樹(shù)，輸入1查看，其它輸入跳過(guò)");
        scanf("%d",&choice);
        getchar();

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

    //要挾據(jù)建立的最優(yōu)二叉樹(shù)進(jìn)行編碼
    encoding();

    //將原始字符串的哈夫曼編碼串輸出
    codeoutput();

    //編碼性能分析
    analyze();

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