文档章节

Python中的高级数据结构

好铁
 好铁
发布于 2016/02/11 23:57
字数 4853
阅读 122
收藏 4
点赞 1
评论 0

数据结构

数据结构的概念很好理解,就是用来将数据组织在一起的结构。换句话说,数据结构是用来存储一系列关联数据的东西。在Python中有四种内建的数据结构,分别是List、Tuple、Dictionary以及Set。大部分的应用程序不需要其他类型的数据结构,但若是真需要也有很多高级数据结构可供选择,例如Collection、Array、Heapq、Bisect、Weakref、Copy以及Pprint。本文将介绍这些数据结构的用法,看看它们是如何帮助我们的应用程序的。

关于四种内建数据结构的使用方法很简单,并且网上有很多参考资料,因此本文将不会讨论它们。

1. Collections

collections模块包含了内建类型之外的一些有用的工具,例如Counter、defaultdict、OrderedDict、deque以及nametuple。其中Counter、deque以及defaultdict是最常用的类。

1.1 Counter()

如果你想统计一个单词在给定的序列中一共出现了多少次,诸如此类的操作就可以用到Counter。来看看如何统计一个list中出现的item次数:

1
2
3
4
5
fromcollectionsimportCounter
 
li=["Dog","Cat","Mouse",42,"Dog",42,"Cat","Dog"]
a=Counter(li)
printa# Counter({'Dog': 3, 42: 2, 'Cat': 2, 'Mouse': 1})

若要统计一个list中不同单词的数目,可以这么用:

1
2
3
4
5
6
7
fromcollectionsimportCounter
 
li=["Dog","Cat","Mouse",42,"Dog",42,"Cat","Dog"]
a=Counter(li)
printa# Counter({'Dog': 3, 42: 2, 'Cat': 2, 'Mouse': 1})
 
printlen(set(li))# 4

如果需要对结果进行分组,可以这么做:

1
2
3
4
5
6
7
8
9
10
fromcollectionsimportCounter
 
li=["Dog","Cat","Mouse","Dog","Cat","Dog"]
a=Counter(li)
 
printa# Counter({'Dog': 3, 'Cat': 2, 'Mouse': 1})
 
print"{0} : {1}".format(a.values(),a.keys()) # [1, 3, 2] : ['Mouse', 'Dog', 'Cat']
 
print(a.most_common(3))# [('Dog', 3), ('Cat', 2), ('Mouse', 1)]

以下的代码片段找出一个字符串中出现频率最高的单词,并打印其出现次数。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
importre
fromcollectionsimportCounter
 
string="""   Lorem ipsum dolor sit amet, consectetur
    adipiscing elit. Nunc ut elit id mi ultricies
    adipiscing. Nulla facilisi. Praesent pulvinar,
    sapien vel feugiat vestibulum, nulla dui pretium orci,
    non ultricies elit lacus quis ante. Lorem ipsum dolor
    sit amet, consectetur adipiscing elit. Aliquam
    pretium ullamcorper urna quis iaculis. Etiam ac massa
    sed turpis tempor luctus. Curabitur sed nibh eu elit
    mollis congue. Praesent ipsum diam, consectetur vitae
    ornare a, aliquam a nunc. In id magna pellentesque
    tellus posuere adipiscing. Sed non mi metus, at lacinia
    augue. Sed magna nisi, ornare in mollis in, mollis
    sed nunc. Etiam at justo in leo congue mollis.
    Nullam in neque eget metus hendrerit scelerisque
    eu non enim. Ut malesuada lacus eu nulla bibendum
    id euismod urna sodales.  """
 
words=re.findall(r'\w+', string)#This finds words in the document
 
lower_words=[word.lower()forwordinwords]#lower all the words
 
word_counts=Counter(lower_words)#counts the number each time a word appears
printword_counts
 
# Counter({'elit': 5, 'sed': 5, 'in': 5, 'adipiscing': 4, 'mollis': 4, 'eu': 3,
# 'id': 3, 'nunc': 3, 'consectetur': 3, 'non': 3, 'ipsum': 3, 'nulla': 3, 'pretium':
# 2, 'lacus': 2, 'ornare': 2, 'at': 2, 'praesent': 2, 'quis': 2, 'sit': 2, 'congue': 2, 'amet': 2,
# 'etiam': 2, 'urna': 2, 'a': 2, 'magna': 2, 'lorem': 2, 'aliquam': 2, 'ut': 2, 'ultricies': 2, 'mi': 2,
# 'dolor': 2, 'metus': 2, 'ac': 1, 'bibendum': 1, 'posuere': 1, 'enim': 1, 'ante': 1, 'sodales': 1, 'tellus': 1,
# 'vitae': 1, 'dui': 1, 'diam': 1, 'pellentesque': 1, 'massa': 1, 'vel': 1, 'nullam': 1, 'feugiat': 1, 'luctus': 1,
# 'pulvinar': 1, 'iaculis': 1, 'hendrerit': 1, 'orci': 1, 'turpis': 1, 'nibh': 1, 'scelerisque': 1, 'ullamcorper': 1,
# 'eget': 1, 'neque': 1, 'euismod': 1, 'curabitur': 1, 'leo': 1, 'sapien': 1, 'facilisi': 1, 'vestibulum': 1, 'nisi': 1,
# 'justo': 1, 'augue': 1, 'tempor': 1, 'lacinia': 1, 'malesuada': 1})

1.2 Deque

Deque是一种由队列结构扩展而来的双端队列(double-ended queue),队列元素能够在队列两端添加或删除。因此它还被称为头尾连接列表(head-tail linked list),尽管叫这个名字的还有另一个特殊的数据结构实现。

Deque支持线程安全的,经过优化的append和pop操作,在队列两端的相关操作都能够达到近乎O(1)的时间复杂度。虽然list也支持类似的操作,但是它是对定长列表的操作表现很不错,而当遇到pop(0)和insert(0, v)这样既改变了列表的长度又改变其元素位置的操作时,其复杂度就变为O(n)了。

来看看相关的比较结果:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
importtime
fromcollectionsimportdeque
 
num=100000
 
defappend(c):
    foriinrange(num):
        c.append(i)
 
defappendleft(c):
    ifisinstance(c, deque):
        foriinrange(num):
            c.appendleft(i)
    else:
        foriinrange(num):
            c.insert(0, i)
defpop(c):
    foriinrange(num):
        c.pop()
 
defpopleft(c):
    ifisinstance(c, deque):
        foriinrange(num):
            c.popleft()
    else:
        foriinrange(num):
            c.pop(0)
 
forcontainerin[deque,list]:
    foroperationin[append, appendleft, pop, popleft]:
        c=container(range(num))
        start=time.time()
        operation(c)
        elapsed=time.time()-start
        print"Completed {0}/{1} in {2} seconds: {3} ops/sec".format(
              container.__name__, operation.__name__, elapsed, num/elapsed)
 
# Completed deque/append in 0.0250000953674 seconds: 3999984.74127 ops/sec
# Completed deque/appendleft in 0.0199999809265 seconds: 5000004.76838 ops/sec
# Completed deque/pop in 0.0209999084473 seconds: 4761925.52225 ops/sec
# Completed deque/popleft in 0.0199999809265 seconds: 5000004.76838 ops/sec
# Completed list/append in 0.0220000743866 seconds: 4545439.17637 ops/sec
# Completed list/appendleft in 21.3209998608 seconds: 4690.21155917 ops/sec
# Completed list/pop in 0.0240001678467 seconds: 4166637.52682 ops/sec
# Completed list/popleft in 4.01799988747 seconds: 24888.0046791 ops/sec

另一个例子是执行基本的队列操作:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
fromcollectionsimportdeque
q=deque(range(5))
q.append(5)
q.appendleft(6)
printq
printq.pop()
printq.popleft()
printq.rotate(3)
printq
printq.rotate(-1)
printq
 
# deque([6, 0, 1, 2, 3, 4, 5])
# 5
# 6
# None
# deque([2, 3, 4, 0, 1])
# None
# deque([3, 4, 0, 1, 2])

译者注:rotate是队列的旋转操作,Right rotate(正参数)是将右端的元素移动到左端,而Left rotate(负参数)则相反。

1.3 Defaultdict

这个类型除了在处理不存在的键的操作之外与普通的字典完全相同。当查找一个不存在的键操作发生时,它的default_factory会被调用,提供一个默认的值,并且将这对键值存储下来。其他的参数同普通的字典方法dict()一致,一个defaultdict的实例同内建dict一样拥有同样地操作。

defaultdict对象在当你希望使用它存放追踪数据的时候很有用。举个例子,假定你希望追踪一个单词在字符串中的位置,那么你可以这么做:

1
2
3
4
5
6
7
8
9
10
11
12
13
fromcollectionsimportdefaultdict
 
s="the quick brown fox jumps over the lazy dog"
 
words=s.split()
location=defaultdict(list)
form, ninenumerate(words):
    location[n].append(m)
 
printlocation
 
# defaultdict(<type 'list'>, {'brown': [2], 'lazy': [7], 'over': [5], 'fox': [3],
# 'dog': [8], 'quick': [1], 'the': [0, 6], 'jumps': [4]})

是选择lists或sets与defaultdict搭配取决于你的目的,使用list能够保存你插入元素的顺序,而使用set则不关心元素插入顺序,它会帮助消除重复元素。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
fromcollectionsimportdefaultdict
 
s="the quick brown fox jumps over the lazy dog"
 
words=s.split()
location=defaultdict(set)
form, ninenumerate(words):
    location[n].add(m)
 
printlocation
 
# defaultdict(<type 'set'>, {'brown': set([2]), 'lazy': set([7]),
# 'over': set([5]), 'fox': set([3]), 'dog': set([8]), 'quick': set([1]),
# 'the': set([0, 6]), 'jumps': set([4])})

另一种创建multidict的方法:

1
2
3
4
5
6
7
8
9
s="the quick brown fox jumps over the lazy dog"
d={}
words=s.split()
 
forkey, valueinenumerate(words):
    d.setdefault(key, []).append(value)
printd
 
# {0: ['the'], 1: ['quick'], 2: ['brown'], 3: ['fox'], 4: ['jumps'], 5: ['over'], 6: ['the'], 7: ['lazy'], 8: ['dog']}

一个更复杂的例子:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
classExample(dict):
    def__getitem__(self, item):
        try:
            returndict.__getitem__(self, item)
        exceptKeyError:
            value=self[item]=type(self)()
            returnvalue
 
a=Example()
 
a[1][2][3]=4
a[1][3][3]=5
a[1][2]['test']=6
 
printa# {1: {2: {'test': 6, 3: 4}, 3: {3: 5}}}

2. Array

array模块定义了一个很像list的新对象类型,不同之处在于它限定了这个类型只能装一种类型的元素。array元素的类型是在创建并使用的时候确定的。

如果你的程序需要优化内存的使用,并且你确定你希望在list中存储的数据都是同样类型的,那么使用array模块很合适。举个例子,如果需要存储一千万个整数,如果用list,那么你至少需要160MB的存储空间,然而如果使用array,你只需要40MB。但虽然说能够节省空间,array上几乎没有什么基本操作能够比在list上更快。

在使用array进行计算的时候,需要特别注意那些创建list的操作。例如,使用列表推导式(list comprehension)的时候,会将array整个转换为list,使得存储空间膨胀。一个可行的替代方案是使用生成器表达式创建新的array。看代码:

1
2
3
4
importarray
 
a=array.array("i", [1,2,3,4,5])
b=array.array(a.typecode, (2*xforxina))

因为使用array是为了节省空间,所以更倾向于使用in-place操作。一种更高效的方法是使用enumerate:

1
2
3
4
5
importarray
 
a=array.array("i", [1,2,3,4,5])
fori, xinenumerate(a):
    a[i]=2*x

对于较大的array,这种in-place修改能够比用生成器创建一个新的array至少提升15%的速度。

那么什么时候使用array呢?是当你在考虑计算的因素之外,还需要得到一个像C语言里一样统一元素类型的数组时。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
importarray
fromtimeitimportTimer
 
defarraytest():
    a=array.array("i", [1,2,3,4,5])
    b=array.array(a.typecode, (2*xforxina))
 
defenumeratetest():
    a=array.array("i", [1,2,3,4,5])
    fori, xinenumerate(a):
        a[i]=2*x
 
if__name__=='__main__':
    m=Timer("arraytest()","from __main__ import arraytest")
    n=Timer("enumeratetest()","from __main__ import enumeratetest")
 
    printm.timeit()# 5.22479210582
    printn.timeit()# 4.34367196717

3. Heapq

heapq模块使用一个用堆实现的优先级队列。堆是一种简单的有序列表,并且置入了堆的相关规则。

堆是一种树形的数据结构,树上的子节点与父节点之间存在顺序关系。二叉堆(binary heap)能够用一个经过组织的列表或数组结构来标识,在这种结构中,元素N的子节点的序号为2*N+1和2*N+2(下标始于0)。简单来说,这个模块中的所有函数都假设序列是有序的,所以序列中的第一个元素(seq[0])是最小的,序列的其他部分构成一个二叉树,并且seq[i]节点的子节点分别为seq[2*i+1]以及seq[2*i+2]。当对序列进行修改时,相关函数总是确保子节点大于等于父节点。

1
2
3
4
5
6
7
8
9
importheapq
 
heap=[]
 
forvaluein[20,10,30,50,40]:
    heapq.heappush(heap, value)
 
whileheap:
    printheapq.heappop(heap)

heapq模块有两个函数nlargest()和nsmallest(),顾名思义,让我们来看看它们的用法。

1
2
3
4
5
importheapq
 
nums=[1,8,2,23,7,-4,18,23,42,37,2]
print(heapq.nlargest(3, nums))# Prints [42, 37, 23]
print(heapq.nsmallest(3, nums))# Prints [-4, 1, 2]

两个函数也能够通过一个键参数使用更为复杂的数据结构,例如:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
importheapq
 
portfolio=[
{'name':'IBM','shares':100,'price':91.1},
{'name':'AAPL','shares':50,'price':543.22},
{'name':'FB','shares':200,'price':21.09},
{'name':'HPQ','shares':35,'price':31.75},
{'name':'YHOO','shares':45,'price':16.35},
{'name':'ACME','shares':75,'price':115.65}
]
cheap=heapq.nsmallest(3, portfolio, key=lambdas: s['price'])
expensive=heapq.nlargest(3, portfolio, key=lambdas: s['price'])
 
printcheap
 
# [{'price': 16.35, 'name': 'YHOO', 'shares': 45},
# {'price': 21.09, 'name': 'FB', 'shares': 200}, {'price': 31.75, 'name': 'HPQ', 'shares': 35}]
 
printexpensive
 
# [{'price': 543.22, 'name': 'AAPL', 'shares': 50}, {'price': 115.65, 'name': 'ACME',
# 'shares': 75}, {'price': 91.1, 'name': 'IBM', 'shares': 100}]

来看看如何实现一个根据给定优先级进行排序,并且每次pop操作都返回优先级最高的元素的队列例子。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
importheapq
 
classItem:
    def__init__(self, name):
        self.name=name
 
    def__repr__(self):
        return'Item({!r})'.format(self.name)
 
classPriorityQueue:
    def__init__(self):
        self._queue=[]
        self._index=0
 
    defpush(self, item, priority):
        heapq.heappush(self._queue, (-priority,self._index, item))
        self._index+=1
 
    defpop(self):
        returnheapq.heappop(self._queue)[-1]
 
q=PriorityQueue()
q.push(Item('foo'),1)
q.push(Item('bar'),5)
q.push(Item('spam'),4)
q.push(Item('grok'),1)
 
printq.pop()# Item('bar')
printq.pop()# Item('spam')
printq.pop()# Item('foo')
printq.pop()# Item('grok')

4. Bisect

bisect模块能够提供保持list元素序列的支持。它使用了二分法完成大部分的工作。它在向一个list插入元素的同时维持list是有序的。在某些情况下,这比重复的对一个list进行排序更为高效,并且对于一个较大的list来说,对每步操作维持其有序也比对其排序要高效。

假设你有一个range集合:

1
a=[(0,100), (150,220), (500,1000)]

如果我想添加一个range (250, 400),我可能会这么做:

1
2
3
4
5
6
7
importbisect
 
a=[(0,100), (150,220), (500,1000)]
 
bisect.insort_right(a, (250,400))
 
printa# [(0, 100), (150, 220), (250, 400), (500, 1000)]

我们可以使用bisect()函数来寻找插入点:

1
2
3
4
5
6
7
8
9
importbisect
 
a=[(0,100), (150,220), (500,1000)]
 
bisect.insort_right(a, (250,400))
bisect.insort_right(a, (399,450))
printa# [(0, 100), (150, 220), (250, 400), (500, 1000)]
 
printbisect.bisect(a, (550,1200))# 5

bisect(sequence, item) => index 返回元素应该的插入点,但序列并不被修改。

1
2
3
4
5
6
7
8
9
10
11
importbisect
 
a=[(0,100), (150,220), (500,1000)]
 
bisect.insort_right(a, (250,400))
bisect.insort_right(a, (399,450))
printa# [(0, 100), (150, 220), (250, 400), (500, 1000)]
 
printbisect.bisect(a, (550,1200))# 5
bisect.insort_right(a, (550,1200))
printa# [(0, 100), (150, 220), (250, 400), (399, 450), (500, 1000), (550, 1200)]

新元素被插入到第5的位置。

5. Weakref

weakref模块能够帮助我们创建Python引用,却不会阻止对象的销毁操作。这一节包含了weak reference的基本用法,并且引入一个代理类。

在开始之前,我们需要明白什么是strong reference。strong reference是一个对对象的引用次数、生命周期以及销毁时机产生影响的指针。strong reference如你所见,就是当你将一个对象赋值给一个变量的时候产生的:

1
2
>>> a=[1,2,3]
>>> b=a

在这种情况下,这个列表有两个strong reference,分别是a和b。在这两个引用都被释放之前,这个list不会被销毁。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
classFoo(object):
    def__init__(self):
        self.obj=None
        print'created'
 
    def__del__(self):
        print'destroyed'
 
    defshow(self):
        printself.obj
 
    defstore(self, obj):
        self.obj=obj
 
a=Foo()# created
b=a
dela
delb# destroyed

Weak reference则是对对象的引用计数器不会产生影响。当一个对象存在weak reference时,并不会影响对象的撤销。这就说,如果一个对象仅剩下weak reference,那么它将会被销毁。

你可以使用weakref.ref函数来创建对象的weak reference。这个函数调用需要将一个strong reference作为第一个参数传给函数,并且返回一个weak reference。

1
2
3
4
5
>>>importweakref
>>> a=Foo()
created
>>> b=weakref.ref(a)
>>> b

一个临时的strong reference可以从weak reference中创建,即是下例中的b():

1
2
3
4
>>> a==b()
True
>>> b().show()
None

请注意当我们删除strong reference的时候,对象将立即被销毁。

1
2
>>>dela
destroyed

如果试图在对象被摧毁之后通过weak reference使用对象,则会返回None:

1
2
>>> b()isNone
True

若是使用weakref.proxy,就能提供相对于weakref.ref更透明的可选操作。同样是使用一个strong reference作为第一个参数并且返回一个weak reference,proxy更像是一个strong reference,但当对象不存在时会抛出异常。

1
2
3
4
5
6
7
8
9
10
11
12
>>> a=Foo()
created
>>> b=weakref.proxy(a)
>>> b.store('fish')
>>> b.show()
fish
>>>dela
destroyed
>>> b.show()
Traceback (most recent call last):
  File"", line1,in?
ReferenceError: weakly-referencedobjectno longer exists

完整的例子:

引用计数器是由Python的垃圾回收器使用的,当一个对象的应用计数器变为0,则其将会被垃圾回收器回收。

最好将weak reference用于开销较大的对象,或避免循环引用(虽然垃圾回收器经常干这种事情)。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
importweakref
importgc
 
classMyObject(object):
    defmy_method(self):
        print'my_method was called!'
 
obj=MyObject()
r=weakref.ref(obj)
 
gc.collect()
assertr()isobj#r() allows you to access the object referenced: it's there.
 
obj=1#Let's change what obj references to
gc.collect()
assertr()isNone#There is no object left: it was gc'ed.

提示:只有library模块中定义的class instances、functions、methods、sets、frozen sets、files、generators、type objects和certain object types(例如sockets、arrays和regular expression patterns)支持weakref。内建函数以及大部分内建类型如lists、dictionaries、strings和numbers则不支持。

6. Copy()

通过shallow或deep copy语法提供复制对象的函数操作。

shallow和deep copying的不同之处在于对于混合型对象的操作(混合对象是包含了其他类型对象的对象,例如list或其他类实例)。

  • 对于shallow copy而言,它创建一个新的混合对象,并且将原对象中其他对象的引用插入新对象。
  • 对于deep copy而言,它创建一个新的对象,并且递归地复制源对象中的其他对象并插入新的对象中。

普通的赋值操作知识简单的将心变量指向源对象。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
importcopy
 
a=[1,2,3]
b=[4,5]
 
c=[a,b]
 
# Normal Assignment
d=c
 
printid(c)==id(d)         # True - d is the same object as c
printid(c[0])==id(d[0])   # True - d[0] is the same object as c[0]
 
# Shallow Copy
d=copy.copy(c)
 
printid(c)==id(d)         # False - d is now a new object
printid(c[0])==id(d[0])   # True - d[0] is the same object as c[0]
 
# Deep Copy
d=copy.deepcopy(c)
 
printid(c)==id(d)         # False - d is now a new object
printid(c[0])==id(d[0])   # False - d[0] is now a new object

shallow copy (copy())操作创建一个新的容器,其包含的引用指向原对象中的对象。

deep copy (deepcopy())创建的对象包含的引用指向复制出来的新对象。

复杂的例子:

假定我有两个类,名为Manager和Graph,每个Graph包含了一个指向其manager的引用,而每个Manager有一个指向其管理的Graph的集合,现在我们有两个任务需要完成:

1) 复制一个graph实例,使用deepcopy,但其manager指向为原graph的manager。

2) 复制一个manager,完全创建新manager,但拷贝原有的所有graph。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
importweakref, copy
 
classGraph(object):
    def__init__(self, manager=None):
        self.manager=NoneifmanagerisNoneelseweakref.ref(manager)
    def__deepcopy__(self, memodict):
        manager=self.manager()
        returnGraph(memodict.get(id(manager), manager))
 
classManager(object):
    def__init__(self, graphs=[]):
        self.graphs=graphs
        forginself.graphs:
            g.manager=weakref.ref(self)
 
a=Manager([Graph(), Graph()])
b=copy.deepcopy(a)
 
if[g.manager()isbforginb.graphs]:
    printTrue# True
 
ifcopy.deepcopy(a.graphs[0]).manager()isa:
    printTrue# True

7. Pprint()

Pprint模块能够提供比较优雅的数据结构打印方式,如果你需要打印一个结构较为复杂,层次较深的字典或是JSON对象时,使用Pprint能够提供较好的打印结果。

假定你需要打印一个矩阵,当使用普通的print时,你只能打印出普通的列表,不过如果使用pprint,你就能打出漂亮的矩阵结构

如果

1
2
3
4
5
6
7
8
9
importpprint
 
matrix=[ [1,2,3], [4,5,6], [7,8,9] ]
a=pprint.PrettyPrinter(width=20)
a.pprint(matrix)
 
# [[1, 2, 3],
#  [4, 5, 6],
#  [7, 8, 9]]

额外的知识

一些基本的数据结构

1. 单链链表

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
classNode:
    def__init__(self):
        self.data=None
        self.nextNode=None
 
    defset_and_return_Next(self):
        self.nextNode=Node()
        returnself.nextNode
 
    defgetNext(self):
        returnself.nextNode
 
    defgetData(self):
        returnself.data
 
    defsetData(self, d):
        self.data=d
 
classLinkedList:
    defbuildList(self, array):
        self.head=Node()
        self.head.setData(array[0])
        self.temp=self.head
        foriinarray[1:]:
            self.temp=self.temp.set_and_return_Next()
            self.temp.setData(i)
            self.tail=self.temp
        returnself.head
    defprintList(self):
        tempNode=self.head
        while(tempNode!=self.tail):
            print(tempNode.getData())
            tempNode=tempNode.getNext()
        print(self.tail.getData())
myArray=[3,5,4,6,2,6,7,8,9,10,21]
 
myList=LinkedList()
myList.buildList(myArray)
myList.printList()

2. 用Python实现的普林姆算法

译者注:普林姆算法(Prims Algorithm)是图论中,在加权连通图中搜索最小生成树的算法。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
fromcollectionsimportdefaultdict
fromheapqimportheapify, heappop, heappush
 
defprim( nodes, edges ):
    conn=defaultdict(list)
    forn1,n2,cinedges:
        conn[ n1 ].append( (c, n1, n2) )
        conn[ n2 ].append( (c, n2, n1) )
 
    mst=[]
    used=set( nodes[0] )
    usable_edges=conn[ nodes[0] ][:]
    heapify( usable_edges )
 
    whileusable_edges:
        cost, n1, n2=heappop( usable_edges )
        ifn2notinused:
            used.add( n2 )
            mst.append( ( n1, n2, cost ) )
 
            foreinconn[ n2 ]:
                ife[2]notinused:
                    heappush( usable_edges, e )
    returnmst
 
#test
nodes=list("ABCDEFG")
edges=[ ("A","B",7), ("A","D",5),
          ("B","C",8), ("B","D",9), ("B","E",7),
      ("C","E",5),
      ("D","E",15), ("D","F",6),
      ("E","F",8), ("E","G",9),
      ("F","G",11)]
 
print"prim:", prim( nodes, edges )

本文转载自:http://blog.jobbole.com/65218/

共有 人打赏支持
好铁
粉丝 34
博文 264
码字总数 78066
作品 0
朝阳
程序员
5本必读Python入门书籍,你都看过吗?(附福利)

今天技术学派为大家准备了5本Python入门书籍,除了书籍小编还整理了3个常用的资源网站分享给大家。 1.Python基础教程 《Python基础教程》是经典的Python入门教程书籍,本书层次鲜明,结构严谨...

Python燕大侠 ⋅ 06/07 ⋅ 0

大数据分析挖掘学习方向?数据分析师的就业前景怎么样?

加米谷数据分析挖掘课程明细,从理论到云端实操环境到项目实战,手把手教您从0掌握数据分析与挖掘技术,带您走进数据时代。 第一阶段(python基础) python入门:1、Python版本特性介绍2、P...

加米谷大数据 ⋅ 04/17 ⋅ 0

良心推荐:一份20周学习计算机科学的经验贴(附资源)

雷锋网按:这里是,油管Artificial Intelligence Education专栏,原作者Siraj Raval授权雷锋字幕组编译。 原标题 Computer Science Curriculum 翻译 | 王飞 整理 | 凡江 这是一份五个月(20个...

雷锋字幕组 ⋅ 05/08 ⋅ 0

一个月入门Python爬虫,快速获取大规模数据

数据是创造和决策的原材料,高质量的数据都价值不菲。而利用爬虫,我们可以获取大量的价值数据,经分析可以发挥巨大的价值,比如: 豆瓣、知乎:爬取优质答案,筛选出各话题下热门内容,探索...

Python开发者 ⋅ 04/25 ⋅ 0

人人都能学会的python编程教程(基础篇)完整版

人人都能学会的python编程教程1:第一行代码 人人都能学会的python编程教程2:数据类型和变量 人人都能学会的python编程教程3:字符串和编码 人人都能学会的python编程教程4:关系运算符与循...

编程老司机 ⋅ 05/10 ⋅ 0

python掀起了全民学习的热潮?

1、 要说这两年最火的关键词,一定是大数据和人工智能,连国务院都在去年7月发布了我国首个人工智能国家规划——《新一代人工智能发展规划》,从国家层面对人工智能进行顶层设计。 人工智能时...

qq_41597912 ⋅ 04/13 ⋅ 0

人工智能“网红”编程语言Python进入教材,我们应该准备些什么?

除了要学英语外,对于一些高中生,甚至小学生来说,他们未来很可能还要多学一门“外语”—— Python。 在程序员的世界中,有句广为流传的话,叫“人生苦短,快用Python”。这句话非常形象地说...

python达人 ⋅ 05/25 ⋅ 0

人人都能学会的python编程教程15:高级特性2

生成器 如果你想要一百万个数,而这些数里只有一百个数是你经常要用的,剩下的都几乎不怎么会用到,那么如果直接把这一百万个数全部放在list中是不明智的因为这会浪费较多存储空间,生成器就...

编程老司机 ⋅ 05/10 ⋅ 0

想用 Python 找到一份好工作?这4种工作最热门!

身边有不少朋友最近都开始学习python,大多都在学了一两个月之后来问小编,我现在已经入行了,能去找什么样的工作呢? 小编只能说: 入行!=找工作 那么,自学python的人,如何才能找到满意的工...

python达人 ⋅ 05/16 ⋅ 0

6个最高效的语言处理Python库,你用过几个?

最近一段时间Python已经成为数据科学行业中大火的编程语言,今天技术学派收集了一些较为高效的语言处理Python库。下面分享给大家。 1.NLTK NLTK是构建Python程序以处理人类语言数据的领先平台...

Python燕大侠 ⋅ 06/05 ⋅ 0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

如何优雅的编程——C语言界面的一点小建议

我们鼓励在编程时应有清晰的哲学思维,而不是给予硬性规则。我并不希望你们能认可所有的东西,因为它们只是观点,观点会随着时间的变化而变化。可是,如果不是直到现在把它们写在纸上,长久以...

柳猫 ⋅ 16分钟前 ⋅ 0

从零手写 IOC容器

概述 IOC (Inversion of Control) 控制反转。熟悉Spring的应该都知道。那么具体是怎么实现的呢?下面我们通过一个例子说明。 1. Component注解定义 package cn.com.qunar.annotation;impo...

轨迹_ ⋅ 17分钟前 ⋅ 0

系统健康检查利器-Spring Boot-Actuator

前言 实例由于出现故障、部署或自动缩放的情况,会进行持续启动、重新启动或停止操作。它可能导致它们暂时或永久不可用。为避免问题,您的负载均衡器应该从路由中跳过不健康的实例,因为它们...

harries ⋅ 18分钟前 ⋅ 0

手把手教你搭建vue-cli脚手架-详细步骤图文解析[vue入门]

写在前面: 使用 vue-cli 可以快速创建 vue 项目,vue-cli很好用,但是在最初搭建环境安装vue-cli及相关内容的时候,对一些人来说是很头疼的一件事情,本人在搭建vue-cli的项目环境的时候也是...

韦姣敏 ⋅ 28分钟前 ⋅ 0

12c rman中输入sql命令

12c之前版本,要在rman中执行sql语句,必须使用sql "alter system switch logfile"; 而在12c版本中,可以支持大量的sql语句了: 比如: C:\Users\zhengquan>rman target / 恢复管理器: Release 1...

tututu_jiang ⋅ 42分钟前 ⋅ 0

Nginx的https配置记录以及http强制跳转到https的方法梳理

Nginx的https配置记录以及http强制跳转到https的方法梳理 一、Nginx安装(略) 安装的时候需要注意加上 --with-httpsslmodule,因为httpsslmodule不属于Nginx的基本模块。 Nginx安装方法: ...

Yomut ⋅ 59分钟前 ⋅ 0

SpringCloud Feign 传递复杂参数对象需要注意的地方

1.传递复杂参数对象需要用Post,另外需要注意,Feign不支持使用GetMapping 和PostMapping @RequestMapping(value="user/save",method=RequestMethod.POST) 2.在传递的过程中,复杂对象使用...

@林文龙 ⋅ 今天 ⋅ 0

如何显示 word 左侧目录大纲

打开word说明文档,如下图,我们发现左侧根本就没有目录,给我们带来很大的阅读障碍 2 在word文档的头部菜单栏中,切换到”视图“选项卡 3 然后勾选“导航窗格”选项 4 我们会惊奇的发现左侧...

二营长意大利炮 ⋅ 今天 ⋅ 0

智能合约编程语言Solidity之线上开发工具

工具地址:https://ethereum.github.io/browser-solidity/ 实例实验: 1.创建hello.sol文件 2.调试输出结果

硅谷课堂 ⋅ 今天 ⋅ 0

ffmpeg 视频格式转换

转 Mp4 格式 #> ffmpeg -i input.avi -c:v libx264 output.mp4#> ffmpeg -i input.avi -c:v libx264 -strict -2 output.mp4#> ffmpeg -i input.avi -c:v libx264 -strict -2 -s 1......

Contac ⋅ 今天 ⋅ 0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

返回顶部
顶部