本文基于Python实现以下几种常用的数据结构，
栈 —基于List实现
class Stack:
'栈'
def __init__(self):
self.__arr=[]
self.__size = 0
def push(self, obj):
'入栈'
self.__arr.append(obj)
self.__size += 1
def pop(self):
'出栈'
if self.__size > 0:
val = self.__arr[self.__size - 1]
del self.__arr[self.__size - 1]
self.__size -= 1
return val
return None
def Count(self):
'栈大小'
return self.__size
队列
class QueueNode:
def __init__(self, v):
self.__data = v
self.__next = None
def GetVal(self):
return self.__data
def AddNextNode(self, v):
self.__next = QueueNode(v)
def GetNextNode(self):
return self.__next
def __del__(self):
class_name = self.__class__.__name__
class Queue:
'队列'
def __init__(self):
self.__front = None
self.__rear = None
self.__size = 0
def enqueue(self, v):
'入队'
if self.__size == 0:
qnode = QueueNode(v)
self.__front = qnode
self.__rear = qnode
else:
self.__rear.AddNextNode(v)
self.__rear = self.__rear.GetNextNode()
self.__size += 1
def dequeue(self):
'出队'
if self.__size != 0:
val = self.__front.GetVal()
self.__front = self.__front.GetNextNode()
self.__size -= 1
return val
return None
def Count(self):
'队列大小'
return self.__size
def __del__(self):
class_name = self.__class__.__name__
优先队列
class PriorityQueueNode:
def __init__(self, v, priority):
self.__data = v
self.__priority = priority
self.__next = None
def GetVal(self):
return self.__data
def GetPriority(self):
return self.__priority
def AddNextNode(self, v, priority):
self.__next = PriorityQueueNode(v, priority)
def GetNextNode(self):
return self.__next
def SetNextNode(self, node):
self.__next = node
def __del__(self):
class_name = self.__class__.__name__
#print class_name, "Dispose"
class PriorityQueue:
'队列'
def __init__(self):
node = PriorityQueueNode(None, None)
self.__front = node
self.__rear = node
self.__size = 0
def push(self, v, priority):
'入队'
nd = self.__front.GetNextNode()
prend = self.__front
while None != nd and nd.GetPriority() >= priority:
prend = nd
nd = nd.GetNextNode()
qnode = PriorityQueueNode(v, priority)
qnode.SetNextNode(nd)
prend.SetNextNode(qnode)
if nd == None:
self.__rear = qnode
self.__size += 1
def pop(self):
'出队'
if self.__size != 0:
val = self.__front.GetNextNode().GetVal()
priority = self.__front.GetNextNode().GetPriority()
self.__front.SetNextNode(self.__front.GetNextNode().GetNextNode())
self.__size -= 1
return val
return None
def Count(self):
'队列大小'
return self.__size
def __del__(self):
class_name = self.__class__.__name__
二叉树
class TreeNode:
def __init__(self, v):
self.__data = v
self.__left = None
self.__right = None
def SetVal(self,v):
self.__data = v
def GetVal(self):
return self.__data
def GetLeftNode(self):
return self.__left
def GetRightNode(self):
return self.__right
def AddLeftNode(self, v):
nd = TreeNode(v)
self.__left = nd
def AddRightNode(self, v):
nd = TreeNode(v)
self.__right = nd
def __del__(self):
class_name = self.__class__.__name__
class BinaryTree:
def __init__(self):
self.__root = TreeNode(None)
self.__size = 0
self.__InOrderList = []
self.__PreOrderList = []
self.__PostOrderList = []
def AddChildNode(self, v):
if self.__size == 0:
self.__root.SetVal(v)
else:
nd = self.__root
endnode = None
while None != nd:
if v > nd.GetVal():
endnode = nd
nd = nd.GetRightNode()
else:
endnode = nd
nd = nd.GetLeftNode()
if v > endnode.GetVal():
endnode.AddRightNode(v)
else:
endnode.AddLeftNode(v)
self.__size += 1
def Count(self):
return self.__size
def __preOrder(self, nd):
if None != nd:
self.__PreOrderList.append(nd.GetVal())
self.__preOrder(nd.GetLeftNode())
self.__preOrder(nd.GetRightNode())
def PreOrder(self):
'树的先序遍历'
self.__PreOrderList = []
self.__preOrder(self.__root)
return self.__PreOrderList
def __inOrder(self, nd):
if None != nd:
self.__inOrder(nd.GetLeftNode())
self.__InOrderList.append(nd.GetVal())
self.__inOrder(nd.GetRightNode())
def InOrder(self):
'树的中序遍历'
self.__InOrderList = []
self.__inOrder(self.__root)
return self.__InOrderList
def __postOrder(self, nd):
if None != nd:
self.__postOrder(nd.GetLeftNode())
self.__postOrder(nd.GetRightNode())
self.__PostOrderList.append(nd.GetVal())
def PostOrder(self):
'树的后序遍历'
self.__PostOrderList = []
self.__postOrder(self.__root)
return self.__PostOrderList
def __del__(self):
class_name = self.__class__.__name__
单链表
class LinkListNode:
def __init__(self, v):
self.__data = v
self.__next = None
def GetVal(self):
return self.__data
def AddNextNode(self, v):
self.__next = LinkListNode(v)
def SetNextNode(self, node):
self.__next = node
def GetNextNode(self):
return self.__next
def __del__(self):
class_name = self.__class__.__name__
class LinkList:
def __init__(self):
nd = LinkListNode(None)
self.__head = nd
self.__end = nd
self.__size = 0
def AddElements(self, datalist):
for d in datalist:
nd = LinkListNode(d)
self.__end.SetNextNode(nd)
self.__end = nd
self.__size += 1
def Insert(self, pos, v):
if pos - 1 > self.__size or pos < 1:
return
nd = LinkListNode(v)
tmp = self.__head
for idx in range(pos - 1):
tmp = tmp.GetNextNode()
nd.SetNextNode(tmp.GetNextNode())
tmp.SetNextNode(nd)
if pos == self.__size + 1:
self.__end = self.__end.GetNextNode()
self.__size += 1
def Remove(self, pos):
if pos > self.__size or pos < 1:
return
tmp = self.__head
for idx in range(pos - 1):
tmp = tmp.GetNextNode()
nd = tmp.GetNextNode()
tmp.SetNextNode(nd.GetNextNode())
nd.SetNextNode(None)
if pos == self.__size:
self.__end = tmp
self.__size -= 1
def Reverse(self):
if self.__size < 2:
return
self.__end = self.__head.GetNextNode()
nd = self.__head.GetNextNode()
p = nd.GetNextNode()
while p is not None:
nd.SetNextNode(p.GetNextNode())
p.SetNextNode(self.__head.GetNextNode())
self.__head.SetNextNode(p)
p = nd.GetNextNode()
def LinkListTolist(self):
lst = []
nd = self.__head.GetNextNode()
while nd is not None:
lst.append(nd.GetVal())
nd = nd.GetNextNode()
return lst
def Count(self):
return self.__size
双向链表
class DLinkListNode:
def __init__(self, v):
self.__data = v
self.__next = None
self.__pre = None
def GetVal(self):
return self.__data
def AddNextNode(self, v):
nd = DLinkListNode(v)
self.__next = nd
nd.__pre = self
def SetNextNode(self, node):
self.__next = node
node.__pre = self
def SetNextNone(self):
self.__next = None
def SetPreNode(self, node):
self.__pre = node
node.__next = self
def GetNextNode(self):
return self.__next
def GetPreNode(self):
return self.__pre
def __del__(self):
class_name = self.__class__.__name__
class DLinkList:
def __init__(self):
nd = DLinkListNode(None)
self.__head = nd
self.__end = nd
self.__size = 0
def AddElements(self, datalist):
for x in datalist:
nd = DLinkListNode(x)
self.__end.SetNextNode(nd)
self.__end = self.__end.GetNextNode()
self.__size += 1
def Insert(self, pos, v):
if pos - 1 > self.__size or pos < 1:
return
nd = DLinkListNode(v)
tmp = self.__head
for idx in range(pos - 1):
tmp = tmp.GetNextNode()
if pos - 1 == self.__size:
nd.SetNextNone()
else:
nd.SetNextNode(tmp.GetNextNode())
tmp.SetNextNode(nd)
if pos == self.__size + 1:
self.__end = self.__end.GetNextNode()
self.__size += 1
def Remove(self, pos):
if pos > self.__size or pos < 1:
return
tmp = self.__head
for idx in range(pos - 1):
tmp = tmp.GetNextNode()
nd = tmp.GetNextNode()
if nd == self.__end:
tmp.SetNextNone()
else:
tmp.SetNextNode(nd.GetNextNode())
if pos == self.__size:
self.__end = tmp
self.__size -= 1
def DLinkListTolist(self):
lst = []
nd = self.__head.GetNextNode()
while nd is not None:
lst.append(nd.GetVal())
nd = nd.GetNextNode()
return lst
def DLinkListToReverselist(self):
lst = []
nd = self.__end
while nd != self.__head:
lst.append(nd.GetVal())
nd = nd.GetPreNode()
return lst
