备战秋招——记录自己学习的第一天(链表、栈、队列)
一、利用python实现单向链表
在程序中,经常需要将一组(通常是同为某个类型的)数据元素作为整体管理和使用,需要创建这种元素组,用变量记录它们,传进传出函数等。一组数据中包含的元素个数可能发生变化(可以增加或删除元素)。
对于这种需求,最简单的解决方案便是将这样一组元素看成一个序列,用元素在序列里的位置和顺序,表示实际应用中的某种有意义的信息,或者表示数据之间的某种关系。
这样的一组序列元素的组织形式,我们可以将其抽象为线性表。一个线性表是某类元素的一个集合,还记录着元素之间的一种顺序关系。线性表是最基本的数据结构之一,在实际程序中应用非常广泛,它还经常被用作更复杂的数据结构的实现基础。
根据线性表的实际存储方式,分为两种实现模型:
顺序表,将元素顺序地存放在一块连续的存储区里,元素间的顺序关系由它们的存储顺序自然表示。
链表,将元素存放在通过链接构造起来的一系列存储块中。
为什么需要链表
顺序表的构建需要预先知道数据大小来申请连续的存储空间,而在进行扩充时又需要进行数据的搬迁,所以使用起来并不是很灵活。
链表结构可以充分利用计算机内存空间,实现灵活的内存动态管理。
链表的定义
链表(Linked list)是一种常见的基础数据结构,是一种线性表,但是不像顺序表一样连续存储数据,而是在每一个节点(数据存储单元)里存放下一个节点的位置信息(即地址)。最后一个节点指向None。
单链表的操作
is_empty() 链表是否为空
length() 链表长度
travel() 遍历整个链表
add(item) 链表头部添加元素
append(item) 链表尾部添加元素
insert(pos, item) 指定位置添加元素
remove(item) 删除节点
search(item) 查找节点是否存在
首先,我们先定义链表中的节点
"""单链表的节点"""
def __init__(self,item):
"""设置单链表的值"""
self.item = item
"""设置单链表指向的地址"""
self.next = None入代码片`
创建单链表,其中封装着头结点:
class SingleLinkList(object):
"""创建单向链表"""
def __init__(self,node = None):
"""创建头结点"""
self.__head = node
判断链表是否为空:
def is_empty(self):
"""链表是否为空"""
return self.__head == None
求出链表长度:
def length(self):
"""链表的长度"""
cur = self.__head
"""定义指针"""
count = 0
while cur != None:
count += 1
cur = cur.next
"""定义下一个指针"""
return count
遍历整个列表,将其中数据输出输出:
def travel(self):
"""遍历整个链表"""
cur = self.__head
while cur != None:
print(cur.item)
cur = cur.next
在链表头部添加首节点:
def add(self,item):
"""链表头部添加元素"""
node = SingleNode(item)
node.next = self.__head
self.__head = node
添加尾节点:
def append(self,item):
"""链表尾部添加元素"""
node = SingleNode(item)
cur = self.__head
if self.is_empty():
self.add(item)
else:
while cur.next != None:
cur = cur.next
cur.next = node
任意位置插入节点:
def insert(self,pos,item):
"""指定位置添加元素"""
node = SingleNode(item)
cur = self.__head
if pos<=0:
self.add(item)
elif pos + 1 >self.length():
self.append(item)
else:
for i in range(0,pos-1):
cur=cur.next
node.next = cur.next
cur.next = node
删除节点:
def remove(self,item):
"""删除节点"""
cur = self.__head
pre = None
if cur.item ==item:
self.__head = cur.next
else:
for i in range(0,self.length()+1):
if item == cur.item:
pre.next = cur.next
else:
pre = cur
cur = cur.next
查找节点是否存在:
def search(self,item):
"""查找节点是否存在"""
cur = self.__head
while cur != None:
if item == cur.item:
return True
cur = cur.next
return False
下面进行程序验证:
if __name__ == "__main__":
li = SingleLinkList()
li.add(5)
li.add(4)
li.add(70)
li.append(100)
li.insert(50,30)
li.remove(70)
print(li.search(1000))
li.travel()
结果图:
二、利用python实现双向链表
双向链表
一种更复杂的链表是“双向链表”或“双面链表”。每个节点有两个链接:一个指向前一个节点,当此节点为第一个节点时,指向空值;而另一个指向下一个节点,当此节点为最后一个节点时,指向空值。
与单向链表的不同之处在于,除了首节点,每个节点多了都会指向前一个节点的地址,下面我们在单向链表的基础上进行修改:
class SingleNode(object):
"""单链表的节点"""
def __init__(self,item):
"""设置单链表的值"""
self.item = item
"""设置单链表指向的地址"""
self.next = None
self.prev = None
class DoubleLinkList(object):
"""创建双向链表"""
def __init__(self,node = None):
"""创建头结点"""
self.__head = node
def is_empty(self):
"""链表是否为空"""
return self.__head == None
def length(self):
"""链表的长度"""
cur = self.__head
"""定义指针"""
count = 0
while cur != None:
count += 1
cur = cur.next
"""定义下一个指针"""
return count
def travel(self):
"""遍历整个链表"""
cur = self.__head
while cur != None:
print(cur.item)
cur = cur.next
def add(self,item):
"""链表头部添加元素"""
node = SingleNode(item)
if self.is_empty():
node.next = self.__head
self.__head = node
self.__head.prev = node
else:
node.next = self.__head
self.__head = node
def append(self,item):
"""链表尾部添加元素"""
node = SingleNode(item)
cur = self.__head
if self.is_empty():
self.add(item)
else:
while cur.next != None:
cur = cur.next
node.prev = cur
cur.next = node
def insert(self,pos,item):
"""指定位置添加元素"""
node = SingleNode(item)
cur = self.__head
if pos<=0:
self.add(item)
elif pos + 1 >self.length():
self.append(item)
else:
for i in range(0, pos - 1):
cur=cur.next
node.next = cur.next
cur.next.prev = node
cur.next = node
node.prev = cur
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
if cur.next:
# 将cur的后一个节点的prev指向cur的前一个节点
cur.next.prev = cur.prev
break
cur = cur.next
def search(self,item):
"""查找节点是否存在"""
cur = self.__head
while cur != None:
if item == cur.item:
return True
cur = cur.next
return False
if __name__ == "__main__":
ll = DoubleLinkList()
ll.append(1)
ll.append(2)
ll.append(3)
ll.append(4)
ll.insert(2,100)
ll.add(5)
ll.remove(100)
ll.travel()
**结果如下:**
5
1
2
3
4
三、利用python实现单项循环链表
单向循环链表
单链表的一个变形是单向循环链表,链表中最后一个节点的next域不再为None,而是指向链表的头节点。
操作
is_empty() 判断链表是否为空
length() 返回链表的长度
travel() 遍历
add(item) 在头部添加一个节点
append(item) 在尾部添加一个节点
insert(pos, item) 在指定位置pos添加节点
remove(item) 删除一个节点
search(item) 查找节点是否存在
class SingleNode(object):
"""单项循环链表的节点"""
def __init__(self,item):
"""设置单链表的值"""
self.item = item
"""设置单链表指向的地址"""
self.next = None
class SinCycLinkedlist(object):
"""创建单向链表"""
def __init__(self,node = None):
"""创建头结点"""
self.__head = node
def is_empty(self):
"""链表是否为空"""
return self.__head == None
def length(self):
"""链表的长度"""
if self.is_empty():
return 0
else:
cur = self.__head
"""定义指针"""
count = 1
while cur.next != self.__head:
count += 1
cur = cur.next
"""定义下一个指针"""
return count
def travel(self):
"""遍历整个链表"""
if self.is_empty():
return
else:
cur = self.__head
while cur.next != self.__head:
print(cur.item)
cur = cur.next
print(cur.item)
def add(self,item):
"""链表头部添加元素"""
node = SingleNode(item)
if self.is_empty():
self.__head = node
node.next = self.__head
else:
node.next = self.__head
cur = self.__head
# self.__head = node #这一步不能写在这里,因为会对cur的值发生改变
while cur.next != self.__head:
cur = cur.next
cur.next = node
self.__head = node
def append(self,item):
"""链表尾部添加元素"""
node = SingleNode(item)
cur = self.__head
if self.is_empty():
self.add(item)
else:
while cur.next != self.__head:
cur = cur.next
cur.next = node
node.next = self.__head
def insert(self,pos,item):
"""指定位置添加元素"""
node = SingleNode(item)
cur = self.__head
if pos<=0:
self.add(item)
elif pos + 1 >self.length():
self.append(item)
else:
for i in range(0,pos-1):
cur=cur.next
node.next = cur.next
cur.next = node
def remove(self, item):
"""删除一个节点"""
# 若链表为空,则直接返回
if self.is_empty():
return
# 将cur指向头节点
cur = self.__head
pre = None
# 若头节点的元素就是要查找的元素item
if cur.item == item:
# 如果链表不止一个节点
if cur.next != self.__head:
# 先找到尾节点,将尾节点的next指向第二个节点
while cur.next != self.__head:
cur = cur.next
# cur指向了尾节点
cur.next = self.__head.next
self.__head = self.__head.next
else:
# 链表只有一个节点
self.__head = None
else:
# 第一个节点不是要删除的
while cur.next != self.__head:
# 找到了要删除的元素
if cur.item == item:
# 删除
pre.next = cur.next
return
else:
pre = cur
cur = cur.next
# cur 指向尾节点
if cur.item == item:
# 尾部删除
pre.next = cur.next
def search(self,item):
"""查找节点是否存在"""
cur = self.__head
if self.is_empty():
return
else:
while cur != self.__head:
if item == cur.item:
return True
cur = cur.next
if item == cur.item:
return True
else:
return False
"""for 循环无法终止程序,所以必须要用while来停止
for i in range(0,self.length()+1):
if item == cur.item:
return True
cur = cur"""
if __name__ == "__main__":
li = SinCycLinkedlist()
li.add(5)
li.append(100)
li.add(4)
li.insert(1,200)
li.remove(100)
# print(li.length())
li.travel()
**结果如下:**
4
200
5
四、利用顺序表(为了方便起见,使用python中自带的顺序表——list,也可以对前三个结构进行封装)实现栈的功能。
让我们介绍一下什么是栈。
栈(stack),有些地方称为堆栈,是一种容器,可存入数据元素、访问元素、删除元素,它的特点在于只能允许在容器的一端(称为栈顶端指标,英语:top)进行加入数据(英语:push)和输出数据(英语:pop)的运算。没有了位置概念,保证任何时候可以访问、删除的元素都是此前最后存入的那个元素,确定了一种默认的访问顺序。
由于栈数据结构只允许在一端进行操作,因而按照后进先出(LIFO, Last In First Out)的原理运作。
class Stack(object):
def __init__(self):
self.__list = []
def push(self,item):
self.__list.append(item)
def pop(self):
return self.__list.pop()
def peek(self):
if self.__list:
return self.__list[-1]
else:
return None
def is_empty(self):
return self.__list == []
def size(self):
return len(self.__list)
s = Stack()
s.push(1)
s.push(2)
s.push(3)
s.push(4)
print(s.size())
print(s.pop())
print(s.pop())
print(s.pop())
print(s.pop())
**结果如下:**
4
4
3
2
1
五、队列
**队列(queue)**是只允许在一端进行插入操作,而在另一端进行删除操作的线性表。
队列是一种先进先出的(First In First Out)的线性表,简称FIFO。允许插入的一端为队尾,允许删除的一端为队头。队列不允许在中间部位进行操作!假设队列是q=(a1,a2,……,an),那么a1就是队头元素,而an是队尾元素。这样我们就可以删除时,总是从a1开始,而插入时,总是在队列最后。这也比较符合我们通常生活中的习惯,排在第一个的优先出列,最后来的当然排在队伍最后。
#__author:"zhnag san pang"
#date: 2019/5/29
#__author:"zhnag san pang"
#date: 2019/5/29
class Queue(object):
def __init__(self):
self.__list = []
def enqueue(self,item):
self.__list.insert(0,item)
def dequeue(self):
return self.__list.pop()
def is_empty(self):
return self.__list == []
def size(self):
return len(self.__list)
s = Queue()
s.enqueue(4)
s.enqueue(3)
s.enqueue(2)
s.enqueue(1)
print(s.size())
print(s.dequeue())
print(s.dequeue())
print(s.dequeue())
print(s.dequeue())
**结果如下:**
4
4
3
2
1
在这里,我们引出
**双端队列**
双端队列(deque,全名double-ended queue),是一种具有队列和栈的性质的数据结构。
双端队列中的元素可以从两端弹出,其限定插入和删除操作在表的两端进行。双端队列可以在队列任意一端入队和出队。
class Deque(object):
def __init__(self):
self.__list = []
def add_front(self,item):
self.__list.insert(0,item)
def add_rear(self,item):
self.__list.append(item)
def remove_front(self):
return self.__list.pop(0)
def remove_rear(self):
return self.__list.pop()
def is_empty(self):
return self.__list == []
def size(self):
return len(self.__list)
上一篇: 文件上传下载