数据结构——哈夫曼树

哈夫曼树：
树的带权路径长度达到最小，称这样的二叉树为最优二叉树，也称为哈夫曼树(Huffman Tree)。哈夫曼树是带权路径长度最短的树，权值较大的结点离根较近。
任务描述:
从文件中读文本;
统计字符频次, 并建立字母表;
构造 Huffman 树;
将文本编码;
解码.
版本一
分析:
parent, lchild, rchild 都用的是整数, 即下标. 也就是说, 先建立节点, 存放于一个数组 (线性表) 中, 再进行链接. 避免使用指针, 有静态链表的味道, good!
代码
#include 
#include 
#include 
using namespace std; 

#define MaxSize 1024  // 读入文件的上限 
#define OK 1
#define ERROR 0
typedef int Status;

typedef struct wordcnt{  // 统计字符和对应的次数 
	char ch;
	int cnt = 0;
}Count;

typedef struct NumCount{  // 统计次数的外部封装 
	Count count[MaxSize];
	int length = 0;
}NumCount;

typedef struct HTree{  // 哈夫曼树结构 
	char data; 
	int weight;
	int parent,lchild,rchild;
}HTNode,*HuffmanTree; 

typedef struct HCode{ // 编码结构 
	char data;
	char* str; 
}*HuffmanCode;


Status ReadData(char *source);  // 读入文件 
Status WordCount(char *data,NumCount *paraCnt); // 统计次数 
Status Show(NumCount *paraCnt);   // 展示次数 
Status CreateHuffmanTree(HuffmanTree &HT,int length,NumCount cntarray);  // 创建哈夫曼树 
Status select(HuffmanTree HT,int top,int *s1,int *s2);  // 选择权重最小的两个节点 
Status CreateHuffmanCode(HuffmanTree HT,HuffmanCode &HC,int length);  // 创建哈夫曼编码 
Status Encode(char *data,HuffmanCode HC,int length);  // 将读入的文件编码，写到txt文件 
Status Decode(HuffmanTree HT,int length);  //读入编码文件，解码 

int main(int argc, char** argv) {
	char data[MaxSize];  
	NumCount Cntarray;
	ReadData(data);  // 读入数据 
	WordCount(data,&Cntarray);  // 统计次数 
//	Show(&Cntarray); //可以查看每个单词出现的对应次数 
	HuffmanTree tree;
	CreateHuffmanTree(tree,Cntarray.length,Cntarray);  // 建树 
	HuffmanCode code;  
	CreateHuffmanCode(tree,code,Cntarray.length);  // 创建编码 
	Encode(data,code,Cntarray.length);  // 生成编码文件 
	Decode(tree,Cntarray.length);  // 解码 
	cout<<"Please view the generated TXT file to check the result"<length;++j)
		{
			if(paraCnt->count[j].ch == data[i]) // 若已有记录，直接++ 
			{
				++paraCnt->count[j].cnt;
				flag = 1;
				break;
			}
			
		}
		if(!flag) // 没有记录，则新增 
		{
			paraCnt->count[paraCnt->length].ch = data[i];
			++paraCnt->count[paraCnt->length].cnt;
			++paraCnt->length;
		}
	}
	return OK;
}

Status Show(NumCount *paraCnt)
{
	cout<<"the length is "<length<length;++i)
	{
		cout<<"The character "<count[i].ch<<"  appears  "<count[i].cnt< 
文本文件内容 
in.txt 
Life is full of confusing and disordering Particular time,a particular location,Do the arranged thing of ten million time in the brain,Step by step ,the life is hard to avoid delicacy and stiffness No enthusiasm forever,No unexpected happening of surprising and pleasing So,only silently ask myself in mind Next happiness,when will come? 
版本二 
source.txt 这么短, 怎么编码 
用的是正宗的链式结构. 难度增加.
#include 
#include 

//最大读入的文本文件的字符长度
#define MAXSIZE 100

typedef struct NODE
{
    char c;
    //结点权重
    int weight;
    //记录结点表示的二进制，左0右1
    int binary;
    //是否已经创建该结点，1为创建，0为未创建
    int flag;

    struct NODE *lchild, *rchild, *parent;

} NODE, *PNODE;

typedef struct
{
    int valuse[MAXSIZE];
    int top;
} STACK;


void initStack(STACK &stack)
{
    stack.top = 0;
}

void push(STACK &stack, int value)
{
    stack.valuse[stack.top++] = value;
}

int pop(STACK &stack)
{
    if (stack.top == 0)
        return -1;
    stack.top--;
    return stack.valuse[stack.top];
}

//初始化树结点
void initNode(PNODE node)
{
    node->lchild = NULL;
    node->parent = NULL;
    node->rchild = NULL;
    node->flag = 0;
    node->weight = 0;
    node->c = -1;
    node->binary = 0;
}


PNODE createNode(int weight)
{
    PNODE node = (PNODE)malloc(sizeof(NODE));
    if (node)
    {
        initNode(node);
        node->weight = weight;
    }
    return node;
}


STACK charEncode(char c, PNODE childrenNodes, int lenOfNodes)
{
    STACK stack;
    initStack(stack);
    for (int i = 0; i < lenOfNodes; i++)
    {
        if (c == childrenNodes[i].c)
        {
            PNODE tmp = &childrenNodes[i];
            while (tmp->parent != NULL)
            {
                push(stack, tmp->binary);
                tmp = tmp->parent;
            }
            break;
        }
    }
    return stack;
}


char *strEncode(char *str, PNODE childrenNodes, int lenOfNodes)
{
    char *result = (char *)malloc(sizeof(char) * MAXSIZE * lenOfNodes);
    int len = 0;
    while (*str != '')
    {
        STACK stack = charEncode(*str, childrenNodes, lenOfNodes);
        while (stack.top > 0)
        {
            result[len++] = pop(stack) + '0';
        }
        str++;
    }
    result[len] = '';
    return result;
}


PNODE getMinWeightNode(PNODE nodes, int lenOfNodes)
{
    PNODE node;
    int min = 0, i;

    //对已创建过的结点进行过滤
    while (min < lenOfNodes)
    {
        if (nodes[min].flag == 0)
        {
            break;
        }
        min++;
    }

    if (min == lenOfNodes)
    {
        return NULL;
    }

    //查找未创建的结点中权重最小的结点
    for (i = min + 1; i < lenOfNodes; i++)
    {
        if (nodes[i].flag == 0 && nodes[i].weight < nodes[min].weight)
        {
            min = i;
            continue;
        }
    }

    nodes[min].flag = 1;
    return &nodes[min];
}


PNODE createHuffmanTree(PNODE nodes, int lenOfNodes, PNODE childNode)
{
    PNODE minWeightNode, parentNode;

    minWeightNode = getMinWeightNode(nodes, lenOfNodes);

    if (!minWeightNode)
        return childNode;

    if (!childNode)
    {
        parentNode = minWeightNode;
    }
    else
    {
        parentNode = createNode(childNode->weight + minWeightNode->weight);

        if (childNode->weight < minWeightNode->weight)
        {
            parentNode->lchild = childNode;
            parentNode->rchild = minWeightNode;
        }
        else
        {
            parentNode->rchild = childNode;
            parentNode->lchild = minWeightNode;
        }
        parentNode->lchild->binary = 0;
        parentNode->rchild->binary = 1;

        childNode->parent = minWeightNode->parent = parentNode;
    }

    createHuffmanTree(nodes, lenOfNodes, parentNode);
}


char charTolowercase(char c)
{
    if (c >= 'A' && c <= 'Z')
    {
        c += 'a' - 'A';
    }
    return c;
}


PNODE readFromSource(const char *filePath, char *buff, PNODE childrenNodes, int &lenOfNodes)
{

    //记录字符串长度
    int lenOfStr = 0, i;

    //记录当前读取的字符
    char c;

    FILE *file = fopen(filePath, "rb");

    if (file == NULL)
    {
        puts("Can't find source file!");
        exit(0);
    }

    //一个字符一个字符读入本地文本
    c = fgetc(file);
    while (!feof(file))
    {
        c = charTolowercase(c);
        //初始化结点
        initNode(&childrenNodes[lenOfNodes]);

        buff[lenOfStr++] = c;
        for (i = 0; i < lenOfNodes; i++)
        {
            if (childrenNodes[i].c == c)
            {
                childrenNodes[i].weight++;
                break;
            }
        }
        if (i == lenOfNodes)
        {
            childrenNodes[lenOfNodes].c = c;
            childrenNodes[lenOfNodes++].weight++;
        }
        c = fgetc(file);
    }
    buff[lenOfStr] = '';

    fclose(file);
    return createHuffmanTree(childrenNodes, lenOfNodes, NULL);
}


void writeResult(const char *filePath, char *result)
{
    FILE *fp = fopen(filePath, "wb");
    if (fputs(result, fp) >= 0)
    {
        printf("生成结果成功rn");
    }
    fclose(fp);
}


char *strDecode(const char *str, PNODE TreeRoot)
{
    const char *tmp = str;
    char *result = (char *)malloc(sizeof(char) * MAXSIZE);
    //用来记录结果字符串的长度
    int len = 0;
    while (*tmp != '')
    {
        PNODE tmpNode = TreeRoot;
        while (tmpNode->lchild && tmpNode->rchild)
        {
            tmpNode = *tmp == '0' ? tmpNode->lchild : tmpNode->rchild;
            tmp++;
        }
        result[len++] = tmpNode->c;
    }
    result[len] = '';
    return result;
}

int main()
{
    char buff[MAXSIZE];

    NODE childrenNodes[MAXSIZE];

    int len = 0;

    //确保source.txt和exe处于同目录
    PNODE root = readFromSource("source.txt", buff, childrenNodes, len);

    writeResult("result.txt", strEncode(buff, childrenNodes, len));

    printf("%s", strDecode("11111111111110111111111110011101111111111011001110011111111101111111101111111011111101111101100111101010", root));

    return 0;
}

 
 
source.txt 
you are a pig
 me too
数据结构——哈夫曼树

C/C++/C#相关栏目本月热门文章
