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
Appearance settings

Commit b3f8af6

Browse filesBrowse files
heqin-zhuheqin-zhu
committed
Correct python typo for data structure
1 parent f9bf499 commit b3f8af6
Copy full SHA for b3f8af6

File tree

Expand file treeCollapse file tree

5 files changed

+125
-91
lines changed
Filter options
Expand file treeCollapse file tree

5 files changed

+125
-91
lines changed

‎数据结构/codes/mbinary/graph/adjacentList.py

Copy file name to clipboardExpand all lines: 数据结构/codes/mbinary/graph/adjacentList.py
+121-87Lines changed: 121 additions & 87 deletions
Original file line numberDiff line numberDiff line change
@@ -10,144 +10,175 @@
1010
#########################################################################
1111
'''
1212

13-
from collections import Iterable,deque
13+
from collections import Iterable, deque
14+
15+
1416
class vertex:
15-
def __init__(self,mark,firstEdge=None,val=None):
17+
def __init__(self, mark, firstEdge=None, val=None):
1618
self.mark = mark
1719
self.val = val
1820
self.firstEdge = firstEdge
1921
self.isVisited = False
22+
2023
def __str__(self):
21-
return 'V'+str(self.mark)
24+
return 'V' + str(self.mark)
25+
2226
def __repr__(self):
2327
return str(self)
28+
29+
2430
class edge:
25-
def __init__(self,adjVertexs, weight = 1,nextEdge=None):
31+
def __init__(self, adjVertexs, weight=1, nextEdge=None):
2632
'''adjVertexs:tuple(v.mark,u.mark)'''
2733
self.weight = weight
2834
self.adjVertexs = adjVertexs
2935
self.nextEdge = nextEdge
3036
self.isVisted = False
31-
def __add__(self,x):
32-
return self.weight +x
33-
def __radd__(self,x):
34-
return self+x
35-
def __getitem__(self,k):
36-
if k!=0 or k!=1:raise IndexError
37+
38+
def __add__(self, x):
39+
return self.weight + x
40+
41+
def __radd__(self, x):
42+
return self + x
43+
44+
def __getitem__(self, k):
45+
if k != 0 or k != 1: raise IndexError
3746
return self.adjVertexs[k]
47+
3848
def __str__(self):
39-
return '--'+str(self.weight)+'--'
49+
return '--' + str(self.weight) + '--'
50+
4051
def __repr__(self):
4152
return str(self)
53+
4254
@property
4355
def v(self):
4456
return self.adjVertexs[0]
57+
4558
@property
4659
def u(self):
4760
return self.adjVertexs[1]
61+
62+
4863
class graph:
49-
def __init__(self):
64+
def __init__(self):
5065
self.vertexs = {}
5166
self.edges = {}
52-
def __getitem__(self,i):
67+
68+
def __getitem__(self, i):
5369
return self.vertexs[i]
54-
def __setitem__(selfi,x):
55-
self.vertexs[i]= x
70+
71+
def __setitem__(self,i, x):
72+
self.vertexs[i] = x
73+
5674
def __iter__(self):
5775
return iter(self.vertexs)
76+
5877
def __bool__(self):
59-
return len(self.vertexs)!=0
60-
def addVertex(self,vertexs):
78+
return len(self.vertexs) != 0
79+
80+
def addVertex(self, vertexs):
6181
'''vertexs is a iterable or just a mark that marks the vertex,whichc can be every imutable type'''
62-
if not isinstance(vertexs,Iterable):vertexs=[vertexs]
82+
if not isinstance(vertexs, Iterable): vertexs = [vertexs]
6383
for i in vertexs:
64-
if not isinstance(i,vertex) and i not in self.vertexs:self.vertexs[i]= vertex(i)
65-
if isinstance(i,vertex) and i not in self.vertexs:self.vertexs[i.mark]= i
84+
if not isinstance(i, vertex) and i not in self.vertexs:
85+
self.vertexs[i] = vertex(i)
86+
if isinstance(i, vertex) and i not in self.vertexs:
87+
self.vertexs[i.mark] = i
6688

67-
def __getVertex(self,v):
68-
if not isinstance(v,vertex):
89+
def __getVertex(self, v):
90+
if not isinstance(v, vertex):
6991
if v not in self.vertexs:
70-
self.vertexs[v]=vertex(v)
92+
self.vertexs[v] = vertex(v)
7193
return self.vertexs[v]
7294
return v
73-
def addEdge(self,v,u,weight = 1):
95+
96+
def addEdge(self, v, u, weight=1):
7497
v = self.__getVertex(v)
7598
u = self.__getVertex(u)
76-
arc = self.findEdge(v,u)
77-
if arc!=None:return #examine that if v,u have been already connected
78-
vertexs = (v,u)
79-
newEdge = edge (vertexs,weight)
99+
arc = self.findEdge(v, u)
100+
if arc != None:
101+
return #examine that if v,u have been already connected
102+
vertexs = (v, u)
103+
newEdge = edge(vertexs, weight)
80104
self.edges[vertexs] = newEdge
81-
if v.firstEdge==None:
82-
v.firstEdge=newEdge
105+
if v.firstEdge == None:
106+
v.firstEdge = newEdge
83107
else:
84-
arc=v.firstEdge.nextEdge
85-
v.firstEdge=newEdge
86-
def findEdge(self,v,u):
108+
arc = v.firstEdge.nextEdge
109+
v.firstEdge = newEdge
110+
111+
def findEdge(self, v, u):
87112
v = self.__getVertex(v)
88113
u = self.__getVertex(u)
89114
arc = v.firstEdge
90-
while arc!=None and u not in arc:
115+
while arc != None and u not in arc:
91116
arc = arc.nextEdge
92-
if arc!=None:return arc
117+
if arc != None: return arc
93118
arc = u.firstEdge
94-
while arc!=None and v not in arc:
119+
while arc != None and v not in arc:
95120
arc = arc.nextEdge
96121
return arc
97-
def delEdge(self,v,u):
98-
if not isinstance(v,vertex):v= self.vertexs[v]
99-
if not isinstance(u,vertex):u= self.vertexs[u]
100-
if u in v.firstEdge:
101-
v.firstEdge =v.firstEdge.nextEdge
122+
123+
def delEdge(self, v, u):
124+
if not isinstance(v, vertex): v = self.vertexs[v]
125+
if not isinstance(u, vertex): u = self.vertexs[u]
126+
if u in v.firstEdge:
127+
v.firstEdge = v.firstEdge.nextEdge
102128
else:
103129
arc = v.firstEdge
104-
while arc.nextEdge!=e:
130+
while arc.nextEdge != None:
105131
arc = arc.nextEdge
106-
if arc!=None: arc.nextEdge = arc.nextEdge.nextEdge
132+
if arc != None: arc.nextEdge = arc.nextEdge.nextEdge
107133
else:
108-
if v in u.firstEdge:
109-
u.firstEdge =u.firstEdge.nextEdge
134+
if v in u.firstEdge:
135+
u.firstEdge = u.firstEdge.nextEdge
110136
else:
111137
arc = u.firstEdge
112-
while arc.nextEdge!=e:
138+
while arc.nextEdge != None:
113139
arc = arc.nextEdge
114140
arc.nextEdge = arc.nextEdge.nextEdge
115-
del self.edges[(v,u)]
141+
del self.edges[(v, u)]
142+
116143
def revisit(self):
117144
for i in self.vertexs.values():
118145
i.isVisited = False
119146
for i in self.edges.values():
120147
i.isVisited = False
148+
121149
def __str__(self):
122-
arcs= list(self.edges.keys())
123-
arcs=[str(i[0])+str(self.edges[i])+str(i[1]) for i in arcs]
124-
s= '\n'.join(arcs)
150+
arcs = list(self.edges.keys())
151+
arcs = [str(i[0]) + str(self.edges[i]) + str(i[1]) for i in arcs]
152+
s = '\n'.join(arcs)
125153
return s
154+
126155
def __repr__(self):
127156
return str(self)
128-
def minPath(self,v,u):
129-
if v not in self or u not in self:return -1
130-
v=self.__getVertex(v)
131-
u=self.__getVertex(u)
132-
q=deque([v])
133-
last={i:None for i in self.vertexs.values()}
157+
158+
def minPath(self, v, u):
159+
if v not in self or u not in self: return -1
160+
v = self.__getVertex(v)
161+
u = self.__getVertex(u)
162+
q = deque([v])
163+
last = {i: None for i in self.vertexs.values()}
134164
last[v] = 0
135-
ds={i:1000000 for i in self.vertexs.values()}
136-
ds[v]=0
137-
while len(q)!=0:
165+
ds = {i: 1000000 for i in self.vertexs.values()}
166+
ds[v] = 0
167+
while len(q) != 0:
138168
nd = q.popleft()
139-
nd.isVisited=True
169+
nd.isVisited = True
140170
arc = nd.firstEdge
141-
while arc!=None:
142-
tgt=None
143-
if arc.v==nd:
171+
while arc != None:
172+
tgt = None
173+
if arc.v == nd:
144174
tgt = arc.u
145-
else:tgt = arc.v
146-
tmp=ds[nd]+arc
147-
if ds[tgt] >tmp:
148-
ds[tgt]=tmp
175+
else:
176+
tgt = arc.v
177+
tmp = ds[nd] + arc
178+
if ds[tgt] > tmp:
179+
ds[tgt] = tmp
149180
last[tgt] = nd
150-
if not tgt.isVisited:q.append(tgt)
181+
if not tgt.isVisited: q.append(tgt)
151182
'''
152183
cur = u
153184
while cur !=v:
@@ -156,36 +187,39 @@ def minPath(self,v,u):
156187
print(str(v))
157188
'''
158189
return ds[u]
190+
159191
def hasCircle(self):
160192
pass
193+
161194
def display(self):
162195
print('vertexs')
163196
for i in self.vertexs:
164197
print(i)
165198
print('edges')
166199
for i in self.edges:
167-
arc=self.edges[i]
168-
print(str(arc.v)+str(arc)+str(arc.u))
169-
170-
if __name__=='__main__':
171-
n=int(input())
172-
while n>0:
173-
cities=int(input())
174-
n-=1
175-
g=graph()
176-
li={}
200+
arc = self.edges[i]
201+
print(str(arc.v) + str(arc) + str(arc.u))
202+
203+
204+
if __name__ == '__main__':
205+
n = int(input())
206+
while n > 0:
207+
cities = int(input())
208+
n -= 1
209+
g = graph()
210+
li = {}
177211
for i in range(cities):
178-
li[input()]=i+1
179-
arc=int(input())
212+
li[input()] = i + 1
213+
arc = int(input())
180214
for j in range(arc):
181-
s=input().split(' ')
182-
g.addEdge(i+1,int(s[0]),int(s[1]))
183-
ct =int(input())
184-
for i in range(ct):
215+
s = input().split(' ')
216+
g.addEdge(i + 1, int(s[0]), int(s[1]))
217+
ct = int(input())
218+
for i in range(ct):
185219
line = input()
186-
line= line .split(' ')
187-
v,u = li[line[0]],li[line[1]]
188-
print(g.minPath(v,u))
220+
line = line.split(' ')
221+
v, u = li[line[0]], li[line[1]]
222+
print(g.minPath(v, u))
189223
g.revisit()
190224
#http://www.spoj.com/submit/SHPATH/id=20525991
191225
'''

‎数据结构/codes/mbinary/graph/directed.py

Copy file name to clipboardExpand all lines: 数据结构/codes/mbinary/graph/directed.py
+1-1Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -45,7 +45,7 @@ def __init__(self):
4545
self.edges = {}
4646
def __getitem__(self,i):
4747
return self.vertexs[i]
48-
def __setitem__(selfi,x):
48+
def __setitem__(self,i,x):
4949
self.vertexs[i]= x
5050
def __iter__(self):
5151
return iter(self.vertexs.values())

‎数据结构/codes/mbinary/graph/undirected.py

Copy file name to clipboardExpand all lines: 数据结构/codes/mbinary/graph/undirected.py
+1-1Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -56,7 +56,7 @@ def __init__(self):
5656
self.edges = {}
5757
def __getitem__(self,i):
5858
return self.vertexs[i]
59-
def __setitem__(selfi,x):
59+
def __setitem__(self,i,x):
6060
self.vertexs[i]= x
6161
def __iter__(self):
6262
return iter(self.vertexs)

‎数据结构/labs/2017/navigation/directed.py

Copy file name to clipboardExpand all lines: 数据结构/labs/2017/navigation/directed.py
+1-1Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -35,7 +35,7 @@ def __init__(self):
3535
self.edges = {}
3636
def __getitem__(self,i):
3737
return self.vertexs[i]
38-
def __setitem__(selfi,x):
38+
def __setitem__(self,i,x):
3939
self.vertexs[i]= x
4040
def __iter__(self):
4141
return iter(self.vertexs.values())

‎数据结构/labs/2017/navigation/graph.py

Copy file name to clipboardExpand all lines: 数据结构/labs/2017/navigation/graph.py
+1-1Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -48,7 +48,7 @@ def __init__(self):
4848
self.edges = {}
4949
def __getitem__(self,i):
5050
return self.vertexs[i]
51-
def __setitem__(selfi,x):
51+
def __setitem__(self,i,x):
5252
self.vertexs[i]= x
5353
def __iter__(self):
5454
return iter(self.vertexs)

0 commit comments

Comments
0 (0)
Morty Proxy This is a proxified and sanitized view of the page, visit original site.