# !/usr/bin/env python# -*- coding: utf-8 -*- __author__ = 'MrHero'  class Node(object):  """  線性表的存儲結構  和 C 語言中的鏈式存儲結構類似  """  def __init__(self, data=None):    self.data = data    self.next = None  class LKList(object):  """  線性表的具體操作  """   def __init__(self):    """    相當于初始化線性表, 即創建頭結點    頭節點為空節點，占據位置號為0    創建好的表即為: 頭節點[0]->節點[1]->節點[2]->節點[3]->節點[4]    :return:    """    self.L = Node(None)    self.L.next = None    self.length = 0   def is_empty(self):    """    判斷線新表的長度    :return:    """    return self.length == 0   def get_length(self):    """    獲取線新表的長度    :return:    """    return self.length   def insert(self, i, elem):    """    在指定位i處置插入元素elem    :param i: 指定的位置    :param elem: 插入的元素elem    :return:    """    j = 0    p = self.L    while j < i-1 and p is not None: # 查找第 i-1 個節點      j += 1      p = p.next    if p is None:  # 未找到邏輯位序為 i-1 的節點      raise IndexError("Index is out of range!")    else:  # 找到邏輯位序為 i-1 的節點      tmp = Node(elem)      tmp.next = p.next      p.next = tmp      self.length += 1   def delete(self, i):    """    刪除指定節點的元素    :param i: 指定節點    :return: 刪除的指定節點元素值    """    if self.is_empty():      raise IndexError("The list is empty!")    elif 0 < i <= self.length:      j = 1      p = self.L      while j < i and p:        p = p.next        j += 1      delelte_node = p.next      p.next = delelte_node.next      self.length -= 1      return delelte_node.data    else:      raise IndexError("Index is out of range!")   def get_elem(self, i):    """    獲取某個節點的值    :param i:    :return:返回某個節點的值    """    if self.is_empty():      raise IndexError("The list is empty")    elif 0 < i <= self.length:      j = 0      p = self.L      while j < i and p:        p = p.next        j += 1      print p.data    else:      raise IndexError("Index is out of range!")   def locate_elem(self, elem):    """    查找某值的位置    :param elem:    :return: 返回第一個值等于elem的位置    """    j = 0    p = self.L    while p is not None and p.data != elem:      p = p.next      j += 1    if p is Node:      return -1    else:      return j   def create_dict_list_H(self, list):    """    頭插法建表    :param list:    :return:    """    p = self.L    for i in range(len(list)):      tmp = Node(list[i])      tmp.next = p.next      p.next = tmp      self.length += 1   def create_dict_list_E(self, list):    """    尾插法建表    :param list:    :return:    """    p = self.L    r = p    for i in range(len(list)):      tmp = Node(list[i])      r.next = tmp      r = tmp      self.length += 1    r.next = None   def show_lklist(self):    if self.is_empty():      raise IndexError("It's a empty list!")    else:      j = 1      p = self.L      while j <= self.length and p:        p = p.next        if p is not None:          print p.data        j += 1  if __name__ == '__main__':  lk = LKList()  #  # lk.create_dict_list_E([1, 2, 3, 4])  # print "-----"  # lk.get_elem(1)  # lk.get_elem(2)  # lk.get_elem(3)  # lk.get_elem(4)  # print "-------"  # lk.show_lklist()  # lk.insert(3, 5)  # print "-------"  # lk.show_lklist()  # lo = lk.locate_elem(5)  # print "location is %d" % lo  # lk.delete(4)  # print "-------"  # lk.show_lklist()