# coding: utf-8
# time: 2020-1-15
class Node:
def __init__(self, cur, va=None):
# 值
self.val = va
# 游标。最后一个元素的游标必须是0
self.cur = cur
class linkList:
# 分配线性表长度、定义线性表
def __init__(self):
self.MAX_SIZE = 7
self.node = list()
for i in range(self.MAX_SIZE):
if i == 0:
self.node.append(Node(1))
elif i == self.MAX_SIZE-1:
self.node.append(Node(0))
else:
self.node.append(Node(i+1))
# 线性表清空
def clearList(self):
self.__init__()
# 线性表是否为空
def emptyList(self):
if self.node[self.MAX_SIZE-1].cur == 0:
return True
return False
# 查找线性表某位置的元素
def getElem(self, ind):
if ind < 1 or ind >= self.MAX_SIZE-1:
return -1
index = self.node[self.MAX_SIZE-1].cur
if index == 0:
return -1
for i in range(1, ind):
index = self.node[index].cur
return self.node[index].val
# 查找线性表的元素所在位置
def locateElem(self, ele):
index = self.node[self.MAX_SIZE-1].cur
ind = -1
if index == 0:
return ind
for i in range(1, self.MAX_SIZE-1):
if self.node[index].val == ele:
ind = i
break
if self.node[index].val is None:
break
index = self.node[index].cur
return ind
# 查找空位置
def findEmpty(self):
ind = self.MAX_SIZE
for i in range(1, self.MAX_SIZE-1):
if self.node[i].val is None:
ind = i
break
return ind
# 指定位置插入元素
def listInsert(self, ind, ele):
sua = 0
# 前一个元素
pre = self.MAX_SIZE-1
# 插入元素的位置（第一个空位置）
insertLoc = self.node[0].cur
# 条件判断
if ind < 1 or ind >= pre or insertLoc >= self.MAX_SIZE:
return 0
# 第一个元素的索引
for i in range(1, self.MAX_SIZE-1):
index = self.node[pre].cur
if i == ind:
self.node[pre].cur = insertLoc
# 元素插入
self.node[insertLoc].val = ele
self.node[insertLoc].cur = index
# 首位元素
self.node[0].cur = self.findEmpty()
sua = 1
break
if self.node[index].val is None:
break
pre = index
return sua
# 删除线性表指定位置的元素
def deleteElem(self, ind):
sua = 0
# 前一个索引
pre = self.MAX_SIZE - 1
for i in range(1, self.MAX_SIZE-1):
index = self.node[pre].cur
# 当前位置是个空位置
if self.node[index].val is None:
break
# 已经遍历到第i个位置
if i == ind:
self.node[pre].cur = self.node[index].cur
self.node[index].val = None
# 删除元素的游标指向备用链表
self.node[index].cur = self.node[0].cur
# 首位元素
self.node[0].cur = index
sua = 1
break
pre = index
return sua
# 按照线性表排序线性表遍历
def travelLink(self):
print("====================================")
index = self.node[self.MAX_SIZE-1].cur
while True:
if self.node[index].val is None:
break
print("va==", self.node[index].val, "; ind==", self.node[index].cur)
index = self.node[index].cur
print("====================================")
# 按照索引遍历
def travel(self):
print("******************************************")
for i in range(0, self.MAX_SIZE):
print("i==", i, "; va==", self.node[i].val, "; ind==", self.node[i].cur)
print("******************************************")
if __name__ == '__main__':
ll = linkList()
print(ll.travel())
print(ll.emptyList())
print(ll.listInsert(1, 'B'))
# ll.travelLink()
print(ll.listInsert(2, 'Bs'))
# ll.travelLink()
print(ll.listInsert(1, 'BsA'))
print(ll.listInsert(4, 'BcA'))
# ll.travelLink()
# ll.travel()
print(ll.deleteElem(3))
ll.travel()
ll.travelLink()
print(ll.emptyList())
print(ll.getElem(2))
print(ll.locateElem('BcA'))
print(ll.clearList())
|
