{"id":279,"date":"2011-09-24T13:29:25","date_gmt":"2011-09-24T05:29:25","guid":{"rendered":"http:\/\/wangkaixuan.tech\/?p=279"},"modified":"2020-06-06T13:47:20","modified_gmt":"2020-06-06T05:47:20","slug":"%e6%95%b0%e6%8d%ae%e7%bb%93%e6%9e%84_%e6%a0%91_%e8%b5%ab%e5%a4%ab%e6%9b%bc%e6%a0%91%e5%8f%8a%e8%b5%ab%e5%a4%ab%e6%9b%bc%e7%bc%96%e7%a0%81_c%e5%ae%9e%e7%8e%b0","status":"publish","type":"post","link":"http:\/\/www.wangkaixuan.tech\/?p=279","title":{"rendered":"\u6570\u636e\u7ed3\u6784_\u6811_\u8d6b\u592b\u66fc\u6811\u53ca\u8d6b\u592b\u66fc\u7f16\u7801_C++\u5b9e\u73b0"},"content":{"rendered":"\n

\u4f20\u8bf4\u4e2d\u7684\u6700\u4f18\u4e8c\u53c9\u6811\u2014\u2014\u8d6b\u592b\u66fc(Huffman)\u6811<\/p>\n\n\n\n

\u672c\u4f8b\u91c7\u7528\u5982\u4e0b\u5b58\u50a8\u7ed3\u6784\uff1a<\/p>\n\n\n\n

\"\"<\/figure>\n\n\n\n

\u5b9e\u4f8b\uff1a<\/p>\n\n\n\n

\"\"<\/figure>\n\n\n\n

\u4e0b\u9762\u8fd9\u4e2a\u662f\u4e25\u851a\u654f\u300a\u6570\u636e\u7ed3\u6784\u300bC\u8bed\u8a00\u7248\u4e0a\u7684\u8d6b\u592b\u66fc\u7f16\u7801\u5b58\u50a8\u7ed3\u6784 \u6211\u6362\u4e86\u4e00\u79cd\u65b9\u5f0f\uff0c\u5f00\u4e86\u4e00\u4e2a\u6808\u7136\u540e\u53cd\u590d\u7528\uff0c\u5177\u4f53\u89c1\u4ee3\u7801\uff1a<\/p>\n\n\n\n

\"\"<\/figure>\n\n\n\n

head.h<\/p>\n\n\n\n

#include<iostream>\n#include<stack>\nusing namespace std;\n\nclass NODE\n{\npublic:\n\tNODE();\n\tint weight, parent, lchild, rchild;\n};\n\nNODE::NODE()\n{\n\tweight = parent = lchild = rchild = 0;\n}\n\nclass HUFFMAN\n{\npublic:\n\tHUFFMAN();\n\tvoid GetHuffmanCode(); \/\/\u83b7\u5f97\u8d6b\u592b\u66fc\u7f16\u7801\u4e3b\u8c03\u51fd\u6570\nprivate:\n\tvoid GetHuffmanNode(); \/\/\u83b7\u5f97\u8282\u70b9\n\tvoid HuffmanCoding(); \/\/\u7f16\u7801\n\tvoid PrintHuffmanCode(); \/\/\u8f93\u51fa\u7f16\u7801\n\tvoid Select(int&, int&); \/\/\u4ece\u68ee\u6797\u4e2d\u9009\u62e9\u4e24\u9897\u6743\u503c\u8f83\u5c0f\u7684\u6811\n\tint len, cur; \/\/len\u8868\u793a\u8868\u957f\u5ea6cur\u8868\u793a\u5f53\u524d\u6307\u793a\u7684\u8282\u70b9\n\tNODE *HT; \/\/HT\u6307\u5411\u8868\u5934\u7ed3\u70b9\n};\n\nHUFFMAN::HUFFMAN()\n{\n\tlen = cur = 0;\n\tHT = NULL;\n}\n\nvoid HUFFMAN::GetHuffmanCode() \/\/\u83b7\u5f97\u8d6b\u592b\u66fc\u7f16\u7801\u4e3b\u8c03\u51fd\u6570\n{\n\tGetHuffmanNode();\n\tHuffmanCoding();\n\tPrintHuffmanCode();\n}\n\nvoid HUFFMAN::GetHuffmanNode() \/\/\u83b7\u5f97\u8282\u70b9\n{\n\tcout << \"GetHuffmanNode Called !\" << endl << endl;\n\tcout << \"Please Enter The Weight Of Each Node .\" << endl << endl;\n\tNODE node[100];\n\tint i = 0, t;\n\twhile (cin >> t)\n\t{\n\t\tnode[i++].weight = t;\n\t}\n\tcin.clear();\n\tlen = i;\n\tHT = new NODE[2 * i];\n\tfor (i = 1; i <= len; i++)\n\t\t*(HT + i) = node[i - 1];\n\tcur = len + 1;\n}\n\nvoid HUFFMAN::HuffmanCoding() \/\/\u7f16\u7801\n{\n\tcout << \"HuffmanCoding Called !\" << endl << endl;\n\twhile (cur < 2 * len) \/\/\u5efa\u6811\u8fc7\u7a0b\n\t{\n\t\tint a, b;\n\t\tSelect(a, b); \/\/\u9009\u62e9\u4e24\u9897\u6743\u503c\u8f83\u5c0f\u7684\u5b50\u6811\n\t\t(HT + cur)->weight = (HT + a)->weight + (HT + b)->weight; \/\/\u8fde\u63a5\u6210\u65b0\u6811\u5e76\u66f4\u8be5\u5176\u6743\u503c\n\t\t(HT + cur)->lchild = a;\n\t\t(HT + cur)->rchild = b;\n\t\tcur++;\n\t}\n}\n\nvoid HUFFMAN::PrintHuffmanCode() \/\/\u8f93\u51fa\u7f16\u7801\n{\n\tcout << \"PrintHuffmanCode Called !\" << endl << endl;\n\tcout << \"The Huffman Code Is :\" << endl << endl;\n\tstack<int> s; \/\/\u5b9a\u4e49\u4e00\u4e2a\u6808\u5b58\u653e\u7f16\u7801\n\tfor (int i = 1; i <= len; i++) \/\/\u4ece\u53f6\u5b50\u8282\u70b9\u5411\u4e0a\u67e5\u627e\u5230\u6839\u8282\u70b9\n\t{\n\t\tcout << (HT + i)->weight << \" : \";\n\t\tint j = i;\n\t\tdo\n\t\t{\n\t\t\tif ((HT + (HT + j)->parent)->lchild == j) \/\/\u5de6\u5b50\u6811\u8868\u793a\u4e3a0\n\t\t\t\ts.push(0);\n\t\t\telse\n\t\t\t\t\/\/\u53f3\u5b50\u6811\u8868\u793a\u4e3a1\n\t\t\t\ts.push(1);\n\t\t\tj = (HT + j)->parent; \/\/j\u6307\u5411\u5176\u7236\u8282\u70b9\n\t\t} while ((HT + j)->parent != 0); \/\/\u672a\u67e5\u627e\u5230\u6839\u8282\u70b9\u65f6\u8fdb\u884c\u67e5\u627e\n\t\twhile (!s.empty()) \/\/\u8f93\u51fa\u7f16\u7801\n\t\t{\n\t\t\tcout << s.top() << \" \";\n\t\t\ts.pop();\n\t\t}\n\t\tcout << endl;\n\t}\n}\n\nvoid HUFFMAN::Select(int &a, int &b) \/\/\u4ece\u68ee\u6797\u4e2d\u9009\u62e9\u4e24\u9897\u6743\u503c\u8f83\u5c0f\u7684\u6811\n{\n\tint min;\n\tbool first = true;\n\tfor (int i = 1; i < cur; i++) \/\/\u4ece\u8868\u4e2d\u83b7\u5f97min\u7684\u503c\u5e76\u5f97\u5230a\u5176\u4e2d\u6709\u4e2a\u5c0f\u6280\u5de7\u4e0d\u77e5\u9053\u60a8\u770b\u61c2\u4e86\u6728\u6709\uff1f\n\t{\n\t\tif ((HT + i)->parent == 0 && (first == true || (HT + i)->weight < min))\n\t\t{\n\t\t\ta = i;\n\t\t\tmin = (HT + i)->weight;\n\t\t\tif (first == true)\n\t\t\t\tfirst = false;\n\t\t}\n\t}\n\tfirst = true;\n\t(HT + a)->parent = cur; \/\/\u66f4\u6539a\u7684\u7236\u8282\u70b9\n\tfor (int i = 1; i < cur; i++) \/\/\u4ece\u8868\u4e2d\u83b7\u5f97min\u7684\u503c\u5e76\u5f97\u5230b\n\t{\n\t\tif ((HT + i)->parent == 0 && (first == true || (HT + i)->weight < min))\n\t\t{\n\t\t\tb = i;\n\t\t\tmin = (HT + i)->weight;\n\t\t\tif (first == true)\n\t\t\t\tfirst = false;\n\t\t}\n\t}\n\t(HT + b)->parent = cur; \/\/\u66f4\u6539b\u7684\u7236\u8282\u70b9\n\tif (a > b) \/\/\u5982\u6709\u5fc5\u8981\u8c03\u6574a\u3001b\u6b21\u5e8f\n\t{\n\t\tint t = a;\n\t\ta = b;\n\t\tb = t;\n\t}\n}\n<\/code><\/pre>\n\n\n\n
main.cpp<\/p>\n\n\n\n
#include<iostream>\n#include\"head.h\"\nusing namespace std;\n \nint main()\n{\n\tHUFFMAN ht;\n\tht.GetHuffmanCode();\n\tsystem(\"pause\");\n}<\/code><\/pre>\n\n\n\n
<\/p>\n","protected":false},"excerpt":{"rendered":"
\u4f20\u8bf4\u4e2d\u7684\u6700\u4f18\u4e8c\u53c9\u6811\u2014\u2014\u8d6b\u592b\u66fc(Huffman)\u6811 \u672c\u4f8b\u91c7\u7528\u5982\u4e0b\u5b58\u50a8\u7ed3\u6784\uff1a \u5b9e\u4f8b\uff1a \u4e0b\u9762\u8fd9\u4e2a\u662f\u4e25\u851a\u654f\u300a\u6570\u636e\u7ed3\u6784\u300bC\u8bed\u8a00\u7248\u4e0a\u7684\u8d6b\u592b\u66fc\u7f16\u7801\u5b58\u50a8\u7ed3\u6784 \u6211\u6362\u4e86\u4e00\u79cd\u65b9\u5f0f\uff0c\u5f00…<\/p>\n
 Read More  Read More<\/span><\/a><\/p>\n","protected":false},"author":2,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[9],"tags":[],"class_list":["post-279","post","type-post","status-publish","format-standard","hentry","category-06-02-"],"_links":{"self":[{"href":"http:\/\/www.wangkaixuan.tech\/index.php?rest_route=\/wp\/v2\/posts\/279","targetHints":{"allow":["GET"]}}],"collection":[{"href":"http:\/\/www.wangkaixuan.tech\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"http:\/\/www.wangkaixuan.tech\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"http:\/\/www.wangkaixuan.tech\/index.php?rest_route=\/wp\/v2\/users\/2"}],"replies":[{"embeddable":true,"href":"http:\/\/www.wangkaixuan.tech\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=279"}],"version-history":[{"count":0,"href":"http:\/\/www.wangkaixuan.tech\/index.php?rest_route=\/wp\/v2\/posts\/279\/revisions"}],"wp:attachment":[{"href":"http:\/\/www.wangkaixuan.tech\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=279"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"http:\/\/www.wangkaixuan.tech\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=279"},{"taxonomy":"post_tag","embeddable":true,"href":"http:\/\/www.wangkaixuan.tech\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=279"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}