使用python实现数组、链表、队列、栈的方法

2023-08-04 06:07:05 306

引言

什么是数据结构？

数据结构是指相互之间存在着一种或多种关系的数据元素的集合和该集合中数据元素之间的关系组成。
简单来说，数据结构就是设计数据以何种方式组织并存储在计算机中。
比如：列表，集合和字典等都是数据结构
N.Wirth：“程序=数据结构+算法”

数据结构按照其逻辑结构可分为线性结构、树结构、图结构

线性结构：数据结构中的元素存在一对一的互相关系。
树结构：数据结构中的元素存在一对多的互相关系。
图结构：数据结构中的元素存在多对多的互相关系。

数组

在python中是没有数组的，有的是列表，它是一种基本的数据结构类型。

实现

classArray(object):
def__init__(self,size=32):
"""
:paramsize:长度
"""
self._size=size
self._items=[None]*size

#在执行array[key]时执行
def__getitem__(self,index):
returnself._items[index]

#在执行array[key]=value时执行
def__setitem__(self,index,value):
self._items[index]=value

#在执行len(array)时执行
def__len__(self):
returnself._size

#清空数组
defclear(self,value=None):
foriinrange(len(self._items)):
self._items[i]=value

#在遍历时执行
def__iter__(self):
foriteminself._items:
yielditem

使用

a=Array(4)
a[0]=1
print(a[0])#1

a.clear()
print(a[0])#None

a[0]=1
a[1]=2
a[3]=4
foriina:
print(i)#1,2,None,4

链表

链表中每一个元素都是一个对象，每一个对象被称为节点，包含有数据域value和指向下一个节点的指针next。

通过各个节点直接的相互链接，最终串成一个链表。

实现

classNode(object):
def__init__(self,value=None,next=None):
self.value,self.next=value,next

classLinkedList(object):
def__init__(self,size=None):
"""
:paramsize:intorNone,如果None，则该链表可以无限扩充
"""
self.size=size
#定义一个根节点
self.root=Node()
#尾节点始终指向最后一个节点
self.tail_node=None
self.length=0
def__len__(self):
returnself.length
defappend(self,value):
#size不为None,且长度大于等于size则链表已满
ifself.sizeandlen(self)>=self.size:
raiseException("LinkedListisfull")
#构建节点
node=Node(value)
tail_node=self.tail_node
#判断尾节点是否为空
iftail_nodeisNone:
#还没有append过，length=0，追加到root后
self.root.next=node
else:
#否则追加到最后一个节点的后边，并更新最后一个节点是append的节点
tail_node.next=node
#把尾节点指向node
self.tail_node=node
#长度加一
self.length+=1
#往左边添加
defappend_left(self,value):
ifself.sizeandlen(self)>=self.size:
raiseException("LinkedListisfull")
#构建节点
node=Node(value)
#链表为空，则直接添加设置
ifself.tail_nodeisNone:
self.tail_node=node
#设置头节点为根节点的下一个节点
head_node=self.root.next
#把根节点的下一个节点指向node
self.root.next=node
#把node的下一个节点指向原头节点
node.next=head_node
#长度加一
self.length+=1
#遍历节点
defiter_node(self):
#第一个节点
current_node=self.root.next
#不是尾节点就一直遍历
whilecurrent_nodeisnotself.tail_node:
yieldcurrent_node
#移动到下一个节点
current_node=current_node.next
#尾节点
ifcurrent_nodeisnotNone:
yieldcurrent_node
#实现遍历方法
def__iter__(self):
fornodeinself.iter_node():
yieldnode.value
#删除指定元素
defremove(self,value):
#删除一个值为value的节点，只要使该节点的前一个节点的next指向该节点的下一个
#定义上一个节点
perv_node=self.root
#遍历链表
forcurrent_nodeinself.iter_node():
ifcurrent_node.value==value:
#把上一个节点的next指向当前节点的下一个节点
perv_node.next=current_node.next
#判断当前节点是否是尾节点
ifcurrent_nodeisself.tail_node:
#更新尾节点tail_node
#如果第一个节点就找到了，把尾节点设为空
ifperv_nodeisself.root:
self.tail_node=None
else:
self.tail_node=perv_node
#删除节点，长度减一，删除成功返回1
delcurrent_node
self.length-=1
return1
else:
perv_node=current_node
#没找到返回-1
return-1
#查找元素，找到返回下标，没找到返回-1
deffind(self,value):
index=0
#遍历链表，找到返回index,没找到返回-1
fornodeinself.iter_node():
ifnode.value==value:
returnindex
index+=1
return-1
#删除第一个节点
defpopleft(self):
#链表为空
ifself.root.nextisNone:
raiseException("popfromemptyLinkedList")
#找到第一个节点
head_node=self.root.next
#把根节点的下一个节点，指向第一个节点的下一个节点
self.root.next=head_node.next
#获取删除节点的value
value=head_node.value
#如果第一个节点是尾节点,则把尾节点设为None
ifhead_nodeisself.tail_node:
self.tail_node=None
#长度减一，删除节点，返回该节点的值
self.length-=1
delhead_node
returnvalue
#清空链表
defclear(self):
fornodeinself.iter_node():
delnode
self.root.next=None
self.tail_node=None
self.length=0
#反转链表
defreverse(self):
#第一个节点为当前节点，并把尾节点指向当前节点
current_node=self.root.next
self.tail_node=current_node
perv_node=None
whilecurrent_node:
#下一个节点
next_node=current_node.next
#当前节点的下一个节点指向perv_node
current_node.next=perv_node
#当前节点的下一个节点为空，则把根节点的next指向当前节点
ifnext_nodeisNone:
self.root.next=current_node
#把当前节点赋值给perv_node
perv_node=current_node
#把下一个节点赋值为当前节点
current_node=next_node

使用

ll=LinkedList()

ll.append(0)
ll.append(1)
ll.append(2)
ll.append(3)
print(len(ll))#4
print(ll.find(2))#2
print(ll.find(-1))#-1

ll.clear()
print(len(ll))#0
print(list(ll))#[]

循环链表

双链表中每一个节点有两个指针，一个指向后面节点、一个指向前面节点。

循环链表实现

classNode(object):
def__init__(self,value=None,prev=None,next=None):
self.value=value
self.prev=prev
self.next=next


classCircularDoubleLinkedList(object):
"""
双向循环链表
"""

def__init__(self,maxsize=None):
self.maxsize=maxsize
node=Node()
node.prev=node
node.next=node
self.root=node
self.length=0

def__len__(self):
returnself.length

defhead_node(self):
returnself.root.next

deftail_node(self):
returnself.root.prev

#遍历
defiter_node(self):
ifself.root.nextisself.root:
return
current_node=self.root.next
whilecurrent_node.nextisnotself.root:
yieldcurrent_node
current_node=current_node.next
yieldcurrent_node

def__iter__(self):
fornodeinself.iter_node():
yieldnode.value

#反序遍历
defiter_node_reverse(self):
ifself.root.previsself.root:
return
current_node=self.root.prev
whilecurrent_node.previsnotself.root:
yieldcurrent_node
current_node=current_node.prev
yieldcurrent_node

defappend(self,value):
ifself.maxsizeisnotNoneandlen(self)>=self.maxsize:
raiseException("LinkedListisfull")
node=Node(value)
tail_node=self.tail_node()orself.root
tail_node.next=node
node.prev=tail_node
node.next=self.root
self.root.prev=node
self.length+=1

defappend_left(self,value):
ifself.maxsizeisnotNoneandlen(self)>=self.maxsize:
raiseException("LinkedListisfull")
node=Node(value)
ifself.root.nextisself.root:
self.root.next=node
node.prev=self.root
node.next=self.root
self.root.prev=node
else:
node.next=self.root.next
self.root.next.prev=node
self.root.next=node
node.prev=self.root
self.length+=1

defremove(self,node):
ifnodeisself.root:
return
node.next.prev=node.prev
node.prev.next=node.next
self.length-=1
returnnode

循环链表的使用

dll=CircularDoubleLinkedList()

dll.append(0)
dll.append(1)
dll.append(2)

assertlist(dll)==[0,1,2]
print(list(dll))#[0,1,2]

print([node.valuefornodeindll.iter_node()])#[0,1,2]
print([node.valuefornodeindll.iter_node_reverse()])#[2,1,0]

headnode=dll.head_node()
print(headnode.value)#0
dll.remove(headnode)
print(len(dll))#2

队列

队列(Queue)是一个数据集合，仅允许在列表的一端进行插入，另一端进行删除。

进行插入的一端成为队尾(rear)，插入动作称为进队或入队。

进行删除的一端称为队头(front)，删除动作称为出队。

队列的性质：先进先出(First-in,First-out)。

基于数组实现环形队列

classArray(object):
def__init__(self,size=32):
"""
:paramsize:长度
"""
self._size=size
self._items=[None]*size

#在执行array[key]时执行
def__getitem__(self,index):
returnself._items[index]

#在执行array[key]=value时执行
def__setitem__(self,index,value):
self._items[index]=value

#在执行len(array)时执行
def__len__(self):
returnself._size

#清空数组
defclear(self,value=None):
foriinrange(len(self._items)):
self._items[i]=value

#在遍历时执行
def__iter__(self):
foriteminself._items:
yielditem


classArrayQueue(object):
def__init__(self,maxsize):
self.maxsize=maxsize
self.array=Array(maxsize)
self.head=0
self.tail=0

def__len__(self):
returnself.head-self.tail

#入队
defpush(self,value):
iflen(self)>=self.maxsize:
raiseException("Queueisfull")
self.array[self.head%self.maxsize]=value
self.head+=1

#出队
defpop(self):
value=self.array[self.tail%self.maxsize]
self.tail+=1
returnvalue

使用

size=5
q=ArrayQueue(size)
foriinrange(size):
q.push(i)

print(len(q))#5

print(q.pop())#0
print(q.pop())#1

基于双向链表实现双向队列

classNode(object):
def__init__(self,value=None,prev=None,next=None):
self.value=value
self.prev=prev
self.next=next


classCircularDoubleLinkedList(object):
"""
双向循环链表
"""

def__init__(self,maxsize=None):
self.maxsize=maxsize
node=Node()
node.prev=node
node.next=node
self.root=node
self.length=0

def__len__(self):
returnself.length

defhead_node(self):
returnself.root.next

deftail_node(self):
returnself.root.prev

#遍历
defiter_node(self):
ifself.root.nextisself.root:
return
current_node=self.root.next
whilecurrent_node.nextisnotself.root:
yieldcurrent_node
current_node=current_node.next
yieldcurrent_node

def__iter__(self):
fornodeinself.iter_node():
yieldnode.value

#反序遍历
defiter_node_reverse(self):
ifself.root.previsself.root:
return
current_node=self.root.prev
whilecurrent_node.previsnotself.root:
yieldcurrent_node
current_node=current_node.prev
yieldcurrent_node

defappend(self,value):
ifself.maxsizeisnotNoneandlen(self)>=self.maxsize:
raiseException("LinkedListisfull")
node=Node(value)
tail_node=self.tail_node()orself.root
tail_node.next=node
node.prev=tail_node
node.next=self.root
self.root.prev=node
self.length+=1

defappend_left(self,value):
ifself.maxsizeisnotNoneandlen(self)>=self.maxsize:
raiseException("LinkedListisfull")
node=Node(value)
ifself.root.nextisself.root:
self.root.next=node
node.prev=self.root
node.next=self.root
self.root.prev=node
else:
node.next=self.root.next
self.root.next.prev=node
self.root.next=node
node.prev=self.root
self.length+=1

defremove(self,node):
ifnodeisself.root:
return
node.next.prev=node.prev
node.prev.next=node.next
self.length-=1
returnnode


#双向队列
classDeque(CircularDoubleLinkedList):
#从右边出队
defpop(self):
iflen(self)<=0:
raiseException("starkisempty!")
tail_node=self.tail_node()
value=tail_node.value
self.remove(tail_node)
returnvalue

#从左边出队
defpopleft(self):
iflen(self)<=0:
raiseException("starkisempty!")
head_node=self.head_node()
value=head_node.value
self.remove(head_node)
returnvalue

双向队列

两端都可以进行插入，删除。

基于双向链表实现双向队列

classNode(object):
def__init__(self,value=None,prev=None,next=None):
self.value=value
self.prev=prev
self.next=next


classCircularDoubleLinkedList(object):
"""
双向循环链表
"""

def__init__(self,maxsize=None):
self.maxsize=maxsize
node=Node()
node.prev=node
node.next=node
self.root=node
self.length=0

def__len__(self):
returnself.length

defhead_node(self):
returnself.root.next

deftail_node(self):
returnself.root.prev

#遍历
defiter_node(self):
ifself.root.nextisself.root:
return
current_node=self.root.next
whilecurrent_node.nextisnotself.root:
yieldcurrent_node
current_node=current_node.next
yieldcurrent_node

def__iter__(self):
fornodeinself.iter_node():
yieldnode.value

#反序遍历
defiter_node_reverse(self):
ifself.root.previsself.root:
return
current_node=self.root.prev
whilecurrent_node.previsnotself.root:
yieldcurrent_node
current_node=current_node.prev
yieldcurrent_node

defappend(self,value):
ifself.maxsizeisnotNoneandlen(self)>=self.maxsize:
raiseException("LinkedListisfull")
node=Node(value)
tail_node=self.tail_node()orself.root
tail_node.next=node
node.prev=tail_node
node.next=self.root
self.root.prev=node
self.length+=1

defappend_left(self,value):
ifself.maxsizeisnotNoneandlen(self)>=self.maxsize:
raiseException("LinkedListisfull")
node=Node(value)
ifself.root.nextisself.root:
self.root.next=node
node.prev=self.root
node.next=self.root
self.root.prev=node
else:
node.next=self.root.next
self.root.next.prev=node
self.root.next=node
node.prev=self.root
self.length+=1

defremove(self,node):
ifnodeisself.root:
return
node.next.prev=node.prev
node.prev.next=node.next
self.length-=1
returnnode


#双向队列
classDeque(CircularDoubleLinkedList):
#从右边出队
defpop(self):
iflen(self)<=0:
raiseException("starkisempty!")
tail_node=self.tail_node()
value=tail_node.value
self.remove(tail_node)
returnvalue

#从左边出队
defpopleft(self):
iflen(self)<=0:
raiseException("starkisempty!")
head_node=self.head_node()
value=head_node.value
self.remove(head_node)
returnvalue

双向队列的使用

dq=Deque()
dq.append(1)
dq.append(2)
print(list(dq))#[1,2]

dq.appendleft(0)
print(list(dq))#[0,1,2]

dq.pop()
print(list(dq))#[0,1]

dq.popleft()
print(list(dq))#[1]

dq.pop()
print(len(dq))#0

栈

栈(Stack)是一个数据集合，可以理解为只能在一端插入或删除操作的链表。

栈的特点：后进先出(Last-in,First-out)

栈的概念：

栈顶
栈底

栈的基本操作：

进栈（压栈）：push
出栈：pop

基于双向队列实现

classNode(object):
def__init__(self,value=None,prev=None,next=None):
self.value=value
self.prev=prev
self.next=next


classCircularDoubleLinkedList(object):
"""
双向循环链表
"""
def__init__(self,maxsize=None):
self.maxsize=maxsize
node=Node()
node.prev=node
node.next=node
self.root=node
self.length=0

def__len__(self):
returnself.length

defhead_node(self):
returnself.root.next

deftail_node(self):
returnself.root.prev

#遍历
defiter_node(self):
ifself.root.nextisself.root:
return
current_node=self.root.next
whilecurrent_node.nextisnotself.root:
yieldcurrent_node
current_node=current_node.next
yieldcurrent_node

def__iter__(self):
fornodeinself.iter_node():
yieldnode.value

#反序遍历
defiter_node_reverse(self):
ifself.root.previsself.root:
return
current_node=self.root.prev
whilecurrent_node.previsnotself.root:
yieldcurrent_node
current_node=current_node.prev
yieldcurrent_node

defappend(self,value):
ifself.maxsizeisnotNoneandlen(self)>=self.maxsize:
raiseException("LinkedListisfull")
node=Node(value)
tail_node=self.tail_node()orself.root
tail_node.next=node
node.prev=tail_node
node.next=self.root
self.root.prev=node
self.length+=1

defappend_left(self,value):
ifself.maxsizeisnotNoneandlen(self)>=self.maxsize:
raiseException("LinkedListisfull")
node=Node(value)
ifself.root.nextisself.root:
self.root.next=node
node.prev=self.root
node.next=self.root
self.root.prev=node
else:
node.next=self.root.next
self.root.next.prev=node
self.root.next=node
node.prev=self.root
self.length+=1

defremove(self,node):
ifnodeisself.root:
return
node.next.prev=node.prev
node.prev.next=node.next
self.length-=1
returnnode


classDeque(CircularDoubleLinkedList):
defpop(self):
iflen(self)<=0:
raiseException("starkisempty!")
tail_node=self.tail_node()
value=tail_node.value
self.remove(tail_node)
returnvalue

defpopleft(self):
iflen(self)<=0:
raiseException("starkisempty!")
head_node=self.head_node()
value=head_node.value
self.remove(head_node)
returnvalue


classStack(object):
def__init__(self):
self.deque=Deque()

#压栈
defpush(self,value):
self.deque.append(value)

#出栈
defpop(self):
returnself.deque.pop()

使用

s=Stack()
s.push(0)
s.push(1)
s.push(2)

print(s.pop())#2
print(s.pop())#1
print(s.pop())#0

总结

以上所述是小编给大家介绍的使用python实现数组、链表、队列、栈的方法，希望对大家有所帮助，如果大家有任何疑问请给我留言，小编会及时回复大家的。在此也非常感谢大家对毛票票网站的支持！
如果你觉得本文对你有帮助，欢迎转载，烦请注明出处，谢谢！

声明：本文内容来源于网络，版权归原作者所有，内容由互联网用户自发贡献自行上传，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任。如果您发现有涉嫌版权的内容，欢迎发送邮件至：czq8825#qq.com（发邮件时，请将#更换为@）进行举报，并提供相关证据，一经查实，本站将立刻删除涉嫌侵权内容。

使用python实现数组、链表、队列、栈的方法

热门推荐

随机推荐