数据结构与算法基础——第02周-线性表的顺序表示和实现-删除算法(2.4.6)

发表于 分类于 ， ， 阅读时长 ≈ 1 分钟

一 概述

  • 顺序表的删除—删除不同位置演示
  • 顺序表的删除—算法思想
  • 顺序表的删除—代码实现
  • 顺序表的删除—算法分析

二 顺序表的删除—删除不同位置演示

三 顺序表的删除—算法思想

3.1 删除描述

  • 线性表的删除运算是指将表的第i(1<=i<=n)个结点删除
  • 使长度为n的线性表(a1,...ai-1,ai,ai+1,...,an)
  • 变成长度为n-1的线性表(a1,..ai-1,ai+1,...an)

3.2 算法思想

  1. 判断删除位置i是否合法(合法值为1<=i<=n)
  2. 将欲删除的元素保留在e中
  3. 将第i+1至第n位的元素依次向前移动一个位置
  4. 表长减1，删除成功后返回OK

四 顺序表的删除—代码实现

1
2
3
4
5
6
7
8
Status ListDelete_Sq(SqList &L,int i)
{
	①if((i<1)||(i>L.length)) return ERROR;  //i值不合法
	②for(j=i;j<=L.length-1;j++)
	 L.elem[j-1]=L.elem[j];                //被删除元素之后的元素迁移
	③L.length--;
    return OK;
}

五 顺序表的删除—算法分析

算法时间主要耗费在移动元素的操作上

  • 若删除尾结点，则根本无需移动(特别快)
  • 若删除首结点，则表中n-1个元素全部前移(特别慢)
  • 若要考虑在各种位置删除(共n种可能)的平均移动次数，该如何计算？
    Edel=1/n*∑ni=1*(n-1)=1/n*(n-1)*n/2=(n-1)/2
  • 顺序表删除算法的平均时间复杂度为O(n)