Python 实现单向链表的插入、删除
程序员文章站
2024-02-13 23:18:04
...
插入节点
在单向链表中插入一个新节点有三种情况:
1.加到头结点之前
2.加到链表末尾
3.加到链表中间任意一个位置
solution1:.加到头结点之前
newnode.next=first
first=newnode
solution2:加到链表末尾
ptr.next=newnode
newnode.next=None
solution3:.加到链表中间任意一个位置
newnode.next=x.next
x.next=newnode
exercise:
设计一个Python程序,建立员工单向链表,并允许在链表头、尾、中三种不同位置插入新节点。最后离开,列出链表内容:
import sys
class employee:
def __init__(self):
self.num=0
self.salary=0
self.name=' '
self.next=None
def findnode(head,num):
ptr=head
while ptr!=None:
if ptr.num==num:
return ptr
ptr=ptr.next
return ptr
def insertnode(head,ptr,num,salary,name):
Insertnode=employee()
if not Insertnode:
return None
Insertnode.num=num
Insertnode.name=name
Insertnode.salary=salary
Insertnode.next=None
if ptr==None:#插入第一个节点
Insertnode.next=head
return Insertnode
else:
if ptr.next==None:#插入最后一个节点
ptr.next=Insertnode
else:
Insertnode.next=ptr.next
ptr.next=Insertnode
return head
position=1
data=[[1001,32678],[1002,23789],[1003,39087],[1004,46789],[1007,32908],[1020,31214]]
namedata=['Allen','Scott','Nelle','Mark','Deny','Bob']
print('员工编号 薪水 员工编号 薪水')
print('________________________________________________________________________')
for i in range(3):
for j in range(2):
print('[%4d]\t$%5d'%(data[j*3+i][0],data[j*3+i][1]),end=' ')
print()
print('_________________________________________________________________________')
head=employee()#建立头结点
head.next=None
if not head:
print('Error!!内存分配失败')
sys.exit(1) #程序有错误退出
head.num=data[0][0]
head.name=namedata[0]
head.salary=data[0][1]
head.next=None
ptr=head
for i in range(1,6):#建立链表
newnode=employee()
newnode.num=data[i][0]
newnode.name=namedata[i]
newnode.salary=data[i][1]
newnode.next=None
ptr.next=newnode
ptr=newnode
while(True):
print('请输入要插入其后员工编号,如果输入的编号不在链表中,')
position=int(input('新输入的员工节点将视为此链表的链表头部,要结束过程,输入-1:'))
if position==-1:
break
else:
ptr=findnode(head,position)
new_num=int(input('请输入新插入的员工编号:'))
new_salary=int(input('请输入新插入的员工薪水:'))
new_name=input('请输入新插入的员工名字:')
head=insertnode(head,ptr,new_num,new_salary,new_name)
print()
ptr=head
print('员工编号 姓名\t薪水')
print('________________________________________')
while ptr!=None:
print('[%2d]\t[%-5s]\t[%3d]'%(ptr.num,ptr.name,ptr.salary))
ptr=ptr.next
结果:
删除节点:
三种情况:
solution1:
删除链表的第一个节点:
top=head
head=head.next
solution2:
删除链表的最后一个节点:
ptr.next=tail
ptr.next=None
solution3:
删除表内中间节点:
Y=ptr.next
ptr.next=Y.next
Python代码:
def del_ptr(head,ptr):
top=head
if ptr.num==head.num:#删除链表头部的节点
head=head.next
print('已删除第%d号员工 姓名:%s 薪水:%d' %(ptr.num,ptr.name,ptr.salary))
else:
while top.next!=ptr:#找到删除节点的前一个位置
top=top.next
if ptr.next==None:#删除链表尾部的节点
top.next=None
print('已删除第%d号员工 姓名:%s 薪水:%d' %(ptr.num,ptr.name,ptr.salary))
else:
top.next=ptr.next #删除节点中任意节点
print('已删除第%d号员工 姓名:%s 薪水:%d' %(ptr.num,ptr.name,ptr.salary))
return head #返回链表
单向链表的反转
反转过来输出单向链表:由于单向链表的节点知道下一个节点的位置,却无从得知上一个节点的位置(ps:双向链表可以)
如果要单向链表反转,必须使用3个指针变量:
以下代码有一点问题
def invert(head):#为链表的头指针
ptr=head #将ptr指向链表的开头
before=None #before是ptr的前一个节点
last=findlast(head)
while ptr!=None:
last=before #将last接到before之后
before=ptr #将before接到ptr之后
ptr=ptr.next #将ptr移到下一个节点
before.next=last #连接到之前的节点
return before
上一篇: 最大堆、最小堆的构造,利用堆实现数组排序的C++代码
下一篇: Elasticsearch面试