哈夫曼树编码及哈夫曼树组

Question

已知四个字符权值。
（1）建立相应的哈夫曼编码树，构造哈夫曼编码表，
（2）在此基础上对压缩文件进行压缩。
输出要求：
（1）输出哈夫曼数组；字符的哈夫曼编码；
（2）文件原文；压缩后的编码。

Answer 1

完整的程序参考

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
typedef int Status;
typedef int Boolean;
typedef struct
{
  unsigned int weight;
  unsigned int parent, lchild, rchild;
} HTNode, *HuffmanTree;
typedef char **HuffmanCode;
int min(HuffmanTree t, int i)
{
  int j, m;
  unsigned int k;
  for (j = 1; j <= i; j++)
    if (t[j].parent == 0)
      {
        k = t[j].weight;
        m = j;
      }
  t[m].parent = 1;
  return m;
}
void select(HuffmanTree t, int i, int &s1, int &s2)
{
  int j;
  s1 = min(t, i);
  s2 = min(t, i);
  if (s1 > s2)
    {
      j = s1;
      s1 = s2;
      s2 = j;
    }
}
void HuffmanCoding(HuffmanTree &HT, HuffmanCode &HC, int *w, int n)
{
  int start;
  unsigned f;
  int m, i, s1, s2;
  unsigned c;
  HuffmanTree p;
  char *cd;
  if (n <= 1)
    return;
  m = 2 * n - 1;
  HT = (HuffmanTree)malloc((m + 1) * sizeof(HTNode));
  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).parent = 0;
  for (i = n + 1; i <= m; ++i)
    {
      select(HT, i - 1, s1, s2);
      HT[s1].parent = 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 *));
  cd = (char *)malloc(n * sizeof(char));
  cd[n - 1] = '\0';
  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) * sizeof(char));
      strcpy(HC[i], &cd[start]);
    }
  free(cd);
}
int main()
{
  HuffmanTree HT, p;
  HuffmanCode HC;
  int w[] = {7, 5, 2, 4}, n = 4, i;
  char c[] = "abcd";
  char s[10001];
  HuffmanCoding(HT, HC, w, n);
  for (i = 0; i < n; i++)
    printf("%c:%d ", c[i], w[i]);
  printf("\n");
  p = HT;
  printf("哈夫曼树数组:\n");
  for (i = 1; i <= 2 * n - 1; i++)
    {
      ++p;
      printf("%d %d %d %d %d\n", i, p->weight, p->parent, p->lchild, p->rchild);
    }
  printf("哈夫曼编码:\t");
  for (i = 1; i <= n; i++)
    printf("%c:%s ", c[i - 1], HC[i]);
  printf("\n");
  printf("原文: ");
  scanf("%s", s);
  printf("哈夫曼编码压缩:");
  for (i = 0; i < strlen(s); i++)
    printf("%s", HC[s[i] - 'a' + 1]);
  printf("\n");
  return 0;
}

测试（原文是输入的）