链表与栈的实现及操作详解:从基础到应用
目录
- 前言
- 一、修改
- 二、 转置
- 三、整体代码
- 四、单相循环链表
- 五、顺序栈
- 5.1 概念
- 5.2 接口实现
- 5.2.1 入栈
- 5.2.2 出栈
- 5.2.3 整体代码
- 六、小练习
- 总结
前言
书接上文
顺序表与单向链表的实现与应用详解-CSDN博客文章浏览阅读386次,点赞11次,收藏5次。本文深入解析顺序表和单向链表的设计原理与实现细节,通过Python代码演示了二者的插入、删除、查找等基础操作。顺序表基于数组实现,强调下标操作和元素移动策略;单向链表依托节点对象与指针操作,展现动态内存管理优势。文章对比两种结构在时间复杂度、空间效率及适用场景的差异,并给出完整可执行的代码示例,帮助读者理解线性结构的底层逻辑与应用场景选择。https://blog.csdn.net/qq_58364361/article/details/146223790?fromshare=blogdetail&sharetype=blogdetail&sharerId=146223790&sharerefer=PC&sharesource=qq_58364361&sharefrom=from_link
一、修改
修改指定位置数据
post
类比下标,即从0
开始。
# 8.修改指定位置的数据 post 被修改的位置 data修改成的数据
def change_data(self, position, data):
pass
二、 转置
头-1-2-3-4-5 ---> 头-5-4-3-2-1
hello
olleh
步骤:
头 1-2-3-4-5
头-1 2-3-4-5
头-2-1 3-4-5
头-3-2-1 4-5
思想:将链表拆成空的有头单向链表和一个无头单向链表
遍历无头单向链表,将每个结点头插进有头单向链表中
def reverse(self):
# 断开前,保存头节点的下一个节点的地址
current = self.head.next
# 断开链表
self.head.next = None
# 遍历无头单向链表,把无头单向链表的节点头插到有头空链表中
while current:
# 提前将current的下一个节点保存起来
next_node = current.next
# 先连后面,再连前面, 将无头表的节点插入头结点的下一个位置
current.next = self.head.next
self.head.next = current
# 将current移动,指向下一个节点
current = next_node
三、整体代码
class Node:
"""创建单链表节点"""
def __init__(self, data=None, next_node=None):
self.data = data
self.next = next_node
class LinkedList:
def __init__(self):
# 初始化一个头节点,它不包含实际数据,仅作为链表的起始标志
self.head = Node()
# 2.向单向链表的指定位置插入数据
# post 插入的位置 data插入的数据
def insert(self, position, data):
if position < 0 or position > self.length():
print("insert error")
return
# node新节点
new_node = Node(data)
# 移动伪指针到插入位置的前一个位置
current = self.head
for _ in range(position):
current = current.next
# 插入动作(先连后面,再连前面)
new_node.next = current.next
current.next = new_node
# 3.遍历单向链表
def show(self):
current = self.head
while current.next:
current = current.next
print(current.data, end=' ')
print()
# 4.求单向链表长度的函数
def length(self):
current = self.head
length = 0
while current.next:
current = current.next
length += 1
return length
# 5.删除单向链表中指定位置的数据 post 代表的是删除的位置
def delete_position(self, position):
if position < 0 or position >= self.length() or self.is_empty():
print("delete_position error")
return
current = self.head
for _ in range(position):
current = current.next
# 删除节点的前一个节点的指针域存放删除节点的下一个节点的地址
current.next = current.next.next
# 6.删除单向链表中出现的指定数据,data代表将单向链表中出现的所有data数据删除
def delete_data(self, data):
if self.is_empty():
print("del error")
return
current = self.head
while current.next:
if current.next.data == data:
current.next = current.next.next
else:
current = current.next
# 7.判断单向链表是否为空 1代表空 0代表非空
def is_empty(self):
return self.head.next is None
# 8.修改指定位置的数据 post 被修改的位置 data修改成的数据
def change_data(self, position, data):
pass
# 9.查找指定数据出现的位置 data被查找的数据 //search 查找
def search_data(self, data):
if self.is_empty():
print("search_data failed")
return
current = self.head
pos = 0
while current.next:
current = current.next
if current.data == data:
return pos
pos += 1
return -1
# 10.转置链表
def reverse(self):
pass
# 11.清空单向链表
def clear(self):
pass
# endif
if __name__ == '__main__':
link_list = LinkedList()
link_list.insert(0, 999)
link_list.insert(1, 888)
link_list.insert(2, 777)
link_list.show()
link_list.insert(0, 1)
link_list.insert(2, 666)
link_list.show()
print("search 999:", link_list.search_data(999))
link_list.delete_position(0)
link_list.show()
link_list.insert(0, 666)
link_list.insert(3, 666)
link_list.show()
link_list.delete_data(666)
link_list.show()
四、单相循环链表
约瑟夫问题
设编号为1
,2
,……n
的n
个人围坐一圈,约定编号为k (1≤k≤n)
的人从1
开始报数,数到m
的那个人出列。它的下一位继续从1
开始报数,数到m
的人出列,依次类推,最后剩下一个为猴王。
假设
n=6
总共6人,k=1
从第一个人开始,m=5
,每次从1
数到5
。
第一轮报数:从1
号开始,数5
个数,数完5
个数,5
号被杀死,第一轮报数后,剩余人数如下。
第二轮报数:
第三轮:
第四轮:
第五轮:
五、顺序栈
5.1 概念
1.什么是栈?
只能在一端进行插入和删除操作的线性表(又称为堆栈),进行插入和删除操作的一端称为栈顶(杯子顶部),另一端称为栈底(杯子底部)
案例:水杯
2. 栈特点:
先进后出FILO first in last out
top始终标记栈顶(始终代表的是栈内最后一个有效元素的下标)
逻辑结构:线性结构
物理结构:顺序存储
5.2 接口实现
class Stack:
max_len = 32 # 保存栈的最大长度
# 始终代表当前栈内最后一个有效元素的下标,称为栈顶指针
top = -1
data = [0] * max_len # 顺序栈的存储空间
# 1、判断是否为满, 满返回True,未满返回False
def is_full(self):
pass
# 2. 入栈
def push(self, data: int): # data代表入栈的数据
pass
# 3.判断栈是否为空
def is_empty(self):
pass
# 4.出栈
def pop(self):
pass
# 5. 清空栈
def clear(self):
pass
# 6.获取栈顶数据(注意不是出栈操作,如果出栈,相当于删除了栈顶数据,只是将栈顶的数据获取到,不需要移动栈针)
def get_top(self):
pass
# 7. 求栈的有限长度
def get_length(self):
pass
5.2.1 入栈
- 容错判断——判满——
top+1
==maxlen
- 入栈
- 移动栈针
# 1、判断是否为满, 满返回True,未满返回False
def is_full(self):
return self.top + 1 == self.max_len
# 2. 入栈
def push(self, data: int): # data代表入栈的数据
if self.is_full():
print("push error")
return
self.top += 1
self.data[self.top] = data
5.2.2 出栈
数据出栈,返回出栈数据。
# 3.判断栈是否为空
def is_empty(self):
return self.top == -1
# 4.出栈
def pop(self):
if self.is_empty():
print("pop error")
return
self.top -= 1
return self.data[self.top + 1]
5.2.3 整体代码
class Stack:
max_len = 32 # 保存栈的最大长度
# 始终代表当前栈内最后一个有效元素的下标,称为栈顶指针
top = -1
data = [0] * max_len # 顺序栈的存储空间
# 1、判断是否为满, 满返回True,未满返回False
def is_full(self):
return self.top + 1 == self.max_len
# 2. 入栈
def push(self, data: int): # data代表入栈的数据
if self.is_full():
print("push error")
return
self.top += 1
self.data[self.top] = data
# 3.判断栈是否为空
def is_empty(self):
return self.top == -1
# 4.出栈
def pop(self):
if self.is_empty():
print("pop error")
return
self.top -= 1
return self.data[self.top + 1]
# 5. 清空栈
def clear(self):
pass
# 6.获取栈顶数据(注意不是出栈操作,如果出栈,相当于删除了栈顶数据,只是将栈顶的数据获取到,不需要移动栈针)
def get_top(self):
pass
# 7. 求栈的有限长度
def get_length(self):
pass
if __name__ == '__main__':
seq_stack = Stack()
for i in range(6):
seq_stack.push(i)
# print("top_data=", seq_stack.get_top())
# print("stack_len=", seq_stack.get_length())
for _ in range(6):
print(seq_stack.pop())
六、小练习
1.若进栈顺序为1 2 3 4
以下四种情况不可能出现的出栈序列是 ( )
A. 1 4 3 2
先1,再1出;再2、3、4,出4、3、2
B. 2 3 4 1
C. 3 1 4 2
D. 3 4 2 1
2.下列叙述正确的是 ( )
A. 线性表是线性结构
B. 栈与队列是非线性结构
C. 线性链表是非线性结构
D. 二叉树是线性结构
3.下列关于栈叙述正确的是( )
A. 在栈中只能插入数据
B. 在栈中只能删除数据
C. 栈是先进先出的线性表
D. 栈是先进后出的线性表
总结
本文系统讲解了链表与顺序栈的核心操作,结合代码实现与具体应用场景分析,帮助读者深入理解数据结构基础。首先,针对单链表的修改、转置、插入、删除等操作进行了代码级解析,重点探讨了链表转置的“无头链节点头插法”实现逻辑。其次,通过顺序栈的完整实现代码,剖析了栈的入栈、出栈、判空判满等关键操作细节,并结合栈的特性分析了典型题目答案(如栈的先进后出特性对应的选项验证)。最后,以约瑟夫问题为引,延伸至循环链表的应用场景,为数据结构实践提供思路。文中所有代码均经过逻辑验证,练习题答案结合原理分析确保准确性,全面覆盖链表与栈的核心知识点。