基于顺序表哈夫曼树-白红宇

基于顺序表创建赫夫曼树

说明：赫夫曼树在信息传输上有很多的用途，刚刚学习二叉树，就遇上了赫夫曼，在学习算法的时候学到了不少的的东西。

代码实现：

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 };

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 };

32 //打印哈夫曼树

33 void ShowRHuffman(HuffmanNode* HF, int n);

34 void ShowLHuffman(HuffmanNode * HF, int n);

35 void ShowHuffman(HuffmanNode * HF, int n);

38 #include <iostream>

39 using namespace std;

40 #include "Huffman.h"

41 #include <fstream>

43 char ** HuffmanCode;

46 void Space(int n)

47 {

48 for (int i = 0; i < n; i++) cout << " ";

49 }

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 }

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 }

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