当前位置:   article > 正文

删除顺序表中指定元素的两种方法的比较_删除顺序表中指定值的所有元素

删除顺序表中指定值的所有元素

eg:假设一个线性表采用顺序表表示,设计一个算法,删除其中所有值等于x的元素,要求算法的时间复杂度为O(n),空间复杂度为O(1)。

解法一:整体建表法

   设删除L中所有值等于x的元素后的顺序表为L1,显然L1包含在L中,为此L1重用L的空间。遍历顺序表L,重建L只包含不等于x的元素。算法的过程是置k=0(k用于记录新表中元素的个数),用i从左到右遍历L中的所有元素,当i指向的元素为x时跳过它;否则将其放置在k的位置,即L->data[k]=L->data[i],k++。最后重置L的长度为k,算法如下:

  1. void delnode1(SqList*& L, ElemType x)
  2. {
  3. int k = 0, i; //k记录不等于x的元素的个数,即保留的元素个数
  4. for (i = 0; i < L->length; i++)
  5. {
  6. if (L->data[i] != x) //若当前元素不为x,将其插入L中
  7. {
  8. L->data[k] = L->data[i];
  9. k++; //插入一个元素时元素的个数增1
  10. }
  11. }
  12. L->length = k; //顺序表L的长度等于k
  13. }

解法二:元素移动法

   用i从左到右遍历L中的所有元素,用k记录L中当前等于x的元素的个数,一边遍历L一边统计当前k值。当i指向的元素为x时k增1;否则将不为x的元素前移k个位置,即L->data[i-k]=L->data[i]。最后将L的长度减少k。算法如下:

  1. void delnode2(SqList*& L, ElemType x)
  2. {
  3. int k = 0, i = 0; //k记录等于x的元素的个数,即要删除的元素个数
  4. while (i < L->length)
  5. {
  6. if (L->data[i] == x) k++; //当前元素为x时k增1
  7. else L->data[i - k] = L->data[i]; //当前元素不为x时将其前移k个位置
  8. i++;
  9. }
  10. L->length -= k; //顺序表L的长度递减k
  11. }

整体建表法和元素移动法的异同:

同:在遍历数组的同时对每个值进行判断,在判断后执行相应的操作,在遍历完成的同时也完成了对新的顺序表的重建。

异:k的统计对象不同。

  整体建表法的k统计的是线性表中不为x的元素的个数,因此在遍历结束后可直接作为改动后线性表的长度。

  元素移动法的k统计的是等于x的元素的个数,因此需与原线性表长度相减后才可作为改动后线性表的长度。

声明:本文内容由网友自发贡献,不代表【wpsshop博客】立场,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:https://www.wpsshop.cn/w/Li_阴宅/article/detail/889435
推荐阅读
相关标签
  

闽ICP备14008679号