{"id":254,"date":"2019-08-01T00:13:23","date_gmt":"2019-07-31T16:13:23","guid":{"rendered":"https:\/\/kanghaov.com\/?p=254"},"modified":"2020-08-03T17:43:16","modified_gmt":"2020-08-03T09:43:16","slug":"%e6%95%b0%e6%8d%ae%e7%bb%93%e6%9e%84","status":"publish","type":"post","link":"https:\/\/nemo.cool\/254.html","title":{"rendered":"\u591a\u79cd\u6570\u636e\u7ed3\u6784\u7684Python\u5b9e\u73b0\u5f62\u5f0f"},"content":{"rendered":"<h2>\u57fa\u7840\u77e5\u8bc6\u70b9<\/h2>\n<ul>\n<li>\u6570\u636e\u7ed3\u6784\u7684\u6982\u5ff5<\/li>\n<li>\u6808<\/li>\n<li>\u961f\u5217<\/li>\n<li>\u94fe\u8868<\/li>\n<\/ul>\n<h3>\u6570\u636e\u7ed3\u6784<\/h3>\n<p><strong>\u6570\u636e\u7ed3\u6784<\/strong>( data structure )\u662f\u8ba1\u7b97\u673a\u5b58\u50a8\u3001\u7ec4\u7ec7\u6570\u636e\u7684\u65b9\u5f0f\u3002\u6570\u636e\u7ed3\u6784\u662f\u6307\u76f8\u4e92\u4e4b\u95f4\u5b58\u5728\u4e00\u79cd\u6216\u591a\u79cd\u7279\u5b9a\u5173\u7cfb\u7684\u6570\u636e\u5143\u7d20\u7684\u96c6\u5408\u3002\u901a\u5e38\u60c5\u51b5\u4e0b\uff0c\u7cbe\u5fc3\u9009\u62e9\u7684\u6570\u636e\u7ed3\u6784\u53ef\u4ee5\u5e26\u6765\u66f4\u9ad8\u7684\u8fd0\u884c\u6216\u8005\u5b58\u50a8\u6548\u7387\u3002\u6570\u636e\u7ed3\u6784\u5f80\u5f80\u540c\u9ad8\u6548\u7684\u68c0\u7d22\u7b97\u6cd5\u548c\u7d22\u5f15\u6280\u672f\u6709\u5173\u3002<\/p>\n<p>\u5728\u8bb8\u591a\u7c7b\u578b\u7684\u7a0b\u5e8f\u7684\u8bbe\u8ba1\u4e2d\uff0c\u6570\u636e\u7ed3\u6784\u7684\u9009\u62e9\u662f\u4e00\u4e2a\u57fa\u672c\u7684\u8bbe\u8ba1\u8003\u8651\u56e0\u7d20\u3002\u8bb8\u591a\u5927\u578b\u7cfb\u7edf\u7684\u6784\u9020\u7ecf\u9a8c\u8868\u660e\uff0c\u7cfb\u7edf\u5b9e\u73b0\u7684\u56f0\u96be\u7a0b\u5ea6\u548c\u7cfb\u7edf\u6784\u9020\u7684\u8d28\u91cf\u90fd\u4e25\u91cd\u5730\u4f9d\u8d56\u4e8e\u662f\u5426\u9009\u62e9\u4e86\u6700\u4f18\u7684\u6570\u636e\u7ed3\u6784\u3002\u8bb8\u591a\u65f6\u5019\uff0c\u786e\u5b9a\u4e86\u6570\u636e\u7ed3\u6784\u540e\uff0c\u7b97\u6cd5\u5c31\u5bb9\u6613\u5f97\u5230\u4e86\u3002\u6709\u4e9b\u65f6\u5019\u4e8b\u60c5\u4e5f\u4f1a\u53cd\u8fc7\u6765\uff0c\u6211\u4eec\u6839\u636e\u7279\u5b9a\u7b97\u6cd5\u6765\u9009\u62e9\u6570\u636e\u7ed3\u6784\u4e0e\u4e4b\u9002\u5e94\u3002<\/p>\n<h3>\u6808<\/h3>\n<p>\u6808\uff08stack\uff09\u53c8\u540d\u5806\u6808\uff0c\u5b83\u662f\u4e00\u79cd\u8fd0\u7b97\u53d7\u9650\u7684\u7ebf\u6027\u8868\u3002\u5176\u9650\u5236\u662f\u4ec5\u5141\u8bb8\u5728\u8868\u7684\u4e00\u7aef\u8fdb\u884c\u63d2\u5165\u548c\u5220\u9664\u8fd0\u7b97\u3002<\/p>\n<p><img decoding=\"async\" src=\"https:\/\/kanghaov-img-1256185664.file.myqcloud.com\/2019\/07\/18\/5d3022894bf29.png\" alt=\"wm.png\" \/><\/p>\n<p>\u6808\u5141\u8bb8\u8fdb\u884c\u63d2\u5165\u548c\u5220\u9664\u64cd\u4f5c\u7684\u4e00\u7aef\u79f0\u4e3a<strong>\u6808\u9876(top)<\/strong>\uff0c\u53e6\u4e00\u7aef\u4e3a<strong>\u6808\u5e95(bottom)<\/strong>\uff1b<strong>\u6808\u5e95\u56fa\u5b9a\uff0c\u800c\u6808\u9876\u6d6e\u52a8<\/strong>\uff1b\u6808\u4e2d\u5143\u7d20\u4e2a\u6570\u4e3a\u96f6\u65f6\u79f0\u4e3a\u7a7a\u6808\u3002<strong>\u63d2\u5165\u4e00\u822c\u79f0\u4e3a\u8fdb\u6808\uff08PUSH\uff09\uff0c\u5220\u9664\u5219\u79f0\u4e3a\u9000\u6808\uff08POP\uff09<\/strong>\u3002<\/p>\n<p>\u7531\u4e8e\u5806\u53e0\u6570\u636e\u7ed3\u6784\u53ea\u5141\u8bb8\u5728\u4e00\u7aef\u8fdb\u884c\u64cd\u4f5c\uff0c\u56e0\u800c\u6309\u7167\u540e\u8fdb\u5148\u51fa\uff08LIFO, Last In First Out\uff09\u7684\u539f\u7406\u8fd0\u4f5c\u3002\u6808\u4e5f\u79f0\u4e3a<strong>\u540e\u8fdb\u5148\u51fa\u8868<\/strong>\u3002<\/p>\n<h4>\u590d\u6742\u5ea6\u5206\u6790<\/h4>\n<p>\u6808\u5c5e\u4e8e\u5e38\u89c1\u7684\u4e00\u79cd\u7ebf\u6027\u7ed3\u6784\uff0c\u5bf9\u4e8e\u8fdb\u6808\u548c\u9000\u6808\u800c\u8a00\uff0c\u65f6\u95f4\u590d\u6742\u5ea6\u90fd\u4e3a O(1)<\/p>\n<h4>\u6808\u7684\u5b9e\u73b0<\/h4>\n<p><strong>1. \u521b\u5efa\u4e00\u4e2a Stack \u7684\u7c7b<\/strong><\/p>\n<p>\u5bf9\u6808\u8fdb\u884c\u521d\u59cb\u5316\u53c2\u6570\u8bbe\u8ba1<\/p>\n<p>\u5177\u4f53\u5b9e\u73b0\u4ee3\u7801\u5982\u4e0b\uff1a<\/p>\n<pre><code class=\"language-python\">class Stack(object):\n    def __init__(self, limit=10):\n        self.stack = [] #\u5b58\u653e\u5143\u7d20\n        self.limit = limit #\u6808\u5bb9\u91cf\u6781\u9650<\/code><\/pre>\n<p><strong>2. push \u8fdb\u6808<\/strong><\/p>\n<p>\u538b\u5165 push \uff1a\u5c06\u65b0\u5143\u7d20\u653e\u5728\u6808\u9876<\/p>\n<p>\u5f53\u65b0\u5143\u7d20\u5165\u6808\u65f6\uff0c\u6808\u9876\u4e0a\u79fb\uff0c\u65b0\u5143\u7d20\u653e\u5728\u6808\u9876\u3002<\/p>\n<p>\u5177\u4f53\u5b9e\u73b0\u4ee3\u7801\u5982\u4e0b:<\/p>\n<pre><code class=\"language-python\">def push(self, data):\n    if len(self.stack) &amp;gt;= self.limit: #\u5224\u65ad\u6808\u662f\u5426\u6ea2\u51fa\n        print(&amp;#039;StackOverflowError&amp;#039;)\n            pass\n    self.stack.append(data)<\/code><\/pre>\n<p><strong>3. pop \u9000\u6808<\/strong><\/p>\n<p>\u5f39\u51fa pop \uff1a\u4ece\u6808\u9876\u79fb\u51fa\u4e00\u4e2a\u6570\u636e<\/p>\n<ul>\n<li>\u6808\u9876\u5143\u7d20\u62f7\u8d1d\u51fa\u6765<\/li>\n<li>\u6808\u9876\u4e0b\u79fb<\/li>\n<li>\u62f7\u8d1d\u51fa\u6765\u7684\u6808\u9876\u4f5c\u4e3a\u51fd\u6570\u8fd4\u56de\u503c<\/li>\n<\/ul>\n<p>\u5177\u4f53\u5b9e\u73b0\u4ee3\u7801\u5982\u4e0b:<\/p>\n<pre><code class=\"language-python\">def pop(self):\n    if self.stack:\n        return self.stack.pop()\n    else:\n        raise IndexError(&amp;#039;pop from an empty stack&amp;#039;) #\u7a7a\u6808\u4e0d\u80fd\u88ab\u5f39\u51fa<\/code><\/pre>\n<p><strong>4. \u6dfb\u52a0\u5176\u4ed6\u51fd\u6570<\/strong><\/p>\n<p>peek : \u67e5\u770b\u5806\u6808\u7684\u6700\u4e0a\u9762\u7684\u5143\u7d20<\/p>\n<p>is_empty : \u5224\u65ad\u6808\u662f\u5426\u4e3a\u7a7a<\/p>\n<p>size : \u8fd4\u56de\u6808\u7684\u5927\u5c0f<\/p>\n<p>\u5177\u4f53\u5b9e\u73b0\u4ee3\u7801\u5982\u4e0b\uff1a<\/p>\n<pre><code class=\"language-python\">def peek(self):\n    if self.stack:\n         return self.stack[-1]\ndef is_empty(self):\n    return not bool(self.stack)\ndef size(self):\n    return len(self.stack)<\/code><\/pre>\n<p>\u5b8c\u6574\u4ee3\u7801\u5982\u4e0b\uff1a<\/p>\n<pre><code class=\"language-python\">class Stack(object):\n    def __init__(self, limit=10):\n        self.stack = [] #\u5b58\u653e\u5143\u7d20\n        self.limit = limit #\u6808\u5bb9\u91cf\u6781\u9650\n    def push(self, data): #\u5224\u65ad\u6808\u662f\u5426\u6ea2\u51fa\n        if len(self.stack) &amp;gt;= self.limit:\n            print(&amp;#039;StackOverflowError&amp;#039;)\n            pass\n        self.stack.append(data)\n    def pop(self):\n        if self.stack:\n            return self.stack.pop()\n        else:\n            raise IndexError(&amp;#039;pop from an empty stack&amp;#039;) #\u7a7a\u6808\u4e0d\u80fd\u88ab\u5f39\u51fa\n    def peek(self): #\u67e5\u770b\u5806\u6808\u7684\u6700\u4e0a\u9762\u7684\u5143\u7d20\n        if self.stack:\n            return self.stack[-1]\n    def is_empty(self): #\u5224\u65ad\u6808\u662f\u5426\u4e3a\u7a7a\n        return not bool(self.stack)\n    def size(self): #\u8fd4\u56de\u6808\u7684\u5927\u5c0f\n        return len(self.stack)<\/code><\/pre>\n<h4>\u793a\u4f8b<\/h4>\n<p>\u68c0\u67e5\u62ec\u53f7\u662f\u5426\u5b8c\u5168\u5339\u914d<\/p>\n<p>\u5728\u8fd9\u4e2a\u5b9e\u9a8c\u4e2d\uff0c\u6211\u4eec\u8981\u6c42\u4f7f\u7528\u4e00\u4e2a\u5806\u6808\u68c0\u67e5\u62ec\u53f7\u5b57\u7b26\u4e32\u662f\u5426\u5e73\u8861<\/p>\n<p>\u5728<code>\/home\/shiyanlou\/<\/code>\u4e0b\u65b0\u5efa\u4e00\u4e2a\u6587\u4ef6<code>balanced_parentheses.py<\/code>\u3002\u6839\u636e\u6808\u7684\u7ed3\u6784\u7279\u70b9\uff0c\u7ed3\u5408 stack \u4ee3\u7801\uff0c\u5b8c\u6210\u4ee5\u4e0b\u529f\u80fd\u7684\u5b9e\u73b0\u3002<\/p>\n<p><strong>\u6709\u6548\u62ec\u53f7\u5b57\u7b26\u4e32<\/strong>\u9700\u6ee1\u8db3\uff1a<\/p>\n<ul>\n<li>\u5de6\u62ec\u53f7\u5fc5\u987b\u7528\u76f8\u540c\u7c7b\u578b\u7684\u53f3\u62ec\u53f7\u95ed\u5408\u3002<\/li>\n<li>\u5de6\u62ec\u53f7\u5fc5\u987b\u4ee5\u6b63\u786e\u7684\u987a\u5e8f\u95ed\u5408\u3002<\/li>\n<li>\u6ce8\u610f\u7a7a\u5b57\u7b26\u4e32\u53ef\u88ab\u8ba4\u4e3a\u662f\u6709\u6548\u5b57\u7b26\u4e32\u3002<\/li>\n<\/ul>\n<p><strong>\u4e3e\u4f8b\uff1a<\/strong><\/p>\n<p>((())): True<\/p>\n<p>((()): False<\/p>\n<p>(())): False<\/p>\n<p><strong>\u76ee\u6807\uff1a<\/strong><\/p>\n<ol>\n<li>\u4f7f\u7528\u4e00\u4e2a\u5806\u6808\u4f5c\u4e3a\u6570\u636e\u7ed3\u6784<\/li>\n<li>\u6765\u68c0\u67e5\u62ec\u53f7\u5b57\u7b26\u4e32\u662f\u5426\u5b8c\u5168\u5339\u914d<\/li>\n<\/ol>\n<p>\u7b54\u6848\uff1a<\/p>\n<pre><code class=\"language-python\">class Stack(object):\n    def __init__(self, limit=10):\n        self.stack = [] #\u5b58\u653e\u5143\u7d20\n        self.limit = limit #\u6808\u5bb9\u91cf\u6781\u9650\n    def push(self, data): #\u5224\u65ad\u6808\u662f\u5426\u6ea2\u51fa\n        if len(self.stack) &amp;gt;= self.limit:\n            print(&amp;#039;StackOverflowError&amp;#039;)\n            pass\n        self.stack.append(data)\n    def pop(self):\n        if self.stack:\n            return self.stack.pop()\n        else:\n            raise IndexError(&amp;#039;pop from an empty stack&amp;#039;) #\u7a7a\u6808\u4e0d\u80fd\u88ab\u5f39\u51fa\n    def peek(self): #\u67e5\u770b\u5806\u6808\u7684\u6700\u4e0a\u9762\u7684\u5143\u7d20\n        if self.stack:\n            return self.stack[-1]\n    def is_empty(self): #\u5224\u65ad\u6808\u662f\u5426\u4e3a\u7a7a\n        return not bool(self.stack)\n    def size(self): #\u8fd4\u56de\u6808\u7684\u5927\u5c0f\n        return len(self.stack)\n\ndef balanced_parentheses(parentheses):\n    stack = Stack(len(parentheses))\n    for parenthesis in parentheses:\n        if parenthesis == &amp;#039;(&amp;#039;:\n            stack.push(parenthesis)\n        elif parenthesis == &amp;#039;)&amp;#039;:\n            if stack.is_empty():\n                return False\n            stack.pop()\n    return stack.is_empty()\n\nif __name__ == &amp;#039;__main__&amp;#039;:\n    examples = [&amp;#039;((()))&amp;#039;, &amp;#039;((())&amp;#039;, &amp;#039;(()))&amp;#039;]\n    print(&amp;#039;Balanced parentheses demonstration:\\n&amp;#039;)\n    for example in examples:\n        print(example + &amp;#039;: &amp;#039; + str(balanced_parentheses(example)))<\/code><\/pre>\n<h3>\u94fe\u8868<\/h3>\n<p>\u94fe\u8868(linked_list)\u662f\u7269\u7406\u5b58\u50a8\u5355\u5143\u4e0a<strong>\u975e\u8fde\u7eed\u7684\u3001\u975e\u987a\u5e8f\u7684\u5b58\u50a8\u7ed3\u6784<\/strong>\uff0c\u6570\u636e\u5143\u7d20\u7684\u903b\u8f91\u987a\u5e8f\u662f\u901a\u8fc7\u94fe\u8868\u7684<strong>\u6307\u9488\u5730\u5740<\/strong>\u5b9e\u73b0\uff0c\u6bcf\u4e2a\u5143\u7d20\u5305\u542b\u4e24\u4e2a\u7ed3\u70b9\uff0c\u4e00\u4e2a\u662f\u5b58\u50a8\u5143\u7d20\u7684\u6570\u636e\u57df (\u5185\u5b58\u7a7a\u95f4)\uff0c\u53e6\u4e00\u4e2a\u662f\u6307\u5411\u4e0b\u4e00\u4e2a\u7ed3\u70b9\u5730\u5740\u7684\u6307\u9488\u57df\u3002\u6839\u636e\u6307\u9488\u7684\u6307\u5411\uff0c\u94fe\u8868\u80fd\u5f62\u6210\u4e0d\u540c\u7684\u7ed3\u6784\uff0c\u4f8b\u5982\u5355\u94fe\u8868\uff0c\u53cc\u5411\u94fe\u8868\uff0c\u5faa\u73af\u94fe\u8868\u7b49\u3002<\/p>\n<p><img decoding=\"async\" src=\"https:\/\/kanghaov-img-1256185664.file.myqcloud.com\/2019\/07\/18\/5d3030f42e4d2.png\" alt=\"wm.png\" \/><\/p>\n<p>\u94fe\u8868\u901a\u8fc7\u5c06\u94fe\u70b9 i \u4e0e\u5176\u90bb\u5c45\u94fe\u70b9 i+1 \u901a\u8fc7\u6307\u9488\u76f8\u5173\u8054\uff0c\u4ece\u7d22\u5f15 0 \u5230\u7d22\u5f15 N-1 \u5bf9\u94fe\u70b9\u8fdb\u884c\u6392\u5e8f\u3002<\/p>\n<p>\u94fe\u8868\u5206\u4e3a\u5355\u94fe\u8868\u548c\u53cc\u94fe\u8868\u4e24\u79cd\u3002<\/p>\n<h4>\u5355\u94fe\u8868<\/h4>\n<p><strong>1. \u521b\u5efa Node \u7c7b<\/strong><\/p>\n<p>\u521b\u5efa\u4e00\u4e2a Node \u7684\u7c7b\uff0c\u4f5c\u4e3a\u57fa\u7840\u6570\u636e\u7ed3\u6784\uff1a\u94fe\u70b9\uff0c\u5e76\u521d\u59cb\u5316\u5bf9\u5e94\u7684\u5185\u53c2\u3002<\/p>\n<p>\u5177\u4f53\u5b9e\u73b0\u4ee3\u7801\u5982\u4e0b\uff1a<\/p>\n<pre><code class=\"language-python\">class Node:\n    def __init__(self, data):\n        self.data = data #\u8868\u793a\u5bf9\u5e94\u7684\u5143\u7d20\u503c\n        self.next = None #\u8868\u793a\u4e0b\u4e00\u4e2a\u94fe\u63a5\u7684\u94fe\u70b9<\/code><\/pre>\n<p><strong>2. \u521b\u5efa Linked_List \u7c7b<\/strong><\/p>\n<p>\u521b\u5efa\u4e00\u4e2a Linked_List \u7684\u7c7b\uff0c\u5e76\u521d\u59cb\u5316\u5bf9\u5e94\u7684\u5185\u53c2\u3002<\/p>\n<p>\u5177\u4f53\u5b9e\u73b0\u4ee3\u7801\u5982\u4e0b\uff1a<\/p>\n<pre><code class=\"language-python\">class Linked_List:\n    def __init__(self):\n        self.head = None #\u8868\u793a\u94fe\u8868\u7684\u5934\u90e8\u5143\u7d20\n    def initlist(self,data_list):    #\u94fe\u8868\u521d\u59cb\u5316\u51fd\u6570\n        self.head=Node(data_list[0])   #\u521b\u5efa\u5934\u7ed3\u70b9\n        temp=self.head\n        for i in data_list[1:]: #\u9010\u4e2a\u4e3a data \u5185\u7684\u6570\u636e\u521b\u5efa\u7ed3\u70b9, \u5efa\u7acb\u94fe\u8868\n            node=Node(i)\n            temp.next=node\n            temp=temp.next<\/code><\/pre>\n<p><strong>3. \u6dfb\u52a0 is_empty \u51fd\u6570<\/strong><\/p>\n<p>\u6dfb\u52a0\u4e00\u4e2a is_empty \u7684\u51fd\u6570\uff0c\u529f\u80fd\u662f\u5224\u65ad\u94fe\u8868\u662f\u5426\u4e3a\u7a7a<\/p>\n<p>\u5177\u4f53\u5b9e\u73b0\u4ee3\u7801\u5982\u4e0b\uff1a<\/p>\n<pre><code class=\"language-python\">def is_empty(self):\n        return self.Head is None #\u5224\u65ad\u94fe\u8868\u662f\u5426\u4e3a\u7a7a<\/code><\/pre>\n<p><strong>4. \u6dfb\u52a0 insert \u51fd\u6570<\/strong><\/p>\n<p>insert(item) \u5f80\u94fe\u8868\u4e2d\u4efb\u610f\u4f4d\u7f6e\u6dfb\u52a0\u4e00\u4e2a item \u5143\u7d20<\/p>\n<p>\u6d41\u7a0b\u5982\u4e0b\uff1a<\/p>\n<ol>\n<li>Vertex vtx = new Vertex(v) \u521d\u59cb\u5316\u4e00\u4e2a\u65b0\u7684\u70b9<\/li>\n<li>tail.next = vtx \u961f\u5217\u5c3e\u90e8\u7684\u540e\u7ee7\u662f\u8fd9\u4e2a\u65b0\u7684\u70b9<\/li>\n<li>tail = vtx \u7136\u540e\u8ba9\u961f\u5217\u5c3e\u90e8\u6307\u9488\u6307\u5411\u8fd9\u4e2a\u65b0\u7684\u70b9<\/li>\n<\/ol>\n<p>\u5177\u4f53\u5b9e\u73b0\u4ee3\u7801\u5982\u4e0b\uff1a<\/p>\n<pre><code class=\"language-python\">def insert(self,key,value): #\u94fe\u8868\u63d2\u5165\u6570\u636e\u51fd\u6570\n        if key&amp;lt;0 or key&amp;gt;self.get_length()-1:\n            print(&amp;quot;insert error&amp;quot;)\n        temp=self.head\n        i=0\n        while i&amp;lt;=key: #\u904d\u5386\u627e\u5230\u7d22\u5f15\u503c\u4e3a key \u7684\u7ed3\u70b9\u540e, \u5728\u5176\u540e\u9762\u63d2\u5165\u7ed3\u70b9\n            pre=temp\n            temp=temp.next\n            i=i+1\n        node=Node(value)\n        pre.next=node\n        node.next=temp<\/code><\/pre>\n<p><strong>5. \u6dfb\u52a0 remove \u51fd\u6570<\/strong><\/p>\n<p>remove() \u4ece\u94fe\u8868\u4e2d\u4efb\u610f\u4f4d\u7f6e\u5220\u9664\u4e00\u4e2a\u5143\u7d20<\/p>\n<p>\u6d41\u7a0b\u5982\u4e0b\uff1a<\/p>\n<ol>\n<li>\u5148\u5224\u65ad\u961f\u5217\u662f\u5426\u4e3a\u7a7a\uff0c\u4e3a\u7a7a\u5373\u9000\u51fa dequeue \u64cd\u4f5c\uff0c\u4e0d\u4e3a\u7a7a\u5373\u7ee7\u7eed\u540e\u7eed\u64cd\u4f5c<\/li>\n<li>temp = head \u8bbe\u7f6e\u4e00\u4e2a temp \u6307\u9488\uff0c\u4f7f\u5b83\u7684\u6307\u9488\u6307\u5411\u961f\u5217\u5934\u90e8<\/li>\n<li>head = head.next \u961f\u5217\u5934\u90e8\u6307\u9488\uff0c\u4f7f\u4e4b\u6307\u5411\u961f\u5217\u5934\u90e8\u7684\u540e\u7ee7(\u5373\u961f\u5217\u5934\u90e8\u5143\u7d20\u51fa\u961f)<\/li>\n<li>delete temp \u5220\u9664 temp \u6307\u9488<\/li>\n<\/ol>\n<p>\u5177\u4f53\u5b9e\u73b0\u4ee3\u7801\u5982\u4e0b\uff1a<\/p>\n<pre><code class=\"language-python\">def remove(self,key):  #\u94fe\u8868\u5220\u9664\u6570\u636e\u51fd\u6570\n        if key&amp;lt;0 or key&amp;gt;self.get_length()-1:\n            print(&amp;quot;insert error&amp;quot;)\n        i=0\n        temp=self.head\n        while temp !=None:  #\u904d\u5386\u627e\u5230\u7d22\u5f15\u503c\u4e3a key \u7684\u7ed3\u70b9\n            pre=temp\n            temp=temp.next\n            i=i+1\n            if i==key:\n                pre.next=temp.next\n                temp=None\n                return True\n        pre.next=None<\/code><\/pre>\n<p><strong>6. \u6dfb\u52a0\u5176\u4ed6\u51fd\u6570<\/strong><\/p>\n<p>get_length:\u83b7\u53d6\u94fe\u8868\u7684\u957f\u5ea6<\/p>\n<p>print_list:\u904d\u5386\u94fe\u8868\uff0c\u5e76\u5c06\u5143\u7d20\u4f9d\u6b21\u6253\u5370\u51fa\u6765<\/p>\n<p>reverse:\u5c06\u94fe\u8868\u53cd\u8f6c<\/p>\n<p>\u5177\u4f53\u5b9e\u73b0\u4ee3\u7801\u5982\u4e0b\uff1a<\/p>\n<pre><code class=\"language-python\"> def get_length(self):  #\u83b7\u53d6\u94fe\u8868\u7684\u957f\u5ea6\n        temp=self.head #\u4e34\u65f6\u53d8\u91cf\u6307\u5411\u961f\u5217\u5934\u90e8\n        length=0 #\u8ba1\u7b97\u94fe\u8868\u7684\u957f\u5ea6\u53d8\u91cf\n        while temp!=None:\n            length=length+1\n            temp=temp.next\n        return length #\u8fd4\u56de\u94fe\u8868\u7684\u957f\u5ea6\n    def print_list(self):   #\u904d\u5386\u94fe\u8868\uff0c\u5e76\u5c06\u5143\u7d20\u4f9d\u6b21\u6253\u5370\u51fa\u6765\n        print(&amp;quot;linked_list:&amp;quot;)\n        temp = self.head #\u4e34\u65f6\u53d8\u91cf\u6307\u5411\u961f\u5217\u5934\u90e8\n        while temp is not None:\n            print(temp.data)\n            temp = temp.next\n    def reverse(self): #\u5c06\u94fe\u8868\u53cd\u8f6c\n        prev = None\n        current = self.head\n        while current:\n            next_node = current.next\n            current.next = prev\n            prev = current\n            current = next_node\n        self.head = prev<\/code><\/pre>\n<h4>\u590d\u6742\u5ea6\u5206\u6790<\/h4>\n<p>\u94fe\u8868\u5c5e\u4e8e\u5e38\u89c1\u7684\u4e00\u79cd\u7ebf\u6027\u7ed3\u6784\uff0c\u5bf9\u4e8e\u63d2\u5165\u548c\u79fb\u9664\u800c\u8a00\uff0c\u65f6\u95f4\u590d\u6742\u5ea6\u90fd\u4e3a O(1)<\/p>\n<p>\u4f46\u662f\u5bf9\u4e8e\u641c\u7d22\u64cd\u4f5c\u800c\u8a00\uff0c\u4e0d\u7ba1\u4ece\u94fe\u8868\u7684\u5934\u90e8\u8fd8\u662f\u5c3e\u90e8\uff0c\u90fd\u9700\u8981\u904d\u5386 O(n)\uff0c\u6240\u4ee5\u6700\u597d\u590d\u6742\u5ea6\u4e3a O(1)\uff0c\u6700\u574f\u7684\u60c5\u51b5\u5c31\u662f\u4ece\u5934\u90e8\u904d\u5386\u5230\u5c3e\u90e8\u624d\u641c\u7d22\u51fa\u5bf9\u5e94\u7684\u5143\u7d20\uff0c\u6240\u4ee5\u6700\u574f\u590d\u6742\u5ea6\u4e3a O(n)\uff0c\u5e73\u5747\u590d\u6742\u5ea6\u4e3a O(n)\u3002<\/p>\n<p>\u5f52\u7eb3\u5982\u4e0b\uff1a<\/p>\n<ul>\n<li>\u6700\u597d\u590d\u6742\u5ea6\u4e3a O(1)<\/li>\n<li>\u6700\u574f\u590d\u6742\u5ea6\u4e3a O(n)<\/li>\n<li>\u5e73\u5747\u590d\u6742\u5ea6\u4e3a O(n)<\/li>\n<\/ul>\n<h3>\u53cc\u94fe\u8868<\/h3>\n<p>\u53cc\u5411\u94fe\u8868\uff08Double_linked_list\uff09\u4e5f\u53eb\u53cc\u94fe\u8868\uff0c\u662f\u94fe\u8868\u7684\u4e00\u79cd\uff0c\u5b83\u7684<strong>\u6bcf\u4e2a\u6570\u636e\u7ed3\u70b9\u4e2d\u90fd\u6709\u4e24\u4e2a\u6307\u9488\uff0c\u5206\u522b\u6307\u5411\u76f4\u63a5\u540e\u7ee7\u548c\u76f4\u63a5\u524d\u9a71<\/strong>\u3002\u6240\u4ee5\uff0c\u4ece\u53cc\u5411\u94fe\u8868\u4e2d\u7684\u4efb\u610f\u4e00\u4e2a\u7ed3\u70b9\u5f00\u59cb\uff0c\u90fd\u53ef\u4ee5\u5f88\u65b9\u4fbf\u5730\u8bbf\u95ee\u5b83\u7684\u524d\u9a71\u7ed3\u70b9\u548c\u540e\u7ee7\u7ed3\u70b9\u3002<\/p>\n<pre><code class=\"language-python\">class Node(object):\n    # \u53cc\u5411\u94fe\u8868\u8282\u70b9\n    def __init__(self, item):\n        self.item = item\n        self.next = None\n        self.prev = None\nclass DLinkList(object):\n    # \u53cc\u5411\u94fe\u8868\n    def __init__(self):\n        self._head = None\n    def is_empty(self):\n        # \u5224\u65ad\u94fe\u8868\u662f\u5426\u4e3a\u7a7a\n        return self._head == None\n    def get_length(self):\n        # \u8fd4\u56de\u94fe\u8868\u7684\u957f\u5ea6\n        cur = self._head\n        count = 0\n        while cur != None:\n            count=count+1\n            cur = cur.next\n        return count\n    def travel(self):\n        # \u904d\u5386\u94fe\u8868\n        cur = self._head\n        while cur != None:\n            print(cur.item)\n            cur = cur.next\n        print(&amp;quot;&amp;quot;)\n    def add(self, item):\n        # \u5934\u90e8\u63d2\u5165\u5143\u7d20\n        node = Node(item)\n        if self.is_empty():\n            # \u5982\u679c\u662f\u7a7a\u94fe\u8868\uff0c\u5c06_head\u6307\u5411node\n            self._head = node\n        else:\n            # \u5c06node\u7684next\u6307\u5411_head\u7684\u5934\u8282\u70b9\n            node.next = self._head\n            # \u5c06_head\u7684\u5934\u8282\u70b9\u7684prev\u6307\u5411node\n            self._head.prev = node\n            # \u5c06_head \u6307\u5411node\n            self._head = node\n    def append(self, item):\n        # \u5c3e\u90e8\u63d2\u5165\u5143\u7d20\n        node = Node(item)\n        if self.is_empty():\n            # \u5982\u679c\u662f\u7a7a\u94fe\u8868\uff0c\u5c06_head\u6307\u5411node\n            self._head = node\n        else:\n            # \u79fb\u52a8\u5230\u94fe\u8868\u5c3e\u90e8\n            cur = self._head\n            while cur.next != None:\n                cur = cur.next\n            # \u5c06\u5c3e\u8282\u70b9cur\u7684next\u6307\u5411node\n            cur.next = node\n            # \u5c06node\u7684prev\u6307\u5411cur\n            node.prev = cur\n    def search(self, item):\n        # \u67e5\u627e\u5143\u7d20\u662f\u5426\u5b58\u5728\n        cur = self._head\n        while cur != None:\n            if cur.item == item:\n                return True\n            cur = cur.next\n        return False\n    def insert(self, pos, item):\n        # \u5728\u6307\u5b9a\u4f4d\u7f6e\u6dfb\u52a0\u8282\u70b9\n        if pos &amp;lt;= 0:\n            self.add(item)\n        elif pos &amp;gt; (self.length()-1):\n            self.append(item)\n        else:\n            node = Node(item)\n            cur = self._head\n            count = 0\n            # \u79fb\u52a8\u5230\u6307\u5b9a\u4f4d\u7f6e\u7684\u524d\u4e00\u4e2a\u4f4d\u7f6e\n            while count &amp;lt; (pos-1):\n                count += 1\n                cur = cur.next\n            # \u5c06node\u7684prev\u6307\u5411cur\n            node.prev = cur\n            # \u5c06node\u7684next\u6307\u5411cur\u7684\u4e0b\u4e00\u4e2a\u8282\u70b9\n            node.next = cur.next\n            # \u5c06cur\u7684\u4e0b\u4e00\u4e2a\u8282\u70b9\u7684prev\u6307\u5411node\n            cur.next.prev = node\n            # \u5c06cur\u7684next\u6307\u5411node\n            cur.next = node\n    def remove(self, item):\n        # \u5220\u9664\u5143\u7d20\n        if self.is_empty():\n            return\n        else:\n            cur = self._head\n            if cur.item == item:\n                # \u5982\u679c\u9996\u8282\u70b9\u7684\u5143\u7d20\u5373\u662f\u8981\u5220\u9664\u7684\u5143\u7d20\n                if cur.next == None:\n                    # \u5982\u679c\u94fe\u8868\u53ea\u6709\u8fd9\u4e00\u4e2a\u8282\u70b9\n                    self._head = None\n                else:\n                    # \u5c06\u7b2c\u4e8c\u4e2a\u8282\u70b9\u7684prev\u8bbe\u7f6e\u4e3aNone\n                    cur.next.prev = None\n                    # \u5c06_head\u6307\u5411\u7b2c\u4e8c\u4e2a\u8282\u70b9\n                    self._head = cur.next\n                return\n            while cur != None:\n                if cur.item == item:\n                    # \u5c06cur\u7684\u524d\u4e00\u4e2a\u8282\u70b9\u7684next\u6307\u5411cur\u7684\u540e\u4e00\u4e2a\u8282\u70b9\n                    cur.prev.next = cur.next\n                    # \u5c06cur\u7684\u540e\u4e00\u4e2a\u8282\u70b9\u7684prev\u6307\u5411cur\u7684\u524d\u4e00\u4e2a\u8282\u70b9\n                    cur.next.prev = cur.prev\n                    break\n                cur = cur.next<\/code><\/pre>\n<h4>\u793a\u4f8b<\/h4>\n<p>\u4ea4\u6362\u5355\u94fe\u8868\u91cc\u4e24\u4e2a\u94fe\u70b9<\/p>\n<p>\u5728\u8fd9\u4e2a\u5b9e\u9a8c\u4e2d\uff0c\u6211\u4eec\u8981\u7ed9\u5b9a\u4e24\u4e2a\u503c\uff0c\u5982\u679c\u8fd9\u4e24\u4e2a\u503c\u90fd\u5728\u5355\u94fe\u8868\u7684\u94fe\u70b9\u4e2d\uff0c\u5373\u4ea4\u6362\u8fd9\u4e24\u4e2a\u94fe\u70b9\u5728\u5355\u94fe\u8868\u7684\u4f4d\u7f6e\u3002<\/p>\n<p>\u4e3e\u4f8b\uff1a<\/p>\n<p>1-&gt;2-&gt;3-&gt;4-&gt;5<\/p>\n<p>input:1 4 output:4-&gt;2-&gt;3-&gt;1-&gt;5<\/p>\n<p>\u76ee\u6807\uff1a<\/p>\n<ol>\n<li>\u4ea4\u6362\u4e24\u4e2a\u94fe\u70b9\u5728\u94fe\u8868\u4e2d\u7684\u4f4d\u7f6e<\/li>\n<li>\u4e0d\u6539\u53d8\u5176\u4ed6\u94fe\u70b9\u5728\u94fe\u8868\u4e2d\u7684\u4f4d\u7f6e<\/li>\n<\/ol>\n<p>\u601d\u8def\uff1a<\/p>\n<ul>\n<li>\u91c7\u7528 insert \u7684\u601d\u60f3\uff0c\u5bf9\u4e8e\u8981\u4ea4\u6362\u7684\u4e24\u4e2a\u94fe\u70b9 d1 d2\uff0c\u5404\u81ea\u58f0\u660e\u65b0\u7684 D1 D2 \uff0c\u4f7f D1=d1, D2=d2<\/li>\n<li>\u7136\u540e\u628a \u7136\u540e\u518d\u6839\u636e d1 d2 \u7684\u4f4d\u7f6e\uff0c\u6539\u53d8\u7d22\u5f15\u7684\u4f4d\u7f6e\uff0c\u5373\u5b8c\u6210\u4ea4\u6362\u7684\u5168\u90e8\u64cd\u4f5c<\/li>\n<\/ul>\n<pre><code class=\"language-python\">class Node:\n    def __init__(self, data):\n        self.data = data\n        self.next = None\nclass Linkedlist:\n    def __init__(self):\n        self.head = None\n    def print_list(self):   #\u904d\u5386\u94fe\u8868\uff0c\u5e76\u5c06\u5143\u7d20\u4f9d\u6b21\u6253\u5370\u51fa\u6765\n        print(&amp;quot;linked_list:&amp;quot;)\n        temp=self.head\n        new_list=[]\n        while temp is not None:\n            new_list.append(temp.data)\n            temp=temp.next\n        print(new_list)\n    def insert(self, new_data):\n        new_node = Node(new_data)\n        new_node.next = self.head\n        self.head = new_node\n    def swapNodes(self, d1, d2):\n        prevD1 = None\n        prevD2 = None\n        if d1 == d2:\n            return\n        else:\n            D1 = self.head\n            while D1 is not None and D1.data != d1:\n                prevD1 = D1\n                D1 = D1.next\n            D2 = self.head\n            while D2 is not None and D2.data != d2:\n                prevD2 = D2\n                D2 = D2.next\n            if D1 is None and D2 is None:\n                return\n            if prevD1 is not None:\n                prevD1.next = D2\n            else:\n                self.head = D2\n            if prevD2 is not None:\n                prevD2.next = D1\n            else:\n                self.head = D1\n            temp = D1.next\n            D1.next = D2.next\n            D2.next = temp\n\nif __name__ == &amp;#039;__main__&amp;#039;:\n    list = Linkedlist()\n    list.insert(5)\n    list.insert(4)\n    list.insert(3)\n    list.insert(2)\n    list.insert(1)\n    list.print_list()\n    list.swapNodes(1, 4)\n    print(&amp;quot;After swapping&amp;quot;)\n    list.print_list()<\/code><\/pre>\n<h3>\u961f\u5217<\/h3>\n<p>\u961f\u5217 (queue) \u662f\u4e00\u79cd\u7279\u6b8a\u7684\u7ebf\u6027\u8868\uff0c\u7279\u6b8a\u4e4b\u5904\u5728\u4e8e\u5b83\u53ea\u5141\u8bb8\u5728\u8868\u7684<strong>\u524d\u7aef\uff08front\uff09\u8fdb\u884c\u5220\u9664<\/strong>\u64cd\u4f5c\uff0c\u800c\u5728\u8868\u7684<strong>\u540e\u7aef\uff08rear\uff09\u8fdb\u884c\u63d2\u5165<\/strong>\u64cd\u4f5c\uff0c\u548c\u6808\u4e00\u6837\uff0c\u961f\u5217\u662f\u4e00\u79cd\u64cd\u4f5c\u53d7\u9650\u5236\u7684\u7ebf\u6027\u8868\u3002\u8fdb\u884c\u63d2\u5165\u64cd\u4f5c\u7684\u7aef\u79f0\u4e3a\u961f\u5c3e\uff0c\u8fdb\u884c\u5220\u9664\u64cd\u4f5c\u7684\u7aef\u79f0\u4e3a\u961f\u5934\u3002<\/p>\n<p><img decoding=\"async\" src=\"https:\/\/kanghaov-img-1256185664.file.myqcloud.com\/2019\/07\/18\/5d306d784ca7c.png\" alt=\"wm.png\" \/><\/p>\n<p>\u961f\u5217\u7b26\u5408\u5148\u8fdb\u5148\u51fa[FIFO]\u7684\u539f\u5219\u3002\u56e0\u4e3a\u8981\u6392\u961f\u7684\u7b2c\u4e00\u4e2a\u9879\u76ee\uff0c\u6700\u7ec8\u5c06\u662f\u7b2c\u4e00\u4e2a\u8981\u51fa\u5217\u7684\u9879\u76ee\uff0c\u5982\u5728\u73b0\u5b9e\u751f\u6d3b\u4e2d\u7684\u961f\u5217\uff0c\u5148\u6765\u7684\u7ad9\u5728\u961f\u5217\u524d\u9762\uff0c\u540e\u6765\u7684\u5c31\u53ea\u80fd\u7ad9\u5728\u961f\u5217\u540e\u9762\u5566\u3002<\/p>\n<p><img decoding=\"async\" src=\"https:\/\/kanghaov-img-1256185664.file.myqcloud.com\/2019\/07\/18\/5d306e0448f5f.png\" alt=\"wm _1_.png\" \/><\/p>\n<p>\u961f\u5217\u6709\u4e24\u79cd\u5b9e\u73b0\u5f62\u5f0f\uff0c\u5206\u4e3a\u4e24\u79cd\uff1a<strong>\u6570\u7ec4<\/strong>\u548c<strong>\u94fe\u8868<\/strong>\u3002<\/p>\n<p>\u5728\u63a5\u4e0b\u6765\u7684\u5185\u5bb9\u91cc\uff0c\u6211\u4eec\u5c06\u4ee5\u94fe\u8868\u7684\u5f62\u5f0f\u5b9e\u73b0\u961f\u5217\uff0c\u9010\u6b65\u4ecb\u7ecd\u5177\u4f53\u529f\u80fd\u662f\u5982\u4f55\u5b9e\u73b0\u7684\u3002<\/p>\n<p><strong>1. \u521b\u5efa Node \u7c7b<\/strong><\/p>\n<p>\u521b\u5efa\u4e00\u4e2a Node \u7684\u7c7b\uff0c\u4f5c\u4e3a\u57fa\u7840\u6570\u636e\u7ed3\u6784\uff1a\u94fe\u70b9\uff0c\u5e76\u521d\u59cb\u5316\u5bf9\u5e94\u7684\u5185\u53c2\u3002<\/p>\n<p>\u5177\u4f53\u5b9e\u73b0\u4ee3\u7801\u5982\u4e0b<\/p>\n<pre><code class=\"language-python\">class Node(object):\n    def __init__(self,elem,next=None):\n        self.elem = elem #\u8868\u793a\u5bf9\u5e94\u7684\u5143\u7d20\u503c\n        self.next=next #\u8868\u793a\u4e0b\u4e00\u4e2a\u94fe\u63a5\u7684\u94fe\u70b9<\/code><\/pre>\n<p><strong>2. \u521b\u5efa Queue \u7c7b<\/strong><\/p>\n<p>\u521b\u5efa\u4e00\u4e2a Queue \u7684\u7c7b\uff0c\u4ee5\u94fe\u8868\u5f62\u5f0f\u7684\u961f\u5217\uff0c\u5e76\u521d\u59cb\u5316\u5bf9\u5e94\u7684\u5185\u53c2\u3002<\/p>\n<p>\u5177\u4f53\u5b9e\u73b0\u4ee3\u7801\u5982\u4e0b\uff1a<\/p>\n<pre><code>class Queue(object):\n    def __init__(self):\n        self.head = None #\u5934\u90e8\u94fe\u70b9\u4e3a None\n        self.rear = None #\u5c3e\u90e8\u94fe\u70b9\u4e3a None<\/code><\/pre>\n<p><strong>3. \u6dfb\u52a0 is_empty \u51fd\u6570<\/strong><\/p>\n<p>\u6dfb\u52a0\u4e00\u4e2a is_empty \u7684\u51fd\u6570\uff0c\u529f\u80fd\u662f\u5224\u65ad\u961f\u5217\u662f\u5426\u4e3a\u7a7a<\/p>\n<p>\u5177\u4f53\u5b9e\u73b0\u4ee3\u7801\u5982\u4e0b\uff1a<\/p>\n<pre><code class=\"language-python\">    def is_empty(self):\n        return self.head is None #\u5224\u65ad\u961f\u5217\u662f\u5426\u4e3a\u7a7a<\/code><\/pre>\n<p><strong>4. \u6dfb\u52a0 enqueue \u51fd\u6570<\/strong><\/p>\n<p>\u6dfb\u52a0\u4e00\u4e2a enqueue(elem) \u51fd\u6570\uff0c\u529f\u80fd\u662f\u5f80\u961f\u5217\u4e2d\u6dfb\u52a0\u4e00\u4e2a elem \u5143\u7d20<\/p>\n<p>\u6d41\u7a0b\u5982\u4e0b\uff1a<\/p>\n<ol>\n<li>Vertex vtx = new Vertex(v) \u521d\u59cb\u5316\u4e00\u4e2a\u65b0\u7684\u70b9<\/li>\n<li>tail.next = vtx \u961f\u5217\u5c3e\u90e8\u7684\u540e\u7ee7\u662f\u8fd9\u4e2a\u65b0\u7684\u70b9<\/li>\n<li>tail = vtx \u7136\u540e\u8ba9\u961f\u5217\u5c3e\u90e8\u6307\u9488\u6307\u5411\u8fd9\u4e2a\u65b0\u7684\u70b9<\/li>\n<\/ol>\n<p>\u6548\u679c\u6f14\u793a\uff1a\u5f80\u5df2\u77e5\u961f\u5217[29,9,53]\u91cc\u9762\u6dfb\u52a0\u4e00\u4e2a 80 \u5143\u7d20<\/p>\n<p><img decoding=\"async\" src=\"https:\/\/kanghaov-img-1256185664.file.myqcloud.com\/2019\/07\/18\/5d3075f6b560e.gif\" alt=\"wm.gif\" \/><\/p>\n<p>\u5177\u4f53\u5b9e\u73b0\u4ee3\u7801\u5982\u4e0b\uff1a<\/p>\n<pre><code class=\"language-python\">    def enqueue(self, elem):\n        p = Node(elem) #\u521d\u59cb\u5316\u4e00\u4e2a\u65b0\u7684\u70b9\n        if self.is_empty():\n            self.head = p #\u961f\u5217\u5934\u90e8\u4e3a\u65b0\u7684\u94fe\u70b9\n            self.rear = p #\u961f\u5217\u5c3e\u90e8\u4e3a\u65b0\u7684\u94fe\u70b9\n        else:\n            self.rear.next = p #\u961f\u5217\u5c3e\u90e8\u7684\u540e\u7ee7\u662f\u8fd9\u4e2a\u65b0\u7684\u70b9\n            self.rear =p #\u7136\u540e\u8ba9\u961f\u5217\u5c3e\u90e8\u6307\u9488\u6307\u5411\u8fd9\u4e2a\u65b0\u7684\u70b9<\/code><\/pre>\n<p><strong>5. \u6dfb\u52a0 dequeue \u51fd\u6570<\/strong><\/p>\n<p>\u6dfb\u52a0\u4e00\u4e2a dequeue() \u51fd\u6570\uff0c\u529f\u80fd\u662f\u4ece\u961f\u5217\u5934\u90e8\u5220\u9664\u4e00\u4e2a\u5143\u7d20<\/p>\n<p>\u6d41\u7a0b\u5982\u4e0b\uff1a<\/p>\n<ol>\n<li>\u5148\u5224\u65ad\u961f\u5217\u662f\u5426\u4e3a\u7a7a\uff0c\u4e3a\u7a7a\u5373\u9000\u51fa dequeue \u64cd\u4f5c\uff0c\u4e0d\u4e3a\u7a7a\u5373\u7ee7\u7eed\u540e\u7eed\u64cd\u4f5c<\/li>\n<li>temp = head \u8bbe\u7f6e\u4e00\u4e2a temp \u6307\u9488\uff0c\u4f7f\u5b83\u7684\u6307\u9488\u6307\u5411\u961f\u5217\u5934\u90e8<\/li>\n<li>head = head.next \u961f\u5217\u5934\u90e8\u6307\u9488\uff0c\u4f7f\u4e4b\u6307\u5411\u961f\u5217\u5934\u90e8\u7684\u540e\u7ee7(\u5373\u961f\u5217\u5934\u90e8\u5143\u7d20\u51fa\u961f)<\/li>\n<li>delete temp \u5220\u9664 temp \u6307\u9488<\/li>\n<\/ol>\n<p>\u6548\u679c\u6f14\u793a\uff1a\u5bf9\u5df2\u77e5\u961f\u5217[29,9,53,80] \u5220\u9664\u5934\u90e8\u5143\u7d20<\/p>\n<p><img decoding=\"async\" src=\"https:\/\/kanghaov-img-1256185664.file.myqcloud.com\/2019\/07\/18\/5d307680c71a1.gif\" alt=\"wm _1_.gif\" \/><\/p>\n<p>\u5177\u4f53\u5b9e\u73b0\u4ee3\u7801\u5982\u4e0b\uff1a<\/p>\n<pre><code class=\"language-python\">    def dequeue(self):\n        if self.is_empty(): #\u5224\u65ad\u961f\u5217\u662f\u5426\u4e3a\u7a7a\n            print(&amp;#039;Queue_is_empty&amp;#039;) #\u82e5\u961f\u5217\u4e3a\u7a7a\uff0c\u5219\u9000\u51fa dequeue \u64cd\u4f5c\n        else:\n            result = self.head.elem #result\u4e3a\u961f\u5217\u5934\u90e8\u5143\u7d20\n            self.head = self.head.next #\u6539\u53d8\u961f\u5217\u5934\u90e8\u6307\u9488\u4f4d\u7f6e\n            return result #\u8fd4\u56de\u961f\u5217\u5934\u90e8\u5143\u7d20<\/code><\/pre>\n<p><strong>6. \u6dfb\u52a0 peek \u51fd\u6570<\/strong><\/p>\n<p>\u6dfb\u52a0\u4e00\u4e2a peek() \u51fd\u6570\uff0c\u529f\u80fd\u662f\u67e5\u770b\u961f\u5217\u5934\u90e8\u7684\u5143\u7d20<\/p>\n<p>\u6d41\u7a0b\u5982\u4e0b\uff1a<\/p>\n<ol>\n<li>\u5224\u65ad\u961f\u5217\u662f\u5426\u4e3a\u7a7a\uff0c\u4e3a\u7a7a\u5373\u8fd4\u56de NOT_FOUND<\/li>\n<li>\u961f\u5217\u5982\u679c\u4e0d\u4e3a\u7a7a\uff0c\u8fd4\u56de\u961f\u5217\u5934\u90e8\u5143\u7d20<\/li>\n<\/ol>\n<p>\u5177\u4f53\u4ee3\u7801\u5b9e\u73b0\u5982\u4e0b:<\/p>\n<pre><code class=\"language-python\">    def peek(self):\n        if self.is_empty(): #\u5224\u65ad\u961f\u5217\u662f\u5426\u4e3a\u7a7a\n            print(&amp;#039;NOT_FOUND&amp;#039;) #\u4e3a\u7a7a\u5219\u8fd4\u56de NOT_FOUND\n        else:\n            return self.head.elem #\u8fd4\u56de\u961f\u5217\u5934\u90e8\u5143\u7d20<\/code><\/pre>\n<p><strong>7. \u6dfb\u52a0 print_queue \u51fd\u6570<\/strong><\/p>\n<p>\u6dfb\u52a0\u4e00\u4e2a print_queue() \u51fd\u6570\uff0c\u529f\u80fd\u662f\u5c55\u73b0\u961f\u5217\u7684\u5143\u7d20<\/p>\n<pre><code class=\"language-python\">    def print_queue(self):\n        print(&amp;quot;queue:&amp;quot;)\n        temp=self.head\n        myqueue=[] #\u6682\u65f6\u5b58\u653e\u961f\u5217\u6570\u636e\n        while temp is not None:\n            myqueue.append(temp.elem)\n            temp=temp.next\n        print(myqueue)<\/code><\/pre>\n<p>\u6700\u7ec8\u4ee3\u7801\u5982\u4e0b\uff1a<\/p>\n<pre><code class=\"language-python\">class Node(object):\n    def __init__(self,elem,next=None):\n        self.elem = elem #\u8868\u793a\u5bf9\u5e94\u7684\u5143\u7d20\u503c\n        self.next=next #\u8868\u793a\u4e0b\u4e00\u4e2a\u94fe\u63a5\u7684\u94fe\u70b9\nclass Queue(object):\n    def __init__(self):\n        self.head = None #\u5934\u90e8\u94fe\u70b9\u4e3a None\n        self.rear = None #\u5c3e\u90e8\u94fe\u70b9\u4e3a None\n    def is_empty(self):\n        return self.head is None #\u5224\u65ad\u961f\u5217\u662f\u5426\u4e3a\u7a7a\n    def enqueue(self, elem):\n        p = Node(elem) #\u521d\u59cb\u5316\u4e00\u4e2a\u65b0\u7684\u70b9\n        if self.is_empty():\n            self.head = p #\u961f\u5217\u5934\u90e8\u4e3a\u65b0\u7684\u94fe\u70b9\n            self.rear = p #\u961f\u5217\u5c3e\u90e8\u4e3a\u65b0\u7684\u94fe\u70b9\n        else:\n            self.rear.next = p #\u961f\u5217\u5c3e\u90e8\u7684\u540e\u7ee7\u662f\u8fd9\u4e2a\u65b0\u7684\u70b9\n            self.rear =p #\u7136\u540e\u8ba9\u961f\u5217\u5c3e\u90e8\u6307\u9488\u6307\u5411\u8fd9\u4e2a\u65b0\u7684\u70b9\n    def dequeue(self):\n        if self.is_empty(): #\u5224\u65ad\u961f\u5217\u662f\u5426\u4e3a\u7a7a\n            print(&amp;#039;Queue_is_empty&amp;#039;) #\u82e5\u961f\u5217\u4e3a\u7a7a\uff0c\u5219\u9000\u51fa dequeue \u64cd\u4f5c\n        else:\n            result = self.head.elem #result\u4e3a\u961f\u5217\u5934\u90e8\u5143\u7d20\n            self.head = self.head.next #\u6539\u53d8\u961f\u5217\u5934\u90e8\u6307\u9488\u4f4d\u7f6e\n            return result #\u8fd4\u56de\u961f\u5217\u5934\u90e8\u5143\u7d20\n    def peek(self):\n        if self.is_empty(): #\u5224\u65ad\u961f\u5217\u662f\u5426\u4e3a\u7a7a\n            print(&amp;#039;NOT_FOUND&amp;#039;) #\u4e3a\u7a7a\u5219\u8fd4\u56de NOT_FOUND\n        else:\n            return self.head.elem #\u8fd4\u56de\u961f\u5217\u5934\u90e8\u5143\u7d20\n    def print_queue(self):\n        print(&amp;quot;queue:&amp;quot;)\n        temp=self.head\n        myqueue=[] #\u6682\u65f6\u5b58\u653e\u961f\u5217\u6570\u636e\n        while temp is not None:\n            myqueue.append(temp.elem)\n            temp=temp.next\n        print(myqueue)<\/code><\/pre>\n<h4>\u590d\u6742\u5ea6\u5206\u6790<\/h4>\n<p>\u961f\u5217\u5c5e\u4e8e\u5e38\u89c1\u7684\u4e00\u79cd\u7ebf\u6027\u7ed3\u6784\uff0c\u5bf9\u4e8e\u51fa\u961f\u548c\u8fdb\u961f\u800c\u8a00\uff0c\u65f6\u95f4\u590d\u6742\u5ea6\u90fd\u4e3a O(1)<\/p>\n<p>\u961f\u5217\u6709\u4e24\u79cd\u5b9e\u73b0\u5f62\u5f0f\uff0c\u6570\u7ec4\u548c\u94fe\u8868\u3002\u6211\u4eec\u5728\u524d\u9762\u5df2\u7ecf\u4ecb\u7ecd\u4e86\u5982\u4f55\u7528\u94fe\u8868\u5b9e\u73b0\u7684\u961f\u5217\uff0c\u8fd9\u91cc\u5c31\u4e0d\u518d\u8d58\u8ff0\uff0c\u76f4\u63a5\u7ed9\u51fa\u53e6\u4e00\u79cd\u7528\u6570\u7ec4\u5b9e\u73b0\u7684\u961f\u5217\u4ee3\u7801\uff0c\u4f9b\u5927\u5bb6\u5b66\u4e60\u53c2\u8003\u3002<\/p>\n<p>\u5f62\u5f0f\uff1a\u7528\u6570\u7ec4\u5b9e\u73b0<\/p>\n<pre><code class=\"language-python\">class Queue():\n    def __init__(self):\n        self.entries = [] #\u8868\u793a\u961f\u5217\u5185\u7684\u53c2\u6570\n        self.length = 0 #\u8868\u793a\u961f\u5217\u7684\u957f\u5ea6\n        self.front=0 #\u8868\u793a\u961f\u5217\u5934\u90e8\u4f4d\u7f6e\n    def enqueue(self, item):\n        self.entries.append(item) #\u6dfb\u52a0\u5143\u7d20\u5230\u961f\u5217\u91cc\u9762\n        self.length = self.length + 1 #\u961f\u5217\u957f\u5ea6\u589e\u52a0 1\n    def dequeue(self):\n        self.length = self.length - 1 #\u961f\u5217\u7684\u957f\u5ea6\u51cf\u5c11 1\n        dequeued = self.entries[self.front] #\u961f\u9996\u5143\u7d20\u4e3adequeued\n        self.front-=1 #\u961f\u9996\u7684\u4f4d\u7f6e\u51cf\u5c111\n        self.entries = self.entries[self.front:] #\u961f\u5217\u7684\u5143\u7d20\u66f4\u65b0\u4e3a\u9000\u961f\u4e4b\u540e\u7684\u961f\u5217\n        return dequeued\n    def peek(self):\n        return self.entries[0] #\u76f4\u63a5\u8fd4\u56de\u961f\u5217\u7684\u961f\u9996\u5143\u7d20<\/code><\/pre>\n<h4>\u793a\u4f8b<\/h4>\n<p>\u8bbe\u8ba1\u961f\u5217\u7684\u5b9e\u73b0( \u5728\u8fd9\u91cc\u6211\u4eec\u8981\u6c42\u7528\u4e4b\u524d\u4ecb\u7ecd\u7684\u94fe\u8868\u5f62\u5f0f\u5b9e\u73b0 )<\/p>\n<p>\u5728\u961f\u5217\u4e2d\u5b9e\u73b0\u8fd9\u4e9b\u6b65\u9aa4\uff1a<\/p>\n<ol>\n<li>\u521d\u59cb\u5316\u521b\u5efa Node, Queue \u7c7b<\/li>\n<li>\u4f9d\u6b21\u6dfb\u52a0 21 35 58 13 \u8fdb\u961f\u5217<\/li>\n<li>\u8fd4\u56de\u961f\u5217\u5934\u90e8\u5143\u7d20<\/li>\n<li>\u5220\u9664\u6b64\u65f6\u961f\u5217\u5934\u90e8\u5143\u7d20<\/li>\n<li>\u8fd4\u56de\u6b64\u65f6\u961f\u5217\u5934\u90e8\u5143\u7d20<\/li>\n<\/ol>\n<pre><code class=\"language-python\">class Node(object):\n    def __init__(self,elem,next=None):\n        self.elem = elem #\u8868\u793a\u5bf9\u5e94\u7684\u5143\u7d20\u503c\n        self.next=next #\u8868\u793a\u4e0b\u4e00\u4e2a\u94fe\u63a5\u7684\u94fe\u70b9\nclass Queue(object):\n    def __init__(self):\n        self.head = None #\u5934\u90e8\u94fe\u70b9\u4e3a None\n        self.rear = None #\u5c3e\u90e8\u94fe\u70b9\u4e3a None\n    def is_empty(self):\n        return self.head is None #\u5224\u65ad\u961f\u5217\u662f\u5426\u4e3a\u7a7a\n    def enqueue(self, elem):\n        p = Node(elem) #\u521d\u59cb\u5316\u4e00\u4e2a\u65b0\u7684\u70b9\n        if self.is_empty():\n            self.head = p #\u961f\u5217\u5934\u90e8\u4e3a\u65b0\u7684\u94fe\u70b9\n            self.rear = p #\u961f\u5217\u5c3e\u90e8\u4e3a\u65b0\u7684\u94fe\u70b9\n        else:\n            self.rear.next = p #\u961f\u5217\u5c3e\u90e8\u7684\u540e\u7ee7\u662f\u8fd9\u4e2a\u65b0\u7684\u70b9\n            self.rear =p #\u7136\u540e\u8ba9\u961f\u5217\u5c3e\u90e8\u6307\u9488\u6307\u5411\u8fd9\u4e2a\u65b0\u7684\u70b9\n    def dequeue(self):\n        if self.is_empty(): #\u5224\u65ad\u961f\u5217\u662f\u5426\u4e3a\u7a7a\n            print(&amp;#039;Queue_is_empty&amp;#039;) #\u82e5\u961f\u5217\u4e3a\u7a7a\uff0c\u5219\u9000\u51fa dequeue \u64cd\u4f5c\n        else:\n            result = self.head.elem #result\u4e3a\u961f\u5217\u5934\u90e8\u5143\u7d20\n            self.head = self.head.next #\u6539\u53d8\u961f\u5217\u5934\u90e8\u6307\u9488\u4f4d\u7f6e\n            return result #\u8fd4\u56de\u961f\u5217\u5934\u90e8\u5143\u7d20\n    def peek(self):\n        if self.is_empty(): #\u5224\u65ad\u961f\u5217\u662f\u5426\u4e3a\u7a7a\n            print(&amp;#039;NOT_FOUND&amp;#039;) #\u4e3a\u7a7a\u5219\u8fd4\u56de NOT_FOUND\n        else:\n            return self.head.elem #\u8fd4\u56de\u961f\u5217\u5934\u90e8\u5143\u7d20\n    def print_queue(self):\n        print(&amp;quot;queue:&amp;quot;)\n        temp=self.head\n        myqueue=[] #\u6682\u65f6\u5b58\u653e\u961f\u5217\u6570\u636e\n        while temp is not None:\n            myqueue.append(temp.elem)\n            temp=temp.next\n        print(myqueue)\nif __name__==&amp;quot;__main__&amp;quot;:\n    queue=Queue()\n    queue.enqueue(21)\n    queue.enqueue(35)\n    queue.enqueue(58)\n    queue.enqueue(13)\n    queue.print_queue()\n    print(queue.peek())\n    queue.dequeue()\n    queue.print_queue()\n    print(queue.peek())<\/code><\/pre>\n<h2>\u8fdb\u9636\u77e5\u8bc6\u70b9<\/h2>\n<ul>\n<li>\u6811<\/li>\n<li>\u5b57\u5178\u6811<\/li>\n<li>\u5806<\/li>\n<li>\u56fe<\/li>\n<li>\u5e76\u67e5\u96c6<\/li>\n<\/ul>\n<h3>\u6811<\/h3>\n<p>\u6811 (tree) \u662f\u4e00\u79cd\u975e\u5e38\u9ad8\u6548\u7684\u975e\u7ebf\u6027\u5b58\u50a8\u7ed3\u6784\u3002\u6811\uff0c\u53ef\u4ee5\u5f88\u5f62\u8c61\u7684\u7406\u89e3\uff0c\u6709\u6839\uff0c\u6709\u53f6\u5b50\uff0c\u5bf9\u5e94\u5728\u6570\u636e\u7ed3\u6784\u4e2d\u5c31\u662f\u6839\u8282\u70b9\u3001\u53f6\u5b50\u8282\u70b9\uff0c\u540c\u4e00\u5c42\u7684\u53f6\u5b50\u53eb\u5144\u5f1f\u8282\u70b9\uff0c\u90bb\u8fd1\u4e0d\u540c\u5c42\u7684\u53eb\u7236\u5b50\u8282\u70b9\uff0c\u975e\u5e38\u597d\u7406\u89e3\u3002<\/p>\n<p>\u6ce8\uff1a\u5b9a\u4e49\u6765\u81ea\u767e\u5ea6\u767e\u79d1\u3002<\/p>\n<h4>\u5176\u4ed6\u6982\u5ff5\u89e3\u91ca<\/h4>\n<ul>\n<li><strong>\u4e8c\u53c9\u6811<\/strong>\uff0c\u5c31\u662f\u6bcf\u4e2a\u8282\u70b9\u90fd<strong>\u81f3\u591a\u6709\u4e8c\u4e2a\u5b50\u8282\u70b9<\/strong>\u7684\u6811\u3002<\/li>\n<li><strong>\u6ee1\u4e8c\u53c9\u6811<\/strong>\uff0c\u5c31\u662f\u9664\u4e86\u53f6\u5b50\u8282\u70b9\u5916\uff0c\u6bcf\u4e2a\u8282\u70b9\u90fd\u6709\u5de6\u53f3\u4e24\u4e2a\u5b50\u8282\u70b9\uff0c\u8fd9\u79cd\u4e8c\u53c9\u6811\u53eb\u505a\u6ee1\u4e8c\u53c9\u6811\u3002<\/li>\n<li><strong>\u5b8c\u5168\u4e8c\u53c9\u6811<\/strong>\uff0c\u5c31\u662f\u53f6\u5b50\u8282\u70b9\u90fd\u5728\u6700\u5e95\u4e0b\u4e24\u5c42\uff0c<strong>\u6700\u540e\u4e00\u5c42\u53f6\u5b50\u8282\u90fd\u9760\u5de6\u6392\u5217<\/strong>\uff0c\u5e76\u4e14\u9664\u4e86\u6700\u540e\u4e00\u5c42\uff0c\u5176\u4ed6\u5c42\u7684\u8282\u70b9\u4e2a\u6570\u90fd\u8981\u8fbe\u5230\u6700\u5927\uff0c\u8fd9\u79cd\u4e8c\u53c9\u6811\u53eb\u505a\u5b8c\u5168\u4e8c\u53c9\u6811\u3002<\/li>\n<\/ul>\n<p>\u5e38\u89c1\u7684\u4e8c\u53c9\u6811\u5982\u4e0b\u56fe\u6240\u793a<\/p>\n<p><img decoding=\"async\" src=\"https:\/\/kanghaov-img-1256185664.file.myqcloud.com\/2019\/07\/18\/5d307a225ebc1.png\" alt=\"wm.png\" \/><\/p>\n<p>\u5728\u63a5\u4e0b\u6765\u7684\u5185\u5bb9\u91cc\uff0c\u6211\u4eec\u5c06\u9010\u6b65\u4ecb\u7ecd\u4e8c\u53c9\u6811\u7684\u5177\u4f53\u529f\u80fd\u662f\u5982\u4f55\u5b9e\u73b0\u7684\u3002<\/p>\n<p><strong>\u601d\u8def\uff1a<\/strong><\/p>\n<ol>\n<li>\u5148\u5b9a\u4e49\u4e00\u4e2a\u8282\u70b9 node \u7c7b\uff0c\u5b58\u50a8\u6570\u636e data \u548c\u5de6\u5b50\u8282\u70b9 left \u4ee5\u53ca \u53f3\u5b50\u8282\u70b9 right\u3002<\/li>\n<li>\u518d\u5b9e\u73b0\u4e8c\u53c9\u6811 binary_tree \u7684\u7c7b\uff0c\u5e94\u81f3\u5c11\u6709\u4ee5\u4e0b\u5c5e\u6027\u548c\u51fd\u6570\uff1a \u5c5e\u6027\uff1a\u6709\u4e00\u4e2a\u6839\u8282\u70b9\uff08root) , \u5b83\u662f node \u7c7b\u3002 \u51fd\u6570\uff1a\u6dfb\u52a0\u5b50\u8282\u70b9 add \uff0c\u8fd4\u56de\u7236\u8282\u70b9 get_parent\uff0c\u5220\u9664\u5b50\u8282\u70b9 delete\u3002<\/li>\n<\/ol>\n<p>\u6b65\u9aa4\u5982\u4e0b\uff1a<\/p>\n<p><strong>1. \u521b\u5efa Node \u7c7b<\/strong><\/p>\n<p>\u521b\u5efa\u4e00\u4e2a Node \u7684\u7c7b\uff0c\u4f5c\u4e3a\u57fa\u7840\u6570\u636e\u7ed3\u6784\uff1a\u94fe\u70b9\uff0c\u5e76\u521d\u59cb\u5316\u5bf9\u5e94\u7684\u5185\u53c2\u3002<\/p>\n<p>\u5177\u4f53\u5b9e\u73b0\u4ee3\u7801\u5982\u4e0b\uff1a<\/p>\n<pre><code class=\"language-python\">class Node(object):\n    def __init__(self,item):\n        self.item = item #\u8868\u793a\u5bf9\u5e94\u7684\u5143\u7d20\n        self.left=None #\u8868\u793a\u5de6\u5b50\u8282\u70b9\n        self.right=None #\u8868\u793a\u53f3\u5b50\u8282\u70b9\n    def __str__(self):\n        return str(self.item)  #print \u4e00\u4e2a Node \u7c7b\u65f6\u4f1a\u6253\u5370 __str__ \u7684\u8fd4\u56de\u503c<\/code><\/pre>\n<p><strong>2. \u521b\u5efa Tree \u7c7b<\/strong><\/p>\n<p>\u521b\u5efa\u4e00\u4e2a Tree \u7684\u7c7b\uff0c\u5b9a\u4e49\u6839\u8282\u70b9\u3002<\/p>\n<p>\u5177\u4f53\u5b9e\u73b0\u4ee3\u7801\u5982\u4e0b\uff1a<\/p>\n<pre><code class=\"language-python\">class Tree(object):\n    def __init__(self):\n        self.root=Node(&amp;#039;root&amp;#039;)  #\u6839\u8282\u70b9\u5b9a\u4e49\u4e3a root \u6c38\u4e0d\u5220\u9664\uff0c\u4f5c\u4e3a\u54e8\u5175\u4f7f\u7528\u3002<\/code><\/pre>\n<p><strong>3. \u6dfb\u52a0 add \u51fd\u6570<\/strong><\/p>\n<p>\u6dfb\u52a0\u4e00\u4e2a add(item) \u7684\u51fd\u6570\uff0c\u529f\u80fd\u662f\u6dfb\u52a0\u5b50\u8282\u70b9\u5230\u6811\u91cc\u9762\u3002<\/p>\n<p>\u5177\u4f53\u5b9e\u73b0\u4ee3\u7801\u5982\u4e0b\uff1a<\/p>\n<pre><code class=\"language-python\">    def add(self,item):\n        node = Node(item)\n        if self.root is None:  #\u5982\u679c\u4e8c\u53c9\u6811\u4e3a\u7a7a\uff0c\u90a3\u4e48\u751f\u6210\u7684\u4e8c\u53c9\u6811\u6700\u7ec8\u4e3a\u65b0\u63d2\u5165\u6811\u7684\u70b9\n            self.root = node\n        else:\n            q = [self.root] # \u5c06q\u5217\u8868\uff0c\u6dfb\u52a0\u4e8c\u53c9\u6811\u7684\u6839\u8282\u70b9\n            while True:\n                pop_node = q.pop(0)\n                if pop_node.left is None: #\u5de6\u5b50\u6811\u4e3a\u7a7a\u5219\u5c06\u70b9\u6dfb\u52a0\u5230\u5de6\u5b50\u6811\n                    pop_node.left = node\n                    return\n                elif pop_node.right is None: #\u53f3\u5b50\u6811\u4e3a\u7a7a\u5219\u5c06\u70b9\u6dfb\u52a0\u5230\u53f3\u5b50\u6811\n                    pop_node.right = node\n                    return\n                else:\n                    q.append(pop_node.left)\n                    q.append(pop_node.right)<\/code><\/pre>\n<p><strong>4. \u6dfb\u52a0 get_parent \u51fd\u6570<\/strong><\/p>\n<p>\u6dfb\u52a0\u4e00\u4e2a get_parent(item) \u51fd\u6570\uff0c\u529f\u80fd\u662f\u627e\u5230 item \u7684\u7236\u8282\u70b9\u3002<\/p>\n<p>\u5177\u4f53\u5b9e\u73b0\u4ee3\u7801\u5982\u4e0b\uff1a<\/p>\n<pre><code class=\"language-python\">    def get_parent(self, item):\n        if self.root.item == item:\n            return None  # \u6839\u8282\u70b9\u6ca1\u6709\u7236\u8282\u70b9\n        tmp = [self.root] # \u5c06tmp\u5217\u8868\uff0c\u6dfb\u52a0\u4e8c\u53c9\u6811\u7684\u6839\u8282\u70b9\n        while tmp:\n            pop_node = tmp.pop(0)\n            if pop_node.left and pop_node.left.item == item: #\u67d0\u70b9\u7684\u5de6\u5b50\u6811\u4e3a\u5bfb\u627e\u7684\u70b9\n                return pop_node #\u8fd4\u56de\u67d0\u70b9\uff0c\u5373\u4e3a\u5bfb\u627e\u70b9\u7684\u7236\u8282\u70b9\n            if pop_node.right and pop_node.right.item == item: #\u67d0\u70b9\u7684\u53f3\u5b50\u6811\u4e3a\u5bfb\u627e\u7684\u70b9\n                return pop_node #\u8fd4\u56de\u67d0\u70b9\uff0c\u5373\u4e3a\u5bfb\u627e\u70b9\u7684\u7236\u8282\u70b9\n            if pop_node.left is not None: #\u6dfb\u52a0tmp \u5143\u7d20\n                tmp.append(pop_node.left)\n            if pop_node.right is not None:\n                tmp.append(pop_node.right)\n        return None<\/code><\/pre>\n<p><strong>5. \u6dfb\u52a0 delete \u51fd\u6570<\/strong><\/p>\n<p>\u6dfb\u52a0\u4e00\u4e2a delete(item) \u51fd\u6570\uff0c\u529f\u80fd\u662f\u4ece\u4e8c\u53c9\u6811\u4e2d\u5220\u9664\u4e00\u4e2a\u5b50\u8282\u70b9\u3002<\/p>\n<p>\u601d\u8def\u5982\u4e0b\uff1a<\/p>\n<pre><code>\u5148\u83b7\u53d6\u5f85\u5220\u9664\u8282\u70b9 item \u7684\u7236\u8282\u70b9\u3002\n    \u5982\u679c\u7236\u8282\u70b9\u4e0d\u4e3a\u7a7a\uff0c\u5224\u65ad item \u7684\u5de6\u53f3\u5b50\u6811\uff1a\n        \u5982\u679c\u5de6\u5b50\u6811\u4e3a\u7a7a\uff0c\u90a3\u4e48\u5224\u65ad item \u662f\u7236\u8282\u70b9\u7684\u5de6\u5b69\u5b50\uff0c\u8fd8\u662f\u53f3\u5b69\u5b50\uff1b\n            \u5982\u679c\u662f\u5de6\u5b69\u5b50\uff0c\u5c06\u7236\u8282\u70b9\u7684\u5de6\u6307\u9488\u6307\u5411 item \u7684\u53f3\u5b50\u6811\uff0c\u53cd\u4e4b\u5c06\u7236\u8282\u70b9\u7684\u53f3\u6307\u9488\u6307\u5411 item \u7684\u53f3\u5b50\u6811\u3002\n        \u5982\u679c\u53f3\u5b50\u6811\u4e3a\u7a7a\uff0c\u90a3\u4e48\u5224\u65ad item \u662f\u7236\u8282\u70b9\u7684\u5de6\u5b69\u5b50\uff0c\u8fd8\u662f\u53f3\u5b69\u5b50\uff1b\n            \u5982\u679c\u662f\u5de6\u5b69\u5b50\uff0c\u5c06\u7236\u8282\u70b9\u7684\u5de6\u6307\u9488\u6307\u5411 item \u7684\u5de6\u5b50\u6811\uff0c\u53cd\u4e4b\u5c06\u7236\u8282\u70b9\u7684\u53f3\u6307\u9488\u6307\u5411 item \u7684\u5de6\u5b50\u6811\u3002\n        \u5982\u679c\u5de6\u53f3\u5b50\u6811\u5747\u4e0d\u4e3a\u7a7a\uff0c\u5bfb\u627e\u53f3\u5b50\u6811\u4e2d\u7684\u6700\u5de6\u53f6\u5b50\u8282\u70b9 x \uff0c\u5c06 x \u66ff\u4ee3\u8981\u5220\u9664\u7684\u8282\u70b9\u3002\n    \u5220\u9664\u6210\u529f\uff0c\u8fd4\u56de True\u3002\n    \u5220\u9664\u5931\u8d25, \u8fd4\u56de False\u3002<\/code><\/pre>\n<p>\u6548\u679c\u6f14\u793a\uff1a\u5bf9\u5df2\u77e5\u4e8c\u53c9\u6811\u5220\u9664\u5143\u7d20 32<\/p>\n<p><img decoding=\"async\" src=\"https:\/\/kanghaov-img-1256185664.file.myqcloud.com\/2019\/07\/19\/5d31608a92f1c.gif\" alt=\"wm.gif\" \/><\/p>\n<p>\u5177\u4f53\u5b9e\u73b0\u4ee3\u7801\u5982\u4e0b\uff1a<\/p>\n<pre><code class=\"language-python\">    def delete(self, item):\n        if self.root is None:  # \u5982\u679c\u6839\u4e3a\u7a7a\uff0c\u5c31\u4ec0\u4e48\u4e5f\u4e0d\u505a\n            return False\n\n        parent = self.get_parent(item)\n        if parent:\n            del_node = parent.left if parent.left.item == item else parent.right  # \u5f85\u5220\u9664\u8282\u70b9\n            if del_node.left is None:\n                if parent.left.item == item:\n                    parent.left = del_node.right\n                else:\n                    parent.right = del_node.right\n                del del_node\n                return True\n            elif del_node.right is None:\n                if parent.left.item == item:\n                    parent.left = del_node.left\n                else:\n                    parent.right = del_node.left\n                del del_node\n                return True\n            else:  # \u5de6\u53f3\u5b50\u6811\u90fd\u4e0d\u4e3a\u7a7a\n                tmp_pre = del_node\n                tmp_next = del_node.right\n                if tmp_next.left is None:\n                    # \u66ff\u4ee3\n                    tmp_pre.right = tmp_next.right\n                    tmp_next.left = del_node.left\n                    tmp_next.right = del_node.right\n\n                else:\n                    while tmp_next.left:  # \u8ba9tmp\u6307\u5411\u53f3\u5b50\u6811\u7684\u6700\u540e\u4e00\u4e2a\u53f6\u5b50\n                        tmp_pre = tmp_next\n                        tmp_next = tmp_next.left\n                    # \u66ff\u4ee3\n                    tmp_pre.left = tmp_next.right\n                    tmp_next.left = del_node.left\n                    tmp_next.right = del_node.right\n                if parent.left.item == item:\n                    parent.left = tmp_next\n                else:\n                    parent.right = tmp_next\n                del del_node\n                return True\n        else:\n            return False<\/code><\/pre>\n<h4>\u4e8c\u53c9\u641c\u7d22\u6811<\/h4>\n<p>\u4e8c\u53c9\u641c\u7d22\u6811\u53c8\u79f0\u4e8c\u53c9\u67e5\u627e\u6811\uff0c\u4ea6\u79f0\u4e8c\u53c9\u6392\u5e8f\u6811\uff0c\u5982\u4e0b\u56fe\u6240\u793a\uff1a<\/p>\n<p><img decoding=\"async\" src=\"https:\/\/kanghaov-img-1256185664.file.myqcloud.com\/2019\/07\/19\/5d31618488b13.png\" alt=\"wm.png\" \/><\/p>\n<p>\u5b83\u4e3b\u8981\u7528\u4e8e\u641c\u7d22\u3002 \u5b83\u6216\u8005\u662f\u4e00\u68f5\u7a7a\u6811\uff0c\u6216\u8005\u662f\u5177\u6709\u4e0b\u5217\u6027\u8d28\u7684\u4e8c\u53c9\u6811\uff1a<\/p>\n<ol>\n<li>\u82e5\u5de6\u5b50\u6811\u4e0d\u7a7a\uff0c\u5219\u5de6\u5b50\u6811\u4e0a\u6240\u6709\u7ed3\u70b9\u7684\u503c\u5747\u5c0f\u4e8e\u5b83\u7684\u6839\u7ed3\u70b9\u7684\u503c\uff1b<\/li>\n<li>\u82e5\u53f3\u5b50\u6811\u4e0d\u7a7a\uff0c\u5219\u53f3\u5b50\u6811\u4e0a\u6240\u6709\u7ed3\u70b9\u7684\u503c\u5747\u5927\u4e8e\u5b83\u7684\u6839\u7ed3\u70b9\u7684\u503c\uff1b<\/li>\n<li>\u5de6\u3001\u53f3\u5b50\u6811\u4e5f\u5206\u522b\u4e3a\u4e8c\u53c9\u6392\u5e8f\u6811\u3002<\/li>\n<\/ol>\n<h4>\u5e73\u8861\u4e8c\u53c9\u6811<\/h4>\n<p>\u5e73\u8861\u4e8c\u53c9\u6811(\u5e73\u8861\u4e8c\u53c9\u6811\u53c8\u88ab\u79f0\u4e3a<strong> AVL \u6811<\/strong> )\u662f\u57fa\u4e8e\u4e8c\u5206\u6cd5\u7684\u7b56\u7565\u63d0\u9ad8\u6570\u636e\u7684\u67e5\u627e\u901f\u5ea6\u7684\u4e8c\u53c9\u6811\u7684\u6570\u636e\u7ed3\u6784\u3002<\/p>\n<p>\u7279\u70b9\uff1a\u5e73\u8861\u4e8c\u53c9\u6811\u662f\u91c7\u7528\u4e8c\u5206\u6cd5\u601d\u7ef4\u628a\u6570\u636e\u6309\u89c4\u5219\u7ec4\u88c5\u6210\u4e00\u4e2a\u6811\u5f62\u7ed3\u6784\u7684\u6570\u636e\uff0c\u7528\u8fd9\u4e2a\u6811\u5f62\u7ed3\u6784\u7684\u6570\u636e\u51cf\u5c11\u65e0\u5173\u6570\u636e\u7684\u68c0\u7d22\uff0c\u5927\u5927\u7684\u63d0\u5347\u4e86\u6570\u636e\u68c0\u7d22\u7684\u901f\u5ea6\uff1b\u5e73\u8861\u4e8c\u53c9\u6811\u7684\u6570\u636e\u7ed3\u6784\u7ec4\u88c5\u8fc7\u7a0b\u6709\u4ee5\u4e0b\u89c4\u5219\uff1a<\/p>\n<ol>\n<li>\u975e\u53f6\u5b50\u8282\u70b9\u53ea\u80fd\u5141\u8bb8\u6700\u591a\u4e24\u4e2a\u5b50\u8282\u70b9\u5b58\u5728\u3002<\/li>\n<li>\u6bcf\u4e00\u4e2a\u975e\u53f6\u5b50\u8282\u70b9\u6570\u636e\u5206\u5e03\u89c4\u5219\u4e3a<strong>\u5de6\u8fb9\u7684\u5b50\u8282\u70b9\u5c0f\u4e8e\u524d\u8282\u70b9\u7684\u503c\uff0c\u53f3\u8fb9\u7684\u5b50\u8282\u70b9\u5927\u4e8e\u5f53\u524d\u8282\u70b9\u7684\u503c<\/strong>(\u8fd9\u91cc\u503c\u662f\u57fa\u4e8e\u81ea\u5df1\u7684\u7b97\u6cd5\u89c4\u5219\u800c\u5b9a\u7684\uff0c\u6bd4\u5982 hash \u503c)\u3002<\/li>\n<\/ol>\n<h4>\u4e8c\u53c9\u6811\u7684\u904d\u5386\u95ee\u9898<\/h4>\n<p>\u904d\u5386\u539f\u7406\uff1a<\/p>\n<p><strong>\u4e8c\u53c9\u6811\u7684\u904d\u5386\uff1a\u662f\u6307\u4ece\u6839\u7ed3\u70b9\u51fa\u53d1\uff0c\u6309\u7167\u67d0\u79cd\u6b21\u5e8f\u4f9d\u6b21\u8bbf\u95ee\u4e8c\u53c9\u6811\u4e2d\u7684\u6240\u6709\u7ed3\u70b9\uff0c\u4f7f\u5f97\u6bcf\u4e2a\u7ed3\u70b9\u88ab\u8bbf\u95ee\u4e00\u6b21\u4e14\u4ec5\u88ab\u8bbf\u95ee\u4e00\u6b21\u3002<\/strong><\/p>\n<p>\u8fd9\u91cc\u6709\u4e24\u4e2a\u5173\u952e\u8bcd\uff1a<strong>\u8bbf\u95ee<\/strong>\u548c<strong>\u6b21\u5e8f<\/strong>\u3002<\/p>\n<p>\u8bbf\u95ee\u5176\u5b9e\u662f\u8981\u6839\u636e\u5b9e\u9645\u7684\u9700\u8981\u6765\u786e\u5b9a\u5177\u4f53\u505a\u4ec0\u4e48\uff0c\u6bd4\u5982\u5bf9\u6bcf\u4e2a\u7ed3\u70b9\u8fdb\u884c\u76f8\u5173\u8ba1\u7b97\uff0c\u8f93\u51fa\u6253\u5370\u7b49\u3002\u5b83\u7b97\u4f5c\u662f\u4e00\u4e2a\u62bd\u8c61\u64cd\u4f5c\u3002<\/p>\n<p>\u4e8c\u53c9\u6811\u7684\u904d\u5386\u6b21\u5e8f\u4e0d\u540c\u4e8e\u7ebf\u6027\u7ed3\u6784\uff0c\u6700\u591a\u4e5f\u5c31\u662f\u4ece\u5934\u5230\u5c3e\u3001\u5faa\u73af\u548c\u53cc\u5411\u7b49\u7b80\u5355\u7684\u904d\u5386\u65b9\u5f0f\u3002\u6811\u7684\u7ed3\u70b9\u4e4b\u95f4\u4e0d\u5b58\u5728\u552f\u4e00\u7684\u524d\u9a71\u548c\u540e\u7ee7\u5173\u7cfb\uff0c\u5728\u8bbf\u95ee\u4e00\u4e2a\u7ed3\u70b9\u540e\uff0c\u4e0b\u4e00\u4e2a\u88ab\u8bbf\u95ee\u7684\u7ed3\u70b9\u9762\u4e34\u7740\u4e0d\u540c\u7684\u9009\u62e9\u3002<\/p>\n<h4>\u4e8c\u53c9\u6811\u904d\u5386\u65b9\u6cd5<\/h4>\n<p>\u4e8c\u53c9\u6811\u7684\u904d\u5386\u65b9\u5f0f\u53ef\u4ee5\u6709\u5f88\u591a\uff0c\u5982\u679c\u6211\u4eec\u9650\u5236\u4ece\u5de6\u5230\u53f3\u7684\u987a\u5e8f\uff0c\u5c31\u4e3b\u8981\u5206\u4e3a\u4e09\u79cd\uff1a<\/p>\n<ol>\n<li>\u4e2d\u5e8f\u904d\u5386<\/li>\n<li>\u540e\u5e8f\u904d\u5386<\/li>\n<li>\u524d\u5e8f\u904d\u5386<\/li>\n<\/ol>\n<h4>\u4e2d\u5e8f\u904d\u5386<\/h4>\n<ol>\n<li>\u5148\u5904\u7406<strong>\u5de6\u5b50\u6811<\/strong>\uff0c\u7136\u540e\u5904\u7406<strong>\u5f53\u524d\u8282\u70b9<\/strong>\uff0c\u518d\u5904\u7406<strong>\u53f3\u5b50\u6811<\/strong>\uff1b<\/li>\n<li>\u5bf9\u4e8e\u4e00\u9897\u4e8c\u53c9\u67e5\u627e\u6811\uff0c\u6240\u6709\u7684\u4fe1\u606f\u90fd\u662f\u6709\u5e8f\u6392\u5217\u7684\uff0c\u4e2d\u5e8f\u904d\u5386\u53ef\u4ee5\u662f\u4fe1\u606f\u6709\u5e8f\u8f93\u51fa\uff0c\u4e14\u8fd0\u884c\u65f6\u95f4\u4e3a O(n)\uff1b<\/li>\n<li>\u9012\u5f52\u5b9e\u73b0\u4e2d\u5e8f\u904d\u5386\u3002<\/li>\n<\/ol>\n<p>\u5728\u4e4b\u524d\u7684 Tree \u7c7b\u91cc\u9762\u6dfb\u52a0 inorder \u51fd\u6570<\/p>\n<p>\u53c2\u8003\u4ee3\u7801\u5982\u4e0b\uff1a<\/p>\n<pre><code class=\"language-python\">    def inorder(self,node):  # \u4e2d\u5e8f\u904d\u5386\n        if node is None:\n            return []\n        result = [node.item]\n        left_item = self.inorder(node.left)\n        right_item = self.inorder(node.right)\n        return left_item + result + right_item<\/code><\/pre>\n<p>\u4e2d\u5e8f\u904d\u5386\u7684\u6548\u679c\u6f14\u793a:<\/p>\n<p><img decoding=\"async\" src=\"https:\/\/kanghaov-img-1256185664.file.myqcloud.com\/2019\/07\/19\/5d31631b18d1e.gif\" alt=\"wm.gif\" \/><\/p>\n<h4>\u540e\u5e8f\u904d\u5386<\/h4>\n<ol>\n<li>\u5148\u5904\u7406\u5de6\u53f3\u5b50\u6811\uff0c\u7136\u540e\u518d\u5904\u7406\u5f53\u524d\u8282\u70b9\uff0c\u8fd0\u884c\u65f6\u95f4\u4e3a O\uff08n\uff09<\/li>\n<li>\u9012\u5f52\u5b9e\u73b0\u540e\u5e8f\u904d\u5386<\/li>\n<\/ol>\n<p>\u53c2\u8003\u4ee3\u7801\u5982\u4e0b\uff1a<\/p>\n<pre><code class=\"language-python\">    def postorder(self,node):  # \u540e\u5e8f\u904d\u5386\n        if node is None:\n            return []\n        result = [node.item]\n        left_item = self.postorder(node.left)\n        right_item = self.postorder(node.right)\n        return left_item + right_item + result<\/code><\/pre>\n<h4>\u5148\u5e8f\u904d\u5386<\/h4>\n<ol>\n<li>\u5148\u5904\u7406\u5f53\u524d\u8282\u70b9\uff0c\u518d\u5904\u7406\u5de6\u53f3\u5b50\u6811\uff1b<\/li>\n<li>\u9012\u5f52\u5b9e\u73b0\u5148\u5e8f\u904d\u5386\u3002<\/li>\n<\/ol>\n<p>\u53c2\u8003\u4ee3\u7801\uff1a<\/p>\n<pre><code class=\"language-python\">    def preorder(self,node):  # \u5148\u5e8f\u904d\u5386\n        if node is None:\n            return []\n        result = [node.item]\n        left_item = self.preorder(node.left)\n        right_item = self.preorder(node.right)\n        return result + left_item + right_item\n<\/code><\/pre>\n<h4>\u793a\u4f8b<\/h4>\n<p>\u8bbe\u8ba1\u4e8c\u53c9\u6811\u4e09\u79cd\u904d\u5386\u7684\u5b9e\u73b0<\/p>\n<p>\u5728\u4ee3\u7801\u4e2d\u5b9e\u73b0\u8fd9\u4e9b\u6b65\u9aa4\uff1a<\/p>\n<ol>\n<li>\u521d\u59cb\u5316\u521b\u5efa Node,Queue \u7c7b\uff1b<\/li>\n<li>\u5c06 1-9 \u6dfb\u52a0\u5230\u4e8c\u53c9\u6811\u91cc\u9762(\u4f7f\u7528 add \u51fd\u6570)\uff1b<\/li>\n<li>\u5c06\u4e09\u79cd\u904d\u5386\u8fc7\u7a0b\uff0c\u6700\u540e\u6253\u5370\u51fa\u6765\u3002<\/li>\n<\/ol>\n<p><strong>\u6548\u679c:<\/strong><\/p>\n<p><strong>input:<\/strong><\/p>\n<p>[1,2,3,4,5,6,7,8,9]<\/p>\n<p><img decoding=\"async\" src=\"https:\/\/kanghaov-img-1256185664.file.myqcloud.com\/2019\/07\/19\/5d316463ee255.png\" alt=\"wm.png\" \/><\/p>\n<p><strong>output:<\/strong><\/p>\n<p>\u4e2d\u5e8f\u904d\u5386: [7,3,8,1,9,4,10,&#8217;root&#8217;,5,2,6]   \u4e2a\u4eba\u7406\u89e3\uff1a\u987a\u65f6\u9488\u753b\u5708<\/p>\n<p>\u5148\u5e8f\u904d\u5386: [&#8216;root&#8217;,1,3,7,8,4,9,10,2,5,6]<\/p>\n<p>\u540e\u5e8f\u904d\u5386\uff1a [7,8,3,9,10,4,1,5,6,2,&#8217;root&#8217;] \u4e2a\u4eba\u7406\u89e3\uff1a\u9006\u65f6\u9488\u753b\u5708<\/p>\n<pre><code class=\"language-python\">class Node(object):\n    def __init__(self,item):\n        self.item=item #\u8868\u793a\u5bf9\u5e94\u7684\u5143\u7d20\n        self.left=None #\u8868\u793a\u5de6\u8282\u70b9\n        self.right=None #\u8868\u793a\u53f3\u8282\u70b9\n    def __str__(self):\n        return str(self.item)  #print \u4e00\u4e2a Node \u7c7b\u65f6\u4f1a\u6253\u5370 __str__ \u7684\u8fd4\u56de\u503c\nclass Tree(object):\n    def __init__(self):\n        self.root=Node(&amp;#039;root&amp;#039;)  #\u6839\u8282\u70b9\u5b9a\u4e49\u4e3a root \u6c38\u4e0d\u5220\u9664\uff0c\u4f5c\u4e3a\u54e8\u5175\u4f7f\u7528\u3002\n    def add(self,item):\n        node = Node(item)\n        if self.root is None:  #\u5982\u679c\u4e8c\u53c9\u6811\u4e3a\u7a7a\uff0c\u90a3\u4e48\u751f\u6210\u7684\u4e8c\u53c9\u6811\u6700\u7ec8\u4e3a\u65b0\u63d2\u5165\u6811\u7684\u70b9\n            self.root = node\n        else:\n            q = [self.root] # \u5c06q\u5217\u8868\uff0c\u6dfb\u52a0\u4e8c\u53c9\u6811\u7684\u6839\u8282\u70b9\n            while True:\n                pop_node = q.pop(0)\n                if pop_node.left is None: #\u5de6\u5b50\u6811\u4e3a\u7a7a\u5219\u5c06\u70b9\u6dfb\u52a0\u5230\u5de6\u5b50\u6811\n                    pop_node.left = node\n                    return\n                elif pop_node.right is None: #\u53f3\u5b50\u6811\u4e3a\u7a7a\u5219\u5c06\u70b9\u6dfb\u52a0\u5230\u53f3\u5b50\u6811\n                    pop_node.right = node\n                    return\n                else:\n                    q.append(pop_node.left)\n                    q.append(pop_node.right)\n    def get_parent(self, item):\n        if self.root.item == item:\n            return None  # \u6839\u8282\u70b9\u6ca1\u6709\u7236\u8282\u70b9\n        tmp = [self.root] # \u5c06tmp\u5217\u8868\uff0c\u6dfb\u52a0\u4e8c\u53c9\u6811\u7684\u6839\u8282\u70b9\n        while tmp:\n            pop_node = tmp.pop(0)\n            if pop_node.left and pop_node.left.item == item: #\u67d0\u70b9\u7684\u5de6\u5b50\u6811\u4e3a\u5bfb\u627e\u7684\u70b9\n                return pop_node #\u8fd4\u56de\u67d0\u70b9\uff0c\u5373\u4e3a\u5bfb\u627e\u70b9\u7684\u7236\u8282\u70b9\n            if pop_node.right and pop_node.right.item == item: #\u67d0\u70b9\u7684\u53f3\u5b50\u6811\u4e3a\u5bfb\u627e\u7684\u70b9\n                return pop_node #\u8fd4\u56de\u67d0\u70b9\uff0c\u5373\u4e3a\u5bfb\u627e\u70b9\u7684\u7236\u8282\u70b9\n            if pop_node.left is not None: #\u6dfb\u52a0tmp \u5143\u7d20\n                tmp.append(pop_node.left)\n            if pop_node.right is not None:\n                tmp.append(pop_node.right)\n        return None\n    def delete(self, item):\n        if self.root is None:  # \u5982\u679c\u6839\u4e3a\u7a7a\uff0c\u5c31\u4ec0\u4e48\u4e5f\u4e0d\u505a\n            return False\n\n        parent = self.get_parent(item)\n        if parent:\n            del_node = parent.left if parent.left.item == item else parent.right  # \u5f85\u5220\u9664\u8282\u70b9\n            if del_node.left is None:\n                if parent.left.item == item:\n                    parent.left = del_node.right\n                else:\n                    parent.right = del_node.right\n                del del_node\n                return True\n            elif del_node.right is None:\n                if parent.left.item == item:\n                    parent.left = del_node.left\n                else:\n                    parent.right = del_node.left\n                del del_node\n                return True\n            else:  # \u5de6\u53f3\u5b50\u6811\u90fd\u4e0d\u4e3a\u7a7a\n                tmp_pre = del_node\n                tmp_next = del_node.right\n                if tmp_next.left is None:\n                    # \u66ff\u4ee3\n                    tmp_pre.right = tmp_next.right\n                    tmp_next.left = del_node.left\n                    tmp_next.right = del_node.right\n\n                else:\n                    while tmp_next.left:  # \u8ba9tmp\u6307\u5411\u53f3\u5b50\u6811\u7684\u6700\u540e\u4e00\u4e2a\u53f6\u5b50\n                        tmp_pre = tmp_next\n                        tmp_next = tmp_next.left\n                    # \u66ff\u4ee3\n                    tmp_pre.left = tmp_next.right\n                    tmp_next.left = del_node.left\n                    tmp_next.right = del_node.right\n                if parent.left.item == item:\n                    parent.left = tmp_next\n                else:\n                    parent.right = tmp_next\n                del del_node\n                return True\n        else:\n            return False\n    def preorder(self,node):  # \u5148\u5e8f\u904d\u5386\n        if node is None:\n            return []\n        result = [node.item]\n        left_item = self.preorder(node.left)\n        right_item = self.preorder(node.right)\n        return result + left_item + right_item\n\n    def inorder(self,node):  # \u4e2d\u5e8f\u904d\u5386\n        if node is None:\n            return []\n        result = [node.item]\n        left_item = self.inorder(node.left)\n        right_item = self.inorder(node.right)\n        return left_item + result + right_item\n\n    def postorder(self,node):  # \u540e\u5e8f\u904d\u5386\n        if node is None:\n            return []\n        result = [node.item]\n        left_item = self.postorder(node.left)\n        right_item = self.postorder(node.right)\n        return left_item + right_item + result\nif __name__ == &amp;#039;__main__&amp;#039;:\n    t = Tree()\n    for i in range(1,11):\n        t.add(i)\n    print(&amp;#039;\u5148\u5e8f\u904d\u5386:&amp;#039;, t.preorder(t.root))\n    print(&amp;#039;\u4e2d\u5e8f\u904d\u5386:&amp;#039;, t.inorder(t.root))\n    print(&amp;#039;\u540e\u5e8f\u904d\u5386:&amp;#039;, t.postorder(t.root))<\/code><\/pre>\n<h3>\u5b57\u5178\u6811<\/h3>\n<p>\u5b57\u5178\u6811\uff0c\u53c8\u79f0\u5355\u8bcd\u67e5\u627e\u6811\uff0cTrie \u6811\uff0c\u662f\u4e00\u79cd\u6811\u5f62\u7ed3\u6784\uff0c\u662f\u4e00\u79cd\u54c8\u5e0c\u6811\u7684\u53d8\u79cd\u3002\u5178\u578b\u5e94\u7528\u662f\u7528\u4e8e\u7edf\u8ba1\uff0c\u6392\u5e8f\u548c\u4fdd\u5b58\u5927\u91cf\u7684\u5b57\u7b26\u4e32\uff08\u4f46\u4e0d\u4ec5\u9650\u4e8e\u5b57\u7b26\u4e32\uff09\uff0c\u6240\u4ee5\u7ecf\u5e38\u88ab==\u641c\u7d22\u5f15\u64ce\u7cfb\u7edf\u7528\u4e8e\u6587\u672c\u8bcd\u9891\u7edf\u8ba1==\u3002\u5b83\u7684\u4f18\u70b9\u662f\uff1a<strong>\u5229\u7528\u5b57\u7b26\u4e32\u7684\u516c\u5171\u524d\u7f00\u6765\u51cf\u5c11\u67e5\u8be2\u65f6\u95f4\uff0c\u6700\u5927\u9650\u5ea6\u5730\u51cf\u5c11\u65e0\u8c13\u7684\u5b57\u7b26\u4e32\u6bd4\u8f83\uff0c\u67e5\u8be2\u6548\u7387\u6bd4\u54c8\u5e0c\u6811\u9ad8<\/strong>\u3002<\/p>\n<h4>\u5b57\u5178\u6811\u7684\u4e3b\u8981\u6027\u8d28<\/h4>\n<p>\u5b83\u6709 3 \u4e2a\u57fa\u672c\u6027\u8d28\uff1a<\/p>\n<ol>\n<li>\u6839\u8282\u70b9\u4e0d\u5305\u542b\u5b57\u7b26\uff0c\u9664\u6839\u8282\u70b9\u5916\u6bcf\u4e00\u4e2a\u8282\u70b9\u90fd\u53ea\u5305\u542b\u4e00\u4e2a\u5b57\u7b26\uff1b<\/li>\n<li>\u4ece\u6839\u8282\u70b9\u5230\u67d0\u4e00\u8282\u70b9\uff0c\u8def\u5f84\u4e0a\u7ecf\u8fc7\u7684\u5b57\u7b26\u8fde\u63a5\u8d77\u6765\uff0c\u4e3a\u8be5\u8282\u70b9\u5bf9\u5e94\u7684\u5b57\u7b26\u4e32\uff1b<\/li>\n<li>\u6bcf\u4e2a\u8282\u70b9\u7684\u6240\u6709\u5b50\u8282\u70b9\u5305\u542b\u7684\u5b57\u7b26\u90fd\u4e0d\u76f8\u540c\u3002<\/li>\n<\/ol>\n<p>\u5728\u63a5\u4e0b\u6765\u7684\u5185\u5bb9\u91cc\uff0c\u6211\u4eec\u5c06\u9010\u6b65\u4ecb\u7ecd\u5b57\u5178\u6811\u7684\u5177\u4f53\u529f\u80fd\u662f\u5982\u4f55\u5b9e\u73b0\u7684\u3002<\/p>\n<p><strong>1. \u521b\u5efa TrieNode \u7c7b<\/strong><\/p>\n<p>\u521b\u5efa\u4e00\u4e2a TrieNode \u7684\u7c7b,\u6784\u5efa\u5185\u7f6e\u5b57\u5178\u7ed3\u6784<\/p>\n<p>\u5177\u4f53\u5b9e\u73b0\u4ee3\u7801\u5982\u4e0b<\/p>\n<pre><code class=\"language-python\">class TrieNode:\n    def __init__(self):\n        self.nodes = dict()  # \u6784\u5efa\u5b57\u5178\n        self.is_leaf = False<\/code><\/pre>\n<p><strong>2. \u6dfb\u52a0 insert \u51fd\u6570<\/strong><\/p>\n<p>\u63d2\u5165\u4e00\u4e2a\u5b57\u5230\u5b57\u5178\u6811\u4e2d<\/p>\n<p>\u5177\u4f53\u5b9e\u73b0\u4ee3\u7801\u5982\u4e0b\uff1a<\/p>\n<pre><code class=\"language-python\">    def insert(self, word: str):\n        curr = self\n        for char in word:\n            if char not in curr.nodes:\n                curr.nodes[char] = TrieNode()\n            curr = curr.nodes[char]\n        curr.is_leaf = True<\/code><\/pre>\n<p><strong>4. \u6dfb\u52a0 search \u51fd\u6570<\/strong><\/p>\n<p>\u5728\u5b57\u5178\u6811\u91cc\u9762\u67e5\u8be2\u4e00\u4e2a\u5b57<\/p>\n<p>\u5177\u4f53\u5b9e\u73b0\u4ee3\u7801\u5982\u4e0b\uff1a<\/p>\n<pre><code class=\"language-python\">    def search(self, word: str):\n        curr = self\n        for char in word:\n            if char not in curr.nodes:\n                return False\n            curr = curr.nodes[char]\n        return curr.is_leaf<\/code><\/pre>\n<pre><code class=\"language-python\">class TrieNode:\n    def __init__(self):\n        self.nodes = dict()\n        self.is_leaf = False\n\n    def insert(self,word:str):\n        curr = self\n        for char in word:\n            if char not in curr.nodes:\n                curr.nodes[char] = TrieNode()\n            curr = curr.nodes[char]\n        curr.is_leaf = True\n\n    def insert_many(self,words:[str]):\n        for word in words:\n            self.insert(word)\n    def search(self,word:str):\n        curr = self\n        for char in word:\n            if char not in curr.nodes:\n                return False\n            curr = curr.nodes[char]\n        return curr.is_leaf<\/code><\/pre>\n<h3>\u5806<\/h3>\n<p>\u5806 (heap) \u662f\u4e00\u79cd\u7ecf\u8fc7\u6392\u5e8f\u7684\u5b8c\u5168\u4e8c\u53c9\u6811\uff0c\u5176\u4e2d\u4efb\u4e00\u975e\u53f6\u5b50\u8282\u70b9\u7684\u503c\u5747\u4e0d\u5927\u4e8e\uff08\u6216\u4e0d\u5c0f\u4e8e\uff09\u5176\u5de6\u5b69\u5b50\u548c\u53f3\u5b69\u5b50\u8282\u70b9\u7684\u503c\u3002<\/p>\n<p>\u6ce8\uff1a\u5b9a\u4e49\u6765\u81ea\u767e\u5ea6\u767e\u79d1\u3002<\/p>\n<p>\u5806\uff0c\u53c8\u88ab\u4e3a\u4f18\u5148\u961f\u5217(priority queue)\u3002\u5c3d\u7ba1\u540d\u4e3a\u4f18\u5148\u961f\u5217\uff0c\u4f46\u5806\u5e76\u4e0d\u662f\u961f\u5217\u3002<\/p>\n<h4>\u5176\u4ed6\u6982\u5ff5\u89e3\u91ca<\/h4>\n<ul>\n<li><strong>\u6700\u5927\u5806<\/strong> \u6839\u7ed3\u70b9\u7684\u952e\u503c\u662f\u6240\u6709\u5806\u7ed3\u70b9\u952e\u503c\u4e2d\u6700\u5927\u8005\u3002<\/li>\n<li><strong>\u6700\u5c0f\u5806<\/strong> \u6839\u7ed3\u70b9\u7684\u952e\u503c\u662f\u6240\u6709\u5806\u7ed3\u70b9\u952e\u503c\u4e2d\u6700\u5c0f\u8005\u3002<\/li>\n<\/ul>\n<p>\u6700\u5c0f\u5806<\/p>\n<p><img decoding=\"async\" src=\"https:\/\/kanghaov-img-1256185664.file.myqcloud.com\/2019\/07\/19\/5d3173f4217a4.png\" alt=\"wm.png\" \/><\/p>\n<p>\u6700\u5927\u5806<\/p>\n<p><img decoding=\"async\" src=\"https:\/\/kanghaov-img-1256185664.file.myqcloud.com\/2019\/07\/19\/5d317421e9357.png\" alt=\"wm.png\" \/><\/p>\n<p>\u5806\u6709\u4e24\u70b9\u9700\u8981\u4e86\u89e3\uff0c\u4e00\u662f\u5806\u4e00\u822c\u91c7\u7528\u5b8c\u5168\u4e8c\u53c9\u6811\uff1b\u4e8c\u662f\u5806\u4e2d\u7684\u6bcf\u4e00\u4e2a\u8282\u70b9\u90fd\u5927\u4e8e\u5176\u5de6\u53f3\u5b50\u8282\u70b9\uff08\u5927\u9876\u5806\uff09\uff0c\u6216\u8005\u5806\u4e2d\u6bcf\u4e00\u4e2a\u8282\u70b9\u90fd\u5c0f\u4e8e\u5176\u5de6\u53f3\u5b50\u8282\u70b9\uff08\u5c0f\u9876\u5806\uff09\u3002<\/p>\n<p><strong>1. \u521b\u5efa heap \u7c7b<\/strong><\/p>\n<pre><code class=\"language-python\">class heap(object):\n    def __init__(self):\n        #\u521d\u59cb\u5316\u4e00\u4e2a\u7a7a\u5806\uff0c\u4f7f\u7528\u6570\u7ec4\u6765\u5728\u5b58\u653e\u5806\u5143\u7d20\uff0c\u8282\u7701\u5b58\u50a8\n        self.data_list = []<\/code><\/pre>\n<p><strong>2. \u6dfb\u52a0 get_parent_index \u51fd\u6570<\/strong><\/p>\n<pre><code class=\"language-python\">    def get_parent_index(self,index):\n        #\u8fd4\u56de\u7236\u8282\u70b9\u7684\u4e0b\u6807\n        if index == 0 or index &amp;gt; len(self.data_list) -1:\n            return None\n        else:\n            return (index -1) &amp;gt;&amp;gt; 1<\/code><\/pre>\n<p><strong>3. \u6dfb\u52a0 swap \u51fd\u6570<\/strong><\/p>\n<pre><code class=\"language-python\">def swap(self,index_a,index_b):\n        #\u4ea4\u6362\u6570\u7ec4\u4e2d\u7684\u4e24\u4e2a\u5143\u7d20\n        self.data_list[index_a],self.data_list[index_b] = self.data_list[index_b],self.data_list[index_a]<\/code><\/pre>\n<p><strong>4. \u6dfb\u52a0 insert \u51fd\u6570<\/strong><\/p>\n<pre><code class=\"language-python\">def insert(self,data):\n        #\u5148\u628a\u5143\u7d20\u653e\u5728\u6700\u540e\uff0c\u7136\u540e\u4ece\u540e\u5f80\u524d\u4f9d\u6b21\u5806\u5316\n        #\u8fd9\u91cc\u4ee5\u5927\u9876\u5806\u4e3a\u4f8b\uff0c\u5982\u679c\u63d2\u5165\u5143\u7d20\u6bd4\u7236\u8282\u70b9\u5927\uff0c\u5219\u4ea4\u6362\uff0c\u76f4\u5230\u6700\u540e\n        self.data_list.append(data)\n        index = len(self.data_list) -1\n        parent = self.get_parent_index(index)\n        #\u5faa\u73af\uff0c\u76f4\u5230\u8be5\u5143\u7d20\u6210\u4e3a\u5806\u9876\uff0c\u6216\u5c0f\u4e8e\u7236\u8282\u70b9\uff08\u5bf9\u4e8e\u5927\u9876\u5806)\n        while parent is not None and self.data_list[parent] &amp;lt; self.data_list[index]:\n            #\u4ea4\u6362\u64cd\u4f5c\n            self.swap(parent,index)\n            index = parent\n            parent = self.get_parent_index(parent)<\/code><\/pre>\n<p><strong>5. \u6dfb\u52a0 removeMax \u51fd\u6570<\/strong><\/p>\n<pre><code class=\"language-python\">    def removeMax(self):\n        #\u5220\u9664\u5806\u9876\u5143\u7d20\uff0c\u7136\u540e\u5c06\u6700\u540e\u4e00\u4e2a\u5143\u7d20\u653e\u5728\u5806\u9876\uff0c\u518d\u4ece\u4e0a\u5f80\u4e0b\u4f9d\u6b21\u5806\u5316\n        remove_data = self.data_list[0]\n        self.data_list[0] = self.data_list[-1]\n        del self.data_list[-1]\n\n        #\u5806\u5316\n        self.heapify(0)\n        return remove_data<\/code><\/pre>\n<p><strong>6. \u6dfb\u52a0 heapify \u51fd\u6570<\/strong><\/p>\n<pre><code class=\"language-python\">    def heapify(self,index):\n        #\u4ece\u4e0a\u5f80\u4e0b\u5806\u5316\uff0c\u4eceindex \u5f00\u59cb\u5806\u5316\u64cd\u4f5c (\u5927\u9876\u5806)\n        total_index = len(self.data_list) -1\n        while True:\n            maxvalue_index = index\n            if 2*index +1 &amp;lt;=  total_index and self.data_list[2*index +1] &amp;gt; self.data_list[maxvalue_index]:\n                maxvalue_index = 2*index +1\n            if 2*index +2 &amp;lt;=  total_index and self.data_list[2*index +2] &amp;gt; self.data_list[maxvalue_index]:\n                maxvalue_index = 2*index +2\n            if maxvalue_index == index:\n                break\n            self.swap(index,maxvalue_index)\n            index = maxvalue_index<\/code><\/pre>\n<h4>\u793a\u4f8b<\/h4>\n<p>\u8bf7\u5c06 \u5143\u7d20 1-10 \u653e\u8fdb\u5806\uff0c\u5e76\u5c55\u793a\u5efa\u5806\u60c5\u51b5\uff0c\u53ca\u5220\u9664\u5806\u9876\u5143\u7d20\u60c5\u51b5<\/p>\n<p>\u5b9e\u4f8b\u5982\u4e0b\uff1a<\/p>\n<p>\u5efa\u5806: [10, 9, 6, 7, 8, 2, 5, 1, 4, 3]<\/p>\n<p>\u5220\u9664\u5806\u9876\u5143\u7d20\uff1a [10, 9, 8, 7, 6, 5, 4, 3, 2, 1]<\/p>\n<pre><code class=\"language-python\">class heap(object):\n\n    def __init__(self):\n        #\u521d\u59cb\u5316\u4e00\u4e2a\u7a7a\u5806\uff0c\u4f7f\u7528\u6570\u7ec4\u6765\u5728\u5b58\u653e\u5806\u5143\u7d20\uff0c\u8282\u7701\u5b58\u50a8\n        self.data_list = []\n\n    def get_parent_index(self,index):\n        #\u8fd4\u56de\u7236\u8282\u70b9\u7684\u4e0b\u6807\n        if index == 0 or index &amp;gt; len(self.data_list) -1:\n            return None\n        else:\n            return (index -1) &amp;gt;&amp;gt; 1\n\n    def swap(self,index_a,index_b):\n        #\u4ea4\u6362\u6570\u7ec4\u4e2d\u7684\u4e24\u4e2a\u5143\u7d20\n        self.data_list[index_a],self.data_list[index_b] = self.data_list[index_b],self.data_list[index_a]\n\n    def insert(self,data):\n        #\u5148\u628a\u5143\u7d20\u653e\u5728\u6700\u540e\uff0c\u7136\u540e\u4ece\u540e\u5f80\u524d\u4f9d\u6b21\u5806\u5316\n        #\u8fd9\u91cc\u4ee5\u5927\u9876\u5806\u4e3a\u4f8b\uff0c\u5982\u679c\u63d2\u5165\u5143\u7d20\u6bd4\u7236\u8282\u70b9\u5927\uff0c\u5219\u4ea4\u6362\uff0c\u76f4\u5230\u6700\u540e\n        self.data_list.append(data)\n        index = len(self.data_list) -1\n        parent = self.get_parent_index(index)\n        #\u5faa\u73af\uff0c\u76f4\u5230\u8be5\u5143\u7d20\u6210\u4e3a\u5806\u9876\uff0c\u6216\u5c0f\u4e8e\u7236\u8282\u70b9\uff08\u5bf9\u4e8e\u5927\u9876\u5806)\n        while parent is not None and self.data_list[parent] &amp;lt; self.data_list[index]:\n            #\u4ea4\u6362\u64cd\u4f5c\n            self.swap(parent,index)\n            index = parent\n            parent = self.get_parent_index(parent)\n\n    def removeMax(self):\n        #\u5220\u9664\u5806\u9876\u5143\u7d20\uff0c\u7136\u540e\u5c06\u6700\u540e\u4e00\u4e2a\u5143\u7d20\u653e\u5728\u5806\u9876\uff0c\u518d\u4ece\u4e0a\u5f80\u4e0b\u4f9d\u6b21\u5806\u5316\n        remove_data = self.data_list[0]\n        self.data_list[0] = self.data_list[-1]\n        del self.data_list[-1]\n\n        #\u5806\u5316\n        self.heapify(0)\n        return remove_data\n\n    def heapify(self,index):\n        #\u4ece\u4e0a\u5f80\u4e0b\u5806\u5316\uff0c\u4eceindex \u5f00\u59cb\u5806\u5316\u64cd\u4f5c (\u5927\u9876\u5806)\n        total_index = len(self.data_list) -1\n        while True:\n            maxvalue_index = index\n            if 2*index +1 &amp;lt;=  total_index and self.data_list[2*index +1] &amp;gt; self.data_list[maxvalue_index]:\n                maxvalue_index = 2*index +1\n            if 2*index +2 &amp;lt;=  total_index and self.data_list[2*index +2] &amp;gt; self.data_list[maxvalue_index]:\n                maxvalue_index = 2*index +2\n            if maxvalue_index == index:\n                break\n            self.swap(index,maxvalue_index)\n            index = maxvalue_index\n\nif __name__ == &amp;quot;__main__&amp;quot;:\n    myheap = heap()\n    for i in range(10):\n        myheap.insert(i+1)\n    print(&amp;#039;\u5efa\u5806:&amp;#039;,myheap.data_list)\n    print(&amp;quot;\u5220\u9664\u5806\u9876\u5143\u7d20\uff1a&amp;quot;, [myheap.removeMax() for _ in range(10)])<\/code><\/pre>\n<h3>\u56fe<\/h3>\n<p>\u4e0b\u9762\u5c31\u901a\u8fc7\u4e00\u4e2a\u4f8b\u5b50\u6765\u8ba9\u5927\u5bb6\u5feb\u901f\u5730\u77e5\u9053\u4ec0\u4e48\u662f\u56fe\uff0c\u5982\u4e0b\u56fe\u6240\u793a\uff0cG1 \u662f<strong>\u6709\u5411\u56fe<\/strong>\uff0cG2 \u662f<strong>\u65e0\u5411\u56fe<\/strong>\uff0c\u6bcf\u4e2a\u6570\u636e\u5143\u7d20\u79f0\u4e3a<strong>\u9876\u70b9<\/strong>\uff0c\u5728\u6709\u5411\u56fe\u4e2d\uff0c\u4ece V1 \u5230 V3 \u79f0\u4e3a\u4e00\u6761<strong>\u5f27<\/strong>\uff0cV3 \u5230 V1 \u4e3a\u53e6\u4e00\u6761\u5f27\uff0cV1 \u79f0\u4e3a<strong>\u5f27\u5c3e<\/strong>\uff0cV3 \u79f0\u4e3a<strong>\u5f27\u5934<\/strong>\uff0c\u5728\u65e0\u5411\u56fe\u4e2d\uff0c\u4ece V1 \u5230 V3 \u79f0\u4e3a\u4e00\u6761<strong>\u8fb9<\/strong>\u3002<\/p>\n<p><img decoding=\"async\" src=\"https:\/\/kanghaov-img-1256185664.file.myqcloud.com\/2019\/07\/30\/5d406043852b7.png\" alt=\"wm.png\" \/><\/p>\n<p>\u6709 n \u4e2a\u9876\u70b9\uff0c$$1\/2n(n-1)$$\u6761\u8fb9\u7684\u65e0\u5411\u56fe\u79f0\u4e3a<strong>\u5b8c\u5168\u56fe<\/strong>\uff0c\u6709 $$n*(n-1)$$\u6761\u5f27\u6709\u5411\u56fe\u79f0\u4e3a<strong>\u6709\u5411\u5b8c\u5168\u56fe<\/strong>\uff0c\u6709\u5f88\u5c11\u6761\u8fb9\u6216\u56fe\u79f0\u4e3a<strong>\u7a00\u758f\u56fe<\/strong>\uff0c\u53cd\u4e4b\u79f0\u4e3a<strong>\u7a20\u5bc6\u56fe<\/strong>\u3002\u5728 G2 \u65e0\u5411\u56fe\u4e2d\uff0c\u7c7b\u4f3c V3 \u4e0e V1\u3001V2 \u548c V4 \u4e4b\u95f4\u6709\u8fb9\u7684\u4e92\u79f0\u4e3a<strong>\u90bb\u63a5\u70b9<\/strong>\uff0c\u4e0e\u9876\u70b9\u76f8\u5173\u8054\u7684\u8fb9\u6570\u79f0\u4e3a\u9876\u70b9\u7684<strong>\u5ea6<\/strong>\uff0c\u4f8b\u5982 V3 \u9876\u70b9\u7684\u5ea6\u4e3a 3\uff0c\u800c\u5728 G1 \u6709\u5411\u56fe\u4e2d\uff0c\u9876\u70b9\u7684<strong>\u5ea6<\/strong>\u662f\u9876\u70b9\u7684\u51fa\u5ea6\u548c\u5165\u5ea6\u4e4b\u548c\uff0c\u4ee5\u9876\u70b9\u4e3a\u5934\u7684\u5f27\u7684\u6570\u76ee\u79f0\u4e3a<strong>\u5165\u5ea6<\/strong>\uff0c\u4e3a\u5c3e\u7684\u5f27\u7684\u6570\u76ee\u79f0\u4e3a<strong>\u51fa\u5ea6<\/strong>\uff0c\u4f8b\u5982 V1 \u9876\u70b9\u7684\u51fa\u5ea6\u4e3a 2\uff0c\u5165\u5ea6\u4e3a 1\uff0c\u5b83\u7684\u5ea6\u4e3a 1+2=3\u3002<\/p>\n<p>\u4ece\u4e00\u4e2a\u9876\u70b9\u5230\u53e6\u4e00\u4e2a\u9876\u70b9\u7684\u9876\u70b9\u5e8f\u5217\u79f0\u4e3a<strong>\u8def\u5f84<\/strong>\uff0c\u5728\u6709\u5411\u56fe\u4e2d\uff0c\u8def\u5f84\u662f\u6709\u65b9\u5411\u7684\uff0c\u8def\u5f84\u4e0a\u8fb9\u6216\u5f27\u7684\u6570\u76ee\u79f0\u4e3a\u8def\u5f84\u7684\u957f\u5ea6\uff0c\u5982\u679c\u4e00\u6761\u8def\u5f84\u4e2d\u7684\u8d77\u59cb\u9876\u70b9\u8ddf\u7ed3\u675f\u7ed3\u70b9\u76f8\u540c\uff0c\u90a3\u4e48\u79f0\u8fd9\u4e2a\u8def\u5f84\u4e3a<strong>\u73af\u6216\u56de\u8def<\/strong>\uff0c\u4e0d\u51fa\u73b0\u91cd\u590d\u9876\u70b9\u7684\u8def\u5f84\u79f0\u4e3a<strong>\u7b80\u5355\u8def\u5f84<\/strong>\u3002\u65e0\u5411\u56fe\u4e2d\uff0c\u5982\u679c\u4e00\u4e2a\u9876\u70b9\u5230\u53e6\u4e00\u4e2a\u9876\u70b9\u6709\u8def\u5f84\uff0c\u90a3\u4e48\u5b83\u4eec\u5c31\u662f<strong>\u8fde\u901a\u7684<\/strong>\uff0c\u5982\u679c\u56fe\u4e2d\u7684\u4efb\u610f\u4e24\u4e2a\u9876\u70b9\u90fd\u662f\u8fde\u901a\u7684\uff0c\u90a3\u4e48\u8fd9\u4e2a\u56fe\u5c31\u662f<strong>\u8fde\u901a\u56fe<\/strong>\uff0c\u65e0\u5411\u56fe\u4e2d\u7684\u6781\u5927\u8fde\u901a\u5b50\u56fe\u79f0\u4e3a\u8fde\u901a\u5206\u91cf\uff0c\u5982\u679c\u662f\u6709\u5411\u56fe\u4e2d\u7684\u4efb\u610f\u4e00\u5bf9\u9876\u70b9\u90fd\u6709\u8def\u5f84\uff0c\u90a3\u4e48\u8fd9\u4e2a\u56fe\u5c31\u662f<strong>\u5f3a\u8fde\u901a\u56fe<\/strong>\uff0c\u76f8\u5e94\u7684\u5b83\u7684\u6781\u5927\u8fde\u901a\u5b50\u56fe\u5c31\u79f0\u4e3a<strong>\u5f3a\u8fde\u901a\u5206\u91cf<\/strong>\u3002\u4e00\u4e2a\u8fde\u901a\u56fe\u7684\u4e00\u4e2a\u6781\u5c0f\u8fde\u901a\u5b50\u56fe\uff0c\u5b83\u5305\u542b\u6240\u6709\u9876\u70b9\uff0c\u4f46\u8db3\u4ee5\u6784\u6210\u4e00\u68f5\u6811\u7684 n-1 \u6761\u8fb9\uff0c\u52a0\u4e00\u6761\u8fb9\u5fc5\u5b9a\u4f1a\u5f62\u6210\u73af\uff0c\u8fd9\u4e2a\u5c31\u79f0\u4e3a<strong>\u751f\u6210\u6811<\/strong>\u3002<\/p>\n<h4>\u6982\u5ff5\u4ecb\u7ecd<\/h4>\n<ul>\n<li><strong>\u65e0\u5411\u56fe<\/strong> \u56fe\u662f\u82e5\u5e72\u4e2a\u9876\u70b9(Vertices)\u548c\u8fb9(Edges)\u76f8\u4e92\u8fde\u63a5\u7ec4\u6210\u7684\u3002\u8fb9\u4ec5\u7531\u4e24\u4e2a\u9876\u70b9\u8fde\u63a5\uff0c\u5e76\u4e14\u6ca1\u6709\u65b9\u5411\u7684\u56fe\u79f0\u4e3a\u65e0\u5411\u56fe\u3002<\/li>\n<li><strong>\u6709\u5411\u56fe<\/strong> \u5728\u6709\u5411\u56fe\u4e2d\uff0c\u8fb9\u662f\u5355\u5411\u7684\uff1a\u6bcf\u6761\u8fb9\u8fde\u63a5\u7684\u4e24\u4e2a\u9876\u70b9\u90fd\u662f\u4e00\u4e2a\u6709\u5e8f\u5bf9\uff0c\u5b83\u4eec\u7684\u90bb\u63a5\u6027\u662f\u5355\u5411\u7684\u3002\u6211\u4eec\u5f00\u53d1\u8fc7\u7a0b\u4e2d\u78b0\u5230\u7684\u5f88\u591a\u573a\u666f\u90fd\u662f\u6709\u5411\u56fe\uff1a\u6bd4\u5982\u4efb\u52a1\u8c03\u5ea6\u7684\u4f9d\u8d56\u5173\u7cfb\uff0c\u793e\u4ea4\u7f51\u7edc\u7684\u4efb\u52a1\u5173\u7cfb\u7b49\u7b49\u90fd\u662f\u5929\u7136\u7684\u6709\u5411\u56fe\u3002<\/li>\n<li><strong>\u5ea6<\/strong> \u4e00\u4e2a\u9876\u70b9\u7684\u5ea6\u662f\u6307\u4e0e\u8be5\u9876\u70b9\u76f8\u5173\u8054\u7684\u8fb9\u7684\u6761\u6570\uff0c\u9876\u70b9 v \u7684\u5ea6\u8bb0\u4f5c d(v)\u3002<\/li>\n<\/ul>\n<p>\u8868\u793a\u56fe\u901a\u5e38\u6709\u56db\u79cd\u65b9\u6cd5\uff1a<\/p>\n<ul>\n<li>\n<p>\u6570\u7ec4\u8868\u793a\u6cd5\u3001<\/p>\n<\/li>\n<li>\n<p>\u90bb\u63a5\u8868\u3001<\/p>\n<\/li>\n<li>\n<p>\u5341\u5b57\u94fe\u8868<\/p>\n<\/li>\n<li>\n<p>\u90bb\u63a5\u591a\u91cd\u8868\u3002<\/p>\n<p>\u90bb\u63a5\u8868\u662f\u56fe\u7684\u4e00\u79cd\u94fe\u5f0f\u5b58\u50a8\u7ed3\u6784\uff0c\u5341\u5b57\u94fe\u8868\u662f\u6709\u5411\u56fe\u7684\u53e6\u4e00\u79cd\u94fe\u5f0f\u5b58\u50a8\u7ed3\u6784\uff0c\u90bb\u63a5\u591a\u91cd\u8868\u662f\u65e0\u5411\u56fe\u7684\u53e6\u4e00\u79cd\u94fe\u5f0f\u5b58\u50a8\u7ed3\u6784\u3002\u8fd9\u91cc\u4e3b\u8981\u8bb2\u89e3\u4e00\u4e0b\u90bb\u63a5\u8868\u7684\u8868\u793a\u548c\u5b9e\u73b0\uff0c\u90bb\u63a5\u8868\u4e2d\u6709\u4e24\u79cd\u7ed3\u70b9\uff0c\u4e00\u79cd\u662f\u5934\u7ed3\u70b9\uff0c\u53e6\u4e00\u79cd\u662f\u8868\u7ed3\u70b9\uff0c\u5934\u7ed3\u70b9\u4e2d\u5b58\u50a8\u4e00\u4e2a\u9876\u70b9\u7684\u6570\u636e\u548c\u6307\u5411\u94fe\u8868\u4e2d\u7b2c\u4e00\u4e2a\u7ed3\u70b9\uff0c\u8868\u7ed3\u70b9\u4e2d\u5b58\u50a8\u5f53\u524d\u9876\u70b9\u5728\u56fe\u4e2d\u7684\u4f4d\u7f6e\u548c\u6307\u5411\u4e0b\u4e00\u6761\u8fb9\u6216\u5f27\u7684\u7ed3\u70b9\uff0c\u8868\u5934\u7ed3\u70b9\u7528\u94fe\u5f0f\u6216\u987a\u5e8f\u7ed3\u6784\u65b9\u5f0f\u5b58\u50a8\uff0c\u5982\u4e0b\u56fe\u6240\u793a\u5c31\u662f\u4e0a\u56fe G2 \u65e0\u5411\u56fe\u7684\u90bb\u63a5\u8868\u8868\u793a\u3002<\/p>\n<\/li>\n<\/ul>\n<p><img decoding=\"async\" src=\"https:\/\/kanghaov-img-1256185664.file.myqcloud.com\/2019\/07\/30\/5d4065fe7444a.png\" alt=\"wm _1_.png\" \/><\/p>\n<p>\u5bf9\u4e8e\u6709\u5411\u56fe\u7684\u90bb\u63a5\u8868\u8868\u793a\u5f62\u5f0f\uff0c\u56fe\u7684\u8fb9\u53ef\u4ee5\u4f7f\u7528\u5b57\u5178\u6570\u636e\u7ed3\u6784\u6765\u8868\u793a\u3002<\/p>\n<p>\u4e0b\u9762\u7ed9\u51fa\u65e0\u5411\u56fe\u7684\u53c2\u8003\u4ee3\u7801(\u5bf9\u4e8e\u6709\u5411\u56fe\uff0c\u8bf7\u81ea\u884c\u4fee\u6539\uff0c\u8fd9\u91cc\u4e0d\u518d\u63d0\u793a)<\/p>\n<pre><code class=\"language-python\">class Graph(object):\n    def __init__(self):\n        self.nodes=[] #\u8868\u793a\u56fe\u7684\u70b9\u96c6\n        self.edge={} #\u8868\u793a\u56fe\u7684\u8fb9\u96c6\n    def insert(self,a,b):\n        if not(a in self.nodes): #\u5982\u679ca \u4e0d\u5728\u56fe\u7684\u70b9\u96c6\u91cc\uff0c\u5219\u6dfb\u52a0a\n            self.nodes.append(a)\n            self.edge[a]=list()\n        if not(b in self.nodes): #\u5982\u679cb \u4e0d\u5728\u56fe\u7684\u70b9\u96c6\u91cc\uff0c\u5219\u6dfb\u52a0b\n            self.nodes.append(b)\n            self.edge[b]=list()\n        self.edge[a].append(b) #a\u8fde\u63a5b\n        self.edge[b].append(a) #b\u8fde\u63a5a\n    def succ(self,a):\n        return self.edge[a] #\u8fd4\u56de\u4e0ea\u8fde\u63a5\u7684\u70b9\n    def show_nodes(self): #\u8fd4\u56de\u56fe\u7684\u70b9\u96c6\n        return self.nodes\n    def show_edge(self):\n        print( self.edge)\ngraph = Graph()\ngraph.insert(&amp;#039;0&amp;#039;,&amp;#039;1&amp;#039;)\ngraph.insert(&amp;#039;0&amp;#039;,&amp;#039;2&amp;#039;)\ngraph.insert(&amp;#039;0&amp;#039;,&amp;#039;3&amp;#039;)\ngraph.insert(&amp;#039;1&amp;#039;,&amp;#039;3&amp;#039;)\ngraph.insert(&amp;#039;2&amp;#039;,&amp;#039;3&amp;#039;)\ngraph.show_edge()<\/code><\/pre>\n<p>\u8be5 graph \u50a8\u5b58\u5f62\u5f0f\u4e3a\uff1a<\/p>\n<p>{&#8216;0&#8217;: [&#8216;1&#8217;, &#8216;2&#8217;, &#8216;3&#8217;], &#8216;1&#8217;: [&#8216;0&#8217;, &#8216;3&#8217;], &#8216;2&#8217;: [&#8216;0&#8217;, &#8216;3&#8217;], &#8216;3&#8217;: [&#8216;0&#8217;, &#8216;1&#8217;, &#8216;2&#8217;]}<\/p>\n<p><img decoding=\"async\" src=\"https:\/\/kanghaov-img-1256185664.file.myqcloud.com\/2019\/07\/31\/5d40fbad1becc.jpg\" alt=\"wm.jpg\" \/><\/p>\n<p>\u90bb\u63a5\u77e9\u9635\u8868\u793a\u6cd5\uff0c\u7528\u4e24\u4e2a\u6570\u7ec4\u8868\u793a\uff0c\u4e00\u4e2a\u4e00\u7ef4\u6570\u7ec4\u548c\u4e00\u4e2a\u4e8c\u7ef4\u6570\u7ec4\u3002<\/p>\n<p>\u4e00\u7ef4\u6570\u7ec4\u5b58\u50a8\u8282\u70b9\u4fe1\u606f\uff0c\u4e8c\u7ef4\u6570\u7ec4\u5b58\u50a8\u8282\u70b9\u4e4b\u95f4\u7684\u5173\u7cfb\u3002<\/p>\n<p>\u901a\u5e38\u56fe\u7684\u904d\u5386\u6709\u4e24\u79cd\uff1a\u6df1\u5ea6\u4f18\u5148\u641c\u7d22\u548c\u5e7f\u5ea6\u4f18\u5148\u641c\u7d22\u3002<\/p>\n<h4>\u6df1\u5ea6\u4f18\u5148\u641c\u7d22<\/h4>\n<p>\u6df1\u5ea6\u4f18\u5148\u641c\u7d22(DFS) \u662f\u6811\u7684\u5148\u6839\u904d\u5386\u7684\u63a8\u5e7f\uff0c\u5b83\u7684\u57fa\u672c\u601d\u60f3\u662f\uff1a<\/p>\n<p>\u4ece\u6839\u8282\u70b9\u51fa\u53d1\uff0c\u6cbf\u7740\u5de6\u5b50\u6811\u65b9\u5411\u8fdb\u884c\u7eb5\u5411\u904d\u5386\uff0c\u76f4\u5230\u627e\u5230\u53f6\u5b50\u8282\u70b9\u4e3a\u6b62\u3002\u7136\u540e\u56de\u6eaf\u5230\u524d\u4e00\u4e2a\u8282\u70b9\uff0c\u8fdb\u884c\u53f3\u5b50\u6811\u8282\u70b9\u7684\u904d\u5386\uff0c\u76f4\u5230\u904d\u5386\u5b8c\u6240\u6709\u53ef\u8fbe\u8282\u70b9\u4e3a\u6b62\u3002<\/p>\n<p>\u6f14\u793a\uff1a\u4ece\u7ed9\u5b9a\u56fe\u4e2d\uff0c\u5b9e\u73b0 DFS<\/p>\n<p>\u53c2\u8003\u4ee3\u7801\u5982\u4e0b\uff1a<\/p>\n<pre><code class=\"language-python\">def dfs(G,s,S=None,res=None):\n    if S is None:\n        # \u50a8\u5b58\u5df2\u7ecf\u8bbf\u95ee\u8282\u70b9\n        S=set()\n    if res is None:\n        # \u5b58\u50a8\u904d\u5386\u987a\u5e8f\n        res=[]\n    res.append(s)\n    S.add(s)\n    for u in G[s]:\n        if u in S:\n            continue\n        S.add(u)\n        dfs(G,u,S,res)\n\n    return res\n\nG = {&amp;#039;0&amp;#039;: [&amp;#039;1&amp;#039;, &amp;#039;2&amp;#039;],\n     &amp;#039;1&amp;#039;: [&amp;#039;2&amp;#039;, &amp;#039;3&amp;#039;],\n     &amp;#039;2&amp;#039;: [&amp;#039;3&amp;#039;, &amp;#039;5&amp;#039;],\n     &amp;#039;3&amp;#039;: [&amp;#039;4&amp;#039;],\n     &amp;#039;4&amp;#039;: [],\n     &amp;#039;5&amp;#039;: []}\n\nprint(dfs(G, &amp;#039;0&amp;#039;))<\/code><\/pre>\n<pre><code class=\"language-python\">[&amp;#039;0&amp;#039;, &amp;#039;1&amp;#039;, &amp;#039;2&amp;#039;, &amp;#039;3&amp;#039;, &amp;#039;4&amp;#039;, &amp;#039;5&amp;#039;]<\/code><\/pre>\n<p>\u6548\u679c\u5982\u4e0b\uff1a<\/p>\n<p><img decoding=\"async\" src=\"https:\/\/kanghaov-img-1256185664.file.myqcloud.com\/2019\/07\/31\/5d4100ffa8592.gif\" alt=\"wm.gif\" \/><\/p>\n<h4>\u5e7f\u5ea6\u4f18\u5148\u641c\u7d22<\/h4>\n<p>\u5e7f\u5ea6\u4f18\u5148\u641c\u7d22(BFS)\u662f\u6811\u7684\u6309\u5c42\u6b21\u904d\u5386\u7684\u63a8\u5e7f\uff0c\u5b83\u7684\u57fa\u672c\u601d\u60f3\u662f\uff1a<\/p>\n<p>\u9996\u5148\u8bbf\u95ee\u521d\u59cb\u70b9 vi\uff0c\u5e76\u5c06\u5176\u6807\u8bb0\u4e3a\u5df2\u8bbf\u95ee\u8fc7\uff0c\u63a5\u7740\u8bbf\u95ee vi \u7684\u6240\u6709\u672a\u88ab\u8bbf\u95ee\u8fc7\u7684\u90bb\u63a5\u70b9 vi1,vi2,&#8230;, vin\uff0c\u5e76\u5747\u6807\u8bb0\u5df2\u8bbf\u95ee\u8fc7\uff0c\u7136\u540e\u518d\u6309\u7167 vi1,vi2,&#8230;, vin \u7684\u6b21\u5e8f\uff0c\u8bbf\u95ee\u6bcf\u4e00\u4e2a\u9876\u70b9\u7684\u6240\u6709\u672a\u88ab\u8bbf\u95ee\u8fc7\u7684\u90bb\u63a5\u70b9\uff0c\u5e76\u5747\u6807\u8bb0\u4e3a\u5df2\u8bbf\u95ee\u8fc7\uff0c\u4f9d\u6b21\u7c7b\u63a8\uff0c\u76f4\u5230\u56fe\u4e2d\u6240\u6709\u548c\u521d\u59cb\u70b9 vi \u6709\u8def\u5f84\u76f8\u901a\u7684\u9876\u70b9\u90fd\u88ab\u8bbf\u95ee\u8fc7\u4e3a\u6b62\u3002<\/p>\n<p>\u6f14\u793a\uff1a\u4ece\u7ed9\u5b9a\u56fe\u4e2d\uff0c\u5b9e\u73b0 BFS<\/p>\n<p>\u53c2\u8003\u4ee3\u7801\u5982\u4e0b\uff1a<\/p>\n<pre><code class=\"language-python\">def bfs(graph, start):\n    explored, queue = [], [start]  #explored\uff1a\u5df2\u7ecf\u904d\u5386\u7684\u8282\u70b9\u5217\u8868\uff0cqueue:\u5bfb\u627e\u5f85\u904d\u5386\u7684\u8282\u70b9\u961f\u5217\n    explored.append(start)\n    while queue:\n        v = queue.pop(0) #v:\u5c06\u8981\u904d\u5386\u7684\u67d0\u8282\u70b9\n        for w in graph[v]: #w:\u8282\u70b9v\u7684\u90bb\u5c45\n            if w not in explored: #w:\u5982\u679cw\u672a\u88ab\u904d\u5386\uff0c\u5219\u904d\u5386\n                explored.append(w) #\u6dfb\u52a0w\u8282\u70b9\u5230\u5df2\u904d\u5386\u7684\u8282\u70b9\u5217\u8868\n                queue.append(w) #\u6dfb\u52a0w\u8282\u70b9\u5230\u5bfb\u627e\u5f85\u904d\u5386\u7684\u8282\u70b9\u961f\u5217\n    return explored\n\nG = {&amp;#039;0&amp;#039;: [&amp;#039;1&amp;#039;, &amp;#039;2&amp;#039;],\n     &amp;#039;1&amp;#039;: [&amp;#039;2&amp;#039;, &amp;#039;3&amp;#039;],\n     &amp;#039;2&amp;#039;: [&amp;#039;3&amp;#039;, &amp;#039;5&amp;#039;],\n     &amp;#039;3&amp;#039;: [&amp;#039;4&amp;#039;],\n     &amp;#039;4&amp;#039;: [],\n     &amp;#039;5&amp;#039;: []}\n\nprint(bfs(G, &amp;#039;0&amp;#039;))<\/code><\/pre>\n<p>\u7ed3\u679c\uff1a<\/p>\n<pre><code class=\"language-python\">[&amp;#039;0&amp;#039;, &amp;#039;1&amp;#039;, &amp;#039;2&amp;#039;, &amp;#039;3&amp;#039;, &amp;#039;5&amp;#039;, &amp;#039;4&amp;#039;]<\/code><\/pre>\n<p><img decoding=\"async\" src=\"https:\/\/kanghaov-img-1256185664.file.myqcloud.com\/2019\/07\/31\/5d41a037233bb.gif\" alt=\"wm.gif\" \/><\/p>\n<p>\u6700\u77ed\u8def\u5f84\u95ee\u9898\u662f\u56fe\u8bba\u7814\u7a76\u4e2d\u7684\u4e00\u4e2a\u7ecf\u5178\u7b97\u6cd5\u95ee\u9898\uff0c\u65e8\u5728\u5bfb\u627e\u56fe\uff08\u7531\u7ed3\u70b9\u548c\u8def\u5f84\u7ec4\u6210\u7684\uff09\u4e2d\u4e24\u7ed3\u70b9\u4e4b\u95f4\u7684\u6700\u77ed\u8def\u5f84\u3002\u7ed9\u5b9a\u4e00\u4e2a\u56fe\uff0c\u548c\u4e00\u4e2a\u6e90\u9876\u70b9 src\uff0c\u627e\u5230\u4ece src \u5230\u5176\u5b83\u6240\u6709\u6240\u6709\u9876\u70b9\u7684\u6700\u77ed\u8def\u5f84\uff0c\u56fe\u4e2d\u53ef\u80fd\u542b\u6709\u8d1f\u6743\u503c\u7684\u8fb9\u3002\u5728\u8fd9\u91cc\u6211\u4eec\u4ecb\u7ecd\u4e24\u79cd\u5e38\u89c1\u7684\u6c42\u89e3\u6700\u77ed\u8def\u5f84\u95ee\u9898\u7684\u7b97\u6cd5\u3002<\/p>\n<p>Dijkstra \u7684\u7b97\u6cd5\u662f\u4e00\u4e2a\u8d2a\u5a6a\u7b97\u6cd5\uff0c\u65f6\u95f4\u590d\u6742\u5ea6\u662f O(VLogV)(\u4f7f\u7528\u6700\u5c0f\u5806)\u3002\u4f46\u662f\u8fea\u6770\u65af\u7279\u62c9\u7b97\u6cd5\u5728\u6709\u8d1f\u6743\u503c\u8fb9\u7684\u56fe\u4e2d\u4e0d\u9002\u7528\uff0cBellman-Ford \u9002\u5408\u8fd9\u6837\u7684\u56fe\u3002\u5728\u7f51\u7edc\u8def\u7531\u4e2d\uff0c\u8be5\u7b97\u6cd5\u4f1a\u88ab\u7528\u4f5c\u8ddd\u79bb\u5411\u91cf\u8def\u7531\u7b97\u6cd5\u3002<\/p>\n<p>Bellman-Ford \u4e5f\u6bd4\u8fea\u6770\u65af\u7279\u62c9\u7b97\u6cd5\u66f4\u7b80\u5355\u548c\u540c\u65f6\u4e5f\u9002\u7528\u4e8e\u5206\u5e03\u5f0f\u7cfb\u7edf\u3002\u4f46 Bellman-Ford \u7684\u65f6\u95f4\u590d\u6742\u5ea6\u662f O(VE)\uff0c\u8fd9\u8981\u6bd4\u8fea\u6770\u65af\u7279\u62c9\u7b97\u6cd5\u6162\u3002\uff08V \u4e3a\u9876\u70b9\u7684\u4e2a\u6570\uff0cE \u4e3a\u8fb9\u7684\u4e2a\u6570\uff09\u3002<\/p>\n<h4>Dijkstra \u7b97\u6cd5<\/h4>\n<p>Dijkstra \u7b97\u6cd5\u4f7f\u7528\u4e86\u5e7f\u5ea6\u4f18\u5148\u641c\u7d22\u89e3\u51b3\u8d4b\u6743\u6709\u5411\u56fe\u6216\u8005\u65e0\u5411\u56fe\u7684\u5355\u6e90\u6700\u77ed\u8def\u5f84\u95ee\u9898\uff0c\u7b97\u6cd5\u6700\u7ec8\u5f97\u5230\u4e00\u4e2a\u6700\u77ed\u8def\u5f84\u6811\u3002\u8be5\u7b97\u6cd5\u5e38\u7528\u4e8e\u8def\u7531\u7b97\u6cd5\u6216\u8005\u4f5c\u4e3a\u5176\u4ed6\u56fe\u7b97\u6cd5\u7684\u4e00\u4e2a\u5b50\u6a21\u5757\u3002<\/p>\n<p>\u5bf9\u4e0b\u56fe\u8fdb\u884c dijkstra<\/p>\n<p><img decoding=\"async\" src=\"https:\/\/kanghaov-img-1256185664.file.myqcloud.com\/2019\/07\/31\/5d41a15c5a747.jpg\" alt=\"wm.jpg\" \/><\/p>\n<p>\u6ce8\u610f\uff1aDijkstra \u7b97\u6cd5\u4e0d\u80fd\u5904\u7406\u5305\u542b\u8d1f\u8fb9\u7684\u56fe\uff01<\/p>\n<p>\u53c2\u8003\u4ee3\u7801\u5982\u4e0b\uff1a<\/p>\n<pre><code class=\"language-python\">import heapq\ndef dijkstra(graph, start, end):\n    heap = [(0, start)]  # cost from start node,end node\n    visited = []\n    while heap:\n        (cost, u) = heapq.heappop(heap)\n        if u in visited:\n            continue\n        visited.append(u)\n        if u == end:\n            return cost\n        for v, c in G[u]:\n            if v in visited:\n                continue\n            next = cost + c\n            heapq.heappush(heap, (next, v))\n    return (-1, -1)\n\nG = {&amp;#039;0&amp;#039;: [[&amp;#039;1&amp;#039;, 2], [&amp;#039;2&amp;#039;, 5]],\n     &amp;#039;1&amp;#039;: [[&amp;#039;0&amp;#039;, 2], [&amp;#039;3&amp;#039;, 3], [&amp;#039;4&amp;#039;, 1]],\n     &amp;#039;2&amp;#039;: [[&amp;#039;0&amp;#039;, 5], [&amp;#039;5&amp;#039;, 3]],\n     &amp;#039;3&amp;#039;: [[&amp;#039;1&amp;#039;, 3]],\n     &amp;#039;4&amp;#039;: [[&amp;#039;1&amp;#039;, 1], [&amp;#039;5&amp;#039;, 3]],\n     &amp;#039;5&amp;#039;: [[&amp;#039;2&amp;#039;, 3], [&amp;#039;4&amp;#039;, 3]]}\nshortDistance = dijkstra(G, &amp;#039;4&amp;#039;, &amp;#039;2&amp;#039;)\nprint(shortDistance)<\/code><\/pre>\n<p>\u7ed3\u679c\uff1a<\/p>\n<pre><code>6<\/code><\/pre>\n<p>\u6f14\u793a\uff1a\u4ece\u9876\u70b9 4 \u8fdb\u884c dijkstra \u627e\u6700\u77ed\u8def\u5f84<\/p>\n<p><img decoding=\"async\" src=\"https:\/\/kanghaov-img-1256185664.file.myqcloud.com\/2019\/07\/31\/5d41a914e3adf.gif\" alt=\"wm _1_.gif\" \/><\/p>\n<h4>bellman_ford \u7b97\u6cd5<\/h4>\n<p>\u542b\u8d1f\u6743\u8fb9\u7684\u5e26\u6743\u6709\u5411\u56fe\u7684\u5355\u6e90\u6700\u77ed\u8def\u95ee\u9898\u3002\uff08\u4e0d\u80fd\u5904\u7406\u5e26\u8d1f\u6743\u8fb9\u7684\u65e0\u5411\u56fe\uff09\u3002<\/p>\n<p>\u7b97\u6cd5\u4f2a\u7801\u5982\u4e0b\uff1a<\/p>\n<pre><code class=\"language-python\">procedure BellmanFord(list vertices, list edges, vertex source)\n\n   \/\/ \u8be5\u5b9e\u73b0\u8bfb\u5165\u8fb9\u548c\u8282\u70b9\u7684\u5217\u8868\uff0c\u5e76\u5411\u4e24\u4e2a\u6570\u7ec4\uff08distance \u548c predecessor\uff09\u4e2d\u5199\u5165\u6700\u77ed\u8def\u5f84\u4fe1\u606f\n\n   \/\/ \u6b65\u9aa4 1\uff1a\u521d\u59cb\u5316\u56fe\n   for each vertex v in vertices:\n       if v is source then distance[v] := 0\n       else distance[v] := infinity\n       predecessor[v] := null\n\n   \/\/ \u6b65\u9aa4 2\uff1a\u91cd\u590d\u5bf9\u6bcf\u4e00\u6761\u8fb9\u8fdb\u884c\u677e\u5f1b\u64cd\u4f5c\n   for i from 1 to size(vertices)-1:\n       for each edge (u, v) with weight w in edges:\n           if distance[u] + w &amp;lt; distance[v]:\n               distance[v] := distance[u] + w\n               predecessor[v] := u\n\n   \/\/ \u6b65\u9aa4 3\uff1a\u68c0\u67e5\u8d1f\u6743\u73af\n   for each edge (u, v) with weight w in edges:\n       if distance[u] + w &amp;lt; distance[v]:\n           error &amp;quot;\u56fe\u5305\u542b\u4e86\u8d1f\u6743\u73af&amp;quot;<\/code><\/pre>\n<p>\u6f14\u793a\uff1a\u4ece\u9876\u70b9 4 \u8fdb\u884c bellman_ford \u627e\u6700\u77ed\u8def\u5f84<\/p>\n<p><img decoding=\"async\" src=\"https:\/\/kanghaov-img-1256185664.file.myqcloud.com\/2019\/07\/31\/5d41aa5e01218.gif\" alt=\"wm.gif\" \/><\/p>\n<h3>\u5e76\u67e5\u96c6<\/h3>\n<p>\u5e76\u67e5\u96c6\u662f\u4e00\u79cd\u6570\u636e\u7ed3\u6784\uff0c\u7528\u4e8e\u5904\u7406\u5bf9 N \u4e2a\u5143\u7d20\u7684\u96c6\u5408\u5212\u5206\u548c\u5224\u65ad\u662f\u5426\u5c5e\u4e8e\u540c\u96c6\u5408\u7684\u95ee\u9898\u3002\u8ba9\u6bcf\u4e2a\u5143\u7d20\u6784\u6210\u4e00\u4e2a\u5355\u5143\u7d20\u7684\u96c6\u5408\uff0c\u7136\u540e\u6309\u4e00\u5b9a\u987a\u5e8f\u5c06\u5c5e\u4e8e\u540c\u4e00\u7ec4\u7684\u5143\u7d20\u6240\u5728\u7684\u96c6\u5408\u5408\u5e76\uff0c\u5176\u95f4\u8981\u53cd\u590d\u67e5\u627e\u4e00\u4e2a\u5143\u7d20\u5728\u54ea\u4e2a\u96c6\u5408\u4e2d\u3002\u5e76\u67e5\u96c6\u662f\u4e00\u79cd\u6811\u578b\u7684\u6570\u636e\u7ed3\u6784\uff0c\u7528\u4e8e\u5904\u7406\u4e00\u4e9b\u4e0d\u76f8\u4ea4\u96c6\u5408\uff08Disjoint Sets\uff09\u7684\u5408\u5e76\u53ca\u67e5\u8be2\u95ee\u9898\u3002<\/p>\n<p>\u6ce8\uff1a\u5b9a\u4e49\u6765\u81ea\u767e\u5ea6\u767e\u79d1\u3002<\/p>\n<h4>\u5e76\u67e5\u96c6\u7684\u4e3b\u8981\u6027\u8d28<\/h4>\n<p>\u7528\u96c6\u5408\u4e2d\u7684\u67d0\u4e2a\u5143\u7d20\u6765\u4ee3\u8868\u8fd9\u4e2a\u96c6\u5408\uff0c\u8be5\u5143\u7d20\u79f0\u4e3a\u96c6\u5408\u7684\u4ee3\u8868\u5143\u3002\u4e00\u4e2a\u96c6\u5408\u5185\u7684\u6240\u6709\u5143\u7d20\u7ec4\u7ec7\u6210\u4ee5\u4ee3\u8868\u5143\u4e3a\u6839\u7684\u6811\u5f62\u7ed3\u6784\u3002\u5bf9\u4e8e\u6bcf\u4e00\u4e2a\u5143\u7d20 parent[x]\u6307\u5411 x \u5728\u6811\u5f62\u7ed3\u6784\u4e0a\u7684\u7236\u4eb2\u8282\u70b9\u3002\u5982\u679c x \u662f\u6839\u8282\u70b9\uff0c\u5219\u4ee4 parent[x] = x\u3002\u5bf9\u4e8e\u67e5\u627e\u64cd\u4f5c\uff0c\u5047\u8bbe\u9700\u8981\u786e\u5b9a x \u6240\u5728\u7684\u7684\u96c6\u5408\uff0c\u4e5f\u5c31\u662f\u786e\u5b9a\u96c6\u5408\u7684\u4ee3\u8868\u5143\u3002\u53ef\u4ee5\u6cbf\u7740 parent[x]\u4e0d\u65ad\u5728\u6811\u5f62\u7ed3\u6784\u4e2d\u5411\u4e0a\u79fb\u52a8\uff0c\u76f4\u5230\u5230\u8fbe\u6839\u8282\u70b9\u3002\u5224\u65ad\u4e24\u4e2a\u5143\u7d20\u662f\u5426\u5c5e\u4e8e\u540c\u4e00\u96c6\u5408\uff0c\u53ea\u9700\u8981\u770b\u4ed6\u4eec\u7684\u4ee3\u8868\u5143\u662f\u5426\u76f8\u540c\u5373\u53ef\u3002<\/p>\n<h4>\u57fa\u672c\u529f\u80fd\u4ecb\u7ecd<\/h4>\n<p>\u5728\u63a5\u4e0b\u6765\u7684\u5185\u5bb9\u91cc\uff0c\u6211\u4eec\u5c06\u9010\u6b65\u4ecb\u7ecd\u5e76\u67e5\u96c6\u7684\u5177\u4f53\u529f\u80fd\u662f\u5982\u4f55\u5b9e\u73b0\u7684\u3002<\/p>\n<h5><strong>\u521b\u5efa union_find \u7c7b<\/strong><\/h5>\n<p>\u521b\u5efa\u4e00\u4e2a union_find \u7684\u7c7b,\u5e76\u521d\u59cb\u5316\u3002\u521d\u59cb\u5316\u4e24\u4e2a\u5b57\u5178\uff0c\u4e00\u4e2a\u4fdd\u5b58\u8282\u70b9\u7684\u7236\u8282\u70b9\uff0c\u53e6\u5916\u4e00\u4e2a\u4fdd\u5b58\u7236\u8282\u70b9\u7684\u5927\u5c0f\u3002\u521d\u59cb\u5316\u7684\u65f6\u5019\uff0c\u5c06\u8282\u70b9\u7684\u7236\u8282\u70b9\u8bbe\u4e3a\u81ea\u8eab\uff0csize \u8bbe\u4e3a 1\u3002<\/p>\n<h4>\u5e76\u67e5\u96c6\u7684\u5e94\u7528<\/h4>\n<p>1\u3001\u7ef4\u62a4\u65e0\u5411\u56fe\u7684\u8fde\u901a\u6027\u3002\u652f\u6301\u5224\u65ad\u4e24\u4e2a\u70b9\u662f\u5426\u5728\u540c\u4e00\u8fde\u901a\u5757\u5185\uff0c\u548c\u5224\u65ad\u589e\u52a0\u4e00\u6761\u8fb9\u662f\u5426\u4f1a\u4ea7\u751f\u73af\u3002<\/p>\n<p>2\u3001\u7528\u5728\u6c42\u89e3\u6700\u5c0f\u751f\u6210\u6811\u7684 Kruskal \u7b97\u6cd5\u91cc\u3002<\/p>\n<h4>\u793a\u4f8b<\/h4>\n<p>\u6839\u636e\u53c2\u8003\u7684 union_find \uff0c\u5b8c\u6210\u4ee5\u4e0b\u529f\u80fd\u7684\u5b9e\u73b0<\/p>\n<p>\u5728\u4ee3\u7801\u4e2d\u5b9e\u73b0\u8fd9\u4e9b\u6b65\u9aa4\uff1a<\/p>\n<ol>\n<li>\u521d\u59cb a = [1,2,3,4,5],\u5e76\u5c06\u5176\u6dfb\u52a0\u5230\u5e76\u67e5\u96c6\u91cc<\/li>\n<li>\u5206\u522b\u5408\u5e76[1,2] [3,5] [3,1]<\/li>\n<li>\u7136\u540e\u5224\u65ad 2 5 \u662f\u5426\u4e3a\u540c\u4e00\u4e2a\u96c6\u5408<\/li>\n<\/ol>\n<pre><code class=\"language-python\">class union_find(object):\n    def __init__(self, data_list):\n        self.father_dict = {} #\u4fdd\u5b58\u8282\u70b9\u7684\u7236\u8282\u70b9\n        self.size_dict = {} #\u4fdd\u5b58\u7236\u8282\u70b9\u7684\u5927\u5c0f\n        for node in data_list:\n            self.father_dict[node] = node\n            self.size_dict[node] = 1\n    def find(self, node):\n        father = self.father_dict[node]\n        if(node != father): #\u9012\u5f52\u67e5\u627e\u7236\u8282\u70b9\n            father = self.find(father)\n        self.father_dict[node] = father #\u5728\u67e5\u627e\u7236\u8282\u70b9\u7684\u65f6\u5019\uff0c\u987a\u4fbf\u628a\u5f53\u524d\u8282\u70b9\u79fb\u52a8\u5230\u7236\u8282\u70b9\u4e0a\u9762\u8fd9\u4e2a\u64cd\u4f5c\u7b97\u662f\u4e00\u4e2a\u4f18\u5316\n        return father\n    def is_same_set(self, node_a, node_b):\n        return self.find(node_a) == self.find(node_b)\n    def union(self, node_a, node_b):\n        if node_a is None or node_b is None: # \u5bf9\u5408\u5e76\u7684\u4e24\u4e2a\u8282\u70b9\u505a\u521d\u6b65\u5224\u65ad\uff0c\u5224\u65ad\u662f\u5426\u4e3a\u7a7a\n            return\n\n        a_head = self.find(node_a) #\u5206\u522b\u67e5\u627e\u4e24\u4e2a\u8282\u70b9\u7684\u7236\u8282\u70b9\n        b_head = self.find(node_b)\n\n        if(a_head != b_head): #\u5f53\u4e24\u4e2a\u8282\u70b9\u7684\u7236\u8282\u70b9\u4e0d\u4e00\u6837\u65f6\uff0c\u624d\u80fd\u505a\u5408\u5e76\u64cd\u4f5c\n            a_set_size = self.size_dict[a_head]\n            b_set_size = self.size_dict[b_head]\n            if(a_set_size &amp;gt;= b_set_size): #\u6839\u636e\u96c6\u5408\u7684\u5927\u5c0f\u505a\u5224\u65ad\uff0c\u5c3d\u91cf\u4f7f\u5c0f\u96c6\u5408\u5e76\u5230\u5927\u96c6\u5408\n                self.father_dict[b_head] = a_head\n                self.size_dict[a_head] = a_set_size + b_set_size\n            else:\n                self.father_dict[a_head] = b_head\n                self.size_dict[b_head] = a_set_size + b_set_size\nif __name__ == &amp;#039;__main__&amp;#039;:\n    a = [1,2,3,4,5]\n    union_find = union_find(a)\n    union_find.union(1,2)\n    union_find.union(3,5)\n    union_find.union(3,1)\n    print(union_find.is_same_set(2,5))  # True<\/code><\/pre>\n<p>\u7ed3\u679c\uff1a<\/p>\n<pre><code>True<\/code><\/pre>\n<h3>\u603b\u7ed3<\/h3>\n<p>\u7531\u4e8e\u6570\u636e\u7ed3\u6784\u7684\u7c7b\u578b\u53d8\u5316\u5f88\u591a\uff0c\u672c\u8282\u4ec5\u5bf9\u5e38\u89c1\u7684\u975e\u7ebf\u6027\u7ed3\u6784\u505a\u4e86\u7b80\u5355\u8bb2\u89e3\u3002\u56de\u987e\u4e0b\u672c\u8282\u5185\u5bb9\u4e3b\u8981\u5305\u542b\u4e86\u4ee5\u4e0b\u5185\u5bb9\uff1a<\/p>\n<ul>\n<li>\u6811<\/li>\n<li>\u5b57\u5178\u6811<\/li>\n<li>\u5806<\/li>\n<li>\u56fe<\/li>\n<li>\u5e76\u67e5\u96c6<\/li>\n<\/ul>\n<p>\u8bf7\u628a\u6587\u6863\u4e2d\u6240\u6709\u7684\u793a\u4f8b\u4ee3\u7801\u90fd\u624b\u52a8\u5b8c\u6210\u5e76\u8fd0\u884c\u5bf9\u6bd4\u7ed3\u679c\uff0c\u53ea\u6709\u8fd9\u6837\u624d\u80fd\u66f4\u52a0\u719f\u7ec3\u7684\u638c\u63e1\u5bf9\u5e94\u7684\u76f8\u5173\u77e5\u8bc6\u3002<\/p>\n","protected":false},"excerpt":{"rendered":"<p>\u57fa\u7840\u77e5\u8bc6\u70b9 \u6570\u636e\u7ed3\u6784\u7684\u6982\u5ff5 \u6808 \u961f\u5217 \u94fe\u8868 \u6570\u636e\u7ed3\u6784 \u6570\u636e\u7ed3\u6784( data structure )\u662f\u8ba1\u7b97\u673a\u5b58\u50a8\u3001\u7ec4\u7ec7\u6570\u636e\u7684\u65b9\u5f0f\u3002\u6570\u636e\u7ed3\u6784\u662f\u6307\u76f8\u4e92\u4e4b\u95f4\u5b58\u5728\u4e00\u79cd\u6216\u591a\u79cd\u7279\u5b9a\u5173\u7cfb\u7684\u6570\u636e\u5143\u7d20\u7684\u96c6\u5408\u3002\u901a\u5e38\u60c5\u51b5\u4e0b\uff0c\u7cbe\u5fc3\u9009\u62e9\u7684\u6570\u636e\u7ed3\u6784\u53ef\u4ee5\u5e26\u6765\u66f4\u9ad8\u7684\u8fd0\u884c\u6216\u8005\u5b58\u50a8\u6548\u7387\u3002\u6570\u636e\u7ed3\u6784\u5f80\u5f80\u540c\u9ad8\u6548\u7684\u68c0\u7d22\u7b97\u6cd5\u548c\u7d22\u5f15\u6280\u672f\u6709\u5173\u3002 \u5728\u8bb8\u591a\u7c7b\u578b\u7684\u7a0b\u5e8f\u7684\u8bbe\u8ba1\u4e2d\uff0c\u6570\u636e\u7ed3\u6784\u7684\u9009\u62e9\u662f\u4e00\u4e2a\u57fa\u672c\u7684\u8bbe\u8ba1\u8003\u8651\u56e0\u7d20\u3002\u8bb8\u591a\u5927\u578b\u7cfb\u7edf\u7684\u6784\u9020\u7ecf\u9a8c\u8868\u660e\uff0c\u7cfb\u7edf\u5b9e\u73b0\u7684\u56f0\u96be\u7a0b\u5ea6\u548c\u7cfb\u7edf\u6784\u9020\u7684\u8d28\u91cf\u90fd\u4e25\u91cd\u5730\u4f9d\u8d56\u4e8e\u662f\u5426\u9009\u62e9\u4e86\u6700\u4f18\u7684\u6570\u636e\u7ed3\u6784\u3002\u8bb8\u591a\u65f6\u5019\uff0c\u786e\u5b9a\u4e86\u6570\u636e\u7ed3\u6784\u540e\uff0c\u7b97\u6cd5\u5c31\u5bb9\u6613\u5f97\u5230\u4e86\u3002\u6709\u4e9b\u65f6\u5019\u4e8b\u60c5\u4e5f\u4f1a\u53cd\u8fc7\u6765\uff0c\u6211\u4eec\u6839\u636e\u7279\u5b9a\u7b97\u6cd5\u6765\u9009\u62e9\u6570\u636e\u7ed3\u6784\u4e0e\u4e4b\u9002\u5e94\u3002 \u6808 \u6808\uff08stack\uff09\u53c8\u540d\u5806\u6808\uff0c\u5b83\u662f\u4e00\u79cd\u8fd0\u7b97\u53d7\u9650\u7684\u7ebf\u6027\u8868\u3002\u5176\u9650\u5236\u662f\u4ec5\u5141\u8bb8\u5728\u8868\u7684\u4e00\u7aef\u8fdb\u884c\u63d2\u5165\u548c\u5220\u9664\u8fd0\u7b97\u3002 \u6808\u5141\u8bb8\u8fdb\u884c\u63d2\u5165\u548c\u5220\u9664\u64cd\u4f5c\u7684\u4e00\u7aef\u79f0\u4e3a\u6808\u9876(top)\uff0c\u53e6\u4e00\u7aef\u4e3a\u6808\u5e95(bottom)\uff1b\u6808\u5e95\u56fa\u5b9a\uff0c\u800c\u6808\u9876\u6d6e\u52a8\uff1b\u6808\u4e2d\u5143\u7d20\u4e2a\u6570\u4e3a\u96f6\u65f6\u79f0\u4e3a\u7a7a\u6808\u3002\u63d2\u5165\u4e00\u822c\u79f0\u4e3a\u8fdb\u6808\uff08PUSH\uff09\uff0c\u5220\u9664\u5219\u79f0\u4e3a\u9000\u6808\uff08POP\uff09\u3002 \u7531\u4e8e\u5806\u53e0\u6570\u636e\u7ed3\u6784\u53ea\u5141\u8bb8\u5728\u4e00\u7aef\u8fdb\u884c\u64cd\u4f5c\uff0c\u56e0\u800c\u6309\u7167\u540e\u8fdb\u5148\u51fa\uff08LIFO, Last In First Out\uff09\u7684\u539f\u7406\u8fd0\u4f5c\u3002\u6808\u4e5f\u79f0\u4e3a\u540e\u8fdb\u5148\u51fa\u8868\u3002 \u590d\u6742\u5ea6\u5206\u6790 \u6808\u5c5e\u4e8e\u5e38\u89c1\u7684\u4e00\u79cd\u7ebf\u6027\u7ed3\u6784\uff0c\u5bf9\u4e8e\u8fdb\u6808\u548c\u9000\u6808\u800c\u8a00\uff0c\u65f6\u95f4\u590d\u6742\u5ea6\u90fd\u4e3a O(1) \u6808\u7684\u5b9e\u73b0 1. \u521b\u5efa\u4e00\u4e2a Stack \u7684\u7c7b \u5bf9\u6808\u8fdb\u884c\u521d\u59cb\u5316\u53c2\u6570\u8bbe\u8ba1 \u5177\u4f53\u5b9e\u73b0\u4ee3\u7801\u5982\u4e0b\uff1a class Stack(object): def __init__(self, limit=10): self.stack = [] #\u5b58\u653e\u5143\u7d20 self.limit = limit #\u6808\u5bb9\u91cf\u6781\u9650 2. push \u8fdb\u6808 \u538b\u5165 push \uff1a\u5c06\u65b0\u5143\u7d20\u653e\u5728\u6808\u9876 \u5f53\u65b0\u5143\u7d20\u5165\u6808\u65f6\uff0c\u6808\u9876\u4e0a\u79fb\uff0c\u65b0\u5143\u7d20\u653e\u5728\u6808\u9876\u3002 \u5177\u4f53\u5b9e\u73b0\u4ee3\u7801\u5982\u4e0b: def push(self, data): if len(self.stack) [&hellip;]<\/p>\n","protected":false},"author":1,"featured_media":284,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[19,28,2],"tags":[],"class_list":["post-254","post","type-post","status-publish","format-standard","has-post-thumbnail","hentry","category-algorithm","category-basic-concepts","category-py"],"yoast_head":"<!-- This site is optimized with the Yoast SEO plugin v27.4 - https:\/\/yoast.com\/product\/yoast-seo-wordpress\/ -->\n<title>\u591a\u79cd\u6570\u636e\u7ed3\u6784\u7684Python\u5b9e\u73b0\u5f62\u5f0f - Nemo<\/title>\n<meta name=\"robots\" content=\"index, follow, max-snippet:-1, max-image-preview:large, max-video-preview:-1\" \/>\n<link rel=\"canonical\" href=\"https:\/\/nemo.cool\/254.html\" \/>\n<meta property=\"og:locale\" content=\"en_US\" \/>\n<meta property=\"og:type\" content=\"article\" \/>\n<meta property=\"og:title\" content=\"\u591a\u79cd\u6570\u636e\u7ed3\u6784\u7684Python\u5b9e\u73b0\u5f62\u5f0f - Nemo\" \/>\n<meta property=\"og:description\" content=\"\u57fa\u7840\u77e5\u8bc6\u70b9 \u6570\u636e\u7ed3\u6784\u7684\u6982\u5ff5 \u6808 \u961f\u5217 \u94fe\u8868 \u6570\u636e\u7ed3\u6784 \u6570\u636e\u7ed3\u6784( data structure )\u662f\u8ba1\u7b97\u673a\u5b58\u50a8\u3001\u7ec4\u7ec7\u6570\u636e\u7684\u65b9\u5f0f\u3002\u6570\u636e\u7ed3\u6784\u662f\u6307\u76f8\u4e92\u4e4b\u95f4\u5b58\u5728\u4e00\u79cd\u6216\u591a\u79cd\u7279\u5b9a\u5173\u7cfb\u7684\u6570\u636e\u5143\u7d20\u7684\u96c6\u5408\u3002\u901a\u5e38\u60c5\u51b5\u4e0b\uff0c\u7cbe\u5fc3\u9009\u62e9\u7684\u6570\u636e\u7ed3\u6784\u53ef\u4ee5\u5e26\u6765\u66f4\u9ad8\u7684\u8fd0\u884c\u6216\u8005\u5b58\u50a8\u6548\u7387\u3002\u6570\u636e\u7ed3\u6784\u5f80\u5f80\u540c\u9ad8\u6548\u7684\u68c0\u7d22\u7b97\u6cd5\u548c\u7d22\u5f15\u6280\u672f\u6709\u5173\u3002 \u5728\u8bb8\u591a\u7c7b\u578b\u7684\u7a0b\u5e8f\u7684\u8bbe\u8ba1\u4e2d\uff0c\u6570\u636e\u7ed3\u6784\u7684\u9009\u62e9\u662f\u4e00\u4e2a\u57fa\u672c\u7684\u8bbe\u8ba1\u8003\u8651\u56e0\u7d20\u3002\u8bb8\u591a\u5927\u578b\u7cfb\u7edf\u7684\u6784\u9020\u7ecf\u9a8c\u8868\u660e\uff0c\u7cfb\u7edf\u5b9e\u73b0\u7684\u56f0\u96be\u7a0b\u5ea6\u548c\u7cfb\u7edf\u6784\u9020\u7684\u8d28\u91cf\u90fd\u4e25\u91cd\u5730\u4f9d\u8d56\u4e8e\u662f\u5426\u9009\u62e9\u4e86\u6700\u4f18\u7684\u6570\u636e\u7ed3\u6784\u3002\u8bb8\u591a\u65f6\u5019\uff0c\u786e\u5b9a\u4e86\u6570\u636e\u7ed3\u6784\u540e\uff0c\u7b97\u6cd5\u5c31\u5bb9\u6613\u5f97\u5230\u4e86\u3002\u6709\u4e9b\u65f6\u5019\u4e8b\u60c5\u4e5f\u4f1a\u53cd\u8fc7\u6765\uff0c\u6211\u4eec\u6839\u636e\u7279\u5b9a\u7b97\u6cd5\u6765\u9009\u62e9\u6570\u636e\u7ed3\u6784\u4e0e\u4e4b\u9002\u5e94\u3002 \u6808 \u6808\uff08stack\uff09\u53c8\u540d\u5806\u6808\uff0c\u5b83\u662f\u4e00\u79cd\u8fd0\u7b97\u53d7\u9650\u7684\u7ebf\u6027\u8868\u3002\u5176\u9650\u5236\u662f\u4ec5\u5141\u8bb8\u5728\u8868\u7684\u4e00\u7aef\u8fdb\u884c\u63d2\u5165\u548c\u5220\u9664\u8fd0\u7b97\u3002 \u6808\u5141\u8bb8\u8fdb\u884c\u63d2\u5165\u548c\u5220\u9664\u64cd\u4f5c\u7684\u4e00\u7aef\u79f0\u4e3a\u6808\u9876(top)\uff0c\u53e6\u4e00\u7aef\u4e3a\u6808\u5e95(bottom)\uff1b\u6808\u5e95\u56fa\u5b9a\uff0c\u800c\u6808\u9876\u6d6e\u52a8\uff1b\u6808\u4e2d\u5143\u7d20\u4e2a\u6570\u4e3a\u96f6\u65f6\u79f0\u4e3a\u7a7a\u6808\u3002\u63d2\u5165\u4e00\u822c\u79f0\u4e3a\u8fdb\u6808\uff08PUSH\uff09\uff0c\u5220\u9664\u5219\u79f0\u4e3a\u9000\u6808\uff08POP\uff09\u3002 \u7531\u4e8e\u5806\u53e0\u6570\u636e\u7ed3\u6784\u53ea\u5141\u8bb8\u5728\u4e00\u7aef\u8fdb\u884c\u64cd\u4f5c\uff0c\u56e0\u800c\u6309\u7167\u540e\u8fdb\u5148\u51fa\uff08LIFO, Last In First Out\uff09\u7684\u539f\u7406\u8fd0\u4f5c\u3002\u6808\u4e5f\u79f0\u4e3a\u540e\u8fdb\u5148\u51fa\u8868\u3002 \u590d\u6742\u5ea6\u5206\u6790 \u6808\u5c5e\u4e8e\u5e38\u89c1\u7684\u4e00\u79cd\u7ebf\u6027\u7ed3\u6784\uff0c\u5bf9\u4e8e\u8fdb\u6808\u548c\u9000\u6808\u800c\u8a00\uff0c\u65f6\u95f4\u590d\u6742\u5ea6\u90fd\u4e3a O(1) \u6808\u7684\u5b9e\u73b0 1. \u521b\u5efa\u4e00\u4e2a Stack \u7684\u7c7b \u5bf9\u6808\u8fdb\u884c\u521d\u59cb\u5316\u53c2\u6570\u8bbe\u8ba1 \u5177\u4f53\u5b9e\u73b0\u4ee3\u7801\u5982\u4e0b\uff1a class Stack(object): def __init__(self, limit=10): self.stack = [] #\u5b58\u653e\u5143\u7d20 self.limit = limit #\u6808\u5bb9\u91cf\u6781\u9650 2. push \u8fdb\u6808 \u538b\u5165 push \uff1a\u5c06\u65b0\u5143\u7d20\u653e\u5728\u6808\u9876 \u5f53\u65b0\u5143\u7d20\u5165\u6808\u65f6\uff0c\u6808\u9876\u4e0a\u79fb\uff0c\u65b0\u5143\u7d20\u653e\u5728\u6808\u9876\u3002 \u5177\u4f53\u5b9e\u73b0\u4ee3\u7801\u5982\u4e0b: def push(self, data): if len(self.stack) [&hellip;]\" \/>\n<meta property=\"og:url\" content=\"https:\/\/nemo.cool\/254.html\" \/>\n<meta property=\"og:site_name\" content=\"Nemo\" \/>\n<meta property=\"article:published_time\" content=\"2019-07-31T16:13:23+00:00\" \/>\n<meta property=\"article:modified_time\" content=\"2020-08-03T09:43:16+00:00\" \/>\n<meta property=\"og:image\" content=\"https:\/\/nemo.cool\/wp-content\/uploads\/2019\/08\/2019-03-27-data_structure.png\" \/>\n\t<meta property=\"og:image:width\" content=\"700\" \/>\n\t<meta property=\"og:image:height\" content=\"350\" \/>\n\t<meta property=\"og:image:type\" content=\"image\/png\" \/>\n<meta name=\"author\" content=\"Nemo\" \/>\n<meta name=\"twitter:card\" content=\"summary_large_image\" \/>\n<meta name=\"twitter:label1\" content=\"Written by\" \/>\n\t<meta name=\"twitter:data1\" content=\"Nemo\" \/>\n\t<meta name=\"twitter:label2\" content=\"Est. reading time\" \/>\n\t<meta name=\"twitter:data2\" content=\"20 minutes\" \/>\n<script type=\"application\/ld+json\" class=\"yoast-schema-graph\">{\"@context\":\"https:\\\/\\\/schema.org\",\"@graph\":[{\"@type\":\"Article\",\"@id\":\"https:\\\/\\\/nemo.cool\\\/254.html#article\",\"isPartOf\":{\"@id\":\"https:\\\/\\\/nemo.cool\\\/254.html\"},\"author\":{\"name\":\"Nemo\",\"@id\":\"https:\\\/\\\/nemo.cool\\\/#\\\/schema\\\/person\\\/698f803ee811e2b140a90f5d5de913d2\"},\"headline\":\"\u591a\u79cd\u6570\u636e\u7ed3\u6784\u7684Python\u5b9e\u73b0\u5f62\u5f0f\",\"datePublished\":\"2019-07-31T16:13:23+00:00\",\"dateModified\":\"2020-08-03T09:43:16+00:00\",\"mainEntityOfPage\":{\"@id\":\"https:\\\/\\\/nemo.cool\\\/254.html\"},\"wordCount\":317,\"commentCount\":4,\"publisher\":{\"@id\":\"https:\\\/\\\/nemo.cool\\\/#\\\/schema\\\/person\\\/698f803ee811e2b140a90f5d5de913d2\"},\"image\":{\"@id\":\"https:\\\/\\\/nemo.cool\\\/254.html#primaryimage\"},\"thumbnailUrl\":\"https:\\\/\\\/nemo.cool\\\/wp-content\\\/uploads\\\/2019\\\/08\\\/2019-03-27-data_structure.png\",\"articleSection\":[\"Algorithm Notes\",\"Basic Concepts\",\"Python\"],\"inLanguage\":\"en-US\",\"potentialAction\":[{\"@type\":\"CommentAction\",\"name\":\"Comment\",\"target\":[\"https:\\\/\\\/nemo.cool\\\/254.html#respond\"]}]},{\"@type\":\"WebPage\",\"@id\":\"https:\\\/\\\/nemo.cool\\\/254.html\",\"url\":\"https:\\\/\\\/nemo.cool\\\/254.html\",\"name\":\"\u591a\u79cd\u6570\u636e\u7ed3\u6784\u7684Python\u5b9e\u73b0\u5f62\u5f0f - Nemo\",\"isPartOf\":{\"@id\":\"https:\\\/\\\/nemo.cool\\\/#website\"},\"primaryImageOfPage\":{\"@id\":\"https:\\\/\\\/nemo.cool\\\/254.html#primaryimage\"},\"image\":{\"@id\":\"https:\\\/\\\/nemo.cool\\\/254.html#primaryimage\"},\"thumbnailUrl\":\"https:\\\/\\\/nemo.cool\\\/wp-content\\\/uploads\\\/2019\\\/08\\\/2019-03-27-data_structure.png\",\"datePublished\":\"2019-07-31T16:13:23+00:00\",\"dateModified\":\"2020-08-03T09:43:16+00:00\",\"breadcrumb\":{\"@id\":\"https:\\\/\\\/nemo.cool\\\/254.html#breadcrumb\"},\"inLanguage\":\"en-US\",\"potentialAction\":[{\"@type\":\"ReadAction\",\"target\":[\"https:\\\/\\\/nemo.cool\\\/254.html\"]}]},{\"@type\":\"ImageObject\",\"inLanguage\":\"en-US\",\"@id\":\"https:\\\/\\\/nemo.cool\\\/254.html#primaryimage\",\"url\":\"https:\\\/\\\/nemo.cool\\\/wp-content\\\/uploads\\\/2019\\\/08\\\/2019-03-27-data_structure.png\",\"contentUrl\":\"https:\\\/\\\/nemo.cool\\\/wp-content\\\/uploads\\\/2019\\\/08\\\/2019-03-27-data_structure.png\",\"width\":700,\"height\":350},{\"@type\":\"BreadcrumbList\",\"@id\":\"https:\\\/\\\/nemo.cool\\\/254.html#breadcrumb\",\"itemListElement\":[{\"@type\":\"ListItem\",\"position\":1,\"name\":\"\u9996\u9875\",\"item\":\"https:\\\/\\\/nemo.cool\\\/\"},{\"@type\":\"ListItem\",\"position\":2,\"name\":\"\u591a\u79cd\u6570\u636e\u7ed3\u6784\u7684Python\u5b9e\u73b0\u5f62\u5f0f\"}]},{\"@type\":\"WebSite\",\"@id\":\"https:\\\/\\\/nemo.cool\\\/#website\",\"url\":\"https:\\\/\\\/nemo.cool\\\/\",\"name\":\"Nemo\",\"description\":\"\",\"publisher\":{\"@id\":\"https:\\\/\\\/nemo.cool\\\/#\\\/schema\\\/person\\\/698f803ee811e2b140a90f5d5de913d2\"},\"potentialAction\":[{\"@type\":\"SearchAction\",\"target\":{\"@type\":\"EntryPoint\",\"urlTemplate\":\"https:\\\/\\\/nemo.cool\\\/?s={search_term_string}\"},\"query-input\":{\"@type\":\"PropertyValueSpecification\",\"valueRequired\":true,\"valueName\":\"search_term_string\"}}],\"inLanguage\":\"en-US\"},{\"@type\":[\"Person\",\"Organization\"],\"@id\":\"https:\\\/\\\/nemo.cool\\\/#\\\/schema\\\/person\\\/698f803ee811e2b140a90f5d5de913d2\",\"name\":\"Nemo\",\"image\":{\"@type\":\"ImageObject\",\"inLanguage\":\"en-US\",\"@id\":\"https:\\\/\\\/nemo.cool\\\/wp-content\\\/uploads\\\/2024\\\/01\\\/Big_Hero_6_Anime_HD_desktop_wallpaper_01_1366x768-e1706020097529-96x96.jpg\",\"url\":\"https:\\\/\\\/nemo.cool\\\/wp-content\\\/uploads\\\/2024\\\/01\\\/Big_Hero_6_Anime_HD_desktop_wallpaper_01_1366x768-e1706020097529-96x96.jpg\",\"contentUrl\":\"https:\\\/\\\/nemo.cool\\\/wp-content\\\/uploads\\\/2024\\\/01\\\/Big_Hero_6_Anime_HD_desktop_wallpaper_01_1366x768-e1706020097529-96x96.jpg\",\"caption\":\"Nemo\"},\"logo\":{\"@id\":\"https:\\\/\\\/nemo.cool\\\/wp-content\\\/uploads\\\/2024\\\/01\\\/Big_Hero_6_Anime_HD_desktop_wallpaper_01_1366x768-e1706020097529-96x96.jpg\"},\"sameAs\":[\"https:\\\/\\\/nemo.cool\"]}]}<\/script>\n<!-- \/ Yoast SEO plugin. -->","yoast_head_json":{"title":"\u591a\u79cd\u6570\u636e\u7ed3\u6784\u7684Python\u5b9e\u73b0\u5f62\u5f0f - Nemo","robots":{"index":"index","follow":"follow","max-snippet":"max-snippet:-1","max-image-preview":"max-image-preview:large","max-video-preview":"max-video-preview:-1"},"canonical":"https:\/\/nemo.cool\/254.html","og_locale":"en_US","og_type":"article","og_title":"\u591a\u79cd\u6570\u636e\u7ed3\u6784\u7684Python\u5b9e\u73b0\u5f62\u5f0f - Nemo","og_description":"\u57fa\u7840\u77e5\u8bc6\u70b9 \u6570\u636e\u7ed3\u6784\u7684\u6982\u5ff5 \u6808 \u961f\u5217 \u94fe\u8868 \u6570\u636e\u7ed3\u6784 \u6570\u636e\u7ed3\u6784( data structure )\u662f\u8ba1\u7b97\u673a\u5b58\u50a8\u3001\u7ec4\u7ec7\u6570\u636e\u7684\u65b9\u5f0f\u3002\u6570\u636e\u7ed3\u6784\u662f\u6307\u76f8\u4e92\u4e4b\u95f4\u5b58\u5728\u4e00\u79cd\u6216\u591a\u79cd\u7279\u5b9a\u5173\u7cfb\u7684\u6570\u636e\u5143\u7d20\u7684\u96c6\u5408\u3002\u901a\u5e38\u60c5\u51b5\u4e0b\uff0c\u7cbe\u5fc3\u9009\u62e9\u7684\u6570\u636e\u7ed3\u6784\u53ef\u4ee5\u5e26\u6765\u66f4\u9ad8\u7684\u8fd0\u884c\u6216\u8005\u5b58\u50a8\u6548\u7387\u3002\u6570\u636e\u7ed3\u6784\u5f80\u5f80\u540c\u9ad8\u6548\u7684\u68c0\u7d22\u7b97\u6cd5\u548c\u7d22\u5f15\u6280\u672f\u6709\u5173\u3002 \u5728\u8bb8\u591a\u7c7b\u578b\u7684\u7a0b\u5e8f\u7684\u8bbe\u8ba1\u4e2d\uff0c\u6570\u636e\u7ed3\u6784\u7684\u9009\u62e9\u662f\u4e00\u4e2a\u57fa\u672c\u7684\u8bbe\u8ba1\u8003\u8651\u56e0\u7d20\u3002\u8bb8\u591a\u5927\u578b\u7cfb\u7edf\u7684\u6784\u9020\u7ecf\u9a8c\u8868\u660e\uff0c\u7cfb\u7edf\u5b9e\u73b0\u7684\u56f0\u96be\u7a0b\u5ea6\u548c\u7cfb\u7edf\u6784\u9020\u7684\u8d28\u91cf\u90fd\u4e25\u91cd\u5730\u4f9d\u8d56\u4e8e\u662f\u5426\u9009\u62e9\u4e86\u6700\u4f18\u7684\u6570\u636e\u7ed3\u6784\u3002\u8bb8\u591a\u65f6\u5019\uff0c\u786e\u5b9a\u4e86\u6570\u636e\u7ed3\u6784\u540e\uff0c\u7b97\u6cd5\u5c31\u5bb9\u6613\u5f97\u5230\u4e86\u3002\u6709\u4e9b\u65f6\u5019\u4e8b\u60c5\u4e5f\u4f1a\u53cd\u8fc7\u6765\uff0c\u6211\u4eec\u6839\u636e\u7279\u5b9a\u7b97\u6cd5\u6765\u9009\u62e9\u6570\u636e\u7ed3\u6784\u4e0e\u4e4b\u9002\u5e94\u3002 \u6808 \u6808\uff08stack\uff09\u53c8\u540d\u5806\u6808\uff0c\u5b83\u662f\u4e00\u79cd\u8fd0\u7b97\u53d7\u9650\u7684\u7ebf\u6027\u8868\u3002\u5176\u9650\u5236\u662f\u4ec5\u5141\u8bb8\u5728\u8868\u7684\u4e00\u7aef\u8fdb\u884c\u63d2\u5165\u548c\u5220\u9664\u8fd0\u7b97\u3002 \u6808\u5141\u8bb8\u8fdb\u884c\u63d2\u5165\u548c\u5220\u9664\u64cd\u4f5c\u7684\u4e00\u7aef\u79f0\u4e3a\u6808\u9876(top)\uff0c\u53e6\u4e00\u7aef\u4e3a\u6808\u5e95(bottom)\uff1b\u6808\u5e95\u56fa\u5b9a\uff0c\u800c\u6808\u9876\u6d6e\u52a8\uff1b\u6808\u4e2d\u5143\u7d20\u4e2a\u6570\u4e3a\u96f6\u65f6\u79f0\u4e3a\u7a7a\u6808\u3002\u63d2\u5165\u4e00\u822c\u79f0\u4e3a\u8fdb\u6808\uff08PUSH\uff09\uff0c\u5220\u9664\u5219\u79f0\u4e3a\u9000\u6808\uff08POP\uff09\u3002 \u7531\u4e8e\u5806\u53e0\u6570\u636e\u7ed3\u6784\u53ea\u5141\u8bb8\u5728\u4e00\u7aef\u8fdb\u884c\u64cd\u4f5c\uff0c\u56e0\u800c\u6309\u7167\u540e\u8fdb\u5148\u51fa\uff08LIFO, Last In First Out\uff09\u7684\u539f\u7406\u8fd0\u4f5c\u3002\u6808\u4e5f\u79f0\u4e3a\u540e\u8fdb\u5148\u51fa\u8868\u3002 \u590d\u6742\u5ea6\u5206\u6790 \u6808\u5c5e\u4e8e\u5e38\u89c1\u7684\u4e00\u79cd\u7ebf\u6027\u7ed3\u6784\uff0c\u5bf9\u4e8e\u8fdb\u6808\u548c\u9000\u6808\u800c\u8a00\uff0c\u65f6\u95f4\u590d\u6742\u5ea6\u90fd\u4e3a O(1) \u6808\u7684\u5b9e\u73b0 1. \u521b\u5efa\u4e00\u4e2a Stack \u7684\u7c7b \u5bf9\u6808\u8fdb\u884c\u521d\u59cb\u5316\u53c2\u6570\u8bbe\u8ba1 \u5177\u4f53\u5b9e\u73b0\u4ee3\u7801\u5982\u4e0b\uff1a class Stack(object): def __init__(self, limit=10): self.stack = [] #\u5b58\u653e\u5143\u7d20 self.limit = limit #\u6808\u5bb9\u91cf\u6781\u9650 2. push \u8fdb\u6808 \u538b\u5165 push \uff1a\u5c06\u65b0\u5143\u7d20\u653e\u5728\u6808\u9876 \u5f53\u65b0\u5143\u7d20\u5165\u6808\u65f6\uff0c\u6808\u9876\u4e0a\u79fb\uff0c\u65b0\u5143\u7d20\u653e\u5728\u6808\u9876\u3002 \u5177\u4f53\u5b9e\u73b0\u4ee3\u7801\u5982\u4e0b: def push(self, data): if len(self.stack) [&hellip;]","og_url":"https:\/\/nemo.cool\/254.html","og_site_name":"Nemo","article_published_time":"2019-07-31T16:13:23+00:00","article_modified_time":"2020-08-03T09:43:16+00:00","og_image":[{"width":700,"height":350,"url":"https:\/\/nemo.cool\/wp-content\/uploads\/2019\/08\/2019-03-27-data_structure.png","type":"image\/png"}],"author":"Nemo","twitter_card":"summary_large_image","twitter_misc":{"Written by":"Nemo","Est. reading time":"20 minutes"},"schema":{"@context":"https:\/\/schema.org","@graph":[{"@type":"Article","@id":"https:\/\/nemo.cool\/254.html#article","isPartOf":{"@id":"https:\/\/nemo.cool\/254.html"},"author":{"name":"Nemo","@id":"https:\/\/nemo.cool\/#\/schema\/person\/698f803ee811e2b140a90f5d5de913d2"},"headline":"\u591a\u79cd\u6570\u636e\u7ed3\u6784\u7684Python\u5b9e\u73b0\u5f62\u5f0f","datePublished":"2019-07-31T16:13:23+00:00","dateModified":"2020-08-03T09:43:16+00:00","mainEntityOfPage":{"@id":"https:\/\/nemo.cool\/254.html"},"wordCount":317,"commentCount":4,"publisher":{"@id":"https:\/\/nemo.cool\/#\/schema\/person\/698f803ee811e2b140a90f5d5de913d2"},"image":{"@id":"https:\/\/nemo.cool\/254.html#primaryimage"},"thumbnailUrl":"https:\/\/nemo.cool\/wp-content\/uploads\/2019\/08\/2019-03-27-data_structure.png","articleSection":["Algorithm Notes","Basic Concepts","Python"],"inLanguage":"en-US","potentialAction":[{"@type":"CommentAction","name":"Comment","target":["https:\/\/nemo.cool\/254.html#respond"]}]},{"@type":"WebPage","@id":"https:\/\/nemo.cool\/254.html","url":"https:\/\/nemo.cool\/254.html","name":"\u591a\u79cd\u6570\u636e\u7ed3\u6784\u7684Python\u5b9e\u73b0\u5f62\u5f0f - Nemo","isPartOf":{"@id":"https:\/\/nemo.cool\/#website"},"primaryImageOfPage":{"@id":"https:\/\/nemo.cool\/254.html#primaryimage"},"image":{"@id":"https:\/\/nemo.cool\/254.html#primaryimage"},"thumbnailUrl":"https:\/\/nemo.cool\/wp-content\/uploads\/2019\/08\/2019-03-27-data_structure.png","datePublished":"2019-07-31T16:13:23+00:00","dateModified":"2020-08-03T09:43:16+00:00","breadcrumb":{"@id":"https:\/\/nemo.cool\/254.html#breadcrumb"},"inLanguage":"en-US","potentialAction":[{"@type":"ReadAction","target":["https:\/\/nemo.cool\/254.html"]}]},{"@type":"ImageObject","inLanguage":"en-US","@id":"https:\/\/nemo.cool\/254.html#primaryimage","url":"https:\/\/nemo.cool\/wp-content\/uploads\/2019\/08\/2019-03-27-data_structure.png","contentUrl":"https:\/\/nemo.cool\/wp-content\/uploads\/2019\/08\/2019-03-27-data_structure.png","width":700,"height":350},{"@type":"BreadcrumbList","@id":"https:\/\/nemo.cool\/254.html#breadcrumb","itemListElement":[{"@type":"ListItem","position":1,"name":"\u9996\u9875","item":"https:\/\/nemo.cool\/"},{"@type":"ListItem","position":2,"name":"\u591a\u79cd\u6570\u636e\u7ed3\u6784\u7684Python\u5b9e\u73b0\u5f62\u5f0f"}]},{"@type":"WebSite","@id":"https:\/\/nemo.cool\/#website","url":"https:\/\/nemo.cool\/","name":"Nemo","description":"","publisher":{"@id":"https:\/\/nemo.cool\/#\/schema\/person\/698f803ee811e2b140a90f5d5de913d2"},"potentialAction":[{"@type":"SearchAction","target":{"@type":"EntryPoint","urlTemplate":"https:\/\/nemo.cool\/?s={search_term_string}"},"query-input":{"@type":"PropertyValueSpecification","valueRequired":true,"valueName":"search_term_string"}}],"inLanguage":"en-US"},{"@type":["Person","Organization"],"@id":"https:\/\/nemo.cool\/#\/schema\/person\/698f803ee811e2b140a90f5d5de913d2","name":"Nemo","image":{"@type":"ImageObject","inLanguage":"en-US","@id":"https:\/\/nemo.cool\/wp-content\/uploads\/2024\/01\/Big_Hero_6_Anime_HD_desktop_wallpaper_01_1366x768-e1706020097529-96x96.jpg","url":"https:\/\/nemo.cool\/wp-content\/uploads\/2024\/01\/Big_Hero_6_Anime_HD_desktop_wallpaper_01_1366x768-e1706020097529-96x96.jpg","contentUrl":"https:\/\/nemo.cool\/wp-content\/uploads\/2024\/01\/Big_Hero_6_Anime_HD_desktop_wallpaper_01_1366x768-e1706020097529-96x96.jpg","caption":"Nemo"},"logo":{"@id":"https:\/\/nemo.cool\/wp-content\/uploads\/2024\/01\/Big_Hero_6_Anime_HD_desktop_wallpaper_01_1366x768-e1706020097529-96x96.jpg"},"sameAs":["https:\/\/nemo.cool"]}]}},"_links":{"self":[{"href":"https:\/\/nemo.cool\/wp-json\/wp\/v2\/posts\/254","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/nemo.cool\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/nemo.cool\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/nemo.cool\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/nemo.cool\/wp-json\/wp\/v2\/comments?post=254"}],"version-history":[{"count":0,"href":"https:\/\/nemo.cool\/wp-json\/wp\/v2\/posts\/254\/revisions"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/nemo.cool\/wp-json\/wp\/v2\/media\/284"}],"wp:attachment":[{"href":"https:\/\/nemo.cool\/wp-json\/wp\/v2\/media?parent=254"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/nemo.cool\/wp-json\/wp\/v2\/categories?post=254"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/nemo.cool\/wp-json\/wp\/v2\/tags?post=254"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}