C++霍夫曼编码要求：手动输入字符串,屏幕显示编码结果和平均码长.复制党退散

C++霍夫曼编码要求：手动输入字符串,屏幕显示编码结果和平均码长.复制党退散
C++霍夫曼编码
要求：手动输入字符串,屏幕显示编码结果和平均码长.
复制党退散

C++霍夫曼编码要求：手动输入字符串,屏幕显示编码结果和平均码长.复制党退散

暂时只实现了显示编码结果,求平均码长没有完成.

#include <iostream>

using namespace std;

/*

 * 霍夫曼树结构

 */

class HuffmanTree

{

public:

    unsigned int Weight, Parent, lChild, rChild;

};

typedef char **HuffmanCode;

/*

 * 从结点集合中选出权值最小的两个结点

 * 将值分别赋给s1和s2

 */

void Select(HuffmanTree* HT,int Count,int *s2,int *s1)

{

    unsigned int temp1=0;

    unsigned int temp2=0;

    unsigned int temp3;

    for(int i=1;i<=Count;i++)

    {

        if(HT[i].Parent==0)

        {

            if(temp1==0)

            {

                temp1=HT[i].Weight;

                (*s1)=i;

            }

            else

            {

                if(temp2==0)

                {

                    temp2=HT[i].Weight;

                    (*s2)=i;

                    if(temp2<temp1)

                    {

                        temp3=temp2;

                        temp2=temp1;

                        temp1=temp3;

                        temp3=(*s2);

                        (*s2)=(*s1);

                        (*s1)=temp3;

                    }

                }

                else

                {

                    if(HT[i].Weight<temp1)

                    {

                        temp2=temp1;

                        temp1=HT[i].Weight;

                        (*s2)=(*s1);

                        (*s1)=i;

                    }

                    if(HT[i].Weight>temp1&&HT[i].Weight<temp2)

                    {

                        temp2=HT[i].Weight;

                        (*s2)=i;

                    }

                }

            }

        }

    }

}

/*

 * 霍夫曼编码函数

 */

void HuffmanCoding(HuffmanTree * HT,

                   HuffmanCode * HC,

                   int *Weight,

                   int Count)

{

    int i;

    int s1,s2;

    int TotalLength;

    char* cd;

    unsigned int c;

    unsigned int f;

    int start;

    if(Count<=1) return;

    TotalLength=Count*2-1;

HT = new HuffmanTree[(TotalLength+1)*sizeof(HuffmanTree)];

    for(i=1;i<=Count;i++)

    {

        HT[i].Parent=0;

        HT[i].rChild=0;

        HT[i].lChild=0;

        HT[i].Weight=(*Weight);

        Weight++;

    }

    for(i=Count+1;i<=TotalLength;i++)

    {

        HT[i].Weight=0;

        HT[i].Parent=0;

        HT[i].lChild=0;

        HT[i].rChild=0; 

    }

    //建造霍夫曼树

    for(i=Count+1;i<=TotalLength;++i)

    {

Select(HT, i-1, &s1, &s2);

HT[s1].Parent = i;

HT[s2].Parent = i;

HT[i].lChild = s1;

HT[i].rChild = s2;

HT[i].Weight = HT[s1].Weight + HT[s2].Weight;

    }

    //输出霍夫曼编码

    (*HC)=(HuffmanCode)malloc((Count+1)*sizeof(char*));

    cd = new char[Count*sizeof(char)];

    cd[Count-1]='\0';

    for(i=1;i<=Count;++i)

    {

        start=Count-1;

        for(c = i,f = HT[i].Parent; f != 0; c = f, f = HT[f].Parent)

        {

            if(HT[f].lChild == c)

                cd[--start]='0';

            else

                cd[--start]='1';

            (*HC)[i] = new char [(Count-start)*sizeof(char)];

            strcpy((*HC)[i], &cd[start]);

        }

    }

delete [] HT;

delete [] cd;

}

/*

 * 在字符串中查找某个字符

 * 如果找到,则返回其位置

 */

int LookFor(char *str, char letter, int count)

{

    int i;

    for(i=0;i<count;i++)

    {

        if(str[i]==letter) return i;

    }

    return -1;

}

void OutputWeight(char *Data,int Length,

                  char **WhatLetter,

                  int **Weight,int *Count)

{

    int i;

    char* Letter = new char[Length];

    int* LetterCount = new int[Length];

    int AllCount=0;

    int Index;

    int Sum=0;

    float Persent=0;

    for(i=0;i<Length;i++)

    {

        if(i==0)

        {

            Letter[0]=Data[i];

            LetterCount[0]=1;

            AllCount++;

        }

        else

        {

            Index=LookFor(Letter,Data[i],AllCount);

            if(Index==-1)

            {

                Letter[AllCount]=Data[i];

                LetterCount[AllCount]=1;

                AllCount++;

            }

            else

            {

                LetterCount[Index]++;

            }

        }

    }

    for(i=0;i<AllCount;i++)

    {

        Sum=Sum+LetterCount[i];

    }

    (*Weight) = new int[AllCount];

    (*WhatLetter) = new char[AllCount];

    for(i=0;i<AllCount;i++)

    {

        Persent=(float)LetterCount[i]/(float)Sum;

        (*Weight)[i]=(int)(100*Persent);

        (*WhatLetter)[i]=Letter[i];

    }

    (*Count)=AllCount;

delete [] Letter;

delete [] LetterCount;

}

int main()

{

HuffmanTree * HT = NULL;

HuffmanCode HC; 

char Data[100];

char *WhatLetter;

int *Weight;

int Count;

cout<<"请输入一行文本数据:"<<endl;

cin>>Data;

cout<<endl;

OutputWeight(Data,strlen(Data),

                 &WhatLetter,

                 &Weight,

                 &Count);

HuffmanCoding(HT, &HC, Weight, Count);

cout<<"字符出现频率编码结果"<<endl;

for(int i = 0; i<Count; i++)

{

cout<<WhatLetter[i]<<"     ";

cout<<Weight[i]<<"%\t";

cout<<HC[i+1]<<endl;

}

cout<<endl;

system("pause");

return 0;

}