[暑期补课]数据结构试验第三题赫夫曼树 - 技术| 编程·课件·Linux - 软院网 RuanYuan.Net

[C++] 纯文本查看 复制代码
// 哈夫曼编码.cpp : 定义控制台应用程序的入口点。
//

#include "stdafx.h"

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <malloc.h>
#include <iostream>

using namespace std;

typedef struct{
        unsigned int weight;
        unsigned int parent,lchild,rchild;
}HTNode, * HuffmanTree;

typedef char * * HuffmanCode;

int min(HuffmanTree t,int i)
{
   int j,flag;
   unsigned int k = 100000;
   for(j=1;j<=i;j++)
      if(t[j].weight<k&&t[j].parent==0)
                        k = t[j].weight,flag = j;
   t[flag].parent = 1;
   return flag;
}

void select(HuffmanTree t,int i, int *s1, int *s2)//在HT[1..i-1]选择parent为0且weight最小的两个结点，其序号分别为s1和s2.
{
        int temp;
        *s1 = min(t,i);   
        *s2 = min(t,i);
        if(*s1>*s2)   
        {
                temp = *s1;
                *s1 = *s2;
                *s2 = temp;
        }
}

void HuffmanCoding(HuffmanTree &HT,HuffmanCode &HC,int *w,int n)
{
        int i,s1,s2,start;
        HuffmanTree p;
        if( n<=1 )
                return;
        int m = 2*n - 1;//n个叶子结点的赫夫曼树共有2n-1个结点（保证是正则二叉树）
        HT = (HuffmanTree) malloc( (m+1)*sizeof(HTNode) );//0号单元未用
        for( p = HT+1,i=1;i <= n;++i,++p,++w)//初始化各节点
    {
                (*p).weight=*w;(*p).parent=0;(*p).lchild=0;(*p).rchild=0;
    }
        for(;i<=m;++i,++p)
        {
                (*p).weight=0;(*p).parent=0;(*p).lchild=0;(*p).rchild=0;
        }
    for(i=n+1;i<=m;++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((n+1)*sizeof(char*));
        char *cd;
        cd=(char*)malloc(n*sizeof(char));
        cd[n-1]='\0';
        int c,f;
        for(i=1;i<=n;++i)
        {
                start=n-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]=(char*)malloc((n-start)*start*sizeof(char));
                strcpy(HC[i],&cd[start]);
        }
free(cd);
}        

int main()
{
        int w[100];
        HuffmanTree ht;
    HuffmanCode hc;
        int n;
        cout<<"请输入需编码个数"<<endl;
        cin>>n;
        cout<<"请输入权值";
        for (int i=0;i<n;i++)
        {
                cin>>w[i];
        }
        HuffmanCoding(ht,hc,w,n);
        for (int i=1;i<=n;i++)
        {
                printf("%d的赫夫曼编码：%s\n",ht[i].weight,hc[i]);
        }
    system("pause");
}
[技术| 编程·课件·Linux] [暑期补课]数据结构试验第三题赫夫曼树

点评

点评

点评

点评

点评

点评
