线性结构－线性表

编译环境：python v3.5.0, mac osx 10.11.4

线性表的表示

<big>例如：</big>表示一个多项式Multinomial
<big>最</big>浪费的表示方法：f(x)=4x^5-3x2+1,浪费大量的存储空间（若多项式指数差异很大，即很多存储单元都空着,为0）

• 数组（计算机内连续的存储单元）表示多项式

• 其下标表示指数，数组中存放的数值表示系数

  
  

结构数组存储非零项:P1(x)= 9x^12+15x8+3x^2

• 构造结构数组（计算机内连续的存储单元）表示多项式。结构数组中单元列表第一位为系数，第二位为指数。
  class Multinomial(): # 定义多项式结构数组
  def init(self,coef,expon):
  self.coef = coef
  self.expon = expon
  

链表结构存储非零项:P1(x)= 9x^12+15x8+3x^2

• 链表（单元随机存储于计算机中）每个节点存储多项式的非零项
• 存储单元包含三个小单元用来存储系数、指数、和下一个链表单元的地址。
  class Multinomial():
  def init(self,chef,expon,link):
  self.coef = coef
  self.expon = expon
  self.link = None
  

什么是线性表

通过上述例子实践，我们可以发想线性表（Linear List）有如下几个特征：

1. 它是由同类型数据元素构成有序序列的线性结构
2. 表中元素的个数称为线性表的长度
3. 线性表没有元素时，称为空表
4. 表的起始位置称为表头，表的结束位置称为表尾

线性表的顺式存储（数组）实现

• List MakeEmpty():初始化一个空的线性表L；
  L = []
• ElementType FindKth(int K, List L):根据位序K，返回相应的元素；
  element = L[k]
• int Find(ElementType X, List L):在线性L中查找X的第一次出现的位置；
  def Find(x,list):
  i = 0
  while x != list[i] and i < len(list):
  i += 1
  if i == len(list): ＃ 若果没有找到返回 －1
  return -1
  else: ＃ 找到返回下标
  return i

• void Insert(ElementType X, int i, List L):在位序i前插入一个元素X；
  L.insert(index,x)

  
  

• void Delete(int i, List L):删除指定位序i的元素；
  del L[i]

  
  
• int Length(List L):返回线性表长度n；
  n = Length(L)

线性表的链式存储（链表）实现

• List MakeEmpty():初始化一个空的线性表L；
  class chainList():
  def init(self, value=None, Next=None): # 空表表头
  self.Value = value
  self.Next = next

     L = chainList()
  

• ElementType FindKth(int K, List L):根据位序K，返回相应的元素；
  def FindKth(k, chain_list):
  index = 0 # 起始序列号为0
  element = chain_list ＃ 将指针指向第一个链表单元
  while index != k and element.Next is not None : ＃ 若找到k，或者到表尾，循环退出
  index += 1
  element = element.Next
  if index == k : ＃ 找到返回元素的值
  return element
  else: ＃ 没有返回 None
  return None

• int Find(ElementType X, List L):在线性L中查找X的第一次出现的位置；
  def Find(x,chain_list):
  index = 0 # 起始序列号为0
  element = chain_list # 将指针指向第一个链表单元
  while element.Value != x and element.Next is not None: # 若找到x，或者到表尾，循环退出
  index += 1
  element = element.Next
  if element.Value == x : # 找到返回元素的值
  return index
  else: # 没有返回 None
  return None

• void Insert(ElementType X, int i, List L):在位序i前插入一个元素X；
  def Insert(x,index ,chain_list):
  element= chainList(x) # 生成新节点
  if index == 0 : # 遇到头节点的话则直接插入到头节点前
  element.Next = chain_list
  return element
  elementBefore = FindKth(index-1, chain_list) ＃ 查找序列前一个节点
  if elementBefore is not None:
  temp = elementBefore.Next
  elementBefore.Next = element ＃将新节点插在index－1节点后
  element.Next = temp ＃ 将原来的index节点插在新节点后
  del temp # 释放内存
  return chain_list ＃ 返回头指针
  else:
  return ‘参数错误'

  
  

• void Delete(int i, List L):删除指定位序i的元素；
  def Delete(index,chain_list):
  if index == 0: # 遇到头节点的话则直接删除头节点
  p = chain_list.Next
  del chain_list
  return p
  elementBefore = FindKth(index-1, L) ＃ 查找序列前一个节点
  if elementBefore is not None:
  temp = elementBefore.Next # 将指针指向要删除的节点
  elementBefore.Next = temp.Next ＃将index－1节点指向index＋1节点
  del temp # 释放内存
  return chain_list #返回头指针
  else:
  return ‘参数错误'

  
  

• int Length(List L):返回线性表长度n；
  def Length(chain_list):
  p = chain_list ＃ p 指向第一个节点
  count = 0
  while p.Next is not None: ＃ p不断指向下一个节点
  count += 1
  p = p.Next
  return count

源代码: GitHub
<big>后续内容：

• 队列
• 堆栈
• 线性结构相关算法