Python 学习:单链表的实现

3218阅读　0评论2012-02-08　wenhaoz
分类：Python/Ruby

要定义一个单链表,首先定义链表元素:Element.它包含3个字段:
list:标识自己属于哪一个list
datum:改元素的value
next:下一个节点的位置
  1. class LinkedList(object):
  2.     
  3.     class Element(object):
  4.         
  5.         def __init__(self,list,datum,next):
  6.             self._list = list
  7.             self._datum = datum
  8.             self._next = next

  10.         def getDatum(self):
  11.             return self._datum

  13.         datum = property(
  14.             fget = lambda self: self.getDatum())

  16.         def getNext(self):
  17.             return self._next

  19.         next = property(
  20.             fget = lambda self: self.getNext())


  23.     def __init__(self):

  25.         self._head = None
  26.         self._tail = None
  27.     def getHead(self):
  28.         return self._head
  29.     head = property(
  30.         fget = lambda self: self.getHead())
  31.     def prepend(self,item):
  32.         tmp = self.Element (self,item,self._head)
  33.         if self._head is None:
  34.             self._tail = tmp
  35.         self._head = tmp

  37.     def insert(self, pos, item):
  38.         i = 0
  39.         p = self._head
  40.         while p != None and i < pos -1:
  41.             p = p._next
  42.             i += 1
  43.         if p == None or i > pos-1:
  44.             return -1
  45.         tmp = self.Element(self, item, p._next)
  46.         p._next = tmp
  47.         return 1
  48.     def getItem(self, pos):
  49.         i = 0
  50.         p = self._head
  51.         while p != None and i < pos -1:
  52.             p = p._next
  53.             i += 1
  54.         if p == None or i > post-1:
  55.             return -1
  56.         return p._datum
  57.     def delete(self, pos):
  58.         i = 0
  59.         p = self._head
  60.         while p != None and i < pos -1:
  61.             p = p._next
  62.             i += 1
  63.         if p == None or i > post-1:
  64.             return -1
  65.         q = p._next
  66.         p._nex = q._next
  67.         datum = p._datum
  68.         return datum
  69.     def setItem(self, pos, item):
  70.         i = 0
  71.         p = self._head
  72.         while p != None and i < pos -1:
  73.             p = p._next
  74.             i += 1
  75.         if p == None or i > post-1:
  76.             return -1
  77.         p._datum = item
  78.         return 1
  79.     def find(self, pos, item):
  80.         i = 0
  81.         p = self._head
  82.         while p != None and i < pos -1:
  83.             if p._datum == item:
  84.                 return 1
  85.             p = p._next
  86.             i += 1
  87.         return -1
  88.     def empty(self):
  89.         if self._head == None:
  90.             return 1
  91.         return 0
  92.     def size(self):
  93.         i = 0
  94.         p = self._head
  95.         while p != None and i < pos -1:
  96.             p = p._next
  97.             i += 1
  98.         return i

  100.     def clear(self):
  101.         self._head = None
  102.         self._tail = None


  105. test = LinkedList()
  106. test.prepend('test0')
  107. print test.insert(1, 'test')
  108. print test.head.datum
  109. print test.head.next.datum
上一篇：php实现树状结构无级分类
下一篇：求PI的近似值，用公式PI/4=1-1/3+1/5-1/7+...