使用Python内置类型实现了一些常用的类型

shengshijun · shengshijun · commit 1778bba92ace · 2014-12-18T23:46:21.000+08:00
diff --git a/.gitignore b/.gitignore
@@ -19,7 +19,6 @@ develop-eggs/
 dist/
 downloads/
 eggs/
-lib/
 lib64/
 parts/
 sdist/
diff --git a/README.md b/README.md
@@ -1,7 +1,7 @@
 algorithm
 =========
 
-在阅读算法导论和上一些在coursera课程的时候。我用Python写的一些算法，这些算法大部分使用list来作为底层存储数据的结构。但是python的list用的是链表实现，因此有些操作性能不高。
+在阅读算法导论的时候。我用Python写的一些算法，这些算法大部分使用list来作为底层存储数据的结构。但是python的list用的是链表实现，因此有些操作性能不高。
 
 #算法
 -------------
@@ -26,7 +26,7 @@ algorithm
 1.  使用分治法的最大子数组（应该算成分治法）
 2.  使用自底向上方法实现的最大子数组
 3.  使用动态规划的两种方式实现的LCS（最大公共串）（下面的算法都会使用动态规划的两种方式来实现）
-4.  
+4.  加权有向无环图中最短路径和最长路径
 
 ###幂乘：算法复杂度是O(lgn)
 
@@ -67,6 +67,14 @@ algorithm
 1.  实现strassen矩阵乘法的矩阵
 
 ##图
+1.  深度遍历，广度遍历和拓扑排序
+
+
+##类库：为了保证被其他算法使用的数据结构一定是没有bug的，我用Python的内置类型实现实现了一些常用的数据结构(lib)
+1.  Stack
+2.  Queue
+3.  Set
+
 
 
 
diff --git a/lib/__init__.py b/lib/__init__.py
@@ -0,0 +1,3 @@
+#!/usr/bin/env python
+# -*- coding:UTF-8
+__author__ = 'shenshijun'
diff --git a/lib/queue.py b/lib/queue.py
@@ -0,0 +1,36 @@
+#!/usr/bin/env python
+# -*- coding:UTF-8
+__author__ = 'shenshijun'
+import copy
+
+class Queue(object):
+    """
+    使用Python的list快速实现一个队列
+    """
+
+    def __init__(self, *arg):
+        super(Queue, self).__init__()
+        self.__queue = list(copy.copy(arg))
+        self.__size = len(self.__queue)
+
+    def enter(self, value):
+        self.__size += 1
+        self.__queue.append(value)
+
+    def exit(self):
+        if self.__size <= 0:
+            return None
+        else:
+            value = self.__queue[0]
+            self.__size -= 1
+            del self.__queue[0]
+            return value
+
+    def __len__(self):
+        return self.__size
+
+    def empty(self):
+        return self.__size <= 0
+
+    def __str__(self):
+        return "".join(["Queue(list=", str(self.__queue), ",size=", str(self.__size)])
diff --git a/lib/set.py b/lib/set.py
@@ -0,0 +1,49 @@
+#!/usr/bin/env python
+# -*- coding:UTF-8
+__author__ = 'shenshijun'
+
+
+class Set(object):
+    """
+    使用Python的Dict实现一个Set结构,如果一个对象没有实现hash方法，那么这个对象的哈希值基本上就是这个对象
+    的内存地址，这个地址是唯一的，不会收对象的属性的变化的影响，因此可以安全地把可变对象存储在Set中
+    """
+
+    def __init__(self, *vargs):
+        """"""
+        self.__dic = {}
+        map(self.add, vargs)
+
+    def add(self, instance):
+        self.__dic[instance] = instance
+
+    def __contains__(self, item):
+        return self.__dic.get(item, False)
+
+    def delete(self, instance):
+        if self.exists(instance):
+            del self.__dic[instance]
+
+    def __len__(self):
+        return len(self.__dic)
+
+    def __getitem__(self, item):
+        """
+        get有特殊的意义，保证了get得到的对象和instance是同值，
+        但是却是set中已经存储在set中的对象。保证不创建新的对象。
+        :param item:
+        :return:
+        """
+        result = self.__dic.get(item, None)
+        if result is None:
+            self.add(item)
+            result = item
+        return result
+
+    def __iter__(self):
+        return self.__dic.iterkeys()
+
+    def __str__(self):
+        return ",".join(iter(self))
+
+
diff --git a/lib/stack.py b/lib/stack.py
@@ -0,0 +1,38 @@
+#!/usr/bin/env python
+# -*- coding:UTF-8
+import copy
+
+__author__ = 'shenshijun'
+
+
+class Stack(object):
+    """
+    使用Python快速实现一个栈
+    """
+
+    def __init__(self, *arg):
+        super(Stack, self).__init__()
+        self.__stack = list(copy.copy(arg))
+        self.__size = len(self.__stack)
+
+    def push(self, value):
+        self.__stack.append(value)
+        self.__size += 1
+
+    def pop(self):
+        if self.__size <= 0:
+            return None
+        else:
+            value = self.__stack[-1]
+            self.__size -= 1
+            del self.__stack[-1]
+            return value
+
+    def __len__(self):
+        return self.__size
+
+    def empty(self):
+        return self.__size <= 0
+
+    def __str__(self):
+        return "".join(["Stack(list=", str(map(lambda s: str(s), self.__stack)), ",size=", str(self.__size), ')'])

-Original file line number
+Diff line change
 dist/
 downloads/
 eggs/
 -lib/
 lib64/
 parts/
 sdist/
Original file line number	Diff line number	Diff line change
`@@ -0,0 +1,3 @@`
	`1`	`+#!/usr/bin/env python`
	`2`	`+# -*- coding:UTF-8`
	`3`	`+__author__ = 'shenshijun'`