2.2.1 顺序表

  以上定义的函数可在程序设计中引用,例如,上述算法2.2可改写为下列可在主函数中调用的函数。
 
 

  当然,在调用前还需要对元素类型 ElemType 和作为参数的函数 equal() 加以明确定义。
 
  算法
  void purge(SqList &La, SqList Lb)
 {
// 构造顺序表 La,使其只包含 Lb 中所有值不相同的数据元素,
  // 算法不改变顺序表 Lb

  bool b;
  int Lb_len = Listlength( Lb );    // 求线性表 Lb 的长度
  InitList( La,Lb_len );        // 创建一个空的线性表 La
  int La_len = 0;           
  for ( i = 1; i <= Lb_len; i++ )    // 依次处理 Lb 中每个元素
  {
   b = GetElem( Lb, i, e );      // 取Lb中第 i 个数据元素赋给 e
   if ( !LocateElem( La, e, equal( ) ) )
   {
    ++La_len;
    b = ListInsert( La,La_len,e );  // 当 La 中不存在和 e 值相同的
   }                  // 数据元素时,进行插入
  } // for
 } // purge
 




  La 中元素个数不超过 Lb 中的元素个数,故设 La 的最大空间和 Lb 相同。





 学习了下一节讨论的内容之后将容易分析出,此算法的时间复杂度仅取决于操作 LocateElem 的时间复杂度。由于每次插入都在表尾进行,因此 ListInsert 在此函数中实际的时间复杂度是常量级的,而其它操作对顺序表类型而言,显然都是常量级的。