Correct python typo for data structure

xuhuairuogu · Apr 4, 2019 · b3f8af6 · b3f8af6
1 parent f9bf499
commit b3f8af6
Show file tree

Hide file tree

Showing 5 changed files with 125 additions and 91 deletions.
diff --git a/数据结构/codes/mbinary/graph/adjacentList.py b/数据结构/codes/mbinary/graph/adjacentList.py
@@ -10,144 +10,175 @@
 #########################################################################
 '''
 
-from collections import Iterable,deque
+from collections import Iterable, deque
+
+
 class vertex:
-    def __init__(self,mark,firstEdge=None,val=None):
+    def __init__(self, mark, firstEdge=None, val=None):
         self.mark = mark
         self.val = val
         self.firstEdge = firstEdge
         self.isVisited = False
+
     def __str__(self):
-        return 'V'+str(self.mark)
+        return 'V' + str(self.mark)
+
     def __repr__(self):
         return str(self)
+
+
 class edge:
-    def __init__(self,adjVertexs, weight = 1,nextEdge=None):
+    def __init__(self, adjVertexs, weight=1, nextEdge=None):
         '''adjVertexs:tuple(v.mark,u.mark)'''
         self.weight = weight
         self.adjVertexs = adjVertexs
         self.nextEdge = nextEdge
         self.isVisted = False
-    def __add__(self,x):
-        return self.weight +x
-    def __radd__(self,x):
-        return self+x
-    def __getitem__(self,k):
-        if k!=0 or k!=1:raise IndexError
+
+    def __add__(self, x):
+        return self.weight + x
+
+    def __radd__(self, x):
+        return self + x
+
+    def __getitem__(self, k):
+        if k != 0 or k != 1: raise IndexError
         return self.adjVertexs[k]
+
     def __str__(self):
-        return '--'+str(self.weight)+'--'
+        return '--' + str(self.weight) + '--'
+
     def __repr__(self):
         return str(self)
+
     @property
     def v(self):
         return self.adjVertexs[0]
+
     @property
     def u(self):
         return self.adjVertexs[1]
+
+
 class graph:
-    def __init__(self): 
+    def __init__(self):
         self.vertexs = {}
         self.edges = {}
-    def __getitem__(self,i): 
+
+    def __getitem__(self, i):
         return self.vertexs[i]
-    def __setitem__(selfi,x):
-        self.vertexs[i]= x
+
+    def __setitem__(self,i, x):
+        self.vertexs[i] = x
+
     def __iter__(self):
         return iter(self.vertexs)
+
     def __bool__(self):
-        return len(self.vertexs)!=0
-    def addVertex(self,vertexs):
+        return len(self.vertexs) != 0
+
+    def addVertex(self, vertexs):
         '''vertexs is a iterable or just a mark that marks the vertex,whichc can be every imutable type'''
-        if not isinstance(vertexs,Iterable):vertexs=[vertexs]
+        if not isinstance(vertexs, Iterable): vertexs = [vertexs]
         for i in vertexs:
-            if  not isinstance(i,vertex) and  i not in self.vertexs:self.vertexs[i]= vertex(i)
-            if isinstance(i,vertex) and  i not in self.vertexs:self.vertexs[i.mark]= i
+            if not isinstance(i, vertex) and i not in self.vertexs:
+                self.vertexs[i] = vertex(i)
+            if isinstance(i, vertex) and i not in self.vertexs:
+                self.vertexs[i.mark] = i
 
-    def __getVertex(self,v):
-        if not isinstance(v,vertex):
+    def __getVertex(self, v):
+        if not isinstance(v, vertex):
             if v not in self.vertexs:
-                self.vertexs[v]=vertex(v)
+                self.vertexs[v] = vertex(v)
             return self.vertexs[v]
         return v
-    def addEdge(self,v,u,weight = 1):
+
+    def addEdge(self, v, u, weight=1):
         v = self.__getVertex(v)
         u = self.__getVertex(u)
-        arc = self.findEdge(v,u)
-        if arc!=None:return #examine that if v,u have been already connected
-        vertexs = (v,u)
-        newEdge = edge (vertexs,weight)
+        arc = self.findEdge(v, u)
+        if arc != None:
+            return  #examine that if v,u have been already connected
+        vertexs = (v, u)
+        newEdge = edge(vertexs, weight)
         self.edges[vertexs] = newEdge
-        if v.firstEdge==None:
-            v.firstEdge=newEdge
+        if v.firstEdge == None:
+            v.firstEdge = newEdge
         else:
-            arc=v.firstEdge.nextEdge
-            v.firstEdge=newEdge
-    def findEdge(self,v,u):
+            arc = v.firstEdge.nextEdge
+            v.firstEdge = newEdge
+
+    def findEdge(self, v, u):
         v = self.__getVertex(v)
         u = self.__getVertex(u)
         arc = v.firstEdge
-        while arc!=None and u not in arc:
+        while arc != None and u not in arc:
             arc = arc.nextEdge
-        if arc!=None:return arc
+        if arc != None: return arc
         arc = u.firstEdge
-        while arc!=None and v not in arc:
+        while arc != None and v not in arc:
             arc = arc.nextEdge
         return arc
-    def delEdge(self,v,u):
-        if not isinstance(v,vertex):v= self.vertexs[v]
-        if not isinstance(u,vertex):u= self.vertexs[u]
-        if  u in v.firstEdge:
-            v.firstEdge =v.firstEdge.nextEdge
+
+    def delEdge(self, v, u):
+        if not isinstance(v, vertex): v = self.vertexs[v]
+        if not isinstance(u, vertex): u = self.vertexs[u]
+        if u in v.firstEdge:
+            v.firstEdge = v.firstEdge.nextEdge
         else:
             arc = v.firstEdge
-            while arc.nextEdge!=e:
+            while arc.nextEdge != None:
                 arc = arc.nextEdge
-            if arc!=None: arc.nextEdge = arc.nextEdge.nextEdge
+            if arc != None: arc.nextEdge = arc.nextEdge.nextEdge
             else:
-                if  v in u.firstEdge:
-                    u.firstEdge =u.firstEdge.nextEdge
+                if v in u.firstEdge:
+                    u.firstEdge = u.firstEdge.nextEdge
                 else:
                     arc = u.firstEdge
-                    while arc.nextEdge!=e:
+                    while arc.nextEdge != None:
                         arc = arc.nextEdge
                     arc.nextEdge = arc.nextEdge.nextEdge
-        del self.edges[(v,u)]       
+        del self.edges[(v, u)]
+
     def revisit(self):
         for i in self.vertexs.values():
             i.isVisited = False
         for i in self.edges.values():
             i.isVisited = False
+
     def __str__(self):
-        arcs= list(self.edges.keys())
-        arcs=[str(i[0])+str(self.edges[i])+str(i[1]) for i in arcs]
-        s= '\n'.join(arcs)
+        arcs = list(self.edges.keys())
+        arcs = [str(i[0]) + str(self.edges[i]) + str(i[1]) for i in arcs]
+        s = '\n'.join(arcs)
         return s
+
     def __repr__(self):
         return str(self)
-    def minPath(self,v,u):
-        if v not in self or u not in self:return -1
-        v=self.__getVertex(v)
-        u=self.__getVertex(u)
-        q=deque([v])
-        last={i:None for i in self.vertexs.values()}
+
+    def minPath(self, v, u):
+        if v not in self or u not in self: return -1
+        v = self.__getVertex(v)
+        u = self.__getVertex(u)
+        q = deque([v])
+        last = {i: None for i in self.vertexs.values()}
         last[v] = 0
-        ds={i:1000000 for i in self.vertexs.values()}
-        ds[v]=0
-        while len(q)!=0:
+        ds = {i: 1000000 for i in self.vertexs.values()}
+        ds[v] = 0
+        while len(q) != 0:
             nd = q.popleft()
-            nd.isVisited=True
+            nd.isVisited = True
             arc = nd.firstEdge
-            while arc!=None:
-                tgt=None
-                if arc.v==nd:
+            while arc != None:
+                tgt = None
+                if arc.v == nd:
                     tgt = arc.u
-                else:tgt = arc.v
-                tmp=ds[nd]+arc
-                if ds[tgt] >tmp:
-                    ds[tgt]=tmp
+                else:
+                    tgt = arc.v
+                tmp = ds[nd] + arc
+                if ds[tgt] > tmp:
+                    ds[tgt] = tmp
                     last[tgt] = nd
-                if not tgt.isVisited:q.append(tgt)
+                if not tgt.isVisited: q.append(tgt)
         '''
         cur = u
         while cur !=v:
@@ -156,36 +187,39 @@ def minPath(self,v,u):
         print(str(v))
         '''
         return ds[u]
+
     def hasCircle(self):
         pass
+
     def display(self):
         print('vertexs')
         for i in self.vertexs:
             print(i)
         print('edges')
         for i in self.edges:
-            arc=self.edges[i]
-            print(str(arc.v)+str(arc)+str(arc.u))               
-
-if __name__=='__main__':
-    n=int(input())
-    while n>0:
-        cities=int(input())
-        n-=1
-        g=graph()
-        li={}
+            arc = self.edges[i]
+            print(str(arc.v) + str(arc) + str(arc.u))
+
+
+if __name__ == '__main__':
+    n = int(input())
+    while n > 0:
+        cities = int(input())
+        n -= 1
+        g = graph()
+        li = {}
         for i in range(cities):
-            li[input()]=i+1
-            arc=int(input())
+            li[input()] = i + 1
+            arc = int(input())
             for j in range(arc):
-                s=input().split(' ')
-                g.addEdge(i+1,int(s[0]),int(s[1]))
-        ct  =int(input())
-        for  i in range(ct):
+                s = input().split(' ')
+                g.addEdge(i + 1, int(s[0]), int(s[1]))
+        ct = int(input())
+        for i in range(ct):
             line = input()
-            line= line .split(' ')
-            v,u = li[line[0]],li[line[1]]
-            print(g.minPath(v,u))
+            line = line.split(' ')
+            v, u = li[line[0]], li[line[1]]
+            print(g.minPath(v, u))
             g.revisit()
 #http://www.spoj.com/submit/SHPATH/id=20525991
 '''

diff --git a/数据结构/codes/mbinary/graph/directed.py b/数据结构/codes/mbinary/graph/directed.py
@@ -45,7 +45,7 @@ def __init__(self):
         self.edges = {}
     def __getitem__(self,i): 
         return self.vertexs[i]
-    def __setitem__(selfi,x):
+    def __setitem__(self,i,x):
         self.vertexs[i]= x
     def __iter__(self):
         return iter(self.vertexs.values())

diff --git a/数据结构/codes/mbinary/graph/undirected.py b/数据结构/codes/mbinary/graph/undirected.py
@@ -56,7 +56,7 @@ def __init__(self):
         self.edges = {}
     def __getitem__(self,i): 
         return self.vertexs[i]
-    def __setitem__(selfi,x):
+    def __setitem__(self,i,x):
         self.vertexs[i]= x
     def __iter__(self):
         return iter(self.vertexs)

diff --git a/数据结构/labs/2017/navigation/directed.py b/数据结构/labs/2017/navigation/directed.py
@@ -35,7 +35,7 @@ def __init__(self):
         self.edges = {}
     def __getitem__(self,i): 
         return self.vertexs[i]
-    def __setitem__(selfi,x):
+    def __setitem__(self,i,x):
         self.vertexs[i]= x
     def __iter__(self):
         return iter(self.vertexs.values())

diff --git a/数据结构/labs/2017/navigation/graph.py b/数据结构/labs/2017/navigation/graph.py
@@ -48,7 +48,7 @@ def __init__(self):
         self.edges = {}
     def __getitem__(self,i): 
         return self.vertexs[i]
-    def __setitem__(selfi,x):
+    def __setitem__(self,i,x):
         self.vertexs[i]= x
     def __iter__(self):
         return iter(self.vertexs)