class Node(object):
def __init__(self, value):
# 元素域
self.value = value
# 链接域
self.next = None
class LinkedListOneway(object):
def __init__(self, node=None):
self.__head = node
def __len__(self):
# 游标，用来遍历链表
cur = self.__head
# 记录遍历次数
count = 0
# 当前节点为None则说明已经遍历完毕
while cur:
count += 1
cur = cur.next
return count
def is_empty(self):
# 头节点不为None则不为空
return self.__head == None
def add(self, value):
"""
头插法
先让新节点的next指向头节点
再将头节点替换为新节点
顺序不可错，要先保证原链表的链不断，否则头节点后面的链会丢失
"""
node = Node(value)
node.next = self.__head
self.__head = node
def append(self, value):
"""尾插法"""
node = Node(value)
cur = self.__head
if self.is_empty():
self.__head = node
else:
while cur.next:
cur = cur.next
cur.next = node
def insert(self, pos, value):
# 应对特殊情况
if pos <= 0:
self.add(value)
elif pos > len(self) - 1:
self.append(value)
else:
node = Node(value)
prior = self.__head
count = 0
# 在插入位置的前一个节点停下
while count < (pos - 1):
prior = prior.next
count += 1
# 先将插入节点与节点后的节点连接，防止链表断掉，先链接后面的，再链接前面的
node.next = prior.next
prior.next = node
def remove(self, value):
cur = self.__head
prior = None
while cur:
if value == cur.value:
# 判断此节点是否是头节点
if cur == self.__head:
self.__head = cur.next
else:
prior.next = cur.next
break
# 还没找到节点，有继续遍历
else:
prior = cur
cur = cur.next
def search(self, value):
cur = self.__head
while cur:
if value == cur.value:
return True
cur = cur.next
return False
def traverse(self):
cur = self.__head
while cur:
print(cur.value)
cur = cur.next
def main():
print('this message is from main function')
L=LinkedListOneway()
L.append('2')
# print(Node.next)
L.append('3')
L.append('5')
# print(L.length)
# L.delete(1)
# print(L.getItem(1))
# L.updata(1,9)
# print(L.getItem(1))
# print(L.length)
if __name__ == '__main__':
main()
# print(__name__)
。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。
class Node(object):
def __init__(self,data,pnext=None):
self.data=data
self.next=pnext
def __repr__(self):
return str(self.data)
class ChainTable(object):
def __init__(self):
self.head=None
self.length=0
def isEmpty(self):
return (self.length==0)
def append(self,dataOrNode):
item=None
if isinstance(dataOrNode,Node):
item=dataOrNode
else:
item=Node(dataOrNode)
if not self.head:
self.head=item
self.length+=1
else:
# print(Node.next)
node=self.head
while not node.next is None:
node=Node.next
self.length+=1
def delete(self,index):
if self.isEmpty():
print("aready empty")
return
if index<0 or index>=self.length:
print("error:out of index")
return
if index==0:
self.head=self.head.next
self.length-=1
return
j=0
node=self.head
prev=self.head
while node.next and j<index:
prev=node
node=node.next
j +=1
if j==index:
prev.next=node.next
self.length -=1
def insert(self,index,dataOrNode):
if self.isEmpty():
print("aready empty")
return
if index<0 or index>=self.length:
print("out of index")
return
item=None
if isinstance(dataOrNode,Node):
item=dataOrNode
else:
item=Node(dataOrNode)
if index==0:
item.next=self.head
self.head=item
self.length +=1
return
j=0
node=self.head
prev=self.head
while node.next and j<index:
prev=node
node=node.next
j +=1
if j==index:
item.next=node
prev.next=item
self.length +=1
def updata(self,index,data):
if self.isEmpty() or index <0 or index>=self.length:
print("error: out of index")
return
j=0
node=self.head
while node.next and j<index:
node=node.next
j+=1
if j==index:
node.data=data
def getItem(self,index):
if self.isEmpty() or index<0 or index>=self.length:
print("error ； out of index")
return
j=0
node=self.head
while node.next and j<index:
node=node.next
j+=1
if j==index:
return node.data
def getIndex(self,data):
if self.isEmpty() or index<0 or index>self.length:
print("out of index")
return
j=0
a=[]
node=self.head
while node.next and j<length+1:
if node.data==data:
a.append(j)
return a
def clear(self):
self.head=None
self.length=0
def __repr__(self):
if self.isEmpty():
return "empty chain table"
node=self.head
nlist=''
while node:
nlist +=str(node.data) +' '
node =node.next
return nlist
def __setItem__(self,index,val):
if self.isEmpty() or index<0 or index>=self.length:
print("out of index")
return
self.updata(index,val)
def __len__(self):
return self.length
def __getItem__(self,index):
if isEmpty() or index<0 or index<=self.length:
print("out of index")
return
return self.getItem(index)
def main():
print('this message is from main function')
L=ChainTable()
L.append('2')
# print(Node.next)
L.append('3')
L.append('5')
print(L.length)
L.delete(1)
print(L.getItem(1))
L.updata(1,9)
print(L.getItem(1))
print(L.length)
if __name__ == '__main__':
main()
# print(__name__)
网友评论