update

yidao620c · yidao620c · commit fb39e73ad491 · 2020-06-01T00:40:21.000+08:00
diff --git a/README.md b/README.md
@@ -9,7 +9,7 @@
 ## 作者的话
 
 书中经典的算法示例使用python3语言实现，并且配有详细的算法原理说明。
-整个部分分为两个部分，第一个部分是基于`《算法》第4版` + `《算法导论》第3版`这两本书中的所有例子写的。作为基础算法部分。
+整个部分分为两个部分，第一个部分是基于`《算法导论》第3版`这两本书中的所有例子写的。作为基础算法部分。
 第二部分是LeeCode算法题库，选取其中最具代表性的100个算法题来演示。
 
 从2013年就开始写这个系列，写到动态规划后就停了，期间工作太忙根本抽不出时间来写。
diff --git a/algorithms/__init__.py b/algorithms/__init__.py
@@ -1,13 +1,7 @@
 #!/usr/bin/env python
 # -*- encoding: utf-8 -*-
 """
-《算法》第4版 + 《算法导论》第3版
-使用python3语言实现书中经典的算法示例
+《算法导论》第3版，使用python3语言实现书中经典的算法示例
 """
 
-s = {}
-s['1'] = None
-s['2'] = None
-print(s['1'])
-
 
diff --git a/algorithms/ch01structure/__init__.py b/algorithms/ch01structure/__init__.py
@@ -1,4 +1,15 @@
 # -*- encoding: utf-8 -*-
 """常见的数据结构
-Some of description...
 """
+
+
+class Node:
+    """
+    节点信息
+    """
+    def __init__(self, item_, next_=None):
+        self.item = item_
+        self.next = next_
+
+    def __str__(self):
+        return str(self.item)
diff --git a/algorithms/ch01structure/array_queue.py b/algorithms/ch01structure/array_queue.py
@@ -0,0 +1,64 @@
+# -*- encoding: utf-8 -*-
+"""基于环形数组实现的一个简单队列
+数组A[1..n]实现最多容纳n-1个元素的队列。
+"""
+
+
+class ArrayQueue:
+    def __init__(self, size):
+        self.head = 0  # 队头元素下标
+        self.tail = 0  # 下一个插入位置
+        self._arr = [None] * size  # 实际存放数据的数组
+
+    def is_empty(self):
+        return self.head == self.tail
+
+    def is_full(self):
+        return self.size() == len(self._arr) - 1
+
+    def size(self):
+        return (len(self._arr) + self.tail - self.head) % len(self._arr)
+
+    def enqueue(self, item):
+        # 队列满了则抛出异常
+        if self.is_full():
+            raise LookupError('Queue is full')
+        self._arr[self.tail] = item
+        self.tail = (self.tail + 1) % len(self._arr)
+
+    def dequeue(self):
+        # 队列空则抛出异常
+        if self.is_empty():
+            raise LookupError('Queue underflow')
+        item = self._arr[self.head]
+        self._arr[self.head] = None
+        self.head = (self.head + 1) % len(self._arr)
+        return item
+
+    def __iter__(self):
+        while not self.is_empty():
+            yield self.dequeue()
+
+
+if __name__ == '__main__':
+    q = ArrayQueue(6)
+    q.enqueue(1)
+    q.enqueue(2)
+    q.enqueue(3)
+    q.enqueue(4)
+    q.enqueue(5)
+    print(q.dequeue())
+    print(q.dequeue())
+    print(q.dequeue())
+    print(q.dequeue())
+    print(q.dequeue())
+    q.enqueue(1)
+    q.enqueue(2)
+    q.enqueue(3)
+    q.enqueue(4)
+    q.enqueue(5)
+    print(q.dequeue())
+    print(q.dequeue())
+    print(q.dequeue())
+    print(q.dequeue())
+    print(q.dequeue())
diff --git a/algorithms/ch01structure/linked_queue.py b/algorithms/ch01structure/linked_queue.py
@@ -1,11 +1,11 @@
 # -*- encoding: utf-8 -*-
-"""自己实现的一个简单队列
+"""基于链表实现的一个简单队列
 队尾插入元素，队头取元素。就跟在菜市场排队买菜原理是一样的
 """
-from algorithms.ch00structure.stack import Node
+from algorithms.ch01structure import Node
 
 
-class Queue:
+class LinkedQueue:
     def __init__(self):
         self.first = None  # beginning of queue
         self.last = None  # end of queue
diff --git a/algorithms/ch01structure/prior_queue.py b/algorithms/ch01structure/prior_queue.py
@@ -4,7 +4,7 @@
 """
 from functools import total_ordering
 
-from algorithms.ch00structure.stack import Stack
+from algorithms.ch01structure.simple_stack import Stack
 
 
 class MaxPriorQueue:
diff --git a/algorithms/ch01structure/simple_stack.py b/algorithms/ch01structure/simple_stack.py
@@ -4,6 +4,7 @@
 另一方面，迭代器应该一直可以迭代。迭代器的 `__iter__` 方法应该返回自身。
 一般可使用生成器函数实现更符合python风格的可迭代对象。
 """
+from algorithms.ch01structure import Node
 
 
 class Stack:
@@ -38,11 +39,3 @@ def __iter__(self):
         while self.n > 0:
             yield self.pop()
 
-
-class Node:
-    def __init__(self, item_, next_=None):
-        self.item = item_
-        self.next = next_
-
-    def __str__(self):
-        return str(self.item)
diff --git a/algorithms/ch02sort/base/template.py b/algorithms/ch02sort/base/template.py
@@ -25,7 +25,6 @@ def less(self, val1, val2):
     def show(self, vals):
         for val in vals:
             print("{}".format(val), end=' ')
-        print()
 
     def is_sorted(self, vals):
         for i in range(1, len(vals)):
diff --git a/algorithms/ch09sample/m06_hornerpoly.py b/algorithms/ch09sample/m06_hornerpoly.py
@@ -9,12 +9,12 @@
 __author__ = 'Xiong Neng'
 
 
-def hornerPoly(coefficientArr, x):
+def horner_poly(coefficient_arr, x):
     res = 0
-    for i in range(len(coefficientArr))[-1::-1]:
-        res = coefficientArr[i] + x * res
+    for i in range(len(coefficient_arr))[-1::-1]:
+        res = coefficient_arr[i] + x * res
     return res
 
 
 if __name__ == '__main__':
-    print(hornerPoly((1, 2, 3), 2))
+    print(horner_poly((1, 2, 3), 2))
diff --git a/algorithms/ch09sample/m16_circle_queue.py b/algorithms/ch09sample/m16_circle_queue.py
