数据结构子目录https://www.jianshu.com/p/a344fa483655
顺序表
顺序表按照存储的元素类型，可以分为两种，一种是单类型顺序表，一种是多类型顺序表。
Python中的列表和元组便是多类型顺序表，多类型顺序表的内存不是连续开辟的。
数组是单类型顺序表。
顺序表的弊端
需要先预知数据大小来开辟空间，如果需要扩充就需要对数据进行迁移。
链表
相比于顺序表，链表可以更加充分利用计算机的空间，实现灵活的内存动态管理，且进行扩容时不需要迁移。
什么是链表
链表中每一个元素都是一个对象，每一个对象称为一个节点，包含有数据域key与指向下一个节点的指针next，通过各个节点之间的相互连接，最终串联成一个链表。
节点定义
# Student类（节点类） 一个Student对象就是一个节点
class Student:
def __init__(self,SchNum,name,score):
self.SchNum = SchNum
self.name = name
self.score = score #保存三个数据
self.next = None #下一个节点的指针
链表定义
# 链表类
class Link:
# 构造函数
def __init__(self):
self.head = Student(None,None,None) # 头节点为空
self.tail = self.head
self.size = 1
单向链表
建立链表--头插法
pcur是要插入到新链表中的节点
prev是pcur的next
步骤如下：
- prev保存下一个要插入的节点
- 把pcur插入到新链表中
- 调整头节点的指向
- 下一个要插入的节点为prev
# 链表类
class Link:
# 构造函数
def __init__(self):
self.head = Student(None,None,None) # 头节点为空
self.tail = self.head
self.size = 1
#头插法
def new_invert(self,head):
dummy = self.head # 头节点当做新链表的尾节点
pcur = head.next
count = 0
while(count < self.size - 1):
prev = pcur.next # prev保存下一个要插入的节点
pcur.next = dummy # 把pcur插入到新链表中
dummy = pcur # 调整头节点的指向
pcur = prev # 下一个要插入的节点为prev
count = count + 1
self.head = dummy
连接链表
直接将link1的尾节点的next指向link2的头节点就可以啦。
# 链表类
class Link:
# 构造函数
def __init__(self):
self.head = Student(None,None,None) # 头节点为空
self.tail = self.head
self.size = 1
# 连接两个链表
def connectLink(self,link):
self.tail.next = link.head.next
self.size = self.size + link.size - 1 # 链表大小相加
反转链表
prev指向头节点
pcur是当前需要反转的节点
dummy是头节点
步骤如下：
- prev连接下一次需要反转的节点
- 反转节点pcur
- 将dummy向后移动一位
- pcur指向下一次需要反转的节点
# 链表类
class Link:
# 构造函数
def __init__(self):
self.head = Student(None,None,None) # 头节点为空
self.tail = self.head
self.size = 1
# 反转链表(就地反转）
def jiudi_invert(self,head):
dummy = Student(None,None,None)
dummy.next = head # 创建新节点，新节点的下一个指向头（head）节点
prev = dummy.next # prev也指向头（head）节点
pcur = prev.next # pcur是当前需要反转的节点
while(pcur != None): # 循环条件：直到尾节点结束
prev.next = pcur.next # prev连接下一次需要反转的节点
pcur.next = dummy.next # 反转
dummy.next = pcur # 纠正头节点的位置（将头节点向后移动一位）
pcur = prev.next # pcur指向下一次需要反转的节点
self.head = dummy.next
节点操作
增加节点
增加元素是将一个新的节点增加在链表的尾部，要增加一个节点，我们需要一下步骤：
- 将链表尾节点的下一个节点指向新节点
- 将新节点作为尾节点
- 链表的长度+1
# 添加节点
def add(self,SchNum,name,score):
stu = Student(SchNum,name,score) # 创建新节点
self.tail.next = stu # 尾节点的下一个节点为新节点
self.tail = stu # 尾节点为新节点
self.size = self.size + 1
插入节点
如果我们想要将一个节点插入到链表中，我们需要哪些步骤呢？
- 首先 ，推进到要插入的位置的前一个节点before处
- before.next为新节点
- 新节点.next为原链表before的下一个节点
- 链表的长度+1
# 插入节点（此节点作为第index个节点）
def insert(self,SchNum,name,score,index):
if(index > self.size):
print('链表还没有这么长哟！请输入小一点的整数......')
else:
stu = self.head
insert_stu = Student(SchNum,name,score)
for i in range(index - 1):
stu = stu.next # 推进到要插入的位置
insert_stu.next = stu.next
stu.next = insert_stu
self.size = self.size + 1
删除节点
我们假设一个链表结构 before—>delete—>after。如果我们想要删除delete节点，那么我们只需要将before的下一个节点指向after就可以了，然后链表长度-1
# 删除节点（索引为index）
def delete(self,index):
if (index > self.size):
print('链表还没有这么长哟！请输入小一点的整数......')
else:
stu = self.head
for i in range(index - 1):
stu = stu.next
temp = stu.next
stu.next = temp.next
self.size = self.size - 1
修改节点数据
# 改变指定节点的数据
def change(self,SchNum,name,score,index):
if (index > self.size):
print('链表还没有这么长哟！请输入小一点的整数......')
else:
stu = self.head
for i in range(index): # 推进到要改变节点的位置
stu = stu.next
stu.SchNum =SchNum
stu.name = name
stu.score =score
查询节点数据
# 返回节点的数据
def getData(self,index):
if(index > self.size): # 判断是否超过链表的长度
print('链表还没有这么长哟！请输入小一点的整数......')
else:
stu = self.head
for i in range(index):
stu = stu.next
return [stu.SchNum,stu.name,stu.score]
获取链表长度
# 返回节点的长度
def getSize(self):
return self.size
总结
# Student类（节点类） 一个Student对象就是一个节点
class Student:
def __init__(self,SchNum,name,score):
self.SchNum = SchNum
self.name = name
self.score = score
self.next = None
# 链表类
class Link:
# 构造函数
def __init__(self):
self.head = Student(None,None,None) # 头节点为空
self.tail = self.head
self.size = 1
# 添加节点
def add(self,SchNum,name,score):
stu = Student(SchNum,name,score) # 创建新节点
self.tail.next = stu # 尾节点的下一个节点为新节点
self.tail = stu # 尾节点为新节点
self.size = self.size + 1
# 插入节点（此节点作为第index个节点）
def insert(self,SchNum,name,score,index):
if(index > self.size):
print('链表还没有这么长哟！请输入小一点的整数......')
else:
stu = self.head
insert_stu = Student(SchNum,name,score)
for i in range(index - 1):
stu = stu.next # 推进到要插入的位置
insert_stu.next = stu.next
stu.next = insert_stu
self.size = self.size + 1
# 删除节点（索引为index）
def delete(self,index):
if (index > self.size):
print('链表还没有这么长哟！请输入小一点的整数......')
else:
stu = self.head
for i in range(index - 1):
stu = stu.next
temp = stu.next
stu.next = temp.next
self.size = self.size - 1
# 改变指定节点的数据
def change(self,SchNum,name,score,index):
if (index > self.size):
print('链表还没有这么长哟！请输入小一点的整数......')
else:
stu = self.head
for i in range(index): # 推进到要改变节点的位置
stu = stu.next
stu.SchNum =SchNum
stu.name = name
stu.score =score
# 返回节点的数据
def getData(self,index):
if(index > self.size): # 判断是否超过链表的长度
print('链表还没有这么长哟！请输入小一点的整数......')
else:
stu = self.head
for i in range(index):
stu = stu.next
return [stu.SchNum,stu.name,stu.score]
# 返回节点的长度
def getSize(self):
return self.size
# 反转链表(就地反转）
def jiudi_invert(self,head):
dummy = Student(None,None,None)
dummy.next = head # 创建新节点，新节点的下一个指向头（head）节点
prev = dummy.next # prev也指向头（head）节点
pcur = prev.next # pcur是当前需要反转的节点
while(pcur != None): # 循环条件：直到尾节点结束
prev.next = pcur.next # prev连接下一次需要反转的节点
pcur.next = dummy.next # 反转
dummy.next = pcur # 纠正头节点的位置（将头节点向后移动一位）
pcur = prev.next # pcur指向下一次需要反转的节点
self.head = dummy.next # 链表彻底反转完成，尾节点变为头节点
# 反转链表（创建新链表，头节点插入法）
def new_invert(self,head):
dummy = self.head # 头节点当做新链表的尾节点
pcur = head.next
count = 0
while(count < self.size - 1):
prev = pcur.next # prev保存下一个要插入的节点
pcur.next = dummy # 把pcur插入到新链表中
dummy = pcur # 调整头节点的指向
pcur = prev # 下一个要插入的节点为prev
count = count + 1
self.head = dummy
# 连接两个链表
def connectLink(self,link):
self.tail.next = link.head.next
self.size = self.size + link.size - 1 # 链表大小相加
def main():
link = Link() # 创建链表
newlink = Link() # 创建newlink，用作链表连接
for i in range(5):
newlink.add(i,'我是新链表！！！',i)
print('添加节点 => 1 , 插入节点 => 2 , 删除节点 => 3 , 改变节点数据 => 4 , 遍历链表 => 5 , 获取链表长度 => 6')
print('反转链表(就地反转） => 7 , 连接两个链表 => 8 , 反转链表（头节点插入法） => 9 , 退出 => 0')
select = -1
while select != 0:
select = int(input('请选择：'))
if(select == 1): # 添加
print('请输入相应数据')
SchNum = int(input('学号：'))
name = input('姓名：')
score = input('成绩：')
link.add(SchNum,name,score)
elif(select == 2): # 插入
print('请输入相应数据')
SchNum = int(input('学号：'))
name = input('姓名：')
score = input('成绩：')
index = int(input('要插入的位置（整数）：'))
link.insert(SchNum,name,score,index)
elif(select == 3): # 删除
index = int(input('要删除节点的索引：'))
link.delete(index)
elif(select == 4): # 改变数据
print('请输入相应数据')
SchNum = int(input('学号：'))
name = input('姓名：')
score = input('成绩：')
index = int(input('要改变的位置（整数）：'))
link.change(SchNum,name,score,index)
elif(select == 5): # 遍历
print('学号------姓名--------成绩')
for i in range(link.size):
data = link.getData(i)
print(str(data[0]) + ' ' + str(data[1]) + ' ' + str(data[2]))
elif(select == 6): # 获取长度
print('链表的长度为：'+str(link.getSize()))
elif(select == 7):
link.jiudi_invert(link.head)
elif(select == 8):
link.connectLink(newlink)
elif(select == 9):
link.new_invert(link.head)
if __name__ == '__main__':
main()
网友评论