Movatterモバイル変換

[0]ホーム
URL:

Skip to content

Navigation Menu

Sign in
Appearance settings

Search code, repositories, users, issues, pull requests...

Provide feedback

We read every piece of feedback, and take your input very seriously.

Saved searches

Use saved searches to filter your results more quickly

 Sign up
Appearance settings

Commit1778bba

Browse files
author
shengshijun
committed
使用Python内置类型实现了一些常用的类型
1 parent779e284 commit1778bba

File tree

6 files changed

+136
-3
lines changed

6 files changed

+136
-3
lines changed

‎.gitignore

Lines changed: 0 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -19,7 +19,6 @@ develop-eggs/
1919
dist/
2020
downloads/
2121
eggs/
22-
lib/
2322
lib64/
2423
parts/
2524
sdist/

‎README.md

Lines changed: 10 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -1,7 +1,7 @@
11
algorithm
22
=========
33

4-
在阅读算法导论和上一些在coursera课程的时候。我用Python写的一些算法，这些算法大部分使用list来作为底层存储数据的结构。但是python的list用的是链表实现，因此有些操作性能不高。
4+
在阅读算法导论的时候。我用Python写的一些算法，这些算法大部分使用list来作为底层存储数据的结构。但是python的list用的是链表实现，因此有些操作性能不高。
55

66
#算法
77
-------------
@@ -26,7 +26,7 @@ algorithm
2626
1. 使用分治法的最大子数组（应该算成分治法）
2727
2. 使用自底向上方法实现的最大子数组
2828
3. 使用动态规划的两种方式实现的LCS（最大公共串）（下面的算法都会使用动态规划的两种方式来实现）
29-
4.
29+
4.加权有向无环图中最短路径和最长路径
3030

3131
###幂乘：算法复杂度是O(lgn)
3232

@@ -67,6 +67,14 @@ algorithm
6767
1. 实现strassen矩阵乘法的矩阵
6868

6969
##图
70+
1. 深度遍历，广度遍历和拓扑排序
71+
72+
73+
##类库：为了保证被其他算法使用的数据结构一定是没有bug的，我用Python的内置类型实现实现了一些常用的数据结构(lib)
74+
1. Stack
75+
2. Queue
76+
3. Set
77+
7078

7179

7280

‎lib/__init__.py

Lines changed: 3 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,3 @@
1+
#!/usr/bin/env python
2+
# -*- coding:UTF-8
3+
__author__='shenshijun'

‎lib/queue.py

Lines changed: 36 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,36 @@
1+
#!/usr/bin/env python
2+
# -*- coding:UTF-8
3+
__author__='shenshijun'
4+
importcopy
5+
6+
classQueue(object):
7+
"""
8+
使用Python的list快速实现一个队列
9+
"""
10+
11+
def__init__(self,*arg):
12+
super(Queue,self).__init__()
13+
self.__queue=list(copy.copy(arg))
14+
self.__size=len(self.__queue)
15+
16+
defenter(self,value):
17+
self.__size+=1
18+
self.__queue.append(value)
19+
20+
defexit(self):
21+
ifself.__size<=0:
22+
returnNone
23+
else:
24+
value=self.__queue[0]
25+
self.__size-=1
26+
delself.__queue[0]
27+
returnvalue
28+
29+
def__len__(self):
30+
returnself.__size
31+
32+
defempty(self):
33+
returnself.__size<=0
34+
35+
def__str__(self):
36+
return"".join(["Queue(list=",str(self.__queue),",size=",str(self.__size)])

‎lib/set.py

Lines changed: 49 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,49 @@
1+
#!/usr/bin/env python
2+
# -*- coding:UTF-8
3+
__author__='shenshijun'
4+
5+
6+
classSet(object):
7+
"""
8+
使用Python的Dict实现一个Set结构,如果一个对象没有实现hash方法，那么这个对象的哈希值基本上就是这个对象
9+
的内存地址，这个地址是唯一的，不会收对象的属性的变化的影响，因此可以安全地把可变对象存储在Set中
10+
"""
11+
12+
def__init__(self,*vargs):
13+
""""""
14+
self.__dic= {}
15+
map(self.add,vargs)
16+
17+
defadd(self,instance):
18+
self.__dic[instance]=instance
19+
20+
def__contains__(self,item):
21+
returnself.__dic.get(item,False)
22+
23+
defdelete(self,instance):
24+
ifself.exists(instance):
25+
delself.__dic[instance]
26+
27+
def__len__(self):
28+
returnlen(self.__dic)
29+
30+
def__getitem__(self,item):
31+
"""
32+
get有特殊的意义，保证了get得到的对象和instance是同值，
33+
但是却是set中已经存储在set中的对象。保证不创建新的对象。
34+
:param item:
35+
:return:
36+
"""
37+
result=self.__dic.get(item,None)
38+
ifresultisNone:
39+
self.add(item)
40+
result=item
41+
returnresult
42+
43+
def__iter__(self):
44+
returnself.__dic.iterkeys()
45+
46+
def__str__(self):
47+
return",".join(iter(self))
48+
49+

‎lib/stack.py

Lines changed: 38 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,38 @@
1+
#!/usr/bin/env python
2+
# -*- coding:UTF-8
3+
importcopy
4+
5+
__author__='shenshijun'
6+
7+
8+
classStack(object):
9+
"""
10+
使用Python快速实现一个栈
11+
"""
12+
13+
def__init__(self,*arg):
14+
super(Stack,self).__init__()
15+
self.__stack=list(copy.copy(arg))
16+
self.__size=len(self.__stack)
17+
18+
defpush(self,value):
19+
self.__stack.append(value)
20+
self.__size+=1
21+
22+
defpop(self):
23+
ifself.__size<=0:
24+
returnNone
25+
else:
26+
value=self.__stack[-1]
27+
self.__size-=1
28+
delself.__stack[-1]
29+
returnvalue
30+
31+
def__len__(self):
32+
returnself.__size
33+
34+
defempty(self):
35+
returnself.__size<=0
36+
37+
def__str__(self):
38+
return"".join(["Stack(list=",str(map(lambdas:str(s),self.__stack)),",size=",str(self.__size),')'])

0 commit comments

Comments
 (0)
[8]ページ先頭
©2009-2025 Movatter.jp