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
? ? ? ? # 記錄遍歷次數(shù)
? ? ? ? count = 0
? ? ? ? # 當前節(jié)點為None則說明已經(jīng)遍歷完畢
? ? ? ? while cur:
? ? ? ? ? ? count += 1
? ? ? ? ? ? cur = cur.next
? ? ? ? return count
? ? def is_empty(self):
? ? ? ? # 頭節(jié)點不為None則不為空
? ? ? ? return self.__head == None
? ? def add(self, value):
? ? ? ? """
? ? ? ? 頭插法
? ? ? ? 先讓新節(jié)點的next指向頭節(jié)點
? ? ? ? 再將頭節(jié)點替換為新節(jié)點
? ? ? ? 順序不可錯，要先保證原鏈表的鏈不斷，否則頭節(jié)點后面的鏈會丟失
? ? ? ? """
? ? ? ? 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
? ? ? ? ? ? # 在插入位置的前一個節(jié)點停下
? ? ? ? ? ? while count < (pos - 1):
? ? ? ? ? ? ? ? prior = prior.next
? ? ? ? ? ? ? ? count += 1
? ? ? ? ? ? # 先將插入節(jié)點與節(jié)點后的節(jié)點連接，防止鏈表斷掉，先鏈接后面的，再鏈接前面的
? ? ? ? ? ? node.next = prior.next
? ? ? ? ? ? prior.next = node
? ? def remove(self, value):
? ? ? ? cur = self.__head
? ? ? ? prior = None
? ? ? ? while cur:
? ? ? ? ? ? if value == cur.value:
? ? ? ? ? ? ? ? # 判斷此節(jié)點是否是頭節(jié)點
? ? ? ? ? ? ? ? if cur == self.__head:
? ? ? ? ? ? ? ? ? ? self.__head = cur.next
? ? ? ? ? ? ? ? else:
? ? ? ? ? ? ? ? ? ? prior.next = cur.next
? ? ? ? ? ? ? ? break
? ? ? ? ? ? # 還沒找到節(jié)點，有繼續(xù)遍歷
? ? ? ? ? ? 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__)
