c++实现哈夫曼编码cd=new（C++哈夫曼编码）

本文实例为大家分享了C++实现哈夫曼编码的具体代码，供大家参考，具体内容如下

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 #include<iostream> #include<string> #include<vector> #include<algorithm> using namespace std; int Max = 300; class tree{ public: char s; int num; tree *left; tree *right; tree(){ s= '!'; num = 0; left = 0; right = 0; } tree(char a,int n,tree* p1,tree* p2){ s = a; num = n; left = p1; right = p2; } }; vector<tree *> open; /********************************* **中序遍历输出各节点及其哈夫曼编码 *********************************/ void inorder(tree *t,string s){ if(t != 0){ inorder(t->left,s+'0'); if(t->s != '!') cout<<t->s<<":"<<s<<endl; inorder(t->right,s+'1'); } } int main(){ int a[Max]; for(int i = 0;i < Max;i++) a[i] = 0; //初始化数组 string s; cout<<"请输入字符串："; cin>>s; vector<char> v; vector<char>::iterator vit; for(int i = 0;i < s.length();i ++){ a[s[i]]++; //确定每个字符出现的次数（频率） vit = find(v.begin(),v.end(),s[i]); if(vit == v.end()) //相同的字符只保留一个 v.push_back(s[i]); } for(int i = 0;i < v.size();i ++){ tree *n = new tree(); n->s = v[i]; n->num = a[v[i]]; open.push_back(n); //存入open表中 } /************************ ** **构造哈夫曼树 ** *************************/ tree *root; while(open.size() != 1){ tree *min1,*min2; //min1,min2是当前open表中num值最小的节点 int sit1,sit2; min1 = open.front(); sit1 = 0; for(int i = 0;i < open.size();i++){ if(open[i]->num < min1->num){ min1 = open[i]; sit1 = i; } } open.erase(open.begin()+sit1); min2 = open.front(); sit2 = 0; for(int i = 0;i < open.size();i++){ if(open[i]->num < min2->num){ min2 = open[i]; sit2 = i; } } open.erase(open.begin()+sit2); tree *t = new tree('!',min1->num + min2->num,min1,min2); //构造新节点，左右指针指min1和min2 open.push_back(t); //存入open表中 root = t; } cout<<"它的哈夫曼编码为："<<endl; string s1 = ""; inorder(root,s1); return 0; }```