数据结构-Huffman树

Huffman树的编码和解码

思想：1.统计字符串每个字母出现的个数2.依次取出两个最小的字母进行合并（分别作为左右子节点，另左子节点<右子节点的值），使用他们值之和作为根节点的值，并将根节点加入到未合并的节点序列中。重复1,2操作，直到没有两个节点可以合并为止。

#include<iostream> #include<iostream> #include<map> #include<vector> using namespace std; map<int,string> pp;//将int类型转化为对应Huffman树中的string，但是只能用于单一元的才行 map<char,int> p;//将字符转化为int类型 int len;//所得字符的个数. struct huffmannode{float data;string ss;huffmannode*leftchild,*rightchild,*parent;huffmannode(float a=0,huffmannode* b=NULL,huffmannode* c=NULL,huffmannode* d=NULL,string s=""){ss=s;data=a;leftchild=b,rightchild=c,parent=d;} };bool operator>= (huffmannode& io,huffmannode& p){return io.data>p.data?true:false; } bool operator<=(huffmannode& io,huffmannode& op){return io.data<op.data?true:false; }template<class T> class minheap{ public:minheap(int sz=20){//建立空堆。只是给了内存空间没有数据值。maxheapsize=sz>20?sz:20;heap=new T[maxheapsize];if(heap==NULL){cout<<"内存分配错误."<<endl;exit(1);}currentsize=0;}minheap(T arr[],int n){maxheapsize=n>20?n:20;heap=new T[maxheapsize];if(heap==NULL){cerr<<"堆存储空间分配失败！"<<endl;exit(1);}for(int i=0;i<n;i++){heap[i]=arr[i];}currentsize=n;int currentpos=(currentsize-2)/2;//第一个节点位置while(currentpos>=0){siftdown(currentpos,currentsize-1);currentpos--;}};~minheap(){delete [] heap;}bool removemin(T& x);//删除堆顶元素.bool isempty(){//当当前指针指向堆首时就为真，即没有元素.if(currentsize==0){return true;}else{return false;}}bool isfull(){if(currentsize>=maxheapsize){return true;}else{return false;}}void makeempty(){currentsize=0;}bool insert(const T& io);void output(){int i=0;while(i<currentsize){cout<<heap[i++]<<" ";}} private:T *heap;int currentsize;int maxheapsize;void siftdown(int start,int m);void siftup(int start); }; template<class T> void minheap<T>::siftdown(int start,int m){int i=start;T io=heap[i];T change;int j=2*i+1;//当前节点的左孩子节点while(j<=m){if(j+1<=m&&heap[j+1]<=heap[j]){change=heap[j+1];heap[j+1]=heap[j];heap[j]=change;}if(heap[j]>=io){break;}else{heap[i]=heap[j];i=j;j=j*2+1;}}heap[i]=io; } template<class T> void minheap<T>::siftup(int start){int j=start,i=(j-1)/2;T temp=heap[j];while(j>0){if(heap[i]>=heap[j]){heap[j]=heap[i];j=i;i=(i-1)/2;}else{break;}}heap[j]=temp; } template<class T> bool minheap<T>::insert(const T& io){if(currentsize==maxheapsize){return false;}else{heap[currentsize]=io;siftup(currentsize);currentsize++;return true;} } template<class T> bool minheap<T>::removemin(T&x){if(currentsize==0){return false;}else{x=heap[0];heap[0]=heap[currentsize-1];currentsize--;siftdown(0,currentsize-1);return true;}// } class huffmantree{ private:huffmannode *root;void deletetree(huffmannode* t); public:void mergetree(huffmannode*& parent1,huffmannode* first,huffmannode* second){parent1=new huffmannode(first->data+second->data);parent1->leftchild=first,parent1->rightchild=second;first->parent=parent1;second->parent=parent1;}huffmantree(float *w=NULL,int n=0){minheap<huffmannode> hp;huffmannode *first,*second,work;huffmannode *parent1;for(int i=0;i<n;i++){work.data=w[i];work.leftchild=NULL,work.rightchild=NULL,work.parent=NULL;hp.insert(work);}for(int i=0;i<n-1;i++){//通过个数限定解决可能first和second无值的情况.注意removemin返回的是bool类型，first=new huffmannode;second= new huffmannode;hp.removemin(*first);hp.removemin(*second);mergetree(parent1,first,second);hp.insert(*parent1);//insert是插入到最小堆中所以他的第一和第二小元素是有先后顺序的}root=parent1;//将最终的父节点赋值给root节点.}huffmannode* getroot(){return root;}void bianma(huffmannode*&op){//根节点初始化为空字符串if(op==NULL){return;}if(op->rightchild==NULL&&op->leftchild==NULL){//尾节点就是我们要的解，即编码后的字符串.pp[op->data]=op->ss;return;//记得返回，因为之后为NULL了但是又没有判断条件}if(op->leftchild!=NULL){op->leftchild->ss=op->ss+"0";}if(op->rightchild!=NULL){op->rightchild->ss=op->ss+"1";}bianma(op->leftchild);bianma(op->rightchild);}void jiema(string oo,vector<char> &io,string op,int left){//不能直接使用io的长度因为可能长度过长，不是他的实际长度if(left==op.length()){//这种条件下，如果满足了会回到原来的位置，cout<<oo<<endl;//可能存在多种解return;}for(int i=0;i<len;i++){if(op.substr(left,(pp[p[io[i]]]).size())==pp[p[io[i]]]){oo+=io[i];int cnt=left;cnt+=pp[p[io[i]]].size();//因为从0开始jiema(oo,io,op,cnt);//使用这样的局部变量才能在这次满足之后下一个循环再使用时为原来的起始值。。}}return;//表示失败时自动返回} }; void output(huffmannode&op) {if (op.data == 0)return;cout << op.data << endl;if (op.leftchild == NULL) {cout << "true" << endl;}cout << (*op.leftchild).data << endl;output(*op.leftchild);output(*op.rightchild); } int main() {string str;cin >> str;for (int i = 0; i < str.length(); i++) {if (!p.count(str[i])) {p[str[i]] = 1;} else {p[str[i]]++;}}map<char, int>::iterator io = p.begin();float *i = new float[100];vector<char> ent(str.length(), 0);for (; io != p.end(); io++) {i[len] = io->second;ent[len] = io->first;cout << i[len] << endl;len++;}huffmantree ip(i, len);huffmannode *end = ip.getroot();//Huffman编码ip.bianma(end);for (int k = 0; k < len; k++) {cout << ent[k] << "的编码为" << pp[p[ent[k]]] << endl;}string iop;cin >> iop;string re = "";//Huffman解码ip.jiema(re, ent, iop, 0);return 0; }

求解字符串队列哈夫曼序列的长度

#include <bits/stdc++.h> //万能头文件，vs2019中需自己设置 using namespace std; string s; map<char, int> mp; priority_queue<int, vector<int>, greater<int>> q; //升序排列int main() {getline(cin, s);int len = s.length();for (int i = 0; i < len; i++) { //记录字符与其对应的出现的次数if (mp.find(s[i]) == mp.end()) {mp[s[i]] = 1;} else {mp[s[i]]++;}}for (map<char, int>::iterator it = mp.begin(); it != mp.end(); it++) {q.push(it->second); //字符出现的次数入队}int ans = 0;//记录结果while (q.size() != 1) {int a, b, temp;//a，b记录最小的两个次数a = q.top();q.pop();b = q.top();q.pop();temp = a + b; //队列中最小的两个次数相加ans += temp;q.push(temp);//最小的两个次数相加再次入队，优先队列自行排序}cout << ans << endl;return 0; }

总结

以上是生活随笔为你收集整理的数据结构-Huffman树的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。