{"id":291,"date":"2011-10-27T13:53:59","date_gmt":"2011-10-27T05:53:59","guid":{"rendered":"http:\/\/wangkaixuan.tech\/?p=291"},"modified":"2020-06-06T13:55:37","modified_gmt":"2020-06-06T05:55:37","slug":"%e6%95%b0%e6%8d%ae%e7%bb%93%e6%9e%84_%e6%9f%a5%e6%89%be_%e9%9d%99%e6%80%81%e6%9f%a5%e6%89%be%e6%95%b0%e8%a1%a8_%e6%9e%84%e9%80%a0%e6%ac%a1%e4%bc%98%e6%9f%a5%e6%89%be%e6%a0%91","status":"publish","type":"post","link":"http:\/\/www.wangkaixuan.tech\/?p=291","title":{"rendered":"\u6570\u636e\u7ed3\u6784_\u67e5\u627e_\u9759\u6001\u67e5\u627e\u6570\u8868_\u6784\u9020\u6b21\u4f18\u67e5\u627e\u6811"},"content":{"rendered":"\n
\"\"<\/figure>\n\n\n\n

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

#include<iostream>\nusing namespace std;\n\n#define MAX_DATA_NUM 20\/\/\u6700\u5927\u8282\u70b9\u503c\n\ntypedef struct SSTable \/\/\u9759\u6001\u67e5\u627e\u8868\u5b58\u50a8\u7ed3\u6784\n{\n\tchar name;\n\tint weight;\n} ElemType;\n\ntypedef struct BiTreeNode \/\/\u4e8c\u53c9\u94fe\u8868\u5b58\u50a8\u7ed3\u6784\n{\n\tElemType data;\n\tBiTreeNode *lchild, *rchild;\n\tBiTreeNode()\n\t{\n\t\tlchild = rchild = NULL;\n\t}\n} *BiTree;\n\nclass SOSTree \/\/\u9759\u6001\u67e5\u627e\u6811\u8868\n{\npublic:\n\tSOSTree(); \/\/\u6784\u9020\u51fd\u6570\n\tvoid SOSTREE(); \/\/\u63a5\u53e3\u51fd\u6570\nprivate:\n\tvoid Findsw(); \/\/\u5f97\u5230\u6743\u503c\u548c\n\tvoid GetSSTable(); \/\/\u5f97\u5230\u9759\u6001\u67e5\u627e\u8868\n\tvoid SecondOptimal(BiTree&, int, int); \/\/\u5f97\u5230\u6b21\u4f18\u67e5\u627e\u6811\n\tvoid SOSTreeTraverse(BiTree&); \/\/\u904d\u5386\u6b21\u4f18\u67e5\u627e\u6811\n\tElemType r[MAX_DATA_NUM]; \/\/\u9759\u6001\u67e5\u627e\u8868\n\tint sw[MAX_DATA_NUM]; \/\/\u7d2f\u8ba1\u6743\u503c\u548c\n\tint datanum; \/\/\u8868\u8282\u70b9\u6570\u91cf\n};\n\nSOSTree::SOSTree()\n{\n\tdatanum = 0;\n}\n\nvoid SOSTree::SOSTREE() \/\/\u63a5\u53e3\u51fd\u6570\n{\n\tBiTree T;\n\tGetSSTable(); \/\/\u5f97\u5230\u9759\u6001\u67e5\u627e\u8868\n\tFindsw(); \/\/\u5f97\u5230\u7d2f\u8ba1\u6743\u503c\u548c\n\tSecondOptimal(T, 0, datanum - 1); \/\/\u5f97\u5230\u6b21\u4f18\u67e5\u627e\u6811\n\tSOSTreeTraverse(T); \/\/\u904d\u5386\u6b21\u4f18\u67e5\u627e\u6811\n}\n\nvoid SOSTree::GetSSTable() \/\/\u5f97\u5230\u9759\u6001\u67e5\u627e\u8868\n{\n\tcout << \"Please Input The SSTable :\" << endl << \"name weight\" << endl;\n\tchar name;\n\tint weight;\n\twhile (cin >> name >> weight)\n\t{\n\t\tr[datanum].name = name;\n\t\tr[datanum].weight = weight;\n\t\tdatanum++;\n\t}\n\tcin.clear();\n}\n\nvoid SOSTree::Findsw() \/\/\u5f97\u5230\u7d2f\u8ba1\u6743\u503c\u548c\n{\n\tsw[0] = r[0].weight;\n\tfor (int i = 1; i < datanum; i++)\n\t\tsw[i] = sw[i - 1] + r[i].weight;\n}\n\nvoid SOSTree::SecondOptimal(BiTree &t, int low, int high) \/\/\u5f97\u5230\u6b21\u4f18\u67e5\u627e\u6811\n{\n\t\/\/\u7531\u6709\u5e8f\u8868r[low,high]\u53ca\u5176\u7d2f\u8ba1\u6743\u503c\u548c\u8868sw\u9012\u5f52\u5efa\u7acb\u6b21\u4f18\u67e5\u627e\u6811\n\tint i = low, min = abs(sw[high] - sw[low]); \/\/\u521d\u59cb\u5316\n\tint dw = sw[high] + ((low == 0) ? 0 : sw[low - 1]);\n\tfor (int j = low + 1; j <= high; j++) \/\/\u627e\u5230\u6700\u5c0f\u7684\u0394pi\n\t\tif (abs(dw - sw[j] - sw[j - 1]) < min)\n\t\t{\n\t\t\ti = j;\n\t\t\tmin = abs(dw - sw[j] - sw[j - 1]);\n\t\t}\n\tt = new BiTreeNode; \/\/\u5efa\u7acb\u65b0\u8282\u70b9\n\tt->data = r[i];\n\tif (i == low)\n\t\tt->lchild = NULL;\n\telse\n\t\tSecondOptimal(t->lchild, low, i - 1);\n\tif (i == high)\n\t\tt->rchild = NULL;\n\telse\n\t\tSecondOptimal(t->rchild, i + 1, high);\n}\n\nvoid SOSTree::SOSTreeTraverse(BiTree &t) \/\/\u904d\u5386\u6b21\u4f18\u67e5\u627e\u6811\n{\n\tif (t == NULL)\n\t\treturn;\n\tcout << t->data.name << \" \" << t->data.weight << endl;\n\tSOSTreeTraverse(t->lchild);\n\tSOSTreeTraverse(t->rchild);\n}\n<\/code><\/pre>\n\n\n\n
main.cpp<\/p>\n\n\n\n
#include\"SecondOptimal.h\"\n \nint main()\n{\n\tSOSTree T;\n\tT.SOSTREE();\n\tsystem(\"pause\");\n}<\/code><\/pre>\n","protected":false},"excerpt":{"rendered":"
SecondOptimal.h main.cpp<\/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-291","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\/291","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=291"}],"version-history":[{"count":0,"href":"http:\/\/www.wangkaixuan.tech\/index.php?rest_route=\/wp\/v2\/posts\/291\/revisions"}],"wp:attachment":[{"href":"http:\/\/www.wangkaixuan.tech\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=291"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"http:\/\/www.wangkaixuan.tech\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=291"},{"taxonomy":"post_tag","embeddable":true,"href":"http:\/\/www.wangkaixuan.tech\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=291"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}