{"id":2447,"date":"2019-11-14T19:53:35","date_gmt":"2019-11-14T11:53:35","guid":{"rendered":"http:\/\/www.sniper97.cn\/?p=2447"},"modified":"2019-11-14T19:53:35","modified_gmt":"2019-11-14T11:53:35","slug":"%e3%80%90%e7%ae%97%e6%b3%95%e5%88%86%e6%9e%90%e4%b8%8e%e8%ae%be%e8%ae%a1%e3%80%91%e5%9f%ba%e6%9c%ac%e6%95%b0%e6%8d%ae%e7%bb%93%e6%9e%84","status":"publish","type":"post","link":"http:\/\/www.sniper97.cn\/index.php\/note\/introduction_to_algorithms\/2447\/","title":{"rendered":"\u3010\u7b97\u6cd5\u5bfc\u8bba\u3011\u57fa\u672c\u6570\u636e\u7ed3\u6784"},"content":{"rendered":"\n

1.\u6808\u548c\u961f\u5217<\/h2>\n\n\n

\u6808\u548c\u961f\u5217\u90fd\u662f\u52a8\u6001\u96c6\u5408\uff0c\u6808\u5b9e\u73b0\u7684\u662f\u4e00\u79cd\u540e\u8fdb\u5148\u51fa\u7684\u7b56\u7565\uff0c\u961f\u5217\u5b9e\u73b0\u7684\u662f\u5148\u8fdb\u5148\u51fa\u7684\u7b56\u7565\u3002<\/p>\n\n\n

\u6808<\/h3>\n\n\n

\u6808\u7684insert\u64cd\u4f5c\u79f0\u4e3a\u538b\u5165\uff08push\uff09\uff0cdelete\u64cd\u4f5c\u79f0\u4e3a\u5f39\u51fa\uff08pop\uff09\u3002<\/p>\n\n\n

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

\u51fa\u5165\u6808\u4ee5\u53ca\u5224\u65ad\u7a7a\u6808\u64cd\u4f5c\uff1a<\/p>\n\n\n

class Stack():
    def __init__(self):
        self.stack = []
        self.top = -1
        pass

    def push(self, i):
        self.stack.append(i)
        self.top += 1

    def pop(self):
        assert self.top != -1, 'stack empty'
        num = self.stack.pop()
        self.top -= 1
        return num

    def is_empty(self):
        \"\"\"
<\/em>        \u5224\u65ad\u662f\u5426\u4e3a\u7a7a
<\/em>        <\/em>:return<\/em><\/strong>:
<\/em>        \"\"\"
<\/em>        <\/em>if self.top == -1:
            return True
        else:
            return False
        pass

    def print(self):
        \"\"\"
<\/em>        \u6253\u5370\u6808
<\/em>        <\/em>:return<\/em><\/strong>:
<\/em>        \"\"\"
<\/em>        <\/em>print(self.stack)<\/pre>\n\n\n
\u961f\u5217<\/h3>\n\n\n
\u961f\u5217\u4e0a\u7684insert\u79f0\u4e3a\u5165\u961f\uff08enqueue\uff09\uff0cdelete\u64cd\u4f5c\u79f0\u4e3a\u51fa\u961f\uff08dequeue\uff09\u3002<\/p>\n\n\n
\u961f\u5217\u6709\u5bf9\u5934\u548c\u961f\u5c3e\u3002<\/p>\n\n\n
\"\"<\/figure><\/div>\n\n\n
\u5165\u961f\u3001\u51fa\u961f\u3001\u4ee5\u53ca\u5224\u65ad\u4e3a\u7a7a\u7684\u64cd\u4f5c\uff1a<\/p>\n\n\n
class Queue():
    def __init__(self):
        self.queue = [0 for _ in range(10)]
        self.head = 0
        self.tail = -1
        pass

    def enqueue(self, i):
        \"\"\"
<\/em>        \u5165\u961f
<\/em>        <\/em>:param<\/em><\/strong> i:
<\/em>        <\/em>:return<\/em><\/strong>:
<\/em>        \"\"\"
<\/em>        <\/em>self.tail += 1
        self.queue[self.tail] = i

    def dequeue(self):
        \"\"\"
<\/em>        \u51fa\u961f
<\/em>        <\/em>:return<\/em><\/strong>:
<\/em>        \"\"\"
<\/em>        <\/em>self.head += 1
        return self.queue[self.head - 1]

    def is_empty(self):
        \"\"\"
<\/em>        \u5224\u65ad\u7a7a
<\/em>        <\/em>:return<\/em><\/strong>:
<\/em>        \"\"\"
<\/em>        <\/em>if self.head == self.tail + 1:
            return True
        else:
            return False
<\/pre>\n\n\n
2.\u94fe\u8868<\/h2>\n\n\n
\u94fe\u8868\u5373\u5404\u5143\u7d20\u4e4b\u95f4\u901a\u8fc7\u4e00\u6761\u94fe\uff08\u5730\u5740\uff09\u76f8\u8fde\u3002\u5982\u4e0b\u56fe\uff08\u4e0b\u56fe\u662f\u53cc\u5411\u94fe\u8868\uff09<\/p>\n\n\n
\"\"<\/figure>\n\n\n
\u540c\u65f6\u4e3a\u4e86\u65b9\u4fbf\u5bf9\u7b2c\u4e00\u4e2a\u94fe\u548c\u540e\u9762\u7684\u94fe\u7684\u64cd\u4f5c\uff0c\u6211\u4eec\u5f15\u5165\u54e8\u5175\u673a\u5236\uff08sentinel\uff09\uff0c\u5982\u56fe\u4e3a\u5e26\u54e8\u5175\u7684\u53cc\u5411\u5faa\u73af\u94fe\u8868\u3002<\/p>\n\n\n
\"\"<\/figure><\/div>\n\n\n
\u4e0b\u9762\u662f\u53cc\u5faa\u73af\u94fe\u8868\u7684\u67e5\u8be2\u3001\u63d2\u5165\u548c\u5220\u9664\u4ee3\u7801\uff1a<\/p>\n\n\n
class LinklistMine():
    def __init__(self):
        self.first = Point()
        self.first.prev = self.first
        self.first.next = self.first
        pass

    def list_search(self, k):
        \"\"\"
<\/em>        \u6284\u627e\u94fe\u8868\u4e2d\u7684k\u5143\u7d20
<\/em>        <\/em>:param<\/em><\/strong> k:
<\/em>        <\/em>:return<\/em><\/strong>:
<\/em>        \"\"\"
<\/em>        <\/em>p = self.first.next
        while p.value != k:
            if p is not self.first:
                p = p.next
            else:
                return 'Null'
        return k

    def list_insert(self, value):
        \"\"\"
<\/em>        \u63d2\u5165value
<\/em>        <\/em>:param<\/em><\/strong> value:
<\/em>        <\/em>:return<\/em><\/strong>:
<\/em>        \"\"\"
<\/em>        <\/em># \u8bbe\u7f6e\u65b0\u8282\u70b9
        p = Point()
        p.set_value(value=value)
        # \u8fde\u63a5\u5230\u94fe\u8868\u4e2d
        point = self.first.prev
        p.prev = point
        point.next = p
        self.first.prev = p
        p.next = self.first
        pass

    def list_delete(self, k):
        \"\"\"
<\/em>        \u5220\u9664k
<\/em>        <\/em>:param<\/em><\/strong> k:
<\/em>        <\/em>:return<\/em><\/strong>:
<\/em>        \"\"\"
<\/em>        <\/em>p = self.first.next
        while p.value != k:
            if p is not self.first:
                p = p.next
        # \u5220\u9664p
        p.prev.next = p.next
        p.next.prev = p.prev
        pass

    def print(self):
        \"\"\"
<\/em>        \u6253\u5370
<\/em>        <\/em>:return<\/em><\/strong>:
<\/em>        \"\"\"
<\/em>        <\/em>if self.first.next is self.first:
            print('linklist empty')
            return
        print('linklist:', end='')
        point = self.first.next
        while point is not self.first:
            print(point.value, ' ', end='')
            point = point.next
        print()


class Point():
    def __init__(self):
        self.prev = None
        self.value = None
        self.next = None

    def link_prev(self, point):
        \"\"\"
<\/em>        \u8fde\u63a5prev
<\/em>        <\/em>:param<\/em><\/strong> point:
<\/em>        <\/em>:return<\/em><\/strong>:
<\/em>        \"\"\"
<\/em>        <\/em>self.prev = point

    def link_next(self, point):
        \"\"\"
<\/em>        \u8fde\u63a5next
<\/em>        <\/em>:param<\/em><\/strong> point:
<\/em>        <\/em>:return<\/em><\/strong>:
<\/em>        \"\"\"
<\/em>        <\/em>self.next = point

    def set_value(self, value):
        \"\"\"
<\/em>        \u8bbe\u7f6e\u503c
<\/em>        <\/em>:param<\/em><\/strong> value:
<\/em>        <\/em>:return<\/em><\/strong>:
<\/em>        \"\"\"
<\/em>        <\/em>self.value = value<\/pre>\n\n\n
3.\u6709\u6839\u6811\u7684\u8868\u793a<\/h2>\n\n\n
\u4e8c\u53c9\u6811<\/h2>\n\n\n
\u5982\u4e0b\u56fe\uff0c\u5206\u4e3a\u5de6\u53f3\u5b50\u6811\uff08left\u4e0eright\u6307\u9488\uff09\u548c\u6839\uff08value\uff09<\/p>\n\n\n
\"\"<\/figure><\/div>\n\n\n
\u5206\u652f\u65e0\u9650\u5236\u7684\u6709\u6839\u6570<\/h2>\n\n\n
\u6211\u4eec\u91c7\u7528\u5de6\u5b69\u5b50\u53f3\u5144\u5f1f\u8868\u793a\u6cd5<\/strong>\uff0c\u5373left\u6307\u9488\u8fde\u63a5\u7684\u662f\u5b69\u5b50\uff0cright\u6307\u9488\u8fde\u63a5\u7684\u662f\u5144\u5f1f\u3002\u5982\u4e0b\u56fe\uff1a<\/p>\n\n\n
\"\"<\/figure><\/div>\n\n\n
<\/p>\n","protected":false},"excerpt":{"rendered":"
1.\u6808\u548c\u961f\u5217 \u6808\u548c\u961f\u5217\u90fd\u662f\u52a8\u6001\u96c6\u5408\uff0c\u6808\u5b9e\u73b0\u7684\u662f\u4e00\u79cd\u540e\u8fdb\u5148\u51fa\u7684\u7b56\u7565\uff0c\u961f\u5217\u5b9e\u73b0\u7684\u662f\u5148\u8fdb\u5148\u51fa\u7684\u7b56\u7565\u3002 \u6808  […]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"om_disable_all_campaigns":false,"_mi_skip_tracking":false,"_monsterinsights_sitenote_active":false,"_monsterinsights_sitenote_note":"","_monsterinsights_sitenote_category":0,"footnotes":""},"categories":[11],"tags":[],"views":3744,"_links":{"self":[{"href":"http:\/\/www.sniper97.cn\/index.php\/wp-json\/wp\/v2\/posts\/2447"}],"collection":[{"href":"http:\/\/www.sniper97.cn\/index.php\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"http:\/\/www.sniper97.cn\/index.php\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"http:\/\/www.sniper97.cn\/index.php\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"http:\/\/www.sniper97.cn\/index.php\/wp-json\/wp\/v2\/comments?post=2447"}],"version-history":[{"count":0,"href":"http:\/\/www.sniper97.cn\/index.php\/wp-json\/wp\/v2\/posts\/2447\/revisions"}],"wp:attachment":[{"href":"http:\/\/www.sniper97.cn\/index.php\/wp-json\/wp\/v2\/media?parent=2447"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"http:\/\/www.sniper97.cn\/index.php\/wp-json\/wp\/v2\/categories?post=2447"},{"taxonomy":"post_tag","embeddable":true,"href":"http:\/\/www.sniper97.cn\/index.php\/wp-json\/wp\/v2\/tags?post=2447"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}