单向双向链表实现
1.顺序表
class SqList:
"""
顺序表
"""
def __init__(self):
self.initcapacity=5
self.capacity=self.initcapacity
self.data=[None]*self.capacity
self.size=0
def Resize(self,newcapacity):
"""
更新链表的容量
"""
assert isinstance(newcapacity,int) and newcapacity>=0
olddata=self.data
self.data=[None]*newcapacity
self.capacity=newcapacity
for i in range(self.size):
self.data[i]=olddata[i]
def CreatList(self,value):
"""
创建链表，将列表value的全部元素放入链表
"""
for i in range(len(value)):
if self.size==self.capacity:
self.Resize(self.capacity+self.initcapacity)
self.data[self.size]=value[i]
self.size+=1
def Add(self,value):
"""
在链表尾部添加单个元素
"""
if self.size==self.capacity:
self.Resize(self.capacity+self.initcapacity)
self.data[self.size]=value
self.size+=1
def GetSize(self):
"""
获取链表的长度
"""
return self.size
def GetElem(self,index):
"""
获取给定索引的值
"""
assert isinstance(index,int)and index>=0
if index>=self.size:
return "索引不存在于链表"
return self.data[index]
def SetElem(self,index,value):
"""
改变给定索引的值
"""
assert isinstance(index,int)and index>=0
if index>=self.size:
return "索引不存在于链表"
self.data[index]=value
def GetNo(self,value):
for i in range(self.size):
if self.data[i]==value:
return i
return "该值在链表中不存在"
def Insert(self,index,value):
"""
在索引为index的位置插入value
"""
assert isinstance(index,int)and index>=0
if index>=self.size:
return "索引不存在于链表"
if self.size+len(value)>self.capacity:
self.Resize(self.size+len(value))
for i in range(len(value)+1):
self.data[self.size+len(value)-1-i]=self.data[self.size-1-i]
self.data[index:index+len(value)]=value
self.size+=len(value)
def Delete(self,index):
"""
删除索引为index的元素
"""
assert isinstance(index,int)and index>=0
if index>=self.size:
return "索引不存在于链表"
for i in range(index,self.size):
self.data[i+1]=self.data[i]
def Display(self):
if self.size==0:
return "链表为空"
for i in range(self.size):
print(self.data[i])# 单向链表节点
class Node(object):
def __init__(self, data, next=None):
self.data = data
self.next = next
# 单向链表
class LinkedList(object):
# 初始化链表，链表为空链表且长度为0
def __init__(self):
self.head = None
self.length = 0
# 将数据从链表的头上插入
def insertat_head(self, newitem):
self.head = Node(newitem, self.head)
self.length += 1
# 将数据从链表的尾部插入
def insertat_end(self, newitem):
if self.head is None:
self.head = Node(newitem, None)
else:
temp = self.head
while temp.next is not None:
temp = temp.next
temp.next = Node(newitem, None)
self.length += 1
# 在任意位置添加
def insertat_anyposition(self, index, newitem):
# 判断index是否为0到n的位置
if index < 0 or index > self.length:
print('index超出范围')
return None # 出错强制停止函数执行
elif index == 0 or self.head is None:
self.head = Node(newitem, None)
else:
temp = self.head
while temp.next is not None and index > 1:
temp = temp.next
index -= 1
temp.next = Node(newitem, temp.next)
self.length += 1
# 在任意位置删除
def delete_at_any_position(self, index):
if self.head is None:
print('链表为空')
return None
elif index < 0 or index > (self.length - 1):
print('index超出范围')
return None
elif index == 0 or self.head.next is None:
removeitem = self.head.data
self.head = None
else:
temp = self.head
while temp.next is not None and index > 1:
temp = temp.next
index -= 1
removeitem = temp.next.data
temp.next = temp.next.next
return removeitem
# 查找元素
def search_target(self, index):
if self.head is None:
print('链表为空')
return None
elif index < 0 or index > (self.length - 1):
print('index超出范围')
return None
else:
temp = self.head
while index > 0:
temp = temp.next
index -= 1
return temp.data
# 打印链表信息
def print_linkedlist(self):
temp = self.head
while temp is not None:
print(temp.data)
temp = temp.next
print('链表长度为%d' % self.length)
2.双向链表的实现
# 双向链表节点
class DNode(object):
def __init__(self, data, pre=None, next=None):
self.data = data
self.pre = pre
self.next = next
# 双向链表
class DLinkedList(object):
def __init__(self):
self.head = DNode(None, None, None)
self.length = 0
def insert_at_any_position(self, index, newitem):
if index > self.length or index < 0:
print('索引超出范围')
return None
elif index == self.length:
temp = self.head
while temp.next is not None:
temp = temp.next
temp.next = DNode(newitem, temp, temp.next)
else:
temp = self.head
while temp.next is not None and index > 0:
temp = temp.next
index -= 1
temp.next = DNode(newitem, temp, temp.next)
temp = temp.next
temp.next.pre = temp
self.length += 1
def delete_at_any_position(self, index):
if index > (self.length - 1) or index < 0:
print('超出索引')
return None
elif self.head.next is None:
print('链表为空')
return None
elif index == self.length - 1:
temp = self.head
while temp.next.next is not None:
temp = temp.next
removeitem = temp.next.data
p = temp.next
temp.next = p.next
else:
temp = self.head
while temp.next.next is not None and index > 0:
temp = temp.next
index -= 1
removeitem = temp.data
p = temp.next
temp.next = p.next
p.next.pre = temp
self.length -= 1
return removeitem
def SearchTarget(self, index):
if index > (self.length - 1) or index < 0:
print("超出索引")
return None
elif self.head.next is None:
print('链表为空')
return None
else:
temp = self.head
while index > 0:
temp = temp.next
index -= 1
return temp.data
def printLinkedList(self):
if self.head.next is None:
print('链表为空')
else:
temp = self.head.next
while temp is not None:
print(temp.data)
temp = temp.next
print('链表长度为%d' % self.length)3.简单栈的实现
# 栈
# 创建节点，data储存数据，next作为连接
class Node(object):
def __init__(self, data=None, next=None):
self.data = data
self.next = next
#创建链子，
class LinkedList(object):
def __init__(self):
self.top = None
# 入栈
def push(self, newitem):
self.top = Node(newitem, self.top)
# 出栈
def pop(self):
if self.top is None:
return None
else:
data = self.top.data
self.top = self.top.next
return data
# 从底部到顶部打印链表元素
def print_stack(self):
temp = self.top
while temp is not None:
print(temp.data)
temp = temp.next3.队列
# 队列，队头出，队尾入
class Node(object):
def __init__(self, data=None, next=None):
self.data = data
self.next = next
# 链表
class LinKQueue(object):
def __init__(self):
self.front = None
self.rear = None
self.length = 0
# 入栈
def push(self, newitem):
if self.front is None and self.rear is None:
self.rear = Node(newitem, None)
self.front = self.rear
else:
self.rear.next = Node(newitem, None)
self.rear = self.rear.next
self.length += 1
# 出栈
def pop(self):
if self.front is None and self.rear is None:
print('队列为空')
else:
remove_item = self.front.data
if self.front is self.rear:
self.rear = None
self.front = None
else:
self.front = self.front.next
self.length -= 1
# 打印队列中的所有信息
def print_queue(self):
if self.rear is None and self.front is None:
print('队列为空')
else:
temp = self.front
while temp is not None:
print(temp.data)
temp = temp.next
print('队列长度为%d' % self.length)4.未改进的KMP算法（链串写法）
# 链串
class Node(object):
def __init__(self, data=None, next=None, link_next=None):
self.data = data
self.next = next
self.link_next = link_next # 用来记录下次开始比较的节点
class LinkString(object):
def __init__(self):
self.head = Node(None, None)
self.length = 0
# 任意位置插入
def insert_link(self, index, new_item):
if index < 0 or index > self.length:
print('超出索引范围')
return None
elif self.head is None:
self.head.next = Node(new_item, None)
else:
temp = self.head
while temp is not None and index > 0:
# 将temp移动到索引处，即index+temp==[index]
temp = temp.next
index -= 1
temp.next = Node(new_item, temp.next)
self.length += 1
def delete_link(self, index):
if self.head is None:
print('链表为空')
return None
elif index < 0 or index > (self.length - 1):
print('超出索引范围')
return None
else:
temp = self.head
while temp is not None and index > 0:
temp = temp.next
index -= 1
remove_data = temp.next.data
temp.next = temp.next.next
self.length -= 1
return remove_data
# 字符串插入系列字符串
def insert_string(self, index, link_str):
for s in link_str:
self.insert_link(index, s)
index += 1
# 比较两个字符串是否相等，相等返回True，不相等返回False
def str_equal(self, t):
if self.length != t.length:
return False
p = self.head.next
q = t.head.next
while p is not None and q is not None:
if p.data != q.data:
return False
else:
p = p.next
q = q.next
return True
# 识别str是否为self的子串，是返回str开始的位置，不是返回-1
def bf_str(self, t):
p = self.head.next
index = 0
while p is not None:
p1 = p
q = t.head.next
while p1 is not None and q is not None and p1.data == q.data:
p1 = p1.next
q = q.next
if q is None:
return index
p = p.next
index += 1
return -1
def print_link(self):
temp = self.head.next
while temp is not None:
print(temp.data)
temp = temp.next
print("长度为%d" % self.length)
# GETNEXT的链串写法
def Get_next(self):
j = self.head.next
k = self.head
while j.next is not None:
if k is self.head or j.data == k.data:
j = j.next
k = k.next
j.link_next = k
else:
k = j.link_next
def Kmp(self, t):
t.Get_next()
i = self.head.next # i作为目标串查找位置
j = t.head.next # j作为模式串查找位置
index = 0 # 记录结果
while i is not None and j is not None:
if j.link_next is None or i.data == j.data:
i = i.next
j = j.next
index += 1
else:
j = j.link_next
if j is None:
return index - t.length
else:
return -1
5.递归生成螺旋数组
# 递归
N = 5
a = [[0] * N for _ in range(N)]
def fun(x, y, start, n):
if n <= 0:
return None
elif n == 1:
a[x][y] = start
return None
else:
for j in range(x, x + n - 1):
a[y][j] = start
start += 1
for i in range(y, y + n - 1):
a[i][x + n - 1] = start
start += 1
for j in range(x + n - 1, x, -1):
a[y + n - 1][j] = start
start += 1
for i in range(y + n - 1, y, -1):
a[i][x] = start
start += 1
fun(x + 1, y + 1, start, n - 2)
n = 4
fun(0, 0, 1, n)
for i in range(N):
for j in range(N):
print(a[i][j])
print('\n')