1. 数据结构
1.1 堆栈(Stack)
后进先出(LIFO, Last In First Out)
class Stack():
"""
栈的实现
如果使用 python 模块提供的数据结构
from pythonds.basic.stack import Stack
"""
def __init__(self): # 初始化
self.stack = []
def isEmpty(self): # 判空
return self.statck == []
def push(self, item): # 进栈
self.stack.append(item)
def pop(self): # 出栈
self.stack.pop()
def peek(self): # 返回栈顶项目
if not self.isEmpty():
return self.stack[-1]
1.2 队列、双端队列(Queue)
先进先出(FIFO, First In First Out), 通常使用链表或者数组来实现。
class Queue():
"""
队列的实现
如果使用 python 模块提供的数据结构
from pythonds.basic.queue import Queue
"""
def __init__(self): # 初始化
self.queue = []
def isEmpty(self):
return self.queue == []
def enqueue(self): # 入队
self.queue.insert(0, item)
def dequeue(self): # 出队
self.queue.pop()
def size(self):
return len(self.queue)
class Deque():
"""
双端队列的实现
如果使用 python 模块提供的数据结构
from pythonds.basic.deque import Deque
"""
def __init__(self):
self.deque = []
def isEmpty(self):
return self.deque == []
def add_front(self, item):
self.deque.append(item)
def remove_front(self):
self.deque.pop()
def add_rear(self):
self.deque.insert(0, item)
def remove_rear(self):
self.deque.remove(self.deque[0])
1.3 链表(Linked List)
链表（Linked list）是一种常见的基础数据结构，是一种线性表，但是并不会按线性的顺序存储数据，而是在每一个节点里存到下一个节点的指针(Pointer)。由于不必须按顺序存储，链表在插入的时候可以达到O(1)的复杂度，比另一种线性表顺序表快得多，但是查找一个节点或者访问特定编号的节点则需要O(n)的时间，而顺序表相应的时间复杂度分别是O(logn)和O(1)。
链表实现的基本构造块是节点(Node)。
class Node:
"""
节点
"""
def __init__(self, initdata):
self.data = initdata
self.next = None
def getData(self):
return self.data
def getNext(self):
return self.next
def setData(self, newdata):
self.data = newdata
def setNext(self, newnext):
self.next = newnext
无序链表
class UnorderedList:
"""
无序列表的 python 实现
"""
def ___init__():
self.head = None
def isEmpty():
return self.head == None
def add(self, item)：
temp = Node(item)
temp.setNext(self.head)
self.head = temp
def size(self):
current = self.head
count = 0
while current != None:
count = count + 1
current = current.getNext()
return count
def search(self, item):
current = self.head
found = False
while current != None and not found:
if current.getData() == item:
found = True
else:
current = current.getNext()
return found
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 == None: # 如果头结点便是查找的节点
self.head = current.getNext()
else:
previous.setNext(current.getNext())
有序列表
class OrderedList():
def __init__(self):
self.head = None
def isEmpty(self):
return self.head == None
def size(self):
count = 0
current = self.head
while current != None:
count += 1
current = current.getNext()
return count
def add(self, item):
current = self.head # 从头结点开始查询
previous = None # 记录前一个节点，头节点的前一个节点为 None
stop = False
while current != None and not stop: # 查找到可以插入的位置，跳出循环
if current.getData() > item:
stop = True
else:
previous = current # 更新前一个节点
current = current.getNext() # 查找下一个节点
temp = Node(item) # 创建新节点
if previous == None: # 插入在头结点位置
temp.setNext(self.head)
self.head = temp
else: # 插入在中间或者尾部
temp.setNext(current)
previous.setNext(temp)
def search(self, item):
# 包含查询、传入值，返回该值在链表中是否存在
current = self.head
found = False
stop = False
while current != None and not found and not stop:
if current.getData() == item:
found = True
else:
if current.getData() > item:
stop = True
else:
current = current.getNext()
return found
def remove(self, item):
current = self.head
previous = None
while current != None:
if current.getData() == data:
break
previous = current.getNext()
if previous == None:
self.head = current.getNext()
else:
previous.setNext(current.getNext())
