class Node(): #node实现,每个node分为两部分:一部分含有链表元素,成数据域;另一部分为指针,指向下一个 __slots__=['_item','_next'] #限定node实例的属性??? 这个元素就是有两部分组成,,,一个指针一个数据,,,但是链表头就不是这样了 def __init__(self,item): self._item=item self._next=None #node的指针部分默认指向none,这个是单链表,所以每个元素只有一个指针 def getItem(self): return self._item def getNext(self): return self._next def setItem(self,newitem): self._item=newitem def setNext(self,newnext): self._next=newnext class SingleLinkedList(): #单链表,,,,python支持在函数中间定义变量,而且还不用定义类型,随用随取,所以你看见一个变量的时候,就表明此刻就有这个变量了 def __init__(self): self._head=None #初始化为空链表,空链表实际上不包含node,,只有一个空的头 头里面有head指针(用于指向第一个node),有current指针(用于遍历node)??? def isEmpty(self): #检测链表是否为空, return self._head==None def size(self): current=self._head count=0 while current!=None: count+=1 current=current.getNext() return count def travel(self): #输出每个node的值 current=self._head while current!=None: print current.getItem() current=current.getNext() def add(self,item): #在链表端段添加元素 temp=Node(item) #创建一个node, temp.setNext(self._head) #新node的指针,self不再是node而是SingleLinkedList,, self._head=temp #岂不是自己指向自己????搞不懂self???,,这里的self不再是node了,而是SingleLinkedList,,,即单链表是另一个类了,,,这里是单链表类是由node类组成的 def append(self,item): #在链表尾部添加元素 temp=Node(item) #生成一个node(链条上的一个链子) if self.isEmpty(): self._head=temp #若为空表，将添加的元素设为第一个元素,,,,self的head指针指向了新建的元素temp else: current=self._head #current是什么东西??? while current.getNext()!=None: current=current.getNext() #遍历链表 current.setNext(temp) #此时current为链表最后的元素 def search(self,item): #检索元素是否在链表中 current=self._head founditem=False while current!=None and not founditem: #如果我想在a>0或者b>0且a,b不同时大于0的情况下返回True:(a>0 or b>0) and not (a>0 and b>0) if current.getItem()==item: founditem=True else: current=current.getNext() return founditem def index(self,item): #索引元素在链表中的位置 current=self._head count=0 found=None while current!=None and not found: #not优先级大于and大于or and两个都为真才是真 count+=1 if current.getItem()==item: found=True else: current=current.getNext() if found: return count else: raise ValueError,'%s is not in linkedlist'%item def remove(self,item): #删除链表中的某项元素 current=self._head pre=None while current!=None: if current.getItem()==item: if not pre: self._head=current.getNext() else: pre.setNext(current.getNext()) break else: pre=current current=current.getNext() def insert(self,pos,item): #链表中插入元素 if pos<=1: self.add(item) elif pos>self.size(): self.append(item) else: temp=Node(item) count=1 pre=None current=self._head while count<pos: count+=1 pre=current current=current.getNext() pre.setNext(temp) temp.setNext(current) if __name__=='__main__': a=SingleLinkedList() #建立类的对象,,,实际上就是用 SingleLinkedList类扣出了一个蛋糕a,,,就是建链表头的过程 for i in range(1,10): a.append(i) print a.size() a.travel() print a.search(6) print a.index(5) a.remove(4) a.travel() a.insert(4,100) a.travel()
class Node(): #node实现,每个node分为两部分:一部分含有链表元素,成数据域;另一部分为指针,指向下一个
__slots__=['_item','_next'] #限定node实例的属性??? 这个元素就是有两部分组成,,,一个指针一个数据,,,但是链表头就不是这样了
def __init__(self,item):
self._item=item
self._next=None #node的指针部分默认指向none,这个是单链表,所以每个元素只有一个指针
def getItem(self):
return self._item
def getNext(self):
return self._next
def setItem(self,newitem):
self._item=newitem
def setNext(self,newnext):
self._next=newnext
class SingleLinkedList(): #单链表,,,,python支持在函数中间定义变量,而且还不用定义类型,随用随取,所以你看见一个变量的时候,就表明此刻就有这个变量了
def __init__(self):
self._head=None #初始化为空链表,空链表实际上不包含node,,只有一个空的头 头里面有head指针(用于指向第一个node),有current指针(用于遍历node)???
def isEmpty(self): #检测链表是否为空,
return self._head==None
def size(self):
current=self._head
count=0
while current!=None:
count+=1
current=current.getNext()
return count
def travel(self): #输出每个node的值
current=self._head
while current!=None:
print current.getItem()
current=current.getNext()
def add(self,item): #在链表端段添加元素
temp=Node(item) #创建一个node,
temp.setNext(self._head) #新node的指针,self不再是node而是SingleLinkedList,,
self._head=temp #岂不是自己指向自己????搞不懂self???,,这里的self不再是node了,而是SingleLinkedList,,,即单链表是另一个类了,,,这里是单链表类是由node类组成的
def append(self,item): #在链表尾部添加元素
temp=Node(item) #生成一个node(链条上的一个链子)
if self.isEmpty():
self._head=temp #若为空表，将添加的元素设为第一个元素,,,,self的head指针指向了新建的元素temp
else:
current=self._head #current是什么东西???
while current.getNext()!=None:
current=current.getNext() #遍历链表
current.setNext(temp) #此时current为链表最后的元素
def search(self,item): #检索元素是否在链表中
current=self._head
founditem=False
while current!=None and not founditem: #如果我想在a>0或者b>0且a,b不同时大于0的情况下返回True:(a>0 or b>0) and not (a>0 and b>0)
if current.getItem()==item:
founditem=True
else:
current=current.getNext()
return founditem
def index(self,item): #索引元素在链表中的位置
current=self._head
count=0
found=None
while current!=None and not found: #not优先级大于and大于or and两个都为真才是真
count+=1
if current.getItem()==item:
found=True
else:
current=current.getNext()
if found:
return count
else:
raise ValueError,'%s is not in linkedlist'%item
def remove(self,item): #删除链表中的某项元素
current=self._head
pre=None
while current!=None:
if current.getItem()==item:
if not pre:
self._head=current.getNext()
else:
pre.setNext(current.getNext())
break
else:
pre=current
current=current.getNext()
def insert(self,pos,item): #链表中插入元素
if pos<=1:
self.add(item)
elif pos>self.size():
self.append(item)
else:
temp=Node(item)
count=1
pre=None
current=self._head
while count<pos:
count+=1
pre=current
current=current.getNext()
pre.setNext(temp)
temp.setNext(current)
if __name__=='__main__':
a=SingleLinkedList() #建立类的对象,,,实际上就是用 SingleLinkedList类扣出了一个蛋糕a,,,就是建链表头的过程
for i in range(1,10):
a.append(i)
print a.size()
a.travel()
print a.search(6)
print a.index(5)
a.remove(4)
a.travel()
a.insert(4,100)
a.travel()
///////////////////////////////////////////////////////////////////////////
运行结果
:
runfile('E:/pythonprogram/GXTon/main.py', wdir='E:/pythonprogram/GXTon')
9
1
2
3
4
5
6
7
8
9
True
5
1
2
3
5
6
7
8
9
1
2
3
100
5
6
7
8
9