{"id":135,"date":"2019-03-12T21:51:03","date_gmt":"2019-03-12T13:51:03","guid":{"rendered":"http:\/\/fankasy.xyz\/?p=135"},"modified":"2019-05-08T17:34:05","modified_gmt":"2019-05-08T09:34:05","slug":"%e5%ad%a6%e4%b9%a0%e6%95%b0%e6%8d%ae%e7%bb%93%e6%9e%847-%e5%93%88%e5%a4%ab%e6%9b%bc%e6%a0%91","status":"publish","type":"post","link":"http:\/\/fankasy.xyz\/index.php\/2019\/03\/12\/%e5%ad%a6%e4%b9%a0%e6%95%b0%e6%8d%ae%e7%bb%93%e6%9e%847-%e5%93%88%e5%a4%ab%e6%9b%bc%e6%a0%91\/","title":{"rendered":"\u5b66\u4e60\u6570\u636e\u7ed3\u67847-\u54c8\u592b\u66fc\u6811"},"content":{"rendered":"

\u4ece\u524d\u6709\u4e2a\u795e\u4eba\u53eb\u54c8\u592b\u66fc\uff0c\u53d1\u660e\u4e86\u4e00\u79cd\u4e8c\u8fdb\u5236\u7f16\u7801\u6280\u672f\uff0c\u53ef\u4ee5\u5b9e\u73b0\u538b\u7f29\u5b58\u50a8\u3002\u540e\u6765\u4eba\u4eec\u53d1\u73b0\u8fd9\u73a9\u610f\u771f\u7684\u597d\u7528\uff0c\u5c45\u7136\u52309102\u5e74\u4e86\u8fd8\u5728\u7528\u5b83\u7684\u6539\u8fdb\u578b\u3002<\/p>\n

\u90a3\u4e48\u7a0d\u7a0d\u5b66\u4e60\u4e00\u4e0b\u5427<\/p>\n

\u8fd9\u4e2a\u7b97\u6cd5\u662f\u57fa\u4e8e\u6743\u503c\u7684\u6982\u5ff5\uff0c\u6743\u4e3a\u51fa\u73b0\u9891\u7387\u8f83\u9ad8\u7684\u5143\u7d20\u8d4b\u8f83\u9ad8\u7684\u6743\u503c\uff0c\u5e76\u7f16\u4ee5\u8f83\u77ed\u7684\u4ee3\u7801\uff0c\u4ee5\u6b64\u7f29\u77ed\u6574\u4e2a\u6570\u636e\u4e32\u7684\u5360\u7528\u7a7a\u95f4\u3002<\/p>\n

\u5b9a\u4e49\u54c8\u592b\u66fc\u6811\u4e4b\u524d\u5148\u8bf4\u660e\u51e0\u4e2a\u4e0e\u54c8\u592b\u66fc\u6811\u6709\u5173\u7684\u6982\u5ff5\uff1a<\/p>\n

\u8def\u5f84\uff1a <\/strong>\u6811\u4e2d\u4e00\u4e2a\u7ed3\u70b9\u5230\u53e6\u4e00\u4e2a\u7ed3\u70b9\u4e4b\u95f4\u7684\u5206\u652f\u6784\u6210\u8fd9\u4e24\u4e2a\u7ed3\u70b9\u4e4b\u95f4\u7684\u8def\u5f84\u3002<\/p>\n

\u8def\u5f84\u957f\u5ea6\uff1a<\/strong>\u8def\u5f84\u4e0a\u7684\u5206\u679d\u6570\u76ee\u79f0\u4f5c\u8def\u5f84\u957f\u5ea6\u3002<\/p>\n

\u6811\u7684\u8def\u5f84\u957f\u5ea6\uff1a<\/strong>\u4ece\u6811\u6839\u5230\u6bcf\u4e00\u4e2a\u7ed3\u70b9\u7684\u8def\u5f84\u957f\u5ea6\u4e4b\u548c\u3002<\/p>\n

\u7ed3\u70b9\u7684\u5e26\u6743\u8def\u5f84\u957f\u5ea6\uff1a<\/strong>\u5728\u4e00\u68f5\u6811\u4e2d\uff0c\u5982\u679c\u5176\u7ed3\u70b9\u4e0a\u9644\u5e26\u6709\u4e00\u4e2a\u6743\u503c\uff0c\u901a\u5e38\u628a\u8be5\u7ed3\u70b9\u7684\u8def\u5f84\u957f\u5ea6\u4e0e\u8be5\u7ed3\u70b9\u4e0a\u7684\u6743\u503c\u4e4b\u79ef\u79f0\u4e3a\u8be5\u7ed3\u70b9\u7684\u5e26\u6743\u8def\u5f84\u957f\u5ea6<\/p>\n

\"\"<\/p>\n

\u4e00\u822c\u6765\u8bf4\uff0c\u7528n\uff08n>0\uff09\u4e2a\u5e26\u6743\u503c\u7684\u53f6\u5b50\u6765\u6784\u9020\u4e8c\u53c9\u6811\uff0c\u9650\u5b9a\u4e8c\u53c9\u6811\u4e2d\u9664\u4e86\u8fd9n\u4e2a\u53f6\u5b50\u5916\u53ea\u80fd\u51fa\u73b0\u5ea6\u4e3a2\u7684\u7ed3\u70b9\u3002<\/p>\n

\u90a3\u4e48\u7b26\u5408\u8fd9\u6837\u6761\u4ef6\u7684\u4e8c\u53c9\u6811\u5f80\u5f80\u53ef\u6784\u9020\u51fa\u8bb8\u591a\u9897\uff0c<\/p>\n

\u5176\u4e2d\u5e26\u6743\u8def\u5f84\u957f\u5ea6\u6700\u5c0f\u7684\u4e8c\u53c9\u6811\u5c31\u79f0\u4e3a\u54c8\u592b\u66fc\u6811\u6216\u6700\u4f18\u4e8c\u53c9\u6811<\/p>\n

\u54c8\u592b\u66fc\u6811\u7684\u6784\u9020\uff1a<\/strong><\/p>\n

\u663e\u7136\uff0c\u6743\u503c\u9ad8\u7684\u5143\u7d20\u5e94\u8be5\u5c3d\u53ef\u80fd\u63a5\u8fd1\u6811\u7684\u6839\u90e8\uff0c\u5c06\u8f83\u8fdc\u7684\u5730\u65b9\u7559\u7ed9\u6743\u503c<\/p>\n

\"\" \"\"<\/p>\n

\u54c8\u5f17\u66fc\u6811\u7684\u5b9e\u73b0\u4ee3\u7801\uff1a<\/strong><\/p>\n

\/* \u56e0\u4e3a\u9700\u8981\u5b58\u50a8\u54c8\u592b\u66fc\u6811\u548c\u690d\u6811\u524d\u7684\u4e34\u65f6\u8282\u70b9\uff0c\u6240\u4ee5\u5728\u62bd\u8c61\u5b9a\u4e49\u7684\u65f6\u5019\u5c06\u6570\u7ec4\u957f\u5ea6\u8bbe\u7f6e\u4e3a2*N\u4f1a\u65b9\u4fbf\u5f88\u591a\u3002\u5176\u4e2d0\u53f7\u4e0d\u4f7f\u7528(\u4f5c\u4e3a\u54e8\u5175)\uff0c1\u5230N\u53f7\u690d\u6811\uff0cN+1\u52302N-1\u53f7\u5b58\u50a8\u8282\u70b9 *\/<\/span>\r\n\r\n#define N 999998\r\n#define MAX 0x3f3f3f3f \u00a0\u00a0\u00a0\u00a0\u00a0\/\/\u5173\u4e8e\u65e0\u7a77\u5927\u4e3a\u5565\u662f3f\u5148\u522b\u95ee\uff0c\u81ea\u5df1\u67e5<\/span>\r\n\r\ntypedef struct\r\n{\r\nelemType Data; \/\/\u6570\u636e\u57df<\/span>\r\nint w;  \/\/\u8282\u70b9\u6743\u503c<\/span>\r\nint parent, lchild, rchild; \/\/\u8fd9\u662f\u5c0f\u5b66\u82f1\u8bed<\/span>\r\n}HFMNode;\r\n\r\nHFMNode Ht[2*N];\r\n\r\nvoid Huffman( HFMNode Ht[] , int N ) \/\/\u5bfc\u5165\u6570\u7ec4\u5b58\u50a8\u7684\u5b8c\u5168\u4e8c\u53c9\u6811\uff0cN\u4e3a\u6700\u5927\u8bb8\u53ef\u957f\u5ea6<\/span>\r\n\r\n{\r\n\r\nint i, k, lmin, rmin; \/\/\u5de6\u6700\u5c0f\u548c\u53f3\u6700\u5c0f\u7528\u6765\u5b58\u653e\u6700\u5c0f\u6743\u503c\u7684\u6807\u53f7<\/span>\r\nint min1, min2; \/\/\u5206\u522b\u5b58\u653e\u6700\u5c0f\u6743\u503c\u7684\u503c<\/span>\r\nfor(i=1; i<2*N; i++)\u00a0 \/\/\u8fd9\u91cc\u4ee4i=N+1\u7684\u610f\u601d\u662f\u5728\u65e0\u4eb2\u65e0\u6545\u8282\u70b9\u7684<\/span>\u68ee\u6797\u91cc\u67e5\u627e<\/span>\r\nHt[i].w = Ht[i].parent = Ht[i].lchild = Ht[i].rchild = -1; \u00a0\/\/\u5168\u90e8\u521d\u59cb\u5316\u4e3a-1<\/span>\r\n\r\n\r\nfor(i=N+1; i<2*N; i++)\u00a0\u00a0 \/\/\u5728\u8fd9\u4e2a\u5faa\u73af\u4e2d\uff0c\u5c06\u8981\u627e\u51fa\u6743\u503c\u6700\u5c0f\u7684\u4e24\u4e2a\u5143\u7d20<\/span>\r\n\r\n{\r\n\r\nmin1=min2=MAX;\r\nlmin=rmin= -1;\u00a0\u00a0\u00a0  \/\/\u8fd9\u4e00\u6b65\u662f\u6e05\u7a7a\u6570\u503c\r\n<\/span>\r\nfor( k=1; k<2*N; k++)\r\nif( Ht[i].parent == -1 )\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0  \/\/\u5bf9\u6ca1\u6709\u5904\u7406\u8fc7\u7684\u8282\u70b9\u8fdb\u884c\u64cd\u4f5c<\/span>\r\n{\u00a0\u00a0 \/\/\u627e\u51fa\u4e24\u4e2a\u6700\u5c0f\u7684\u503c<\/span>\r\n\r\nif( Ht[k].w<min1 )\r\n\r\n{min2=min1;\r\nmin1=Ht[k].w;\r\nlmin=rmin;\r\nlmin=k;\r\nbreak;}\r\n\r\nelse if( Ht[k].w<min2 )\r\n{min2=Ht[k].w;\r\nrmin=k;\r\nbreak;}\r\n\r\n}\r\n\r\n\/\/\u6743\u503c\u76f8\u52a0\uff0c\u7236\u8282\u70b9\u548c\u5b50\u8282\u70b9\u5f52\u4f4d<\/span>\r\n\r\nHt[k].w = Ht[lmin].w + Ht[rmin].w;\r\nHt[k].lchild = lmin;\r\nHt[k].rchild = rmin;\r\nHt[lmin].parent =Ht[rmin].parent = I;\r\n\r\n\r\n}\r\n\r\n\r\n}<\/pre>\n
\u600e\u4e48\u6837\uff0c\u5f88\u7b80\u5355\u5427\uff1f\u4f5c\u4e3a\u4f5c\u4e1a\u8bf7\u7f16\u5199\u4e00\u4e2a\u6570\u636e\u538b\u7f29\u8f6f\u4ef6\u4f5c\u4e3a\u7ec3\u4e60\uff01<\/span><\/strong><\/h2>\n
\u56e0\u4e3a\u54c8\u592b\u66fc\u6811\u4e5f\u662f\u4e00\u79cd\u4e8c\u53c9\u6811\uff0c\u6240\u4ee5\u5728\u904d\u5386\u7684\u65f6\u5019\u548c\u4e00\u822c\u7684\u4e8c\u53c9\u6811\u4e00\u6837\uff0c\u5229\u7528\u9012\u5f52\u6216\u8005\u6808\/\u961f\u5217\u5373\u53ef\u5b8c\u6210\u3002\u7a0d\u5fae\u6709\u4e9b\u4e0d\u540c\u4e4b\u5904\u5728\u4e8e\u54c8\u592b\u66fc\u6811\u5229\u7528\u7684\u662f\u987a\u5e8f\u8868\u800c\u4e0d\u662f\u94fe\u8868\uff01<\/p>\n
\u63a5\u4e0b\u6765\u6211\u4f1a\u8d34\u4e0a\u6211\u5b9e\u73b0\u6570\u636e\u538b\u7f29\u7684\u4ee3\u7801\uff0c\u5728\u4e66\u4e0a\u662f\u8bfe\u540e\u9898\u6765\u7740<\/p>\n
\u8b66\u544a\uff1a\u622a\u6b62\u76ee\u524d\u8fd9\u6bb5\u4ee3\u7801\u5e76\u6ca1\u6709\u5b8c\u5584\u5e76\u901a\u8fc7\u6d4b\u8bd5\uff01<\/span><\/h2>\n
\u73b0\u5728\u6211\u4e5f\u770b\u4e0d\u61c2\u4e86<\/del><\/span><\/p>\n
huffman.h<\/p>\n
\r\n#pragma once\r\n#include \r\n#include\r\n#include\r\n#define N 350 \r\n#define MAXBIT 20\r\ntypedef struct\r\n{\r\n    char ch;\r\n    int weight;\r\n    int parent;\r\n    int Lchild, Rchild;\r\n}HtreeNode;\r\n\r\ntypedef struct\r\n{\r\n    int  bit[MAXBIT];\r\n    int start;\r\n    char ch;\r\n}HcodeNode;\r\n\r\nint WeightCount(char* str, HtreeNode t[]);\r\nvoid PlantTree(HtreeNode t[], char* str);\r\nvoid EnCode(HtreeNode t[], HcodeNode code[], char* str); \r\nvoid Print(HtreeNode t[], HcodeNode code[]);\r\n<\/pre>\n
huffman.c<\/p>\n
\r\n#include\"Huffman.h\"\r\n\r\nint WeightCount(char* str, HtreeNode t[])\r\n\/*\r\n    Scan the words and count the weight\r\n*\/\r\n{\r\n    int len = strlen(str);\r\n    for (int i = 0; i < len; i++)\r\n    {\/\/ If existed, weight++, or create a new item \r\n        char ch = str[i];\r\n        \/\/find if str[i] existed or current node is empty ?\r\n        for (int x = 0; x < N; x++)\r\n            if (t[x].ch == ch || t[x].weight == 0)\r\n            {\r\n                t[x].ch = ch;\r\n                t[x].weight++;\r\n                break;\r\n            }\r\n    }\r\n    int i = 0;\r\n    while (t[i].ch != 0)\r\n        i++;\r\n    return i;\r\n}\r\n\r\nvoid PlantTree(HtreeNode t[], char* str)\r\n\/*\r\n    Reorder the Nodes and create\r\n*\/\r\n{\r\n    for (int temp = 0; temp < 2 * N; temp++)\/\/Initialize the array\r\n    {\r\n        t[temp].ch = t[temp].weight = 0;\r\n        t[temp].Lchild = t[temp].Rchild = t[temp].parent = -1;\r\n    }\r\n\r\n    int i, j, Lmin, Rmin;\r\n    int min1, min2;\r\n    int allweight;\r\n\r\n    allweight = WeightCount(str, t);\r\n\r\n    for (i = allweight; i < 2 * N; i++) \/\/place new nodes behind original nodes\r\n    {\r\n        min1 = min2 = INT_MAX;\r\n        Lmin = Rmin = -1;\r\n        for (j = 0; j < i+1; j++)\/\/ Reorder nodes from [0]--[allweight]\r\n        {\r\n            if (t[j].parent == -1) \/\/Only reorder node those still in the forest\r\n            {\r\n                if (t[j].weight < min1)\r\n                {\r\n                    Rmin = Lmin;\r\n                    Lmin = j;\r\n                    min1 = t[j].weight;\r\n                    min2 = min1;\r\n                }\r\n                else if (t[j].weight < min2 && j != Lmin)\r\n                {\r\n                    min2 = t[j].weight;\r\n                    Rmin = j;\r\n                }\r\n            }\r\n        }\r\n\r\n        \/\/place new node\r\n        t[Lmin].parent = t[Rmin].parent = i;\r\n        t[i].weight = t[Lmin].weight + t[Rmin].weight;\r\n        t[i].Lchild = Lmin; t[i].Rchild = Rmin;\r\n\r\n\r\n    }\r\n\r\n}\r\n\r\nvoid EnCode(HtreeNode t[], HcodeNode code[], char* str)\r\n{\r\n    PlantTree(t, str);\r\n    for (int s = 0; s < 2 * N; s++)\r\n        if (t[s].weight == 0 && t[s].parent != -1)\r\n            t[s].parent = -1;\r\n    t[63].parent = -1;\r\n\r\n}\r\n\r\nvoid Print(HtreeNode t[], HcodeNode code[])\r\n{\r\n    int i;\r\n    for (i = 0; i < 2 * N; i++)\r\n        if(t[i].weight)\r\n            printf(\" %d  '%c'   P:%d    W:%d    L:%d    R:%d  \\n\", i, t[i].ch, t[i].parent, t[i].weight, t[i].Lchild, t[i].Rchild);\r\n}<\/pre>\n
main.c<\/p>\n
\r\n#include\"Huffman.h\"\r\nint main()\r\n{\r\n    HtreeNode* t = malloc(sizeof(HtreeNode) * 2*N);\r\n    if (!t)\r\n        exit(\"16543\");\r\n    HcodeNode* code = malloc(sizeof(HcodeNode) * N);\r\n    if (!code)\r\n        exit(\"64541\");\r\n\r\n    char* str = \"I prefer my English classes to betaught in both English and Chinese, whose advantage is that it is easy for usto understand what the teacher talks about. The teacher first teaches the classin English, and then she explains those that are hard to understand to us sothat we get a better knowing of the passage. That will be good for us.However, teaching the class in twolanguages will make the English atmosphere not so strong.Some students whowish to be taught in English will be disappointed.      Except for the disadvantage, I thinkit is really good to hear two languages in classes.It can make us morefamiliar with the foreign culture.\";\r\n\r\n    EnCode(t, code, str);\r\n    Print(t, code, strlen(str) );\r\n    return 0;\r\n}\r\n\r\n<\/pre>\n","protected":false},"excerpt":{"rendered":"
\u4ece\u524d\u6709\u4e2a\u795e\u4eba\u53eb\u54c8\u592b\u66fc\uff0c\u53d1\u660e\u4e86\u4e00\u79cd\u4e8c\u8fdb\u5236\u7f16\u7801\u6280\u672f\uff0c\u53ef\u4ee5\u5b9e\u73b0\u538b\u7f29\u5b58\u50a8\u3002\u540e\u6765\u4eba\u4eec\u53d1\u73b0\u8fd9\u73a9\u610f\u771f\u7684\u597d\u7528\uff0c\u5c45\u7136\u52309102\u5e74 […]<\/p>\n","protected":false},"author":3,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":[],"categories":[5,10],"tags":[],"_links":{"self":[{"href":"http:\/\/fankasy.xyz\/index.php\/wp-json\/wp\/v2\/posts\/135"}],"collection":[{"href":"http:\/\/fankasy.xyz\/index.php\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"http:\/\/fankasy.xyz\/index.php\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"http:\/\/fankasy.xyz\/index.php\/wp-json\/wp\/v2\/users\/3"}],"replies":[{"embeddable":true,"href":"http:\/\/fankasy.xyz\/index.php\/wp-json\/wp\/v2\/comments?post=135"}],"version-history":[{"count":0,"href":"http:\/\/fankasy.xyz\/index.php\/wp-json\/wp\/v2\/posts\/135\/revisions"}],"wp:attachment":[{"href":"http:\/\/fankasy.xyz\/index.php\/wp-json\/wp\/v2\/media?parent=135"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"http:\/\/fankasy.xyz\/index.php\/wp-json\/wp\/v2\/categories?post=135"},{"taxonomy":"post_tag","embeddable":true,"href":"http:\/\/fankasy.xyz\/index.php\/wp-json\/wp\/v2\/tags?post=135"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}