鼻翼整形费用,给未来自己的一封信,美女恐龙妹
链表：由一系列不必再内存中相连的结构组成，每一个结构均含有表元素和指向后继结构的指针。
与数组、列表的主要区别：
优点：
缺点：
实现一个链表：
我要评论 1 class node(object):
2 """定义链表元素类"""
3 def __init__(self, value=none, next=none):
4 self.value = value
5 self.next = next
6
7
8 class singlelinklist(object):
9 def __init__(self):
10 self.head = node() # 头节点没有数据，仅作为链表访问的起点
11 self.tail = self.head
12 self.length = 0
13
14 def append(self, value):
15 node = node(value)
16 self.tail.next = node
17 self.tail = node
18 self.length += 1
19
20 def appendleft(self, value):
21 """将节点插入到head后面"""
22 node = node(value)
23 if self.head.next is not none: # 判断链表是否插入过元素
24 firstnode = self.head.next
25 node.next = firstnode
26 self.head.next = node
27 else:
28 self.head.next = node
29 self.tail = node
30 self.length += 1
31
32 def iter_node(self):
33 """构造生成器用于遍历链表节点"""
34 curnode = self.head.next
35 while curnode is not self.tail:
36 yield curnode
37 curnode = curnode.next
38 yield curnode
39
40 def __iter__(self):
41 """通过生成器，使链表可被for循环遍历"""
42 for node in self.iter_node():
43 yield node.value
44
45 def __len__(self):
46 return self.length
47
48 def remove(self, value):
49 for curnode in self.iter_node():
50 if curnode.next is not none and curnode.next.value == value:
51 node = curnode.next
52 curnode.next = node.next
53 del node
54 self.length -= 1
55 return 0 # 删除成功
56 return -1 # 删除失败
57
58 def popleft(self):
59 """删除链表第一个节点"""
60 if self.length > 0:
61 node = self.head.next
62 self.head.next = node.next
63 self.length -= 1
64 return node.value
65 else:
66 raise exception('linklist is empty')
以上代码定义了一个单链表类，并实现了常用的添加、删除链表元素的方法。
双端链表：单链表无法满足有些倒叙遍历链表的需求，因此需要双端链表。双端链表的实现只需要在单链表的基础上增加一个指向前一节点的指针即可，却极大的简化了某些针对节点的操作，如删除某节点的时间复杂度直接变为o(1)。
循环双端链表：将双端链表的头节点与尾节点链接起来，就是循环双端链表。
代码实现：
1 class node(object): 2 def __init__(self, value=none, next=none, prev=none): 3 self.value, self.next, self.prev = value, next, prev 4 5 6 class circulardoublelinklist(object): 7 def __init__(self): 8 self.head = node() # 头节点没有数据，仅作为链表访问的起点 9 self.tail = self.head 10 self.length = 0 11 12 def append(self, value): 13 node = node(value, self.head, self.tail) 14 self.tail.next = node 15 self.head.prev = node 16 self.tail = node 17 self.length += 1 18 19 def appendleft(self, value): 20 node = node(value) 21 if self.head.next is not none: 22 nextnode = self.head.next 23 node.next = nextnode 24 node.prev = self.head 25 nextnode.prev = node 26 self.head.next = node 27 else: 28 node.prev = self.head 29 node.next = self.head 30 self.head.next = node 31 self.head.prev = node 32 self.tail = node 33 self.length += 1 34 35 def iter_node(self): 36 """构造生成器用于遍历链表节点""" 37 curnode = self.head.next 38 while curnode is not self.tail: 39 yield curnode 40 curnode = curnode.next 41 yield curnode 42 43 def __iter__(self): 44 """通过生成器，使链表可被for循环遍历""" 45 for node in self.iter_node(): 46 yield node.value 47 48 def __len__(self): 49 return self.length 50 51 def remove(self, node): 52 """注意参数是node""" 53 prevnode = node.prev 54 nextnode = node.next 55 if node is self.tail: 56 self.tail = prevnode 57 prevnode.next = nextnode 58 nextnode.prev = prevnode 59 self.length -= 1 60 61 def iter_node_reverse(self): 62 curnode = self.tail 63 while curnode is not self.head: 64 yield curnode 65 curnode = curnode.prev
如对本文有疑问，请在下面进行留言讨论，广大热心网友会与你互动！！ 点击进行留言回复
python求numpy中array按列非零元素的平均值案例
网友评论