非递归哈夫曼编码

正文

给学弟改哈夫曼编码程序，所以把以前写的一些哈夫曼编码的程序都翻出来上传了，源码是之前博客数据库中翻出来的，可能有些地方不小心改动，如果发现无法运行或者存在bug请留言

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
#include "malloc.h"
#include "stdio.h"
#include "iostream.h"
typedef struct
{
  unsigned int weight;
  unsigned int parent,lchild,rchild;
}htnode,*huffmantree;  //动态分配数组存储赫夫曼树。
 
typedef char **huffmancode;  //动态分配数组存储赫夫曼编码表。
 
int min(huffmantree t,int i)
{ //求赫夫曼树中权值最小结点，并返回其序号，为函数select（）调用。
  int j,flag;
  unsigned int k=100;
  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)
{ //求赫夫曼树中权值最小两结点，s1最小，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)
{ //无栈非递归遍历赫夫曼树，求赫夫曼编码，算法6.12&6.13结合
  int m,i,s1,s2;
  unsigned c,cdlen;
  huffmantree p;
  char *cd;
  if(n<=1)
    return;
  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)
    { //为前n个结点（未进行处理前的结点）赋初值。
      (*p).weight=*w;
      (*p).parent=0; //未按赫夫曼算法进行处理前，全为单结点，无子树。
      (*p).lchild=0;
      (*p).rchild=0;
    }
  for(;i<=m;++i,++p)
    (*p).parent=0;  //剩余n-1个结点为度为2的结点，默认父结点赋值为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*));
  //开辟空间（指向每个字符串的指针空间）HC存储每个结点对应的赫夫曼编码，0位置未用。
  cd=(char*)malloc(n*sizeof(char)); //开辟存储单一结点对应的赫夫曼编码的空间。
  c=m;
  cdlen=0; //记录编码字符个数。
  for(i=1;i<=m;++i)
    ht[i].weight=0; //默认全部为0。
  while(c)
    {
      if(ht[c].weight==0)
        {
          ht[c].weight=1;
          if(ht[c].lchild!=0)
            { //存在左子树。
              c=ht[c].lchild; //将c“指向”现结点的左子树。
              cd[cdlen++]='0'; //添加相应编码字符。
            }
          else if(ht[c].rchild==0)
            { //无右子树，证明该结点是叶结点，则该结点编码完成。
              hc[c]=(char*)malloc((cdlen+1)*sizeof(char)); //开辟储存该结点赫夫曼编码的空间，长度为cdlen+1。
              cd[cdlen]='\0';
              strcpy(hc[c],cd);
            }
        }
      else if(ht[c].weight==1)
        { //为1时说明已经访问过左子树。
          ht[c].weight=2;
          if(ht[c].rchild!=0)
            { //左子树已经访问过，且存在右子树，则应访问右子树。
              c=ht[c].rchild; //将c“指向”现结点的右子树。
              cd[cdlen++]='1'; //添加相应编码字符。
            }
        }
      else //ht[c].weight=2
        { //此语句执行是在该结点所在“路径”已经编码完毕的情况下。
          //作用是返回离该叶结点最近的某一结点（该结点另一子树未编码）
          ht[c].weight=0;
          c=ht[c].parent; //退回至父结点。
          --cdlen; //编码长度对应-1。
        }
    }
  free(cd);
}
//-----------------------------------------------------------------------------------------
int main()
{
  huffmantree ht;
  huffmancode hc;
  int *w,n,i;
  cout<<"请输入权值的个数(>1):";
  cin>>n;
  w=(int *)malloc(n*sizeof(int));
  cout<<"请依次输入n个权值（整型）：";
  for(i=0;i<=n-1;i++)
    cin>>*(w+i);
  cout<<"对应赫夫曼编码为：\n";
  huffmancoding(ht,hc,w,n);
  for(i=1;i<=n;i++)
    {
      cout<<w[i-1]<<" ";
      puts(hc[i]);
    }
return 0;
}