哈弗曼编码用优先队列解决

旧城等待， 2024-02-18 22:23 8阅读 0赞

\#include<iostream>  
\#include<stdio.h>  
\#include<algorithm>  
\#include<queue>  
\#include<string.h>  
using namespace std;  
typedef struct Node  
\{  
char c;  
Node \*self,\*lchild,\*rchild;  
int weight;  
friend bool operator <(const Node &a,const Node &b) //这个地方我还不太明白，好像是友元，  
\{  
return a.weight>b.weight; //重载小于号，使权值小的先出队列  
\}  
\}Tnode;  
char c\[30\];  
priority\_queue<Tnode> q;  
void DFS(Tnode \*T,int e) //这个地方，我传的是指针，也可以用引用参数  
\{  
  
if(T->lchild==T->rchild) //叶子节点  
\{  
if(e==0) // 特例，如DDDD  
\{  
c\[0\]='0';  
e++;  
\}  
c\[e\]='\\0';  
printf("%c 的哈弗曼编码==%s\\n",T->c,c);  
\}  
else  
\{  
c\[e\]='0'; //左分支为零  
DFS(T->lchild,e+1);  
c\[e\]='1'; //右分枝为一  
DFS(T->rchild,e+1);  
\}  
\}  
void HashMake(int \*b) //构建哈弗曼树  
\{  
Tnode \*p,\*s;  
Tnode f,t;  
for(int i=0;i<26;i++)  
\{  
if(!b\[i\])  
continue;  
p=(Tnode \*)malloc(sizeof(Tnode));  
p->c='A'+i;  
p->lchild=p->rchild=NULL;  
p->self=p;  
p->weight=b\[i\];  
q.push(\*p);  
  
\}  
while(q.size()>1)  
\{  
f=q.top();  
q.pop();  
t=q.top();  
q.pop();  
s=(Tnode\*)malloc(sizeof(Tnode));  
s->lchild=f.self;  
s->rchild=t.self;  
s->self=s;  
s->weight=f.weight+t.weight;  
q.push(\*s);  
\}  
f=q.top();  
q.pop();  
DFS(&f,0);  
\}  
int main()  
\{  
char txt\[100\];  
int b\[30\],i,j;  
memset(b,0,sizeof(b));  
cout<<"请输入待编码的文本："<<endl;  
scanf("%s",txt);  
for(i=0;txt\[i\]!='\\0';i++)  
b\[txt\[i\]-'A'\]++;  
cout<<"字母出现的次数："<<endl;  
for(i=0;i<26;i++)  
if(b\[i\]!=0)  
printf("%c :%d\\n",'A'+i,b\[i\]);  
  
HashMake(b);  
return 0;  
\}

![70][]

[70]: https://image.dandelioncloud.cn/pgy_files/images/2024/01/29/4b33478584d249f2a776463572ad7dc1.png