基于順序表創建赫夫曼樹
說明：赫夫曼樹在信息傳輸上有很多的用途，剛剛學習二叉樹，就遇上了赫夫曼，在學習算法的時候學到了不少的的東西。
代碼實現：
1?//哈弗曼節點數據結構
??2?struct?HuffmanNode//數據結構的設計是本赫夫曼的一大敗筆，我居然用了里面的很多東西我居然用了指針。
??3?{
??4?????int?weight;
??5?????char?data;
??6?????HuffmanNode?*?leftChild,*rightChild,*parent;
??7?????HuffmanNode():leftChild(NULL),rightChild(NULL),parent(NULL){}
??8?????HuffmanNode(int?elem,HuffmanNode?*?left=NULL,
??9?????????HuffmanNode?*?right=NULL,
?10?????????HuffmanNode?*?pr=NULL):weight(elem),leftChild(left),rightChild(right){}
?11?};
?12?
?13?//哈弗曼類
?14?class?Huffman
?15?{
?16?private:
?17?????char?**?HuffmanCode;
?18?public:
?19?????HuffmanNode?*?HF;
?20?????~Huffman()
?21?????{
?22?????????delete?HF;
?23?????????delete?[]?HuffmanCode;
?24?????}
?25?????void?CreateHuffmanTree(int?n);
?26?????void?TranslateCode(char?*?code,int?sz,int?n);
?27?????void?Safe(char?*?text,int?n);
?28?protected:
?29?????void?Select(int?n,int?&s1,int?&s2);
?30?};
?31?
?32?//打印哈夫曼樹
?33?void?ShowRHuffman(HuffmanNode*?HF,?int?n);
?34?void?ShowLHuffman(HuffmanNode?*?HF,?int?n);
?35?void?ShowHuffman(HuffmanNode?*?HF,?int?n);
?36?
?37?
?38?#include?<iostream>
?39?using?namespace?std;
?40?#include?"Huffman.h"
?41?#include?<fstream>
?42?
?43?char?**?HuffmanCode;
?44?
?45?
?46?void?Space(int?n)
?47?{
?48?????for?(int?i?=?0;?i?<?n;?i++)?cout?<<?"?";
?49?}
?50?
?51?void?ShowRHuffman(HuffmanNode*?HF,?int?n)
?52?{
?53?????if?(!HF)
?54?????{
?55?????????cout?<<?endl;
?56?????????return;
?57?????}
?58?????else
?59?????{
?60?????????{
?61?????????????ShowRHuffman(HF->rightChild,n+5);
?62?????????????Space(n);
?63?????????????cout?<<?HF->weight?<<"?";
?64?????????????cout?<<?HF->data;
?65?????????????ShowLHuffman(HF->leftChild,n+5);?
?66?????????}
?67?????}
?68?}
?69?
?70?void?ShowLHuffman(HuffmanNode?*?HF,?int?n)
?71?{
?72?????if?(!HF)
?73?????{
?74?????????cout?<<?endl;
?75?????????return;
?76?????}
?77?????else
?78?????{
?79?????????{
?80?????????????ShowLHuffman(HF->leftChild,n+5);
?81?????????????Space(n);
?82?????????????cout?<<?HF->weight?<<"?";
?83?????????????cout?<<?HF->data;
?84?????????????ShowRHuffman(HF->rightChild,n+5);
?85?????????}
?86?????}
?87?}
?88?
?89?void?ShowHuffman(HuffmanNode?*?HF,?int?n)
?90?{
?91?????if?(!HF)
?92?????{
?93?????????cout?<<?endl;
?94?????????return;
?95?????}
?96?????else
?97?????{
?98?????????ShowRHuffman(HF->rightChild?,n+4);
?99?????????cout?<<?HF->weight?<<"?";
100?????????cout?<<HF->data;
101?????????ShowLHuffman(HF->leftChild?,n+4);
102?????}
103?}
104?
105?void?Huffman::Select(int?n,int?&s1,int?&s2)
106?{
107?????int?i;//純粹是計數
108?????s1=0;//跟蹤第一個目標
109?????s2=1;//跟蹤第二個目標
110?
111?????HuffmanNode?*?p?;//跟蹤哈弗曼節點
112?????p?=?HF;
113?????int?fst;
114?????int?snd;
115?
116?????//找出第一個和第二個父節點非NULL的節點，也就是尚未處理的節點
117?????i=0;
118?????while(p->parent)
119?????{
120?????????i++;
121?????????p++;
122?????}
123?????fst?=?p->weight;
124?????s1?=?i;
125?????p++;
126?????i++;
127?
128?????while(p->parent)
129?????{
130?????????i++;
131?????????p++;
132?????}
133?????snd?=?p->weight?;
134?????s2=?i;
135?
136?????//循環前的數據準備
137?????p++;
138?????int?indexp?=?s2+1;
139?
140?????if(fst<=snd)//fst始終是權重比較大的節點，在進入循環之前進行調換
141?????{
142?????????swap(fst,snd);
143?????????swap(s1,s2);
144?????}
145?????for(i=indexp;i<=n;i++,p++,indexp++)
146?????{
147?????????if(!p->parent)
148?????????{
149?????????????if(p->weight<fst)?
150?????????????{????????
151?????????????????fst?=?p->weight;
152?????????????????s1?=?indexp;
153?????????????}
154?????????????if(fst<snd)//fst始終是權重比較大的節點
155?????????????{
156?????????????????swap(fst,snd);
157?????????????????swap(s1,s2);
158?????????????}
159?????????}
160?????}
161?}
162?
163?void?Huffman::CreateHuffmanTree(int?n)
164?{
165?????int?i;
166?????int?m?=?n*2-1;//需要的空間為n*2-1
167?????char?test;
168?
169?????if(n<=1)return;//如果是1，啥都別干了
170?
171?????//從文件當中讀取權重和字符
172?????ifstream?fs("hfmTree.txt",ios::in);
173?
174?????HuffmanNode?*?p;
175?????HF?=?new?HuffmanNode[m];
176?????p?=?HF;
177?????
178?????/*讀取過程，收獲>>重載符會忽略空
179?????格和換行符，當然，在遇到這些的時候
180?????讀取也會停下來*/
181?????for(i=0;?i<n?;i++)
182?????{
183?????????fs.get(p->data);
184?????????fs.get(test);
185?????????fs>>p->weight?;
186?????????fs.get(test);
187?????????//cout?<<?p->weight<<"?";
188?????????p++;
189?????}
190?????fs.close();
191?
192?????/*構建哈夫曼樹，因為在這里我把哈弗曼的數據結
193?????設計成了指針，所以用的都是指針，其實可以更簡單，
194?????就是按書上的用數組的下標。
195?????下面這種做法有點生硬了，掉進了鏈表的思路里。*/
196?????int?s1,s2;
197?????for(i=n;i<=m-1;i++)
198?????{
199?????????Select(i-1,s1,s2);????//將較大的下標放在s1
200?????????HF[i].leftChild?=?HF+s2;//左邊較小
201?????????HF[i].rightChild?=?HF+s1;//右邊較大
202?????????HF[s1].parent?=?HF+i;
203?????????HF[s2].parent?=?HF+i;
204?????????(HF+i)->weight?=?HF[s1].weight?+HF[s2].weight;
205?????}
206?
207?????//打印測試數據
208?????
209?????p?=?HF;
210?????for(i=0;i<m;i++)
211?????{
212?????????cout?<<?p->weight?<<"?";
213?????????p++;
214?????}
215?????cout?<<endl;
216?????
217?
218?????HuffmanCode?=?new?char*?[n];
219?????char?*?cd?=?new?char[n];
220?????cd[n-1]?=?0;
221?
222?????/*p用來記錄當前節點的父節點，q用來記錄當前節點*/
223?????p?=?HF;
224?????HuffmanNode?*?q;
225?????int?start;
226?
227?????for(int?i=0;i<n;i++)
228?????{
229?????????start?=?n-1;//將start放在最后一個字符
230?????????for(q?=?HF+i,p=(HF+i)->parent?;p!=NULL;q=p,p=p->parent)
231?????????{
232?????????????if(p->leftChild?==?q)
233?????????????????cd[--start]?=?'0';
234?????????????else
235?????????????????cd[--start]?=?'1';
236?????????}
237?????????HuffmanCode[i]?=?new?char[n-start];????//為當前的字符譯碼分配存儲空間
238?????????strcpy(HuffmanCode[i],&cd[start]);
239?
240?????????//打印測試數據
241?????????
242?????????cout?<<?&cd[start]?<<endl;
243?????????
244?????}
245?????delete(cd);
246?}
247?
248?void?Huffman::TranslateCode(char?*?code,int?sz,int?n)
249?{
250?????int?i;//純粹是計數
251?
252?????HuffmanNode?*?p?=?HF+(2*n-2);//指向根節點
253?????cout?<<?"原文：";
254?????for(i=0;i<sz;i++)
255?????{
256?????????if(p->rightChild!=NULL&&p->leftChild!=NULL)
257?????????{
258?????????????if(code[i]=='0')
259?????????????????p?=?p->leftChild;
260?????????????else
261?????????????????p?=?p->rightChild?;????????
262?
263?????????????if(p->rightChild==NULL&&p->leftChild==NULL)?
264?????????????{
265?????????????????cout?<<?p->data;
266?????????????????p?=?HF+(2*n-2);//解碼成功，就指向根節點
267?????????????}
268?????????}
269?????}
270?}
271?
272?void?Huffman::Safe(char?*?text,int?n)
273?{
274?????ofstream?ofs;
275?????ofs.open("CodeFile.txt",ios::out|ios::beg);
276?????int?i;
277?????for(int?j=0;text[j]!=NULL;j++)
278?????{
279?????????i=0;
280?????????for(;i<n;i++)
281?????????{
282?????????????if((HF+i)->data?==?text[j])
283?????????????{
284?????????????????ofs?<<?HuffmanCode[i];//寫入CodeFile.txt文件
285?????????????????break;
286?????????????}
287?????????}
288?????}
289?????ofs.close();
290?}
291?
292?
293?void?main()
294?{
295?????/*預先在ToBeTran.txt文件當中存入要加密的文本*/
296?????fstream?ofs("hfmTree.txt",ios::out);
297?????fstream?ifs;
298?
299?????int?n;
300?????char?ch;
301?????char?blank;
302?????int?weight;
303?????char??TobeCode[50];
304?????char??Code[100];
305?????char?CodeInFile[50];
306?
307?????cout?<<?"輸入字符集的大小n：";
308?????cin?>>?n;
309?????int?count?=?n;
310?
311?????
312?????int?a?=?getchar();
313?????cout?<<?"輸入字符和其對應的權值："<<endl;
314?????while(count--)
315?????{
316?????????/*如下操作做得那么復雜就是為了能夠讀懂【空格】*/
317?????????cin.get(ch);
318?????????ofs.put(ch);
319?????????ofs.put('?');
320?????????cin.get(blank);//讀空格
321?????????cin?>>?weight;
322?????????ofs?<<?weight;
323?????????ofs.put('\n');
324?????????cin.get(blank);//讀空格
325?????}
326?????ofs.close();
327?????ofs.clear();
328?
329?????Huffman?HFtest;
330?????HFtest.CreateHuffmanTree(n);
331?
332?????ifs.open("ToBeTran.txt",ios::in|ios::beg);
333?????ifs?>>?TobeCode;
334?????cout?<<?"從ToBeTran文件當中讀取等待加密的文本："<<TobeCode<<endl;
335?????ifs.close();
336?????ifs.clear();
337?
338?????/*在與一個文件綁定之后，調用close來關閉流；但關閉
339?????流不能改變流內部的狀態，如果想用同一個文件流來
340?????關聯多個文件的話，最好讀另一個文件之前調用clear來
341?????清楚流的狀態*/
342?????HFtest.Safe(TobeCode,n);
343?
344?????
345?????ifs.open("CodeFile.txt",ios::in);
346?????ifs?>>?CodeInFile;
347?????cout?<<?"譯碼："<<CodeInFile<<endl;
348?????ifs.close();
349?????ifs.clear();
350?
351?????ifs.open("CodeFile.txt",ios::in);
352?????ifs?>>?Code;
353?????HFtest.TranslateCode(Code,strlen(Code),n);
354?????::ShowHuffman(HFtest.HF+(2*n-2),0);
355?
356?????ifs.close();?
??2?struct?HuffmanNode//數據結構的設計是本赫夫曼的一大敗筆，我居然用了里面的很多東西我居然用了指針。
??3?{
??4?????int?weight;
??5?????char?data;
??6?????HuffmanNode?*?leftChild,*rightChild,*parent;
??7?????HuffmanNode():leftChild(NULL),rightChild(NULL),parent(NULL){}
??8?????HuffmanNode(int?elem,HuffmanNode?*?left=NULL,
??9?????????HuffmanNode?*?right=NULL,
?10?????????HuffmanNode?*?pr=NULL):weight(elem),leftChild(left),rightChild(right){}
?11?};
?12?
?13?//哈弗曼類
?14?class?Huffman
?15?{
?16?private:
?17?????char?**?HuffmanCode;
?18?public:
?19?????HuffmanNode?*?HF;
?20?????~Huffman()
?21?????{
?22?????????delete?HF;
?23?????????delete?[]?HuffmanCode;
?24?????}
?25?????void?CreateHuffmanTree(int?n);
?26?????void?TranslateCode(char?*?code,int?sz,int?n);
?27?????void?Safe(char?*?text,int?n);
?28?protected:
?29?????void?Select(int?n,int?&s1,int?&s2);
?30?};
?31?
?32?//打印哈夫曼樹
?33?void?ShowRHuffman(HuffmanNode*?HF,?int?n);
?34?void?ShowLHuffman(HuffmanNode?*?HF,?int?n);
?35?void?ShowHuffman(HuffmanNode?*?HF,?int?n);
?36?
?37?
?38?#include?<iostream>
?39?using?namespace?std;
?40?#include?"Huffman.h"
?41?#include?<fstream>
?42?
?43?char?**?HuffmanCode;
?44?
?45?
?46?void?Space(int?n)
?47?{
?48?????for?(int?i?=?0;?i?<?n;?i++)?cout?<<?"?";
?49?}
?50?
?51?void?ShowRHuffman(HuffmanNode*?HF,?int?n)
?52?{
?53?????if?(!HF)
?54?????{
?55?????????cout?<<?endl;
?56?????????return;
?57?????}
?58?????else
?59?????{
?60?????????{
?61?????????????ShowRHuffman(HF->rightChild,n+5);
?62?????????????Space(n);
?63?????????????cout?<<?HF->weight?<<"?";
?64?????????????cout?<<?HF->data;
?65?????????????ShowLHuffman(HF->leftChild,n+5);?
?66?????????}
?67?????}
?68?}
?69?
?70?void?ShowLHuffman(HuffmanNode?*?HF,?int?n)
?71?{
?72?????if?(!HF)
?73?????{
?74?????????cout?<<?endl;
?75?????????return;
?76?????}
?77?????else
?78?????{
?79?????????{
?80?????????????ShowLHuffman(HF->leftChild,n+5);
?81?????????????Space(n);
?82?????????????cout?<<?HF->weight?<<"?";
?83?????????????cout?<<?HF->data;
?84?????????????ShowRHuffman(HF->rightChild,n+5);
?85?????????}
?86?????}
?87?}
?88?
?89?void?ShowHuffman(HuffmanNode?*?HF,?int?n)
?90?{
?91?????if?(!HF)
?92?????{
?93?????????cout?<<?endl;
?94?????????return;
?95?????}
?96?????else
?97?????{
?98?????????ShowRHuffman(HF->rightChild?,n+4);
?99?????????cout?<<?HF->weight?<<"?";
100?????????cout?<<HF->data;
101?????????ShowLHuffman(HF->leftChild?,n+4);
102?????}
103?}
104?
105?void?Huffman::Select(int?n,int?&s1,int?&s2)
106?{
107?????int?i;//純粹是計數
108?????s1=0;//跟蹤第一個目標
109?????s2=1;//跟蹤第二個目標
110?
111?????HuffmanNode?*?p?;//跟蹤哈弗曼節點
112?????p?=?HF;
113?????int?fst;
114?????int?snd;
115?
116?????//找出第一個和第二個父節點非NULL的節點，也就是尚未處理的節點
117?????i=0;
118?????while(p->parent)
119?????{
120?????????i++;
121?????????p++;
122?????}
123?????fst?=?p->weight;
124?????s1?=?i;
125?????p++;
126?????i++;
127?
128?????while(p->parent)
129?????{
130?????????i++;
131?????????p++;
132?????}
133?????snd?=?p->weight?;
134?????s2=?i;
135?
136?????//循環前的數據準備
137?????p++;
138?????int?indexp?=?s2+1;
139?
140?????if(fst<=snd)//fst始終是權重比較大的節點，在進入循環之前進行調換
141?????{
142?????????swap(fst,snd);
143?????????swap(s1,s2);
144?????}
145?????for(i=indexp;i<=n;i++,p++,indexp++)
146?????{
147?????????if(!p->parent)
148?????????{
149?????????????if(p->weight<fst)?
150?????????????{????????
151?????????????????fst?=?p->weight;
152?????????????????s1?=?indexp;
153?????????????}
154?????????????if(fst<snd)//fst始終是權重比較大的節點
155?????????????{
156?????????????????swap(fst,snd);
157?????????????????swap(s1,s2);
158?????????????}
159?????????}
160?????}
161?}
162?
163?void?Huffman::CreateHuffmanTree(int?n)
164?{
165?????int?i;
166?????int?m?=?n*2-1;//需要的空間為n*2-1
167?????char?test;
168?
169?????if(n<=1)return;//如果是1，啥都別干了
170?
171?????//從文件當中讀取權重和字符
172?????ifstream?fs("hfmTree.txt",ios::in);
173?
174?????HuffmanNode?*?p;
175?????HF?=?new?HuffmanNode[m];
176?????p?=?HF;
177?????
178?????/*讀取過程，收獲>>重載符會忽略空
179?????格和換行符，當然，在遇到這些的時候
180?????讀取也會停下來*/
181?????for(i=0;?i<n?;i++)
182?????{
183?????????fs.get(p->data);
184?????????fs.get(test);
185?????????fs>>p->weight?;
186?????????fs.get(test);
187?????????//cout?<<?p->weight<<"?";
188?????????p++;
189?????}
190?????fs.close();
191?
192?????/*構建哈夫曼樹，因為在這里我把哈弗曼的數據結
193?????設計成了指針，所以用的都是指針，其實可以更簡單，
194?????就是按書上的用數組的下標。
195?????下面這種做法有點生硬了，掉進了鏈表的思路里。*/
196?????int?s1,s2;
197?????for(i=n;i<=m-1;i++)
198?????{
199?????????Select(i-1,s1,s2);????//將較大的下標放在s1
200?????????HF[i].leftChild?=?HF+s2;//左邊較小
201?????????HF[i].rightChild?=?HF+s1;//右邊較大
202?????????HF[s1].parent?=?HF+i;
203?????????HF[s2].parent?=?HF+i;
204?????????(HF+i)->weight?=?HF[s1].weight?+HF[s2].weight;
205?????}
206?
207?????//打印測試數據
208?????
209?????p?=?HF;
210?????for(i=0;i<m;i++)
211?????{
212?????????cout?<<?p->weight?<<"?";
213?????????p++;
214?????}
215?????cout?<<endl;
216?????
217?
218?????HuffmanCode?=?new?char*?[n];
219?????char?*?cd?=?new?char[n];
220?????cd[n-1]?=?0;
221?
222?????/*p用來記錄當前節點的父節點，q用來記錄當前節點*/
223?????p?=?HF;
224?????HuffmanNode?*?q;
225?????int?start;
226?
227?????for(int?i=0;i<n;i++)
228?????{
229?????????start?=?n-1;//將start放在最后一個字符
230?????????for(q?=?HF+i,p=(HF+i)->parent?;p!=NULL;q=p,p=p->parent)
231?????????{
232?????????????if(p->leftChild?==?q)
233?????????????????cd[--start]?=?'0';
234?????????????else
235?????????????????cd[--start]?=?'1';
236?????????}
237?????????HuffmanCode[i]?=?new?char[n-start];????//為當前的字符譯碼分配存儲空間
238?????????strcpy(HuffmanCode[i],&cd[start]);
239?
240?????????//打印測試數據
241?????????
242?????????cout?<<?&cd[start]?<<endl;
243?????????
244?????}
245?????delete(cd);
246?}
247?
248?void?Huffman::TranslateCode(char?*?code,int?sz,int?n)
249?{
250?????int?i;//純粹是計數
251?
252?????HuffmanNode?*?p?=?HF+(2*n-2);//指向根節點
253?????cout?<<?"原文：";
254?????for(i=0;i<sz;i++)
255?????{
256?????????if(p->rightChild!=NULL&&p->leftChild!=NULL)
257?????????{
258?????????????if(code[i]=='0')
259?????????????????p?=?p->leftChild;
260?????????????else
261?????????????????p?=?p->rightChild?;????????
262?
263?????????????if(p->rightChild==NULL&&p->leftChild==NULL)?
264?????????????{
265?????????????????cout?<<?p->data;
266?????????????????p?=?HF+(2*n-2);//解碼成功，就指向根節點
267?????????????}
268?????????}
269?????}
270?}
271?
272?void?Huffman::Safe(char?*?text,int?n)
273?{
274?????ofstream?ofs;
275?????ofs.open("CodeFile.txt",ios::out|ios::beg);
276?????int?i;
277?????for(int?j=0;text[j]!=NULL;j++)
278?????{
279?????????i=0;
280?????????for(;i<n;i++)
281?????????{
282?????????????if((HF+i)->data?==?text[j])
283?????????????{
284?????????????????ofs?<<?HuffmanCode[i];//寫入CodeFile.txt文件
285?????????????????break;
286?????????????}
287?????????}
288?????}
289?????ofs.close();
290?}
291?
292?
293?void?main()
294?{
295?????/*預先在ToBeTran.txt文件當中存入要加密的文本*/
296?????fstream?ofs("hfmTree.txt",ios::out);
297?????fstream?ifs;
298?
299?????int?n;
300?????char?ch;
301?????char?blank;
302?????int?weight;
303?????char??TobeCode[50];
304?????char??Code[100];
305?????char?CodeInFile[50];
306?
307?????cout?<<?"輸入字符集的大小n：";
308?????cin?>>?n;
309?????int?count?=?n;
310?
311?????
312?????int?a?=?getchar();
313?????cout?<<?"輸入字符和其對應的權值："<<endl;
314?????while(count--)
315?????{
316?????????/*如下操作做得那么復雜就是為了能夠讀懂【空格】*/
317?????????cin.get(ch);
318?????????ofs.put(ch);
319?????????ofs.put('?');
320?????????cin.get(blank);//讀空格
321?????????cin?>>?weight;
322?????????ofs?<<?weight;
323?????????ofs.put('\n');
324?????????cin.get(blank);//讀空格
325?????}
326?????ofs.close();
327?????ofs.clear();
328?
329?????Huffman?HFtest;
330?????HFtest.CreateHuffmanTree(n);
331?
332?????ifs.open("ToBeTran.txt",ios::in|ios::beg);
333?????ifs?>>?TobeCode;
334?????cout?<<?"從ToBeTran文件當中讀取等待加密的文本："<<TobeCode<<endl;
335?????ifs.close();
336?????ifs.clear();
337?
338?????/*在與一個文件綁定之后，調用close來關閉流；但關閉
339?????流不能改變流內部的狀態，如果想用同一個文件流來
340?????關聯多個文件的話，最好讀另一個文件之前調用clear來
341?????清楚流的狀態*/
342?????HFtest.Safe(TobeCode,n);
343?
344?????
345?????ifs.open("CodeFile.txt",ios::in);
346?????ifs?>>?CodeInFile;
347?????cout?<<?"譯碼："<<CodeInFile<<endl;
348?????ifs.close();
349?????ifs.clear();
350?
351?????ifs.open("CodeFile.txt",ios::in);
352?????ifs?>>?Code;
353?????HFtest.TranslateCode(Code,strlen(Code),n);
354?????::ShowHuffman(HFtest.HF+(2*n-2),0);
355?
356?????ifs.close();?
357?}
更多請訪問：http://daoluan.net
