終于寫完了~~我覺得那個解碼編碼部分還能優化~~?
如果有更好的方法歡迎賜教~~呵呵
題目:
解法:
??1?
#include?<iostream>
??2?
#include?<windows.h>
??3?
#include?<tchar.h>
??4?
??5?
#define?MAXVALUE?0xffff
??6?
using?namespace?std?;
??7?
??8?
typedef?struct{
??9?
????char?data?;
?10?
????int?value?;
?11?
????int?parent?;
?12?
????int?lchild?;
?13?
????int?rchild?;
?14?
}?HfmTree;??//哈夫曼樹結構?
?15?
?16?
typedef?struct?{
?17?
????int?count?;
?18?
????char?code[10]?;
?19?
}?HfmCode?,*pHfmCode;???//哈夫曼樹編碼時儲存編碼序列結構
?20?
?21?
void?CreateHfm(HfmTree?hfmt[]?,?int?bufcount)??//建立哈夫曼樹
?22?
{
?23?
????for(?int?i?=?0?;?i?<?2*bufcount-1?;?i++?)
?24?
????{
?25?
????????hfmt[i].parent?=?-1?;
?26?
????????hfmt[i].lchild?=?-1?;
?27?
????????hfmt[i].rchild?=?-1?;
?28?
????}
?29?
?30?
????for(?int?i?=?0?;?i?<?bufcount-1?;?i?++?)
?31?
????{
?32?
????????int?min1?=?MAXVALUE,?min2?=?MAXVALUE?,tem1?=?0?,?tem2?=?0?;
?33?
?34?
????????for(int?j?=?0?;?j?<?bufcount+i?;?j++?)????//找出權值最小的2個樹
?35?
????????{
?36?
????????????if(?hfmt[j].parent?==?-1?&&?hfmt[j].value?<?min1?)
?37?
????????????{
?38?
????????????????min2?=?min1?;
?39?
????????????????tem2?=?tem1?;
?40?
????????????????min1?=?hfmt[j].value?;
?41?
????????????????tem1?=?j?;
?42?
????????????}else?if(?hfmt[j].parent?==?-1?&&?hfmt[j].value?<?min2)
?43?
????????????{
?44?
????????????????min2?=?hfmt[j].value?;
?45?
????????????????tem2?=?j?;
?46?
????????????}
?47?
????????}
?48?
????????//合并樹
?49?
????????????hfmt[tem1].parent?=?bufcount?+?i?;
?50?
????????????hfmt[tem2].parent?=?bufcount?+?i?;
?51?
????????????hfmt[bufcount+i].lchild???=?tem1?;
?52?
????????????hfmt[bufcount+i].rchild???=?tem2?;
?53?
????????????hfmt[bufcount+i].value?=?hfmt[tem1].value?+?hfmt[tem2].value??;
?54?
????}
?55?
}
?56?
????
?57?
pHfmCode?GetHfmCode(HfmTree?hfmt[]?,?char?target?,?int?bufcount)??//根據哈夫曼樹編碼函數
?58?
{
?59?
????int?pos?,?temp?,?count?=?0?;
?60?
????pHfmCode?code?=?new?HfmCode?;
?61?
????code->count?=?0?;
?62?
?63?
????for(?int?i?=?0?;?i?<?bufcount?;?i++?)
?64?
????{
?65?
????????if(?hfmt[i].data?==?target?)??//找到目標字符在樹中位置
?66?
????????{????????
?67?
????????????pos?=?i?;
?68?
????????????break?;
?69?
????????}
?70?
????}
?71?
????
?72?
????while(1)??//從葉子逆推到根節點,所得的序列倒序就是字符對應的哈夫曼編碼
?73?
????{
?74?
????????temp?=?hfmt[pos].parent?;
?75?
????????
?76?
????????if(temp?==?-1)
?77?
????????????break?;
?78?
?79?
????????if(?hfmt[temp].lchild?==?pos?)
?80?
????????????code->code[count++]?=?0+'0'?;??//轉換成字符串存放
?81?
????????else
?82?
????????????code->code[count++]?=?1+'0'?;
?83?
?84?
????????pos?=?temp?;
?85?
????????code->count++?;
?86?
????}
?87?
?88?
????return?code?;????
?89?
}
?90?
?91?
void?CodingBuf(char?ipbuf[]?,?HfmTree?*hfmt?,?int?bufcount)???//講得到的字符串進行編碼,然后寫入文件
?92?
{
?93?
????FILE?*codef?;
?94?
?95?
?????codef?=?_tfopen("codefile.txt"?,?"w+"?)?;
?96?
????
?97?
????while(1)
?98?
????{
?99?
????????if(*ipbuf?==?'\0')??//如果字符串遍歷結束就跳出循環
100?
????????????break?;
101?
102?
????????pHfmCode?code?=?GetHfmCode(hfmt?,?*ipbuf?,?bufcount)?;?//獲得哈夫曼編碼
103?
????????
104?
????????for(?int?i?=?code->count?;?i?>?0?;?i--?)??//要倒著打印,應為之前是逆推到樹根的,得到的序列也是倒序的
105?
????????????fwrite(&code->code[i-1]?,?sizeof(char)?,?1?,?codef?)?;
106?
????????
107?
????????ipbuf++?;
108?
????}
109?
110?
????fclose(codef)?;
111?
}
112?
113?
void?DecodingBuf(HfmTree?hfmt[]?,?char?codefile[]?,?int?bufcount)??//哈夫曼解碼函數
114?
{
115?
????????FILE?*textf?;
116?
????????textf?=?_tfopen("textfile.txt"?,?"w+")?;
117?
????????char?decodebuf[100]?=?{?0?}??,?*temp?=?codefile?;
118?
????????int?count?=?bufcount*2-2??,?i?=?0;
119?
/*
120?
根據輸入的編碼信息,從樹根開始向下遍歷,
121?
只要到葉子的地方就儲存葉子數據,然后回到樹根繼續遍歷
122?
知道將輸入的編碼信息遍歷完為止
123?
*/
124?
????????do?
125?
????????{
126?
????????????if(?hfmt[count].data?!=?0?)
127?
????????????{
128?
????????????????decodebuf[i++]?=?hfmt[count].data?;
129?
????????????????count?=?bufcount*2-2?;
130?
????????????}
131?
????????????if(?*temp?==?'0'?)
132?
????????????????count?=?hfmt[count].lchild?;
133?
????????????else
134?
????????????????count?=?hfmt[count].rchild?;
135?
????????}while(?*?(temp++)?!=?'\0')?;
136?
137?
????????fwrite(decodebuf?,?sizeof(char)?,?100?,?textf?)?;??//解碼信息寫入文件
138?
139?
????????fclose(textf)?;
140?
}
141?
142?
143?
??
144?
int?main(void)
145?
{
146?
????FILE?*hfmf?,?*codef?,*textf?;
147?
????char?ipbuf[100]?;
148?
????int?bufcount?=?4?;
149?
????HfmTree?hfmt[19]?=?{0}?;
150?
151?
//----------------------------------------------信息收集部分
152?
????cout<<"輸入終端字符集大小(1-10)"<<endl?;
153?
????cin>>bufcount?;
154?
155?
????for(int?i?=?0?;?i?<?bufcount?;?i++?)
156?
????{
157?
????cout<<"請輸入終端字符內容:"<<endl?;
158?
????cin>>hfmt[i].data?;
159?
????cout<<"請輸入終端字符權值:(0-9)"<<endl?;
160?
????cin>>hfmt[i].value?;
161?
????}
162?
163?
164?
//-----------------------------------------------建哈夫曼樹部分
165?
????CreateHfm(hfmt?,bufcount?)?;
166?
167?
????//打印哈夫曼樹
168?
????for(int?i?=?0?;?i?<?bufcount*2-1?;?i++)
169?
????{
170?
????????cout<<"id"<<'\t'<<"data"<<'\t'<<"parent"<<'\t'<<"lchild"<<'\t'<<"rchild"<<'\t'<<"value"<<endl?;
171?
????????cout<<i<<'\t'<<hfmt[i].data<<'\t'<<hfmt[i].parent<<'\t'<<hfmt[i].lchild<<'\t'<<hfmt[i].rchild<<'\t'<<hfmt[i].value<<endl?;
172?
????}
173?
174?
????hfmf?=?_tfopen("hfmtree.txt"?,?"w+"?)?;
175?
????
176?
177?
178?
????char?tittle[]="id????data????parent????lchild????rchild????values"?;
179?
????tittle[strlen(tittle)]?=?'\n'?;
180?
????fwrite(tittle?,?sizeof(char)?,?sizeof(tittle)?,?hfmf?)?;
181?
????char?data[1000]?={0},*buf?=?data??,?intbuf[10]?={?0?};
182?
????for(int?i?=?0?;?i?<?bufcount*2-1?;?i++)
183?
????{
184?
????????_itoa(i?,??intbuf?,?10?)?;
185?
????????memcpy(buf?,??intbuf?,?strlen(intbuf)*sizeof(char)?)?;
186?
????????buf?+=?strlen(intbuf)?;?
187?
????????*buf?=?'\t';?buf++?;
188?
????????*buf?=?hfmt[i].data?;?buf++?;
189?
????????*buf?=?'\t';?buf++?;
190?
????????
191?
????????_itoa(hfmt[i].parent?,??intbuf?,?10?)?;
192?
????????memcpy(buf?,??intbuf?,?strlen(intbuf)*sizeof(char)?)?;
193?
????????buf?+=?strlen(intbuf)?;
194?
????????*buf?=?'\t';?buf++?;
195?
196?
????????_itoa(hfmt[i].lchild?,??intbuf?,?10?)?;
197?
????????memcpy(buf?,??intbuf?,?strlen(intbuf)*sizeof(char)?)?;
198?
????????buf?+=?strlen(intbuf)?;
199?
????????*buf?=?'\t';?buf++?;
200?
????????
201?
????????_itoa(hfmt[i].rchild?,??intbuf?,?10?)?;
202?
????????memcpy(buf?,??intbuf?,?strlen(intbuf)*sizeof(char)?)?;
203?
????????buf?+=?strlen(intbuf)?;
204?
????????*buf?=?'\t';?buf++?;
205?
206?
????????_itoa(hfmt[i].value?,??intbuf?,?10?)?;
207?
????????memcpy(buf?,??intbuf?,?strlen(intbuf)*sizeof(char)?)?;
208?
????????buf?+=?strlen(intbuf)?;
209?
????????*buf?=?'\n';?buf++?;
210?
211?
????}
212?
????fwrite(data?,?sizeof(char)?,?1000?,?hfmf?);
213?
????
214?
????cout<<buf<<endl?;
215?
//-----------------------------------------------編碼部分
216?
????cout<<"輸入要編碼的字符串"<<endl?;
217?
????cin>>ipbuf?;
218?
219?
????CodingBuf(ipbuf?,?hfmt?,?bufcount?)?;
220?
????
221?
????codef?=?_tfopen("codefile.txt"?,?"r+")?;
222?
????char?codefile[100]?=?{0};
223?
224?
????fread(codefile?,?sizeof(char)?,?100?,?codef)?;
225?
????
226?
????cout<<"編碼結果"<<endl?;
227?
????cout<<codefile<<endl?;
228?
229?
????system("pause")?;
230?
//-----------------------------------------------解碼部分
231?
????cout<<"解碼ING
"<<endl?;
232?
????DecodingBuf(hfmt?,?codefile?,?bufcount?)?;
233?
234?
????cout<<"解碼結果:"<<endl??;
235?
????textf?=?_tfopen("textfile.txt"?,?"r+"?)?;
236?
????memset(codefile?,?0?,?100)?;
237?
238?
????fread(codefile?,?sizeof(char)?,?100?,?textf?)?;
239?
240?
????cout<<codefile<<endl?;
241?
????
242?
????system("pause")?;
243?
244?
245?
246?
????fclose(?textf?)?;
247?
????fclose(?hfmf?)?;
248?
????fclose(codef)?;
249?
????return?1;
250?
251?
}
252?
253?
254?