python数据结构:实现单链表的构建和功能操作(自定义)
#创建节点类
class Mode:
'''
思路：将自定义的类视为节点生成类，实例对象中包含
数据部分和指向下一个节点的next
'''
def __init__(self,val,next=None):
self.val=val#存储有用数据
self.next=next#循环下一个节点关系
class LinkList:
'''
单链表类：可以进行增、删、改、查等操 作
具体操作通过调用具体方法完成
'''
def __init__(self):
'''
初始化链表，标记一个链表的开端，便于获取下后续节点
'''
self.head=Mode(None)
#通过list_为链表添加节点
def init_list(self,list_):
p=self.head#p做为移动变量
for item in list_:
p.next=Mode(item)
p=p.next
#遍历链表
def show(self):
p=self.head.next#第一个有效节点
while p is not None:#判断对象时用is 或is not,判断值用==或!=
print(p.val)
p=p.next
#判断链表为空
def is_empty(self):
if self.head.next is None:
return True
else:
return False
#清空链表
def clear(self):
'''
头节点清空认为是清空了，其它元素自动清理
:return:
'''
self.head.next=None
#尾部插入元素
def append(self,val):
p=self.head
while p.next is not None:
p=p.next
p.next=Mode(val)
#头部插入
def head_insert(self,val):
node=Mode(val)#创建新节点
#hend为空它的next指向后一个节点
node.next=self.head.next
#要插入的新节点指向hend后面节点，
# 也不是mext的元素。
# 也就是hend.next内部是下一个节点。
self.head.next=node#再把hend头节点批向新节点。
#指定插入位置
def insert(self,index,val):
'''
中间插入
:param index: 要插入的拉置
:param val: 要插入的值
:return:
'''
p=self.head
for item in range(index):
p=p.next
if p.next is None:
break
#if item==index-1:
#循环后P.next指向了index的位置
node = Mode(val)
node.next=p.next
p.next=node
#按索引删除
def delindex(self,index):
p=self.head
for item in range(index-1):
if p.next is None:
raise Exception("not is this dndex")
p=p.next
p.next=p.next.next#让要删除的元素前面元素的节点连接删除元素下一个节点
#按值删除
def romve(self,val):
p=self.head
while p.next and p.next.val!=val :#p.next相当于p.next is ont None
p=p.next
if p.next is None:#根据短路原则：先判断是不是空，所以上面条件也是要先
#判断p.next为假
raise Exception("没有找到该值")
else:
p.next = p.next.next
#传入节点位置，获取节点值
def get_index(self,index):
p=self.head.next#p指向第一个有用元素即0的位置
for item in range(index):
if p.next is None:
raise IndexError("not is this dndex")
p=p.next#p移到指定位置
return p.val
#修改链表元素
def set_val(self,index,x):
p = self.head.next # p指向第一个有用元素即0的位置
for item in range(index):
if p.next is None:
raise IndexError("not is this dndex")
p = p.next # p移到指定位置
p.val=x
#升序排序
def sort(self):
listsort = []
#判断链表是否为空
while self.head.next is not None:#self.is_empty()==False:
p = self.head.next#实例化对象指向第一个有效元素
numner = p.val#自定义变量初始为第一个元素的值
while p.next is not None:#判断是否到了链表末尾
if numner>p.next.val:
numner=p.next.val
p=p.next
self.romve(numner)#删除最小的这个元素
listsort.append(numner)#把筛选出来的元素加到列表
self.init_list(listsort)#给链表重新赋值
def link_merge(self,l,n):
'''
合并数据
:param l: 第一个链表实例
:param n: 第二个链表实例
:return:
'''
list_mer=[]#用于储存两个链表的值
p=l.head.next
q=n.head
while p.next is not None:#添加第一个链表的值
list_mer.append(p.next.val)
p=p.next
while q.next is not None:#添加第二个链表的值
list_mer.append(q.next.val)
q=q.next
self.init_list(list_mer)#生成一个新的链表