首页 > 代码库 > Huffman树编码-优先队列实现

Huffman树编码-优先队列实现

2024-08-02 05:14:38   213人阅读

Huffman编码是之前一道算法作业题，最近又要复习考试了，先把这个的代码再看一下吧。

算法原理很简单，使用优先队列将两个节点弹出，然后合并节点之后再入队列如此循环做下去即可。

主要问题在于树的修改问题，出队的树进行修改，然后将其合并成为一个新的树，在弹出的时候，树的两个节点地址已定，但是由于循环这两个地址会进行修改，所以单独写了一个函数用来进行树的复制。

 1 #include<iostream> 2 #include<algorithm> 3 #include<vector> 4 #include<string.h> 5 #include<queue> 6 using namespace std; 7 typedef struct tree{ 8     struct tree *left; 9     struct tree *right;10     int data;11 }Tree;12 13 struct cmp14 {15        bool operator()(const Tree &t1,const Tree &t2)16        {17            return t1.data>t2.data;18        }19 };20 int a[8]={1,1,2,5,3,8,13,21};//乱序21 int code[10]={0};22 int m=0;23 void printhuffman(Tree *huffman)24 {25     if(huffman->left!=NULL)26     {27         code[m]=0;m++;28         printhuffman(huffman->left);29         m--;30     }31     if(huffman->right!=NULL)32     {33         code[m]=1;m++;34         printhuffman(huffman->right);35         m--;36     }37     if(huffman->left==NULL&&huffman->right==NULL)38     {39         printf("The code of frequency is %3d :",huffman->data);40         for(int i=0;i<m;i++)41             printf("%d ",code[i]);42         printf("\n");43         return ;44     }45 }46 void copytree(Tree **a,Tree *b)47 {48     *a=new Tree();49     if(b->left==NULL&&b->right==NULL)50     {51         (*a)->left=NULL;(*a)->right=NULL;52         (*a)->data=http://www.mamicode.com/b->data;53         return;54     }55     if(b->left!=NULL)56     {57         (*a)->left=b->left;58         copytree(&((*a)->left),b->left);59     }60     (*a)->data=http://www.mamicode.com/b->data;61     if(b->right!=NULL)62     {63         (*a)->right=b->right;64         copytree(&((*a)->right),b->right);65     }66 67 }68 int main()69 {70     int n=8;71     priority_queue<Tree,vector<Tree>,cmp> minnode;72     Tree huffman;73     74     for(int i=0;i<n;i++)75     {76         Tree *newtree=new Tree();77         newtree->data=http://www.mamicode.com/a[i];78         newtree->left=NULL;79         newtree->right=NULL;80         minnode.push(*newtree);81     }82     while(minnode.size()>=2)83     {84         Tree temp1=minnode.top();minnode.pop();85         Tree temp2=minnode.top();minnode.pop();86         Tree *temp3=new Tree();87         temp3->left=NULL;88         temp3->right=NULL;89         temp3->data=http://www.mamicode.com/0;90         copytree(&temp3->left,&temp1);91         copytree(&temp3->right,&temp2);92         temp3->data=http://www.mamicode.com/(*(temp3->left)).data+(*(temp3->right)).data;93         minnode.push(*temp3);94     }95     huffman=minnode.top();96     printhuffman(&huffman);97     return 0;98 }

运行结果：

Huffman树编码-优先队列实现


联系
我们