python数据结构之线性表
python内置了很多高级数据结构，list，dict，tuple，string，set等，在使用的时候十分舒心。但是，如果从一个初学者的角度利用python学习数据结构时，这些高级的数据结构可能给我们以迷惑。
比如，使用list实现queue的时候，入队操作append()时间复杂度可以认为是O(1),但是，出队操作pop(0)的时间复杂度就是O(n)。
如果是想利用python学学数据结构的话，我觉得还是自己实现一遍基本的数据结构为好。
1.链表
在这里，我想使用类似于c语言链式存储的形式，借助于class，分别构成无序链表以及有序链表。
我们先看看链表节点的定义：
class ListNode(object):
def __init__(self, data):
self.data = data
self.next = None
def getData(self):
return self.data
def setData(self, newData):
self.data = newData
def getNext(self):
return self.next
def setNext(self, nextNode):
self.next = nextNode
利用链表节点，组成无序链表类：
class UnorderedList(object):
def __init__(self):
self.head = None
def getHead(self):
return self.head
def isEmpty(self):
return self.head is None
def add(self, item):
node = ListNode(item)
node.next = self.head
self.head = node # the head is the most recently added node
def size(self):
current = self.head
count = 0
while current is not None:
count += 1
current = current.getNext()
return count
def search(self, item):
current = self.head
found = False
while current is not None and not found:
if current.getData() == item:
found = True
else:
current = current.getNext()
return found
def append(self, item):
node = ListNode(item)
if self.isEmpty():
self.head = node
else:
current = self.head
while current.getNext() is not None:
current = current.getNext()
current.setNext(node)
def remove(self, item):
current = self.head
previous = None
found = False
while not found:
if current.getData() == item:
found = True
else:
previous = current
current = current.getNext()
if previous is None:
self.head = current.getNext()
else:
previous.setNext(current.getNext())
在上面的链表中，每次添加元素都直接添加在链表头部，add()的时间复杂度为O(1)，而append()操作在队尾，其时间复杂度为O(n)。有没有前后加入操作的时间复杂度都为O(1)的链表呢，当然是有的：
class UnorderedList(object):
def __init__(self):
self.head = None
self.tail = None
def getHead(self):
return self.head
def isEmpty(self):
return self.head is None and self.tail is None
def add(self, item):
node = ListNode(item)
if self.isEmpty():
self.head = self.tail = node
else:
node.next = self.head
self.head = node # the head is the most recently added node
def size(self):
current = self.head
count = 0
while current is not None:
count += 1
current = current.getNext()
return count
def search(self, item):
current = self.head
found = False
while current is not None and not found:
if current.getData() == item:
found = True
else:
current = current.getNext()
return found
def append(self, item):
node = ListNode(item)
self.tail.setNext(node)
self.tail = node
def remove(self, item):
current = self.head
previous = None
found = False
while not found:
if current.getData() == item:
found = True
else:
previous = current
current = current.getNext()
if current.getNext() is None:
self.tail = previous
if previous is None:
self.head = current.getNext()
else:
previous.setNext(current.getNext())
对无序链表类加入一个属性，引用链表末尾节点，即可。做出了这样的改变，在add和remove操作也应作出相应变化。
下面再看看有序链表。有序链表在插入节点的时候便寻找适合节点的位置。
class OrderedList(object):
def __init__(self):
self.head = None
def isEmpty(self):
return self.head is None
def search(self, item):
stop = False
found = False
current = self.head
while current is not None and not found and not stop:
if current.getData() > item:
stop = True
elif current.getData() == item:
found = True
else:
current = current.getNext()
return found
def add(self, item):
previous = None
current = self.head
stop = False
while current is not None and not stop:
if current.getData() >item:
stop = True
else:
previous = current
current = current.getNext()
node = ListNode(item)
if previous is None:
node.getNext(current)
self.head = node
else:
previous.setNext(node)
node.setNext(current)
2.栈stack
对于栈来说，python内置的列表已经可以满足栈的要求。
入栈操作为append(),出栈操作为pop()。它们的时间复杂度都为O(1).
class Stack(object):
def __init__(self):
self._items = []
def is_empty(self):
return self._items == []
def push(self, item):
self._items.append(item)
def pop(self):
return self._items.pop()
def peek(self):
return self._items[-1]
当然了，我们也可以自己实现链栈，跟链表的实现类似。
class StackNode(object):
"""docstring for StackNode"""
def __init__(self, value):
self.value = value
self.next = None
class Stack(object):
"""docstring for Stack"""
def __init__(self, top=StackNode(None)):
self.top = top
def get_top(self):
return self.top
def is_empty(self):
return self.top.value is None
def push(self, val):
node = StackNode(val)
node.next = self.top
self.top = node
return
def pop(self):
if self.is_empty():
print("Stack is Empty, cannot pop anymore.\n")
return
node = self.top
self.top = self.top.next
return node
3.队列queue
队列如果利用链表实现的话会，出现文章开头提及的问题。
所以队列可以用链表实现。
class QueueNode(object):
def __init__(self, value):
self.value = value
self.next = None
class Queue(object):
def __init__(self):
self.front = None
self.rear = None
def is_empty(self):
return self.front is None and self.rear is None
def enqueue(self, num):
node = QueueNode(num)
if self.is_empty():
self.front = node
self.rear = node
else:
self.rear.next = node
self.rear = node
def dequeue(self):
if self.front is self.rear:
node = self.front
self.front = None
self.rear = None
return node.value
else:
node = self.front
self.front = node.next
return node.value
在python的库中，比如collections以及Queue中都有deque模块。
deque模块顾名思义，可以做双端队列。所以，deque模块也可以做队列，和栈。
dq = deque([1,2,3,4,5,6,7,8,9])
dq.pop() # pop 9
dq.popleft() #pop 1
dq.apend(9) # append 9
dq.appendleft(1) #insert 1 in index 0
在多线程，多进程编程时，经常使用Queue模块的Queue类。
其实：假设q=Queue.Queue()
那么 q.queue就是一个deque。
这个以后再谈。
本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)
