数据结构与算法（Python）[超详细版本] 01-2 线性表-顺序表的操作（或实现）_如何改进线性表插入、删除算法的效率

数据结构的基本运算：

修改、插入、删除、查找、排序

1) 修改

通过数组的下标便可访问某个特定元素并修改之。
核心语句: V[i]=x;

显然，顺序表修改操作的时间效率是 O(1)

2）插入

在线性表的第i个位置前插入一个元素的示意图如下

实现步骤：
将第n至第i 位的元素向后移动一个位置；
将要插入的元素写到第i个位置；
表长加1。
注意：事先应判断: 插入位置i 是否合法?表是否已满?
应当有1≤i≤n+1 或 i=[1, n+1]

核心语句：

//c语言
for (n; j>=i; j--)
     a[j+1]=a[ j ];   // 元素后移一个位置
a[ i ]=x;        // 插入x 
n++;   // 表长加1 

//python 实现
for (j, n, -1)
     a[j+1]=a[ j ];    // 元素后移一个位置
a[ i ]=x;             // 插入x 
n++;                // 表长加1 
1
2
3
4
5
6
7
8
9
10
11
12

时间复杂度

a. 尾端加入元素，时间复杂度为O(1)
b. 非保序的加入元素（不常见），时间复杂度为O(1)
c. 保序的元素加入，时间复杂度为O(n)

3）删除

删除顺序表中某个指定的元素的示意图如下：

删除线性表的第i个位置上的元素

实现步骤：

• 将第i+1 至第n 位的元素向前移动一个位置；
• 表长减1
  注意：事先需要判断，删除位置i 是否合法?是否为空表？应当有1≤i≤n 或 i=[1, n]

核心语句：

//c语言
for ( j=i+1; j<=n; j++ )
    a[j-1]=a[j];    // 元素前移一个位置
n--;                // 表长减1 


//python
for ( j， n  )
    a[j-1]=a[j];    // 元素前移一个位置
n--;               // 表长减1 
1
2
3
4
5
6
7
8
9
10

时间复杂度

a. 删除表尾元素，时间复杂度为O(1)
b. 非保序的元素删除（不常见），时间复杂度为O(1)
c. 保序的元素删除，时间复杂度为O(n)

顺序表的运算效率分析

时间效率分析:

• 算法时间主要耗费在移动元素的操作上，因此 计算时间复杂度的基本操作（最深层语句频度）
  T(n)= O (移动元素次数) 而移动元素的个数取决于插入或删除元素的位置.

讨论1：若在长度为 n 的线性表的第 i 位前 插入一个元素，则向后移动元素的次数f(n)为:
f(n) =n – i + 1

思考：若插入在尾结点之后，则根本无需移动（特别快）；
若插入在首结点之前，则表中元素全部要后移（特别慢）；
应当考虑在各种位置插入（共n+1种可能）的平均移动次数才合理。

Python中的顺序表

Python中的list和tuple两种类型采用了顺序表的实现技术，具有前面讨论的顺序表的所有性质。
tuple是不可变类型，即不变的顺序表，因此不支持改变其内部状态的任何操作，而其他方面，则与list的性质类似。

list的基本实现技术

Python标准类型list就是一种元素个数可变的线性表，可以加入和删除元素，并在各种操作中维持已有元素的顺序（即保序），而且还具有以下行为特征：

基于下标（位置）的高效元素访问和更新，时间复杂度应该是O(1)； 为满足该特征，应该采用顺序表技术，表中元素保存在一块连续的存储区中。
允许任意加入元素，而且在不断加入元素的过程中，表对象的标识（函数id得到的值）不变。为满足该特征，就必须能更换元素存储区，并且为保证更换存储区时list对象的标识id不变，只能采用分离式实现技术。
在Python的官方实现中，**list就是一种采用分离式技术实现的动态顺序表。这就是为什么用list.append(x) （或 list.insert(len(list), x)，即尾部插入）**比在指定位置插入元素效率高的原因。

在Python的官方实现中，list实现采用了如下的策略：在建立空表（或者很小的表）时，系统分配一块能容纳8个元素的存储区；在执行插入操作（insert或append）时，如果元素存储区满就换一块4倍大的存储区。但如果此时的表已经很大（目前的阀值为50000），则改变策略，采用加一倍的方法。引入这种改变策略的方式，是为了避免出现过多空闲的存储位置。