Huffman树

╰+攻爆jí腚メ 2022-01-07 16:15 219阅读 0赞

### 实验题目(共6题, 第1题) ###

<table> 
 <tbody> 
  <tr> 
   <td>标题：</td> 
   <td>Huffman树</td> 
  </tr> 
  <tr> 
   <td>时 限：</td> 
   <td>1000 ms</td> 
  </tr> 
  <tr> 
   <td>内存限制：</td> 
   <td>10000 K</td> 
  </tr> 
  <tr> 
   <td>总时限：</td> 
   <td>3000 ms</td> 
  </tr> 
  <tr> 
   <td>描述：</td> 
   <td> 
    <div> 
     <span style="font-size:medium;">Huffman树</span> 
    </div> <p><span style="font-size:medium;">对输入的英文大写字母进行统计概率 然后构建哈夫曼树,输出是按照概率降序排序输出Huffman编码。</span></p></td> 
  </tr> 
  <tr> 
   <td>输入：</td> 
   <td> 
    <div>
      大写字母个数 n 
    </div>第一个字母 第二个字母 第三个字母 ...&nbsp; 第n个字母</td> 
  </tr> 
  <tr> 
   <td>输出：</td> 
   <td> 
    <div>
      字母1 出现次数 Huffman编码 
    </div> 
    <div>
      字母2 出现次数 Huffman编码 
    </div> 
    <div>
      字母3 出现次数 Huffman编码 
    </div> 
    <div>
      … 
    </div> 
    <div>
      字母n 出现次数 Huffman编码 
    </div></td> 
  </tr> 
  <tr> 
   <td>输入样例：</td> 
   <td> 
    <div> 
     <span style="font-size:medium;">10</span> 
    </div> 
    <div> 
     <span style="font-size:medium;">I I U U U I U N U U</span> 
    </div></td> 
  </tr> 
  <tr> 
   <td>输出样例：</td> 
   <td> 
    <div> 
     <span style="font-size:large;">U 6 1</span> 
    </div> 
    <div> 
     <span style="font-size:large;">I 3 01</span> 
    </div> 
    <div> 
     <span style="font-size:large;">N 1 00</span> 
    </div> 
    <div>
      &nbsp; 
    </div></td> 
  </tr> 
  <tr> 
   <td>提示：</td> 
   <td>参见教材<span style="font-family:'宋体';"><span style="font-size:medium;">144</span>页</span></td> 
  </tr> 
  <tr> 
   <td>来源：</td> 
   <td>&nbsp;</td> 
  </tr> 
 </tbody> 
</table>

\#include <stdio.h>  
\#include <stdlib.h>  
\#include <string.h>

\#define MAX 27  
\#define MAX\_INT 99999

//哈夫曼树和哈夫曼编码的存储表示  
typedef struct  
\{  
int weight;  
int parent,lchild,rchild;  
\} HTNode,\*HuffmanTree; // 动态分配数组存储哈夫曼树

typedef char \*\*HuffmanCode;

typedef struct Charnode  
\{  
char c;  
int weight;  
\} CharNode,\*CharNodePtr; //不要定义为Char

CharNode \*b;

int Chat\_get()  
\{  
char c;  
int j=0;  
int m;  
int i;  
scanf("%d",&m);  
getchar();  
b=(CharNodePtr)malloc(sizeof(CharNode)\*MAX);  
int a\[MAX\];  
for(i=0; i<MAX; i++)  
\{  
a\[i\]=0;  
\}  
for(i=0; i<m; i++)  
\{  
scanf("%c",&c);  
getchar();  
a\[c-'A'\]++;  
\}  
for(i=0; i<26; i++)  
\{  
if(a\[i\]!=0)  
\{  
b\[j\].c=char(i+'A');  
b\[j\].weight=a\[i\];  
j++;  
\}  
\}  
return j;  
\}//得到不同字符的个数和数组

int min(HuffmanTree t,int i)  
\{  
int j,flag;  
int k=MAX\_INT; // 取k为不小于可能的值  
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)  
\{  
s2=min(t,i);  
s1=min(t,i);  
\}

void PrintHuffmanTree(HuffmanTree &HT,HuffmanCode &HC, int n)  
\{  
int i, c, cdlen;  
char \*cd;  
HC=(HuffmanCode)malloc((n+1)\*sizeof(char\*));  
// 分配n个字符编码的头指针向量(\[0\]不用)  
cd=(char\*)malloc(n\*sizeof(char)); // 分配求编码的工作空间  
c=2\*n-1;  
cdlen=0;  
for(i=0; i<=c; ++i) HT\[i\].weight=0; // 遍历赫夫曼树时用作结点状态标志  
while(c)  
\{  
if(HT\[c\].weight==0) // 向左  
\{  
HT\[c\].weight=1;  
if(HT\[c\].lchild==0 && HT\[c\].rchild==0) // 登记叶子结点字符编码  
\{  
HC\[c\]=(char \*)malloc((cdlen+1)\*sizeof(char));  
cd\[cdlen\]='\\0';  
strcpy(HC\[c\],cd); // 复制编码(串)  
\}  
if(HT\[c\].lchild!=0)  
\{  
c=HT\[c\].lchild;  
cd\[cdlen++\]='1';  
\}  
\}  
else if(HT\[c\].weight==1) // 向右  
\{  
HT\[c\].weight=2;  
if(HT\[c\].rchild!=0)  
\{  
c=HT\[c\].rchild;  
cd\[cdlen++\]='0';  
\}  
\}  
else  
\{  
HT\[c\].weight=0;  
c=HT\[c\].parent;  
\--cdlen; // 退到父结点,编码长度减1  
\}  
\}  
free(cd);  
\}

// w存放n个字符的权值(均>0),构造哈夫曼树HT,并求出n个字符的哈夫曼编码HC  
void HuffmanCoding(HuffmanTree &HT,HuffmanCode &HC,int \*w,int n)  
\{  
int m,i,s1,s2;

HuffmanTree p;

if(n<=1) exit(0);  
m=2\*n-1;  
HT=(HuffmanTree)malloc((m+1)\*sizeof(HTNode)); // 0号单元未用  
//因为0号单元未用，处理数据时候从1号单元开始  
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;  
// 在HT\[1~i-1\]中选择parent为0且weight最小的两个结点,其序号分别为s1和s2  
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;  
\}  
//顺序输出哈夫曼树  
PrintHuffmanTree(HT, HC, n);  
\}

void sort\_b(int k)  
\{  
int n;  
char c;  
int i,j;  
for(i=0; i<k; i++)  
\{  
for(j=k-1; j>=i; j--)  
\{  
if(b\[j\].weight>b\[j-1\].weight)  
\{  
n=b\[j\].weight;  
b\[j\].weight=b\[j-1\].weight;  
b\[j-1\].weight=n;  
c=b\[j\].c;  
b\[j\].c=b\[j-1\].c;  
b\[j-1\].c=c;  
\}  
\}  
\}  
\}

int main()  
\{  
int k;  
int j;  
int i;  
HuffmanTree HT;  
HuffmanCode HC;  
k=Chat\_get();  
int \*w;  
w=(int \*)malloc(sizeof(int)\*k);  
sort\_b(k);  
for(i=0; i<k; i++)  
\{  
w\[i\]=b\[i\].weight;  
\}  
HuffmanCoding(HT,HC,w,k);  
for(i=0,j=1; i<k; j++,i++)  
\{  
printf("%c %d %s\\n",b\[i\].c,b\[i\].weight,HC\[j\]);  
\}  
return 0;  
\}

转载于:https://www.cnblogs.com/ronaldHU/archive/2012/10/07/2490784.html