算法与数据结构python实现-栈、链表、队列
| 阿里云国内75折 回扣 微信号：monov8 |
| 阿里云国际，腾讯云国际，低至75折。AWS 93折 免费开户实名账号 代冲值 优惠多多 微信号：monov8 飞机：@monov6 |
目录标题
栈
数据结构是计算机存储、组织数据的方式
栈后进先出。进栈和出栈时间复杂度都是O(1)
#创建一个Stack类
Class Stack(object):
def __init__(self,limit=10):
self.stack = [] #存放元素
self.limit = limit #栈容量极限
#进栈push
def push(self,data):
if len(self.stack)>= self.limit
raise IndexError('超出栈容量极限')
self.stack.append(data)
#退栈pop
def pop(self):
if self.stack:
return self.stack.pop()
else:
return IndexError('空栈不能被弹出')
#查看栈最上面的元素peek
def peek(self):
if self.stack:
return self.stack[-1]
#判断是否为空栈is_empty
def is_empty(self):
return not bool(self.stack)
#栈的大小
def size(self):
return len(self.stack)
链表
链表(linked_list)是物理存储单元上非连续的、非顺序的存储结构数据元素的逻辑顺序是通过链表的指针地址实现每个元素包含两个结点一个是存储元素的数据域 (内存空间)另一个是指向下一个结点地址的指针域。
根据指针的指向链表能形成不同的结构例如单链表双向链表循环链表等。
#创建一个Node的类作为基础数据结构链点
class Node:
def __init__(self,data):
self.data = data #对应元素值
self.next = Node #下一个链接的链点
#创建 Linked_List 类
class Linked_List:
def __init__(self,head=None): #链表初始化函数
self.head = head #链表头部
def append(self,new_element): #在链表后添加一个元素
current = self.head
#头部节点存在时
if self.head:
while current.next:
current = current.next
current.next = new_element
#头部节点不存在时
else:
self.head = new_element
def is_empty(self): #判断链表是否为空
return not self.head
def insert(self,position,new_element): #在链表中指定位置插入元素
if position <0 or position >self.get_length():
raise IndexError('insert 插入时key的值超过了范围')
temp = self.head
if position == 0:
new_element.next = temp
self.head = new_element
return
i =0
while i<position:
pre = temp
temp = temp.next
i+=1
pre.next = nex_element
new_element.next = temp
def remove(self,position): #删除指定索引的链表元素
if position<0 or position >self.get_length()-1:
raise IndexError('删除元素的索引超出范围')
i = 0
temp = self.head
while temp!=None: #当链表非空时才能执行删除操作
if position == 0:
self.head = temp.next
temp.next = None
return
pre = temp
temp = temp.next
i+=1
if i == position:
pre.next = temp.next
temp.next = None
return
def get_length(self): #返回链表长度
temp = self.head
length = 0
while temp !=None: #指针进一位计数加一
length = length+1
temp = temp.next
return length
def print_list(self): #遍历链表并将元素依次打印出来
print('linked_list:')
temp = self.head # 头部结点赋值给临时变量 temp
while temp is not None:
print('temp.data')
temp = temp.next
def reverse(self): #将链表反转
prev = None
current = self.head
while current:
next_node = current.next
current.next = prev
prev = current
self.head = prev
def initlist(self,data_list): #将列表转换为链表
self.head = None(data_list[0])
temp = self.head
for i in data_list[1:]:
node = Node(i)
temp.next = node
temp = temp.next
append思路分链表是否为空两种情况为空时直接指向新元素不为空时先循环到链表最后再指向
insert思路
1先判断要插入的位置是否在链表的索引范围内。
2当插入的位置是头结点即索引为 0时将插入元素的 next 属性指向老的头结点并将新的元素赋值给头结点
3当要插入结点的位置不在 0 时找到要插入的位置插入新结点
remove思路
1先判断要删除的元素索引是否存在如果不存在抛出错误
2接着判断链表非空时才能执行删除操作。
3当要删除的是头结点时即索引为 0做特殊情况处理。-将头结点的后一个结点赋值给新的头结点再将之前的头结点指向 `None
4其他情况时通过循环找到要删除的结点。
5最后要做的就是把这个结点删除掉。
复杂度分析
对于插入和移除而言时间复杂度都为 O(1)but 对于搜索操作而言不管从链表的头部还是尾部都需要遍历 O(n)
所以最好复杂度为 O(1)最坏复杂度为 O(n)平均复杂度为 O(n)
双向链表
双向链表Double_linked_list也叫双链表是链表的一种它的每个数据结点中都有两个指针分别指向直接后继和直接前驱。
所以从双向链表中的任意一个结点开始都可以很方便地访问它的前驱结点和后继结点。
class Node(object):
# 双向链表节点
def __init__(self, item):
self.item = item
self.next = None
self.prev = None
class DLinkList(object):
# 双向链表
def __init__(self):
self._head = None
def is_empty(self):
# 判断链表是否为空
return self._head == None
def get_length(self):
# 返回链表的长度
cur = self._head
count = 0
while cur != None:
count = count+1
cur = cur.next
return count
def travel(self):
# 遍历链表
cur = self._head
while cur != None:
print(cur.item)
cur = cur.next
print("")
def add(self, item):
# 头部插入元素
node = Node(item)
if self.is_empty():
# 如果是空链表将 node 赋值给 _head
self._head = node
else:
# 将 node 的 next 属性指向头节点 _head
node.next = self._head
# 将头节点 _head 的 prev 属性指向 node
self._head.prev = node
# 将 node 赋值给 _head
self._head = node
def append(self, item):
# 尾部插入元素
node = Node(item)
if self.is_empty():
# 如果是空链表将 node 赋值给 _head
self._head = node
else:
# 循环移动到链表尾部结点的位置
cur = self._head
while cur.next != None:
cur = cur.next
# 将尾结点 cur 的 next 属性指向 node
cur.next = node
# 将 node 的 prev 属性指向 cur
node.prev = cur
def search(self, item):
# 查找元素是否存在
cur = self._head
while cur != None:
if cur.item == item:
return True
cur = cur.next
return False
def insert(self, pos, item):
# 在指定位置添加节点
if pos <= 0:
self.add(item)
elif pos > (self.length()-1):
self.append(item)
else:
node = Node(item)
cur = self._head
count = 0
# 移动到指定位置的前一个位置
while count < (pos-1):
count += 1
cur = cur.next
# 将 node 的 prev 属性指向 cur
node.prev = cur
# 将 node 的 next 属性指向 cur 的下一个节点
node.next = cur.next
# 将 cur 的下一个节点的 prev 属性指向 node
cur.next.prev = node
# 将 cur 的 next 指向 node
cur.next = node
def remove(self, item):
# 删除元素
if self.is_empty():
return
else:
cur = self._head
if cur.item == item:
# 如果首节点的元素即是要删除的元素
if cur.next == None:
# 如果链表只有这一个节点
self._head = None
else:
# 将第二个节点的 prev 属性设置为 None
cur.next.prev = None
# 将 _head 指向第二个节点
self._head = cur.next
return
while cur != None:
if cur.item == item:
# 将 cur 的前一个节点的 next 指向 cur 的后一个节点
cur.prev.next = cur.next
# 将 cur 的后一个节点的 prev 指向 cur 的前一个节点
cur.next.prev = cur.prev
break
cur = cur.next
案例交换单链表里两个链点
要求交换两个链点在链表中的位置不改变其他链点在链表中的位置
思路采用 insert 的思想对于要交换的两个链点 d1 d2各自声明新的 D1 D2 使 D1=d1, D2=d2。然后再根据 d1 d2 的位置改变索引的位置即完成交换的全部操作
class Node:
def __init__(self, data):
self.data = data
self.next = None
class Linkedlist:
def __init__(self):
self.head = None
def print_list(self): # 遍历链表并将元素依次打印出来
print("linked_list:")
temp = self.head
new_list = []
while temp is not None:
new_list.append(temp.data)
temp = temp.next
print(new_list)
def insert(self, new_data):
new_node = Node(new_data)
new_node.next = self.head
self.head = new_node
def swapNodes(self, d1, d2):
prevD1 = None
prevD2 = None
if d1 == d2:
return
else:
D1 = self.head
while D1 is not None and D1.data != d1:
prevD1 = D1
D1 = D1.next
D2 = self.head
while D2 is not None and D2.data != d2:
prevD2 = D2
D2 = D2.next
if D1 is None and D2 is None:
return
if prevD1 is not None:
prevD1.next = D2
else:
self.head = D2
if prevD2 is not None:
prevD2.next = D1
else:
self.head = D1
temp = D1.next
D1.next = D2.next
D2.next = temp
if __name__ == '__main__':
list = Linkedlist()
list.insert(5)
list.insert(4)
list.insert(3)
list.insert(2)
list.insert(1)
list.print_list()
list.swapNodes(1, 4)
print("After swapping")
list.print_list()
队列
只允许在表的前端front进行删除操作而在表的后端rear进行插入操作和栈一样队列是一种操作受限制的线性表。进行插入操作的端称为队尾进行删除操作的端称为队头。
先进先出。
队列有两种实现形式分为两种数组和链表。
链表形式
#创建一个 Node 的类
class Node(object):
def __init__(self,elem,next = None):
self.elem = elem # 表示对应的元素值
self.next = next # 表示下一个链接的链点
class Queue(object):
def __init__(self):
self.head = None # 头部链点
self.rear = None # 尾部链点
def is_empty(self): ## 判断队列是否为空
return self.head is None
def enqueue(self, elem): #往队尾添加一个 elem 元素
p = Node(elem) # 初始化一个新的点
if self.is_empty():
self.head = p # 队列头部为新的链点
self.rear = p # 队列尾部为新的链点
else:
self.rear.next = p # 队列尾部的后继是这个新的点
self.rear =p # 然后让队列尾部指针指向这个新的点
def dequeue(self): ##从队列头部删除一个元素
if self.is_empty(): # 判断队列是否为空
print('Queue_is_empty') # 若队列为空则退出 dequeue 操作
else:
result = self.head.elem # result为队列头部元素
self.head = self.head.next # 改变队列头部指针位置
return result # 返回队列头部元素
def peek(self): ##peek() 函数查看队列头部的元素
if self.is_empty(): # 判断队列是否为空
print('NOT_FOUND') # 为空则返回 NOT_FOUND
else:
return self.head.elem # 返回队列头部元素
def print_queue(self): ##print_queue() 函数打印队列的元素
print("queue:")
temp=self.head
myqueue=[] # 暂时存放队列数据
while temp is not None:
myqueue.append(temp.elem)
temp=temp.next
print(myqueue)
dequeue 函数思路
1先判断队列是否为空为空即退出 dequeue 操作不为空即继续后续操作
2将队列头部元素赋值到 result 变量里
3改变队列的头部指针的位置然后返回 resul
数组形式
class Queue():
def __init__(self):
self.entries = [] # 表示队列内的参数
self.length = 0 # 表示队列的长度
self.front = 0 # 表示队列头部位置
def enqueue(self, item):
self.entries.append(item) # 添加元素到队列里面
self.length = self.length + 1 # 队列长度增加 1
def dequeue(self):
self.length = self.length - 1 # 队列的长度减少 1
dequeued = self.entries[self.front] # 队首元素为 dequeued
self.front += 1 # 队首的位置减少 1
self.entries = self.entries[self.front:] # 队列的元素更新为退队之后的队列
return dequeued
def peek(self):
return self.entries[0] # 直接返回队列的队首元素